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

Основные структуры и фазы генетического алгоритма
Задача максимизации некоторой функции двух переменных 
f(x1, x2)
, 
при ограничениях: 
0 < x1 < 1 
и
0 < x2 < 1
. Обычно методика кодирования 
реальных переменных 
x1
и 
x2 
состоит в преобразовании их в двоичные 
целочисленные строки определенной длины, достаточной для того, чтобы 
обеспечить желаемую точность.
Предположим, что 10-ти разрядное кодирование достаточно для 
x1
и 
x2
. Установить соответствие между генотипом и фенотипом можно, разделив 
соответствующее двоичное целое число на 210 ­ 1. Например, 0000000000 
соответствует 0 / 1023 или 0, тогда как 1111111111 соответствует 1023 / 1023 
или 1.
Оптимизируемая структура данных есть 20-битовая строка, 
представляющая собой конкатенацию (объединение) кодировок 
x1
и 
x2
. 
Пусть переменная 
x1
размещается в крайних левых 10 битах строки, тогда 
как 
x2
размещается в правой части генотипа особи. Таким образом, генотип 
представляет собой точку в 20-мерном целочисленном пространстве 
(вершину единичного гиперкуба), которое исследуется генетическим 
алгоритмом. Для этой задачи фенотип будет представлять собой точку в 
двумерном пространстве параметров 
(x1, x2)
. Для решения задачи 
оптимизации необходимо определить для каждой структуры в пространстве 
поиска 
меру 
качества. 
Для 
этой 
цели 
используется 
функция 
приспособленности. При максимизации целевая функция часто сама 
выступает в качестве функции приспособленности, для задач минимизации 
целевая функция инвертируется и смещается в область положительных 
значений. 
Рассмотрим фазы работы простого генетического алгоритма. Вначале 
случайным образом генерируется начальная популяция (набор хромосом). 

---

109 
Работа алгоритма продолжается, пока не будет смоделировано заданное 
число поколений или выполнен некоторый критерий останова. В каждом 
поколении реализуется пропорциональный отбор приспособленности, 
одноточечная рекомбинация и вероятностная мутация. Пропорциональный 
отбор реализуется путем назначения каждой особи (хромосоме) 
i 
вероятности 
Р(i)
, равной отношению ее приспособленности к суммарной 
приспособленности популяции по целевой функции):
Затем происходит отбор (с замещением) всех п особей для дальнейшей 
генетической 
обработки, 
согласно 
убыванию 
величины 
Р(i).
Пропорциональный отбор можно реализовать с помощью рулетки – 
механизма, предложенного Гольдбергом в 1989 г. Каждый сектор «колеса» 
рулетки соответствует одному сектору для каждого члена популяции. Размер