Разработка и исследование адаптивного поискового алгоритма для решения многокритериальных задач условной оптимизации

2. Агрегирующая селекция с вариацией параметров

В данном случае целевые функции как в классических подходах агрегируются в одну параметризированную целевую функцию, однако параметры этой функции не изменяются при различных оптимизационных прогонах, а варьируются во время одного запуска.

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

3. Селекция, основанная на понятии Парето доминирования

Всем недоминируемым индивидам присваивается ранг 1 и временно они удаляются из популяции. Далее, следующим недоминируемым индивидам, назначается ранг 2 и они также убираются из рассмотрения. Этот процесс продолжается, пока всем индивидам не будет назначен определенный ранг относительно других членов популяции. В результате ранг индивида определяет его значение пригодности. Таким образом, пригодность связана со всей популяцией, в то время как в других агрегирующих подходах значение пригодности индивида вычисляется независимо от других индивидов.

2.3 Поддержание разнообразия популяции

Чтобы хорошо аппроксимировать Парето-оптимальное множество за один прогон, необходимо выполнять полимодальный поиск, чтобы обеспечить нахождение значительно отличающихся решений. Поэтому обеспечение разнообразия популяции, является важнейшим аспектом многокритериальной оптимизации генетическими алгоритмами. К сожалению, простой генетический алгоритм ведет к одному решению, т.е. не обеспечивает такой возможности, поэтому были разработаны и разрабатываются подходы, основные идеи наиболее используемых из которых и рассматриваются в диссертации [23].

1. Деление общей пригодности

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

Ниша - это группа индивидов, имеющих одинаковую пригодность. В многокритериальной и многоэкстремальной оптимизации для уменьшения пригодности индивидов, попавших в одну и ту же нишу, обычно используется подход, называемый делением общей пригодности. Это делается для того, чтобы предотвратить схождение популяции к одному решению. Таким образом, могут образовываться устойчивые подпопуляции, каждая из которых соответствует различным оптимумам функции [16].

Соседство или окрестность определяется через меру расстояния и так называемый радиус ниши . Математически общая пригодность индивида определяется как его старая пригодность , деленная на так называемый счетчик ниши:

.

В свою очередь счетчик ниши индивида определяется как сумма значений функции между ним и другими индивидами популяции:

В зависимости от того, как определяется функция расстояния, различают 3 типа деления пригодности:

· в пространстве индивидов ,

· в пространстве решений ,

· в критериальном пространстве ,

где - соответствующая метрика расстояния.

Наглядно взаимосвязь между этими тремя типами деления пригодности можно видеть на рисунке 1 (п. 2.1.1).

2. Ограниченное спаривание

Двум индивидам разрешено скрещиваться, только если они находятся на определенном расстоянии друг от друга, определяемом параметром . Так же как и при делении пригодности, расстояние между двумя индивидами может определяться с помощью 3-х рассмотренных выше метрик. Также стоит отметить, что данный подход не получил широкого распространения в практике.

3. Изоляция посредством дистанцирования

При данном механизме каждому индивиду назначается определенное положение. И, в общем, различаются 2 подхода: либо определяется пространственная структура одной популяции, таким образом, что образуются пространственные ниши; либо популяция разбивается на отдельные подпопуляции, которые лишь изредка обмениваются индивидами, при этом имеют место так называемые миграции случайных индивидов.

4. Переопределение

Согласно этому методу, индивиды состоят из активной и неактивной частей: первая определяет закодированный вектор решений, а неактивная часть не используется. Таким образом, информация может быть «спрятана» в индивиде, так как во время эволюции активная и неактивная части могут меняться местами.

5. Перезапуск

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

6. Уплотнение (объединение)

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

2.4 Элитизм

Наряду с поддержанием разнообразия важную роль играет понятие элитизма, основная идея которого заключается в том, чтобы всегда включать лучших индивидов в следующую популяцию, чтобы не потерять хорошие признаки вследствие действия генетических операторов. Использование элитизма гарантирует, что максимальная пригодность популяции не будет уменьшаться от поколения к поколению, а может только увеличиваться. В противовес методам, рассмотренным в предыдущем разделе, применение концепции элитизма в алгоритме обычно способствует более быстрой сходимости популяции. Поэтому, этот подход хорош при оптимизации унимодальных функций, а на многоэкстремальных может вызвать преждевременную сходимость [16, 23].

Соответственно, в отличие от однокритериальной оптимизации, использование концепции элитизма при многокритериальной оптимизации является более сложной процедурой, связанной с понятием доминирования. Вместо одного лучшего индивида здесь создается элитарное множество, чей размер может быть сравним с размерами самой популяции. В связи с этим возникают вопросы:

- Каких именно индивидов и как долго сохранять в элитарном множестве?

- Каких индивидов и когда возвращать в популяцию?

В общем, различают 2 основных элитарных подхода:

1. Напрямую копировать недоминируемых индивидов в следующую популяцию. Иногда используются варианты с ограничениями, когда только индивидов, оптимальных по какой-то определенной функции передаются в следующую популяцию независимо от значений по другим критериям.

2. Часто используется концепция поддержания внешнего множества индивидов, относительно всех индивидов популяции. Таким образом, в каждом поколении определенный процент популяции заполняется или заменяется представителями внешнего множества, которые выбираются случайно, либо согласно какому-либо критерию, например, по истечении времени, в течение которого индивид должен оставаться во внешнем множестве [23].

2.5 Методы многокритериальной оптимизации генетическими алгоритмами

Генетический алгоритм, применяемый для решения конкретной задачи, должен состоять из следующих основных компонентов [16]:

1. Представление потенциальных решений задачи.

2. Способ, которым создается начальная популяция возможных решений.

3. Функция оценки решений, которая играет роль внешней среды, определяющая решения в смысле их пригодности.

4. Генетические операторы, которые изменяют состав детей (потомков).

5. Значения различных параметров, которые используются генетическим алгоритмом (размер популяции, вероятность, с которой применяются генетические операторы и т.д.).

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

В диссертационной работе исследовались 4 метода, реализующие различные схемы назначения пригодности и селекции, о которых и пойдет речь далее:

1. VEGA - Vector Evaluated Genetic Algorithm [22];

2. FFGA - Fonseca and Fleming's Multiobjective Genetic Algorithm [18];

3. NPGA - Niched Pareto Genetic Algorithm [21];

4. SPEA - Strength Pareto Evolutionary Algorithm [23].

2.5.1 Метод VEGA (Vector Evaluated Genetic Algorithm)

Метод VEGA, который впервые был предложен в 1984 году Шафером, относится к категории селекции по переключающимся целевым функциям. В данном методе селекция производится для каждого из критериев отдельно, тем самым промежуточная популяция заполняется равными порциями индивидов, отобранных по каждому из критериев.

Назначение пригодности и селекция в методе VEGA:

Входные данные: (текущая популяция).

Выход: (промежуточная популяция).

Шаг 1: положить =1, и =0.

Шаг 2: для каждого индивида , , вычислить

.

Шаг 3: для

выбрать индивида , используя выбранный механизм селекции, основываясь на значении пригодности по данному критерию, и скопировать его в

:=+.

Шаг 4: положить

=+1.

Шаг 5: если , перейти на шаг 2, иначе - результирующая промежуточная популяция.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 2 - Механизм селекции в методе VEGA

2.5.2 Метод FFGA (Fonseca and Fleming's Multiobjective Genetic Algorithm)

Метод FFGA (1993) представляет собой основанную на Парето-доминировании процедуру ранжирования индивидов, где ранг каждого индивида определяется числом доминирующих его индивидов.

Назначение пригодности в методе FFGA:

Вход: (популяция).

Выход: (значения пригодности).

Шаг 1. Для каждого индивида вычислить его ранг

.

Шаг 2. Отсортировать популяцию согласно рангам . Назначить каждому индивиду посредством интерполирования от лучшего индивида к худшему сырую пригодность , то есть лучшему индивиду назначается сырая пригодность =, а худшему () - сырая пригодность =1.

Шаг 3. Вычислить значение пригодности для каждого индивида посредством усреднения и деления сырой пригодности между индивидами, имеющими одинаковый ранг:

,

- индивиды, имеющие одинаковый ранг , - количество индивидов, имеющих ранг r. Деление пригодности осуществляется в критериальном пространстве.

Метод FFGA реализует лишь схему назначения пригодности, а для отбора индивидов в следующее поколение используется процедура турнирной селекции с размером турнира = 2, которая осуществляется на основании полученных значений пригодности каждого индивида ,

.

На рисунке 3 представлены гипотетическая популяция и соответствующие ранги индивидов, назначенные согласно рассмотренной схеме метода FFGA. Индивиды, чьи соответствующие решения недоминируемы относительно всей популяции , имеют ранг 1, в то время как наихудший индивид, доминируемый всеми членами популяции получает ранг 10.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 3 - Механизм селекции в методе FFGA

В данном методе используется понятие пригодности, но, в отличие от пригодности в алгоритме VEGA, она назначается не для каждого критерия в отдельности, а для индивида в целом и определяется не значениями целевых функций, а рангом каждого индивида в популяции, который в свою очередь основан на понятии доминирования.

2.5.3 Метод NPGA (Niched Pareto Genetic Algorithm)

Третий рассматриваемый в работе метод - NPGA (1994) - принципиально отличается от двух предыдущих, так как в нем заложен механизм поддержания разнообразия (действует в критериальном пространстве). Метод NPGA представляет собой комбинацию турнирной селекции и концепции доминирования по Парето.

Назначение пригодности и селекция в методе NPGA:

Входными данными для этого метода являются:

(популяция),

(радиус ниши),

(давление доминирования - количество индивидов в сравнительном множестве ).

Выход: (промежуточная популяция).

Шаг 1. Положить =1 и промежуточную популяцию=0.

Шаг 2. Выбрать двух индивидов и сравнительное множество , состоящее из случайно выбранных индивидов популяции.

Шаг 3. Проверить условие: если недоминируем относительно , а доминируется индивидами сравнительного множества, то победителем турнира является индивид :

=+.

Шаг 4. Иначе, если недоминируем относительно , а - доминируем, то победителем турнира становится индивид :

=+.

Шаг 5. Если победитель турнира не определился, турнир разрешается делением общей пригодности:

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

: . Проделать то же для индивида .

б) если , то

=+, иначе =+,

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

Шаг 6. Положить

=+1.

Если , перейти на шаг 2, иначе стоп.

На рисунке 4 проиллюстрирован механизм Парето турнира: сопоставление 2-х индивидов популяции со сравнительным множеством индивидов. Участник турнира, обозначенный серой точкой, является его победителем, так как в отличие от другого участника, закодированный вектор данного индивида не доминируется представителями сравнительного множества.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 4 - Механизм селекции в методе NPGA

В рассмотренном методе не используется понятие пригодности как таковое, а этап назначения пригодности заменяется модифицированной схемой деления пригодности с использованием понятия ниш, которые определяются для индивидов в пространстве целевых функций.

2.5.4 Метод SPEA (Strength Pareto Evolutionary Algorithm)

Метод SPEA (1998) в корне отличается от рассмотренных ранее методов, так как в нем [23]:

- для назначения индивидам скалярного значения пригодности используется концепция Парето доминирования;

- индивиды, недоминируемые относительно других членов популяции, хранятся внешне в специальном внешнем множестве;

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

Уникальность и преимущества метода SPEA заключаются в том, что:

- он сочетает вышеперечисленные подходы в одном алгоритме;

- пригодность каждого индивида популяции в данном методе определяется только относительно индивидов внешнего множества, независимо от того, доминируют ли индивиды популяции друг друга;

- несмотря на то, что «лучшие» индивиды, полученные в предыдущих поколениях, хранятся отдельно - во внешнем множестве, все они принимают участие в селекции;

- а, для предотвращения преждевременной сходимости, в методе SPEA используется особый механизм образования ниш, где деление общей пригодности осуществляется не в смысле расстояния между индивидами, а на основе Парето доминирования.

Процедура метода SPEA [23]:

Вход: (размер популяции),

(размер внешнего множества),

(максимальное число поколений),

(вероятность скрещивания),

(вероятность мутации).

Выход: (недоминируемое множество).

Шаг 1. Инициализация:

Создать начальную популяцию , согласно 1 этапу схемы общего эволюционного алгоритма, и пустое внешнее множество . Положить =0.

Шаг 2. Модернизация внешнего множества:

Положить промежуточное внешнее множество .

а) скопировать индивидов, чьи векторы решений недоминируемы относительно

в : =+ .

б) удалить тех индивидов из , чьи соответствующие векторы решений слабо доминируемы относительно , то есть, если существует пара с индивидами и , то

=-.

в) уменьшить посредством кластеризации (с параметрами и ) число индивидов, хранящихся во внешнем множестве, и поместить результирующее уменьшенное множество в .

Шаг 3. Назначение пригодности:

Вычислить значения пригодности индивидов в и .

Шаг 4. Селекция:

Положить =0 и для

выполнить:

а) случайным образом выбрать двух индивидов

,

б) если , то

=+, иначе

=+ (в случае задачи минимизации).

Шаг 5. Рекомбинация:

Рекомбинация осуществляется согласно 4 этапу в схеме общего эволюционного алгоритма.

Шаг 6. Мутация:

Мутация осуществляется согласно 5 этапу в схеме общего эволюционного алгоритма.

Шаг 7. Окончание:

Положить и . Если или выполняется какой-то другой критерий остановки, тогда

- есть искомое недоминируемое множество, иначе перейти на шаг 2.

Основной цикл описанного алгоритма схематично показан на рисунке 5. Шаг 1 не обозначен на представленном рисунке, так как инициализация начальной популяции осуществляется один раз и является обязательным первичным этапом любого эволюционного алгоритма. Далее, в начале каждой итерации (Шаг 2) происходит модернизация внешнего множества и его уменьшение, если максимальный размер был превышен. После этого происходит оценка индивидов из относительно индивидов внешнего множества для назначения индивидам популяции значений пригодности (Шаг 3). Следующий шаг (Шаг 4) представляет фазу селекции, когда отбираются индивиды из объединенного множества + для заполнения промежуточной популяции (в данной схеме используется турнирная селекция с удалением индивида, «проигравшего» турнир). Наконец, скрещивание и мутация (Шаг 5 и Шаг 6) осуществляются как соответствующие этапы общего эволюционно алгоритма.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 5 - Основные шаги метода SPEA

Однако в схеме метода SPEA этап назначения пригодности осуществляется не так, как в общем эволюционном алгоритме, а представляет собой модифицированную процедуру, основанную на концепции Парето доминирования. Наряду с этим этапом, механизм кластеризации, используемый для уменьшения количества индивидов во внешнем множестве, также осуществляется по особой схеме. Алгоритмы пошаговой реализации обеих процедур представлены ниже.

Назначение пригодности в методе SPEA:

Вход: (популяция),

(внешнее множество).

Выход: (значения пригодности).

Шаг 1. Каждому индивиду присваивается значение , называемое «силой» индивида (отражает пригодность недоминируемого решения), которое пропорционально количеству членов популяции , для которых :

.

Таким образом, пригодность индивида , принадлежащего внешнему множеству, равна его «силе»: .

Шаг 2. Пригодность индивида вычисляется посредством суммирования «сил» всех индивидов , хранящихся во внешнем множестве, чьи векторы решений слабо доминируют . К общему полученному числу добавляется единица, чтобы гарантировать, что индивиды внешнего множества имеют лучшую пригодность, по сравнению с индивидами из (то есть, чем меньше пригодность, тем у индивида больше шансов перейти в следующее поколение):

, где .

Чтобы механизм ранжирования стал более понятным, обратимся к рисунку 6. Пять недоминируемых решений, обозначенных серыми точками, разбивают область критериального пространства на прямоугольники. Каждое подмножество внешнего множества определяет один такой прямоугольник, представляющий область в критериальном пространстве, которая в общем доминируется всеми векторами решений в . Например, на представленном рисунке светлый прямоугольник в нижнем левом углу доминируется всеми векторами решений в , в то время как верхний левый светлый прямоугольник доминируется только . Прямоугольники здесь рассматриваются как ниши, а цель состоит в том, чтобы так распределить индивидов по искусственно созданной сетке, чтобы прямоугольники (темные), доминируемые только несколькими , содержали больше индивидов, чем прямоугольники (светлые), доминируемые большим количеством индивидов из , а также два прямоугольника (одинаково окрашенные) должны содержать одинаковое количество индивидов, если они доминируются равным количеством решений. Этот механизм отражает идею предпочтения индивидов, расположенных вблизи Парето-оптимального фронта и, в то же время, их распределения вдоль всего пространства поиска, что можно видеть на рисунке 6: индивиды, сосредоточенные в светлых прямоугольниках, вдоль недоминируемых точек, получают лучшую пригодность, чем оставшиеся члены популяции, а при удалении от фронта Парето, пригодность индивидов ухудшается.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 6 - Механизм селекции в методе SPEA

Механизм кластеризации в методе SPEA:

Вход: (внешнее множество),

(размер внешнего множества).

Выход: (модернизированное внешнее множество).

Шаг 1. Инициализировать множество кластеров . Каждый индивид образует отдельный кластер:

.

Шаг 2. Если , перейти на Шаг 5, иначе перейти на Шаг 3.

Шаг 3. Вычислить расстояния между всеми возможными парами кластеров. Отдаленность двух кластеров и друг от друга определяется как среднее расстояние между парами индивидов, принадлежащих этим кластерам:

,

где функция отражает расстояние (в пространстве целей) между двумя индивидами и .

Шаг 4. Определить два кластера и с минимальным расстоянием . Эти кластеры объединяются в один больший по размеру кластер:

.

Перейти на Шаг 2.

Шаг 5. Для каждого кластера выбрать репрезентативного индивида, а всех остальных индивидов из него удалить. (Таким образом, репрезентативный индивид - это точка с минимальным средним расстоянием до всех остальных точек кластера.) Определить уменьшенное недоминируемое множество путем объединения репрезентативных индивидов всех кластеров:

.

При решении некоторых задач, размер множества Парето может быть довольно значительным и даже содержать бесконечное число решений. Однако, с точки зрения ЛПР, нахождение всех недоминируемых решений, когда их количество превышает разумные пределы, является бесполезным. Более того, размер внешнего множества влияет на поведение метода SPEA. С одной стороны, так как все индивиды внешнего множества участвуют в селекции, слишком большое количество хранящихся внешне индивидов может уменьшить селективное давление и замедлить поиск. С другой стороны, усиленный механизм ниширования основывается на образовании так называемой «сетки», определяемой индивидами внешнего множества и, если индивиды из разбросаны неравномерно, представленный выше метод назначения пригодности направит алгоритм в определенные области поискового пространства, что, в свою очередь, приведет к несбалансированности в популяции. Поэтому, порой может быть необходимым и даже обязательным уменьшение размеров внешнего множества, при сохранении его основных характеристик.

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

Таким образом, в данном разделе были рассмотрены 4 алгоритма, реализующие этапы назначения пригодности и/или селекции в схеме общего эволюционного алгоритма. Результаты их сравнительного анализа представлены в следующем разделе.

2.6 Сравнительный анализ методов многокритериальной оптимизации генетическими алгоритмами

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

2.6.1 Тестовые задачи

Рассматривались следующие задачи:

2-хкритериальная задача, где в качестве критериев выступали квадратичные функции:

,

.

2) 2-хкритериальная задача, с критериями - тестовыми функциями:

- Функция Растригина:

- с минимумом f(x)=0 в точке .

- Функция Розенброка: с минимумом f(x)=0 в точке .

3) 3-хкритериальная задача, где критериями были квадратичные функции:

,

,

.

4) Условная задача с одной целевой функцией и тремя ограничениями - квадратичными функциями:

целевая функция - ,

ограничения:,

,

.

2.6.2 Параметры алгоритмов

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

Как уже было сказано в п. 2.1.1, решения в генетических алгоритмах представляются в виде хромосом - бинарных строк, длина которых (количество битов) зависит от интервала (a,b - наименьшее и наибольшее значения, которые может принимать переменная - границы интервала) и точности вычислений и определяется по следующей формуле:

.

Существуют разные виды мутации и скрещивания, основными из которых являются: скрещивание - одноточечное, двухточечное и равномерное; вероятность мутации - низкая , средняя и высокая (, соответственно, - длина хромосомы, определенная выше). Но так как в данной работе эти параметры не являлись предметом исследования, поскольку в эволюционных многокритериальных алгоритмах определяющую роль играют механизмы селекции, назначения пригодности и поддержания разнообразия, реализующиеся в соответствующих алгоритмах (см. п. 2.5), их особенности здесь не приводятся.

Была проверена работа алгоритмов с различными сочетаниями параметров, характеризующих скрещивание и мутацию, и выбраны их наиболее подходящие значения для рассматриваемых алгоритмов. Для того чтобы при решении тестовых задач объективно оценивать работоспособность разных алгоритмов, общие для них параметры не менялись, а сами методы отличались лишь некоторыми параметрами, специфическими для каждого конкретного алгоритма в отдельности. Для наглядности общие и специфические параметры методов VEGA, FFGA, NPGA и SPEA сведены в таблицу 1.

Таблица 1 - Параметры алгоритмов

Параметры алгоритма	VEGA	FFGA	NPGA	SPEA
Количество поколений	1000	1000	1000	1000
Общий размер популяции	100	100	100	100
Границы поискового пространства
Точность вычислений	0,001	0,001	0,001	0,001
Тип скрещивания	двухточ.	двухточ.	двухточ.	двухточ.
Вероятность скрещивания	0,8	0,8	0,8	0,8
Вероятность мутации	низкая	низкая	низкая	низкая
Размер внешнего множества	-	-	-	30
Радиус ниши	-	-	2	-
Давление доминирования	-	-	5	-

2.6.3 Результаты решения тестовых задач методами VEGA, FFGA, NPGA и SPEA

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

1) 2-хкритериальная задача с квадратичными функциями

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

1.1) VEGA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 7 - Результаты решения 2-хкритериальной задачи

с квадратичными функциями методом VEGA

Как видно из рисунка 7 решения (точки) в основном группируются в нескольких областях, т.е. не обеспечивается хорошая представительность получаемого множества. Эта особенность характерна для рассматриваемого метода VEGA. Но преимуществом данного подхода является то, что почти все точки, отражающие недоминируемый фронт лежат на линии Парето-оптимального фронта.

1.2) FFGA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 8 - Результаты решения 2-хкритериальной задачи

с квадратичными функциями методом FFGA

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

1.3) NPGA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 9 - Результаты решения 2-хкритериальной задачи

с квадратичными функциями методом NPGA

Как видно из рисунка 9 при решении задачи методом NPGA результирующие точки-решения распределены достаточно равномерно, что является результатом работы заложенного в данный метод механизма поддержания разнообразия, при этом расстояние между точками соответствует радиусу ниши, а их количество значительно уменьшается по сравнению с методом FFGA. Зато в отличие от двух предыдущих методов, недоминируемые точки в методе NPGA повторяют наклон прямой - множества Парето, но в пространстве решений находятся дальше от него, чем в методе FFGA. А также много точек находится не на линии множества Парето, что в свою очередь вызывает проблему плохой точности аппроксимации.

1.4) SPEA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 10 - Результаты решения 2-хкритериальной задачи

с квадратичными функциями методом SPEA

В сравнении с вышерассмотренными результатами, которые дают методы VEGA, FFGA и NPGA, получаемое при решении 2-хкритериальной задачи с использованием метода SPEA множество недоминируемых точек (как и недоминируемый фронт) является наиболее представительным и расположенным наиболее близко к действительному множеству Парето, а в критериальном пространстве все точки недоминируемого фронта лежат на линии фронта Парето. Таким образом, метод SPEA показал лучшие результаты при решении 2-хкритериальной задачи с критериями - квадратичными функциями.

2) 2-хкритериальная задача с функциями Растригина и Розенброка

Для получения в данной задаче множества Парето все пространство поиска (от -5 до 7 по каждой координате) было представлено в виде сетки с шагом 0.1 по обеим координатам. По полученным значениям комбинаций были получены значения критериев (функции Растригина и функции Розенброка) в точках сетки. Далее из всех точек сетки, по полученным значениям функций, были определены недоминируемые точки, которые и представляют собой искомое множество Парето для рассматриваемой задачи, которое далее на рисунках 11-14 изображено в виде кривой, соединяющей найденные точки. А в виде кружков на представленных рисунках обозначены результирующие недоминируемые точки.

2.1) VEGA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 11 - Результаты решения 2-хкритериальной задачи

с функциями Растригина и Розенброка методом VEGA

2.2) FFGA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 12 - Результаты решения 2-хкритериальной задачи

с функциями Растригина и Розенброка методом FFGA

2.3) NPGA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 13 - Результаты решения 2-хкритериальной задачи

с функциями Растригина и Розенброка методом NPGA

2.4) SPEA

а) Множество Парето и б) Парето-оптимальный и

недоминируемые точки недоминируемый фронты

Рисунок 14 - Результаты решения 2-хкритериальной задачи

с функциями Растригина и Розенброка методом SPEA

При решении 2-хкритериальной задачи с функциями Растригина и Розенброка в качестве критериев, по всем 4-м методам были получены примерно одинаковые результаты. Но в методах FFGA (рисунок 12), NPGA (рисунок 13) и SPEA (рисунок 14) точки-решения, близкие к паретовским (или точки Парето), получались в большем количестве прогонов, при этом, по сути, алгоритмы выдавали одну точку - точку минимума функции Растригина (0,0) вместо всего множества Парето-оптимальных в этой задаче точек. Однако, указанная точка при применении методов FFGA, NPGA и SPEA выдавалась еще на первых поколениях поиска, а при использовании метода VEGA (рисунок 11), точки-решения постепенно стягиваются к множеству Парето и в результате получается не одна, а несколько точек, принадлежащих множеству Парето. То есть, в случае решения 2-хкритериальной задачи с критериями - тестовыми функциями Растригина и Розенброка, при применении метода VEGA получается более представительное множество недоминируемых решений, чем в других рассматриваемых методах, но при этом требуемого решения можно добиться не во всех запусках алгоритма.

3) 3-хкритериальная задача

При решении 3-хкритериальной задачи с критериями - квадратичными функциями, результирующее множество Парето представляет собой уже не прямую, как в 2-хкритериальной задаче, а треугольник в пространстве решений, при этом множество Парето включает все точки этого треугольника: как внутри него, так и на границе. Соответственно и в критериальном пространстве - фронтом Парето будет трехмерный криволинейный треугольник, соответствующий треугольнику Парето в пространстве решений. Но для лучшего представления результатов в критериальном пространстве, фронт Парето изображен в виде двухмерных проекций критериев, взятых попарно. Описанная ситуация показана на рисунках 15-18. Точками в пространстве решений, как и в случае 2-хкритериальной задачи, обозначены результирующие недоминируемые решения, а в критериальном - соответствующий им недоминируемый фронт.

3.1) VEGA



а) Множество Парето и недоминируемые точки

б) Парето-оптимальный и недоминируемый фронты

Рисунок 15 - Результаты решения 3-хкритериальной задачи

с квадратичными функциями методом VEGA

Как и в случае 2-хкритериальной задачи, метод VEGA (рисунок 15) показал не самые лучшие результаты - итоговые точки-решения в основном группируются в какой-то одной или нескольких областях, т.е. не обеспечивается хорошая представительность получаемого множества (разнообразие популяции), при этом зачастую эти точки вообще далеки от действительных Парето-оптимальных точек.

3.2) FFGA

а) Множество Парето и недоминируемые точки



б) Парето-оптимальный и недоминируемый фронты

Рисунок 16 - Результаты решения 3-хкритериальной задачи

с квадратичными функциями методом FFGA

Как видно из рисунка 16 метод FFGA и для 3-хкритериальной оптимизации квадратичных функций дает сравнительно неплохие результаты, так как обеспечивает по сравнению с предыдущим методом нахождение довольно представительного множества решений (но, тем не менее, не достаточного). Однако разнообразие чаще всего поддерживается лишь по одной из переменных, в чем метод FFGA в некотором смысле схож по действию со схемой селекции VEGA. Зато при применении этого подхода результирующее множество недоминируемых решений почти не содержит неоптимальных по Парето точек, то есть аппроксимирует действительное множество Парето более точно.

3.3) NPGA

а) Множество Парето и недоминируемые точки



б) Парето-оптимальный и недоминируемый фронты

Рисунок 17 - Результаты решения 3-хкритериальной задачи

с квадратичными функциями методом NPGA

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

3.4) SPEA

а) Множество Парето и недоминируемые точки



б) Парето-оптимальный и недоминируемый фронты

Рисунок 18 - Результаты решения 3-хкритериальной задачи

с квадратичными функциями методом SPEA

Как видно из рисунка 18 (и результатам, рассмотренным ранее - рисунок 10) метод SPEA сочетает в себе достоинства указанных выше методов и дает по совокупности лучшие результаты по сравнению с остальными методами. При его работе использованием кластеров обеспечивается разнообразие популяции, а за счет того, что во внешнем множестве хранятся недоминируемые точки, в результате обеспечивается хорошая аппроксимация Парето-оптимального фронта, особенно при решении 2-хкритериальной задачи с квадратичными критериями. Также стоит отметить еще одно (очень важное иногда) достоинство этого метода, которое заключается в возможности задания количества точек-решений, получаемых при работе алгоритма, априори.

4) Условная задача

На основании полученных результатов и, исходя их сложности задачи - наличие трех ограничений, для решения условной задачи был выбран метод SPEA. Результаты решения задачи с ограничениями с помощью метода SPEA представлены на рисунке 19.

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

Для того чтобы решить условную задачу методом SPEA, предварительно необходимо представить ее в виде многокритериальной задачи. Подробнее эта процедура описывается ниже, в разделе 3.1.

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

Рисунок 19 - Множество Парето и недоминируемые точки

при решении условной задачи методом SPEA

Как видно из рисунка решение задачи с ограничениями с использованием метода SPEA не удовлетворяет ответу задачи - не отображает искомую точку условного минимума. Недоминируемые точки разбросаны, причем большая их часть даже не лежит в допустимой области. Таким образом, можно сделать вывод, что метод SPEA не справился с поставленной задачей - не сошелся к точке условного оптимума. Но, так как он показал себе как перспективный метод решения безусловных задач, следовательно, он просто не приспособлен для решения задач с ограничениями и для решения подобных задач требуется его модификация, учитывающая специфику условной задачи.

Выводы

Благодаря заложенному параллелизму, у генетических алгоритмов есть большой потенциал в нахождении множества Парето-оптимальных решений при однократном запуске. Однако в большинстве сложных задач невозможно сгенерировать эффективные точки, представляющие более-менее полное множество Парето. Поэтому цель многокритериальной оптимизации может быть переформулирована и представлена в общем виде в виде трех подцелей [23]:

- отдаленность полученного недоминируемого фронта от Парето-оптимального фронта должна быть минимальна;

- желательно хорошее (в большинстве случаев однородное) распределение найденных решений;

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

Как показали проведенные исследования 4 методов многокритериальной оптимизации генетическими алгоритмами (см. п. 2.6), наиболее хорошо достичь всех подцелей, а, следовательно, и наиболее точно решить исходную задачу многокритериальной оптимизации удается при использовании метода SPEA.

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

Глава 3 Алгоритм решения многокритериальной задачи условной оптимизации

При формулировке реальных задач оптимизации - задач технического проектирования, задач распределения ресурсов и других - из физических, технических или экономических соображений обычно приходится накладывать на переменные известные ограничения [1]. Таким образом, учет лишь только многокритериальной составляющей задачи не отражает истинной картины выбора ее эффективного решения. В подобных задачах этот выбор может производиться только из некоторого подмножества пространства решений. Это подмножество обычно задается неявно, системой дополнительных уравнений, называемых уравнениями ограничений или просто ограничениями. Система ограничений может состоять из ограничивающих равенств, ограничивающих неравенств или тех и других вместе. Ограничения задачи образуют допустимую область, в которой в итоге должны находиться решения, а сама задача оптимизации при этом называется условной.

В классических методах математического программирования в постановке условной задачи присутствует лишь одна целевая функция при наличии нескольких ограничений. А что же делать, если исходная задача оптимизация к тому же еще является и многокритериальной?

Как мы выяснили в главе 2, большую перспективность при решении многокритериальных задач оптимизации имеет применение эволюционного подхода. Но решение задачи с ограничениями одним из методов многокритериальной оптимизации генетическими алгоритмами (методом SPEA) показало, что применение одного только эволюционного подхода не достаточно, так как в итоге не обеспечивается сходимость к точке условного оптимума, а большинство результирующих недоминируемых решений вообще не попадает в допустимую область (см. п. 2.6.3). Возникающие при решении условных многокритериальных задач проблемы вызывают отсутствие эффективных методов решения задач подобного класса: как свидетельствует [17] в разработках по генетическим алгоритмам представлены методы решения лишь безусловных многокритериальных задач, оставляя область исследования многокритериальных задач с ограничениями практически неизученной. Поэтому основным предметом исследования в представленной диссертационной работе является разработка алгоритма, использующего методы многокритериальной оптимизации генетическими алгоритмами, но способного при этом эффективно решать задачи условной оптимизации.

Основная идея разработанного алгоритма

Основная идея подхода состоит в сведении исходной условной задачи к многокритериальной и дальнейшем поиске решения составленной таким образом безусловной многокритериальной задачи. При этом поиск Парето-оптимальных точек осуществляется с помощью проверенного на тестовых задачах эволюционного многокритериального алгоритма - метода SPEA. Впоследствии, используя известный алгоритм локального поиска, происходит “лечение” точек, полученных после остановки генетического алгоритма, для достижения более точного конечного результата - точки условного оптимума.

Таким образом, разработанный алгоритм представляет собой многошаговую процедуру, которая состоит из следующих основных этапов:

1. Представление исходной условной задачи в виде набора критериев - сведение к безусловной многокритериальной задаче.

2. Решение полученной задачи выбранным методом многокритериальной оптимизации генетическими алгоритмами - методом SPEA.

3. Улучшение (“лечение”) точек-решений многокритериальной задачи с помощью алгоритма локального поиска. Результат - стягивание к точке условного оптимума.

Рассмотрим каждый из этапов более подробно.

3.1 Сведение условной задачи к безусловной многокритериальной задаче

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

- Исходная задача:

целевые функции - , ограничения - ;

- Преобразованная задача:

целевые функции - , .

3.2 Решение условной задачи методом SPEA

Разработка алгоритма проводилась путем модернизации метода SPEA, показавшего в совокупности лучший результат при решении тестовых задач среди рассматриваемых в диссертации методов (см. п. 2.6). Но при этом непосредственно учитывалась специфика исходной задачи - наличие в ней ограничений.

Как оказалось, сведение условной задачи к многокритериальной и ее решение методом SPEA должным образом не решает проблему нахождения множества Парето: значительное количество получаемых решений в итоге не принадлежит допустимой области (см. п. 2.6.3). Отсюда следует вывод, что необходимо каким-то образом «сгонять» недоминируемые точки в допустимую область. Для этого используется информация, получаемая от ограничений исходной задачи, то есть они не отбрасываются, а учитываются при оптимизации наряду с целевыми функциями. Правда, как показали эксперименты, лучше всего это делать на завершающем этапе всего периода оптимизации методом SPEA, когда ограничения играют даже большую роль, чем целевые функции.

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

3.3 Лечение точек-решений локальным поиском

На последнем этапе алгоритма решения условной задачи многокритериальной оптимизации происходит улучшение полученных после остановки работы генетического алгоритма недоминируемых точек.

Благодаря тому, что решения в генетических алгоритмах представляются в виде бинарной строки, для «лечения» недоминируемых точек очень удобным представляется использование алгоритма локального поиска, действующего в пространстве булевых переменных. Для того чтобы эта процедура стала более понятной, дадим основные понятия теории локального поиска.

Алгоритм локального поиска

Главная идея локального поиска - существование окрестности, которая представляет собой некоторое множество решений, близких к текущему решению в некотором смысле [11].

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

В алгоритме локального поиска отыскание оптимального решения осуществляется посредством просмотра точек окрестности, меняя компоненты булева вектора решений. А решение о переносе поиска в новую точку принимается после просмотра ближайших точек окрестности. При этом различают 2 способа просмотра окрестности: 1) наискорейший спуск, когда просматривается вся окрестность и осуществляется переход в точку с наилучшим значением функции, и 2) переход по первому улучшению - очевидная альтернатива наискорейшему спуску, который следует применять в условиях, когда отсутствует специфическая информация, дающая повод надеяться, что "наискорейший" спуск будет действительно наискорейшим [11].

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

Таким образом, после остановки генетического алгоритма получаются недоминируемые точки, среди которых есть как удовлетворяющие ограничениям, так и недопустимые точки. Для того чтобы свести недопустимые точки к допустимым, происходит их так называемое “лечение”, которое осуществляется с помощью алгоритма паретовского локального поиска. Так как заранее не известно, что, применяя «лечение» точек, мы получим их реальное улучшение, в разработанном алгоритме при просмотре окрестности используется стратегия перехода по первому улучшению. При этом паретовский локальный поиск, действующий в пространстве булевых переменных, включает просмотр 1-соседних, 2-соседних и 3-соседних точек окрестности (точек, отличающихся одной, двумя и тремя координатами соответственно). Процедура улучшения точек паретовским локальным поиском осуществляется уже с учетом целевых функций.