4.8.7. Генетические алгоритмы для многокритериальной оптимизацииБольшинство задач, решаемых при помощи генетических алгоритмов, имеют один критерий оптимизации. В свою очередь, многокритериальная оптимизация основана на отыскании решения, одновременно оптимизирующего более чем одну функцию. В этом случае ищется некоторый компромисс, в роли которого выступает решение, оптимальное в смысле Парето. При многокритериальной оптимизации выбирается не единственная хромосома, представляющая собой закодированную форму оптимального решения в обычном смысле, а множество хромосом, оптимальных в смысле Парето. Пользователь имеет возможность выбрать оптимальное решение из этого множества. Рассмотрим определение решения, оптимального в смысле Парето (символами Определение 4.3 Решение
Определение 4.4 Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето. Существует несколько классических методов, относящихся к многокритериальной оптимизации. Один из них - это метод взвешенной функции (method of objective weighting), в соответствии с которым оптимизируемые функции
где Различные веса дают различные решения в смысле Парето. Другой подход известен как метод функции расстояния (method of distance function). Идея этого метода заключается в сравнении значений
При этом, как правило, принимается Еще один подход к многокритериальной оптимизации связан с разделением популяции на подгруппы одинакового размера (subpopulations), каждая из которых «отвечает» за одну оптимизируемую функцию. Селекция производится автономно для каждой функции, однако операция скрещивания выполняется без учета границ подгрупп [33]. Алгоритм многокритериальной оптимизации реализован в программе FlexTool [48]. Селекция выполняется турнирным методом, при этом «лучшая» особь в каждой подгруппе выбирается на основе функции приспособленности, уникальной для данной подгруппы. Схема такой селекции в случае оптимизации двух функций представлена на рис. 4.17; на этом рисунке Рис. 4.17. Схема турнирной селекции в случае многокритериальной оптимизации по двум функциям.
|