基于分解排序的多目标进化算法的研究

《基于分解排序的多目标进化算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP391论文编号：102871616-S046学科分类号：081203硕士学位论文基于分解排序的多目标进化算法的研究研究生姓名杨志翔学科、专业计算机科学与技术研究方向计算智能理论及应用指导教师蔡昕烨副教授南京航空航天大学研究生院计算机科学与技术学院二О一六年一月NanjingUniversityofAeronauticsandAstronauticsTheGraduateSchoolCollegeofComputerScienceandTechnologyAMultiobjectiveEvolutionaryAlgorithmBasedonDecompos

2、itionandSortingAThesisinComputerScienceandTechnologybyYangZhixiangAdvisedbyAssociateProf.CaiXinyeSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringJanuary,2016承诺书本人声明所呈交的硕士学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京航空航天大学或其

3、他教育机构的学位或证书而使用过的材料。本人授权南京航空航天大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）作者签名：日期：南京航空航天大学硕士学位论文摘要由于基于种群的进化算法在单次运行中能近似出一个Pareto解集，因此多目标进化算法已成为一种较为普遍且有效的求解多目标优化问题的方法。本文将基于分解和排序的方法融入到多目标进化算法框架中以求解多目标优化问题。本文主要包括如下部分：第一，基于分解的多目标进化算法（如MOEA/D）将一个多目标优化问题分解成一组单目标优化子

4、问题，然后并行地求解它们。为了在进化过程中进一步平衡算法的收敛性和多样性，我们提出了一种新的解选择方法：首先通过解在各个子问题上的收敛性对它们进行整体排序，然后基于解之间的多样性进行二次选择。我们将该方法嵌入到基于分解的算法框架中并将它和三个经典多目标进化算法以及一个目前较好的多目标算法进行比较。实验结果表明所提出的算法非常具有竞争力。第二，在MOEA/D及其变种算法中，每个子问题有且仅有一个解与之关联。隐含的假设为每个子问题对应一个不同的Pareto最优解。这种假设对于一些特殊的多目标优化问题（如具有分段的不完整的Pareto前沿的问题）并不成立。为了进一步拓展基于分

5、解的多目标进化算法，在本文提出的算法（MOEA/D-SAS）中，不同的解可被关联到相同的子问题，一些子问题甚至可以没有解与之关联。同时，不同于其它算法，本文使用了基于分解的排序（DBS）和基于角度的选择（ABS）来平衡算法的收敛性和多样性。为了减少算法的计算复杂度，DBS仅对子问题的局部邻居解进行排序；ABS利用解在目标空间域的角度信息来维持一个更加细化（fine-grained）的多样性。实验表明MOEA/D-SAS能够同时保持良好的收敛性和多样性，特别是对于特殊的多目标优化问题（如具有不连续且不完整的Pareto前沿）更为有效。此外，我们对DBS的计算效率和ABS的

6、作用也进行了详细分析和讨论。关键词：多目标优化，进化计算，多样性，基于角度选择，邻居，基于分解排序I基于分解排序的多目标进化算法的研究ABSTRACTDuetothepopulation-basednatureofevolutionaryalgorithmsthatisabletoapproximateaParetosetinasinglerun,multi-objectiveevolutionaryalgorithms(MOEAs)havebecomeprevalentandefficientapproachesforsolvingmulti-objectiveopt

7、imizationproblems(MOPs).Thispaperincorporatesthemethodsofdecompositionandsortingintotheframeworkofmulti-objectiveevolutionaryalgorithmstosolvemulti-objectiveoptimizationproblems.Thepapermainlyincludesthefollowingparts.First,multiobjectiveevolutionaryalgorithmbasedondecomp