元启发式算法 | 遗传算法(GA)解决TSP问题(Python)
文章目录
1.GA基本概念与算法最简单的python实现
遗传算法（Genetic Algorithm, GA），是一种通过模拟生物自然进化过程的随机搜索算法，主要思想是模拟生物进化论中自然选择和遗传学机理的生物进化过程。废话不多说，看看实现过程。
这里列出几个算法的名词及定义：
- 基因（gene）：顾名思义每个生物体都有独特的DNA遗传信息，用基因来作为个体的标签，区别每个个体。
- 个体（individual）：每个个体代表一个可行解。例如，一个可行解就是TSP的一个个体：route=[1,2,3,4,5,6,7,8,9,10].
- 种群（population）：个体的集合，可以看做是可行解的集合。在TSP问题中就是路径的排列组合了。
- 繁衍代数（generation）：生物每一次繁衍就是一次迭代。代码里的最大循环次数。
- 进化(evolution)：种群逐渐适应生存环境，品质不断得到改良（生物的进化是以种群的形式进行的）。在具体问题中就表现为解的质量越来越好。
基本操作：
- 编码(coding)：将个体编码成基因的形式。如二进制编码、浮点编码法、符号编码法等等。
- 解码(decoding)：编码的逆操作。
- 适应度(fitness)：度量某个物种对于生存环境的适应程度，这里可以理解为目标函数。
- 选择(selection)：自然选择，优胜劣汰，按适应度大小从种群中随机选择若干个体用于产生下一代。（优秀个体有更大概率被选择，本着优秀个体必然含优秀基因的原则）
- 交叉(crossover)：被选中的个体进行基因重组或杂交，组成新的个体。
- 变异(mutation)：在基因重组过程中（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
花里胡哨一大堆，遗传算法核心思想说白了就一句话：把优秀的基因传递下去（个人认为这也是算法最精髓的一点，很好的体现了“进化”的思想，很简洁）
光说不练假把式，上代码Python：
import numpy as np
import random,time
import matplotlib.pyplot as plt
from GetData import *
class GA():
def __init__(self,disMatrix,MaxGens,pop_size,cross_rate,mutation_rate):
"pop_size > 1 "
self.disMatrix = disMatrix
self.gene_size = len(disMatrix) # 基因长度,路径长度，0为Depot
self.pop_size = pop_size #种群大小，每一代解的数量
self.MaxGens = MaxGens #最大迭代次数
self.cross_rate = cross_rate #交叉概率
self.mutation_rate = mutation_rate #变异概率
def get_init_solution(self):
init_routes = np.array([])
route = np.arange(1,self.gene_size) # 生成初始解
for i in range(self.pop_size):
np.random.shuffle(route)
init_routes = np.append(init_routes,route)
return init_routes.reshape(self.pop_size,self.gene_size-1).astype(int)
def get_route_distance(self,route):
routes = list(route)
routes = [0] + routes +[0]
total_distance = 0
for i,n in enumerate(routes):
if i != 0 :
total_distance = total_distance + self.disMatrix[last_pos][n]
last_pos = n
return total_distance
def get_fitness(self,pop_routes):
fitness = []
for route in pop_routes:
fitness.append(self.get_route_distance(route))
fitness = 1 - fitness/np.sum(fitness) # 归一化后取反
return np.array(fitness)
def select(self,pop_routes):
fitness = self.get_fitness(pop_routes)
#轮盘赌的形式进行选择，适应度高的被选中的概率就大
selected_label = np.random.choice(range(self.pop_size), size=self.pop_size, replace=True, p=fitness/np.sum(fitness))
return pop_routes[selected_label]
def crossover(self,pop_routes):
for i in range(self.pop_size):
if np.random.rand() < self.cross_rate :
obj = pop_routes[np.random.randint(self.pop_size)] #随机选一个交叉对象，也可以选到自己,生成新的一代
cross_point = np.random.randint(self.gene_size) #在DNA片段中随机选一个交叉点
new_one = np.hstack((pop_routes[i][0:cross_point],obj[cross_point::])) #从交叉点往后交换基因片段
if len(set(new_one)) < self.gene_size-1 : #交换片段后可能是无效解，即有重复元素,处理一下
new_one__ = []
for num in new_one:
if num not in new_one__:
new_one__.append(num)
else:
for j in range(1,self.gene_size):
if j not in new_one__:
new_one__.append(j)
pop_routes[i] = new_one__
continue
pop_routes[i] = new_one
return pop_routes
def mutate(self,pop_routes):
for i in range(self.pop_size):
if np.random.rand() < self.mutation_rate :
pos1 = np.random.randint(0,self.gene_size-1) # 随机选取某一个基因位置发生变异
pos2 = np.random.randint(0,self.gene_size-1)
pop_routes[i][pos1],pop_routes[i][pos2] = pop_routes[i][pos2],pop_routes[i][pos1] #交换位置，完成变异
return pop_routes
def ga_evolution(self):
routes = self.get_init_solution() #生成初始解
result=[] #记录迭代过程中的信息
while(self.MaxGens):
self.MaxGens -=1
routes = self.select(routes)
routes = self.crossover(routes)
routes = self.mutate(routes)
result.append(max(self.get_fitness(routes))) #记录一下迭代过程中的信息
plt.plot(range(len(result)),result)
plt.show()
idx = np.where(self.get_fitness(routes)==max(self.get_fitness(routes))) #挑出适应度最大的，可能不止一个
best_id = random.sample(list(idx[0]), 1) #从中拿一个
best_route = routes[best_id]
return np.squeeze(best_route).tolist()
if __name__ == "__main__":
data=GetData()
solomon_data = data.read_solomon(path ='R101.txt',customerNum=7) #定义多少个点
dismatrix = data.get_euclidean_distance_matrix(solomon_data.locations)
ga = GA(disMatrix=dismatrix,MaxGens=500,pop_size=100,cross_rate=0.3,mutation_rate=0.1)
best_route = ga.ga_evolution()
print('best_route:',best_route)
print('best distance:',ga.get_route_distance(best_route))
data.plot_route(solomon_data.locations,[0]+best_route+[0])
GetData.py 文件 见https://blog.csdn.net/DCXY71/article/details/110991670 （或运小筹github上获取）
R101.txt 为solomon数据集
结果：
2.对GA的思考和改进
这是最最最简单的实现，运行完你会发现好像每次运行结果都不太一样，有时候效果不是很好，尤其点数稍微增加… 4个参数需要反复调整，很是麻烦。
ga = GA(disMatrix=dismatrix,MaxGens=500,pop_size=100,cross_rate=0.3,mutation_rate=0.1)
2.1 GA改进思路
在众多元启发式算法中我个人是比较喜欢遗传算法的，可操作性高，适用各类问题，非常巧妙的模拟了生物“进化”的思想。GA虽然名字看起来花里胡哨，本质其实就是蒙特卡洛搜索。这里抛开花里胡哨的名字，看看每一步操作背后的含义。
-
编码，解码：对问题的建模，定义解的形式，一个好的编/解码（建模）直接决定了后续操作的复杂度和解的质量，很大程度上决定了算法效率。在TSP问题中比较简单直观的就是自然数编码，每个节点代表一个基因。还有没有其他更好的编码方式，需要根据问题查阅更多论文了。
-
适应度(fitness)：是种群进化淘汰的评价指标，这里我用总的路径长度为指标。但是如果某个问题目标函数很复杂，其实可以考虑间接的评价或者设计更复杂的评价指标。这里我没有设计种群的评价指标，其实种群平均适应度，中位数等等指标一定程度上反应了进化（搜索）的方向，可以针对性的进行设计。
def get_fitness(self,pop_routes):
fitness = []
for route in pop_routes:
fitness.append(self.get_route_distance(route))
fitness = 1 - fitness/np.sum(fitness) # 归一化后取反
return np.array(fitness)
- 选择(selection)：进化优胜劣汰就体现在这一步骤，从父辈（上一代可行解集合）中挑选出优秀的个体生成下一代。这里我采用常规轮盘赌的方式在当前可行解集合中进行选择和淘汰，质量越好的解被挑中概率越大（同一个个体可以被选择多次），被选中的解参与生成下一代。为了加快收敛其实可以考虑， p = e f i t n e s s ∑ e i f i t n e s s p=\frac{e^{fitness}}{\sum{e_{i}^{fitness}}} p=∑eifitnessefitness ，增大适应度高的个体被选中的概率。其次，精英保护策略也可以加快收敛，即直接选择适应度最高的几个个体进入下一环节，不进行概率选择。
def select(self,pop_routes):
fitness = self.get_fitness(pop_routes)
#轮盘赌的形式进行选择，适应度高的被选中的概率就大
selected_label = np.random.choice(range(self.pop_size), size=self.pop_size, replace=True, p=fitness/np.sum(fitness))
return pop_routes[selected_label]
-
交叉(crossover)：这一步本质上就是领域搜索，通过个体基因的交换生成新的个体（通过当前解搜索附近领域可行解），好的交叉操作设计能有效的进行搜索，这里我用的部分匹配法，按一个固定概率
self.cross_rate对部分基因片段交换。当然，改进的地方有很多，比如换一种基因交换方式，增加领域搜索效率；不采用固定概率，用动态的概率对动态大小的基因片段进行交换如模拟退火的思想。
def crossover(self,pop_routes):
for i in range(self.pop_size):
if np.random.rand() < self.cross_rate :
obj = pop_routes[np.random.randint(self.pop_size)] #随机选一个交叉对象，也可以选到自己,生成新的一代
....
有很多交叉方法，具体问题可根据问题特征进行设计或查阅相关文献例如：
部分匹配法（Partially Matching Crossover， PMX）
循环交叉法（Cycle Crossover， CX）
次序交叉法1（Order Crossover， OX1）
次序交叉法2（Order Crossover， OX2）
基于位置的交叉法（Position Based Crossover， POS）
交替位置交叉法（Alternating Position Crossover，APX）
-
变异(mutation)：变异操作其实就是随机扰动因子，在进行领域搜索的过程中如果问题很复杂容易陷入局部最优，变异的操作就能跳出局部最优，当然大部分时候的变异并不会提高解的质量，甚至会更差，这也符合生物进化规律，但总有一些关键的变异能带领整个群体进化。
替换变异（Displacement Mutation， DM）
交换变异（Exchange Mutation， EM）
插入变异（Insertion Mutation， IM）
简单倒位变异（Simple Inversion Mutation， SIM）
倒位变异（Inversion Mutation， IVM）
争夺变异（Scramble Mutation， SM）
2.2 GA优缺点
GA有其独特的优点：
- 直接对结构对象进行操作，对目标函数没有限定，没有可导性和连续性的要求；
- 具有内在的隐并行性和更好的全局寻优能力；
- 基于随机概率的搜索，不需要严格的规则和约束，就能自动在解空间内搜索空间，自适应地调整搜索方向。
局限性：
- 没有理论证明能得到最优解 （元启发式算法通病了）
- 搜索容易超出解空间（需要设计好交叉和变异操作）。
- 每一步搜索需要更新整个种群，花费时间太长，不适于高维数据搜索。
- 依赖建模和规则设计，例如编码、解码、交叉、变异这些操作和规则非常依赖人的经验和建模，不同人对同一问题写出来的效果可以完全不一样。