混合算法（SA+TS）解决TSP问题——lua实现(Microcity)
·
模拟退火算法和禁忌搜索结合（SA+TS）混合算法解决TSP问题——lua实现(Microcity)
本文从TSLIB上获取实际城市坐标，写出单独使用模拟退火（SA），模拟退火和禁忌搜索结合（SA+TS）的算法流程图和各自代码结果，最后与CPLEX精确解进行比较，得出混合（SA+TS）算法在求解效率和质量上的优越性。
当时为了赶现代优化技术大作业做的并不是很完善，大家可以批评指正。MicroCity软件是我导师自己编写的软件，集成了包括GIS、DES（离散事件仿真）、3D、Optimizer、Network、PLC control等等功能于一体。下载链接：https://pan.baidu.com/s/1S7a1al1r48pCw3Zr3g0GCg 提取码：o1at
首先，在TSPLIB上获取到的burma14.tsp.gz文件，其中包含十四个城市的坐标：
混合算法流程图（Microsoft Viso绘制）：
单纯使用模拟退火的代码（使用lua编写，MicroCity编译）：
--Author：sts
--Date：2020.12.10
function Tsp_SA() --求解TSP-burma14问题
local T --当前温度
local T_start = 5000.0 --初始温度
local T_end = 0.00000008 --结束温度
local q = 0.98 --退火系数
local L = 1000 --每个温度最大迭代次数
local N = 14 --城市个数
local result = {} --路径数组
local count = 0 --迭代次数
local time0 = os.clock()
local p = {{16,96},{16,94},{20,92},{22,93},{25,97},{22,96},{20,97},{17,96},{16,97},{14,98},{16,97},{21,95},{19,97},{20,94}} --缅甸14座城市城市坐标
function ini() --初始化
for i = 1, N do
result[i] = i --顺序生成解空间
end
end
function distance(p1,p2) --求两点间距离
local distance = math.sqrt(math.pow(p1[1]-p2[1],2)+math.pow(p1[2]-p2[2],2))
return distance
end
function path_len(result) --路径总长度
local sum = 0
for i = 1, N-1 do
sum = sum + distance(p[result[i]],p[result[i+1]])
end
sum = sum + distance(p[result[14]],p[result[1]])
return sum
end
function create() --生成新的解空间
local new = {}
for i = 1, N do --把旧解空间的每个值赋给新解空间
new[i] = result[i]
end
random = CreateRandEng(math.random(0,100000000),"uniform_int",1,N) --生成均匀分布1-14整数随机数，随机数种子也为随机数，以此保证每次随机数生成不同，且p1，p2不同
p1 = GetNextRandom(random)
p2 = GetNextRandom(random)
new[p1], new[p2] = result[p2], result[p1]
return new
end
function main() --主函数
ini()
T = T_start
while T > T_end do
for i = 1, L do
new_result = create() --产生新的解空间
local path1 = path_len(result)
local path2 = path_len(new_result)
local dE = path1 - path2
if dE > 0 then --Metropolis准则
r = math.random(0,1) --接受新解概率下界
if math.exp(-dE/T) > r then --高温状态下，可以接受能量差值较大的新状态；低温状态下，则只能接受能量差值较小的新状态
result = new_result --接受新解
end
end
end
T = T * q
count = count + 1
end
local time1 = os.clock()
print("共降温：", count,"次");
print("旅行商路径为：", table.concat(result,"->"),"->",result[1])
print("总长度为：", path_len(result))
print("计算所用时间为：", time1 - time0, "s")
end
main()
end
Tsp_SA()
利用Microcity编译，结果为38.85，旅行商路径为：1->2->3->4->5->6->7->13->10->11->9->12->14->8->1， 计算所用时间为：6.644s
模拟退火与禁忌搜索结合使用的代码（使用lua编写，MicroCity编译）：
--Author：sts
--Date：2020.12.10
function Tsp_SA_TS() --求解TSP-burma14问题
local T --当前温度
local T_start = 5000.0 --初始温度
local T_end = 0.00000008 --结束温度
local q = 0.98 --退火系数
local L = 1000 --每个温度最大迭代次数
local N = 14 --城市个数
local result = {} --路径数组
local count = 0 --迭代次数
local tabu = {} --初始化禁忌表
local time0 = os.clock() --初始操作系统时间
local p = {{16,96},{16,94},{20,92},{22,93},{25,97},{22,96},{20,97},{17,96},{16,97},{14,98},{16,97},{21,95},{19,97},{20,94}} --缅甸14座城市城市坐标
function ini() --初始化
for i = 1, N do
result[i] = i --顺序生成解空间
end
end
function distance(p1,p2) --求两点间距离
local distance = math.sqrt(math.pow(p1[1]-p2[1],2)+math.pow(p1[2]-p2[2],2))
return distance
end
function path_len(result) --路径总长度
local sum = 0
for i = 1, N-1 do
sum = sum + distance(p[result[i]],p[result[i+1]])
end
sum = sum + distance(p[result[14]],p[result[1]])
return sum
end
function create() --生成新的解空间
local new = {}
for i = 1, N do --把旧解空间的每个值赋给新解空间
new[i] = result[i]
end
random = CreateRandEng(math.random(0,100000),"uniform_int",1,N) --生成均匀分布1-14整数随机数，随机数种子也为随机数，以此保证每次随机数生成不同，且p1，p2不同
p1 = GetNextRandom(random)
p2 = GetNextRandom(random)
new[p1], new[p2] = result[p2], result[p1] --随机交换序列中两个城市的排序，2U法则
return new
end
function main() --主函数
ini()
T = T_start
while T > T_end do
for i = 1, L do
new_result = create() --产生新的解空间
if #tabu <= 100 then --更新禁忌表
table.insert(tabu,path_len(new_result)) --初始化禁忌表
else
local max = 0
local j = 0
for k = 1, 100 do
if tabu[k] > max then
max = tabu[k]
j = k
end
end
if path_len(new_result) < max then --更新禁忌表，新解代替最差解
table.insert(tabu,j,path_len(new_result))
end
end
local path1 = path_len(result)
local path2 = path_len(new_result)
local dE = path1 - path2
local min = 999
local j = 0
for k = 1, 100 do --与禁忌表的最小值比较
if tabu[k] and tabu[k] < min then
min = tabu[k]
j = i
end
end
if math.exp((min-path2)/T) > math.random(0,1) then --高温状态下，可以接受比禁忌表最小值大的值
if dE > 0 then --Metropolis准则
r = math.random(0,1) --接受新解概率下界
if math.exp(-dE/T) > r and math.exp((min-path2)/T) > r then --高温状态下，可以接受能量差值较大的新状态；低温状态下，则只能接受能量差值较小的新状态
result = new_result --接受新解
end
end
else
break
end
end
T = T * q
count = count + 1
end
local time1 = os.clock()
print("共降温：", count,"次");
print("旅行商路径为：", table.concat(result,"->"),"->",result[1])
print("总长度为：", path_len(result))
print("计算所用时间为：", time1 - time0, "s")
end
main()
end
Tsp_SA_TS()
利用Microcity编译，结果为32.23，旅行商路径为：13->7->6->5->4->12->14->3->2->1->10->9->11->8->13， 计算所用时间为：0.016s，不难看出，加入了禁忌搜索，算法无论在解的质量和求解效率上都有提升。
利用CPLEX求精确解，代码和结果如下，最优解为28，具体步骤与代码如下
lua建立运输距离矩阵代码，生成后导入CPLEX的.DAT文件中
function Dis_Matrix()
local p = {{16,96},{16,94},{20,92},{22,93},{25,97},{22,96},{20,97},{17,96},{16,97},{14,98},{16,97},{21,95},{19,97},{20,94}}
local dis = {}
function distance(p1,p2) --求两点间距离
local distance = math.sqrt(math.pow(p1[1]-p2[1],2)+math.pow(p1[2]-p2[2],2))
distance = math.floor(distance)
return distance
end
for i = 1, #p do
dis[i] = {}
for j = 1, i do
dis[i][j] = distance(p[i],p[j])
end
print("[",table.concat(dis[i],",",dis[i][j]),"],")
end
end
Dis_Matrix()
结果为
CPLEX的.MOD文件：
/*********************************************
* OPL 12.6.3.0 Model
* Author: sts
* Creation Date: 2020-12-8 at 下午6:45:23
*********************************************/
int CityNum = ...;//the number of city
range City =0..CityNum-1;
//range SNode =2..CityNum-1;
float distance[City][City]=...;//the distance between city A and city B
dvar boolean visitCity[City][City];//City A to city B or not
{int} nodes ={i|i in City};
range r=1..-2+ftoi(pow(2,card(nodes)));
{int} nodes2[k in r]={i|i in nodes :((k div(ftoi(pow(2,(ord(nodes,i)))))mod 2)==1)};
execute{
for(var c1 in City)
for(var c2 in City)
if(c1<c2)distance[c1][c2]=distance[c2][c1];
}
minimize
sum(c1 in City)
sum(c2 in City)
distance[c1][c2]*visitCity[c1][c2];
subject to{
forall(c1 in City)
sum(c2 in City)
visitCity[c1][c2]==1;
forall(c2 in City)
sum(c1 in City)
visitCity[c1][c2]==1;
forall(c1 in City)
visitCity[c1][c1]==0;
forall(s in r){
sum(c1 in nodes2[s])
sum(c2 in nodes2[s])
visitCity[c1][c2]<=card(nodes2[s])-1;
}
}
CPLEX的.DAT文件（距离矩阵，使用lua程序生成后导入）：
/*********************************************
* OPL 12.6.3.0 Data
* Author: sts
* Creation Date: 2020-12-8 at 下午6:45:23
*********************************************/
CityNum=14;
distance=[
[0],
[2,0],
[5,4,0],
[6,6,2,0],
[9,9,7,5,0],
[6,6,4,3,3,0],
[4,5,5,4,5,2,0],
[1,2,5,5,8,5,3,0],
[1,3,6,7,9,6,4,1,0],
[2,4,8,9,11,8,6,3,2,0],
[1,3,6,7,9,6,4,1,0,2,0],
[5,5,3,2,4,1,2,4,5,7,5,0],
[3,4,5,5,6,3,1,2,3,5,3,2,0],
[4,4,2,2,5,2,3,3,5,7,5,1,3,0]];
结果，最优解为28 ：
所以，模拟退火法与禁忌搜索法结合性能较好，与精确解只差了4误差。
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)