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

Ezugwu, AE-S, Adewumi, AO and Frîncu, ME ORCID: https://orcid.org/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

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:	77
ISSN:	0957-4174
Identifiers:	Number Type 10.1016/j.eswa.2017.01.053 DOI S0957417417300702 Publisher Item Identifier 1393199 Other
Divisions:	Schools > School of Science and Technology
Record created by:	Jill Tomkinson
Date Added:	08 Dec 2020 14:22
Last Modified:	31 May 2021 15:10
URI:	https://irep.ntu.ac.uk/id/eprint/41809

Actions (login required)

Edit View

Statistics

Views

Downloads