Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

1.4. Задачи оптимизации и применение алгоритмов 
Генетические алгоритмы - это очень популярные способы решения 
задач оптимизации. В их основе лежит использование эволюционных 
принципов для поиска оптимального решения. Уже сама идея выглядит 
довольно интригующей и любопытной, чтобы претворить её в жизнь, а 
многочисленные положительные результаты только разжигают интерес 
со стороны исследователей. 
Здесь не будет рассматриваться история становления и признания 
эволюционных вычислений вообще и генетических алгоритмов в 
частности. Вместо этого мы сразу перейду к рассмотрению самих 
алгоритмов.
Генетические алгоритмы в основном применяются для решения задач 
оптимизации, т.е. задач, в которых есть некоторая функция нескольких 
переменных 
F(x
1
, x
2
, ... ,x
n
) и необходимо найти либо её максимум, либо 
её минимум. Функция 
F
называется 
целевой функцией
, а переменные - 
параметрами функции
. Генетические алгоритмы "пришиваются" к 
данной задаче следующим образом. 
Параметры задачи являются генетическим материалом - генами. 
Совокупность генов составляет хромосому. Каждая особь обладает 
своей хромосомой, а, следовательно, своим набором параметров. 
Подставив параметры в целевую функцию, можно получить какое-то 
значение. То, насколько это значение удовлетворяет поставленным 
условиям, определяет характеристику особи, которая называется 
приспособленностью 
(fitness)
. 
Функция, 
определяющая 
приспособленность должна удовлетворять следующему условию: чем 
"лучше" особь, тем выше приспособленность. Генетические алгоритмы 
работают с популяцией как правило фиксированного размера, 
состоящей из особей, заданных при помощи способа, описанного выше. 
Особи "скрещиваются" между собой с помощью 
генетических 
операторов
(о том как происходит этот процесс – будет описано 
отдельно), и таким образом получается потомство, причем часть 
потомков заменяют представителей более старого поколения в 
соответствии со 
стратегией формирования нового поколения
. Выбор 

---

А.Е. Кононюк Дискретно-непрерывная математика 
28 
особей для скрещивания проводится согласно 
селективной стратегии 
(selection 
strategy)
. Заново сформированная популяция снова 
оценивается, затем выбираются наиболее достойные для скрещивания 
особи, которые скрещиваются между собой, получаются «дети»и 
занимают место «престарелых» индивидуумов и т.д. 
Все эта продолжается до тех пор пока не найдется особь, гены которой 
представляют оптимальный набор параметров, при которых значение 
целевой функции близко к максимуму или минимуму, либо равно ему. 
Останов работы ГА может произойти также в случае, если популяция 
вырождается, т.е. если практически нет разнообразия в генах особей 
популяции, либо если просто вышел лимит времени. Вырождение 
популяции называют 
преждевременной сходимостью (premature 
convergence)
. 
Может создаться впечатление, что ГА являются просто извращенным 
вариантом случайного поиска. Но приспособленность была введена 
совсем не зря. Дело в том, что она непосредственно влияет на шанс 
особи принять участие в скрещивании с последующим «рождением 
детей». 
Выбирая 
каждый 
раз 
для 
скрещивания 
наиболее 
приспособленных особей, можно с определенной степенью уверенности 
утверждать, что потомки будут либо не намного хуже, чем родители, 
либо лучше их. Приблизительно эту величину уверенности можно 
оценить с помощью теоремы шаблонов (теоремы шим).  
Теоретические аспекты ГА, следующие:
Представление данных в генах  
Генетические операторы  
Модели ГА  
Тестовые функции  
 Стратегии отбора и формирования нового поколения  
Где же применяются ГА? Всего применений очень много, поэтому 
приведенный список не является исчерпывающим.

Экстремальные задачи (нахождение точек минимума и 
минимума);

---

А.Е. Кононюк Дискретно-непрерывная математика 
29 

Задачи о кратчайшем пути;

Задачи компоновки;

Составление расписаний;

Аппроксимация функций;

Отбор (фильтрация) входных данных;

Настройка искусственной нейронной сети;

Моделирование искусственной жизни (Artificial life systems) ;

Биоинформатика (свертывание белков и РНК);

Игровые стратегии;

Нелинейная фильтрация;

Развивающиеся агенты/машины (Evolvable agents/machines);

Оптимизация запросов в базах данных 

Разнообразные задачи на графах (задача коммивояжера, 
раскраска, нахождение паросочетаний) 

Обучение искусственной нейронной сети 

Искусственная жизнь 
Некоторые разделы могут содержать подпункты. Так, например, 
экстремальные задачи включают в мебя целый класс задач линейного и 
нелинейного программирования.