Популярно про генетические алгоритмы:
Источник:http://www.victoria.lviv.ua/html/oio/html/theme10_rus.htm
История появления эволюционных алгоритмов
Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая обьясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение и отбор.
На мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 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), зависящей от этих параметров. Например, если нужно максимизировать целевую функцию "доход компании", тогда управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т.д. Эти параметры связаны между собой - в частности, при уменьшении числа сотрудников скорее всего упадет и объем производства.
Генетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. Известно два основных пути решения таких задач - метод перебора или градиентный метод. Рассмотрим классическую задачу коммивояжера. Суть задачи состоит в нахождении кратчайшего пути прохождения всех городов.
Переборный метод проще. Для поиска оптимального решения (максимум целевой функции) нужно последовательно вычислить значения функции во всех точках. Недостатком является большое количество вычислений.
Другой способ - градиентный спуск. Выбираем случайные значения параметров, далее значения постепенно изменяются, достигая наибольшей скорости роста целевой функции. Алгоритм может остановиться, достигнув локального максимума. Градиентные методы быстрые, но не гарантируют оптимального решения (поскольку целевая функция имеет несколько максимумов).
Генетический алгоритм представляет собой комбинацию переборного и градиентного методов. Механизмы кроссинговера (скрещивания) и мутации реализуют переборную часть, а отбор лучших решений - градиентный спуск.
То есть, если на некотором множестве задана сложная функция от нескольких переменных, тогда генетический алгоритм является программой, которая за допустимое время находит точку, где значение функции находится довольно близко к максимально возможному значению. Выбирая приемлемое время расчета, получаем лучшие решения, которые можно получить за это время.