NACO algorithm for TSP

ant colony optimization combined with neighbour-joining method

The traveling salesman problem (TSP) is a classic algorithmic problem in the fields of operational research, mathematical optimization, and theoretical computing. The salesman must visit a certain number of places bypassing the shortest route and returning to the starting point. Both exact and heuristics algorithms are used to solve TSP.
An exact algorithm designed to gain an exact solution that has factorial complexity due to it is classified as NP-Complete. Either the solution of the heuristic methods is based on an optimization problem. The complexity of these algorithms is less than the exact algorithms. Therefore, it gives solutions in less time and space and used in cases where the approximate solution is sufficient for the problem in particular when reaching the exact solution is very difficult.
The first aim of this thesis is to emphasize each TSP method’s requirements, limitations, and capabilities, to guide scientists and researchers to choose the most appropriate method for their specific needs. It presents a comprehensive survey of the most efficient and widely used TSP methods, to clarify their main differences by studying their approaches aiming at discovering their strengths and weaknesses.
Ant Colony Optimization (ACO) consider one of the heuristic methods that has a great ability to reach the optimal TSP solution. It is derived from the natural behavior of ants in the nature-based on analyzing the real ants thinking about finding and storing food in the colony. The second aim of this thesis is to propose a new hybrid algorithm to solve TSP. It is going to structure that consists of the ACO combined with the Neighbour Joining (NJ) and call it a (NACO). The new algorithm takes intensive attention to all of the criteria that might affect the solution and applied it to the TSP, and it gets many improvements in the solutions by comparing them with the original algorithm of the ant colony especially in reducing calculations as well as time.
In addition, this thesis introduces a parallel NACO as a highly efficient parallel program for high-performance TSP. It is advisable to run ants in separate execution threads in parallel to benefit from the independent operations of each ant and implemented the parallel algorithm by using a multi-core system. The proposed programs were programmed by MATLAB® R2017a (Version 9.2) and implemented on an HP computer with 8GB of RAM and Intel Core i7-8565U CPU, 64-bit windows operating system. The results obtained showed that the complexity was reduced to O(n^2 (n-ω)) in relation to the NACO. As for the PNACO, the complexity was reduced from O(n(n⁄p)(n-ω)), in addition to that the acceleration up to 10.