Summary
The chapter discusses the application of Opposition-Based Optimization (OBO) to ant algorithms. Ant Colony Optimization (ACO) is a powerful optimization technique that has been used to solve many complex problems. Despite its successes, ACO is not a perfect algorithm: it can remain trapped in local optima, miss a portion of the solution space or, in some cases, it can be slow to converge. Thus, we were motivated to improve the accuracy and convergence of the current algorithm by extending it with the concept of OBO. In the case of ACO, the application of opposition can be challenging because ACO usually optimizes using a graph representation of problems, where the opposite of solutions and partial components of the solutions are not clearly defined.
The chapter presents two types of opposition-based extensions to the ant algorithm. The first type, called Opposite Pheromone per Node (OPN), involves a modification to the construction phase of the algorithm which affects the decisions of the ants by altering the pheromone values used in the decision. Basically, there is an opposite rate that determines the frequency at which opposite pheromone will be used in the construction step. The second method, Opposite Pheromone Update (OPU), involves an extension to the update phase of the algorithm that performs additional updates to the pheromone content of opposite decisions. The opposition-based approaches were tested using the Travelling Salesman Problem (TSP) and the Grid World Problem (GWP).
Overall, the application of some fundamental opposition concepts led to encouraging results in the TSP and the GWP. OPN led to some accuracy improvements and OPU demonstrated significant speed-ups. However, further work is necessary to fully evaluate the benefits of opposition. Theoretical work involving the application of opposition to graphs is necessary, specifically in establishing the ‘opposite graph’.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Travelling Salesman Problem
- Opposite Edge
- Quadratic Assignment Problem
- Exploration Ability
- Pheromone Matrix
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)
Bullnheimer, B., Hartl, R.F., Strauss, C.: Applying the Ant System to the Vehicle Routing Problem. In: Osman, I.H., Voβ, S., Martello, S., Roucairol, C. (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 109–120. Kluwer Academic Publishers, Dordrecht (1998)
Bullnheimer, B., Hartl, R.F., Strauss, C.: An Improved Ant System Algorithm for the Vehicle Routing Problem. Ann. Oper. Res. 89, 319–328 (1999)
Cordón, O., de Viana, I.F., Herrera, F., Moreno, L.: A New ACO Model Integrating Evolutionary Computation Concepts: The Best-Worst Ant System. In: Proc. of the 2nd Int. Workshop on Ant Algorithms (ANTS 2000), Brussels, Belgium, pp. 22–29 (2000)
Dorigo, M.: Optimization, Learning and Natural Algorithms (in Italian). PhD dissertation, Dipartimento di Elettronica, Politecnico di Milano, Italy (1992)
Dorigo, M., Maniezzo, V., Colorni, A.: The Ant System: Optimization by a Colony of Cooperating Agents. SMC 26, 29–41 (1996)
Dorigo, M., Gambardella, L.M.: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions On Evolutionary Computation 1(1), 53–66 (1997)
Dorigo, M., Stützle, T.: The Ant Colony Optimization Metaheuristic: Algorithm, Applications, and Advances. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 55–82. Kluwer Academic Publishers, Boston (2003)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Gambardella, L.M., Dorigo, M.: Solving Symmetric and Asymmetric TSPs by Ant Colonies. In: Proc. IEEE Int. Conf. on Evolutionary Computation (ICEC 1996), Nagoya, Japan, pp. 622–627 (1996)
Gambardella, L.M., Taillard, E., Agazzi, G.: MACS-VRPTW: A multiple Ant Colony System for Vehicle Routing Problems with Time Windows. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 63–76. McGraw-Hill, New York (1999)
Hollander, M., Wolfe, D.A.: Nonparametric Statistical Methods. Wiley, Chichester (1973)
Iredi, S., Merkle, D., Midderndorf, M.: Bi-Criterion Optimization with Multi Colony Ant Algorithms. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 359–372. Springer, Heidelberg (2001)
Kennedy, J., Eberhart, R.C., Shi, Y.: Swarm Intelligence. Morgan Kaufmann, San Mateo (2001)
Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., Shmoys, D.B.: The Travelling Salesman Problem. Wiley, New York (1985)
Malisia, A.R.: Investigating the Application of Opposition-Based Ideas to Ant Algorithm. MASc. thesis, University of Waterloo, ON, Canada (2007), http://hdl.handle.net/10012/3233
Malisia, A.R., Tizhoosh, H.R.: Applying Opposition-Based Ideas to the Ant Colony System. In: Proc. of IEEE Swarm Intelligence Symposium, Honolulu, HI, April 1-5, pp. 182–189 (2007)
Maniezzo, V., Colorni, A.: The Ant System Applied to the Quadratic Assignment Problem. IEEE Trans. Knowl. Data Eng. 11(5), 769–778 (1999)
Montgomery, J., Randall, M.: Anti-Pheromone as a Tool for Better Exploration of Search Spaces. In: Proc. 3rd Int. Workshop on Ant Algorithms (ANTS 2002), Brussels, Belgium, pp. 100–110 (September 2002)
Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.: Opposition-Based Differential Evolution Algorithms. In: Proc. IEEE Congress on Evolutionary Computation, Vancouver, July 16-21, pp. 7363–7370 (2006)
Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.: A Novel Population Initialization Method for Accelerating Evolutionary Algorithms. Computers and Mathematics with Applications 53(10), 1605–1614 (2007)
Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.: Opposition-Based Differential Evolution (ODE) With Variable Jumping Rate. In: Proc. of IEEE Symposium on Foundations of Computational Intelligence (FOCI 2007), Hawaii, April 1-5, pp. 81–88 (2007)
Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.A.: Opposition-Based Differential Evolution. IEEE Transactions of Evolutionary Computation (in press, 2008)
Randall, M., Montgomery, J.: The Accumulated Experience Ant Colony for the Travelling Salesman Problem. In: Proc. of Inaugural Workshop on Artificial Life, Adelaide, Australia, pp. 79–87 (2001)
Reinelt, G.: TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3, 376–384 (1991)
Schoonderwoerd, R., Holland, O.E., Bruten, J.L., Rothkrantz, L.J.M.: Ant-Based Load Balancing in Telecommunications Networks. Adaptive Behavior 2, 169–207 (1996)
Shokri, M., Tizhoosh, H.R., Kamel, M.S.: Opposition-Based Q(λ) Algorithm. In: Proc. IEEE International Joint Conf. on Neural Networks (IJCNN), Vancouver, July 16-21, pp. 646–653 (2006)
Shokri, M., Tizhoosh, H.R., Kamel, M.S.: Opposition-Based Q(λ) with Non-Markovian Update. In: Proc. IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning (ADPRL 2007), Hawaii, April 1-5, pp. 288–295 (2007)
Song, Y., Irving, M.R.: Optimisation techniques for electrical power systems. II. Heuristic optimisation methods. Power Engineering Journal 15(1), 151–160 (2001)
Stützle, T., Hoos, H.H.: MAX-MIN Ant System. Future Generation Computer Systems 16(8), 889–914 (2000)
Tizhoosh, H.R.: Opposition-Based Learning: A New Scheme for Machine Intelligence. In: Proc. Int. Conf. on Computational Intelligence for Modelling Control and Automation - CIMCA 2005, Vienna, Austria, vol. I, pp. 695–701 (2005)
Tizhoosh, H.R.: Opposition-Based Reinforcement Learning. Journal of Advanced Computational Intelligence and Intelligence Informatics 10(4), 578–585 (2006)
Ventresca, M., Tizhoosh, H.R.: Improving the Convergence of Backpropagation by Opposite Transfer Functions. In: Proc. IEEE International Joint Conf. on Neural Networks (IJCNN), Vancouver, July 16-21, pp. 9527–9534 (2006)
Ventresca, M., Tizhoosh, H.R.: Opposite Transfer Functions and Backpropagation Through Time. In: Proc. IEEE Symposium on Foundations of Computational Intelligence (FOCI 2007), Hawaii, April 1-5, pp. 570–577 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Malisia, A.R. (2008). Improving the Exploration Ability of Ant-Based Algorithms. In: Tizhoosh, H.R., Ventresca, M. (eds) Oppositional Concepts in Computational Intelligence. Studies in Computational Intelligence, vol 155. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70829-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-70829-2_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70826-1
Online ISBN: 978-3-540-70829-2
eBook Packages: EngineeringEngineering (R0)