python实现遗传算法，gif动图展示结果

目的：使用遗传算法寻找方程的最大值

这里先放最后的结果：

，可以看到在经过多次迭代后，初始种群在向函数的最大值点逼近。

遗传算法是用于解决NP—hard问题的，目的是为了有效的求解出相对最优的解，用计算机上的语言来说就是以损失一定精度换取求解时间。在网上有很多描述遗传算法的，道理很简单，就是模拟八个字“物竞天择，优胜劣汰”（这里不得不佩服John Henry Holland这位大师的脑洞），学完遗传算法，蚁群算法，粒子群算法，模拟退火算法我还是想感叹一句，生活就是最美的数学。话不多说，接下来说一下我的思路。

步骤

1-确定解码方式（我采用的是二进制编码，因为更形象，也简单），取精度为0.0001，函数自变量x的范围为[0,9],那么需要的位数为17位，所以解码代码如下：

#解码
def decode(genCode):
 y = 0 + int(genCode,2)/(2**17-1)*9 
 return y
1
2
3
4

2-初始化种群（遗传算法的效果受初始化种群的影响较大，选择不好很容易陷入局部最优）

#初始化种群数(假设初始种群数目为10个)，10个17位位str
population = [] #总群
for i in range(20):
 strCode = ''
 for j in range(17):
 strCode += str(np.random.randint(0,2))
 population.append(strCode)
1
2
3
4
5
6
7

3-适应函数（这里就是目标函数），求解每个个体的适应值

def fitnessfunction(population,initFunction):
 value = []
 for i in range(len(population)):
 value.append(initFunction(decode(population[i])))
 if value[i] < 0:
 value[i] = 0
 return value
1
2
3
4
5
6
7
8

4-轮盘赌选择（模拟优胜劣汰），根据个体适应值大小，采用轮盘法选择优胜个体

def selectChild(population,fitnessResult):
 childPopulation = []
 Sumfitness = []
 indiviSumP = []
 for i in range(len(fitnessResult)):
 if i == 0:
 Sumfitness.append(fitnessResult[i])
 else:
 Sumfitness.append(Sumfitness[i-1] + fitnessResult[i]) 
 for j in range(len(Sumfitness)):
 indiviSumP.append(Sumfitness[j]/sum(fitnessResult))
 for childNum in range(len(population)):
 x = np.random.uniform(0,1)
 if x <= indiviSumP[0]:
 childPopulation.append(population[0])
 else:
 for m in range(1,len(population)):
 if indiviSumP[m-1] <= x and x <= indiviSumP[m]:
 childPopulation.append(population[m])
 break 
 return childPopulation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5-交叉选择（对选择的优胜个体进行交叉信息，模拟繁殖下一带，且用一个概率控制满足自然界中颜色体交换是普遍的（所以这里的交叉概率取固定的0.7），变异是罕见的（这里取较小0.002））

#对选择后的子代进行一定概率的染色提交换
def crossParent(new_population,pc):
 crossChildPopulation = []
 #如果为单身则先选择出单shen
 if len(new_population)%2 != 0:
 randmSingleNum = np.random.randint(0,len(new_population))
 crossChildPopulation.append(new_population[randmSingleNum])
 del(new_population[randmSingleNum])
 half = int(len(new_population)/2)
 father = new_population[:half]
 mother = new_population[half:]
 np.random.shuffle(father)
 np.random.shuffle(mother)
 for i in range(half):
 crossP = np.random.uniform(0,1)
 if pc >= crossP:
 breakPoint = np.random.randint(0,len(new_population[0]))
 son = father[i][:breakPoint] + mother[i][breakPoint:]
 daughter = mother[i][:breakPoint] + father[i][breakPoint:]
 else:
 son = father[i]
 daughter = mother[i]
 crossChildPopulation.append(son)
 crossChildPopulation.append(daughter)
 return crossChildPopulation
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

6-变异获得子代

#变异
def variation(crossChildPopulation,pc):
 variationPopulation = []
 for i in range(len(crossChildPopulation)):
 variationP = np.random.uniform(0,1)
 variationPos = np.random.randint(0,len(crossChildPopulation[0]))
 if variationP <= pc:
 if variationPos == 0:
 if crossChildPopulation[i][0] == '0':
 crossChildPopulation[i] = '1'+crossChildPopulation[i][1:]
 else:
 crossChildPopulation[i] = '0'+crossChildPopulation[i][1:]
 else:
 if crossChildPopulation[i][variationPos] == '0':
 crossChildPopulation[i] = crossChildPopulation[i][:variationPos-1] + '1' + crossChildPopulation[i][variationPos:]
 else:
 crossChildPopulation[i] = crossChildPopulation[i][:variationPos-1] + '0' + crossChildPopulation[i][variationPos:]
 variationPopulation.append(crossChildPopulation[i])
 return variationPopulation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

然后进行多步训练即可：

for i in range(1000):
 fitnessValue = fitnessfunction(population,initFunction)
 selectChildes = selectChild(population,fitnessValue)
 crossChild = crossParent(selectChildes,0.7)
 population = variation(crossChild,0.02)
1
2
3
4
5
6

但是我们想要模拟动态过程，所以我们需要引入

from matplotlib.animation import FuncAnimation
from matplotlib import animation
1
2

用于绘制我们的动图，如前面所示。这里大家可以取查官方文档看这个的具体用法，或者给我留言，我就直接贴更新图片获得动图的代码：

def updata(i):
 global population
 x1 = [0 for j in range(len(population))]
 y1 = [0 for j in range(len(population))]
 fig.set_size_inches(15,10)#控制再保存图片的时候窗口不要缩小
 picpath = 'C:\Users\Amie\Desktop\png\{0}.png'.format(i)
 plt.savefig(picpath,pi = 600,edgecolor = 'r')
 fitnessValue = fitnessfunction(population,initFunction)
 selectChildes = selectChild(population,fitnessValue)
 crossChild = crossParent(selectChildes,0.7)
 population = variation(crossChild,0.02)
 for i in range(len(population)):
 x1[i] = decode(population[i])
 y1[i] = initFunction(decode(population[i]))
 data = [[x,y] for x,y in zip(x1,y1)]
 sca1.set_offsets(data)
 print(list(zip(x1,y1)))
 return sca1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

现在我们只需要组装好所有函数即可得到，动态显示模拟遗传算法的效果图了，以下是完整代码：

from __future__ import division
import math
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from matplotlib import animation
fig = plt.figure(figsize=(15,10))
ax1 = fig.add_subplot(111)
ax1.set_xlim([0,10])
ax1.set_ylim([-10,15])
#定义函数
def initFunction(x):
 y = x + 5*math.sin(5*x)+2*math.cos(3*x)
 return y
#形成一些点用于绘图（这里生成900个点）
x = [i / 100 for i in range(900)]
y = [i%900 for i in range(900)]
for i in range(900):
 y[i] = initFunction(x[i])
ax1.plot(x,y)
#初始化种群数(假设初始种群数目为10个)，10个17位位str
population = []
for i in range(20):
 strCode = ''
 for j in range(17):
 strCode += str(np.random.randint(0,2))
 population.append(strCode)
#解码
def decode(genCode):
 y = 0 + int(genCode,2)/(2**17-1)*9 
 return y
m = [m for m in range(len(population))]
n = [n for n in range(len(population))]
for i in range(len(population)):
 n[i] = initFunction(decode(population[i]))
 m[i] = decode(population[i])
sca1 = ax1.scatter(m,n)#散点图命名，用于更新
#
#适应度函数，其中负数置零的步骤可以调整
def fitnessfunction(population,initFunction):
 value = []
 for i in range(len(population)):
 value.append(initFunction(decode(population[i])))
 if value[i] < 0:
 value[i] = 0
 return value
#采用轮盘赌算法进行选择
#输入是种群的适应度函数值向量
#population 为父代，经过选择后返回子代childPopulation
def selectChild(population,fitnessResult):
 childPopulation = []
 Sumfitness = []
 indiviSumP = []
 for i in range(len(fitnessResult)):
 if i == 0:
 Sumfitness.append(fitnessResult[i])
 else:
 Sumfitness.append(Sumfitness[i-1] + fitnessResult[i]) 
 for j in range(len(Sumfitness)):
 indiviSumP.append(Sumfitness[j]/sum(fitnessResult))
 for childNum in range(len(population)):
 x = np.random.uniform(0,1)
 if x <= indiviSumP[0]:
 childPopulation.append(population[0])
 else:
 for m in range(1,len(population)):
 if indiviSumP[m-1] <= x and x <= indiviSumP[m]:
 childPopulation.append(population[m])
 break 
 return childPopulation
#对选择后的子代进行一定概率的染色提交换
def crossParent(new_population,pc):
 crossChildPopulation = []
 #如果为单身则先选择出单shen
 if len(new_population)%2 != 0:
 randmSingleNum = np.random.randint(0,len(new_population))
 crossChildPopulation.append(new_population[randmSingleNum])
 del(new_population[randmSingleNum])
 half = int(len(new_population)/2)
 father = new_population[:half]
 mother = new_population[half:]
 np.random.shuffle(father)
 np.random.shuffle(mother)
 for i in range(half):
 crossP = np.random.uniform(0,1)
 if pc >= crossP:
 breakPoint = np.random.randint(0,len(new_population[0]))
 son = father[i][:breakPoint] + mother[i][breakPoint:]
 daughter = mother[i][:breakPoint] + father[i][breakPoint:]
 else:
 son = father[i]
 daughter = mother[i]
 crossChildPopulation.append(son)
 crossChildPopulation.append(daughter)
 return crossChildPopulation
#变异
def variation(crossChildPopulation,pc):
 variationPopulation = []
 for i in range(len(crossChildPopulation)):
 variationP = np.random.uniform(0,1)
 variationPos = np.random.randint(0,len(crossChildPopulation[0]))
 if variationP <= pc:
 if variationPos == 0:
 if crossChildPopulation[i][0] == '0':
 crossChildPopulation[i] = '1'+crossChildPopulation[i][1:]
 else:
 crossChildPopulation[i] = '0'+crossChildPopulation[i][1:]
 else:
 if crossChildPopulation[i][variationPos] == '0':
 crossChildPopulation[i] = crossChildPopulation[i][:variationPos-1] + '1' + crossChildPopulation[i][variationPos:]
 else:
 crossChildPopulation[i] = crossChildPopulation[i][:variationPos-1] + '0' + crossChildPopulation[i][variationPos:]
 variationPopulation.append(crossChildPopulation[i])
 return variationPopulation
def updata(i):
 global population
 x1 = [0 for j in range(len(population))]
 y1 = [0 for j in range(len(population))]
 fig.set_size_inches(15,10)#控制再保存图片的时候窗口不要缩
 fitnessValue = fitnessfunction(population,initFunction)
 selectChildes = selectChild(population,fitnessValue)
 crossChild = crossParent(selectChildes,0.7)
 population = variation(crossChild,0.02)
 for i in range(len(population)):
 x1[i] = decode(population[i])
 y1[i] = initFunction(decode(population[i]))
 data = [[x,y] for x,y in zip(x1,y1)]
 sca1.set_offsets(data)
 print(list(zip(x1,y1)))
 return sca1
ani = animation.FuncAnimation(fig = fig,func=updata,frames=np.arange(1,20),init_func = None,interval = 500,blit = False)
plt.show()
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

源代码链接：

链接：https://pan.baidu.com/s/1WL14a5-Q3tsqoIuJSikx4A 密码：ggu0