Advertisement

A Multi-Agent Organizational Framework for Coevolutionary Optimization

  • Grégoire Danoy
  • Pascal Bouvry
  • Olivier Boissier
Chapter
Part of the Lecture Notes in Computer Science book series (LNCS, volume 6550)

Abstract

This paper introduces DAFO, a Distributed Agent Framework for Optimization that helps in designing and applying Coevolutionary Genetic Algorithms (CGAs). CGAs have already proven to be efficient in solving hard optimization problems, however they have not been considered in the existing agent-based metaheuristics frameworks that currently provide limited organization models. As a solution, DAFO includes a complete organization and reorganization model, Multi-Agent System for EVolutionary Optimization (MAS4EVO), that permits to formalize CGAs structure, interactions and adaptation. Examples of existing and original CGAs modeled using MAS4EVO are provided and an experimental proof of their efficiency is given on an emergent topology control problem in mobile hybrid ad hoc networks called the injection network problem.

Keywords

Multi-Agent Systems Organizational Model Evolutionary Algorithms 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Alba, E., Almeida, F., Blesa, M., Cabeza, J., Cotta, C., Díaz, M., Dorta, I., Gabarró, J., León, C., Luna, J.M., Moreno, L., Pablos, C., Petit, J., Rojas, A., Xhafa, F.: MALLBA: A library of skeletons for combinatorial optimisation. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 927–932. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  2. 2.
    Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evolutionary Computation 6(5), 443–462 (2002)CrossRefGoogle Scholar
  3. 3.
    Bauer, B., Muller, J., Odell, J.: Agent UML: A formalism for specifying multiagent interaction (2001)Google Scholar
  4. 4.
    Bellifemine, F.L., Poggi, A., Rimassa, G.: Developing multi-agent systems with JADE. In: Castelfranchi, C., Lespérance, Y. (eds.) ATAL 2000. LNCS (LNAI), vol. 1986, pp. 89–103. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  5. 5.
    Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)CrossRefGoogle Scholar
  6. 6.
    Boissier, O., Gâteau, B.: Normative multi-agent organizations: Modeling, support and control, draft version. In: Normative Multi-agent Systems. No. 07122 in Dagstuhl Seminar Proceedings, IBFI, Schloss Dagstuhl, Germany (2007)Google Scholar
  7. 7.
    Cahon, S., Melab, N., Talbi, E.G.: Building with paradisEO reusable parallel and distributed evolutionary algorithms. Parallel Comput. 30(5-6), 677–697 (2004)CrossRefzbMATHGoogle Scholar
  8. 8.
    Cahon, S., Melab, N., Talbi, E.G.: ParadisEO: A framework for the reusable design of parallel and distributed metaheuristics. Journal of Heuristics 10(3), 357–380 (2004)CrossRefzbMATHGoogle Scholar
  9. 9.
    Crainic, T., Toulouse, M.: Parallel Strategies for Meta-heuristics, pp. 475–513. Kluwer Academic Publishers, Dordrecht (2003)zbMATHGoogle Scholar
  10. 10.
    Danoy, G., Bouvry, P., Seredynski, F.: Evaluations of Strategies for Co-Evolutionary Genetic Algorithms: dLCGA Case Study. In: Proceedings of the 16th International Conference on Artificial Neural Networks In Engineering (ANNIE 2006), pp. 91–96. ASME publisher, Saint Louis (2006) ISBN 0–7918–0256–6Google Scholar
  11. 11.
    Danoy, G.: A Multi-Agent Approach for Hybrid and Dynamic Coevolutionary Genetic Algorithms: Organizational Model and Real-World Problems Applications. Ph.D. thesis (2008)Google Scholar
  12. 12.
    Danoy, G., Alba, E., Bouvry, P., Brust, M.R.: Optimal design of ad hoc injection networks by using genetic algorithms. In: Lipson, H. (ed.) GECCO, p. 2256. ACM, New York (2007)Google Scholar
  13. 13.
    Danoy, G., Bouvry, P., Alba, E.: Distributed coevolutionary genetic algorithm for optimal design of ad hoc injection networks. Special Session on Parallel and Grid Computing for Optimization (PGCO 2007), Prague (2007)Google Scholar
  14. 14.
    Danoy, G., Bouvry, P., Martins, T.: hlcga: A hybrid competitive coevolutionary genetic algorithm. In: HIS, p. 48. IEEE Computer Society, Los Alamitos (2006)Google Scholar
  15. 15.
    Darwin, C.: The Origin of Species by Means of Natural Selection. Mentor Reprint, 1958, NY (1859)Google Scholar
  16. 16.
    David Meignan, J.C.C., Koukam, A.: An organizational view of metaheuristics. In: AAMAS 2008: Proceedings of First International Workshop on Optimisation in Multi-Agent Systems, pp. 77–85 (2008)Google Scholar
  17. 17.
    Dorne, R., Voudouris, C.: Hsf: the iopt’s framework to easily design metaheuristic methods, pp. 237–256 (2004)Google Scholar
  18. 18.
    Dréo, J., Aumasson, J.P., Tfaili, W., Siarry, P.: Adaptive learning search, a new tool to help comprehending metaheuristics. International Journal on Artificial Intelligence Tools 16(3), 483–505 (2007)CrossRefGoogle Scholar
  19. 19.
    Ehrlich, P.R., Raven, P.H.: Butterflies and plants: A study in coevolution. Evolution 18(4), 586–608 (1964)CrossRefGoogle Scholar
  20. 20.
    Ferber, J., Gutknecht, O., Michel, F.: From agents to organizations: An organizational view of multi-agent systems. In: Giorgini, P., Müller, J.P., Odell, J.J. (eds.) AOSE 2003. LNCS, vol. 2935, pp. 214–230. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  21. 21.
    Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston (1989)zbMATHGoogle Scholar
  22. 22.
    Gutknecht, O., Ferber, J.: Madkit: a generic multi-agent platform. In: Proc. of the Fourth International Conference on Autonomous Agents, pp. 78–79. ACM Press, New York (2000)CrossRefGoogle Scholar
  23. 23.
    Hogie, L., Bouvry, P., Guinand, F., Danoy, G., Alba, E.: Simulating Realistic Mobility Models for Large Heterogeneous MANETS. In: Demo proceeding of the 9th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM 2006). IEEE, Los Alamitos (October 2006)Google Scholar
  24. 24.
    Hübner, J.F., Sichman, J.S., Boissier, O.: Developing organised multiagent systems using the moise. IJAOSE 1(3/4), 370–395 (2007)CrossRefGoogle Scholar
  25. 25.
    Iorio, A.W., Li, X.: Parameter control within a co-operative co-evolutionary genetic algorithm. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 247–256. Springer, Heidelberg (2002)Google Scholar
  26. 26.
    Mathieu, P., Routier, J.-C., Secq, Y.: RIO: Roles, interactions and organizations. In: Mařík, V., Müller, J.P., Pěchouček, M. (eds.) CEEMAS 2003. LNCS (LNAI), vol. 2691, pp. 147–157. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  27. 27.
    Meignand, D.: Une Approche Organisationnelle et multi-Agent pour la Modélisation et l’Implantation de Métaheuristiques, Application aux problmes doptimisation de rśeaux de transport. Ph.D. thesis (2008)Google Scholar
  28. 28.
    Milano, M., Roli, A.: Magma: A multiagent architecture for metaheuristics. IEEE Trans. on Systems, Man and Cybernetics – Part B 34(2), 925–941 (2004)CrossRefGoogle Scholar
  29. 29.
    Mulet, L., Such, J.M., Alberola, J.M.: Performance evaluation of open-source multiagent platforms. In: AAMAS 2006: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1107–1109. ACM Press, New York (2006)CrossRefGoogle Scholar
  30. 30.
    Noda, E., Coelho, A.L.V., Ricarte, I.L.M., Yamakami, A., Freitas, A.A.: Devising adaptive migration policies for cooperative distributed genetic algorithms. In: Proc. 2002 IEEE Int. Conf. on Systems, Man and Cybernetics. IEEE Press, Los Alamitos (2002)Google Scholar
  31. 31.
    O’Brien, P.D., Nicol, R.C.: FIPA, towards a standard for software agents. BT Technology Journal 16(3), 51–59 (1998)CrossRefGoogle Scholar
  32. 32.
    Paredis, J.: Coevolutionary life-time learning. In: Ebeling, W., Rechenberg, I., Voigt, H.-M., Schwefel, H.-P. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 72–80. Springer, Heidelberg (1996)CrossRefGoogle Scholar
  33. 33.
    Popovici, E., De Jong, K.: The effects of interaction frequency on the optimization performance of cooperative coevolution. In: GECCO 2006: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 353–360. ACM, New York (2006)Google Scholar
  34. 34.
    Popovici, E., Jong, K.D.: The dynamics of the best individuals in co-evolution. Natural Computing: An International Journal 5(3), 229–255 (2006)MathSciNetCrossRefzbMATHGoogle Scholar
  35. 35.
    Popovici, E., Jong, K.D.: Sequential versus parallel cooperative coevolutionary algorithms for optimization. In: Proceedings of Congress on Evolutionary Computation (2006)Google Scholar
  36. 36.
    Potter, M.A.: The design and analysis of a computational model of cooperative coevolution. Ph.D. thesis (1997)Google Scholar
  37. 37.
    Potter, M.A., De Jong, K.: A cooperative coevolutionary approach to function optimization. In: Davidor, Y., Männer, R., Schwefel, H.-P. (eds.) PPSN 1994. LNCS, vol. 866, pp. 249–257. Springer, Heidelberg (1994)CrossRefGoogle Scholar
  38. 38.
    Potter, M.A., De Jong, K.A.: The coevolution of antibodies for concept learning. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 530–539. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  39. 39.
    Potter, M.A., Jong, K.A.D.: Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation 8(1), 1–29 (2000)CrossRefGoogle Scholar
  40. 40.
    Potter, M.A., Jong, K.A.D., Grefenstette, J.J.: A coevolutionary approach to learning sequential decision rules. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 366–372. Morgan Kaufmann Publishers Inc., San Francisco (1995)Google Scholar
  41. 41.
    Potter, M.A., Meeden, L., Schultz, A.C.: Heterogeneity in the coevolved behaviors of mobile robots: The emergence of specialists. In: IJCAI, pp. 1337–1343 (2001)Google Scholar
  42. 42.
    Roli, A.: Metaheuristics and structure in satisfiability problems. Tech. Rep. DEIS-LIA-03-005, University of Bologna (Italy), phD. Thesis - LIA Series no. 66 (May 2003)Google Scholar
  43. 43.
    Seredynski, F.: Competitive coevolutionary multi-agent systems: the application to mapping and scheduling problems. J. Parallel Distrib. Comput. 47(1), 39–57 (1997)MathSciNetCrossRefGoogle Scholar
  44. 44.
    Seredynski, F., Koronacki, J., Janikow, C.Z.: Distributed scheduling with decomposed optimization criterion: Genetic programming approach. In: Proceedings of the 11 IPPS/SPDP 1999 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, pp. 192–200. Springer, London (1999)Google Scholar
  45. 45.
    Seredynski, F., Zomaya, A.Y., Bouvry, P.: Function optimization with coevolutionary algorithms. In: Proc. of the International Intelligent Information Processing and Web Mining Conference. Springer, Poland (2003)Google Scholar
  46. 46.
    Son, Y.S., Baldick, R.: Hybrid coevolutionary programming for nash equilibrium search in games with local optima. IEEE Trans. Evolutionary Computation 8(4), 305–315 (2004)CrossRefGoogle Scholar
  47. 47.
    Taillard, E.D., Gambardella, L.M., Gendreau, M., Potvin, J.Y.: Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research 135(1), 1–16 (2001)MathSciNetCrossRefzbMATHGoogle Scholar
  48. 48.
    Talbi, E.G., Bachelet, V.: Cosearch: A parallel co-evolutionary metaheuristic. In: Blum, C., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics, pp. 127–140 (2004)Google Scholar
  49. 49.
    Watts, D.J.: Small Worlds – The Dynamics of Networks between Order and Randomness. Princeton University Press, Princeton (1999)zbMATHGoogle Scholar
  50. 50.
    Wooldridge, M.J., Jennings, N.R.: Agent theories, architectures, and languages: A survey. In: Wooldridge, M.J., Jennings, N.R. (eds.) ECAI 1994 and ATAL 1994. LNCS, vol. 890, pp. 1–22. Springer, Heidelberg (1995)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2010

Authors and Affiliations

  • Grégoire Danoy
    • 1
  • Pascal Bouvry
    • 1
  • Olivier Boissier
    • 2
  1. 1.FSTC/CSC/ILIASUniversity of LuxembourgLuxembourg
  2. 2.SMA/G2I/ENSM.SESaint-EtienneFrance

Personalised recommendations