Discrete Spider Monkey Optimization for Travelling Salesman Problem

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

Research output: Contribution to journalArticle

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

Fingerprint

Traveling salesman problem
Heuristic algorithms
Combinatorial optimization
Birds
Fish
Mathematical operators

Keywords

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

Cite this

Siddique, N ; Akhand, M.A.H ; Ayon, Safial Islam ; Shahriyar, S. A. ; Adeli, Hojjat. / Discrete Spider Monkey Optimization for Travelling Salesman Problem. In: Applied Soft Computing Journal. 2020 ; Vol. 86.
@article{303a795e70844ea19ab1792781df5168,
title = "Discrete Spider Monkey Optimization for Travelling Salesman Problem",
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.",
keywords = "Travelling Salesman Problem, Swap Sequence, Swap Operator, Partial Search, Spider Monkey Optimization",
author = "N Siddique and M.A.H Akhand and Ayon, {Safial Islam} and Shahriyar, {S. A.} and Hojjat Adeli",
year = "2020",
month = "1",
day = "1",
doi = "10.1016/j.asoc.2019.105887",
language = "English",
volume = "86",
journal = "Applied Soft Computing",
issn = "1568-4946",
publisher = "Elsevier",

}

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 journalArticle

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 -