遗传算法的产生

遗传算法的产生

早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；

1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；

60年代，L.J.Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了《基于模拟进化的人工智能》，系统阐述了进化规划的思想。

60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；

1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；

1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。遗传算法的发展

70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；

1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；

1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；

1991年，L.Davis编辑出版了《遗传算法手册》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。遗传算法——进化计算——计算智能——人工智能遗传学基本概念与术语

染色体（chromosome）：遗传物质的载体；

脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；

核糖核酸（RNA）：核酸的一类。由核苷酸通过3′，5′-磷酸二酯键连接而成的多聚体。不同种类的RNA链长不同，行使各式各样的生物功能。

遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；

基因型（genotype）：遗传因子组合的模型；

表现型（phenotype）：由染色体决定性状的外部表现；

个体（individual）：指染色体带有特征的实体；

种群（population）：个体的集合，该集合内个体数称为种群的大小；

进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；

适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝；

选择（selection）：指决定以一定的概率从种群中选择若干个体的操作（实现优胜劣汰）；

复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因；

交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”；

变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状；

编码（coding）：表现型到基因型的映射；

解码（decoding）：从基因型到表现型的映射。遗传算法的原理遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成，每个个体实际上是染色体带有特征的实体，初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：

在每一代，根据问题域中个体的适应度大小挑选个体，并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。

这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。

基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。遗传算法的基本流程遗传算法的特点

遗传算法的本质并行性。

首先，遗传算法以并行的方式从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的，容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。

其次，算法内含并行性。遗传算法采用种群方式组织搜索，因而可同时搜索解空间的多个区域，并相互交流信息，能以较小的计算获得较大的收益。

遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导其搜索方向。

具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

遗传算法可更直接地应用，对给定的问题，可以产生许多潜在解，最终选择可以由使用者指定，通用性高，应用范围广。遗传算法的基本操作

遗传基因型(编码)

编码方式

二进制编码、浮点数编码、格雷码编码、符号编码、复数编码、DNA编码等。

以大象灰色皮肤为例：二进制编码：，浮点编码：127.0

编码原则

完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；

健全性（soundness）：任何一个基因型都对应于一个可能解；

非冗余性（non-redundancy）：问题空间和表达空间一一对应。

二进制编码与浮点数编码的比较

在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；

在变异操作时，二进制编码的种群稳定性比浮点数编码差。

选择

适应度计算：

按比例的适应度函数（proportionalfitnessassignment）：

基于排序的适应度计算（Rank-basedfitnessassignment）：

选择算法：

轮盘赌选择（roulettewheelselection）：

随机遍历抽样（stochasticuniversalselection）：

局部选择（localselection）：

截断选择（truncationselection）：

锦标赛选择（tournamentselection）：

交叉或基因重组

二进制交叉（binaryvaluedcrossover）：

单点交叉（single-pointcrossover）

多点交叉（multiple-pointcrossover）

均匀交叉（uniformcrossover）

洗牌交叉（shufflecrossover）

缩小代理交叉（crossoverwithreducedsurrogate）

实值重组（realvaluedrecombination）：

离散重组（discreterecombination）

中间重组（intermediaterecombination）

线性重组（linearrecombination）（均匀、非均匀）

扩展线性重组（extendedlinearrecombination

交叉方式

半种群交叉(N/2)：对群体中的要交叉的个体进行两两随机配对。若群体大小为M，则最多共有[M/2]对相互配对的个体组参与交叉。(若种群数为奇数，则其中任一个个体多选一次配对)

全种群交叉(N)：对群体中要交叉的个体，从种群中随机挑选一个个体与其完成交叉操作，最多共有M对相互配对的个体参与变异。

变异方法

二进制变异

单点变异

逆序变异

均匀变异

实值变异

随机变异

边界变异

非一致变异

自适应变异

高斯变异

变异方式

基于个体的变异：即对任意一个个体，判断其是否进行变异操作，如果是，则随机生成一个变异基因发生变异操作。

基于基因座的变异：即对种群中的个体，判断每一个个体的每一位基因是否进行变异操作，如果是，则发生变异操作。遗传算法的应用

函数优化：是遗传算法的经典应用领域；

组合优化：实践证明，遗传算法对于组合优化中的NP完全问题非常有效；

自动控制：如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等；

机器人智能控制：遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面广泛得到了应用；

组合图像处理和模式识别：目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用；

人工生命：基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；

遗传程序设计：Koza发展了遗传程序设计的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序；

机器学习：机器学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。基本遗传算法遗传算法在自然与社会现象的模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进。为不至于混淆，把Holland提出的算法称为基本遗传算法，简称为SGA（SimpleGeneticAlgorithm)，也有称其为(GA、CGA)。以SGA为例，阐述遗传算法的设计与实现方法。

SGA的构成要素：

染色体编码方法：基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x：就可表示一个个体，该个体的染色体长度是l＝18。

个体适应度评价：基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。

遗传算子：基本遗传算法使用下述三种遗传算子：

选择运算：使用比例选择算子；

交叉运算：使用单点交叉算子；

变异运算：使用基本位变异算子。

基本遗传算法的运行参数：基本遗传算法有下述4个运行参数需要提前设定：

M：群体大小，即群体中所含个体的数量，一般取为20∽100。

T：遗传运算的终止进化代数，一般取为100∽500

pc：交叉概率，一般取为0.4∽0.99

pm：变异概率，一般取为0.0001∽0.1说明：这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。

基本遗传算法的描述基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算子；c——交叉操作算子：m——变异操作算子；pc——交叉概率；pm——变异概率。

编码与解码

编码假设某一参数的取值范围是[umin,umax]，我们用长度为len的二进制编码符号串来表示该参数，则它总共能够产生2len种不同的编码，参数编码时的对应关系如下：…＝0umin…＝1umin+d………=2len–1umax其中，d为二进制编码的编码精度，其公式为：

解码假设某一个体的编码是：x：blenblen-1blen-2……b2b1，则对应的解码公式为：

[例]设-3.0≤x≤12.1，精度要求＆=1/10000，由公式：得到：即：217<<218x需要18位{0/1}符号表示。如：解码：

个体适应度评价如前所述，要求所有个体的适应度必须为正数或零，不能是负数。(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)＝f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)＝max(-f(X))但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求，需要进行适应度函数尺度转换，将目标函数值f(x)变换为个体的适应度F(x)。(3)SGA适应度函数变换常用方法：方法一：对于求目标函数最大值的优化问题，变换方法为：其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：?预先指定的一个较小的数。?进化到当前代为止的最小目标函数值。?当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：?预先指定的一个较大的数。?进化到当前代为止的最大目标函数值。?当前代或最近几代群体中的最大目标函数值。

比例选择算子指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。pi=fi/∑fi(i=1,2,…,M)式中pi——个体i被选中的概率；fi——个体i的适应度；∑fi——群体的累加适应度。显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。执行比例选择的手段是轮盘选择。个体被选中的概率取决于个体的相对适应度：从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被“破格”选中。

单点交叉算子Ⅰ.对群体中的个体进行两两随机配对。若群体大小为M，则共有[M/2]对相互配对的个体组。Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为len，则共有(len-1)个可能的交叉点位置。Ⅲ.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。单点交叉运算的示例如下所示：

基本位变异算子对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有基因值为1，则变异操作将其变为0。基本位变异因子的具体执行过程是：Ⅰ.对个体的每一个基因座，依变异概率pm指定其为变异点。Ⅱ.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。基本位变异运算的示例如下所示：

变异概率变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm也是针对基因而言，即：式中：B——每代中变异的基因数目；M——每代中群体拥有的个体数目len——个体中基因串长度。GA算法流程图简单函数优化实例

问题的提出：一元函数求最大值：

编码表现型：x基因型：二进制编码（串长取决于求解精度）按编码原理：假设要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.=3×106等份。所以编码的二进制串长应为22位。

产生初始种群产生的方式：随机产生的结果：长度为22的二进制串产生的数量：种群的大小（规模），如30，50，………

计算适应度直接用目标函数作为适应度函数①解码：将个体s转化为[-1,2]区间的实数：s=<>→x=0.②计算x的函数值（适应度）：f(x)=xsin(10πx)+2.0=2.

遗传操作选择：比例选择法；交叉：单点交叉；变异：小概率变异

模拟结果设置的参数：种群大小50；交叉概率0.75；变异概率0.05；最大代数200。得到的最佳个体：smax=<>;xmax=1.8506;f(xmax)=3.8503;遗传算法的改进

传统的GA在解决时就存在如下问题：首先，模型复杂，参数太多难以达到优化目的，优化速度慢且达不到最优解。其次，约束条件复杂、繁多，算法收敛的时候很难满足约束条件。因此，在处理交通控制问题上扬长避短，需要改进遗传算法，使其达到智能控制的效果。

改进措施改变遗传算法的组成成分；采用混合遗传算法；采用动态自适应技术；采用非标准的遗传操作算子；采用并行遗传算法等。

参数分析交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；Pc过小，搜索过程缓慢，以至停止不前；Pm过小，不易产生新个体结构，Pm过大，变成纯粹的随机搜索。

自适应策略Srinvivas等提出一种自适应遗传算法，Pc和Pm能够随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加；而当群体适应度比较分散时，使Pc和Pm减少；对于适应度较高的个体，对应于较低的Pc和Pm；而较低适应度的个体，对应于较高的Pc和Pm。

自适应方法fmax——群体中最大的适应度值；favg——每代群体的平均适应度值；f’——要交叉的两个个体中较大的适应度值；f——要交叉或变异的个体适应度值。k1、k2、k3、k4取(0,1)的值。

自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由0提高到Pc2和Pm2；采用精英选择策略；CHC算法

改进思路1991年Eshelman提出的一种改进遗传算法；C：跨世代精英选择（Crossgenerationalelitistselection）策略；H：异物种重组（Heterogeneousrecombination）；C：大变异（Cataclysmicmutation）。

选择上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。

交叉均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的交换；确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。

变异在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般0.35）的基因座，随机地决定它们的位值。基于小生境技术的遗传算法

小生境概念小生境（niche）：生物学中，特定环境中的一种组织功能；在SGA中，容易“近亲繁殖”；NGA（NicheGenericAlgorithm），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。

选择策略预选择（preselection,1970）机制：当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留，从而有效维持种群多样性，造就小生境进化环境。排挤（crowding,1975）机制：设置排挤因子CF（CF=2或3），随机选取1/CF个个体组成排挤成员，排挤与其相似（用距离来度量）的个体，使个体之间的相似性可用个体编码串之间的海明距离来度量。共享（sharing,1987）机制：通过个体之间的相似性程度的共享函数来调整各个体的适应度。共享函数的目的是将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关。共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体i和j之间的距离。σshare是niche的半径，由使用者给定。共享法将个体的适应度降低，即适应度值fi除以一个niche计数mi：在距离为σshare的范围内的个体彼此削减适应度，这些个体将收敛在一个niche内，避免了整个种群的收敛。退火进化算法退火进化算法(annealingevolutionalgorithm,AEA）遗传算法（GA)模拟退火算法（SA）是人工智能中用于解决组合优化问题的经典。但是，SA在全局搜索能力方面不足，GA在局部搜索能力方面不足。而退火进化算法（annealingevolutionalgorithm,AEA)综合了SA和GA算法，优势互补，发挥SA局部搜索能力和GA全局搜索能力,克服SA全局搜索能力差及效率不高的问题和GA局部搜索能力差及其早熟现象。AEA把SA算法与GA结合在一起，通过变异与选择不断改善解群体，并行搜索解空间，从而有可能更迅速地找到全局最优解。由于在选择中采用Metropolis准则，因而保留了SA算法易跳出某局部极值“陷阱”的优点，易于向全局极小值快速收敛。算法求解过程如下：(1)初始化进化代数计数器k←0，随机给出种群P(k)初值，给定初试退火温度T0。(2)评价当前群体