资源描述:
《09Genetic algorithm 》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、IntelligentSystemsPrinciplesandProgrammingXiaoqingZhengzhengxq@fudan.edu.cnEvolution"...nolimittothispowerofslowlyandbeautifullyadaptingeachformtothemostcomplexrelationsoflife..."CharlesDarwinGeneticalgorithmbeginsettimet=0initializethepopulationP(t)whiletheterminationcondition
2、isnotmetdobeginevaluatefitnessofeachmemberofthepopulationP(t);selectmembersfrompopulationP(t)basedonfitness;producetheoffspringofthesepairsusinggeneticoperators;replacecandidatesofP(t),withtheseoffspring;settimet=t+1endendExampleMaximumf(x)=x2,x∈[1,31]óRepresentation5x∈{0,1}óIn
3、itialization1stgeneration01101,11000,01000,10011Interpretation13,24,8,19Fitness169,576,64,361ExampleMaximumf(x)=x2,x∈[1,31]óSelectionIndividual01101,11000,01000,10011Fitness169,576,64,361=1170Probability0.14,0.49,0.06,0.31=1.0Result01101,11000,11000,10011óCrossover0110101100110
4、001101111000110011001110000óMutation0110011100KnapsackproblemAthiefrobbingastorefindsnitems;theithitemisworthvdollarsandweighswpounds,wherevandwiiiiareintegers.Hewantstotakeasvaluablealoadaspossible,buthecancarryatmostWpoundsinhisknapsackforsomeintegerW.Whichitemsshouldhetake?C
5、NF-satisfactionproblemTheconjunctivenormalform(CNF)satisfiabilityproblemisstraightforward:anexpressionofpropositionsisinconjunctivenormalformwhenitisasequenceofclausesjoinedbyanANDrelation.Eachoftheseclausesisintheformofadisjunction,theORofliterals.()¬∨∧¬∨∨¬∧¬∨∨∨¬∧ac(ace)(bcde)
6、()abcev∨¬∨∧¬∨()Semantictree{p(),xpxqxq¬∨¬()(),(())fa}0p()a¬p()a12qa()¬qa()qa()¬qa()3456pf(())a¬pf(())a7891011121314AnalysisoftravelingsalesmanproblemGivenafinitenumberof"cities"alongwiththecostoftravelbetweeneachpairofthem,findthecheapestwayofvisitingeachcityexactlyonceandfinis
7、hingatthecityhestartsfrom.ó19CitiesóPossibleroutes=18!=6.40237×1015ólifetime=80×365×24×60×60=2.52288×109óComputerspeed=10000routes/second253.77Generation!TravelingsalesmanproblemCrossoverp=(192465783)1p=(459187623)2Startfromthesecondcutpointofoneparent,thecitiesfromtheotherpare
8、ntarecopiedinthesameorder,omittingcitiesalreadypresent