Эволюционное моделирование. Назначение и принципы построения генетических алгоритмов

Эволюционное моделирование – направление ИИ, предназначенное для воспроизведения естественных эволюционных процессов с помощью компьютерных программ.

Основа эволюционного моделирования – принципы развития природы:

1. наследственность и улучшение в поколениях полезных свойств;

2. изменчивость;

3. естественный отбор.

Алгоритмические основы эволюционного моделирования:

1. генетические алгоритмы;

2. генетическое программирование;

3. эволюционные стратегии;

4. эволюционное программирование.

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

Основателем генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (1992) (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.

Основные понятия ГА:

Хромосома – вектор (последовательность) из 0 и 1. Каждая позиция (бит) называется геном.

Индивидуум (генетический код) – набор хромосом (вариант решения задачи).

Кроссовер – операция, при которой 2 хромосомы обмениваются своими частями.

Мутация – случайное изменение одной или нескольких позиций в хромосоме.

Описание алгоритма

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

1. нахождение глобального, либо субоптимального решения;

2. исчерпание числа поколений, отпущенных на эволюцию;

3. исчерпание времени, отпущенного на эволюцию.

Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска.

Создание начальной популяции. Перед первым шагом нужно случайным образом создать некую начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности. Итогом первого шага является популяция H, состоящая из N особей.

Отбор. На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

Размножение. Размножение в генетических алгоритмах, чтобы произвести потомка, нужны несколько родителей; обычно нужны ровно два. Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо достаточно разумным способом. Недостаток ГА – достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей.

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

Стратегия элитизма – в новую популяцию добавляется лучшая хромосома предыдущего поколения.

Достоинства генетических алгоритмов:

· они не требуют никакой информации о поверхности ответа;

· разрывы, существующие на поверхности ответа имеют незначительный эффект на полную эффективность оптимизации;

· они стойки к попаданию в локальные оптимумы;

· они хорошо работают при решении крупномасштабных проблем оптимизации;

· могут быть использованы для широкого класса задач;

· просты и прозрачны в реализации;

· могут быть использованы в задачах с изменяющейся средой.

Недостатки генетических алгоритмов:

· в случае когда необходимо найти точный глобальный оптимум;

· время исполнения функции оценки велико;

· необходимо найти все решения задачи, а не одно из них;

· конфигурация является не простой (кодирование решения).