基于文化的多目标协同进化算法.pdf

第28卷第7期计算机应用研究Vol．28No．7
2011年7月ApplicationResearchofComputersJul．2011

基于文化的多目标协同进化算法*

赵学臣1，2，王洪国1，邵增珍1，2，苗金凤1，2
(1．山东师范大学信息科学与工程学院，济南250014;2．山东省分布式计算机软件新技术重点实验室，济南
250014)

摘要:为了改进NSGAⅡ算法中存在的分布性等不理想问题，在NSGAⅡ的基础上提出了基于文化的多目标
协同进化算法。该算法提出评测信念空间多样性的指标，从信念空间中提取知识，利用知识来指导种群的进化;
提出知识假说集，以现有知识为基础产生新知识，加强局部搜索，加速算法收敛。仿真实验表明该算法较NSGA
Ⅱ在收敛性及分布性方面均有明显提高。
关键词:多目标;文化;协同进化
中图分类号:TP18;TP301.6文献标志码:A文章编号:1001-3695(2011)07-2494-03
doi:10．3969/j．issn．1001-3695．2011．07．026

Multi-objectiveco-evolutionaryalgorithmbasedonculture

ZHAOXue-chen1，2，WANGHong-guo1，SHAOZeng-zhen1，2，MIAOJin-feng1，2
(1．SchoolofInformationScience＆Engineering，ShandongNormalUniversity，Jinan250014，China;2．ShandongProvincialKeyLaboratory
forDistributedComputerSoftwareNovelTechnology，Jinan250014，China)

Abstract:InordertoovercomethedeficiencyofNSGAⅡondistribution，thispaperproposedamulti-objectiveco-
evolutionaryalgorithmbasedonculture．Thealgorithmproposedanindexwhichwasusedforevaluatingthediversityofbelief
space，extractedknowledgefrombeliefspace，andutilizedtheknowledgetoguidetheevolutionofpopulation．Itproposeda
conceptcalledknowledgehypothesisset，creatednewknowledgesbasedonknowledgesinbeingtoenhancelocalsearchin
sparsearea，whichspeededuptheconvergenceofthealgorithm．Simulationresultsindicatethatthealgorithmimprovessignifi-
cantlyintermsoftheabilityofconvergenceanddistribution．
Keywords:multi-object;culture;co-evolution

在工程实践和科学研究等领域中存在许多的多目标优化
1种群文化
问题。进化算法经一次优化即可获得多个Pareto最优解，因此
具有求解多目标优化问题的优势。目前，国内外学者已对多目本文借鉴文化算法［8］的框架，各种群分别维护一个种群
［1～3］
标进化算法做了大量研究，提出了许多经典的多目标进化进化空间和信念空间。从种群进化空间中选取优秀个体进入
［］［］［］
算法，具有代表性的有VEGA4、MOGA5、NSGAⅡ6、SPEA信念空间，按挤压系数［9］维护信念空间中个体为一定数目。
［］
Ⅱ7等。VEGA对目标函数的处理比较简单，但当搜索空间非维护完成后，以现有知识为基础生成知识假说集，通过检验的
凸时无法求得Pareto最优解;MOGA效率较高，但Pareto最优知识假设一方面可丰富信念空间，另一方面可指导种群进化过
解的分布不理想;SPEA性能优越，但是算法过程十分复杂;程。算法结构如图1所示。
NSGAⅡ采用简洁明晰的非支配排序机制，使算法具有较好的
逼近Pareto最优前沿的能力。
NSGAⅡ虽然收敛速度快，但是过度利用了优秀个体，存在
种群早熟问题。对于较易收敛的函数，NSGAⅡ收敛性较好;但
是对于较难收敛的函数，NSGAⅡ则表现出不足。由此，本文在
NSGAⅡ的基础上，提出了基于文化的多目标协同进化算法1.1知识提取
(CMOCEA)。在种群进化层，基于文化算法的框架，多种群协本文根据