3数学建模-基本遗传算法入门

基本遗传算法GeneticAlgorithm(GA)Introduction生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithms，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传与变异遗传(Heredity)——世间的生物从其父代继承特性或性状，这种生命现象就称为遗传(Heredity)，由于遗传的作用，使得人们可以种瓜得瓜、种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中邀游。1遗传算法的生物学基础•构成生物的基本结构和功能的单位是细胞(Ce11)。•细胞中含有的一种微小的丝状化合物称为染色体(Chromosome)，生物的所有遗传信息都包含在这个复杂而又微小的染色体中。•基因经过生物学家的研究，控制并决定生物遗传性状的染色体主要是由一种叫做脱氧核糖核酸(简称DNA)的物质所构成。基因就是DNA长链结构中占有一定位置的基本遗传单位。•遗传信息是由基因(Gene)组成的，生物的各种性状由其相应的基因所控制。•基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。1遗传算法的生物学基础生物的遗传方式：1.复制生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制到子代。即细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新生的细胞中，新细胞就继承了旧细胞的基因。2.交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover)而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交义组合而形成两个新的染色体。3.变异在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使DNA发生某种变异(Mutation)，产生出新的染色体。这些新的染色体表现出新的性状。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。1遗传算法的生物学基础进化地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对环境的适应能力，适者生存，不适者消亡。自然界中的生物，就是根据这种优胜劣汰的原则，不断地进行进化。•生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)，或称为种群。•组成群体的单个生物称为个体(Individual)，•每一个个体对环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。1遗传算法的生物学基础将n维决策向量X＝[x1,x2,…,xn]T用n个记号Xi(i=1,2,…,n))所组成的符号串X来去示：X＝xlx2…xnX＝[x1，x2，…,xn]T•把每一个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。•这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。•这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。•对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。2遗传算法中的概念•遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。•生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程：第t代群体记做P(t)，经过一代遗传和进化后，得到t+1代群体，记做P(t+1),这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。2遗传算法中的概念(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x；100111001000101101就可表示一个个体，该个体的染色体长度是l＝18。3基本遗传算法的构成要素(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。(3)遗传算子基本遗传算法使用下述三种遗传算子：•选择运算：使用比例选择算子；•交叉运算：使用单点交叉算子；•变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：•M：群体大小，即群体中所含个体的数量，一般取为20~100。•T：遗传运算的终止进化代数，一般取为100~500•pc：交叉概率，一般取为0.4~0.99•pm：变异概率，一般取为0.0001~0.13基本遗传算法的构成要素基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算子；c——交叉操作算子：m——变异操作算子；pc——交叉概率；pm——变异概率；4基本遗传算法的形式化定义序号遗传学概念遗传算法概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解5遗传算法中的生物遗传学概念对应数学概念8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般为0.001~0.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解5遗传算法中的生物遗传学概念对应数学概念遗传算法的运算过程群体P(t)选择运算交叉运算变异运算群体P(t+1)解码个人评价解集遗传空间解空间6遗传算法的实现6.1编码与解码(1)编码假设某一参数的取值范围是[umin,umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2l–1umax其中，为二进制编码的编码精度，其公式为：=Umaxumin2l1(2)解码假设某一个体的编码是：x：blbl-1bl-2……b2b1则对应的解码公式为：x=umin+(bi·2i-1)·1i=lUmaxumin2l16遗传算法的实现6.2个体适应度评价如前所述，要求所有个体的适应度必须为正数或零，不能是负数。(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)＝f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)＝max(-f(X))但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。6遗传算法的实现将目标函数值f(x)变换为个体的适应度F(x)：方法一：对于求目标函数最大值的优化问题，变换方法为：其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：•预先指定的一个较小的数。•进化到当前代为止的最小目标函数值。•当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：•预先指定的一个较大的数。•进化到当前代为止的最大目标函数值。•当前代或最近几代群体中的最大目标函数值。F(X)=f(X)+Cminiff(X)+Cmin00iff(X)+Cmin≤0F(X)=Cmax-f(X)iff(X)Cmax0iff(X)Cmax6遗传算法的实现6.3比例选择算子从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。(1)最常用和最基本的选择算子：比例选择算子。(2)比例选择算子：指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。(3)执行比例选择的手段是轮盘选择。轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度：pi=fi/fi(i=1,2,…,M)式中pi——个体i被选中的概率；fi——个体i的适应度；fi——群体的累加适应度。显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。6遗传算法的实现轮盘选择的原理：图中指针固定不动，外圈的圆环可以自由转动，圆环上的刻度代表各个个体的适应度。当圆环旋转若干圈后停止，指针指定的位置便是被选中的个体。从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被“破格”选中。6遗传算法的实现6.4单点交叉算子通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。(1)最常用和最基本——单点交叉算子。(2)单点交叉算子的具体计算过程如下：Ⅰ.对群体中的个体进行两两随机配对。Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l，则共有(l-1)个可能的交叉点位置。Ⅲ.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。单点交叉运算的示例如下所示:单点交叉A；1011011100A’：1011011111B：0001110011B’：00011100006遗传算法的实现6.5基本位变异算子对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有基因值为1，则变异操作将其变为0。基本位变异因子的具体执行过程是：Ⅰ.对个体的每一个基因座，依变异概率pm指定其为变异点。Ⅱ.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。基本位变异运算的示例如下所示：A：1010101010A’：10100010