UM ETheses Collection (澳門大學電子學位論文庫)
 Title

Parallel algorithm of changes to solve traveling salesman problem
 English Abstract

Show / Hidden
Parallel Algorithm of Changes to solve Traveling Salesman Problem by MAK Hoi Fong Thesis Supervisor: Prof. TAM Sik Chung Faculty of Science and Technology Today the maturity of multicore processor computing platform provides an unprecedented environment for the development of practical applications and research on parallel computing, which comes with different architectures and scales, such as distributed computing which connects separated and individual computers through the Internet; computer cluster which bonds many individual computers; and a single computer with multiprocessing units, whether are they CPUs or other types of processing cores. With performance improved, problems that previously cannot be solved by a single machine, due to unrealistic computation time requirement, are now tractable in parallel computing environment. For example, in the application to optimize the aerodynamics design of commercial aircraft, the fastest supercomputer by June 2015, the Tianhe2 [41], sped up the computation time from 2 years to 6 days [15]. Meanwhile, combinatorial optimization is a type of problem that requires huge computation power even when equipped with different tools and algorithms. Among such problems, the Traveling Salesman Problem (TSP) is one of the most studied with practical value. Despite the many algorithms trying to tackle the problem, in general an N Phard one, computation power is still on high demand. Parallel computing expedites the process. This thesis presents the implementation of parallel Algorithm of Changes (AOC) for finding the shortest path for TSP. Inspired by the ancient Chinese book “I Ching”, AOC is a newly proposed Evolutionary Algorithm which represents and manipulates data to uncover useful information from problems. Besides porting the AOC to parallel environment, the thesis devises two new variations of AOC, benefiting from the efficiency of parallel computation architecture. Results show that in some testing problems, the new parallel AOC can attain a 10fold speedup over the original AOC, and at least 1.5fold over the generic parallel AOC. Experiments show that the new parallel AOC also outperforms parallel Genetic Algorithm (GA) with a 350% speedup and results that are more nearoptimal, displaying its potential in solving other combinatorial optimization problems.
 Issue date

2015.
 Author

Mak, Hoi Fong
 Faculty

Faculty of Science and Technology
 Department

Department of Mathematics
 Degree

M.Sc.
 Subject

Traveling salesman problem
Genetic algorithms
 Supervisor

Tam, Sik Chung
 Files In This Item
 Location
 1/F Zone C
 Library URL
 991000841469706306