[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Comparative evaluation of platforms for parallel Ant Colony Optimization

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

The rapidly growing field of nature-inspired computing concerns the development and application of algorithms and methods based on biological or physical principles. This approach is particularly compelling for practitioners in high-performance computing, as natural algorithms are often inherently parallel in nature (for example, they may be based on a “swarm”-like model that uses a population of agents to optimize a function). Coupled with rising interest in nature-based algorithms is the growth in heterogenous computing; systems that use more than one kind of processor. We are therefore interested in the performance characteristics of nature-inspired algorithms on a number of different platforms. To this end, we present a new OpenCL-based implementation of the Ant Colony Optimization algorithm, and use it as the basis of extensive experimental tests. We benchmark the algorithm against existing implementations, on a wide variety of hardware platforms, and offer extensive analysis. This work provides rigorous foundations for future investigations of Ant Colony Optimization on high-performance platforms.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. Full technical details at http://docs.nvidia.com/cuda/index.html.

  2. See https://bitbucket.org/ivarun/ranluxcl/.

References

  1. Alba E, Luque G, Nesmachnow S (2013) Parallel metaheuristics: recent advances and new trends. Int Trans Oper Res 20(1):1–48. doi:10.1111/j.1475-3995.2012.00862.x

    Article  MATH  Google Scholar 

  2. Brodtkorb AR, Dyken C, Hagen TR, Hjelmervik JM, Storaasli OO (2010) State-of-the-art in heterogeneous computing. Sci Progr 18(1):1–33

    Google Scholar 

  3. Cecilia JM, Garcia JM, Nisbet A, Amos M, Ujaldón M (2013) Enhancing data parallelism for ant colony optimization on GPUs. J Parallel Distrib Comput 73(1):42–51

    Article  Google Scholar 

  4. Cecilia JM, Garcia JM, Ujaldon M, Nisbet A, Amos M (2011) Parallelization strategies for ant colony optimisation on GPUs. In: Proceedings of the 2011 IEEE international symposium on parallel and distributed processing. IEEE, pp 339–346

  5. Chang RSS, Chang JSS, Lin PSS (2009) An ant algorithm for balanced job scheduling in grids. Future Gener Comput Syst 25(1):20–27. doi:10.1016/j.future.2008.06.004

    Article  Google Scholar 

  6. Chen Y, Miao D, Wang R (2010) A rough set approach to feature selection based on ant colony optimization. Pattern Recognit Lett 31(3):226–233. doi:10.1016/j.patrec.2009.10.013

    Article  Google Scholar 

  7. Delévacq A, Delisle P, Gravel M, Krajecki M (2013) Parallel ant colony optimization on graphics processing units. J Parallel Distrib Comput 73(1):52–61. doi:10.1016/j.jpdc.2012.01.003

    Article  Google Scholar 

  8. Dorigo M, Birattari M, Stutzle T (2006) Ant colony optimization. Comput Intell Mag IEEE 1(4):28–39

    Article  Google Scholar 

  9. Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Future Gener Comput Syst 16(8):851–871

    Article  Google Scholar 

  10. Dorigo M, Di Caro G (1999) Ant colony optimization: a new meta-heuristic. In: Proceedings of the 1999 congress on evolutionary computation (CEC’99). IEEE Press, pp 1470–1477

  11. Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern B 26(1):29–41

    Article  Google Scholar 

  12. Dorigo M, Stutzle T (2004) Ant Colony Optimization. Bradford Company

  13. Dorigo M, Stützle T (2010) Ant colony optimization: overview and recent advances. In: Handbook of metaheuristics. Springer, Berlin, pp 227–263

  14. Flannery BP, Press WH, Teukolsky SA, Vetterling W (1992) Numerical recipes in c. Press Syndicate of the University of Cambridge, New York

    MATH  Google Scholar 

  15. Garcia MP, Montiel O, Castillo O, Sepúlveda R, Melin P (2009) Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation. Appl Soft Comput 9(3):1102–1110. doi:10.1016/j.asoc.2009.02.014

    Article  Google Scholar 

  16. Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Professional, Reading

  17. He B, Govindaraju NK, Luo Q, Smith B (2007) Efficient gather and scatter operations on graphics processors. In: Proceedings of the 2007 ACM/IEEE conference on supercomputing. ACM, New York, pp 46–57

  18. Johnson DS, McGeoch LA (1997) The traveling salesman problem: a case study in local optimization. In: Lenstra J, Aarts E (eds) Local search in combinatorial optimization. Wiley, New York, pp 215–310

  19. Ke BR, Chen MC, Lin CL (2009) Block-layout design using max-min ant system for saving energy on mass rapid transit systems. IEEE Trans Intell Transp Syst 10(2):226–235. doi:10.1109/TITS.2009.2018324

    Article  Google Scholar 

  20. Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, vol 4. IEEE, pp 1942–1948

  21. Komarudin Wong KY (2010) Applying ant system for solving unequal area facility layout problems. Eur J Oper Res 202(3):730–746. doi:10.1016/j.ejor.2009.06.016

    Article  MATH  Google Scholar 

  22. Lee VW, Kim C, Chhugani J, Deisher M, Kim D, Nguyen AD, Satish N, Smelyanskiy M, Chennupaty S, Hammarlund P (2010) Debunking the 100x gpu vs. cpu myth: an evaluation of throughput computing on cpu and gpu. In: ACM international symposium on computer architecture. ACM, pp 451–460

  23. Manfrin M, Birattari M, Stützle T, Dorigo M (2006) Parallel ant colony optimization for the traveling salesman problem. In: Ant colony optimization and swarm intelligence. Springer, Berlin, pp 224–234

  24. Nickolls J, Buck I, Garland M, Skadron K (2008) Scalable parallel programming with cuda. Queue 6(2):40–53

    Article  Google Scholar 

  25. Nvidia (2011) CUDA Toolkit 4.0 CURAND Guide. http://developer.download.nvidia.com/compute/DevZone/docs/html/CUDALibraries/doc/CURAND_Library.pdf

  26. Pedemonte M, Nesmachnow S, Cancela H (2011) A survey on parallel ant colony optimization. Appl Soft Comput 11(8):5181–5197. doi:10.1016/j.asoc.2011.05.042

    Article  Google Scholar 

  27. Reinelt G (1991) TSPLIB—a traveling salesman problem library. ORSA J Comput 3(4):376–384. Library available at http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

    Google Scholar 

  28. Rozenberg G, Bäck T, Kok JN (2011) Handbook of natural computing. Springer, Berlin

  29. Stone JE, Gohara D, Shi G (2010) OpenCL: a parallel programming standard for heterogeneous computing systems. Comput Sci Eng 12(3):66–72. doi:10.1109/MCSE.2010.69

    Article  Google Scholar 

  30. Stützle T (1998) Parallelization strategies for ant colony optimization. In: Parallel Problem Solving from Nature (PPSN V). Springer, Berlin, pp 722–731

  31. Stutzle T, Hoos HH (2000) MAX-MIN ant system. Future Gener Comput Syst 16(8):889–914

    Article  Google Scholar 

  32. Yu B, Yang ZZ, Yao B (2009) An improved ant colony optimization for vehicle routing problem. Eur J Oper Res 196(1):171–176. doi:10.1016/j.ejor.2008.02.028

    Article  MATH  Google Scholar 

  33. Zhu W, Curry J (2009) Parallel ant colony for nonlinear function optimization with graphics hardware acceleration. In: IEEE international conference on systems, man and cybernetics, 2009, SMC 2009. IEEE, pp 1803–1808

Download references

Acknowledgments

This work is jointly supported by the Fundación Séneca (Agencia Regional de Ciencia y Tecnología, Región de Murcia) under grant 15290/PI/2010, by the Spanish MEC and European Commission FEDER under grant TIN2012-31345, by the UCAM under grant PMAFI/26/12, by the Junta de Andalucía under Project of Excellence P12-TIC-1741 and by the supercomputing infrastructure of the NLHPC (ECM-02). We also thank NVIDIA for hardware donation under CUDA Teaching Center 2011-14, CUDA Research Center 2012-14 and CUDA Fellow 2012-14 Awards.

Author information

Authors and Affiliations

  1. National Laboratory for High Performance Computing, University of Chile, Santiago, Chile

    Ginés D. Guerrero

  2. Computer Science Department, Universidad Católica San Antonio de Murcia, Murcia, Spain

    José M. Cecilia & Antonio Llanes

  3. Computer Engineering Department, University of Murcia, Murcia, Spain

    José M. García

  4. School of Computing, Mathematics and Digital Technology, Manchester Metropolitan University, Manchester, UK

    Martyn Amos

  5. Computer Architecture Department, University of Malaga, Malaga, Spain

    Manuel Ujaldón

Authors
  1. Ginés D. Guerrero
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José M. Cecilia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antonio Llanes
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. José M. García
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Martyn Amos
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Manuel Ujaldón
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to José M. Cecilia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Guerrero, G.D., Cecilia, J.M., Llanes, A. et al. Comparative evaluation of platforms for parallel Ant Colony Optimization. J Supercomput 69, 318–329 (2014). https://doi.org/10.1007/s11227-014-1154-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-014-1154-5

Keywords

Search

Navigation