湘潭大学-人工智能课件-遗传算法

ArtificialIntelligence(AI)人工智能第八章：仿生进化系统遗传算法遗传算法（GeneticAlgorithm,GA）是模拟生物在自然环境种的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法最早由美国密西根大学的J.Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究。70年代，DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。遗传算法的基本思想:是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法遗传算法遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解。遗传算法从一组随机初始化的候选解出发按某种指标从解群中选取较优的个体利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群重复此过程，直到满足某种收敛指标为止。遗传算法所涉及到的基本概念:种群（Population）：是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。个体（Individual）：是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。染色体（Chromos）：是指对个体进行编码后所得到的编码串。其中的每1位称为基因，若干个基因构成的一个有效信息段称为基因组。遗传算法1.遗传算法的基本概念适应度（Fitness）函数：是一种用来对种群中各个个体的环境适应性进行度量的函数。遗传操作（GeneticOperator）：是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下3种基本形式：选择（Selection）交叉（Crosssover）变异（Mutation）遗传算法1.遗传算法的基本概念遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成。遗传算法2.遗传算法的基本过程算法主要内容和基本步骤:(1)选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；(2)定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数；(3)令t=0，随机选择N个染色体初始化种群P(0)；(4)定义适应度函数f（f0）；(5)计算P(t)中每个染色体的适应值；(6)t=t+1；(7)运用选择算子，从P(t-1)中得到P(t)；(8)对P(t)中的每个染色体，按概率Pc参与交叉；(9)对染色体中的基因，以概率Pm参与变异运算；(10)判断群体性能是否满足预先设定的终止标准，若不满足则返回(5)。遗传算法2.遗传算法的基本过程计算种群中各个个体的适应度，并进行评价满足终止条件吗？终止选择交叉变异Y基本遗传算法的算法流程图编码和生成初始种群N选择遗传算法2.遗传算法的基本结构常用的遗传编码算法：霍兰德二进制码格雷码（GrayCode）实数编码字符编码遗传算法3.遗传编码(1)二进制编码（Binaryencoding）二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度，该长度与变量的定义域和所求问题的计算精度有关。例假设变量x的定义域为[A，B]，用长度为二进制编码串来表示该参数，将[A，B]等分成个子部分，记每一个等分的长度为，则它能够产生种不同的编码。遗传算法3.遗传编码ll21l2l二进制编码存在的主要缺点：汉明（Hamming）悬崖。例如，7和8的二进制数分别为0111和1000，当算法从7改进到8时，就必须改变所有的位。遗传算法3.遗传编码遗传算法3.遗传编码(2)格雷编码（Grayencoding）格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。它有效地解决了汉明悬崖问题遗传算法3.遗传编码格雷编码基本原理如下：设有二进制串b1,b2,…,bn，对应的格雷串为a1,a2,…,an，则从二进制编码到格雷编码的变换为：其中，⊕表示模2加法。而从一个格雷串到二进制串的变换为：例十进制数7和8的二进制编码分别为0111和1000，而其格雷编码分别为0100和1100。111ibbibaiiiiijiiab1)2(mod(3)实数编码（Realencoding）实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。实数编码适应于那种多维、高精度要求的连续函数优化问题。遗传算法3.遗传编码适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。(1)常用的适应度函数①原始适应度函数：直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。例如，在求解极值问题时，f(x)即为x的原始适应度函数。)(max],[xfbax遗传算法4.适应度函数采用原始适应度函数优点：能够直接反映出待求解问题的最初求解目标缺点：是有可能出现适应度值为负的情况。遗传算法4.适应度函数②标准适应度函数在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数fNormal(x)。例如下面的极小化和极大化问题：遗传算法4.适应度函数极小化问题对极小化问题，其标准适应度函数可定义为其中，fmax(x)是原始适应函数f(x)的一个上界。如果fmax(x)未知，则可用当前代或到目前为止各演化代中的f(x)的最大值来代替。可见，fmax(x)是会随着进化代数的增加而不断变化的。遗传算法4.适应度函数否则当0)()()()()(maxmaxxfxfxfxfxfnomal极大化问题对极大化问题，其标准适应度函数可定义为其中，fmin(x)是原始适应函数f(x)的一个下界。如果fmin(x)未知，则可用当前代或到目前为止各演化代中的f(x)的最小值来代替。遗传算法4.适应度函数否则当0)()()()()(minminxfxfxfxfxfnomal(2)适应度函数的加速变换在某些情况下，需要对适应度函数进行加速速度。适应度函数的加速变换有两种基本方法线性加速的适应度函数的定义如下：f'(x)=αf(x)+β其中，f(x)是加速转换前的适应度函数；f'(x)是加速转换后的适应度函数；α和β是转换系数,它们应满足如下条件：遗传算法4.适应度函数①变化后得到的新的适应度函数平均值要等于原适应度函数的平均值。即其中，xi(i=1,…,n)为当前代中的染色体。遗传算法4.适应度函数nxfnxfniinii11)()(②变换后所得到的新的种群个体所具有的最大适应度要等于其平均适应度的指数倍数。即有关系：式中，xi(i=1,…,n)为当前代中的染色体，M是指将当前的最大适应度放大为平均值的M倍。目的是通过M拉开不同染色体适应度值的差距。遗传算法4.适应度函数nxfMxfniiini11)()(max非线性加速幂函数变换方法f'(x)=f(x)k指数变换方法f'(x)=exp(-βf(x))遗传算法4.适应度函数遗传算法中的基本遗传操作包括选择、交叉和变异3种，而每种操作又包括多种不同的方法，下面分别对它们进行介绍。(1).选择操作选择（Selection）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。常用的选择策略:比例选择排序选择竞技选择遗传算法5.基本遗传操作①比例选择基本思想是：各个个体被选中的概率与其适应度大小成正比。常用的比例选择策略:轮盘赌选择繁殖池选择遗传算法5.基本遗传操作②轮盘赌选择轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：其中，P(xi)是个体xi的相对适应度，即个体xi被选中的概率；f(xi)是个体xi的原始适应度；是种群的累加适应度。1()()()iiNjjfxPxfx遗传算法5.基本遗传操作轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将一个圆盘分成N个扇区，其中第i个扇区的中心角为：再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向第i个扇区，则选择个体i。1()22()()iiNijjfxpxfx遗传算法5.基本遗传操作P(x1)P(x2)P(xN)……P(xi)2πp(xi)轮盘赌选择从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。遗传算法5.基本遗传操作(2)交叉操作交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型。遗传算法5.基本遗传操作①二进制交叉二进制交叉（BinaryValuedCrossover）是指二进制编码情况下所采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀交叉等方法。遗传算法5.基本遗传操作单点交叉单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉，交叉后生成的两个新的个体是：X'=x1x2…xkyk+1…ynY'=y1y2…ykxk+1…xn遗传算法5.基本遗传操作单点交叉例设有两个父代的个体串A=001101和B=110010，若随机交叉点为4，则交叉后生成的两个新的个体是：A'=001110B'=110001遗传算法5.基本遗传操作两点交叉两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。假设两个父代的个体串分别是：X=x1x2…xi…xj…xnY=y1y2…yi…yj…,yn随机设定第i、j位为两个交叉点（其中ijn），两点交叉是将X中的xi+1到xj部分与Y中的yi+1到yj部分进行交换，交叉后生成的两个新的个体是：X'=x1x2…xiyi+1…yjxj+1…xnY'=y1y2…yixi+1…xjyj+1…yn遗传算法5.基本遗传操作两点交叉例设有两个父代的个体串A=001101和B=110010，若随机交叉点为3和5，则交叉后的两个新的个体是：A'=001011B'=110100遗传算法5.基本遗传操作多点交叉多点交叉是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个新的个体。假设交叉点个数为m，则可将个体串划分为m+1个分段，其划分方法是：当m为偶数时，对全部交叉点依次进行两两配对，构成m/2个交叉段。当m为奇数时，对前(m-1)个交叉点依次进行两两配对，构成(m-1)/2个交叉段，而第m个交叉点则按单点交叉方法构成一个交叉段。遗传算法5.基本遗传操作多点交叉以m=3为例进