Устройство для выделения эффективных решений Советский патент 1992 года по МПК G06F15/419 

Изобретение относится к области вычислительной техники и может быть использовано для решения многокритериальных задач исследования операций, а именно при выборе парето-оптимальных вариантов

Известно устройство, предназначенное для решения задач многокритериальной (векторной) оптимизации и обеспечивающее определение обобщенного показателя эффективности многокритериальных задач. Однако это устройство не позволяет выделять из множества вариантов парето-опти- мальные решения.

Наиболее близким по технической сущности к заявляемому устройству является устройство для выбора оптимальных решений, содержащее блок сравнения, блок памяти векторов исходной информации, группу блоков задания показателей, группу блоков задания допусков, группу блоков памяти показателей, группу сумматоров, две

группы блоков деления, две группы квадраторов, первый и второй сумматоры.

Данное устройство обеспечивает свертку векторной информации в скалярные величины и выбор по ним решения, соответствующего лучшему в субъективно принятом смысле набору показателей. Однако это устройство также не позволяет выделять из исходной векторной информации множество парето-оптимальных решений.

Цель изобретения - расширение класса решаемых задач за счет выделения парето- оптимальных решений.

На чертеже приведена функциональная схема устройства.

Устройство содержит блок 1 формирования адреса, блок 2 памяти векторов исходной информации, блок 3 сравнения, первый 4 и второй 5 дешифраторы, вход 6 запуску устройства, выход 7 признака окончания решения.

VJ

сл

00

о сл со

Блок 1 формирования адреса предназначен для формирования управляющих сигналов в соответствии с реализуемым алгоритмом. Блок имеет пять управляющих входов, два информационных и один управляющий выход. При поступлении сигналов на первый, второй и пятый управляющий входы блока значение сигнала на первом информационном выходе увеличивается на единицу, на втором информационном выходе становится на единицу большим, чем стало на первом информационном выходе. Кроме того, в блоке формируется управляющий импульс, поступающий с его управляющего выхода на управляющий вход блока сравнения. При поступлении импульсов на третий или четвертый управляющий входы увеличивается на единицу значение на втором информационном выходе, и, если это значение не стало равным (М+1), то появляется импульс на управляющем выходе блока.

Возможная функциональная схема блока задания адреса приведены на фиг. 1. Блок 1 содержит первый 8 и второй 9 элементы ИЛИ, первый 10 и второй 11 счетчики, генераторы одиночных импульсов 12,13, элемент И 14, элементы задержки 15, 16.

Блок 2 памяти векторов исходной информации предназначен для хранения векторов исходной информации, выдачи значений пары очередных векторов для поэлементного сравнения и обнуления значений векторов, не принадлежащих подмножеству парето-оптммальных решений.

Блок содержит М элементов памяти 17i,

17м (где М - количество векторов

исходной информации), каждый из которых содержит элемент ИЛ И 18, первый 19 и второй 20 элементы И, регистры 211,21221Р

(р - количество компонент в векторах), первый 22 и второй 23 ключи, первый 24 и второй 25 разделительные диоды. Каждый элемент памяти имеет четыре управляющих входа и две группы информационных выходов. Первый и четвертый управляющие входы соответственно объединены у всех элементов памяти. Второй управляющий вход всех элементов памяти соединен с соответствующим выходом первого дешифратора, а третий управляющий вход всех элементов памяти соединен с соответствующими выходами второго дешифратора. При наличии сигнала уровня логической единицы на втором управляющем входе содержимое регистров данного элемента памяти поступает через ключ 22 на первую группу информационных выходов, а при наличии сигнала уровня логической единицы

на третьем управляющем входе содержимое регистров элементов памяти поступает через ключ 23 на вторую группу информационных выходов элемента памяти. Поступление импульса на первый или четвертый управляющий входы при условии наличия сигнала уровня логической единицы на втором или третьем управляющем входе приводит к обнулению содержимого регистров

данного элемента памяти.

Блок 3 сравнения предназначен для сравнения компонент очередных векторов и формирования управляющих сигналов на управляющих выходах блока. Блок 3 содержит схемы сравнения 26i, 262, .... 26Р, первую и вторую группу элементов ИЛИ 27i,

27227Р и 28|„ 28229Р, элемент ИЛИНЕ 30, элемент И 31,32,33 и элемент задержки 34. Если значение k-той компоненты,

поступающей на первый информационный вход схемы сравнения 26.меньше k-той компоненты, поступающей на второй информационный вход этой схемы сравнения, то на ее признаковом выходе появляется сигнал

уровня логической единицы, в противном случае сигнал на признаковом выходе имеет уровень логического нуля.

Устройство работает следующим образом. Перед началом решения значения компонент исходных векторов заносятся в регистры 21k, к 1, Р элементов памяти 17s. S 1,7й и обнуляются счетчики 10, 11 блока 1 задания адреса.

Решение начинается подачей импульса уровня логической единицы на вход 6 запуска устройства. При этом импульс входа 6 запуска поступает на первый управляющий вход блока 1 задания адреса. С первого управляющего входа сигнал поступает на вход элемента ИЛИ 18, а с его выхода - на вход генератора одиночных импульсов 12. Гене- рагор формирует импульс, длительность которого достаточна для срабатывания

счетчиков 10, 11, этот импульс поступает с выхода генератора 12 на счетный вход счетчика 10 и вход элемента задержки 15. Содержимое счетчика 10 увеличивается на единицу (в начале первого шага решения

становится равным единице). Информационные выходы счетчика 10 соединены с информационными входами счетчика 11, поэтому, когда через ri - время задержки элемента 15 сигнал с выхода элемента задержки поступает на вход записи счетчика 11, содержимое счетчика 10 записывается в счетчик 11. Кроме того, импульс с выхода элемента задержки 15 поступает на вход элемента ИЛИ 9, а с его выхода - на вход генератора одиночных импульсов 13, который через время задержки тг формирует управляющий импульс, поступающий на счетный вход счетчика 11 и вход элемента задержки 16. При этом содержимое счетчика 11 увеличивается на единицу и становится равным на первом шаге решения двум. Коды содержимого счетчиков 10, 11 через информационные выходы блока 1 задания адреса поступают на входы первого и второго дешифраторов Л и 5.

При этом появляются сигналы уровня логической единицы на первом выходе дешифратора 4 и втором выходе дешифратора 5. Эти сигналы поступают на второй управляющий вход элемента памяти 17i и третий управляющий вход элемента памяти 172. При этом в элементе памяти 17i сигнал поступает на вход элемента ИЛИ 18, один вход элемента И 19 и управляющий вход ключа 22, информационные цепи которого при этом замыкаются. С выхода элемента ИЛИ 18 сигнал поступает на объединенные считывающие входы регистров 21i«, k 1, Р элемента памяти 17i и значения компонент первого вектора с выходов регистров этого элемента памяти поступают через информационные цепи ключа 22 на соответствующие входы элементов ИЛИ 27k, k 1, Р блока 2 сравнения. В элементе памяти 172 сигнал с дешифратора 5 поступает на вход элемента ИЛИ 18, один вход элемента И 20 и на управляющий вход ключа 23, информационные цепи которого при этом замыкаются. С выхода элемента ИЛИ 18 сигнал поступает на объединенные считывающие входы регистров 21и, k 1, Р и содержимое компонент второго вектора с выходов регистров через информационные цепи ключа 23 элемента памяти 172 поступает на соответствующие входы элементов ИЛИ 28k, k 1. Р блока 2 сравнения.

С выходов элементов ИЛИ 27k, 28k, k 1, Р значения соответствующих компонент первого и второго векторов поступают соответственно на первый и второй информа- ционные входы схем сравнения 26k, k 1, Р.

Через Т2 - время задержки элемента задержки 16 импульс с его выхода через элемент И 14 поступает на управляющий вход блока 2 сравнения, а с него - на объединенные управляющие входы схем сравнения 26k, k 1, Р и вход элемента задержки 34. При этом в схемах сравнения осуществляется сравнение значений компонент первого и второго векторов, если k-ая компонента первого вектора меньше k-ой компоненты второго вектора, то на признаковом выходе k-ой схемы сравнения появляется сигнал уровня логической единицы, в

противном случае сигнал на признаковом выходе будет иметь уровень логического нуля. Через гз - время задержки элемента задержки 34, сигнал с его выхода поступает

на входы элементов И 31, 32. 33.

Дальнейшая работа устройства зависит от результатов сравнения компонент очередных векторов. При этом возможны три варианта, которые рассмотрим на примере

сравниваемых на первом шаге решения компонент первого и второго векторов.

Первый вариант. Если все компоненты первого вектора меньше соответствующих компонент второго вектора, то единичные

сигналы с выходов схем сравнения 26k, k 1, Р поступают на все входы элементов И 29 и ИЛИ-НЕ 30. При этом сигнал уровня логической единицы с выхода элемента И 29 подается на вход элемента И 31 и инверсный

вход элемента И 33, поэтому сигнал с выхода элемента задержки 34 поступает через элемент И 31 на объединенные первые входы элементов памяти 17s, S 1, М и на второй управляющий вход блока 1 задания

адреса. Сигнал с первого управляющего входа элементов памяти поступает на вход элементов И 19 всех элементов памяти. Так как на втором входе элемента И 19 присутствует сигнал только в элементе памяти 17ь

то сигнал с выхода элемента И 19 этого элемента памяти через разделительный ди- од.24 поступает на объединенные входы обнуления регистров 21 k, k 1, Р и содержимое этих регистров обнуляется. На этом заканчивается первый шаг решения и на втором уже будет осуществляться сравнение второго вектора с третьим.

Второй вариант. Если все компоненты первого вектора больше, или равны соответствующим компонентам второго вектора, то на признаковых выходах всех схем сравнения будет сигнал уровня логического нуля и тогда сигнал с выхода элемента ИЛИ-НЕ 30 поступает на один из входов элемента И 32.

Сигнал с выхода элемента задержки 34 поступает на объединенные входы элементов памяти 17s, S 1, М и на четвертый управляющий вход блока 1 задания адреса. Сигнал с четвертых управляющих входов

элементов памяти поступает на вход элементов И 20. Так как на втором входе элемента И 20 на первом шаге решения будет присутствовать сигнал только в элементе памяти 172, то с выхода элемента И 20 сигнал через разделительный диод 25 поступает на объединенные входы обнуления регистров 21 k, k 1, Р и содержимое регистров элемента памяти 172 обнуляется. На этом шаг решения заканчивается и начинается следующий, на котором будет осуществляться сравнение компонент первого и третьего векторов.

Третий вариант. Если условия для рассмотренных выше первого и второго вариантов на первом шаге решения не реализуются, то к моменту поступления импульса с выхода элемента задержки 34 на выходах элементов 29 и 30 будут сигналы уровня логического нуля и импульс с выхода элемента задержки 34 через элемент И 33 поступает на третий управляющий вход блока 1 задания адреса. На этом шаг решения заканчивается и начинается следующий шаг, на котором будет осуществляться сравнение компонент первого и третьего векторов.

Работа устройства на последующих шагах решения будет аналогична выше рассмотренному первому шагу, за тем исключением, что если в начале очередного шага содержимое счетчика 11 станет равным (М+1). то сигнал с (М+1)-го выхода второго дешифратора 5 поступит на пятый вход блока 1 задания адреса и начинается другой шаг решения. Поступление сигнала с пятого управляющего входа на инверсный вход элемента И 14 исключает преждевременное прохождение импульса от генератора одиночных импульсов 13 на управляющий выход блока.

Решение заканчивается при достижении содержимого счетчика 10 в начале очередного шага решения значения М, при этом сигнал с М-го выхода первого дешифратора 4 поступает на выход 7 признака окончания решения. Множество парето-оп- тимальных решений, выделенных в результате работы устройства, однозначно определены содержимым необнуленных элементов памяти 17s. S ТГЖ

Таким образом, предлагаемое устройство обеспечивает за R шагов решения (М R 0.5М (М - 1)) выделение парето- оптимальных решений из исходного множества векторов исходной информации, что свидетельствует о существенном расширении класса решаемых задач многокритериальной оптимизации и достижении цели изобретения.

Формула изобретения Устройство для выделения эффективных решений, содержащее блок сравнения, блок памяти векторов исходной информации, первая группа выходов блока памяти векторов исходной информации подключена к первой группе информационных входов блока сравнения, первый выход которого подключен к первой группе входов разрешения обнуления блока памяти векторов исходной информации, отличающееся тем, что, с целью расширения класса решаемых задач за счет выделения парето-опти- мальных решений, дополнительно введены

первый и второй дешифраторы, блок формирования адреса, первый управляющий вход которого является входом запуска устройства, входы первого и второго дешифраторов подключены соответственно к первому и

0 второму информационным выходам блока формирования адреса, группы выходов соответственно к первой и второй группам входов разрешения считывания блока памяти векторов исходной информации, один из

5 выходов первого дешифратора является вы- ходом признака окончания решения устройства, а управляющий выход второго дешифратора подключен к второму управляющему входу блока формирования адре0 са, третий, четвертый и пятый управляющие входы которого соответственно подключены к первому, второму выходам блока сравнения и к второй группе входов разрешения обнуления блока памяти векторов исходной

5 информации, третьему выходу блока сравнения, а управляющий выход - к управляющему входу блока сравнения, вторая группа информационных входов которого подключена к второй группе выходов блока памяти

0 векторов исходной информации, причем блок памяти векторов исходной информации содержит элементы памяти по числу векторов исходной информации, первый и четвертый, второй и третий входы элемен5 тов памяти образуют соответственно первые и вторые группы входов разрешения обнуления и разрешения считывания блока, а первая и вторая группы выходов - соответственно первую и вторую группы выходов

0 блока, причем каждый элемент памяти содержит первый и второй элементы И, элемент ИЛИ, первый и второй разделительные диоды, регистры по числу компонент в векторе исходной информации, первый и вто5 рой блоки ключей, выходы которых являются соответственно первой и второй группами выходов элемента памяти, группы информационных входов подключены соответственно к выходам регистров, а управля0 ющие входи - соответственно к первым входам первого и второго элементов И и к первому и второму входам элемента ИЛИ. которые являются соответственно вторым и третьим входами элемента памяти, первым

5 и четвертым входам которого являются вторые входы первого и второго элементов И, выходы которых подключены соответственно к входам первого и второго разделительных диодов, выходы которых объединены и подключены к входам обнуления регистров,

входы разрешения считывания которых подключены к выходу элемента ИЛИ, блок сравнения содержит первую и вторую группы блоков элементов ИЛИ по числу компонент в векторе исходной информации, группу элементов сравнения по числу компонент в векторе исходной информации, элемент задержки, первый, второй, третий и четвертый элементы И, элемент ИЛИ-НЕ, каждый вход которого подключен к соответствующему входу первого элемента И и выходу соответствующего элемента сравнения, а выход - к первому входу третьего элемента И, выход которого является третьим выхо0

дом блока, а второй вход подключен к выходу элемента задержки и к первым входам второго и четвертого элементов И, выходы которых являются соответственно первым и вторым выходами блока, а вторые входы подключены к выходу первого элемента И, управляющие входы элементов сравнения подключены к управляющему входу блока и к входу элемента задержки, а первый и второй информационные входы - соответственно к выходам блоков элементов ИЛИ первой и второй группы, входы которых образуют соответственно первую и вторую группы информационных входов блока.

Изобретение относится к области вычислительной техники и может быть использовано при решении многокритериальных задач исследования операций. Целью изобретения является расширение класса решаемых задач за счет выделения парето-оп- тимальных решений. Устройство содержит блок формирования адреса, два дешифратора, блок памяти векторов исходной информации и блок сравнения. Блок памяти векторов исходной информации содержит М элементов памяти (М - число вариантов решения), каждый из которых состоит из Р регистров (Р - количество компонент в варианте решения), два элемента И, два блока ключей, два разделительных диода и элемент ИЛИ. Блок сравнения содержит Р элементов сравнения, две группы блоков элементов ИЛИ, четыре элемента И, элемент ИЛИ-НЕ и элемент задержки. 1 ил.

ТОГЭДНОг

Ъ I «г