首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Tabu Guided Generalized Hill Climbing Algorithms
Authors:Vaughan  Diane E  Jacobson  Sheldon H
Institution:(1) Los Alamos National Laboratory, Los Alamos, New Mexico, 87544;(2) Simulation and Optimization Laboratory, Department of Mechanical and Industrial Engineering, University of Illinois, 1206 West Green Street, MC-244, Urbana, Illinois, 61801–2906
Abstract:This paper formulates tabu search strategies that guide generalized hill climbing (GHC) algorithms for addressing NP-hard discrete optimization problems. The resulting framework, termed tabu guided generalized hill climbing (TG2HC) algorithms, uses a tabu release parameter that probabilistically accepts solutions currently on the tabu list. TG2HC algorithms are modeled as a set of stationary Markov chains, where the tabu list is fixed for each outer loop iteration. This framework provides practitioners with guidelines for developing tabu search strategies to use in conjunction with GHC algorithms that preserve some of the algorithmsrsquo known performance properties. In particular, sufficient conditions are obtained that indicate how to design iterations of problem-specific tabu search strategies, where the stationary distributions associated with each of these iterations converge to the distribution with zero weight on all non-optimal solutions.
Keywords:tabu search  local search  generalized hill climbing algorithms  Markov chains
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号