论文部分内容阅读
N-车探险问题是一类在燃油约束下安排N辆车的行驶顺序以使车辆行驶最远的NP-hard问题.针对该问题,首次提出一种融合局部搜索的Memetic烟花算法.根据该问题等价于置换排序的特性,设计基于ranked-order value规则的编码方式,引入动态爆炸半径,使用烟花算法进行全局搜索;设计插入、交换和反转等邻域操作,增强算法的局部搜索能力;利用实验设计探讨了关键参数对算法性能的影响.基于14个标准问题的测试结果表明:所设计的局部搜索操作有助于增强烟花算法在N-车探险问题上的寻优精度;Memetic烟花算法(MFWA)的寻优精度、稳定性等整体优于(至少不劣于)标准烟花算法(FWA)、已有的启发式算法(H1-H4)、PSO和WWO;与MFWA相比,TBVLS用至少55倍的计算时间得到了最大竞争比为1.126的寻优精度.这些结果表明,MFWA能在较短时间内获得较满意的寻优精度.
N-car exploration is a kind of NP-hard problem that arranges the sequence of N cars under the fuel constraint to drive the vehicle furthest. In response to this problem, a memetic fireworks algorithm based on local search is proposed for the first time Equivalent to the characteristics of permutation and ordering, we design the coding method based on ranked-order value rule, introduce the dynamic explosion radius and use the fireworks algorithm for global search. We design the neighborhood operations such as insertion, exchange and inversion to enhance the local search ability of the algorithm. The experimental results show that the key parameters affect the performance of the algorithm.The test results based on 14 standard problems show that the designed local search operation can help to improve the accuracy of the fireworks algorithm in N-car exploration. (MFWA) is superior to (at least not inferior to) the standard fireworks algorithm (FWA), existing heuristic algorithms (H1-H4), PSO and WWO, At least 55 times the computational time obtained the maximum competition ratio of 1.126, the optimal accuracy of these results show that, MFWA in a relatively short period of time to obtain more satisfactory optimization accuracy.