Исследование влияния параметров генетического алгоритма на точность и скорость нахождения решения. Разработка структуры генетического алгоритма для решения задач оптимизации

Исследование структуры стандартного генетического алгоритма

Выполнил: ст. гр. ИТ-042 Хайрутдинов Д.Г.

Проверил: Сыркин И.С.

Цель работы – исследовать структуру стандартного генетического алгоритма; разработать структуру генетического алгоритма для решения задач оптимизации.

1. Исследование влияния параметров ГА на точность и скорость нахождения решения

Задание:

Целевая функция:. Исследовать влияние размера популяции (от 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	%

Вывод:

Использование ГА сильно повышает эффективность решения задач.

2. Разработка структуры ГА для решения задачи оптимизации

Задание:

Буровая вышка расположена в поле в 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));