遗传算法基础（Genetic Algorithm含Tictactoe问题的解决）

作者:神秘网友发布时间:2020-10-12 13:42:57

遗传算法基础（Genetic Algorithm含Tictactoe问题的解决）

1 概述
2 基本概念
3 基础算法
- 3.1 基础框架
- 3.2 主要步骤
- 3.3 基本算法
4 理论基础
参考文献

1 概述

遗传算法属于演化计算的一个分支。演化计算是一种模拟生物进化机制的通用问题求解方法。它采用简单的编码技术来表示问题的解结构，然后将类似于生物的遗传操作直接作用于这些解形成的群体，并利用优胜劣汰的选择机制来生成新的解群体，经过若干代的进化之后，较优的解将会进化而出。对于一些问题，设计良好的演化计算算法，甚至可以找到最优解。演化计算最核心的思想是优胜劣汰-适者生存。

2 基本概念

遗传算法在求解问题时，从初始的解种群(Population）开始，首先对种群中的 N 个个体随机初始化，并计算每个个体的适应度函数（依照具体问题的处理函数来计算，可以看作离期望值越近，适应度越高）。如果不满足优化准则，开始新一代计算：按照适应度选择个体，进行基因重组（杂交或交叉），按一定的概率进行变异，重新计算适应度，替换上一代个体。上述过程循环往复，直到满足优化准则为止。
种群（记为 P(t)，t 表示迭代步），是由一定数目（记为 N）的个体（Individual）或染色体（Chromosome）组成的，记为 x 1 ( t ) , x 2 ( t ) , . . . , x N ( t ) x_{1}(t), x_{2}(t), ..., x_{N}(t) x1?(t),x2?(t),...,xN?(t)。一般地，P(t) 的数目 N 在整个演化过程中是不变的。
在进行遗传迭代时，要选择当前解种群中的 2 个个体进行杂交以产生新的个体，这 2 个个体被称为新个体的父亲（Parent），产生的新个体被称为后代（Offspring）或儿子（Son）。
一般地，遗传算法首先需要对问题的解进行编码，即通过变换将 X 映射到另一空间（基因空间）I。要求该变换 F : X → I F : X → I F:X→I 是可逆的，记 F ? 1 : I → X F^{-1}:I→X F?1:I→X为解码变换，以便将求解到的解进行解码，转换到问题域中。
为讨论方便，假设使用二进制对问题解进行二进制编码。注意，遗传算法不限于二进制编码，其它形式的编码也是可行的。应用时，要依据问题的性质，选择适当的编码形式对问题解进行编码。
遗传算法可以形式化如下：
G A = ( P 0 , B , I , N , l , s , g , p , f , C ) GA = (P0, B, I, N, l, s, g, p, f, C) GA=(P0,B,I,N,l,s,g,p,f,C)
其中P0表示初始种群；B={0,1}表示编码字符集； I = B l I=B^{l} I=Bl表示长度为 l l l的二进制串全体；N表示种群中个体的数目； l l l表示二进制串的长度； I → I I → I I→I表示选择策略；g表示遗传算子：繁殖算子 Or : I → I、杂交算子 Oc : I × I → I × I I × I → I × I I×I→I×I 和变异算子 Om : I → I I → I I→I；p 表示遗传算子的操作概率：繁殖概率 p r p_{r} pr?、杂交概率 p c p_{c} pc? 和变异概率 p m p_{m} pm?； f : I → R + f : I → R^{+} f:I→R+ 是适应度函数；C 是终止条件。

3 基础算法

不同的问题，具有不同的编码方案、选择策略和遗传算子，并且遗传算法有很多变体。但是，遗传算法的基本框架是一样的。下面给出算法的基本框架：

def GA0():
	Initialize the Population P randomly
	Calculate the fitness of each individual in P
	while the terminal condition does not meet:
		Generate the new population newP from P, by individual's fitness
		Calculate the fitness of each individual in newP

基本的遗传算法也称为简单的遗传算法（Simple Genetic Algorithm, SGA），包括几个方面：编码方法、个体评价函数、初始种群、群体大小、选择算子、交叉算子、变异算子、算法终止条件等。编码方法采用固定长度的二进制编码，个体评价函数采用非负数，初始种群随机产生，仅使用选择、交叉和变异三种遗传算子。选择方法采用赌轮方法，交叉方法采用单点交叉，变异方法采用基本位变异，算法终止条件为指定的迭代次数或找到最优解（或次优解）。
例如，现在考虑如下优化问题：
m a x f ( x ) ∣ x ∈ X max{f(x)|x∈X} maxf(x)∣x∈X
其中， f f f 是 X X X 上的非负函数，即 ? x ∈ X ， f ( x ) ≥ 0 ， X ?x ∈ X，f(x) ≥ 0，X ?x∈X，f(x)≥0，X 是问题的解空间。
其中， f ( x ) = x + 2 s i n 2 x + 3 s i n 3 x + 4 s i n 4 x f(x)= x + 2 sin 2x + 3 sin 3x + 4 sin 4x f(x)=x+2sin2x+3sin3x+4sin4x如下图：
遗传算法基础（Genetic Algorithm含Tictactoe问题的解决）
如何利用遗传算法计算该函数在定义域 x ∈ [ 0 , 10 ] x ∈ [0, 10] x∈[0,10] 上的最大值（精确到 4 位小数）？
首先需要明确，如果使用穷举法，需要执行至少 100000 次计算。下面是遗传算法需要考虑的步骤：

编码与解码
该问题需要对 100000 个解（数）进行编解码，这些解均匀地分布于区间 [ 0 , 10 ] [0, 10] [0,10]上。如果采用二进制编码方式，因为 2 16 < 100000 < 2 17 2^{16} < 100000 < 2^{17} 216<100000<217，所以总共需要 17 位二进制编码。设 x ∈ [ 0 , 10 ] ， x ′ = ( b 16 b 15 b 14 . . . b 2 b 1 b 0 ) 2 x ∈ [0, 10]，x′ = (b_{16}b_{15}b_{14}...b_{2}b_{1}b_{0})_{2} x∈[0,10]，x′=(b16?b15?b14?...b2?b1?b0?)2?，它们之间的关系如下：
x = 0 + x ′ 2 17 ? 1 × 10 x=0+\frac{{x}'}{2^{17}-1}\times 10 x=0+217?1x′?×10
该公式将用于编解码。从生物学的角度看， x x x 是表现型， x ′ {x}′ x′是基因型；
群体的生成
在确定了编解码方式后，可以随机地生成 N 个个体，它们组成了遗传演化的初始群体；
适应度函数
适应度函数用于确定每个个体的质量。一般而言，需要根据问题来选择合适的适应度函数。个体的适应度越高，生存的机会就越大。本例中，函数 f ( x ) f(x) f(x)可以作为适应度函数；
选择操作
这是群体的优胜劣汰操作。可用的选择策略有：基于适应值比例的策略、基于排名的策略、基于局部竞争机制的选择等。
基于适应值比例的策略有：
(a ) 繁殖池（Breeding Pool）策略
繁殖池策略根据个体的适应值，首先计算每个个体的相对适应值 r e l i = f i ∑ i = 1 N f i rel_{i} = \frac{f_{i}}{\sum_{i=1}^{N}f_{i}} reli?=∑i=1N?fi?fi??，其中 f i f_{i} fi? 是群体中第 i i i 个个体的适应度， N N N是群体中个体数目；然后计算每个个体的繁殖量 N i = r o u n d ( r e l i × N ) N_{i} = round(rel_{i} × N) Ni?=round(reli?×N)，其中 r o u n d ( x ) round(x) round(x) 表示与 x x x 距离最小的整数；
(b ) 轮盘赌（Roulette）策略
这种选择策略在实际应用中得到了广泛的使用。与繁殖池策略一样，它也是计算每个个体的相对适应值 r e l i = f i ∑ i = 1 N f i rel_{i} = \frac{f_{i}}{\sum_{i=1}^{N}f_{i}} reli?=∑i=1N?fi?fi??，它直接将适应度 r e l i rel_{i} reli?作为每个个体被选择的概率。显然，个体的适应度越大，扇区的面积越大，个体被选中的机会就越大。对于本例，可以选择轮盘赌策略；

(c ) Boltzmann 策略
它使用函数 δ ( f i ) = e x p ( f i / T ) δ(fi) = exp(fi/T) δ(fi)=exp(fi/T)，将适应度进行变换，以改变原始的选择压力，其中 T 是一个控制参数，T 越大，选择压力越小，T 越小，选择压力越大；
基于排名的选择策略有：线性排名选择、非线性排名选择。基于局部竞争机制的策略有：锦标赛（Tournament）策略、(µ, λ) 和 µ + λ 策略、Boltzmann锦标赛策略等。
一般而言，无论是哪种选择策略，个体的适应度越高，生存的机会就越大；反之，生存的机会就越低。
杂交或交叉（Crossover）操作
杂交操作分为点式杂交和均匀杂交。
点式杂交分为单点式杂交和多点式杂交。单点式杂交随机地在两个父串中选择一个杂交点，然后交换这 2 个父串中的子串，其中杂交点的位置可以随机设定。多点式杂交则是一次随机生成多个杂交点，然后间隔地交换 2 个父串中的子串。
均匀杂交依照概率交换两个父串中的每一位。其过程是，先随机地生成一个与父串具有相同长度的杂交模板（Template），其中 0 表示不交换，1 表示交换；然后依据杂交模板对 2 个父串进行杂交，所得的 2 个新串即为后代串。
显然，通过交叉操作，可以生成新的个体。下面比较 2 种杂交操作的优缺点：
? 点式杂交对个体的破坏性小，在搜索过程中，能以较大的概率保护好个体的模式。但是，这种策略能够搜索到的个体模式数也少。在群体规模较小时，搜索能力受到一定的影响；
? 均匀杂交对个体中的每个基因位均匀对待，破坏个体模式的可能性比较大。它能够搜索到点式杂交无法搜索到的模式。因此，在群体规模较小时，具有较强的搜索能力；
基于上述原因，当群体规模较小时，使用均匀杂交操作较合适。当群体规模较大时，群体的内在多样性本身可以弥补点式杂交的缺点，而点式杂交对个体的破坏性小，可以让好的个体模式得到更多的保护，算法收敛较快；
变异（Mutation）操作
变异操作非常简单，它以一定的变异概率 p m p_{m} pm? 改变个体的基因位。在二进制编码中，它的操作是取反。在其它编码中，它以变异概率将每个基因位改变为任意合法的编码。
变异操作是十分微妙的遗传操作，需要与交叉操作妥善配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。
主要控制参数的优化与选取
在遗传算法中，主要的控制参数包括：群体的规模 N N N（个体的数目）、杂交概率 p c p_{c} pc?、变异概率 p m p_{m} pm?。这些控制参数对遗传算法的性能及收敛性 会产生较大的影响。对于一个具体的问题，要想获得最优的参数配置，可以采取试验的方法，这一过程被称为调参。例如，针对每个参数，可以在某个区间上按一定的间隔取有限个值，然后针对每一种组合，执行遗传算法并比较它们的性能。最后，选出最佳的参数组合。但是，这种方法的计算量很大。在实际应用中，可以依据经验值选取控制参数，然后多执行几次以获得较优的结果。
根据经验，对于执行重叠的遗传算法，参数可以设置为： N = 20 ～ 100 、 p c = 0.60 ～ 0.95 、 p m = 0.001 ～ 0.01 N = 20 ～ 100、p_{c} = 0.60 ～ 0.95、p_{m} = 0.001 ～ 0.01 N=20～100、pc?=0.60～0.95、pm?=0.001～0.01（或取 1 / l 1/l 1/l， l l l 为编码长度）；对于执行非重叠的遗传算法，参数可以设置为： N = 20 ～ 100 、 p c = 0.5 ～ 0.7 、 p m = 0.2 ～ 0.4 N = 20 ～ 100、p_{c} = 0.5 ～ 0.7、p_{m} = 0.2 ～ 0.4 N=20～100、pc?=0.5～0.7、pm?=0.2～0.4。

在明确了遗传算法的主要步骤之后，下面给出计算函数 f ( x ) = x + 2 s i n 2 x + 3 s i n 3 x + 4 s i n 4 x f(x) = x + 2 sin 2x + 3 sin 3x + 4 sin 4x f(x)=x+2sin2x+3sin3x+4sin4x在定义域 [ 0 , 10 ] [0, 10] [0,10] 上的最大值的算法伪代码：

Input

None

Output

the best solution

def GA():
	seed()		#初始化随机数种子
	generation_num = 500		#设置种群演化的代数（可看作迭代的次数）
	population_num = 20			#设置种群数量
	codebit_num = 17			#设置基因位数
	prob_crossover = 0.7		#设置杂交概率
	prob_mutation = 0.02		#设置变异概率
	POPULATION = []				#定义一个用来存放种群的列表
	FITNESS = []				#定义一个用来存放种群个体适应度的队列
	PROB = []					#定义一个用来存放前n个个体适应度之和
	Init()						#初始化种群函数
	for t in range(generation_num):
		fitness_sum = 0			#重新将个体适应度之和置为零
		P_TMP = POPULATION[:]	#定义一个种群副本
		for i in range(0,population_num,2):#种群
			d1 = Select(P_TMP)	#从种群中选择一个个体
			d2 = Select(P_TMP)	#从种群中选择一个个体
			Crossover(d1, d2)	#将两个个体杂交
			Mutate(d1)			#个体随机变异
			Mutate(d2)			#个体随机变异
			POPULATION[i] = d1	#更新第i个个体
			POPULATION[i+1] = d2	#更新第i+1个个体
			f1 = CalculateFitness(d1)	#计算新个体的适应度
			FITNESS[i] = f1		#将第i个个体的适应度更新
			fitness_sum += f1	#计入适应度总和
			f2 = CalculateFitness(d2)	#计算新个体的适应度
			FITNESS[i+1] = f2		#将第i+1个个体的适应度更新
			fitness_sum += f2	#计入适应度总和
		#Update the statistics of population
		PROB[0] = FITNESS[0]/fitness_sum	#每更新一代种群，需要更新一次种群适应数据
		for i in range(1, len(FITNESS)):	#遍历种群个体适应度
			PROB[i] = PROB[i-1]+FITNESS[i]/fitness_sum #前i个个体占总体的适应度比
	return x with MAX_FITNESS of POPULATION	#返回适应度最高的个体
	
def Init():		#初始化种群
	fitness_sum = 0
	for i in range(population_num):
		generate an individual randomly	#创建一个随机个体
		POPULATION.append(individual)	#将该个体放入种群
		f = CalculateFitness(individual)#计算该个体的适应度
		FITNESS.append(f)				#放入适应度列表中
		fitness_sum += f				#计入总和
	PROB.append(FITNESS[0]/fitness_sum)	#计算适应度占比
	for i in range(1, len(FITNESS)):	#前i个个体占总体的适应度比
		PROB.append(PROB[i-1]+FITNESS[i]/fitness_sum)

def Fitness(xx):
	x = 0 + xx*10/131071	#pow(2,17)-1=131071，每次x增量
	return x + 2*sin(2*x) + 3*sin(3*x) + 4*sin(4*x) #返回一个y值

def Select(population):		# 随机从种群中选择一个个体
	r = random()
	for i in range(len(PROB)):	# 轮盘赌策略
		if r <= PROB[i]:		# 个体适应度越高，扇形区域越大
			return population[i][:]	#返回一个个体
	
def Crossover(d1, d2):	#将两个个体部分交叉，此处模板为取[x,:]后段基因
	r = random()
	if r <= prob_crossover:
		point = randint(0, len(d1)-1)
		d1[point:], d2[point:] = d2[point:], d1[point:]

def Mutate(d):			#对个体基因段变异
	for i in range(len(d)):
		if random() <= prob_mutation:	#如果随机概率小于变异概率，即出现比变异概率更小事件
			d[i] = str((int(d[i])+1) % 2)	#变异
			
def CalculateFitness(d):	#计算适应度
	xx = int(''.join(d), base = 2)	#将字符串以二进制的形式转换为10进制
	f = Fitness(xx)
	if f < 0:#abandon negative value
		f = 0
	return f

下面给出Tictactoe最优解算法伪代码： Tictactoe 的其他方法，如：Minimax算法、alpha~beta算法、MCTS算法

4 理论基础

参考文献

《人工智能》课程系列遗传算法基础? 武汉纺织大学数学与计算机学院杜小勤

Date

-[ ] Create on Sat 2020/10/11

-[x] Last update on

人间万事，毫发常重泰山轻