优化算法之遗传算法-pyy

遗传算法GeneticAlgorithm(GA)主要内容遗传算法简介基本原理研究进展遗传算法的流程流程结构应用举例遗传算法的改进算子选择参数设置混合遗传算法并行遗传算法遗传算法的应用遗传算法在生物信息学中的应用遗传算法是什么？遗传算法（GeneticAlgorithm，GA）是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。

遗传算法的思想来源是怎样的？它由谁提出的？GA思想源于自然界“自然选择”和“优胜劣汰”的进化规律，通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。它最早由美国密歇根大学教授JohnH.Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。遗传算法简介产生60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic

Algorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；发展1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了《遗传算法手册》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。达尔文(Darwin)的进化论进化论是生物学最基本的理论之一。生物学上的所谓进化或者演化（Evolution），旧称“天演”，是指生物在变异、遗传与自然选择作用下的演变发展，物种淘汰和物种产生过程。地球上原来无生命，大约在30多亿年前，在一定的条件下，形成了原始生命，其后，生物不断的进化，直至今天世界上存在着170多万个物种。达尔文用自然选择来解释生物进化。自然选择就是指生物由于环境中某些因素的影响而使得有利于一些个体的生存，而不利于另外一些个体生存的演化过程。简而言之——物竞天择，适者生存达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。孟德尔(Mendel)的遗传学遗传学是研究基因及它们在生物遗传中的作用的科学分支。遗传学最早的应用在有历史记载之初就已经出现了，即驯养动物及植物的选择育种。遗传信息以化学方法被编码在DNA（脱氧核糖核酸）中。1865年，孟德尔首先记录了豌豆某些特性的遗传模式，表明它们遵守简单的统计学规律。由他的统计分析中，孟德尔定义了一个概念：遗传的基本单位——等位基因。他描述的等位基因类于现在的基因。直到孟德尔死后，20世纪初另外的科学家重新发现这个定律之后，孟德尔的工作的重要性才被大家了解。改变一个生物的DNA从而达到某种目的被称为基因工程。生物进化过程遗传基因重组过程群体竞争淘汰的群体变异子群种群婚配生物遗传学基础遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；遗传学基本概念与术语基因型（genotype）：遗传因子组合的模型，染色体的内部表现；表现型（phenotype）：由染色体决定性状的外部表现，基因型形成的个体；ATCGTAATCATA遗传学基本概念与术语个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；种群大小：种群中个体的数量，也叫群体规模。遗传学基本概念与术语进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：个体性能的数量值，度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;遗传学基本概念与术语选择（selection）：指决定以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;遗传学基本概念与术语变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。进化论与遗传学的融合

1930～1947年，达尔文进化论与遗传学走向融合，Th.Dobzhansky1937年发表的《遗传学与物种起源》是融合进化论与遗传学的代表作。生物进化与智能学的关系

生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。如何借鉴？对于一个优化问题，一定数量的候选解（生命个体）被表示为抽象的数字串（染色体），通过进化向更好的解发展。选解一般为二进制数字串（即0和1），但也可能有其他表示。一开始，生命个体完全随机产生，之后一代一代的进化，在进化过程中的每一代，每一个个体的适应程度被评价，通过自然选择和变异产生新的生命群体，该群体就是下一代的个体。选择运算群体p(t)交叉运算变异运算解码群体p(t+1)解集合个体评价遗传空间解空间编码遗传算法原理在遗传算法中，问题的每个有效解被称为一个“染色体

(chromosome)”，也称为“串”，对应于群体中的每个生物个体(individual）。染色体的具体形式是一个使用特定编码方式生成的编码串，编码串中的每一个编码单元称为"基因(gene)"遗传算法通过比较适应值(fitnessvalue)区分染色体的优劣，适应值越大的染色体越优秀。评估函数(evaluationfunction)用来计算并确定染色体对应的适应值。遗传算法原理选择算子(selection)按照一定的规则对群体的染色体进行选择，得到父代种群。一般情况下，越优秀的染色体被选中的次数越多。交叉算子(crossover)作用于每两个成功交配的父代染色体，染色体交换各自的部分基因，产生两个子代染色体。子代染色体取代父代染色体进入新种群，而没有交配的染色体则直接进入新种群。变异算子(mutation)使新种群进行小概率的变异。染色体发生变异的基因改变数值，得到新的染色体。经过变异的新种群替代原有群体进入下一次进化。遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。遗传算法对求解问题的本身一无所知，它所需要的仅仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。再对这个新种群进行下一轮进化。这就是遗传算法的基本原理。遗传算法原理遗传算法原理Holland给出了著名的模式定理(SchemaTheory)

，为遗传算法提供了理论支持。模式(schema)

是指群体中编码的某些位置具有相似结构的染色体集合。

假设染色体的编码是由0或1组成的二进制符号序列，

模式01***0

则表示以01开头且以0结尾的编码串对应的染色体的集合，即{010000，010010，010100，010110，011000，011010，011100，011110}。遗传算法原理模式的阶(schemaorder):模式中具有确定取值的基因个数。

如模式01***0的阶为3模式的定义长度(schemaddefininglength)

是指模式中第一个具有确定取值的基因到最后一个具有确定取值的基因的距离，例如模式01***0的定义长度为5

而模式*1****的定义长度为0遗传算法原理Holland的模式定理提出，遗传算法的实质是通过选择、交叉、变异的遗传算子对模式进行搜索。低阶、定义长度较小且平均适应值高于群体平均适应值的模式在群体中的比例将呈指数级增长。随着进化的不断进行，较优染色体的个数将快速增加。模式定理证明了遗传算法寻求全局最优解的可能性，但不能保证算法一定能找到全局最优解。遗传算法原理积木块假设(BuildingBlockHypothesis)

，对模式定理做了补充，说明遗传算法具有能够找到全局最优解的能力。积木块(buildingblock)

是指低阶、定义长度较小且平均适应值高于群体平均适应值的模式。积木块假设认为在遗传算法运行过程中，积木块在遗传算子的影响下能够相互结合，产生新的更加优秀的积木块，最终接近全局最优解。研究内容和方向遗传算法的流程七个重要问题:染色体的编码群体的初始化适应值评价选择群体种群交配种群变异算法流程选择运算群体p(t)交叉运算变异运算解码群体p(t+1)解集合个体评价遗传空间解空间编码染色体的编码原因：遗传算法只能处理染色体，不能直接在问题解集上进行相应操作。应用遗传算法,需要解决问题解的表示,即染色体的编码编码:将问题结构变换为位串形式编码表示的过程；解码或译码:将位串形式编码表示变换为原问题结构的过程。解空间一个解的编码染色体(chromosome)编码解码编码方法二进制编码方法浮点数编码方法格雷码(Gray)符号编码

二进制编码方法产生的染色体是一个二进制符号序列，染色体的每一个基因只能取值0或1。

假定问题定义的有效解取值空间为[Umin，Umax],其中D为有效解的变量维数，使用L位二进制符号串表示解的一维变量，则我们可以得到如表4.2所示的编码方式:二进制编码方法

假设[Umin，Umax]为[1,64]，采用6位二进制符号串进行编码，则某个二进制符号串010101代表了数值22

L位二进制编码的精度为:

二进制编码的最大缺点是长度较大，当要求采用较高的精度或表示较大范围的数时，必须通过增加L来达到要求。●一维染色体编码指问题空间映射到染色体空间后，其相应的基因呈一维排列构成染色体。一维染色体常用的符号集是二值符号集{0，1}●如果问题解空间是整数，其编码需要两步确定确定编码长度。如果问题解空间范围为x，那么编码长度为

2.确定编码

●确定编码，将整数转换为二进制表示形式。方法：除2取余法。例如：9=(1001)2910014210●如果所求解空间包含负值。如果解空间为整数，可使用添加符号位的方法解决，即正数符号位为0，负数为1+9=(01001)2

-9=(11001)2

如果所求解空间为实数空间？确定编码长度假设范围：[a,b]精度：小数点后4位至少需要的空间存储码长:2.编码(1)转换为整数(2)转换为二进制

例1

问题的解空间为[-3.0,12.1],求1.02编码后的结果，精度为小数点后4位。1.根据精度和解空间大小，确定编码长度

(1)转化为整数(2)转化为二进制2.编码(1)转化为整数

假设转换公式：

将1100100解码是多少呢？(2)转化为实数依据上例编写程序，给定任意N位的染色体，将其转换为解空间为[a,b]的实数。(1)转化为整数doubledecoding(intchrom[]){inti;doublex=0;

returnx;}

(2)转化为实数for(i=0;i<L;i++){x=x+pow(2,N-i-1)*chrom[i];}x=a+(x/(pow(2,N)-1)*(b-a);●2.多参数映射编码优化问题经常碰到带优化的参数不止一个的情况，因此需要采用多参数映射编码。

思想：现将每个参数进行二进制串编码，然后将这个子串生成一个完整的染色体。例如：（2，5，6）----010101110

注：每个子串的码长可以不同。

(2,5,100)----0101011100100

背包问题编码每个染色体用某一范围内的一个浮点数来表示染色体的编码长度等于问题定义的解的变量个数染色体的每一个基因等于解的每一维变量。待求解问题的一个有效解为则该解对应的染色体编码为因为这种编码方法使用的是变量的真实值，所以浮点数编码方法也叫做真值编码方法。对于一些多维、高精度要求的连续函数优化问题，用浮点数编码来表示个体时将会有一些益处。浮点数编码方法格雷码(Gray)是将二进制编码通过一下变换得到的码：设二进码(B1B2…Bn)对应的格雷码为(G1G2…Gn),则从二进码到格雷码的转换为：从格雷码到二进码的转换为:

符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义而只有代码含义的符号集。这个符号集可以是一个字母表，如{A,B,C,D,…}；也可以是一个数字序号表，如{1,2,3,4,5,…}；还可以是一个代码表，如{x1,x2,x3,x4,x5,…}，等等。如:旅行商问题群体的初始化群体的初始化遗传算法在给定的初始进化群体中进行迭代搜索采用生成随机数的方法，对染色体的每一维变量进行初始化赋值初始化染色体时必须满足优化问题对有效解的定义。在算法的开始得到一个平均适应值相对较高的初始群体再进行进化来提高算法的求解性能适应值评价用于评估各个染色体的适应值，区分优劣为了体现染色体的适应能力，引入了对每一个染色体都能进行度量的函数，叫做适应度函数(fitnessfunction)。通过计算适应度函数值来决定染色体的优劣程度，它体现了自然进化中的优胜劣汰原则。在遗传算法中，规定适应值越大的染色体越优。适应度函数要求能有效地反映每一个染色体的适应能力。若一个染色体与问题的最优解染色体之间的差距较小，则对应的适应度函数值就会较大。评估函数常常根据问题的优化目标

来确定，例如求解函数优化问题时，问题定义的目标函数可以作为评估函数的原型。对于一些求解最大值的数值优化问题，我们可以直接套用问题定义的函数表达式。但是对于其他优化问题，问题定义的目标函数表达式必须经过一定的变换。例如TSP的目标是路径总长度为最短，路径总长度变换后就可作为TSP问题的适应度函数：

ωn+1=ω1,d(ωj,ωj+1)表示两城市间的距离(路径长度)。选择运算群体p(t)交叉运算变异运算解码群体p(t+1)解集合个体评价遗传空间解空间编码遗传操作遗传算法的遗传操作主要有三种：选择算子(selection)交叉算子(crossover)变异算子(mutation)选择算子选择操作也叫做复制(reproduction)操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。一般地，适应度较大(优良)的个体有较大的存在机会，而适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制.根据每个染色体的适应值得到群体中所有染色体的适应值总和。计算每个染色体适应值与群体适应值总和的比Pi

假设一个具有N

个扇区的轮盘，每个扇区对应群体中的一个染色体，扇区的大小与对应染色体的Pi值成正比。交叉算子交叉操作的简单方式是:按交叉概率Pc选择出两个父代个体P1和P2，将两者的部分码值进行交换。交叉概率的Pc

一般取值为：0.4~0.99之间。随机数

Random(0,1)

小于Pc

，则表示该染色体可进行交叉操作随机产生一个有效的交配位置，父代染色体交换位于该交配位置后的所有基因编码长度为8，产生一个在1~7之间的随机数k，假如现在产生的是5,将P1和P2的后3位基因交换：P1的高5位与P2的低三位组成数串10001001,这就是P1和P2的一个子代个体Q1

；P2的高5位与P1的低3位组成数串11011110,这就是P1和P2的另一个子代Q2个体。交换过程如图所示69单点交叉运算的伪代码:procedure:

One-cutPointCrossoverinput:pC,parentPk,k=1,2,...,popSizeoutput:offspringCkBegin

pos

c()for

k=1topopSize

//popSize:populationsize ifpcrandom[0,1]

//pC:theprobabilityofcrossover

pos=c(pos,k)

else

CkPkend

endwhile(length(pos)>1)

i

random[1,pos];

j

random[1,pos];

if

(i≠j)

p

random[1,L-1];//p:thecutposition,L:thelengthofchromosome

CiPi

[1:p-1]//Pj

[p:L];

CjPj

[1:p-1]//Pi

[p:L

];pospos\{i,j}

endend

outputoffspringCk;end变异操作的简单方式就是改变码串中某个位置上的数码变异概率的Pm一般取值为：0.001~0.1之间。随机数

Random(0,1)小于Pm

，则表示该染色体上的基因可进行变异操作随机产生一个有效的变异位置，染色体上位于该位置的基因发生改变变异算子二进制编码表示的每个位置的数码只有0和1两种可能，二进制编码的简单变异操作是将0与1互换：0变异为1，1变异为0。设有如下二进制编码：码长为8，随机产生一个1~8之间的数k，假如现在k=5，对第5位(从右到左)进行变异操作，将原来的0变为1，得到如下数码串：浮点数编码形式的染色体若某基因发生变异，则可采用随机数方法随机产生一个满足问题定义的数值取代该基因现有的值。procedure:Mutationinput:pM,parentPk,k=1,2,...,popSizeoutput:offspringCkbeginfor

k=1topopSize

//popSize:populationsize forj=1to

L

//L:thelengthofchromosome

ifpMrandom[0,1]

//pM:theprobabilityofmutation

Pk[j]

=1-Pk[j]

; //p:thecutposition

CkPk

[1:j-1]//Pk

[j]//Pk[j+1:L]; end endendoutputoffspringCk;end变异运算的伪代码:算法流程：一般遗传算法的主要步骤如下Step1初始化规模为N的群体，其中染色体每个基因的值采用随机数产生器生成并满足问题定义的范围。当前进化代数Generation=0。Step2用评估函数对群体中所有染色体进行评价，分别计算每个染色体的适应值,保存适应值最大的染色体BestStep3采用轮盘赌选择运算对群体的染色体进行选择操作，产生规模同样为N的种群。Step4按照概率Pc从种群中选择染色体进行交叉运算。两两父代染色体交换部分基因，产生两个新的子代染色体，子代染色体取代父代染色体进入新种群。没有进行交配的染色体直接复制进入新种群。Step5按照概率Pm对新种群中染色体的基因进行变异操作。发生变异的基因数值发生改变。变异后的染色体取代原有染色体进入新群体，未发生变异的染色体直接进入新群体。Step6变异后的新群体取代原有群体，重新计算群体中各个染色体的适应值。倘若群体的最大适应值大于Best的适应值，则以该最大适应值对应的染色体替代Best，即更新最大适应值大于Best。Step7当前进化代数Generation加l。如果Generation超过规定的最大进化代数或Best达到规定的误差要求，算法结束，Best可表示问题的一个解;否则返回Step3输出种群中适应度值最优的染色体作为问题的满意解或最优解。算法的停止条件最简单的有如下两种：①完成了预先给定的进化代数则停止；②种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。用遗传算法求解优化问题其中为整数。用遗传算法求解优化问题其中为整数。解:(1)确定初始种群①参数编码将整数

x*{0,1,…,31}作为参数，采用二进制进行编码：X=0—>00000，……x=31—>11111②随机生成例如:①01001；②11001；

③01000；④10011。③随机选择适者个体

采用轮盘法，对初始种群进行选择，使得最优秀的个体获得最多的生存繁殖机会。(3)交叉将选择出的个体存入交配池中，用随机方法配对交叉，以产生新一代的个体①随机选择配对；②随机选择交叉点；③采用单点交叉，产生新的种群(4)变异在交叉过程中，可能丢失一些重要的遗传信息(特定位置的1与0)，因而产生变异。为了获得新的遗传信息，则需引入适度的变异。遗传算法的特点遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。因此，遗传算法的求解过程也可看做是最优化过程。遗传算法并不能保证所得到的是最佳答案，但通过一定的方法，可以将误差控制在容许的范围内。遗传算法具有以下特点：

(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；

(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度值这一信息而非利用导数或其他辅助信息来指导搜索；

(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题。它不受搜索空间的限制性假设的约束，不必要求诸如连续性，导数存在和单峰等假设，能从离散的、多极值的、含有噪音的高维问题中以很大的概率找到全局最优裤。确定性采样(DeterministicSampling)排挤模型（CrowdingModel）最佳个体保存模型（ElitistModel）适应值比例模型（fitnessproportionmodel）

排序模型(rank-basedmodel)随机锦标赛模型(StochastictournamentModel)无回放余数随机采样(Remainderstochasticsamplingandreplacement)期望值模型(expectedvaluemodel)选择算子遗传算法的改进遗传算法的改进交配算子单性孢子交配算子边重组交配算子循环交配算子顺序交配算子部分匹配交配算子多点交配算子算术交配算子均匀交配算子两点交配算子边集合交配算子遗传算法的改进非均匀变异算子高斯变异算子边界变异算子变异算子

群体规模N√影响算法的搜索能力和运行效率。若N设置较大，一次进化所覆盖的模式较多，可以保证群体的多样性，从而提高算法的搜索能力，但是由于群体中染色体的个数较多，势必增加算法的计算量,降低了算法的运行效率。若N设置较小，虽然降低了计算量，但是同时降低了每次进化中群体包含更多较好染色体的能力问。N的设置一般为20~100。参数设置

染色体的长度L√影响算法的计算量和交叉变异操作的效果。L的设置跟优化问题密切相关，一般由问题定义的解的形式和选择的编码方法决定。对于二进制编码方法，染色体的长度L根据解的取值范围和规定精度要求选择大小。对于浮点数编码方法，染色体的长度L跟问题定义的解空间维数D相同。除了染色体长度一定的编码方法，Goldberg等人还提出了一种变长度染色体遗传算法MessyGA，其染色体的长度并不是固定的。参数设置

基因的取值范围R√R视采用的染色体编码方案而定。对于二进制编码方法，R={0，1}对于浮点数编码方法，R与优化问题定义的解每一维变量的取值范围相同。参数设置交叉概率Pc√决定了进化过程中，种群参加交叉运算的染色体的平均数目Pc×N。Pc的取值范围一般为0.4~0.99也可采用自适应的方法调整算法运行过程中的Pc

值参数设置变异概率Pm√增加群体进化的多样性，决定了进化过程中群体发生变异的基因平均个数。Pm的值不宜过大。因为变异对己找到的较优解具有一定的破坏作用，如果Pm的值太大，可能会导致算法目前所处的较好的搜索状态倒退回原来较差的情况。Pm的取值一般为0.001~0.1也可采用自适应的方法调整算法运行过程中的Pm值参数设置适应值评价√影响算法对种群的选择，恰当的评估函数应该能够对染色体的优劣做出合适的区分，保证选择机制的有效性，从而提高群体的进化能力。评估函数的设置同优化问题的求解目标有关。评估函数应满足较优染色体的适应值较大的规定。为了更好地提高选择的效能，可以对评估函数做出一定的修正。目前主要的评估函数修正方法有:令线性变换令乘客变换令指数变换等参数设置终止条件√决定算法何时停止运行，输出找到的最优解。采用何种终止条件，跟具体问题的应用有关。可以使算法在达到最大进化代数时停止，最大进化代数一般可设置为100~1000，根据具体问题可对该建议值作相应的修改。也可以通过考察找到的当前最优解的情况来控制算法的停止。例如，当目前进化过程算法找到的最优解达到一定的误差要求，则算法可以停止。误差范围的设置同样跟具体的优化问题相关。或者是算法在持续很长的一段进化时间内所找到的最优解没有得到改善时，算法可以停止。参数设置混合遗传算法√提高遗传算法求解问题的能力。并行组合模拟退火算法(ParallelRecombinationSimulatedAnneali吨，PRSA)并行模拟退火遗传算法(ParallelSimulatedAnnealingandGeneticAlgorithms,PSAGA)贪婪遗传算法(GreedyGenetic<Algorithm,GGA)遗传比率切割算法(GeneticRatio-CutAlgorithm,GRCA)遗传爬山法(GeneticHillclimbi吨Algorithm，GHA)引人局部改善操作的混合遗传算法免疫遗传算法(lmmuneGeneticAlgorithm,IGA)

并行遗传算法√算法从整体的流程上看仍然是串行的，但是算法运行过程中对每个染色体的处理却是具有潜在的并行性。标准型并行方法(StandardParallelApproach)

没有根本改变遗传算法整体上的串行计算结构，只是在算法的某些操作中引入并行计算技术，这些操作包括适应值计算、选择操作、交配操作、变异操作等分解型并行方法(DecompositionParallelApproach)

将整个群体分解成几个子群体，各个子群体分配到不同的计算资源上分别独立地使用原有的遗传