【LS-SDMTSP问题】基于多元宇宙优化算法MVO的大规模单仓库多旅行商问题LS-SDMTSP算法研究附Matlab代码

✅作者简介热爱科研的Matlab仿真开发者擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。 往期回顾关注个人主页Matlab科研工作室 关注我领取海量matlab电子书和数学建模资料个人信条格物致知,完整Matlab代码获取及仿真咨询内容私信。 内容介绍一、引言大规模单仓库多旅行商问题LS - SDMTSP在物流配送、资源分配等众多领域有着广泛应用。该问题旨在从一个中心仓库出发安排多个旅行商遍历一系列客户点要求每个客户点仅被访问一次且所有旅行商的总行程最短。多元宇宙优化算法MVO作为一种新兴的智能优化算法借鉴了宇宙学中的一些概念和规律为解决 LS - SDMTSP 问题提供了新的思路。本文将深入探讨基于 MVO 的 LS - SDMTSP 算法。二、大规模单仓库多旅行商问题LS - SDMTSP一问题描述假设有一个仓库和 n 个客户点以及 m 个旅行商。每个旅行商从仓库出发依次访问部分客户点后返回仓库且所有客户点都必须被访问到。目标是合理分配客户点给各个旅行商并规划每个旅行商的路线使得所有旅行商的总行程最小。三、多元宇宙优化算法MVO一算法原理MVO 模拟了多元宇宙中不同宇宙的进化过程。在 MVO 中每个宇宙代表问题的一个潜在解宇宙的特征由其物理定律对应解的参数决定。算法主要包括三个关键步骤白洞效应、黑洞效应和虫洞旅行。白洞效应在多元宇宙中白洞被认为是物质和能量的源。在算法中白洞代表当前找到的最优解即适应度最好的宇宙。其他宇宙会受到白洞的影响向白洞的物理定律靠近类似于其他解向最优解的搜索过程。黑洞效应黑洞具有强大的引力能吸收周围的物质和能量。在 MVO 中黑洞的作用是偶尔随机选择一个宇宙并将其替换为一个新的随机生成的宇宙这有助于增加种群的多样性避免算法陷入局部最优。虫洞旅行虫洞被假设为连接不同宇宙的通道。在算法中通过一定的概率一个宇宙可以通过虫洞旅行到另一个宇宙这使得算法能够在解空间中进行更广泛的搜索。二算法流程初始化多元宇宙随机生成一组宇宙即问题的初始解每个宇宙包含旅行商的路径分配信息。同时初始化每个宇宙的适应度值根据目标函数计算、白洞当前最优解等参数。迭代优化计算适应度根据目标函数计算每个宇宙的适应度值评估当前解的优劣。白洞更新比较所有宇宙的适应度值更新白洞为当前最优解。白洞效应对于每个非白洞的宇宙根据一定的概率按照白洞的物理定律即最优解的结构对其进行调整使该宇宙向白洞靠近。黑洞效应以一定的概率选择一个宇宙将其替换为一个新的随机生成的宇宙增加种群的多样性。虫洞旅行每个宇宙以一定的概率通过虫洞旅行到另一个随机选择的宇宙进行解空间的探索。终止条件判断检查是否满足终止条件如达到最大迭代次数或适应度值收敛到一定精度。如果满足终止条件则输出当前白洞即最优解否则返回步骤 2 继续迭代。四、基于 MVO 的 LS - SDMTSP 算法设计一编码方式采用一种基于路径表示的编码方式。对于 m 个旅行商和 n 个客户点的 LS - SDMTSP 问题将所有客户点按顺序编号。每个宇宙解表示为一个长度为 n 的序列序列中的每个元素对应一个客户点编号。然后根据一定的规则将这个序列分配给 m 个旅行商形成每个旅行商的路径。例如对于 n10m3 的问题一个宇宙可能编码为 [3,7,1,9,5,2,8,4,6,10]通过某种分配规则如按顺序分配可以得到旅行商 1 的路径为 [0,3,7,0]旅行商 2 的路径为 [0,1,9,5,0]旅行商 3 的路径为 [0,2,8,4,6,10,0]这里 0 代表仓库。二适应度函数适应度函数直接采用 LS - SDMTSP 问题的目标函数即所有旅行商的总行程。对于给定的一个宇宙解根据编码方式确定每个旅行商的路径然后计算所有旅行商路径的总长度作为该宇宙的适应度值。适应度值越小说明该解越优。三MVO 算子在 LS - SDMTSP 中的应用白洞效应应用当执行白洞效应时对于非白洞的宇宙根据其与白洞最优解的差异调整其编码序列。例如如果白洞的编码序列中客户点 A 紧跟在客户点 B 之后而当前宇宙中这两个客户点的顺序不同则以一定概率调整当前宇宙中这两个客户点的顺序使其更接近白洞的结构。黑洞效应应用在 LS - SDMTSP 中当触发黑洞效应时随机生成一个新的客户点序列并按照编码方式将其分配给旅行商替换被选择的宇宙。这样可以引入新的解结构避免算法过早收敛到局部最优。虫洞旅行应用在虫洞旅行过程中随机选择一个目标宇宙然后将当前宇宙中的部分客户点序列与目标宇宙中的对应部分进行交换。例如当前宇宙为 [3,7,1,9,5,2,8,4,6,10]目标宇宙为 [5,2,6,8,3,1,9,4,7,10]随机选择一段序列如从第 3 个元素开始的 3 个元素将当前宇宙的 [1,9,5] 与目标宇宙的 [6,8,3] 进行交换得到新的当前宇宙 [3,7,6,8,3,2,8,4,6,10]然后重新分配给旅行商探索新的解空间。⛳️ 运行结果 部分代码​% This function draws the benchmark functions​function func_plot(func_name)​[lb,ub,dim,fobj]Get_Functions_details(func_name);​switch func_namecase F1x-100:2:100; yx; %[-100,100]case F2x-100:2:100; yx; %[-10,10]case F3x-100:2:100; yx; %[-100,100]case F4x-100:2:100; yx; %[-100,100]case F5x-200:2:200; yx; %[-5,5]case F6x-100:2:100; yx; %[-100,100]case F7x-1:0.03:1; yx %[-1,1]case F8x-500:10:500;yx; %[-500,500]case F9x-5:0.1:5; yx; %[-5,5]case F10x-20:0.5:20; yx;%[-500,500]case F11x-500:10:500; yx;%[-0.5,0.5]case F12x-10:0.1:10; yx;%[-pi,pi]case F13x-5:0.08:5; yx;%[-3,1]case F14x-100:2:100; yx;%[-100,100]case F15x-5:0.1:5; yx;%[-5,5]case F16x-1:0.01:1; yx;%[-5,5]case F17x-5:0.1:5; yx;%[-5,5]case F18x-5:0.06:5; yx;%[-5,5]case F19x-5:0.1:5; yx;%[-5,5]case F20x-5:0.1:5; yx;%[-5,5]case F21x-5:0.1:5; yx;%[-5,5]case F22x-5:0.1:5; yx;%[-5,5]case F23x-5:0.1:5; yx;%[-5,5]end​​Llength(x);f[];​for i1:Lfor j1:Lif strcmp(func_name,F15)0 strcmp(func_name,F19)0 strcmp(func_name,F20)0 strcmp(func_name,F21)0 strcmp(func_name,F22)0 strcmp(func_name,F23)0f(i,j)fobj([x(i),y(j)]);endif strcmp(func_name,F15)1f(i,j)fobj([x(i),y(j),0,0]);endif strcmp(func_name,F19)1f(i,j)fobj([x(i),y(j),0]);endif strcmp(func_name,F20)1f(i,j)fobj([x(i),y(j),0,0,0,0]);endif strcmp(func_name,F21)1 || strcmp(func_name,F22)1 ||strcmp(func_name,F23)1f(i,j)fobj([x(i),y(j),0,0]);endendend​surfc(x,y,f,LineStyle,none);​end​​ 参考文献往期回顾扫扫下方二维码