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

В.М. Курейчик

Генетические алгоритмы (ГА) есть поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики. Они реализуют «выживание сильнейших» среди рассмотренных структур, формируя и изменяя поисковый алгоритм на основе моделирования эволюции [1-7].

Основой для возникновения генетических алгоритмов считается модель биологической эволюции и методы случайного поиска [ 6, 7 ]. Один из известных специалистов в мире в области случайного поиска и стохастической оптимизации Растригин пишет [ 6 ]. Случайный поиск (СП) возник как реализация простейшей модели эволюции, когда случайные мутации моделировались случайнымишагами оптимального решения, а отбор “уходом” неудачных вариантов. Например, для прикладных оптимизационных задач

K(X) extr,

здесь K- функционая, X- искомое решение, extr – экстремум (принимает

в зависимости от условий задачи минимальное или максимальное значение).

Тогда, например, для максимизации

K(X) min X*,

где X* - наилучшее решение.

Это выражение реализуется с учетом ограничений и граничных условий. Эволюционный поиск согласно [6] – это последовательное преобразование одного конечного множества промежуточных решений в другое. Само преобразование можно назвать алгоритмом поиска или алгоритмом эволюции.

Растригин выделяет три особенности алгоритма эволюции:

– каждая новая популяция состоит только из “жизнеспособных” хромосом;

– каждая новая популяция “лучше” (в смысле целевой функции) предыдущей;

– в процессе эволюции последующая популяция зависит только от предыдущей [ 7 ].

Согласно [7] природа, реализуя эволюцию, как бы решает оптимизационную задачу на основе случайного поиска. Выделяется три основных бионических эвристики случайного поиска:

– клеточный СП,

– моделирование целесообразного поведения особей,

– моделирование передачи наследуемой биологической информации.

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

Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда [1,2]. Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей – стрингов (хромосом). Затем ГА применяет множество простых операций к начальной популяции и генерирует новые популяции. ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация. Р е п р о д у к ц и я - процесс, в котором хромосомы копируются согласно их целевой функции (ЦФ). Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР), является искусственной версией натуральной селекции, “выживания сильнейших” по Дарвину. После выполнения ОР оператор кроссинговера (ОК) может выполниться в 3 шага. На первом шаге члены нового репродуцированного множества хромосом выбираются сначала. Далее каждая пара хромосом (стрингов) пересекается по следующему правилу: целая позиция k вдоль стринга выбирается случайно между l и длиной хромосомы меньше единицы т.е. в интервале (1,L-1). Длина L хромосомы это число значащих цифр в его двоичном коде. Число k, выбранное случайно между первым и последним членами, называется точкой ОК или разделяющим знаком.

Механизм ОР и ОК. Он включает случайную генерацию чисел, копирование хромосом и частичный обмен информацией между хромосомами.

Генерация ГА начинается с репродукции. Мы выбираем хромосомы для следующей генерации, вращая колесо рулетки, такое количество раз, которое соответствует мощности начальной популяции. Величину отношения называют вероятностью выбора копий (хромосом) при ОР и обозначают

(1)

здесь f_i (x)- значение ЦФ i-той хромосомы в популяции, sum f(x)- суммарное значение ЦФ всех хромосом в популяции. Величину (1) также называют нормализованной величиной.Ожидаемое число копий i-ой хромосомы после ОР определяют

(2)

где n- число анализируемых хромосом.

Число копий хромосомы, переходящее в следующее положение, иногда определяют на основе выражения

. (3)

Далее, согласно схеме классического ПГА, выполняется оператор мутации. Считают, что мутация - вторичный механизм в ГА.

Понятие "схема" (схемата), согласно Холланду, есть шаблон, описывающий подмножество стрингов, имеющих подобные значения в некоторых позициях стринга [8]. Для этого вводится новый алфавит {0,1,*}, где * - означает: не имеет значения 1 или 0. Для вычисления числа схем или их границы в популяции требуются точные значения о каждом стринге в популяции.

Для количественной оценки схем введены 2 характеристики [1,2]: порядок схемы - О(H); определенная длина схемы - L(H). Порядок схемы - число закрепленных позиций (в двоичном алфавите - число единиц и нулей), представленных в шаблоне.

Предположим, что заданы шаг (временной) t, m примеров частичных схем H, содержащихся в популяции A(t). Все это записывают как m=m(H,t) - возможное различное число различных схем H в различное время t.

В течение репродукции стринги копируются согласно их ЦФ или более точно: стринг A(i) получает выбор с вероятностью, определяемой выражением

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать