对遗传算法解决TSP问题的简单改进PPT精品文档.ppt

遗传算法的提出遗传算法的提出o遗传算法是根据自然界“物竞天择、适者生存”的现象而提出的一种随机搜索算法；o遗传算法把优化问题看作是自然界中的生物进化过程，通过模拟大自然中生物进化过程的遗传规律，来达到寻优的目的o生物进化圈示意图婚配选择变异子群种群群体遭淘汰的群体1生物进化的特性生物进化的特性o进化过程发生在染色体上，而不是发生在他们所编码的生物体上；o自然选择把染色体以及由他们所译成的结构的表现联系在一起，适应性好的个体染色体比差的染色体有更多的繁殖机会；o繁殖过程发生在进化那一刻变异可以使生物体子代的染色体不同于他们的父代染色体；通过结合两个父代染色体中的物质，重组过程可以产生在子代中有很大差异的染色体；o生物进化没有记忆2遗传算法的基本思想遗传算法的基本思想o遗传算法通过自然选择中“优胜劣汰”的策略在每次搜索中利用各种随机的遗传算子生成问题一些新的解，淘汰较差的解，保留较好的以及有希望的解，从而不断对搜索空间中新的未知区域进行探索它有效地利用了许多历史信息，使得搜索每次都向着最好的方向前进o对优化问题的解进行编码，编码后的一个解称为染色体，组成染色体的元素称为基因；o一个群体由若干染色体组成，染色体的个数称为群体的规模；o用适应度函数表示环境，它是已编码的解的函数，是一个解适应环境程度的评价；适应函数的构造一般与优化问题的指标函数相关；3遗传算法的基本思想遗传算法的基本思想o适应函数值大表示所对应的染色体适应环境的能力强，自然选择规律将以适应函数值的大小来决定染色体是否继续生存下去的概率；o生存下来的染色体称为种群，他们中的部分或全部以一定的概率进行交配、繁衍，从而得到下一代群体；o交配是一个生殖过程，发生在两个染色体之间，作为双亲的染色体，交换部分基因后，生殖出两个新的染色体，即问题的新解；o在进化过程中，染色体的某些基因可能会发生变异，即染色体的编码发生了某些变化。

一个群体的进化需要染色体的多样性，变异对于保持群体的多样性具有一定的作用4生物进化与遗传算法之间的对应关系生物进化与遗传算法之间的对应关系5遗传算法的基本模型遗传算法的基本模型（1）遗传算法可以形式化地描述如下：（2） 表示初始群体；（3） 表示长度为l 的符号串全体，Σ为字母表； 若使用二进制编码，则 ；（4）N 为一个正整数，表示种群中含有个体的个数；（5）l 为一个正整数，表示符号串的长度；（6） 表示选择策略；（7）g 表示遗传算子，通常包括复制算子 、交叉算子 和变异算子 ；（8）p 表示操作概率，包括复制概率 、交叉概率 和变异概率 ；（9） 是适应度函数；（10） 是终止准则6遗传算法的基本操作遗传算法的基本操作o简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。

改进的遗传算法大量扩充了遗传操作，以达到更高的效率o选择操作选择操作实现从群体中选择存活的个体(染色体)根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传o交叉操作交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的基因进行交换，产生新个体的染色体o变异操作变异操作的简单方式是改变数码串的某个位置上的数码二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为07选择操作选择操作q选择概率： 设群体规模为N，F(xi)(i=1,…,N)是N个染色体的适应值，则第i个染色体被选中的概率由下式计算： P(xi)= F(xi)/ ∑F(xj) q“轮盘赌”选择法： 一个转盘划分为N个扇区，每个xi在转盘上占有一个扇区，扇区的大小与选择概率P(xi)成正比在选择一个染色体时，先转动轮盘，等轮盘停下后，指针指向的区所对应的xi应是被选中的染色体q“分组淘汰”选择法： 设群体规模为N，按 P(xi)由大到小对染色体进行排序，再依次分为相等数目的k组，每组按淘汰概率Pi(i=1,..,k)淘汰本组染色体，各组剩余者合并为种群。

淘汰概率满足：P1< P2<… < Pk8选择操作选择操作q“确定性”选择法： 设群体规模为N，一个选择概率为P(xi)的染色体被选中的次数的期望值e(xi)= P(xi) N 对于群体中的每一个xi ，首先选择[e(xi)]次，这样共得∑[e(xj)] 个染色体再按e(xi)- [e(xi)]由小到大对染色体进行排序，依次取出N- ∑[e(xj)] 个染色体，这样共得到N个染色体组成种群9交配操作交配操作q交配操作发生在两个父代染色体之间，经过杂交产生两个具有双亲的部分基因的新染色体q单点交配：q 多点交配：a1 a2…ai ai+1 … an b1 b2…bi bi+1 … bna1 a2…ai bi+1 … bn b1 b2…bi ai+1 … ana1…ai ai+1 … aj aj+1 … an b1…bi bi+1 … bj bj+1 … bna1…ai bi+1 … bj aj+1 … an b1…bi ai+1 … aj bj+1 … bn10变异操作变异操作q 变异操作是发生在某一个基因上的随机变化，模拟基因突变现象，有利于保持群体的多样性，但也有很强的破坏作用。

q 二进制基因的变异操作，可以是简单地按变异概率翻转某一个位，即某位由0变1，或由1变0q 字符基因的变异操作将某一个基因字符上的随机地换为任一其他可能基因字符11遗传算法的基本流程遗传算法的基本流程12遗传算法的描述遗传算法的描述1.给定群体规模N，交配概率pc和变异概率pm2.随机生成一个N个初始解组成的初始群体；3.计算当前初始群体各染色体xi的适应度函数值F(xi)；4.如果满足停止准则，则转10；5.对群体中的每一个染色体xi计算概率p(xi)；6.依据概率值从群体中随机选择N个染色体，得到种群；7.依交配概率pc按交叉算子Oc进行交配，其子代进入新的群体，未进行交配的染色体直接复制到新群体中；8.依变异概率pm从种群中选择染色体按变异算子Om进行变异，用变异后的染色体代替新群体中的原染色体；9.用新群体代替旧群体，t=t+1，转310.进化过程中适应值最大的染色体，经解码后作为最优解输出；11.结束13用于求解函数优化问题用于求解函数优化问题例如：求函数f(x)=x2的最大值，其中x为[0，31]间的整数利用遗传算法进行求解，关键要解决如下问题：o编码与解码：染色体由五个二进制位组成，可能的染色体有：00000~11111共32个。

o适应度函数：F(x)= f(x)o选择操作：轮盘赌o交配操作：单点交配o变异操作：位翻转o控制参数：N=4，Pc=100%,Pm=1%o求解过程：14适应度函数适应度函数o为了评价染色体的适应能力，引入了对问题中的每一个染色体都能进行评价的函数，叫适应度函数适应度函数（fitness function）o一般情况下，可以直接选取问题的指标函数作为适应度函数o例1：求f(x)的最大值问题，可以直接采用f(x)作为适应度函数，即F(x)=f(x)o例2：TSP问题，目标是路径总长度最短，因此可以将路径总长度作为TSP问题的适应度函数o适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距15适应度函数适应度函数o某些情况下，f(x)在最大值附近的变化可能非常小，以至于很难区分哪个染色体更优，这时应如何定义适应度函数，才能有效反映染色体与最优解染色体的差异?ü 非线性加速适应函数ü 线性加速适应函数ü 利用染色体指标函数值从小到大的排列号作为适应函数值 按定义，选择概率计算式为：16二进制编码的交配规则二进制编码的交配规则o双亲双子法 参与交配的两个双亲染色体确定后，随机地产生一个交配位，双亲染色体交换各自的交配位后的基因给对方，得到两个子染色体。

o变化交配法 随机产生交配位时，排除与双亲一样的交配位 o多交配位法 产生多个交配位进行交配，在交配时采用交配区间交替进行的方法o双亲单子法 两个染色体交配后只得到一个子染色体一般选择适应值大的17二进制交配操作的例子二进制交配操作的例子o如下表所示，第0代种群为：01101,11000,11000,10011假定交配概率的100%，即种群中所有染色体均参与交配，并按顺序两两交配o交配后得到的子群为： 01100,11001,11011,1000018整数编码的交配规则整数编码的交配规则-1整数编码的交配规则必须保持编码的有效性下面以TSP问题的整数编码为例进行说明(P318)o常规交配法 与二进制编码的双亲双子法类似子代1交配位之前的基因采用父代1交配位之前的基因，交配位之后的基因从父代2中按顺序选取那些没有出现过的基因父代1：12345678父代2：52373846子代1：12345786子代2：5237146819整数编码的交配规则整数编码的交配规则-2o基于次序的交配法 对于两个选定的父代染色体父代1和父代2，首先随机地选择一组位置，设父代1中所选位置对应的数字从左到右依次为x1,x2,…,xk，然后从父代2中也找到这k个数字，并从父代2删除，空位置用x1,x2,…,xk依次填入，就得到子代1。

子代2同理父代1：1 2 3 4 5 6 7 8 9 10父代2：5 9 2 4 6 1 10 7 3 8选 定： * * * *子代1： 2 9 3 4 6 1 10 7 5 8子代2： 1 9 3 4 5 2 6 8 7 10父代2‘：b 9 b 4 6 1 10 7 b b父代1‘：1 b 3 4 5 b b 8 b 1020整数编码的交配规则整数编码的交配规则o基于位置的交配法 对于两个选定的父代染色体父代1和父代2，首先随机地选择一组位置，对于这些位置上的基因，子代1从父代2直接得到，子代1其他位置的基因，按顺序从父代1中选取那些不相重的基因子代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 子代2： 9 2 3 4 5 6 1 8 721整数编码的交配规则整数编码的交配规则o基于部分映射的交配法 对于两个选定的父代染色体父代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 子代2： 6 5 2 3 8 1 4 7 922变异操作变异操作o变异操作发生在某个染色体的某个基因上，它将可变性引入群体中，增强了群体的多样性，从而提供了从局部最优中跳出来的一种手段o一般通过一个很小的变异概率来控制变异o对二进制编码，随机产生一个变异位，被选中的基因由0变为1，或者由1变为023整数编码的变异规则整数编码的变异规则对整数编码，必须考虑变异后染色体的合理性常用的变异规则有如下几种（祥见P320）：o基于位置的变异 随机地产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前o基于次序的变异 随机地产生两个变异位，然后交换这两个变异位上的基因o打乱变异 随机选取染色体上的一段，然后打乱在该段内的基因次序逆序交换方式是打乱变异的一个特例24控制参数控制参数遗传算法的控制参数主要包括：o群体规模 每一代中群体的规模一般是固定的扩大群体的规模可以防止早熟现象的发生o停止准则 一般可以通过规定进化的最大代数来定义；或者定义为经过连续的几代进化后，得到的最优解没有任何变化。

o进化代数 根据实际需要以及时间约束设置o交配概率o变异概率25遗传算法的特点遗传算法的特点o遗传算法是对参数集合的编码而非针对参数本身进行进化；o遗传算法是从问题解的编码组开始而非从单个解开始搜索；o遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；o遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作o随机性：遗传算法是一个随机搜索算法，每一次运行得到的结果可能是不一样的o通用性：遗传算法经过编码表示后除适应值计算外几乎不需要任何与问题有关的知识，而且对待求解问题的指标函数没有什么特殊的要求；o并行性：遗传算法具有天然的并行性，适用于并行求解；26遗传算法的收敛性定理遗传算法的收敛性定理o如果在代的进化过程中，遗传算法每次保留到目前为止的最好解，并且算法以交配和变异为其随机化操作，则对于一个全局最优化问题，当进化代数趋于无穷时，遗传算法找到最优解的概率为1o该定理从理论上保证了只要进化代数足够多，则遗传算法找到最优解的可能性非常大o实际使用中，要考虑在可接受的有限时间内终止算法，因此解的质量与算法的控制参数，如群体的规模、进化代数等有很大的关系。