1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
| import numpy as np
import random
class Individ:
def __init__(self):
self.A=np.random.randint(0,2,30) #Объявляем атрибут "А" нашего индивида (это будет сама строка 010..101)
self.fit=0 #Объявляем атрибут "живучести" индивида (это будет сумма элементов нашей строки 010..101) (пока присвоим ей значение 0)
def fitness(self): #Эта функция нашего индивида как раз отвечает за подсчёт "живучести" (считает сумму)
summa=0
for i in range(30): #Цикл в 30 итераций (i принимает значения от 0 до 29)
summa=summa+self.A[i] #Сумма вбирает поочерёдно в себя все элементы строки (A[0], A[1], ... A[29])
self.fit=summa
def info(self): #Функция вывода на экран индивида. В программе мы её не используем.
print(self.A) #Осталась со времени отладки. Важно заметить, что мы тут используем
self.fitness() #функцию fitness(), чтобы она подсчитала нам сумму ряда.
print(self.fit) #прежде чем выводить этот самый fit на экран.
class Population:
def __init__(self):
self.B = [] #Объявляем массив "В", в котором будем хранить популяцию из 10 индивидов.
for i in range(10): #Цикл
c=Individ() #В переменную "с" запихнулся (срандомился) новёхонький уникальненький индивид. (на каждой итерации цикла новый)
self.B.append(c) #А тут мы добавляем i-го уникального индивида к массиву (заполняем нашу популяцию)
def info(self): #Функция вывода популяции на экран.
for i in range(10): #Выводим все 10 строк (все 10 индивидов популяции)
for j in range(30): #Выводим поочерёдно каждый элемент строки "А" нашего индивида.
print(self.B[i].A[j], end ="") # i-й элемент массива индивидов "В". И j-й элемент строки "A" этого самого i-го индивида.
print("=",end="") #Важно понять структуру "self.B[i].A[j]". Мы тут залезаем внутрь одного массива в гости к другим массивам. self - вместо него будет имя нашей популяции "pop1". У популяции есть атрибут "B" - массив индивидов. i-й элемент этого массива (B[i]), являясь индивидом, будет иметь все атрибуты класса "индивид", а именно массив из 30 нулей и единиц ("А"). И доступ от атрибута одного класса к атрибуту "внутреннего" класса осуществляется через точку "."
self.B[i].fitness() #Вникаем в значение точек. self(имя экземпляра класса (pop1) ТОЧКА B[i] (i-й индивид популяции) ТОЧКА fitness() (функция считающая сумму и кидающая значение этой суммы в переменную self.fit)
print(self.B[i].fit) #Принтим значение fit i-го индивида популяции.
pop1=Population() #Создаём экземпляр класса. Т.е. создаём нашу популяцию из 10 рандомных индивидов
pop1.info() #Выводим её на экран нашей клёвой функцией вывода.
Mother = Individ() #Инициализируем переменные, с которыми будем работать: маму, папу, двух сыночков..
Father = Individ() #..и массив индивидов "Родители+Дети" в котором будем хранить
Son1 = Individ() #10 родителей и 10 их детишек (по два сына у каждой из пяти пар родителей).
Son2 = Individ()
ParAndSons = []
for j in range(20): #Тут мы "придаём форму" нашему массиву "Родителей и детей". Инициализируем его рандомными индивидами.
ParAndSons.append(Individ()) #Чтобы в дальнейшем иметь возможность напрямую работать с этим массивом с помощью наших атрибутов (А, fit)
#Рандомные значения, которыми мы забили этот массив, нам не помешают. Т.к. мы поэлементно все элементы этого массива забьём актуальными данными вручную по ходу программы.
print("\n") #Отступаем две строчки после вывода нашей стартовой популяции. И да начнётся.. ЕСТЕСТВЕННЫЙ ОТБОР!!!11
for p in range(60): #Это наш основной цикл. Сейчас стоит 60 итераций. Т.е. мы ставим ограничение в 60 поколений.
#За них мы должны успеть вырастить целое поколение мутантов-переростков. Мы всегда можем увеличить количество поколений и увеличить вероятность нахождения ответа. Или уменьшить, если наш механизм скрещиваний очень крутой, и мы очень быстро (за 20-30 поколений) находим ответ.
for i in range(10): #Заносим в первые 10 элементов массива "Отцы и дети" всю нашу входную популяцию.
for j in range(30):
ParAndSons[i].A[j]=pop1.B[i].A[j]
tt=0 #Счётчик, который нужён для реализации небанального скрещивания.
for s in range(0,10,2): #Цикл. От 0 до 10 с шагом 2. Т.е. тут мы берём 5 пар родителей.
for j in range(30): #Как ты заметил, цикл из 30 итераций есть практически везде. Т.к. все операции мы проводим поэлементно (большая честь каждому нолику и каждой единичке).
Mother.A[j]=pop1.B[tt+5].A[j] #Пусть мамами у нас будут последние 5 индивидов нашей популяции (т.к. они у нас в последствии всегда будут отранжированы (наши популяции), беря последние 5, мы тем самым берём лучших представителей и с ними работаем. Чего с посредственностей-то взять, ну.
Father.A[j]=pop1.B[random.randint(0,9)].A[j] #А папами пусть будет любой случайный индивид из нашей популяции. (использовали рандом от 0 до 9). Кстати, если делать совсем по-умному, то надо и папу и маму выбирать случайным образом. Но вероятность выбора в качестве родителя у индивида должна быть тем выше, чем выше у него живучесть (fit). Предлагаю (после того как со всем остальным хорошенько разберёшься) тебе подумать о том, как это можно сделать. Ничего особенно сложного в этом и нет на самом деле.
tt=tt+1 # Двигаем наш счётчик ручками.
ran=random.random()
if (ran>0.8): #А это наши механизмы скрещивания.
for n in range(5): #Берём первые 5 элементов у папы и у мамы (для сына1 и сына2 соответственно).
Son1.A[n]=Father.A[n]
Son2.A[n]=Mother.A[n]
for n in range(5,30): #И берём остальные 25 элементов у мамы и у папы для сына1 и сына2 соответственно (крест-накрест)
Son1.A[n]=Mother.A[n]
Son2.A[n]=Father.A[n]
if ((ran>0.6) & (ran <=0.8)): #Тот же самый крест-накрест, только теперь самого тривиального вида.
for n in range(15): #Первые 15 у папы и вторые 15 у мамы для сына1.
Son1.A[n]=Father.A[n] #И первые 15 у мамы и вторые 15 у папы для сына2.
Son2.A[n]=Mother.A[n]
for n in range(16,30):
Son1.A[n]=Mother.A[n]
Son2.A[n]=Father.A[n]
if ((ran <0.6) & (ran >=0.4)): #Крест накрест. Зеркален первому методу скрещивания. (только не первые 5 элементов берём, а последние)
for n in range(25):
Son1.A[n]=Father.A[n]
Son2.A[n]=Mother.A[n]
for n in range(25,30):
Son1.A[n] = Mother.A[n]
Son2.A[n] = Father.A[n]
if ((ran <0.4) & (ran>=0.3)): #Срединный крест-накрест + инверсия.
for n in range(15):
Son1.A[n]=Father.A[14-n]
Son2.A[n]=Mother.A[14-n]
for n in range(15,30):
Son1.A[n]=Mother.A[44-n]
Son2.A[n]=Father.A[44-n]
if (ran<0.3): #Тут берём для сына1 первые 15 элементов папы + первые 15 элементов мамы.
for n in range(15): #А для сына2 берём вторые 15 элементов мамы + вторые 15 элементов папы.
Son1.A[n]=Father.A[n]
Son1.A[n+15]=Mother.A[n]
Son2.A[n]=Mother.A[n+15]
Son2.A[n+15]=Father.A[n+15]
for i in range(30): #Тут мы закидываем наших получившихся в результате скрещивания s-той пары родителей Сына1 и Сына2 во вторую половину массива "Отцы и дети".
ParAndSons[10+s].A[i]=Son1.A[i]
ParAndSons[11+s].A[i]=Son2.A[i]
for r in range(17,18): #Это мутации. Чтобы доказать крутость нашего скрещивания мы минимизируем мутации.
for w in range(30): #Т.к. при большой вероятности мутации верное решение находится даже при совершенно неработающем механизме скрещивания.
if random.random()<0.00001: #Поэтому мы мутируем только одного (17-го) индивида. Т.е. мы с вероятностью 0.00001
if ParAndSons[r].A[w]==1: #инвертируем каждую из его 30 нулей и единиц.
ParAndSons[r].A[w]=0 #((При решении задачи с уравнением будем мутировать 3-5 индивидов с вероятностью 0.01-0.05 примерно.))
if ParAndSons[r].A[w]==0:
ParAndSons[r].A[w]=1
for i in range(20): #Это важно. Далее мы будем ранжировать массив отцов и детей в порядке возрастания живучести (суммы (fit)).
ParAndSons[i].fitness() #Поэтому мы сначала должны посчитать для всех 20 индивидов в этом массиве это самое fit с помощью нашей клёвой функции fitness().
for m in range(len(ParAndSons)-1,0,-1): #Ранжирование (методом пузырька). Лёгкие всплывают наверх, а тяжёлые оказываются внизу. (вместо "len(ParAndSons)-1" можно просто написать 19, т.к. мы знаем длину нашего массива.) Напомню, что Range(19,0,-1) означает, что мы в цикле идём от 19 до 0 с шагом "-1".
for b in range(m): #Тут мы идём в цикле от 0 до "m" (а это счётчик предыдущего цикла). Т.е. каждая итерация внешнего цикла будет уменьшать и длину внутреннего цикла.
if ParAndSons[b].fit > ParAndSons[b+1].fit: #Разобраться с методом пузырька проще всего нарисовав на бумаге ряд 31597 и проделать на нём письменно весь алгоритм, который выдаст гугл по запросу "ранжирование пузырьком".
mem = ParAndSons[b] #Мы используем переменную "mem" (от слова memory) чтобы хранить в ней одно значение в момент, когда мы взаимно меняем местами два элемента массива.
ParAndSons[b] = ParAndSons[b+1]
ParAndSons[b+1] = mem
for i in range(10): #Это финал нашего основного цикла.
for j in range(30): #Тут мы перебрасываем лучших из массива "отцов и детей" (т.е. последние 10 индивидов)
pop1.B[i].A[j]=ParAndSons[i+10].A[j] #в массив нашей основной рабочей популяции pop1.
pop1.info() #Выводим нашу новую популяцию на экран.
print() #Отступаем строчку. И повторяем наш цикл ещё 59 раз. Итого мы выведем 60 популяций, причём каждая последующая будет лучше предыдущей. |
(
