Abstract
For solving combinatorial optimisation problems, exact methods accurately exploit the structure of the problem but are tractable only up to a certain size; approximation or heuristic methods are tractable for very large problems but may possibly be led into a bad solution. A question that arises is, From where can we obtain knowledge of the problem structure via exact methods that can be exploited on large-scale problems by heuristic methods? We present a framework that allows the exploitation of existing techniques and resources to integrate such structural knowledge into the Ant Colony System metaheuristic, where the structure is determined through the notion of kernelization from the field of parameterized complexity. We give experimental results using vertex cover as the problem instance, and show that knowledge of this type of structure improves performance beyond previously defined ACS algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Blum, C.: Ant colony optimization: Introduction and recent trends. Physics of Life Reviews 2, 353–373 (2005)
Downey, R., Fellows, M., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1997)
Downey, R., Fellows, M.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1998)
Gilmour, S., Dras, M.: Understanding the pheromone system within ant colony optimization. In: Zhang, S., Jarvis, R. (eds.) AI 2005. LNCS, vol. 3809, pp. 786–789. Springer, Heidelberg (2005)
Dorigo, M., Stützle, T.: Ant Colony Optimization. A Bradford Book. MIT Press, Cambridge (2004)
Shyu, S.J., Yin, P.Y., Lin, B.M.T.: An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem. Annals of Operational Research 131, 283–304 (2004)
Chen, J., Kanj, I., Jia, W.: Vertex cover: Further observations and further improvements. Journal of Algorithms 41, 280–301 (2001)
Gilmour, S., Dras, M.: Exactness as Heuristic Structure for Guiding Ant Colony System. Technical report, Department of Computing, Macquarie University, Australia (2006)
Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: A simple model to generate hard satisfiable instances. In: Proceedings of 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 337–342 (2005)
Birattari, M.: On the Estimation of the Expected Performance of a Metaheuristic on a Class of Instances: How many instances, how many runs? IRIDIA Technical Report No. TR/IRIDIA/2004-001 (2005)
Taillard, E.D.: Comparison of non-deterministic iterative methods. In: MIC 2001 - 4th Metaheuristic International Conference, pp. 272–276 (2001)
Skiena, S.S.: The algorithm design manual. Springer, New York (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gilmour, S., Dras, M. (2006). Kernelization as Heuristic Structure for the Vertex Cover Problem. In: Dorigo, M., Gambardella, L.M., Birattari, M., Martinoli, A., Poli, R., Stützle, T. (eds) Ant Colony Optimization and Swarm Intelligence. ANTS 2006. Lecture Notes in Computer Science, vol 4150. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11839088_45
Download citation
DOI: https://doi.org/10.1007/11839088_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38482-3
Online ISBN: 978-3-540-38483-0
eBook Packages: Computer ScienceComputer Science (R0)