第七章 高级搜索.ppt

1、第七章 高级搜索,主要内容,局部搜索方法 模拟退火算法 遗传算法,7.1 基本概念,优化与组合优化问题,很多问题属于优化问题，或者可以转化为优化问题 如TSP问题，皇后问题,优化问题的描述,设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。 如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。,算法的时间复杂度,对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，就难于求解了。 常用的算法复杂度函数,时间复杂性函

2、数比较（10亿次/秒）,一些难的组合优化问题,旅行商问题 背包问题 装箱问题 .寻求在可以接受的时间内得到满意解的方法,邻域的概念,邻域，简单的说就是一个点附近的其他点的集合。 在距离空间，邻域就是以某一点为中心的圆。 组合优化问题的定义： 设D是问题的定义域，若存在一个映射N，使得：则称N(S)为S的邻域。,例：皇后问题,S=Si表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。 如四皇后问题的一个解：S=(2, 4, 1, 3),定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。例：当S = (2, 4, 1, 3)时，其邻域为： N(S) = (4,

3、 2, 1, 3), (1, 4, 2, 3), (3, 4, 1, 2), (2, 1, 4, 3), (2, 3, 1, 4), (2, 4, 3, 1),例：旅行商问题,用一个城市的序列表示一个可能的解。 通过交换两个城市的位置获取S的邻居 例：简单交换方法设S = (x1, x2, xi-1, xi, xi+1, , xj-1, xj, xj+1, , xn) 则通过交换xi和xj两个城市的位置可以得到S的一个邻居：S = (x1, x2, xi-1, xj, xi+1, , xj-1, xi, xj+1, , xn),x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+

4、1,x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,例：逆序交换方法 设xi、xj是选取的两个城市，所谓的逆序交换方式是指，通过逆转xi、xj两个城市之间的城市次序来得到S的邻居。 设：S = (x1, x2, xi-1, xi, xi+1, , xj-1, xj, xj+1, , xn) 则：S = (x1, x2, xi-1, xi, xj-1, x j-2, xi+1, xj, xj+1, , xn),x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,7.2 局部搜索算法,基本

5、思想：在搜索过程中，始终向着离目标最接近的方向搜索。 目标可以是最大值，也可以是最小值。 在后面的介绍中，如果没有特殊说明，均假定是最小值。,局部搜索算法（Local Search） 1，随机的选择一个初始的可能解x0D，xb=x0，P=N(xb)； 2，如果不满足结束条件，则 3，Begin 4， 选择P的一个子集P，xn为P中的最优解 5， 如果f(xn) f(xb)，则xb xn，P = N(xb)，转2；f(x)为指标函数。 6， 否则P = P P，转2。 7，End 8，输出计算结果 9，结束,例：5城市旅行商问题,A,B,C,D,E,7,13,6,10,7,10,10,9,6,5

6、,设初始的可能解：x0 = (a, b, c, d, e) f(xb) = f(x0) = 38 通过交换两个城市获得领域P = (a, c, b, d, e), (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d) 设每次随机从P中选择一个邻居。,第一次循环,从P中选择一个元素， 假设xn = (a, c, b, d, e), f(xn) = 42, f(xn) f(xb), P = P xn = (a, d, c, b, e), (a, e, c, d, b), (a, b,

7、d, c, e), (a, b, e, d, c), (a, b, c, e, d),第二次循环,从P中选择一个元素， 假设xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(xb), P = P xn = (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d),第三次循环,从P中选择一个元素， 假设xn = (a, e, c, d, b), f(xn) = 44, f(xn) f(xb), P = P xn = (a, b, d, c, e), (a, b, e, d, c), (a

8、, b, c, e, d),第四次循环,从P中选择一个元素， 假设xn = (a, b, d, c, e), f(xn) = 44, f(xn) f(xb), P = P xn = (a, b, e, d, c), (a, b, c, e, d),第五次循环,从P中选择一个元素， 假设xn = (a, b, e, d, c), f(xn) = 34, f(xn) f(xb), xb = (a, b, e, d, c), P = (a, e, b, d, c), (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e),

9、 (a, b, e, c, d),第六次循环,从P中选择一个元素， 假设xn = (a, e, b, d, c), f(xn) = 44, f(xn) f(xb), P = P xn = (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d),第七次循环,从P中选择一个元素， 假设xn = (a, d, e, b, c), f(xn) = 39, f(xn) f(xb), P = P xn = (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d

10、, e), (a, b, e, c, d),第八次循环,从P中选择一个元素， 假设xn = (a, c, e, d, b), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d),第九次循环,从P中选择一个元素， 假设xn = (a, b, d, e, c), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, c, d, e), (a, b, e, c, d),第十次循环,从P中选择一个元素， 假设xn = (a, b, c, d, e),

11、f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, e, c, d),第十一次循环,从P中选择一个元素， 假设xn = (a, b, e, c, d), f(xn) = 41, f(xn) f(xb), P = P xn = P等于空，算法结束， 得到结果为xb = (a, b, e, d, c), f(xb) = 34。,存在的问题,局部最优问题,解决方法,每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，而指标函数差的点，被选中的概率比较小。,选择概率的计算,设求最大值：,选择概率的计算,当求最小值

12、时：,局部搜索算法1（Local Search 1） 1，随机的选择一个初始的可能解x0D，xb=x0，P=N(xb) 2，如果不满足结束条件，则 3，Begin 4， 对于所有的xP计算指标函数f(x)，并按照式（3）或者式（4）计算每一个点x的概率 5， 依计算的概率值，从P中随机选择一个点xn，xb xn，P = N(xb)，转2 6，End 7，输出计算结果 8，结束,存在的问题,步长问题,解决方法,变步长,局部搜索算法2（Local Search 2） 1，随机的选择一个初始的可能解x0D，xb=x0，确定一个初始步长计算P=N(xb) 2，如果不满足结束条件，则 3，Begin 4

13、， 选择P的一个子集P，xn为P中的最优解 5， 如果f(xn) f(xb)，则xb xn 6， 按照某种策略改变步长，计算P = N(xb)，转2 7， 否则P = P P，转2。 8，End 9，输出计算结果 10，结束,存在问题,起始点问题,A,B,全局最大值,局部最大值,解决方法,随机的生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。,局部搜索算法3（Local Search 3） 1，k = 0 2，随机的选择一个初始的可能解x0D，xb=x0，P=N(xb) 3，如果不满足结束条件，则 4，Begin 5， 选择P的一个

14、子集P，xn为P中的最优解 6， 如果f(xn) f(xb)，则xb xn，P = N(xb)，转3 7， 否则P = P P，转3。 8，End 9，k = k+1 10，如果k达到了指定的次数，则从k个结果中选择一个最好的结果输出，否则转（2） 11，输出结果 12，结束,多种方法的集成,以上几种解决方法可以结合在一起使用，比如第一、第二种方法的结合，就产生了我们将在后面介绍的模拟退火方法。,皇后搜索算法（Queen Search） 1，随机地将n个皇后分布在棋盘上，使得棋盘的每行、每列只有一个皇后。 2，计算皇后间的冲突数conflicts。 3，如果冲突数conflicts等于0，则转

15、（6） 4，对于棋盘上的任意两个皇后，交换他们的行或者列，如果交换后的冲突数conflicts减少，则接受这种交换，更新冲突数conflicts，转3。 5，如果陷入了局部极小，既交换了所有的皇后后，冲突数仍然不能下降，则转1。 6，输出结果 7，结束。,不同规模下皇后问题的 平均求解时间,7.3 模拟退火算法,是局部搜索算法的一种扩展 最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。 基本思想是借用金属的退化过程改进局部搜索算法,固体退火过程,溶解过程：随着温度的不断上升，粒子逐渐脱离开其平衡位置，变得越来越自由，直

16、到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。 退火过程：随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。,粒子不同的排列结构，对应着不同的能量水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0（绝对温度）时，系统的能量将趋于最小值。,如果以粒子的排列或者相应的能量来表达固体所处的状态，在温度T下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍了系统准确落入低能

17、状态。,Metropolis准则,从状态i转换为状态j的准则： 如果E(j)E(i)，则状态转换被接受； 如果E(j)E(i)，则状态转移被接受的概率为： 其中E(i)、E(j)分别表示在状态i、j下的能量，T是温度，K0是波尔兹曼常数。,在给定的温度T下，当进行足够多次的状态转换后，系统将达到热平衡。此时系统处于某个状态i的概率由波尔兹曼（Boltzmann）分布给出：（6）其中 为归一化因子，S是所有可能状态的集合。,考察一下式（6）随温度T的变化情况： 同一温度下，两个能量不同的状态 高温下的情况 低温下的情况 当温度下降时的情况,在给定的温度T下，设有i、j两个状态，E(i)E(j)

18、：即在任何温度T下，系统处于能量低的状态的概率大于处于能量高的状态的概率。,由于E(i)E(j)，所以该项小于1,当温度趋于无穷时：其中|S|表示系统所有可能的状态数。 当温度很高时，系统处于各个状态的概率基本相等，接近于平均值，与所处状态的能量几乎无关。,当温度趋于0时 ：设Sm表示系统最小能量状态的集合，Em是系统的最小能量。上式分子、分母同乘以,当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处于其他状态的概率为0。以概率1达到能量最小的状态。,当温度上升或下降时：,系统落入低能量状态的概率随着温度的下降单调上升，而系统落入高能量状态的概率随着温度的下降单调下降。,在高

19、温下，系统基本处于无序的状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率大于系统落入高能量状态的概率，这样在同一温度下，如果系统交换的足够充分，则系统会趋向于落入较低能量的状态。随着温度的缓慢下降，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减少，使得系统各状态能量的期望值随温度的下降单调下降，而只有那些能量小于期望值的状态，其概率才随温度下降增加，其他状态均随温度下降而下降。因此，随着能量期望值的逐步下降，能量低于期望值的状态逐步减少，当温度趋于0时，只剩下那些具有最小能量的状态，系统处于其他状态的概率趋近于0。因此最终系统将以概率1处于具有最小能量的

20、一个状态。,达到最小能量状态的三个条件,（1）初始温度必须足够高； （2）在每个温度下，状态的交换必须足够充分； （3）温度T的下降必须足够缓慢。,组合优化问题与退火过程的类比,1，随机选择一个解i，k=0，t0=Tmax（初始温度），计算指标函数f(i)。 2，如果满足结束条件，则转（15）。 3，Begin 4， 如果在该温度内达到了平衡条件，则转（13）。 5， Begin 6， 从i的邻域N(i)中随机选择一个解j。 7， 计算指标函数f(j)。 8， 如果f(j)j)Random(0, 1)，则i=j，f(i)=f(j)。 11， 转（4） 12， End 13， tk+1=Drop

21、(tk)，k=k+1。 14，End 15，输出结果。 16，结束。,算法中的问题,初始温度的选取 内循环的结束条件，即每个温度状态交换何时结束 外循环的结束条件，即温度下降到什么时候结束 温度的下降方法,在模拟退火过程中，给定温度下状态（解）的转移可以看作是一个马尔可夫链。对于任意两个状态i和j，我们用Pt(i, j)表示温度t下，从状态i转移到状态j的一步转移概率，则有：其中：Gt(i,j) 是产生概率，表示从状态i产生状态j的概率。At(i,j) 是接受概率，表示在状态i产生状态j后，接受状态j的概率。,定理7.1,满足条件的Gt(i,j)、At(i,j) 举例：,说明：条件2的后半部分

22、除外，该条件与具体的问题有关。,定理7.2： 在定理1的条件下，如果对于任意两个状态 有：则有：,定理7.3（放宽了定理1的条件）Gt(i,j)、At(i,j)满足定理1中除条件（2）以外的所有其他条件，并且： 1，对于任意两个状态i、j，它们相互为邻居或者相互都不为邻居； 2，对于任意i，Gt(i,j)满足：3，状态空间S对于邻域是连通的；则与模拟退火算法相伴的时齐马尔可夫链存在平稳分布，其分布概率为：,算法的实现,（1）初始温度t0； （2）温度t的衰减函数，即温度的下降 方法； （3）算法的终止准则，用终止温度tf或 者终止条件给出； （4）每个温度t下的马尔可夫链长度Lk。,起始温度的

23、选取（1）,一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等，也就是接受概率P0近似等于1。在Metropolis准则下，即要求：,如果我们给定一个比较大的接受概率P0，则：,其中， 可以有以下估计方式：,起始温度的选取（2）,假设在t0下随机的生成一个状态序列，分别用m1和m2表示指标函数下降的状态数和指标函数上升的状态数， 表示状态增加的平均值。则m2个状态中，被接受的个数为：,所以平均接受率为： 求解有：,起始温度的选取（3）,模拟固体的升温过程： （1）给定一个希望的初始接受概率P0，给定一个较低的初始温度t0，比如t01； （2）随机的产生一个状态序列，并计算该序列的接收

24、率：如果接收率大于给定的初始接受概率P0，则转（4）； （3）提高温度，更新t0，转（2）； （4）结束。,温度的下降方法（1）,等比例下降,温度的下降方法（2）,等值下降,温度的下降方法（3）,由定理1我们知道，在一定的条件下，与模拟退火算法相伴的时齐马尔可夫链存在平稳分布。如果温度每次下降的幅度比较小的话，则相邻温度下的平稳分布应该变化不大，也就是说，对于任意一个状态i，相邻温度下的平稳分布应满足：,一个充分条件是：,两边取对数，并整理得：用 代替 可得温度的衰减函数：,每一温度下的停止准则（1）,固定长度方法 在每一个温度下，都使用相同的Lk。Lk的选取与具体的问题相关，一般与邻域的大小

25、直接关联，通常选择为问题规模n的一个多项式函数。,每一温度下的停止准则（2）,基于接受率的停止准则 ： 规定一个接受次数R，在某一温度下，只有被接受的状态数达到R时，在该温度下的迭代才停止，转入下一个温度。 规定一个状态接受率R，R等于该温度下接受的状态数除以总生成的总状态数。如果接受率达到了R，则停止该温度下的迭代，转入下一个温度。 在迭代的过程中，若干相邻的状态称为“一代”，如果相邻两代的解的指标函数差值小于规定的值的话，则停止该温度下的迭代。,算法的终止原则 （1）,零度法设定一个正常数e，当时tke时，算法结束。,算法的终止原则 （2）,循环总控制法 给定一个指定的温度下降次数K，当温

26、度的迭代次数达到K次时，则算法停止。,算法的终止原则 （3）,无变化控制法如果在相邻的n个温度中，得到的解的指标函数值无任何变化，则说明算法已经收敛。,算法的终止原则 （4）,接受概率控制法给定一个小的概率值p，如果在当前温度下除了局部最优状态外，其他状态的接受概率小于p值，则算法结束。,算法的终止原则 （5）,领域平均概率控制法 设大小为N的一个领域，在邻域内一个状态被接受的平均概率为1/N。设f0、f1为该领域中的局部最优值和局部次最优值。则次最优解是除了局部最优解以外接受概率最大的，其接受概率为：,如果该概率值小于平均值1/N时，即：可以认为从局部最优解跳出的可能性已经很小了，因此可以终

27、止算法。此时的终止温度tf为：,算法的终止原则 （6）,相对误差估计法 设温度t时指标函数的期望值为：则当终止温度1时，由泰勒展开近似有：,由于：所以可用下式估计当前解与最优解之间的误差 ：,或者使用相对于 的相对误差：,实际计算时：其中：,应用举例旅行商问题,解的表示： n个城市的任何一种排列均是问题的一个可能解，表示为:指标函数(能量函数) 其中,新解的产生 采用第一节介绍的两个城市间的逆序交换方式得到问题的一个新解。设当前解是 ，被选中要逆序交换的城市是第u和第v个到访的城市，uv。则逆序排列u和v之间的城市，得到问题的新解为：则两个路径的距离差为：,新解的接受准则,初始参数的确定 康立

28、山等人的方法： 初始温度t0=280；在每个温度下采用固定的迭代次数，Lk=100n，n为城市数； 温度的衰减系数0.92，即tk+1=0.92tk； 算法的停止准则为：当相邻两个温度得到的解无任何变化时算法停止。,Nirwan Ansari和Edwin Hou的方法： 初始温度t0是这样确定的：从t0=1出发，并以t0=1.05t0对t0进行更新，直到接受概率大于等于0.9时为止，此时得到的温度为初始温度； 在每个温度下采用固定的迭代次数，Lk=10n，n为城市数； 温度的衰减系数0.95，即tk+1=0.95tk；,10城市旅行商问题求解结果,20城市旅行商问题求解结果,7.4 遗传算法,

29、达尔文进化论：“物竞天择、适者生存” 70年代由美国的密执根大学的Holland教授首先提出 近年来，遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。,生物进化与遗传算法,生物进化与遗传算法之间的对应关系,遗传算法的三个主要操作,选择 交配 变异,“轮盘赌”法 ：设群体的规模为N，F(xi)(i=1, ., N)是其中N个染色体的适应值。则第i个染色体被选中的概率由下式给出：,选择,模拟“轮盘赌” 算法,（1）r=random(0, 1)，s=0，i=0； （2）如果sr，则转（4）； （3）s=s+p(xi)，i=i+1, 转（2） （4）xi即为被选中的染色体，输出i （5）

30、结束。,“确定性”法 对于规模为N的群体，一个选择概率为p(xi)的染色体xi被选择次数的期望值e(xi)： 对于群体中的每一个xi，首先选择 次。这样共得到 个染色体。然后按照 从大到小对染色体排序，依次取出 个染色体，这样就得到了N个染色体。,交配,交配发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色体采用二进制形式编码时，交配过程是以这样一种形式进行的：,a1 a2 . ai ai+1 . an b1 b2 . bi bi+1 . bn,a1 a2 . ai bi+1 . bn b1 b2 . bi ai+1 . an,交配

31、前,交配后,交配位置,变异,变异发生在染色体的某一个基因上，当以二进制编码时，变异的基因由0变成1，或者由1变成0。如对于染色体x=11001，如果变异位发生在第三位，则变异后的染色体变成了y=11101。,遗传算法 （1）给定群体规模N，交配概率pc和变异概率pm，t0； （2）随机生成N个染色体作为初始群体； （3）对于群体中的每一个染色体xi分别计算其适应值F(xi)； （4）如果算法满足停止准则，则转（10）； （5）对群体中的每一个染色体xi计算概率； （6）依据计算得到的概率值，从群体中随机的选取N个染色体，得到种群；,（7）依据交配概率pc从种群中选择染色体进行交配，其子代进入新

32、的群体，种群中未进行交配的染色体，直接复制到新群体中； （8）依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体； （9）用新群体代替旧群体，t=t+1，转（3）； （10）进化过程中适应值最大的染色体，经解码后作为最优解输出； （11）结束。,例：求函数的最大值,其中x为0, 31间的整数 编码：采用二进制形式编码由于x的定义域是0, 31间的整数，刚好可以用5位二进制数表示，因此可以用5位二进制数表示该问题的解，即染色体。如00000表示x0，10101表示x21，11111表示x31等,适应函数： 直接使用函数f(x)作为适应函数。 假设群体的规模N4，

33、交配概率pc100，变异概率pm1。 设随机生成的初始群体为：01101，11000，01000，10011 选择方法：“确定性”法,第0代情况表,第0代种群的交配情况,第1代情况表,第1代种群的交配情况,第2代种群的交配情况,最大适应值、平均适应值进化曲线,遗传算法的特点,（1）遗传算法是一个随机搜索算法，适用于数值求解具有多参数、多变量、多目标等复杂的最优化问题。 （2）遗传算法对待求解问题的指标函数没有什么特殊的要求，比如不要求诸如连续性、导数存在、单峰值假设等。甚至于不需要显式的写出指标函数。 （3）在经过编码以后，遗传算法几乎不需要任何与问题有关的知识，唯一需要的信息是适应值的计算。

34、也不需要使用者对问题有很深入的了解和求解技巧，通过选择、交配和变异等简单的操作求解复杂的问题，是一个比较通用的优化算法。 （4）遗传算法具有天然的并行性，适用于并行求解。,收敛性定理：如果在代的进化过程中，遗传算法每次保留到目前为止的最好解，并且算法以交配和变异为其随机化操作，则对于一个全局最优化问题，当进化代数趋于无穷时，遗传算法找到最优解的概率为1。,遗传算法的实现问题,编码 评价 适应函数 交配规则 停止条件,编码举例：十杆桁架问题,100 kg,100 kg,30,30,30,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,假设每个杆的截面积在0.1至10之间，在该范围内

35、，有16个可能的取值。这样我们可以用4位二进制向量表示截面积的可能取值，其中0000表示0.1，1111表示10，余下的14位二进制向量表示其他的截面积的可能取值。这样10个杆，共用40位二进制向量表示一个十杆桁架问题的染色体。例：0010 1110 0001 0011 1011 0011 1111 0011 0011 1010,编码举例：旅行商问题,对于n个城市的旅行商问题，可以用一个矩阵来表示一个可能解。如果按行展开该矩阵，则该可能解可以用一个44的二进制向量表示为：0100100000010010,二进制表示存在的问题,采用这样的表示方法，对于n城市的旅行商问题，至少需要用nn位二进制向

36、量表示一个可能的旅行路线。一个nn位二进制向量，所有可能的编码个数为 ，而一个对称的n城市旅行商问题的可能解个数为n!/2，只占编码个数非常小的比例。以n10为例，编码个数为可能解个数的7.01023倍。可能解在整个状态空间中，是非常稀疏的，交配和变异所产生的是大量的非可能解。,遗传算法的评价,定理7.4给出了当进化代数趋于无穷时，遗传算法找到最优解的概率为1。即保证了遗传算法的收敛性。但在实际计算时，希望随时了解遗传算法的进展情况，监视算法的变化趋势。,当前最好法,该方法在每一代进化过程中，记录得到的最好解，通过最好解的变化，了解算法的变化趋势。不同的算法之间，也可以通过该最好解的变化情况进

37、行横向比较。,在线比较法,该方法用当前代中染色体的平均指标函数值来刻划算法的变化趋势。计算方法如下：其中T为当前代中染色体的个数 。,离线比较法,该方法与在线比较法有些相似，但是用进化过程中每代最好解的指标函数值的平均值，来评价算法的进化过程。计算方法如下：其中T是到目前为止的进化代数，f*(t)是第t代中，染色体的最好指标函数值。,适应函数,一般情况下，我们可以直接选取问题的指标函数作为适应函数。如求函数f(x)的最大值，就可以直接采用f(x)为适应函数。但在有些情况下，函数f(x)在最大值附近的变化可能会非常小，以至于他们的适应值非常接近，很难区分出那个染色体占优。在这种情况下，希望定义新

38、的适应函数，要求该适应函数与问题的指标函数具有相同的变化趋势，但变化的速度更快。,非线性加速适应函数,其中f(x)是问题的指标函数，fmax是当前得到的最优指标函数值，M是一个充分大的数。,线性加速适应函数,上式中的第一个方程表示变换前后的平均值不变，第二个方程表示将当前的最优值放大为平均值的M倍。,二进制编码的交配规则,双亲双子法,a1 a2 . ai ai+1 . an b1 b2 . bi bi+1 . bn,a1 a2 . ai bi+1 . bn b1 b2 . bi ai+1 . an,交配前,交配后,交配位置,变化交配法 1 1 0 1 0 0 1 1 1 0 0 0 1 0由于

39、两个父染色体的前三位完全一致，因此当交配位选择在前三位时，其子染色体将与两个父染色体完全一致。变化交配法就是在随机产生交配位时，排除掉这样的交配位。,多交配位法 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1,整数编码的交配规则,下面以旅行商问题为例，介绍几种整数编码的交配规则。,常规交配法,随机选取一个交配位，子代1交配位之前的基因选自父代1交配位之间的基因，交配位之后的基因，从父代2中按顺序选取那些没有出现过的基因。交配位 交配位父代1：1 2 3 4 5 6 7 8 子代1：1 2 3 4 5 7 8 6父代2：5 2 1

40、7 3 8 4 6 子代2：5 2 1 7 3 4 6 8,基于次序的交配法,父代1: 1 2 3 4 5 6 7 8 9 10 父代2: 5 9 2 4 6 1 10 7 3 8 所选位置: * * * *父代1中与所选位置相对应的数字为：2、3、5、8。从父代2中找出这些数字，并去除它们，其中b表示空位置：父代2: b 9 b 4 6 1 10 7 b b用2、3、5、8依次填入上述父代2的空位置中，得到子代1：子代1: 2 9 3 4 6 1 10 7 5 8,基于位置的交配法,首先随机产生一组位置。对于这些位置上的基因，子代1从父代2中直接得到，子代1的其他位置的基因，按顺序从父代1中

41、选取那些不相重的基因。子代2也类似处理。如： 父代1：1 2 3 4 5 6 7 8 9 父代2：5 9 2 4 6 1 7 3 8 * * * *子代1：1 9 2 4 6 5 7 3 8,基于部分映射的交配法,对于两个选定的父代染色体父代1和父代2，随机产生两个位置，两个父代在这两个位置之间的基因产生对应对，然后用这种对应对分别去替换两个父代的基因，从而产生两个子代。父代1：2 6 4 3 8 1 5 7 9 父代2：8 5 1 7 6 2 4 3 9子代1：1 8 4 7 6 2 5 3 9,对应对：3:7 8:6 1:2,变异规则,二进制编码中的变异 整数编码中的变异,二进制编码中的变

42、异,当问题以二进制编码形式表示时，随机的产生一个变异位，被选中的基因由“0”变为“1”，或者由“1”变为“0”。 变异前 变异后1 1 0 1 1 0 1 1 1 0 1 0 0 1 变异位,整数编码中的变异,基于位置的变异 随机的产生两个变异位，然后将第二个变异位上的基因移动到第一变异位之前。 2 1 3 6 4 5 7 2 4 1 3 6 5 7 变异前 变异后,基于次序的变异 随机的产生两个变异位，然后交换这两个变异位上的基因。 2 1 3 6 4 5 7 2 4 3 6 1 5 7 变异前 变异后,打乱变异 随机选取染色体上的一段，然后打乱在该段内的基因次序。 2 1 3 6 4 5 7 2 4 3 6 1 5 7 变异前 变异后逆序交换方式可以认为是打乱变异的一个特例。,性能评价,如何对遗传算法的性能进行评价是一件很困难的事情，为此需要确定性能度量和一些具有代表性的函数。一般可以用达到最优点时性能函数值的平均计算次数和计算所需要的时间来进行度量。一些学者给出了如下的测试函数集，这些函数或者是多峰值的，或者是不连续的，或者是具有一定的噪声的，对于求解他们的最小值具有一定的难度。,测试函数举例,高级搜索小结,局部搜索 模拟退火算法 遗传算法,