Discrete Spider Monkey Optimization for Travelling Salesman Problem

Meta-heuristic algorithms inspired by biological species have become very popular in recent years.Collective intelligence of various social insects such as ants, bees, wasps, termites, birds, fish, hasbeen investigated to develop a number of meta-heuristic algorithms in the general domain of swarmintelligence (SI). The developed SI algorithms are found effective in solving different optimizationtasks. Travelling Salesman Problem (TSP) is the combinatorial optimization problem where a salesmanstarting from a home city travels all the other cities and returns to home city in the shortest possiblepath. TSP is a popular problem due to the fact that the instances of TSP can be applied to solve real-world problems, implication of which turns TSP into a standard test bench for performance evaluationof new algorithms. Spider Monkey Optimization (SMO) is a recent addition to SI algorithms basedon the social behaviour of spider monkeys. SMO implicitly adopts grouping and regrouping for theinteractions to improve solutions; such multi-population approach is the motivation of this study todevelop an effective method for TSP. This paper presents an effective variant of SMO to solve TSPcalled discrete SMO (DSMO). In DSMO, every spider monkey represents a TSP solution where SwapSequence (SS) and Swap Operator (SO) based operations are employed, which enables interactionamong monkeys in obtaining the optimal TSP solution. The SOs are generated using the experience ofa specific spider monkey as well as the experience of other members (local leader, global leader, or arandomly selected spider monkey) of the group. The performance and effectiveness of the proposedmethod have been verified on a large set of TSP instances and the outcomes are compared to otherwell-known methods. Experimental results demonstrate the effectiveness of the proposed DSMO for solving TSP.