In this chapter we discuss the ant colony optimization meta-heuristic (ACO) and its application to static and dynamic constraint satisfaction optimization problems, in particular the static and dynamic maximum satisfiability problems (MAX-SAT). In the first part of the chapter we give an introduction to meta-heuristics in general and ant colony optimization in particular, followed by an introduction to constraint satisfaction and static and dynamic constraint satisfaction optimization problems. Then, we describe how to apply the ACO algorithm to the problems, and do an analysis of the results obtained for several benchmarks. The adapted ant colony optimization accomplishes very well the task of dealing with systematic changes of dynamic MAX-SAT instances derived from static problems.
This is a preview of subscription content, log in via an institution to check access.
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
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press (2004)
Garey, M.R., Johson, D.S.J.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman Publishers (1979)
Roli, A., Blum, C., Dorigo, M.: ACO for maximal constraint satisfaction problems. MIC’2001 - Metaheuristics International Conference, Porto, Portugal (2001) 187-192
Kennedy, J., Eberhart, R.: Swarm intelligence. Morgan Kaufmann Publishers (2001)
Osman, I., Laporte, G.: Metaheuristics: A bibliography. Annals of Operations Research (63)(1996)513-628,
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and concep-tual comparison. ACM Compututational Survey 35(3) (2003) 268-308
Aarts, E.H.L., Korst, J.H.M., Laarhoven, P.J.M.V.: Simulated annealing. In: Local Search in Combinatorial Optimization. Wiley-Interscience Eds, Chichester, England (1997) 91-120
Glover, F., Laguna, M.: Tabu search. (1993) 70-150
Ramalhinho-Lourenço, H., Martin, O.C., Stützle, T.: Iterated local search. (513) (2000)
Feo, T., Resende, M.: Greedy randomized adaptive search procedures. Journal of Global Optimization 6 (1995) 109-133
Cicirello, V.A., Smith, S.F.: Wasp-like agents for distributed factory coordination. Autonomous Agents and Multi-agent systems 8 (2004) 237-266
Pinto, P., Runkler, T.A., Sousa, J.M.C.: Agent based optimization of the MAX -SAT problem using wasp swarms. Controlo 2006, 7th Portuguese Conference on Automatic Control (2006)
Pinto, P., Runkler, T.A., Sousa, J.M.C.: Wasp swarm algorithm for dynamic MAX -SAT problems. ICANNGA 2007, 8th International Conference on Adaptive and Natural Com-puting Algorithms (2007)
Abbass, H.: An agent based approach to 3-SAT using marriage in honey-bees optimization. International Journal of Knowledge-Based Intelligent Engineering Systems (2002) 1-8
Grasse., P.P.: La reconstruction du nid et les coordinations inter-individuelles chez belli-cositermes natalensis et cubitermes sp. la theorie de la stigmergie: Essai d’interpretation du comportement des termites constructeurs. Insectes Sociaux 6 (1959) 41-81
Pimont, S., Solnon, C.: A generic ant algorithm for solving constraint satisfaction prob-lems. 2nd International Workshop on Ant Algorithms (ANTS 2000), Brussels, Belgium (2000)100-108
Cicirello, V.A., Smith, S.F.: Ant colony for autonomous decentralized shop floor routing. In: Proceedings of ISADS-2001, Fifth International symposium on autonomous decen-tralized systems. (2001)
Silva, C.A., Runkler, T.A., Sousa, J.M.C., da Costa, J.M.S.: Optimization of logistic processes in supply-chains using meta-heuristics. In Pires, F.M., Abreu, S., eds.: Lecture Notes on Artificial Intelligence 2902, Progress in Artificial Intelligence, 11th Portuguese Conference on Artificial Intelligence. Springer Verlag, Beja, Portugal (2003) 9-23
Silva, C.A., Runkler, T.A., Sousa, J.M.C., Palm, R.: Ant colonies as logistic process optimizers. In Dorigo, M., Caro, G.D., Sampels, M., eds.: Ant Algorithms, International Workshop ANTS 2002, Brussels, Belgium. Lecture Notes in Computer Science LNCS 2463, Heidelberg, Springer (2002) 76-87
Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press (2007)
Tsang, E.: Foundations of Constraint Satisfaction. Academic Press (1993)
Gennari, R.: Temporal reasoning and constraint programming: A survey (1998)
Frei, C., Faltings, B.: Resource allocation and constraint satisfaction techniques. In: CP ’99: Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, London, UK, Springer-Verlag (1999) 204-218
Cesta, A., Cortellessa, G., Oddi, A., Policella, N., Susi, A.: A constraint-based archi-tecture for flexible support to activity scheduling. In: AI*IA 01: Proceedings of the 7th Congress of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence, London, UK, Springer-Verlag (2001) 369-381
Abril, M., Salido, M.A., Barber, F., Ingolotti, L.: Distributed constraint satisfaction prob-lems to model railway scheduling problems. ICAPS 2006 Workshop on Constraint Satis-faction Techniques for Planning and Scheduling Problems, Cumbria (England) (2006)
Rasconi, R., Policella, N., Cesta, A.: Fix the schedule or solve again - comparing constraint-based approaches to schedule execution. In: Proceedings of the ICAPS Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. (2006)
Goodrich, M.T., Tamassia, R.: Algorithm Design - Foundations, Analysis, and Internet Examples. John Wiley & Sons, Inc. (2001)
Zhang, W.: Phase transitions and backbones of 3-SAT and maximum 3-SAT. In: Princi-ples and Practice of Constraint Programming. (2001) 153-167
Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: Pro-ceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91, Sidney, Australia. (1991) 331-337
Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: 10-th National Conf. on Artificial Intelligence (AAAI-92), San Jose, CA (1992) 459-465
Mertens, K., Holvoet, T., Berbers, Y.: The dynCOAA algorithm for dynamic constraint optimization problems. In Weiss, G., Stone, Peter, e., eds.: Proceedings of the Fifth International Joint Conference on Autonomous Agents and MultiAgent Systems. (2006) 1421-1423
Mertens, K., Holvoet, T., Berbers, Y.: Which dynamic constraint problems can be solved by ants. In Sutcliffe, G., Goebel, Randy, E., eds.: Proceedings of The 19th International FLAIRS Conference. (2006) 439-444
Mailler, R.: Comparing two approaches to dynamic, distributed constraint satisfaction. In: AAMAS ’05: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, USA, ACM Press (2005) 1049-1056
Hoos, H.H., O’Neill, K.: Stochastic local search methods for dynamic SAT - an initial investigation. AAAI-2000 Workshop “Leveraging Probability and Uncertainty in Com-putation”, Austin, Texas (2000) 22-26
Solnon, C.: Ants can solve constraint satisfaction problems. IEEE Transactions on Evo-lutionary Computation 6 (2002) 347-357
Battiti, R., Protasi, M.: Reactive search, a history-based heuristic for MAX -SAT. ACM Journal of Experimental Algorithmics 2 (1997)
Johnson, D., Trick, M.: Cliques, coloring, and satisfiability: Second DIMACS implemen-tation challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1996)
Hoos, H.H., Stützle, T.: SATLIB: An online resource for research on SAT. SAT 2000 (2000)283-292
Hoos, H.H., Stützle, T.: Local search algorithms for SAT: an empirical evaluation. Journal of Automated Reasoning, special Issue “SAT 2000” (1999) 421-481
Smyth, K., Hoos, H.H., Stützle, T.: Iterated robust tabu search for MAX -SAT. Lecture Notes in Computer Science, Springer Verlag 44 (2003) 279-303
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Pinto, P.C., Runkler, T.A., Sousa, J.M.C. (2007). Ant Colony Optimization and its Application to Regular and Dynamic MAX-SAT Problems. In: Dressler, F., Carreras, I. (eds) Advances in Biologically Inspired Information Systems. Studies in Computational Intelligence, vol 69. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72693-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-72693-7_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72692-0
Online ISBN: 978-3-540-72693-7
eBook Packages: EngineeringEngineering (R0)