A study of ACO capabilities for solving the maximum clique problem. (English) Zbl 1163.90817
Summary: 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.
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.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Karp, R.M. (1972). ”Reducibility Among Combinatorial Problems.” Complexity of Computer Computations 85–104 |
| [2] | 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. · Zbl 1253.90188 |
| [3] | Johnson, D.S. (1974). ”Approximation Algorithms for Combinatorial Problems.” Journal of Computer Science 9, 256–278. · Zbl 0296.65036 · doi:10.1016/S0022-0000(74)80044-9 |
| [4] | 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. · Zbl 0815.90121 · doi:10.1287/opre.42.5.860 |
| [5] | 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.. · Zbl 0947.68119 |
| [6] | Battiti, R. and M. Protasi. (2001). ”Reactive Local Search for the Maximum Clique Problem.” Algorithmica 29(4), 610–637. · Zbl 0985.68016 · doi:10.1007/s004530010074 |
| [7] | Jagota, A. and L.A. Sanchis. (2001). ”Adaptive, Restart, Randomized Greedy Heuristics for Maximum Clique.” Journal of Heuristics 7(6), 565–585. · Zbl 0987.68612 · doi:10.1023/A:1011925109392 |
| [8] | 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. · doi:10.1023/B:HEUR.0000026264.51747.7f |
| [9] | 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. · Zbl 0674.90059 |
| [10] | 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. · Zbl 0859.68068 |
| [11] | 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. · Zbl 0685.68056 · doi:10.1007/BF02243141 |
| [12] | 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. · Zbl 0774.90033 |
| [13] | 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. · Zbl 0775.90297 · doi:10.1007/BF02023002 |
| [14] | 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. · Zbl 1044.68780 |
| [15] | 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. |
| [16] | Dorigo, M., G. Di Caro, and L.M. Gambardella. (1999). ”Ant Algorithms for Discrete Optimization.” Artificial Life 5(2), 137–172. · doi:10.1162/106454699568728 |
| [17] | 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. |
| [18] | 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. |
| [19] | 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. · doi:10.1016/S0167-739X(00)00043-1 |
| [20] | Dorigo, M. (1992). Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy. |
| [21] | 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. · doi:10.1109/3477.484436 |
| [22] | 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. · doi:10.1109/4235.585892 |
| [23] | 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. · Zbl 1054.90621 |
| [24] | 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. · doi:10.1109/69.806935 |
| [25] | 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. · Zbl 0937.90125 · doi:10.1023/A:1018940026670 |
| [26] | 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. |
| [27] | 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. |
| [28] | Solnon, C. (2002). ”Ants Can Solve Constraint Satisfaction Problems.” IEEE Transactions on Evolutionary Computation 6(4), 347–357. · doi:10.1109/TEVC.2002.802449 |
| [29] | 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. · Zbl 1033.68623 |
| [30] | 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. |
| [31] | 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. |
| [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. |
| [33] | 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. · Zbl 1044.68801 |
| [34] | 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. |
| [35] | 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. |
| [36] | 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. · Zbl 1177.90428 |
| [37] | 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. · Zbl 1054.68661 |
| [38] | 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. · Zbl 1054.68655 |
| [39] | 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. |
| [40] | 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. · Zbl 0859.68066 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
