禁忌搜索算法

禁忌搜索算法（TabuSearch）吴浩博1局部搜索2禁忌搜索1算法的主要思路2禁忌搜索示例3禁忌搜索的关键参数和操作3.1变化因素3.2禁忌表3.3其他4禁忌搜索的实现与应用4.1图结点染色1局部搜索n个城市的对称旅行商问题简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域的结构；为了得到好的解，可以比较不同的邻域结构和不同的初始点；如果初始点的选择足够多，总可以计算出全局最优解。局部搜索示例禁忌搜索算法（TabuSearch）是由美国科罗拉多州大学的FredGlover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。2禁忌搜索2.1算法的背景2禁忌搜索2.1算法的背景使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域、禁忌表、禁忌长度、候选解、藐视准则等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化等计算机领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。2禁忌搜索2.1算法的背景2禁忌搜索四城市非对称TSP问题初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。2.2禁忌搜索示例2禁忌搜索四城市非对称TSP问题第1步解的形式禁忌对象及长度候选解f(x0)=42.2禁忌搜索示例ABCDBCDABC对换评价值CD4.5BC7.5BD8☻2禁忌搜索四城市非对称TSP问题第2步解的形式禁忌对象及长度候选解f(x1)=4.52.2禁忌搜索示例ABDCBCDABC3对换评价值CD4.5BC3.5BD4.5☻T2禁忌搜索四城市非对称TSP问题第3步解的形式禁忌对象及长度候选解f(x2)=3.52.2禁忌搜索示例ACDBBCDAB3C2对换评价值CD8BC4.5BD7.5☻TT2禁忌搜索四城市非对称TSP问题第4步解的形式禁忌对象及长度候选解f(x3)=7.5禁忌长度的选取2.2禁忌搜索示例ACBDBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT2禁忌搜索四城市非对称TSP问题第4步（如果减小禁忌长度）解的形式禁忌对象及长度候选解f(x3)=7.52.2禁忌搜索示例ACBDBCDAB12C0对换评价值CD4.5BC4.5BD3.5☻TT2禁忌搜索四城市非对称TSP问题第5步解的形式禁忌对象及长度候选解f(x4)=4.52禁忌搜索示例ADBCBCDAB01C2对换评价值CD7.5BC8BD4.5☻TTTS算法框架(1)是否有其他形式的候选集？(2)禁忌的长度如何确定？如果在算法中记忆下搜索到的当前最优解，极端的两种情况是：一是将所有的对换个数作为禁忌长度，此时等价于将候选集中的所有的对换遍历；另外则取为1，这等价于局部搜索算法。(3)是否有评价值的其他替代形式？有时计算目标值的工作量较大，或无法接受计算目标值所花费的时间，于是需要其他的方法。(4)被禁的对换能否再一次解禁？有这样的直观现象，当搜索到一个局部最优解后，它邻域中的其他状态都被禁，我们是否解禁一些状态以便跳出局部最优？解禁的功能就是为了获得更大的搜索范围，以免陷入局部最优。(5)如何利用更多的信息？在禁忌搜索算法中，还可记录其他一些信息。如一个被禁对象（交换）被禁的次数，评价值变化的大小等。(6)终止原则，即一个算法停止的条件，怎样给出？3禁忌搜索的关键参数和操作禁忌表的主要指标（两项指标）禁忌对象：禁忌表中被禁的那些变化元素禁忌长度：禁忌的步数状态变化（三种变化）解的简单变化解向量分量的变化目标值变化3.1变化因素3禁忌搜索的关键参数和操作解的简单变化3.1变化因素个解。是从一个解变化到另一则简单解变化为优化问题的定义域，，其中，邻域映射为假设)(,xNyxDNDyx这种变化最为简单，如从（ABCDE）变到（ABCED）3禁忌搜索的关键参数和操作向量分量的变化设原有的解向量为(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本变化为(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)即只有第i个分量发生变化。也包含多个分量变化的情形。3.1变化因素3禁忌搜索的关键参数和操作目标值的变化目标值的变化隐含着解集合的变化。3.1变化因素3禁忌搜索的关键参数和操作禁忌对象的选取情况1：禁忌对象为简单的解变化禁忌长度为4，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。3.2禁忌表3禁忌搜索的关键参数和操作禁忌对象的选取情况1：禁忌对象为简单的解变化第1步——xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。3.2禁忌表xnext=(ACBDE)3禁忌搜索的关键参数和操作禁忌对象的选取情况1：禁忌对象为简单的解变化第2步——xnow=(ACBDE)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。3.2禁忌表xnext=(ACBED)3禁忌搜索的关键参数和操作禁忌对象的选取情况1：禁忌对象为简单的解变化第3步——xnow=(ACBED)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)}Can_N(xnow)={(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)}。3.2禁忌表xnext=(ABCED)3禁忌搜索的关键参数和操作禁忌对象的选取情况1：禁忌对象为简单的解变化第4步——xnow=(ABCED)，f(xnow)=44，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)，(ABCED;44)}Can_N(xnow)={(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)}。3.2禁忌表xnext=(AECBD)此时H已达到4个解，新选入的解代替最早被禁的解3禁忌搜索的关键参数和操作禁忌对象的选取情况1：禁忌对象为简单的解变化第5步——xnow=(AECBD)，f(xnow)=44，H={(ACBDE;43)，(ACBED;43)，(ABCED;44)，(AECBD;44)}Can_N(xnow)={(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)}。3.2禁忌表xnext=(AEDBC)3禁忌搜索的关键参数和操作禁忌对象的选取情况2：禁忌对象为分量变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。3.2禁忌表3禁忌搜索的关键参数和操作禁忌对象的选取情况2：禁忌对象为分量变化第1步——xnow=(ABCDE)，f(xnow)=45，H=ΦCan_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)}。3.2禁忌表xnext=(ACBDE)由于H为空集，从候选集中选最好的一个，它是B与C的对换构成3禁忌搜索的关键参数和操作禁忌对象的选取情况2：禁忌对象为分量变化第2步——xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N(xnow)={(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}。3.2禁忌表xnext=(ACBED)3禁忌搜索的关键参数和操作禁忌对象的选取情况2：禁忌对象为分量变化第3步——xnow=(ACBED)，f(xnow)=43，H={(B,C)，(D,E)}Can_N(xnow)={(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)}。3.2禁忌表xnext=(AEBCD)可以看出，情况2比情况1禁忌的范围要更大一些3禁忌搜索的关键参数和操作禁忌对象的选取情况3：禁忌对象为目标值变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。3.2禁忌表3禁忌搜索的关键参数和操作禁忌对象的选取情况3：禁忌对象为目标值变化第1步——xnow=(ABCDE)，f(xnow)=45，H={45}Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。3.2禁忌表xnext=(ACBDE)3禁忌搜索的关键参数和操作禁忌对象的选取情况3：禁忌对象为目标值变化第2步——xnow=(ACBDE)，f(xnow)=43，H={45，43}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。3.2禁忌表xnext=(ADBCE)这种方法禁忌的范围更大3禁忌搜索的关键参数和操作禁忌对象的选取解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。3.2禁忌表3禁忌搜索的关键参数和操作3.2禁忌表],[maxminttt3禁忌搜索的关键参数和操作禁忌长度的选取禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。3.2禁忌表3禁忌搜索的关键参数和操作特赦（藐视）原则（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；3.2禁忌表3禁忌搜索的关键参数和操作候选集合的确定（1）从邻域中选择若干目标值最佳的邻居入选；（2）随机选取。3.3其他3禁忌搜索的关键参数和操作评价函数（1）直接评价函数，通过目标函数的运算得到评价函数；（2）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。3.3其他3禁忌搜索的关键参数和操作记忆频率信息根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。例如：如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。3