Ant Colony Optimization with Re-Initialization

Matej Ciba; Ivan Sekaj

doi:doi:10.11648/j.acis.20130103.14

| Peer-Reviewed

Ant Colony Optimization with Re-Initialization

Matej Ciba, Ivan Sekaj

Published in Automation, Control and Intelligent Systems (Volume 1, Issue 3)

Received: 19 June 2013 Published: 30 June 2013

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Matej Ciba

Institute of Control and Industrial Informatics, Bratislava, Slovakia
Ivan Sekaj

Institute of Control and Industrial Informatics, Bratislava, Slovakia

Download PDF

Sections

Plain Text BibTeX RIS

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