基于节约算法和移动方向的禁忌搜索算法

作     者：郭娜 

作者单位：大连理工大学 

学位级别：硕士

导师姓名：曹晓东

授予年度：2009年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：禁忌搜索 c-w节约算法 多样性搜索 

摘      要：随着优化算法和启发式算法的提出,国内外掀起了研究智能优化算法的热潮。禁忌搜索是一种新的智能优化算法,是由美国科学家Glover教授于1986年正式提出。禁忌搜索(TS)在智能算法中独树一帜,成为一个研究热点,受到了国内外学者的广泛关注,并应用到组合优化和函数优化问题中。本文基于原禁忌搜索的思想提出一种改进的禁忌搜索算法,并把这种改进算法应用到实际问题中。 在前期工作的基础上,本文主要的工作包括针对禁忌搜索算法对初始解依赖性强的缺点,利用c-w节约算法得到初始解。禁忌搜索算法设计的框架中初始解尤为关键,初始解的好坏制约着搜索的收敛速度。通过c-w节约算法得到高质量解,构造算法新的搜索起点,加强了集中性搜索力度。在仿真实验中验证了其有效性。 同时针对禁忌搜索算法中集中性与多样性搜索并重的情况下,多样性不足的缺点,从下面两个方面改进算法,拓宽搜索领域,加强多样性搜索,增加灵活性。通过改进禁忌表存储结构,定义优质解和劣质解的出现次数这两个概念,不只利用禁忌表禁忌最近的搜索,还记录这些移动是否有所改进,记录下改进的信息,表明新解的改变程度,在搜索决策中并入这些信息,使得搜索往利于改进的方向进行。T S中确定性的搜索过程制约了它的灵活性,所以在禁忌搜索原则确定的基础上,根据搜索中的移动信息,增加概率性因素,在评价函数中增加一个概率函数,把确定性选择过程变为概率性的,从而改进搜索方向,拓宽搜索领域,使得更好的解有更大的被选中的机会。 旅行商问题(TSP)是典型的组合优化难题,但由于TSP有着广泛的实际应用工程背景,有效地解决TSP问题一直受到人们的重视,已有多种方法成功求解TSP问题。根据本文改进的禁忌搜索算法提出一种解决TSP问题有效形式。