1、主 讲：谢 榕 武汉大学国际软件学院u20世纪60年代以来，如何模仿生物来建立功能强如何模仿生物来建立功能强大的算法大的算法，进而将它们运用于复杂的优化问题，越来越成为一个研究热点。u进化计算(evolutionary computation)正是在这一背景下孕育而生的，包括：p遗传算法(genetic algorithm，简称GA)p遗传编程(genetic programming)p进化策略(evolution strategy)p进化编程(evolutionary programming)图：人工鱼图：人工脑第五章第五章 计算智能（计算智能（3 3） 遗传算法遗传算法内容提要：u概述u遗
2、传算法的基本机理u遗传算法的求解步骤u遗传算法求解举例u达尔文的进化论？达尔文的进化论？u达尔文的进化论最基本原理:适者生存，优胜劣汰适者生存，优胜劣汰。u在进化过程中，物种每个个体的基本特征将被后代所继承，并且后代会产生一些异于父代的新变化，只有那些能适应环境的个体特征能得以保留。u每一物种都会在其所处的环境中不断进化，以便适应环境得以生存。5.1 5.1 概述概述u遗传算法（Genetic Algorithm, GA）p霍兰德(Holland)在他的著作Adaptation in Natural and Adaptation in Natural and Artificial System
3、sArtificial Systems首次提出遗传算法（1965年）p基本思想：使用模拟生物和人类进化的方法求解复杂的优化问题优化问题。p 遗传算法是一个迭代过程，每次迭代中都保留一组候选解，并按某种优劣指标进行排序，然后按某种指标从中选出一些解，利用遗传算子对其进行运算以产生新一代的一组解。重复以上过程，直到满足指定收敛要求为止。Adaptation in Natural andArtificial Systems.htm遗传算法的基本概念遗传算法的基本概念u定义1：个体（个体（individualindividual）个体是一个数据结构，用来描述基本的遗传结构。u定义2：适应性（适应性（f
4、itnessfitness）每个个体有一对应的适应值，在优化问题中，适应值来自一个估计函数。u定义3：群体（群体（populationpopulation）由个体组成的集合。u定义4：遗传操作遗传操作遗传操作作用于群体而产生新的群体。标准遗传操作包括选择选择、交叉交叉、变异变异3种基本形式。例如，用0，1组成的串可以表示个体，这样的串叫做染染色体色体，其中每个0或1叫做等位基因。5.2 5.2 遗传算法的基本机理遗传算法的基本机理u简单遗传算法（SGA）pHolland的遗传算法通常称为简单遗传算法。p目前人们提到的遗传算法多以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。u
5、遗传算法的基本组成p遗传编码p初始化种群p适应度函数p遗传操作p算法参数1.1.遗传编码遗传编码u许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。u为位串形式编码表示的过程叫编码编码。u相反地，将位串形式编码表示变换为原问题结构的过程叫解码解码或译码译码。遗传算法常用编码方法遗传算法常用编码方法u遗传算法最常用的编码方法p二进制编码p浮点数编码方法p格雷码p符号编码方法p多参数编码方法二进制编码二进制编码u假设某一参数的取值范围是A，B，AB。u用长度为l的二进制编码串来表示该参数，将A，B等分成2l-1个子部分，记每个等分长度为，则能产生2l种不同编码。u参数编码编码的对应关系如
6、下： 00000000 00000000=0 A 00000000 00000001=1 A +, 11111111 11111111=2l - 1 Bu因为“二进制编码串”的长度为l，每个编码位置的取值有两种可能(0或1)，因此共有222，共2l种不同的编码。12 lABu假设某个二进制编码是：X: xlxl-1xl-2 x2x1则二进制编码所对应的解码解码公式为：u例如，编码00010001的解码为：u二进制编码的最大缺点之一是长度较大，对很多问题用其它主编码方法可能更有利。11212iliiXlABAxx=A+(B-A)/(2l-1)(120+021+022+023 +124+）2.2.
7、适应度函数适应度函数(fitness function)(fitness function)u为了体现染色体的适应能力，对问题中的每个染色体都能进行度量的函数，叫适应度函数适应度函数。u适应度函数要有效地反映每个染色体与问题的最优解染色体之间的差距。u适应度函数的取值大小与求解问题对象的意义有很大的关系。例：货郎担问题例：货郎担问题u货郎担问题货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，城市i和城市j之间的距离为d(i，j) i, j=1,.,n。TSP问题是要找遍访每个城市恰好一次的一条回路，且其路径总长度为最短。TSP的目标是路径总长度
8、为最短，自然地，路径总长度就可作为TSP问题的适应度函数。3.3.遗传操作遗传操作u简单遗传算法的遗传操作主要有三种:p选择(selection)p交叉(crossover)p变异(mutation)选择操作（选择操作（SelectionSelection）u选择操作选择操作p也叫复制（reproduction）操作。p从种群中选择生命力强的染色体产生新群种的过程。u根据个体适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。u目前常用选择算子p转盘赌轮选择机制或称为Monte Carlo选择。选择操作选择操作转盘赌轮选择机制转盘赌轮选择机制u简单遗传算法采用转盘赌轮选择机制。u令f
9、i表示种群的适应度值之总和，fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额 ，记为pi。p1pNp2pi图：转盘赌选择u根据选择概率pi,i=1,2,N，把圆盘分成N份。在进行选择时，可以假想转动圆盘，若某参照点落入第i个扇形内，则选择个体i。u具体实现具体实现：生成一个0,1内的随机数r，若p1+p2+pi-1rp1+p2+pi，则选择个体i。交叉操作（交叉操作（crossovercrossover）u用两个个体的遗传物交换产生新个体。u它可把两个个体优良的“格式”传递到下一代某个个体中，使其具有父辈的性能。u如果交叉后得到的个体性能不佳，则可以在后面的复制操
10、作中将其淘汰。u它是遗传算法中获取新优个体的最重要的手段。u交叉操作的具体步骤：Step1Step1：从交配池中随机取出要交配的一对个体。Step2Step2：根据位串长度L，随机选取1,L-1中的一个或多个整数k作为交叉点。Step3Step3：根据交叉概率Pc（0pc1）实施交叉操作，配对个体在交叉点处，相互交换各自的部分内容，形成新的一对个体。u例如，考虑两个8位变量的父个体：父个体1：父个体2：交叉点在位置3，交叉后生成两个子个体。变异操作（变异操作（mutationmutation）u变异是在个体中的遗传物质被改变，可以使运算过程中丢弃的个体的某些重要特性得以恢复。u作用作用u变异与
11、选择和交叉结合在一起，保证遗传算法有效性，使遗传算法具有局部随机搜索能力；u同时使得遗传算法保持群的多样性，防止非成熟收敛。u变异操作变异操作 改变数码串的某个位置上的数码。 二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。u变异的基本原则：对P中任一个体，随机产生一个实数，01，如果大于事先定义的变异概率的阈值m，就对该个体进行变异。变异前：变异后：K=5，第5位进行变异5.3 5.3 遗传算法的求解步骤遗传算法的求解步骤u遗传算法的基本原理u遗传算法的特点u遗传算法的框图u遗传算法求解举例1.1.遗传算法的基本原理遗传算法的基本原理u遗传算法类似于自然进化。u通过作用于
12、染色体上的基因寻找好染色体来求解问题。与自然界相似，遗传算法对求解问题本身一无所知，仅是对算法所产生的每个染色体进行评价，并基于适应值选择染色体，使适应性好的染色体有更多的繁殖机会。u在遗传算法中，通过随机方式产生若干求解问题的数字编码，即染色体，形成初始群体；通过适应度函数对每个个体进行评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。u对该新种群进行下一轮进化。2.2.遗传算法的特点遗传算法的特点u是一种基于空间搜索的算法，通过自然选择、遗传、变异等操作以及达尔文适者生存理论，模拟自然进化过程来寻找所求问题的解答。u特点：p对参数集合的编
13、码而非针对参数本身进行进化p从问题解的编码组开始而非从单个解开始搜索p利用目标函数的适应度而非利用导数或其它辅助信息来指导搜索p利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作uStep1：初始化初始化群体;uStep2：计算计算群体上每个个体的适应度值适应度值;uStep3：按按由个体适应度值所决定的某个规则选择规则选择将进入下一代的个体;uStep4：按概率Pc进行交叉交叉操作;uStep5：按概率Pm进行变异变异操作;uStep6：没有满足某种停止条件，则转 Step2，否则进入Step7。uStep7：输出种群中适应度值最优的染色适应度值最优的染色 体体作为问题的满意解或最优
14、解。3.3.简单遗传算法简单遗传算法的求解步骤的求解步骤uStep1Step1：随机产生一个由确定长度的特征字符串组成的初始种群。uStep2Step2：对该字符串种群迭代地执行步骤和步骤，直到满足：计算种群中每个个体字符串的适应值；应用复制、交叉和变异等遗传算子产生下一代种群。uStep3Step3：把在后代中出现的最好个体字符串指定为遗传算法的执行结果，该结果可表示问题的一个解。4.4.一般遗传算法一般遗传算法的求解步骤的求解步骤u关键问题是群体规模群体规模，即群体中包括的个体数目如何设定。需考虑两个因素： 初始群体的设定初始群体的设定 根据问题固有知识，设法把握最优解所占空间在整个问题空
15、间中分布范围，再在此分布范围内设定初始群体。 先随机生成一定数目的个体，再从中挑出最好个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到预先确定的规模。 进化过程中各代的规进化过程中各代的规模如何维持模如何维持 群体规模太大群体规模太大，从计算效率着眼，群体越大，适应度评估次数增加，计算量也增加，从而影响算法效能。 群体规模太小群体规模太小，使遗传算法的搜索空间分布范围有限，搜索有可能停止在未成熟阶段，引起过早收敛现象。群体设定群体设定算法的终止准则算法的终止准则u遗传算法许多控制转移规则是随机的随机的，没有利用目标函数的梯度等信息，所以在演化过程中，无法确定个体在解空间的位置，从
16、而也无法用传统的方法来判断算法的收敛与否来终止算法。u常用的终止算法：p预先规定最大演化代数。p连续多代后解适应值没有明显改进，则终止。p达到明确的解目标，则终止。算法的终止准则算法的终止准则u遗传算法许多控制转移规则是随机的随机的，没有利用目标函数的梯度等信息，所以在演化过程中，无法确定个体在解空间的位置，从而也无法用传统的方法来判断算法的收敛与否来终止算法。u常用的终止算法：p预先规定最大演化代数。p连续多代后解适应值没有明显改进，则终止。p达到明确的解目标，则终止。5.4 5.4 遗传算法求解举例遗传算法求解举例u例例1 1：用遗传算法求解一元函数最大值的优化问题。：用遗传算法求解一元函
17、数最大值的优化问题。f(x)=xsin(10 x)+1.0，x-1,2uStep1:Step1:编码编码 采用二进制编码形式，设求解精度精确到6位小数。 由于变量x的区间长度为3，将区间-1，2分为3*106个等长区间。 2097152=2213*106222=4194304编码的二进制串长至少需要22位。u将区间-1，2内对应的实数和二进制串(b21b20b0)之间建立对应关系。(a)将二进制串(b21b20b0)转化为相应的十进制：(b)找到相应的实数x: x = -1.0 + x 3222 - 1(b21b20b0)2 = ( bi 2i )10 = xi=021u例如，一个二进制串(1
18、000101110110101000111)表示实数x=?u(0000000000000000000000)和(1111111111111111111111)分别表示区间的边界:-1.0和2.0。因为：x=(1000101110110101000111)2=2288967 x=-1.0+228867(3/4194303)=0.637197 uStep2:Step2:产生种群初始化产生种群初始化 一个个体由串长为22的、随机产生的二进制串组成染色体的基因码 用它产生一定数目的个体组成种群。 例：假设产生的3个初始个体为： s1= s2= s3=uStep3:Step3:计算适应度计算适应度p为种
19、群中每个字符串指定一个适应值。p本例直接引用目标函数作为适应度函数即为f(x)=xsin(10 x)+1.0图：初始群体与选择编号编号个体值个体值 x适应值适应值s110001011101101010001110.6371791.586345s20000001110000000100000-0.958973 0.078878s311100000001111110001011.6278882.25065uStep4:Step4:遗传操作遗传操作p对s3进行变异操作变异操作，随机选择一个变异点s3 =f(s3)=f(1.721638)=-0.082257 例如第5位，变异后产生新的子个体： 子个体
20、的适应值为： 变异后个体s3的适应值比其父个体的适应值低s3 =f(s3)=f(1.630818)=2.250650 例如第10位，变异后产生新的子个体： 子个体的适应值为： 变异后个体s3的适应值比其父个体的适应值一样uStep4:Step4:遗传操作遗传操作s2=s3= 对s2和s3进行交叉操作交叉操作，随机选择一个交叉点，例如第5位与第6位之间的位置，交叉后产生新的子个体：f(s2)=f(-0.998113)=0.940865f(s3)=f(1.666028)=2.459245 两个子个体的适应值分别为： 交叉后个体s3的适应值比其父个体的适应值高。s2=s3= 设按转盘赌方式选择子个体
21、，生成的随机数为0.35，0.72，则选中的个体为s2和s3。uStep5:Step5:模拟结果模拟结果设定种群大小为50，交叉概率pc=0.25，变异概率pm=0.01图：模拟世代种群中最佳个体的演变情况uStep5:Step5:模拟结果模拟结果设定种群大小为50，交叉概率pc=0.25，变异概率pm=0.01，按照标准的遗传算法SGA，在运行到第150代时获得最佳个体： smax= xmax=1.850549,f(xmax)=2.850274u例例2：用遗传算法进行路径规划：用遗传算法进行路径规划 寻找一条从起点到终点的能够避开障碍物的尽量短的路径u用遗传算法进行路径规划u用遗传算法进行路
22、径规划u用遗传算法进行路径规划遗传算法研究综述.pdf用遗传算法进行路径规划.pdf计算智能小结计算智能小结u1994年6月，国际电气电子工程师学会召开了一次国际计算智能会议，首次将有关人工神经网络、模糊技术和进化计算方面的内容放在一起交流讨沦，随后，计算计算智能智能成为众所关注的热点。人工智能的新领域_计算智能.flvu计算智能是人工智能的深化和发展。u如果说经典人工智能(如专家系统)是以知识库为基础、以顺序离散符号推理为特征的知识表达、推理和利用的知识系统，那么计算智能则是以模型(数学模型、计算模型)为基础，以分布、并行、仿生计算为特征的数据、算法和实现的信息系统。u前者强调规则的形成和表
23、示，而后者强调模型的建立和形成；前者依赖专家知识，而后者强调自组织、自学习和自适应。u生物是自然智能的载体，因此生物学理所当然是人工智能研究灵感的重要来源。从信息处理的视角来看，生物体就是一部优秀的信息处理机，而其通过自身演化完美解决问题的能力让目前最好的计算机也相形见绌。u在计算机科学中，我们永远不会有运动学三定律，智能行为是不能用简单的数学模型来描述的。人工智能“应该从生物学而不是物理学中受到启示”。1. 简单遗传算法的步骤是什么？课堂练习课堂练习2. 考虑两个11位变量的父个体：父个体1：父个体2：3. 用遗传算法求解max f(x)=x2，其中x0,31。交叉点在位置5，求交叉后生成两
24、个子个体。u1. 简单遗传算法的步骤是什么？（1）将问题的每个可能解按某种形式进行编码。（2）随机选取N个染色体构成初始种群。（3）根据预定的评价函数对每个染色体计算适应度值。（4）选择适应度值高的染色体进行复制，通过遗传算子（选择、交叉、变异）产生一群新的更适应环境的染色体，形成新的种群。（5）一代一代不断繁殖、进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。u2. 考虑两个11位变量的父个体：父个体1：父个体2：交叉点在位置5，求交叉后生成两个子个体。3. 用遗传算法求解max f(x)=x2，其中x0,31。 Step 1：编码：5位二进制数。 Step 2：初始群体：群体规模
25、为4个个体，随机产生。 假设为：01101，11000，01000，10011 Step 3：适应度计算： （适应值直接取 f(x) ） Step 4：选择复制产生下一代群体；（选择概率按适应值大小采用轮盘赌的随机策略）个体个体编号编号初始群体初始群体基因基因译码译码适应度适应度计算计算f(xi)/ f(xi)f(xi)/f下一代群下一代群体复制数体复制数101101131690.140.581211000245760.491.9723010008640.060.220410011193610.311.231310f=x2 Step 5：个体基因交叉；（一般交叉概率较大0.70.9）个体个体编号编号复制后复制后的群体的群体基因基因译码译码适应度适应度计算计算交叉交叉对象对象交叉交叉位置位置交叉后交叉后的群体的群体适应度适应度计算计算10110113169240110014421100024576141100162531100024576431101172941001119361331000025601110011000011001011交叉0011000010变异 Step 6：个体基因变异（一般变异概率较小0.0010.01 ） Step 7：转Step 3直至算法终止。
