Tabu Search集中性和多样性自动平衡下的增强搜索策略  

A Fortified Search Strategy of Intensification and Diversification in Tabu Search

作　　者：雷开友[1] 王芳[1] 贺一[1] 邱玉辉[1] 刘光远[2] 

机构地区：[1]西南师范大学计算机与信息科学学院,重庆400715 [2]西南师范大学电子信息工程学院,重庆400715

出　　处：《计算机科学》2005年第11期161-163,共3页Computer Science

基　　金：教育部科学技术重点项目(NO.104262);重庆市科委基金项目(2003-7881)

摘　　要：在禁忌搜索算法中,集中性搜索与多样性搜索是缺一不可但又相互矛盾的两个方面。本文提出了一种在禁忌搜索集中性和多样性自动平衡下的增强搜索策略算法,这种算法在集中性搜索与多样性搜索之间保持合理平衡的同时,又进一步对结果加强集中性搜索或者多样性搜索,以获全局最优解。以组合优化中的典型难题 TSP为例,通过自动更换邻域、候选集,较好地解决了集中性搜索与多样性搜索的冲突。仿真实验表明,解的质量提高了,验证该算法有效。Intensification and diversification are two highly important components of tabu search, which conflict each other in many cases. We proposed a fortified search strategy that can encourage searching to the known solution more thoroughly,and can retain reasonable balance between intensification search and diversification search at the same time in order to get global optimal. Taking the classical combinatorial optimization problem TSP as samples,the conflict between intensification and diversification can be harmonized effectively by updating neighborhood and candidate automatively. Finally we give the experimental results.

关 键 词：禁忌搜索 集中性搜索 多样性搜索 TSP问题 搜索策略 自动平衡 多样性 集中性 SEARCH Tabu 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TH113.25[自动化与计算机技术—控制科学与工程]