ДЛЯ КАЖДОЙ k ОСОБИ В ПОПУЛЯЦИИ

{

ЕСЛИ (PI > RANDOM)

{

БИТОВАЯ_МУТАЦИЯ (ОСОБЬ[k], RANDOM*ДЛИНА_ХРОМОСОМЫ_В_БИТАХ);

}

}

Схематически механизм инверсии представлен на рис. 11.

Рисунок 11. Пример работы инверсии для целочисленного кодирования

2.5.5.4. Оператор популяционного всплеска. Если разница приспособленности наилучшей и наихудшей особей в популяции меньше определенного малого значения e и это неравенство сохраняется в течение нескольких поколений, то говорят, что такая популяция выродилась. Говоря другими словами, алгоритм сошелся в окрестности какого-то предполагаемого минимума. В то же время операторы скрещивания, мутации и инверсии оказываются неспособны дать популяции свежий «генный материал». Во избежание такой ситуации, как правило, вводятся различные эвристические модификации, например оператор популяционного всплеска[5].

Принцип его действия такой: когда становится ясно, что популяция выродилась, случайным образом выбирается некоторое количество особей (обычно не более 50% популяции [13]). Затем выбранные особи инициализируется случайными точками поискового пространства (см. разд. 5.1) и помещаются обратно в популяцию на свои места. Таким образом, алгоритм получает новых особей, среди которых, возможно, будут лучшие решения.

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

(а) (б)

Рисунок 12. сетка ГА (а) до уплотнения; (б) после уплотнения.

Пример: изначально m = 4, т.е. 2⁴ = 16 узлов на заданном поисковом интервале. Оператор увеличил длину гена на 4. Таким образом, m₁ = 8, а количество узлов равно 2⁸ = 256. Следовательно, в результате применения данного оператора сетка стала плотнее в 256/16 = 16 раз.

Очень важен следующий нюанс: сразу после увеличения m вся популяция должна быть перекодирована так, чтобы фенотип особей остался прежним. В программе Genetic Optimum[6] это реализовано путем добавления 4 нулевых разрядов с левого конца каждого гена в битовой цепочке хромосомы.

2.5.6. Формирование новой популяции

Хромосомы, полученные в результате применения генетических операторов к хромосомам родительской выборки, включаются в состав нового поколения. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом популяции, после чего проверяется условие остановки алгоритма. Если условие выполнено, то результат фиксируется в виде лидера, либо осуществляется переход к следующему шагу ГА, т.е. к селекции. В классическом ГА предшествующее поколение замещается поколением потомков, имеющим ту же численность. Однако существуют модификации ГА, в которых часть наиболее приспособленных хромосом из предыдущего поколения переносится в текущую популяцию без изменения, минуя этап генетических операторов (так называемые элитные особи). Если доля новорожденных особей равна T, 0 < T < 1, тогда в новое поколение попадает (T×N) потомков, где N – размер популяции. С другой стороны (1 – T)N особей в новой популяции являются элитными особями, перенесенными с предыдущего поколения без изменения. Параметр T называют параметром разрыва поколений (generation gap) [15]. Использование элитных особей вводит в ГА подобие «генетической памяти» о лучших решениях и позволяет увеличить скорость сходимости алгоритма за счет сохранения лучшего генофонда предыдущих поколений.

2.6. Вспомогательные материалы

Пример работы ГА и анализа результатов.

При использовании ГА для решения задачи оптимизации необходимо:

1. Определить количество и тип переменных задачи, которые необходимо закодировать в хромосоме.

2. Задать критерий оценки особей в качестве функции приспособленности (целевой функции).

3. Выбрать способ кодирования и его параметры.

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

Стоит отметить, что параметры ГА, упомянутые в пункте 4 (а также, иногда, те, что указаны в пунктах 2 и 3), часто задаются методом проб и ошибок, на основе анализа получаемых результатов. Для анализа результатов работы ГА необходимо произвести серию запусков алгоритма. Описанная общая схема решения задачи с использованием ГА показана на рис. 13.

Рисунок 13. Общая схема решения задачи с использованием ГА

Пример (для задачи минимизации функции):

, n = 10, x_i Î [-5,12; 5,12].

Параметр n задает количество переменных функции z. Необходимо найти такие значения переменных x_i , при которых функция z принимает наименьшее значение.

1. Определение неизвестных переменных задачи.По условию поставленной задачи необходимо найти значения переменных x_i, минимизирующие значение функции z, поэтому в хромосоме будем кодировать значения x_i. Таким образом, каждый i-й ген хромосомы будет соответствовать i-й переменной функции z.

2. Задание функции приспособленности.имеет смысл определить приспособленность особи как значение, которое зависит от функции z при подстановке в нее вектора параметров x (генотипа этой особи). Поскольку рассматривается задача минимизации функции z, то принимается, что чем меньше значение z, тем лучше приспособлена особь. Приспособленность l-й особи f_l определяется по следующей формуле:

f_l = z_l,

где z_l – значение функции z в точке, соответствующей l-й особи.

3. Выбор способа кодирования.В качестве способа представления генетической информации рассматривается целочисленное кодирование с 10-разрядными генами. Учитывая, что содержимое каждого гена может принимать одно из 2¹⁰ = 1024 значений в диапазоне от [-5,12; 5,12], получается, что переменные x_i кодируются в хромосоме с точностью до 0,01.

4. Определение параметров ГА.Для решения задачи рассматривается популяция из 20 особей. Для отбора особей используется турнирная селекция. В качестве генетических операторов предлагается применить 1-точечное скрещивание и битовую мутацию. Вероятности применения операторов скрещивания и мутации задаются равными 0,7 и L^-1 = 0,01 (где L – длина хромосомы в битах, в данном случае L = 100) соответственно. Новое поколение формируется только из особей-потомков, т.е. величина разрыва поколений T равна 1. Результат работы ГА с выбранными параметрами представлен на рис. 14. Показаны зависимости изменения среднего <z> и наименьшего z_min по популяции значения функции z от номера поколения k. Данные усреднены по 50 независимым запускам. Тонкими огибающими линиями показаны статистические 95%-ные доверительные интервалы по 50 запускам.

Рисунок 14. Динамика z_min(k) и <z>(k). Популяция из 20 особей, турнирная селекция, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,01).

Из рисунка видно, что после 20 поколения значение z_min практически стабилизировалось и перестало «улучшаться». Из этого следует, что генерации новых хороших особей не происходит, и следует увеличить вероятность мутации, например, до 0,1. Результаты работы ГА с измененным значением вероятности мутации показаны на рис. 15.

Рисунок 15. Динамика z_min(t) и <z>(t). Популяция из 20 особей, турнирная селекция, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,1).

Увеличение вероятности мутации улучшило результат работы ГА. Стоит отметить, что теперь эволюционный процесс стабилизировался значительно позднее, примерно после 60 поколения. Минимальное значение функции z, достигнутое за отрезок из первых 100 поколений, примерно равно 9,7. Чтобы улучшить результат, имеет смысл установить разрыв поколений, например, равным T = 0,97. Результат представлен на рис. 16.

Рисунок 16. Динамика z_min(t) и <z>(t). Популяция из 20 особей, турнирная селекция, разрыв поколений T = 0,97, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,1).

Увеличение разрыва поколений привело к ускорению эволюционного поиска за счет сохранения 3% элитных особей от популяции на каждой итерации ГА. Хотя на стабилизацию значения z_min потребовалось почти 80 поколений, было найдено новое минимальное значение функции z равно 6,8.

Аналитически можно найти, что минимум функции z лежит в точке x_i = 0, i = 1, 2,…, 10 и значение z_min = 0. В случае поиска минимума функции z с точностью 0,01, для ГА с параметрами, соответствующими графику на рис. 16, решение не было найдено с заданной точностью ни в одном из 50 запусков. Чтобы найти решение имеет смысл увеличить размер популяции до 100 особей. Полученная динамика z_min(t) и <z>(t) изображена на рис. 17. В 48 из 50 запусков был найден минимум функции z с точностью 0,01. Среднее количество вычислений целевой функции, использованное для нахождения решения, равно 1904,26.

Рисунок 17. Динамика z_min(t) и <z>(t). Популяция из 100 особей, турнирная селекция, разрыв поколений T = 0,97, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,1).

Общие рекомендации к программной реализации ГА

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

Таблица 2

Компонент ГА	Процедурный подход	Объектно-ориентированный подход
Особь	Одномерный массив для записи значений генов. Размерность массива совпадает с количеством генов у одной особи (количество генов равно числу оптимизируемых параметров)	Класс «Особь», содержащий коллекцию генов с реализованным алгоритмом ее обхода (паттерн iterator).
Популяция	Двумерный массив, в котором i-я строка содержит гены i-й особи.	Типизированный класс «Популяция», содержащий коллекцию «особей». В роли параметра-типизатора может выступать класс «особь», если типов особей несколько и в каждом типе – своя логика вычислений
Оценка популяции	Подпрограмма оценки строк массива популяции в соответствии с выбранной целевой функцией.	Метод управляющего класса, оценивающий популяцию в соответствии с выбранной целевой функцией.
Приспособленность популяции	Одномерный массив, в котором i-й элемент соответствует приспособленности i-й особи.	Свойство в классе «особь», характеризующее приспособленность данной особи
Особи, выбранные для скрещивания	Двумерный массив, строки которого соответствуют хромосомам особей, выбранным для скрещивания.	Объект класса «популяция», содержащий объекты класса «особь», соответствующие выбранным особям
Реализация скрещивания, мутации, формирования нового поколения	Подпрограммы, обрабатывающие элементы массива, представляющего популяцию особей, а также популяцию особей, выбранных для скрещивания.	Методы управляющего класса, работающие с основной популяцией и выборкой особей для скрещивания.

Приведенные в таблице 2 советы по реализации ГА не являются эталонными и, возможно, далеки от идеала проектирования. Данные, приведенные в этой таблице, могут служить в качестве опорной точки для программной реализации ГА. Стоит отметить, что большую гибкость и расширяемость программной реализации не только ГА, но и любого другого алгоритма, можно достичь, грамотно применяя объектно-ориентированный подход и паттерны проектирования [16].

2.7. Список обозначений

· ГА – генетический алгоритм;

· N – размер популяции;

· m – разрядность гена (длина гена в разрядах);

· G – количество генов в хромосоме;

· L – длина хромосомы в битах;

· p_c – вероятность применения оператора скрещивания к выбранной паре родителей. В псевдокоде имеет обозначение PC;

· RND – случайное число, сгенерированное по заданному закону распределения;

· RANDOM – случайная величина, равномерно распределенная на интервале [0; 1];

· p_m – вероятность применения оператора мутации к новорожденному потомку. В псевдокоде имеет обозначение PM;

· p_I – вероятность применения оператора инверсии к новорожденному потомку. В псевдокоде имеет обозначение PI;

· T – разрыв поколений (доля новорожденных потомков в следующем поколении);

2.8. Терминологический словарь

· Популяция - это конечное множество особей.

· Особи, входящие в популяцию, в ГА представляются хромосомами с закодированным в них параметрами задачи. Таким образом, особи - это возможные решения, которые иначе называются точками в пространстве поиска.

· Хромосомы - это упорядоченные последовательности генов.

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

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

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

· Скрещивание (кроссовер) – генетический оператор, предназначенный для порождения новых решений путем обмена генами между выборкой особей.

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

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

· Лидер – самая приспособленная в текущем поколении особь.

· Вырождение популяции – событие, характеризующееся тем, что на протяжении нескольких поколений сохраняется следующее неравенство: |f_best – f_worst| £ e, где f_best – приспособленность лучшей особи популяции, f_worst – приспособленность наихудшей особи популяции, e - заданное малое число.

Приложение 3. Справочные материалы

3.1. Титульный лист

МИНОБРНАУКИ РОССИИ