Repository logo
 

The mixing genetic algorithm for traveling salesman problem

Simple item page
dc.contributor.authorVaradarajan, Swetha, author
dc.contributor.authorWhitley, Darrell, advisor
dc.contributor.authorBöhm, Wim, committee member
dc.contributor.authorBeveridge, Ross, committee member
dc.contributor.authorChong, Edwin, committee member
dc.contributor.authorPouchet, Louis-Noël, committee member
dc.date.accessioned2022-05-30T10:22:25Z
dc.date.available2024-05-24T10:22:25Z
dc.date.issued2022
dc.description.abstractThe Traveling Salesman Problem (TSP) is one of the most intensively studied NP-Hard problems. The TSP solvers are well-suited for multi-core CPU-based architectures. With the decline in Moore's law, there is an increasing need to port the codes to parallel architectures such as the GPU massively. This thesis focuses on the Genetic Algorithm (GA) based TSP solvers. The major drawback in porting the state-of-the-art GA based TSP solver (called the Edge Assembly Crossover (EAX)) are (a) the memory per crossover operation is large and limits the scalability of the solver (b) the communication per crossover operation is random and not favorable for the SIMD machines. We designed a new solver, the Mixing Genetic Algorithm (MGA), using the Generalized Partition Crossover (GPX) operator to overcome these aspects. The GPX consumes 4 x lesser memory and does not access the memory during crossover operation. The MGA is used in three different modes. (1) MGA can converge fast on problems smaller than 2,000 cities as a single solver. (2) As a hybrid solver, together with EAX, it speeds up the convergence rate for problems up to 85,900 cities. (3) In an ensemble setting, together with EAX and an iterated local search (called the Lin-Kernighan Helsgaun (LKH) heuristic), it increases the success rate of some of the hard TSP instances. The MGA is parallelized on shared memory (using OpenMP), distributed memory (using MPI), and GPU (using CUDA). A combination of OpenMP and MPI parallelization is examined on problems ranging between 5,000 to 85,900 cities. We show near-linear speedup (proportional to the number of parallel units) on these instances. Preliminary results on GPU parallelization of the GPX crossover operator partition phase show a 48x to 625x speedup over the naive sequential implementation. This is the first step towards the fine-grain parallelization of GA operators for TSP. The results are tested on problems ranging from 10,000 to 2M cities.
dc.format.mediumborn digital
dc.format.mediumdoctoral dissertations
dc.identifierVaradarajan_colostate_0053A_17021.pdf
dc.identifier.urihttps://hdl.handle.net/10217/235266
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2020-
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.rights.accessEmbargo Expires: 05/24/2024
dc.subjectGPU
dc.subjectSIMD
dc.subjecttraveling salesman problem
dc.subjectmixing genetic algorithm
dc.subjectgeneralized partition crossover
dc.subjectsupercomputer
dc.titleThe mixing genetic algorithm for traveling salesman problem
dc.typeText
dcterms.embargo.expires2024-05-24
dcterms.embargo.terms2024-05-24
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineComputer Science
thesis.degree.grantorColorado State University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (Ph.D.)

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Varadarajan_colostate_0053A_17021.pdf
Size:
16.72 MB
Format:
Adobe Portable Document Format
Download

Collections

2020-
Theses and Dissertations