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

CSpace

	求解N-车探险问题的离散水波优化算法
其他题名	A Discrete Water Wave Optimization Algorithm for N-Vehicle Exploration Problem
	刘翱 1; 邓旭东 1; 任亮 1; 杨怡欣 3
	2020
发表期刊	系统管理学报
ISSN	1005-2542
卷号	29.0 期号:003 页码:513-521
摘要	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.
关键词	N-车探险问题水波优化局部搜索启发式算法
收录类别	CSCD
语种	中文
CSCD记录号	CSCD:6732304
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/57510
专题	中国科学院数学与系统科学研究院
作者单位	1.武汉科技大学 2.冶金工业过程系统科学湖北省重点实验室 3.中国科学院数学与系统科学研究院 4.中国科学院大学
推荐引用方式 GB/T 7714	刘翱,邓旭东,任亮,等. 求解N-车探险问题的离散水波优化算法[J]. 系统管理学报,2020,29.0(003):513-521.
APA	刘翱,邓旭东,任亮,&杨怡欣.(2020).求解N-车探险问题的离散水波优化算法.系统管理学报,29.0(003),513-521.
MLA	刘翱,et al."求解N-车探险问题的离散水波优化算法".系统管理学报 29.0.003(2020):513-521.