压缩感知与信号恢复.ppt

(TabuSearch,简称TS)的思想最早由FredGlover提出,是对局部领域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。在解决最优问题上,一般区分为两种方式,一种是传统的方法,就是穷举法、贪婪法、分治法、动态规划等等;而另一种方法则是一些启发式搜索算法。而这两种方法最大的不同点就在于使用传统的方法,我们必须对每一个问题都去设计一套算法,一旦我们遇到一个新的问题,整个算法就得重新设计,所以相当不方便,也缺乏广泛性。可是相对的好处就是一旦我们可以证明算法的正确性,那么我们就可以保证找到的答案一定是最优的。而对于启发式算法,针对不同的问题,我们可以套用同一个架构来寻找答案,在这个过程中,我们只需要设计评价函数以及如何找到下一个可能解的函数等等,所以启发式算法的广泛性比较高。,是一种全局逐步寻求最优算法。禁忌搜索算法中充分体现了集中和扩散两个策略,它的集中策略体现在局部搜索,即从一点出发,在这点的邻域内寻求更好的解,以达到局部最优解而结束,为了跳出局部最优解,扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息,算法通过对禁忌表中点的禁忌,而达到一些没有搜索的点,从而实现更大区域的搜索。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索,虽然算法通用易实现,且容易理解,但搜索性能完全依赖于邻域结构和初解,尤其会陷入局部极小而无法保证全局优化型。TS的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小跳出策略。:首先,由于TS是局部邻域搜索的一种扩充,因此邻域结构设计很关键,它决定了当前解的邻域解的产生形式和数目以及各个解之间的关系。候选解:出于改善算法的优化时间性能考虑,如果邻域结构决定了大量的邻域解,则可仅尝试部分解互换的结构,而候选解也仅去其中的少量最佳状态。禁忌长度:禁忌长度是一个很重要的关键参数,它决定禁忌对象的禁忌时间,其大小直接影响整个算法的搜索进程和行为。禁忌对象的替换可以采用FIFO方式,即先进先出,也可以采用其他方式甚至是动态自适应的方式。禁忌搜索算法理论介绍特赦准则:特赦准则的设置是算法避免遗失优良状态,激励对优良状态的局部搜索,进而实现全局优化的关键步骤。对非禁忌候选状态,算法无视它与当前状态的适配值的优劣关系,仅考虑它们中间的最佳状态为下一步决策,如此可实现对局部极小的跳出。终止准则:为了使算法具有优良的性能或时间性能,必须设置一个合理的终止准则来结束整个搜索过程。此外,在许多场合禁忌对象的被禁次数越多也被用于搜索,以取得更大的搜索空间。禁忌次数越高,通常可认为出现循环搜索的概率越大。禁忌搜索算法理论介绍为了便于理解,我们可以将禁忌搜索过程看作一群兔子寻找最高峰(最优)的问题。禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地方寻找。当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中禁忌表的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的禁忌搜索算法理论介绍兔群,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做禁忌长度,如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当一个有兔子留守的地方优越性太突出,超过了目前最好的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则”。禁忌搜索算法流程给定算法参数,随机产生初始解x,置禁忌表为空。判断算法终止条件是否满足。若是,则结束算法并输出优化结果;否则,继续以下步骤。利用当前解的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。对候选解判断藐视准则是否满足。若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,即x=y,并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换目前最优状态,然后转步骤6;否则,继续以下步骤。禁忌搜索算法流程判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。转第二步禁忌搜索算法流程伪代码表达: begininitializeastringvcatrandom,clearup