Генетические алгоритмы

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

Идея генетических алгоритмов была высказана Д.Холландом в 60-е годы и затем развита им в фундаментальной работе " Адаптация в естественных и искусственных системах" (1975). Ипользовать их в численной оптимизации предложил Д.Гольдберг (1995). Но в основном генетические алгоритмы находят применение для обучения нейронных сетей. Поэтому здесь они будут рассмотрены только на уровне идей.

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

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

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

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

(8.54)

где f_i – значение критерия на i- й особи.

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

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

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

На последнем шаге цикла проверяется условие останова. В качестве критерия останова используют число поколений, качество поколения (пороговое значение), близость особей между собой и др.

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

Отличительной чертой генетических алгоритмов является одновременное использование набора точек в пространстве поиска вместо перехода от точки к точке в традиционных методах. Эта особенность позволяет применять такие алгоритмы для решения многоэкстремальных задач.

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

Пример 8.7. Найти целочисленный максимум функции f (x ₁, x ₂)=675- x ₁²- x ₂²+20 x ₁+10 x ₂ на области 5£ x ₁£ 36, 2£ x ₂£ 17.

Сначала сделаем преобразования: x ₁= y ₁+5, x ₂= y ₂+2, тогда 0£ y ₁£ 31, 0£ y ₂£ 15. В этом случае новые аргументы функции y ₁, y ₂ можно представить в двоичной системе, а за код принять строку из 9 бит. Первые 5 бит будут отражать y ₁, остальные – y ₂. Определим размер популяции: N =2log₂(16*32)=18. Ограничимся N =10. Используя датчик случайных чисел, создаем исходную популяцию и для всех ее особей вычисляем значение f и вероятность отбора p_i (табл. 8.1).

Таблица 8.1

Действия оператора отбора, использующего распределение p_i, привели к выбору родительских пар (2, 7), (5, 10), (6, 9), (1, 4), (4, 9). В каждой паре точки разбиения выбираются независимо с помощью датчика целых случайных чисел от 1 до 8 с равными вероятностями. Результаты работы оператора скрещивания приведены в табл. 8.2. Точки разбиения показаны косой чертой. Значения аргументов и функции даны для потомков.

Таблица 8.2

Теперь предположим, что оператор мутации сработал для 7 потомка, поменяв местами биты 1 и 2. Код этого потомка сменился с 011101110 на 101011010, значение функции стало 495. Расширенная популяция включает 10 исходных особей и 10 потомков. Сокращаем популяцию до принятого размера, отбрасывая особи с меньшими значениями функции. Полученная после этого популяция первого поколения представлена в табл. 8.3. В ней только первые 4 особи из исходной популяции.

Таблица 8.3

Из сравнения данных в таблицах 8.1 и 8.3 видно, что новая популяция лучше исходной. Если среднее значение целевой функции на начальной популяции было равно 585, 3, то на новом поколении оно возросло до 725, 6.

Следующий шаг заключается в проверке условия окончания поиска. Оно может быть представлено в разных вариантах: min f_i > f _min или max f_i -min f_i < e_f, или n ³ n _задан. В первом варианте все особи должны быть лучше заданного уровня качества, во втором критерием выступает близость особей, в третьем – число поколений (итераций). Если предположить, что выбранное условие выполняется на первом поколении, то поиск на этом заканчивается. За решение принимаем лучший результат: x ₁=11, x ₂=10, f =774. Оптимальному решению соответствуют значения: x ₁=10, x ₂=5, f =800. Сравнение показывает, что по значению критерия получено неплохое приближение к оптимуму. Понятно, что продолжение итераций приведет к дальнейшему улучшению популяции и получению более близкого к оптимальному решения.▲

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