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

Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

История

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере, установленном в Институте перспективных исследований Принстонского университета.^[1]^[2] Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года,^[3] австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970)^[4] и Кросби (1973)^[5], с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов.^[6] Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998).^[7]

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру,^[8] искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века — группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции.^[9]^[10]^[11]^[12] Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975)^[13]. Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver — первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал^[14] об Evolver в 1990 году.

Описание алгоритма

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

Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.

При выборе «функции приспособленности» (или fitness function в англоязычной литературе) важно следить, чтобы её «рельеф» был «гладким».

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

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

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

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

Таким образом, можно выделить следующие этапы генетического алгоритма:

Задать целевую функцию (приспособленности) для особей популяции
Создать начальную популяцию

(Начало цикла)

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

Создание начальной популяции

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм всё равно достаточно быстро переведёт её в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

Отбор (селекция)

На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и её просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

Турнирная селекция - сначала случайно выбирается установленное количество особей (обычно две), а затем из них выбирается особь с лучшим значением функции приспособленности
Метод рулетки - вероятность выбора особи тем вероятнее, чем лучше её значение функции приспособленности <math>p_i=\frac {f_i} {\sum^{N}_{i=1} {f_i}}</math>, где <math>p_i</math> - вероятность выбора i особи, <math>f_i</math> - значение функции приспособленности для i особи, <math>N</math> - количество особей в популяции
Метод ранжирования - вероятность выбора зависит от места в списке особей отсортированном по значению функции приспособленности <math>p_i=\frac {1} {N} (a-(a-b)\frac {i-1} {N-1})</math>, где <math>a\in[1,2]</math>, <math>b=2-a</math>, <math>i</math> - порядковый номер особи в списке особей отсортированном по значению функции приспособленности ( т.е. <math>\forall \text{ } i \text{ } \forall \text{ } j>i \text{ }\text{ } f_i \le f_j</math> - если мы минимизируем значение функции приспособленности)
Равномерное ранжирование - вероятность выбора особи определяется выражением: <math>p_i=\begin{cases}

 \frac {1} {\mu},  & \mbox{if } 1 \le i \le \mu \\
 0, & \mbox{if } \mu \le i \le N

\end{cases}</math>, где <math>\mu \le N</math> параметр метода

Сигма отсечение - для предотвращения преждевременной сходимости генетического алгоритма используются методы, масштабирующие значение целевой функции. Вероятность выбора особи тем больше, чем оптимальнее значение масштабируемой целевой функции <math>p_i=\frac {F_i} {\sum^{N}_{i=1} {F_i}}</math>, где <math>F_i=1+\frac {f_i+f_{avg}} {2\sigma}</math>, <math>f_{avg}</math> - среднее значение целевой функции для всей популяции, σ - среднеквадратичное отклонение значения целевой функции

Выбор родителей

Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей, обычно два.

Можно выделить несколько операторов выбора родителей:

Панмиксия - оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной
Инбридинг - первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя
Аутбридинг - первый родитель выбирается случайно, а вторым выбирается такой, который наиболее не похож на первого родителя

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

Размножение (Скрещивание)

Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.

Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H' (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей. Однако такой подход вынуждает хранить всех существовавших ранее особей, что увеличивает вычислительную сложность задачи. Поэтому часто применяют методы отбора особей для скрещивания таким образом, чтобы «размножались» не только самые приспособленные, но и другие особи, обладающие плохой приспособленностью. При таком подходе для разнообразия генотипа возрастает роль мутаций.

Мутации

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

Критика

Существует несколько поводов для критики насчёт использования генетического алгоритма по сравнению с другими методами оптимизации:

Повторная оценка функции приспособленности (фитнесс-функции) для сложных проблем, часто является фактором, ограничивающим использование алгоритмов искусственной эволюции. Поиск оптимального решения для сложной задачи высокой размерности зачастую требует очень затратной оценки функции приспособленности. В реальных задачах, таких как задачи структурной оптимизации, единственный запуск функциональной оценки требует от нескольких часов до нескольких дней для произведения необходимых вычислений. Стандартные методы оптимизации не могут справиться с проблемами такого рода. В таком случае, может быть необходимо пренебречь точной оценкой и использовать аппроксимацию пригодности, которая способна быть вычислена эффективно. Очевидно, что применение аппроксимации пригодности может стать одним из наиболее многообещающих подходов, позволяющих обоснованно решать сложные задачи реальной жизни с помощью генетических алгоритмов.
Генетические алгоритмы плохо масштабируемы под сложность решаемой проблемы. Это значит, что число элементов, подверженных мутации очень велико, если велик размер области поиска решений. Это делает использование данной вычислительной техники чрезвычайно сложным при решении таких проблем, как, например, проектирование двигателя, дома или самолёта. Для того чтобы сделать так, чтобы такие проблемы поддавались эволюционным алгоритмам, они должны быть разделены на простейшие представления данных проблем. Таким образом, эволюционные вычисления используются, например, при разработке формы лопастей, вместо всего двигателя, формы здания, вместо подробного строительного проекта и формы фюзеляжа, вместо разработки вида всего самолёта. Вторая проблема, связанная со сложностью, кроется в том, как защитить части, которые эволюционировали с высокопригодными решениями от дальнейшей разрушительной мутации, в частности тогда, когда от них требуется хорошая совместимость с другими частями в процессе оценки пригодности. Некоторыми разработчиками было предложено, что подход, предполагающий развитие пригодности эволюционирующих решений, смог бы преодолеть ряд проблем с защитой, но данный вопрос всё ещё остаётся открытым для исследования.
Решение является более пригодным лишь по сравнению с другими решениями. В результате условие остановки алгоритма неясно для каждой проблемы.
Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальному оптимуму или даже к спорным точкам, вместо глобального оптимума для данной задачи. Это значит, что они «не знают», каким образом пожертвовать кратковременной высокой пригодностью для достижения долгосрочной пригодности. Вероятность этого зависит от формы ландшафта пригодности: отдельные проблемы могут иметь выраженное направление к глобальному минимуму, в то время как остальные могут указывать направление для фитнесс-функции на локальный оптимум. Эту проблему можно решить использованием иной фитнесс-функции, увеличением вероятности мутаций, или использованием методов отбора, которые поддерживают разнообразие решений в популяции, хотя Теорема об отсутствии бесплатного обеда при поиске и оптимизации^[15] доказывает, что не существует общего решения данной проблемы. Общепринятым методом поддержания популяционного разнообразия является установка уровневого ограничения на численность элементов с высоким сродством, которое снизит число представителей сходных решений в последующих поколениях, позволяя другим, менее сходным элементам оставаться в популяции. Данный приём, тем не менее, может не увенчаться успехом в зависимости от ландшафта конкретной проблемы. Другим возможным методом может служить простое замещение части популяции случайно сгенерированными элементами, в момент, когда элементы популяции становятся слишком сходны между собой. Разнообразие важно для генетических алгоритмов (и генетического программирования) потому, что перекрёст генов в гомогенной популяции не несёт новых решений. В эволюционных стратегиях и эволюционном программировании, разнообразие не является необходимостью, так как большая роль в них отведена мутации.

Имеется много скептиков относительно целесообразности применения генетических алгоритмов. Например, Стивен С. Скиена, профессор кафедры вычислительной техники университета Стоуни—Брук, известный исследователь алгоритмов, лауреат премии института IEEE, пишет^[16]:

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

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

Генетические алгоритмы применяются для решения следующих задач:

Оптимизация функций
Оптимизация запросов в базах данных
Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
Настройка и обучение искусственной нейронной сети
Задачи компоновки
Составление расписаний
Игровые стратегии
Теория приближений
Искусственная жизнь
Биоинформатика (фолдинг белков)
Синтез конечных автоматов
Настройка ПИД регуляторов

Пример простой реализации на C++

Поиск в одномерном пространстве, без скрещивания.

#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <numeric>
  
int main()
{
    srand((unsigned int)time(NULL));
    const size_t N = 1000;
    int a[N] = { 0 };
    for ( ; ; )
    {
        //мутация в случайную сторону каждого элемента:
        for (size_t i = 0; i < N; ++i)
            a[i] += ((rand() % 2 == 1) ? 1 : -1);

        //теперь выбираем лучших, отсортировав по возрастанию
        std::sort(a, a + N);
        //и тогда лучшие окажутся во второй половине массива.
        //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:
        std::copy(a + N / 2, a + N, a);
        //теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.
        std::cout << std::accumulate(a, a + N, 0) / N << std::endl;
    }
}

Пример простой реализации на Delphi

Поиск в одномерном пространстве с вероятностью выживания, без скрещивания. (проверено на Delphi XE)

program Program1;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.Generics.Defaults,
  System.Generics.Collections,
  System.SysUtils;

const
  N = 1000;
  Nh = N div 2;
  MaxPopulation = High(Integer);
var
  A: array [1..N] of Integer;
  I, R, C, Points, BirthRate: Integer;
  Iptr: ^Integer;
begin
  Randomize;
  // Частичная популяция
  for I := 1 to N do
    A[I] := Random(2);
  repeat
    // Мутация
    for I := 1 to N do
      A[I] := A[I] + (-Random(2) or 1);
    // Отбор, лучшие в конце
    TArray.Sort<Integer>(A, TComparer<Integer>.Default);
    // Предустановка
    Iptr := Addr(A[Nh + 1]);
    Points := 0;
    BirthRate := 0;
    // Результаты скрещивания
    for I := 1 to Nh do
    begin
      Inc(Points, Iptr^);
      // Случайный успех скрещивания
      R := Random(2);
      Inc(BirthRate, R);
      A[I] := Iptr^ * R;
      Iptr^ := 0;
      Inc(Iptr,1);
    end;
    // Промежуточный итог
    Inc(C);
  until (Points / N >= 1) or (C >= MaxPopulation);
  Writeln(Format('Population %d (rate:%f) score:%f', [C, BirthRate / Nh, Points / N]));
end.

В культуре

В фильме 1995 года «Виртуозность» мозг главного злодея выращен генетическим алгоритмом с использованием воспоминаний и поведенческих черт преступников.

Напишите отзыв о статье "Генетический алгоритм"

Примечания

↑ Barricelli, Nils Aall (1954). «Esempi numerici di processi di evoluzione». Methodos: 45–68.
↑ Barricelli, Nils Aall (1957). «Symbiogenetic evolution processes realized by artificial methods». Methodos: 143–182.
↑ Fraser, Alex (1957). «Simulation of genetic systems by automatic digital computers. I. Introduction». Aust. J. Biol. Sci. 10: 484–491.
↑ Fraser Alex. Computer Models in Genetics. — New York: McGraw-Hill, 1970. — ISBN 0-07-021904-4.
↑ Crosby Jack L. Computer Simulation in Genetics. — London: John Wiley & Sons, 1973. — ISBN 0-471-18880-8.
↑ [berkeley.edu/news/media/releases/96legacy/releases.96/14319.html 02.27.96 — UC Berkeley’s Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69]
↑ Fogel David B. (editor). Evolutionary Computation: The Fossil Record. — New York: IEEE Press, 1998. — ISBN 0-7803-3481-7.
↑ Barricelli, Nils Aall (1963). «Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life». Acta Biotheoretica (16): 99–126.
↑ Rechenberg Ingo. Evolutionsstrategie. — Holzmann-Froboog, 1973. — ISBN 3-7728-0373-3.
↑ Schwefel Hans-Paul. Numerische Optimierung von Computer-Modellen (PhD thesis). — 1974.
↑ Schwefel Hans-Paul. Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. — Birkhäuser, 1977. — ISBN 3-7643-0876-1.
↑ Schwefel Hans-Paul. Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. — Wiley, 1981. — ISBN 0-471-09988-0.
↑ J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
↑ Markoff, John. [www.nytimes.com/1990/08/29/business/business-technology-what-s-the-best-answer-it-s-survival-of-the-fittest.html What's the Best Answer? It's Survival of the Fittest], New York Times (29 августа 1990). Проверено 9 августа 2009.
↑ Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
↑ Steven S. Skiena. The Algorithm Design Manual. Second Edition. Springer, 2008.

Книги

Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 2003. — С. 432. — ISBN 5-9221-0337-7.
Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. — М: Физматлит, 2006. — С. 272. — ISBN 5-9221-0749-6.
Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — С. 320. — ISBN 5-9221-0510-8.
Гладков Л. А., Курейчик В. В, Курейчик В. М. и др. Биоинспирированные методы в оптимизации: монография. — М: Физматлит, 2009. — С. 384. — ISBN 978-5-9221-1101-0.
Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. — 2-е изд. — М: Горячая линия-Телеком, 2008. — С. 452. — ISBN 5-93517-103-1.
Скобцов Ю. А. Основы эволюционных вычислений. — Донецк: ДонНТУ, 2008. — С. 326. — ISBN 978-966-377-056-6.

Ссылки

[www.getinfo.ru/article31_1.html Эволюционные вычисления]
[andyceo.ruware.com/study/ispolzovanie-geneticheskih-algoritmov-v-probleme-avtomaticheskogo-napisaniya-programm Использование генетических алгоритмов в проблеме автоматического написания программ]
[andyceo.ruware.com/study/realizatsiya-geneticheskih-algoritmov-v-srede-matlab-v612 Реализация генетических алгоритмов в среде MATLAB v6.12]
Сергей Николенко. [logic.pdmi.ras.ru/~sergey/teaching/ml/04-genetic.pdf Генетические алгоритмы] (слайды) — лекция № 4 из курса [www.csin.ru/courses/samoobuchayushchiesya-sistemy-i-nechetkaya-logika «Самообучающиеся системы»]
[www.geneticprogramming.us/ geneticprogramming.us]
[is.ifmo.ru/genalg/ Генерирование автоматов состояний с помощью ГА]
[www.csit.narod.ru/subject/mag_SShI/mono.pdf Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с.] (укр.)
Poli, R., Langdon, W. B., McPhee, N. F. A Field Guide to Genetic Programming. — Lulu.com, freely available from the internet, 2008. — ISBN 978-1-4092-0073-4.
[delta.cs.cinvestav.mx/~ccoello/EMOO/ Подборка статей по использованию генетических алгоритмов в задачах многокритериальной оптимизации] (англ.)
[science-library.at.ua/load/sistemy_iskusstvennogo_intellekta/nechetkie_sistemy_i_nechetkaja_logika/fusion_of_neural_networks_fuzzy_systems_and_genetic_algorithms_industrial_applications/4-1-0-5 Lakhmi C. Jain; N.M. Martin Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications. — CRC Press, CRC Press LLC, 1998]

Отрывок, характеризующий Генетический алгоритм

Проезжая позади одной из линий пехотных гвардейских полков, он услыхал голос, назвавший его по имени.
– Ростов!
– Что? – откликнулся он, не узнавая Бориса.
– Каково? в первую линию попали! Наш полк в атаку ходил! – сказал Борис, улыбаясь той счастливой улыбкой, которая бывает у молодых людей, в первый раз побывавших в огне.
Ростов остановился.
– Вот как! – сказал он. – Ну что?
– Отбили! – оживленно сказал Борис, сделавшийся болтливым. – Ты можешь себе представить?
И Борис стал рассказывать, каким образом гвардия, ставши на место и увидав перед собой войска, приняла их за австрийцев и вдруг по ядрам, пущенным из этих войск, узнала, что она в первой линии, и неожиданно должна была вступить в дело. Ростов, не дослушав Бориса, тронул свою лошадь.
– Ты куда? – спросил Борис.
– К его величеству с поручением.
– Вот он! – сказал Борис, которому послышалось, что Ростову нужно было его высочество, вместо его величества.
И он указал ему на великого князя, который в ста шагах от них, в каске и в кавалергардском колете, с своими поднятыми плечами и нахмуренными бровями, что то кричал австрийскому белому и бледному офицеру.
– Да ведь это великий князь, а мне к главнокомандующему или к государю, – сказал Ростов и тронул было лошадь.
– Граф, граф! – кричал Берг, такой же оживленный, как и Борис, подбегая с другой стороны, – граф, я в правую руку ранен (говорил он, показывая кисть руки, окровавленную, обвязанную носовым платком) и остался во фронте. Граф, держу шпагу в левой руке: в нашей породе фон Бергов, граф, все были рыцари.
Берг еще что то говорил, но Ростов, не дослушав его, уже поехал дальше.
Проехав гвардию и пустой промежуток, Ростов, для того чтобы не попасть опять в первую линию, как он попал под атаку кавалергардов, поехал по линии резервов, далеко объезжая то место, где слышалась самая жаркая стрельба и канонада. Вдруг впереди себя и позади наших войск, в таком месте, где он никак не мог предполагать неприятеля, он услыхал близкую ружейную стрельбу.
«Что это может быть? – подумал Ростов. – Неприятель в тылу наших войск? Не может быть, – подумал Ростов, и ужас страха за себя и за исход всего сражения вдруг нашел на него. – Что бы это ни было, однако, – подумал он, – теперь уже нечего объезжать. Я должен искать главнокомандующего здесь, и ежели всё погибло, то и мое дело погибнуть со всеми вместе».
Дурное предчувствие, нашедшее вдруг на Ростова, подтверждалось всё более и более, чем дальше он въезжал в занятое толпами разнородных войск пространство, находящееся за деревнею Працом.
– Что такое? Что такое? По ком стреляют? Кто стреляет? – спрашивал Ростов, ровняясь с русскими и австрийскими солдатами, бежавшими перемешанными толпами наперерез его дороги.
– А чорт их знает? Всех побил! Пропадай всё! – отвечали ему по русски, по немецки и по чешски толпы бегущих и непонимавших точно так же, как и он, того, что тут делалось.
– Бей немцев! – кричал один.
– А чорт их дери, – изменников.
– Zum Henker diese Ruesen… [К чорту этих русских…] – что то ворчал немец.
Несколько раненых шли по дороге. Ругательства, крики, стоны сливались в один общий гул. Стрельба затихла и, как потом узнал Ростов, стреляли друг в друга русские и австрийские солдаты.
«Боже мой! что ж это такое? – думал Ростов. – И здесь, где всякую минуту государь может увидать их… Но нет, это, верно, только несколько мерзавцев. Это пройдет, это не то, это не может быть, – думал он. – Только поскорее, поскорее проехать их!»
Мысль о поражении и бегстве не могла притти в голову Ростову. Хотя он и видел французские орудия и войска именно на Праценской горе, на той самой, где ему велено было отыскивать главнокомандующего, он не мог и не хотел верить этому.

Около деревни Праца Ростову велено было искать Кутузова и государя. Но здесь не только не было их, но не было ни одного начальника, а были разнородные толпы расстроенных войск.
Он погонял уставшую уже лошадь, чтобы скорее проехать эти толпы, но чем дальше он подвигался, тем толпы становились расстроеннее. По большой дороге, на которую он выехал, толпились коляски, экипажи всех сортов, русские и австрийские солдаты, всех родов войск, раненые и нераненые. Всё это гудело и смешанно копошилось под мрачный звук летавших ядер с французских батарей, поставленных на Праценских высотах.
– Где государь? где Кутузов? – спрашивал Ростов у всех, кого мог остановить, и ни от кого не мог получить ответа.
Наконец, ухватив за воротник солдата, он заставил его ответить себе.
– Э! брат! Уж давно все там, вперед удрали! – сказал Ростову солдат, смеясь чему то и вырываясь.
Оставив этого солдата, который, очевидно, был пьян, Ростов остановил лошадь денщика или берейтора важного лица и стал расспрашивать его. Денщик объявил Ростову, что государя с час тому назад провезли во весь дух в карете по этой самой дороге, и что государь опасно ранен.
– Не может быть, – сказал Ростов, – верно, другой кто.
– Сам я видел, – сказал денщик с самоуверенной усмешкой. – Уж мне то пора знать государя: кажется, сколько раз в Петербурге вот так то видал. Бледный, пребледный в карете сидит. Четверню вороных как припустит, батюшки мои, мимо нас прогремел: пора, кажется, и царских лошадей и Илью Иваныча знать; кажется, с другим как с царем Илья кучер не ездит.
Ростов пустил его лошадь и хотел ехать дальше. Шедший мимо раненый офицер обратился к нему.
– Да вам кого нужно? – спросил офицер. – Главнокомандующего? Так убит ядром, в грудь убит при нашем полку.
– Не убит, ранен, – поправил другой офицер.
– Да кто? Кутузов? – спросил Ростов.
– Не Кутузов, а как бишь его, – ну, да всё одно, живых не много осталось. Вон туда ступайте, вон к той деревне, там всё начальство собралось, – сказал этот офицер, указывая на деревню Гостиерадек, и прошел мимо.
Ростов ехал шагом, не зная, зачем и к кому он теперь поедет. Государь ранен, сражение проиграно. Нельзя было не верить этому теперь. Ростов ехал по тому направлению, которое ему указали и по которому виднелись вдалеке башня и церковь. Куда ему было торопиться? Что ему было теперь говорить государю или Кутузову, ежели бы даже они и были живы и не ранены?
– Этой дорогой, ваше благородие, поезжайте, а тут прямо убьют, – закричал ему солдат. – Тут убьют!
– О! что говоришь! сказал другой. – Куда он поедет? Тут ближе.
Ростов задумался и поехал именно по тому направлению, где ему говорили, что убьют.
«Теперь всё равно: уж ежели государь ранен, неужели мне беречь себя?» думал он. Он въехал в то пространство, на котором более всего погибло людей, бегущих с Працена. Французы еще не занимали этого места, а русские, те, которые были живы или ранены, давно оставили его. На поле, как копны на хорошей пашне, лежало человек десять, пятнадцать убитых, раненых на каждой десятине места. Раненые сползались по два, по три вместе, и слышались неприятные, иногда притворные, как казалось Ростову, их крики и стоны. Ростов пустил лошадь рысью, чтобы не видать всех этих страдающих людей, и ему стало страшно. Он боялся не за свою жизнь, а за то мужество, которое ему нужно было и которое, он знал, не выдержит вида этих несчастных.
Французы, переставшие стрелять по этому, усеянному мертвыми и ранеными, полю, потому что уже никого на нем живого не было, увидав едущего по нем адъютанта, навели на него орудие и бросили несколько ядер. Чувство этих свистящих, страшных звуков и окружающие мертвецы слились для Ростова в одно впечатление ужаса и сожаления к себе. Ему вспомнилось последнее письмо матери. «Что бы она почувствовала, – подумал он, – коль бы она видела меня теперь здесь, на этом поле и с направленными на меня орудиями».
В деревне Гостиерадеке были хотя и спутанные, но в большем порядке русские войска, шедшие прочь с поля сражения. Сюда уже не доставали французские ядра, и звуки стрельбы казались далекими. Здесь все уже ясно видели и говорили, что сражение проиграно. К кому ни обращался Ростов, никто не мог сказать ему, ни где был государь, ни где был Кутузов. Одни говорили, что слух о ране государя справедлив, другие говорили, что нет, и объясняли этот ложный распространившийся слух тем, что, действительно, в карете государя проскакал назад с поля сражения бледный и испуганный обер гофмаршал граф Толстой, выехавший с другими в свите императора на поле сражения. Один офицер сказал Ростову, что за деревней, налево, он видел кого то из высшего начальства, и Ростов поехал туда, уже не надеясь найти кого нибудь, но для того только, чтобы перед самим собою очистить свою совесть. Проехав версты три и миновав последние русские войска, около огорода, окопанного канавой, Ростов увидал двух стоявших против канавы всадников. Один, с белым султаном на шляпе, показался почему то знакомым Ростову; другой, незнакомый всадник, на прекрасной рыжей лошади (лошадь эта показалась знакомою Ростову) подъехал к канаве, толкнул лошадь шпорами и, выпустив поводья, легко перепрыгнул через канаву огорода. Только земля осыпалась с насыпи от задних копыт лошади. Круто повернув лошадь, он опять назад перепрыгнул канаву и почтительно обратился к всаднику с белым султаном, очевидно, предлагая ему сделать то же. Всадник, которого фигура показалась знакома Ростову и почему то невольно приковала к себе его внимание, сделал отрицательный жест головой и рукой, и по этому жесту Ростов мгновенно узнал своего оплакиваемого, обожаемого государя.
«Но это не мог быть он, один посреди этого пустого поля», подумал Ростов. В это время Александр повернул голову, и Ростов увидал так живо врезавшиеся в его памяти любимые черты. Государь был бледен, щеки его впали и глаза ввалились; но тем больше прелести, кротости было в его чертах. Ростов был счастлив, убедившись в том, что слух о ране государя был несправедлив. Он был счастлив, что видел его. Он знал, что мог, даже должен был прямо обратиться к нему и передать то, что приказано было ему передать от Долгорукова.
Но как влюбленный юноша дрожит и млеет, не смея сказать того, о чем он мечтает ночи, и испуганно оглядывается, ища помощи или возможности отсрочки и бегства, когда наступила желанная минута, и он стоит наедине с ней, так и Ростов теперь, достигнув того, чего он желал больше всего на свете, не знал, как подступить к государю, и ему представлялись тысячи соображений, почему это было неудобно, неприлично и невозможно.
«Как! Я как будто рад случаю воспользоваться тем, что он один и в унынии. Ему неприятно и тяжело может показаться неизвестное лицо в эту минуту печали; потом, что я могу сказать ему теперь, когда при одном взгляде на него у меня замирает сердце и пересыхает во рту?» Ни одна из тех бесчисленных речей, которые он, обращая к государю, слагал в своем воображении, не приходила ему теперь в голову. Те речи большею частию держались совсем при других условиях, те говорились большею частию в минуту побед и торжеств и преимущественно на смертном одре от полученных ран, в то время как государь благодарил его за геройские поступки, и он, умирая, высказывал ему подтвержденную на деле любовь свою.
«Потом, что же я буду спрашивать государя об его приказаниях на правый фланг, когда уже теперь 4 й час вечера, и сражение проиграно? Нет, решительно я не должен подъезжать к нему. Не должен нарушать его задумчивость. Лучше умереть тысячу раз, чем получить от него дурной взгляд, дурное мнение», решил Ростов и с грустью и с отчаянием в сердце поехал прочь, беспрестанно оглядываясь на всё еще стоявшего в том же положении нерешительности государя.
В то время как Ростов делал эти соображения и печально отъезжал от государя, капитан фон Толь случайно наехал на то же место и, увидав государя, прямо подъехал к нему, предложил ему свои услуги и помог перейти пешком через канаву. Государь, желая отдохнуть и чувствуя себя нездоровым, сел под яблочное дерево, и Толь остановился подле него. Ростов издалека с завистью и раскаянием видел, как фон Толь что то долго и с жаром говорил государю, как государь, видимо, заплакав, закрыл глаза рукой и пожал руку Толю.
«И это я мог бы быть на его месте?» подумал про себя Ростов и, едва удерживая слезы сожаления об участи государя, в совершенном отчаянии поехал дальше, не зная, куда и зачем он теперь едет.
Его отчаяние было тем сильнее, что он чувствовал, что его собственная слабость была причиной его горя.
Он мог бы… не только мог бы, но он должен был подъехать к государю. И это был единственный случай показать государю свою преданность. И он не воспользовался им… «Что я наделал?» подумал он. И он повернул лошадь и поскакал назад к тому месту, где видел императора; но никого уже не было за канавой. Только ехали повозки и экипажи. От одного фурмана Ростов узнал, что Кутузовский штаб находится неподалеку в деревне, куда шли обозы. Ростов поехал за ними.
Впереди его шел берейтор Кутузова, ведя лошадей в попонах. За берейтором ехала повозка, и за повозкой шел старик дворовый, в картузе, полушубке и с кривыми ногами.
– Тит, а Тит! – сказал берейтор.
– Чего? – рассеянно отвечал старик.
– Тит! Ступай молотить.
– Э, дурак, тьфу! – сердито плюнув, сказал старик. Прошло несколько времени молчаливого движения, и повторилась опять та же шутка.
В пятом часу вечера сражение было проиграно на всех пунктах. Более ста орудий находилось уже во власти французов.
Пржебышевский с своим корпусом положил оружие. Другие колонны, растеряв около половины людей, отступали расстроенными, перемешанными толпами.
Остатки войск Ланжерона и Дохтурова, смешавшись, теснились около прудов на плотинах и берегах у деревни Аугеста.
В 6 м часу только у плотины Аугеста еще слышалась жаркая канонада одних французов, выстроивших многочисленные батареи на спуске Праценских высот и бивших по нашим отступающим войскам.
В арьергарде Дохтуров и другие, собирая батальоны, отстреливались от французской кавалерии, преследовавшей наших. Начинало смеркаться. На узкой плотине Аугеста, на которой столько лет мирно сиживал в колпаке старичок мельник с удочками, в то время как внук его, засучив рукава рубашки, перебирал в лейке серебряную трепещущую рыбу; на этой плотине, по которой столько лет мирно проезжали на своих парных возах, нагруженных пшеницей, в мохнатых шапках и синих куртках моравы и, запыленные мукой, с белыми возами уезжали по той же плотине, – на этой узкой плотине теперь между фурами и пушками, под лошадьми и между колес толпились обезображенные страхом смерти люди, давя друг друга, умирая, шагая через умирающих и убивая друг друга для того только, чтобы, пройдя несколько шагов, быть точно. так же убитыми.
Каждые десять секунд, нагнетая воздух, шлепало ядро или разрывалась граната в средине этой густой толпы, убивая и обрызгивая кровью тех, которые стояли близко. Долохов, раненый в руку, пешком с десятком солдат своей роты (он был уже офицер) и его полковой командир, верхом, представляли из себя остатки всего полка. Влекомые толпой, они втеснились во вход к плотине и, сжатые со всех сторон, остановились, потому что впереди упала лошадь под пушкой, и толпа вытаскивала ее. Одно ядро убило кого то сзади их, другое ударилось впереди и забрызгало кровью Долохова. Толпа отчаянно надвинулась, сжалась, тронулась несколько шагов и опять остановилась.
Пройти эти сто шагов, и, наверное, спасен; простоять еще две минуты, и погиб, наверное, думал каждый. Долохов, стоявший в середине толпы, рванулся к краю плотины, сбив с ног двух солдат, и сбежал на скользкий лед, покрывший пруд.
– Сворачивай, – закричал он, подпрыгивая по льду, который трещал под ним, – сворачивай! – кричал он на орудие. – Держит!…
Лед держал его, но гнулся и трещал, и очевидно было, что не только под орудием или толпой народа, но под ним одним он сейчас рухнется. На него смотрели и жались к берегу, не решаясь еще ступить на лед. Командир полка, стоявший верхом у въезда, поднял руку и раскрыл рот, обращаясь к Долохову. Вдруг одно из ядер так низко засвистело над толпой, что все нагнулись. Что то шлепнулось в мокрое, и генерал упал с лошадью в лужу крови. Никто не взглянул на генерала, не подумал поднять его.
– Пошел на лед! пошел по льду! Пошел! вороти! аль не слышишь! Пошел! – вдруг после ядра, попавшего в генерала, послышались бесчисленные голоса, сами не зная, что и зачем кричавшие.
Одно из задних орудий, вступавшее на плотину, своротило на лед. Толпы солдат с плотины стали сбегать на замерзший пруд. Под одним из передних солдат треснул лед, и одна нога ушла в воду; он хотел оправиться и провалился по пояс.
Ближайшие солдаты замялись, орудийный ездовой остановил свою лошадь, но сзади всё еще слышались крики: «Пошел на лед, что стал, пошел! пошел!» И крики ужаса послышались в толпе. Солдаты, окружавшие орудие, махали на лошадей и били их, чтобы они сворачивали и подвигались. Лошади тронулись с берега. Лед, державший пеших, рухнулся огромным куском, и человек сорок, бывших на льду, бросились кто вперед, кто назад, потопляя один другого.
Ядра всё так же равномерно свистели и шлепались на лед, в воду и чаще всего в толпу, покрывавшую плотину, пруды и берег.

На Праценской горе, на том самом месте, где он упал с древком знамени в руках, лежал князь Андрей Болконский, истекая кровью, и, сам не зная того, стонал тихим, жалостным и детским стоном.
К вечеру он перестал стонать и совершенно затих. Он не знал, как долго продолжалось его забытье. Вдруг он опять чувствовал себя живым и страдающим от жгучей и разрывающей что то боли в голове.
«Где оно, это высокое небо, которое я не знал до сих пор и увидал нынче?» было первою его мыслью. «И страдания этого я не знал также, – подумал он. – Да, я ничего, ничего не знал до сих пор. Но где я?»
Он стал прислушиваться и услыхал звуки приближающегося топота лошадей и звуки голосов, говоривших по французски. Он раскрыл глаза. Над ним было опять всё то же высокое небо с еще выше поднявшимися плывущими облаками, сквозь которые виднелась синеющая бесконечность. Он не поворачивал головы и не видал тех, которые, судя по звуку копыт и голосов, подъехали к нему и остановились.
Подъехавшие верховые были Наполеон, сопутствуемый двумя адъютантами. Бонапарте, объезжая поле сражения, отдавал последние приказания об усилении батарей стреляющих по плотине Аугеста и рассматривал убитых и раненых, оставшихся на поле сражения.
– De beaux hommes! [Красавцы!] – сказал Наполеон, глядя на убитого русского гренадера, который с уткнутым в землю лицом и почернелым затылком лежал на животе, откинув далеко одну уже закоченевшую руку.
– Les munitions des pieces de position sont epuisees, sire! [Батарейных зарядов больше нет, ваше величество!] – сказал в это время адъютант, приехавший с батарей, стрелявших по Аугесту.
– Faites avancer celles de la reserve, [Велите привезти из резервов,] – сказал Наполеон, и, отъехав несколько шагов, он остановился над князем Андреем, лежавшим навзничь с брошенным подле него древком знамени (знамя уже, как трофей, было взято французами).
– Voila une belle mort, [Вот прекрасная смерть,] – сказал Наполеон, глядя на Болконского.
Князь Андрей понял, что это было сказано о нем, и что говорит это Наполеон. Он слышал, как называли sire того, кто сказал эти слова. Но он слышал эти слова, как бы он слышал жужжание мухи. Он не только не интересовался ими, но он и не заметил, а тотчас же забыл их. Ему жгло голову; он чувствовал, что он исходит кровью, и он видел над собою далекое, высокое и вечное небо. Он знал, что это был Наполеон – его герой, но в эту минуту Наполеон казался ему столь маленьким, ничтожным человеком в сравнении с тем, что происходило теперь между его душой и этим высоким, бесконечным небом с бегущими по нем облаками. Ему было совершенно всё равно в эту минуту, кто бы ни стоял над ним, что бы ни говорил об нем; он рад был только тому, что остановились над ним люди, и желал только, чтоб эти люди помогли ему и возвратили бы его к жизни, которая казалась ему столь прекрасною, потому что он так иначе понимал ее теперь. Он собрал все свои силы, чтобы пошевелиться и произвести какой нибудь звук. Он слабо пошевелил ногою и произвел самого его разжалобивший, слабый, болезненный стон.
– А! он жив, – сказал Наполеон. – Поднять этого молодого человека, ce jeune homme, и свезти на перевязочный пункт!
Сказав это, Наполеон поехал дальше навстречу к маршалу Лану, который, сняв шляпу, улыбаясь и поздравляя с победой, подъезжал к императору.
Князь Андрей не помнил ничего дальше: он потерял сознание от страшной боли, которую причинили ему укладывание на носилки, толчки во время движения и сондирование раны на перевязочном пункте. Он очнулся уже только в конце дня, когда его, соединив с другими русскими ранеными и пленными офицерами, понесли в госпиталь. На этом передвижении он чувствовал себя несколько свежее и мог оглядываться и даже говорить.
Первые слова, которые он услыхал, когда очнулся, – были слова французского конвойного офицера, который поспешно говорил:
– Надо здесь остановиться: император сейчас проедет; ему доставит удовольствие видеть этих пленных господ.
– Нынче так много пленных, чуть не вся русская армия, что ему, вероятно, это наскучило, – сказал другой офицер.
– Ну, однако! Этот, говорят, командир всей гвардии императора Александра, – сказал первый, указывая на раненого русского офицера в белом кавалергардском мундире.
Болконский узнал князя Репнина, которого он встречал в петербургском свете. Рядом с ним стоял другой, 19 летний мальчик, тоже раненый кавалергардский офицер.
Бонапарте, подъехав галопом, остановил лошадь.
– Кто старший? – сказал он, увидав пленных.
Назвали полковника, князя Репнина.
– Вы командир кавалергардского полка императора Александра? – спросил Наполеон.
– Я командовал эскадроном, – отвечал Репнин.
– Ваш полк честно исполнил долг свой, – сказал Наполеон.
– Похвала великого полководца есть лучшая награда cолдату, – сказал Репнин.
– С удовольствием отдаю ее вам, – сказал Наполеон. – Кто этот молодой человек подле вас?
Князь Репнин назвал поручика Сухтелена.
Посмотрев на него, Наполеон сказал, улыбаясь:
– II est venu bien jeune se frotter a nous. [Молод же явился он состязаться с нами.]
– Молодость не мешает быть храбрым, – проговорил обрывающимся голосом Сухтелен.

[1] Barricelli, Nils Aall (1954). «Esempi numerici di processi di evoluzione». Methodos: 45–68.

[2] Barricelli, Nils Aall (1957). «Symbiogenetic evolution processes realized by artificial methods». Methodos: 143–182.

[3] Fraser, Alex (1957). «Simulation of genetic systems by automatic digital computers. I. Introduction». Aust. J. Biol. Sci. 10: 484–491.

[4] Fraser Alex. Computer Models in Genetics. — New York: McGraw-Hill, 1970. — ISBN 0-07-021904-4.

[5] Crosby Jack L. Computer Simulation in Genetics. — London: John Wiley & Sons, 1973. — ISBN 0-471-18880-8.

[6] [berkeley.edu/news/media/releases/96legacy/releases.96/14319.html 02.27.96 — UC Berkeley’s Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69]

[7] Fogel David B. (editor). Evolutionary Computation: The Fossil Record. — New York: IEEE Press, 1998. — ISBN 0-7803-3481-7.

[8] Barricelli, Nils Aall (1963). «Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life». Acta Biotheoretica (16): 99–126.

[9] Rechenberg Ingo. Evolutionsstrategie. — Holzmann-Froboog, 1973. — ISBN 3-7728-0373-3.

[10] Schwefel Hans-Paul. Numerische Optimierung von Computer-Modellen (PhD thesis). — 1974.

[11] Schwefel Hans-Paul. Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. — Birkhäuser, 1977. — ISBN 3-7643-0876-1.

[12] Schwefel Hans-Paul. Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. — Wiley, 1981. — ISBN 0-471-09988-0.

[book-13] J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.

[14] Markoff, John. [www.nytimes.com/1990/08/29/business/business-technology-what-s-the-best-answer-it-s-survival-of-the-fittest.html What's the Best Answer? It's Survival of the Fittest], New York Times (29 августа 1990). Проверено 9 августа 2009.

[15] Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.

[16] Steven S. Skiena. The Algorithm Design Manual. Second Edition. Springer, 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]