现代优化算法学习心得正式Word文件下载.docx

现代优化算法学习心得正式Word文件下载.docx

《现代优化算法学习心得正式Word文件下载.docx》由会员分享，可在线阅读，更多相关《现代优化算法学习心得正式Word文件下载.docx（33页珍藏版）》请在冰点文库上搜索。

局部搜索算法

STEP1选下一个初始可行解x0；

记录当前最优解xbest：

=x0，令P=N（xbest）；

STEP2当P=Ф时，或满足其他停止运算准则时，输出计算结果，停止运算；

否则，从N（xbest）中选一集合S，得到S中的最优解xbest；

若

xbest＜

xbest，则xbest：

=xnow，P：

=N（xbest）；

否则，P：

=P-S；

重复STEP2。

在局部搜索算法中，STEP1的初始可行解选择可以采用随机的方法，也可用一些经验的方法或是其他算法所得到的解。

STEP2中的集合S选取可以大到是N（xbest）本身，也可以小到只有一个元素，如用随机的方法在N（xbest）中选一点，从直观可以看出，S选取得小将使每一步的计算量减少，但可比较的范围很小；

S选取大时每一步计算时间增加，比较的范围自然增加，这两种情况的应用效果依赖于实际问题。

在STEP2中，其他停止准则是除STEP2的P=Ф以外的其他准则。

这些准则的给出往往取决于人们对算法的计算时间、计算结果的要求，通过下面的例子来理解局部搜索算法。

例2．15个城市的对称TSP数据

如图2.1

对应的距离矩阵为

初始解为xbest=（ABCDE），f（xbest）=45。

在本例中，邻域映射定义为对换两个城市位置的2-OPT，选定A城市为起点，我们用两种情况解释局部搜索算法。

情况1全部域搜运，即S=-N（xbest）。

此时，P=N（xbest）—S为空集，于是所得解为（ADCBE），目标值为43。

情况2一步随机搜索

xbest=（ABCDE），fxbest=45

第一循环：

由于采用N（xbest）中的一步随机搜索，可以不再计算N（xbest）中每一点的值，若从中随机选一点，如xnow=（ACBDE）。

因f（xbest）=43＜45，所以xbest：

=（ACBDE）。

第二循环：

若从N（xbest）中又随机选一点xnow=（ACBDE），f（xnow）=44＞43。

P=N（xbest）-{xnow}，最后得到的解为（ACBDE）。

局部搜索算法的优点是简单易行，容易理解，但其缺点是无法保证全局最优性。

2.禁忌搜索

禁忌搜索是一种人工智能算法，是局部搜索算法的扩展，它的一个重要思想是标记已得到的局部最优解，并在进一步的选代中避开这些局部最优解，如何避开和记忆这些点是本章主要讨论的问题，首先，用一个示例来理解禁忌搜索算法。

例2.3（例2.2续）假设：

初始解x0=（ABCD），邻域映射为两个城市位置对换，始终点都为A城市，目标值为f（x0）-4，城市间的距离为：

第1步：

解的形式禁忌对象及长度候选集

此处评价值为目标值，由天假设了A城市为起终点，故候选集中最多有两两城市对换对3个。

分别对换城市顺序并按目标值由小到大排列，三个评价值劣于原值，在原有的局部搜索算法中，此时已达到局部最优解而停止，但现在，我们允许从候选集中选一个最好的对换—CD城市的位置交换，用★标记入选的对换，此时，解从（ABCD）变化为（ABDC），目标值上升，但此法可能跳出局部最优。

第2步：

由于第1步中选择了CD交换，于是，我们希望这样的交换在下面的若干次迭代中不再出现，以避免计算中的循环，CD成为禁忌对象并限定在3次迭代计算中不允许CD或DC对换。

在对应位置记录3，在N（x1）中又出现被禁忌的CD对换，故用T标记而不选此交换。

在选择最佳的候选对换后，到第3步。

第3步：

新选的BC对换被禁后，CD在被禁一次后还有二次禁忌，虽说候选集中的评价值都变坏，但为达到全局最优，还是从中选取，由于BC和CD对换被禁，只有BD对换入选。

第4步：

此时，所有候选对换被禁，怎么办？

通过这一个示例，我们会产生如下问题：

·

本例禁忌对象是对换，如BC对换造成ABCD到ACBD的变化，禁忌BC对换包括如下城市间顺序的对换：

ACBD到ABCD、ABCD到ACBD、ADBC到ADCB、ADCB到ADBC、ADBC到ACDB、ACDB到ABDC等的变化，若ACBD是刚才由ABCD变化而来的，结合解的变化，禁忌ACBD到ABCD和ABCD到ACDB的变化是可以接受的，但对其他变化的禁忌是否会影响求解的效率？

如ADBC到ADCB是否允许？

这一个问题说明禁忌对象是禁忌算法中一个基本的因素。

禁忌的次数如何选取？

若在例2.3中将禁忌次数从3更改为2，则有下列情形：

例2.4

第5步：

再迭代一步，又回到状态（ABCD），此时出现循环。

由例2.3和例2.4的计算可以看出，禁忌搜索算法是局部搜索算法的变形，应该注意到禁忌搜索算法计算中的关键点：

禁忌对象、长度和候选集成为算法的主要特征，围绕这些特征需要考虑下列因素。

（1）是否有其他形式的候选集？

上面的例子是将所有可对换的城市对作为候选集，再从候选集中没有被禁的对换对中选最佳，对n个城市的TSP，这样构造候选集使得每个集中有C2n1个交换对。

为了节省每一步的计算时间，有可能只在邻域中随机选一些对换，而不一定是比较邻域中的所有对换。

（2）禁忌的长度如何确定？

如果在算法中记忆下搜索到的当前最优解，极端的两种情况是：

一是将所有的对换个数作为禁忌长度，此时等价于将候选集中的所有的对换遍历；

另外则取为1，这等价于局部搜索算法。

（3）是否有评价值的其他替形式？

上面例中用目标值作为评价值，有时计算目标值的工作量较大，或无法接受计算目标值所花费的时间，于是需要其他的方法。

（4）被禁的对换能否再一次解禁？

如在例2.3的第4步中，候选集中的交换都被禁忌，若此时停止，得到的解甚至不是一个局部最优解，候选集中BD对换的评价值最小，是否不考虑对BD的禁忌而选择这个对换？

有这样的直观现象，当搜索到一个局部最优解后，它邻域中的其他状态都被禁，我们是否解禁一些状态以便跳出局部最优？

解禁的功能就是为了获得更大的搜索范围，以免陷入局部最优。

（5）如何利用更多的信息？

在禁忌搜索算法中，还可记录其他一些信息，如一个被禁对象（交换）被禁的次数，评价值变化的大小等，如果在例2.3中记忆同一个对换出现的此数，我们可以得到如下的一个有关禁忌对象的信息，

其中，矩阵右上角记录禁忌的长度，矩阵的左下角部分出现的数据表示对换被选为最佳的次数。

B与C对应5表示BC交换5次成为最佳候选。

这些数字提供了状态出现的频率，反映解的一些性质。

（6）终止原则，即一个算法停止的条件，怎样给出？

综合上面的讨论，禁忌算法的特征由禁忌对象和长、候选集和评价函数、停止规则和一些计算信息组成，禁忌表特别指禁忌对象及其被禁的长度，禁忌对象是指变化的状态，如上面例子中的两个城市的对换，候选集中的元素依评价函数而确定，根据评价函数的规划和其他一些特殊规则，在后续部分将介绍一个特殊规则—特赦原则。

计算中的一些信息，如被禁对象对应的评价值、被禁的频率等，对禁忌的长度和停止规划提供帮助。

禁忌搜索算法

STEP1选下一个初始解xnow及给以禁忌表H=Ф；

STEP2若满足停止规则，停止计算；

否则，在xnow的邻域N（H，xnow）中选出满足禁忌要求的候选集Can-N（xnow）；

在Can-N（xnow）中选一个评价值最佳的解xbext，xnow：

=xbext，更新历史记录II，重复STEP2。

禁忌算法的STEP2中，xnow的邻域N（H（xnow）中满足禁忌要求的元素包含两类：

一类是那些没有被禁忌的元素，另一类是可以被解除禁忌的元素，详细的技术问题将在2.3节讨论。

比较局部搜索算法，蒙特卡罗算法和禁忌搜索算法，它们的主要区别是第二步对接受点选择的原则不同。

为了给出禁忌搜索算法的全局最优定理，先介绍连通的概念。

定义2.1集合C称为相对邻域映射N：

X∈C→2c是连通的,若对C中的任意两点X,Y,存在X=X1;

X2……X1=Y，使得N（x）∩（X1+1）≠Ф；

i=1，2……,l-1。

定理2.1（最优定理）在禁忌搜运计算法中，若可行解区域相对Can-N（xnow）是连通的，且H的记录充分大，则一定可以达到全局最优解。

证明非常直观，虽说从理论上保证全局最优，但若使得H的记录充分大，也就是遍历所有的状态，这不是我们希望的，我们的期望是用更少的花费得到我们期望的解。

3．技术问题

禁忌搜索算法是一种人工智能算法，因此，实现的技术问题是算法的关键，本节按禁忌对象、候选集合的构成、评价函数的构造、特赦规则、记忆频率信息和终止规划等分别给予介绍和讨论。

3.1禁忌对象、长度与候选集

禁忌表中的两个主要指标是禁忌对象和禁忌长度，顺名思义，禁忌对象指的是禁忌表中被禁的那些变化元素，因为首先需要了解状态是怎样变化的，我们将状态的变化分为解的简单变化，解向量分量的变化和目标值变化三种情况，在这三种变化的基础上，讨论禁忌对象，本小节同时介绍禁忌长度和候选集确定的经验方法。

1、解和简单变化

这种变化最为简单，假设x，y∈D，其中D为优化问题的定义域，则简单解变化为

x→y

是从一个解变化到另一个解，这种变化在局部搜索算法中经常采用，如例2.1第一循环中从（ABCDE）变化到（ACBDE），这种变化将问题的解看成变化最基本因素。

2、向量分量的变化

这种变化考虑的更为精细，以解向量的每一个分量为变化的最基本因素，仅以（ABCDE）变化到（ACBDE）为例，它的变化实际是由B和C的对换引起，但B和C对换可以引起更多解的简单变化，如：

（ABCDE）→（ACBDE）

（ABDCE）→（ACDBE）

（ACBED）→（ABCED）

等。

设原有的解向量为（X1……X1-1,X1+1……Xn）,用数学表达式来描述向量分量的最基本变化为：

（X1……Xi1,Xi，X1+1……Xn）→（X1……Xi1,yi，X1+1……Xn）

即只有第i个分量发生变化，向量的分量变化包含多个分量发生变化的情形。

部分优化问题的解可以用一个向量形式x-（X1，X2……Xn）r∈{0,1}n表示。

解与解之间的变化可以表示某些分量的变化，如用分量从X1=0变化为X1=1或从XK]变化为XK=0，或是两者的结合，可以通过下面两个例子理解。

例2.5例1.1的01背包问题的状态变化是向量分量变化形式，如果每次只允许一个变量变化，即，N；

xD→N（x）{∣y

∣-Xi∣≤1}∈2n，则变化的变量只可能由Xj=0。

例2.6TSP问题采用例1.28R2–opt位置交换规划，以例2.2的四城市TSP数据为例，当一个解为（ABCD）时，两个城市BD的交换可以理解为：

用一个{0，1}n×

（n-1）的向量表示解，则（XAB=1；

XBC=1，XCD=1，XDA=1）其他分量为零；

分量的变化是：

由XAB=1变化为XBB=0，；

XBC=1变化为XBC=0；

XCD=1变化为XCD=0；

XDA=1变化为XDA=0，由XDA=0变化为XDA=1；

由XAD=0变化为XAD=1，由XBC=0变化为XBC=1；

由Xcb=0变化为Xcb=1,由XDA=0变化为XBA=1,于是，一个2-opt交换共需8个分量发生变化，这种情况归类于多个分量变化的结合。

3、目标值变化

在优化问题的求解过程中，我们非常关心目标值是否发生变化，是否接近最优目标值，这就产生一种观察状态变化的方式：

观察目标值或评价值的变化，就犹如等位线的道理一样，把处在同一等位线的解视为相同，这种变化是考察。

II（a）={x∈D∣f（X）=a}

其中，f（x）为目标函数，它的表面是两个目标值的变化，即从a→b，但隐含着两个解集合的各种变化

的可能。

例2.7考虑目标函数f（x）-x2的目标值从1变化到4，这里隐含着解空间中四个变化的可能

以上三种状态变化的情形，第一种的变化比较单一，而第二和第三种变化则隐含着多个解变化的可能，因此在选择禁忌对象时，可以根据实际问题采用适当的变化。

4禁忌对象的选取

由上面关于状态变化三种形式的讨论，禁忌的对象就可以是上面的任何一种，现用示例来分别理解，第一种情况考虑解为简单变化，当解从x→y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一个解再度出现，禁忌的规则是：

当y的邻域中有比它更优的点时，则选择更优的解；

当y为N（y）的局部最优时，不再选y，而选择比y较差的解。

见例2.8

禁忌对象为简单的解变化，禁忌表H只记忆三个被禁的解，即禁忌长度为3，从2-opt邻域N（II，xnow）中选出最佳的五个解组成候选集Can.N（xnow）；

初始解xnow=xo=（ABCDE），

（x0）=45

由于H为空集，从候选集中选最好的一个。

如果禁忌第2种变化，则观察下例。

例2.9（例2.8续）数据同例2.8H只记忆三对对换时，从2-opt邻域N（H，xnow）-{xnow}中选出最佳的五个状态对应的交换对组成候选集Can.N（xnow），这一眯不同于例2.8，因为受禁的是交换对，因此不考虎没有变化的xnow，初始解xnow=xo=（ABCDE），

由于H为空集，从候选集中选最好的一个，它是B与C的对换构成。

前两步计算同例2.8的前两步相同，但第3步同例2.8的第3步不同，因为根据禁忌表中的条件，禁忌选取由（ABCED）经BC对换后的解（ABCED）。

由此看出禁忌对换的范围要大于例2.8只对简单解禁忌的范围。

例2.9的邻域定义和禁忌决定了：

当一对元素X和y被禁忌后，包含两个元素的两种对换X与Y交换和Y与X交换，如禁忌B和C对换后，禁忌C与B对换和B与C对换。

禁忌C与B对换的出发点是：

上一步已经对换的两个元素不能再对换回去，以免还原到原有的解，还以例2.9为例，假设在例2.9问题中，某一步得到解为（ABCDE），迭代一步得到xnow）=（ABCDE）时，此时，应该考虑禁忌C与B的对换，否则，可能回到（ABCDE），禁忌B与C对换的出发点是：

上一步已经对B与C的对换进行了分析和评价，希望搜索有较大的遍历性，因此，我们不再考虑B与C的对换，即禁忌这个对换。

在有些情况下，更细地将一对元素X与Y对换分成X与Y对换和Y与X对换两种情形，即考虑对换的方向，因此，我们可以考虑只禁忌一个方向的对换，如X与Y的对换或Y与X的对换。

例2.10（例2.9续）以第三种目标值的变化情形来继续观察例2.9.II只记忆三组元素（解及其目标值），从2-otp邻域N（II，xnow）中选出最佳的五个元素为候选集Can.N（xnow）中选一个目标最佳的解xbest初始解xnow=xo=（ABCDE）

由于函数值43受禁,选候选集中不受禁的最佳函数值44的状态.

在此例中,采用禁忌目标值的方法所禁忌的范围比例2.8和例2.9的受禁范围更大,这在这一例中明显地体现.

所谓禁忌就是禁止重复前面达到局部最优的状态,由于计算过程中解的状态在不断地变化,因此我们对造成状态的变化的对象进行禁忌,上面已经讨论,状态变化的主要因素归结一种形式,简单的解的变化.

针对三种不同的状态变化方式,例2.8、例2.9和例2.10体现了禁忌搜索算法在计算中的不同，实际应用中，应根据具体问题采用一种方法，从上面示例的计算中也可以看出，解的简单变化比解的分量变化和目标值变化的受禁忌范围要小，这可能造成计算时间的增加，但它也给予了较大的搜索范围。

解分量的变化和目标值变化的禁忌范围要大，这减少了计算的时间，可能引发的问题是禁忌的范围太大以至陷在局部最优点。

由此可以得知，禁忌搜索算法中的技术很强，因为NP-hard问题不可能奢望计算得到最优解，在算法的构造和计算的过程中，一方面要求尽量少的占用机器内存，这就要求禁忌长度、候选集合尽量小，正好相反，禁忌长度过短造成搜索的循环，候选集合过小造成过早地陷入局部最优。

5、禁忌长度的确定

禁忌长度是被禁对象不允许选取的迭代次数，一般是给被禁对象X一个数（禁忌长度）t，要求对象X在t步迭代内被禁，在禁忌表中采用tabu（X）=t记忆，每迭代一步，该项指标做运算tabu（X）=t-1，直到tabu（X）=0时解禁。

于是，我们可将所有元素分成两类，被禁元素和自由元素，有关禁忌长度t的选取，可以归纳为下面几种情况：

（1）t为常数,如t=10,t=

其中n为邻居的个数,这种规则容易在算法中实现.

（2）t∈[tmin,tmix],此时t是可以变化的数,它的变化是依据被禁对象的目标值和邻域的结构,此时tmin,tmix是确定的,确定tmin,tmix的常用方法是根据问题的规模T,限定变化区间[a

β

]（0＜a＜β，也可用邻域中邻居的个数n确定变化区间[a

，β

]（0＜a＜β）当给定了变化区间,确定t的大小主要依据实际问题、实验和设计者的经验，如从直观可见，当函数值下降较大时，可能谷较深，欲跳出局部最优，希望被禁的长度较大。

（3）tmin,tmix的动态选取，有的情况下，用tmin,tmix的变化能达到更好的解，它的基本思想同

（2）类似。

禁忌长度的选取同实际问题、实验和设计者的经验有紧密的联系，同时它决定了计算的复杂性，过短会造成循环的出现，如f

（1）-1，f

（2）=3.5；

f（3）=2.5，f（4）=2,f（5）=3，f（6）=6，极端情况禁忌长度是1，邻域为相距不超过1的整数点，一旦陷入局部最优点x=4，则出现循环而无法跳出局部最优，过长又造成计算时间较长。

上面

（2）中给出的区间估计参数都是一些经验的估计。

6、候选集合的确定

候选集合由邻域中的邻居驵成，常规的方法是从邻域中选择若干个目标值或评价值最佳的邻居人选，如上面的TSP中采用2opt邻域定义，一个状态的邻域中菜有C2n个邻居，计算目标值后，例2.8、例2.9和例2.10选择五个目标值最佳的邻居人选。

有时认为上面的计算量还是太大，则不在邻域中所有邻居中选择，而是在邻域中的一部分中选择若干个目值或评价值最佳的状态入选。

也可以用随机选取的方法实现部分邻居的选取。

3.2评价函数

评价函数是候选集合元素选取的一个评价公式，候选集合的元素通过评价函数值来选取，以目标函数作为评价函数是比较容易理解的。

目标值是一个非常直观的指标，但有时为了方便或易于理解，会采用其他函数来取代目标函数，我们将评价函数分为基于目标函数和其他方法两类。

1、基于目标函数的评价函数

这一类主要包含以目标函数的运算所得到的评价方法，如记评价函数为p（x）目标函数为f（x），则评价函数可以采用目标函数

P（x）=f（x）

目标函数值与xnow目标值的差值

P（x）=f（x）-

（xnow）

其中xnow是上一次迭代计算的解；

目标函数值与当面最优解xbest目标值的差值

（xbest）

其中xbest是目前计算中的最好解。

基于目标函数的评价函数的形成主要通过对目标数进行简单的运算，它的变形很多。

2、其他方法

有时计算目标值比较复杂或耗时较多，解决这一问题的方法之一是采用替代的评价函数，替代的评价函数还应该反映原目标函数的一些特征，如原目标函数对应的最优点还应该是替代函数的最优点。

构造替代函数的目标是减少计算的复杂性，具体问题的替代函数构造依问题而定，它的一个例子是在生产计划中的约束批量计划与调度（Gapacitatedlotsizeplanningandscheduling）模型中的应用。

例：

2.11简单的生产计划批量问题，一个工厂安排n个产品在T个计划时段里加工，其各个产品的需求量、加工费用和加工能力等之间的关系用下面数学模型（PP）描述。

其中，Si表示生产i产品需耗的生产准备费用；

Hi表示单位i产品需耗的库存费用；

Pi表示生产单位i产品需耗的费用；

Xn表示第t时段，i产品的生产批量；

Iit表示第t时段，i产品的库存量；

Dit表示第t时段，i产品的外部需求量；

ai表示生产单位i产品需耗的资源量；

Ct表示i时段能力的提供量；

上面模型中Xn，Iit为决策变量，所有参数为非负值，目标（2.1）要求生产，生产准备有库存费用三项费用和最小，（2.2）为外部需求、生产和库存之间的平衡关系，（2.3）为资源约束，要求每个时段生产占用的能力不超过可提供的能力，PP模型是一个混合整数规划问题，因为yit取0.1两个值，当Yn=（yit）的值选定后，PP模型为一个线性规划问题，对应的最优目标值为Z（Y0）。

这样，禁忌搜索算法可以只将（yit）看成决策变量进行计算求解，如果采用基于目标函数的评价函数方法，对应每一个Yn-（yit）要解一个线性规划问题，虽说线性规划问题有多项式时间的最优算法，但对每一个给定的Y0求解一次Z（Y0）还是很费时的，一个简单位替代方法是对给定的Y0，用启发式的算法求解PP，其本思想是根据Y0、Dit和Ct安排各时段的生产（可参见文献[4]），最后得到一个启发式算法的目标值ZH（Y0），以此为评价函数值。

求解的基本思想是：

当没有资源约束（2.3）时，PP模型存在一个最优解满足

当增加（2.3）资源约束后，从最后一个时段T开始按资源约束逐个时段验证解（2.5）是否满足（2.3），当不满足时，将超出资源约束的部分前移一个时段加工，如此修正，最后若第一个时段资源不足时，则认为无可行解，此时目标值记为充分大的一个数，若可