Исследование структуры стандартного генетического алгоритма
Выполнил: ст. гр. ИТ-042 Хайрутдинов Д.Г.
Проверил: Сыркин И.С.
Цель работы – исследовать структуру стандартного генетического алгоритма; разработать структуру генетического алгоритма для решения задач оптимизации.
Задание:
Целевая функция:. Исследовать влияние размера популяции (от 20 до 100) и вероятности кроссовера (от 0 до 1) на скорость нахождения результата.
Таблица:
Population Number |
Total Fitness |
0 |
53560,34178 |
1 |
119994,06 |
2 |
174386,5338 |
3 |
183824,6851 |
4 |
184221,789 |
5 |
185817,9719 |
6 |
186104,6173 |
7 |
186343,6785 |
8 |
186285,042 |
9 |
186726,3302 |
10 |
194059,8456 |
11 |
197583,1577 |
12 |
219840,9408 |
13 |
222442,6285 |
14 |
223294,0094 |
15 |
223755,2299 |
16 |
223776,1063 |
17 |
225209,3654 |
18 |
225386,5339 |
19 |
225386,5267 |
20 |
225386,535 |
21 |
225390,4424 |
22 |
225394,6505 |
23 |
226252,0467 |
24 |
227918,1554 |
25 |
226379,5167 |
26 |
225605,1038 |
27 |
225605,9373 |
28 |
225607,7137 |
29 |
227233,8651 |
30 |
230687,0388 |
31 |
234841,1795 |
32 |
240390,2998 |
33 |
243804,5812 |
34 |
244239,932 |
35 |
244612,2791 |
36 |
244787,3914 |
37 |
244846,689 |
38 |
244979,8134 |
39 |
244991,6265 |
40 |
244993,975 |
41 |
244994,0001 |
42 |
244994,019 |
43 |
244994,1245 |
44 |
244994,0782 |
45 |
244994,1895 |
46 |
244994,2878 |
47 |
244994,4145 |
48 |
244994,4426 |
49 |
244994,4445 |
50 |
244994,4447 |
51 |
244994,4448 |
52 |
244994,445 |
53 |
244994,4471 |
54 |
244994,4463 |
55 |
244994,4469 |
56 |
244994,4469 |
57 |
244994,4469 |
58 |
244994,4487 |
59 |
244994,4495 |
60 |
244994,4565 |
61 |
244994,4582 |
62 |
244994,4573 |
63 |
244994,4599 |
64 |
244994,4634 |
65 |
244994,4647 |
66 |
244994,4649 |
67 |
244994,4655 |
68 |
244994,4655 |
69 |
244994,4663 |
70 |
244994,4665 |
71 |
244994,4665 |
72 |
244994,4667 |
73 |
244994,4668 |
74 |
244994,4668 |
75 |
244994,4668 |
76 |
244994,4668 |
77 |
244994,4669 |
78 |
244994,4669 |
79 |
244994,4669 |
80 |
244994,4669 |
81 |
244994,4669 |
82 |
244994,4669 |
83 |
244994,4669 |
84 |
244994,4669 |
85 |
244994,4669 |
86 |
244994,4669 |
87 |
244994,4669 |
88 |
244994,4669 |
89 |
244994,4669 |
90 |
244994,4669 |
91 |
244994,4669 |
92 |
244994,467 |
93 |
244994,467 |
94 |
244994,467 |
95 |
244994,467 |
График зависимости TotalFitness от PopulationNumber:
Результат исследования влияния начальных параметров в виде графиков:
Влияние размера популяции:
Чем больше размер популяции, тем выше скорость.
Влияние вероятности кроссовера:
Чем выше вероятность кроссовера, тем выше скорость.
Результаты решения задачи аналитическим методом и при помощи ГА, а также их процентное отличие:
глобальный максимум функции: |
||||
аналитическим методом |
12249,72333 |
|||
ГА |
12249,70658 |
|||
Расхождение |
0,000136722 |
% |
Вывод:
Использование ГА сильно повышает эффективность решения задач.
Задание:
Буровая вышка расположена в поле в 9 км от ближайшей точки шоссе. С буровой надо направить курьера в населённый пункт, расположенный по шоссе 15 км от упомянутой точки. Скорость курьера по полю 8 км/ч, а по шоссе 10 км/ч. К какой точке ему надо ехать, чтобы в кратчайшее время достичь населенного пункта.
Построить график зависимости средней приспособленности текущей популяции от поколения.
Исходный код программы:
decimal startLong = DateTime.Now.Ticks;
richTextBox2.Text = "";
int tochnost = Convert.ToInt32(Math.Pow(2, Convert.ToInt32(numericUpDown5.Value)));
double bad=0; //худшее время для одного поколения
double good = 1000; //лучшее время для одного поколения
double max=0; //максимальное время за все поколения
double min = 1000; //минимальное время за все поколения
int population =Convert.ToInt32(numericUpDown1.Value); //размер популяции
int generation =Convert.ToInt32(numericUpDown2.Value); //количество поколений
int amountGenes =1; //количество параметров
decimal mut = numericUpDown3.Value*100; //вероятность мутации
string[] phenotype = new string[population]; // совокупность генотипа
string[] pt = new string[population]; //вспомогательная совокупность генотипа
Random rand = new Random(DateTime.Now.Millisecond);
for(int i=0;i<population;i++) //заполнение массива случайными значениями параметров
{
for(int j=0;j<amountGenes;j++)
{
string str = Convert.ToString(rand.Next(0,tochnost),2);
char[] ch = str.ToCharArray();
for (int simv = 0; simv < numericUpDown5.Value - ch.Length; simv++) str = "0" + str;
phenotype[i] = phenotype[i]+str;
}
}
int a; //ген отвечающий за точку
double summa; //сумма времени по коэф каждой особи
int obrsumma; //обратная сумма
int r; //случайное число
double otbor; //отбор
int roditel1; //первый родитель
int roditel2; //второй родитель
double[] genes =new double[population]; //массив решений задачи
double[] koef_prisp = new double[generation]; //коэффициент приспособленность
for (int i = 0; i < generation; i++)
{
phenotype.CopyTo(pt, 0);
a = 0;
summa = 0;
obrsumma = 0;
r = 0;
for (int j = 0; j < population; j++)
{
char[] ch = pt[j].ToCharArray();
string osob="";
for (int simvol=0; simvol < numericUpDown5.Value; simvol++)
{
osob = osob + ch[simvol];
}
a = Convert.ToInt32(osob,2);
int a2 = Convert.ToInt32(a * 15 / (tochnost + 0.001 - 0.001));
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.