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

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

ННГУ, ВМК

Д.И. Батищев dibat@iani.unn.ru

Е.А. Неймарк e.neumark@mts-nn.ru

Н.В. Старостин nvstar@iani.unn.ru

603950, Н. Новгород, пр. Гагарина 23

Аннотация

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

Введение

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

Q^*(x)= min Q(x), xG,

0 |G| N < .(1)

Основной целью задачи дискретной оптимизации - является нахождение лучшего решения из конечного, но достаточно большого их числа. Задача дискретной оптимизации (1) является сложной не только для классических алгоритмов, но и для генетического алгоритма. Это связано с некоторыми особенностями задач данного класса. Во-первых, задачи имеют переборный характер, при этом с ростом параметров задачи перебор становится принципиально невозможным. Во-вторых, задачи являются нерегулярными, они могут иметь несколько оптимумов, в том числе локальные, значение функции в которых не совпадает с глобальным. Кроме того, область допустимых решений может быть несвязна и невыпукла. Затруднительно указать меру близости решений, поскольку «близкие» значения х₁,х₂G могут иметь сколь угодно далекие значения Q(х₁) и Q(х₂). Для определения близости решений в этих задачах используются различные техники, зависящие, в основном, от вида задачи.

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

1. Комбинаторные задачи

В качестве представителей из класса задач дискретной оптимизации рассматриваются две следующие задачи: задача о ранце и задача коммивояжера. Эти задачи из класса NP, их вычислительная сложность растет экспоненциально с ростом числа параметров [Гери и др., 1982] , [Сигал и др., 2002].

Задача коммивояжера формулируется следующим образом: дан полный взвешенный граф из N вершин, необходимо найти Гамильтонов цикл, имеющий минимальный вес. Или математически (1.1), где N - количество вершин графа, с_ij - вес ребра, ведущего из вершины i в вершину j.

(1.1)

Задача о ранце содержательно звучит так: дан набор из N предметов, каждый из которых имеет вес и ценность, из них нужно выбрать несколько предметов, чтобы общий вес предметов не превосходил определенного значения, и при этом суммарная их ценность была максимальной. Формально (1.2), где - с_i ценность предмета, а_i его вес, W - ограничение на общий вес предметов.

(1.2)

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

§ Методы отсечения

§ Комбинаторные

§ Приближенные.

Генетические алгоритмы (ГА) относятся к третьему типу.

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

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

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

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

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

2. Типы нестационарности в задачах

Стационарная задача коммивояжера однозначно задается матрицей весов ребер. При изменении весов с течением времени задача становится нестационарной, изменяется вид целевой функции (2.1).

(2.1)

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

(2.2)

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

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

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

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

3. Методы решения нестационарных задач

Методы, Применяемые для оптимизации нестационарных функций при помощи генетического алгоритма, условно можно разделить на несколько классов:

§ методы увеличения генетического разнообразия при изменении среды,

§ методы постоянного поддержания генетического разнообразия,

§ методы, использующие дополнительную память,

§ методы, использующие дополнительные популяции.

В этой работе, в основном, рассматривались методы, использующие дополнительную память. Использование памяти может быть явным и неявным.

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

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

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

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

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

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

4. Тесты и результаты

В работе сравнивались пять методов: три на основе гаплоидного представления решения, в том числе алгоритм с использованием внешней памяти, один на основе диплоидного представления (триаллельная схема) [Smith et al., 1992] и на основе структурного представления [Dasgupta, 1993].

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

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

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

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

Перечисленные выше алгоритмы сравнивались по скорости отклика на изменение состояния среды, коллективной приспособленности [Morrison, 2003]. Под скоростью отклика понимается количество замеров, произведенных алгоритмом после изменения среды, для прихода к оптимальному решению (в таблице приведено среднее количество поколений). Коллективная приспособленность для алгоритма, является значением лучшей в популяции особи, усредненным по количеству поколений в одном запуске и общему количеству запуска алгоритма.

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

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

Табл. 1

Список литературы

1. Гери и др., 1982 Гери М. , Джонсон Д. Вычислительные машины и трудно решаемые задачи: Пер. С англ.- М: Мир,1982.

2. Сигал и др., 2002 Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. Учебное пособие. - М.: Физматлит, 2002.

3. Dasgupta, 1993 Dasgupta D. Optimisation in Time-Varying environments using Structured Genetic Algorithms, Technical Report No IKBS-17-93, Dec. 1993.

4. Morrison, 2003 R. Morrison. Performance measurement in dynamic environments.// In J. Branke, editor, GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 5-8, 2003.

5. Smith et al., 1992 Smith R. E. ,. Goldberg D. E. Diploidy and Dominance. // in Artificial Genetic Search , Complex Systems, V.6, 1992, ph. 251--285.

Размещено на Allbest.ru