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

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (en:evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1992)[1] является основополагающим трудом в этой области исследований.

Содержание

[править] Описание алгоритма

Схема работы генетического алгоритма

Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

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

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

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

  1. Создание начальной популяции
  2. Определение (задание) функций приспособленности для особей популяции (оценивание)
  • (Начало цикла)
  1. Выбор индивидов из текущей популяции (селекция)
  2. Скрещивание и\или мутация
  3. Вычисление функций приспособленности для всех особей
  4. Формирование нового поколения
  5. Если выполняются условия останова, то (конец цикла), иначе (начало цикла).

[править] Создание начальной популяции

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

[править] Отбор

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

[править] Размножение

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

[править] Мутации

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

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

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

  1. Оптимизация функций
  2. Оптимизация запросов в базах данных
  3. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
  4. Настройка и обучение искусственной нейронной сети
  5. Задачи компоновки
  6. Составление расписаний
  7. Игровые стратегии
  8. Теория приближений
  9. Искусственная жизнь
  10. Биоинформатика (свёртывание белков)

[править] Пример тривиальной реализации на C++

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

#include <iostream>
#include <algorithm>
#include <numeric>
 
int main()
{
    using namespace std;
    srand((unsigned)time(NULL));
    const int N = 1000;
    int a[N];
    //заполняем нулями
    fill(a, a+N, 0);
    for (;;)
    {
        //мутация в случайную сторону каждого элемента:
        for (int i = 0; i < N; ++i)
            if (rand()%2 == 1)
                a[i] += 1;
            else
                a[i] -= 1;
        //теперь выбираем лучших, отсортировав по возрастанию... 
        sort(a, a+N);
        //... и тогда лучшие окажутся во второй половине массива.
        //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:
        copy(a+N/2, a+N,    a /*куда*/);
        //теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.
        cout << accumulate(a, a+N, 0) / N << endl;
    }
}

[править] Примечания

  1. ↑ J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.

[править] Ссылки

п·о·р
Инженерия знаний
Информатика
Общие понятия Данные · Метаданные · Знания · Метазнание · Представление знаний · База знаний · Онтология
Жёсткие модели Продукции · Семантическая сеть · Фреймы · Логическая модель
Мягкие методы Нейронная сеть · Генетический алгоритм · Нечёткая логика · Гибридная интеллектуальная система
п·о·р
Искусственный интеллект
Философия Тест Тьюринга • Китайская комната Файл:Nuvola apps Talk.PNG
Направления
Применение
Исследователи
Организации
Портал • Все статьи

Источник — «http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC»