神经网络与遗传算法：计算智能2

第二章遗传算法兔子进化的例子物竞天择(Selection)交配(换)(CrossOver)突变(Mutation)进化GeneticAlgorithms利用自然进化原理的一种搜寻方法。ThreeOperators(ex.兔子)Selection(腿、耳好)CrossoverMutationTwoissuesEncodingtheproblemintoachromosomeDefiningthefitnessfunctionBasicframeofGeneticalgorithm初始化群体评价群体While(不满足结束条件)do基于适应度选择子群体利用交叉产生群体后代后代随机变异EvolutionRunsUntil:性能好的个体出现（如果目标条件已知）或：性能提高缓慢或：用户规定迭代次数一个小例子，求最大值：SimpleGASimulation例最优化问题求函数f(x)=x2的最大值x:[0，31]的整数目标函数作为评价函数利用二进制进行编码110112=19101*24+0*23+0*22+1*21+1*200isthen0000031isthen11111SimpleGASimulation:InitialPopulation假设我们想创建一个种群为4的初始群体可以随机产生20个{0，1}的随机数(4populationsize*stringof5)StringInitialNo.Population1011012 110003 010004 10011SimpleGASimulation:FitnessFunctionStringInitialf(x) Prob.=fi/SumNo.Population1 01101169 0.142 11000

576 0.493 01000

64 0.064 10011

361 0.31 Sum1170 Average293 Max576SimpleGASimulation:RouletteWheelStringInitialf(x) Prob Roulette.No.Population Wheel1 01101 169 0.14 12 11000

576 0.49 23 01000 64 0.06 04 10011 361 0.31 1 Sum1170 Average293 Max576SimpleGASimulation:MatingPoolStringInitialf(x) Prob Roulette.MatingNo.Population Wheel Pool1 01101 169 0.14 1 011012 11000 576 0.49 2 110003 01000 64 0.06 0 110004 10011 361 0.31 1 10011 Sum1170 Average293 Max576SimpleGASimulation:MateStringInitialf(x) Prob Roulette.MatingMateNo.Population Wheel Pool1 01101 169 0.14 1 0110122 11000 576 0.49 2 1100013 01000 64 0.06 0 1100044 10011 361 0.31 1 100113 Sum1170 Average293MateisRandomlyselected Max576SimpleGASimulation:CrossoverStringInitialf(x)Prob R.MatingMateCrossoverNo.Population W Pool1 01101 1690.14 1011012

42 11000 5760.49 211000143 01000 64

0.06 011000424 10011 3610.31 11001132 Sum1170 Average293CrossoverisRandomlyselected Max576SimpleGASimulation:NewPopulationStringInitialf(x)ProbR.MatingMateCrossNewNo.Population W PooloverPop.1 01101 1690.14 10110124 011002 11000 5760.49 21100014 110013 01000 640.06 01100042 110114 10011 3610.31 11001132 10000 Sum1170 Average293 Max576SimpleGASimulation:MutationStringInitialf(x)ProbR.MatingMateCrossNewNo.Population W PooloverPop.1 01101 1690.14 10110124 011002 11000 5760.49 21100014 110013 01000 640.06 01100042 110114 10011 3610.31 11001132 10000 Sum1170 Average293 Max576SimpleGASimulation:MutationStringInitialf(x)ProbR.MatingMateCrossNewNo.Population W PooloverPop.1 01101 1690.14 10110124 011002 11000 5760.49 21100014 100013 01000 640.06 01100042 110114 10011 3610.31 11001132 10000 Sum1170 Average293 Max576SimpleGASimulation:EvaluationNewPopulationStringInitialf(x)Prob R.MatingMateCNewf(x)No.Population W PooloPop.1 01101 1690.14 1011012 4011001442 11000 5760.49 21100014100012893 01000 640.06 01100042110117294 10011 3610.31 1100113210000256 Sum1170 1418Average293354Max576729上述操作过程构成了标准的遗传算法，有时也叫简单遗传算法。其特点：1）利用赌轮选择方法2）随机配对3）采用一点交叉并生成两个子个体4）群体内允许有相同的个体存在InitialPopulation--Problem&Representations遗传算法主要通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断搜索出群体中个体间的结构相似性，以逼近最优解。遗传算法不能直接处理问题空间的参数，必须把他们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，或问题的表示。Problem&Representations染色体以基因型来代表问题的解应有如下特点：可以自发生成可以对基因型的演化进行评价

可以变异可以交叉HowGAsRepresentProblems'Solutions:Genotypes二进制编码—最常用方法浮点数编码混合编码二进制编码比浮点数编码搜索能力强，但浮点数编码比二进制编码在变异操作上能够更好的保持种群多样性。二进制编码采用二进制符号0和1来表现个体的遗传基因型。优点：编码、解码操作简单，交叉、变异等遗传操作便于实现。缺点：不便于反映所求问题的特定知识，对于一些连续函数的优化问题，也由于GA的随机特性而使得局部能力很差。实际问题用二进制编码的步骤1）根据具体问题确定待寻优的参数；2）对每个参数确定它的变化范围，并用一个二进制数来表示，若参数a的变化范围[amin,amax],用m位二进制数b来表示，则两者之间满足参数范围的确定应考虑全部寻优空间，字长m应在满足精度要求情况下尽量取小的m,从而减少GA计算的复杂性。3）将所有表示参数的二进制数串结起来，组成一个长的二进制字串，该字串即为GA的操作对象。已知：f(x)=sin2(x),说明遗传算法在区间[-1，1]上搜索最大值,精度要求小数点后两位。[1-（-1）]/0.01=200200d=11001000bm=8a=00=-1+b*2/255b=125=01111101浮点数编码假设种群中个体数目为n,xti表示第t代的第i（1,2,…n）个个体,每个个体的基因位数L=m,由m个实数构成，个体xti可以表示成m的行向量，即xti={xti(1),

xti

(2),…

xti

(m)

}混合编码将上述两种方式结合InitializationInitialiseapopulationEvaluateapopulationWhile(terminationconditionnotmet)doSelectsub-populationbasedonfitnessProduceoffspringofthepopulationusingcrossoverMutateoffspringstochasticallyInitializationinit(){for(i=0;i<POP_SIZE;i++)//种群大小，一般在10-160之间

for(j=0;j<N;j++)p[i][j]=random_int(2);}GAMainProgramInitialiseapopulationEvaluateapopulationWhile(terminationconditionnotmet)doSelectsub-populationbasedonfitnessProduceoffspringofthepopulationusingcrossoverMutateoffspringstochastically适应度函数选取对适应度函数的要求：适应度函数不能为负。问题是求函数的最大值目标函数映射成适应度函数适应度函数调整目标函数映射成适应度函数在许多问题求解中，其目标是求函数g(x)的最小值，而不是最大值；即使是最大值形式，也不能保证所有的g(x)为非负值。把最小化问题转化成最大化问题，需费用函数乘以-1。但对遗传算法而言，这种方法还不足以保证适应度函数的非负性。目标函数映射成适应度函数方案1：Cmax可以是一个合适的输入值；可以采用迄今为止进化过程中g(x)的最大值，或g(x)的最大值。方案2：式中系数Cmin可以是一个合适的输入值，或是当前代或前k代中g(x)的最小值。适应度函数调整进化过程中有可能出现一些异常个体，这些个体竞争力太突出，从而控制选择过程，从而影响算法的全局优化能力。可以降低这些异常个体的竞争力，可以通过缩小相应的适应度函数值来实现。有时需要扩大相应的适应度函数值。这种适应度的缩放称作适应度调整。线性调整a和b的选择需要满足：原适应度平均值要等于调整后的适应度平均值调整后的适应度函数的最大值要等于原适应度函数平均值所指定的倍数。GAMainProgramInitialiseapopulationEvaluateapopulationWhile(terminationconditionnotmet)doSelectsub-populationbasedonfitnessProduceoffspringofthepopulationusingcrossoverMutateoffspringstochasticallyGAMainProgramfor(trial=0;trial<LOOPS;trial++){selection()crossover()mutation()

for(who=0;who<POP_SIZE;who++)fitness[who]=fv(who);}SelectionInitialiseapopulationEvaluateapopulationWhile(terminationconditionnotmet)doSelectsub-populationbasedonfitnessProduceoffspringofthepopulationusingcrossoverMutateoffspringstochasticallySelection1适应度比例方法：轮盘赌选择方法,MonteCarlo选择方法2最佳个体保存方法3期望值方法4排序选择方法5联赛选择方法轮盘赌方法（RouletteWheelSelection）目前最基本也是最常用的方法。各个个体的选择概率和其适应度值成比例。设

F=j=1topopsizefitnessj以概率

fitnessk/F选择个体

kRouletteWheelSelection根据选择概率把圆盘分成n份在圆盘上选择一个随机位置Fitnessa:1b:3c:5d:3e:2f:2g:8cdefgabRouletteWheelRealization对每一个染色体计算其适应度和累积适应度生成一个随机数（N次）选择其累积适应度值大于所产生的随机数的第一个染色体IndividualChromosomeFitnessCumulativex1101100 20 20x2111000 7 27x3001110 6 33x4101010 10 43x5100011 12 55x6011011 9 64RouletteWheelExampleIndividualChromosomeFitnessCumulativeRandomIndividualx1 101100 20 20 42.8x2 111000 7 27 x3 001110 6 33 x4 101010 10 43 x5 100011 12 55x6 011011 9 64RouletteWheelExampleIndividualChromosomeFitnessCumulativeRandomIndividualx1 101100 20 20 42.8 x4x2 111000 7 27 x3 001110 6 33x4 101010 10 43x5 100011 12 55x6 011011 9 64RouletteWheelExampleIndividualChromosomeFitnessCumulativeRandomIndividualx1 101100 20 20 42.8 x4x2 111000 7 27 19.78x3 001110 6 33x4 101010 10 43x5 100011 12 55x6 011011 9 64RouletteWheelExampleIndividualChromosomeFitnessCumulativeRandomIndividualx1 101100 20 20 42.8 x4x2 111000 7 27 19.78 x1x3 001110 6 33x4 101010 10 43x5 100011 12 55x6 011011 9 64RouletteWheelExampleIndividualChromosomeFitnessCumulativeRandomIndividualx1 101100 20 20 42.8 x4x2 111000 7 27 19.78 x1x3 001110 6 33 42.73 ?x4 101010 10 43 58.44 ?x5 100011 12 55 27.31 ?x6 011011 9 64 28.31 ?RouletteWheelExampleIndividualChromosomeFitnessCumulativeRandomIndividualx1 101100 20 20 42.8 x4x2 111000 7 27 19.78 x1x3 001110 6 33 42.73 x4x4 101010 10 43 58.44 x6x5 100011 12 55 27.31 x3x6 011011 9 64 28.31 x3RouletteWheelSelection存在如下问题：

适应度值不能为负只对最大值问题有效

ParentSelection:Rank按照适应度值对个体进行排序。最差个体序号为1，最好的个体序号为

POPSIZELetF=1+2+3++POP_SIZE以概率rankk/F选择个体kBenefitsofrankselection:

概率全为非负

可以用在maxandmin问题

TournamentSelection从群体中任意选择一定数目的个体（称为联赛规模），适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数目为止。CrossoverMethodsInitialiseapopulationEvaluateapopulationWhile(terminationconditionnotmet)doSelectsub-populationbasedonfitnessProduceoffspringofthepopulationusingcrossoverMutateoffspringstochasticallyCrossoverMethodsCrossoverisaprimarytoolofaGA.(Theothermaintoolisselection.)交叉率：决定染色体是否交叉。一般从0.25到1之间Commontechniquesforbitstringrepresentations:单点交叉：父辈两个个体该点前或后的部分结构进行互换

两点交叉：。。。。。。在这两个交叉点之间的基因链码相互交换。一致交叉：依概率交换父辈个体基因串中的每一位。1-pointCrossover 假设两个串：a，b,每个包含6个变量a1,a2,a3,a4,a5,a6b1,b2,b3,b4,b5,b6代表了问题的两个解.交叉点随机选取，然后结合这两个初始解产生一个新解。设交叉点取2，则a1,a2,

b3,b4,b5,b6b1,b2,

a3,a4,a5,a61-pointCrossoverParentsChildren2-pointCrossover 单点交叉不能将基因的头部信息和尾部信息一起遗传给后代，如果其头尾包含了好的基因信息，那么任何一个后代都不能同时保留这些信息。

两点交叉就可以克服这一缺点。ParentsChildrenUniformCrossover一致交叉是指通过设定屏蔽字来决定新个体的基因继承两个旧个体中哪个个体的对应基因。操作如下：当屏蔽字中的位为0时，新个体继承旧个体A’中对应的基因，当屏蔽字中的位为1时，新个体继承旧个体B中对应的基因，由此生成一个完整的新个体A’。反之，可生成新个体B’。屏蔽字随机产生。UniformCrossoverParentsChild10010110CrossoverMaskUniformCrossovermake_children(intp1,p2,c1,c2){inti,j;for(i=0;i<N;i++){if(random_int(2))p[c1][i]=p[p1][i],p[c2][i]=p[p2][i];elsep[c1][i]=p[p2][i],p[c2][i]=p[p1][i];}}浮点数编码交叉实值重组中间重组线性重组实值重组离散重组是在个体之间交换变量的值。父个体1：3410528父个体2：6145927子个体的每个变量等概率的挑选父个体：子个体1：344598子个体2：6145528中间重组子个体的产生方式：子个体=父个体1+a*(父个体2-父个体1)其中，a是一个比例因子，可由[-d,1+d]上均匀分布随机数产生。对于每个变量要选择一个新的a值。父个体1：3410528父个体2：6145927a值的样本为:样本10.60.20.10.8计算出的新子个体：

50.21747.723.2线性重组与中间重组类似，只是对所有变量取同一个a值父个体1：3410528父个体2：6145927a值样本为0.1子个体：36.713.547.79.9Mutation:PreserveGeneticDiversityInitialiseapopulationEvaluateapopulationWhile(terminationconditionnotmet)doSelectsub-populationbasedonfitness