Abstract
We present a new Immune Algorithm that incorporates a simple local search procedure to improve the overall performances to tackle the graph coloring problem instances. We characterize the algorithm and set its parameters in terms of Information Gain. Experiments will show that the IA we propose is very competitive with the best evolutionary algorithms.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dasgupta, D. (ed.): Artificial Immune Systems and their Applications. Springer-Verlag, Berlin Heidelberg New York (1999)
De Castro L.N., Timmis J.: Artificial Immune Systems: A New Computational Intelligence Paradigm. Springer-Verlag, UK (2002)
Forrest, S., Hofmeyr, S. A.: Immunology as Information Processing. Design Principles for Immune System & Other Distributed Autonomous Systems. Oxford Univ. Press, New York (2000)
Nicosia, G., Castiglione, F., Motta, S.: Pattern Recognition by primary and secondary response of an Artificial Immune System. Theory in Biosciences 120 (2001) 93–106
Galinier, P., Hao, J.: Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization Vol. 34 (1999) 379–397
Marino, A., Damper, R.I.: Breaking the Symmetry of the Graph Colouring Problem with Genetic Algorithms. Workshop Proc. of the Genetic and Evolutionary Computation Conference (GECCO’00). Las Vegas, NV: Morgan Kaufmann (2000)
Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979)
Mehrotra, A., Trick, M.A.: A Column Generation Approach for Graph Coloring. INFORMS J. on Computing 8 (1996) 344–354
Caramia, M., Dell’Olmo, P.: Iterative Coloring Extension of a Maximum Clique. Naval Research Logistics, 48 (2001) 518–550
Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, Providence, RI (1996)
De Castro, L. N., Von Zuben, F. J.: The Clonal Selection Algorithm with Engineering Applications. Proceedings of GECCO 2000, Workshop on Artificial Immune Systems and Their Applications, (2000) 36–37
De Castro, L.N., Von Zuben, F.J.: Learning and optimization using the clonal selection principle. IEEE Trans. on Evolutionary Computation Vol. 63 (2002) 239–251
Nicosia, G., Castiglione, F., Motta, S.: Pattern Recognition with a Multi-Agent model of the Immune System. Int. NAISO Symposium (ENAIS’2001). Dubai, U.A.E. ICSC Academic Press, (2001) 788–794
Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Trans. on Evolutionary Computation, Vol. 32 (1999) 124–141
Leung, K., Duan, Q., Xu, Z., Wong, C.W.: A New Model of Simulated Evolutionary Computation — Convergence Analysis and Specifications. IEEE Trans. on Evolutionary Computation Vol. 51 (2001) 3–16
Seiden P.E., Celada F.: A Model for Simulating Cognate Recognition and Response in the Immune System. J. Theor. Biol. Vol. 158 (1992) 329–357
Nicosia, G., Cutello, V.: Multiple Learning using Immune Algorithms. Proceedings of the 4th International Conference on Recent Advances in Soft Computing, RASC 2002, Nottingham, UK, 12–13 December (2002)
Johnson, D.R., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning. Operations Research 39 (1991) 378–406
Barbosa, V.C., Assis, C.A.G., do Nascimento, J.O.: Two Novel Evolutionary Formulations of the Graph Coloring Problem. Journal of Combinatorial Optimization (to appear)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cutello, V., Nicosia, G., Pavone, M. (2003). A Hybrid Immune Algorithm with Information Gain for the Graph Coloring Problem. In: Cantú-Paz, E., et al. Genetic and Evolutionary Computation — GECCO 2003. GECCO 2003. Lecture Notes in Computer Science, vol 2723. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45105-6_23
Download citation
DOI: https://doi.org/10.1007/3-540-45105-6_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40602-0
Online ISBN: 978-3-540-45105-1
eBook Packages: Springer Book Archive