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

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

Генети́ческий алгори́тм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «кроссовера», который производит операцию, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.

Содержание 1 Описание алгоритма 2 Применение генетических алгоритмов 3 Пример тривиальной реализации на C++ 4 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

#include <iostream>
#include <algorithm>
#include <numeric>
int main()
{
   const int N = 1000;
   int a[N];
   //заполняем нулями
   std::fill(a, a+N, 0);
   for (;;)
   {
       //мутация в случайную сторону каждого элемента:
       for (int i = 0; i < N; ++i)
           if (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;
   }
}

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

• 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

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