Генетические алгоритмы
Keith E. Mathias and L. Darrell Whitley. Transforming the Search Space with Gray Encoding
| На главную |
| Генетические алгоритмы |
| Статьи |
| Группа исследований эволюционных алгоритмов (ТПУ) |
| Дискуссионная группа по эволюционным вычислениям |
| Написать письмо |
Рассматривается использование кодов Грея для численной оптимизации с помощью генетических алгоритмов. Анализируется трансформация пространства поиска и изменение связей между гиперплоскостями в результате применения кодов Грея. Показано существенное влияние кодирования Грея на рельеф целевой функции, что в некоторых случаях приводит к превосходству локальных методов оптимизации над генетическими алгоритмами. Представлен анализ смежности (связности, adjacency) бинарного пространства.
1. Introduction (Введение)
На основе анализа литературы сделан вывод об эффективности использования кодов Грея. Высказано мнение о необходимости сравнения методов оптимизации не только на одних и тех же функциях, но и при условии одинаковости их рельефа и связности точек. Иными словами сравнивать ГА с использованием кодов Грея и без не совсем правомерно, т.к. рельеф функций различный, а следовательно условия тестирования неравные, что нарушает чистоту эксперимента.
2. Gray Coding the Function Space (Кодирование Грея: Рельеф функции)
Рассматриваются способы преобразования из прямого кода в код Грея. На примерах показано, что в случае использования кодов Грея уменьшается количество локальных экстремумов (за счет удаления так называемых Hamming cliffs - переходов между числами вида 2^n и (2^n-1), в которых n различных битов, хотя сами они отличаются на 1).
3. Gray Coding the Genetic Search Space (Кодирование Грея: Генетическое пространство поиска)
Несмотря на то, что использование кодов Грея уменьшает количество локальных экстремумов за счет перераспределения точек в пространстве, данное свойство, с другой стороны, может осложнить генетический поиск, т.к. связь между шаблонами (schemas) также изменяется. На примере 4-битной функции с ложным экстремумом показано, как применение кодирования Грея уводит генетический поиск от локального оптимума.
4. Empirical Performance Results (Результаты экспериментов)
Сравниваются результаты работы различных методов оптимизации (СНС, steepest descent, stochastic hill-climber). Используется набор из 10 функций.
5. Adjacency Analysis (Анализ связности)
Анализируется расстояние Хэмминга для 3, 4 и 5 битных чисел для случаев прямого кодирования и кодов Грея.
6. Conclusions (Выводы)
Высказывается предположение об успешности ГА с элементами hill-climbing'a, использующих кодирование Грея. Также формулируется предположение о необходимости использования тестовых функций с нелинейными зависимостями между параметрами.
Скачать статью (pdf, rar, 87 kb)
Работа очень интересная. Она не дает окончательный ответ на вопрос, использовать коды Грея или нет, но информацию к размышлению предоставляет. Результаты, представленные в 4 и 5 разделах, неоднозначны и напоминают что-то типа "Сравнительные тесты Р4ЕЕ и Athlon64 FX": и так - хорошо, и так - тоже неплохо. Стоит отметить, что для использованных локальных методов оптимизации применение кодов Грея пошло на пользу. Что в общем и понятно: меньше локальных минимумов, шаблоны не используются. В конечном итоге решать вам.
По поводу использования функций с нелинейными зависимостями между параметрами, упомянутыми в выводах. В качестве таких тестов могут служить задачи настройки ИНС, поскольку величины весов различных связей взаимно влияют друг на друга, причем зависимости множественные и часто неоднозначные.
От себя могу добавить, что я использовал обычное прямое кодирование и при этом у меня получилось создать весьма эффективный генетический алгоритм для численной оптимизации. По крайней мере, таковы результаты для использованных функций (ONEMAX, сферическая, Растригина, Швефеля, Розенброка, SAT-2, SAT-3), хотя при настройке весов ИНС с фиксированной структурой его показатели были хуже, чем у канонического алгоритма.
[24 апреля 2004г.]
