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

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

Содержание

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

Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» - 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;
   }
}

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home