[优化算法] 基因算法解决 TSP 问题

基因算法解决 TSP 问题

基因算法的运算方法包括

• Representation：将需要求解的问题的解空间用“基因”表示（连续变量用浮点型；离散变量用编码）
• Evaluate：评价个体的适应度
• Crossover：交叉父本的基因得到子代基因，增强搜索解空间的能力（个人认为是提高了搜索局部最优的能力）
• Mutation：通过变异扩大搜索解空间的能力（个人认为是提高搜索全局最优的能力）
• Selection：选择适应度最高的个体并保留，淘汰适应度低的个体

对于二进制编码Representation，基因算法的过程可以清晰地表示为：

1. 二进制编码表示，如基因A：01001和基因B：00111
2. 交叉运算，由交叉因子pc控制是否交叉一对父本基因的基因段。对于第i位，从（0，1）均匀分布中抽样x并和pc相比较，若x<pc，则将两个基因的第i位互换。比如对于第三位抽样x，若x<pc，则得到子代A：01101和子代B：00011
3. 变异运算，由变异因子pm控制是否使父本基因的某段基因产生变异，对于第i位，从（0，1）均匀分布中抽样x并和pm相比较，若x<pm，则将基因的第i位取反。比如对于基因B的第一位，同样从（0，1）均匀分布中抽样x并和pm相比较，若x<pm，则得到子代B：10011
4. 评价运算，计算各个个体（基因）的适应度，易知我们需要一个合适的评价函数，如f(A)=a和f(B)=b
5. 选择运算，通常使用轮盘赌的方法选择适应度高的种群，但其实这个可以根据自己的需要来自定义实现方式

Tips:

　　1. 变异因子pm和交叉因子pc是可以随着优化进行而自适应的。比如在优化起始阶段，pm和pc的值设置稍大可以提高搜索能力，而到了优化后期，pm和pc应当相应地减小，以强化其局部搜索能力。

　　2. 轮盘赌：简言之即得分高的个体其保留概率越大。比如对于基因A适应度/得分为f(A)=a，基因B为f(B)=b，那么A的保留概率为P_A=a/(a+b)，而P_B=b/(a+b)。

 

对于TSP问题：

　　首先，我们要有各个城市/地点之间的距离表distance_between_cities。(可以自己随机生成)

　　然后，TSP问题其实就是寻找一个合适的地点（循环的）排序R，使得对于R中的每个相邻元素city_i的距离之和最小。对于Multiple-Run Algorithm，可以不停生成不同的排序R_i，并计算相应的距离之和（即成本Cost）。而采用基因算法，其步骤如下：

1. 随机生成包含N个排序个体的初始排序种群R，并计算其成本Cost_original = evaluate(R)（这里假设已经有了评价运算函数evaluate，以下同理）。
2. 在迭代次数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（部分映射交叉）

Order Crossover（顺序交叉）

Position-based Crossover（基于位置的交叉）

交叉因子pc 通常较大，比如取pc=0.8。

变异运算

　　TSP问题中，变异运算只需要随机确定需要执行的数量，再依据变异因子pm随机地交换两个城市的位置即可。

评价函数

　　可以生成一个三维张量R_tensor，其中行列为各个城市，那么易知，矩阵元素若为“1/0”即是表示俩城市间是/否属于路径R_i。而通道则代表了种群中的不同个体，故R_tensor的大小为num_city * num_city * num_population。将各通道分别与距离表distance_between_cities作矩阵相乘得到矩阵Temp，取其对角元素求和并除以2就是路径R_i的距离之和，可以用来作为每个路径个体的适应度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问题中，多样性则体现在路径“基因段”的多样性。变异因子初始值pm₀通常在种群数量倒数与基因长度(TSP问题中就是路径长度=城市数量)倒数之间，即pm₀∈(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附近。

　　其计算过程将不同通道的R_i相乘再取对角元素求和除以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，整体过程类似，只是其交叉运算和变异运算都有不同。

交叉运算

　　假设有父本X_i和母本Y_i

　　子代Z_i = a*X_i + (1-a)*Y_i　　0 < a < 1 且a是随机生成的。

变异运算

　　变异运算可以用 x_new_i = x_old_i + Δx_i

　　有Δx_i|r > 0.5 = (x_{max, i} - x_i)*(2*(r - 0.5))^β   和　Δx_i|otherwise = (x_min, i - x_i)*(2*(0.5 - r))^β

　　其中r是从(0,1)均匀分布随机生成的，β通常大于1（比如可以取β = 3）。

 

关于算法的收敛性：还没有找资料深入研究过该算法的收敛性。直观地看，该算法可以高效地搜索解空间，并且会得到一个最优个体（感觉有点类似Multiple-Run）。

 

Acknowlegement:

https://blog.csdn.net/greedystar/article/details/80343841?utm_source=blogxgwz2