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

 

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

COI03 СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 G 06 F 15/419

ГОСУДАРСТВЕННЫЙ KOMVlt ET

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4882765/24 (22) 16.11.90 (46) 30.08.92. Бюл. % 32 (72) Г.И.Кожевников, В.А.Мильков и Н.И.Ячкула (56) Авторское свидетельство СССР

N- 1206798, кл. G 06 Г 15/20, 1984.

Авторское свидетельство СССР

hb 1244672, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭФФЕКТИВНЫХ РЕШЕНИЙ (57) Изобретение относится к области вычислительной техники и может быть использовано при решении мнагакритериальных задач исследования операций. Целью изоИзобретение относится к области вычислительной техники и может быть использовано для решения мнагакритериальных задач исследования операций, а именно при выборе парето-оптимальных вариантов.

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

Однако эта устройство не позволяет выделять из множества вариантов парето-оптимальные решения.

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

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

ЯЛ, » 1758653 А1 бретения является расширение класса решаемых задач за счет выделения парето-orIтимальных решений. Устройство содержит блок формирования адреса, два дешифратора, блок памяти векторов исходной информации и блок сравнения. Блок памяти векторов исходной информации содержит

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

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

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

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

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

1758653

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

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

Возможная функциональная схема блока задания адреса приведены на фиг, 1.

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

Блок содержит M элементов памяти 171, 172, ..., 17м (где M — количество векторов . исходной информации), каждый из которых содержит элемент ИЛИ 18, перный 19 и второй 20 элементы И, регистры 211, 21, ..., 21 (р — количество компонент в векторах), первый 22 и второй 23 ключи, первый 24 и второй 25 разделительные диоды. Каждый элемент памяти имеет четыре уп ранляющих входа и дне группы информационных выходов, Первый и четвертый управляющие входы соответственно объединены у всех элементов памяти. Второй управляющий вход всех элементов памяти соединен с соответствующим выходом первого дешифратора, а третий управляющий вход всех элементов памяти соединен с соответствующими выходами второго дешифратора.

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

Блок 3 сравнения предназначен для сравнения компонент очередных векторов и формирования управляющих сигналов на управляющих выходах блока. Блок 3 содержит схемы сравнения 261, 262...„26р, первую и вторую группу элементов ИЛИ 27I, ?72, ..., 27 и 28I„28, ..., 29р, элемент ИЛИН Е 30, элемент И 31, 32, 33 и элемент задержки 34. Если значение k-той компоненты, поступающей на первый информационный вход схемы сравнения 26,меньше k-той компоненты, поступающей на отарой информационный вход этой схемы сравнения, то на ее признакооам выходе появляется сигнал уровня логической единицы, о противном случае сигнал на признаковам выходе имеет уровень лагическага нуля.

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

$ = 1, M и обнуляются счетчики 10, 11 блока

1 задания адреса.

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

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

При агом появляются сигналы уровня логической единицы на первом выходе дешифратора 4 и втором выходе дешифрэтора

5. Эти сигналы поступают на второй управляющий вход элемента памяти 17> и третий упра вля ющий вход эл емента памяти 17z.

При этом в элементе памяти 171 сигнал поступает на вход элемента ИЛИ 18, один вход элемента И 19 и управляющий вход ключа

22, информационные цепи которого при этом замыкаются. С выхода элемента ИЛИ

18 сигнал поступает на объединенные считывающие входы регистров 21, k = 1, P элемента памяти 171 и значения компонент первого вектора с выходов регистров этого элемента памяти поступают через информационные цепи ключа 22 на соответствующие входы элементов ИЛИ 27, k=1, P блока

2 сравнения. В элементе памяти 17z сигнал с дешифратора 5 поступает на вход элемента ИЛИ 18, один вход элемента И 20 и на управляющий вход ключа 23, информационные цепи которого при этом замыкаются. С выхода элемента ИЛИ 18 сигнал поступает на обьединенные считывающие входы регистров 21, k = 1, P и содержимое компонент второго вектора с выходов регистров через информационные цепи ключа 23 элемента памяти 17z поступает нэ соответствующие входы элементов ИЛИ 28, k = 1, P блока 2 сравнения.

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

Через т2 — время задержки элемента задержки 16 импульс с его выхода через элемент И 14 поступает на управляющий вход блока 2 сравнения. а с него — на объединенные управляющие входы схем сравнения 26k k = 1, P и вход элемента задержки

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

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

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

Первый вариант. Если все компоненты первого вектора меньше соответствующих компонент второго вектора, то единичные сигналы с выходов схем сравнения 26, k = 1, Р поступают на все входы элементов И 29 и

ИЛИ-НЕ 30. При этом сигнал уровня логической единицы с выхода элемента И 29 подается на вход элемента И 31 и инверсный вход элемента И 33, поэтому сигнал с выхода элемента задержки 34 поступает через элемент И 31 на объединенные первые входы элементов памяти 17э, S = 1, M и на второй управляющий вход блока 1 задания адреса. Сигнал с первого управляющего входа элементов памяти поступает на вход элементов И 19 всех элементов памяти. Так как на втором входе элемента И 19 присутствует сигнал только в элементе памяти 17 . то сигнал с выхода элемента И 19 этого элемента памяти через разделительный диод.24 поступает на объединенные входы обнуления регистров 21к, k = 1, P и содержимое этих регистров обнуляется. На этом заканчивается первый шаг решения и на втором уже будет осуществляться сравнение второго вектора с третьим.

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

Сигнал с выхода элемента задержки 34 поступает на объединенные входы элементов памяти 17з, S = 1, М и на четвертый управляющий вход блока 1 задания адреса. Сигнал с четвертых управляющих входов элементов памяти поступает на вход элементов И 20. Так как на втором входе элемента И 20 на первом шаге решения будет присутствовать сигнал только в элементе памяти 17z, то с выхода элемента И 20 сигнал через разделительный диод 25 поступает «а объединенные входы обнуления регистров 21, k = 1, P и содержимое регистров элемента памяти 17z обнуляется, На этом шаг решения заканчивается и начина1758653 ется следующий, на котором будет осуществляться сравнение компонент первого и третьего векторов, Третий вариант. Если условия для рассмотренных выше первого и второго вариантов на первом шаге решения не реализуются, то к моменту поступления импульса с выхода элемента задержки 34 на выходах элементов 29 и 30 будут сигналы уровня логического нуля и импульс с выхода элемента задержки 34 через элемент И 33 поступает на третий управляющий вход блока 1 задания адреса. На этом шаг решения заканчивается и начинается следующий шаг, на котором будет осуществляться сравнение компонент первого и третьего векторов.

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

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

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

Формула изобретения

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

20

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

1758653

Составитель Н.Ячкула

Редактор В.Пилишкин Техред M,Mîðãåíòàë Корректор С.Патрушева

Заказ 3001 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035. Москва, Ж-35, Раушская наб., 4/5

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

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

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

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

 

Похожие патенты:

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки процессора реляционной алгебры систем управления базами данных и базами знаний интеллектуальной системы автоматизированного проектирования РЭА и ЭВА Целью изобретения является повышение быстродействия Устройство содержит счетчики 1и 2, блок 3 постоянной памяти, регистр 4, триггер 5, элементы И 6-13, элемент ЗАПРЕТ 14, элементы ИЛИ 15-17, элемент И 18, элемент 19 задержки, формирователь 20 импульсов, элемент 21 задержки, дешифратор 22, узел 23 сравнения, элемент ИЛИ 24 триггер 25

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

Изобретение относится к вычислительной технике и цифровой обработке сигналов

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

Изобретение относится к вычислительной технике и может быть использовано в вычислительных устройствах и системах

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

Изобретение относится к электронным играм

Микроэвм // 2108619
Изобретение относится к области микропроцессорной техники, в частности, может применяться для реализации обмена информацией

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

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

Изобретение относится к цифровым компьютерным системам и предназначено для обработки двух и более команд параллельно

Изобретение относится к вычислительной технике, точнее к построению многопроцессорных векторных ЭВМ

Изобретение относится к вычислительной технике и может найти применение в автоматизированных системах управления АСУ индустриального и специального назначения

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