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

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

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

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

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

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

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

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

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

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