Volume 1, Issue 3, June 2013, Page: 59-63
Ant Colony Optimization with Re-Initialization
Matej Ciba, Institute of Control and Industrial Informatics, Bratislava, Slovakia
Ivan Sekaj, Institute of Control and Industrial Informatics, Bratislava, Slovakia
Received: Jun. 19, 2013;       Published: Jun. 30, 2013
DOI: 10.11648/j.acis.20130103.14      View  2949      Downloads  167
Abstract
This contribution introduces an Ant Colony Optimization (ACO) algorithm with re-initialization mechanism. The whole search process is broken by re-initialization into shorter semi-independent steps called “macro cycles”. The length of macro cycle depends on pheromone accumulation and can be adjusted by a user parameter. It is shown that re-initialization mechanism prevents ACO algorithm from pheromone saturation and consecutive stagnation. This approach avoids overhead caused by algorithm run with excessive pheromone values where further exploration is hardly possible. The solution offers lower CPU cost of the search process and enables automation of heuristic search especially in changing environments like dynamic networks. The efficiency of proposed method is demonstrated on a path minimization problem on 50 node graph.
Keywords
Ant Colony Optimization, Re-Initialization, Pheromone Saturation, Minimal Path Search
To cite this article
Matej Ciba, Ivan Sekaj, Ant Colony Optimization with Re-Initialization, Automation, Control and Intelligent Systems. Vol. 1, No. 3, 2013, pp. 59-63. doi: 10.11648/j.acis.20130103.14
Reference
[1]
P. E. Hart, N. J. Nilsson and B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics SSC4 4(2), 1968, 100–107
[2]
M. Dorigo, V. Maniezzo and A. Colorni, The Ant System: An autocatalytic optimizing process, Technical report 91-016 revised, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1991
[3]
M. Dorigo and L. M. Gambardella, Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1), 53–66,
[4]
Y. Nakamichi and T. Arita, Diversity control in ant colony optimization, In Abbas HA (ed) Proceedings of the Inaugural Workshop on Artificial Life (AL'01), Adelaide, Australia, Dec 11, 2001, 70-78
[5]
R. Kumar M. K. Tiwari and R. Shankar, Scheduling of flexible manufacturing systems: an ant colony optimization approach, proc. Instn. Mech. Engrs Vol. 217 Part B: J. Engineering Manufacture, 2003, 1443–1453
[6]
T. Stützle and H. H. Hoos, Improving the Ant System: A detailed report on the MAX-MIN Ant System. Technical report AIDA-96-12, FG Intellektik, FB Informatik, TU Darmstadt, Germany, 1996
[7]
T. Stützle and H. H. Hoos, MAX-MIN Ant System. Future Generation Computer Systems, 2000, 16(8), 889–914
[8]
M. Ciba, ACO algorithm with macro cycles, Proceedings on 14th Conference of Doctorial Students on Elitech’12, Slovak Technical University of Bratislava, May 2012
[9]
M. Becker and H. Szczerbicka, Parameters influencing the performance of ant algorithms applied to optimization of buffer size in manufacturing, IEMS Vol. 4, No. 2, December 2005, 184–191.
Browse journals by subject