Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
11. Генетические алгоритмы для многокритериальной оптимизации: сущность вопроса, решение, оптимальное в смысле Парето; используемые методы.
Генетические алгоритмы для многокритериальной оптимизации
Большинство задач, решаемых при помощи генетических алгоритмов, имеют один критерий оптимизации. В свою очередь, многокритериальная оптимизация основана на отыскании решения, одновременно оптимизирующего более чем одну функцию. В этом случае ищется некоторый компромисс, в роли которого выступает решение, оптимальное в смысле Парето. При многокритериальной оптимизации выбирается не единственная хромосома, представляющая собой закодированную форму оптимального решения в обычном смысле, а множество хромосом, оптимальных в смысле Парето. Пользователь имеет возможность выбрать оптимальное решение из этого множества. Рассмотрим определение решения, оптимального в смысле Парето (символами х, у будем обозначать фенотипы).
Решение х называется доминируемым, если существует решение у, не хуже чем х, т.е. для любой оптимизируемой функции fi,i =1,2,…, m,
Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето. Существует несколько классических методов, относящихся к многокритериальной оптимизации. Один из них - это метод взвешенной функции (method of objective weighting), в соответствии с которым оптимизируемые функции fi, с весами wi, образуют единую функцию. Различные веса дают различные решения в смысле Парето. Другой подход известен как метод функции расстояния (method of distance function). Идея этого метода заключается в сравнении значений fi(x) с заданным значением уi.
Это метрика Эвклида.
Еще один подход к многокритериальной оптимизации связан с разделением популяции на подгруппы одинакового размера (sub-populations), каждая из которых «отвечает» за одну оптимизируемую функцию. Селекция производится автономно для каждой функции, однако операция скрещивания выполняется без учета границ подгрупп. Селекция выполняется турнирным методом, при этом «лучшая» особь в каждой подгруппе выбирается на основе функции приспособленности, уникальной для данной подгруппы. Схема такой селекции в случае оптимизации двух функций представлена на рис. 10.
Рис. 10. Схема турнирной селекции в случае многокритериальной оптимизации по двум функциям.
На этом рисунке F1 и F2 обозначают две различные функции приспособленности. «Наилучшая» особь из каждой подгруппы смешивается с другими особями, и все генетические операции выполняются так же, как в генетическом алгоритме для оптимизации одной функции. Схему на рис. 10 можно легко обобщить на большее количество оптимизируемых функций.
Генетические микроалгоритмы
Генетический микроалгоритм - это модификация классического генетического алгоритма, предназначенная для решения задач, не требующих больших популяций и длинных хромосом. Такие алгоритмы применяются при ограниченном времени вычислений в случае, когда решение (не обязательно глобальное) необходимо найти быстро. Речь идет о том, чтобы не производить трудоемких вычислений, связанных с большим количеством итераций. Генетические микроалгоритмы обычно находят несколько худшие решения, однако экономят вычислительные ресурсы компьютера. В качестве примера можно привести генетический микроалгоритм программы FlexTool. Он подразделяется на шесть шагов.
1. Сформировать популяцию с числом особей, равным пяти. Можно либо случайным образом выбрать все пять хромосом, либо сохранить одну «хорошую» хромосому, полученную на предыдущих итерациях, и случайным образом «добрать» четыре остальные хромосомы.
6. Перейти к шагу 2.
Заметим, что в генетическом микроалгоритме размер популяции предполагается небольшим и фиксированным. Применяется элитарная стратегия, которая предотвращает потерю «хороших» хромосом. Поскольку размер популяции невелик, то выполняется детерминированная селекция. Скрещивание проводится с вероятностью 1. Мутация не требуется, так как достаточное разнообразие обеспечивается формированием новой популяции при каждом «рестарте» алгоритма, т.е. в случае перехода к шагу 1 при обнаружении сходимости. Процедура «старта» и «рестарта» алгоритма предназначена для предотвращения преждевременной сходимости; генетический микроалгоритм всегда ищет наилучшие решения. Главная цель его применения заключается в скорейшем нахождении оптимального (или почти оптимального) решения.