C_Meng PSNA

Never wait for the storm to pass, just dance in the rain.

0%

启发式算法学习（三）：遗传算法GA

Posted on Edited on In Valine:

算法简介

遗传算法（Genetic Alogrithm，GA）是最早由美国Holland教授提出的一种基于自然界的“适者生存，优胜劣汰”基本法则的智能搜索算法。该法则很好地诠释了生物进化的自然选择过程。遗传算法也是借鉴该基本法则，通过基于种群的思想，将问题的解通过编码的方式转化为种群中的个体，并让这些个体不断地通过选择、交叉和变异算子模拟生物的进化过程，然后利用“优胜劣汰”法则选择种群中适应性较强的个体构成子种群，然后让子种群重复类似的进化过程，直到找到问题的最优解或者到达一定的进化（运算）时间。

重要概念

个体（染色体）：自然界中一个个体（染色体）代表一个生物，在GA算法中，个体（染色体）代表了具体问题的一个解。

基因：在GA算法中，基因代表了具体问题解的一个决策变量，问题解和染色体中基因的对应关系如下所示

种群：多个个体即组成一个种群。GA算法中，一个问题的多组解即构成了问题的解的种群。

主要步骤

主要操作介绍

种群的初始化

选择一种编码方案，然后在解空间内通过随机生成的方式初始化一定数量的个体构成GA的种群
种群的初始化和具体问题相关，一般来说可以采取某种分布（如高斯分布）在一定求解范围内随机获取

种群评价

种群的评价即计算种群中个体的适应度值。假设种群population有popsize个个体。依次计算每个个体的适应度值及评价种群。或者利用启发式算法对种群中的个体（矩形件的排入顺序）生成排样图并依此计算个体的适应函数值（利用率），然后保存当前种群中的最优个体作为搜索到的最优解。

选择操作

常见的选择操作有轮盘赌的方式：根据个体的适应度计算被选中的概率，公式如下：

$$P(x_j)=\frac{fit(x_j)}{\sum_{i=1}^n fit(x_i)}, j\in{1,2,…,n}$$

交叉操作

一般以概率阀值Pc控制是否进行单点交叉、多点交叉或者其他交叉方式生成新的交叉个体。

交叉操作也有许多种：单点交叉，两点交叉等。此处仅讲解一下两点交叉。首先利用选择操作从种群中选择两个父辈个体parent1和parent2,然后随机产生两个位置pos1和pos2，将这两个位置中间的基因位信息进行交换，便得到下图所示的off1和off2两个个体，但是这两个个体中一般会存在基因位信息冲突的现象（整数编码时），此时需要对off1和off2个体进行调整：off1中的冲突基因根据parent1中的基因调整为parent2中的相同位置处的基因。如off1中的“1”出现了两次，则第二处的“1”需要调整为parent1中“1”对应的parent2中的“4”，依次类推处理off1中的相冲突的基因。需要注意的是，调整off2，则需要参考parent2。

变异操作

一般以概率阀值Pm控制是否对个体的部分基因执行单点变异或多点变异。

变异操作的话，根据不同的编码方式有不同的变异操作。

如果是浮点数编码，则变异可以就染色体中间的某一个基因位的信息进行变异（重新生成或者其他调整方案）。

如果是采用整数编码方案，则一般有多种变异方法：位置变异（调换同一个体的多个基因）和符号变异（正数变负数）。

python实现

求 $f(x,y)=21.5+x\times\sin(4\times\pi\times x) + y \times\sin(20\times\pi\times y)$ 的最大值

代码来自：
https://blog.csdn.net/qq_30666517/article/details/78637255

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
# -*- coding:utf-8 -*- 
import numpy as np
from scipy.optimize import fsolve, basinhopping
import random
import timeit
 
 
# 根据解的精度确定染色体(chromosome)的长度
# 需要根据决策变量的上下边界来确定
def getEncodedLength(delta=0.0001, boundarylist=[]):
	# 每个变量的编码长度
	lengths = []
	for i in boundarylist:
		lower = i[0]
		upper = i[1]
		# lamnda 代表匿名函数f(x)=0,50代表搜索的初始解
		res = fsolve(lambda x: ((upper - lower) * 1 / delta) - 2 ** x - 1, 50)
		length = int(np.floor(res[0]))
		lengths.append(length)
	return lengths
 
 
# 随机生成初始编码种群
def getIntialPopulation(encodelength, populationSize):
	# 随机化初始种群为0
	chromosomes = np.zeros((populationSize, sum(encodelength)), dtype=np.uint8)
	for i in range(populationSize):
		chromosomes[i, :] = np.random.randint(0, 2, sum(encodelength))
	# print('chromosomes shape:', chromosomes.shape)
	return chromosomes
 
 
# 染色体解码得到表现型的解
def decodedChromosome(encodelength, chromosomes, boundarylist, delta=0.0001):
	populations = chromosomes.shape[0]
	variables = len(encodelength)
	decodedvalues = np.zeros((populations, variables))
	for k, chromosome in enumerate(chromosomes):
		chromosome = chromosome.tolist()
		start = 0
		for index, length in enumerate(encodelength):
			# 将一个染色体进行拆分，得到染色体片段
			power = length - 1
			# 解码得到的10进制数字
			demical = 0
			for i in range(start, length + start):
				demical += chromosome[i] * (2 ** power)
				power -= 1
			lower = boundarylist[index][0]
			upper = boundarylist[index][1]
			decodedvalue = lower + demical * (upper - lower) / (2 ** length - 1)
			decodedvalues[k, index] = decodedvalue
			# 开始去下一段染色体的编码
			start = length
	return decodedvalues
 
 
# 得到个体的适应度值及每个个体被选择的累积概率
def getFitnessValue(func, chromosomesdecoded):
	# 得到种群规模和决策变量的个数
	population, nums = chromosomesdecoded.shape
	# 初始化种群的适应度值为0
	fitnessvalues = np.zeros((population, 1))
	# 计算适应度值
	for i in range(population):
		fitnessvalues[i, 0] = func(chromosomesdecoded[i, :])
	# 计算每个染色体被选择的概率
	probability = fitnessvalues / np.sum(fitnessvalues)
	# 得到每个染色体被选中的累积概率
	cum_probability = np.cumsum(probability)
	return fitnessvalues, cum_probability
 
 
# 新种群选择
def selectNewPopulation(chromosomes, cum_probability):
	m, n = chromosomes.shape
	newpopulation = np.zeros((m, n), dtype=np.uint8)
	# 随机产生M个概率值
	randoms = np.random.rand(m)
	for i, randoma in enumerate(randoms):
		logical = cum_probability >= randoma
		index = np.where(logical == 1)
		# index是tuple,tuple中元素是ndarray
		newpopulation[i, :] = chromosomes[index[0][0], :]
	return newpopulation
 
 
# 新种群交叉
def crossover(population, Pc=0.8):
	"""
	:param population: 新种群
	:param Pc: 交叉概率默认是0.8
	:return: 交叉后得到的新种群
	"""
	# 根据交叉概率计算需要进行交叉的个体个数
	m, n = population.shape
	numbers = np.uint8(m * Pc)
	# 确保进行交叉的染色体个数是偶数个
	if numbers % 2 != 0:
		numbers += 1
	# 交叉后得到的新种群
	updatepopulation = np.zeros((m, n), dtype=np.uint8)
	# 产生随机索引
	index = random.sample(range(m), numbers)
	# 不进行交叉的染色体进行复制
	for i in range(m):
		if not index.__contains__(i):
			updatepopulation[i, :] = population[i, :]
	# crossover
	while len(index) > 0:
		a = index.pop()
		b = index.pop()
		# 随机产生一个交叉点
		crossoverPoint = random.sample(range(1, n), 1)
		crossoverPoint = crossoverPoint[0]
		# one-single-point crossover
		updatepopulation[a, 0:crossoverPoint] = population[a, 0:crossoverPoint]
		updatepopulation[a, crossoverPoint:] = population[b, crossoverPoint:]
		updatepopulation[b, 0:crossoverPoint] = population[b, 0:crossoverPoint]
		updatepopulation[b, crossoverPoint:] = population[a, crossoverPoint:]
	return updatepopulation
 
 
# 染色体变异
def mutation(population, Pm=0.01):
	"""
	:param population: 经交叉后得到的种群
	:param Pm: 变异概率默认是0.01
	:return: 经变异操作后的新种群
	"""
	updatepopulation = np.copy(population)
	m, n = population.shape
	# 计算需要变异的基因个数
	gene_num = np.uint8(m * n * Pm)
	# 将所有的基因按照序号进行10进制编码，则共有m*n个基因
	# 随机抽取gene_num个基因进行基本位变异
	mutationGeneIndex = random.sample(range(0, m * n), gene_num)
	# 确定每个将要变异的基因在整个染色体中的基因座(即基因的具体位置)
	for gene in mutationGeneIndex:
		# 确定变异基因位于第几个染色体
		chromosomeIndex = gene // n
		# 确定变异基因位于当前染色体的第几个基因位
		geneIndex = gene % n
		# mutation
		if updatepopulation[chromosomeIndex, geneIndex] == 0:
			updatepopulation[chromosomeIndex, geneIndex] = 1
		else:
			updatepopulation[chromosomeIndex, geneIndex] = 0
	return updatepopulation
 
 
# 定义适应度函数
def fitnessFunction():
	return lambda x: 21.5 + x[0] * np.sin(4 * np.pi * x[0]) + x[1] * np.sin(20 * np.pi * x[1])
 
 
def main(max_iter=500):
    # 每次迭代得到的最优解
    optimalSolutions = []
    optimalValues = []
    # 决策变量的取值范围
    decisionVariables = [[-3.0, 12.1], [4.1, 5.8]]
    # 得到染色体编码长度
    lengthEncode = getEncodedLength(boundarylist=decisionVariables)

    # 得到初始种群编码
    chromosomesEncoded = getIntialPopulation(lengthEncode, 10)

    for iteration in range(max_iter):
        # 种群解码
        decoded = decodedChromosome(lengthEncode, chromosomesEncoded, decisionVariables)
        # 得到个体适应度值和个体的累积概率
        evalvalues, cum_proba = getFitnessValue(fitnessFunction(), decoded)
        # 选择新的种群
        newpopulations = selectNewPopulation(chromosomesEncoded, cum_proba)
        # 进行交叉操作
        crossoverpopulation = crossover(newpopulations)
        # mutation
        mutationpopulation = mutation(crossoverpopulation)
        # 将变异后的种群解码，得到每轮迭代最终的种群
        final_decoded = decodedChromosome(lengthEncode, mutationpopulation, decisionVariables)
        # 适应度评价
        fitnessvalues, cum_individual_proba = getFitnessValue(fitnessFunction(), final_decoded)
        # 搜索每次迭代的最优解，以及最优解对应的目标函数的取值
        optimalValues.append(np.max(list(fitnessvalues)))
        index = np.where(fitnessvalues == max(list(fitnessvalues)))
        optimalSolutions.append(final_decoded[index[0][0], :])
        chromosomesEncoded = mutationpopulation

    # 搜索最优解
    optimalValue = np.max(optimalValues)
    optimalIndex = np.where(optimalValues == optimalValue)
    optimalSolution = optimalSolutions[optimalIndex[0][0]]
    return optimalSolution, optimalValue
 
 
solution, value = main()
print('最优解: x1, x2')
print(solution[0], solution[1])
print('最优目标函数值:', value)
# 测量运行时间
elapsedtime = timeit.timeit(stmt=main, number=1)
print('Searching Time Elapsed:(S)', elapsedtime)

Reference:
https://blog.csdn.net/bible_reader/article/details/72782675
https://blog.csdn.net/qq_30666517/article/details/78637255

点击这个按钮，会有好事发生哦~(>w<)~