Abstract

This study proposes machine learning strategies to control the parameter adaptation in ant colony optimization algorithm, the prominent swarm intelligence metaheuristic. The sensitivity to parameters’ selection is one of the main limitations within the swarm intelligence algorithms when solving combinatorial problems. These parameters are often tuned manually by algorithm experts to a set that seems to work well for the problem under study, a standard set from the literature or using off-line parameter tuning procedures. In the present study, the parameter search process is integrated within the running of the ant colony optimization without incurring an undue computational overhead. The proposed strategies were based on a novel nature-inspired idea. The results for the travelling salesman and quadratic assignment problems revealed that the use of the augmented strategies generally performs well against other parameter adaptation methods.

Keywords:

Ant colony optimization, combinatorial problems, parameter control, swarm intelligence metaheuristics,

References

1. Barbero, F., S. Bonelli, J.A. Thomas, E. Balletto and K. Schönrogge, 2009. Acoustical mimicry in a predatory social parasite of ants. J. Exp. Biol., 212(Pt 24): 4084-4090.
   CrossRef    PMid:19946088    
2. Barbero, F., D. Patricelli, M. Witek, E. Balletto, L.P. Casacci, M. Sala and S. Bonelli, 2012. Myrmica ants and their butterfly parasites with special focus on the acoustic communication. Psyche, 2012(2012): 11, Article Id: 725237.
   
3. Broderick, C., R. Soto, E. Monfroy and F. Johnson, 2014. Self-adaptive systems: Facilitating the use of combinatorial problem solvers. Proceeding of the Part I, International Conference, HCI International 2014. Heraklion, Crete, Greece, June 22-27, 434: 503-508.
   
4. Collings, J. and E. Kim, 2014. A distributed and decentralized approach for ant colony optimization with fuzzy parameter adaptation in traveling salesman problem. Proceeding of the IEEE Symposium on Swarm Intelligence (SIS, 2014). Florida, U.S.A., pp: 1-9.
   CrossRef    
5. Dorigo, M. and T. Stützle, 2010. Ant Colony Optimization: Overview and Recent Advances. In: Gendreau, M. and J. Potvin (Eds.), Handbook of Metaheuristics. Springer US, New York, USA, pp: 227-263.
   CrossRef    
6. Förster, M., B. Bickel, B. Hardung and G. Kókai, 2007. Self-adaptive ant colony optimisation applied to function allocation in vehicle networks. Proceeding of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO, 2007). ACM Press, London, UK, pp: 1991-1998.
   CrossRef    
7. Khichane, M., P. Albert and C. Solnon, 2009. An ACO-based reactive framework for ant colony optimization: First experiments on constraint satisfaction problems. Learn. Intell. Optimiz., 5851: 119-133.
   CrossRef    
8. Liu, X., C. Yang and X. Liu, 2011a. Optimization of vehicle routing problem based on max-min ant system with parameter adaptation. Proceeding of the 7th IEEE International Conference on Computational Intelligence and Security. Hainan, China.
   CrossRef    
9. Liu, Y., G. Ang, H. Chen, Z. Zhao, X. Zhu and Z. Liu, 2011b. An adaptive fuzzy ant colony optimization for feature selection. J. Comput. Inform. Syst., 4(7): 1206-1213.
   
10. Lopez-Ibanez, M. and T. Stützle, 2014. Automatically improving the anytime behaviour of optimisation algorithms. Eur. J. Oper. Res., 235(3): 569-582.
    CrossRef    
11. Martens, D., M. De Backer, R. Haesen, S. Member, J. Vanthienen and M. Snoeck, 2007. Classification with ant colony optimization. IEEE T. Evolut. Comput., 11(5): 651-665.
    CrossRef    
12. Melo, L., F. Pereira and E. Costa, 2010. MC-ANT: A Multi-Colony ant algorithm. In: Collet, P. et al. (Eds.), EA, 2009. LNCS 5975, Springer-Verlag, Berlin, Heidelberg, pp: 25-36.
    CrossRef    
13. Neyoy, H., O. Castillo and J. Soria, 2013. Dynamic fuzzy logic parameter tuning for ACO and its application in TSP problems. In: Castillo, O., P. Melin and J. Kacprzyk (Eds.), Studies in Computational Intelligence (SCI): Recent Advances on Hybrid Intelligent Systems. Springer, Heidelberg, Germany, 451: 259-271.
    CrossRef    
14. Olivas, F., F. Valdez and O. Castillo, 2014. A fuzzy system for parameter adaptation in ant colony optimization. Proceeding of the IEEE Symposium on Swarm Intelligence. Orlando, FL, pp: 1-6.
    CrossRef    
15. Pellegrini, P., T. Stützle and M. Birattari, 2012. A critical analysis of parameter adaptation in ant colony optimization. Swarm Intell., 6(1): 23-48.
    CrossRef    
16. Randall, M., 2004. Near parameter free ant colony optimisation. In: Dorigo, M. et al. (Eds.), ANTS 20004. LNCS 3172, Springer-Verlag, Berlin, Heidelberg, pp: 374-381.
    CrossRef    
17. Sagban, R., K.R. Ku-Mahamud and M. Shahbani, 2014. Reactive memory model for ant colony optimization and its application to TSP. In Proceedings of the 4th International Conference on Control System, Computing and Engineering (ICCSCE, 2014). IEEE, Penang, Malaysia, pp: 310-315.
    CrossRef    
18. Sagban, R., K.R. Ku-Mahamud and M.S.A. Bakar, 2015. ACOustic?: A nature-inspired exploration indicator for ant colony optimization. Sci. World J., 2015(2015): 11, Article ID 392345.
    
19. Solnon, C., 2010. Ant Colony Optimization and Constraint Programming. Weley and Sons Ltd., U.S.A.
    PMid:20403487    
20. Stützle, T. and H.H. Hoos, 2000. MAX–MIN ant system. Future Gener. Comp. Sy., 16(8): 889-914.
    CrossRef    
21. Stützle, T., M. Maur and M. López-Ibáñez, 2010. Pre-scheduled and adaptive parameter variation in MAX-MIN ant system. Proceeding of the IEEE Congress on Evolutionary Computation (CEC, 2010), pp: 1-8.
    
22. Stützle, T., L. Manuel, P. Pellegrini, M. Maur, M.M. De Oca, M. Birattari and M. Dorigo, 2012. Parameter adaptation in ant colony optimization. In: Hamadi, Y. et al. (Eds.), Autonomous Search. Springer-Verlag, Berlin, Heidelberg, pp: 191-215.
    
23. Wang, Y., 2013. Adaptive ant colony algorithm for the VRP solution of logistics distribution. Res. J. Appl. Sci. Eng. Technol., 6(5): 807-811.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.