Генетические алгоритмы
Luke S. When Short Runs Beat Long Runs
| На главную |
| Генетические алгоритмы |
| Статьи |
| Группа исследований эволюционных алгоритмов (ТПУ) |
| Дискуссионная группа по эволюционным вычислениям |
| Написать письмо |
Расматривается вопрос о том, что лучше: один длительный поиск в течении n поколений или m перезапусков по n/m поколений в каждом? Предлагается способ независимого анализа, который отвечает на эти вопросы. Рассматривается применение разработанного математического аппарата на примере решения трех задач из области генетического программирования.
1. Introduction (Введение)
Кратко описывается состояние проблемы и рассматриваются варианты теорий сходимости эволюционных алгоритмов и вопросы их применимости к реальным задачам.
2. Preliminaries (Основы)
Формулируются и доказываются теоремы о значении максимального числа из некоторого набора в n испытаниях. Приводятся теоремы для непрерывной и дискретной функций распределения.
3. Schedules (Расписания)
Дается определение расписанию (schedule), и стремлению расписания S к расписанию T. Сформулированы и доказаны теоремы о численных критериях стремления расписания S к расписанию T.
На основе теорем предлагается метод определения оптимальной стратегии перезапусков.
4. Analysis of Three Genetic Programming Domains (Анализ трех задач из области генетического программирования)
Описываются условия запусков алгоритмов для генетического программирования.
4.1 Symbolic Regression (Символьная регрессия)
Рассматривается решение задачи символьной регрессии (Symbolic Regression). По результатам 50 запусков можно наблюдать, что начиная с некоторого этапа поиска приспосбленность увеличивается сравнительно незначительно. При этом более выгодными, по количеству вычислений целевой функции, выглядят варианты с перезапусками алгоритма, чем с одним запуском на длительное время (рис.2).
4.2 Artificial Ant (Управление искусственным муравьем)
Описываются результаты экспериментов для задачи управления движением муравья. Полученные результаты в целом схожи с результатми пункта 4.1.
4.3 Even-10 Parity (10-битная четность)
Рассматривается решение задачи 10-битной четности. В данном случае результаты довольно сильно отличаются от результатов для двух предыдущих задач.
5. Discussion (Анализ)
Вводится понятие критической точки, как числа поколений, выше которого генетический поиск сравнительно малоэффективен, и более хорошие результаты могут быть получены с помощью множественных запусков на меньшее число поколений. При этом количество вычислений целевой функции останется неизменным.
Скачать статью (pdf, rar, 74 kb)
Результаты, похожие на полученные автором, можно наблюдать не только для генетического программирования. Уменьшение эффективности поиска с ростом числа поколений присутствует и при решении различных задач генетическими алгоритмами. Как мне кажется, это не в последнюю очередь связано с группированием большинства особей в областях локальных экстремумов. Данное явление особенно сильно проявляется по прошествии некоторого числа поколений после инициализации. Возможно, где-то там и находится критическая точка, после которой поиск малоэффективен и стоит начать все заново, чем "мучать" существующую популяцию. БОльшая часть особей остается в локальных экстремумах, а вероятность того, что какой-нибудь потомок окажется в новом локальном оптимуме, а потом еще и сможет "повести" за собой популяцию, очень невелика.
Последнее утверждение, в общем-то, субъективно, и сделано на основе собственного опыта. Тем не менее об этом позволяют судить результаты решения немалого количества задач, включающих более 10 задач оптимизации, а также настройку искусственной нейронной сети и связанных с ней задач классификации и нейроуправления.
[10 мая 2004г.]
