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

Страницы работы

Содержание работы

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

Выполнил: ст. гр. ИТ-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

%

Вывод:

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

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

Задание:

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

Похожие материалы

Информация о работе