摘要
N-车探险问题是一类NP-hard离散优化问题,针对该问题,提出一种融合局部搜索的离散水波优化算法。结合该问题等价于置换排序的特性,设计基于置换序列的编码方式;利用反转、移动、交换等操作重新定义传播、折射和碎浪算子;开发基于插入邻域的局部搜索策略,以增强水波优化算法的局部搜索能力。最后,利用实验设计探讨关键参数对算法性能的影响。基于14个标准问题的测试结果表明:所提方法的寻优精度、稳定性等整体优于标准水波优化算法、粒子群算法、烟花算法和启发式算法H1~H4;与离散水波优化算法相比,基于禁忌搜索的变邻域搜索算法用至少66.6倍的计算时间得到了最大相对偏差比为0.017的寻优精度。结果表明,离散水波优化算法能在较短时间内获得较满意的解。
The N-vehicle exploration problem is a NP-hard discrete optimization problem.In this paper,a discrete water wave optimization algorithm with local search enhancement(DWWO-LS)is proposed to solve this discrete optimization problem.First,according to the characteristic of permutation equivalence,apermutation sequence-based encoding scheme is employed.Next,a novel discrete water wave optimization algorithm(DWWO)is developed by redefining the propagation,refraction,and breaking operator.After that,an insertion-based local search is incorporated into the discrete water wave optimization algorithm in order to enhance its local search ability.Finally,the effects of key parameters with regard to the performance are investigated.The numerical results on fourteen benchmark instances demonstrate that the algorithm proposed,in average,is superior to the standard water wave optimization algorithm,particle swarm optimization,fireworks algorithm,and the existing heuristic algorithms named as H1-H4in terms of solution accuracy and stability.Compared to DWWO-LS,tabu-based variable neighborhood local search(TBVLS)obtains a maximal relative deviation ratio of 0.017at the expense of computational efforts of at least 66.6times.These results indicate that DWWO-LS can obtain satisfactory results in a short time.
作者
刘翱
邓旭东
任亮
杨怡欣
LIU Ao;DENG Xudong;REN Liang;YANG Yixin(Evergrande School of Management,Wuhan University of Science and Technology,Wuhan 430065,China;Center for Service Science and Engineering,Wuhan University of Science and Technology,Wuhan 430065,China;Hubei Province Key Laboratory of Systems Science in Metallurical Process,Wuhan 430065,China;Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)
出处
《系统管理学报》
CSSCI
CSCD
北大核心
2020年第3期513-521,共9页
Journal of Systems & Management
基金
国家自然科学基金资助项目(71701156,71390331)
教育部人文社会科学研究青年基金资助项目(16YJCZH056)
中国科学院前沿科学重点研究计划资助项目(QYZDB-SSW-SYS020)
湖北省自然科学基金资助项目(2017CFB427)
冶金工业过程系统科学湖北省重点实验室开放基金资助项目(Y201901)。
关键词
N-车探险问题
水波优化
局部搜索
启发式算法
N-vehicle exploration problem
water wave optimization
local search
heuristic algorithms
