Работа генетического алгоритмаВообразим себе искусственный мир, населенный множеством существ (особей), причем каждая особь - это некоторое решение задачи. Будем считать особь более приспособленной, чем лучше соответствующее решение (чем больше значение целевой функции оно дает). Тогда задача максимизации целевой функции сводится к поиску более приспособленной особи. Конечно, мы не можем поселить в наш виртуальный мир все особи сразу, так как их очень много. Вместо этого будем рассматривать множество поколений, которые сменяют друг друга. Теперь, если мы сумеем задействовать естественный отбор и генетическое наследование, тогда полученная среда будет подчиняться законам эволюции. Целью этой искусственной эволюции будет создание наилучших решений. Очевидно, эволюция - бесконечный процесс, в ходе которого приспособленность особей постепенно повышается. Принудительно остановив этот процесс через длительное время после его начала и выбрав наиболее приспособленную особь в текущем поколении, получим не абсолютно точный, но близкий к оптимальному ответ. Такова идея генетического алгоритма. Перейдем теперь к точным определениям и опишем работу генетического алгоритма детальней. Для того чтобы говорить о генетическом наследовании, нужно наделить наши особи хромосомами. В генетическом алгоритме хромосома - это некоторый числовой вектор, который отвечает подбираемому параметру, а набор хромосом данной особи определяет решение задачи. Какие именно векторы следует рассматривать в конкретной задаче, решает сам пользователь. Каждая из позиций вектора хромосомы называется геном. Простой генетический алгоритм случайным образом генерирует начальную популяцию. Работа генетического алгоритма представляет итерационный процесс, который продолжается до тех пор, пока не выполнится заданное число поколений или любой другой критерий остановки. В каждом поколении генетического алгоритма реализуется отбор пропорционально приспособленности, одноточечный кроссинговер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(и) равную отношению ее приспособленности к суммарной приспособленности популяции:
Потом происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, соответственно величине Ps(і). При таком отборе члены популяции с высокой приспособленностью с большей вероятностью будут выбираться чаще, чем особи с низкой приспособленностью. После отбора, n избранных особей случайным образом разбиваются на n/2 пары. Для каждой пары с вероятностью Ps может применяться кроссинговер. Соответственно, с вероятностью 1-Ps кроссинговер не происходит и неизмененные особи переходят на стадию мутации. Если кроссинговер происходит, полученные потомки заменяют родителей и переходят к мутации. Определим теперь понятия, отвечающие мутации и кроссинговеру в генетическом алгоритме. Мутация - это преобразование хромосомы, которое случайно изменяет одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций - случайное изменение только одного из генов хромосомы. Кроссинговер (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) - это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. Одноточечный кросинговер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва - участок между соседними битами в строке.) Обе родительские структуры в этой точке разрываются на два сегмента. Потом, соответствующие сегменты разных родителей склеиваются и выходят два генотипа потомков. Например, предположим, один родитель состоит из 10 нулей, а другой - с 10 единиц. Пусть из 9 возможных точек разрыва избрана точка 3. Родители и их потомки показаны ниже. Кроссинговер Родитель 1 0000000000 000~0000000--> 111~0000000 1110000000 Потомок 1 Родитель 2 1111111111 111~1111111 --> 000~1111111 0001111111 Потомок 2 После того как заканчивается стадия кроссинговера, выполняются операторы мутации. В строке, к которой применяется мутация, каждый бит с вероятностью Pm изменяется на противоположный. Популяция, полученная после мутации записывает поверх старой и цикл одного поколения завершается. Следующие поколения обрабатываются подобным образом: отбор, кроссинговер и мутация. В настоящее время исследователи генов предлагают другие операторы отбора, кроссинговера и мутации. Ниже приведены наиболее распространенные. Элитные методы отбора гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссинговера и мутации. Элитизм может быть введен практически в любой стандартный метод отбора. Двухточечный кроссинговер и равномерный кроссинговер - достойные альтернативы одноточечному оператору. В двухточечном кроссинговере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, находящемся между этими точками. В равномерном кроссинговере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью, в противном случае этот бит передается второму потомку. И наоборот. Блок-схема генетического алгоритма изображена на рис. 2. Сначала генерируется начальная популяция особей (индивидуумов), то есть некоторый набор решений задачи. Как правило, это делается случайным образом. Потом моделируется размножение внутри популяции. Для этого, случайно отбирается несколько паров индивидуумов, происходит скрещивание между хромосомами в каждой паре, а полученные новые хромосомы переходят в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора - чем приспособленней индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет брать участие в скрещивании. Теперь моделируются мутации - в нескольких случайно избранных особях нового поколения изменяются некоторые гены. Старая популяция частично или целиком уничтожается и переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т.д.
Рис. 2. Блок-схема генетического алгоритма В каждом следующем поколении наблюдается возникновение новых решений задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору, число приемлемых решений будет возрастать. Заметим, что в природе не бывает абсолютных гарантий, и приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомков. Имитируя эволюцию на компьютере, можно избежать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения - такая методика называется "стратегией элитизма".
|
