Cover Image

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

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 choosi...

Full description

Saved in:
Bibliographic Details
Main Authors: Alobaedy, Mustafa Muwafak, Ku-Mahamud, Ku Ruhana
Format: Conference or Workshop Item
Language:English
Published: 2012
Subjects:
QA76 Computer software
Online Access:http://repo.uum.edu.my/6966/1/P10_-_ICCCT.pdf
http://repo.uum.edu.my/6966/
http://www.gconference.net/eng/conference_view.html?no=35577&location=02&rDay=11012012
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.uum.repo.6966
record_format eprints
spelling my.uum.repo.69662013-01-21T01:11:55Z http://repo.uum.edu.my/6966/ New heuristic function in ant colony system for the travelling salesman problem Alobaedy, Mustafa Muwafak Ku-Mahamud, Ku Ruhana QA76 Computer software 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. 2012-12-03 Conference or Workshop Item NonPeerReviewed application/pdf en http://repo.uum.edu.my/6966/1/P10_-_ICCCT.pdf 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) http://www.gconference.net/eng/conference_view.html?no=35577&location=02&rDay=11012012
institution Universiti Utara Malaysia
building UUM Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Utara Malaysia
content_source UUM Institutionali Repository
url_provider http://repo.uum.edu.my/
language English
topic QA76 Computer software
spellingShingle QA76 Computer software
Alobaedy, Mustafa Muwafak
Ku-Mahamud, Ku Ruhana
New heuristic function in ant colony system for the travelling salesman problem
description 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.
format Conference or Workshop Item
author Alobaedy, Mustafa Muwafak
Ku-Mahamud, Ku Ruhana
author_facet Alobaedy, Mustafa Muwafak
Ku-Mahamud, Ku Ruhana
author_sort Alobaedy, Mustafa Muwafak
title New heuristic function in ant colony system for the travelling salesman problem
title_short New heuristic function in ant colony system for the travelling salesman problem
title_full New heuristic function in ant colony system for the travelling salesman problem
title_fullStr New heuristic function in ant colony system for the travelling salesman problem
title_full_unstemmed New heuristic function in ant colony system for the travelling salesman problem
title_sort new heuristic function in ant colony system for the travelling salesman problem
publishDate 2012
url http://repo.uum.edu.my/6966/1/P10_-_ICCCT.pdf
http://repo.uum.edu.my/6966/
http://www.gconference.net/eng/conference_view.html?no=35577&location=02&rDay=11012012
_version_ 1644279411708526592
score 13.211869

Similar Items