Tabu search with multi-level neighborhood structures for high dimensional problems

被引:22
作者
Hedar, Abdel-Rahman [1 ]
Ali, Ahmed Fouad [2 ]
机构
[1] Assiut Univ, Dept Comp Sci, Fac Comp & Informat, Assiut 71526, Egypt
[2] Suez Canal Univ, Dept Comp Sci, Fac Comp & Informat, Ismailia, Egypt
关键词
Metaheuristics; Tabu search; High dimensional problems; Global optimization; CODED GENETIC ALGORITHMS; GLOBAL OPTIMIZATION; SCATTER SEARCH; MINIMIZATION; REDUCTION;
D O I
10.1007/s10489-011-0321-0
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:189 / 206
页数:18
相关论文
共 72 条
[1]  
Ahuja R. K., 2000, International Transactions in Operational Research, V7, P301, DOI 10.1111/j.1475-3995.2000.tb00201.x
[2]   A survey of very large-scale neighborhood search techniques [J].
Ahuja, RK ;
Ergun, Ö ;
Orlin, JB ;
Punnen, AP .
DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :75-102
[3]  
Ali YMB, APPL INTELL IN PRESS
[4]  
[Anonymous], 2005, METAHEURISTIC OPTIMI
[5]   Population size reduction for the differential evolution algorithm [J].
Brest, Janez ;
Maucec, Mirjam Sepesy .
APPLIED INTELLIGENCE, 2008, 29 (03) :228-247
[6]   A clustering-based differential evolution for global optimization [J].
Cai, Zhihua ;
Gong, Wenyin ;
Ling, Charles X. ;
Zhang, Harry .
APPLIED SOFT COMPUTING, 2011, 11 (01) :1363-1379
[7]  
Chiarandini M, 2008, STUD COMPUT INTELL, V114, P117
[8]  
Conn AR, 1987, MPS SIAM SERIES OPTI
[9]   Differential Evolution Using a Neighborhood-Based Mutation Operator [J].
Das, Swagatam ;
Abraham, Ajith ;
Chakraborty, Uday K. ;
Konar, Amit .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2009, 13 (03) :526-553
[10]  
DOLAN ED, 1999, THESIS