基于遗传算法和模拟退火解决TSP问题（源码+项目说明）.zip

# 高级搜索解决旅行商问题 ## 实验题目 使用模拟退火和遗传算法解决TSP问题 ## 实验内容 ### 模拟退火算法 #### 1.算法原理 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 #### 2.伪代码 (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L (2) 对k=1, …, L做第(3)至第6步： (3) 产生新解S′ (4) 计算增量ΔT=C(S′)-C(S)，其中C(S)为评价函数 (5) 若ΔT<0则接受S′作为新的当前解，否则以概率exp(-ΔT/T)接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。 终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少，且T->0，然后转第2步。 #### 3.关键代码展示 ##### 局部搜索策略 * 简单交换两个城市 ```python def nextStatus_swap(self): temp=deepcopy(self.path) left = np.random.randint(0, self.dim - 1) right = np.random.randint(left + 1, self.dim) # 交换位置 temp[left],temp[right]=temp[right],temp[left] return temp ``` * 交换城市并且翻转 ```python def nextStatus_inversion(self): # 随机产生下一个状态 temp=deepcopy(self.path) left = np.random.randint(0, self.dim - 1) right = np.random.randint(left + 1, self.dim) # 交换位置 while left < right: temp[left],temp[right]=temp[right],temp[left] left+=1 right-=1 return temp ``` * 找到城市放到开头 ```python # 随机找到两个点，要求两个点不能相同，提取该序列放到路径的头部 def nextStatus_head(self): left = np.random.randint(0, self.dim - 1) right = np.random.randint(left + 1, self.dim) new_index=np.arange(left,right+1) new_index=np.append(new_index,np.delete(range(self.dim),new_index)) return self.path[new_index] ``` ##### 爬山法 未加入退火策略的随机算法 ```python def search_HC(self): t=self.t0 while t>=self.te: for i in range(self.n): next_status=self.nextStatus_head() # 获取下一个状态 next_distance=self.calDistance(next_status) # 计算下一个状态的路径长 df=next_distance-self.length # 是否接受解 if df<0: # 必须优于当前的解才会接受 self.length=next_distance self.path=next_status self.lengths.append(self.length) self.count+=1 t*=self.q pass ``` ##### 退火法 加入退火策略的随机算法 ```python def search_SA(self): t=self.t0 while t>=self.te: for i in range(self.n): next_status=self.nextStatus_head() # 获取下一个状态 next_distance=self.calDistance(next_status) # 计算下一个状态的路径长 df=next_distance-self.length # 是否接受解 if df<0: self.length=next_distance self.path=next_status else: p=math.exp(-df/t) if p>=random.random(): # 不优于当前解也有一定机率接受 self.length=next_distance self.path=next_status self.lengths.append(self.length) self.count+=1 t*=self.q ``` #### 4.创新点 在创新点方面主要是尝试了多种局部搜索策略并尝试了爬山法与退火法进行对比，具体代码可以查看[关键代码展示](#3关键代码展示-1) #### 5.优化与比较 ##### 爬山法与退火法比较 测试集lin105，局部搜索方法:交换城市并且翻转 | 算法策略 | 最短距离 | 时间 | 结果 | | -------- | -------- | ---- | ------------------------------------------------------------ | | 爬山法 | 15853.5 | 13.7 | <img src="D:\Programme\Python\TSP\lin105_HC_test.png" alt="lin105_HC_test" style="zoom:50%;" /> | | 退火法 | 15023.2 | 14.1 | <img src="D:\Programme\Python\TSP\lin105_SA_test.png" alt="lin105_SA_test" style="zoom:50%;" /> | 通过比较可以发现爬山法收敛速度极快并陷入局部最优，退火法收敛速度较慢但没有陷入局部最优。另外在速度方面二者相差不多。 ##### 局部搜索策略比较 测试集lin105 | 局部搜索策略 | 最短路径 | 时间 | | ---------------- | -------- | ------ | | 简单交换两个城市 | 18767.1 | 13.3 | | 交换城市并且翻转 | 14723.3 | 14.9秒 | | 找到城市放到开头 | 16423.1 | 21.9秒 | 从测试结果可以看出：第二种局部搜索策略更优。 #### 6.测试结果 | 测试集 | 最短路径 | 时间 | 效果图 | 与最优解误差 | | ------ | -------- | ------- | ------------------------------------------------------------ | ------------ | | lin105 | 14919.5 | 14.5秒 | <img src="C:\Users\24293\AppData\Roaming\Typora\typora-user-images\image-20220507164316163.png" alt="image-20220507164316163" style="zoom:50%;" /> | 3.9% | | gr120 | 1744.4 | 15秒 | <img src="C:\Users\24293\AppData\Roaming\Typora\typora-user-images\image-20220507164802990.png" alt="image-20220507164802990" style="zoom:50%;" /> | 4.56% | | rd100 | 8059.9 | 13.75秒 | <img src="C:\Users\24293\AppData\Roaming\Typora\typora-user-images\image-20220507164614454.png" alt="image-20220507164614454" style="zoom:50%;" /> | 最优 | | pr107 | 45120.6 | 15.2秒 | <img src="C:\Users\24293\AppData\Roaming\Typora\typora-user-images\image-20220507164521533.png" alt="image-20220507164521533" style="zoom:50%;" /> | 2.12% | 从测试结果上来看，模拟退火表现优异，有一定的概率获得最优解。 ### 遗传算法 #### 1.算法原理 遗传算法起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。 #### 2.伪代码 1.评估每条染色体所对应个体的适应度。 2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。 3.抽取父母双方的染色体，进行交叉，产生子代。 4.对子代的染色体进行变异。 5.重复2，3，4步骤，直到新种群的产生或者迭代数结束。 #### 3.关键代码展示 ##### 选择算子 * 轮盘赌策略：个体适应度越高，被选择的概率越大 ``` python # 选择个体轮盘赌策略 def select_roulette(self): fits=self.groupFitness() temp_group=np.array(self.group) new_group_index=np.random.choice(range(self.og),size=self.mc,replace=True,p=fits/fits.sum()) # 轮盘赌选出相应个体的索引 new_group=temp_group[new_group_index] # 选出新个体 self.group=new_group.tolist() self.og=self.mc ``` * 精英保留策略：依某种策略生成新种群后，用当代最优个体随机替换新种群的某个体，或者直接替换最差个体 ``` python # 精英保留策略 def select_optimal(self): fits=self.groupFitness() temp_group=np.array(self.group) new_group_index=np.random.choice(self.og,size=self.mc,replace=True,p=fits/fits.sum()) # 先进行轮盘赌策略筛选个体 new_group=temp_group[new_group_index] new_fits=fits[new_group