Эволюционная оптимизация структуры

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

W+ S (23.28)

Задача структурной оптимизации записывается в виде

(23.29)

Процесс эволюции структуры W происходит поэтапно. На первом этапе порождаются измененные структуры:

W_0.i=W₀+ _i, i=1, k₀, (23.30)

где _i i-я случайная вариация структуры, ограниченная. Число новых структур k₀– является параметром, который назначается из конкретных условий эволюции данной структуры.

Новые структуры (15.7.12) оцениваются по критерию эффективности

Q_0.i=Q(W_0.i), i=1, k₀ (23.31)

и далее происходит отбор, в процессе которого отсеиваются структуры с большим значением минимизируемого функционала Q, в результате чего на следующий этап эволюции остаются q₀<k₀ структур. Можно применять алгоритм вероятностного отбора, при котором структура, имеющая большее значение минимизируемого критерия, выбывает с большей вероятностью, чем структура с меньшим значением критерия. Вероятность такого выбора для Q>0 может быть определена соотношением

(23.32)

При этом процесс “разыгрывания” выбывающих структур заканчивается тогда, когда остается q₀ структур.

Заметим, что вполне может оказаться (особенно при малом k₀), что лучшая из новых структур хуже исходной W₀. В этом случае естественно W₀ сохранить на следующий этап эволюции. На втором этапе эволюции каждая из остающихся структур изменяется аналогично и дает столько новых структур, чтобы их общее число вместе с исходными было равно k₀. Последующий отбор составляет q₁ структур на следующий этап эволюции, и т.д. Легко видеть, что такого рода эволюция структуры будет стремиться отбирать структуры с малым значением критерия качества, среди которых находится и оптимальная структура. Случайность вариаций и отбор обеспечивают целенаправленность процесса эволюции к оптимальному решению W_оп. Рассмотрим влияние параметров k_i и q_i (i=0,1, ...). Эти параметры позволяют изменять число структур на каждом этапе и уровень отбора. При q_i=1 на следующий этап эволюции оставляется лишь одна структура. Такая структура эффективна при унимодальности задачи. Ее многоэкстремальность требует q_i>1 и значение q_i тем больше, чем сложнее поиск глобального экстремума. Число k_i также влияет на эффективность процесса эволюции. При большем k_i эволюция имеет глобальную тенденцию, но идет медленней, т.е. требует значительных затрат времени и памяти ЭВМ.

Здесь изложены примеры структурной оптимизации без параметрической подстройки параметров С объекта. Параметрическая оптимизация, если она необходима для повышения эффективности структур, легко вводится перед стадией отбора и осуществляется параметрическими методами, рассмотренными выше. Рассмотрим в качестве примера структуры, описываемые графом. В этом случае в процессе оптимизации оптимизирует граф. Пусть структура W объекта описывается графом

Г=<А,В>, (23.33)

где А - множество из n его вершин, а В - множество ребер с их параметрами:

В=[b_ij]_nXn, (23.34)

где b_ij - параметры дуги, соединяющей i-ю и j-ю вершины. На графе Г задан функционал качества, который следует минимизировать:

(23.35)

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

• объединение двух случайно выбранных вершин графа в одну;

• введение новой (n+1)-й вершины со случайными связями b_n+1, i(i= ) и b_j,n+1 (j= );

• устранение случайно выбранной вершины вместе с ее связями;

• введение новой связи двух случайно выбранных вершин;

• устранение случайно выбранного ребра;

• случайное “переключение” случайно выбранного ребра и т.д.

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

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

Вопросы для самоподготовки:

1. В чем заключаются задачи оптимального проектирования?

2. Как при оптимальном проектировании выполняется учет ограничений?

3. Приведите основные алгоритмы структурной оптимизации?