Определение 4.3

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

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

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

Ь, *=1,2.... т,

/)(х) < /)-(у) при максимизации функции /)-, /)(х) > /)(у) при минимизации функции f;.

4.8. Модификации классическоёо а

тического алгоритма

Определение 4.4

Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Паре-то.

Существует несколько классических методов, относящихся к многокритериальной оптимизации. Один из них - это метод взве-шенной функции (method of objective weighting), в соответствии с ко­торым оптимизируемые функции f, с весами w, образуют единую функцию

где wi e [0,1] и £ и/р 1

Различные веса дают различные решения в смысле Парето.

Другой подход известен как метод функции расстояния (method of distance function). Идея этого метода заключается в сравне­нии значений /j(x) с заданным значением у,-, т.е.

_f{x)=

да.

При этом, как правило, принимается г = 2. Это метрика Эвкли-

Еще один подход к многокритериальной оптимизации связан с разделением популяции на подгруппы одинакового размера (sub-populations), каждая из которых «отвечает» за одну оптимизируемую функцию. Селекция производится автономно для каждой функции, однако операция скрещивания выполняется без учета границ под­групп [33].

Алгоритм многокритериальной оптимизации реализован в про­грамме FlexTool [48]. Селекция выполняется турнирным методом, при этом «лучшая» особь в каждой подгруппе выбирается на основе функции приспособленности, уникальной для данной подгруппы. Схе­ма такой селекции в случае оптимизации двух функций представлена на рис. 4.17; на этом рисунке F₁ и F₂ обозначают две различные функ­ции приспособленности. Эта схема аналогична схеме, изображенной на рис. 4.10, с той разницей, что на более ранней схеме все подгруп­пы оценивались по одной и той же функции приспособленности. «На­илучшая» особь из каждой подгруппы смешивается с другими особя­ми, и все генетические операции выполняются так же, как в генетиче­ском алгоритме для оптимизации одной функции. Схему на рис. 4.17 можно легко обобщить на большее количество оптимизируемых функций. Программа FlexTool обеспечивает одновременную оптими­зацию четырех функций.

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

Дата добавления: 2015-06-04