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

John H. Holland Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions

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

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

Написать письмо

Представлен новый класс тестовых функций - Hyperplane-defined functions (hdf), позволяющие проанализировать причины быстродействия алгоритмов и, в то же время, устойчивые к реверс инженирингу. Также представлен новый класс генетических алгоритмов cohort GA (cGA).

2 Building Blocks (Строительные блоки)

Строительные блоки - одно из основных понятий в теории ГА. Считается, что строки (хромосомы) собираются, путем применения генетических операторов, с помощью комбинаций различных строительных блоков с различной приспособленностью. Основные характеристики строительных блоков:
1) Должен быть простой способ их идентификации, выделения.
2) Они должны легко сочетаться в различных комбинациях.

4 Designing Genetic Algorithms (Разработка генетических алгоритмов)

На основе анализа биологических систем даются следующие объяснения почему в природе преобладает кроссовер, а не мутация:
1) Кроссовер предусматривает дальние (случайные) прыжки в пространстве поиска, обеспечивая возможность выхода из локальных экстремумов.
2) Кроссовер "чинит" некоторые повреждения, наносимые мутациями.
3) Кроссовер обеспечивает постоянную изменчивость, что защищает организм от нацеленых атак вирусов, бактерий и паразитов.
4) Кроссовер рекомбинирует строительные блоки.
Объяснения приведены по возрастанию их важности (с т.з. Д.Холланда).

5 Robustness (Эффективность)

На анализе опыта исследования ГА сделаны следующие замечания:
1) Если необходимо разработать тестовые функции для проверки способностей ГА, то это не должны быть выпуклые функции (с одним экстремумом).
2) Если необходимо использовать функции, которые показывают сильные стороны ГА, то это не должны быть "плоские" (shallow) функции.

6 Cohort Genetic Algorithms (Когортный ГА)

Алгоритм разработан для преодоления трудностей, связанных с дробной относительной приспособленностью особей в простом ГА (см. например описание канонического ГА). Для этого в новом алгоритме приспособленность определяет скорость, с которой особь будет скрещиваться, или, другими словами, частоту скрещивания. Таким образом, особи с различной приспосбленностью могут дать каждая 2 потомков, но более приспособленная особь даст потомство быстрее.

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

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

7 Hyperplane-Defined Functions (Функции определенные гиперплоскостями)

Сформулированы общие требования к тестовым функциям:
- используют строительные блоки;
- нелинейные, нельзя разбиты на подфункции (nonseparable) и несимметричные (должны быть сложными для комбинированных методов, использующих градиентные техники, т.н. hillclimbers);
- масштабируемые по сложности;
- должны быть записаны в canonical (?) форме.

Дополнительные требования к функциям включают:
- должны предусматривать случайное задание параметров и устойчивость к реверс инженирингу (как, например, для функций с подсчетом битов - OneMax и др.);
- наличие контролируемого набора свойств рельефа функции (пики, плато и т.д.)
- include all finite functions in limit. (???) :(

Для предлагаемых hdf-функций необходимо найти битовую строку с максимальной приспособленностью. Приспособленность вычисляется по довольно сложной схеме, и для каждого запуска критерии приспособленности формируются случайным образом.

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

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

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

Для того, чтобы лучше понять, что такое hdf-функции, советую прочитать сначала их описание, чтобы ознакомиться с терминологией (глава 7), а затем рассмотреть пример из приложения.

[3 апреля 2004г.]