Optimization of Saleman Travelling Problem Using Genetic Algorithm with Combination of Order and Random Crossover
Muhammad Firdaus Shafie, Fadzil Ahmad, Muhammad Khusairi Osman, Ahmad Puad Ismail, Khairul Azman Ahmad, Saiful Zaimy Yahaya, Mohaiyedin Idris, Anwar Hassan Ibrahim · 2023
Traveling salesman problem (TSP) is a problem of determining the shortest path for a salesman to take to visit all cities. Although a small number of cities is easy to solve, as the number of cities increases, it’s not possible to solve in polynomial time as it was a combinatorial nondeterministic polynomial (NP-hard) problem. Hence, this project is implementing a genetic algorithm (GA) to solve TSP using Python programming. The focus of this paper is to analyze the GA using order crossover (OX) and random crossover (RX) and propose a combination mechanism, direct combination (OX-RX) and Dynamic Linear combination (OXRX-Linear) to optimize TSP. We test GA for OX and RX in a random set of cities, up to 75 total cities. Then compare the result of the proposed combination OX-RX and OX-RXLinear. The result shows that both proposed combined mechanisms OX-RX and OX-RX-Linear improve the performance of GA in solving TSP.