《计算机应用研究》|Application Research of Computers

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

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

免费全文下载 (已被下载 次)  
获取PDF全文
作者 王阳,苗克坚
机构 西北工业大学 计算机学院,西安 710072
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2011)01-0131-03
DOI 10.3969/j.issn.1001-3695.2011.01.036
摘要 提出了将固定变量与禁忌搜索结合的启发式算法来求解UBQP。此算法包含两个阶段:采用禁忌搜索得到一个参考解;根据该参考解固定或释放若干变量。选择固定变量还是释放变量由搜索的历史信息决定。此算法动态地在禁忌搜索与固定或释放变量这两个阶段之间交替进行,直到停机条件满足为止。用提出的算法对国际文献中公认的15个难算例进行实算测试,得到了全部测试算例的最优解。实验结果表明,该算法是求解UBQP的一个高效求解算法。
关键词 组合优化;启发式算法;禁忌搜索;固定变量
基金项目
本文URL http://www.arocmag.com/article/1001-3695(2011)01-0131-03.html
英文标题 Tabu search algorithm with variable-based fixation on solving UBQP problem
作者英文名 WANG Yang, MIAO Ke-jian
机构英文名 College of Computer Science, Northwestern Polytechnical University, Xi'an 710072, China
英文摘要 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 be compatible with the optimal solution or to loose a certain number of fixed variables 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.
英文关键词 UBQP(unconstrained binary quadratic programming problem); heuristics; tabu search; variable-fixation
参考文献 查看稿件参考文献
 
收稿日期
修回日期
页码 131-133
中图分类号
文献标志码 A