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 обеспечивает одновременную оптимизацию четырех функций.

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