Improved discrete plant propagation algorithm for solving the traveling salesman problem
Abstract
The primary goal of traveling salesman problem (TSP) is for a salesman to visit many cities and return to the starting city via a sequence of potential shortest paths. Subsequently, conventional algorithms are inadequate for large-scale problems; thus, metaheuristic algorithms have been proposed. A recent metaheuristic algorithm that has been implemented to solve TSP is the plant propagation algorithm (PPA), which belongs to the rose family. In this research, this existing PPA is modified to solve TSP. Although PPA is claimed to be successful, it suffers from the slow convergence problem, which significantly impedes its applicability for getting good solution. Therefore, the proposed partial-partitioned greedy algorithm (PPGA) offers crossover and three mutation operations (flip, swap, and slide), which allow local and global search and seem to be wise methods to help PPA in solving the TSP. The PPGA performance is evaluated on 10 separate datasets available in the literature and compared with the original PPA. In terms of distance, the computational results demonstrate that the PPGA outperforms the original PPA in nine datasets which assures that it is 90% better than PPA. PPGA produces good solutions when compared with other algorithms in the literature, where the average execution time reduces by 10.73%.
Keywords
Genetic algorithm; Metaheuristic; Optimization; Plant intelligence
Full Text:
PDFDOI: http://doi.org/10.11591/ijai.v11.i1.pp13-22
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
IAES International Journal of Artificial Intelligence (IJ-AI)
ISSN/e-ISSN 2089-4872/2252-8938
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).