Tabu search with multi-level neighborhood structures for high dimensional problems
详细信息 查看全文
- 作者：Abdel-Rahman Hedar (1) hedar@aun.edu.eg
Ahmed Fouad Ali (2) - 关键词：Metaheuristics – ; Tabu search – ; High dimensional problems – ; Global optimization
- 刊名：Applied Intelligence
- 出版年：2012
- 出版时间：September 2012
- 年：2012
- 卷：37
- 期：2
- 页码：189-206
- 全文大小：1.4 MB
- 参考文献：1. Ahujaa RK, Orlinb JB, Sharmac D (2000) Very large-scale neighborhood search. Int Trans Oper Res 7:301–317
2. Ahujaa RK, Ergunb O, Orlinc JB, Punnend A (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl Math 123:75–102
3. Ali YMB Psychological model of particle swarm optimization based multiple emotions. Appl Intell (to appear)
4. Brest J, Maucec MS (2008) Population size reduction for the differential evolution algorithm. Appl Intell 29:228–247
5. Cai Z, Gonga W, Lingb CX, Zhangc H (2011) A clustering-based differential evolution for global optimization. Appl Soft Comput 11:1363–1379
6. Chiarandini M (2008) Very large-scale neighborhood search: overview and case studies on coloring problems. Stud Comput Intell 114:117–150
7. Conn AR, Gould NIM, Toint PL (1987) Trust-region methods. MPS-SIAM series on optimization. SIAM, Philadelphia
8. Das S, Abraham A, Chakraborty UK, Konar A (2009) Differential evolution using a neighborhood-based mutation operator. IEEE Trans Evol Comput 13(3):526–553
9. Dolan ED Pattern search behaviour in nonlinear optimization. Thesis (1999)
10. Dreo J, P茅trowski A, Siarry P, Taillard E (2007) Metaheuristics for hard optimization. Springer, Berlin
11. Duarte A, Marti R, Glover F, Gortazar F (2011) Hybrid scatter tabu search for unconstrained global optimization. Ann Oper Res 183:95–123
12. Erguna O, Orlin JB (2006) A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem. Discrete Optim 3:78–85
13. Gallego RA, Romero R, Monticelli AJ (2000) Tabu search algorithm for network synthesis. IEEE Trans Power Syst 15(2):490–495
14. Garc铆a S, Lozano M, Herrera F, Molina D, S谩nchez AM (2008) Global and local real-coded genetic algorithms based on parent-centric crossover operators. Eur J Oper Res 185:1088–1113
15. Ge R (1990) A filled function method for finding a global minimizer of a function of several variables. Math Program 146:191–204
16. Glover F, Laguna M (1997) Tabu search. Kluwer, Boston
17. Glover F, Taillard E, Werra D (1993) A user’s guide to tabu search. Ann Oper Res 41:3–28
18. Hadi Mashinchia M, Orguna MA, Pedryczb W (2011) Hybrid optimization with improved tabu search. Appl Soft Comput 11(2):1993–2006
19. Hansen N (2006) The CMA evolution strategy: a comparing review. In: Lozano JA, Larra帽aga P, Inza I, Bengoetxea E (eds) Towards a new evolutionary computation. Springer, Berlin
20. Hansen P, Mladenovic N, P茅rez JA Moreno (2010) Variable neighbourhood search: methods and applications. Ann Oper Res 175(1):367–407
21. Hedar A, Fouad A (2009) Genetic algorithm with population partitioning and space reduction for high dimensional problems. In: Proceeding of the 2009 international conference on computer engineering and systems (ICCES09), Cairo, Egypt, pp 151–156
22. Hedar A, Fukushima M (2002) Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optim Methods Softw 17:891–912
23. Hedar A, Fukushima M (2003) Minimizing multimodal functions by simplex coding genetic algorithm. Optim Methods Softw 18:265–282
24. Hedar A, Fukushima M (2004) Heuristic pattern search and its hybridization with simulated annealing for nonlinear global optimization. Optim Methods Softw 19:291–308
25. Hedar A, Fukushima M (2006) Tabu search directed by direct search methods for nonlinear global optimization. Eur J Oper Res 170:329–349
26. Hedar A, Fukushima M (2006) Evolution strategies learned with automatic termination criteria. In: Proceedings of SCIS&ISIS 2006, Tokyo, Japan, September 20–24, 2006. Japan Society for Fuzzy Theory and Intelligent Informatics, Tokyo, pp 1126–1134
27. Hedar A, Fukushima M (2006) Directed evolutionary programming: towards an improved performance of evolutionary programming. In: Proceedings of congress on evolutionary computation, CEC 2006, IEEE world congress on computational intelligence, Vancouver, Canada, July 16–21, pp 1521–1528
28. Hedar A, Ong BT, Fukushima M (January 2007) Genetic algorithms with automatic accelerated termination. Technical Report 2007-002, Department of Applied Mathematics and Physics, Kyoto University
29. Hedar A, Jue W, Fukushima M (2008) Tabu search for attribute reduction in rough set theory. Soft Comput 12:909–918
30. Herrera F, Lozano M (2000) Two-loop real-coded genetic algorithms with adaptive control of mutation step sizes. Appl Intell 13(3):187–204
31. Herrera F, Lozano M, Verdegay JL (1998) Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artif Intell Rev 12:265–319
32. Herrera F, Lozano M, Molina D (2006) Continuous scatter search: An analysis of the integration of some combination methods and improvement strategies. Eur J Oper Res 169(2):450–476
33. Hvattum LM, Glover F (2009) Finding local optima of high-dimensional functions using direct search methods. Eur J Oper Res 195:31–45
34. Jones DR (2001) The DIRECT global optimization algorithm. In: Floudas C, Pardalos P (eds) Encyclopedia of optimization. Kluwer Academic, Dordrecht, pp 431–440
35. Keane AJ http://www.soton.ac.uk/~ajk/bump.html. Visited on 30 March 2011
36. Kolda TG, Lewies RM, Torczon VJ (2003) Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev 45:385–482
37. Laguna M, Mart铆 R (2005) Experimental testing of advanced scatter search designs for global optimization of multimodal functions. J Glob Optim 33(2):235–255
38. Lee CY, Yao X (2004) Evolutionary programming using the mutations based on the L茅vy probability distribution. IEEE Trans Evol Comput 8:1–13
39. Leung YW, Wang Y (2001) An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Trans Evol Comput 5(1):41–53
40. Levy A, Montalvo A (1985) The tunneling algorithm for the global minimization of functions. SIAM J Sci Stat Comput 6:15–29
41. Li Y, Zeng X (2010) Multi-population co-genetic algorithm with double chain-like agents structure for parallel global numerical optimization. Appl Intell 32:292–310
42. Liang JJ, Suganthan PN, Deb K (2005) Novel composition test functions for numerical global optimization. In: Proceedings of 2005 IEEE swarm intelligence symposium, Pahes, pp 68–75
43. Liang JJ, Qin AK, Suganthan PN, Baskar S (2006) Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans Evol Comput 10(3):281–295
44. Linhares A, Yanasse HH (2010) Search intensity versus search diversity: a false trade off? Appl Intell 32:279–291
45. Liu H, Cai Z, Wang Y (2010) Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Appl Soft Comput 10(2):629–640
46. Liuzzi G, Lucidi S, Piccialli V (2010) A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems. Comput Optim Appl 45:353–375
47. Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with crossover hill-climbing. Evol Comput 12(3):273–302
48. MacQueen LB (1967) Some methods for classification and analysis of multivariate observations. In: LeCam LM, Neyman N (eds) Proceedings of 5th Berkeley symposium om mathematical statistics and probability. University of California Press, Berkeley, pp 281–297
49. Maniezzo V, Stutzle T, Vob S (2009) Matheuristics: hybridizing metaheuristics and mathematical programming. Annals of information systems. Springer, Berlin
50. Meyers C, Orlin J (2007) Very large-scale neighborhood search techniques in timetabling problems. In: PATAT’06 proceedings of the 6th international conference on practice and theory of automated timetabling VI. Springer, Berlin, pp 24–39
51. Mladenovic N, Drazic M, Kovac V, Angalovic M (2008) General variable neighborhood search for the continuous optimization. Eur J Oper Res 191:753–770
52. Montes de Oca MA, Stutzle T, Birattari M, Dorigo M (2009) Frankenstein’s PSO: a composite particle swarm optimization algorithm. IEEE Trans Evol Comput 13(5):1120–1132
53. M眉hlenbein H, Schlierkamp-Vose D (1993) Predictive models for the breeder genetic algorithm. IEEE Trans Evol Comput 1(1):25–49
54. Nguyen QH, Ong Y-S, Lim MH (2009) A probabilistic memetic framework. IEEE Trans Evol Comput 13(3):604–623
55. Noman N, Iba H (2008) Accelerating differential evolution using an adaptive local search. IEEE Trans Evol Comput 12(1):107–125
56. Pan ZJ, Kang LS (1997) An adaptive evolutionary algorithms for numerical optimization. In: Yao X, Kim JH, Furuhashi T (eds) Simulated evolutionary and learning. Lecture notes in artificial intelligence. Springer, Berlin, pp 27–34
57. Price KV, Storn RM, Lampinen JA (2005) Differential evolution: a practical approach to global optimization. Springer, Berlin
58. Qin AK, Huang VL, Suganthan PN (2009) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13(2):298–417
59. Rego C, Alidaee B (2005) Metaheuristic optimization via memory and evolution, Tabu search and scatter search. Springer, Berlin
60. Rosin CD, Halliday R Scott, Hart WE, Belew RK (1997) A comparison of global and local search methods in drug docking. In: B盲ck T (ed) Proceeding of the seventh international conference on genetic algorithms (ICGA97). Morgan Kaufmann, San Francisco, pp 221–228
61. Siarry P, Michalewicz Z (2007) Advances in metaheuristics for hard optimization. Natural computing series. Springer, Berlin
62. Socha K, Dorigo M (2008) Ant colony optimization for continuous domains. Eur J Oper Res 185(3):1155–1173
63. Solis FJ, Wets RJB (1981) Minimization by random search techniques, Mathematical. Oper Res 6:19–30
64. Spall JC (1992) Multivariate stochastic approximation using a simulation perturbation gradient approximation. IEEE Trans Autom Control 37:332–341
65. Spall JC (1998) Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Trans Aerosp Electron Syst 34:817–823
66. Torezon VJ (1989) Multi-directional search, a direct search algorithm for parallel machines. PhD Thesis, Rice University
67. Vrugt JA, Robinson BA, Hyman JM (2009) Self-adaptive multimethod search for global optimization in real-parameter spaces. IEEE Trans Evol Comput 13(2)
68. Wang Y-J, Zhang J-S (2007) An efficient algorithm for large scale global optimization of continuous functions. J Comput Appl Math 206:1015–1026
69. Wright MH (1996) Direct search methods, Once Scorned, now respectable. In: Griffiths DF, Watson GA (eds) Numerical analysis, 1995. Addison-Wesley Longman, Harlow, pp 191–208
70. Yang Z, Tang K, Yao X (2008) Large scale evolutionary optimization using cooperative coevolution. Inf Sci 178:2986–2999
71. Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evol Comput 3(2):82–102
72. Zhong W, Liu J, Xue M, Jiao L (2004) A Multiagent genetic algorithm for global numerical optimization. IEEE Trans Syst Man Cybern, Part B, Cybern 34(2):1128–1141
73. Zilinskas J (2008) Branch and bound with simplicial partitions for global optimization. Math Model Anal 13(1):145–159 - 作者单位：1. Dept. of Computer Science, Faculty of Computers & Information, Assiut Univ., Assiut, 71526 Egypt2. Dept. of Computer Science, Faculty of Computers & Information, Suez Canal University, Ismailia, Egypt
- ISSN：1573-7497
文摘
Metaheuristics have been successfully applied to solve different types of numerical and combinatorial optimization problems. However, they often lose their effectiveness and advantages when applied to large and complex problems. Moreover, the contributions of metaheuristics that deal with high dimensional problems are still very limited compared with low and middle dimensional problems. In this paper, Tabu Search algorithm based on variable partitioning is proposed for solving high dimensional problems. Specifically, multi-level neighborhood structures are constructed by partitioning the variables into small groups. Some of these groups are selected and the neighborhood of their variables are explored. The computational results shown later indicate that exploring the neighborhood of all variables at the same time, even for structured neighborhood, can badly effect the progress of the search. However, exploring the neighborhood gradually through smaller number of variables can give better results. The variable partitioning mechanism used in the proposed method can allow the search process to explore the region around the current iterate solution more precisely. Actually, this partitioning mechanism works as dimensional reduction mechanism. For high dimensional problems, extensive computational studies are carried out to evaluate the performance of newly proposed algorithm on large number of benchmark functions. The results show that the proposed method is promising and produces high quality solutions within low computational costs.