第8章捕食搜索算法

1第八章捕食搜索算法2PredatorySearchAlgorithm捕食搜索算法的基本思想：模仿动物的捕食策略（广域与邻域有效结合起来）。捕食搜索算法（PS）3AlexandreLinhares在1998提出来的一种用于解决组合优化问题的模拟动物捕食行为的空间搜索策略。把捕食搜索策略分别应用于解决旅行商问题（TSP）和超大规模集成电路设计（VLSI）问题，都取得了较好效果捕食搜索算法——产生4动物捕食时，在没有发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物；一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有猎物的迹象的附近区域进行集中的区域搜索，以找到更多的猎物。在搜寻一段时间没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻找猎物。动物的这种捕食搜索策略可以概括为以下两个搜索：捕食搜索算法——基本原理5搜索1（全局搜索）：在整个搜索空间进行全面搜索，直到发现猎物或者有猎物的迹象而转到搜索2进行局域搜索；搜索2（局域搜索）：在猎物或者有猎物的迹象的附近区域进行集中搜索，直到搜索很多次也没有找到猎物而放弃局域搜索，转到搜索1进行全局搜索。捕食搜索算法——基本原理6动物的捕食策略全局搜索(在整个捕食空间内)发现新的猎物?N局部搜索(在局域内)发现新的猎物?YYN7应用捕食搜索算法寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解；然后在较优解附近的区域进行集中搜索，直到搜索很多次也没有找到更优解，从而放弃局域搜索；然后再在整个搜索空间进行全局搜索。如此循环，直到找到最优解（或近似最优解）为止。在捕食搜索算法中，使用限制（restriction）来表征较优解的邻域大小。通过限制的调节，实现搜索空间的增大和减小，从而达到探索能力和开发能力的平衡。捕食搜索算法——基本原理8捕食搜索算法——基本原理全局搜索(在整个解空间内)找到更好的解?N邻域搜索(在邻域内)找到更好的解?YYN9捕食搜索算法——基本概念把组合优化问题定义为一个二元组(,)Z，这里是解的集合，函数:Z代表每个解到对应的适应值的变换。假设每个解s存在一个邻域()Ns，定义'()()NsNs，这里'()Ns包含了()Ns中元素的5%。()Ns中一个解到另一个解的变换称为一个移动。在规模为n个城市的TSP问题中，用由从1到n的n个自然数组成的集合中的每个元素表示城市，元素所在的位置表示被访问的顺序。例如，状态s=12(,,,)nxxx表示旅行商访问的路线为：x1——x2——…——xn——x1。10捕食搜索算法——基本概念一个解为一个巡回路线，给定一个解s，采用2-opt法进行状态的转移，即将其子串：xq，xq+1，…，xq+r倒转得到：xq+r，…，xq+1，xq则得到一个新的解，其中：1,qqrn。组合所有可能的q和r就得到s的邻域()Ns。如果对于任何两个状态s0和sm，和某个R，存在一个序列：s0，s1，s2，…，sm-1，sm若对于所有正整数0km，有1()kksNs，则称解sm是从s0可达的。11捕食搜索算法——基本概念如果对某个R，对于路径上的所有状态有()kZsR，则称这条路径服从限制（Restriction）R。因此我们可以将函数:2A定义为从s可达的服从限制R的所有解的集合(,)As。这样，给定一个最好解b和一个限制R，围绕b的一个受限搜索区域可以表示为(,)AbR。为了实现一个在已知最好解附近的逐渐扩大的搜索区域，可以定义一个由NumLevel+1个限制级别组成的序列：限制[L]，这里{0,1,,}LNumLevel，称为限制的级别（LeveloftheRestriction）。12捕食搜索算法——基本概念解空间示意图121115248671093Z限制[0]限制[1]限制[2]限制[3]13捕食搜索算法——基本概念算法的主要迭代来自搜索1：从邻域中取样，如果样品中的最好解的适应值小于限制L，那么将其作为新的解，重新开始。出于可操作性的考虑，算法的每步取样取一个较小的子集，即邻域的5%。没有将整个集合()Ns作为考察的样本是因为：（1）这是一个耗时为2()On的操作（2）将使算法成为不具可行性的操作，导致无限的循环。需要注意的是，邻域中的最好解即使其适应值大于当前解也会被接受，当移动出一个局优之后，算法必然还会返回该点，因为该点是邻域()Ns中的最好解。14捕食搜索算法——基本概念每一次尝试性的移动之后，有一个指针来记录在该区域内迭代的次数。当指针到达一个关键点之后，增加限制的等级L，从而不断加大搜索的区域。当L到达某一个值Lthreshold时，意味着算法已经在所限制的区域内进行了多次有效的搜索而没有找到改进的解（improvingsolution），于是算法放弃区域限制的搜索方式，将L设置为一个较高的值LhighThreshold。这个较高的值表示在建立一列取样时得到的一个较差解的适应值，在这样一个限制的约束下，算法可以搜索很大的区域，很快跳出原来所限制的较小的区域。15捕食搜索算法——基本概念当发现一个改进的解时，需要一些特殊的操作：（1）若找到更好的解则更新最优解b；（2）从b的邻域中计算得到一列限制等级（具体后述）；（3）将L设为0，从而让算法在b的附近进行细致的搜索。16捕食搜索算法——算法步骤算法步骤可表达如下：步1：随机选择一个初始点solution，solution，令bsolution，counter=0，L=0；步2：如果LNumLevel，取()Ns的5%构造出'()Ns，并取其中最小解proposal，然后转步3；否则结束。步3：如果(,[])proposalAbRestrictionL，令solution=proposal，然后转步4；否则转步5；17捕食搜索算法——算法步骤步4：如果()()ZsolutionZb，令bsolution，level=0，counter=0，重新计算限制，然后转步2；否则转步5；步5：令counter=counter+1，如果counterCthreshold，令L=L+1，counter=0，然后转步6；否则转步2；步6：如果L=Lthreshold，令L=LhighThreshold，并转步2；否则直接转步2；这里，Restriction[L]表示限制，其他相关符号的定义，见算法概念中的描述。18捕食搜索算法——限制的计算上述步骤4中，如果()()ZsolutionZb，重新计算限制，具体操作为：(1)搜索NumLevel次迄今为止发现的最好解b的邻域，计算Z，得到NumLevel个适应值；(2)把这NumLevel个值与发现的最好解的适应值按照升序排列；把排列后的NumLevel个值依次赋给限制Restriction[1]，Restriction[2]，…，Restriction[NumLevel]。而Restriction[0]的值取为刚获得的最好的适应值()Zb。19捕食搜索算法——参数的设置（1）每一步搜索时评估邻域中解的比例。邻域中可能的解数量为20.5()nn，这里是取邻域中解的5%进行评估。（2）NumLevel：总的限制级别数为NumLevel+1，文献中NumLevel取为n。（3）Cthreshold：用于增大限制等级L的指针阈值。文献中设置为3n。如果在某个限制等级下，搜索了Cthreshold次（搜索一次即取样5%）仍没有找到改进的解，那么将增大限制等级L。（4）Lthreshold：当L到达Lthreshold时，意味着算法已经在所限制的区域内进行了多次有效的搜索而没有找到改进的解，于是算法放弃区域限制的搜索方式，在文献中将其设置为[n/20]，这里[]为取整运算符，即区域限制搜索模式的限制等级数为城市总数被20除的结果的整数。20捕食搜索算法——参数的设置（5）LhighThreshold：表示一个较高的适应值，文献[2]中取为n-[n/20]。即在常规搜索模式下，如果算法在[n/20]个限制等级下搜索过后仍不能发现新的改进的解，那么算法将停止。从上面的参数设置我们可以看到，在文献[2]中区域限制的搜索和常规搜索中经历的限制等级数都为[n/20]，具体如下。对于区域限制搜索来说，限制等级为：0,1,2…,[n/20]-1；对于常规限制搜索来说，限制等级为：n-[n/20]，n-[n/20]+1，n-[n/20]+2,…,n-1。21捕食搜索算法——计算举例五城市非对称TSP问题，设五个城市分别为：1，2，3，4，5，距离矩阵为：0856760859()790569780556780ijDd22捕食搜索算法——计算举例为简化计算该问题的过程，相关参数设置如下：（1）每一步搜索时评估邻域中解的数量为2。（2）NumLevel=5；（3）Cthreshold=1；（4）Lthreshold=1；（5）LhighThreshold=4。邻域定义如前所示。23捕食搜索算法——计算举例算法开始，随机取一个初始点：solution=（1,2,3,4,5）则b=solution,counter=0,L=0。初始点的适应值为：()()885526ZbZsolution然后来计算限制，随机取solution邻域中的五个解为：s1=（2,1,3,4,5）s2=（1,2,4,3,5）s3=（3,2,1,4,5）s4=（1,2,5,4,3）s5=（1,5,4,3,2）24捕食搜索算法——计算举例计算其相应的适应值为：1()655521Zs2()858627Zs3()966526Zs4()898833Zs5()788932Zs25捕食搜索算法——计算举例所以，得到相应的限制为：Restriction[0]=26Restriction[1]=21Restriction[2]=26Restriction[3]=27Restriction[4]=32Restriction[5]=33至此，得到了第一列限制，邻域搜索的准备工作完毕。下面是捕食搜索的过程，从最小限制Restriction[0]开始。26捕食搜索算法——计算举例1）第一列限制中的Restriction[0]限制下，solution的邻域进行第一次搜索。随机取solution的邻域中的两个解为：（2,1,3,4,5），其适应值为21（1,3,2,4,5），其适应值为24故proposal=（2,1,3,4,5），又Z(proposal)=21Restriction[0]=26所以，solution=（2,1,3,4,5），令b=solution，重新计算限制。27捕食搜索算法——计算举例同样的方法得到5个限制：Restriction[0]=21Restriction[1]=24Restriction[2]=25Restriction[3]=26Restriction[4]=29Restriction[5]=32至此得到了第二列限制。28捕食搜索算法——计算举例2）第二列限制中的Restriction[0]限制下，solution的邻域进行第一次搜索。随机取solution的邻域中的两个解为：（2,1,4,3,5），其适应值为24（2,1,3,5,4），其适应值为25故proposal=（2,1,4,3,5），又Z(proposal)=24Restriction[0]=21，不更新solution，counter=counter+1=1。29捕食搜索算法——计算举例3）第二列限制中的Restriction[0]限制下，solution的邻域进行第二次搜索。再次搜索solution=（2,1,3,4,5）的邻域。随机取solution的邻域中的两个解：（3,1,2,4,5），其适应值为25（2,4,3,1,5），其适应值为27所以：proposal=（3,1,2,4,5）由Z(pro