Memory Optimized Pheromone Structures for Max-Min Ant System

Marek Běhálek, Martin Šurkovský, Ondřej Meca, Stanislav Böhm

Abstract


Ant Colony Optimization is a meta-heuristic for solving hard combinatorial optimization problems. It is a constructive population based approach inspired by the social behavior of ants. In our research, we are focused on the parallel/distributed computing on massively parallel systems. More precisely, we want to adjust Max-Min Ant System (one of Ant Colony Optimization algorithms) for these systems. Traditionally, a matrix is used to store the pheromone information. If we want to solve large instances, this is a very memory consuming solution. In this paper, we propose a different approach. We do not use the matrix to store the pheromone information. Instead, ant trails that are normally incorporated into this matrix are stored during the computation and just some parts and only in time when they are really needed are assembled. Proposed solution was implemented in C++. The implemented solution was tested on large symmetric instances of Traveling Salesman Problem. In these experiments, we were able to compute results with a comparable quality and even faster than with the traditional approach while using only a portion of the original memory.

Keywords


Max-Min Ant System; memory optimized pheromone structures; distributed memory systems; C++

Full Text:

PDF

References


AARTS E., LENSTRA J. Local Search in Combinatorial Optimization. New Jersey: Princeton University Press, 2003.

ALBA E., LUQUE G., NESMACHNOW S. Parallel metaheuristics: recent advances and new trends. International Transactions in Operational Research. 2013, 20(1), pp. 1–48, doi: 10.1111/j.1475-3995.2012.00862.x.

BÖHM S., BĚHÁLEK M., MECA O., ŠURKOVSKÝ M. Kaira: Development environment for MPI applications. In: Proceedings of the 35th International Conference on Application and Theory of Petri Nets and Concurrency, Tunis, Tunisia. Springer International Publishing, 2014, pp. 385–394, doi: 10.1007/978-3-319-07734-5 22.

BÖHM S., BĚHÁLEK M., MECA O., ŠURKOVSKÝ M. Kaira 1.2 [software]. 2014-06-21 [accessed 2014-10-07]. Available from: http://verif.cs.vsb.cz/kaira.

CECILIA J.M., GARCÍA J.M., NISBET A., AMOS M., UJALD ÓN M. Enhancing data parallelism for ant colony optimization on GPUs. Journal of Parallel and Distributed Computing. 2013, 73(1), pp. 42–51, doi: 10.1016/j.jpdc.2012.01.002.

DORIGO M., GAMBARDELLA L. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. 1997, 1(1), pp. 53–66, doi: 10.1109/4235.585892.

DORIGO M., STÜTZLE T. Ant Colony Optimization. Bradford Company, MA: MIT Press, USA, 2004.

GUNTSCH M., MIDDEMDORF M. A population based approach for ACO. In: Proceedings of the Applications of Evolutionary Computing on EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN, Kinsale, Ireland. Berlin-Heidelberg: Springer, 2002, pp. 72–81, doi: 10.1007/3-540-46004-7 8.

GUNTSCH M., MIDDEMDORF M. Applying population based ACO to dynamic optimization problems. In: Proceedings of the 3rd International Workshop Ant Algorithms (ANTS 2002), Brussels, Belgium. Berlin-Heidelberg: Springer, 2002, pp. 111–122, doi: 10.1007/3-540-45724-0 10.

IT4Inovations. Anselm Cluster Documentation. In: IT4Inovations#Docs [online]. IT4Inovations, Ostrava [viewed 2014-10-07]. Available from: https://docs.it4i.cz/anselm-cluster-documentation/compute-node.

REINELT G. Symmetric traveling salesman problem. In TSPLIB [online]. Universität Heidelberg, Germany [viewed 2014-10-07]. Available from: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.

STÜTZLE T. ACOTSP 1.03 [software]. 2004-03-01 [accessed 2014-10-07]. Available from: http://www.aco-metaheuristic.org/aco-code/public-software.htm.

STÜTZLE T., HOOS H. Max–min ant system. Future Generation Computer Systems. 2000, 16(8), pp. 889–914, doi: 10.1016/S0167-739X(00)00043-1.




DOI: http://dx.doi.org/10.14311/NNW.2015.25.008

Refbacks

  • There are currently no refbacks.


Should you encounter an error (non-functional link, missing or misleading information, application crash), please let us know at nnw.ojs@fd.cvut.cz.
Please, do not use the above address for non-OJS-related queries (manuscript status, etc.).
For your convenience we maintain a list of frequently asked questions here. General queries to items not covered by this FAQ shall be directed to the journal editoral office at nnw@fd.cvut.cz.