История статьи "Эволюционный алгоритм"

Версия 51 (изменялась пользователем admin 26 июня 2006 г. 12:12)
Изменить версию №51 этой статьи | Другие версии

В.1 Что такое Эволюционные Алгоритмы?

(англ. Evolutionary Algorythms)

Эволюционный алгоритм – это всеохватывающий термин, используемый для описания компьютерных систем решения проблем, в которых в качестве ключевого элемента конструкции и исполнения используются вычислительные модели эволюционных процессов. Существует множество различных эволюционных алгоритмов. Основные из них: генетические алгоритмы (В.1.1), эволюционное программирование (В.1.2), эволюционные стратегии (В.1.3), классификаторы (В.1.4), генетическое программирование (В.1.5). Они все разделяют общую концепцию симуляции ЭВОЛЮЦИИ ИНДИВИДУАЛЬНЫХ структур, посредством процессов ОТБОРА, МУТАЦИИ и ВОСПРОИЗВОДСТВА. Поведение процессов опрделяется ОКРУЖЕНАЮЩЕЙ СРЕДОЙ индивидуальных структур и зависит от их текущих ХАРАКТЕРИСТИК.

Другими словами, эволюционные алгоритмы поддерживают ПОПУЛЯЦИИ структур, которые эволюционируют в соответствии с правилами ОТБОРА и другими операторами, которые называются «операторами поиска» (или ГЕНЕТИЧЕСКИМИ ОПЕРАТОРами), такие как РЕКОМБИНАЦИЯ и МУТАЦИЯ. Каждому ИНДИВИДУУМу популяции назначается значение его ПРИГОДНОСТи в ОКРУЖАЮЩЕЙ СРЕДЕ. ВОСПРОИЗВОДСТВО фокусирует внимание на индивидуумах с более высокими значениями пригодности, используя (ИСПОЛЬЗОВАНИЕ) доступную информацию об индивидуумах. Рокомбинация и мутация влияют на индивидуумов, предостовляя тем самым базовую эвристику для ИССЛЕДОВАНИЯ. Несмотря на свою простоту с точки зрения биолога, эти алгоритмы достаточно сложны, чтобы предоставить устойчивые и мощные адаптивные поисковые механизмы.

Псевдокод:

Algorithm EA is
    // Начальное время
    t := 0;
    // Инициализация обычно случайной популяции инивидуумов
    initpopulation P (t);
    // Оценка пригодности всех начальных индивидуумов популяции
    evaluate P (t);
    // Проверка критерия прекращения поиска (время, пригодность, и т.п.)
    while not done do
        // Увеличить счетчик времени
        t := t + 1;
        // Выбор суб-популяции для производства потомоков
        P' := selectparents P (t);
        // Рекомбинация «генов» выбранных родителей
        recombine P' (t);
        // Искажение спаренной популяции случайным образом
        mutate P' (t);
        // Переоценка новых значений пригодности популяции
        evaluate P' (t);
        // Отбор выживших индивидуумов по значению пригодности
        P := survive P,P' (t);
    od
end EA.

---

Оригинальная статья на англ.: http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/html/faqs/ai/genetic/part2/faq-doc-1.html

Изменить версию №51 этой статьи | Другие версии