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

Оператор мутации
призван внести разнообразия в наш островок 
цифровой жизни, под его действием у хромосомы изменяется 
произвольный ген. 
Fitness-функция
: Как и в жизни – не приспособленные виды должны 
погибать, «чистить» нашу популяцию будет последняя функция, 
называемая функцией приспособления, или Fitness-функцией. 
Для каждой хромосомы эта функция возвращает число, обратно 
пропорциональное «приспособленности» этой хромосомы, на нее 
накладываются условия: 
Значение Fitness от идеального решения = 0 
Это основное условие, но все же желательно подобрать функцию так, 
чтобы ее значение росло, по мере удаления решения от идеального. 
Иными словами – чтобы она имела только один минимум. 
Теперь можно сформулировать вариант алгоритма 
1. Обозначить номер эпохи = 0, создать популяцию хромосом, в генах 
которых будет произвольная, не противоречащая задаче, информация 
2. Посчитать приспособленность популяции 
3. Выбрать из популяции особь А 
4. С вероятностью P(скрещивания) выбрать особь B и применить 
оператор кроссовера, результирующую особь занести в новую 
популяцию. 
5. С вероятностью P(мутации) выполнить мутацию произвольной 
особи, результирующую особь занести в новую популяцию 
6. Выполнить операции 3,4,5 n раз, где n >= размера популяции 
7. Создать новую популяцию из лучших особей существующей и 
только что сформированной популяции 
8. Увеличить номер текущей эпохи 
9. Если результат работы удовлетворителен – остановка алгоритма, 
иначе – переход к шагу 2. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
345 
Генетический алгоритм не является строго детерминированным, 
например, мы можем сначала выполнить скрещивание всех особей, а 
потом мутацию (в рамках данной задачи именно этот подход оказался 
более эффективным). Итак, попробуем, на основе описанного, решить 
поставленную задачу. Сначала нам понадобится определить 
хромосому, которая и будет хранилищем информации о генах. 
1.
public
class
Chromosome : IComparable
2.
{ 
3.
public
double
[] gens; 
4.
static
Random
random = 
new
Random
(); 
5.
6.
public
Chromosome() 
7.
{ 
8.
this
.gens = 
new
double
[3]; 
9.
10.
for
(
int
i = 0; i < 3; i++) 
11.
{ 
12.
this
.gens[i] = 
random.NextDouble() * 100; 
13.
} 
14.
this
.fit = fitness(
this
); 
15.
} 
16.
public
int
CompareTo(
object
obj) 
17.
} 
* This source code was highlighted with Source Code 
Highlighter.
Значение 100 выбрано для примера, это не ограничит общности, даже 
если искомая парабола будет иметь кофээфициенты >100 
Отметим метод CompareTo, позволяющий нам сортировать списки 
объектов Chromosome.
1.
public
class
Population

---

А.Е. Кононюк Дискретно-непрерывная математика 
346 
2.
{ 
3.
Random
random = 
new
Random
(); 
4.
public
List
population; 
5.
public
int
count; 
6.
public
double
crossProbability; 
7.
public
double
MutationProbability; 
8.
public
int
age; 
9.
10.
public
Population() 
11.
{ 
12.
for
(
int
i = 0; i < 5000; i++) 
13.
{ 
14.
this
.population.Add(
new
Chromosome()); 
15.
} 
16.
} 
17.
18.
public
void
GoToNextGeneration() 
19.
{ 
20.
Chromosome chromosome; 
21.
for
(
int
i = 0; i < count; i++) 
22.
{ 
23.
chromosome = population[i]; 
24.
25.
if
(random.NextDouble() < 
crossProbability) 
26.
{ 
27.
population.Add(Cross(ch
romosome,population[random.Next(count)])); 
28.
} 
29.
} 
30.
31.
for
(
int
i = 0; i < 
population.Count; i++) 
32.
{ 
33.
if
(random.NextDouble() < 
MutationProbability) 
34.
{ 
35.
population.Add(Mutate(p
opulation[i])); 

---