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

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

История

«Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ.), книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований. Ему же принадлежит доказательство теоремы схем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мутации

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

Отбор

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

Критика

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

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

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

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

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

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

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

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

Книги

• Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 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

Ссылки

• Научные статьи по генетическим алгоритмам
• Реализация генетического алгоритма для .NET Framework 2.0
• Проект CuberGA — расширяемый framework для реализации генетических алгоритмов
• GAlib Реализация генетического алгоритма на C++
• EvoJ Легковесный но мощный Java фреймворк для решения задач генетическим алгоритмом
• Эволюционные вычисления
• Генетические алгоритмы
• Генетические алгоритмы
• Решение Диофантова уравнения
• Подборка статей по теме Генетические алгоритмы
• Основные операции генетического алгоритма
• Использование генетических алгоритмов в проблеме автоматического написания программ
• Реализация генетических алгоритмов в среде MATLAB v6.12
• Сергей Николенко. Генетические алгоритмы (слайды) — лекция № 4 из курса «Самообучающиеся системы»
• geneticprogramming.us
• Обзор методов эволюции нейронных сетей
• Генерирование автоматов состояний с помощью ГА

• Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 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
• Special Interest Group for Genetic and Evolutionary Computation (former ISGEC) (англ.)
• JAGA (Java API for Genetic Algorithms) — Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications in Java (англ.)
• IlliGAL (Illinois Genetic Algorithms Laboratory) Home Page (англ.)
• Evolutionary Computation Laboratory at George-Mason University (англ.)
• GENITOR Research Group (CS, Colorado) (англ.)
• Evolutionary and Adaptive Systems (EASy) at Sussex (англ.)
• Genetic Algorithms Articles (англ.)
• Evolutionary Algorithms Research Group at University of Dortmund (англ.)
• Evolutionary Digest Archive (англ.)
• GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA (англ.)
• Очень большая подборка статей по использованию генетических алгоритмов в задачах многокритериальной оптимизации (англ.)
• Genetic Algorithms in Ruby (англ.)
• Lakhmi C. Jain; N.M. Martin Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications. — CRC Press, CRC Press LLC, 1998