New heuristic function in ant colony system algorithm

• Main Authors: Ku-Mahamud, Ku Ruhana, Mohamed Din, Aniza, Yusof, Yuhanif, Mahmuddin, Massudi, Alobaedy, Mustafa Muwafak
• Format: Conference or Workshop Item
• Language: English
• Published: 2012
• Subjects: QA76 Computer software
• Online Access: http://repo.uum.edu.my/6964/1/P6_-_ISSC2012.pdf; http://repo.uum.edu.my/6964/; http://issc.uum.edu.my/index.php/ISSC2012/ISSC2012

NP-hard problem can be solved by Ant Colony System (ACS) algorithm.However, ACS suffers from pheromone stagnation problem, a situation when all ants converge quickly to one sub-optimal solution.ACS algorithm utilizes the value between nodes as heuristic value to calculate the probability of choosing the next node.However, the heuristic value is not updated throughout the process to reflect new information discovered by the ants.This paper proposes a new heuristic function for the Ant Colony System algorithm that can reflect new information discovered by ants.The credibility of the new function was tested on travelling salesman and grid computing problems.Promising results were obtained when compared to classical ACS algorithm in terms of best tour length for the travelling sales-man problem. Better results were also obtained for the grid scheduling problem in terms of makespan and utilization.