Evolutionary algorithms for solving multi-objective travelling salesman problem

Vui Ann Shim*, Kay Chen Tan, Jun Yong Chia, Jin Kiat Chong

*Corresponding author for this work

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

18 Citations (Scopus)

Abstract

This paper studies the application of evolutionary algorithms for bi-objective travelling salesman problem. Two evolutionary algorithms, including estimation of distribution algorithm (EDA) and genetic algorithm (GA), are considered. The solution to this problem is a set of trade-off alternatives. The problem is solved by optimizing the order of the cities so as to simultaneously minimize the two objectives of travelling distance and travelling cost incurred by the travelling salesman. In this paper, binary-representation-based evolutionary algorithms are replaced with an integer-representation. Three existing EDAs are altered to use this integer-representation, namely restricted Boltzmann machine (RBM), univariate marginal distribution algorithm (UMDA), and population-based incremental learning (PBIL). Each city is associated with a representative integer, and the probability of any of this representative integer to be located in any position of the chromosome is constructed through the modeling approach of the EDAs. New sequences of cities are obtained by sampling from the probabilistic model. A refinement operator and a local search operator are proposed in this piece of work. The EDAs are subsequently hybridized with GA in order to complement the limitations of both algorithms. The effect that each of these operators has on the quality of the solutions are investigated. Empirical results show that the hybrid algorithms are capable of finding a set of good trade-off solutions.
Original languageEnglish
Pages (from-to)207-241
JournalFlexible Services and Manufacturing Journal
Volume23
Issue number2
Online published1 Jun 2011
DOIs
Publication statusPublished - Jun 2011
Externally publishedYes

Research Keywords

  • Estimation of distribution algorithm
  • Evolutionary multi-objective optimization
  • Probabilistic model
  • Restricted Boltzmann machine
  • Travelling salesman problem

Fingerprint

Dive into the research topics of 'Evolutionary algorithms for solving multi-objective travelling salesman problem'. Together they form a unique fingerprint.

Cite this