搜索
EvolutionaryPrinciplesappliedtoProblemSolving遗传算法ThereisnothingparticularlynewaboutEvolutionarySolversorGeneticAlgorithms.Thefirstreferencestothisfieldofcomputationstemfromtheearly60'swhenLawrenceJ.FogelpublishedthelandmarkpaperOntheOrganizationofIntellectwhichsparkedthefirstendeavoursintoevolutionarycomputing.Theearly70'switnessedfurtherforayswithseminalworkproducedby-amongothers-IngoRechenbergandJohnHenryHolland.EvolutionaryComputationdidn'tgainpopularitybeyondtheprogrammerworlduntilRichardDawkins'bookTheBlindWatchmakerin1986,whichcamewithasmallprogramthatgeneratedaseeminglyendlessstreamofbody-planscalledBio-morphsbasedonhumanselection.Sincethe80'stheadventofthepersonalcomputerhasmadeitpossibleforindividualswithoutgovernmentfundingtoapplyevolutionaryprinciplestopersonalprojectsandtheyhavesincemadeitintothecommonparlance.其实在遗传算法和基因算法里并什么特别新的理论出现，该领域的第一篇文献出现在六十年代由LawrenceJ.Fogel出版的具有里程碑意义的论文“智能组织”，这篇论文使人们开始致力于研究遗传算法。七十年代又由ngoRechenbergandJohnHenryHolland的工作进一步带动了基因算法的发展，遗传算法直到1986年才因为RichardDawkins的“TheBlindWatchmake”而让人广为人知，里面有个小的例子，基于人类的选择仍然会产生无尽的被称为“生态形变”的动作计划。80年代由于个人电脑的出现使得每个人都可以将进化算法用于个人项目而不用政府提供资金支持，从此，进化算法开始像日常话题一样进入公众视野。ThetermEvolutionaryComputingmayverywellbewidelyknownatthispointintime,buttheyarestillverymuchaprogrammerstool.'Byprogrammersforprogrammers'ifyouwill.Theapplicationsouttherethatapplyevolutionarylogicareeitheraimedatsolvingspecificproblems,ortheyaregenericlibrariesthatallowotherprogrammerstopiggybackalong.ItismyhopethatGalapagoswillprovideagenericplatformfortheapplicationofEvolutionaryAlgorithmstobeusedonawidevarietyofproblemsbynon-programmers.虽然现在进化算法在现在已经广为人知，但他大部分还作为编程工具使用，只是程序员和程序员之间交流，遗传算法即使应用也是处理一些特别的问题，大部分时间还是呆在通用库里等着程序员来用它，我希望galapagos可以提供一个遗传算法的广泛平台来让那些非编程人员来处理一些问题。ProsandCons赞成和反对BeforewediveintothesubjectmattertoodeeplythoughIfeelitisimportanttohighlightsomeofthe(dis)advantagesofthisparticulartypeofsolver,justsoyouknowwhattoexpect.Sincewearenotlivinginthebestofallpossibleworldsthereisoftennosuchthingastheperfectsolution.Everyapproachhasdrawbacksandlimitations.InthecaseofEvolutionaryAlgorithmstheseareluckilywellknownandeasilyunderstooddrawbacks,eventhoughtheyarenottrivial.Indeed,theymaywellbeprohibitiveformanyaparticularproblem.在我们深入探讨这个问题之前，我认为有必要向大家介绍这类特殊算法处理方式的优缺点，这样可能更利于你了解你到底想通过这个获得什么。事实上我们生活在一个不完美的世界，没有什么事情会有一个完美地解决方案，每个解决方案都会有他的缺陷和限制。而在遗传算法领域可喜的是我们明确地知道他的一些缺陷，而且这些缺陷也不小，而且确实在一些具体问题的处理上明确禁止用遗传算法来解决。Firstly;EvolutionaryAlgorithmsareslow.Deadslow.Itisnotunheardofthatasingleprocessmayrunfordaysorevenweeks.Especiallycomplicatedset-upsthatrequirealongtimeinordertosolveasingleiterationwillquicklyrunoutofhand.Alight/shadoworacousticcomputationforexamplemayeasilytakeaminuteperiteration.Ifweassumewe'llneedatleast50generationsof50individualseach(whichisalmostcertainlyanunderestimateunlesstheproblemhasaveryobvioussolution.)we'realreadylookingatatwo-dayruntime.首先，遗传算法在运行起来的时候很慢，奇慢，非常慢，慢的要死。一个小程序运行几天甚至几个星期一点也不见怪，尤其是需要长时间简单迭代的复杂数据结构，运行起来会马上超出你的掌控，就算简单的光影分析或者是声学分析每次迭代就要几分钟，假设我们设置50代，每代50个个体（这都是按照最少最理想的状态来设定的），那这个程序需要两天才能做完。Secondly,EvolutionaryAlgorithmsdonotguaranteeasolution.Unlessapredefined'good-enough'valueisspecified,theprocesswilltendtorunonindefinitely,neverreachingTheAnswer,or,havingreachedit,notrecognizingitforwhatitis.其次，遗传算法并不能百分之百的保证求出正确的解，除非一个预先你已经想好的差不多的解已经确定下来，遗传算法会尽量的朝着你想要的那个解努力，但是他永远不会找到“真理”，当然，也可能找到了只不过他是电脑，根本意识不到那个是最优解，即“真理”。Allisnotbleakanddismalhowever,EvolutionaryAlgorithmshavestrongbenefitsaswell,someofthemratheruniqueamongsttheplethoraofcomputationalmethods.Theyareremarkablyflexibleforexample,abletotackleawidevarietyofproblems.Thereareclassesofproblemswhicharebydefinitionbeyondthereachofeventhebestsolverimplementationandotherclassesthatareverydifficulttosolve,butthesearetypicallyrareintheprovinceofthehumanmeso-world.Byandlargetheproblemsweencounteronadailybasisfallintothe'evolutionarysolvable'category.当然，遗传算法也并不是上面我说的那么单调无力，一直被吐槽。进化算法在一些方面也有着强大的性能体现，在茫茫多的计算算法里他确实一枝独秀，进化算法有很强的灵活性，能同时处理各种各样的问题，有些问题最好的解算器也解不出来，而且很多的我们日常遇到的问题都可以放到进化算法的范畴内进行解决。EvolutionaryAlgorithmsarealsoquiteforgiving.Theywillhappilychewonproblemsthathavebeenunder-orover-constrainedorotherwisepoorlyformulated.Furthermore,becausetherun-timeprocessisprogressive,intermediateanswerscanbeharvestedatpracticallyanytime.Unlikemanydedicatedalgorithms,EvolutionarySolversspewforthaneverendingstreamofanswers,whereneweranswersaregenerallyofahigherqualitythanolderanswers.Soevenapre-maturelyabortedrunwillyieldsomethingwhichcouldbecalledaresult.Itmightnotbeaverygoodresult,butitwillbearesultofsorts.进化算法的容忍性也很好，他很有能力去处理一些你低估或者高估或者很傻X的操作，进一步讲，因为它运行的时候是动态的，所以你在任何时候都可以收获一大堆的解而不像其他解算法（解完了才能得到答案），进化算法射出来一大堆永远没有尽头的解，而且这一代的解总体上来说会比上一代的质量更高，所以，尽管一些早产的结果产生我们也可以姑且把他认为是结果，虽然他不是最优秀的结果，但是他确是得到最优结果必不可少的一部分。Finally,EvolutionarySolversallow-inprinciple-forahighdegreeofinteractionwiththeuser.Thistooisafairlyuniquefeature,especiallygiventhebroadrangeofpossibleapplications.Therun-timeprocessishighlytransparentandbrowsable,andthereexistsalotofopportunityforadialoguebetweenalgorithmandhuman.Thesolvercanbecoachedacrossbarrierswiththeai