请选择 进入手机版 | 继续访问电脑版

混合算法(SA+TS)解决TSP问题——lua实现

[复制链接]
谢世民 发表于 2021-1-2 19:43:04 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
模拟退火算法和禁忌搜索联合(SA+TS)混淆算法办理TSP问题——lua实现

我叫sts,是孙卓传授的学生,本文从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编译):
  1. --Author:sts--Date:2020.12.10function 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()endTsp_SA()
复制代码
使用Microcity编译,效果为38.85,观光商路径为:1->2->3->4->5->6->7->13->10->11->9->12->14->8->1, 盘算所用时间为:6.644s

模拟退火与禁忌搜索联合使用的代码(使用lua编写,MicroCity编译):
  1. --Author:sts--Date:2020.12.10function 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  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()endTsp_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文件中
  1. 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]),"],")    endendDis_Matrix()
复制代码
效果为

CPLEX的.MOD文件:
[code]/********************************************* * OPL 12.6.3.0 Model * Author: sts * Creation Date: 2020-12-8 at 下午6:45:23 *********************************************/int CityNum = ...;//the number of cityrange City =0..CityNum-1;//range SNode =2..CityNum-1;float distance[City][City]=...;//the distance between city A and city Bdvar 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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )