第七章人工智能蔡自兴

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

输入量n复杂性函数10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.0ms1.1s18.3min4.0世纪n!3.6ms77.1年8.4×1013世纪2.6×1029世纪3.0×10139世纪时间复杂性函数比较（10亿次/秒）一些难的组合优化问题旅行商问题背包问题装箱问题...寻求在可以接受的时间内得到满意解的方法邻域的概念邻域，简单的说就是一个点附近的其他点的集合。在距离空间，邻域就是以某一点为中心的圆。组合优化问题的定义：设D是问题的定义域，若存在一个映射N，使得：则称N(S)为S的邻域。例：皇后问题S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。如四皇后问题的一个解：S=(2,4,1,3)

Q

QQ

Q

定义映映射N为棋棋盘上上任意意两个个皇后后的所所在行行或列列进行行交换换，即即S中中任意意两个个元素素交换换位置置。例：当当S=(2,4,1,3)时，，其邻邻域为为：N(S)={(4,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)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+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,xj-2…,xi+1,xj,xj+1,……,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+17.2局局部搜搜索算法法基本思想想：在搜搜索过程程中，始始终向着着离目标标最接近近的方向向搜索。。目标可以以是最大大值，也也可以是是最小值值。在后面的的介绍中中，如果果没有特特殊说明明，均假假定是最最小值。。局部搜索索算法（（LocalSearch））1，随机的选选择一个个初始的的可能解解x0∈D，xb=x0，P=N(xb)；2，如果果不满足足结束条条件，则则3，Begin4，选择P的一个子子集P'，xn为P'中的最优优解5，如如果果f(xn)<f(xb)，则xb＝xn，P=N(xb)，转2；f(x)为指标函函数。6，否否则则P=P––P'，转2。7，End8，输出计算算结果9，结束束例：5城城市旅行行商问题题●●●●●ABCDE71361071010965设初始的的可能解解：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,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,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),(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,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),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。存在的问题局部最优问题题解决方法每次并不一定定选择邻域内内最优的点，，而是依据一一定的概率，，从邻域内选选择一个点，，指标函数优优的点，被选选中的概率比比较大，而指指标函数差的的点，被选中中的概率比较较小。选择概率的计计算设求最大值：：选择概率的计计算当求最小值时时：局部搜索算法法1（LocalSearch1）1，随机的选择一一个初始的可可能解x0∈D，xb=x0，P=N(xb)2，如果不满满足结束条件件，则3，Begin4，对于所有的的x∈P计算指标函函数f(x)，，并按照式（（3）或者者式（4））计算每一一个点x的概率5，依依计算的的概率值，，从P中随机选择择一个点xn，xb＝xn，P=N(xb)，转26，End7，输出计算结结果8，结束存在的问题题步长问题初始值搜索到的最优解解决方法变步长初始值搜索到的最优解局部搜索算算法2（LocalSearch2）1，随机的选择择一个初始始的可能解解x0∈D，xb=x0，确定一个初初始步长计计算P=N(xb)2，如果不不满足结束束条件，则则3，Begin4，选择P的一个子集集P'，xn为P'中的最优解解5，如如果f(xn)<f(xb)，则xb＝xn6，按照某种策策略改变步步长，计算算P=N(xb)，转27，否否则P=P–P'，转2。8，End9，输出计算结结果10，结束束存在问题起始点问题题AB全局最大值值局部最大值值解决方法随机的生成成一些初始始点，从每每个初始点点出发进行行搜索，找找到各自的的最优解。。再从这些些最优解中中选择一个个最好的结结果作为最最终的结果果。局部搜索算算法3（LocalSearch3）1，k=02，随机的选择择一个初始始的可能解解x0∈D，xb=x0，P=N(xb)3，如果不不满足结束束条件，则则4，Begin5，选择P的一个子集集P'，xn为P'中的最优解解6，如如果f(xn)<f(xb)，则xb＝xn，P=N(xb)，转37，否否则P=P–P'，转3。8，End9，k=k+110，如果k达到了指定定的次数，，则从k个结果中选选择一个最好好的结果输输出，否则则转（2））11，输出出结果12，结束束多种方法的的集成以上几种解解决方法可可以结合在在一起使用用，比如第第一、第二二种方法的的结合，就就产生了我我们将在后后面介绍的的模拟退火火方法。皇后搜索算算法（QueenSearch））1，随机地将n个皇后分布布在棋盘上上，使得棋棋盘的每行、每每列只有一一个皇后。。2，计算皇皇后间的冲冲突数conflicts。3，如果冲突数数conflicts等于0，则则转（6））4，对于棋棋盘上的任任意两个皇皇后，交换换他们的行行或者列，如如果交换后后的冲突数数conflicts减少，则接受这种种交换，更更新冲突数数conflicts，转3。5，如果陷陷入了局部部极小，既既交换了所所有的皇后后后，冲突数数仍然不能能下降，则则转1。6，输出结结果7，结束。。不同规模下下皇后问题题的

平均均求解时间间皇后数1005001000200050001000030000平均时间（秒）551228170900100007.3模模拟退火算算法是局部搜索索算法的一一种扩展最早由Metropolis在1953年提出出，Kirkpatrick等人在1983年年成功地将将模拟退火火算法用于于求解组合合优化问题题。基本思想是是借用金属属的退化过过程改进局局部搜索算算法固体退火过过程溶解过程：：随着温度的的不断上升升，粒子逐逐渐脱离开开其平衡位位置，变得得越来越自自由，直到到达到固体体的溶解温温度，粒子子排列从原原来的有序序状态变为为完全的无无序状态。。退火过程：：随着温度的的下降，粒粒子的热运运动逐渐减减弱，粒子子逐渐停留留在不同的的状态，其其排列也从从无序向有有序方向发发展，直至至到温度很很低时，粒粒子重新以以一定的结结构排列。。粒子不同的的排列结构构，对应着着不同的能能量水平。。如果退火火过程是缓缓慢进行的的，也就是是说，温度度的下降如如果非常缓缓慢的话，，使得在每每个温度下下，粒子的的排列都达达到一种平平衡态，则则当温度趋趋于0（绝绝对温度））时，系统统的能量将将趋于最小小值。如果以粒子子的排列或或者相应的的能量来表表达固体所所处的状态态，在温度度T下，固固体所处的的状态具有有一定的随随机性。一一方面，物物理系统倾倾向于能量量较低的状状态，另一一方面，热热运动又妨妨碍了系统统准确落入入低能状态态。Metropolis准则从状态i转换为状态态j的准则：如果E(j)≤≤E(i)，则状态转换换被接受；；如果E(j)＞＞E(i)，则状态转移移被接受的的概率为：：其中E(i)、、E(j)分别表示在在状态i、j下的能量，，T是温度，K＞0是波尔兹曼曼常数。在给定的温温度T下，，当进行足足够多次的的状态转换换后，系统统将达到热热平衡。此此时系统处处于某个状状态i的概概率由波尔尔兹曼（Boltzmann）分布给给出：（6）其中为为归归一化因子子，S是所所有可能状状态的集合合。考察一下式式（6）随随温度T的变化情况况：同一温度下下，两个能能量不同的的状态高温下的情情况低温下的情情况当温度下降降时的情况况在给定的温温度T下，设有i、j两个状态，，E(i)＜＜E(j)：即在任何温温度T下，系统处处于能量低低的状态的的概率大于于处于能量量高的状态态的概率。。由于E(i)＜＜E(j)，所以该项小小于1当温度趋于于无穷时：：其中|S|表示系统所所有可能的的状态数。。当温温度度很很高高时时，，系系统统处处于于各各个个状状态态的的概概率率基基本本相相等等，，接接近近于于平平均均值值，，与与所所处处状状态态的的能能量量几几乎乎无无关关。。当温温度度趋趋于于0时时：：设Sm表示示系系统统最最小小能能量量状状态态的的集集合合，，Em是系系统统的的最最小小能能量量。。上上式式分分子子、、分分母母同同乘乘以以当温温度度趋趋近近于于0时时，，系系统统以以等等概概率率趋趋近近于于几几个个能能量量最最小小的的状状态态之之一一，，而而系系统统处处于于其其他他状状态态的的概概率率为为0。。以以概概率率1达达到到能能量量最最小小的的状状态态。。当温温度度上上升升或或下下降降时时：：系统统落落入入低低能能量量状状态态的的概概率率随随着着温温度度的的下下降降单单调调上上升升，，而而系系统统落落入入高高能能量量状状态态的的概概率率随随着着温温度度的的下下降降单单调调下下降降。。在高高温温下下，，系系统统基基本本处处于于无无序序的的状状态态，，基基本本以以等等概概率率落落入入各各个个状状态态。。在在给给定定的的温温度度下下，，系系统统落落入入低低能能量量状状态态的的概概率率大大于于系系统统落落入入高高能能量量状状态态的的概概率率，，这这样样在在同同一一温温度度下下，，如如果果系系统统交交换换的的足足够够充充分分，，则则系系统统会会趋趋向向于于落落入入较较低低能能量量的的状状态态。。随随着着温温度度的的缓缓慢慢下下降降，，系系统统落落入入低低能能量量状状态态的的概概率率逐逐步步增增加加，，而而落落入入高高能能量量状状态态的的概概率率逐逐步步减减少少，，使使得得系系统统各各状状态态能能量量的的期期望望值值随随温温度度的的下下降降单单调调下下降降，，而而只只有有那那些些能能量量小小于于期期望望值值的的状状态态，，其其概概率率才才随随温温度度下下降降增增加加，，其其他他状状态态均均随随温温度度下下降降而而下下降降。。因因此此，，随随着着能能量量期期望望值值的的逐逐步步下下降降，，能能量量低低于于期期望望值值的的状状态态逐逐步步减减少少，，当当温温度度趋趋于于0时时，，只只剩剩下下那那些些具具有有最最小小能能量量的的状状态态，，系系统统处处于于其其他他状状态态的的概概率率趋趋近近于于0。。因因此此最最终终系系统统将将以以概概率率1处处于于具具有有最最小小能能量量的的一一个个状状态态。。达到最小小能量状状态的三三个条件件（1）初初始温度度必须足足够高；；（2）在在每个温温度下，，状态的的交换必必须足够够充分；；（3）温温度T的下降必必须足够够缓慢。。组合优化化问题与与退火过过程的类类比固体退火过程组合优化问题物理系统中的一个状态组合优化问题的解状态的能量解的指标函数能量最低状态最优解温度控制参数1，随随机选选择一一个解解i，k=0，t0=Tmax（初始温温度）），计计算指指标函函数f(i)。。2，如果满满足结结束条条件，，则转转（15））。3，Begin4，如果在在该温温度内内达到到了平平衡条条件，，则转转（13））。5，Begin6，从i的邻域域N(i)中随机机选择择一个个解j。7，计算指指标函函数f(j)。。8，如果f(j)<f(i)，则i=j，f(i)=f(j)，转（4）。。9，计计算算10，，如如果Pt(i=>j)>Random(0,1)，则i=j，f(i)=f(j)。11，，转（4）12，，End13，，tk+1=Drop(tk)，k=k+1。14，，End15，，输出结结果。。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的的后半半部分分除外外，该该条件件与具具体的的问题题有关关。定理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。起始温温度的的选取取（1）一个合合适的的初始始温度度，应应保证证平稳稳分布布中每每一个个状态态的概概率基基本相相等，，也就就是接接受概概率P0近似等于1。在Metropolis准则下，即即要求：如果我们给给定一个比比较大的接接受概率P0，则：其中，可可以以有以下估估计方式：：起始温度的的选取（2）假设在t0下随机的生生成一个状状态序列，，分别用m1和m2表示指标函函数下降的的状态数和和指标函数数上升的状状态数，表表示状态增增加的平均均值。则m2个状态中，，被接受的的个数为：：所以平均接接受率为：：求解有：起始温度的的选取（3）模拟固体的的升温过程程：（1）给定定一个希望望的初始接接受概率P0，给定一个较较低的初始始温度t0，比如t0＝1；（2）随机的产生生一个状态态序列，并并计算该序序列的接收收率：如果接收率率大于给定定的初始接接受概率P0，则转（4））；（3）提高高温度，更更新t0，转（2）；；（4）结束束。温度的下降降方法（1）等比例下降降温度的下降降方法（2）等值下降温度的下降降方法（3）由定理1我我们知道，，在一定的的条件下，，与模拟退退火算法相相伴的时齐齐马尔可夫夫链存在平平稳分布。。如果温度度每次下降降的幅度比比较小的话话，则相邻邻温度下的的平稳分布布应该变化化不大，也也就是说，，对于任意意一个状态态i，相邻邻温度下的的平稳分布布应满足：：一个充分条条件是：两边取对数数，并整理理得：用代代替可可得温度度的衰减函函数：每一温度下下的停止准准则（1））固定长度方方法在每一个温温度下，都都使用相同同的Lk。Lk的选取与具具体的问题题相关，一一般与邻域域的大小直直接关联，，通常选择择为问题规规模n的一个多项项式函数。。每一温度下下的停止准准则（2））基于接受率率的停止准准则：规定一个接接受次数R，在某一温度度下，只有有被接受的的状态数达达到R时，在该温温度下的迭迭代才停止止，转入下下一个温度度。规定一个状状态接受率率R，R等于该温度度下接受的的状态数除除以总生成成的总状态态数。如果果接受率达达到了R，则停止该温温度下的迭迭代，转入入下一个温温度。在迭代的过过程中，若若干相邻的的状态称为为“一代””，如果相相邻两代的的解的指标标函数差值值小于规定定的值的话话，则停止止该温度下下的迭代。。算法的终止止原则（（1）零度法设定一个正正常数e，当时tk<e时，算法结结束。算法的终止止原则（（2）循环总控制制法给定一个指指定的温度度下降次数数K，当温度的迭迭代次数达达到K次时，则算算法停止。。算法的终止止原则（（3）无变化控制制法如果在相邻邻的n个温度中，，得到的解解的指标函函数值无任任何变化，，则说明算算法已经收收敛。算法的终止止原则（（4）接受概率控控制法给定一个小小的概率值值p，如果在当前前温度下除除了局部最最优状态外外，其他状状态的接受受概率小于于p值，则算法法结束。算法的终止止原则（（5）领域平均概概率控制法法设大小为N的一个领域域，在邻域域内一个状状态被接受受的平均概概率为1/N。设f0、f1为该领域中中的局部最最优值和局局部次最优优值。则次次最优解是是除了局部部最优解以以外接受概概率最大的的，其接受受概率为：：如果该概率率值小于平平均值1/N时，即：可以认为从从局部最优优解跳出的的可能性已已经很小了了，因此可可以终止算算法。此时时的终止温温度tf为：算法的终止止原则（（6）相对误差估估计法设温度t时指标函数数的期望值值为：则当终止温温度<<1时，由泰泰勒展开近近似有：由于：所以可用下式式估计当前解解与最优解之之间的误差：：或者使用相对对于的的相对误差差：实际计算时：：其中：应用举例———旅行商问题题解的表示：n个城市的任何何一种排列均均是问题的一一个可能解，，表示为:指标函数(能能量函数)其中新解的产生采用第一节介介绍的两个城城市间的逆序序交换方式得得到问题的一一个新解。设当前解是，，被选选中要逆序交交换的城市是是第u和第v个到访的城市市，u<v。则逆序排列u和v之间的城市，，得到问题的的新解为：则两个路径的的距离差为：：新解的接受准准则初始参数的确确定康立山等人的的方法：初始温度t0=280；在每个温度下下采用固定的的迭代次数，，Lk=100n，，n为城市数；温度的衰减系系数＝0.92，即tk+1=0.92××tk；算法的停止准准则为：当相相邻两个温度度得到的解无无任何变化时时算法停止。。NirwanAnsari和EdwinHou的方法：初始温度t0是这样确定的的：从t0=1出发，并以t0=1.05××t0对t0进行更新，直直到接受概率率大于等于0.9时为止止，此时得到到的温度为初初始温度；在每个温度下下采用固定的的迭代次数，，Lk=10n，n为城市数；温度的衰减系系数＝0.95，即tk+1=0.95××tk；10城市旅行行商问题求解解结果

路径长度出现次数平均转移次数路径最优2.6919063952BCADEFGHIJ次优2.752464056BCADEGFHIJ第三2.769104053DEFGHIJCBA最差2.89854497ABCDEFHIJG20城市旅行行商问题求解解结果

路径长度出现次数平均转移次数路径最优24.387928740ACLBIQFTMEPRGSOJHDKN次优24.621678638ADCLBIQFTMEPRGSOJHKN第三25.17399902ANKDHIOJSGRPEMTFQBLC最差25.5015794AQFTMEPRGSJOIBLCDHKN7.4遗传传算法达尔文进化论论：“物竞天天择、适者生生存”70年代由美美国的密执根根大学的Holland教授首先提出出近年来，遗传传算法作为一一种有效的工工具，已广泛泛地应用于最最优化问题求求解之中。生物进化与遗遗传算法群体种群子群选择婚配变异遭淘汰的群体生物进化中的概念遗传算法中的作用环境适应函数适应性适应值函数适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程生物进化与遗遗传算法之间间的对应关系系遗传算法的三三个主要操作作选择交配变异“轮盘赌”法法：设群体的规模模为N，F(xi)(i=1,...,N)是其中N个染色体的适适应值。则第第i个染色体被选选中的概率由由下式给出：：选择x1x2x3x4x5x6模拟“轮盘赌赌”算法（1）r=random(0,1)，s=0，i=0；（2）如果s≥r，则转（4）；；（3）s=s+p(xi)，i=i+1,转（2）（4）xi即为被选中的的染色体，输输出i（5）结束。“确定性”法法对于规模为N的群体，一个个选择概率为为p(xi)的染色体xi被选择次数的的期望值e(xi)：对于群体中的的每一个xi，首先选择次次。这这样共得到个个染色体体。然后按照照从从大到到小对染色体体排序，依次次取出个个染染色体，这样样就得到了N个染色体。交配交配发生在两两个染色体之之间，由两个个被称之为双双亲的父代染染色体，经杂杂交以后，产产生两个具有有双亲的部分分基因的新的的染色体。当当染色体采用用二进制形式式编码时，交交配过程是以以这样一种形形式进行的：：a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前前交配后后交配位位置变异变异发发生在在染色色体的的某一一个基基因上上，当当以二二进制制编码码时，，变异异的基基因由由0变变成1，或或者由由1变变成0。如如对于于染色色体x=11001，如果变变异位位发生生在第第三位位，则则变异异后的的染色色体变变成了了y=11101。遗传算算法（1））给定定群体体规模模N，交配概概率pc和变异异概率率pm，t＝＝0；；（2））随机生生成N个染色色体作作为初初始群群体；；（3））对于于群体体中的的每一一个染染色体体xi分别计计算其其适应应值F(xi)；（4））如果算算法满满足停停止准准则，，则转转（10））；（5））对群群体中中的每每一个个染色色体xi计算概概率；；（6））依据据计算算得到到的概概率值值，从从群体体中随随机的的选取取N个染色色体，，得到到种群群；（7））依据据交配配概率率pc从种群群中选选择染染色体体进行行交配配，其其子代代进入入新的的群体体，种种群中中未进进行交交配的的染色色体，，直接接复制制到新新群体体中；；（8））依据据变异异概率率pm从新群群体中中选择择染色色体进进行变变异，，用变变异后后的染染色体体代替替新群群体中中的原原染色色体；；（9））用新新群体体代替替旧群群体，，t=t+1，转（3）；；（10）进进化过过程中中适应应值最最大的的染色色体，，经解解码后后作为为最优优解输输出；；（11）结结束。。例：求求函数数的最最大值值其中x为[0,31]间间的整整数编码：：采用用二进进制形形式编编码由于x的定义义域是是[0,31]间间的整整数，，刚好好可以以用5位二二进制制数表表示，，因此此可以以用5位二二进制制数表表示该该问题题的解解，即即染色色体。。如00000表示示x＝0，10101表示x＝21，，11111表示x＝31等适应函函数：：直接使使用函函数f(x)作为适适应函函数。。假设群群体的的规模模N＝4，交配概概率pc＝100％％，变异概概率pm＝1％％。设随机机生成成的初初始群群体为为：01101，11000，01000，10011选择方方法：：“确确定性性”法法序号群体适应值选择概率（％）期望次数选中次数10110116914.440.58121100057649.231.972301000645.470.22041001136130.851.231第0代代情况况表序号种群交配对像交配位子代适应值1011012401100144211000141100162531100042110117294100113210000256第0代代种群群的交交配情情况序号群体适应值选择概率（％）期望次数选中次数1011001448.210.33021100162535.621.42131101172941.561.66241000025614.600.581第1代代情况况表序号种群交配对像交配位子代适应值1110012311011729211011131100162531101141100002564100003111011729第1代代种群群的交交配情情况序号种群交配对像交配位子代适应值1110112311001625211101131111196131000042100012894110113211010676第2代代种群群的交交配情情况最大适适应值值、平平均适适应值值进化化曲线线遗传算算法的的特点点（1））遗传传算法法是一一个随随机搜搜索算算法，，适用用于数数值求求解具具有多多参数数、多多变量量、多多目标标等复复杂的的最优优化问问题。。（2））遗传传算法法对待待求解解问题题的指指标函函数没没有什什么特特殊的的要求求，比比如不不要求求诸如如连续续性、、导数数存在在、单单峰值值假设设等。。甚至至于不不需要要显式式的写写出指指标函函数。。（3））在在经经过过编编码码以以后后，，遗遗传传算算法法几几乎乎不不需需要要任任何何与与问问题题有有关关的的知知识识，，唯唯一一需需要要的的信信息息是是适适应应值值的的计计算算。。也也不不需需要要使使用用者者对对问问题题有有很很深深入入的的了了解解和和求求解解技技巧巧，，通通过过选选择择、、交交配配和和变变异异等等简简单单的的操操作作求求解解复复杂杂的的问问题题，，是是一一个个比比较较通通用用的的优优化化算算法法。。（4））遗遗传传算算法法具具有有天天然然的的并并行行性性，，适适用用于于并并行行求求解解。。收敛敛性性定定理理：：如果果在在代代的的进进化化过过程程中中，，遗遗传传算算法法每每次次保保留留到到目目前前为为止止的的最最好好解解，，并并且且算算法法以以交交配配和和变变异异为为其其随随机机化化操操作作，，则则对对于于一一个个全全局局最最优优化化问问题题，，当当进进化化代代数数趋趋于于无无穷穷时时，，遗遗传传算算法法找找到到最最优优解解的的概概率率为为1。。遗传传算算法法的的实实现现问问题题编码码评价价适应应函函数数交配配规规则则停止止条条件件编码码举举例例：：十十杆杆桁桁架架问问题题100kg100kg303030A1A2A3A4A5A6A7A8A9A10假设每个个杆的截截面积在在0.1至10之间，，在该范范围内，，有16个可能能的取值值。这样样我们可可以用4位二进进制向量量表示截截面积的的可能取取值，其其中0000表表示0.1，1111表示10，余余下的14位二二进制向向量表示示其他的的截面积积的可能能取值。。这样10个杆杆，共用用40位位二进制制向量表表示一个个十杆桁桁架问题题的染色色体。例：编码举例例：旅行行商问题题对于n个城市的的旅行商商问题，，可以用用一个矩矩阵来表表示一个个可能解解。如果按行行展开该该矩阵，，则该可可能解可可以用一一个4××4的二二进制向向量表示示为：二进制表表示存在在的问题题采用这样样的表示示方法，，对于n城市的旅旅行商问问题，至至少需要要用n×n位二进制制向量表表示一个个可能的的旅行路路线。一一个n×n位二进制制向量，，所有可可能的编编码个数数为，，而而一个对对称的n城市旅行行商问题题的可能能解个数数为n!/2，只占编码码个数非非常小的的比例。。以n＝10为例，编编码个数数为可能能解个数数的7.0×1023倍。可能能解在整整个状态态空间中中，是非非常稀疏疏的，交交配和变变异所产产生的是是大量的的非可能能解。遗传算法法的评价价定理7.4给出出了当进进化代数数趋于无无穷时，，遗传算算法找到到最优解解的概率率为1。。即保证证了遗传传算法的的收敛性性。但在在实际计计算时，，希望随随时了解解遗传算算法的进进展情况况，监视视算法的的变化趋趋势。当前最好好法该方法在在每一代代进化过过程中，，记录得得到的最最好解，，通过最最好解的的变化，，了解算算法的变变化趋势势。不同同的算法法之间，，也可以以通过该该最好解解的变化化情况进进行横向向比较。。在线比较较法该方法用用当前代代中染色色体的平平均指标标函数值值来刻划划算法的的变化趋趋势。计计算方法法如下：：其中T为当前代代中染色色体的个个数。。离线比较较法该方法与与在线比比较法有有些相似似，但是是用进化化过程中中每代最最好解的的指标函函数值的的平均值值，来评评价算法法的进化化过程。。计算方方法如下下：其中T是到目前前为止的的进化代代数，f*(t)是第t代中，染染色体的的最好指指标函数数值。适应函数数一般情况况下，我我们可以以直接选选取问题题的指标标函数作作为适应应函数。。如求函函数f(x)的最大值值，就可可以直接接采用f(x)为适应函函数。但但在有些些情况下下，函数数f(x)在最大值值附近的的变化可可能会非非常小，，以至于于他们的的适应值值非常接接近，很很难区分分出那个个染色体体占优。。在这种种情况下下，希望望定义新新的适应应函数，，要求该该适应函函数与问问题的指指标函数数具有相相同的变变化趋势势，但变