Solving Travelling Salesman Problem using Artificial Immune System Optimization (AISO)

Travelling Salesman Problem (TSP) is a typical NP complete combinatorial optimization problem with various applications. In this paper, a nature inspired meta-heuristic optimization algorithm named as Artificial Immune System Optimization (AISO) algorithm is proposed for solving TSP. There are other approaches for solving this problem, namely Greedy Method, Brunch and Bound (B&B), and Dynamic Programming (DP) but they are not very efficient. The time complexity of Greedy approach is O (n2). However, the Greedy method doesn't always converge to an optimum solution whereas the B&B increases search space exponentially and DP finds out optimal solution in O (n22 n) time. The population based meta-heuristic optimization algorithms such as Artificial Immune System Optimization (AISO) and Genetic Algorithm (GA) provide a way to find solution of the TSP in linear time complexity. The proposed algorithm finds out the best cell (optimum solution) using a Survivor Selection (SS) operator which reduces the search space to ensure that effective information is not lost. Dataset, results and convergence graphs are presented and accuracy of the analysis is briefly discussed.