Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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

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

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

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

 при максимизации функции ,

 при минимизации функции .

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

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

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

,

где  и .

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

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

.

При этом, как правило, принимается . Это метрика Эвклида.

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

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

161.jpg

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

 



<< ПредыдущаяОглавлениеСледующая >>