Введение.
Четкого определения понятия Генетические Алгоритмы (далее ГА) не существует, но в общих чертах можно сказать, что ГА – это алгоритмы, которые методами похожими на естественный отбор в природе, находят среди множества решений какой-то задачи оптимальное.
Автор поставил перед собой цель объяснить читателю, что ГА
- это не какие-то заоблачные дали, о которых имеют право говорить только умудренные опытом теоретики, а вполне применимый и часто очень эффективный метод решения задач, стоящих перед обычным практикующим программистом (я не имею в виду специалистов по рисованию программ мышью). Статья рассчитана на программистов, ранее ничего не слышавших о ГА, и написана для того, чтобы, прочитав её, они сразу же могли применить полученные знания на практике.
Теория.
В общих чертах работу ГА можно описать так: он создает популяцию особей, каждая из которых является решением задачи, а затем эти особи эволюционируют по принципу «выживает сильнейший», то есть остаются лишь самые оптимальные решения.
Теперь разберемся подробнее. Каждую особь описывает хромосома (это данные, описывающие определенное решение задачи, в подавляющем большинстве случаев они выражены массивом), которые располагаются в определенных позициях (локусах) хромосомы. Вообще, в большинстве случаев хромосома представляет собой битовую строку, где каждый бит является геном, но программист волен выбирать ту форму, которая удобнее для
решения его задачи. Итак вся наследственная информация или генотип, хранится в хромосомах.
Работа ГА имитирует естественную эволюцию, только сильно упрощенную.
1. Создание популяции.
На этом этапе мы случайным образом создаем начальную или стартовую популяцию особей. Конечно, особь – это решение задачи, и напрямую воспользоваться счетчиком случайных чисел для её генерации не всегда удается, поэтому алгоритм генерации случайного множества решений, в общем, зависит от условий конкретной задачи.
2. Селекция.
Здесь алгоритм выбирает особей в следующее поколение. При этом большие шансы выжить имеют более приспособленные. Без сомнения, самый распространенный метод селекция – рулетка (roulette – wheel selection), им мы и будем пользоваться. Причиной популярности этого метода является то, что он прост и при этом достаточно точно воспроизводит процесс эволюции. Заключается метод рулетки в том, что для каждой особи вычисляется функция приспособленности, и шансы у этой особи прямо пропорциональны значению этой функции. Другими словами, колесо рулетки делится на секторы особей, размер которых пропорционален приспособленности, и, запустив рулетку столько раз, сколько у нас особей, мы получаем новое поколение (в него переходят те особи, напротив секторов которых остановился шарик). Суть этого метода состоит в том, что
чем более приспособлена особь, тем больше у неё шансов на выживание. В природе все устроено точно также: у зайца, умеющего быстро бегать, шанс выжить при нападении волка, конечно больше, чем у зайца бегающего медленно, но это вовсе не значит, что быстрый заяц обязательно останется в живых – в конце концов, все решает случай.
Нельзя также не упомянуть о таком методе отбора, как элитизм – при нем самая приспособленная особь всегда переходит в следующее поколение. Элитизм обычно внедряют в другие методы отбора – сохраняют «элитную» особь вне зависимости от других условий селекции.
3. Скрещивание или кроссовер (crossover).
В этой части ГА случайным образом выбираются две особи, которые затем по определенным правилам обмениваются генами. Конечно, скрещиваются не все особи в популяции – существует вероятность скрещивания для пары особей, заданная заранее (обычно она берется порядка 60%).
Самым простым и, в то же время, по мнению автора, самым эффективным методом скрещивания является одноточечный кроссовер. Он работает так: генерируется случайное натуральное число n, меньшее длины хромосомы, и каждая родительская хромосома делится на две части, первая из которых содержит первые n генов, а вторая – оставшийся генотип. Каждая дочерняя особь состоит из первой части одной родительской особи и второй части другой, то есть родители как бы обмениваются частями.
В подавляющем большинстве случаев хромосомы после такого скрещивания продолжают оставаться одними из возможных решений задачи, но иногда «дети» кроссовера уже не будут удовлетворять условию, тогда приходиться переделывать метод скрещивания исходя из специфики решаемой задачи.
Также довольно распространен двухточечный кроссовер. При нем выбираются две точки разрыва, и родители обмениваются участком хромосом между ними. Равномерный кроссовер реализует наследование детьми каждого из генов родителей с некоторой вероятностью.
4. Мутация (mutation).
Этот этап ГА с заданной (обычно очень маленькой, порядка 1%) вероятностью случайным образом изменяет случайный ген особи (для битовых строк – инвертирует). Здесь также иногда может возникать загвоздка : в некоторых задачах полученная после изменения хромосома, возможно, перестанет быть решением. В таких случаях приходится писать такую процедуру мутации, которая всё же случайно изменяет особь, но при этом не нарушает условия задачи. Можно лишь добавить, что необходимость в подобных ухищрениях возникает довольно редко.
Теперь взглянем на ГА в целом. Его работа фактически заключается в выполнении цикла, изображенного на первом рисунке, он последовательно выполняет селекцию, скрещивание и кроссовер, генерируя все новые и новые поколения. В этом процессе выживают только самые приспособленные особи, то есть самые оптимальные решения. Причем «улучшение породы» происходит как бы само собой, программисту нужно лишь организовать цикл. Условие конца цикла может быть разным, например, если достигнута необходимая приспособленность особей, или создано определенное число поколений. После выхода из цикла остается лишь выбрать лучшую особь из последнего поколения – это и будет результат.
Одним из базовых понятий теории ГА является шима (schema). Шима – это шаблон для хромосом, от которых она отличается лишь тем, что в её локусах могут стоять не только гены, но и звездочки (*) – неопределенные гены. Если в качестве хромосом рассматривать битовые строки длины 5, то шимы могут быть, например, такими : *10*1, **110, 1***0. У каждой шимы есть два важных параметра: порядок и определенная длина. Порядок – это количество определённых генов в шиме, а определенная длина – расстояние между крайними значащими генами. Например, шима *1*00 имеет порядок три и определенную длину 4. Шимы нужны потому, что ГА обрабатывает вовсе не хромосомы, а шимы – неявно, но именно в этом кроется секрет работы ГА. Из поколения в поколение переходят только лучшие гены, которые называют строящими блоками.
Строящие блоки – это шимы, обладающими тремя признаками:
- Высокая приспособленность (вычисляется как среднее приспособленностей задаваемых шимой хромосом).
- Низкий порядок.
- Короткая определенная длина
Первый признак позволяет пройти селекцию (чем выше приспособленность, тем больше шансы выжить), второй мутацию (меньше значащих генов – меньше вероятность их изменения), третий – кроссовер (меньше определенная длина – меньше вероятность того, что точка разрыва попадает между значащими генами и уничтожают шиму).
Рассмотрим простой ГА, он выполняет селекцию пропорционально приспособленности, скрещивание одноточечным кроссовером и мутацию случайным изменением случайного гена. Для такого ГА справедливо утверждение: он экспоненциально увеличивает число строящих блоков. Доказательством этого является теорема шим. Эта теорема довольно проста, однако, несмотря на это, она даёт понятие о том, как работает ГА.
Не вдаваясь в детали скажу, что число примеров строящих блоков растет из поколения в поколение по экспоненте, в то время как число представителей «бесполезных» шим убывает по экспоненте.
Из сказанного можно сделать важный практический вывод: если увеличить
вероятность кроссовера и вероятность
мутации, то популяция быстрее сойдется к результату, но не все строящие блоки будут использованы, поэтому результат может оказаться лишь локальным экстремумом. Если же уменьшить
вероятности, то результат будет искаться медленнее, но будет более близок к точному.
