进化算法 遗传算法课件

1.IntroductiontoGeneticAlgorithms进化算法遗传算法优化问题对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型：SoftComputingLab.2进化算法遗传算法例：无约束单目标，多峰SoftComputingLab.3进化算法遗传算法约束单目标SoftComputingLab.4进化算法遗传算法约束多目标SoftComputingLab.5进化算法遗传算法TSP旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。（n-1)!/2SoftComputingLab.6进化算法遗传算法TSP

ADECBTheonebelowislength:33ABCDEA57415B53410C7327D4429E151079SoftComputingLab.7进化算法遗传算法传统最优化面临新挑战：实际问题离散性问题——主要指组合优化不确定性问题——随机性数学模型半结构或非结构化的问题大规模问题：超高维动态优化问题有噪的现代优化方法：追求满意—近似解实用性强—解决实际问题SoftComputingLab.8进化算法遗传算法优化问题的复杂性Complexity:HardproblemsandEasyproblemsWhenSissmall(e.g.10,100,oronly1,000,000orsoitems),wecansimplydoso-calledexhaustivesearch(穷举搜索)Exhaustivesearch:Generateeverypossiblesolution,workoutitsfitness,andhencediscoverwhichisbest(orwhichsetsharethebestfitness)

比如从n个数找到最大ThisisalsocalledEnumeration(列举法）SoftComputingLab.9进化算法遗传算法问题的复杂度

Thisisallaboutcharacterisinghowharditistosolveagivenproblem.Statementsaremadeintermsoffunctionsofn,whichismeanttobesomeindicationofthesizeoftheproblem.E.g.:（通过n的一个函数来描述问题的复杂度）Correctlysortasetofnnumbers（排序）Canbedoneinaround

nlognstepsFindtheclosestpairoutofnvectors（从n个向量找出最接近两个)CanbedoneinO(n2)stepsFindbestmultiplealignmentofnsequences.CanbedoneinO(2n)steps…SoftComputingLab.10进化算法遗传算法PolynomialandExponentialComplexityGivensomeproblemQ,with`size’n,imaginethatAisthefastestalgorithmknownforsolvingthatproblemexactly.ThecomplexityofproblemQisthetimeittakesAtosolveit,asafunctionofn.(问题Q的维数为n，A是一个已知快速算法，复杂度就是通过A求解Q所用时间)Therearetwokeykindsofcomplexity:Polynomial:

thedominanttermintheexpressionispolynomialinn.E.g.n34,n.log.n,sin(n2.2),etc…Exponential:thedominanttermisexponentialinn.E.g.1.1n,nn+2,2n,…SoftComputingLab.11进化算法遗传算法PolynomialandExponentialComplexity

1.1n1.211.331.461.611.772.596.7311713,780n1.12.143.354.595.877.1812.627.073.9159n23456102050100ProblemswithexponentialcomplexitytaketoolongtosolveatlargenSoftComputingLab.12进化算法遗传算法Polynomial

Complexity:thesearecalledtractable,andeasyproblems.Fastalgorithmsareknownwhichprovidethebestsolution.

ExponentialComplexity:thesearecalledintractable,andhardproblems.Thefastestknownalgorithmwhichexactlysolvesitisusuallynotsignificantlyfasterthanexhaustivesearch.(为所谓的Hard难问题,已有的快速算法与穷举算法相比较并没有明显的提高)SoftComputingLab.13进化算法遗传算法polynomialexponential指数复杂度一般要比多项式复杂要复杂F(n)IncreasingnSoftComputingLab.14进化算法遗传算法随机算法：爬山法0.Initialise:Generatearandomsolutionc;evaluateitsfitness,f(c).Callcthecurrentsolution.1.Mutateacopyofthecurrentsolution–callthemutantm

Evaluatefitnessofm,f(m).2.Iff(m)isnoworse

thanf(c),thenreplacecwithm,otherwisedonothing(effectivelydiscardingm).3.Ifaterminationconditionhasbeenreached,stop.Otherwise,goto1.Note.Nopopulation(well,populationof1).ThisisaverysimpleversionofanEA,althoughithasbeenaroundformuchlonger.SoftComputingLab.15进化算法遗传算法

12435,867910SoftComputingLab.16进化算法遗传算法易陷入局部最优SoftComputingLab.17进化算法遗传算法1.IntroductionofGeneticAlgorithmsFoundationsofGeneticAlgorithms1.1IntroductionofGeneticAlgorithms1.2GeneralStructureofGeneticAlgorithms1.3MajorAdvantagesExamplewithSimpleGeneticAlgorithms

2.1Representation2.2InitialPopulation2.3Evaluation2.4GeneticOperatorsEncodingIssue3.1CodingSpaceandSolutionSpace3.2SelectionSoftComputingLab.18进化算法遗传算法1.IntroductionofGeneticAlgorithmsGeneticOperators4.1ConventionalOperators4.2ArithmeticalOperators4.3Direction-basedOperators4.4StochasticOperatorsAdaptationofGeneticAlgorithms5.1StructureAdaptation5.2ParametersAdaptationHybridGeneticAlgorithms6.1AdaptiveHybridGAApproach6.2ParameterControlApproachofGA6.3ParameterControlApproachusingFuzzyLogicController6.4DesignofaHGAusingConventionalHeuristicsandFLCSoftComputingLab.19进化算法遗传算法1.IntroductionofGeneticAlgorithmsFoundationsofGeneticAlgorithms1.1IntroductionofGeneticAlgorithms1.2GeneralStructureofGeneticAlgorithms1.3MajorAdvantagesExamplewithSimpleGeneticAlgorithms

EncodingIssueGeneticOperatorsAdaptationofGeneticAlgorithmsHybridGeneticAlgorithmsSoftComputingLab.20进化算法遗传算法进化论Simon把复杂性定义为：当给定各部分的性质和他们的相互作用规律，却很难推演总体性质的情形，系统的复杂性不仅与相互作用各部分的数目有关，而且与其结构和功能上的差别有关复杂系统具有进化性，而进化又使得系统变得更复杂，生物系统是复杂系统，进化的总趋势是产生越来越复杂的生物体。SoftComputingLab.21进化算法遗传算法Lamarck进化论一切物种都是其他物种演变和进化而来的，而生物的演变和进化是一个缓慢和连续的过程。环境的变化能够引起生物的变异，环境的变化迫使生物发生适应性的进化。有神经系统的动物发生变异的原因，除了环境变化和杂交外，更重要是通过用进废退和获得性状遗传。生物进化的方向从简单到复杂，从低到高。最原始的生物起源于自然发生。生物并不起源于共同祖先。拉马克曾以长颈鹿的进化为例，说明他的"用进废退"观点。长颈鹿的祖先预部并不长，由于干旱等原因。在低处已找不到食物，迫使它伸长脖颈去吃高处的树叶，久而久之，它的颈部就变长了。一代又一代，遗传下去，它的脖子越来越长，终于进化为现在我们所见的长颈鹿。SoftComputingLab.22进化算法遗传算法Darwin进化论包括两部分：遗传(基因)变异；自然选择生物不是静止的，而是进化的。物种不断变异，旧物种消灭，新物种产生。生物的进化是连续和逐渐，不会发生突变。生物之间存在一定的亲缘关系，他们具有共同的祖先。自然选择是变异的最重要的途径。生物过渡繁殖，但是它们的生存空间和食物有限，从而面临生存斗争，包括:种内、种间以及生物与环境的斗争。自然选择是达尔文进化论的核心。SoftComputingLab.23进化算法遗传算法孟德尔学说1、分离定律：基因作为独特的独立单位而代代相传。细胞中有成对的基本遗传单位，在杂交的生殖细胞中，一个来自雄性亲本，一个来自雌性亲本.2、独立分配定律：在一对染色体上的基因对中的等位基因能够独立遗传。孟德尔的这两条遗传基本定律就是新遗传学的起点，孟德尔也因此被后人称为现代遗传学的奠基人。SoftComputingLab.24进化算法遗传算法SoftComputingLab.25进化算法遗传算法比较达尔文抛弃拉马克的获得性遗传法则，认为性状并不重要，只有可遗传的变异才具有明显的进化价值，变异在群体内遗传，产生进化效应。不过达尔文过分强调物种形成的渐进方式。如果进化是渐变的话，为什么在化石的范围里面，找不到证据；如果进化是突变的话，但是根据医学及科学的研究，突变产生的不是进化，而是退化,如突变产生癌，进化论证据缺乏。SoftComputingLab.26进化算法遗传算法新达尔文主义将达尔文进化论和魏斯曼选择和孟德尔-摩根基因相结合，成为现被广泛接受的新达尔文主义。新达尔文注意认为，只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史，这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。SoftComputingLab.27进化算法遗传算法生物学中的遗传概念在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基因），即可改变人体的身高。细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了上一代细胞的基因。SoftComputingLab.28进化算法遗传算法生物学中的遗传概念有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生新的染色体。这些新的染色体将决定新的个体（后代）的新的性状。SoftComputingLab.29进化算法遗传算法生物学中的遗传概念在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。Inparticular,anynewmutationthatappearsinachild(e.g.longerneck(脖),longerlegs,thickerskin,longergestation(孕)period,biggerbrain)andwhichhelpsitinitseffortstosurvivelongenoughtohavechildren,willbecomemoreandmorewidespreadinfuturegenerations.SoftComputingLab.30进化算法遗传算法EvolutionasProblemSolving

Here’saproblem:DesignamaterialforthesolesofbootsthatcanhelpyouwalkupasmoothverticalbrickwallWehaven’tsolvedthis,butnaturehas:Geckos（设计一种可以帮助人类爬上光滑的墙壁的鞋底材料）生物的进化是经过无数次有利的进化积累而成的，不同的环境保留了不同的变异后代！SoftComputingLab.31进化算法遗传算法EvolutionasaProblemSolvingMethod

所有的生物经常面临一个共同的问题

HowcanIsurviveinthisenvironment？自然界解决问题的方法就是：进化Evolution

Thebasicmethodofitistrialanderror(反复试验).

1.Comeupwithanewsolutionbyrandomlychanginganoldone.Doesitworkbetterthanprevioussolutions?Ifyes,keepitandthrowawaytheoldones.Otherwise,discardit.2.Goto1.

SoftComputingLab.32进化算法遗传算法

Lesson1:Keepapopulation/collectionofdifferentthingsonthego.

Lesson2:Select`parents’witharelativelyweak

biastowardsthefittest.It’snotreallyplainsurvivalofthefittest,whatworksis

thefitteryouare,themorechanceyouhavetoreproduce,

anditworksbestifeventheleastfitstillhavesomechance.

（无偏见的选择父代，或适者生存)Lesson3:Itcansometimeshelptouserecombinationoftwoormore`parents’–I.e.generatenewcandidatesolutionsbycombiningbitsandpiecesfromdifferentprevioussolutions.

通过重组将父代优良基因遗传给后代Thisisgeneticalgorithm什么是进化？SoftComputingLab.33进化算法遗传算法Morelikeselectivebreedingthannaturalevolution

Time

SoftComputingLab.34进化算法遗传算法InitialpopulationSoftComputingLab.35进化算法遗传算法SelectSoftComputingLab.36进化算法遗传算法CrossoverSoftComputingLab.37进化算法遗传算法AnotherCrossoverSoftComputingLab.38进化算法遗传算法AmutationSoftComputingLab.39进化算法遗传算法AnotherMutationSoftComputingLab.40进化算法遗传算法Oldpopulation+childrenSoftComputingLab.41进化算法遗传算法NewPopulation:Generation2SoftComputingLab.42进化算法遗传算法Generation3SoftComputingLab.43进化算法遗传算法Generation4,etc…SoftComputingLab.44进化算法遗传算法SoftComputingLab.45进化算法遗传算法遗传算法的基本思想首先实现从性状到基因得映射，即编码工作，然后从代表问题可能潜在解集得一个种群开始进行进化求解。初代种群（编码集合）产生后，按照优胜劣汰的原则，根据个体适应度大小挑选（选择）个体，进行复制、交叉、变异，产生出代表新的解集的群体，再对其进行挑选以及一系列遗传操作，如此往复，逐代演化产生出越来越好的近似解。SoftComputingLab.46进化算法遗传算法选择：通过适应度的计算，淘汰不合理的个体。类似于自然界的物竞天择.复制：编码的拷贝，类似于细胞分裂中染色体的复制。交叉：编码的交叉重组，类似于染色体的交叉重组。变异：编码按小概率扰动产生的变化，类似于基因的突变。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中得最优个体经过解码（从基因到性状的映射），可以作为问题近似最优解。SoftComputingLab.47进化算法遗传算法遗传算法历史遗传算法的发展历史：1965年，Holland首次提出人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。 1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。

SoftComputingLab.48进化算法遗传算法遗传算法历史1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schematatheory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。SoftComputingLab.49进化算法遗传算法遗传算法历史在一系列研究工作的基础上，上世纪80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。SoftComputingLab.50进化算法遗传算法产生初始种群计算适应度是否满足优化准则最佳个体选择交叉变异编码（性状到基因）解码（基因到性状）YN父代子代开始结束SoftComputingLab.51进化算法遗传算法1.3MajorAdvantages

共轭梯度法、拟牛顿法、单纯形方法特点：渐进收敛经典的优化搜索算法往往是基于梯度的，梯度方向提高个体性能；单点搜索局部最优

ConventionalMethod(point-to-pointapproach)initialsinglepointimprovement(problem-specific)terminationcondition?startstopConventionalMethodYesNoSoftComputingLab.52进化算法遗传算法遗传算法improvement(problem-independent)terminationcondition?startstopGeneticAlgorithminitialpoint...initialpointinitialpointInitialpopulationYesNo遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。SoftComputingLab.53进化算法遗传算法遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。SoftComputingLab.54进化算法遗传算法遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。SoftComputingLab.55进化算法遗传算法遗传算法使用概率搜索技术。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。RandomSearch+DirectedSearchSearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3SoftComputingLab.56进化算法遗传算法SoftComputingLab.57进化算法遗传算法1.1IntroductionofGeneticAlgorithms分支：Thebestknownalgorithmsinthisclassinclude:GeneticAlgorithms(GA),developedbyDr.Holland.Holland,J.:AdaptationinNaturalandArtificialSystems,UniversityofMichiganPress,AnnArbor,MI,1975;MITPress,Cambridge,MA,1992.Goldberg,D.:GeneticAlgorithmsinSearch,OptimizationandMachineLearning,Addison-Wesley,Reading,MA,1989.EvolutionStrategies(ES),developedbyDr.RechenbergandDr.Schwefel.Rechenberg,I.:Evolutionstrategie:OptimierungtechnischerSystemenachPrinzipienderbiologischenEvolution,Frommann-Holzboog,1973.Schwefel,H.:EvolutionandOptimumSeeking,JohnWiley&Sons,1995.EvolutionaryProgramming(EP),developedbyDr.Fogel.Fogel,L.A.Owens&M.Walsh:ArtificialIntelligencethroughSimulatedEvolution,JohnWiley&Sons,1966.GeneticProgramming(GP),developedbyDr.Koza.Koza,J.R.:GeneticProgramming,MITPress,1992.Koza,J.R.:GeneticProgrammingII,MITPress,1994.SoftComputingLab.58进化算法遗传算法1.2GeneralStructureofGeneticAlgorithmsIngeneral,aGAhasfivebasiccomponents,assummarizedbyMichalewicz.(用遗传算法求解问题需要解决以下五个问题)Ageneticrepresentationofpotentialsolutionstotheproblem.(编码)Awaytocreateapopulation(aninitialsetofpotentialsolutions).(群体初始化)Anevaluationfunctionratingsolutionsintermsoftheirfitness.(个体评价)Geneticoperatorsthatalterthegeneticcompositionofoffspring(selection,crossover,

mutation,etc.).(遗传算子)

Parametervaluesthatgeneticalgorithmuses(populationsize,probabilitiesofapplyinggeneticoperators,etc.).(参数选择).SoftComputingLab.59进化算法遗传算法1.2GeneralStructureofGeneticAlgorithmsGeneticRepresentationand

Initialization:Thegeneticalgorithmmaintainsapopulation

P(t)

ofchromosomesorindividualsvk(t),k=1,2,…,popSizeforgenerationt.(保持一个规模不变群体)Eachchromosomerepresentsapotentialsolutiontotheproblemathand.Evaluation:Eachchromosomeisevaluatedtogivesomemeasureofitsfitness

eval(vk).GeneticOperators:Somechromosomesundergostochastictransformationsbymeansofgeneticoperatorstoformnewchromosomes,i.e.,

offspring.Therearetwokindsoftransformation:Crossover,whichcreatesnewchromosomesbycombiningpartsfromtwochromosomes.Mutation,whichcreatesnewchromosomesbymakingchangesinasinglechromosome.Newchromosomes,calledoffspring

C(t),arethenevaluated.Selection:Anewpopulationisformedbyselecting

the

morefitchromosomes

fromtheparentpopulationandtheoffspringpopulation.Bestsolution:Afterseveralgenerations,thealgorithmconvergestothebestchromosome,whichhopefullyrepresentsanoptimalorsuboptimalsolutiontotheproblem.SoftComputingLab.60进化算法遗传算法1.2GeneralStructureofGeneticAlgorithmsInitialsolutionsstart1100101010101110111000110110011100110001encodingchromosome110010101010111011101100101110101110101000110110010011001001crossovermutation110010111010111010100011001001solutionscandidatesdecodingfitnesscomputationevaluationroulettewheelselectionterminationcondition?YNbestsolutionstopnewpopulationThegeneralstructureofgeneticalgorithmsGen,M.&R.Cheng:GeneticAlgorithmsandEngineeringDesign,JohnWiley,NewYork,1997.offspringoffspringt0

P(t)CC(t)CM(t)P(t)+C(t)SoftComputingLab.61进化算法遗传算法1.2GeneralStructureofGeneticAlgorithmsProcedureofSimpleGAprocedure:SimpleGAinput:GAparametersoutput:bestsolutionbegin

t

0;

//t:generationnumber initializeP(t)byencodingroutine; //P(t):populationofchromosomes fitnesseval(P)bydecodingroutine; while(notterminationcondition)do

crossover

P(t)toyieldC(t);//C(t):offspring

mutation

P(t)toyieldC(t);

fitnesseval(C)bydecodingroutine;

select

P(t+1)fromP(t)

andC(t); t

t+1;

end outputbestsolution;end

SoftComputingLab.62进化算法遗传算法1.IntroductionofGeneticAlgorithmsFoundationsofGeneticAlgorithmsExamplewithSimpleGeneticAlgorithms

2.1Representation2.2InitialPopulation2.3Evaluation2.4GeneticOperatorsEncodingIssueGeneticOperatorsAdaptationofGeneticAlgorithmsHybridGeneticAlgorithmsSoftComputingLab.63进化算法遗传算法2.ExamplewithSimpleGeneticAlgorithmsWeexplainindetailabouthowageneticalgorithmactuallyworkswithasimpleexamples.(举例说明如何用遗传算法求解具体的优化问题)Thenumericalexampleofunconstrainedoptimizationproblemisgivenasfollows:maxf(x1,x2)=21.5+x1·sin(4p

x1)+x2·sin(20p

x2)s.t.-3.0£x1£12.14.1£x2£5.8SoftComputingLab.64进化算法遗传算法2.ExamplewithSimpleGeneticAlgorithmsmaxf(x1,x2)=21.5+x1·sin(4p

x1)+x2·sin(20p

x2)s.t.-3.0£x1£12.14.1£x2£5.8SoftComputingLab.65进化算法遗传算法2.1RepresentationBinaryStringRepresentationThedomainofxj

is[aj,bj]andtherequiredprecisionisfive

placesafterthedecimalpoint.(精度小数点后面五位)Theprecisionrequirementimpliesthattherangeofdomainof

eachvariableshouldbedividedintoatleast(bj-aj)

105sizeranges.Therequiredbits(denotedwithmj)foravariableiscalculatedas

follows:Themapping

fromabinarystringtoarealnumberforvariablexj

iscompletedasfollows:SoftComputingLab.66进化算法遗传算法2.1RepresentationBinaryStringEncoding(二进制编码)Theprecisionrequirementimpliesthattherangeofdomainofeachvariableshouldbedividedintoatleast(bj-aj)

105sizeranges.x1:(12.1-(-3.0))10,000=151,000217<151,000218,m1=18bitsx2:(5.8-4.1)10,000=17,000214<17,000215,m2=15bitsprecisionrequirement:

m=m1+

m2=18+15=33bitsTherequiredbits(denotedwithmj)foravariableiscalculatedasfollows:SoftComputingLab.67进化算法遗传算法2.1RepresentationProcedureofBinaryStringEncoding(表现型

基因型)step1:Thedomainofxj

is[aj,bj]andtherequiredprecisionisfive

placesafterthedecimalpoint.step2:Theprecisionrequirementimpliesthattherangeofdomainof

eachvariableshouldbedividedintoatleast(bj-aj)

105sizeranges.step3:Therequiredbits(denotedwithmj)foravariableiscalculatedas

follows:step4:Achromosomevisrandomlygenerated,whichhasthenumberofgenesm,

wheremissumofmj(j=1,2).m=m1+m2

input:domainofxj

[aj,bj],(j=1,2)(输入可行解(x1,x2)，表现型)output:chromosomev(输出二进制码，基因型）SoftComputingLab.68进化算法遗传算法2.1RepresentationBinaryStringDecoding(基因型

表现型)Themapping

fromabinarystringtoarealnumberforvariablexjiscompletedasfollows:SoftComputingLab.69进化算法遗传算法input:substringjoutput:arealnumber

xj2.1RepresentationProcedureofBinaryStringDecodingstep1:Convertasubstring(abinarystring)toadecimalnumber.step2:Themapping

forvariablexjiscompletedasfollows:SoftComputingLab.70进化算法遗传算法2.2InitialPopulationInitialpopulationisrandomlygeneratedasfollows:v1=[11011111110]=[x1x2]=[-2.6879695.361653]v2=[10101001000]=[x1x2]=[0.4741014.170144]v3=[11111000110]=[x1x2]=[10.4194574.661461]v4=[11010111001]=[x1x2]=[6.1599514.109598]v5=[11001101000]=[x1x2]=[-2.3012864.477282]v6=[11111011001]=[x1x2]=[11.7880844.174346]v7=[11111101101]=[x1x2]=[9.3420675.121702]v8=[10011001100]=[x1x2]=[-0.3302564.694977]v9=[11111111101]=[x1x2]=[11.6712674.873501]v10=[11111101010]=[x1x2]=[11.4462734.171908]SoftComputingLab.71进化算法遗传算法2.3EvaluationTheprocessofevaluatingthefitnessofachromosomeconsistsofthefollowingthreesteps:input:chromosomevk,k=1,2,...,popSizeoutput:thefitnesseval(vk)step1:Convertthechromosome’sgenotypetoitsphenotype,i.e.,convertbinarystringintorelativerealvaluesxk

=(xk1,xk2),k=1,2,…,popSize.(基因型到表现型)step2:Evaluatetheobjectivefunctionf(xk),k=1,2,…,popSize.step3:Convertthevalueofobjectivefunctionintofitness.Forthemaximizationproblem,thefitnessissimplyequaltothevalueofobjectivefunction:eval(vk)=f(xk),k=1,2,…,popSize.f(x1,x2)=21.5+x1·sin(4π

x1)+x2·sin(20π

x2)eval(v1)=f(-2.687969,5.361653)=19.805119Example:

(x1=-2.687969,x2=5.361653)SoftComputingLab.72进化算法遗传算法Anevaluationfunctionplaystheroleoftheenvironment,anditrateschromosomesintermsoftheirfitness.(适应度函数起到环境的作用)Thefitnessfunctionvaluesofabovechromosomesareasfollows:Itisclearthatchromosomev4isthestrongestoneandthatchromosomev3

istheweakestone.2.3Evaluationeval(v1)=f(-2.687969,5.361653)=19.805119eval(v2)

=f(0.474101,4.170144)=17.370896eval(v3)

=f(10.419457,4.661461)=9.590546eval(v4)

=f(6.159951,4.109598)=29.406122eval(v5)

=f(-2.301286,4.477282)=15.686091eval(v6)

=f(11.788084,4.174346)=11.900541eval(v7)

=f(9.342067,5.121702)=17.958717eval(v8)

=f(-0.330256,4.694977)=19.763190eval(v9)

=f(11.671267,4.873501)=26.401669eval(v10)

=f(11.446273,4.171908)=10.252480SoftComputingLab.73进化算法遗传算法2.4GeneticOperatorsSelection(无偏见，平等)Inmostpractices,aroulettewheelapproachisadoptedastheselectionprocedure,whichisoneofthefitness-proportionalselection

andcanselectanewpopulationwithrespecttotheprobabilitydistributionbasedonfitnessvalues.(通过适应度来设计个体被选择的概率）Theroulettewheelcanbeconstructedwiththefollowingsteps:step1:Calculatethetotalfitnessforthepopulationstep2:Calculateselectionprobability

pkfor

eachchromosomevkstep3:Calculatecumulativeprobability

qkforeachchromosomevkstep4:Generatearandomnumber

rfromtherange[0,1].step5:Ifr

q1,thenselectthefirstchromosomev1;otherwise,selectthekthchromosomevk(2

k

popSize)suchthatqk-1<r

qk.input:populationP(t-1),C(t-1)output:populationP(t),C(t)SoftComputingLab.74进化算法遗传算法2.4GeneticOperatorsIllustrationofSelection:step1:CalculatethetotalfitnessFforthepopulation.step2:Calculateselectionprobabilitypkfor

eachchromosomevk.step3:Calculatecumulativeprobabilityqkforeachchromosomevk.step4:Generatearandomnumberrfromtherange[0,1].135372.178)(101==å=kkevalFv0.197577

0.032685,

0.343242,

0.177618,

0.583392,

0.350871,

0.881893,

0.766503,

0.322062,

0.301431,

input:populationP(t-1),C(t-1)output:populationP(t),C(t)SoftComputingLab.75进化算法遗传算法1100.197577

0.032685,

0.343242,

0.177618,

0.583392,

0.350871,

0.881893,

0.766503,

0.322062,

0.301431,

SoftComputingLab.76进化算法遗传算法2.4GeneticOperatorsIllustrationofSelection:step5:q3<r1=0.301432

q4,itmeansthatthechromosomev4isselectedfornewpopulation;q3<r2=0.322062

q4,itmeansthatthechromosome

v4isselectedagain,andsoon.Finally,thenewpopulationconsistsofthefollowingchromosome.v1'

=[11010111001](v4)v2'

=[11010111001](v4)v3'

=[10011001100](v8)v4'

=[11111111101](v9)v5'

=[11010111001](v4)v6'

=[11111101101](v7)v7'

=[10101001000](v2)v8'

=[11010111001](v4)v9'

=[11011111110](v1)v10'

=[10101001000](v2)SoftComputingLab.77进化算法遗传算法2.4GeneticOperatorsCrossover(One-cutpointCrossover)Crossoverusedhereisone-cutpointmethod,whichrandomselectsonecutpoint.Exchangestherightpartsoftwoparentstogenerateoffspring.Considertwochromosomesasfollowandthecutpointisrandomlyselectedafterthe17thgene:v1=[11010111001]

v2=[10101001000]c1=[11011001000]

c2=[00110111001]crossingpointat17thgeneSoftComputingLab.78进化算法遗传算法2.4GeneticOperatorsProcedureofOne-cutPointCrossover:procedure:

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

k1to

do //popSize:populationsize ifpc

random[0,1]then //pC:theprobabilityofcrossover

i

0;

j

0; repeat

i

random[1,popSize];

j

random[1,popSize];

until(i≠j)

p

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

Ci

Pi

[1:p-1]//Pj

[p:l];

Cj

Pj

[1:p-1]//Pi

[p:l]; endendoutputoffspringCk;endSoftComputingLab.79进化算法遗传算法2.4GeneticOperatorsMutationAltersoneormoregenes

withaprobabilityequaltothemutationrate.(改变一个或多个基因)Assumethatthe16thgeneofthechromosomev1isselectedforamutation.Sincethegeneis1,itwouldbeflippedinto0.Sothechromosomeaftermutationwouldbe:v1=[11011111001]

c1=[11010001000]mutatingpointat16thgeneSoftComputingLab.80进化算法遗传算法2.ExamplewithSimpleGeneticAlgorithmsProcedureofMutation:IllustrationofMutation:procedure:Mutationinput:pM,parentPk,k=1,2,...,popSizeoutput:offspringCkbeginfor

k1topopSizedo //popSize:populationsize forj1to

ldo(基因串长度）//l:thelengthofchromosome

ifpM

random[0,1]then //pM:theprobabilityofmutation

p

random[1,l-1];(位置) //p:thecutposition

Ck

Pk

[1:j-1]//1-Pk

[j]//Pk[j+1:l]; end endendoutputoffspringCk;endAssumethatpM=0.01

bitPos

chromNum

bitNo

randomNum105460.0098571645320.0031131997