Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Adapting Distributed Evolutionary Algorithms to Heterogeneous Hardware

  • Chapter
  • First Online:
Transactions on Computational Collective Intelligence XIX

Part of the book series: Lecture Notes in Computer Science ((TCCI,volume 9380))

Abstract

Distributed computing environments are nowadays composed of many heterogeneous computers able to work cooperatively. Despite this, the most of the work in parallel metaheuristics assumes a homogeneous hardware as the underlying platform. In this work we provide a methodology that enables a distributed genetic algorithm to be customized for higher efficiency on any available hardware resources with different computing power, all of them collaborating to solve the same problem. We analyze the impact of heterogeneity in the resulting performance of a parallel metaheuristic and also its efficiency in time. Our conclusion is that the solution quality is comparable to that achieved by using a theoretically faster homogeneous platform, the traditional environment to execute this kind of algorithms, but an interesting finding is that those solutions are found with a lower numerical effort and even in lower running times in some cases.

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

Access this chapter

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

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://www.roylongbottom.org.uk/.

  2. 2.

    https://code.google.com/p/pyeq2/.

References

  1. Alba, E.: Parallel evolutionary algorithms can achieve super-linear performance. Inf. Process. Lett. 82(1), 7–13 (2002). Elsevier

    Article  MathSciNet  MATH  Google Scholar 

  2. Alba, E.: Parallel Metaheuristics: A New Class of Algorithms. Wiley, New Jersey (2005)

    Book  MATH  Google Scholar 

  3. Alba, E., Nebro, A.J., Troya, J.M.: Heterogeneous computing and parallel genetic algorithms. J. Parallel Distrib. Comput. 62, 1362–1385 (2002)

    Article  MATH  Google Scholar 

  4. 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 

  5. Domínguez, J., Alba, E.: A methodology for comparing the execution time of metaheuristics running on different hardware. In: Hao, J.-K., Middendorf, M. (eds.) EvoCOP 2012. LNCS, vol. 7245, pp. 1–12. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  6. Baugh, J., Kumar, S.: Asynchronous genetic algorithms for heterogeneous networks using coarse-grained dataflow. In: Cantú-Paz, E., et al. (eds.) GECCO 2003. LNCS, vol. 2723, pp. 730–741. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  7. Bazterra, V.E., Cuma, M., Ferraro, M.B., Facelli, J.C.: A general framework to understand parallel performance in heterogeneous clusters: analysis of a new adaptive parallel genetic algorithm. J. Parallel Distrib. Comput. 65(1), 48–57 (2005)

    Article  MATH  Google Scholar 

  8. Branke, J., Kamper, A., Schmeck, H.: Distribution of evolutionary algorithms in heterogeneous networks. In: Deb, K., Tari, Z. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 923–934. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  9. Chong, F.: Java based distributed genetic programming on the internet. Technical report, School of Computer Science, University of Birmingham (1999)

    Google Scholar 

  10. Curnow, H.J., Wichmann, B.A.: A synthetic benchmark. Comput. J. 19(1), 43–49 (1976)

    Article  Google Scholar 

  11. Dominguez, J., Alba, E.: Ethane: A heterogeneous parallel search algorithm for heterogeneous platforms. In: DECIE 2011 (2011)

    Google Scholar 

  12. Dominguez, J., Alba, E.: Dealing with hardware heterogeneity: a new parallel search model. Nat. Comput. 12(2), 179–193 (2013)

    Article  MathSciNet  Google Scholar 

  13. Dongarra, J.: Performance of various computers using standard linear equations software in a fortran environment. Simulation 49(2), 51–62 (1987)

    Article  Google Scholar 

  14. Alba, E., et al.: 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)

    Chapter  Google Scholar 

  15. García-Arenas, M., Merelo, J., Castillo, P., Laredo, J., Romero, G., Mora, A.: Using free cloud storage services for distributed evolutionary algorithms. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO 2011, pp. 1603–1610. ACM, New York (2011)

    Google Scholar 

  16. Garey, M.R., Johnson, D.S.: COmputers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    MATH  Google Scholar 

  17. Gong, Y., Nakamura, M., Tamaki, S.: Parallel genetic algorithms on line topology of heterogeneous computing resources. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, GECCO 2005, pp. 1447–1454 (2005)

    Google Scholar 

  18. Lim, D., Ong, Y.-S., Jin, Y., Sendhoff, B., Lee, B.-S.: Efficient hierarchical parallel genetic algorithms using grid computing. Future Gener. Comput. Syst. 23(4), 658–670 (2007)

    Article  Google Scholar 

  19. Liu, P., Lau, F., Lewis, M.J., Wang, C.: A new asynchronous parallel evolutionary algorithm for function optimization. In: Merelo Guervós, J.J., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 401–410. Springer, Heidelberg (2002)

    Google Scholar 

  20. Luque, G., Alba, E. (eds.): Parallel Genetic Algorithms: Theory and Real World Applications. SCI, vol. 367. Springer, Heidelberg (2011)

    MATH  Google Scholar 

  21. McMahon, F.H.: The Livermore Fortran Kernels: A Computer Test of the Numerical Performance Range. Lawrence Livermore National Laboratory (1986)

    Google Scholar 

  22. Meri, K., Arenas, M., Mora, A., Merelo, J., Castillo, P., Garca-Snchez, P., Laredo, J.: Cloud-based evolutionary algorithms: An algorithmic study. Natural Comput. 12(2), 135–147 (2013)

    Article  MathSciNet  Google Scholar 

  23. Mostaghim, S., Branke, J., Lewis, A., Schmeck, H.: Parallel multi-objective optimization using master-slave model on heterogeneous resources. In: IEEE Congress on Evolutionary Computation, CEC 2008. (IEEE World Congress on Computational Intelligence), pp. 1981–1987 (2008)

    Google Scholar 

  24. Pisinger, D.: A minimal algorithm for the 0–1 knapsack problem. Oper. Res. 45, 758–767 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  25. Pisinger, D.: Core problems in knapsack algorithms. Oper. Res. 47, 570–575 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  26. Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32, 2271–2282 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  28. Weicker, R.P.: Dhrystone: a synthetic systems programming benchmark. Commun. ACM 27(10), 1013–1030 (1984)

    Article  Google Scholar 

Download references

Acknowledgments

We acknowledge the UNLPam, the ANPCYT, CONICET and PICTO-UNLPam-0278 in Argentina from which Dr. Salto receives regular support. The work of Prof. Alba has been partially funded by the University of Málaga UMA/FEDER FC14-TIC36, programa de fortalecimiento de las capacidades de I+D+I en las universidades 2014–2015, de la Consejería y Economía, Innovación, Ciencia y Empleo, with European FEDER, and also by the UMA Project 8.06/5.47.4142 with the VSB-Technical University of Ostrava (CR). Finally, we acknowledge the funding by the Spanish MINECO project TIN2014-57341-R (http://moveon.lcc.uma.es).

Author information

Authors and Affiliations

  1. Universidad Nacional de La Pampa - CONICET, General Pico, Argentina

    Carolina Salto

  2. 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. Enrique Alba
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carolina Salto .

Editor information

Editors and Affiliations

  1. Department of Information Systems, Wrocław University of Technology, Wrocław, Poland

    Ngoc Thanh Nguyen

  2. Swinburne University of Technology, Hawthorn, Victoria, Australia

    Ryszard Kowalczyk

  3. Universitat Politècnica de Catalunya, Barcelona, Spain

    Fatos Xhafa

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Salto, C., Alba, E. (2015). Adapting Distributed Evolutionary Algorithms to Heterogeneous Hardware. In: Nguyen, N., Kowalczyk, R., Xhafa, F. (eds) Transactions on Computational Collective Intelligence XIX . Lecture Notes in Computer Science(), vol 9380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49017-4_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-49017-4_7

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-49016-7

  • Online ISBN: 978-3-662-49017-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation