Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

SpringerLink
Log in

Enhancing distributed EAs by a proactive strategy

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

In this work we propose a new distributed evolutionary algorithm that uses a proactive strategy to adapt its migration policy and the mutation rate. The proactive decision is carried out locally in each subpopulation based on the entropy of that subpopulation. In that way, each subpopulation can change their own incoming flow of individuals by asking their neighbors for more frequent or less frequent migrations in order to maintain the genetic diversity at a desired level. Moreover, this proactive strategy is reinforced by adapting the mutation rate while the algorithm is searching for the problem solution. All these strategies avoid the subpopulations to get trapped into local minima. We conduct computational experiments on large instances of the NK landscape problem which have shown that our proactive approach outperforms traditional dEAs, particularly for not highly rugged landscapes, in which it does not only reaches the most accurate solutions, but it does the fastest.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Algorithm 3
Fig. 1
Algorithm 4
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Aguirre, H., Tanaka, K.: A study on the behavior of genetic algorithms on nk-landscapes: effects of selection, drift, mutation, and recombination. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86-A(9), 2270–2279 (2003)

    Google Scholar 

  2. Alba, E., Dorronsoro, B.: Cellular Genetic Algorithms. Operations Research/Computer Science Interfaces Series, vol. 42. Springer, Berlin (2008)

    MATH  Google Scholar 

  3. Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)

    Article  Google Scholar 

  4. Alba, E., Troya, J.M.: A survey of parallel distributed genetic algorithms. Complexity 4(4), 31–52 (1999)

    Article  MathSciNet  Google Scholar 

  5. Alba, E., Troya, J.M.: Analyzing synchronous and asynchronous parallel distributed genetic algorithms. Future Gener. Comput. Syst. 17(4), 451–465 (2001)

    Article  MATH  Google Scholar 

  6. Araujo, L., Merelo, J.J.: Diversity through multiculturality: assessing migrant choice policies in an island model. IEEE Trans. Evol. Comput. 15(4), 456–469 (2011)

    Article  Google Scholar 

  7. Bäck, T.: Self-adaptation in genetic algorithms. In: Proceedings of the First European Conference on Artificial Life, pp. 263–271. MIT Press, Cambridge (1992)

    Google Scholar 

  8. Bäck, T., Fogel, D., Michalewicz, Z.: Handbook of Evolutionary Computation. Oxford University Press, New York (1997)

    Book  MATH  Google Scholar 

  9. DeJong, K.: An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Ann Arbor, MI (1975)

  10. Eiben, A., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Trans. Evol. Comput. 3(2), 124–141 (1999)

    Article  Google Scholar 

  11. Eiben, A.E., Michalewicz, Z., Schoenauer, M., Smith, J.E.: Parameter control in evolutionary algorithms. In: Studies in Computational Intelligence, vol. 54, pp. 19–46. Springer, Berlin (2007)

    Google Scholar 

  12. Alba, E., et al.: MALLBA: A Library of Skeletons for Combinatorial Optimisation. LNCS, vol. 2400, pp. 927–932. Springer, Berlin (2002)

    Google Scholar 

  13. Gong, X., Xie, J.: Migration strategy and mathematical analysis of sub-population size adaptation in parallel genetic algorithm. In: Medical Imaging, Parallel Processing of Images, and Optimization Techniques, vol. 7497, pp. 1–15 (2009)

    Google Scholar 

  14. Greffenstette, J.J.: Optimization of control parameters for genetic algorithms. IEEE Trans. Syst. Man Cybern. 16(1), 122–128 (1986)

    Article  Google Scholar 

  15. Hijaze, M., Corne, D.: Distributed evolutionary algorithm topologies with adaptive migration schemes. In: IEEE Congress on Evolutionary Computation, pp. 608–615 (2011)

    Google Scholar 

  16. Kauffman, S.: The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, London (1993)

    Google Scholar 

  17. Kauffman, S., Levin, S.: Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol. 128(1), 11–45 (1987)

    Article  MathSciNet  Google Scholar 

  18. Kramer, O.: Evolutionary self-adaptation: a survey of operators and strategy parameters. Evol. Intell. 3(2), 51–65 (2010)

    Article  MATH  Google Scholar 

  19. Kwasnicka, H.: An ensemble of cooperative genetic algorithms as an intelligent search tool. Int. J. Comput. Intell. Res. 3(2), 165–176 (2007)

    Article  Google Scholar 

  20. Luque, G., Alba, E.: Parallel Genetic Algorithms: Theory and Real World Applications. Studies in Computational Intelligence, vol. 367. Springer, Berlin (2011)

    Google Scholar 

  21. Michalewicz, M.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd revised edn. Springer, Berlin (1996)

    Book  MATH  Google Scholar 

  22. Ochoa, G., Harvey, I., Buxton, H.: On recombination and optimal mutation rates. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 488–495 (1999)

    Google Scholar 

  23. Osorio, K., Luque, G., Alba, E.: Distributed evolutionary algorithms with adaptive migration period. In: 2011 11th International Conference on Intelligent Systems Design and Applications (ISDA), pp. 259–264 (2011)

    Chapter  Google Scholar 

  24. Salto, C., Luna, F., Alba, E.: Heterogeneity through proactivity: enhancing distributed EAs. In: 1st International Workshop on Soft Computing Techniques in Cluster and Grid Computing Systems (SCCG), Part of the Seventh International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), pp. 279–284 (2012)

    Google Scholar 

  25. Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423 (1948) and 623–656

    Article  MATH  MathSciNet  Google Scholar 

  26. Skolicki, Z., De Jong, K.: The influence of migration sizes and intervals on island models. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation (GECCO’2005), pp. 1295–1302 (2005)

    Chapter  Google Scholar 

  27. Spiessens, P., Manderick, B.: A massively parallel genetic algorithm. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 279–286 (1991)

    Google Scholar 

  28. Srinivasa, K.G., Venugopal, K.R., Patnaik, L.M.: A self-adaptive migration model genetic algorithm for data mining applications. Inf. Sci. 177(20), 4295–4313 (2007)

    Article  MATH  Google Scholar 

  29. Syswerda, G.: Study of reproduction in generational and steady-state genetic algorithms. In: Foundations of Genetic Algorithms, pp. 94–101 (1991)

    Google Scholar 

  30. Tanese, R.: Distributed genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 434–439 (1989)

    Google Scholar 

  31. Tang, J., Lim, M.-H., Ong, Y.-S.: Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput. 11(9), 873–888 (2007)

    Article  Google Scholar 

  32. Wang, R., Ru, Y., Long, Q.: Improved adaptive and multi-group parallel genetic algorithm based on good-point set. J. Softw. 4(4), 348–356 (2009)

    Google Scholar 

Download references

Acknowledgements

We acknowledge the Universidad Nacional de La Pampa, the ANPCYT and CONICET in Argentina from which the first author receive continuous support. The work of Francisco Luna and Enrique Alba has been partially funded by the Spanish Ministry of Science and Innovation and FEDER under contract TIN2011-28194 (the roadME project). Francisco Luna also acknowledges support from TIN2011-28336.

Author information

Authors and Affiliations

  1. Universidad Nacional de La Pampa—CONICET, General Pico, Argentine

    Carolina Salto

  2. Departamento de Informática, Universidad Carlos III de Madrid, Leganés, Madrid, Spain

    Francisco Luna

  3. Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Málaga, Spain

    Enrique Alba

Authors
  1. Carolina Salto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francisco Luna
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Enrique Alba
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carolina Salto.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Salto, C., Luna, F. & Alba, E. Enhancing distributed EAs by a proactive strategy. Cluster Comput 17, 219–229 (2014). https://doi.org/10.1007/s10586-013-0321-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-013-0321-4

Keywords

Search

Navigation