Генетические алгоритмы
L. Darrell Whitley. Fundamental principles of deception in genetic search
| На главную |
| Генетические алгоритмы |
| Статьи |
| Группа исследований эволюционных алгоритмов (ТПУ) |
| Дискуссионная группа по эволюционным вычислениям |
| Написать письмо |
В работе представлено несколько теорем о природе обманчивости и центральной роли, которую играет ложная информация в оптимизации функций с использованием генетических алгоритмов. Предлагается простое доказательство, которое показывает, что только те проблемы являются сложными для оптимизации, которые включают элементы обманчивости. Представлена концепция ложного аттрактора, являющаяся более обобщенным случаем, чем ложный оптимум в обманцивых функциях, созданных на сегодняшний день. Также представлены понятия полностью обманчивых проблем и менее строгих последовательно (consistently) обманчивых проблем. Приведены некоторые эмпирические результаты, которые показывают различные способы решения проблемы обманчивости и слабой связанности пространства поиска.
1. Background (Исторический обзор)
Дается краткий исторический обзор проблем с ложными экстремумами (deceptive problems). Вводится понятие ложного аттрактора, который является своеобразным "антимаксимумом" с точки зрения двоичного представления (ложный аттрактор представлен бинарной строкой, которая является инверсией строки, представляющей глобальный максимум).
Одной из причин изучения проблем с ложными экстремумами является лучшее понимание факторов, способных сдерживать генетический поиск в точках близких к глобальному или близких к нему по значению целевой функции экстремумах. Задачи, которые значительно уводят в сторону генетический поиск называются генетически тяжелыми (GA-hard).
2. Definitions (Определения)
Вводятся следующие понятия:
4. The Only Challenging Problems are Deceptive (Все тяжелые проблемы обманчивы)
Сформулирована и доказана теорема и следствие из нее. Проводится анализ с использованием аналогии о выборе оптимальной стратегии (с максимальным выигрышем) для игровых автоматов, использованной еще Д.Холландом и описанной также К.Де Джонгом.
5. Constructing a Fully Deceptive Problem (Создание полностью обманчивой проблемы)
Предложен вариант построения полностью обманчивой проблемы произвольного порядка. Рассмотрен вариант проблемы 4-го порядка.
6. The Deceptive Attractor Theorem (Теорема об обманчивом аттракторе)
Сформулирована и доказана теорема о виде обманчивого аттрактора для полностью и последовательно обманчивых проблем. Также представлено следствие из теоремы, которая позволяет по виду аттрактора судить об обманчивости функции.
7. The Deceptive Attractor and Local Optima (Обманчивый аттрактор и локальные экстремумы)
Сформулирована и доказана теорема о связи обманчивого аттрактора, значения целевой функции близких к нему точек для в пространстве поиска и характером проблемы. Сформулировано следствие из теоремы. Рассматриваются последовательные обманчивые функции.
8. The Deceptive Attractor Remapping Strategies (Стратегии преобразования обманчивого аттрактора)
Рассматривается влияние преобразования топологии пространства поиска (remapping) на рельеф функции с ложными экстремумами. В частности анализируется изменение расстояния Хемминга между истинным и ложным экстремумами в результате перекодировки точек в пространстве поиска.
9. Deception and Linkage Problem (Обманчивость и проблема связанности)
Рассматривается связь между сложностью обманчивой функции и связанностью битов в хромосоме. Под связанностью (linkage) понимается неоцениваемая численно величина, пропорциональная вероятности неразрушения некоторых бит в результате применения генетических операторов к хромосоме. Например, рядом расположенные биты являются более сильно связанными, чем биты, удаленные друг от друга, причем чем больше будет расстояние между ними, тем меньше степень их связанности. В главе приводится вариант усложнения обманчивых функций, когда разряды, отвечающие за ложный экстремум, расположены не последовательно, а разнесены в хромосоме.
10. A Description of the Experiments
Описываются использованные задачи, параметры запусков ГА и варианты алгоритмов, включающие:
11. Summary of Experimental Results (Сводные результаты экспериментов)
Представлены усредненные результаты по 30 запускам каждого варианта алгоритма для различных проблем с ложными экстремумами. По результатм сформулированы три гипотезы: (1) использование битов с тегами улучшает работу алгоритма; (2) однородный кроссовер показывает более плохие результаты, чем 1-точечный кроссовер; (3) . Автор отмечает возможную неоднозначность сделанных выводов в силу "искусственности" использованных задач.
12. Conclusions and Future Directions
Подчеркиваются основные цели представленной работы: (1) обсуждение обманчивых проблем и их связь с выбором (sampling) гиперплоскостей и вложенным параллелизмом (implicit parallelism); (2) создание задела для дальнейших исследований.
Рассматривается проблема выбора тестовых функций для генетических алгоритмов. Также обсуждается проблема сложных функций для генетических алгоритмов.
Скачать статью (pdf, rar, 116 kb)
Более подробно о связанности смотрите в "GA Tutorial" D. Whitley.
В чистом виде обманчивые проблемы, наверное, не встречаются. Однако их "обблегченные" варианты практически всегда можно встретить в задачах численной оптимизации, поэтому преодоление проблем такого рода является довольно актуальным.
Проблемы с обманчивыми экстремумами на самом деле являются тяжелыми для ГА. К примеру, описываемый в статье GENITOR, являющийся по совместительству весьма эффективной моделью генетического алгоритма в среднем показал довольно посредственные результаты. С другой стороны, хочется отметить, что создание генетического алгоритма, который успешно справляется с обманчивыми проблемами еще не гарантирует эффективной работы этого алгоритма вообще.
[18 мая 2004г.]
