A Discrete Fruit Fly Optimization Algorithm for the Traveling Salesman Problem

The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA (DFO...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2016-11, Vol.11 (11), p.e0165804-e0165804
Main Authors: Jiang, Zi-Bin, Yang, Qiong
Format: Article
Language:English
Subjects:
Air travel
Algorithms
Animals
Biology and Life Sciences
Biomimetics
Cities
Combinatorial analysis
Computer and Information Sciences
Computer engineering
Continuity (mathematics)
Discounts
Drosophila melanogaster - physiology
Exploration
Fruit flies (Tephritidae)
Fruits
Genetic algorithms
Heuristic
Heuristic methods
Heuristics
Integer programming
Intelligence
International conferences
Knowledge
Management science
Mathematical problems
Models, Theoretical
Operators (mathematics)
Optimization
Optimization algorithms
Optimization theory
Physical Sciences
Research and Analysis Methods
Scheduling
Smell
Social Sciences
Taste Perception
Travel
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA (DFOA) is developed and applied to the traveling salesman problem (TSP), a common combinatorial problem. In the DFOA, the TSP tour is represented by an ordering of city indices, and the bio-inspired meta-heuristic search processes are executed with two elaborately designed main procedures: the smelling and tasting processes. In the smelling process, an effective crossover operator is used by the fruit fly group to search for the neighbors of the best-known swarm location. During the tasting process, an edge intersection elimination (EXE) operator is designed to improve the neighbors of the non-optimum food location in order to enhance the exploration performance of the DFOA. In addition, benchmark instances from the TSPLIB are classified in order to test the searching ability of the proposed algorithm. Furthermore, the effectiveness of the proposed DFOA is compared to that of other meta-heuristic algorithms. The results indicate that the proposed DFOA can be effectively used to solve TSPs, especially large-scale problems.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0165804