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

Пример реализации генетического алгоритма на языке C++ 
Поиск в одномерном пространстве, без скрещивания. 
#include  
#include  
#include  
using namespace std; 
int main() 
{ 
const int N = 1000; 
int a[N]; 
//заполняем нулями 
fill(a, a+N, 0); 
for (;;) 
{ 
//мутация в случайную сторону каждого элемента: 
for (int i = 0; i < N; ++i) 
if (rand()%2 == 1) 
a[i] += 1; 
else 
a[i] -= 1; 
//теперь выбираем лучших, отсортировав по возрастанию...
sort(a, a+N); 
//... и тогда лучшие окажутся во второй половине массива. 
//скопируем лучших в первую половину, куда они оставили 
потомство, а первые умерли: 
copy(a+N/2, a+N, a /*куда*/); 
//теперь посмотрим на среднее состояние популяции. Как видим, 
оно всё лучше и лучше. 
cout << accumulate(a, a+N, 0) / N << endl; 

---

А.Е. Кононюк Дискретно-непрерывная математика 
60 
} 
 
2. 
Классический генетический
 
алгоритм и 
его релизация
 
2.1. Функция приспособленности и кодирование 
решений 
 
Родителем теории генетических алгоритмов (ГА) считается Холланд 
(J. Holland), чья работа «Adaptation in Natural and Artificial Systems» 
(1975), стала классикой в этой области. В ней Холланд впервые ввел 
термин «генетический алгоритм». Сейчас описанный там алгоритм 
называют «классический ГА» (иногда «канонический ГА», canonical 
GA), а понятие «генетические алгоритмы» стало очень широким, и 
зачастую к ним относятся алгоритмы, сильно отличающиеся от 
классического ГА.
Ученики Холланда Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг 
(David E. Goldberg) внесли огромный вклад в развитие ГА. На книгу 
Голдберга «Genetic algorithms in search optimization and machine 
learning» (1989), ссылаются авторы практически каждой работы по этой 
теме.
Как уже было сказано выше, генетические алгоритмы работают по 
аналогии с природой. Они оперируют с совокупностью «особей», 
представляющих собой строки, каждая из которых кодирует одно из 
решений задачи. Приспособленность особи оценивается с помощью 
специальной функции. Наиболее приспособленные получают шанс 
скрещиваться и давать потомство. Наихудшие особи удаляются и не 
дают потомства. Таким образом, приспособленность нового поколения 
в среднем выше предыдущего.

---

А.Е. Кононюк Дискретно-непрерывная математика 
61 
Итак, пусть перед нами стоит задача оптимизации. Варьируя некоторые 
параметры, к примеру, если решать задачу размещения, координаты 
размещаемых элементов, нужно найти такую их комбинацию, чтобы 
минимизировать занимаемую площадь. Такую задачу можно 
переформулировать как задачу нахождения максимума некоторой 
функции 
f
(
x
1
, 
x
2
, …, 
x
n
). Эта функция называется 
функцией 
приспособленности
(fitness function) и используется для вычисления 
приспособленности особей. Она должна принимать неотрицательные 
значения, а область определения параметров должна быть ограничена.
Если нам, к примеру, требуется найти минимум некоторой функции, то 
достаточно перенести область ее значений на положительную область, а 
затем инвертировать. Таким образом, максимум новой функции будет 
соответствовать минимуму исходной.
В генетических алгоритмах никак не используются такие свойства 
функции, как непрерывность, дифференцируемость и т. д. Она 
подразумевается как устройство (
blackbox
), которое на вход получает 
параметры, а на выход выводит результат.
Теперь обратимся к кодировке набора параметров. Закодируем каждый 
параметр строкой битов. Если он принимает непрерывное множество 
значений, то выберем длину строки в соответствии с требуемой 
точностью. Таким образом, параметр сможет принимать только 
дискретные значения (этих значений будет степень 2), в некотором 
заданном диапазоне.
Например, пусть переменная 
x
k
принадлежит отрезку [
x
min
, 
x
max
]. 
Закодируем ее бинарной строкой из 
l
битов. Тогда строка 
s
k
обозначает 
следующее значение переменной 
x
k
:
x
k
= 
x
min
+ 
s
k
(
x
max
− 
x
min
) ⁄ 2
l
если в формуле 
s
k
обозначает значение бинарного числа, кодируемого 
этой строкой.
Если же некоторый параметр принимает конечное количество значений, 
к примеру, целые от 0 до 1000, то закодируем его бинарной строкой 

---

А.Е. Кононюк Дискретно-непрерывная математика 
62 
достаточной длины, в данном случае 10. Лишние 23 строки могут 
повторять уже закодированные значения параметра, либо они могут 
быть доопределены в функции приспособленности как «худшие», т. е. 
если параметр кодируется одной из этих строк, то функция принимает 
заведомо наименьшее значение.
Итак, мы определили для каждого параметра строку, кодирующую его. 
Особью будет называться строка, являющаяся конкатенацией строк 
всего упорядоченного набора параметров:
101100 11001011 01101100 1100 1 11101 
| x
1
| x
2
| | | | x
n
| 
Приспособленность особи высчитывается следующим образом: строка 
разбивается на подстроки, кодирующие параметры. Затем для каждой 
подстроки высчитывается соответствующее ей значение параметра, 
после чего приспособленность особи получается как значение функции 
приспособленности от полученного набора.
Вообще говоря, от конкретной задачи зависят только такие параметры 
ГА, как функция приспособленности и кодирование решений. 
Остальные шаги для всех задач производятся одинаково, в этом 
проявляется универсальность ГА.