Содержание к диссертации
Введение
Г'лава 1. Эволюционные методы вычислений и некоторые их приложения 11
1.1 Основные схемы эволюционных алгоритмов . 11
1.2 Вопросы теоретического анализа эволюционных алгоритмов 22
1.3 Генетический алгоритм для задачи о вершинном покрытии графа 27
1.4 Генетические алгоритмы для задачи о доставках . 34
Г'лава 2. Моделирование и сравнение эволюционных алгоритмов 42
2.1 Описание модели 42
2.2 Анализ алгоритма (1,А)-ЕА 46
2.3 Анализ алгоритма (1+1)-ЕА 50
2.4 Сравнение (1+1)-ЕА с другими эволюционными алгоритмами 53
2.5 Сложность операторов мутации 65
Плава 3. Экспериментальное исследование эволюционных алгоритмов для двух комбинаторных задач . 71
3.1 Постановка задачи 71
3.2 Исследование величины штрафа 73
3.3 Экспериментальное сравнение алгоритмов ГА, ИО и (М + А)-ЕА 77
3.4 Сравнение теоретической модели (1 -f- 1)-ЕА с экспериментальными данными 83
3.5 Экспериментальное сравнение алгоритмов на задаче максимальной выполнимости 88
Заключение 90
Список литературы 92
Приложение
- Вопросы теоретического анализа эволюционных алгоритмов
- Генетические алгоритмы для задачи о доставках
- Сравнение (1+1)-ЕА с другими эволюционными алгоритмами
- Экспериментальное сравнение алгоритмов ГА, ИО и (М + А)-ЕА
Введение к работе
Диссертация посвящена разработке, моделированию и сравнению различных эволюционных алгоритмов для решения задач дискретной оптимизации. Эволюционные алгоритмы (ЭА) - сравнительно новые эвристические методы поиска, которые успешно применяются при решении оптимизационных задач различных типов. В основе ЭА лежат элементы теории эволюции Ч. Дарвина [16], такие как наследственность, изменчивость и отбор. Многие термины, используемые при описании ЭА (особь, мутация, кроссинговер и др.), заимствованы из биологии, и обозначают элементы алгоритма, сходные с аналогичными объектами и процессами в природе.
Область практического применения ЭА включает в себя задачи планирования и размещения производства [14,82], управления потоками продукции [62,96], составления расписаний [98], раскроя и упаковки [29], проектирования автоматических производственных линий [59] и многие другие [12,17,65]. Известно большое количество различных реализаций ЭА для решения классических задач дискретной оптимизации, таких как задача целочисленного линейного программирования [18,64], задача коммивояжера [68], задача о выполнимости логической формулы [70], задачи о покрытии и упаковке множеств [43,45,49] и т.д.
Основная идея ЭА достаточно проста и интуитивно понятна: необходимо построить некоторое множество решений оптимизационной задачи, и путем случайных преобразований из имеющихся решений строить новые, удаляя решения "низкого" качества. Такой подход лег-ко реализуется программно, хотя, несомненно, связан с большими вычислительными затратами. Появление в последнее время доступных компьютеров высокой скорости вычислений и с большим объемом памяти позволило преодолеть эту трудность, благодаря чему популяр-
ность ЭА значительно возросла.
Отличительной особенностью ЭА, которая позволяет избегать локализации поиска в областях с низким качеством решений, является организация процесса таким образом, что на каждой итерации хранится информация о нескольких пробных решениях (популяция особей). Это позволяет создать эффект параллельного поиска и значительно увеличить шансы нахождения глобального оптимума. Однако, в некоторых случаях выигрыш от использования популяции не оправдывает вычислительных затрат, и простые варианты случайного поиска с одной пробной точкой на каждой итерации показывают большую эффективность по скорости работы и качеству найденных решений. Данная работа большей частью посвящена изучению именно таких случаев.
Другая привлекательная черта ЭА - сравнительная простота их реализации для решения конкретной задачи. ЭА являются универсальными схемами, при использовании которых достаточно подходящим образом определить представление решений рассматриваемой задачи в некотором универсальном виде (бинарные строки, перестановки и др.), называемом генотипом. При этом имеются широкие возможности комбинирования ЭА с другими эвристиками. Построенные таким способом гибридные алгоритмы позволяют сравнительно быстро находить качественные решения труднорешаемых задач большой размерности. Общая схема ЭА и формальные определения основных его операторов приведены в главе 1.
В области эволюционных алгоритмов можно выделить два направления: теоретическое и экспериментальное. Теоретические исследования ЭА направлены в основном на построение математических моделей различных алгоритмов, исходя из которых выдаются рекомендации по выбору тех или иных вычислительных схем и настройке внутренних параметров, а также вычисляются оценки точ-
ности и скорости работы алгоритмов [52, 54, 63, 74, 77, 87, 91, 92]. В рамках экспериментального направления разрабатываются алгоритмы, предназначенные для решения прикладных задач. Особое место здесь занимают способы гибридизации ЭА, методов локального поиска и алгоритмов, разработанных для решения конкретного типа задач с учетом их специфики [29,34,45,49,59,64,98]. Вопросы о сравнении алгоритмов и настройке параметров решаются путем вычислительных экспериментов. Важную роль здесь играет создание общедоступных библиотек тестовых задач, размещенных в сети Интернет, которые позволяют исследователю сравнивать свои результаты с работами других авторов. В качестве примеров можно привести проект DIMACS Challenge II [75] (), библиотеку OR Library [48] ( библиотеку тестовых задач Института математики им. С.Л. Соболева [13] ().
Надо сказать, что между результатами теоретических и экспериментальных исследований наблюдается значительный разрыв: построенные модели, как правило, описывают лишь простейшие алгоритмы в применении к задачам простой структуры с заранее известными оптимальными решениями. Напротив, успешные практические реализации ЭА пока не имеют теоретического обоснования. Такую ситуацию не следует считать недостатком эволюционных алгоритмов, а только свидетельством сложности возникающих здесь вопросов, а также подтверждением важности экспериментальных исследований.
Целью данной работы является моделирование и сравнение различных схем ЭА в применении к задачам дискретной оптимизации, а также разработка новых алгоритмов для практического использования.
В диссертации построены модели для эволюционных алгоритмов (1,А)-ЕА и (Ц-І)-ЕА и проведены эксперименты по проверке адекват-
ности построенных моделей. Рассмотрено введенное в [63] условие монотонности оператора воспроизведения, а также более общее условие доминирования. Показано, что при выполнении этих условий алгоритм (1+1)-ЕА обладает наилучшими вероятностными характеристиками среди всех ЭА. Предложено обобщение известной штрафной функции, используемой при решении задачи о независимом множестве графа с помощью генетических алгоритмов и указано наилучшее значение величины штрафа. Экспериментально установлено преимущество алгоритма (1+1)-ЕА по сравнению с другими наиболее известными ЭА на задаче о независимом множестве графа и проведено исследование соответствия теоретических результатов экспериментальным данным. Предложен и реализован генетический алгоритм для задачи о поставках продукции, основанный на использовании жадной эвристики. Проведен вычислительный эксперимент.
Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. В первой главе приведены схемы различных алгоритмов эволюционного типа, таких как имитация отжига, генетический алгоритм, алгоритмы (//, Л)-ЕА и (^ + Л)-ЕА, показана их связь с алгоритмами локального поиска. Дан краткий обзор некоторых классических результатов теории эволюционных вычислений, имеющих отношение к вопросам, обсуждаемым в данной работе: теорема об эквивалентности алгоритмов поиска (известная в англоязычной литературе как теорема "no free lunch"), моделирование генетического алгоритма и (1+1)-ЕА с помощью цепей Маркова, исследование метрических свойств пространства поиска. В качестве примеров практического применения Э А приводятся генетические алгоритмы для решения классической задачи о вершинном покрытии графа и одной прикладной задачи о поставках продукции. Проведены вычислительные эксперименты, которые показали хорошую производительность алго-
ритмов на тестовых задачах. Результаты этой главы опубликованы в работах [5,6]
Во второй главе, используя подход, предложенный в [63], для двух простых эволюционных алгоритмов (1,А)-ЕА и (1+1)-ЕА построены оценки вероятностей нахождения решения заданного качества. Обсуждаются условия сходимости алгоритмов к оптимальному решению. В этой же главе сформулирован и доказан один из основных результатов данной работы (теорема о сравнении), в котором показано превосходство (1+1)-ЕА над другими эволюционными алгоритмами при выполнении условий монотонности или доминирования. Данный результат позволяет давать рекомендации по выбору наиболее подходящего алгоритма для решения некоторых классов задач, а также получать обобщения оценок времени поиска оптимума. Приведен пример использования теоремы о сравнении для оценки времени поиска оптимума произвольным эволюционным алгоритмом для задачи сортировки [94]. Кроме того, с точки зрения теории сложности рассмотрены вероятностные характеристики монотонного оператора мутации при решении NP-трудных задач. Результаты второй главы опубликованы в работах [4,7-9,52-54]
В третьей главе с целью выяснения рамок применения теоремы о сравнении был проведен вычислительный эксперимент с рассматриваемыми здесь эволюционными алгоритмами на задаче о независимом множестве графа и задаче выполнимости логической формулы. В обоих случаях использовался общеизвестный подход, основанный на двоичном представлении решений. В ходе эксперимента наилучшие результаты показали алгоритмы, в которых популяция состоит из одной пробной точки: (1+1)-ЕА и имитация отжига. Были проведены дополнительные эксперименты для исследования соответствия теоретических результатов экспериментальным данным. Показано, что в начальной
стадии поиска условие монотонности выполняется лишь с небольшими отклонениями, и превосходство (1+1)-ЕА может быть объяснено теоремой о сравнении. Конечная стадия поиска, где монотонность нарушается значительно, также рассмотрена и выявлены общие свойства задач, при которых (1+1)-ЕА показывает преимущества над алгоритмами с популяцией большого размера. Кроме того, для задачи о независимом множестве рассмотрен более общий вид известной штрафной функции, экспериментально исследована связь производительности ЭА со значением величины штрафа и указано его наилучшее значение. Результаты этой главы приводятся в [10,55].
Основные результаты диссертации опубликованы в работах [4-10, 52-55] и докладывались на
Российских конференциях "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004),
XII Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003),
Международном семинаре "The 1-st European Workshop on Evolutionary Computation in Combinatorial Optimization" (Комо, Италия, 2001),
Международной конференции "Foundations of Genetic Algorithms 7" (Малага, Испания, 2002),
Международном семинаре "The 3-rd European Workshop on Evolutionary Computation in Combinatorial Optimization" (Ко л честер, Великобритания, 2003),
Международных семинарах "Theory of Evolutionary Algorithms" (Дагштул, Германия, 2002, 2004),
Международном семинаре "The 2-nd International Workshop "Discrete Optimization Methods in Production and Logistics" (Омск, 2004),
V Международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 2004),
а также на семинарах в Институте математики им. С.Л. Соболева СО РАН и в Омском филиале Института математики им. С.Л. Соболева СО РАН.
Автор выражает благодарность А.А. Колоколову и А.В. Еремееву за помощь в работе над диссертацией. Часть работы выполнена при финансовой поддержке РГНФ (проект 04-02-00238а) и INTAS (проект 03-51-5501).
Вопросы теоретического анализа эволюционных алгоритмов
Одним из основных вопросов при анализе приближенных алгоритмов, по-видимому, можно считать вопрос о том, какой из алгоритмов предпочесть при решении некоторой задачи, и, наоборот, для каких типов задач определенный алгоритм будет показывать наилучшие результаты, и для каких задач его применять нецелесообразно. В слу чае решения NP-трудных задач с помощью эволюционных алгоритмов полное решение этого вопроса оказывается практически невозможным, ввиду сложности структуры задачи и вычислительных схем алгоритмов.
Классическим результатом теории эволюционных вычислений является, так называемая, теорема об эквивалентности (теорема "No Free Lunch.", (NFL)) [97]. Рассмотрим два конечных множества X, Y и множество F всех функций / : X — У. Пусть А и В два алгоритма оптимизации, работающих по следующей схеме: генерируется начальное решение х \ и на очередной итерации t решение х строится случайно с некоторым распределением, зависящим только от предыдущих решений x \x l\ ...,0: 1) и соответствующих им значений целевой функции. Алгоритмы такого рода принято называть алгоритмами оптимизации "черного ящика", так как они предназначены для решения задач, входные данные которых не содержат дополнительной информации о внутренних параметрах целевой функции (например, для задач на графах такими параметрами могут быть значения степеней вершин, для задач непрерывной оптимизации - величина градиента и т.д.). Очевидно, описанной схеме удовлетворяют все рассмотренные выше эволюционные алгоритмы (исключая варианты со специализированными операторами репродукции и особыми способами построения начальной популяции).
Как следствие из этой теоремы утверждается, что наилучшим значением рт будет 1/п, при котором достигается минимум E[t ]. Несмотря на то, что данный результат справедлив только для указанной целевой функции, рекомендация о выборе рт — 1/п используется и для более сложных задач. При моделировании ГА с помощью цепей Маркова за состояния цепи приходится обычно брать все возможные популяции, число которых растет экспоненциально с ростом размерности задачи. Большое число состояний ограничивает возможность практического применения цепей Маркова, но позволяет получать результаты общего характера. Так, в работе [93] исследуется сходимость стандартного ГА с попу ля-ционной схемой воспроизводства и пропорциональной селекцией.
Таким образом, для сходимости ГА к оптимальному решению требуется в процессе работы сохранять лучшее найденное решение. Отметим, что при доказательстве существенно использовалась способность стандартного оператора мутации переходить от произвольного решения к любому другому с ненулевой вероятностью при рт Є (0,1).
Одним из важных направлений в теории ЭА является исследование метрических свойств пространства поиска и связи производительности ЭА со структурой локальных оптимумов. При этом требуется подходящим образом задать систему окрестностей с учетом свойств используемых операторов воспроизведения. Например, под действием стандартного оператора мутации в среднем изменяется ровно один бит, два бита могут измениться с небольшой вероятностью, а вероятность изменения трех и более битов на практике зачастую совсем мала. Поэтому наиболее подходящей окрестностью считается единичный шар в метрике Хэмминга. Введение метрики позволяет проводить классификацию легких и трудных задач для ЭА. Так, в работе [76] трудность задачи оценивается по коэффициенту корреляции между значением пригодности решения, и расстоянием от него до ближайшего глобального оптимума: г — согт(Ф(х),ё(х,х )) который вычисляется по всему пространству решений, либо по некоторой случайной выборке. Для задач максимизации значение г, близкое к минус 1, означает, что функция пригодности правильно указывет направление поиска, поэтому можно ожидать хорошей работы ЭА (к примеру, г — — 1 для уже упоминавшейся задачи максимизации единиц в бинарной строке). Если г близко к 1, то глобальные оптимумы расположены "в окружении" решений невысокого качества, и вероятность найти их с помощью ЭА очень мала. При г близких к 0 функция пригодности не содержит информации о расположении оптимальных решений, и ЭА будут работать не лучше, чем простой случайный перебор. В качестве примера можно привести задачу, где имеется единственный глобальный оптимум, все остальные решения имеют одно и то же значение целевой функции. Проведенное в [76] исследование показало, что в целом коэффициент корреляции адекватно отражает трудность задачи. Как отмечается в [37], недостатком данного подхода является то, что метрика Хэмминга не подходит для операторов кроссинговера, т.к. потомки обычно оказываются значительно удаленными от родителей. В этой же работе был предложен пример задачи с нулевым значением г, на которой ГА показывал хорошие результаты.
Коэффициент корреляции тесно связан с так называемой гипотезой большой долины о том, что локальные оптимумы распределены неравномерно, а расположены вблизи глобального оптимума [25,50]. Кроме того, в литературе также описаны другие характеристики задач, такие как функция автокорреляции [39], корреляция между значениями пригодности родителей и потомков [38] и т.д. В [36] отмечается, что более адекватной мерой может служить "вероятность успеха", т.е. вероятность получить потомка со значением пригодности лучше, чем у родителей.
В данной диссертации исследуется более строгое предположение, введенное в [63], о том, что вероятность получить потомка со значением пригодности не ниже заданного порога монотонно зависит от пригодности родителей. В главе 2 показано, что при выполнении этого условия наилучшим оказывается алгоритм (1+1)-ЕА, в главе 3 сделана экспериментальная проверка выполнения этого условия для задачи о независимом множестве.
Вершинным покрытием графа G = (V, Е), где Vф$жЕ фЪ- множества вершин и ребер соответственно, называется множество CCV, такое, что для любого ребра е = (i?i, v%) Є Е либо v\ Є С, либо V2 Є С Так как в работе рассматривается только вершинные покрытия, будем для краткости называть их просто покрытиями. Задача вершинного покрытия (ЗВП) состоит в нахождении покрытия С наименьшей мощности. Дополнение к покрытию в V называется независимым множеством. Вершины из независимого множества попарно несмежны. При переходе к дополнительному графу они становятся попарно смежными, то есть порождают полный подграф (клику). В этом смысле ЗВП эквивалентна задаче нахождения наибольшего независимого множества и задаче о наибольшей клике.
Рассматривается также постановка взвешенной ЗВП, в которой ка ждой вершине v Є V сопоставлен вес w(v) 0. Требуется найти покрытие минимального суммарного веса. Указанные задачи находят применение в проектировании систем контроля и наблюдения, теории передачи сигналов и диагностики ошибок, построении непротиворечивых расписаний и т.д. [3,51,73]. Для их решения известно множество точных и приближенных алгоритмов [18,19,30,34,43,45-47,69,83]. Поскольку данные задачи являются TVP-трудными, разработка быстрых эвристических алгоритмов представляет большой интерес.
Генетические алгоритмы для задачи о доставках
Большую роль в экономике играют задачи составления наилучшего плана доставки продукции от поставщиков потребителям [2,31]. В данном разделе рассматривается обобщенная постановка классической транспортной задачи, особенностями которой являются нелинейность целевой функции и наличие дополнительных ограничений на минимально возможный объем открытой поставки. Пусть количество поставщиков равно и, а количество потребителей - т. Обозначим через МІ максимальный объем продукции, который способен предоставить поставщик і (і — 1,...,n), Aj - объем продукции, необходимый потребителю j (j = 1,..., т).
Булевы переменные Z{j указывают на наличие или отсутствие поставки от поставщика г потребителю j, а вещественные переменные х обозначают ее объем. Данная задача была сформулирована в [57], там же был предложен приближенный алгоритм ее решения. В [56] доказано, что задача поиска хотя бы допустимого решения является NP-трудной даже при 7П = 1. В [20] был разработан алгоритм ветвей и границ, основанный на переборе булевых переменных ().
В случае, когда все ггцу равны нулю, то рассматриваемая задача является хорошо известной транспортной задачей с фиксированными доплатами. Для ее решения предложено множество алгоритмов, в том числе генетических [62,96]. В данной работе для решения задачи о поставках предлагаются два варианта генетического алгоритма, основанных на различном представлении решений.
Удачный выбор представления оказывает существенное влияние на результат работы алгоритма. В первом варианте ГА (назовем его GAbin) реализован наиболее известный принцип представления особи с помощью бинарных переменных. В нашем случае в качестве особи можно использовать матрицу (). Легко показать, что при фиксированных z значения переменных хц находятся путем решения неко торой транспортной задачи. Если матрица ( ) соответствует допустимому решению, то в качестве величины пригодности принимается значение целевой функции с обратным знаком (т.к. пригодность в ГА требуется максимизировать), иначе в величину пригодности включаются штрафы за каждое нарушение ограничений. Для построения новых особей используются операторы одноточечного кроссинговера и стандартной мутации [90].
Второй вариант, алгоритм GAgrd, основан на идее последовательного решения задачи о поставках для каждого потребителя в отдельности. При таком подходе каждый потребитель "стоит в очереди" на назначение поставок из оставшегося на данный момент объема продукции. Целью алгоритма является подбор наилучшего порядка потребителей в очереди. Если порядок задается с помощью перестановки индексов потребителей 7Г — (jit..., Jm), то решение может быть построено, используя следующую процедуру:
Похожая ситуация (поиск наилучшей перестановки) возникает при решении классической задачи коммивояжера, где требуется найти порядок обхода заданного множества городов, который давал бы наименьшую суммарную длину пути. Для задачи коммивояжера было раз работано множество успешных реализаций генетического алгоритма (см. [90]), и алгоритм GAgrd можно понимать как адаптацию одного из них для задачи о поставках.
В качестве мутации был выбран оператор, который меняет местами два случайно выбранных элемента перестановки (см. также определение Лчія из п. 2.4.3), в качестве кроссинговера были опробованы известные операторы ОХ и РМХ [90].
Нетрудно показать, что в алгоритме GAgrd не каждое решение задачи может быть представлено в виде перестановки. Для частичного устранения этого недостатка была реализована эвристическая процедура корректировки решения, которая состоит в том, что в матрице (xij) выбираются два потребителя и два поставщика, и путем перебора решается подзадача размерности 2x2. Так как процедура выполняется очень быстро, то ее можно применять к решению несколько раз, чтобы повысить вероятность улучшения решения (в наших экспериментах корректировка повторялась 100 раз). Также в ходе эксперимента было замечено, что корректировку лучше применять в конечной стадии поиска, например во второй половине периода времени, отведенного на вычисления. Это позволяет повысить скорость работы и приводит к более качественным результатам. Надо сказать, что на практике алгоритм GAgrd показал хорошие результаты даже без использования корректировки.
Результаты эксперимента для четырех задач приведены в таблице 1. Столбец АВГ показывает лучшее решение, найденное алгоритмом ветвей и границ за 1 час работы (ввиду большой размерности точных решений найти не удалось). Тестирование производилось на компьютере с процессором Intel Celeron 766 Mhz и операционной системой MS Windows 98. Остальные столбцы содержат величину лучшего решения, найденного алгоритмами GAbin, GAgrd и GAgrd с процедурой корректировки за 15 запусков. Суммарное время работы GAbin на каждой задаче составляло также 1 час, а время работы GAgrd было сокращено до 15 минут, поскольку дальнейшее увеличение времени не давало существенной разницы результатов.
Как видно из таблицы, алгоритм GAbin показал очень плохие результаты, уступив алгоритму ветвей и границ, что может быть обусловлено слабым учетом свойств задачи. Напротив, использование в GAbin жадной эвристики позволило получать значительный выигрыш как по времени, так и по качеству решений.
Сравнение (1+1)-ЕА с другими эволюционными алгоритмами
Подобно приведенному выше сравнению ГА и (1,Л)-ЕА можно сформулировать превосходство (І-Н)-ЕА над (1,А)-ЕА при выполнении условия монотонности, как это было сделано в [52]. Однако, здесь можно доказать более общий результат о том, что (1+1)-ЕА при сделанных предположениях не уступает никакому другому алгоритму, основанному только на использовании мутации. Это тем более важно потому, что, как быпо отмечено разделе 2.3, наша модель (1,А)-ЕА описывает только генотип на конечной итерации, а не лучший генотип, найденный за все время работы. На самом деле, мы докажем еще более общий вариант, в котором оператор мутации заменен оператором воспроизведения. Кроме того, в этом разделе не используется предположения о дискретности множества значений целевой функции, поэтому полученные результаты будут справедливы и для задач на непрерывных множествах.
Определим оператор воспроизведения7Z(xT, ...,хг) как вероятностный алгоритм, который получает на вход г родительских решений и случайным образом строит s решений-потомков, распределение которых зависит от входных решений и данных задачи.
Далее будет удобно ввести другую формулировку понятия монотонности, которая для оператора мутации совпадает с определением из п. 2.1, но позволяет перейти к операторам воспроизведения, а также обойтись без матриц переходных вероятностей и предположения о дискретности множества значений целевой функции. Пусть случайное решение Tlmax(x1, ...,хт) представляет собой лучший из 5 потомков, полученных применением 7с к набору
Заметим, что из этого определения следует, что если все условия (2.16) выполнены как равенства, то распределения случайных величин Ф(7стаг( х1,...,хг)) и Ф {71тах(у1,..., уг)) должны совпадать. Очевидно, что монотонный оператор мутации - частный случай монотонного оператора воспроизведения при г — s = 1.
Условие монотонности может быть ослаблено следующим образом: назовем 7с слабо монотонным, если неравенство (2.17) выполняется хотя бы для всех ip твх{Ф(ук) : к = 1,..., г}.
Оператору 7Z сопоставим оператор мутации Аі-л{х), действующий следующим образом: сначала оператор Тс применяется к набору, со стоящему из г копий решения я, и в качестве результата выдается х — Т тажС ) — x)i если Ф(:г ) Ф(:г), Иначе полагаем М.%{х) = х. Очевидно, что для монотонного Л. оператор Л4ц также является монотонным.
Обозначим через с№ лучшее решение из множества А (также напомним, что через х обозначается текущее решение на итерации і алгоритма (1+1)-ЕА). Сформулируем основной результат данной главы:
Утверждение (Ь) теперь следует из теоремы 2.7. П В [63] было показано, что стандартный оператор мутации является монотонным для задачи максимизации количества единиц в строке. В [54] сформулировано более общее утверждение:
Предложение 2.3 Пусть Л4 - стандартный оператор мутации с рт 1/2, и функция Ф : {0,1}п — R принимает ровно п + 1 различных значений и имеет единственный глобальный оптимум. Оператор Л4 является монотонным тогда и только тогда, когда Ф имеет вид: где (аі,„. ап) - некоторый булев вектор, 0 - строго возрастающая функция.
Таким образом, в условиях предложения 2.3 монотонность стандартного оператора мутации выполняется только в классе задач максимизации расстояния от некоторой фиксированной точки, очевидно, эквивалентных задаче максимизации количества единиц. Как следствие, мы получаем, что для этого класса (1+1)-ЕА является наилучшим среди всех ЭА основанных на стандартной мутации. Отметим, что преимущество (1+1)-ЕА над ГА на указанной задаче отмечалось в [91], но сравнение проводилось в других условиях: в ГА не использовался оператор мутации, а только одноточечный кроссинговер.
Конечно, для многих известных операторов мутации маловероятно, что они окажутся монотонными и ступенчатыми, хотя бы в слабом смысле, при решении трудных задач оптимизации. Например, если множество линий уровня Фі,..., Ф состоит из всех возможных значений функции пригодности, то при наличии локальных, но не глобальных, оптимумов в смысле метрики Хэмминга, упомянутый только что оператор мутации не будет монотонным и ступенчатым. Тем не менее, ступенчатый оператор может быть полезен в качестве теоретического
вспомогательного средства. Например, для данного оператора Л4 может быть построен монотонный ступенчатый оператор УИ с пороговыми вероятностями перехода, равными монотонным нижним оценкам для Л4. Тогда Л4 можно рассматривать как наихудшую реализацию действия Л4. При таком подходе теорема 2.7 утверждает, что гаранти-рованная нижняя оценка для вектора вероятностей РдА не лучше, чем гарантированная нижняя оценка для Q \
Предположим, что некоторый оператор мутации ЛІ доминирует оператор воспроизведения TZ, Обозначим максимальное значение функции пригодности через if Если известна некоторая нижняя оценка L для Щ х\ то, по следствию 2.3, эта же оценка будет верна для любого ЭА, основанного на операторе 71. Для иллюстрации этого подхода рассмотрим задачу сортировки, сформулированную в виде задачи оптимизации, как было предложено в [94].
Задача сортировки состоит в том, что требуется найти перестановку 7Г элементов массива (х\,..., хп) так, чтобы xn (i) 2V(2) Хъ п). Предполагается, что все элементы (xi, ...,:пп) различны. Введем функцию НАМ(-к), которая будет подсчитывать число правильных позиций в перестановке 7г, т.е. НАМ {ж) = \{ъ : 7г(г) — 7г (г)}. Задачу сортировки будем теперь понимать как задачу максимизации функции НАМ (ЇЇ). Надо отметить, что с практической точки зрения такой подход не представляет интереса, поскольку для вычисления функции НАМ {-к) требуется заранее знать оптимальную перестановку. Тем не менее, данный анализ представляет интерес с точки зрения теории эволюционных алгоритмов как иллюстрация поведения ЭА. В частности, здесь эта задача служит примером применения полученных выше результатов.
Экспериментальное сравнение алгоритмов ГА, ИО и (М + А)-ЕА
В данном разделе приведен эксперимент по применению различных алгоритмов к тестовым задачам из библиотеки DIM ACS и задачах на случайно сгенерированных графах. Целью эксперимента было выявить наиболее подходящие вычислительные схемы в зависимости от выбора величины штрафа а. Сравнение проводилось в двух вариантах: при а = 1 и а = 100.
Для обеспечения работы в равных условиях количество обращений каждого алгоритма к процедуре вычисления целевой функции было ограничено одной величиной tmax которое выбиралось достаточно большим, так что его дальнейшее увеличение не давало значительных улучшений. Отметим, что вычисление целевой функции является самой трудоемкой операцией, поэтому количество обращений к процедуре ее вычисления является адекватным критерием времени работы. Данный подход общепринят при исследовании трудоемкости так называемых алгоритмов оптимизации черного ящика (см. [61] и п. 1.2), к которым можно отнести и рассматриваемые здесь ЭА.
Существенной проблемой при проведении эксперимента является настройка внутренних параметров каждого алгоритма. В случае (1+1)-ЕА настройки не требуется, значение единственного параметра р было выбрано 1, исходя из выводов предыдущего раздела.
ГА был реализован по схеме, приведенной в п. 1.1, с использованием турнирной селекции. При выборе размера популяции были опробованы значения N = 10, 50,100,150. Замечено, что при а = 1 лучшие результаты дают небольшие значения N, в то время как при а = 100 существенных различий не наблюдалось. Здесь приводятся результаты для N = 10. Так как на каждой итерации значение Ф вычисляется два раза, то предельное число итераций ГА равно tmax/2.
Для алгоритма ИО выбраны следующие значения параметров: начальная температура г = 1.5, коэффициент остывания г = 0.98, длина температурного интервала I = 100. Таким образом, в начале работы вероятность перейти к новому решению со значением Ф на 1 меньше, чем у текущего, приближенно равна 1/2. При достижении 10000 итераций вероятность снижается практически до нуля и алгоритм работает как (1+1)-ЕА. Такой выбор показал сравнительно хорошие результаты при а = 100. При а = 1 алгоритм работает тем лучше, чем меньше температура, т.е. чем более ИО приближается к (l-H)-EA.
Результаты эксперимента на задачах из DIM ACS для алгоритмов ГА, (1+1)-ЕА, ИО и (5+10)-ЕА приведены в таблицах 1 и 2 приложения. Результаты для (5,10)-ЕА оказались слишком плохими и здесь не приводятся. Первое число в каждой ячейке таблиц означает среднее значение пригодности найденного решения за 200 независимых запусков алгоритма. Далее через запятую указана пригодность лучшего найденного решения, первое число в скобке показывает, сколько раз из 200 было найдено лучшее решение, второе - сколько раз было найдено решение с пригодностью на 1 меньше, чем у лучшего. Жирным шрифтом отмечены оптимальные значения. Также в соответствующем столбце указано выбранное значение tmax для каждой задачи.
Как видно из таблиц, при а = 1 алгоритм (1+1)-ЕА заметно превосходит остальные почти на всех задачах как по точности в среднем, так и по вероятности нахождения близких к оптимуму решений. Наихудшие результаты показал ГА. При а = 100 лучшие решения были получены алгоритмом ИО, при этом ГА, (1+1)-ЕА и (5+10)-ЕА давали примерно одинаковые результаты. Кроме того, каждый алгоритм при а = 100 показал худшую производительность, чем при а = 1, причины этого обсуждались в предыдущем разделе.
В главе 2 была доказана теорема о сравнении, которая утверждает, что (l-j-l)-EA является наилучшим среди всех эволюционных алгоритмов, использующих монотонный оператор воспроизведения. Похожий результат с экспериментальной точки зрения показывает проведенное здесь сравнение (1+1)-ЕА с наиболее известными схемами ЭА для рас смотренных тестовых задач при а = 1. Поэтому именно вариант с а — 1 представляет для нас наибольший интерес. В следующем разделе будет приведен пример семейства графов, для которых ГА работает лучше, чем (1+1)-ЕА. Для общего же случая ЗНМ с а = 1 хотя и нельзя достоверно утверждать, что не существует алгоритма, который показал бы существенное превосходство над (l-f-l)-EA, но найти такой алгоритм в данной работе не удалось. Это позволяет предположить, что для ЗНМ условие монотонности должно выполняться, может быть с некоторым отклонением. В п. 3.4 будет дано более детальное исследование вопроса о том, в каких рамках экспериментальные результаты могут быть объяснены с помощью теоремы о сравнении.
Несмотря на отмеченное превосходство (І-Н)-ЕА над многими другими алгоритмами на задачах из DIM ACS, можно предложить класс задач, для которых (1 + 1)-ЕА работает хуже, чем ГА. Рассмотрим полный двудольный граф K d+x = (V1UV2, ?). Множество вершин состоит из двух долей Vi и V i с количеством вершин d и d -Ь 1 соответственно. Каждая вершина из V\ соединяется с каждой вершиной из V2. Единственное наибольшее независимое множество такого графа состоит из d + 1 вершин, находящихся во второй доле. Любое другое независимое множество целиком содержится либо в V\ либо в 14.
Эти неформальные рассуждения подтверждаются экспериментами, проведенными на двудольных графах Kd,d+i различной размерности. Результаты эксперимента на графе А"юо,юі отражены на рис. 5, где показана зависимость средних значений пригодности решений, полученных (1 + 1)-ЕА и ГА, от числа итераций t. Средние значения вычислялись по 400 независимым запускам каждого алгоритма, на рисунке отмечены границы доверительных интервалов с уровнем доверия 95%.
Хотя численное различие в результатах невелико, но общая тенденция видна очень четко. Как и прежде, в начальной стадии поиска, (l-fl)-EA показывает более высокую скорость роста, но при достижении определенной величины рост прекращается, и в преимуществе оказывается ГА. 3.3.2 Эксперименты для взвешенной задачи о независимом множестве
Для взвешенной ЗНМ применимы все рассмотренные выше алгоритмы с тем же способом представления решений, требуется только модифицировать функцию пригодности для учета весов. В данном случае она выглядит следующим образом: Ф(х) = Т, iVfrXk — min{wi,Wj}xiXj.
В качестве штрафа выступает теперь величина mm{wi, Wj}. Назначение штрафа можно понимать как удаление вершины меньшего веса для каждого недопустимого ребра. Был проведен аналогичный п. 3.3 эксперимент по сравнению алгоритмов на тестовых задачах, предложенных в [46], результаты которого приведены в таблице 3 приложения. Настройки параметров алгоритмов были такими же, как в п. 3.3, кроме алгоритма ИО, для которого были выбраны следующие значения: начальная температура т = 1, коэффициент остывания г = 1 (ИО с постоянной температурой, известный также как алгоритм Метрополиса). Было замечено, что такой вариант работает значительно лучше для взвешенной ЗНМ, при этом его дополнительное тестирование на невзвешенных задачах показало очень плохие результаты. Данное наблюдение хорошо иллюстрирует, насколько сильно влияет удачная настройка на работу алгоритма. В целом по результатам можно сказать, что ситуация оказалась похожей на эксперимент с невзвешенными задачами при а = 100: наилучшим оказался алгоритм ИО, далее следуют (1+1)-ЕА, (5Н-10)-ЕА и ГА. Это объясняется усложнением структуры задачи, а именно, большим числом возможных значений функции пригодности и наличием локальных оптимумов, из которых трудно перейти к другому решению, хотя бы такого же качества.
