Генетические алгоритмы поиска глобального экстремума

Генетические алгоритмы поиска глобального экстремума

Курсовая работа

по дисциплине - Методы оптимизации и теория принятия решений

Генетические алгоритмы поиска глобального экстремума

 

Содержание:

Введение

1. Эволюционные процессы в природе

2. Принцип работы генетического алгоритма

3. Операторы генетических алгоритмов

3.1 Операторы выбора родителей

3.2 Рекомбинация (воспроизведение)

3.3 Мутация

3.4 Операторы отбора особей в новую популяцию

4. Разнообразие генетических алгоритмов

5. Модели параллельных генетических алгоритмов

6. Модернизация генетических алгоритмов

Заключение

Список литературы

Введение

Как известно, оптимизационные задачи заключаются в нахождении минимума или максимума целевой функции. Как правило, целевая функция - сложная функция, зависящая от некоторых входных параметров. В оптимизационной задаче требуется найти значения входных параметров, при которых целевая функция достигает минимального или максимального значения. Для этого существует целый класс оптимизационных методов, которые можно условно разделить на методы, использующие понятие производной (градиентные методы) и стохастические методы (методы, основанные на получении большого числа реализаций стохастического (случайного) процесса). С их помощью можно найти экстремальное значение целевой функции, но не всегда можно быть уверенным, что получено значение глобального экстремума. Нахождение локального экстремума вместо глобального называется преждевременной сходимостью. Для решения этой проблемы и проводится поиск новых оптимизационных алгоритмов. Предложенные сравнительно недавно - в 1975 году в Мичиганском университете Джоном Холландом (John Holland) генетические алгоритмы (ГА) основаны на принципах естественного отбора Ч. Дарвина и относятся к стохастическим методам.

Изначально новый алгоритм получил название «репродуктивный план Холланда» и в дальнейшем активно использовался в качестве базового алгоритма в эволюционных вычислениях. Идеи Холланда развили его ученики Кеннет Де Йонг (Kenneth De Jong) из университета Джорджа Мейсона (Вирджиния) и Дэвид Голдберг (David E. Goldberg) из лаборатории ГА Иллинойса. Благодаря им, был создан классический ГА, описаны все операторы и исследовано поведение группы тестовых функций (именно алгоритм Голдберга и получил название «генетический алгоритм»).

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

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

генетический оператор алгоритм функция

1. Эволюционные процессы в природе

Теория Дарвина биологической эволюции была изложена в 1859 г. в работе «Происхождение видов». Она рассматривает изменение популяции биологических видов для наилучшего приспособления к окружающей среде. В основе модели эволюции Дарвина лежат случайные изменения отдельных материальных элементов живого организма при переходе от поколения к поколению. Целесообразные изменения, которые облегчают выживание и производство потомков в данной конкретной внешней среде, сохраняются и передаются потомству (т.е. наследуются). Особи, не имеющие соответствующих характеристик, погибают, не оставив потомства или оставив его меньше, чем приспособленные (считается, что количество потомства пропорционально степени приспособленности).

Все члены популяции характеризуются индивидуальными внешними параметрами (фенотипом).

Некоторые из параметров оказываются полезными для выживания и размножения, другие скорее вредят. В каждой клетке любого живого организма содержится вся генетическая информация этой особи (генотип). Эта информация записана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это очень длинная строка символов, где используются 4 буквы. В клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой.

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

При размножении особей происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссинговер (crossing over, скрещивание). При кроссинговере ДНК предков делятся на две части и обмениваются своими половинками.

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

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

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

Генетические алгоритмы моделируют процесс эволюции в природе. Тем самым для решения задачи оптимизации многопараметрической функции и применяется теория Дарвина.

2. Принцип работы генетического алгоритма

Основные принципы работы ГА заключены в следующем (см. также схему 1):

1.         Генерируем начальную популяцию из n хромосом.

2.         Вычисляем для каждой хромосомы ее пригодность.

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

4.         Проводим кроссинговер двух родителей с вероятностью p_c, производя двух потомков.

5.         Проводим мутацию потомков с вероятностью p_m.

6.         Повторяем шаги 3-5, пока не будет сгенерировано новое поколение популяции, содержащее n хромосом.

7.         Повторяем шаги 2-6, пока не будет достигнут критерий окончания процесса.

Схема 1. Простой генетический алгоритм

Критерием окончания процесса может служить заданное количество поколений или схождение (convergence) популяции.

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

Пример основных принципов работы генетических алгоритмов:

Пусть требуется найти глобальный минимум функции

на отрезке [0; 7] (рис. 1).

На этом отрезке функция принимает минимальное значение в точке  = 1. Очевидно, что в точке  = 6 функция попадает в локальный минимум. Если для нахождения глобального минимума использовать градиентные методы, то в зависимости от начального приближения можно попасть в данный локальный минимум.

Для простоты положим, что x принимает только целые значения, т.е.  {0,1,2,3,4,5,6,7}. Это предположение существенно упростит изложение, сохранив все основные особенности работы генетического алгоритма.

Выберем случайным образом несколько чисел на отрезке [0;7]: {2,3,5,4}. Будем рассматривать эти числа в качестве пробных решений нашей задачи.

Рис. 1. График целевой функции с выбранными значениями пробных решений

Основной идеей генетических алгоритмов является организация «борьбы за существование» и «естественного отбора» среди этих пробных решений. Запишем пробные решения в двоичной форме: {010,011,101,100}. Поскольку генетические алгоритмы используют биологические аналогии, то и применяющаяся терминология напоминает биологическую. Так, одно пробное решение, записанное в двоичной форме, обычно называют особью или хромосомой, а набор всех пробных решений - популяцией. Как известно, принцип естественного отбора заключается в том, что в конкурентной борьбе выживает наиболее приспособленный. В нашем случае приспособленность особи определяется целевой функцией: чем меньше значение целевой функции, тем более приспособленной является особь, т.е. пробное решение, использовавшееся в качестве аргумента целевой функции (см. табл. 1).

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

Например: пусть скрещиваются две хромосомы 111111 и 000000. Определяем случайным образом точку разрыва хромосомы, пусть, это будет 3: 111|111 000|000. Теперь хромосомы обмениваются частями, стоящими после точки разрыва, и образуют двух новых потомков: 111000 и 000111.

Таблица 1

Исходная популяция

№	Особь
	Целое число	Двоичное число	Приспособленность
1	2	010	-0,33
2	3	011	7,25
3	101	7,92
4	4	100	10,33

Для нашей популяции процесс создания первого поколения потомков показан в таблице 2.

Таблица 2

Одноточечный кроссинговер

№	Особь популяции	Выбранный номер	Вторая особь-родитель	Точка кроссинговера	Особи-потомки
1	010	4	100	1	000
					110
2	011	2	011		011
					011
3	101	1	010	2	100
					011
4	100	4	100		100
					100

Следующим шагом в работе генетического алгоритма являются мутации, т.е. случайные изменения полученных в результате скрещивания хромосом. Пусть вероятность мутации равна 0,3. Для каждого потомка возьмем случайное число на отрезке [0;1], и если это число меньше 0,3, то инвертируем случайно выбранный ген (заменим 0 на 1 или наоборот) (см. табл. 3).

Таблица 3

Мутация потомков

№	Особи-потомки	Случайное число	Выбранный ген для мутации	Потомок после мутации	Приспособленность потомка  до мутации	Приспособленность потомка  после мутации
1	000	0,1	3	001	5	-5,42
2	110	0,6	-	110	5	5
3	100	0,5	-	100	10,33
4	011	0,2	1	111	7,25	12,58

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

Рис. 2. Изменение популяции в процессе естественного отбора

Теперь из четырех особей-родителей и четырех полученных особей потомков необходимо сформировать новую популяцию. В новую популяцию отберем четыре наиболее приспособленных особей из числа «старых» особей и особей-потомков (см. табл. 4).

Таблица 4

Формирование новой популяции из особей-родителей и особей-потомков

№	Особи	Приспособленность	Новая популяция	Приспособленность особей в новой популяции
1	010	-0,33	001	-5,42
2	011	7,25	010	-0,33
3	101	7,92	110	5
4	100	10,33	011	7,25
5	001	-5,42
6	110	5
7	100	10,33
8	111	12,58

В результате получим новое поколение, которое представлено на рис. 3.

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

Рис. 3. Особи новой популяции

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

3. Операторы генетических алгоритмов

3.1 Операторы выбора родителей

Существует несколько подходов к выбору родительской пары.

Панмиксия - самый простой оператор отбора. В соответствии с ним каждому члену популяции сопоставляется случайное целое число на отрезке [1;n], где n - количество особей в популяции. Будем рассматривать эти числа как номера особей, которые примут участие в скрещивании. При таком выборе какие-то из членов популяции не будут участвовать в процессе размножения, так как образуют пару сами с собой. Какие-то члены популяции примут участие в процессе воспроизводства неоднократно с различными особями популяции. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.

Инбридинг представляет собой такой метод, когда первый родитель выбирается случайным образом, а вторым родителем является член популяции ближайший к первому. Здесь «ближайший» может пониматься, например, в смысле минимального расстояния Хемминга (для бинарных строк) или евклидова расстояния между двумя вещественными векторами. Расстояние Хемминга равно числу различающихся локусов (разрядов) в бинарной строке. Пример определения родства бинарных хромосом при выборе родительской пары для хромосомы 1010001 показан в табл. 5.

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

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

Таблица 5

Хеммингово расстояние между хромосомами популяции и хромосомой 1010001

Хромосомы популяции	Количество отличающихся локусов
1000000	2
1010101	1
1111111
1100001	2
0110011	3
0100011	4
0011100	4
0000000	3

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

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

При турнирном отборе (tournament selection) из популяции, содержащей N особей, выбираются случайным образом t особей, и лучшая из них особь записывается в промежуточный массив (рис. 4). Эта операция повторяется N раз. Особи в полученном промежуточном массиве затем используются для скрещивания (также случайным образом). Размер группы строк, отбираемых для турнира, часто равен 2. В этом случае говорят о двоичном (парном) турнире. Вообще же t называют численностью турнира. Преимуществом данного способа является то, что он не требует дополнительных вычислений.

Рис. 4. Турнирный отбор

В методе рулетки (roulette-wheel selection) особи отбираются с помощью N «запусков» рулетки, где N - размер популяции. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален вероятности попадания в новую популяцию P(i), вычисляемой по формуле:

где f(i) - пригодность i-й особи. Ожидаемое число копий i-ой хромосомы после оператора рулетки определяются по формуле Ni = P(i)N.

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

Таблица 6

Метод рулетки. Суммарная пригодность = 200, суммарная вероятность = 1

Популяция из 5 особей	Пригодность	Вероятность выбора
С1	52	52/200 = 0,26
С2	85	85/200 = 0,425
С3	37	37/200 = 0,185
С4	3	3/200 = 0,015
С5	23	23/200 = 0,115

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

3.2 Рекомбинация (воспроизведение)

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

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

Дискретная рекомбинация соответствует обмену генами между особями. Для иллюстрации данного оператора сравним две особи с тремя генами:

Особь 1	12	25	7
Особь 2	116	4	34

Для создания двух потомков с равной вероятностью случайно выберем номер особи для каждого гена:

Схема 1	2	2	1
Схема 2	1	2	1

Согласно схеме создадим потомков:

Потомок 1	116	4	7
Потомок 2	12	4	7

Дискретная рекомбинация применима для любого типа генов (двоичные, вещественные и символьные).

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

где множитель  - случайное число на отрезке [-d, 1 + d], d  0. Как отмечают сторонники этого метода, наиболее оптимальное воспроизведение получается при d = 0,25. Для каждого гена создаваемого потомка выбирается отдельный множитель .

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

Линейная рекомбинация (Line recombination) отличается от промежуточной тем, что множитель  выбирается для каждого потомка один раз. Если рассматривать особи популяции как точки в k-мерном пространстве, где k - количество генов в одной особи, то можно сказать, что при линейной рекомбинации генерируемые точки потомков лежат на прямой, заданной двумя точками - родителями.

Кроссинговер (бинарная рекомбинация)

Рекомбинацию бинарных строк принято называть кроссинговером (кроссовером) или скрещиванием.

Одноточечный кроссинговер (Single-point crossover) моделируется следующим образом. Пусть имеются две родительские особи с хромосомами XXXXXX и YYYYYY. Случайным образом определяется точка внутри хромосомы (точка разрыва), в которой обе хромосомы делятся на две части и обмениваются ими:

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

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

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

Для многоточечного кроссинговера (Multi-point crossover) точки разреза выбираются случайно без повторений и сортируются в порядке возрастания. При кроссинговере происходит обмен участками хромосом, ограниченными точками разреза и таким образом получают двух потомков. Участок особи с первым геном до первой точки разреза в обмене не участвует. Применение многоточечного кроссинговера требует введения нескольких переменных (точек разреза), и для воспроизведения выбираются особи с наибольшей приспособленностью.

Одноточечный и многоточечный кроссинговер определяют точки разреза, которые разделяют особи на части. В отличие от них однородный кроссинговер (Uniform crossover) создает маску (схему) особи, в каждом локусе которой находится потенциальная точка кроссинговера. Маска кроссинговера имеет ту же длину, что и скрещивающиеся особи. Создать маску можно следующим образом: введем некоторую величину 0 < p₀ < 1, и если случайное число больше p₀, то на n-ю позицию маски ставим 0, иначе - 1. Таким образом, гены маски представляют собой случайные двоичные числа (0 или 1). Согласно этим значениям, геном потомка становится первая (если ген маски = 0) или вторая (если ген маски = 1) особь-родитель.

Триадный кроссинговер (Triadic crossover). Данная разновидность кроссинговера отличается от однородного тем, что после отбора пары родителей из остальных членов популяции случайным образом выбирается особь, которая в дальнейшем используется в качестве маски. Далее 10 % генов маски мутируют. Затем гены первого родителя сравниваются с генами маски: если гены одинаковы, то они передаются первому потомку, в противном случае на соответствующие позиции хромосомы потомка переходят гены второго родителя. Генотип второго потомка отличается от генотипа первого тем, что на тех позициях, где у первого потомка стоят гены первого родителя, у второго потомка стоят гены второго родителя и наоборот.

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

Кроссинговер с уменьшением замены (Crossover with reduced surrogate). Оператор уменьшения замены ограничивает кроссинговер, чтобы всегда, когда это возможно, создавать новые особи. Это осуществляется за счет ограничения на выбор точки разреза: точки разреза должны появляться только там, где гены различаются.

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

3.3 Мутация

После процесса воспроизводства происходят мутации (mutation). Данный оператор необходим для «выбивания» популяции из локального экстремума и препятствует преждевременной сходимости. Это достигается за счет того, что изменяется случайно выбранный ген в хромосоме.

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

Вероятность мутации p_m (как правило, p_m << 1) может являться или фиксированным случайным числом на отрезке [0;1], или функцией от какой-либо характеристики решаемой задачи. Например, можно положить вероятность мутирования генов, обратно пропорциональную числу всех генов в особи (размерности).

Мутация для вещественных особей (Real valued mutation).

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

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

новая переменная = старая переменная ± ,

где знаки + или  выбираются с равной вероятностью,  = 0,5  поисковое пространство (интервал изменения данной переменной),

 = 1 с вероятностью  , в противном случае  = 0, m - параметр.

Новая особь, получившаяся при такой мутации, не намного отличается от старой. Это связано с тем, что вероятность маленького шага мутации выше, чем вероятность большого шага. При m = 20, данный алгоритм мутации пригоден для локализации оптимума с точностью .

Плотность мутации (Density mutation). Стратегия мутации с использованием понятия плотности заключается в мутировании каждого гена потомка с заданной вероятностью. Таким образом, кроме вероятности применения мутации к самому потомку используется еще вероятность применения мутации к каждому его гену, величину которой выбирают с таким расчетом, чтобы в среднем мутировало от 1 до 10 % генов.

3.4 Операторы отбора особей в новую популяцию

Для создания новой популяции можно использовать различные методы отбора особей.

Отбор усечением (Truncation selection). При отборе усечением используют популяцию, состоящую как из особей-родителей, так и особей-потомков, отсортированную по возрастанию значений функции пригодности особей. Число особей для скрещивания выбирается в соответствии с порогом Т  [0;1]. Порог определяет, какая доля особей, начиная с самой первой (самой пригодной), будет принимать участие в отборе. Порог можно задать и числом больше 1, тогда он будет просто равен числу особей из текущей популяции, допущенных к отбору. Среди особей, попавших «под порог», случайным образом выбирается одна и записывается в новую популяцию. Процесс повторяется N раз, пока размер новой популяции не станет равен размеру исходной популяции. Новая популяция состоит только из особей с высокой пригодностью, причем одна и та же особь может встречаться несколько раз, а некоторые особи, имеющие пригодность выше пороговой, могут не попасть в новую популяцию.

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

Элитарный отбор (Elite selection). Создается промежуточная популяция, которая включает в себя как родителей, так и их потомков. Члены этой популяции оцениваются, а за тем из них выбираются N самых лучших (пригодных), которые и войдут в следующее поколение. Зачастую данный метод комбинируют с другими - выбирают в новую популяцию, например, 10 % «элитных» особей, а остальные 90 % - одним из традиционных методов селекции. Иногда эти 90 % особей создают случайно, как при создании начальной популяции перед запуском работы генетического алгоритма. Использование стратегии элитизма оказывается весьма полезным для эффективности ГА, так как не допускает потерю лучших решений. К примеру, если популяция сошлась в локальном максимуме, а мутация вывела одну из строк в область глобального, то при предыдущей стратегии весьма вероятно, что эта особь в результате скрещивания будет потеряна, и решение задачи не будет получено. Если же используется элитизм, то полученное хорошее решение будет оставаться в популяции до тех пор, пока не будет найдено еще лучшее.

Отбор вытеснением (Exclusion selection). В данном отборе выбор особи в новую популяцию зависит не только от величины ее пригодности, но и от того, есть ли уже в формируемой популяции особь с аналогичным хромосомным набором. Отбор проводится из числа родителей и их потомков. Из всех особей с одинаковой приспособленностью предпочтение сначала отдается особям с разными генотипами. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, во-вторых, в популяции постоянно поддерживается генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из удаленных особей, вместо особей, группирующихся около текущего найденного решения. Данный метод наиболее пригоден для многоэкстремальных задач, при этом помимо определения глобальных экстремумов появляется возможность выделить и те локальные максимумы, значения которых близки к глобальным.

4. Разнообразие генетических алгоритмов

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

Канонический ГА. Данная модель алгоритма является классической. Она была предложена Джоном Холландом. Согласно ей, популяция состоит из N хромосом с фиксированной разрядностью генов. С помощью пропорционального отбора формируется промежуточный массив, из которого случайным образом выбираются два родителя. Далее производится одноточечный кроссинговер, и созданные два потомка мутируют (одноточечная мутация) с заданной вероятностью. Мутировавшие потомки занимают места своих родителей. Процесс продолжается до тех пор, пока не будет достигнут критерий окончания алгоритма.

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

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

Гибридный алгоритм. Идея гибридных алгоритмов (Hybrid algorithms) заключается в сочетании генетического алгоритма с некоторым другим классическим методом поиска, подходящим в данной задаче. В каждом поколении все сгенерированные потомки оптимизируются выбранным методом и затем заносятся в новую популяцию. Тем самым получается, что каждая особь в популяции достигает локального оптимума, вблизи которого она находится. Далее производятся обычные для ГА действия: отбор родительских пар, кроссинговер и мутации. На практике гибридные алгоритмы оказываются очень удачными. Это связано с тем, что вероятность попадания одной из особей в область глобального максимума обычно велика. После оптимизации такая особь будет являться решением задачи.

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

СНС (Eshelman, 1991) расшифровывается как Cross-population selection, Heterogeneous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, следующих за оператором кроссинговера, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В данном методе для кроссинговера выбирается случайная пара, но не допускается, чтобы между родителями было маленькое хеммингово расстояние или мало расстояние между крайними различающимися битами. Для скрещивания используется разновидность однородного кроссовера HUX (Half Uniform Crossover), при котором потомку переходит ровно половина битов каждого родителя. Для нового поколения выбираются N лучших различных особей среди родителей и детей. При этом дублирование строк не допускается. В модели СНС размер популяции относительно мал - около 50 особей. Это оправдывает использование однородного кроссинговера и позволяет алгоритму сойтись к решению. При получении более или менее одинаковых строк СНС применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссинговер.

В генетическом алгоритме с нефиксированным размером популяции (Genetic Algorithm with Varying Population Size - GAVaPS) каждой особи приписывается максимальный возраст, т.е. число поколений, по прошествии которых особь погибает. Внедрение в алгоритм нового параметра - возраста - позволяет исключить оператор отбора в новую популяцию. Возраст каждой особи индивидуален и зависит от ее приспособленности. В каждом поколении t на этапе воспроизведения обычным образом создается дополнительная популяция из потомков. Размер дополнительной популяции (AuxPopsize(t)) пропорционален размеру основной популяции (Popsize(t)) и равен:

AuxPopsize(t) = [Popsize(t) p_c],

где p_c - вероятность воспроизведения.

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

Popsize(t + 1) = Popsize(t) + AuxPopsize(t) - D(t),

где D(t) - число особей, которые умирают в поколении t.

5. Модели параллельных генетических алгоритмов

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

Простейший параллельный ГА.

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

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

Отбор особей для миграции может происходить следующим образом:

• случайная однообразная выборка из числа особей;

• пропорциональный отбор: для миграции берутся наиболее пригодные особи.

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

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

Другая основная миграционная схема - это топология кольца (см. схему 3). Здесь особи передаются между соседними (по направлению обхода) подпопуляциями. Таким образом, особи из одной подпопуляций могут мигрировать только в одну - соседнюю подпопуляцию.

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

Глобальная модель «Рабочий и Хозяин».

Алгоритм «Рабочий и Хозяин» (Global model - worker/farmer) реализуется с применением нескольких одновременно работающих компьютеров (см. схему 5). Среди всех компьютеров выделяют «Хозяина» и «Рабочих». Компьютеры - «Рабочие» отвечают за процессы воспроизводства, мутации и вычисления функции пригодности особей для их отбора в новое поколение. Все созданные и оцененные «Рабочими» особи поступают к компьютеру - «Хозяину», который затем проводит отбор особей согласно оценке их пригодности в новую популяцию. Отобранные особи передаются «Хозяином» к компьютерам - «Рабочим».

Модель диффузии, или островная модель ГА.

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

Пусть выполняются 16 независимых генетических алгоритмов, используя подпопуляции из 1000 особей на каждом процессоре. Если миграций нет, то происходит 16 независимых поисков решения. Все поиски ведутся на различных начальных популяциях и сходятся к определенным особям. Исследования подтверждают, что генетический дрейф склонен приводить подпопуляции к различным доминирующим особям. Это связано с тем, что, во-первых, количество островов, принимающих доминирующих «эмигрантов» с острова, ограничено (2-5 островов). Во-вторых, обмен особями односторонен. Поэтому в большой популяции появятся группы островов с различными доминирующими особями. Если популяция небольшого размера, то возможно быстрая миграция ложных доминирующих особей. Например, истинное решение находится только на одном острове, а несколько ложных доминант - на других островах. Тогда при миграции количество ложных особей на островах возрастет (на каждый остров миграции происходят с не менее 2 островов), генетическим алгоритмом верное решение будет разрушено. Тем самым в маленькой популяции при генетическом дрейфе возможно появление ошибочных доминирующих особей и схождение алгоритма к ложному оптимуму.

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

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

6. Модернизация генетических алгоритмов

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

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

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

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

Неоднородная мутация.

где q случайным образом принимает значения 0 или 1; r - случайное число, принимающее значение из диапазона [0; 1]; t - номер поколения; Т - максимальное число поколений; b - некоторый параметр, обусловленный природой задачи; и - верхняя и нижняя границы для величины .

Инцест.

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

Заключение

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

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

·        не требуют никакой информации о поведении функции (например, дифференцируемости и непрерывности);

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

·        пригодны для решения крупномасштабных задач оптимизации за счет эффективного распараллеливания;

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

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

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

В то же время существует ряд трудностей в практическом использовании генетических алгоритмов, а именно:

·        очень сложно найти точный глобальный оптимум;

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

·        сложно смоделировать для нахождения всех решений задачи;

·        трудно применить для изолированных функций. Изолированность («поиск иголки в стоге сена») - проблема для любого метода оптимизации, поскольку функция не предоставляет никакой информации, подсказывающей, в какой области искать экстремум. Лишь случайное попадание особи в глобальный экстремум может решить задачу (рис. 6);

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

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

Список литературы

.          Батищев Д.И. Генетические алгоритмы решения экстремальных задач /Д.И. Батищев/ - Нижний Новгород: Нижегородский госуниверситет, 1995. - 62 с.

2.       Дарвин Ч. О происхождении видов путём естественного отбора или сохранении благоприятствуемых пород в борьбе за жизнь /Ч. Дарвин/ - М.: АН СССР, 1939.

.         Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы /Л.А. Гладков, В.В. Курейчик, В.М. Курейчик/ - М.: ФИЗМАТЛИТ, 2006. - 320 с.

.         Панченко Т.В. Генетические алгоритмы /Т.В. Панченко/ - Астрахань: издательский дом «Астраханский университет», 2007. - 87 с.

.         Санкт-Петербургский государственный университет информационных технологий, механики и оптики. Генетические алгоритмы. [Электронный ресурс]. Режим доступа: http://rain.ifmo.ru/cat/. Загл. с экрана.

.         Ю. Цой. Авторский сайт. [Электронный ресурс]. Режим доступа: http://www.qai.narod.ru/. Загл. с экрана.

.         Исаев С.А. Популярно о генетических алгоритмах. [Электронный ресурс]. Режим доступа: http://algolist.manual.ru/ai/ga/ga1.php. Загл. с экрана.