中科大本科毕业论文

采用协同演化算法解决大规模数值优化问题的研究Large-ScaleNumericalOptimizationusingCooperativeCoevolutionaryAlgorithms计算机科学与技术学院陈文祥PB07210425唐珂教授二〇一一年六月中国科学技术大学UniversityofScienceandTechnologyofChina本科毕业论文ADissertationSubmittedfortheBachelor’sDegree采用协同演化算法解决大规模数值优化问题的研究Large-ScaleNumericalOptimizationusingCooperativeCoevolutionaryAlgorithms姓名陈文祥B.S.CandidateWenxiangChen导师唐珂教授SupervisorProf.KeTang2011年6月June,2010致谢随着本科毕业论文的完成，我在科大四年的学习接近尾声，而在自然计算与应用实验室已经学习研究了两年零两个月。衷心感谢自然计算与应用实验室的各位老师及师兄师姐们在两年多来给予我的热情鼓励和耐心帮助，是你们帮助我发掘兴趣所在，让我自由而愉快的徜徉于科学的海洋，决定了我的人生轨迹！首先感谢唐珂老师两年来点点滴滴对我科研上的指导和生活上的关心。感谢您提供给我如同博士生般的待遇：从台式计算机购买到服务器使用、从鼓励我参加最前沿的尖端课题到全力资助我参加国际学术会议，是您让我感觉到，一个本科生也同样能够做一点真正的研究。感谢您总是在我需要帮助的时候，百忙之中抽出时间，解除了我诸多科研上的疑惑和指明了前方的道路。感谢您一直把学生的发展和利益放在首位，给予我许多关于未来职业规划的指导和建议。感谢您让彭飞师兄、杨振宇师兄和ThomasWeise博士直接帮助我解决工作中众多琐碎的细节问题，他们亦师亦友，扫除了我科研道路上无数的绊脚石。感谢彭飞师兄的引荐。如果没有师兄当年在数据结构实验课上的一番关于NICAL颇具感染力的介绍，我可能错过NICAL这个让我蜕变的熔炉。虽然当时选择NICAL前并没有进行对多个实验室的理性比较，而更多的是出于对师兄的信任。现在回头看来，如果再让我选择一次，我肯定还会成为一个NICALer！感谢师兄在我刚刚进入实验室时，耐心解答了关于论文的阅读、各种研究相关软件的使用等细节问题，你乐于助人的精神永远值得我学习。感谢杨振宇师兄领我进入了大规模数值优化这个前沿课题。师兄对大规模数值优化问题的独到见解，就像是一把进入密室的钥匙。是师兄让我快速登堂入室，从2010年1月底开始接触具体的课题，到同年4月20日投出第一篇论文并被PPSN接受，如果没有师兄的帮助，这是绝对不可能完成的。我对科研具体流程的把握，正是通过和师兄一次次讨论逐步形成的。感谢姚新老师高屋建瓴的指导。和姚老师的交流机会并不是太多，不过每次交流都是极具启发性的，是我产生新思路的最重要源泉。PPSN会议期间您热情邀请我到你所下榻的旅馆就餐，中途还遇见进化策略的发明者H.P.Schwefel教授，还获得了和他握手的机会，让我感受到演化计算社区的温暖，有了继续在这个领域探索的勇气。PPSN会议和两次由姚老中国科学技术大学本科毕业论文师发起的workshop，让我看到演化计算的研究当前蓬勃的发展趋势，使我坚定了在这个领域继续研究的信心。感谢ThomasWeise博士就科技论文写作方面提供的悉心指导，你严谨的写作风格将使我受用终生。感谢你在对我工作进展孜孜不倦的关心，在失落时给我持续不断的鼓励。感谢科大所有有教过我的和没有教过我老师，你们是科大真正的脊梁！我坚信，科大在你们兢兢业业的不懈努力下，一定能够重振往日的雄风！你们在传授给我知识的同时，踏实的作风更是给我留下了深刻的印象，你们永远是我精神丰碑。感谢三位可爱的室友，司成可、李啸海和周金红，是你们让小小的寝室有了家的温馨。感谢你们一直以来对我科研工作的鼓励和支持。感谢07级计算机学院全体同学，和你们一起度过的四年欢乐时光我将永生难忘！感谢生我养我的、最可敬的父母亲，虽然由于种种原因你们都没有完成正常的教育，但你们在很多生活问题中体现出的睿智、对我人生积极向上态度的培养、对我任何选择的信任和尊重，你们是所知道的最好的家长！ii中国科学技术大学本科毕业论文TableofContents致谢i摘要viAbstractviiiChapter1Introduction11.1Motivation...............................21.2Objectives...............................4Chapter2Background62.1EvolutionaryComputation......................62.2CooperativeCoevolution.......................7Chapter3FormulatingInterdependenciesamongSubproblems113.1BackgroundandRelatedWorks...................113.1.1ClassicalBenchmarkProblems...............113.1.2InterdependenciesamongSubcomponents.........113.1.3LimitationsforpreviousFormulationofInterdependencyinCooperativeCoevolution.................123.2NewFormationthatNeverCommitstheType-IIError......14Chapter4ImpactofProblemDecompositionStrategyonCooper-ativeCoevolution174.1InterpretationofProblemDecompositionStrategy.........174.2HowtoHandleUnknownElementsin⃗Aintr.............184.3ExperimentalStudies.........................184.3.1ExperimentalSetup.....................184.3.2ExperimentalResultswithPpriorvaryingfrom0%to100%194.3.3ExperimentalResultswithPpriorvaryingfrom1%to9%.194.3.4InsightsintotheUnderlyingReasons............22iii中国科学技术大学本科毕业论文Chapter5EnableVariableInteractionLearninginCooperativeCoevolutionaryAlgorithms285.1Background..............................285.1.1DiscoveringDecisionVariableInteractions.........295.1.2RelatedWorks........................315.2CooperativeCoevolutionwithVariableInteractionLearning...325.2.1LearningStage........................335.2.2OptimizationStage......................355.3ExperimentalStudies.........................365.3.1ExperimentalSetup.....................365.3.2BenchmarkFunctionsandLearnedGroups.........365.3.3ComparisonwithotherCC-basedalgorithmsandJADE.385.4Summary...............................41Chapter6EnhancetheEffectivenessofVariableInteractionLearn-ingMechanism426.1SimplifyLearningProcessbyEmployingOccam’sRazor.....426.1.1RandomSamplingLearningProcess(RS-LP).......436.1.2DiscussiononParameterTerminationCondition......446.1.3ExperimentalStudy.....................456.2InspirationsFromLinkageLearningTechniques..........466.2.1Background..........................466.2.2GeneralizingtheDefinitionofVariableInteraction.....486.2.3WillLocalSearchbeHelpfulforLearningVariableInter-action?............................496.2.4ReducingtheRuntimeComplexityofLearningProcessByBinarySearch.........................496.2.5ExperimentalStudies.....................50iv中国科学技术大学本科毕业论文Chapter7Conclusions567.1Summary...............................567.2FutureWorks.............................577.2.1VerificationoftheEfficacyofCCVILinvariousReal-WorldApplications.........................587.2.2TheScalabilityofCCVIL..................587.2.3MultipleOptimizationStrategiesintheOptimizationStage587.2.4MoreSophisticatedApproachesforSeparableyetNotAd-ditivelySeparableFunctions.................597.2.5EvolvingVariablePartitioning...............59Bibliography60v中国科学技术大学本科毕业论文摘要数值优化存在广泛的应用背景，很多科学研究与工程实践问题都可抽象为数值优化模型加以求解。演化算法作为一类基于群体搜索的启发式方法，因具有使用简单、全局搜索能力强等特点，在数值优化领域受到越来越多的关注。然而，因为“维数灾难”问题的存在，这类方法仍然存在无法有效求解大规模问题等不足，严重影响了算法的求解效率与可扩展性，从而限制了其在相关应用领域的发展。基于“分而治之”思想的“合作型协同演化算法”在变量相关性信息已知的情况下，被认为是解决大规模数值优化难题有潜力的方法。然而在实际生产生活中，所面对的问题往往无从事先知道变量相关性信息（即黑盒难题），从而无法确保合理的将原问题分解成若干个相互独立的子问题。而不合理的问题分解策略使得分解之后的子问题存在相互依赖关系，这将是极大的限制协同演化算法全局搜索能力，从而使算法陷入局部最