Устройство для решения задач оптимизации Советский патент 1992 года по МПК G06F15/419 

V

00 О О

Јь

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

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

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

Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств элементов множества компонент модели, блок 3 моделирования объектов и/или процессов, накапливающий блок 4 выбора значений функции, блок 5 регистрации, вход 6 пуска устройства, выходы 7, 8 блока 1 синхронизации, вход 9 задания допустимых значений параметров модели, входы 10 задания значений параметров компонент модели устройства, выходы 11 признаков принадлежности компонент модели подмножеству модифицируемых устройства и выход 12 признака окончания работы устройства.

Устройство работает следующим образом.

Пусть, например, G - вероятностный граф исходной конфигурации сети. Задан набор резервных линий связи в виде ребер и/или дуг графа G на вершинах G0, для которых кроме их принадлежности Рк известны веса Ск (К 1, ..., М, где М - количество резервных линий связи дополнительных друг и/или ребер). Вес Ск может характеризовать, например, стоимость введения К-го дополнительного ребра и/или дуги. Необходимо синтезировать такую сеть, вероятность связности которой не меньше заданной нормы, путем введения дополнительных линий связи в исходную сеть, при условии, что вес дополнительных линий связи (т. е. дополнитепьных дуг или ребер) минимален.

Перед началом работы блок 2 настраивают на требуемый алгоритм перечисления подмножеств элементов множества компонент модели(например, на такой алгоритм, при котором последовательно перебираются все возможные сочетания дополнительных дуг и/или ребер) и приводят в исходное состояние, при котором потенциалы уровня логической единицы на его выходах признаков принадлежности элементов множества подмножеству выбранных определяют первое из перечисленных подмножеств (в данном случае, например, такое, при котором в графе нет ни одной дополнительной дуги и/или ребра). Блок 3 настраивают на моделирование конкретного объекта и/или процесса (на моделирование вероятностного графа), блок 4 выбора значений функции - на требуемую функциональную зависимость значения функции от ее аргументов (в данном случае на вычисление суммы всех аргументов, т. е. суммы весов всех дополнительно введенных дуг и/или ребер графа) и критерий предпочтения последующего зна0 чения функции предыдущему ее значению (в данном случае предпочтение отдается меньшему значению функции, т. е. графу с меньшим значением суммы весов дополнительных дуг и/или ребер). По входу 9 устрой5 ства задают значения допустимых параметров модели (т. е. допустимое значение вероятности связности всех вершин графа), по входам 10 - значения параметров компонент модели (т. е. веса соответствую0 щих дополнительных дуг и/или ребер).

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

5 предусмотренную временной диаграммой его работы.

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

0 на своих выходах в соответствии с результатами использования заданного алгоритма перечисления подмножеств.

В том случае, если алгоритм не позволил сформировать очередное подмножест5 во элементов (например, если все допустимые комбинации уже были сформированы), блок 2 перечисления формирует на своем выходе признака окончания списка подмножеств потенциал уровня логической

0 единицы. При этом блок 1 синхронизации прекращает формирование синхросигналов на своих выходах 7, 8 (останавливается).

В том случае, если алгоритм позволил сформировать очередное подмножество

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

0 выходе признака окончания списка подмножеств. При этом блок 1 синхронизации через заранее определенное время ожидания (сигнала останова) формирует на своем выходе 8 импульс уровня логической единицы.

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

сравнивает значение параметров модели (т. е. значения вероятности связности, полученные в результате моделирования с допустимыми значениями).

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

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

В том случае, если значение функции вычисленное в одном такте работы, не удовлетворяет заданному критерию предпочтения, блок 4 сохраняет на своем выходе потенциал уровня логического нуля.

Через время, достаточное для выполнения указанных операций, блок 1 синхронизации повторяет цикл выдачи синхроимпульсов на своих выходах 7,8. При этом работа устройства повторяется.

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

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

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

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

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

моделирования объектов и/или процессов подключен к входу повторного пуска блока синхронизации, второй вход которого подключен к входу пуска блока моделирования объектов и/или процессов, вход задания допустимых значений параметров модели которого является одноименным выходом устройства, вход задания значения параметров К-й компоненты модели которого подключен к входу задания значений К-го

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

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

Изобретение относится к вычислительной технике и может быть использовано для синтеза объектов и/или процессов по их моделям. Целью изобретения является расширение функциональных возможностей устройства за счет синтеза оптимальных объектов и/или процессов по заданным параметрам модифицируемых компонент их моделей. Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств элементов множества компонент модели, блок 3 моделирования объектов и/или процессов, накапливающий блок 4 выбора значений функции, блок5 регистрации, вход 6 пуска устройства, выходы 7, 8 блока 1 синхронизации, вход 9 задания допустимых значений параметров модели, входы 10 задания значений параметров компонент модели устройства, выходы 11 признаков принадлежности компонент модели подмножеству модифицируемых устройств и выход 12 признака окончания работы устройства На вход 6 пуска устройства подают импульс уровня логической 1 При этом блок 1 синхронизации формирует на своих выходах 7, 8 последовательность синхроимпульсов, под управлением которой на выходах 11 устройства формируется набор компонент модели, модификация которых позволяет оптимизировать параметры синтезируемого объекта и/или процесса 1 ил СО С