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

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

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

Schema simple algorithme genetique ru — Схема работы генетического алгоритма

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

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

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

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

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

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

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

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

Перед первым шагом нужно случайным образом создать некую начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (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 особей, а затем изменить их в соответствии с заранее определенными операциями мутации.

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

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

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

Пример тривиальной реализации на 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;
    }
}

Примечания[]

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

Ссылки[]

A Field Guide to Genetic Programming. — Lulu.com, freely available from the internet, 2008. — ISBN 978-1-4092-0073-4

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Генетический алгоритм. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

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

[1]

п·о·р Инженерия знаний
Информатика
Общие понятия	Данные · Метаданные · Знания · Метазнание · Представление знаний · База знаний · Онтология
Жёсткие модели	Продукции · Семантическая сеть · Фреймы · Логическая модель
Мягкие методы	Нейронная сеть · Генетический алгоритм · Нечёткая логика · Гибридная интеллектуальная система