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

Эволюция и поиск

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

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