Лабораторная работа №6
«Генетические алгоритмы».
Цель работы:Получить практические навыки в создании и использовании генетических алгоритмов.
Теоретические сведения:
Подобно нейронным сетям, генетические алгоритмы основываются на свойствах биологического прототипа. В рамках этого подхода обучение рассматривается как конкуренция внутри популяции между эволюционирующими кандидатами на роль решения задачи. Каждое решение оценивается согласно критерию отбора. По результатам оценки определяется, будет ли этот экземпляр участвовать в следующем поколении решений. Затем с помощью операций, аналогичных трансформации биологического воспроизводства, создается новое поколение решений-кандидатов.
Пусть Р(t) — поколение решений-кандидатов 
в момент времени t P(t) = { 
, 
,…, 
}.
В общем виде генетический алгоритм можно представить следующим образом.
procedure genetic algorithm;
begin
установить t:=0;
инициализировать популяцию P(t);
while не достигнуто условие завершения
begin
вычислить значение критерия качества для каждого члена
популяции P(t);
на основе значений критерия качества выбрать из Р(t) нужное
число членов;
создать следующее поколение с помощью генетических операций;
заменить с учётом значений критерия качества особей
популяции P(t) их потомками;
установить время t: = t+1
end.
end.
Этот алгоритм отражает основные принципы генетического обучения. Его конкретные реализации могут отличаться в зависимости от задачи. Какое процентное соотношение особей выживает в следующем поколении? Сколько особей участвуют в скрещивании? Как часто и к кому применяются генетические операторы? Процедуру "заменить особей популяции P(t)" можно реализовать простейшим образом, заменив фиксированное процентное соотношение слабейших кандидатов. Более сложный подход состоит в упорядочении популяции согласно критерию качества и удалении особей с учетом вероятности, обратно пропорциональной значению критерия качества. Такую меру можно использовать для выбора исключаемых особей. И хотя для наилучших особей популяции вероятность их исключения очень низка, все же существует шанс удаления самых "сильных" особей популяции. Преимущество этой схемы состоит в возможности сохранения некоторых "слабых" особей, которые в дальнейшем могут внести свой вклад в получение более точного решения.Такой алгоритм замены известен под многими именами, в том числе как метод Монте-Карло (Monte-Carlo), правило рулетки (roulette wheel) или алгоритм отбора пропорционально критерию качества (fitness proportionate selection).
Решение задачи будем описывать с помощью обычных битовых строк. Предположим, что необходимо с помощью генетического алгоритма научиться классифицировать строки, состоящие из единиц и нулей. В такой задаче популяцию битовых строк можно описывать с помощью шаблона, состоящего из 1, 0 и символов #, которые могут соответствовать как 1, так и 0. Следовательно, шаблон 1##00##1 представляет всё восьмибитовые строки, начинающиеся, заканчивающиеся 1 и содержащие в середине строки два нуля подряд.
При работе генетического алгоритма популяция кандидатов Р(0) некоторым образом инициализируется. Обычно инициализация выполняется с помощью датчика случайных чисел. Для оценки решений-кандидатов вводится критерий качества f( ), определяющий меру соответствия каждого кандидата в момент времени t. При классификации мерой соответствия кандидатов является процентное соотношение правильных ответов на множестве обучающих примеров. При таком критерии качества каждому решению-кандидату соответствует значение
f ( ) / m (Р, t) ,
где m (Р, t) — среднее значение критерия качества для всех членов популяции. Обычно мера соответствия изменяется во времени, поэтому критерий качества может быть функцией от стадии решения всей проблемы или f( ).
После анализа каждого кандидата выбираются пары для рекомбинации. При этом используются генетические операторы, в результате выполнения которых новые решения получаются путем комбинации свойств родителей. Как и в естественном процессе эволюции, степень участия в репродуктивном процессе для каждого кандидата определяется значением критерия качества: кандидаты с более высоким значением критерия качества участвуют в процессе воспроизводства с более высокой вероятностью. Как уже отмечалось, выбор осуществляется на основе вероятностных законов, когда слабые члены популяции имеют меньшую вероятность воспроизводства, однако такая возможность не исключается. Выживание некоторых слабейших особей имеет важное значение для развития популяции, поскольку они могут содержать некоторые важные компоненты решения, например, фрагмент битовой строки, которые могут извлекаться при воспроизводстве.