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 multi-core 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 multi-processing 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 Tianhe-2 [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 P-hard 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 10-fold speedup over the original AOC, and at least 1.5-fold 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 near-optimal, displaying its potential in solving other combinatorial optimization problems.