A fast parallel genetic algorithm for traveling salesman problem

Chun Wei Tsai, Shih Pang Tseng, Ming Chao Chiang, Chu-Sing Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

In this paper, we present a fast scalable method to reduce the computation time of genetic algorithms for traveling salesman problem, called the Parallel Pattern Reduction Enhanced Genetic Algorithm (PPREGA). The general idea behind the proposed algorithm is twofold: (1) Eliminate the redundant computations of GA on its convergence process by pattern reduction and (2) Minimize the completion time of GA by parallel computing. Our simulation result shows that the proposed algorithm can significantly reduce not only the computation time but also the maximum completion time of GA. Moreover, our simulation result shows further that the loss of the quality of the end result is small.

Original languageEnglish
Title of host publicationMethods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers
Pages241-250
Number of pages10
DOIs
Publication statusPublished - 2010 Dec 13
Event2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010 - Vladivostok, Russian Federation
Duration: 2010 May 162010 May 19

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6083 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010
CountryRussian Federation
CityVladivostok
Period10-05-1610-05-19

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Tsai, C. W., Tseng, S. P., Chiang, M. C., & Yang, C-S. (2010). A fast parallel genetic algorithm for traveling salesman problem. In Methods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers (pp. 241-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6083 LNCS). https://doi.org/10.1007/978-3-642-14822-4_27