基因算法解决 TSP 问题
基因算法的运算方法包括
- Representation：将需要求解的问题的解空间用“基因”表示（连续变量用浮点型；离散变量用编码）
- Evaluate：评价个体的适应度
- Crossover：交叉父本的基因得到子代基因，增强搜索解空间的能力（个人认为是提高了搜索局部最优的能力）
- Mutation：通过变异扩大搜索解空间的能力（个人认为是提高搜索全局最优的能力）
- Selection：选择适应度最高的个体并保留，淘汰适应度低的个体
对于二进制编码Representation，基因算法的过程可以清晰地表示为：
- 二进制编码表示，如基因A：01001和基因B：00111
- 交叉运算，由交叉因子pc控制是否交叉一对父本基因的基因段。对于第i位，从（0，1）均匀分布中抽样x并和pc相比较，若x<pc，则将两个基因的第i位互换。比如对于第三位抽样x，若x<pc，则得到子代A：01101和子代B：00011
- 变异运算，由变异因子pm控制是否使父本基因的某段基因产生变异，对于第i位，从（0，1）均匀分布中抽样x并和pm相比较，若x<pm，则将基因的第i位取反。比如对于基因B的第一位，同样从（0，1）均匀分布中抽样x并和pm相比较，若x<pm，则得到子代B：10011
- 评价运算，计算各个个体（基因）的适应度，易知我们需要一个合适的评价函数，如f(A)=a和f(B)=b
- 选择运算，通常使用轮盘赌的方法选择适应度高的种群，但其实这个可以根据自己的需要来自定义实现方式
Tips:
1. 变异因子pm和交叉因子pc是可以随着优化进行而自适应的。比如在优化起始阶段，pm和pc的值设置稍大可以提高搜索能力，而到了优化后期，pm和pc应当相应地减小，以强化其局部搜索能力。
2. 轮盘赌：简言之即得分高的个体其保留概率越大。比如对于基因A适应度/得分为f(A)=a，基因B为f(B)=b，那么A的保留概率为PA=a/(a+b)，而PB=b/(a+b)。
对于TSP问题：
首先，我们要有各个城市/地点之间的距离表distance_between_cities。(可以自己随机生成)
然后，TSP问题其实就是寻找一个合适的地点（循环的）排序R，使得对于R中的每个相邻元素cityi的距离之和最小。对于Multiple-Run Algorithm，可以不停生成不同的排序Ri，并计算相应的距离之和（即成本Cost）。而采用基因算法，其步骤如下：
- 随机生成包含N个排序个体的初始排序种群R，并计算其成本Cost_original = evaluate(R)（这里假设已经有了评价运算函数evaluate，以下同理）。
- 在迭代次数k<设置的最大迭代次数k_max时，执行以下步骤：
-
- 交叉运算 R_crossover=crossover(R)
- 变异运算 R_mutation=mutation(R_crossover)
- 评价运算 Cost=evaluate(R_mutation)
- 选择运算 [R, R_best, Cost_best]=selection(R_mutation, Cost)
交叉运算
交叉运算有几种方式，本次实现采用的是基于位置的交叉。首先将种群分为父本和母本，随机确定父本中要交换的部分并复制到子代，然后将母本的其他基因按顺序复制到子代。代码实现就需要关注避免重复的部分，可以这样实现：随机取出父本中要保留的基因部分F_section（要注意的是这是一段分立的基因），再顺序逐个取出母本基因元素M_element生成和F_section同等大小的M_section，两向量相减再求元素积，为0则表示母本基因元素M_element在父本基因段F_section中已经出现了。利用矩阵、向量运算可以避免循环查询父本基因段中是否有母本元素，以此实现高效率（因为矩阵运算有相关的优化）。
Partial-Mapped Crossover（部分映射交叉）
![[优化算法] 基因算法解决 TSP 问题](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pLzEyZWJhNjk4ZTc2NWE4YmZjMThjNzQzMWU3MWYzOGQzMS5qcGc%3D.jpg?w=700 "[优化算法] 基因算法解决 TSP 问题")
Order Crossover（顺序交叉）
![[优化算法] 基因算法解决 TSP 问题](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pLzEyZWJhNjk4ZTc2NWE4YmZjMThjNzQzMWU3MWYzOGQzMi5qcGc%3D.jpg?w=700 "[优化算法] 基因算法解决 TSP 问题")
Position-based Crossover（基于位置的交叉）
![[优化算法] 基因算法解决 TSP 问题](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pLzEyZWJhNjk4ZTc2NWE4YmZjMThjNzQzMWU3MWYzOGQzMy5qcGc%3D.jpg?w=700 "[优化算法] 基因算法解决 TSP 问题")
交叉因子pc 通常较大，比如取pc=0.8。
变异运算
TSP问题中，变异运算只需要随机确定需要执行的数量，再依据变异因子pm随机地交换两个城市的位置即可。
评价函数
可以生成一个三维张量R_tensor，其中行列为各个城市，那么易知，矩阵元素若为“1/0”即是表示俩城市间是/否属于路径Ri。而通道则代表了种群中的不同个体，故R_tensor的大小为num_city * num_city * num_population。将各通道分别与距离表distance_between_cities作矩阵相乘得到矩阵Temp，取其对角元素求和并除以2就是路径Ri的距离之和，可以用来作为每个路径个体的适应度Cost。
选择运算
有两部分，1.挑选出最优的个体R_best与对应的适应度Cost_best。2.挑选出较优的种群的一部分，作为下一次迭代的父代。（因为交叉运算中通常会使得种群数量减半，所以这里可以加倍来使种群维持在定值）。
自适应的变异因子pm：利用种群多样性
在优化初期，根据种群多样性population_diversity保持在某个值S附近来调整pm，比如population_diversity < S时，需要提升种群多样性，故取c>1，令pm=pm*c提升变异的概率，同理population_diversity > S时，令pm=pm/c降低变异概率。对于浮点型算法，求种群多样性是采用了标准差，而对应到TSP问题中，多样性则体现在路径“基因段”的多样性。变异因子初始值pm0通常在种群数量倒数与基因长度(TSP问题中就是路径长度=城市数量)倒数之间，即pm0∈(min{1/num_population, 1/num_city}, max{1/num_population, 1/num_city})。
举个例子，路径A：1354267和路径B：5423716的相似基因段有：54,42,71，故在此定义A与B的非相似度为7-3=4.对于路径C=A，其非相似度为7-7=0，易知此时非相似度∈[0,7]。对于确定的城市数量num_city，非相似度=城市数-相似基因段数量，可以考虑用因子S将种群控制在非相似度在0.1*num附近。
其计算过程将不同通道的Ri相乘再取对角元素求和除以2即使相似基因段数量。如路径1342和路径4123，计算后得到值为2，即12和34。
|
|
1 |
2 |
3 |
4 |
| 1 |
0 |
1 |
1 |
0 |
| 2 |
1 |
0 |
0 |
1 |
| 3 |
1 |
0 |
0 |
1 |
| 4 |
0 |
1 |
1 |
0 |
|
|
1 |
2 |
3 |
4 |
| 1 |
0 |
1 |
0 |
1 |
| 2 |
1 |
0 |
1 |
0 |
| 3 |
0 |
1 |
0 |
1 |
| 4 |
1 |
0 |
1 |
0 |
关于浮点Representation，整体过程类似，只是其交叉运算和变异运算都有不同。
交叉运算
假设有父本Xi和母本Yi
子代Zi = a*Xi + (1-a)*Yi 0 < a < 1 且a是随机生成的。
变异运算
变异运算可以用 x_newi = x_oldi + Δxi
有Δxi|r > 0.5 = (xmax, i - xi)*(2*(r - 0.5))β 和 Δxi|otherwise = (xmin, i - xi)*(2*(0.5 - r))β
其中r是从(0,1)均匀分布随机生成的，β通常大于1（比如可以取β = 3）。
关于算法的收敛性：还没有找资料深入研究过该算法的收敛性。直观地看，该算法可以高效地搜索解空间，并且会得到一个最优个体（感觉有点类似Multiple-Run）。
Acknowlegement:
https://blog.csdn.net/greedystar/article/details/80343841?utm_source=blogxgwz2