Генетические алгоритмы

История

Группа исследований эволюционных алгоритмов (ТПУ)

Дискуссионная группа по эволюционным вычислениям

Написать письмо

Генетические алгоритмы являются частью более общей группы методов, называемой эволюционными вычислениями, которые объединяют различные варианты использования эволюционных принципов для достижения поставленной цели. Подоплекой возникновения этих методов стали несколько открытий в биологии. Сначала Чарльз Дарвин опубликовал в 1859г. свою знаменитую работу "Происхождение видов", где были провозглашены основные принципы эволюционной теории: наследственность, изменчивость и естественный отбор. Тем самым было показано, что использование данных механизмов способно привести к определенному результату под влиянием окружающей среды. Однако долгое время оставался открытым вопрос о том, как же все-таки передается генетическая информация от родителей потомкам. В 1944 году Эйвери, Маклеод и Маккарти опубликовали результаты своих исследований, доказывавших, что за наследственные процессы ответственна "кислота дезоксирибозного типа". Однако о том, как работает ДНК, весь мир узнал ещё позднее - 27 апреля 1953 года в номере журнала "Nature" вышла статья Уотсона и Крика, впервые предложивших модель двухцепочечной спирали ДНК. Такми образом стали известны все необходимые компоненты для реализации модели эволюции на компьютере.

Здесь стоит немного остановиться. Дело в том, что, наверное, единственная цель существования природного комплекса - выживание в постоянно изменяющихся условиях окружающей среды. И хотя смысл существования - извечный вопрос для философов и других любителей мудрости, но если немного абстрагироваться от глобальных замыслов вроде постижения сущности Вселенной, достижения трансцендентности, слияния с космическим Я и поиска ответа на вопрос "Что было раньше, курица или яйцо?", наконец, то можно сделать предположение, что смысл жизни - в самой жизни. Что-то меня понесло, право слово ;-)). В общем, я все это к тому, что во всех искусственных системах есть такое понятие, как назначение, иначе говоря, смысл, цель. Эти параметры есть и у эволюционных алгоритмов, за исключением, может быть, систем искусственной жизни (Artificial Life (A-Life) Systems).

Так вот, о птичках. Первая публикация, которую можно хоть как-то отнести к генетическим алгоритмам появилась в 1957г, автором был Баричелли Н.А. (Barricelli N.A.), и называлась она "Symbiogenetic evolution processes realised by artificial methods". В 1962 году появилась ещё одна его работа "Numerical testing of evolution theories". Примерно в то же время ещё один исследователь Фрейзер А.С. (Fraser A.S.) также опубликовал две статьи: "Simulation of genetic systems by automatic digital computers: S-linkage, dominance, and epistasis" (1960) и "Simulation of genetic systems" (1962). Несмотря на то, что работы обоих авторов были направлены прежде всего на понимание природного феномена наследственности, работа Фрейзера имеет много общего с сегодняшним видением генетических алгоритмов. Он моделировал эволюцию 15-битных строк и подсчитывал процентное содержание особей с удачным фенотипом в успешных поколениях. Его работы напоминают оптимизацию функций, однако в работах Фрейзера нет ни одного упоминания о возможности использовать ГА для искусственных задач.

Во многих источниках именно Холланда называют родителем современной теории ГА. Однако, Холланд занимался ими не с самого начала. Его интересовала, прежде всего, способность природных систем к адаптации, а его мечтой было создание такой системы, которая могла бы приспособиться к любым условиям окружающей среды. Заслуга Холланда в том, что он осознал значение эволюционных принципов в адаптации и развил свои предположения. Звучит, вообще-то, как-то сухо, но на самом деле, до такого ещё надо додуматься! Вместе со своими студентами, слушавшими курсы по адаптивным системам в Университете штата Мичиган, он разрабатывает то, что впоследствии назовет "генетическим планом", а нам это известно как "генетический алгоритм". О том, насколько серьезно велись работы в этом направлении говорит уже то, что один из студентов Холланда - Кеннет Де Йонг (Kenneth De Jong) защищал диссертацию на степень Доктора Философии (Doctor of Philosophy) в 1975 году! Диссертация называется "An Analysis of the Behavior of a Class of Genetic Adaptive Systems" и является просто сокровищем для тех, кто хочет заниматься ГА всерьез. Лежит она здесь в разделе "Публикации" ("Publications"). В том же году выходит знаменитая книга Холланда "Адаптация в природных и искусственных системах" ( "Adaptation in Natural and Artificial Systems", 1975). После этого ГА начинают привлекать к себе все больше внимания, ими занимается все больше исследователей, которые находят им новые сферы применения. В 1992 году, по данным библиографии Ярмо Аландера (Jarmo T. Alander, 1994), число публикаций перевалило за 500, что, в общем-то, немного, однако в 1982 году их было всего 15!

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

1. http://www.brunel.ac.uk/depts/AI/alife/

2. Jarmo T. Alander "An Indexed Bibliography of Genetic Algorithms: Years 1957-1993"

3. Дюк В., Самойленко А. Data Mining: Учебный курс (+CD). - СПб: Питер, 2001. - 368с.: ил.