Устройство для управления движением симплекса в пространстве параметров

Полезная модель относится к цифровой вычислительной технике, а именно к специализированным устройствам анализа выбора направления движения симплекса, и может быть использовано в научных исследованиях, где необходимо осуществлять поиск оптимальных решений с использованием симплексного метода.
Устройство предназначено для автоматизации анализа и выбора направлений симплексного поиска и принятия решений о достижении экстремума целевой функции в задачах поиска оптимальных решений.
Известны системы поиска оптимальных решений, использующие симплексный метод [Нечипоренко В.И. Структурный анализ систем (эффективность и надежность). М.: Сов., радио, 1977; Дамбраускас А.П. Симплексный поиск. М.: Энергия, 1979.]. В этих системах одной из задач является сравнительный анализ значений целевой функции в вершинах единичного симплекса, определение вершины с наименьшим значением отклика и принятие решения о замене вершины с наименьшим значением целевой функции. Недостаток системы - блок управления движением симплекса в пространстве параметров описан на логическом уровне и отсутствует схема устройства для выбора вершины симплекса, подлежащей замене.
Известна система определения и реализации оптимальных траекторий управляющих воздействий в условиях неопределенности [Патент на полезную модель №114535 Опубл. 27.03.2012 Бюл. №9]. В этой системе сравнительный анализ значений целевой функции в вершинах единичного симплекса, определение вершины с наименьшим значением отклика и принятие решения о замене вершины с наименьшим значением целевой функции описан на логическом уровне и отсутствует схема устройства для выбора вершины симплекса, подлежащей замене.
Цель разработки полезной модели - создание технического средства определенного назначения (сравнительный анализ значений целевой функции в вершинах единичного симплекса, определение вершины с наименьшим значением отклика и выбор вершины симплекса, подлежащей замене).
Устройство предназначено для автоматизации анализа и выбора направлений симплексного поиска и принятия решений о достижении экстремума целевой функции в двухпараметрических задачах оптимизации.
Исходными данными служат координаты х, у вершин симплекса -равностороннего треугольника ABC - и значения отклика целевой функции в вершинах А, В, С.
Анализ направлений симплексного поиска экстремума (для определенности - максимума) целевой функции включает перебор вершин А, В, С и определение вершины с наименьшим значением отклика. После определения этой вершины принимается решение о ее замене и построении симплекса с зеркально отображенной вершиной относительно отброшенной.
По результатам оценки отклика в новой вершине и сравнения его со значением целевой функции в отброшенной вершине принимается решение о направлении дальнейшего поиска оптимума, при этом возможны два варианта.
В первом случае, когда отклик в новой вершине больше, чем в отброшенной, оставляется новая вершина.
Во втором случае (отклик в новой вершине меньше или равен отклику в отбрасываемой вершине), осуществляется возврат к предыдущему положению симплекса и производится перебор оставшихся вершин с апробированием для каждой очередной вершины нового направления поиска. Здесь также возможны два варианта.
Если для очередной выбранной вершины новое направление поиска оказывается успешным (замена вершины дает прирост целевой функции), оставляется новое положение симплекса.
Если замена вершины не дает прироста целевой функции, эта вершина оставляется и осуществляется переход к следующей вершине с проведением в отношении нее аналогичных действий по апробированию замены.
Принятие решения о достижении оптимума осуществляется в случае, если поочередная замена всех трех вершин не дает в отношении каждой вершины увеличения отклика при ее замене.
Данная модель реализована в предлагаемом устройстве (фиг. 1).
Устройство для управления движением симплекса в пространстве параметров содержит задающий генератор 1, первый, второй, третий, четвертый, пятый и шестой регистры 3, 7, 11, 14, 21, 24, первый, второй, третий, четвертый, пятый и шестой блоки сравнения 6, 13, 23, 9, 15, 19, первый, второй третий, четвертый, пятый и шестой блоки элементов И 2, 10, 20, 5, 12, 22, первый, второй, третий, четвертый, пятый, шестой и седьмой элементы И 26, 16, 17, 18, 42, 43, 44, первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый, десятый, одиннадцатый и двенадцатый элементы ИЛИ 8, 28, 33 - 38, 32, 29 - 31, первый, второй и третий триггеры 39, 40, 41, счетчик 27, элемент задержки 4, элемент НЕ 25. На схеме показаны информационные входы устройства 45, вход запуска устройства 46, выходы устройства 47, 48, 49.
Информационные входы устройства 45 подключены к информационным входам первого, второго и третьего блоков элементов И 2, 10, 20, вход запуска устройства 46 соединен с входом запуска задающего генератора 1 и со вторым входом второго элемента ИЛИ 28, выход задающего генератора 1 соединен с первыми управляющими входами первого, второго и третьего блоков элементов И 2, 10, 20 и через элемент задержки 4 - с управляющими входами первого, второго и третьего блоков сравнения 6, 13, 23 и первым входом первого элемента И 26, выходы первого, второго и третьего блоков элементов И 2, 10, 20 соединены соответственно с входами первого, третьего и пятого регистров 3, 11, 21, выходы которых подключены соответственно к информационным входам четвертого, пятого и шестого блоков элементов И 5, 12, 22 и к первым входам первого, второго и третьего блоков сравнения 6, 13, 23, выходы четвертого, пятого и шестого блоков элементов И 5, 12, 22 подключены соответственно к входам второго, четвертого и шестого регистров 7, 14, 24, выходы второго регистра 7 соединены со вторыми входами первого блока сравнения 6, с первыми входами четвертого и пятого блоков сравнения 9, 15, выходы четвертого регистра 14 соединены со вторыми входами второго и четвертого блоков сравнения 13, 9 и с первыми входами шестого блока сравнения 19, выходы шестого регистра 24 соединены со вторыми входами третьего, пятого и шестого блоков сравнения 23, 15, 19, выходы первого, второго и третьего блоков сравнения 6, 13, 23 соединены соответственно с управляющими входами четвертого, пятого и шестого блоков элементов И 5, 12, 22 и с первым, вторым и третьим входами первого элемента ИЛИ 8, выход которого соединен с управляющим входом четвертого, пятого и шестого блоков сравнения 9, 15, 19, с входом установки в нулевое состояние счетчика 27 и через элемент НЕ 25 подключен ко второму входу первого элемента И 26, выход которого соединен с первым входом пятого, шестого и седьмого элементов И 42, 43, 44, первый выход четвертого блока сравнения 9 подключен к первому входу третьего элемента И 17, второй вход которого соединен со вторым выходом шестого блока сравнения 19, а выход - с первым входом третьего, шестого, одиннадцатого и вторым входом седьмого элементов ИЛИ 33, 36, 30, 37, второй выход четвертого блока сравнения 9 подключен к первому входу второго элемента И 16, второй вход которого соединен с первым выходом пятого блока сравнения 15, а выход - с первым входом второго элемента ИЛИ 28, выход которого подключен ко второму входу третьего, пятого, восьмого и к первому входу десятого элементов ИЛИ 33, 35, 38, 29, второй выход пятого блока сравнения 15 соединен с первым входом четвертого элемента И 18, второй вход которого соединен с первым выходом шестого блока сравнения 19, а выход - с первым входом четвертого, пятого, седьмого и двенадцатого элементов ИЛИ 34, 35, 37, 31, выходы третьего, пятого и седьмого элементов ИЛИ 33, 35, 37 подключены к входу установки в нулевое состояние соответственно первого, второго и третьего триггеров 39, 40, 41, выходы четвертого, шестого и восьмого элементов ИЛИ 34, 36, 38 подключены входом установки в единичное состояние соответственно первого, второго и третьего триггеров 39, 40, 41, единичный выход первого триггера 39 соединен со вторым входом пятого элемента И 42 и со вторым управляющим входом третьего блока элементов И 20, единичный выход второго триггера 40 соединен со вторым входом шестого элемента И 43 и со вторым управляющим входом второго блока элементов И 10, единичный выход третьего триггера 41 соединен со вторым входом седьмого элемента И 44 и со вторым управляющим входом первого блока элементов И 2, выход пятого элемента И 42 соединен с четвертым входом пятого, третьим входом третьего, первым входом восьмого, третьим входом девятого и вторым входом двенадцатого элементов ИЛИ 35, 33, 38, 32, 31, выход шестого элемента И 43 соединен со вторым входом четвертого, третьим входом пятого и седьмого, вторым входом девятого и одиннадцатого элементов ИЛИ 34, 35, 37, 32, 30, выход седьмого элемента И 44 соединен с четвертым входом третьего, вторым входом шестого, четвертым входом седьмого, первым входом девятого и вторым входом десятого элементов ИЛИ 33, 36, 37, 32, 29, выход девятого элемента ИЛИ 32 подключен к входу счетчика 27, выход которого подключен к входу останова задающего генератора 1, выходы десятого, одиннадцатого и двенадцатого элементов ИЛИ 29, 30, 31 являются выходами устройства 47, 48, 49.
Работает устройство следующим образом.
В исходном состоянии регистры 3, 7, 11, 14, 21, 24, счетчик 27, триггеры 39, 40, 41 находятся в нулевом состоянии.
*
При подаче на вход запуска устройства 46 импульса, который пройдет элементы ИЛИ 28, 38, 29 установит триггер 41 в единичное состояние, поступит на выход устройства 47 и запустит генератор 1. Предполагается, что по сигналу на выходе 47 осуществляется замена вершины А симплекса и рассчитывается отклик (значение целевой функции) в новой вершине А, который поступает на входы устройства 45. Т.к. триггер 41 установлен в единичное состояние, то первый блок элементов И 2 будет открыт при поступлении импульса от генератора 1 и значение отклика запишется в регистр 3. После задержки на элементе 4 импульс поступит на входы блоков сравнения 6, 13, 23. Т.к. значение в регистре 3 больше чем значение в регистре 7, то только на выходе блока сравнения 6 появится сигнал, по которому значение регистра 3 перепишется через блок элементов И 5 в регистр 7. Т.к. значение в регистре 7 больше значения в регистрах 14, 24, то при поступлении сигнала с выхода элемента ИЛИ 8 на входы блоков сравнения 9, 15, 19, сигнал появится на первых выходах блоков 9, 15 и на втором выходе блока 19 и, следовательно, сигнал появится на выходе элемента И 17, по которому через элемент ИЛИ 37 триггер 41 установится в нулевое состояние, а через элемент ИЛИ 36 триггер 40 в единичное состояние. Одновременно сигнал через элемент ИЛИ 30 поступит на выход 48. Предполагается, что по сигналу на выходе 48 осуществляется замена вершины В симплекса и рассчитывается отклик (значение целевой функции) в новой вершине В, который поступает на входы устройства 45. Т.к. триггер 40 установлен в единичное состояние, то второй блок элементов И 10 будет открыт при поступлении импульса от генератора 1 и значение отклика запишется в регистр 11. После задержки на элементе 4 импульс поступит на входы блоков сравнения 6, 13, 23. Т.к. значение в регистре 11 больше чем значение в регистре 14, то только на выходе блока сравнения 13 появится сигнал, по которому значение регистра 11 перепишется через блок элементов И 12 в регистр 14.
Т.к. значение в регистрах 7 и 14 больше значения чем в регистре 24, то при поступлении сигнала с выхода элемента ИЛИ 8 на входы блоков сравнения 9, 15, 19, сигнал появится на первых выходах блоков 15, 19 и, следовательно, сигнал появится на выходе элемента И 18, по которому через элемент ИЛИ 35 триггер 40 установится в нулевое состояние, а через элемент ИЛИ 34 триггер 39 в единичное состояние. Одновременно сигнал через элемент ИЛИ 31 поступит на выход 49. Предполагается, что по сигналу на выходе 49 осуществляется замена вершины С симплекса и рассчитывается отклик (значение целевой функции) в новой вершине С, который поступает на входы устройства 45. Т.к. триггер 39 установлен в единичное состояние, то третий блок элементов И 20 будет открыт при поступлении импульса от генератора 1 и значение отклика запишется в регистр 21. После задержки на элементе 4 импульс поступит на входы блоков сравнения 6, 13, 23. Т.к. значение в регистре 21 больше чем значение в регистре 24, то только на выходе блока сравнения 23 появится сигнал, по которому значение регистра 21 перепишется через блок элементов И 22 в регистр 24. В дальнейшем с помощью блоков сравнения 9, 15, 19 и элементов И 16, 17, 18 выбирается наименьшее значение отклика записанного в регистрах 7, 14, 24 и на соответствующий выход 47, 48, 49 поступит сигнал, по которому осуществляется замена одной из вершин симплекса А или В или С и рассчитывается отклик (значение целевой функции) в новой вершине А* или В* или С*, который поступает на входы устройства 45. Т.к. один из триггеров 39 или 40 или 41 установлен в единичное состояние, то соответствующий блок элементов И 2 или И 10 или И 20 будет открыт при поступлении импульса от генератора 1 и значение отклика запишется в соответствующий регистр 3 или регистр 11 или регистр 21.
Если полученный новый отклик, записанный в регистр 3 или в регистр 11 или в регистр 21, будет больше, чем значение соответственно в регистре 7 или регистре 14 или в регистре 24, то работа устройства будет продолжена описанным выше образом. При этом осуществляется выбор новой вершины симплекса. Если для очередной выбранной вершины новое направление оказывается успешным (замена вершины дает прирост целевой функции), то остается новое положение симплекса.
Если, полученный новый отклик, записанный в регистр 3 или в регистр 11 или в регистр 21, будет меньше или равный, чем соответствующее значение в регистре 7 или регистре 14 или в регистре 24 (т.е. нет приращения целевой функции), то на выходе блоков сравнения 6, 13, 23 и на выходе элемента ИЛИ 8 сигнала не будет. В этом случае сигнал появится на выходе элемента И 26, по которому через один из элементов И 42, 43, 44, который будет открыт высоким потенциалом одного из триггеров 39, 40, 41. Если, например, была замена вершины А на А симплекса, т.к. триггер 41 находился в единичном состоянии, то сигнал с выхода элемента И 44 через элементы ИЛИ 33, 36, 37 установит триггеры 39, 41 в нулевое состояние, а триггер 40 в единичное состояние, одновременно сигнал с выхода элемента И 44 поступит через элемент ИЛИ 32 на вход счетчика 27 и через элемент ИЛИ 29 на выход 47. В результате будет замена вершины А* симплекса на А, т.е. произошла обратная замена (откат на 1 шаг назад). В связи с тем, что триггер 40 установлен в единичное состояние отклик с входа 45 через блок элементов И 10 запишется в регистр 11 и работа устройства будет продолжена описанным выше способом. Если, полученный новый отклик, записанный в регистр 11, будет больше, чем соответствующее значение в регистре 14 (т.е. есть приращение целевой функции), то на выходе блоков сравнения 13 и на выходе элемента ИЛИ 8 будет сигнал, по которому произойдет замена вершины симплекса, описанным выше способом и счетчик 27 установится в нулевое состояние.
Если, полученный новый отклик, записанный в регистр 11, будет меньше или равный, чем соответствующее значение в регистре 14 (т.е. нет приращения целевой функции), то на выходе блоков сравнения 6, 13, 23 и на выходе элемента ИЛИ 8 сигнала не будет. В этом случае сигнал появится на выходе элемента И 26, по которому через элемент И 43, который будет открыт высоким потенциалом триггера 40. Если, например, была замена вершины В на В* симплекса, т.к. триггер 40 находился в единичном состоянии, то сигнал с выхода элемента И 43 через элементы ИЛИ 34, 35, 37 установит триггеры 40, 41 в нулевое состояние, а триггер 39 в единичное состояние, одновременно сигнал с выхода элемента И 43 поступит через элемент ИЛИ 32 на вход счетчика 27, увеличив его содержимое на единицу, и через элемент ИЛИ 30 на выход 48. В результате будет замена вершины В* симплекса на В, т.е. произойдет обратная замена (откат на 1 шаг назад). Работа устройства продолжится описанным выше способом. Если замена третьей вершины симплекса не приведет к приращению целевой функции, то при увеличении содержимого счетчика 27 произойдет его переполнение и сигнал с его выхода остановит генератор 1. На этом работа устройства будет закончена.
Данное устройство позволяет принять решение о достижении оптимума целевой функции в задачах двухпараметрической оптимизации.
Таким образом, при создании полезной модели решена техническая проблема создания технического средства определенного назначения (сравнительный анализ значений целевой функции в вершинах единичного симплекса, определение вершины с наименьшим значением отклика и выбор вершины симплекса, подлежащей замене) для принятия решения в двухпараметрических задачах оптимизации.