禁忌搜索与固定变量结合的启发式算法求解UBQP

Tabu search algorithm with variable-based fixation on solving UBQP problem

提出了将固定变量与禁忌搜索结合的启发式算法来求解UBQP。此算法包含两个阶段:采用禁忌搜索得到一个参考解;根据该参考解固定或释放若干变量。选择固定变量还是释放变量由搜索的历史信息决定。此算法动态地在禁忌搜索与固定或释放变量这两个阶段之间交替进行,直到停机条件满足为止。用提出的算法对国际文献中公认的15个难算例进行实算测试,得到了全部测试算例的最优解。实验结果表明,该算法是求解UBQP的一个高效求解算法。

This paper proposed a tabu search algorithm with variable-based fixation to solve UBQP. The algorithm alternated between two phases ： one was a basic tabu search procedure to optimize the objective function as far as possible, the other was to fix the values of some variables which might he compatible with the optimal solution or to loose a certain number of fixed varia- bles when detected a stagnation behavior. The proposed algorithm was capable of finding the best-known solutions for 15 large random instances. Experimental results demonstrate the efficacy of the proposed algorithm in terms of both solution quality and computational efficiency.