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

摘要：

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

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