KMS Of Academy of mathematics and systems sciences, CAS
| 求解N-车探险问题的离散水波优化算法 | |
| Alternative Title | A Discrete Water Wave Optimization Algorithm for N-Vehicle Exploration Problem |
| 刘翱1; 邓旭东1; 任亮1; 杨怡欣3 | |
| 2020 | |
| Source Publication | 系统管理学报
 |
| ISSN | 1005-2542 |
| Volume | 29.0Issue:003Pages:513-521 |
| Abstract | N-车探险问题是一类NP-hard离散优化问题,针对该问题,提出一种融合局部搜索的离散水波优化算法。结合该问题等价于置换排序的特性,设计基于置换序列的编码方式;利用反转、移动、交换等操作重新定义传播、折射和碎浪算子;开发基于插入邻域的局部搜索策略,以增强水波优化算法的局部搜索能力。最后,利用实验设计探讨关键参数对算法性能的影响。基于14个标准问题的测试结果表明:所提方法的寻优精度、稳定性等整体优于标准水波优化算法、粒子群算法、烟花算法和启发式算法H1~H4;与离散水波优化算法相比,基于禁忌搜索的变邻域搜索算法用至少66.6倍的计算时间得到了最大相对偏差比为0.017的寻优精度。结果表明,离散水波优化算法能在较短时间内获得较满意的解。 |
| Other 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,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. |
| Keyword | N-车探险问题 水波优化 局部搜索 启发式算法 |
| Indexed By | CSCD |
| Language | 中文 |
| CSCD ID | CSCD:6732304 |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/57510 |
| Collection | 中国科学院数学与系统科学研究院 |
| Affiliation | 1.武汉科技大学 2.冶金工业过程系统科学湖北省重点实验室 3.中国科学院数学与系统科学研究院 4.中国科学院大学 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment