首页*焦点注册*首页Vol.27Decision2012Aug.2012一种基于粒子群算法的改进多目标文化算法文章编号:1001-0920(2012)08-1127-06提出一种基于粒子群算法的改进多目标文化算法并用于求解多目标优化问题.算法中群体空间采用多目标粒子群优化算法进行演化;信念空间通过对形势知识、规范化知识和历史知识的重新定义使之符合多目标优化问题;信念空间和群体空间的交互通过自适应的接受操作和影响操作来实现.若干多目标标准测试函数的仿真结果表明,改进多目标文化算法能够在保持Pareto解集多样性的同时具有较好的均匀性和收敛性.关键词:多目标优化；文化算法；粒子群算法；Pareto最优前沿中图分类号:TP18文献标识码:improvedmulti-objectiveculturalalgorithmbasedparticleswarmoptimizationWUYa-li,XULi-qing(CollegeInformationEngineering，Xi’anUniversityTechnology，Xi’an710048，respondent：WUYa-li，E-mail：eractionbetweenbeliefspacepopulationspaceadaptiveacceptfunctioninfluencefunction.Simulationresultsbenchmarktestfunctionsshowthatimprovedmulti-objectiveculturalalgorithmcanpossessgooduniformityParetooptimalsolution.Keywords:multi-objectiveoptimization；culturalalgorithm；particleswarmoptimization；Paretooptimalfront中一个目标优化必须以其他目标作为代价,因此多目标优化问题的解是一组非劣解,即Pareto最优解集基于种群的进化算法具有隐含的并行特征,可在单次迭代过程中得到多个解,适合求解多目标优化问题.众多研究者对基于种群的进化算法如遗传算法、粒子群算法进行改进,提出了多种多目标遗传算法目标粒子群优化算法[3-5]但目前针对各种基于种群的智能优化算法的研究均集中在生物自然选择这一层面上,对于演化过程中形成的知识没有有效利用.Reynolds提出的文化算法从微观和宏观角度模拟生物层面和文化层面的进化,提供了一种显性的机制来获取、保存和整合问题求解的知识,使种群进化速度超越单纯依靠生物基因遗传的进化速度.目前,将文化算法与已有的智能优化算法相结合来解决多目标优化问题已引起研究者的关注.文献[7]将文化算法的信念空间定义为网格结构,首次提出采用文化算法求解多目标优化问题;对文化算法的知识空间进行扩展,提出一种分阶段多目标协作进化;信念空间中的知识进行定义,提出求解函数优化的多目标文化算法;[10]采用文化算法来调整多目标粒子群算法的加速度系数、认知系数和社会系数;[11]出了一种多目标文化算法,并应用于水资源优化问[12]提出一种基于文化的多目标粒子群优化算法.与上述文献思路不同,本文拟在文化算法的框架下求解多目标优化问题.为了保持Pareto最优前沿的收敛性、多样性和均匀性,本文重点对文化算法中信收稿日期:2010-12-24；修回日期:2011-04-12.基金项目:陕西省自然科学基础研究计划项目(2010JQ8006)；陕西省教育厅科学研究专项基金项目(2010JK711).作者简介:吴亚丽(1975),副教授,从事复杂系统建模、优化与仿线),硕士生,从事复杂系统建模、控制与优化的研究.1128念空间中形势知识、规范化知识和历史知识进行重新定义,使之适应于多目标优化问题的求解;采用循环拥挤距离排序法对外部归档集进行维护,提高对种群空间的均匀采样;采用多目标适应值轮盘赌法选择粒子全局最优位置,以避免Pareto最优解的丢失,法获得了更逼近整个均衡面的非劣解.仿真结果表基于粒子群算法的改进多目标文化算法具有良好的均匀性和收敛性.改改改进进进多多多目目目标标标文文文化化化算算算法法法2.1文文文化化化算算算法法法描描描述述述文化算法算框架如图1所示.算法包含两类进化空间:群体空间和信念空间.群体空间通过演化操作和性能评价进行自身的迭代求解,是算法进行问题求解的主空间.信念空间将接收到的个体经验不断地进行自身的性能评价与演化,形成群体经验,并通过影响函数对群体空间的个体行为规则进行修改,以使群体空间中得到更高的进化效率.文化算法的基本框架2.2改改改进进进多多多目目目标标标文文文化化化算算算法法法采用文化算法求解多目标优化问题,关键要解决的问题有:信念空间中的知识如何定义和更新才能更适合多目标问题的求解;群体空间的演化过程中如何产生非支配解并构成Pareto最优解集;如何保持Pareto最优前沿上优化解的多样性和均匀性.为此提出一种基于粒子群算法的改进多目标文化算法.2.2.1群群群体体体空空空间间间的的的演演演化化化策策策略略略群体空间的演化策略分3个部分:个体演化策略、参数调整和非劣解集的构造.群体中个体的演化策略.改进多目标文化算法的群体空间采用多目标粒子群算法的编码和演化机制.算法中各粒子的速度和位置的演化公式为[13]个粒子在代的速度;粒子在代的位置;个粒子在代的局部最优个体;个粒子在代的全局最优个体;为[0,1]区间的随机数;为当前迭代次数.由于多目标优化问题优化解的特性,需要对式中全局最优个体和局部最优个体的定义进行修正.全局最优个体的选择策略采用多目标适应值轮盘赌法在非劣解集中产生,具体过程为:设多目标优化问题含有(个目标,产生(0,个目标函数适应值,采用轮盘赌策略确定的最好粒子即为该粒 子的全局最好粒子. 当代局部最优个体 的选择规则为: 将种群中根据粒子飞行过程中获得的新解 算法的参数调整策略.为了加快群体空间中多目标PSO算法的收敛速 max分别为惯性权重的最小值和最大 max为最大迭代次数. 随着种群的演化, 加速度 在当前粒子中的比重越来越小, 更适于局部的搜索. 认知系数 调整策略为[14] 可以看出,认知系数随着迭代次数的增大 而减小, 而社会系数随着迭代次数的增大而增大. 表明,在种群演化过程中, 社会行为的作用越来越明 为了保证多目标文化算法得到的Pareto最优前 沿的收敛性、多样性和均匀性, 需要为群体空间构造 传统的多目标进化算法非劣解集的构造通常采用NSGA-II 策略容易丢失互不支配的个体.本文采用一种新的非 劣解集构造策略, 具体步骤如下: Step 则rank[]=rank[] 则rank[]=rank[] +1; 否则, 粒子, 序号不变. 一种基于粒子群算法的改进多目标文化算法1129 Step 将序号为1的粒子放入非支配解集中. 2.2.2 信信信念念念空空空间间间的的的知知知识识识描描描述述述和和和更更更新新新策策策略略略 为了适应多目标优化问题的求解, 本文对文化算 法信念空间中最常用的形势知识、规范化知识和历史 知识的描述及更新策略进行如下修正. 形势知识.形势知识的初始解在群体空间非 支配解集中根据多样性和均匀性指标选择产生, 随机选择非劣解集中的两个粒子, 将两个成员间的差向 量增加到形势知识中选定的非支配解成员上的方 法来产生新个体. 是形势知识中第个粒子, 是群体空间非支配解集中的两个不相同的个体, 新解为 其中是[0,1] 区间的比例系数. 形势知识用来更新信念空间中第 个粒子在 寻优的最优解.产生的新解