本章涉及知识点
1、达尔文进化论
2、遗传算法的思想
3、遗传算法下的TSP模型
4、染色体的编码
5、种群的初始化
6、适应度函数
7、精英种群的选择
8、轮盘赌法
9、染色体的交叉操作
10、染色体的变异操作
11、染色体的逆转操作
12、python编程实现遗传算法
13、结果分析
一、达尔文进化论
达尔文认为，生物之间都存在着生存斗争，只有经过不同程度的斗争，适应者才可以顺利的存活下来，而不适者将被合理的淘汰，即"物竞天择，适者生存"
而斗争的过程和结果，就是生物的进化，生物正是通过基因的交叉、变异和自然选择，让自己从低级到高级，从简单到复杂，从不适到适合的进化成长，如果进化成功，它就能继续存活并且进化下去，否则将面临灭亡
二、遗传算法的思想
在日常生活中，我们经常需要求一个问题的最优解，而许多问题的最优解却没有一个通用的数学解法，或者在有限的时间空间内，无法精确的找到全局最优解，例如NP问题里的组合优化问题—TSP问题
遗传算法思想
遗传算法（GA）属于人工智能启发式算法，启发式算法的目标就是寻找原始问题的最优解，该算法的定义为
人类通过直观常识和生活经验，设计出一种以搜索最优解为目的，通过仿真大自然规律的算法，该算法在可以在接受的花销（计算时间和存储空间）范围内找到问题实例的一个可行解，且该可行解和真实最优解的误差一般不可以被估计
当下主要有的启发式算法包括遗传算法、退火法，蚁群算法、人工神经网络等，这篇文章主要介绍遗传算法
遗传算法的基本原理是模拟达尔文进化论"物竞天择，适者生存"的自然法则，其核心思想为
（1）将原始问题的参数，抽象为基因编码
（2）将原始问题的可行解，抽象为基因排列的染色体组合
（3）将原始问题的解集规模，抽象为一定数量染色体组成的种群
（4）寻找可行解的过程，抽象为种群的进化过程（染色体选择、交叉、变异等）
（5）比较可行解的优劣，抽象为量化比较不同种群对当前环境的适应程度
（6）逼近最优解的过程，抽象为淘汰适应度差的种群，保留适应度高的种群进行下一次进化
（7）问题的最优解，抽象为经过多次进化后，最终生存下来的精英种群
理论上，通过有限次种群进化，生存下来的种群都是精英染色体，是最适合当前环境条件的种群，也就可以无限逼近原始问题的最优解
遗传算法可以用来求解多元非线性函数的极值，也可以用来求解组合问题的最优解
三、遗传基因算法下的TSP模型
我们选择GA算法来求解TSP问题，首先需要抽象出GA算法下TSP的模型
GA算法下TSP的模型
四、染色体的编码
我们将一个城市抽象为一个基因，而城市的旅行顺序，可以看做一个离散型问题，因此我们可以采用1~n的整数，对这n个城市进行一一编码，即
基因整数编码
我们对编码好的城市，进行任意的排列，即让一组基因组成一个染色体，染色体的意义为
（1）染色体包含了所有的基因（城市）
（2）染色体的长度，就是所有城市的数量
（3）一个染色体描述了一次TSP的旅行路线
（4）一个染色体代表了一个TSP的可行解
染色体编码
五、种群的初始化
TSP问题中所有旅行线路的规模为n!，由于n可能非常大，一般我们选择初始化m个染色体来组成种群(m < n)
初始化种群可以有下面两个方法
（1）求解m的全排列，这样求解出的种群就包含了原始问题的所有可行解
（2）每次都随机打乱基因组的排列，来生成不同的染色体
我们的程序里就是采用第二种方法来初始化种群
六、适应度函数
由于种群需要不断进化，为此我们需要定义一个规则，来评估打分当前环境下哪些种群可以生存，哪些种群将被淘汰，我们将这个规则叫做适应度函数
我们可以设计出TSP模型下的适应度函数为：一次旅行路线行走的总距离的倒数
适应度函数
可以看出：总距离越长，适应度越低；总距离越短，适应度越高
七、精英种群的选择
每一次种群进化后，我们都需要对当前种群进行优胜劣汰，让精英种群尽量生存下去，翻译为数学语言为：
种群被选中定义为精英种群的概率，与其适应度成正比，即一个染色体的适应度越高，该染色体被选中为精英染色体的概率也将越大
选择精英种群的概率方法，我们使用轮盘赌法
八、轮盘赌法
根据古典概率型，第i个种群被选中的概率为
第i个种群被选中的概率
每个种群都对应着其相应的适应度分数Fi，我们抽象出一张转盘来表示n个种群的概率分布
n个种群的概率分布
饼图中每个种群的扇形面积，就是其适应度分数的比例，我们只要随机旋转这个轮盘，直到轮盘停止的时候，指针指在哪一块上，就选择该种群，显然分数越高（面积越大），被选中的概率也就越大
由此可以看出轮盘赌法满足：
种群被选中的概率与其适应度函数值成正比
九、染色体的交叉操作
交叉操作：发生在两个染色体各自任意的基因片段上
假设有下面两个染色体
两个染色体
染色体交叉的策略如下：
（1）产生两个随机数r1和r2，代表这两个染色体发生交叉操作的基因片段位置，如r1=1，r2=3，下图红色标注的区域就是即将发生交叉操作的基因片段
即将发生交叉操作的基因片段
（2）交换这两个基因片段，变为
交换基因片段
但是我们发现交换基因片段后，染色体的基因会有重复，为此我们需要解决这个基因冲突问题，下图蓝色标注的区域就是冲突的基因
基因冲突问题
（3）一一交换两个染色体的冲突基因，即可解决冲突产生新的一对染色体
解决基因冲突
至此，我们可以看到交叉操作的意义为
（1）通过交叉产生两个新的染色体
（2）为寻找全局最优解，提供了新的可能性
十、染色体的变异操作
染色体变异：发生在单个染色体的两个基因位置上
假设有下面染色体
染色体
染色体变异的策略如下：
（1）产生两个随机数r1和r2，代表两个即将发生基因变异的位置，如r1=3，r2=6，下图红色标注的区域就是即将变异的基因位置
即将发生变异操作的基因片段
（2）直接交换这两个基因位置，得到
染色体变异
至此，我们可以看到变异操作的意义为
（1）使得染色体的基因更加有随机性
（2）为跳出局部最优解，提供了可能性
十一、染色体的逆转操作
染色体的逆转：发生在单个染色体的一段基因片段上
假设有下面染色体
染色体
染色体逆转的策略如下：
（1）产生两个随机数r1和r2，代表单个染色体的某段基因片段，如r1=2，r2=5，下图红色标注的区域就是即将发生逆转的基因片段
即将发生逆转操作的基因片段
（2）逆转这段基因片段，得到
染色体逆转
（3）比较新旧两个染色体的适应度分数
（1）如果逆转后新染色体适应度分数大于旧染色体，则逆转有意义
（2）如果逆转后新染色体适应度分数小于旧染色体，则逆转无意义
比较新旧两个染色体的适应度分数
至此，我们可以看到逆转操作的意义为
（1）单向性逆转，提供了比较逆转前后染色体优劣的机会
（2）使得逆转后的染色体变得更加优秀
（3）加速种群进化的质量
十二、python编程实现遗传算法
根据上述分析，我们可以很容易的用python编程实现GA算法来解决案例的TSP问题
种群的编码和初始化
种群的编码和初始化
适应度打分函数
适应度打分函数
轮盘赌法
轮盘赌法
染色体选择操作
染色体选择操作
染色体交叉操作
染色体交叉操作-1
染色体交叉操作-2
染色体变异操作
染色体变异操作
染色体逆转操作
染色体逆转操作
开始种群进化
开始种群进化
十三、结果分析
我们设置以下GA算法的参数来求解TSP案例
初值设置
根据这些初值，GA算法在100个种群进化了200代之后，找到的TSP的最优路线解为
Hopfield网络找到的TSP路线
最终GA算法找到的最优哈密顿回路为
GA算法找到的最优哈密顿回路
可以看到初值设置得当，GA算法非常迅速的在进化到第二代的时候就找到了最优解，且该最优解和案例的真实最优解一致
至此，用GA算法来求解TSP问题，我们可以总结出以下几点
（1）GA算法是求解TSP问题的一种启发式仿真算法
（2）GA算法通过模拟大自然优胜劣汰的进化法则，在参数设置合理的情况下，有可能直接找到真实最优解，比近似算法计算的效果要好
（3）GA算法的随机性非常强，种群规模、进化代数以及交叉变异的概率都会影响算法的寻优，从而算法可能会陷入局部最优解而没有及时跳出，最后可能找到不同的次优解
案例代码见：GA算法求解TSP问题
网友评论