基于禁忌表的捕食搜索算法及其在旅行商问题中的实验研究  

Predatory search algorithm based on tabu list and its experimental research on travelling salesman problems

作　　者：王有为[1] 

机构地区：[1]复旦大学管理学院,上海200433

出　　处：《系统工程理论与实践》2008年第2期131-136,共6页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70401010);国家留学基金

摘　　要：针对捕食搜索算法搜索过程中容易走回头路的缺点,提出了一种基于禁忌表的捕食搜索算法,然后对三个旅行商测试问题进行了实验研究.结果表明,新算法在求解的速度方面稍慢于原捕食搜索算法,但是解的质量比原捕食搜索算法有明显提高.As a new evolutionaly computation algorithm proposed recently, Predatory Search （PS） has been applied successfully in many NP-hard problems such as Travelling Salesman Problem （TSP） and design of large-scale integrated circuit. To account for the weakness of PS which prones to ＂go back＂ repeatedly to solution areas searched, this paper devised a new Predatory Search algorithm based on Tabu list. Experimental results on three TSP benchmark problems showed that although the efficiency of the new algorithm is slightly lower than that of the original PS algorithm, the quality of the solutions is improved evidently.

关 键 词：捕食搜索 禁忌搜索 旅行商问题 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]