Feedback Searching Bias and Measurement of its Effect on Ant Colony Optimization

Abstract:

One of the obstacles in applying ant colony optimization (ACO) to the combinatorial optimization is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Due to such searching bias, ant colony optimization cannot converge to the optimal solution for some problems. In this paper, we discover and define a new type of searching bias in ACO named feedback bias. We empirically prove the existence of feedback bias and its influence on ACO. We also present the concept of intensity of bias as a measurement of the effect on ACO by such bias. Our experimental results show that it is reasonable and reliable to use the intensity to measure the influence of bias on ACO.

• Periodical: Advanced Engineering Forum (Volumes 6-7)
• Pages: 315-320
• DOI: https://doi.org/10.4028/www.scientific.net/AEF.6-7.315
• Online since: September 2012
• Authors: Bo Lun Chen, Ling Chen
• Keywords: Ant Colony Optimization (ACO), Deceptive Problems, K-Cardinality Tree Problem, Solution Convergence

References

[1] Dorigo M, Stützle T, Ant Colony Optimization, MIT Press, (2004).

[2] Dorigo M, Blum C, Ant colony optimization theory: A survey, Theoretical Computer Science, 344 (2005) 243-278.

DOI: 10.1016/j.tcs.2005.05.020

[3] Blum C, Ant colony optimization: Introduction and recent trends, Physics of Life Reviews, 2 (2005) 353-373.

DOI: 10.1016/j.plrev.2005.10.001

[4] Shtovba S, Ant Algorithms: Theory and Applications, Programming and Computer Software, 31(2005) 167-178.

DOI: 10.1007/s11086-005-0029-1

[5] Agarwal A., Lim M. H., Er M. J., Chew C. Y., ACO for a new TSP in region coverage, Proceedings of Intelligent Robots and Systems 2005, 2-6 Aug. (2005) 1717 – 1722.

DOI: 10.1109/iros.2005.1545460

[6] Blum C, Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling, Computers & Operations Research, 32(2005) 1565-1591.

DOI: 10.1016/j.cor.2003.11.018

[7] Prokopenko M, Peter Wang, Foreman M, Valencia P, Price D, Poulton G, On connectivity of reconfigurable impact networks in ageless aerospace vehicles, Robotics and Autonomous Systems, 53(2005)36-58.

DOI: 10.1016/j.robot.2005.06.003

[8] Kuo R.J., Wang H.S., Hu T. L. , Chou S.H., Application of ant K-means on clustering analysis, Computers & Mathematics with Applications, 50 (2005) 1709-1724.

DOI: 10.1016/j.camwa.2005.05.009

[9] R.J. Kuo, Y.P. Kuo, Kai-Ying Chen, Developing a diagnostic system through integration of fuzzy case-based reasoning and fuzzy ant colony system, Expert Systems with Applications, 28(2005)783-797.

DOI: 10.1016/j.eswa.2004.12.034

[10] Katangur, A.K., Akkaladevi S., Pan, Y., Fraser, M.D., Applying ant colony optimization to routing in optical multistage interconnection networks with limited crosstalk, Proceedings of 18th International Parallel and Distributed Processing Symposium, 2004, pp.26-30.

DOI: 10.1109/ipdps.2004.1303156

[11] Shyong Jian Shyu, B.M.T. Lin , Tsung-Shen Hsiao, Ant colony optimization for the cell assignment problem in PCS networks , Computers & Operations Research, 33(2006)1713-1740.

DOI: 10.1016/j.cor.2004.11.026

[12] Maniezzo V., Carbonaro A., An ANTS heuristic for the frequency assignment problem, Future Generation Computer Systems, 16(2000)927 – 935.

DOI: 10.1016/s0167-739x(00)00046-7

[13] Kalinli A., Karaboga N., Artificial immune algorithm for IIR filter design,  Engineering Applications of Artificial Intelligence, 18(2005)919-929.

DOI: 10.1016/j.engappai.2005.03.009

[14] Talbi E. -G., Roux O., Fonlupt C., Robillard D., Parallel Ant Colonies for the quadratic assignment problem, Future Generation Computer Systems, 17(2001)441-449.

DOI: 10.1016/s0167-739x(99)00124-7

[15] Gambardella L. M., Dorigo M., Ant Colony System hybridized with a new local search for the sequential ordering problem, INFORMS Journal on Computing, 12(2000)237–255.

DOI: 10.1287/ijoc.12.3.237.12636

[16] Lee Z.J., Lee C.Y., Su S. F, An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem, Applied Soft Computing, 2(2002)39-47.

DOI: 10.1016/s1568-4946(02)00027-3

[17] Blum C., Sampels M., Ant colony optimization for FOP shop scheduling: A case study on different pheromone representation, in Proceedings of Congress on Evolutionary Computation 2002, vol. 2, pp.1558-1563.

DOI: 10.1109/cec.2002.1004474

[18] Blum C, Sampels M. When model bias is stronger than selection pressure, In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature(PPSN'02), London, UK , Springer-Verlag, 2002, pp.893-902.

DOI: 10.1007/3-540-45712-7_86

[19] Merkle D, Middendorf M. Modeling the dynamics of ant colony optimization algorithms, Evolutionary Computation, 2002, 10(3) : 235 - 262.

DOI: 10.1162/106365602760234090

[20] Merkle D, Middendorf M. Modeling ACO: composed permutation problems, Proceedings of ANTS2002, Lecture Notes in Computer Science, 2002, 2463: 149-162.

DOI: 10.1007/3-540-45724-0_13

[21] Montgomery J, Randall M, Hendtlass T. Solution bias in ant colony optimization: Lessons for selecting pheromone models, Computers and Operations Research, 2008, 35(9): 2728-2749.

DOI: 10.1016/j.cor.2006.12.014

[22] Montgomery J, Randall M, Hendtlass T. Structure advantages for ant colony optimization inherent in permutation scheduling problems, Proceedings of IEA/AIE , LNAI, 2005, 3533, : 218-228.

DOI: 10.1007/11504894_31