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

А.Е. Кононюк Дискретно-непрерывная математика 
347 
36.
} 
37.
} 
38.
39.
population.Sort(); 
40.
population.RemoveRange(count,po
pulation.Count-count); 
41.
42.
age++; 
43.
} 
44.
45.
Chromosome Cross(Chromosome a, 
Chromosome b) 
46.
Chromosome Mutate(Chromosome a) 
47.
double
Fitness(Chromosome a) 
48.
} 
* This source code was highlighted with Source Code 
Highlighter.
Вот она, эволюция в двадцати строчках! Это и будет сердцем нашей 
программы. 
В первой части мы получаем потомство от уже существующей 
популяции, и добавляем его в конец списка, т.е. все «дети» будут 
находится подномерами большими чем count. 
Второй шаг – мутация, было бы логично мутировать саму хромосому, а 
не добавлять мутировавший клон, но в этом случае мы теряем 
содержащееся в исходной хромосоме решение, а оно может быть 
лучшим в популяции. 
Наконец, в конце мы сортируем всю нашу получившуюся популяцию 
по возрастанию Fitness функции, (следовательно – по убыванию 
правильности решения) удаляем наименее «приспособленные» 
хромосомы, и увеличиваем номер текущей эпохи. 
Давайте рассмотрим, что же представляют собой три последние 
функции, производящии операции над нашими хромосомами? 
1.
Chromosome Cross(Chromosome a, Chromosome b)
2.
{ 

---

А.Е. Кононюк Дискретно-непрерывная математика 
348 
3.
double
[] pair = 
new
double
[3]; 
4.
5.
for
(int i = 0; i < 3; i++) 
6.
{ 
7.
if
((random.
Next
() % 2) == 0) 
8.
{ 
9.
pair[i] = a.Gens[i] + (b.Gens[i] 
- a.Gens[i]) * 0.1; 
10.
} 
11.
else
12.
{ 
13.
pair[i] = b.Gens[i] - 
(b.Gens[i] - a.Gens[i]) * 0.1; 
14.
} 
15.
} 
16.
17.
Chromosome result = 
new
Chromosome(pair); 
18.
return
result; 
19.
} 
* This source code was highlighted with Source Code 
Highlighter.
Реализация оператора кроссовера может быть достаточно 
разнообразной, и, обычно, подбирается под конкретную задачу. Здесь, 
с вероятностью 0.5, для каждого гена, потомок получит его от первого 
родителя или, с такой же вероятностью, от второго родителя. 
Поправка (b.Gens[i] — a.Gens[i]) * 0.1 сделана чтобы както 
разнообразить популяцию новыми генотипом. 
1.
Chromosome Mutate(Chromosome a)
2.
{ 
3.
double
[] pair = (
double
[])a.Gens.Clone(); 
4.
int
geneNum = random.Next(3); 
5.
pair[geneNum] = random.NextDouble() * 
100; 

---

А.Е. Кононюк Дискретно-непрерывная математика 
349 
6.
return
new
Chromosome(pair, 
a.chromosomeSettings); 
7.
} 
* This source code was highlighted with Source Code 
Highlighter.
Как и обещано, оператор мутации изменяет один произвольный ген. 
Взглянем на самое интересное, как же мы будем определять, насколько 
близка наша хромосома к идеальному решению? 
1.
double
GetFitness(Chromosome a)
2.
{ 
3.
double
result = 0; 
4.
double
temp; 
5.
for
(
int
i = 0; i < funcLength; i++) 
6.
{ 
7.
temp = 
Math
.Abs(Func(i, a.Gens) - 
funcArray[i]); 
8.
result += temp; 
9.
} 
10.
11.
return
result; 
12.
} 
13.
14.
double
Func(
double
x, 
double
[] gens) 
15.
{ 
16.
double
result = 0; 
17.
for
(
int
i =2; i >= 0; i--) 
18.
{ 
19.
result += gens[2-i] * 
Math
.Pow(x, i); 
20.
} 
21.
return
result; 
22.
} 
* This source code was highlighted with Source Code 
Highlighter.

---

А.Е. Кононюк Дискретно-непрерывная математика 
350 
Массив funcArray получается сканированием картинки снизу вверх по 
столбцам, каждый столбец – индекс массива, высота первой найденной 
черной точки в столбце – значение. 
Функция Func – возвращает значение уравнения 2й степени в точке x, с 
коэффициентами из массива gens 
Получается Fitness – это сумма «погрешностей», для каждой точки 
нашей параболы, которая есть на рисунке. Такая функция не имеет 
единственный минимум, но, тем не менее, обеспечивает достаточную 
сходимость алгоритма. 
Результат: 
При количестве хромосом в популяции = 5000, на 25ом поколении мы 
получаем достаточно близкое сходство. 
Данный алгоритм можно расширить на кривые любого порядка =) 

---

А.Е. Кононюк Дискретно-непрерывная математика 
351