Explicit and Emergent Cooperation Schemes for Search Algorithms | SpringerLink
Skip to main content
Springer Nature Link
Log in

Explicit and Emergent Cooperation Schemes for Search Algorithms

  • Conference paper
Learning and Intelligent Optimization (LION 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5313))

Included in the following conference series:

Abstract

Cooperation as problem-solving and algorithm-design strategy is widely used to build methods addressing complex discrete optimization problems. In most cooperative-search algorithms, the explicit cooperation scheme yields a dynamic process not deliberately controlled by the algorithm design but inflecting the global behaviour of the cooperative solution strategy. The paper presents an overview of explicit cooperation mechanisms and describes issues related to the associated dynamic processes and the emergent computation they often generate. It also identifies a number of research directions into cooperation mechanisms, strategies for dynamic learning, automatic guidance, and self-adjustment, and the associated emergent computation processes.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alba, E. (ed.): Parallel Metaheuristics. A New Class of Algorithms. John Wiley & Sons, Hoboken (2005)

    MATH  Google Scholar 

  2. Arkin, R.C.: Behavior-Based Robotics. MIT Press, Cambridge (1998)

    Google Scholar 

  3. Brooks, R.A.: Intelligence without Representation. Intelligence without Representation 47(1-3), 139–159 (1991)

    Google Scholar 

  4. Brooks, R.A.: Cambrian Intelligence: The arly History of the New AI. MIT Press, Cambridge (1999)

    MATH  Google Scholar 

  5. Brooks, R.S.: A robust layered control system for a mobile robot. In: Readings in Uncertain Reasoning, pp. 204–213. Morgan Kaufmann Publishers Inc., San Francisco (1990)

    Google Scholar 

  6. Cao, U.Y., Fukunaga, A.S., Kahng, A.B.: Cooperative Mobile Robotics: Antecedents and Directions. Autonomous Robots 4(1), 7–23 (1997)

    Article  Google Scholar 

  7. Crainic, T.G.: Parallel Computation, Co-operation, Tabu Search. In: Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization Via Memory and Evolution: Tabu Search and Scatter Search, pp. 283–302. Kluwer Academic Publishers, Norwell (2005)

    Chapter  Google Scholar 

  8. Crainic, T.G.: Parallel Solution Methods for Vehicle Routing Problems. In: Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, Heidelberg (to appear, 2007)

    Google Scholar 

  9. Crainic, T.G., Di Chiara, B., Nonato, M., Tarricone, L.: Tackling Electrosmog in Completely Configured 3G Networks by Parallel Cooperative Meta-Heuristics. IEEE Wireless Communications 13(6), 34–41 (2006)

    Article  Google Scholar 

  10. Crainic, T.G., Gendreau, M.: Towards an Evolutionary Method - Cooperating Multi-Thread Parallel Tabu Search Hybrid. In: Voß, S., Martello, C., Roucairol, C., Osman, I.H. (eds.) Meta-Heuristics 1998: Theory & Applications, pp. 331–344. Kluwer Academic Publishers, Norwell (1999)

    Google Scholar 

  11. Crainic, T.G., Gendreau, M.: Cooperative Parallel Tabu Search for Capacitated Network Design. Journal of Heuristics 8(6), 601–627 (2002)

    Article  Google Scholar 

  12. Crainic, T.G., Li, Y., Toulouse, M.: A First Multilevel Cooperative Algorithm for the Capacitated Multicommodity Network Design. Computers & Operations Research 33(9), 2602–2622 (2006)

    Article  MATH  Google Scholar 

  13. Crainic, T.G., Nourredine, H.: Parallel Meta-Heuristics Applications. In: Alba, E. (ed.) Parallel Metaheuristics, pp. 447–494. John Wiley & Sons, Hoboken (2005)

    Chapter  Google Scholar 

  14. Crainic, T.G., Toulouse, M.: Parallel Strategies for Meta-heuristics. In: Glover, F., Kochenberger, G. (eds.) Handbook in Metaheuristics, pp. 475–513. Kluwer Academic Publishers, Norwell (2003)

    Chapter  Google Scholar 

  15. Crainic, T.G., Toulouse, M., Gendreau, M.: Parallel Asynchronous Tabu Search for Multicommodity Location-Allocation with Balancing Requirements. Annals of Operations Research 63(2), 277–299 (1996)

    Article  MATH  Google Scholar 

  16. Crainic, T.G., Toulouse, M., Gendreau, M.: Towards a Taxonomy of Parallel Tabu Search Algorithms. INFORMS Journal on Computing 9(1), 61–72 (1997)

    Article  MATH  Google Scholar 

  17. Cung, V.-D., Martins, S.L., Ribeiro, C.C., Roucairol, C.: Strategies for the Parallel Implementations of Metaheuristics. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 263–308. Kluwer Academic Publishers, Norwell (2002)

    Chapter  Google Scholar 

  18. Dagaeff, T., Chantemargue, F.: Performance of Autonomy-based Systems: Tuning Emergent Cooperation. Technical Report 98-20, Computer Science Department, University of Fribourg (1998)

    Google Scholar 

  19. Engelbrecht, A.P.: Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester (2006)

    Google Scholar 

  20. Fodor, J.A.: The Modularity of Mind. MIT Press, Cambridge (1983)

    Google Scholar 

  21. Le Bouthillier, A., Crainic, T.G.: A Cooperative Parallel Meta-Heuristic for the Vehicle Routing Problem with Time Windows. Computers & Operations Research 32(7), 1685–1708 (2005)

    Article  MATH  Google Scholar 

  22. Le Bouthillier, A., Crainic, T.G., Kropf, P.: A Guided Cooperative Search for the Vehicle Routing Problem with Time Windows. IEEE Intelligent Systems 20(4), 36–42 (2005)

    Article  Google Scholar 

  23. Mataric, M.J.: Designing Emergent Behaviors: From Local Interactions to Collective Intelligence. In: Proceedings of the Second International Conference on From Animals to Animats 2: Simulation of Adaptive Behavior, pp. 432–441. MIT Press, Cambridge (1993)

    Google Scholar 

  24. Mataric, M.J.: Issues and Approaches in the Design of Collective Autonomous Agents. Robotics and Autonomous Systems 16(2-4), 321–331 (1995)

    Article  Google Scholar 

  25. Nitschke, G.: Emergence of Cooperation: State of the Art. Artificial Life 11(3), 367–396 (2005)

    Article  Google Scholar 

  26. Oduntan, I.O., Toulouse, M., Baumgartner, R., Bowman, C., Somorjai, R., Crainic, T.G.: A Multilevel Tabu Search Algorithm for the Feature Selection Problem in Biomedical Data Sets. Computers & Mathematics with Applications 55(5), 1019–1033 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  27. Oliveira, E.C., Fischer, K., Stepánková, O.: Multi-agent systems: which research for which applications. Robotics and Autonomous Systems 27(1-2), 91–106 (1999)

    Article  Google Scholar 

  28. Ouyang, M., Toulouse, M., Thulasiraman, K., Glover, F., Deogun, J.S.: Multilevel cooperative search for the circuit/hypergraph partitioning problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21(6), 685–694 (2002)

    Article  Google Scholar 

  29. Rochat, Y., Taillard, É.D.: Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics 1(1), 147–167 (1995)

    Article  MATH  Google Scholar 

  30. Talbi, E.-G. (ed.): Parallel Combinatorial Optimization. Wiley-Interscience, Wiley & Sons, Hoboken (2006)

    Google Scholar 

  31. Toulouse, M., Crainic, T.G., Sansó, B., Thulasiraman, K.: Self-Organization in Cooperative Search Algorithms. In: Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics, Omnipress, Madisson, WI, pp. 2379–2385 (1998)

    Google Scholar 

  32. Toulouse, M., Thulasiraman, K., Glover, F.: Multi-Level Cooperative Search: A New Paradigm for Combinatorial Optimization and an Application to Graph Partitioning. In: Amestoy, P., Berger, P., Daydé, M., Duff, I., Frayssé, V., Giraud, L., Ruiz, D. (eds.) Euro-Par 1999. LNCS, vol. 1685, pp. 533–542. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  33. Verhoeven, M.G.A., Aarts, E.H.L.: Parallel Local Search. Journal of Heuristics 1(1), 43–65 (1995)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CIRRELT, Université de Montréal, C.P. 6128, Succursale Centre-Ville, Montreal, H3C 3J7, Canada

    Teodor Gabriel Crainic & Michel Toulouse

  2. Department of Management and Technology, ESG UQAM, C.P. 8888, succ. Centre-ville, Montreal, QC, Canada, H3C 3P8

    Teodor Gabriel Crainic

Authors
  1. Teodor Gabriel Crainic
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michel Toulouse
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. Computer Science, University of Bologna, Bologna, Italy

    Vittorio Maniezzo

  2. Università degli Studi di Trento, Trento, Italy

    Roberto Battiti

  3. Discrete Math and Complex Systems Department, Sandia National Laboratories, Albuquerque, New Mexico, USA

    Jean-Paul Watson

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Crainic, T.G., Toulouse, M. (2008). Explicit and Emergent Cooperation Schemes for Search Algorithms. In: Maniezzo, V., Battiti, R., Watson, JP. (eds) Learning and Intelligent Optimization. LION 2007. Lecture Notes in Computer Science, vol 5313. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92695-5_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92695-5_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92694-8

  • Online ISBN: 978-3-540-92695-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation