| Peer-Reviewed

Ant Colony Optimization with Re-Initialization

Received: 19 June 2013     Published: 30 June 2013
Views:       Downloads:
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.

Published in Automation, Control and Intelligent Systems (Volume 1, Issue 3)
DOI 10.11648/j.acis.20130103.14
Page(s) 59-63
Creative Commons

This is an Open Access article, 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 or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2013. Published by Science Publishing Group

Keywords

Ant Colony Optimization, Re-Initialization, Pheromone Saturation, Minimal Path Search

References
[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.
Cite This Article
  • APA Style

    Matej Ciba, Ivan Sekaj. (2013). Ant Colony Optimization with Re-Initialization. Automation, Control and Intelligent Systems, 1(3), 59-63. https://doi.org/10.11648/j.acis.20130103.14

    Copy | Download

    ACS Style

    Matej Ciba; Ivan Sekaj. Ant Colony Optimization with Re-Initialization. Autom. Control Intell. Syst. 2013, 1(3), 59-63. doi: 10.11648/j.acis.20130103.14

    Copy | Download

    AMA Style

    Matej Ciba, Ivan Sekaj. Ant Colony Optimization with Re-Initialization. Autom Control Intell Syst. 2013;1(3):59-63. doi: 10.11648/j.acis.20130103.14

    Copy | Download

  • @article{10.11648/j.acis.20130103.14,
      author = {Matej Ciba and Ivan Sekaj},
      title = {Ant Colony Optimization with Re-Initialization},
      journal = {Automation, Control and Intelligent Systems},
      volume = {1},
      number = {3},
      pages = {59-63},
      doi = {10.11648/j.acis.20130103.14},
      url = {https://doi.org/10.11648/j.acis.20130103.14},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acis.20130103.14},
      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.},
     year = {2013}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Ant Colony Optimization with Re-Initialization
    AU  - Matej Ciba
    AU  - Ivan Sekaj
    Y1  - 2013/06/30
    PY  - 2013
    N1  - https://doi.org/10.11648/j.acis.20130103.14
    DO  - 10.11648/j.acis.20130103.14
    T2  - Automation, Control and Intelligent Systems
    JF  - Automation, Control and Intelligent Systems
    JO  - Automation, Control and Intelligent Systems
    SP  - 59
    EP  - 63
    PB  - Science Publishing Group
    SN  - 2328-5591
    UR  - https://doi.org/10.11648/j.acis.20130103.14
    AB  - 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.
    VL  - 1
    IS  - 3
    ER  - 

    Copy | Download

Author Information
  • Institute of Control and Industrial Informatics, Bratislava, Slovakia

  • Institute of Control and Industrial Informatics, Bratislava, Slovakia

  • Sections