Immunity Ant Colony System (IACS) For Solving Traveling Salesman Problem

Lee , Sung Yao (2011) Immunity Ant Colony System (IACS) For Solving Traveling Salesman Problem. Project Report. UTeM, Melaka. (Submitted)

	PDF (24 Pages) Immunity_Ant_Colony_System_(IACS)_For_Solving_Traveling_Salesman_Problem_24_Pages.pdf - Submitted Version Download (2MB)
	PDF (Full Text) Immunity_Ant_Colony_System_(IACS)_For_Solving_Traveling_Salesman_Problem_Full_Text.pdf - Submitted Version Restricted to Registered users only Download (8MB)

Abstract

Ant Colony System (ACS) is a well-known method for solving Traveling Salesman Problem (TSP), which is the problem faced by a salesman who wants to find a shortest possible trip through a given set of cities, starting from his home town and visiting each city once before finally returning borne. However, one underlying weakness of ACS is it has no protection against the generation of bad solution. Hence, a new method called Immunity Ant Colony System (lACS) was proposed to overcome this problem. The new method has an "immunity operator" which acts just like the immune system in human body. It can check for bad components in the solutions and then repair them. An application was developed to ease the implementation and testing of the new algorithms, by using Microsoft Visual Studio 2010 as the developing tool and Visual C# as the programming language. Datasets used for testing the algorithm were obtained from TSPLIB website. Three datasets were chosen for the experiment, and they are of different sizes. One of the parameters, the heuristic coefficient, was set at different values to test the effect on result. The new algorithm was then compared to ACS, and the result shows that lACS outperforms ACS in all the tested datasets. That is because every long link in the solution is "repaired" before they are brought to the neA'1 iteration, and thus producing higher quality of solution with less computation time.

Actions (login required)

View Item