简介

遗传算法是一种基于自然选择原理和自然遗传机制的启发式搜索算法。该算法通过模拟自然界中生物遗传进化的自然机制（选择、交叉和变异），将好的遗传基因（最优目标）不断遗传给子代，使得后代产生最优解的概率增加（后代还是会有一些较差结果）。

算法流程：

遗传算法流程图
  • 首先根据具体问题确定可行解域和编码方式，用数值串或字符串的形式表示可行解域中的每一个可行解；
  • 构建适应度函数度量每一个解，该函数为非负函数；
  • 确定种群的大小、选择、交叉和变异方式及概率，判断终止条件（可以是某一个阈值或者指定进化的代数）。

在整个过程当中，交叉操作是优化的主要操作，而变异操作可以看成对种群的扰动。根据具体问题构建适应度函数，并优化极值（可以是求最大值，也可以求最小值）。

名词解析

image-20220307142151332

代码解释

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

"""
题目：遗传算法
示例：寻找函数 y = a^2 + b^2 + c^3 + d^4 在[1,30]之间的最大值
备注：此算法仅为demo，有较大缺陷，后需改进
"""


import random
from operator import itemgetter


class Gene:
	"""
	名称：Gene类
	描述：这个类只有一个初始化方法，该方法就是获得基因里面的内容和大小，
		在这个例子中，内容就是[1,30]之间的任意4个数字组成的列表
	"""
	def __init__(self, **data):
		# 基因的内容
		self.__dict__.update(data)
		# 基因的长度
		self.size = len(data['data'])


class GA:
	"""
	名称：GA类
	描述：这个类包括遗传算法的所有操作方法
			__init__ ：初始化参数，包括自变量可取的最大值，最小值，种群大小，交叉率，变异率和繁殖代数
			evaluate ：该方法作为适应度函数评估该个体的函数值，在这里就是函数y的值
			selectBest ：挑选出当前代种群中的最好个体作为历史记录
			selection ：按照概率从上一代种群中选择个体，直至形成新的一代
			crossoperate ：实现交叉操作
			mutation ：实现变异操作
			GA_main ：实现整个算法的循环
	"""

	# 参数初始化
	def __init__(self, parameter):
		# parameter = [CXPB, MUTPB, NGEN, popsize, low, up]
		self.parameter = parameter
		# 可取的最小值，列表
		low = self.parameter[4]
		# 可取的最大值，列表
		up = self.parameter[5]
		# 取值范围边界
		self.bound = []
		self.bound.append(low)
		self.bound.append(up)

		# 通过这些参数随机产生一个种群的列表pop作为首代种群
		# 里面的每一条染色体是一个字典
		# 该字典有两个内容，分别是包含基因的Gene类和适应度函数值fitness
		pop = []
		for i in range(self.parameter[3]):
			# 保存种群中每一个染色体信息
			geneinfo = []
			for pos in range(len(low)):
				# 返回[low,high)区间的随机整数
				geneinfo.append(random.randint(self.bound[0][pos], self.bound[1][pos]))
			
			# 评估每一条染色体
			fitness = self.evaluate(geneinfo)
			# 保存染色体及其适应度
			pop.append({'Gene': Gene(data=geneinfo), 'fitness': fitness})
		
		self.pop = pop
		# 保存群体中最好的染色体
		self.bestindividual = self.selectBest(self.pop)

	# 适应度计算
	def evaluate(self, geneinfo):
		a = geneinfo[0]
		b = geneinfo[1]
		c = geneinfo[2]
		d = geneinfo[3]
		y = a**2 + b**2 + c**3 + d**4
		return y

	# 挑选出当前种群最好个体
	def selectBest(self, pop):
		# 按照适应度从大到小排序
		s_inds = sorted(pop, key=itemgetter("fitness"), reverse=True)
		# 返回适应度最好的
		return s_inds[0]

	# 按照概率从上一代种群中选择个体，直至形成新的一代
	# 我们需要适应度函数值大的个体被选择的概率大，可以使用轮盘赌选择法
	def selection(self, individuals, k):
		# 根据适应度从大到小排序
		s_inds = sorted(individuals, key=itemgetter("fitness"), reverse=True)
		# 群体适应度之和
		sum_fits = sum(ind['fitness'] for ind in individuals)

		chosen = []
		for i in range(k):
			# 随机生成[0，sum_fits]范围内的数值作为阈值
			u = random.random() * sum_fits
			sum_ = 0
			# 适应度之和第一次大于阈值的个体
			for ind in s_inds:
				sum_ += ind['fitness']
				if sum_ >= u:
					chosen.append(ind)
					break
		# 对重新生成的新一代种群按照适应度从小到大进行排序，方便接下来的交叉操作
		chosen = sorted(chosen, key=itemgetter("fitness"), reverse=False)
		return chosen

	# 双点交叉
	def crossoperate(self, offspring):
		# 数据长度
		dim = len(offspring[0]['Gene'].data)

		# 从选定的pop中选择的第一代后代的基因数据
		geneinfo1 = offspring[0]['Gene'].data
		geneinfo2 = offspring[1]['Gene'].data

		# 数据长度为1则不交叉
		if dim == 1:
			pos1 = 1
			pos2 = 1
		else:
			# [1,dim)获取随机整数
			pos1 = random.randrange(1, dim)
			pos2 = random.randrange(1, dim)
		
		# 存储交叉后染色体
		newoff1 = Gene(data=[])
		newoff2 = Gene(data=[])
		# 临时存储交叉后染色体
		temp1 = []
		temp2 = []
		for i in range(dim):
			# 两个交叉点之间不交换
			if min(pos1, pos2) <= i < max(pos1, pos2):
				temp2.append(geneinfo2[i])
				temp1.append(geneinfo1[i])
			# 交叉点以外的互换
			else:
				temp2.append(geneinfo1[i])
				temp1.append(geneinfo2[i])
		
		# 更新交叉后染色体信息
		newoff1.data = temp1
		newoff2.data = temp2

		return newoff1, newoff2

	# 变异在遗传过程中属于小概率事件
	# 但是在种群数量较小的情况下，只通过交叉操作并不能产生优秀的后代，此时变异就显得非常重要了
	# 通过适当的变异甚至能够产生更优秀的后代
	# 此处使用单点变异
	def mutation(self, crossoff, bound):
		dim = len(crossoff.data)

		# 如果数据长度为1，则0号位置变异
		if dim == 1:
			pos = 0
		# 否则[0,dim)区间随机整数
		else:
			pos = random.randrange(0, dim)
		
		# 变异位置pos确定后，在[low，high]区间随机整数
		crossoff.data[pos] = random.randint(bound[0][pos], bound[1][pos])
		return crossoff

	# 整合算法流程
	def GA_main(self):
		# 种群大小
		popsize = self.parameter[3]
		print("@@遗传算法开始@@")
		for g in range(NGEN):
			print(f"****第{g}代****")
			# 根据转换后的适应度重新生成群体
			selectpop = self.selection(self.pop, popsize)
			nextoff = []
			while len(nextoff) != popsize:
				# 对后代进行交叉和变异
				# 选择两个个体
				offspring = [selectpop.pop() for _ in range(2)]

				if random.random() < CXPB:
					# 以CXPB概率进行交叉
					crossoff1, crossoff2 = self.crossoperate(offspring)
					if random.random() < MUTPB:
						# 以MUTPB概率变异个体
						muteoff1 = self.mutation(crossoff1, self.bound)
						muteoff2 = self.mutation(crossoff2, self.bound)
						# 计算新的适应度
						fit_muteoff1 = self.evaluate(muteoff1.data)
						fit_muteoff2 = self.evaluate(muteoff2.data)
						# 存储交叉变异后染色体信息
						nextoff.append({'Gene': muteoff1, 'fitness': fit_muteoff1})
						nextoff.append({'Gene': muteoff2, 'fitness': fit_muteoff2})
					# 只交叉未变异
					else:
						fit_crossoff1 = self.evaluate(crossoff1.data)
						fit_crossoff2 = self.evaluate(crossoff2.data)
						nextoff.append({'Gene': crossoff1, 'fitness': fit_crossoff1})
						nextoff.append({'Gene': crossoff2, 'fitness': fit_crossoff2})
				# 未交叉未变异
				else:
					nextoff.extend(offspring)
			
			# 赋值
			self.pop = nextoff
			# 取出适应度
			fits = [ind['fitness'] for ind in self.pop]
			# 返回最好个体
			best_ind = self.selectBest(self.pop)
			# 若此最好个体适应度大于当前群体最好适应度，则更新
			if best_ind['fitness'] > self.bestindividual['fitness']:
				self.bestindividual = best_ind
			
			print(f"最佳个体：{self.bestindividual['Gene'].data},{self.bestindividual['fitness']}")
			print(f"当前最大适应度：{max(fits)}")

		print("@@遗传算法结束@@")

"""
main函数后面设置所有参数
CXPB(交叉概率)：0.8
MUTPB(变异概率)：0.1
NGEN(繁殖代数)：1000
popsize(每代种群大小)：100
"""
if __name__ == "__main__":
	CXPB, MUTPB, NGEN, popsize = 0.8, 0.1, 1000, 100
	up = [30, 30, 30, 30]
	low = [1, 1, 1, 1]
	parameter = [CXPB, MUTPB, NGEN, popsize, low, up]
	run = GA(parameter)
	run.GA_main()