Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая обьясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение и отбор.
На мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в Природе.
Поэтому не удивительно, что ученые, занимающиеся компьютерными исследованиями, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в естественных системах, была очень привлекательной. Эта надежда является причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.
История эволюционных вычислений началась с разработки ряда разных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голанда (Holland), разработанные в начале 60-х лет. После выхода книги, ставшей классикой - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975), направление получило общее признание.
Главная трудность при построении вычислительных систем, основанных на принципах естественного отбора и применении этих систем в прикладных задачах, состоит в том, что естественные системы довольно хаотичные, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, что мы сами и формулируем, и акцентируем внимание на максимально быстром выполнении при минимальных затратах. Естественные системы не имеют таких целей или ограничений, во всяком случае, нам они не известны. Выживание в природе не направлено к фиксированной цели, вместо этого эволюция делает шаг вперед в любом доступном направлении. Возможно это большое обобщение, но усилия, направленные на моделирование эволюции по аналогии с естественными системами можно разбить на две больших категории:
Конечно, на практике нельзя разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат разные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).
Конечно, эволюция биологических систем не единственный "источник вдохновения" творцов новых методов, которые моделируют естественные процессы.
Как известно, эволюционная теория утверждает, что жизнь на нашей планете возникла вначале лишь в простейших формах - в виде одноклеточных организмов. Эти формы постепенно усложнялись, приспосабливаясь к окружающей среде, порождая новые виды, и только через много миллионов лет появились первые животные и люди. Каждый биологический вид с течением времени совершенствует свои качества так, чтобы эффективней справляться с важнейшими задачами выживания, самозащиты, размножения и т.д. Таким путем возникла защитная окраска у многих рыб и насекомых, панцирь у черепахи, яд у скорпиона и многие другие полезные приспособления.
С помощью эволюции природа постоянно оптимизирует все живое, находя неординарные решение. Неясно, за счет чего происходит этот прогресс, однако ему можно дать научное пояснение, базируясь всего на двух биологических механизмах - естественного отбора и генетического наследования.
Ключевую роль в эволюционной теории играет естественный отбор. Его суть состоит в том, что наиболее приспособленные особи лучше выживают и приносят больше потомков, чем менее приспособленные. Заметим, что сам по себе естественный отбор еще не обеспечивает развитие биологического вида. Поэтому очень важно понять, каким образом происходит наследование, то есть как свойства потомка зависят от свойств родителей.
Основной закон наследования интуитивно понятен каждому - он состоит в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Чтобы понять, на чем основано это сходство, нужно немного углубиться в построение естественной клетки - в мир генов и хромосом.
Почти в каждой клетке любой особи есть набор хромосом, несущих информацию про эту особь. Основная часть хромосомы - нить ДНК, определяющая, какие химические реакции будут происходить в данной клетке, как она будет развиваться и какие функции выполнять.
Ген - это отрезок цепи ДНК, ответственный за определенное свойство особи, например за цвет глаз, тип волос, цвет кожи и т.д. Вся совокупность генетических признаков человека кодируется с помощью приблизительно 60 тыс. генов, длина которых составляет более 90 млн. нуклеотидов.
Различают два вида клеток: половые (такие, как сперматозоид и яйцеклетка) и соматические. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом - на самом деле 23 пары, причем в каждой паре одна из хромосом получена от отца, а вторая - от матери. Парные хромосомы отвечают за одинаковые признаки - например, родительская хромосома может содержать ген черного цвета глаз, а парная ей материнская - ген голубого цвета. Существуют определенные законы, управляющие участием тех или иных генов в развитии особи. В частности, в нашем примере потомок будет черноглазым, поскольку ген голубых глаз является "слабым" и подавляется геном любого другого цвета.
В половых клетках хромосом только 23, и они непарные. При оплодотворении происходит слияние мужской и женской половых клеток и получается клетка зародыша, содержащая 46 хромосом. Какие свойства потомок получит от отца, а какие - от матери? Это зависит от того, какие именно половые клетки принимали участие в оплодотворении. Процесс выработки половых клеток (так называемый мейоз) в организме подвергается случаяйностям, благодаря которым потомки во многом отличаются от своих родителей. При мейозе, происходит следующее: парные хромосомы соматической клетки сближаются вплотную, потом их нити ДНК разрываются в нескольких случайных местах и хромосомы обмениваются своими частями (рис. 1).
Рис.1. Условная схема кроссинговера
Этот процесс обеспечивает появление новых вариантов хромосом и называется "кроссинговер". Каждая из вновь появившихся хромосом окажется затем внутри одной из половых клеток, и ее генетическая информация может реализоваться в потомках данной особи.
Второй важный фактор, влияющий на наследственность, - это мутации, которые выражаются в изменении некоторых участков ДНК. Мутации также случайны и могут быть вызваны различными внешними факторами, такими, как радиоактивное облучение. Если мутация произошла в половой клетке, то измененный ген может передаться потомку и проявиться в виде наследственной болезни либо в других новых свойствах потомка. Считается, что именно мутации являются причиной появления новых биологических видов, а кроссинговер определяет уже изменчивость внутри вида (например, генетические различия между людьми).
Как уже были отмечено выше, эволюция - это процесс постоянной оптимизации биологических видов. Естественный отбор гарантирует, что наиболее приспособленные особи дадут большое количество потомков, а благодаря генетическому наследованию, часть потомков не только сохранит высокую приспособленность родителей, но будет иметь и новые свойства. Если эти новые свойства оказываются полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособленности биологического вида в целом. Зная, как решается задача оптимизации видов в природе, применим похожий метод для решения разных реальных задач.
Задачи оптимизации - наиболее распространенный и важный для практики класс задач. Их приходится решать любому из нас или в быту, распределяя свое время между разными делами, или на работе, добиваясь максимальной скорости работы программы или максимальной прибыльности компании - в зависимости от должности. Среди этих задач есть решаемые простым путем, но есть и такие, точное решение которых найти практически невозможно.
Введем обозначения и приведем несколько классических примеров. Как правило, в задаче оптимизации мы можем руководить несколькими параметрами (обозначим их значения через x1, x2, ..., xn, целью является максимизация (или минимизация) некоторой целевой функции, f(x1, x2, ..., xn), зависящей от этих параметров. Например, если нужно максимизировать целевую функцию "доход компании", тогда управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т.д. Эти параметры связаны между собой - в частности, при уменьшении числа сотрудников скорее всего упадет и объем производства.
Генетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. Известно два основных пути решения таких задач - метод перебора или градиентный метод. Рассмотрим классическую задачу коммивояжера. Суть задачи состоит в нахождении кратчайшего пути прохождения всех городов.
Переборный метод проще. Для поиска оптимального решения (максимум целевой функции) нужно последовательно вычислить значения функции во всех точках. Недостатком является большое количество вычислений.
Другой способ - градиентный спуск. Выбираем случайные значения параметров, далее значения постепенно изменяются, достигая наибольшей скорости роста целевой функции. Алгоритм может остановиться, достигнув локального максимума. Градиентные методы быстрые, но не гарантируют оптимального решения (поскольку целевая функция имеет несколько максимумов).
Генетический алгоритм представляет собой комбинацию переборного и градиентного методов. Механизмы кроссинговера (скрещивания) и мутации реализуют переборную часть, а отбор лучших решений - градиентный спуск.
То есть, если на некотором множестве задана сложная функция от нескольких переменных, тогда генетический алгоритм является программой, которая за допустимое время находит точку, где значение функции находится довольно близко к максимально возможному значению. Выбирая приемлемое время расчета, получаем лучшие решения, которые можно получить за это время.
Вообразим себе искусственный мир, населенный множеством существ (особей), причем каждая особь - это некоторое решение задачи. Будем считать особь более приспособленной, чем лучше соответствующее решение (чем больше значение целевой функции оно дает). Тогда задача максимизации целевой функции сводится к поиску более приспособленной особи. Конечно, мы не можем поселить в наш виртуальный мир все особи сразу, так как их очень много. Вместо этого будем рассматривать множество поколений, которые сменяют друг друга. Теперь, если мы сумеем задействовать естественный отбор и генетическое наследование, тогда полученная среда будет подчиняться законам эволюции. Целью этой искусственной эволюции будет создание наилучших решений. Очевидно, эволюция - бесконечный процесс, в ходе которого приспособленность особей постепенно повышается. Принудительно остановив этот процесс через длительное время после его начала и выбрав наиболее приспособленную особь в текущем поколении, получим не абсолютно точный, но близкий к оптимальному ответ. Такова идея генетического алгоритма. Перейдем теперь к точным определениям и опишем работу генетического алгоритма детальней.
Для того чтобы говорить о генетическом наследовании, нужно наделить наши особи хромосомами. В генетическом алгоритме хромосома - это некоторый числовой вектор, который отвечает подбираемому параметру, а набор хромосом данной особи определяет решение задачи. Какие именно векторы следует рассматривать в конкретной задаче, решает сам пользователь. Каждая из позиций вектора хромосомы называется геном.
Простой генетический алгоритм случайным образом генерирует начальную популяцию. Работа генетического алгоритма представляет итерационный процесс, который продолжается до тех пор, пока не выполнится заданное число поколений или любой другой критерий остановки. В каждом поколении генетического алгоритма реализуется отбор пропорционально приспособленности, одноточечный кроссинговер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность 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. Блок-схема генетического алгоритма
В каждом следующем поколении наблюдается возникновение новых решений задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору, число приемлемых решений будет возрастать. Заметим, что в природе не бывает абсолютных гарантий, и приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомков. Имитируя эволюцию на компьютере, можно избежать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения - такая методика называется "стратегией элитизма".
Генетические алгоритмы в разных формах применяются к решению многих научных и технических проблем. Генетические алгоритмы используются при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они используются при проектировании нейронных сетей или управлении роботами. Они также применяются при моделировании развития в разных предметных областях, включая биологические (экология, иммунология и популярная генетика) и социальные (такие как экономика и политические системы) системы.
Тем не менее, возможно популярное применение генетических алгоритмов - оптимизация многопараметрических функций. Большинство реальных задач могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от определенных входных параметров. В некоторых случаях, нужно найти те значения параметров, при которых достигается точное значение функции. В других случаях, точный оптимум не нужен - решением может считаться любое значение, лучшее за определенную заданную величину. В этом случае, генетические алгоритмы - приемлемый метод для поиска "приемлемых" значений. Сила генетического алгоритма состоит в его способности манипулировать одновременно многими параметрами, которая используется в сотнях прикладных программ, включая проектирование самолетов, настраивании параметров алгоритмов и поиске стойких состояний систем нелинейных дифференциальных уравнений.
Генетические алгоритмы являются эффективной процедурой поиска, которая конкурирует с другими процедурами. Эффективность генетических алгоритмов сильно зависит от таких деталей, как метод кодирования решений, операторов, настраивания параметров, отдельных критериев успеха.