Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

 
Генетический алгоритм 
 
1. Создать начальную популяцию 
2. Цикл по поколениям пока не выполнено условие останова // цикл 
жизни одного поколения 
3. Оценить приспособленность каждой особи 
4. Выполнить отбор по приспособленности 
5. Случайным образом разбить популяцию на две группы пар 
6. Выполнить фазу вероятностной рекомбинации для пар популяции и 
заменить родителей 
7. Выполнить фазу вероятностной мутации 
8. Оценить приспособленность новой популяции и вычислить условие 
останова 
9. Объявить потомков новым поколением 
10. Конец цикла по поколениям 
Модификации генетического алгоритма 
 
Очевидно, что тонкая настройка базового генетического алгоритма 
может быть выполнена путем изменения значений вероятностей 
рекомбинации и мутации, существует много исследований и предложений в 
данной области. В настоящее время предлагаются разнообразные 
модификации генетических алгоритмов в части методов отбора по 

---

111 
приспособленности, рекомбинации и мутации. Приведем несколько 
примеров.
Метод турнирного отбора (Бриндел, 1981 г.; Гольдберг и Деб, 1991 г.)
реализуется в виде 
п
турниров для выборки п особей. Каждый турнир 
состоит в выборе 
k
элементов из популяции и отбора лучшей особи среди 
них. 
Элитные методы отбора (Де Ионг, 1975 г.) гарантируют, что при отборе 
обязательно будут выживать лучший или лучшие члены популяции. 
Сохраняется только одна лучшая особь, которая не прошла отбор, 
рекомбинацию и мутацию. Этот метод может быть внедрен практически в 
любой стандартный метод отбора.
Двухточечная рекомбинация (Гольдберг 1989 г.) и равномерная 
рекомбинация (Сисверда, 1989 г.) являются вполне достойными 
альтернативами одноточечному оператору. При двухточечной рекомбинации 
происходит выбор двух точек разрыва. Далее родительские хромосомы 
обмениваются сегментом. Сегмент располагается между двумя точками 
разрыва. При равномерной рекомбинации каждый бит первого родителя 
наследуется первым потомком с известной вероятностью. Иначе бит 
передается второму потомку. 
Механизмы мутаций могут быть также заимствованы из молекулярной 
биологии, например, обмен концевых участков хромосомы (механизм 
транслокации), обмен смежных сегментов (транспозиция). По мнению М.В. 
Ульянова, интерес представляет механизм инверсии, т. е. перестановки генов 
в хромосоме, управляющим параметром при этом может выступать 
инверсионное расстояние ­ минимальное количество единичных инверсий 
генов, преобразующих исходную хромосому в мутированную.