董素媛遗传算法

1、遗传算法简介Genetic Algorithm (GA)An Brief Introduction一、遗传算法的概述起源和特点：遗传算法是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的 计算模型，是由美国Michigan (密西根)大学的J.Holland教授于1975年首先提出的，是搜索最 优解的一种随机化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，是近十 多年来备受关注的一种算法。搜索机制:遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、 交叉和变异)对这些个

2、体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指生物进化循环图遗传算法概要：对于一个求函数最大值的优化问题(求最小值也类同)，一般可描述为下述数学规划模型:max f(X) (1-1)s.t.X 属于 R (1-2)公属于。(1-3)其中：X=x1,x2，,xnT为决策变量，f(X)为目标函数，(1-2)、(1-3)为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解X称为可行解；集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的 是连续的，有的是离散的；有的是单峰值的，有

3、的是多峰值的。随着研究的深入，人们逐渐认 识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最 优解或满意解是人们的主要着眼点之一。总的来说，求最优解或近似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来解决上述最 优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和 通用框架，开创了一种新的全局优化搜索算法。遗传算法中：将n维决策向量X=%,x2，遇nT用个记号Xi(i=1,2,_,n)所组成的符号串乂来表示：X=XX2.xnX=x1，x2，.,xnT-把每一

4、个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位 基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的个体表现型乂的目标函数 值相关联，乂越接近于目标函数的最优点，其适应度越大；反之，适应度越小。遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。 从而所有的染色体X就组

5、成了问题的搜索空间。生物的进化是以集团为主体的。与此对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体(或 称种群)。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程：第俄群体记做P(t)，经过一代遗传和进化后，得到t+1代群体，记做P(t+1),这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体 更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型乂将达 到或接近于问题的最优解乂*。二、遗传算法的基本流程：Stepl给出一个有N个染色体的初始群体pop(1),t=1；Step2若停止规则满足，则算法停止

6、；否则，对群体pop(t)中每一个染色体popi(t)计算其适应值； Step3从群体pop(t)中随机选一些染色体构成一个种群newpop(t+1)=popj(t)lj=1,2，,N;Step4通过交叉，交叉概率为Pc,得到有N个染色体的crosspop(t+1)Step5对每个新个体依变异概率Pm进行变异，形成mutpop(t+1);t=t+1,新的群体pop(t)=mutpop(t);返回Step2注意：1)newpop(t+1)集中可能重复选pop(t)中的某个元素2)最好的染色体不一定出现在最后一代，所以在进化开始，必须把最好的染色体保留下来，记为V0， 如果在新的种群中又发现了更好

7、的染色体，则用它代替原来的染色体V0,在进化完成之后，这个染色体就可以 看作是最优问题的解。三、遗传算法实现的技术问题：解的编码；初始群体的设定；适应值函数的设计；遗传算子(选择规则；交叉规则；变异规则；) 约束条件的处理；结束准则；运行参数的选择；GA的流程框图编码的主要方法：常规码(二进制编码)每个实数都可以用二进制数表示例(连续变量的编码)：对于给定的区间a,b,设采用二进制编码长为n,则任一变量x=a+ai(b-a)/2+ a (b-a)/22+H a (b-a)/2n对应二进制编码a a - a，二进制码与实际变量的最大误差为(b-a)/2 n(2)有些问题的解可以用0，1变量来表示

8、例(01背包问题)：设有一个容积为b的背包，n个体积分别为ai (i=1,2, -,n)的价值分别为ci (i=1,2,-,n)的物品，如何以最大的价值装包？在这个问题中可以定义xi为决策变量，其中xi = 1表示第i个物品装包，xi = 0表示第i个物品不装包，于是可以按(x1,x2, ,xn)的取值形成一个自然编码。浮点码：每一个染色体由一个向量表示，如用向量x=(x1,x2,xn)表示最优化问题的解，相 应的染色体也是V= (x1,x2, ,xn)(常用于一些多维，高精度要求的连续函数优化问题) 非常规码：非常规的编码与问题联系紧密(基因值取决一个无数值意义，而只有代码意义的符号集)例(

9、TSP旅行商问题)：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij,如何选择一 条道路使得商人每个城市走一遍后回到起点且所走路径最短。？群体的设定：遗传算法的两个主要特点之一就是基于群体搜索的策略，群体的设定，尤其是群体规模的设定，对遗传算 法性能有着重要的影响。这中间包括两个问题：1)初始群体如何设定；2)进化过程中各代的规模如何维持？ 初始群体的设定：遗传算法中初始群体中的个体是按一定的分布随机产生的，一般来讲，初始 群体的设定可以采用如下的策略：根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定 初始群体。先随机生成一定数目的个

10、体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始 群体中个体数达到了预定的规模。群体规模的设定：若群体规模太大，群体中个体的多样性越高，算法陷入局部最优解的危险就越小。另外，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟 阶段，引起未成熟收敛(premature convergence)现象。实际应用中群体规模一般取几十几百。适应值函数的设计：在传统的优化方法中，判断一个解集的好坏是根据目标函数值的大小，而在遗传算法中，则是根据适应值的大 小。因此存在目标函数到适应值函数的对应问题。一般来讲，适应值函数应该满足：非负性；目标函数的优化方向对应

11、适应值增大方向。如果目标函数本身已经满足上述两个条件，可以直接用目标函数代替适应值函数。否则就要设计适当的适应值 函数，下面介绍几种使用比较方便的适应值函数的设计方法。简单适应函数(目标函数的简单变形)max f(x),且在可行域内不是非负函数可适当取适应值函数fitness(x)=f(x)+M,其中M为常数，且保证fitness(x) 30min f(x)可适当取适应值函数fitness(x)=M-f(x),其中M为常数，且保证fitness(x) 30排序适应函数(计算同一代群体中N个染色体的目标函数值)使染色体由好到坏进行排序，即一个染色体越好其序号越小。设参数a仁(0，1)给定， 定义

12、基于序的适应函数为p (Vi) = a (1- a )i-1(i=1,2,N)将染色体由坏到好进行排序，即一个染色体越好其序号越大。定义基于序的2i适应函数为 p (V.) = N(N +1) (i=1,2,N)遗传算子：遗传操作是模拟生物基因遗传的操作。包括三个基本遗传算子(genetic operator)：选择，交叉和变异。这三个遗传算子具有一些特点：这三个算子的操作都是在随机扰动情况下进行的。换句话说，遗传操作是随机化操作，因此，群体中个体 向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作 进行的是高效有向的搜索，而不是如一般随机搜索方法

13、所进行的无向搜索。遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。选择规则:从群体中选择优胜个体，淘汰劣质个体的操作叫选择。根据各个个体的适应度，按照 一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中； 适应度比例选择：最基本的选择方法，其中每个个体被选择的期望数量与其适应度值和群体平 均适应度值的比例有关，通常采用轮盘赌(roulette wheel)方式实现。这种方式首先计算每个 个体的适应度值，然后计算出此适应度值在群体

14、适应度值总和中所占的比例，表示该个体在选 择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。对于给定的规模为n的群体P = ai,a2,一，叩，个体aj G P的适应度值为f(aj其选择概率 n ，/、f (a )ps为：步骤1(a ) =j,j = ，2, . . ., nj 切 f (a )ii =1对每个染色体V.，计算累积概率q.iiq0= 0,5jq =Z p(七)，i = 1,2, , Nj=l步骤2从区间0, q中产生一个随机数r;步骤3若q. 1 Wr W q.,选择第i个染色体V. (1i WN)；步骤4重复步骤2和步骤3共N次，这样可以得到N个

15、染色体.(可能会有重复)交叉规则：群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率(称为交叉概率) 交换它们之间的部分染色体.交叉操作一般分为以下几个步骤：从配对池中随机取出要交配的一对个体；根据位串长度L,对要交叉的一对个体，随机选取1, L-1中一个或多个整数k作为交叉位置；根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，形成新的一对个体。 注意：任何交叉算子需满足交叉算子的评估准则，即交叉算子需保证前一代中优秀个体的性状 能在下一代的新个体中尽可能得到遗传何继承。此外，交叉算子设计和编码设计需协调操作常规码的交叉规则:父代个体子代个体非常规码的常规交

16、叉法随机选一个交叉位，两个后代交叉位之前的基因分别继承双亲的交叉位之前的基因，交叉 位之后的基因分别按异方基因顺序选取不重基因。如父 A1 2 3|4 5 6 78 910子 A1 2 3 | 478 59610父 B4 7 8|3 2 5 91 610子 B4 7 8 | 123 56910浮点码的交叉操作从开区间(0，1)中产生一个随机数c，然后，按以下形式在Vi和Vj之间进行交叉操作， 并产生两个后代X和Y：Y = (1 - c).V + cV.如果可行集是凸的，这种凸组合交叉运算在两个父代可行的情况下，能够保证两个后代也是可行的.但是， 在许多情况下，可行集不一定是凸的，或很难验证其凸

17、性，此时必须检验每一后代的可行性.如果两个后代均 可行，则用它们代替其父代，否则，保留其中可行的(如果存在的话)，然后，产生新的随机数C,重新进行交 叉操作，直到得到两个可行的后代或循环给定次数为止.无论如何，仅用可行的后代取代其父代.变异规则：变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染 色体的结构和物理性状。在遗传算法中，对群体P(t)中的每一个个体，变异算子通过按变异概 率pm随机反转某位等位基因的二进制字符值来实现。注意：变异操作作用于个体位串的等位基因上，由于变异概率比较小，在实施过程中一些个体可能根本不发生 一次变异，造成大量计算资源的浪费。给定一个较小的变异概率Pm