Генетические алгоритмы
Alden H. Wright, Jonathan E. Rowe, James R. Neil. Analysis of the Simple Genetic Algorithm on the Single-peak and Double-peak Landscapes
| На главную |
| Генетические алгоритмы |
| Статьи |
| Группа исследований эволюционных алгоритмов (ТПУ) |
| Дискуссионная группа по эволюционным вычислениям |
| Написать письмо |
Мы проведем сравнение работы ГА с кроссовером и без. Простой ГА с кроссовером может иметь две фиксированные точки равновесия (бистабильность) в одноэкстремальных пространствах для строк длиной как минимум 8 разрядов. С увеличением вероятности мутации появляются резкие переходы от первой ко второй и обратно к первой точке равновесия. Также изменение распределения популяции может быть вызвано влиянием кроссовера. Для фиксированной точки возле экстремума в популяции существует несколько копий оптимальной строки, больше копий квази-оптимальных строк и меньше копий строк, далеких от оптимума. Приведен пример, где в ГА с кроссовером средняя приспособленность в популяции уменьшается до минимально возможного значения, в то время как для ГА без кроссовера средняя приспособленность увеличивается. Результаты получены с использованием модели Воса для динамической системы.
1. Introduction
Почеркивается важность понимания роли кроссовера в генетическом алгоритме. Для сравнения с рассматривается алгоритм без кроссовера и приводится пример, когда использование кроссовера может увести процесс эволюционного поиска от "точки" сходимости, когда в популяции присутствует много копий оптимальной особи.
Описываются одно- и двухэкстремальная NEEDLE функции. Описываются наблюдаемые "точки стабильности" (stable points)
2. Literature Review
2.1 The Boerlijst models and results
Описывается модель Боерлижста (Boerlijst, не уверен, что именно так, поэтому прошу прощения, если неправильно) и др., разработанная для описания описания эволюции популяции вирусов. Математическая модель подразумевает популяцию бесконечного размера и учитывает влияние операторов мутации и рекомбинации. Результаты работы модели на одноэкстремальной функции показывают, что с использованием кроссовера "порог ошибки" для вероятности мутации (см. работы M.Eigen и P.Schuster) уменьшается.
2.2 Other models and results
Коротко описываются основные результаты работ Ochoa и Harvey, и Barnett.
3 The Vose Dynamical System Model
Дается представление о модели Воса (Vose) для динамической системы, используемой в данной работе. Модель рассматривает бесконечно большую популяцию, развивающуюся в дискретном времени с учетом пропорционального отбора, кроссовера и мутации. Описан вариант представления состава популяции, а также математическая модель и адаптировано понятие асимптотически стабильной фиксированной точки применительно к модели Воса.
4 A comparison of models
Приведен краткий сравнительный анализ рассмотренных выше моделей.
5 Results for the NEEDLE fitness
Описаны результаты работы компьютерной модели Воса для 8-разрядных строк для NEEDLE-функции. Рассматривается два случая: с оператором кроссовера и без него (только мутация). Приведены описания точек "стабильности", наблюдаемых в результате работы алгоритма. Также проведен анализ влияния вероятности мутации на получаемый результат.
6 The distribution of a population at a fixed point
Более подробно описываются полученные распределения в популяции в результате запуска алгоритма с кроссовером и без него.
7 Bineedle results
Описаны результаты работы модели для BINEEDLE-функции. Описываются фиксированные точки возле экстремумов и в центре пространства поиска. Рассматривается влияние величины вероятности мутации на стабильность фиксированных точек. Описывается случай, когда популяция в генетическом алгоритме может содержать особи из различных экстремумов, а также условия сходимости к одному экстремуму.
8 Examples where crossover causes fitness to decrease
Приводится пример, когда использование оператора кроссовера "заводит" популяцию в область с минимальной приспособленностью.
9 Discussion
Проводится анализ взаимного влияния оператора мутации и селекции. Сделан вывод, что для NEEDLE-функции при большой вероятности мутации популяция "уводится" к точке, соответствующей случайной популяции. В то же время, при малой вероятности мутации фиксированная точка будет ближе к экстремуму.
Скачать статью (pdf, rar, 50 kb)
Прежде всего, хочу извиниться за "криво" переведенную аннотацию. Чесслово, я старался. Чтож будет еще один повод прочитать статью в подлиннике ;-)
Статья чисто теоретическая, но, надеюсь, материал интересный. Работа будет полезна, помимо всего прочего, тем, кто пытается лучше понять роль операторов скрещивания и мутации в ГА, в статье этот момент довольно четко обозначен. Лично для себя узнал о существовании некоторых аналитических моделей эволюционных алгоритмов, а также, что модель Липенса-Воса жива и неплохо себя чувствует. Более подробно с ранним вариантом модели и ее расширением, предложенном Д.Уитли читайте на http://www.cs.colostate.edu/~genitor, статья называется "An Executable Genetic Algorithm". Также по этому вопросу можно заглянуть на http://www.generation5.org/
Интересны точки "стабильности", наблюдаемые авторами. Стоит отметить, что в ряде экспериментов по проводимому в настоящий момент исследованию по эволюционной кибернетике, наблюдаются точки стабильности, отличные от описываемых авторами.
[16 ноября 2004г.]
