Hybrid Genetic Ant Colony Optimisation Technique For Travelling Salesman Problem

Teo, Chia Lee (2011) Hybrid Genetic Ant Colony Optimisation Technique For Travelling Salesman Problem. Project Report. UTeM, Melaka, Malaysia. (Submitted)

	PDF (24 Pages) Hybrid_Genetic_Ant_Colony_Optimisation_Technique_For_Travelling_Salesman_Problem-24_Pages.pdf - Submitted Version Download (3MB)
	PDF (Full Text) Hybrid_Genetic_Ant_Colony_Optimisation_Technique_For_Travelling_Salesman_Problem-Full_Text.pdf - Submitted Version Restricted to Registered users only Download (19MB)

Abstract

Ant Colony Optimization {ACO) algorithm is a famous optimization technique that using artificial ant agents to generate solutions for Travelling Salesman Problem (TSP) by mimic real ant behavior in finding source of food. However, ACO may generate an inefficiency travelling path caused by premature convergence to local optimum. The larger the data size, the higher the probability of ACO converges premature into local optimum. This project proposes a hybrid technique, the Genetic Ant Colony Optimization (GACO) technique to overcome the problem. Due to the stochastic characteristics of Genetic Algorithm (GA), it is able to prevent ACO premature convergence to local optimum effectively by hybridized it with ACO. In order to evaluate the performance of GACO, a module of GACO has been designed and implemented. Thus, a comparison of performance between ACO Aand GACO has been conducted by applying both of the techniques to three typical TSP which are laul5, kn57 and sgb128. Measurement parameters involve in the comparison are best distance, averaged distance and error percentage. Results generated by ACO and GACO have been analyze and finally come out with a conclusion which is GACO perform better than ACO in solving all of the problems. Finally, GACO has been embedded into Intelligent Vacation Planner System (IVPS). IVPS is a web application that applying ACO as its optimization technique to solve the travelling problem of tourist. IVPS is able to generate travelling route with minimum distance that based on travel spots selected by tourist. However, IPVS may generate inefficient travelling path in sometimes especially for large number of travel spots. By replacing ACO with GACO, IVPS is able to generate efficient travelling path even for large number of travel spots.

Actions (login required)

View Item