禁忌搜索TabuSearch禁忌搜索(TabuSearch或TabooSearch，简称TS)的思想最早由Glover(1986)提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索概述特点Neighborhoodsearch+memoryNeighborhoodsearchMemoryRecordthesearchhistoryForbidcyclingsearch3的邻域加入禁忌表，避免陷入循环避免循环的原理：当前解为④时，其领域中最好的解为①，原本下一步应为①，但其与禁忌表中的元素相同，所以选择次好的解⑤，从而避免死循环禁忌表的更新禁忌表中元素禁忌表长度如果找到了一个新的解比当前记录的最好解还要好，那么即使从当前得到这个新的解被tabulist禁止，仍然接受这个新的解，并更新tabulist.即tabulist对这个解没有禁止作用假设记录生成相邻解的方法，Tabulist={②,③,④},下一步采用②方法生成了迄今为止最好的解，仍然接受这个，更新Tabulist={②,③,②},分散搜索：是为了对整个解的空间进行更广泛的覆盖，而不是仅仅局限在某个局部的区域。集中搜索：如果当前搜索区域内发现了比较好的解，如果进一步对当前区域进行更集中的搜索，那么可能会发现更多更好的解。分散搜索策略（Diversificationstrategy）在当前搜索区域内进行了一定次数的搜索了之后（如25次），若不能发现更好的解，那么就执行分散搜索策略。把tabulist清空，然后从一个新的初始解开始搜索。集中搜索：如果最好解的记录被更新，那么就执行集中搜索策略，即清空tabulist.这样可以在当前区域进行更自由的搜索。要设计一个禁忌搜索算法，需要确定以下环节变量定义：n＝搜索次数N＝搜索N次，程序结束NI＝连续没有找到更好解的次数M＝连续M次没有找到更好解，执行分散搜索策略BS＝找到的最好的解Tabulist初始化(清空)设M,N的值TSP算例Tabulist初始化(清空)设M,N的值Tabulist初始化(清空)设M,N的值Tabulist初始化(清空)设M,N的值求得初始解BS=初始解Tabulist初始化(清空)设M,N的值求得一系列候选解，并按优劣排序Tabulist初始化(清空)设M,N的值判断是否为tabu,决定接受与否Tabulist初始化(清空)设M,N的值求得一系列候选解，并按优劣排序Tabulist初始化(清空)设M,N的值判断是否为tabu,决定接受与否Tabulist初始化(清空)设M,N的值判断是否为tabu,决定接受与否Tabulist初始化(清空)设M,N的值更新当前解、最好解、tabulist及相关参数Tabulist初始化(清空)设M,N的值分散搜索（diversification）Tabulist初始化(清空)设M,N的值求得一系列候选解，并按优劣排序Tabulist初始化(清空)设M,N的值判断是否为tabu,决定接受与否Tabulist初始化(清空)设M,N的值求得一系列候选解，并按优劣排序Tabulist初始化(清空)设M,N的值判断是否为tabu,决定接受与否判断是否为tabu,决定接受与否Tabulist初始化(清空)设M,N的值EffectiveTabuSearchTabuSearchTabulist:Thelistconsistsofcombinationofjobattributes,thejobnumberanditspreviouslocationorpositionforrestrictionrule(a)andonlythejobnumberfor(b).Tabulistsize:Experimentsarecarriedoutwithfixedanddynamicallychangingtabulistsizes.Withrespecttodynamicallychangingtabulistsizesweimplementedthefollowingstrategy:Ifthereisnoimprovementintheprescribednumberofiterations,thetabusizeisincreasedtodiversifythesearch,sothatthesearchprocessmovesoutofthecurrentregiontoexploreotherareas.Stoppingcriterion:Noimprovementsinsolutionvalueforfixednumber