Open Access Open Access  Restricted Access Subscription or Fee Access

Ant Colony Optimization Approach for TTP with Balanced Intensification and Diversification

Kruti Khalpada, Amit P. Ganatra, C.K. Bhensdadia, Y.P. Kosta, Kamal K. Sutaria

Abstract


Ant Colony Optimization (ACO) is one of the techniques of swarm intelligence motivated by real world foraging behavior of ants. ACO has been successfully applied to so many combinatorial optimization problems successfully. However, ACO has not achieved excellent solutions to constraint satisfaction problems. Traveling Tournament Problem (TTP) is a real world sports time tabling problem that abstracts the important issues in creating time tables where teams‘ travel is an important issue and is one of the constraint satisfaction problems. In the existing approaches of ACO to TTP have some of the issues like poor quality solution (sum of the total distance traveled by each team in the tournament is large) and large solution construction time. So here, we have made efforts to deal with some of the above mentioned issues. First we have compared different ACO family algorithms and have analyzed that ACS is the most successful algorithm of ACO family. So here by using Ant Colony System (ACS) as the base algorithm with backtracking integration, we are getting better solution quality. Cranky ant approach has been used for better exploration. Apart from the solution quality, number of iterations and the number of local search solutions needed to construct the solution have been reduced up to a large extent.

Keywords


Ant Colony Optimization, Traveling Tournament Problem, Ant Colony System

Full Text:

PDF

References


M. Dorigo, ―An introduction to ant colony optimization‖, IRIDIA, Technical Report No. TR/IRIDIA/2006-010, 2007.

M. Dorigo and L.M. Gambardella ―Ant colony system: A Cooperative learning approach to the TSP‖, IEEE, pp. 39—74, 1997.

K. Easton, ―The traveling Tournament Problem description and benchmarks‖, LNCS, Vol. 2239, pp. 580—584, Springer, Heidelberg 2001.

H. Crauwels, ―ACO and local improvement. Workshop of real-life applications of metaheuristics‖, 2003.

M. Yoshikawa and T. Nagura, ―Adaptive ACO for intensification and Diversificatio‖, IMECS, pp. 200—203, 2009.

Y. Nakamichi and T. Arita, ―Diversity control in Ant colony optimization‖, ISAROB-2007, pp. 198-204, 2007.




DOI: http://dx.doi.org/10.36039/AA032011006

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.