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

Ячеистые генетические алгоритмы (Cellular Genetic Algorithms) - модель параллельных генетических алгоритмов. Пусть дано 2500 процессов, расположенных на сетке размером 50×50 ячеек, замкнутой, как показано на рисунке 18 (левая сторона замыкается с правой, верхняя с нижней, получается тор).

Каждый процесс может взаимодействовать только с четырьмя своими соседями (сверху, снизу, слева, справа). В каждой ячейке находится ровно одна особь. Каждый процесс будет выбирать лучшую особь среди своих соседей, скрещивать с ней особь из своей ячейки и одного полученного ребенка помещать в свою ячейку вместо родителя.

Рис. 18. Ячеистый генетический алгоритм

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

Тест по теме «Эволюционное моделирование»

Кто считается «отцом» генетических алгоритмов?

a) Д. Голдберг

b) Д. Холланд

c) К. Де Йонг

d) Нет правильного ответа

Какие методы относятся к направлению «Эволюционное моделирование»?

a) Метод группового учета аргументов

b) Нейронные сети

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

d) Эволюционное программирование

e) Эвристическое программирование

Какие понятия относятся к генетическим алгоритмам?

a) особь

b) фенотип

c) ген

d) ДНК

e) нейрон

f) функция активации

Какие виды отбора в генетических алгоритмах существуют?

a) Дискретный отбор

b) Ранговый отбор

c) Поэтапный отбор

d) Дуэльный отбор

e) Турнирный отбор

f) Рулетка

Какие бывают операторы генетического алгоритма?

a) кроссинговер

b) скрещивание

c) транслитерация

d) транслокация

e) мутация

f) конверсия

6. Какие виды генетического алгоритма подразумевают параллельную обработку?  

a) genitor

b) CHC

c) гибридные алгоритмы

d) островная модель

e) нет правильного ответа

Из какого числа особей можно выбирать пару (второго родителя) для особи в островной модели?

a) m, где m – число особей в популяции

b) m-1, где m – число особей в популяции

c) 4

d) 8

e) t, выбирается случайным образом, чаще всего t = 2

f) Нет правильного ответа

8. Какой оператор применен к особи (0001000 -> 0000000)?

a) инверсии

b) кроссовер

c) скрещивания

d) нет правильного ответа

Литература по теме «Эволюционное моделирование»:

1) Вороновский Г.К. Махотило К.В. Петрашев С.Н. Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Х.:ОСНОВА, 1997. - с.112.

2) Исаев С.А. Популярно о генетических алгоритмах. http://algolist.manual.ru/ai/ga/ga1.php

3) Каширина И.Л. Введение в эволюционное моделирование. Учебное пособие. Воронеж. 2007. с. 40.

4) Стариков А. Лаборатория BaseGroup. Генетические алгоритмы – математический аппарат. http://www.basegroup.ru/genetic/

5) Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. 230 с.

6) Яминов Б. Генетические алгоритмы. Санкт-Петербургский государственный университет. 2005. http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005