系统管理学报 ›› 2020, Vol. 29 ›› Issue (3): 513-521.DOI: 10.3969/j.issn.1005-2542.2020.03.011

• 运筹学与工业工程 • 上一篇    下一篇

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

刘翱1a,1b,2,邓旭东1a,1b,任亮1a,1b,杨怡欣3,4
  

  1. 武汉科技大学 1a.管理学院;1b.服务科学与工程研究中心,武汉 430065;2. 智能信息处理与实时工业系统湖北省重点实验室,武汉 430065;3.中国科学院 数学与系统科学研究院,北京 100190;4. 中国科学院大学,北京 100049
  • 出版日期:2020-05-29 发布日期:2020-07-09
  • 通讯作者: 杨怡欣(1991—),女,博士生。
  • 作者简介:刘 翱(1987—),男,博士,讲师。研究方向为智能优化与调度。
  • 基金资助:
    国家自然科学基金资助项目(71701156,71390331);教育部人文社会科学研究青年基金资助项目(16YJCZH056),中国科学院前沿科学重点研究计划资助项目(QYZDB-SSW-SYS020);湖北省自然科学基金资助项目(2017CFB427);湖北省教育厅人文社会科学研究青年项目(17Q034);湖北省教育厅科学技术研究项目(Q20171104);智能信息处理与实时工业系统湖北省重点实验室开放基金资助项目(2016znss18B);武汉科技大学青年科技骨干培育计划资助项目(2016xz0l7,2017xz031)

A Discrete Water Wave Optimization Algorithm for  -Vehicle Exploration Problem

LIU Ao1a,1b,2, DENG Xudong1a,1b, REN Liang1a,1b, YANG Yixin3,4   

  1. 1a. School of Management; 1b. Center for Service Science and Engineering, Wuhan University of Science and Technology, Wuhan 430065, China; 2. Key Laboratory of Intelligent Information Processing and Real-Time Industrial System of Hubei Province, Wuhan 430065, China; 3. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; 4. University of Chinese Academy of Sciences, Beijing 100049, China
  • Online:2020-05-29 Published:2020-07-09

摘要:

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

关键词: N-车探险问题, 水波优化算法, 局部搜索, 启发式算法

Abstract:

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, a permutation 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-H4 in 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.017 at the expense of computational efforts of at least 66.6 times. These results indicate that DWWO-LS can obtain satisfactory results in a short time.

Key words: N-vehicle exploration problem, water wave optimization, local search, heuristic algorithms

中图分类号: