Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Термины / Генетический алгоритм

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

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

Генетический алгоритм является разновидностью эволюционных вычислений.

Задача кодируется таким образом, чтобы её решение можно было представить в виде набора коэффициентов — генов. Это, пожалуй, единственное ограничение, и если это возможно, то задача вполне успешно будет решаться генетическим алгоритмом. То есть основная сложность — представление (интерпретация) решения задачи в необходимом виде.

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

Fitness-функция — это целевая функция, то есть мера точности решения или мера удовлетворения решению задачи. Увеличением значения fitness-функции и занимается генетический алгоритм.

Определив fitness-функции и подсчитав их для каждого варианта, отбираются лучшие гены, которые будут переданы следующему поколению вариантов решений. Таким образом, через несколько поколений будет найдено (если это возможно) хорошее решение поставленной задачи.

Типичный порядок действий алгоритма представлен далее.
Инициализация:
  1. Определяется fitness-функция, то есть способ оценки генов для отбора.
  2. Создание начальной популяции. Чаще всего начальные гены заполняются случайными значениями.
Цикл:
  1. Определение значений fitness-функции для каждого гена.
  2. Отбор лучших генов.
  3. Скрещивание генов и / или мутация.
  4. Создание новой популяции на основе полученных генов.

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

В качестве примера работы генетического алгоритма привожу график из моей статьи (Вестник ИжГТУ 2008) :

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

На графике представлены максимальные и средние из всей популяции значения фитнесс-функции для каждой эпохи. Коэффициенты подбирались для нейронной сети, задача была не простая — обучение механизмов правильному движению. И тем не менее, за небольшое количество эпох уже был найден хороший вариант.

В качестве дополнения привожу одну из моих реализаций генетического алгоритма, а точнее функцию эволюции, простой и одновременно отличный вариант:

void GeneticPool::Evolve(int diversity, float mutationPower)           
{
     SortByFitness(); // сортировка генов

     for (int i = diversity; i < genesCount; i++)
     {
           Genes[i] = MutateGenes(Genes[RandomInt(diversity)], MutationPower);
     }
}

Значение diversity определяет количество особей, гены которых будут переданы следующему поколению. Сами эти особи изменению не подвергнутся, дабы не потерять лучшие решения. Таким образом мы получили отличный вариант генетического алгоритма.

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

15 июля 2010

#ИИ, #algorithms, #genetic


Обновление: 6 октября 2010

Постельное белье интернет-магазин качественное постельное белье.
2001—2017 © GameDev.ru — Разработка игр