Alobaedy, Mustafa Muwafak and Ku-Mahamud, Ku Ruhana (2012) New heuristic function in ant colony system for the travelling salesman problem. In: 7th International Conference on Computing and Convergence Technology, 03-05 December 2012, Seoul, Korea. (Unpublished)
PDF
Restricted to Registered users only Download (894kB) |
Abstract
Ant Colony System (ACS) is one of the best algorithms to solve NP-hard problems.However, ACS suffers from pheromone stagnation problem when all ants converge quickly on one sub-optimal solution.ACS algorithm utilizes the value between nodes as heuristic values to calculate the probability of choosing the next node. However, one part of the algorithm, called heuristic function, is not updated at any time throughout the process to reflect the new information discovered by the ants.This paper proposes an Enhanced Ant Colony System algorithm for solving the Travelling Salesman Problem.The enhanced algorithm is able to generate shorter tours within reasonable times by using accumulated values from pheromones and heuristics.The proposed enhanced ACS algorithm integrates a new heuristic function that can reflect the new information discovered by the ants. Experiments conducted have used eight data sets from TSPLIB with different numbers of cities.The proposed algorithm shows promising results when compared to classical ACS in term of best, average, and standard deviation of the best tour length.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Uncontrolled Keywords: | Ant colony optimization, ant colony system, heuristic function, traveling salesman problem. |
Subjects: | Q Science > QA Mathematics > QA76 Computer software |
Divisions: | College of Arts and Sciences |
Depositing User: | Prof. Dr. Ku Ruhana Ku Mahamud |
Date Deposited: | 10 Jan 2013 02:03 |
Last Modified: | 21 Jan 2013 01:11 |
URI: | https://repo.uum.edu.my/id/eprint/6966 |
Actions (login required)
View Item |