mailto:uumlib@uum.edu.my 24x7 Service; AnyTime; AnyWhere

New heuristic function in ant colony system for the travelling salesman problem

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)

[thumbnail of P10_-_ICCCT.pdf] 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 View Item