1.4 Отбор

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

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

Существует несколько способов реализации данного отбора:

• stochastic sampling. Пусть особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. N раз запуская рулетку, выбираем требуемое количество особей для записи в промежуточную популяцию.
• remainder stochastic sampling. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная показывает её вероятность попасть туда ещё раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию.¹⁵ Такой способ иллюстрируется рисунком 3:

Рис 3. Способ remainder stochastic sampling в реализации отбора

1.5 Скрещивание

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

           В классическом ГА применяется одноточечный оператор кроссовера (1-point crossover): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями ¹⁶ (рис.4).

Рис 4. Одноточечный оператор кроссовера

1.6 Мутация

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

     Каждый  бит каждой особи популяции с  некоторой вероятностью инвертируется. Эта вероятность обычно очень  мала, менее 1% (рис 5).  

1011001100101101 -> 1011001101101101

Рис 5. Мутация 

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

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

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

1. нахождение глобального, либо субоптимального решения;
2. исчерпание числа поколений, отпущенных на эволюцию;
3. исчерпание времени, отпущенного на эволюцию. Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска.¹⁸

2. Преимущества  и  недостатки  ГА

2.1 Преимущества

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

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

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

• 2.2 Недостатки

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

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

3.1 Canonical GA (J. Holland)

   Данная  модель алгоритма является классической. Она была предложена Джоном Холландом в его знаменитой работе "Адаптация в природных и исусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Пропорциональный отбор.
• Особи для скрещивания выбираются случайным образом.
• Одноточечный кроссовер и одноточечная мутация.
• Следующее поколение формируется из потомков текущего поколения без "элитизма". Потомки занимают места своих родителей. ²¹
 


3.2 Genitor (D. Whitley)

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

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Особи для скрещивания выбираются случайным образом.
• Ограничений на тип кроссовера и мутации нет.
• В результате скрещивания особей получается один потомок, который занимает место наименее приспособленной особи.²²
 


3.3 Hybrid algorithm (L. "Dave" Davis)

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

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Любые комбинации стратегий отбора и формирования следующего поколения
• Ограничений на тип кроссовера и мутации нет.
• ГА применяется на начальном этапе, а затем в работу включается классический метод оптимизации.²³
 

3.4 Island Model GA

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

• Наличие нескольких популяций, как правило, одинакового фиксированного размера.
• Фиксированная разрядность генов.
• Любые комбинации стратегий отбора и формирования следующего поколения в каждой популяции. Можно сделать так, что в разных популяциях будут использоваться разные комбинации стратегий, хотя даже один вариант дает разнообразные решения на различных "островах".
• Ограничений на тип кроссовера и мутации нет.
• Случайный обмен особями между "островами". Если миграция будет слишком активной, то особенности островной модели будут сглажены, и она будет не очень сильно отличаться от моделей ГА без параллелизма.²⁴

 

3.5 CHC (Eshelman)

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

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Перезапуск алгоритма после нахождения решения.
• Небольшая популяция.
• Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.
• Отбор в следующее поколение проводится между родительскими особями и потомками.
• Используется половинный однородный кроссовер (HUX).
• Макромутация при перезапуске.²⁵

II. Практическая часть реализации генетических алгоритмов

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

1. Математическое обоснование принципа работы программы 

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

       Диофа́нтово уравнение или уравнение в целых числах — это уравнение с целыми коэффициентами и неизвестными, которые могут принимать только целые значения. Названы в честь древнегреческого математика Диофанта.²⁶

     Рассмотрим  диофантово уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время  находит искомое решение (a, b, c, d).

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

     Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем  использовать меньшее ограничение  для b,c,d, но для упрощения пусть  будет 30. 
 
 

Таблица 1: 1-е поколение хромосом и их содержимое 

     Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением. 

Таблица 2: Коэффициенты выживаемости первого поколения хромосом (набора решений) 

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

Таблица 3: Вероятность оказаться родителем

     Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-стонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем:

Таблица 4: Симуляция выбора родителей 

     Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кроссоверов (| = разделительная линия):