求解N-车探险问题的离散水波优化算法

发布时间：2024-05-12 21:24

　　N-车探险问题是一类NP-hard离散优化问题,针对该问题,提出一种融合局部搜索的离散水波优化算法。结合该问题等价于置换排序的特性,设计基于置换序列的编码方式;利用反转、移动、交换等操作重新定义传播、折射和碎浪算子;开发基于插入邻域的局部搜索策略,以增强水波优化算法的局部搜索能力。最后,利用实验设计探讨关键参数对算法性能的影响。基于14个标准问题的测试结果表明:所提方法的寻优精度、稳定性等整体优于标准水波优化算法、粒子群算法、烟花算法和启发式算法H1～H4;与离散水波优化算法相比,基于禁忌搜索的变邻域搜索算法用至少66.6倍的计算时间得到了最大相对偏差比为0.017的寻优精度。结果表明,离散水波优化算法能在较短时间内获得较满意的解。

【文章页数】：9 页

【部分图文】：

图2反转操作

(1）随机选取πi的两个位置i、j，反转i,i+1，…，j-1,j得到π′i;3.3折射

图1车辆行驶序列图[17-18]

定义π=（π1，π2，…，πn）为车辆的行驶序列，前面的车给后面的车供油，是车辆πi的行驶距离，如图1所示。车辆πi的行驶距离满足[17]:

图3移动操作

如图3所示，在π*和πi之间移动[4,2,6]的操作步骤为：(1)π*（4)=4，分别找到πi(1)=4，πi(4)=5，交换πi的4和5;(2)π*（5)=2，分别找到πi(3)=2，πi(5)=1，交换πi的2和1;(3)π*（6)=6，分别找到πi(2)=6，πi(6)=3....

图4交换操作

(2）如果f（π*）>f（πi），则更新πi=π*；如果min（βf（πi）/f（π*），1)<u，则更新πi=π*，否则保留πi。其中，u为[0,1]上的均匀随机数。3.5基于插入邻域的局部搜索

本文编号：3971916