Главная arrow Поиск arrow Эволюция и поиск
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Эволюция и поиск Печать
Теория эволюции была изложена Чарльзом Дарвином в его книге On the Origin of Species by Means of Natural Selection (Происхождение видов путем естественного отбора). Основная идея этой теории проста: при воспроизводстве возникают вариации (известные как мутации), которые сохраняются в следующих поколениях с частотой, приблизительно пропорциональной тому, как они влияют на пригодность к воспроизводству.

Дарвин разрабатывал свою теорию, не зная о том, благодаря чему происходит наследование и модификация характерных особенностей организмов. Вероятностные законы, управляющие этими процессами, были впервые обнаружены Грегором Менделем, монахом, проводившим эксперименты с душистым горошком с использованием метода, названного им искусственным оплодотворением. Гораздо позже Уотсон и Крик выявили структуру молекулы ДНК (дезоксирибонуклеиновой кислоты) и ее алфавит, состоящий из аминокислот АГТЦ (аденин, гуанин, тимин, цитозин). В предложенной ими стандартной модели вариации возникают и в результате точечных мутаций в последовательности этих аминокислот, и в результате «скрещивания» (при котором ДНК потомка формируется путем объединения длинных секций ДНК от каждого родителя).

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

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

На первый взгляд может показаться, что механизм дарвиновской эволюции является неэффективным, поскольку в его рамках на Земле за многие тысячи лет было вслепую сформировано около 1045 или примерно столько организмов, притом что за такое время поисковые эвристики этого механизма не улучшились ни на йоту. Но за пятьдесят лет до Дарвина французский натуралист Жан Ламарк, получивший известность в другой области, предложил теорию эволюции, согласно которой характерные особенности организма, приобретенные в результате его адаптации на протяжении срока жизни этого организма, передаются его потомкам. Такой процесс был бы очень эффективным, но в природе, по-видимому, не происходит.

Намного позднее Джеймс Болдуин предложил теорию, которая внешне кажется аналогичной; согласно этой теории, поведение, которому обучился организм на протяжении своей жизни, способствует повышению скорости эволюции. В отличие от теории Ламарка, теория Болдуина полностью согласуется с дарвиновской теорией эволюции, поскольку в ней учитываются давления отбора, действующие на индивидуумов, которые нашли локальные оптимумы среди множества возможных вариантов поведения, допустимых согласно их генетической природе. Современные компьютерные модели подтвердили, что «эффект Болдуина» является реальным, при условии, что «обычная» эволюция способна создавать организмы, внутренние показатели производительности которых каким-то образом коррелируют с их фактической жизненной пригодностью.