Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem

Tools

Ezugwu, A.E.-S., Adewumi, A.O. and Frîncu, M.E. ORCID: 0000-0003-1034-8409, 2017. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Systems with Applications, 77, pp. 189-210. ISSN 0957-4174

Preview

Text
1393199_Frincu.pdf - Post-print
Download (1MB) | Preview

Official URL: https://doi.org/10.1016/j.eswa.2017.01.053

Abstract

Symbiotic Organisms Search (SOS) algorithm is an effective new metaheuristic search algorithm, which has recently recorded wider application in solving complex optimization problems. SOS mimics the symbiotic relationship strategies adopted by organisms in the ecosystem for survival. This paper, presents a study on the application of SOS with Simulated Annealing (SA) to solve the well-known traveling salesman problems (TSPs). The TSP is known to be NP-hard, which consist of a set of (n − 1)!/2 feasible solutions. The intent of the proposed hybrid method is to evaluate the convergence behaviour and scalability of the symbiotic organism’s search with simulated annealing to solve both small and large-scale travelling salesman problems. The implementation of the SA based SOS (SOS-SA) algorithm was done in the MATLAB environment. To inspect the performance of the proposed hybrid optimization method, experiments on the solution convergence, average execution time, and percentage deviations of both the best and average solutions to the best known solution were conducted. Similarly, in order to obtain unbiased and comprehensive comparisons, descriptive statistics such as mean, standard deviation, minimum, maximum and range were used to describe each of the algorithms, in the analysis section. The oneway ANOVA and Kruskal-Wallis test were further used to compare the significant difference in performance between SOS-SA and the other selected state-of-the-art algorithms. The performances of SOS-SA and SOS are evaluated on different sets of TSP benchmarks obtained from TSPLIB (a library containing samples of TSP instances). The empirical analysis’ results show that the quality of the final results as well as the convergence rate of the new algorithm in some cases produced even more superior solutions than the best known TSP benchmarked results.

Item Type:

Journal article

Publication Title:

Expert Systems with Applications

Creators:

Ezugwu, A.E.-S., Adewumi, A.O. and Frîncu, M.E.

Publisher:

Elsevier BV

Date:

1 July 2017

Volume:

ISSN: