Journal Home Online First Current Issue Archive For Authors Journal Information 中文版

2017, Volume 18, Issue 10

Abstract

Keywords

Related Research

Back to Top

Frontiers of Information Technology & Electronic Engineering >> 2017, Volume 18, Issue 10 doi: 10.1631/FITEE.1601364

An improved fruit fly optimization algorithm for solving traveling salesman problem

. 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

Available online: 2018-01-18
HTML33 PDF 13 Collect 0

Next Previous

Abstract

The traveling salesman problem (TSP), a typical non-deterministic polynomial (NP) hard problem, has been used in many engineering applications. As a new swarm-intelligence optimization algorithm, the fruit fly optimization algorithm (FOA) is used to solve TSP, since it has the advantages of being easy to understand and having a simple implementation. However, it has problems, including a slow convergence rate for the algorithm, easily falling into the local optimum, and an insufficient optimi-zation precision. To address TSP effectively, three improvements are proposed in this paper to improve FOA. First, the vision search process is reinforced in the foraging behavior of fruit flies to improve the convergence rate of FOA. Second, an elimination mechanism is added to FOA to increase the diversity. Third, a reverse operator and a multiplication operator are proposed. They are performed on the solution sequence in the fruit fly’s smell search and vision search processes, respectively. In the experiment, 10 benchmarks selected from TSPLIB are tested. The results show that the improved FOA outperforms other alternatives in terms of the convergence rate and precision.

Related Research