Устройство для выделения эффективных решений

(56) АвторскоеМ. 1206798, клАвторскоВ 1244672, кл Бюл, В 32ников, В.А.Милько свидетельство СС . О 06 Г 15(20, 198 свидетельство СС . 6 06 Р 15/20, 198 НИЯ ЭФласти выть исполь- ериальных оГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВтОРСОМ СНИДЕтЕЛЬСтВ 54) УСТРОЙСТВО ДЛЯ ВЫДЕЛФЕКТИВНЫХ РЕШЕНИЙ57) Изобретение относится к оислительной техники и может быовано при решении многокри 1адач исследования операций. Ц Изобретение относится к области вычислительной техники и может быть использовано для решения многокритериальных задач исследования операций, а именно при выборе парето-оптимальных вариантов,Известно устройство, предназначенное для решения задач многокритериальной (векторной) оптимизации и обеспечивающее определение обобщенного показателя эффективности многокритериальных задач. Однако это устройство не позволяет выделять из множества вариантов парето-оптимальные решения.Наиболее близким по технической сущности к заявляемому устройству является устройство для выбора оптимальных решений, содержащее блок сравнения, блок памяти векторов исходной информации. группу блоков задания показателей, группу блоков задания допусков, группу блоков памяти показателей, группу сумматоров, две бретения является расширение класса решаемых задач за счет выделения парето-оптимальных решений. Устройство содержит блок формирования адреса, два дешифратора, блок памяти векторов исходной информации и блок сравнения. Блок памяти векторов исходной информации содержит М элементов памяти (М - число вариантов решения), каждый из которых состоит из Р регистров(Р - количество компонент в варианте решения), два элемента И, два блока ключей, два разделительных диода и элемент ИЛИ, Блок сравнения содержит Р элементов сравнения, две группы блоков элементов ИЛИ, четыре элемента И, элемент ИЛИ-НЕ и элемент задержки, 1 ил,группы блоков деления, две группы квадраторов, первый и второй сумматоры.Данное устройство обеспечивает свертку векторной информации в скалярные величины и выбор по ним решения, соответствующего лучшему в субьективно принятом смысле набору показателей, Однако это устройство также не позволяет выделять из исходной векторной информации множество парето-оптимальных решений.Цель изобретения - расширение класса решаемых задач эа счет выделения парето- оптимальных решений.На чертеже приведена функциональная схема устройства.Устройство содержит блок 1 формирования адреса, блок 2 памяти векторов исходной информации, блок 3 сравнения, первый 4 и второй 5 дешифраторы, вход 6 запуска устройства, выход 7 признака окончания решения.5 10 15 20 25 30 35 40 45 50 Блок 1 формирования адреса предназначен для формирования управляющих сигналов в соответствии с реализуемым алгоритл 1 ом. Блок имеет пять управляющих входов, два информационных и один управляющий выход. При поступлении сигналов на первый, второй и пятый управляющий входы блока значение сигнала на первом информационном выходе увеличивается на единицу, на втором информационном выходе становится на единицу большим, чем стало на первом информационном выходе, Кроме того, в блоке формируется управляющий импульс, поступающий с его управляащего выхода на управляющий вход блока сравнения, При поступлении импульсов на третий или четвертый управляющий входы увеличивается на единицу значение на нтаром информационном выходе, и, если это значение не стало равным (М+1), то появляется импульс на управляощем выходе блока.Возможная функциональная схема блока задания адреса приведены на фиг, 1.Блок 1 содержит первый 8 и второй 9 элементы ИЛИ, первый 10 и второй 11 счетчики, генераторы одиночных импульсов 12, 13, элемент И 14, элементы задержки 15, 16,Блок 2 памяти векторов исходной информации предназначен для хранения векторов исходной информации, выдачи значений пары очередных векторов для поэлементного сравнения и обнуления значений векторов, не принадлежащих подмножеству парето-оптимальных решений.Блок содержит М элементов памяти 171,172, ., 17 м (где М - количество векторов . исходной информации), каждый из которых содержит элемент ИЛИ 18, первый 19 и втоРой 20 элементы И, РегистРы 211, 212, "21 р (р - количество компонент в векторах), первый 22 и второй 23 ключи, первый 24 и второй 25 разделительные диоды. Каждый элемент памяти имеет четыре уп ранляющих входа и дне группы информационных выходов, Первый и четвертый управляющие входы соответственно объединены у всех элементов памяти, Второй управляющий вход всех элементов памяти соединен с соответствующим выходом первого дешифратора, а третий управляющий вход всех элементов памяти соединен с соответствующими выходами второго дешифратора.При наличии сигнала уровня логической единицы на втором управляющем входе содержимое регистров данного элемента памяти поступает через ключ 22 на первую группу информационных выходов, а при наличии сигнала уровня логической единицы на третьем управляющел входе содеркимое регистров элементов памяти поступает через ключ 23 на вторую группу информационных выходов элемента памяти. Поступление импульса на первый или четвертый управляющий входы при условии наличия сигнала уровня логической единицы на втором или третьем управляющем входе приводит к обнулению содержимого регистров данного элемента памяти.Блок 3 сравнения предназначен для сравнения компонент очередных векторов и формирования управляющих сигналов на управляющих выходах блока. Блок 3 содержит схемы сравнения 261, 26226 р, первую и вторую группу элементов ИЛИ 271, 272, ,27 р и 281282, ,29 р, элемент ИЛИНЕ 30, элемент И 31,32,33 и элемент задержки 34. Если значение 1-той компоненты, поступающей на первый информационный вход схемы сравнения 26,меньше К-той компоненты, поступающей на отарой информационный вход этой схемы сравнения, то на ее признаконам выходе появляется сигнал уровня логической единицы, н противном случае сигнал на признаковам выходе имеет уровень лагическага нуля.Устройство работает следующим образом, Перед началом решения значения компонент исходных нектаров заносятся н регистры 21, 1 = 1, Р элементов памяти 17 з.5 = 1, М и обнуляются счетчики 10, 11 блока 1 задания адреса,Рещение начинается подачей импульса уровня логической единицы на нхад 6 запуска устройства. При этом импульс охода 6 запуска поступает на первый управляющий вход блока 1 задания адреса. С первого управляющего входа сигнал поступает на вход элемента ИЛИ 18, а с его выхода - на вход генератора одиночных импульсов 12. Генератор формирует импульс, длительность которого достаточна для срабатывания счетчиков 10, 11, этот импульс поступает с выхода генератора 12 на счетный вход счетчика 10 и вход элемента задержки 15, Содержимое счетчика 10 увеличивается на единицу (в начале первого шага решения становится равным единице). Информационные выходы счетчика 10 соединены с информационными входами счетчика 11, поэтому, когда через т 1 - время задержки элемента 15 сигнал с выхода элемента задержки поступает на вход записи счетчика11, содержимое счетчика 10 записывается в счетчик 11. Кроме того, импульс с выхода элемента задержки 15 поступает на вход элемента ИЛИ 9, а с его выхода - на вход генератора одиночных импульсов 13, кото 1758653рый через время задержки х 2 формирует управляющий импульс, поступающий на счетный вход счетчика 11 и вход элемента задержки 16. При этом содержимое счетчика 11 увеличивается на единицу и становится равным на первом шаге решения двум, Коды содержимого счетчиков 10, 11 через информационные выходы блока 1 задания адреса поступают на входь 1 первого и второго дешифратороо 4 и 5.При агом появляются сигналы уровня логической единицы на первом выходе дешифратора 4 и втором выходе дешифрэтора 5. Эти сигналы поступают на второй управляющий вход элемента памяти 171 и третий управляющий вход элемента памяти 172. При атом в элементе памяти 171 сигнал поступает на вход элемента ИЛИ 18, один вход элемента И 19 и управляющий вход ключа 22, информационные цепи которого при этом замыкаются, С выхода элемента ИЛИ 18 сигнал поступает на объединенные считывающие входы регистров 21, Е = 1, Р элемента памяти 171 и значения компонент первого вектора с выходов регистров этого элемента памяти поступают через информационные цепи ключа 22 на соответствующие входы элементов ИЛИ 27, Е =1, Р блока 2 сравнения. В элементе памяти 172 сигнал с дешифратора 5 поступает на вход элемента ИЛИ 18, один вход элемента И 20 и на управляющий вход ключа 23, информационные цепи которого при этом замыкаются, С выхода элемента ИЛИ 18 сигнал поступает на обьединенные считывающие входы регистров 21, К = 1, Р и содержимое компонент второго вектора с выходов регистров через информационные цепи ключа 23 элемента памяти 172 поступает на соответствующие входы элементов ИЛИ 28, 1 = 1, Р блока 2 сравнения.С выходов элементов ИЛИ 27, 28, К = 1, Р значения соответствующих компонент первого и второго векторов поступают соответственно на первый и второй информационные входы схем сравнения 26, К = 1, Р,Через х 2 - время задержки элемента задержки 16 импульс с его выхода через элемент И 14 поступает на управляющий вход блока 2 сравнения. а с него - на объединенные управляющие входы схем сравнения 26 ь 1 = 1, Р и вход элемента задержки 34. При этом в схемах сравнения осуществляется сравнение значений компонент первого и второго векторов, если К-ая компонента первого вектора меньше К-ой компоненты второго вектора, то на признаковом выходе К-ой схемы сравнения появляется сигнал уровня логической единицы, в 5 10 15 20 25 30 35 40 45 50 55 противном случае сигнал на признаковом выходе будет иметь уровень логического нуля, Через хз - время задержки элемента задержки 34, сигнал с его выхода поступает на входы элементов И 31, 32, 33.Дальнейшая работа устройства зависит от результатов сравнения компонент "очередных" векторов, При этом возможны три варианта, которые рассмотрим на примере сравниваемых на первом шаге решения компонент первого и второго векторов,Первый вариант. Если все компоненты первого вектора меньше соответствующих компонент второго вектора, то единичные сигналы с выходов схем сравнения 26, Е = 1, Р поступают на все входы элементов И 29 и ИЛИ-НЕ 30. При этом сигнал уровня логической единицы с выхода элемента И 29 подается на вход элемента И 31 и инверсный вход элемента И 33, поэтому сигнал с выхода элемента задержки 34 поступает через элемент И 31 на объединенные первые входы элементов памяти 178, 3 = 1, М и на второй управляющий вход блока 1 задания адреса. Сигнал с первого управляющего входа элементов памяти поступает на вход элементов И 19 всех элементов памяти. Так как на втором входе элемента И 19 присутствует сигнал только в элементе памяти 171, то сигнал с выхода элемента И 19 этого элемента памяти через разделительный диод,24 поступает на объединенные входы обнуления регистров 21 к, 1 = 1, Р и содержимое этих регистров обнуляется, На этом заканчивается первый шаг решения и на втором уже будет осуществляться сравнение второго вектора с третьим.Второй вариант. Если все компоненты первого вектора больше, или равны соответствующим компонентам второго вектора, то на признэковых выходах всех схем сравнения будет сигнал уровня логического нуля и тогда сигнал с выхода элемента ИЛИ-НЕ 30 поступает на один из входов элемента И 32. Сигнал с выхода элемента задержки 34 поступает на обьединенные входы элементов памяти 17 з, Я = 1, М и на четвертый управляющий вход блока 1 задания адреса. Сигнал с четвертых управляющих входов элементов памяти поступает на вход элементов И 20. Так как на втором входе элемента И 20 на первом шаге решения будет присутствовать сигнал только в элементе памяти 172, то с выхода элемента И 20 сигнал через разделительный диод 25 поступает на объединенные входы обнуления регистров 21, 1 = 1, Р и содержимое регистров элемента памяти 172 обнуляется, На этом шаг решения заканчивается и начина 17586535 10 20 ется следующий, на котором будет осуществляться сравнение компонент первого и третьего векторов,Третий вариант. Если условия для рассмотренных выше первого и второго вариантов на первом шаге решения не реализуются, то к моменту поступления импульса с выхода элемента задержки 34 на выходах элементов 29 и 30 будут сигналы уровня логического нуля и импульс с выхода элемента задержки 34 через элемент И 33 поступает на третий управляющий вход блока 1 задания адреса, На этом шаг решения заканчивается и начинается следующий шаг, на котором будет осуществляться сравнение компонент первого и третьего векторов,Работа устройства на последующих шагах решения будет аналогична выше рассмотренному первому шагу, эа тем исключением, что если в начале очередного шага содержимое счетчика 11 станет равным (М+1), то сигнал с (М+1)-го выхода второго дешифратора 5 поступит на пятый вход блока 1 задания адреса и начинается другой шаг решения, Поступление сигнала с пятого управляющего входа на инверсный вход элемента И 14 исключает преждевременное прохождение импульса от генератора одиночных импульсов 13 на управляющий выход блока.Решение заканчивается при достижении содержимого счетчика 10 в начале очередного шага решения значения М, при этом сигнал с М-го выхода первого дешифратора 4 поступает на выход 7 признака окончания решения. Множество парето-оптимальных решений, выделенных в результате работы устройства, однозначно определены содержимым необнуленных элементов памяти 17 э, Я = 1, М.Таким образом, предлагаемое устройство обеспечивает за й шагов решения (М 58 0,5 М (М -1 выделение парето- оптимальных решений из исходного множества векторов исходной информации, что свидетельствует о существенном расширении класса решаемых задач многокритериальной оптимизации и достижении цели изобретения.Формула изобретения Устройство для выделения эффективных решений, содержащее блок сравнения, блок памяти векторов исходной информации, первая группа выходов блока памяти векторов исходной информации подключена к первой группе информационных входов блока сравнения, первый выход которого подключен к первой группе входов разрешения обнуления блока памяти векторов ис 25 30 35 40 50 55 ходной информации, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет выделения парето-аптимальных решений, дополнительно оведены первый и второй дешифраторы, блок формирования адреса, первый управляющий вход которого является входом запуска устройства, входы первого и второго дешифратороо подключены соответственно к пероому и второму информационным выходам блока формирования адреса, группы выходов соответственно к первой и второй группам входов разрешения считывания блока пагляти векторов исходной информации, один из выходов первого дешифратора является оыходом признака окончания решения устройства, а управляющий выход второго дешифратора подключен к второму управляющему входу блока формирования адреса, третий, четвертый и пятый управляющие входы которого соответственно подключены к первому, второму выходам блока сравнения и к второй группе входов разрешения обнуления блока памяти векторов исходной информации, третьему выходу блока сравнения, а управляющий выход - к управляющему входу блока сравнения, вторая группа информационных оходоо которого подключена к второй группе выходов блока памяти оекторов исходной информации, причем блок памяти векторов исходной информации содержит элементы памяти по числу векторов исходной информации, первый и четвертый, второй и третий входы элементов памяти образуют соответстоенно первые и оторые группы входов разрешения обнуления и разрешения. считывания блока, а первая и вторая группы выходов - соответственно первую и вторую группы выходов блока, причем каждый элемент памяти содержит первый и второй элементы И, элемент ИЛИ, первый и второй разделительные диоды, регистры по числу компонент о векторе исходной информации, первый и второй блоки ключей, выходы которых являются соответственно первой и второй группами выходоо элемента памяти, группы информационных входов подключены соответственно к выходам регистров, а управляющие входи - соответственно к первым входам первого и второго элементов И и к первому и второму входам элемента ИЛИ. которые являются соответственно вторым и третьим оходали элемента памяти, первым и четвертым входам которого являются вторые входы первого и второго элементов И, выходы которых подключены соответственно к входам первого и второго разделительных диодов, выходы которых обьединены и подключены к входам обнуления регистров.10 1758653 Составитель Н.Ячкулаор В.Пилишкин Техред М,Моргентал Корректор С,Патруш каэ 3001 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 водственн.-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 входы разрешения считывания которых подключены к выходу элемента ИЛИ, блок сравнения содержит первую и вторую группы блоков элементов ИЛИ по числу компонент в векторе исходной информации, группу элементов сравнения по числу компонент в векторе исходной информации, элемент задержки, первый, второй, третий и четвертый элементы И, элемент ИЛИ-НЕ, каждый вход которого подключен к соответствующему входу первого элемента И и выходу соответствующего элемента сравнения, а выход - к первому входу третьего элемента И, выход которого является третьим выходом блока, а второй вход подключен к выходу элемента задержки и к первым входам второго и четвертого элементов И, выходы которых являются соответственно первым и 5 вторым выходами блока, а вторые входыподключены к выходу первого элемента И, управляющие входы элементов сравнения подключены к управляющему входу блока и к входу элемента задержки, а первый и вто рой информационные входы - соответственно к выходам блоков элементов ИЛИ первой и второй группы, входы которых образуют соответственно первую и вторую группы информационных входов блока.