一种改进的果蝇优化算法及其在旅行商问题求解中的应用

2017年第18卷第10期

摘要

关键词

相关研究

回顶部

《信息与电子工程前沿（英文）》 >> 2017年第18卷第10期 doi: 10.1631/FITEE.1601364

一种改进的果蝇优化算法及其在旅行商问题求解中的应用

. College of Computer Science and Technology, Jilin University, Changchun 130012, China.. Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012, China

发布日期： 2018-01-18

HTML36 PDF 13 收藏 0

摘要

旅行商问题（traveling salesman problem, TSP）是经典的NP（non-deterministic polynomial）难问题，在实际工程中有许多应用。而果蝇优化算法作为一种用于求解TSP问题的新群智能算法，具有易于理解、实现简单等优点。然而，该算法收敛速度慢、易陷入局部最优，从而导致寻优精度不高。为了有效求解TSP问题，本文提出了三种改进方法，以优化果蝇算法在TSP求解中的应用。一是，更加注重果蝇觅食行为中的视觉搜索能力，从而增强果蝇算法的收敛能力；二是，在果蝇优化算法中融入了淘汰机制以增加种群多样性；三是，提出了逆序操作算子和乘法操作算子，并将这两种基本操作算子运用到果蝇算法求解TSP问题上。本文对TSPLIB中的10个算例进行仿真实验，并与其它算法的实验结果进行对比，结果证明该算法不仅收敛速度快，而且寻优精度高。

关键词

旅行商问题 ; 果蝇优化算法 ; 淘汰机制 ; 视觉搜索 ; 操作算子