实验3：遗传算法求函数最大值实验
一、实验目的
通过本实训的学习，你将掌握遗传算法算法的原理和实现步骤，以实验的方式学会如何使用遗传算法解决当前实际生活中的部分问题，这为以后继续学习其他人工智能算法奠定了基础，也提供了一个学习其他算法的步骤模板。
二、实验设备与器件
PC机
三、实验内容
本实训将为学员介绍遗传算法求函数最大值实验，并通过求解过程的讲解加深对遗传算法的理解以及应用能力。遗传算法 (GeneticAlgorithm, GA) 是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
任务描述
本关任务：编写一个使用遗传算法计算函数最大值的小程序。
相关知识
为了完成本关任务，你需要掌握：1.什么是遗传算法，2.如何使用遗传算法对函数的最大值进行计算。
遗传算法
遗传算法 (GeneticAlgorithm, GA) 是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。
其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。
遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。
基本思想
在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。
发展历史
1962年，Fraser 提出了自然遗传算法。
1965年，Holland 首次提出了人工遗传操作的重要性。
1967年，Bagley 首次提出了遗传算法这一术语。
1970年，Cavicchio 把遗传算法应用于模式识别中。
1971年，Hollstien 在论文《计算机控制系统中人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。
1975年，美国 J. Holland 出版了《自然系统和人工系统的适配》；DeJong 完成了重要论文《遗传自适应系统的行为分析》。
20 世纪 80 年代以后，遗传算法进入兴盛发展时期。
遗传算法的数学运算
对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：
⎩
⎪
⎨
⎪
⎧
maxf(x)
X∈R
R⊂U
式中 S 为决策变量，maxf(x) 为目标函数式，X∈R、R⊂U为约束条件，U是基本空间，R是U的子集。满足约束条件的解称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。
遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优 ，而不能达到全局最优。
遗传算法的实现过程
“袋鼠跳”问题
既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰(尽管袋鼠本身不见得愿意那么做)。
所以求最大值的过程就转化成一个“袋鼠跳”的过程。
模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。
在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。
或者换个说法：
从前，有一大群袋鼠，它们被莫名其妙的零散地遗弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。
遗传算法解决“袋鼠跳”问题
遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。建立表现型和基因型的映射关系，用随机数初始化一个种群(那么第一批袋鼠就被随意地分散在山脉上)，种群里面的个体就是这些数字化的编码。
接下来，通过适当的解码过程之后(得到袋鼠的位置坐标)，用适应性函数对每一个基因个体作一次适应度评估(袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高)。
用选择函数按照某种规定择优选择,要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。让个体基因变异(袋鼠随机地跳一跳)。然后产生子代(希望存活下来的袋鼠是多产的，并在那里生儿育女)。
遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。不必去指导袋鼠向那边跳，跳多远,而只要简单的“否定”一些表现不好的个体就行了。把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！
遗传算法的实现过程
遗传算法的运算流程：
构造初始种群
计算初始种群的每个个体的值
轮盘选择法进行交叉，生成子代个体
变异
如果未到终止条件，则回到步骤1
终止，选出最佳个体的编码
流程图如下：
构建初始种群并对数据进行编码
在搜索解空间之前需要将解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合构成了不同的染色体。代码示例如下：
def decodeDNA(pop): #解码
x_pop = pop[:,1::2] #奇数列表示X
y_pop = pop[:,::2] #偶数列表示y
x = x_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(X_BOUND[1]-X_BOUND[0])+X_BOUND[0]
y = y_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Y_BOUND[1]-Y_BOUND[0])+Y_BOUND[0]
return x,y
计算初始种群每个个体的评价值
适应度评估：适应度表明个体或者解的优劣性。不同的问题，定义适应度函数的方式也不同。比如如果是求一个函数的最大值，那么一般某个解对应的函数值越大，那么这个个体（解）的适应度也就越高。代码示例如下：
def getfitness(pop):
x,y = decodeDNA(pop)
temp = F(x, y)
return (temp - np.min(temp)) + 0.0001 #减去最小的适应度是为了防止适应度出现负数
选择
选择的目的是为了从当前种群中选出优良的个体，使它们有机会成为父代繁殖下一代子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或者多个后代的概率大。这体现了达尔文的适者生存原则。代码示例如下：
def select(pop, fitness): # 根据适应度选择
temp = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,p=(fitness)/(fitness.sum()))
return pop[temp]
交叉
交叉操作是遗传算法中最主要的遗传操作。通过交叉可以得到新一代个体，新个体组合了其父代的个体特征。交叉体现了信息交换的思想。代码示例如下：
def crossmuta(pop, CROSS_RATE):
new_pop = []
for i in pop: #遍历种群中的每一个个体，将该个体作为父代
temp = i #子代先得到父亲的全部基因
if np.random.rand() < CROSS_RATE: #以交叉概率发生交叉
j = pop[np.random.randint(POP_SIZE)] #从种群中随机选择另一个个体，并将该个体作为母代
cpoints1 = np.random.randint(0, DNA_SIZE*2-1) #随机产生交叉的点
cpoints2 = np.random.randint(cpoints1,DNA_SIZE*2)
temp[cpoints1:cpoints2] = j[cpoints1:cpoints2] #子代得到位于交叉点后的母代的基因
mutation(temp,MUTA_RATE) #后代以变异率发生变异
new_pop.append(temp)
return new_pop
变异
变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率（通常是比较小的概率，这与自然界一致，自然界的变异都是小概率事件）随机改变染色体中某个基因的值。代码示例如下：
def mutation(temp, MUTA_RATE):
if np.random.rand() < MUTA_RATE: #以MUTA_RATE的概率进行变异
mutate_point = np.random.randint(0, DNA_SIZE) #随机产生一个实数，代表要变异基因的位置
temp[mutate_point] = temp[mutate_point]^1 #将变异点的二进制为反转
终止条件
首先设置了一个进化代数的上下限，最多迭代1000代，最小100代。另外，如果持续很多代最优值的改善幅度很小，便会提前终止，在算法执行时间和精确性之间取得了一个平衡。
例： 用遗传算法求解下面一个Rastrigin函数的最小值。
f(x
1
,x
2
)=20+x
1
2
+x
2
2
−10(cos2πx
1
+cos2πx
2
)
其中 −5⩽x
i
⩽5；i=1,2 。
使用遗传算法实现求解函数的最小值的变化图如下：
原图。
初始种群和第二代种群。
在迭代60、80、95、100次时的种群。
编程要求
根据提示，在右侧编辑器补充代码，使用遗传算法计算并输出 f(x,y) 最大值。
适应度函数：
f(x,y)=
0.8+(x−4.2)
2
+2∗(y−7)
2
6.452(x+0.125y)(cos(x)−cos(2y))
2
+3.226y
测试说明
平台会对你编写的代码进行测试：
预期输出：
max_fitness: 44.4531135077434
最优的基因型： [1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1
0 0 1 1 0 1 1 0 1 1 1]
(x, y): (3.4837099006003083, 6.377666972736535)
F(x,y)_max = 69.56249587430571
