symbiotic organisms search optimization algorithm for traveling salesman problem

What is it about?

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 sym- biotic 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 sales- man 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 scal- ability 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, ex- periments 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 unbi- ased 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 Fried- man’s Test (with post hoc tests) was 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.

Featured Image

Why is it important?

i. Proposal of a new TSP optimization method, called simulated annealing based symbiotic organisms search optimization algo- rithm. ii. Implementation of the proposed method using different scale of TSP benchmark instances. iii. Performance comparison of the proposed hybrid method with other state-of-the-art algorithms (GA-PSO-ACO, ASA-GS, MSA- IBS, LBSA, and IBA). iv. Descriptive statistical validation of the SOS-SA results against other selected methods using different statistical analysis tests.

Perspectives