差分进化算法的改进及应用研究

分类号：密级：UDC：编号：工学博士学位论文差分进化算法的改进及应用研究博士研究生：肖婧指导教师：毕晓君教授学科、专业：信号与信息处理哈尔滨工程大学2011年9月分类号：密级：UDC：编号：工学博士学位论文差分进化算法的改进及应用研究博士研究生：肖婧指导教师：毕晓君教授学位级别：工学博士学科、专业：信号与信息处理所在单位：通信与信息工程学院论文提交日期：2011年9月论文答辩日期：2011年11月学位授予单位：哈尔滨工程大学ClassifiedIndex:U.D.C:ADissertationfortheDegreeofD.EngResearchontheImprovementandApplicationofDifferentialEvolutionAlgorithmCandidate:Candidate:Candidate:Candidate:JingXiaoSupervisor:Supervisor:Supervisor:Supervisor:Prof.XiaojunBiAcademicAcademicAcademicAcademicDegreeDegreeDegreeDegreeAppliedAppliedAppliedAppliedfor:for:for:for:DoctorofEngineeringSpecialtySpecialtySpecialtySpecialty::::SignalandInformationProcessDateDateDateDateofofofofSubmission:Submission:Submission:Submission:September.2011DateDateDateDateofofofofOralOralOralOralExamination:Examination:Examination:Examination:November.2011University:University:University:University:HarbinEngineeringUniversity哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者（签字）：日期：年月日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文（□在授予学位后即可□在授予学位12个月后□解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。作者（签字）：导师（签字）：日期：年月日年月日哈尔滨工程大学博士学位论文摘要差分进化(DifferentialEvolution,DE)是目前最优秀的进化优化算法之一，成为进化计算、智能优化技术方面的研究热点，并已广泛应用于数字信号处理、神经网络优化、模式识别、机器智能、化工、医学等诸多实际工程领域，取得了良好的应用效果。然而，DE和其他进化算法一样，在对复杂度较高的高维多峰函数进行优化时仍不可避免地存在早熟收敛、后期收敛速度慢、控制参数难以设定等问题。此外DE算法本身不可直接用于求解多目标优化问题，在一定程度上限制了算法的应用范围。本课题针对DE算法存在的不足，对算法的结构和关键步骤，如变异操作、交叉操作以及控制参数自适应调整等进行了深入研究和大量实验仿真工作，提出了若干种改进方法，大幅度提升了算法在高维多峰复杂单目标优化上的性能，并使其在多目标优化上取得了良好的效果。此外，从应用角度出发，将改进后的DE算法应用于人脑PET医学图像的病灶目标边缘检测以及合作环境下的电子商务多边多议题协商等前沿问题的求解中，均取得了良好的效果。首先，为提高DE算法在高维多峰复杂单目标优化问题上的求解性能，加快算法收敛速度、防止陷入局部最优并提高稳定性，提出了基于分类思想的新变异策略，并设计了新的参数自适应调整机制，从而构成一种性能优异的改进算法p-ADE。具体改进措施包括：1、设计新的DE变异策略。同时利用全局最优解以及个体历史最优解提供搜索方向性信息，避免差分向量中个体随机选择带来的搜索盲目性；2、引入分类策略。有针对性地调整不同特性个体的进化程度，平衡算法的“开采”与“勘探”能力；3、设计新的参数自适应策略。根据个体优劣以及进化代数设计每个个体的参数自适应方法。在22个标准测试函数上的实验结果显示，p-ADE算法能有效提高全局最优解精度，加快算法收敛速度并增强DE算法的鲁棒性，其相关性能指标优于国内外多种先进算法。其次，为提高现有多目标优化算法的求解性能，在以NSGA-II为代表的精英多目标进化算法模型基础上，对DE算法本身和精英多目标优化模型进行了综合改进，提出了一种基于精英策略的改进多目标自适应差分进化算法SDEMO。主要改进措施包括：1、设计新的精英多目标进化算法模型中的选择策略；2、设计新的精英多目标进化算法模型中的个体密度估计方法；3、根据多目标的特点设计新的DE算法变异策略；4、设计新的DE算法中的参数自适应策略。标准测试函数上的实验结果显示，SDEMO能够稳定有效地找到Pareto最优解集并同时保证良好分布性，尤其在复杂多目标优化问题中相差分进化算法的改进及应用研究关性能指标超过国内外多个先进多目标进化算法。再次，针对目前人脑PET医学图像的病灶目标边缘检测所存在的对初始轮廓敏感、难以收敛到目标凹型区域等问题，提出了一种结合p-ADE算法的GVFSnake模型，在提高检测精度解决实际问题的同时扩展DE算法的应用领域。新检测方法中首先利用GVFSnake模型进行收敛得到病灶目标的粗轮廓，然后为防止GVFSnake模型陷入局部最优，进一步利用p-ADE算法的全局优化特性以及图像信息对该粗轮廓进行优化，最终得到精确的病灶目标边缘轮廓线。在30幅真实人脑PET图像上的实验结果显示，新方法能有效提高PET图像的检测精度并缩短时耗，检测效果优于现有多种检测方法。最后，研究了p-ADE算法在合作环境下的电子商务多边多议题协商中的应用。针对现有基于遗传(GeneticAlgorithm,GA)等进化算法的多Agent协商方法计算效率低、需要具有协商各方完全私有信息等缺点，提出一种基于p-ADE算法的多Agent自动协商模型。新模型设计了基于仲裁Agent的多Agent协商协议及协商策略，避免了对协商各方完全私有信息的需求，更符合实际协商环境。p-ADE算法用于生成具有更高适应性的可行协商提议Offer，促进协商各方达成一致，加速协商空间中Pareto最优协商解的搜索速度。实验部分中将新协商模型与目前解决多边多议题协商问题效果最好的混合遗传算法HGA(HybridGeneticAlgorithm,HGA)，在合作环境下的实际多边多议题协商问题中进行性能对比，证明新协商模型能有效地减少协商次数，提高协商效率和稳定性，为多边多议题协商问题的求解提供了新思路。关键词：差分进化算法；高维多峰单目标优化；多目标优化；PET医学图像；多边多议题协商哈尔滨工程大学博士学位论文ABSTRACTABSTRACTABSTRACTABSTRACTDifferentialEvolution(DE)isoneofthecurrentbestevolutionaryalgorithms,whichhasbecometheresearchhotspotinmanyfieldssuchasevolutionarycomputingandintelligentoptimization.Atpresent,DEhassuccessfullybeenappliedtodiversedomainsofscienceandengineering,suchassignalprocessing,neuralnetworkoptimization,patternrecognition,machineintelligence,chemicalengineeringandmedicalscience.However,almostalloftheevolutionaryalgorithms,includingDE,stillsufferfromtheproblemsofprematureconvergence,slowconvergencerateanddifficultparametersetting,especiallyinoptimizinghigh-dimensionalmulti-modalcomplexoptimizationproblems.Inaddition,thestandardDEalgorithmcan'tbeuseddirectlytosolvethemulti-objectiveoptimizationproblems(MOPs)andthisshortcominglimitsthescopeofapplicationofDEtosomeextent.AccordingtotheinsufficiencyofDE,thestructureandkeystepsofthealgorithm,includingmutation,crossoverandparametersetting,aredeeplyinvestigatedinthispaperandbasedonwhichseveralimprovementmeasuresofDEareproposedtoimproveitsoptimalperformance.Inaddition,theimprovedDEalgorithmproposedinthispaperisappliedsuccessfullytosolveseveralfrontierproblems,suchasthefocuscontourextractionofhumanbrainPETimagesandthemulti-lateralmulti-issuenegotiationinE-commerceundercooperativeenvironment.Firstly,inordertoimprovetheconvergenceperformanceofDEinsolvinghigh-dimensionalmulti-modalcomplexoptimizationproblems,anewmodifiedDEalgorithmbasedonaclassificationmechanism,calledp-ADE,ispresented.Concreteimprovementmeasuresinp-ADEinclude:1、AnewDEmutationstrategyisdesigned,inwhichtheglobalbestsolutionandthebestprevioussolutionofeachindividualareutilizedtoguidethesearchdirectionsynchronously,avoidingthesearchblindnessbroughtbytherandomselectionofindividualsindifferencevector;2、Classificationmechanismisintrod