Skip to main content
SpringerLink
Log in

A study of ACO capabilities for solving the maximum clique problem

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal cliques through the repeated addition of vertices into partial cliques, and uses “pheromone trails” as a greedy heuristic to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are laid and exploited, i.e., on edges or on vertices of the graph.

We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Karp, R.M. (1972). “Reducibility Among Combinatorial Problems.” Complexity of Computer Computations 85–104

  • Bomze, I., M. Budinich, P.M. Pardalos, and M. Pelillo. (1999). “The Maximum Clique Problem.” In D.-Z. Du and P. M. Pardalos (eds.), Handbook of Combinatorial Optimization Springer, vol. 4, pp. 1–74.

  • Johnson, D.S. (1974). “Approximation Algorithms for Combinatorial Problems.” Journal of Computer Science 9, 256–278.

    MATH  Google Scholar 

  • Feo, T.A., M.G.C. Resende, and S.H. Smith. (1994). “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42, 860–878.

    Google Scholar 

  • Abello, J., P.M. Pardalos, and M.G.C. Resende. (1999). “On Maximum Clique Problems in Very Large Graphs.” In J.M. Abello (ed.), External Memory Algorithms of DIM ACS Series in Discrete Mathematics and Theoretical Computer Science American Mathematical Society, Boston, MA, USA, vol. 50, pp. 119–130..

  • Battiti, R. and M. Protasi. (2001). “Reactive Local Search for the Maximum Clique Problem.” Algorithmica 29(4), 610–637.

    Article  MathSciNet  Google Scholar 

  • Jagota, A. and L.A. Sanchis. (2001). “Adaptive, Restart, Randomized Greedy Heuristics for Maximum Clique.” Journal of Heuristics 7(6), 565–585.

    Article  Google Scholar 

  • Grosso, A., M. Locatelli, and F. Delia Croce. (2004). “Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem.” Journal of Heuristics 10(2), 135–152.

    Article  Google Scholar 

  • Aarts, E.H.L. and J.H.M. Korst. (1989). Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, Chichester, U.K.: John Wiley & Sons.

    Google Scholar 

  • Homer, S. and M. Peinado. (1996). “Experiments with Polynomial-time Clique Approximation Algorithms on Very Large Graphs.” In D.S. Johnson and M.A. Trick (eds.), Cliques, Coloring, and Satisfiability, volume 26 of DIM ACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Boston, MA, USA, pp. 147–168.

  • Friden, C., A. Hertz, and D. de Werra. (1989). “STABULUS: A Technique for Finding Stable Sets in Large Graphs with Tabu Search.” Computing 42(l), 35–44.

    Google Scholar 

  • Glover, F. and M. Laguna. (1993). “Tabu Search.” In C.R. Reeves (ed.), Modern Heuristics Techniques for Combinatorial Problems, Oxford, UK, Blackwell Scientific Publishing, pp. 70–141.

    Google Scholar 

  • Gendreau, M., P. Soriano, and L. Salvail (1993). Salvail. Solving the Maximum Clique Problem Using a Tabu Search Approach. Annals of Operations Research 41(4), 385–403.

    Article  Google Scholar 

  • Marchiori, E. (2002). “Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem.” In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, and G.R. Raidl (eds.), Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTim, volume 2279 of LNCS, pp. 112–121. Springer-Verlag.

  • Dorigo, M. and G. Di Caro. (1999). “The Ant Colony Optimization Meta-heuristic.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, McGraw Hill, UK, pp. 11–32.

    Google Scholar 

  • Dorigo, M., G. Di Caro, and L.M. Gambardella. (1999). “Ant Algorithms for Discrete Optimization.” Artificial Life 5(2), 137–172.

    Article  Google Scholar 

  • Jones, T. and S. Forrest. (1995). “Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms.” In L. Eshelman (ed.), Proceedings of the Sixth International Conference on Genetic Algorithms 184–192, San Francisco, CA, Morgan Kaufmann.

  • Merz, P. and B. Freisleben. (1999). “Fitness Landscapes and Memetic Algorithm Design.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization McGraw Hill, UK, pp. 245–260.

    Google Scholar 

  • Stützle, T. and H.H. Hoos. (2000). MAX - MXN Ant System. Journal of Future Generation Computer Systems, special isuue on Ant Algorithms 16, 889–914.

    Google Scholar 

  • Dorigo, M. (1992). Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy.

  • Dorigo, M., V. Maniezzo, and A. Colorni. (1996). “Ant System: Optimization by a Colony of Cooperating Agents.” IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics 26(1), 29–41.

    Google Scholar 

  • Dorigo, M. and L.M. Gambardella. (1997). “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.” IEEE Transactions on Evolutionary Computation l(l), 53–66.

    Google Scholar 

  • Gambardella, L.M., E. Taillard, and M. Dorigo. (1999). “Ant Colonies for the Quadratic Assignment Problem.” Journal of the Operational Research Society 50, 167–176.

    Google Scholar 

  • Maniezzo, V. and A. Colorni. (1999). “The Ant System Applied to the Quadratic Assignment Problem.” IEEE Transactions on Data and Knowledge Engineering 11(5), 769–778.

    Google Scholar 

  • Bullnheimer, B., R.F. Hartl, and C. Strauss. (1999). “An Improved Ant System Algorithm for the Vehicle Routing Problem.” Annals of Operations Research 89, 319–328.

    Article  MathSciNet  Google Scholar 

  • Gambardella, L.M., E.D. Taillard, and G. Agazzi. (1999). “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, McGraw Hill, London, UK, pp. 63–76.

    Google Scholar 

  • Solnon, C. (2000). “Solving Permutation Constraint Satisfaction Problems with Artificial Ants.” In W. Horn (ed.), Proceedings of ECAI’2000, IOS Press, Amsterdam, The Netherlands pp. 118–122.

  • Solnon, C. (2002). “Ants Can Solve Constraint Satisfaction Problems.” IEEE Transactions on Evolutionary Computation 6(4), 347–357.

    Article  Google Scholar 

  • Fenet, S. and C. Solnon. (2003). “Searching for Maximum Cliques with Ant Colony Optimization.” In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, and G.R. Raidl (eds.), Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2003: EvoCOP, EvoIASP, EvoSTim, volume 2611 of LNCS, Springer-Verlag, 2003, pp. 236–245.

  • Bui, T.N. and J.R. Rizzo. (2004). “Finding Maximum Cliques with Distributed Ants.” In K. Deb, R. Poli, W. Banzhaf, H.-G. Beyer, E.K. Burke, P.J. Darwen, D. Dasgupta, D. Floreano, J.A. Foster, M. Harman, O. Holland, P.L. Lanzi, L. Spector, A. Tettamanzi, D. Thierens, and A.M. Tyrell (eds.), Genetic and Evolutionary Computation - GECCO 2004,volume 3102 of lncs, Springer-Verlag, pp. 24–35.

  • van Hemert, J.I. and T. Bäck. (2002). “Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction.” In J.J. Merelo, A. Panagiotis, H.-G. Beyer, Jośe-Luis Fernàndez-Villacañtilde;as, and Hans-Paul Schwefel (eds.), Proceedings of the 7th International Conference on Parallel Problem Solving from Nature,volume 2439 of lncs, Berlin, Springer-Verlag, pp. 23–32.

  • Colorni, A., M. Dorigo, and V. Maniezzo. (1992). “An Investigation of Some Properties of an Ant Algorithm.” In R. Männer and B. Manderick (eds.), Parallel Problem Solving from Nature 2, PPSN-II, Brussels, Belgium Elsevier, pp. 515–526.

  • Solnon, C. (2002). “Boosting AGO with a Preprocessing Step.” In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, and G.R. Raidl (eds.), Applications of Evolutionary Computing, Proceedings of EvoWorkshops2002: EvoCOP, EvoIASP, EvoSTim,volume 2279 of LNCS, Springer-Verlag, pp. 161–170.

  • Birattari, M., T. Stiitzle, L. Paquete, and K. Varrentrapp. (2002). “A Racing Algorithm for Configuring Metaheuristics.” In W. B. Langdon, E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poll, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska (eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002) San Mateo, CA, Morgan Kaufmann Publishers, pp. 11–18.

  • Burke, R., S. Gustafson, and G. Kendall. (2002). “A Survey and Analysis of Diversity Measures in Genetic Programming.” In W. B. Langdon, E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M.A. Potter, A.C. Schultz, J.F. Miller, E. Burke, and N. Jonoska (eds.), GECCO 2002: Proceedings of the Ge netic and Evolutionary Computation Conference, New York, 9–13 July. Morgan Kaufmann Publishers, pp. 716–723.

  • van Hemert, J.I. and C. Solnon. (2004). “A Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems.” In S. Cagnoni, J. Gottlieb, E. Hart, M. Midden-dorf, and G.R. Raidl (eds.), Evolutionary Computation in Combinatorial Optimization (EvoCOP 2004) volume 3004 of LNCS, Springer-Verlag, pp. 114–123.

  • Sidaner, A., O. Bailleux, and J.J. Chabrier. (2001). “Measuring the Spatial Dispersion of Evolutionist Search Processes: Application to Walksat.” In P. Collet, C. Fonlupt, J.K. Hao, E. Lutton, and M. Schoenauer (eds.), 5th International Conference EA 2001 volume 2310 of lncs, Springer-Verlag, pp. 77–90.

  • Morrison, R.W. and K.A. De Jong. (2001). “Measurement of Population Diversity.” In P. Collet, C. Fonlupt, J.K. Hao, E. Lutton, and M. Schoenauer (eds.), 5th International Conference EA 2001,volume 2310 of lncs, Springer-Verlag, pp. 31–41.

  • Lourengo, H.R., O. Martin, and T. Stützle. (2002). “Iterated Local Search.” In F. Glover and G. Kochenberger (eds.), Handbook of metaheuristics, Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 321–353.

    Google Scholar 

  • Brockington, M. and J.C. Culberson. (1996). “Camouflaging Independent Sets in Quasi-random Graphs.” In D.S. Johnson and M.A. Trick (eds.), Cliques, Coloring, and Satisfiability volume 26 of DIM ACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Boston, MA, USA, pp. 75–88.

Download references

Author information

Authors and Affiliations

  1. LIRIS CNRS UMR 5205, University Lyon I, Nautibus, 43 Bd du 11 novembre, 69622, Villeurbanne cedex, France

    Christine Solnon & Serge Fenet

Authors
  1. Christine Solnon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Serge Fenet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christine Solnon.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Solnon, C., Fenet, S. A study of ACO capabilities for solving the maximum clique problem. J Heuristics 12, 155–180 (2006). https://doi.org/10.1007/s10732-006-4295-8

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-006-4295-8

Keywords

Search

Navigation