Discrete Spider Monkey Optimization for Travelling Salesman Problem

M.A.H Akhand, Safial Islam Ayon, S. A. Shahriyar, N Siddique, Hojjat Adeli

Research output: Contribution to journalArticle

11 Citations (Scopus)
18 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number105887
Number of pages13
JournalApplied Soft Computing Journal
Volume86
Early online date28 Oct 2019
DOIs
Publication statusPublished - 1 Jan 2020

Keywords

  • Travelling Salesman Problem
  • Swap Sequence
  • Swap Operator
  • Partial Search
  • Spider Monkey Optimization

Fingerprint Dive into the research topics of 'Discrete Spider Monkey Optimization for Travelling Salesman Problem'. Together they form a unique fingerprint.

Cite this