南平公司做网站,网站如何做软文推广,阿里云 wordpress rds,百度的网站计算机设计大赛国奖作品_5. 模拟退火求解旅行商问题
本系列是2021年中国大学生计算机设计大赛作品“环境监测无人机航线优化”的相关文档#xff0c;获得2021年西北赛区一等奖#xff0c;国赛三等奖。学生习作#xff0c;只供大家参考。 计算机设计大赛国奖作品_1. 项目概要…计算机设计大赛国奖作品_5. 模拟退火求解旅行商问题
本系列是2021年中国大学生计算机设计大赛作品“环境监测无人机航线优化”的相关文档获得2021年西北赛区一等奖国赛三等奖。学生习作只供大家参考。 计算机设计大赛国奖作品_1. 项目概要 计算机设计大赛国奖作品_2. 报名材料 计算机设计大赛国奖作品_3. 需求分析 计算机设计大赛国奖作品_4. 界面设计 计算机设计大赛国奖作品_5. 核心算法 计算机设计大赛国奖作品_6. 测试报告 [计算机设计大赛国奖作品_7. 安装使用] [计算机设计大赛国奖作品_8. 项目总结] [计算机设计大赛国奖作品_9. PPT] 作品名称环境监测无人机航线优化 第三章 详细设计 3.2 模拟退火求解旅行商问题
3.2.1 模拟退火算法概述
模拟退火算法是解决大规模组合优化问题的常用方法可以解决无人机飞行路线的路径优化问题。
模拟退火算法结构简单由温度更新函数、状态产生函数、状态接受函数和内循环、外循环终止准则构成。 温度更新函数是指退火温度缓慢降低的实现方案也称冷却进度表状态产生函数是指由当前解随机产生新的候选解的方法状态接受函数是指接受候选解的机制通常采用Metropolis准则。 外循环是由冷却进度表控制的温度循环内循环是在每一温度下循环迭代产生新解的次数也称Markov链长度。
模拟退火算法的基本步骤如下
1 随机产生初始解 X_0
2在温度 TkT_kTk下进行 LkL_kLk 次循环迭代由当前解 XoldX_{old}Xold 产生新的候选解 XnewX_{new}Xnew并按 Metropolis 接受准则以一定的概率接受候选解 XnewX_{new}Xnew 作为当前解 ∆EE(Xnew)−E(Xold)∆EE(X_{new})-E(X_{old} )∆EE(Xnew)−E(Xold) P{1,∆E0exp((−∆E)/Tk),∆E≥0P \begin{cases} 1 , ∆E0 \\ exp((-∆E)/T_k ),∆E≥0 \end{cases} P{1,∆E0exp((−∆E)/Tk),∆E≥0
这里 EoldE_{old}Eold、EnewE_{new}Enew分别是当前解 XoldX_{old}Xold、新解 XnewX_{new}Xnew 的目标函数值。
3按照冷却进度表控制退火温度从温度初值缓慢降低直到达到温度终值结束。
模拟退火算法要从当前解的邻域中产生新的候选解。新解的产生机制是在当前解序列的基础上进行变换操作随机改变序列中某些点的排列次序常见的基本变换操作有交换算子(Swap Operator)、反序算子Inversion Operator、移位算子(Move Operator)等。
交换算子将当前路径 S_now 中的第 i 个城市 C_i 与第 j 个城市 C_j 的位置交换得到新路径 S_swap
S_now C_1⋯C_(i-1)∙(C_i)∙C_(i1)⋯C_(j-1)∙(C_j)∙C_(j1)⋯C_nS_swap C_1⋯C_(i-1)∙(C_j)∙C_(i1)⋯C_(j-1)∙〖(C〗i)∙C(j1)⋯C_n
反序算子也称2-opt将当前路径 S_now 中从第 i 个城市 C_i 到第 j 个城市 C_j 之间的城市排列顺序反向翻转得到新路径 S_inv
S_now C_1⋯C_(i-1)∙(C_i∙C_(i1)⋯C_(j-1)∙C_j)∙C_(j1)⋯C_nS_inv C_1⋯C_(i-1)∙〖(C〗j∙C(j-1)⋯C_(i1)∙C_i)∙C_(j1)⋯C_n 以下两节因涉及待发表论文暂不公开。
3.2.2 操作算子的等价关系
略
3.2.3 联合算子改进算法
略
3.3 模拟退火求解旅行商问题 Python 程序
# SATSP_demo_V1_20201212.py
# 模拟退火算法求解旅行商问题 DEMO 程序
# v1.0:
# 模拟退火求解旅行商问题TSP基本算法
# (1) 直接读取城市坐标数据CTSP31
# (2) 仅采用2-交换方式产生新解
# (3) 图形输出最优路径图优化过程图
# (4) 城市间距离取整
# Copyright 2020 YouCans, XUPT
# Crated2020-12-15# -*- coding: utf-8 -*-
import math # 导入模块 math
import random # 导入模块 random
import pandas as pd # 导入模块 pandas 并简写成 pd
import numpy as np # 导入模块 numpy 并简写成 np
import matplotlib.pyplot as plt # 导入模块 matplotlib.pyplot 并简写成 pltnp.set_printoptions(precision4)
pd.set_option(display.max_rows, 20) # youcans
pd.set_option(expand_frame_repr, False)
pd.options.display.float_format {:,.2f}.format# 子程序初始化模拟退火算法的控制参数
def initParameter():# custom function initParameter():# Initial parameter for simulated annealing algorithmtInitial 100.0 # 设定初始退火温度(initial temperature)tFinal 1 # 设定终止退火温度(stop temperature)alfa 0.985 # 设定降温参数T(k)alfa*T(k-1)nMarkov 500 # Markov链长度也即内循环运行次数return alfa,nMarkov,tInitial,tFinal# 子程序计算各城市间的距离得到距离矩阵
def getDistMat(nCities, coordinates):# custom function getDistMat(nCities, coordinates):# computer distance between each 2 CitiesdistMat np.zeros((nCities,nCities)) # 初始化距离矩阵for i in range(nCities):for j in range(i,nCities):# np.linalg.norm 求向量的范数默认求 二范数得到 s1、s2 间的距离distMat[i][j] distMat[j][i] round(np.linalg.norm(coordinates[i]-coordinates[j]))return distMat # 城市间距离取整四舍五入# 子程序计算 TSP 路径长度
def caltourMileage(tour, nCities, distMat):# custom function caltourMileage(nCities, tour, distMat):# compute mileage of the given tourmileageTour 0.0 # 路径长度 置 0for i in range(nCities-1): # dist(0,1),...dist((n-2)(n-1))mileageTour distMat[tour[i], tour[i1]]mileageTour distMat[tour[nCities-1], tour[0]] # dist((n-1),0)return round(mileageTour) # 路径总长度取整四舍五入# 子程序交换操作算子
def mutateSwap(tour, nCities):# custom function mutateSwap(nCities, tourNow)# produce a mutation tour with 2-Swap operator# swap the position of two Cities in the given tour# 在 [0,n) 产生 2个不相等的随机整数 s1,s2s1 np.random.randint(nCities) # 产生第一个 [0,n) 区间内的随机整数while True:s2 np.random.randint(nCities) # 产生一个 [0,n) 区间内的随机整数if s1!s2: break # 保证 s1, s2 不相等tourSwap tour.copy() # 将给定路径复制给新路径 tourSwap#tourSwap[s1] tour[s2] # 交换 城市 s1 和 s2 的位置#tourSwap[s2] tour[s1]# 交换 城市 s1 和 s2 的位置————简洁的实现方法# 特别注意深入理解深拷贝和浅拷贝的区别注意内存中的变化谨慎使用tourSwap[s1],tourSwap[s2] tour[s2],tour[s1]return tourSwap# 子程序绘制 TSP 路径图
def plot_tour(tour, value, coordinates):# custom function plot_tour(tour, nCities, coordinates)num len(tour)x0, y0 coordinates[tour[num - 1]]x1, y1 coordinates[tour[0]]plt.scatter(int(x0), int(y0), s15, cr) # 绘制城市坐标点 C(n-1)plt.plot([x1, x0], [y1, y0], cb) # 绘制旅行路径 C(n-1)~C(0)for i in range(num - 1):x0, y0 coordinates[tour[i]]x1, y1 coordinates[tour[i 1]]plt.scatter(int(x0), int(y0), s15, cr) # 绘制城市坐标点 C(i)plt.plot([x1, x0], [y1, y0], cb) # 绘制旅行路径 C(i)~C(i1)plt.xlabel(Total mileage of the tour:{:.1f}.format(value))plt.title(Optimization xupt of TSP{:d}.format(num)) # 设置图形标题plt.show()def main():# 主程序# 读取旅行城市位置的坐标coordinates np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0],[880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0],[1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0],[725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],[300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0],[1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0],[420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0],[685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0],[475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0],[830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0],[1340.0, 725.0], [1740.0, 245.0]coordinates np.array([[1164.6,399.2],[1172.0,391.3],[1214.8,312.2],[1065.4,295.9],[911.1,299.7],[876.8,437.7],[1062.7,384.7],[1116.5,408.2],[1083.3,228.4],[1266.3,457.5],[1253.5,438.8],[1233.8,418.0],[1144.8,380.3],[1125.3,378.7],[1017.4,365.6],[1170.0,366.5],[1136.0,347.6],[1187.8,320.4],[1172.7,318.6],[1201.9,302.6],[1193.0,260.8],[1158.9,286.8],[1130.0,282.1],[1143.1,305.2],[1132.3,231.6],[1103.5,200.2],[1037.3,360.3],[1089.5,342.7],[1040.6,306.7],[1067.1,265.7],[1027.3,250.4]]) # CTSP31nCities coordinates.shape[0] # 根据输入的城市坐标 获得城市数量 nCitiesdistMat getDistMat(nCities,coordinates) # 调用子程序计算城市间距离矩阵tourNow np.arange(nCities) # 产生初始路径返回一个初值为0、步长为1、长度为n 的排列tourBest tourNow.copy() # 初始化最优路径将 tourNow 复制给 tourBestvalueNow caltourMileage(tourNow,nCities,distMat) # 计算当前路径的总长度valueBest valueNow # 初始化最优路径的总长度alfa,nMarkov,tInitial,tFinal initParameter() # 调用子程序获得模拟退火算法的设置参数# 开始模拟退火优化过程iter 0 # 外循环迭代次数计数器recordBest [] # 初始化 最优路径记录表recordNow [] # 初始化 最优路径记录表tNow tInitial # 初始化 当前温度(current temperature)while tNow tFinal: # 外循环直到当前温度达到终止温度时结束# 在当前温度下进行充分次数(nMarkov)的状态转移以达到热平衡for k in range(nMarkov): # 内循环循环次数为Markov链长度# 产生新解通过在当前解附近随机扰动而产生新解新解必须在 [min,max] 范围内tourNew mutateSwap(tourNow,nCities) # 通过 交换操作 产生新路径valueNew caltourMileage(tourNew,nCities,distMat) # 计算当前路径的总长度# 接受判别按照 Metropolis 准则决定是否接受新解if valueNew valueNow: # 更优解如果新解的目标函数好于当前解则接受新解accept Trueelse: # 容忍解如果新解的目标函数比当前解差则以一定概率接受新解deltaE valueNew - valueNowpAccept math.exp(-deltaE/tNow) # 计算容忍解的状态迁移概率if pAccept random.random():accept Trueelse:accept False# 保存新解if accept True: # 如果接受新解则将新解保存为当前解tourNow[:] tourNew[:]valueNow valueNewif valueNew valueBest: # 如果新解的目标函数好于最优解则将新解保存为最优解tourBest[:] tourNew[:]valueBest valueNew# 完成当前温度的搜索保存数据和输出recordBest.append(valueBest) # 将本次温度下的最优路径长度追加到 最优路径记录表recordNow.append(valueNow) # 将当前路径长度追加到 当前路径记录表print(i:{}, t(i):{:.2f}, valueNow:{:.1f}, valueBest:{:.1f}.format(iter,tNow,valueNow,valueBest))# 缓慢降温至新的温度降温曲线T(k)alfa*T(k-1)tNow tNow * alfaiter iter 1# 结束模拟退火过程print(Best xupt: \n, tourBest)print(Best value: {:.1f}.format(valueBest))# 图形化显示优化结果figure1 plt.figure() # 创建图形窗口 1plot_tour(tourBest,valueBest,coordinates)figure2 plt.figure() # 创建图形窗口 2plt.title(Optimization youcans of TSP{:d}.format(nCities)) # youcansxuptplt.plot(np.array(recordBest),b-, labelBest) # 绘制 recordBest曲线plt.plot(np.array(recordNow),g-, labelNow) # 绘制 recordNow曲线plt.xlabel(iter) # 设置 x轴标注plt.ylabel(mileage of tour) # 设置 y轴标注plt.legend() # 显示图例plt.show()exit()if __name__ __main__:main()版权声明
youcansxupt 原创作品转载必须标注原文链接(https://blog.csdn.net/youcans/article/details/124004941)
Copyright 2022 youcans, XUPT Crated2022-4-15 计算机设计大赛国奖作品_1. 项目概要 计算机设计大赛国奖作品_2. 报名材料 计算机设计大赛国奖作品_3. 需求分析 计算机设计大赛国奖作品_4. 界面设计 计算机设计大赛国奖作品_5. 核心算法 计算机设计大赛国奖作品_6. 测试报告 [计算机设计大赛国奖作品_7. 安装使用] [计算机设计大赛国奖作品_8. 项目总结] [计算机设计大赛国奖作品_9. PPT]
