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 algorithms 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 等数据库收录! |
|