Continuous ant colony system and tabu search algorithms hybridized for global minimization of continuous multi-minima functions. (English) Zbl 1190.90141
Summary: A new hybrid optimization method, combining Continuous Ant Colony System (CACS) and Tabu Search (TS) is proposed for minimization of continuous multi-minima functions. The new algorithm incorporates the concepts of promising list, tabu list and tabu balls from TS into the framework of CACS. This enables the resultant algorithm to avoid bad regions and to be guided toward the areas more likely to contain the global minimum. New strategies are proposed to dynamically tune the radius of the tabu balls during the execution and also to handle the variable correlations. The promising list is also used to update the pheromone distribution over the search space. The parameters of the new method are tuned based on the results obtained for a set of standard test functions. The results of the proposed scheme are also compared with those of some recent ant based and non-ant based meta-heuristics, showing improvements in terms of accuracy and efficiency.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
ant colony optimization; tabu search; hybrid meta-heuristics; global optimization; continuous optimizationReferences:
| [1] | Glover, F.: Tabu search: Part I. ORSA J. Comput. 3, 190–206 (1989) · Zbl 0753.90054 |
| [2] | Glover, F.: Tabu search: Part II. ORSA J. Comput. 1, 4–32 (1990) · Zbl 0771.90084 |
| [3] | Hu, N.: Tabu search method with random moves for globally optimal design. Int. J. Numer. Methods Eng. 35, 1055–1070 (1992) · doi:10.1002/nme.1620350508 |
| [4] | Cvijovic, D., Klinowski, J.: Taboo search: an approach to the multiple minima problem. Science 667, 664–666 (1995) · Zbl 1226.90101 · doi:10.1126/science.267.5198.664 |
| [5] | Battiti, R., Tecchiolli, G.: The continuous reactive tabu search: blending combinatorial optimization and stochastic search for global optimization. Ann. Oper. Res. 63, 53–188 (1996) · Zbl 0851.90093 · doi:10.1007/BF02125453 |
| [6] | Siarry, P., Berthiau, G.: Fitting of tabu search to optimize functions of continuous variables. Int. J. Numer. Methods Eng. 40, 2449–2457 (1997) · Zbl 0882.65049 · doi:10.1002/(SICI)1097-0207(19970715)40:13<2449::AID-NME172>3.0.CO;2-O |
| [7] | Chelouah, R., Siarry, P.: Enhanced continuous tabu search: an algorithm for the global optimization of multiminima functions. In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (eds.) Meta-Heuristics, Advances and Trends in Local Search Paradigms for Optimization, vol. 4, pp. 49–61. Kluwer Academic, Dordrecht (1999) · Zbl 1073.90578 |
| [8] | Chelouah, R., Siarry, P.: Tabu search applied to global optimization. Eur. J. Oper. Res. 123, 256–270 (2000) · Zbl 0961.90037 · doi:10.1016/S0377-2217(99)00255-6 |
| [9] | Dorigo, M.: Optimization, learning and natural algorithms. Ph.D. thesis, Univ. of Milan, Milan (1992) |
| [10] | Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies. In: Proceedings of the First European Conference on Artificial Life, pp. 134–142. Elsevier, Amsterdam (1992) |
| [11] | Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 1, 29–41 (1996) · doi:10.1109/3477.484436 |
| [12] | Stutzle, T., Hoos, H.: The MAX–MIN ant system and local search for the traveling salesman problem. In: Proceedings of IEEE International Conference on Evolutionary Computation and Evolutionary Programming, pp. 309–314 (1997) |
| [13] | Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1, 53–66 (1997) · doi:10.1109/4235.585892 |
| [14] | Gambardella, L.M., Dorigo, M.: Ant-Q: a reinforcement learning approach to the traveling salesman problem. In: Proceedings of the Twelfth International Conference on Machine Learning, Palo Alto, pp. 252–260 (1995) |
| [15] | Costa, D., Hertz, A.: Ants can colour graphs. J. Oper. Res. Soc. 48, 295–305 (1997) · Zbl 0890.90174 |
| [16] | Dorigo, M., Caro, G.D., Gambardella, L.M.: Ant algorithms for discrete optimization. Artif. Life 3, 137–172 (1999) · doi:10.1162/106454699568728 |
| [17] | Dorigo, M., Bonabeau, E., Theraulaz, G.: Ant algorithms and stigmergy. Future Gener. Comput. Syst. 16, 851–871 (2000) · doi:10.1016/S0167-739X(00)00042-X |
| [18] | Wodrich, M., Bilchev, G.: Cooperative distributed search: the ants’ way. Control Cybern. 26(3), 413–445 (1997) · Zbl 0890.90159 |
| [19] | Bilchev, G., Parmee, I.C.: The ant colony metaphor for searching continuous design spaces. Lect. Notes Comput. Sci. 993, 25–39 (1995) |
| [20] | Monmarché, N., Venturini, G., Slimane, M.: On how Pachycondyla apicalis ants suggest a new search algorithm. Future Gener. Comput. Syst. 16, 937–946 (2000) · doi:10.1016/S0167-739X(00)00047-9 |
| [21] | Dréo, J., Siarry, P.: Continuous interacting ant colony algorithm based on dense heterarchy. Future Gener. Comput. Syst. 20, 841–856 (2004) · doi:10.1016/j.future.2003.07.015 |
| [22] | Dréo, J., Siarry, P.: A new ant colony algorithm using the heterarchical concept aimed at optimization of multi-minima continuous functions. Lect. Notes Comput. Sci. 2463, 216–221 (2002) · doi:10.1007/3-540-45724-0_18 |
| [23] | Ling, C., Jie, S., Ling, O., Hongjian, C.: A method for solving optimization problems in continuous space using ant colony algorithm. Lect. Notes Comput. Sci. 2463, 288–289 (2002) · doi:10.1007/3-540-45724-0_29 |
| [24] | Jun, L.Y., Jun, W.T.: An adaptive ant colony system algorithm for continuous-space optimization problems. J. Zhejiang Univ. Sci. 1, 40–46 (2003) |
| [25] | Pourtakdoust, S.H., Nobahari, H.: An extension of ant colony system to continuous optimization problems. Lect. Notes Comput. Sci. 3172, 294–301 (2004) · doi:10.1007/978-3-540-28646-2_27 |
| [26] | Socha, K.: ACO for continuous and mixed-variable optimization. Lect. Notes Comput. Sci. 3172, 25–36 (2004) · doi:10.1007/978-3-540-28646-2_3 |
| [27] | Socha, K., Dorigo, M.: Ant colony optimization for continuous domains. IRIDIA Technical Report, TR/IRIDIA/2005-037 · Zbl 1146.90537 |
| [28] | Socha, K., Dorigo, M.: Ant colony optimization for continuous domains. Eur. J. Oper. Res. 185, 1155–1173 (2008) · Zbl 1146.90537 · doi:10.1016/j.ejor.2006.06.046 |
| [29] | Nobahari, H., Pourtakdoust, S.H.: Optimization of fuzzy rule bases using continuous ant colony system. In: Proceedings of the First International Conference on Modeling, Simulation and Applied Optimization, Sharjah, U.A.E., Paper No. 243 (2005) · Zbl 1159.68649 |
| [30] | Nobahari, H., Pourtakdoust, S.H.: Optimal fuzzy CLOS guidance law design using ant colony optimization. Lect. Notes Comput. Sci. 3777, 95–106 (2005) · Zbl 1159.68649 · doi:10.1007/11571155_10 |
| [31] | Nobahari, H., Nabavi, S.Y., Pourtakdoust, S.H.: Aerodynamic shape optimization of unguided projectiles using ant colony optimization. In: Proceedings of ICAS 2006, Hamburg, Germany, 3–8 Sept. 2006 |
| [32] | Chelouah, R., Siarry, P.: A continuous genetic algorithm designed for the global optimization of multimodal functions. J. Heuristics 6, 191–213 (2000) · Zbl 0969.68641 · doi:10.1023/A:1009626110229 |
| [33] | Siarry, P., Berthiau, G., Durbin, F., Haussy, J.: Enhanced simulated annealing for globally minimizing functions of many continuous variables. ACM Trans. Math. Softw. 23(2), 209–228 (1997) · Zbl 0887.65067 · doi:10.1145/264029.264043 |
| [34] | Chelouah, R., Siarry, P.: Genetic and Nelder–Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions. Eur. J. Oper. Res. 148, 335–348 (2003) · Zbl 1035.90062 · doi:10.1016/S0377-2217(02)00401-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
