Abstract
| Language | English |
|---|---|
| Article number | 105887 |
| Journal | Applied Soft Computing Journal |
| Volume | 86 |
| Early online date | 28 Oct 2019 |
| DOIs | |
| Publication status | Published - 1 Jan 2020 |
Fingerprint
Keywords
- Travelling Salesman Problem
- Swap Sequence
- Swap Operator
- Partial Search
- Spider Monkey Optimization
Cite this
}
Discrete Spider Monkey Optimization for Travelling Salesman Problem. / Siddique, N; Akhand, M.A.H; Ayon, Safial Islam ; Shahriyar, S. A.; Adeli, Hojjat.
In: Applied Soft Computing Journal, Vol. 86, 105887, 01.01.2020.Research output: Contribution to journal › Article
TY - JOUR
T1 - Discrete Spider Monkey Optimization for Travelling Salesman Problem
AU - Siddique, N
AU - Akhand, M.A.H
AU - Ayon, Safial Islam
AU - Shahriyar, S. A.
AU - Adeli, Hojjat
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
U2 - 10.1016/j.asoc.2019.105887
DO - 10.1016/j.asoc.2019.105887
M3 - Article
VL - 86
JO - Applied Soft Computing
T2 - Applied Soft Computing
JF - Applied Soft Computing
SN - 1568-4946
M1 - 105887
ER -