《进化计算及其应用ppt课件.ppt》由会员分享，可在线阅读，更多相关《进化计算及其应用ppt课件.ppt（50页珍藏版）》请在三一办公上搜索。
1、第一部分 计算智能,引言Ch2 进化计算及其应用Ch3 群智能算法及其应用Ch4 其它近邻搜索算法,2,优化问题的分类,许多工程问题都可以看成为最优化问题。根据优化目标，最优化问题可以分为：最小化问题和最大化问题。从数学模型的表现形式来看，最优化问题可以分类为：函数优化问题或组合优化问题。,3,函数优化问题,以最小化问题为例，优化对象：一定区间S内的连续变量。问题的一般描述：求XminS使f(Xmin)在S上全局最小。符号化表示为：XS: f(Xmin)f(X)。S为Rn上的有界子集，即变量的定义域。f: SR为n维实值函数。,Xmax 最大,4,组合优化问题,优化对象：解空间中的离散状态问题
2、的一般描述：寻找最优解s*，si，C(s*)=minC(si) =s1, s2, , sn为所有状态构成的离散解空间。C(si)为状态si对应的目标函数值。典型的组合优化问题：TSP问题、加工调度问题、0-1背包问题、装箱问题等。特点：问题的描述很简单，有很强的工程代表性，最优化求解很困难，主要原因是“组合爆炸”。,max,Ch2 进化算法及其应用,1. 进化算法简介2. 遗传算法的基本理论3. 进化策略的基本理论4. 进化规划的基本理论5. 进化算法的应用实例,5,产生背景主要特点理论基础基本框架分类说明,1. 进化算法简介,对自身的大脑信息处理机制进行模拟-人工神经网络理论。对自身模糊性的
3、思维方式进行类比-模糊系统。对自然界中动植物的免疫机理进行模拟-免疫系统。对自身进化这一更为宏观的过程学习-进化算法(Evolutionary Computation，EC) 。,1.1 进化算法的产生背景,进化算法以达尔文的进化论思想为基础，通过模拟生物进化过程与机制来求解问题的自组织、自适应的人工智能技术。生物进化是通过繁殖、变异、竞争和选择实现的。进化算法主要通过选择、重组和变异这三种操作实现优化问题的求解。,1.1 进化算法的产生背景,1.2 进化算法的主要特点,是一种全局优化、自适应概率搜索算法，主要特点有：有指导的搜索：依据是每个个体的适应度值。自适应搜索：通过进化操作改进群体性能
4、。渐进式寻优：每代进化的结果都优于上一代。并行式搜索：对每一代群体所有个体同时进行。黑箱式结构：只要研究输入和输出而不需考虑过程。全局最优解：在整个搜索区域的各个部分同时进行。稳健性强：不同的条件和环境下，算法都适用且有效。,1.3 进化算法的理论基础,具有深厚的生物学理论基础。遗传：父代利用遗传基因将自身的基因信息复制给下一代（子代），属性特征相同或相近。变异：子代和父代，以及子代各个体之间存在着一定的差异，在进化过程中是随机发生的。生存斗争和适者生存：适应性变异较强的个体被保留下来，而适应性变异较弱的个体则被淘汰。,1.4 进化算法的基本框架,Begint=0初始化群体p(0)评估初始化群
5、体p(0)While 终止条件不满足 do重组操作：p(t)=r(p(t)变异操作：p(t)=m(p(t)评估操作：p(t)选择操作：p(t+1)=s(p(t)Q) t=t+1endEnd,1.5 进化算法的分类,与进化算法相关的算法可细分为：遗传算法(Genetic Algorithms)、遗传规划(Genetic Programming)、进化策略(Evolution Strategies)和进化规划(Evolution Programming)四种典型方法。第一类方法比较成熟，现已广泛应用。进化策略和进化规划在科研和实际问题中的应用也越来越广泛。遗传算法最具代表性也是最基本的。,2. 遗
6、传算法的基本理论,1. 遗传算法与生物进化学说2. 遗传算法的计算机实现3. 遗传算法解决TSP问题4. 遗传算法的特点5. 遗传规划,13,14,2.1 遗传算法与生物进化学说,1885年，达尔文用自然选择来解释物种的起源和生物的进化。 达尔文的自然选择学说包括三个方面：遗传变异生存斗争和适者生存,15,2.1 遗传算法与生物进化学说,上世纪20年代，一些学者用统计生物学和种群遗传学重新解释达尔文自然选择理论，形成现代综合进化论。 种群遗传学认为：在一定地域中一个物种的全体成员构成一个种群；生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种
7、群的进化。,16,2.1 遗传算法与生物进化学说,GA中与生物学相关的概念与术语： 个体种群适应度选择交叉变异,2.2 遗传算法的计算机实现,上世纪60年代中期，Holland提出位串编码技术。这种技术适用于变异和交叉操作，而且强调将交叉作为主要的遗传操作。Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了开创性著作“Adaptation in Natural and Artifical System”。之后，他将算法应用到优化以及学习中，并将其命名为遗传算法（简称GA）。,18,遗传算法基本思路：计算开始时，随机初始化一定数目的个体，并计算每个个体的适应度值，产生第
8、一代（初始种群）。如果不满足优化准则，开始新一代的计算：按照适应度值选择个体，产生下一代；父代按一定概率进行交叉操作，产生子代；所有的子代按一定概率变异，形成新的一代。计算新子代的适应度值。这一过程循环执行，直到满足优化准则为止。,2.2 遗传算法的计算机实现,19,遗传算法基本流程,2.2 遗传算法的计算机实现,20,需要解决的问题： 种群 适应度函数 复制（选择） 交叉 变异 编码：首先需要解决的问题,遗传操作,21,2.2.1 编码,什么是编码？解题过程中，每个具体的解就对应一个个体。编码将问题的解用某种码制来表示，从而将问题的解(状态)空间与GA的码空间相对应。,22,2.3 遗传算法
9、的计算机实现,编码的意义：很大程度上，编码方案决定了如何进行群体的遗传运算及其运算效率。一个好的方案，可以使遗传运算简单易行。编码是应用GA时要解决的首要问题，也是设计GA的关键步骤之一，选择或设计一种合适的编码方案对算法的性能和效率意义重大。,23,2.3 遗传算法的计算机实现,例：考虑一元函数求最大值的优化问题,24,2.2.1 编码,已有的编码方案：二进制编码、Delta编码、格雷码编码、实数编码、自然数编码、符号编码、动态变量编码、链表编码、矩阵编码、树型编码、量子比特编码,最常用的编码方法：二进制编码使用二值编码符号集0, 1。一个二进制符号串代表一个个体，串长与求解精度有关。,25
10、,设求解精度为6位小数，求解区间-1, -2。将闭区间-1, 2改为：0, 31063106=(1011 0111 0001 1011 0000 00)2 2097152 = 221 3106 222 = 4194304所以，编码的二进制串长至少需要22位,穷尽编码：二进制串(0000000000000000000000)表示区间端点值-1二进制串(1111111111111111111111)表示区间端点值2,不穷尽编码？,2.2.1 编码,26,2.2.1 编码,将一个二进制串（b21b20b0）转化为区间-1, 2内对应的实数，需要采用以下步骤：将二进制数转化为十进制数 x将 x 转化为
11、区间-1，2内的实数 x,27,2.2.1 编码,根据模式理论，采用二进制编码处理的模式最多，几乎任何问题都可以用二进制编码来表达。因此，二进制编码应用是最早和最广泛的，它是GA中最常用的一种编码方案。二进制编码的主要优点：编码、解码操作简单易行。选择、交叉和变异等遗传操作便于实现。符合最小符号集编码原则。便于利用模式定理对算法进行理论分析。,28,2.2.1 编码,二进制编码缺点：存在Hamming悬崖问题在某些相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越。算法效率和最优解精度的矛盾问题,29,2.2.2 产生种群,一定数目的个体组成种群。种群中个体的数目被称
12、为种群规模。初始个体的产生方法：随机法、启发法。种群规模会影响算法优化性能和效率。太小，不能提供足够的采样点，算法性能很差，甚至得不到问题的可行解。太大，可以增加优化信息以阻止早熟收敛，但计算量增加，使收敛时间变长。,30,2.2.3 适应度函数,GA在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。 一般，适应度函数由目标函数变换而成。若目标函数为最大化问题：Fit(x)=f(x)若目标函数为最小化问题：Fit(x)=-f(x),适应度函数设计原则：单值、非负。能够正确反映解空间分布情况。计算量小。要能够满足某一具体问题下的不同情况，即具有较强的通
13、用性。,2.2.3 适应度函数,32,2.2.3 适应度函数,设个体的二进制为：s=(1000101110110101000111),33,2.2.3 适应度函数,设有三个个体的二进制为：s1=(1000101110110101000111)s2=(0000001110000000010000) s3=(1110000000111111000101)分别对应于变量：x1=0.637197、x2=-0.958973、x3=1.627888个体的适应度为：f(s1)=f(x1)=2.586345、f(s2)=f(x2)=1.078878 f(s3)=f(x3)=3.250650三个个体中s3的适应
14、度最大，因此，s3为最佳个体。,34,以个体的适应度值为评价指标，对种群中个体进行优胜劣汰，决定从父代种群中选取哪些个体遗传到下一代种群中。 选择算子有：比例选择、最优保存策略、确定性采样选择、排序选择、竞技选择等。 比例选择又分为：轮盘赌选择法、繁殖池选择法、Boltzmann选择法。,2.2.4 选择操作,35,轮盘赌选择法：每个个体被选中的概率与其适应度值成正比。设种群规模为M，个体i的适应度值为fi，则个体i被选中的概率Pi为：,2.2.4 选择操作,36,当Pi给定后，产生0, 1区间内的均匀随机数来决定哪个个体参加交叉操作。即：用赌轮方式决定个体的选择份数。,2.2.4 选择操作,
15、37,2.1 遗传算法及其应用,38,经选择产生的交叉种群由以下个体组成：1, 2, 3, 5, 6, 9,2.2.4 选择操作,39,在选择操作基础上，根据交叉概率进行交叉操作：把两个父个体的部分结构进行替换重组，生成新个体。对应于二进制编码，常用的交叉算子是：单点交叉。此外还有双点交叉、均匀交叉。交叉点的范围为：1，N-1，N为二进制串的串长。交叉操作时，个体以该点为分界相互交换变量。,2.2.5 交叉操作,40,设经过选择操作，得到两个个体： s2 = (00000 | 01110000000010000) s3 = (11100 | 00000111111000101)随机选择一个交叉
16、点，交叉后产生新的子个体： s2 = (00000 | 00000111111000101) s3 = (11100 | 01110000000010000),2.2.5 交叉操作,41,交叉概率控制交叉操作频率，使部分被选择的个体进行交叉操作。概率太大，个体更新过快，高适应度值的个体很快被破坏。概率太小，很少进行交叉操作，使搜索停滞不前。,2.2.5 交叉操作,42,基于二进制编码的GA中，变异是指将被选中个体的某一位进行翻转操作，即：将1换为0，将0换为1。s3=(1110000000111111000101) 选择第5位变异：s3=(1110100000111111000101)f(s3
17、)=0.917743f(s3)=3.250650选择第10位变异：s3=(1110100001111111000101)f(s3)=f(1.630818)=3.343555f(s3)=3.250650,2.2.6 变异操作,43,不是所有被选择的个体，都要进行变异操作。变异概率是加大种群多样性的重要因素。概率太小很难产生新个体。概率太大会使GA成为随机搜索。基于二进制编码的GA中，通常一个较低的变异率足以防止整个种群中任一位置的基因一直保持不变。,2.2.6 变异操作,44,用于判断算法是否可以终止。最常用的终止条件：事先给定一个最大进化步数；判断连续若干步内，最佳优化值是否有明显变化。,2.
18、2.7 优化准则,45,2.3 遗传算法求解TSP问题,编码最常用策略：路径编码直接采用城市在路径中的位置来构造用于优化的状态。例：九城市TSP问题，路径：5-4-1-7-9-8-6-2-3路径编码：(5 4 1 7 9 8 6 2 3),46,47,2.3 遗传算法求解TSP问题,48,2.4 遗传算法的特点,GA是一种通用的优化算法，它的优点有：编码技术和遗传操作比较简单；优化不受限制性条件的约束；隐含并行性和全局解空间搜索。 随着计算机技术的发展，GA愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI设计、遗传学等领域得到了成功应用。,2.5 遗传规划,遗传算法：采用定长字符串，对问题解答的结构和大小进行了预确定。极大地限制了在人工智能、及其学习和符号处理等领域的应用。遗传规划：计算机程序的结构和大小都是可以变化的。采用层次化的计算机程序代替字符串表达问题，克服了遗传算法表达方面的局限性。,自学和作业内容,1. 遗传算法的进一步讨论 2. 进化策略的基本理论3. 进化规划的基本理论4. 进化算法的应用实例,50,
