Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ИИС / поштучно / 23.Генетические алгоритмы для многокритериальной оптимизации

.docx
Скачиваний:
42
Добавлен:
02.03.2016
Размер:
44.68 Кб
Скачать

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

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

Решение x называется доминируемым, если существует решение y, не хуже чем x, т.е. для любой оптимизируемой функции fi, i = 1, 2, …, m

fi(x) ≤ fi(y) при максимизации функции fi,

fi(x) ≥ fi(y) при минимизации функции fi.

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

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

,

(68)

где и .

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

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

.

(69)

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

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

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

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