Генетические алгоритмы
Popovici E. & De Jong K. Understanding EA Dynamics via Population Fitness Distribution
| На главную |
| Генетические алгоритмы |
| Группа исследований эволюционных алгоритмов (ТПУ) |
| Дискуссионная группа по эволюционным вычислениям |
| Написать письмо |
Исследуется распределение приспособленности в популяции и ее
зависимость от параметров ГА.
Используемая методология включает два пункта:
3 Initial Experiments (Первые эксперименты)
Эксперименты направлены на исследование следующих факторов:
3.1 EA details and settings (Особенности и параметры эволюционного алгоритма)
Характеристики использованного для исследования алгоритма:
3.2 Data collection (Сбор данных)
Алгоритм запускался 100 раз. Время эволюции - 50 поколений.
В каждом поколении данные о приспособленности фиксировались после: кроссовера, мутации и отбора.
Также записывались данные о начальном распределении (после инициализации). Всего собрано 1+3*n
(n=50) распределений. После этого полученные данные сравнивались с помощью статистических тестов
Q-Q и R-square на сооветствие следующим распределениям:
4 Initial Experimental Results (Результаты первых экспериментов)
В качестве задачи была выбрана функция F1 из набора тестовых функций Де Джонга (также известна как сферическая функция) от 4 переменных.
4.1 Observed Differences Between lambda + nu and Generational GAs (Наблюдаемые отличия между (lambda + nu) и поколенческим ГА)
Увеличение давления отбора оказывает влияние на распределение приспособленности внутри популяции (см для сравнения рис.2 и рис.4).
4.2 Observed Effects of Selection, Crossover and Mutation (Наблюдаемое влияние типов селекции, кроссовера и мутации)
В [9] сделано предположение о следующем изменении распределения приспособленности в популяции в ходе эволюции. Сначала приспособленность распределена нормально, затем отбор родительских особей "искривляет" распределение влево (для задач минимизации), а кроссовер и мутация снова приводят его к нормальному виду. Таким образом в начале следующего поколения мы имеем нормальное РПП, математическое ожидание которого меньше чем математическое ожидание РПП в предыдущем поколении.
В представленной работе описанная выше гипотеза опровергается результатами экспериментов.
Показывается, что искажения РПП, вносимые кроссовером и мутацией на ранних поколениях мало отличаются, однако на более поздних поколениях различие становится более выраженным. При этом РПП после кроссовера мало соответствует какому-либо из рассматриваемых распределений, в отличии от РПП после мутации.
4.3 Experiments Using a Complex Cellular Automata Fitness Landscape (Эксперименты с анализом ландшафта функции приспособленности сложного клеточного автомата)
Исследования, аналогичные приведенным выше, были проведены для эволюции клеточного автомата.
На основании экспериментальных данных делается вывод о похожести влияния генетических операторов и селекции на РПП в обоих использованных задачах (сферическая функция и клеточный автомат) как для ранних, так и для более поздних поколений.
5 Discussion And Conclusions (Анализ результатов и заключение)
Делается вывод о пригодности использованной методологии для анализа и исследования эволюционных алгоритмов.
Отмечается, что РПП редко является нормальным, а также то, что ращличия во влиянии генетических операторов наблюдаются на более поздних поколениях.
6 Future Work (Дальнейшая работа)
Отмечается необходимость дальнейших исследований для различных функций приспособленности и типов эволюционных алгоритмов, а также поиск возможностей совместного использования уже разработанных методов анализа ГА и представленной методологии для более детального изучения работы эволюционных алгоритмов.
Скачать статью (pdf, rar, 282 kb)
К пункту 4.1.
Под поколенческим ГА понимается алгоритм, в котором все или почти все родительские особи заменяются потомками, несмотря на приспособленность, в отличие от (lambda + nu) стратегии, где сначала потомки и родители сортируются по приспособленности, и в следующее поколение попадает только лучшая часть особей.
Распределения очень напоминают хи-квадрат, только для стандартного ГА графики распределений соответствуют случаям с бОльшим количеством степеней свободы. Это, скорее всего, неудивительно, т.к. (lambda+nu) стратегия обладает большим давлением отбора (особи выживают по более строгому правилу), что уменьшает разнообразие, а, следовательно, и число степеней свободы. Вообще, я писал по этому поводу Е.Поповичи, но ответа не было.
К пункту 4.2.
Судя по приведенным рисункам происходит не только сдвиг мат. ожидания, а также уменьшение числа степеней свободы РПП.
Подобный вывод был сделан Т.Бликле и Л.Тиеле в 1995 о турнирном отборе. При этом они показали, что чем больше размер турнира, тем меньше дисперсия РПП.
Несколько смущает то, что ранним поколением считается 1-е, а поздним 6-е. Здесь, скорее всего, дело в выбранной сферической функции, которая является очень простой, в силу чего алгоритм быстро находит решение.
[16 апреля 2004г.]
