基于组合优化问题的多目标模因算法的-研究

《基于组合优化问题的多目标模因算法的-研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京航空航天大学硕士学位论文摘要组合优化问题，如旅行商问题(TSP)，车间调度问题(JSP)和软件版本发布问题(NRP)等在现实世界中具有广泛的应用。由于这类问题拥有巨大的搜索空间和众多局部最优等因素的影响，没有精确算法能够保证获得此类问题的最优解。模因算法(MAs)是针对此类复杂优化问题的一类进化算法，它采用了全局搜索定位好的区域，再采用局部搜索定位好的最优解。本文主要针对组合优化问题，研究多目标下的模因算法。本文包括以下几个方面：1、分析了具有代表性的多目标优化算法，包括基于带精英策略的快速非支配排序遗传算法(NSGA-II)、基于分解的多目标进化算法(MOEA/D)等

2、，为后续的研究提供了支撑。2、在基于分解的多目标优化框架下，本文采用了基因算法(GA)作为全局搜索，并使用了模拟退火算法(SA)作为局部搜索算法，便于在可能的最优解的区域能够进行更加精细化的搜索，以保证算法具备更好的收敛性能。3、本文分别使用了两种自适应性机制，通过分析历史收敛性和多样性信息，指导局部搜索的过程，从而进一步提高算法的效率。这两种自适应机制分别为基于子问题收敛实效信息的自适应局部搜索和基于外部集信息的自适应局部搜索。4、我们将算法使用于软件版本发布问题(NRP)和车辆路径问题(VRP)；与其他算法的对比实验表明，我们提出的模因算法非常具有竞争力。此外，根据真实

3、数据的NRP模型，我们分别建立了约束条件下的单目标NRP和2个目标NRP优化模型（我们将约束违反程度作为第二个目标），再分别采用多目标算法与state-of-art的单目标优化算法进行比较，与通常我们直觉性地认为单目标问题更加容易求解，实验结果表明多目标算法在真实数据的NRP问题上要优于单目标算法。关键词：多目标组合优化，模因算法，基于分解的方法，局部搜索，自适应I基于组合优化问题的多目标模因算法的研究ABSTRACTCombinatorialOptimizationProblems(COPs),suchastravelingsalesmanproblem,job-fows

4、hopschedulingproblem,softwarenextreleaseproblem,etc.,areverypervasiveinthereal-worldapplications.Duetothehugesearchspaceandmanylocaloptimaofsuchproblems,noexactalgorithmscansolvetheminthereasonabletime.Memeticalgorithms(MAs)belongtoadvancedevolutionaryalgorithms,usedtoobtaingoodapproximate

5、solutons.MAsusuallyadopttheglobalsearchtolocatepromisingregions,andthenuselocalsearchtorefinesuchregionsinthehopeofobtainingtheoptimalsolutions.Thispaperstudiesthemultiobjectivememeticalgorithmsforcombinatorialoptimization,asfollows.1)Therepresentativesofdecompositionbasedalgorithm(MOEA/D)

6、anddominationbasedalgorithm(NSGA-II)areintroduced.2)ThisthesisadoptsanewframeworkofMAsbasedondecomposition,inwhichthegeneticalgorithm(GA)isusedastheglobalsearch,andsimulatedannealingalgorithm(SA)asthelocalsearch.3)Inaddition,thisthesiscomparestwoadaptivemechanisms,bothofwhichusethehistoric

7、alinformationtoguidethelocalsearchprocess,soastofurtherenhancetheefficiencyoftheproposedalgorithm.4)Theproposedalgorithmisappliedtothesoftwarenextreleaseproblem(NRP)andvehicleroutingproblems(VRP).Theexperimentalresultsshowthatourproposedapproachisverycompetiti