Томас Бэкк (1992)

Генетические алгоритмы

Thomas Back. Self-Adaptation in Genetic Algorithms.

Группа исследований эволюционных алгоритмов (ТПУ)

Дискуссионная группа по эволюционным вычислениям

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

Introduction (Введение)

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

Adaptive mutation rates (Адаптивные вероятности мутации)

Дан краткий анализ предыдущих работ различных исследователей.

Основные особенности предлагаемого подхода:

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

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

вероятности мутации инициализируются случайным образом.

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

Описывается механизм реализации адаптивной вероятности мутации. Сформулирована и доказана теорема об асимптотическом поведении вероятности оператора мутации.

Extinctive Selection (Селекция с угасанием)

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

Experimental Results (Результаты экспериментов)

Для тестирования взяты следующие функции:

сферическая;

взвешенная сферическая;

обобщенная функция Растригина.

Параметры алгоритма (модифицированный алгоритм Грефенстетта):

размер популяции = 50 особей;

длина хромосомы 32n, где n - количество параметров задачи;

вероятность кроссовера 0,6;

двухточечный кроссовер;

кодирование Грея.

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

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

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

Summary (Выводы)

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

Скачать статью (pdf, rar, 109 kb)

Скачать статью (pdf, 207 kb)

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

вероятность и тип кроссовера;

вероятность и тип мутации;

размер популяции;

длина хромосомы.

размеры подпопуляций и частота миграций (для островной модели ГА).
Что интересно, по отдельности работы в этих направлениях имеются. Однако о конкретных реализациях, вобравших несколько пунктов, известно мало. Вроде бы, часть упомянутых возможностей есть в реализации В.М. Курейчика (из российских исследователей). Кстати, книга В.М. Курейчика "Теория и практика эволюционных вычислений" единственная из встреченных мне на русском языке, которая подробно освещала бы генетические алгоритмы и, что важно, теоретические и практические проблемы и возможные пути их решения. Поэтому, пользуясь случаем, рекомендую. Книга выпущена издательством "ФИЗМАТЛИТ" в 2003г.
[1 мая 2004г.]