Ch8-进化控制与免疫控制

中南大学CentralSouthUniversity(CSU)1IntelligentControl智能控制蔡自兴肖晓明余伶俐中南大学CentralSouthUniversity(CSU)Ch.8EvolutionalControlandImmuneControl第八章进化控制与免疫控制讲授：蔡自兴中南大学CentralSouthUniversity(CSU)8.1遗传算法简介8.2进化控制基本原理8.3进化控制系统示例8.4免疫算法和人工免疫系统原理8.5免疫控制基本原理8.6免疫控制系统示例8.7小结本章重点和难点中南大学CentralSouthUniversity(CSU)4进化计算与人工生命进化计算内容遗传算法(geneticalgorithms,GA)进化策略(evolutionstrategies)进化编程(evolutionaryprogramming)遗传编程(geneticprogramming)人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。上述方向是人工智能和计算智能的一个新的研究热点。中南大学CentralSouthUniversity(CSU)问题1什么是进化？中南大学CentralSouthUniversity(CSU)8.1IntroductiontoGeneticAlgorithm遗传算法简介8.1.1BasicMechanismofGA基本原理遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。中南大学CentralSouthUniversity(CSU)78.1.1BasicMechanismofGA霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。编码与解码Encoding&Decoding适应度函数FitnessFunction遗传操作GeneticOperation中南大学CentralSouthUniversity(CSU)8.1.1BasicmechanismofGA遗传算法的基本机理遗传算法研究的进展GeneticAlgorithms(Holland–1975)InspiredbygeneticsandnaturalselectionSimulatedAnnealing(Kirkpatrick–1983)Inspiredbymoleculardynamics–energyminimizationParticleSwarmOptimization(EberhartandKennedy-1995)Inspiredbythesocialbehaviorofswarmsofinsectsorflocksofbirds这些技术都用于随机性和启发性组合，以便指导全局最大化或最小化的搜索求解。中南大学CentralSouthUniversity(CSU)8.1.1BasicmechanismofGAGATerminology术语中南大学CentralSouthUniversity(CSU)名词解释Genes（基因）：AnindividualischaracterizedbyasetofparametersChromosome（染色体）：ThegenesarejoinedintoastringParametersofthesolution(genes)areconnectedtoformastring(chromosome)Fitnessfunction（适应度函数）isafunctionintherealworldtomeasurethechromosomes对问题中的每个染色体进行度量的函数，体现优胜劣汰。中南大学CentralSouthUniversity(CSU)BasicprinciplesofGAEncoding&Decoding编码把问题结构（参数）变换为位串形式的表示过程。Stringwithallparameters解码把位串形式编码表示变换为原问题结构（参数）的过程遗传操作选择Selection/Reproduction交叉Crossover变异Mutation中南大学CentralSouthUniversity(CSU)编码与解码Encoding&DecodingAllkindofalphabets（字母）canbeusedforachromosome(numbers,characters),butgenerallyabinaryalphabetisusedForexample：chromosomescouldbe:Bitstrings(0101...1100)Realnumbers(43.2-33.1...0.089.2)Permutationsofelement(E11E3E7...E1E15)Listsofrules(R1R2R3...R22R23)Programelements(geneticprogramming)...anydatastructure...中南大学CentralSouthUniversity(CSU)Examples中南大学CentralSouthUniversity(CSU)假设某一参数的取值范围是[A,B]，AB。用长度为A的二进制编码串来表示该参数，将[A,B]等分成2A-1个子部分，记每一个等分的长度为δ，则它能够产生2A种不同的编码。BinaryEncoding二进制编码问题二δ应如何表示？中南大学CentralSouthUniversity(CSU)参数编码的对应关系如下：00000000…00000000=0ÆA00000000…00000001=1ÆA+δ………………11111111…11111111=2l-1ÆB其中12−−=lABδBinaryEncoding中南大学CentralSouthUniversity(CSU)Decoding1221:xxxxxXlll−−假设某一个体的编码是:∑=−•−−+=liiilxABAx11212则上述二进制编码所对应的解码公式为：中南大学CentralSouthUniversity(CSU)编码举例例：用遗传算法求解函数的最大值，其中。0.1)10sin()(+••=xxxfπ]2,1[−∈x由染色体来代表变量x的实数值。用一个二进制矢量表示一个染色体矢量长度取决于所要求的精度，在此取小数点后6位数。变量x域长为3，则[-1,2]将被均匀地分为3×106个等长区间。每个染色体由22位字节的二进制矢量表示。因为：419430423000000220971522221=≤=中南大学CentralSouthUniversity(CSU)区间[-1,2]中的x和二进制串b21b20┉b0是直接映射的，并由以下两步进行：∑==•=21010202021')2()(iiixbbbb(a)将二进制串转化为相应的十进制数：123'0.122−•+−=xx(b)找到相应的实数x：其中-1.0为区间[-1,2]的左边界，3为区间长度。编码举例中南大学CentralSouthUniversity(CSU)显然(0000000000000000000000)和(1111111111111111111111)分别表示区间的左右边界-1.0和2.0。把x=0.637197代入下式即可求得函数的最大值：=0.637197*Sin(66.9546°)+1.0=1.58622可将实数以二进制数（染色体）来表述，如(1000101110110101000111)表示实数0.637197，因为2288967)1111010100011000101110('2==x637197.04194303322889670.1=•+−=x编码解码举例Encoding&Decoding0.1)10sin()(+••=xxxfπ中南大学CentralSouthUniversity(CSU)Reproduction/selection选择，即复制（Copy）Crossover交叉Mutation变异遗传操作中南大学CentralSouthUniversity(CSU)遗传操作CrossoverTwoparentsproducetwooffspringThereisachancethatthechromosomesofthetwoparentsarecopiedunmodifiedasoffspringThereisachancethatthechromosomesofthetwoparentsarerandomlyrecombined(crossover)toformoffspringGenerallythechanceofcrossoverisbetween0.6and1.0MutationThereisachancethatageneofachildischangedrandomlyGenerallythechanceofmutationislow(e.g.0.001)中南大学CentralSouthUniversity(CSU)CrossoverinBiology中南大学CentralSouthUniversity(CSU)ReproductionOperatorsCrossoverGeneratingoffspringfromtwoselectedparentsSinglepointcrossoverTwopointcrossover(Multipointcrossover)Uniformcrossover中南大学CentralSouthUniversity(CSU)One-pointcrossover1RandomlyonepositioninthechromosomesischosenChild1isheadofchromosomeofparent1withtailofchromosomeofparent2Child2isheadof2withtailof1Parents:10100011100011010010Offspring:01010100100011001110Randomlychosenposition中南大学CentralSouthUniversity(CSU)One-pointcrossover-Nature12121221中南大学CentralSouthUniversity(CSU)Two-pointcrossoverRandomlytwopositionsinthechromosomesarechosenAvoidsthatgenesattheheadandgenesatthetailofachromosomearealwayssplitwhenrecombinedParents:10100011100011010010Offspring:10100100100011001110Randomlychosenpositions中南大学CentralSouthUniversity(CSU)ReproductionOperatorsComparisonSinglepointcrossoverCrosspointÆÆ•Twopointcrossover(Multipointcrossover)中南大学CentralSouthUniversity(CSU)8.1.2SolvingprocedureofGA遗传算法的求解步骤1.遗传算法的特点(1)遗传算法是对参数集合的编码而非针对参数本身进行进化。(2)遗传算法是从问题解的编码组开始搜索而非从单个解开始搜索。(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索。(4)遗传算法利用选择、交叉