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

В общем виде алгоритмы эволюционных вычислений, 
предназначенные для поиска оптимального решения некоторой 
задачи, могут быть представлены следующим образом. 
Альтернативные решения (или оптимизируемые объекты) трактуются 
как особи, степень приспособленности которых, или фитнесс-функция, 
явно или неявно определяется условиями задачи. Эти особи 
«эволюционируют» — к ним применяются «генетические операторы», 
такие как операторы скрещивания, мутации и редукции (селекции или 
отбора). Такие алгоритмы обычно состоят из следующих шагов. 
1.
Сгенерировать начальную популяцию (случайную 
совокупность неоптимальных решений). 
2.
Выбрать родительские пары. 
3.
Для каждой родительской пары с использованием оператора 

---

А.Е. Кононюк Дискретно-непрерывная математика 
46 
скрещивания породить потомство. 
4.
К порожденным особям применить оператор мутации, внеся 
случайные искажения. 
5.
Произвести отбор особей из популяции по значению их 
фитнесс-функции, применив оператор редукции. 
6.
Повторять шаги 2–5, пока не выполнится критерий остановки. 
Каждый шаг имеет разные реализации. Кроме того, особенности 
генетических операторов зависят от конкретной формы эволюционных 
вычислений. Так, особенностью генетических алгоритмов является то, 
что в них для представления решений используются битовые строки, 
трактуемые как генотипы (обычно состоящие из единственной 
хромосомы), и все генетические операторы применяются к битовым 
строкам. В эволюционных стратегиях операторы применяются к самим 
решениям, представленным в их естественной форме. Особенность же 
эволюционного (генетического) программирования состоит в том, что в 
них рассматривается оптимизация особых объектов — компьютерных 
программ. Рассмотрим каждый из шагов чуть подробнее на примере 
генетических алгоритмов (ГА). 
1.
Генерация начальной популяции обычно производится 
равномерно по пространству генотипов. Размер популяции — 
установочный параметр. 
2.
Выбор родительских пар может осуществляться различными 
способами. Обычно он включает два этапа: выбор первого 
родителя и формирование пары. При выборе первого родителя 
обычно используется один из следующих способов: 
с равной вероятностью выбирается любая особь из имеющейся 
популяции; 
особь выбирается случайно с вероятностью, пропорциональной 
значению фитнесс-функции; т. е. в этом случае значение 
фитнесс-функции сказывается не только на том, какие особи 
останутся в популяции в результате отбора, но и на том, 
сколько потомства они произведут. 
Выбор второго родителя осуществляется по одному из следующих 
критериев: 

независимо от уже выбранного родителя (т. е. второй родитель 

---

А.Е. Кононюк Дискретно-непрерывная математика 
47 
выбирается абсолютно так же, как и первый); этот вид отбора 
называется неселективным; 

на основе ближнего родства; 

на основе дальнего родства. 
В последних двух случаях выбор одного родителя влияет на выбор 
другого родителя: с большей вероятностью формируются пары, 
состоящие из особей, которые больше похожи друг на друга (т. е. ближе 
находятся в пространстве генотипов) при использовании ближнего 
родства или меньше похожи при использовании дальнего родства. В 
генетических алгоритмах в качестве меры близости обычно 
используется расстояние Хемминга, которое для двух битовых строк 
вычисляется как число позиций, в которых в двух строках стоят 
несовпадающие символы (т. е. в одной строке стоит 0, а в другой — 1). 
3.