Генетичні алгоритми

Отож сьогоднішня тема “Генетичні алогоритми”,  тема дійсно цікава особливо для людей які тільки починають вивчати алгоритми тим більше тому що цей алгоритм дозволяє покрити велику частину задач серед яких:

• Математичні завдання
• Задачі на графи
• Складання розлкаду
• Задача Комівояжера
• Створення штучного інтелекту
• та ніші.

Тобто знаючи принцип вирішення задач генетичним алгоритмом, ви зможете його реалізувати для того, що вам потрібно. Звичайно він не замінить вам знання алгоритмів пошуку або сортування, але ці алгоритми я планую покрити в наступних постах, так що підписуйтесь і слідкуєте за оновленнями на блозі.
Робота алгоритму дуже близька до того що ми звикли бачити в природі, тобто виживають найсильніші/найрозумніші і відповідно їхні потомки вбирають все найкраще від батьків стаючи при тому ще сильнішими, витривалішими і тд. Так само буде в нас Ми маємо якусь задачу для неї ми генеруємо випадкові варіанти розвязків і в результаті відбору та схрешування найкращих отримуємо необхідний нам результат.
Отож маємо основні кроки:

1. формування початкової популяції
2. відбір найкращих
3. формування потомства на основі найкращих
4. перехід на крок 2

Перевірка на те чи хоть хтось з популяції задовільняє необіхдну умову відбувається на кроці 2.

Маємо задачу a+2b+3c+4d = 30

Клас(ген) який описує змінні для вирішення задачі досить простий і виглядає наступним чином:

1: class Gene

2: {

3:     public Gene(int A, int B, int C, int D)

4:     {

5:         this.A = A;

6:         this.B = B;

7:         this.C = C;

8:         this.D = D;

9:     }

10:  

11:     public Gene()

12:     {

13:     }

14:  

15:     public int A { get; set; }

16:     public int B { get; set; }

17:     public int C { get; set; }

18:     public int D { get; set; }

19:  

20:     public float Fittnes

21:     {

22:         get { return ((A + 2 * B + 3 * C + 4 * D) - 30); }

23:     }

24:  

25:     public int ParentIndex

26:     {

27:         get

28:         {

29:             return (int)((1 / (Fittnes + 30)) * 1000);

30:         }

31:     }

32: }

При запуску програми випадково генеруємо початкову популяцію:

1: private static IEnumerable<Gene> GetBaseGenes()

2: {

3:    List<Gene> randomGenes = new List<Gene>();

4:    for (int i = 0; i < 100; i++)

5:    {

6:        randomGenes.Add(new Gene(rand.Next(30), rand.Next(30), rand.Next(30), rand.Next(30)));

7:    }

8:    return randomGenes;

9: }

до прикладу отримаємо таку:

	a	b	c	d
I	2	9	12	25
II	20	1	16	10
III	4	6	24	9
IV	8	19	18	4
V	21	12	8	5

Підставляючи ці дані в нашу формулу(метод Fittness) отримаємо слідуючі результати

	a	b	c	d	fittnes
I	2	9	12	25	126
II	20	1	16	10	80
III	4	6	24	9	94
IV	8	19	18	4	86
V	21	12	8	5	59

Отож перший варіант найменш підходящий а останній найкращий відповідно настпне покоління має бути сформовене в основному з найкращих генів але виключати найгірші гени повністью не варто так як вони дають нам додаткові шанси випадкового співпадіння і відповідно вирішення задачі.
Для кожного гену з популяції ми вираховуємо наскільки він там підходить, і відповідно якщо він підходить краще ніж інші то ймовірність того що саме його гени попадуть в наступне покоління має бути вищою. Для цього я додав так званий “Батьківський індекс” який вирахував за наступною формулою:

1 / (fittnes + 30) * 1000

для першого гена батьківський індекс буде 7 а для останнього найбільш підходящого 16. На базі ціього індексу заповнюю простий маси в якому будуть числа від 1 до 5 кількість чисел відповідатиме батьківському індексу і відповідно чим більший “батьківський індекс” тим більше елементів з номером гену:

1 1 1 1 1 1 1 ……… 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
(так як ген 5 найбільш підходящий чисел які вказують на нього більше)

Наступним кроком буде сформувати випадковим чином таблицю на базі цього масиву

mather	father
5	3
4	5
1	5
2	4
2	5

Далі схрещуємо елементи

Схрещення буде відбуватись одним з наступних чинів:

• mother.A     father.B     father.C    father.D
• mother.A     mother.B   father.C    father.D
• mother.A     mother.B   mother.C  father.D
• mother.A     father.B     mother.C  father.D

В результаті хсрещування двох останніх генів з попередньої колекції ми отримаємо:

• 8

  12

  8

  5

  або

• 8

  19

  8

  5

  …..

Код схрещення в моєму випадку виглядає наступним чином:

1: Gene[] array = parents.ToArray();

2:  

3: List<int> left = new List<int>();

4: List<int> right = new List<int>();

5:  

6: for (int i = 0; i < parents.Count; i++)

7: {

8:     left.Add(rand.Next(0, parents.Count));

9:     right.Add(rand.Next(0, parents.Count));

10: }

11:  

12: List<Gene> childrens = new List<Gene>();

13:  

14: for (int i = 0; i < parents.Count; i++)

15: {

16:     Gene children = new Gene();

17:  

18:     switch (rand.Next(1, 4))

19:     {

20:         case 1:

21:             {

22:                 children.A = array[left[i]].A;

23:                 children.B = array[right[i]].B;

24:                 children.C = array[right[i]].C;

25:                 children.D = array[right[i]].D;

26:                 break;

27:             }

28:  

29:         case 2:

30:             {

31:                 children.A = array[left[i]].A;

32:                 children.B = array[left[i]].B;

33:                 children.C = array[right[i]].C;

34:                 children.D = array[right[i]].D;

35:                 break;

36:             }

37:         case 3:

38:             {

39:                 children.A = array[left[i]].A;

40:                 children.B = array[left[i]].B;

41:                 children.C = array[left[i]].C;

42:                 children.D = array[right[i]].D;

43:                 break;

44:             }

45:         case 4:

46:             {

47:                 children.A = array[left[i]].A;

48:                 children.B = array[right[i]].B;

49:                 children.C = array[left[i]].C;

50:                 children.D = array[right[i]].D;

51:                 break;

52:             }

53:     }

54:     parents[i] = children;

55:     childrens.Add(children);

56: }

 

Все це чудово працює але досить часто не дає кінцевого вирішення задачі бо в кінці кінців все зводить до того що після багатьох схрещувань ми отримуємо ідентичні набори у всіх генах і відповідно ми зависаємо на якомусь варіанті відповіді яке досить близко до того що нам треба але не є кінцевим. В такому випадку використовують мутацію. Фактично іноді при створенні нового покоління один з генів замінюють на випадково згенерований в надії на те що він дасть кращий результат.

1: int next = rand.Next(0, 1000);

2:  

3: if (next > 900)

4: {

5:     childrens[0].A = rand.Next(0, 30);

6: }

7:  

8: next = rand.Next(0, 1000);

9: if (next < 900 && next > 820)

10: {

11:     childrens[4].D = rand.Next(0, 30);

12: }

13: next = rand.Next(0, 1000);

14: if (next < 700 && next > 800)

15: {

16:     childrens[3].B = rand.Next(0, 30);

17: }

18: next = rand.Next(0, 1000);

19: if (next < 100 && next > 20)

20: {

21:     childrens[2].C = rand.Next(0, 30);

22: }

Як бачите я реалізував це дуже просто якщо на цьому кроці рандомно буде згенеровано число яке входить в межі які зазначені іфками то ми замінюємо один або декілька генів.
Відповідно визначити на перед яким буде наступне покоління практично не можливо, тому що попри те що воно буде базуватись на найкращих особах популяції воно може містити мутації в своїх генах.
Після цього знову проганяємо перевіряємо нове покоління на те чи не містить воно вирішення задачі якщо ні то знову відбираємо найкращих, схрещуємо, мутуємо і знову по колу доки не отримаємо результат який буде задовільняти необіхдну нам задачу.

А ось і результат:

1: using System;

2: using System.Collections;

3: using System.Collections.Generic;

4: using System.Linq;

5:  

6: namespace DiafantEqGaMegaSmpl

7: {

8:     class Gene

9:     {

10:         public Gene(int A, int B, int C, int D)

11:         {

12:             this.A = A;

13:             this.B = B;

14:             this.C = C;

15:             this.D = D;

16:         }

17:  

18:         public Gene()

19:         {

20:         }

21:  

22:         public int A { get; set; }

23:         public int B { get; set; }

24:         public int C { get; set; }

25:         public int D { get; set; }

26:  

27:         public float Fittnes

28:         {

29:             get { return ((A + 2 * B + 3 * C + 4 * D) - 30); }

30:         }

31:  

32:         public int ParentIndex

33:         {

34:             get

35:             {

36:                 return (int)((1 / (Fittnes + 30)) * 1000);

37:             }

38:         }

39:     }

40:  

41:     class Program

42:     {

43:         static Random rand = new Random(DateTime.Now.Millisecond);

44:  

45:         static void Main(string[] args)

46:         {

47:             IEnumerable<Gene> population = GetBaseGenes();

48:             for (int i = 0; i < 1000; i++)

49:             {

50:                 foreach (var baseGene in population)

51:                 {

52:                     if ((int)baseGene.Fittnes == 0)

53:                     {

54:                         Console.WriteLine("--Done--");

55:                         Console.WriteLine("A-{0} \t B-{1} \t C-{2} \t D-{3} \t Fittnes-{4} \t PrentIdx-{5}", baseGene.A, baseGene.B, baseGene.C, baseGene.D, baseGene.Fittnes, baseGene.ParentIndex);

56:                         Console.ReadLine();

57:                     }

58:                     else

59:                     {

60:                         Console.WriteLine("A-{0} \t B-{1} \t C-{2} \t D-{3} \t Fittnes-{4} \t PrentIdx-{5}", baseGene.A, baseGene.B, baseGene.C, baseGene.D, baseGene.Fittnes, baseGene.ParentIndex);

61:                     }

62:                 }

63:                 population = CreateChildrens(population);

64:             }

65:             Console.WriteLine("Solution not found :( ");

66:             Console.ReadLine();

67:         }

68:  

69:         private static IEnumerable<Gene> CreateChildrens(IEnumerable<Gene> population)

70:         {

71:             Gene[] genes = population.ToArray();

72:  

73:             List<int> parents = new List<int>();

74:  

75:             //sequence generation.

76:             for (int i = 0; i < genes.Count(); i++)

77:             {

78:                 for (int j = 0; j < (int)genes[i].ParentIndex; j++)

79:                 {

80:                     parents.Add(i);

81:                 }

82:             }

83:  

84:             List<Gene> bestFits = new List<Gene>();

85:  

86:             for (int i = 0; i < genes.Count(); i++)

87:             {

88:                 int next = rand.Next(0, parents.Count);

89:                 bestFits.Add(genes[parents[next]]);

90:             }

91:  

92:             return CreatenewPopulation(bestFits);

93:         }

94:  

95:         private static List<Gene> CreatenewPopulation(List<Gene> parents)

96:         {

97:             Gene[] array = parents.ToArray();

98:  

99:             List<int> left = new List<int>();

100:             List<int> right = new List<int>();

101:  

102:             for (int i = 0; i < parents.Count; i++)

103:             {

104:                 left.Add(rand.Next(0, parents.Count));

105:                 right.Add(rand.Next(0, parents.Count));

106:             }

107:  

108:             List<Gene> childrens = new List<Gene>();

109:  

110:             for (int i = 0; i < parents.Count; i++)

111:             {

112:                 Gene children = new Gene();

113:  

114:                 switch (rand.Next(1, 4))

115:                 {

116:                     case 1:

117:                         {

118:                             children.A = array[left[i]].A;

119:                             children.B = array[right[i]].B;

120:                             children.C = array[right[i]].C;

121:                             children.D = array[right[i]].D;

122:                             break;

123:                         }

124:  

125:                     case 2:

126:                         {

127:                             children.A = array[left[i]].A;

128:                             children.B = array[left[i]].B;

129:                             children.C = array[right[i]].C;

130:                             children.D = array[right[i]].D;

131:                             break;

132:                         }

133:                     case 3:

134:                         {

135:                             children.A = array[left[i]].A;

136:                             children.B = array[left[i]].B;

137:                             children.C = array[left[i]].C;

138:                             children.D = array[right[i]].D;

139:                             break;

140:                         }

141:                     case 4:

142:                         {

143:                             children.A = array[left[i]].A;

144:                             children.B = array[right[i]].B;

145:                             children.C = array[left[i]].C;

146:                             children.D = array[right[i]].D;

147:                             break;

148:                         }

149:                 }

150:                 parents[i] = children;

151:                 childrens.Add(children);

152:             }

153:  

154:             int next = rand.Next(0, 1000);

155:  

156:             if (next > 900)

157:             {

158:                 childrens[0].A = rand.Next(0, 30);

159:             }

160:  

161:             next = rand.Next(0, 1000);

162:             if (next < 900 && next > 820)

163:             {

164:                 childrens[4].D = rand.Next(0, 30);

165:             }

166:             next = rand.Next(0, 1000);

167:             if (next < 700 && next > 800)

168:             {

169:                 childrens[3].B = rand.Next(0, 30);

170:             }

171:             next = rand.Next(0, 1000);

172:             if (next < 100 && next > 20)

173:             {

174:                 childrens[2].C = rand.Next(0, 30);

175:             }

176:  

177:             return childrens;

178:         }

179:  

180:         private static IEnumerable<Gene> GetBaseGenes()

181:         {

182:             List<Gene> randomGenes = new List<Gene>();

183:             for (int i = 0; i < 100; i++)

184:             {

185:                 randomGenes.Add(new Gene(rand.Next(30), rand.Next(30), rand.Next(30), rand.Next(30)));

186:             }

187:             return randomGenes;

188:         }

189:     }

190: }

ПС все написано максимально просто і не претендує ні на які нагороди за мега дизайн тому сприймайте як є, будуть питання пишіть..