On the Development of a Hybridized Ant Colony Optimization (HACO) Algorithm
- 1 Department of Mathematics, Ekiti State University, Ado Ekiti, Nigeria
- 2 Department of Mathematics, Ekiti State University, Ado Ekiti, Nigeria
- 3 College of Education, Ikere Ekiti, Nigeria
Abstract
This paper proposes a Hybridized Ant Colony Optimization (HACO) algorithm. It integrates the advantages of Ant System (AS) and Ant Colony System (ACS) of solving optimization problems. The main focus and core of the HACO algorithm are based on annexing the strengths of the AS, ACO and the Max-Min Ant System (MMAS) previously proposed by various researchers at one time or the order. In this paper, the HACO algorithm for solving optimization problems employs new Transition Probability relations with a Jump transition probability relation which indicates the point or path at which the desired optimum value has been met. Also, it brings to play a new pheromone updating rule and introduces the pheromone evaporation residue that calculates the amount of pheromone left after updating which serves as a guide to the successive ant traversing the path and diverse local search approaches. Regarding the computational efficiency of the HACO algorithm, we observe that the HACO algorithm can find very good solutions in a short time, as the algorithm has been tested on a number of combinatorial optimization problems and results shown to compare favourably with analytical results. This strength can be combined with other metaheuristic approaches in the future work to solve complex combinatorial optimization problems.
- Colorni, A., Dorigo, M. and Maniezzo, V. (1991) Distributed Optimization by Ant Colonies. In: Varela, F.and Bourgine, P., Eds., Proceedings of ECAL91—European Conference on Artificial Life, Elsevier Publishing, Paris, France, 134-142.
- Dorigo, M., Birattari, M. and Stützle, T. (2006) Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. Technical Report, IRIDIA, Institut de Recherches Interdisciplinaires et de Développements en Intelligence Artificielle, Université Libre de Bruxelles.
- Dorigo, M. and Di Caro, G. (1999) The Ant Colony Optimization Meta-Heuristic. In: Corne, D., Dorigo, M. and Glover, F., Eds., New Ideas in Optimization, McGraw- Hill, London, UK, 11-32.
- Dorigo, M. (1992) Optimization, Learning and Natural Algorithms, Ph.D. Thesis, DEI, Politecnico di Milano, Italy.
- Dorigo, M. and Gambardella, L.M. (1996) A Study of Some Properties of Ant-Q. In: Voigt, H.-M., Ebeling, W., Rechenberg, I. and Schwefel, H.-S., Eds., Proceedings of PPSN IV—Fourth International Conference on Parallel Problem Solving From Nature, Springer-Verlag, Berlin, 656-665. https://doi.org/10.1007/3-540-61723-X_1029
- Chen, C.-H. and Ting, C.-J. (2006) An Improved Ant Colony System Algorithm for the Vehicle Routing Problem. Journal of the Chinese Institute of Industrial Engineers, 23, 115-126. https://doi.org/10.1080/10170660609509001
- Dorigo, M., Maniezzo, V. and Colorni, A. (1996) Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B, 26, 29-41. https://doi.org/10.1109/3477.484436
- Dorigo, M. and Gambardella, L.M. (1997) Ant Colonies for the Traveling Salesman Problem. Biosystems, 43, 73-81. https://doi.org/10.1016/S0303-2647(97)01708-5
- Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System: A Cooperative Learning Approach for the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66. https://doi.org/10.1109/4235.585892
- Russell, S.J. and Norvig, P. (2009) Artificial Intelligence: A Modern Approach. 3rd Edition, Prentice Hall, Bergen, NJ.
- Florence, M. (2013) Optimization Approaches for Vehicle Routing Problems with Black Box Feasibility. A Thesis Submitted to Institute of Information and Communication Technologies, Electronics and Applied Mathematics Louvain School of Engineering, Louvain-La-Neuve, Belgium.