Материал: Введение в математическое моделирование технологического оборудования. курс лекций. Новокщенов С.Л., Бойко А.Ю

Рассмотрим специфику процессов случайного поиска при учете ограничений различного рода.

Ограничения типа неравенств

Ограничения типа неравенств (S=S_H) образует обычно область размерности n. Выход за границу этой области (C S) является сигналом о необходимости учета ограничений S. При случайном поиске это можно осуществить множеством способов. Рассмотрим наиболее эффективный из них.

С пособ возврата заключается в том, что нарушение ограничений S отождествляется с неудачным шагом, т. е. c не убыванием показателя качества ( ), для чего вводится оператор возврата. Таким образом, в процессе поиска различаются лишь две ситуации удачного и неудачного шагов:

: (C S) ( Q<0), : (C S) ( Q 0) (23.14)

т.е. удачным шагом считается случай , когда ограничения не нарушены и одновременно уменьшился показатель качества. Неудачным шагом считается тот, при котором нарушены ограничения или увеличился показатель качества. Реакцией на является возврат в предыдущее состояние ( C[N+1]=- C[N]) и случайный шаг. ( C[N+2]=a ). На удачу – можно реагировать по-разному. При случайном спуске (см. П. 15.3.2) - повторять удачный шаг ( C[N+1]= C[N]). При алгоритме с возвратом (п. 15.3.1) - вводить случайный шаг ( C[N+1]=a ).

Ограничения типа равенств

Учет ограничений типа равенств (S=S_G) в процессе случайного поиска связан с организацией движения вдоль этих ограничений. Это можно осуществить различными путями. Простейшим из них является введение “коридора”, т.е. переход к ограничениям типа неравенств:

||gj(C)||<e, f= (23.15)

При этом величина – должна стремиться к нулю в процессе поиска.

Ограничения типа неравенств и равенств

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

Дискретные ограничения

Простейшая схема следующего поиска в случае ограничений S_D опирается на случайный выбор новой точки в e - окрестности исходной точки. Пусть e - окрестность исходной точки С[N] имеет вид

||C-C[N]|| e (23.16)

и пусть для простоты множество S_p образовано целочисленными векторами С. Это означает, что все координаты этих векторов имеют целочисленные значения (более общий случай легко сводится к этому). Пусть D_e[N] - множество целочисленных точек, попавших в --окрестность, т.е. удовлетворяющих условию. Так, например, при e=1 таких точек будет 2n.

Тогда процедура случайного поиска на (N+1)-м шаге будет связана со случайным выбором такой точки множества D_e[N], для которой выполняются очевидные условия

Q(C[N+1])<Q(C[N], C[N+1] De[N]. (23.17)

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

Дискретные ограничения с неравенствами

Учет ограничений типа неравенств в задаче дискретной оптимизации (S_D S_H) незначительно усложняет процедуру случайного поиска. В этом случае к условиям (15.4.7) добавляется еще одно условие C[N+1] S_H , которое легко проверяется.

23.3. Алгоритмы структурной оптимизации

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

Дискретизация структуры

Если структура образуется набором структурных элементов, то ее удобно кодировать двоичным вектором

W=( ₁, ..., _n), (23.18)

где _i характеризует наличие ( _i=1) или отсутствие ( _i=0) i-го структурного элемента в проектируемой САУ. На вектор W могут быть наложены ограничения типа равенств и неравенств, характеризующие зависимость между структурными элементами. Тогда задача проектирования САУ сводится к решению следующей оптимизационной задачи:

(23.19)

где ограничения S имеют вид

(23.20)

Здесь функционалы Q, g_j и h_i определяются характером задачи проектирования конкретной САУ.

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

(23.21)

где v>0 - коэффициент штрафа, а область S` определена условиями

(23.22)

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

Другим способом сведения дискретной задачи (15.7.2) и непрерывной является рандомизация, в соответствии с которой вводится непрерывный вектор вероятностей

P=P₁, ..., P_n), (23.23)

в котором

P_k=P{w_k=1} (23.24)

-вероятность события w_k=1. С помощью этого вектора функционал Q(W) сглаживается:

(23.25)

где суммирование проводится по всем вариантам двоичного вектора—и введены обозначения

(23.26)

Сглаженный (или рандомизированный) функционал Q(W) зависит лишь от непрерывного вектора вероятностей Р. Легко видеть, что минимум этого функционала лежит в одной из вершин гиперкуба {P}, т.е. решение P_оп является двоичным вектором, который совпадает с решение исходной задачи. Для приближенной оценки значения сглаженного функционала при заданном Р можно воспользоваться методом Монте-Карло:

(23.27)

где N база оценки, а W_i случайный двоичный вектор распределения Р. С ростом N точности оценки естественно возрастает.