TY - JOUR
T1 - Discrete Spider Monkey Optimization for Travelling Salesman Problem
AU - Akhand, M.A.H
AU - Ayon, Safial Islam
AU - Shahriyar, S. A.
AU - Siddique, N
AU - Adeli, Hojjat
N1 - Publisher Copyright:
© 2019
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - 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.
AB - 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.
KW - Travelling Salesman Problem
KW - Swap Sequence
KW - Swap Operator
KW - Partial Search
KW - Spider Monkey Optimization
UR - https://pure.ulster.ac.uk/en/publications/discrete-spider-monkey-optimization-for-travelling-salesman-probl
UR - http://www.scopus.com/inward/record.url?scp=85075395815&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2019.105887
DO - 10.1016/j.asoc.2019.105887
M3 - Article
VL - 86
JO - Applied Soft Computing
JF - Applied Soft Computing
SN - 1568-4946
M1 - 105887
ER -