Генетические алгоритмы и моделирование биологической эволюции

 

Основные понятия, принципы и предпосылки генетических алгоритмов.

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

 

Рисунок 21 – Модель эволюции в природе

 

Эволюционная теория утверждает, что каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде.Можно сказать, что эволюция - это процесс оптимизации всех живых организмов. Основной механизм эволюции - это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает. Схема генетического алгоритма приведена на рисунке справа. Вначале генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом. Затем необходимо смоделировать размножение внутри этой популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора — чем приспособленнее индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Теперь моделируются мутации — в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и мы переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше.Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.В каждом следующем поколении мы будем наблюдать возникновение совершенно новых решений нашей задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число хороших решений будет возрастать. Мутация — это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций — случайное изменение только одного из генов хромосомы. Кроссинговер (кроссовер или скрещивание) — это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. Фенотип - совокупность всех внутренних и внешних признаков и свойств особи, организма. Генотип - совокупность всех генов, локализованных в хромосомах данного организма. В более широком смысле генотип — совокупность всех наследственных факторов организма — как ядерных (геном), так и неядерных, внехромосомных (т. е. цитоплазматических и пластидных наследственных факторов). Термин предложен датским биологом В. Иогансеном (1909).

Генетические алгоритмы (ГА) являются адаптивными методами функциональной оптимизации, основанные на компьютерном имитационном моделировании биологической эволюции. Основные принципы ГА были сформулированы Голландом (1975), и хорошо описаны во многих работах и на ряде сайтов в Интернете.

В настоящее время существует ряд теорий биологической эволюции (Ж.-Б.Ламарка, П.Тейяра де Шардена, К.Э.Бэра, Л.С.Берга, А.А.Любищева, С.В.Мейена и др.), однако, ни одна из них не считается общепризнанной. Наиболее известной и популярной, конечно, является теория Чарльза Дарвина, которую он представил в работе "Происхождение Видов" в 1859 году.

Эта теория, как и другие, содержит довольно много нерешенных проблем, глубокое рассмотрение которых далеко выходит за рамки данной работы. Здесь мы можем отметить лишь некоторые наиболее известные из них. Как это ни парадоксально, но несмотря на то, что сам Чарльз Дарвин назвал свою работу "Происхождение Видов" но как раз именно происхождения видов она и не объясняет. Дело в том, что возникновение нового вида "по алгоритму Дарвина" является крайне маловероятным событием, т.к. для этого требуется случайное возникновение в одной точке пространства и времени сразу не менее 100 особей нового вида, т.е. особей, которые могли бы иметь плодовитое потомство. При меньшем количестве особей вид обречен на вымирание. Поэтому процесс видообразования на основе случайных мутаций должен был бы занять несуразно много времени (по некоторым оценкам даже в намного раз больше, чем время существования Вселенной). Кроме того, "алгоритм Дарвина" не объясняет явной системности в многообразии возникающих форм, типа закона гомологичных рядов Н.И. Вавилова. Поэтому Л.С. Берг предложил очень интересную концепцию номогенеза - закономерной или направленной эволюции живого. В этой концепции предполагается, что филогенез имеет определенное направление и смена форма является не случайной, а задается некоторым вектором, природа которого не ясна. Идеи номогенеза глубоко разработал и развил А.А. Любищев, высказавший гипотезу о математических закономерностях, которые определяют многообразие живых форм. Кроме того, Дарвин не смог показать механизм наследования, при котором поддерживается и закрепляется изменчивость. Это было на пятьдесят лет до того, как генетическая теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и молодой генетикой.

Тем ни менее и не смотря на свои недостатки, именно теория Дарвина традиционно и моделируется в ГА, хотя, конечно, это не исключает возможности моделирования и других теорий эволюции в ГА. Более того, возможно именно такое компьютерное моделирование и сравнение его результатов с картиной реальной эволюции жизни на Земле может быть и сыграет положительную роль в дальнейшей разработке наиболее адекватной теории биологической эволюции.

Теория Дарвина применима не к отдельным особям, а к популяциям - большому количеству особей одного вида, т.е. способных давать плодовитое потомство, находящейся в определенной статичной или динамичной внешней среде.

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

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

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

Таким образом, можно сделать фундаментальный вывод, имеющий даже мировоззренческое звучание, о том, что естественный отбор представляет собой процесс генерации и накопления информации о выживании и продолжении рода в ряде поколений популяции, как системы.

Это накопление информации происходит на различных уровнях иерархии популяции, как системы, включающей:

- элементы системы: отдельные особи;

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

- цель системы: сохранение и развитие популяции, реализуется через цели особей: индивидуальное выживание и продолжение рода.

Фенотип соответствует генотипу и представляет собой его внешнее проявление в признаках особи. Особь взаимодействует с окружающей средой и другими особями в соответствии со своим фенотипом. В случае, если это взаимодействие удачно, то особь передает генетическую информацию, определяющую фенотип, последующим поколениям.

Если кроссовер происходит, то потомки получают по половине случайным образом определенных признаков от каждого из родителей. Численность потомства пропорциональна суммарной приспособленности родителей. В некоторых вариантах ГА потомки после своего появления заменяют собой родителей и переходят к мутации.

Если кроссовер не происходит, то исходные особи - несостоявшиеся родители, переходят на стадию мутации.

Если ГА сошелся, то это означает, что решение найдено, т.е. получено поколение, идеально приспособленное к условиям данной фиксированной среды обитания. Иначе - переход на шаг 4 - начало формирования нового поколения.

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

Конечно, реальные генетические алгоритмы, на которых проводятся научные исследования, чаще всего мало похожи на приведенный пример.

Исследователи экспериментируют с различными параметрами генетических алгоритмов, например: способами отбора особей для скрещивания; критериями приспособленности и жесткостью влияния факторов среды; способами выбора признаков, передающихся от родителей потомкам (рецессивные и не рецессивные гены и т.д.); интенсивностью, видом случайного распределения и направленностью мутаций; различными подходами к воспроизводству и отбору.

Поэтому под термином "генетические алгоритмы" по сути дела надо понимать не одну модель, а довольно широкий класс алгоритмов, подчас мало похожих друг на друга.

В настоящее время рассматривается много различных операторов отбора, кроссовера и мутации: турнирный отбор (1981; 1991), реализует n турниров, чтобы выбрать n особей, при этом каждый турнир построен на выборке К элементов из популяции, и выбора лучшей особи среди них (наиболее распространен турнирный отбор с К=2); элитный отбор (1975) гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности (наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссовера и мутации); двухточечный кроссовер (1970; 1989) и равномерный кроссовер (1989) отличаются способами наследования потомками признаков родителей.

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

Достоинства и недостатки генетических алгоритмов.

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

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

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

Примеры применения генетических алгоритмов

В 1994 году Эндрю Кин из университета Саутгемптона использовал генетический алгоритм в дизайне космических кораблей. За основу была взята модель опоры космической станции, спроектированной в NASA из которой после смены 15 поколений, включавших 4.500 вариантов дизайна, получилась модель, превосходящая по тестам тот вариант, что разработали люди.

Аналогичный генетический алгоритм был использован NASA при разработке антенны для спутника.

Джон Коза из Стэнфорда разработал технологию генетического программирования, в которой результатом эволюции становятся не отдельные числовые параметры "особей", а целые имитационные программы, которые являются виртуальными аналогами реальных устройств. Эта технология позволила компании Genetic Programming повторить 15 человеческих изобретений, 6 из которых были запатентованы после 2000 года, то есть представляют собой самые передовые достижения, а один из контроллеров, "выведенных" в GР, даже превосходит аналогичную человеческую разработку.

Сейчас плоды электронной эволюции можно найти в самых разных сферах: от двигателя самолета Боинг 777 до новых антибиотиков.

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

1. Естественный отбор, моделируемый ГА, переносится из виртуального мира в реальный, например, проводятся эксперименты по реальным битвам роботов на выживание.

2. Интеллектуальные системы, основанные на ГА, конструируют роботов, которые в принципе могут быть изготовлены на автоматизированных заводах без участия человека.

Пример воплощения ГА в реальной битве роботов на выживание: в 2002 году в британском центре Magna открылся павильон Live Robots, где боролись за выживание 12 роботов двух видов: "гелиофаги", способные добывать электроэнергию с использованием солнечных батарей; "хищники", которые могли получать электроэнергию только от гелиофагов. Выжившие роботы загружали свои "гены" в погибших и, таким образом, образовывали новые поколения. Те хищники, которые забирали всю энергию у гелиофагов, теряли источник питания и погибали, не передавая свою тактику потомкам, поступавшие же "более разумно" продолжили свой род. В результате возникла равновесная сбалансированная искусственная экосистема с двумя популяциями.

Пример конструирования роботов роботами: в Brandeis University была создана программа Golem, которая сама конструировала роботов. В программу была база деталей, а также механизм мутаций и функция пригодности для "отсеивания" неудачников - тех, кто не научился двигаться. После 600 поколений за несколько дней программа получила модели трех ползающих роботов. Показательно, что роботы оказались симметричными, хотя симметрия никак не была явно прописана в правилах эволюции и исходных данных. Это означает, что она появилась в ходе моделирования машинной эволюции как полезная черта, позволяющая двигаться прямолинейно.