Материал взят с: http://cgm.graphicon.ru/content/view/35/66/

Автор: Антон Конушин. Научно-образовательный сетевой журнал, посвященный компьютерной графике, машинному зрению и обработке изображений.

"Введение в генетические алгоритмы."

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

   У Матушки-Природы заранее припасено по примеру почти на каждую из идей, когда-либо пришедших в голову человека. Это же мысль можно выразить и по другому: почти все, придуманное человеком уже когда-то было изобретено природой. У Природы есть и свой метод создания лучших организмов. Дарвин назвал его Эволюцией вследствие Естественного отбора. Эволюция подразумевает под собой последовательное развитие организмов - непрерывную последовательность родителей и их детей, когда дети многое наследуют от своих родителей, но кое в чем от них отличаются. Естественный отбор - от непрерывное сражение за жизнь между всеми. "Выживает сильнейший" - вот жизненное кредо Природы, если награждать титулом "сильный" самого подходящего, самого приспособленного для жизни.

   Если подходить к описанию эволюции более формально, то вначале необходимо отметить что объектом развития (т.е. эволюции) являются не сами организмы, а виды в целом. Вид - это совокупность организмов, сходных по строению и другим признакам. Пользуясь терминологией объектно-ориентированного программирования, вид - это класс, а принадлежащие виду индивиды - объекты это класса. Совокупность индивидов одного вида назовем популяцией. Чтобы эволюция вообще была возможна, организмы должны отвечать 4 важнейшим свойствам:

1. Каждый индивид в популяции способен к размножению

2. Отличия индивидов друг от друга влияют на вероятность их выживания

3. Каждый потомок наследует черты своего родителя (подобное происходит от подобного)

4. Ресурсы для поддержания жизнедеятельности и размножения ограничены, что порождает конкуренцию и борьбу за них

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

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

    В Генетическом Алгоритме (ГА) каждый индивид кодируется сходным с ДНК методом - в виде строки из символов одного типа. Длина строки (ДНК) постоянна. Популяция из индивидов подвергается процессу эволюции с интенсивным использованием перекреста и мутаций.

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

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

    Процесс работы ЭС и ЭП состоит из следующих фаз:

•    Создание популяции объектов, со случайным выбором их параметров

•    Порождение каждым объектом новой популяции (клонирование). Каждый объект в новой популяции подвергается мутации

•    Все объекты оцениваются, и вся популяции подвергается процедуре естественного отбора, после чего осуществляется переход на 2-ю фазу

    Между ЭС и ЭП существуют несколько отличий:

•    ЭП работает на уровне видов, а не на уровне индивидов, поэтому скрещивание между объектами невозможно

•    В ЭП процедура отбора детерминирована - отбрасываются самые плохие объекты, в ЭС используется турнирный метод

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

Рис.1 Ген

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

   В качестве оператора мутации чаще всего применяется так называемая побитовая мутация (bit-flip или uniform). При применении такого оператора мутации каждый бит в гене меняет свое значение на противоположенное с некоторой заданной вероятностью. Т.к. и старшие и младшие биты двоичного представления чисел меняются с одинаковой вероятностью, то наряду с небольшими изменениями в значениях могу случаться и очень значительные. Поэтому наряду с побитовой мутацией часто применяется Гауссова мутация. Оператор гауссовой мутации работает только с генами из вещественных переменных. К значению каждой переменной в гене прибавляется некоторое случайное число, полученное с помощью нормального распределения с заданными параметрами. Параметры мутации могут задаваться как таким образом, чтобы мутация была незначительным изменением гена, так и для совершения больших скачков по пространству поиска. Приводятся доводы в пользу обоих вариантов, поэтому обычно для каждой задачи и тип оператора мутации и его конкретные параметры задаются отдельно.

   Оператор перекреста обеспечивает обмен отдельными сегментами гена в процессе размножения. Чаще всего применяется одноточечный перекрест. Случайным образом выбирается точка на гене, по которой геном "разрезается". Ген - потомок получает сегмент гена до точки разреза от одного родителя, а после точки разреза - от другого родителя. Аналогично вводятся двухточечный перекрест по двум точкам разреза и т.д.

Рис.2 Оператор перекреста

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

    А в качестве критерия завершения обычно задается ограничение по количеству шагов эволюции.