«История развития искусственного интеллекта» 12

1   2   3   4   5   6   7   8   9   10   11

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

Мутация

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

Особь до мутации: 1 0 0 1 0 1 1 0 0 1 1 1

Особь после мутации: 1 0 0 1 0 1 0 0 0 1 1 1

Более сложной разновидностью мутации являются операторы инверсии и транслокации. Инверсия – это перестановка генов в обратном порядке внутри наугад выбранного участка хромосомы.

Особь до инверсии: 1 0 0 1 1 1 1 0 0 1 1 1

Особь после инверсии: 1 0 0 1 0 0 1 1 1 1 1 1

Транслокация - это перенос какого-либо участка хромосомы в другой сегмент этой же хромосомы.

Особь до транслокации: 1 0 0 1 1 1 1 0 0 1 1 1

Особь после транслокации: 1 1 1 0 0 0 1 1 0 1 1 1

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

Формирование нового поколения

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

1. Новые особи (потомки) занимают места своих родителей. После этого наступает следующий этап, в котором потомки оцениваются, отбираются, дают потомство и уступают место своим "детям".

2. Следующая популяция включает в себя как родителей, так и их потомков.

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

Критерии останова

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

Схождением называется такое состояние популяции, когда все строки популяции почти одинаковы и находятся в области некоторого экстремума (рис. 16).
Рис.16. Схождение генетического алгоритма

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

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

Существуют различные модели генетического алгоритма (классический, простой генетический алгоритм, гибридный, CHC генетический алгоритм и др.) Они различаются по стратегиям отбора и формирования нового поколения особей, операторами генетического алгоритма, кодированием ген и т.д.

CHC-алгоритм

CHC (Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation) был предложен Эсхелманом и характеризуется следующими параметрами:

1. 
   Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.
   
2. 
   Для скрещивания выбирается случайная пара, но не допускается, чтобы между родителями было мало Хэммингово расстояние или мало расстояние между крайними различающимися битами.
   
3. 
   Для скрещивания используется разновидность однородного кроссовера HUX (Half Uniform Crossover): ребенку переходит ровно половина битов каждого родителя.
   
4. 
   Размер популяции небольшой, около 50 особей. Этим оправдано использование однородного кроссовера.
   

CHC противопоставляет агрессивный отбор агрессивному кроссоверу, однако все равно малый размер популяции быстро приводит ее к состоянию, когда создаются только более или менее одинаковые строки. В таком случае CHC применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.

Genitor

Этот алгоритм был создан Д. Уитли. Genitor-подобные алгоритмы отличаются от классического ГА следующими тремя свойствами:

1. 
   На каждом шаге только одна пара случайных родителей создает только одного ребенка.
   
2. 
   Этот ребенок заменяет не родителя, а одну из худших особей популяции (в первоначальном Genitor — самую худшую).
   
3. 
   Отбор особи для замены производится по ее ранку (рейтингу), а не по приспособленности.
   

В Genitor поиск гиперплоскостей происходит лучше, а сходимость быстрее, чем у классического генетического алгоритма, предложенного Холландом.

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

Идея гибридных алгоритмов (hybrid algorithms) заключается в сочетании генетического алгоритма с некоторым другим методом поиска, подходящим в данной задаче. На каждом поколении каждый полученный потомок оптимизируется этим методом, после чего производятся обычные для генетического алгоритма действия.

Такой вид развития называется Ламарковой эволюцией, при которой особь способна обучаться, а затем полученные навыки записывать в собственный генотип, чтобы потом передать их потомкам. И хотя такой метод ухудшает способность алгоритма искать решение с помощью отбора гиперплоскостей, однако на практике гибридные алгоритмы оказываются очень удачными. Это связано с тем, что обычно велика вероятность того, что одна из особей попадет в область глобального максимума и после оптимизации окажется решением задачи.

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

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

Рассмотрим переход от классического генетического алгоритма к параллельному. Для этого будем использовать турнирный отбор. Заведем N⁄2 процессов (здесь и далее процесс подразумевается как некоторая машина, процессор, который может работать независимо). Каждый из них будет выбирать случайно из популяции 4 особи, проводить 2 турнира и скрещивать победителей. Полученные дети будут записываться в новое поколение. Таким образом, за один цикл работы одного процесса будет сменяться целое поколение.

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

Островная модель (island model, рис. 17) — это тоже модель параллельного генетического алгоритма. Она заключается в следующем: пусть у нас есть 16 процессов и 1600 особей. Разобьем их на 16 подпопуляций по 100 особей. Каждая их них будет развиваться отдельно с помощью некого генетического алгоритма. Таким образом, можно сказать, что мы расселили особи по 16-ти изолированным островам.
Рис. 17. Островная модель генетического алгоритма

Изредка (например, каждые 5 поколений) процессы (или острова) будут обмениваться несколькими хорошими особями. Это называется миграция. Она позволяет островам обмениваться генетическим материалом.

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

Генетические алгоритмы стохастичны, поэтому при разных его запусках популяция может сходиться к разным решениям (хотя все они в некоторой степени «хорошие»). Островная модель позволяет запустить алгоритм сразу несколько раз и пытаться совмещать «достижения» разных островов для получения в одной из подпопуляций наилучшего решения.

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

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

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

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

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

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

1. 
   Д. Голдберг
   
2. 
   Д. Холланд
   
3. 
   К. Де Йонг
   
4. 
   Нет правильного ответа
   

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

1. 
   Метод группового учета аргументов
   
2. 
   Нейронные сети
   
3. 
   Генетические алгоритмы
   
4. 
   Эволюционное программирование
   
5. 
   Эвристическое программирование
   

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

1. 
   особь
   
2. 
   фенотип
   
3. 
   ген
   
4. 
   ДНК
   
5. 
   нейрон
   
6. 
   функция активации
   

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

1. 
   Дискретный отбор
   
2. 
   Ранговый отбор
   
3. 
   Поэтапный отбор
   
4. 
   Дуэльный отбор
   
5. 
   Турнирный отбор
   
6. 
   Рулетка
   

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

1. 
   кроссинговер
   
2. 
   скрещивание
   
3. 
   транслитерация
   
4. 
   транслокация
   
5. 
   мутация
   
6. 
   конверсия
   

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

1. 
   genitor
   
2. 
   CHC
   
3. 
   гибридные алгоритмы
   
4. 
   островная модель
   
5. 
   нет правильного ответа
   

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

1. 
   m, где m – число особей в популяции
   
2. 
   m-1, где m – число особей в популяции
   
3. 
   4
   
4. 
   8
   
5. 
   t, выбирается случайным образом, чаще всего t = 2
   
6. 
   Нет правильного ответа
   

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

1. 
   инверсии
   
2. 
   кроссовер
   
3. 
   скрещивания
   
4. 
   нет правильного ответа
   

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

1   2   3   4   5   6   7   8   9   10   11

При копировании материала укажите ссылку © 2024
контакты
rykovodstvo.ru