多资源均衡优化的布谷鸟算法

摘要：针对标准多目标布谷鸟算法（CSA）后期收敛速度慢、收敛精度不高的缺陷，提出一种求解多资源均衡优化问题的改进多目标布谷鸟算法。首先，引入非均匀变异算子，以均衡算法的全局搜索能力和局部寻优能力；然后，引进差分进化算子，促进群体间的合作和信息交流，提高算法的收敛精度。通过算例测试表明，改进的多目标布谷鸟算法比标准多目标算法和VEPSOBP算法具有更好的全局收敛性。

关键词： 多目标布谷鸟算法； 多资源均衡优化； 非均匀变异算子； 差分进化算子； 全局收敛性

中图分类号： TP18 文献标志码： A

0引言

在项目计划制定阶段，网络计划的初始方案往往只提供了项目各项工作的资源需求、逻辑关系以及时间参数等基本信息，将其运用到指导项目的实施过程必须根据项目的限制条件和特殊目的对其进行优化。常见的网络计划优化包括工期优化、费用优化以及资源优化。资源均衡优化作为资源优化的一种是指在工期固定的前提下，合理地安排各项工作的开始时间，使得资源需求在整个工期内趋于均衡。资源均衡通常具有降低管理难度、减少临时设施、降低工程成本以及最大限度地保障各项目标实现的现实意义[1]，因此资源均衡优化问题越来越受到项目管理者和专家学者的关注。通过查阅文献可知，相关研究主要集中在单资源单目标的网络计划优化[2-3]，并形成了相对成熟的优化理论与方法，而在实际项目中，一项工作任务通常需要耗费人工、材料及机械多种资源，因此多资源均衡优化更为切合实际。多资源均衡优化问题以各资源均衡评价指标为优化目标，则多资源均衡优化问题即成为多目标优化问题。目前求解多资源均衡优化问题较为常见的方法是通过引入权重系数将其转化为单目标资源均衡问题[4]。郭研等[5]认为该方法主要的缺陷在于权重系数选择的主观性与随机性以及优化解的单一性，而多目标优化问题存在着一组Pareto解集，这种方法不可避免地会遗漏更适合实际问题的其他方案。多目标进化算法是搜索此类优化问题Pareto解集的有效方法，文献[5-6]采用基于Pareto的向量评价粒子群（VectorEvaluatedParticleSwarmOptimizationbasedonPareto，VEPSOBP）算法分别对单项目多资源和多项目多资源优化问题进行求解获得一组Pareto解集，取得了较为良好的效果。文献[7]则提出了一种基于动态种群的多目标粒子算法来求解多模式多资源均衡优化问题并通过实例仿真验证了其可行性和有效性。但是，多目标粒子群算法的性能依赖于全局最优粒子选取，算法容易陷入局部最优而影响优化结果的质量。

布谷鸟算法（CuckooSearchAlgorithm，CSA）是由Yang等[8]提出的一种新型智能算法，它是通过模拟自然界中布谷鸟借窝产卵的繁殖习性以及Levy飞行特征而发展起来的智能算法，具有参数设置少、收敛速度快、全局搜索能力强等优点，并且实例测试结果证明了它比遗传算法、粒子群算法、萤火虫算法具有更高寻优性能[8-9]。鉴于此，Yang等在布谷鸟算法中引入了支配关系和非支配集的概念，构建了多目标布谷鸟（MultiobjectiveCuckooSearch，MOCS）算法，将算法拓展应用于多目标优化领域。多目标布谷鸟算法继承了布谷鸟算法优良特性，在基准函数以及工程优化问题测试中发现，算法相比传统的NSGAⅡ（NondominatedSortingGeneticAlgorithmⅡ）、SPEA（StrengthParetoEvolutionaryAlgorithm）以及VEGA（VectorEvaluatedGeneticAlgorithm）等算法更能逼近真实的Pareto解集[10]。Leandrodos等则对控制步长设置做了改进，采用Duffing振子混沌映射动态调整步长，改进多目标布谷鸟算法，并用于JilesAtherton磁滞模型参数估计[11]。Hanoun等将多目标布谷鸟算法应用于求解多目标车间调度问题，结果同样表明了多目标布谷鸟算法的有效性与优越性[12]。

本文针对布谷鸟算法的搜索机制以及多资源均衡问题的特点，提出一种改进的多目标布谷鸟算法。改进多目标布谷鸟算法引入了非均匀变异算子[13-16]取代标准多目标布谷鸟算法中的变异策略，使算法具有均衡的“勘探”和“开发”能力，同时采用差分进化算子[17-19]促进鸟群之间协作，实现种群间信息共享，提高算法的收敛精度。

5结语

本文针对多资源均衡优化问题构建了其数学模型，并提出了一种改进多目标布谷鸟算法对其求解。改进的算法引入了非均匀变异算子动态调节种群的变异范围，使算法具备较为均衡的全局搜索能力和局部寻优能力，差分进化算子则加强了群体间的信息交流。仿真测试结果表明，在多资源均衡优化问题领域，多目标布谷鸟算法相比VEPSOBP算法能收敛到更优的Pareto最优解，具有更强的全局收敛性能，同时改进多目标布谷鸟算法的收敛精度极大提高，收敛速度明显改善，是一种可行和高效的方法。改进多目标布谷鸟算法提供了一组Pareto最优解，如何从中选择一个切合实际工程需求的解作为施工方案将是下一步研究工作的重点。

参考文献：

[1]CHENGH，CHENQ.Projectmanagement[M].Beijng：ChinaArchitecture&BuildingPress，2009：256-257.

[2]EASAS.Resourcelevelinginconstructionbyoptimization[J].JournalofConstructionEngineeringandManagement，1989，115（2）：302-312.

[3]GUOYT，BAISJ，XUJC，etal.Theresourcelevelingbasedonparticleswarmoptimization[J].SystemEngineering，2008，26（4）：99-103.

[4]WANGZH，QIX.Theweightoptimalchoicemethodofmultiresourceleveling[J].JournalofIndustrialEngineeringandEngineeringManagement，2002，16（3）：91-93.

[5]GUOY，LIN，LIXS.MultiresourceequilibriumoptimizationbasedonVEPSOBP[J].SystemEngineering，2009，27（10）：108-111.

[6]GUOY，LIN，LIXS.MultiresourcelevelinginmultipleprojectsandvectorevaluatedparticleswarmoptimizationbasedonPareto[J].ControlandDecision，2010，25（5）：790-793.

[7]GUOY，LIN，LIXS.Multimodemultipleresourceslevelingandmultiobjectiveparticleswarmoptimizationwithdynamicpopulation[J].ControlandDecision，2013，28（1）：131-135.

[8]YANGX，SUASHD.CuckoosearchviaLevyflight[C]//Proceedingsofthe2009WorldCongressonNature&BiologicallyInspiredComputing.Piscataway，NJ：IEEEPress，2009：210-214.

[9]LIUCP，YECM.Cuckoosearchalgorithmfortheproblemofpermutationflowshopscheduling[J].JournalofUniversityofShanghaiforScienceandTechnology，2013，35（1）：17-20.

[10]XINSY，SUASHD.Multiobjectivecuckoosearchfordesignoptimization[J].Computers&OperationResearch，2011，40（6）：1616-1624.

[11]LEANDRODOSSC.MultiobjectivecuckoosearchalgorithmbasedonDuffingsoscillatorappliedtoJilesAthertonvectorhysteresisparametersestimation[J].IEEETransactionsonMagnetics，2013，45（5）：1745-1748.

[12]HANOUNS.SolvingamultiobjectivejobshopschedulingproblemusingParetoarchivedcuckoosearch[C]//Proceedingsofthe17thIEEEConferenceonEmergingTechnologies&Factoryautomation.Piscataway，NJ：IEEEPress，2012：1-8.

[13]YANGC，DENGFQ，YANGHD，etal.Quantuminspiredevolutionaryalgorithmtomultiobjectivenumericaloptimizationproblems[J].JournalofSouthChinaUniversityofTechnology：NaturalScienceEdition，2009，37（1）：79-85.

[14]ZHAOXC.Nonuniformvariancefuzzyguidedparticleswarmalgorithm[C]//ICNC2009：Proceedingsofthe2009FifthInternationalConferenceonNaturalComputation.Piscataway，NJ：IEEEPress，2009：341-345.

[15]JIAOLC，SHANGRH，MAWP，etal.Theoryandapplicationofmultiobjectiveartificialimmunealgorithm[M].Beijing：SciencePress，2010：71-76.

[16]WANGXY，ZOUL，ZHANGWX，etal.Reactivepoweroptimizationofpowerbasedontheimprovedimmunegeneticalgorithm[J].PowerSystemProtectionandControl，2010，38（1）：1-5.

[17]LIUB，WANGL，JINYH.Advanceindifferentialevolution[J].ControlandDecision，2007，22（7）：721-729.

[18]PARASSURAMA，DEEPASN，KARTHICKM.Ahybridtechniqueusingparticleswarmoptimizationanddifferentialevolutiontosolveeconomicdispatchproblemwithvalvepointeffect[C]//Proceedingsofthe2011InternationalConferenceonRecentAdvancementsinElectrical，ElectronicsandControlEngineering.Piscataway，NJ：IEEEPress，2011：51-56.

[19]YIZJ，QIRB，XUB，etal.Constraineddifferentialimmuneclonalalgorithmanditsapplicationinoptimizationofgasolineblendingoperation[J].JournalofEastChinaUniversityofScienceandTechnology：NaturalScienceEdition，2013，39（3）：311-318.

[20]MICHALEWICZZ.Geneticalogrithms+datastructures=evolutionprograms[M].3rded.Berlin：SpringerVerlag，1996：285-287.

[21]WULH.Researchonmultiobjectivedynamicdifferentialevolutionanditsapplication[D].Changsha：HunanUniversity，2011.

[22]KNOWLESJD，CORNEDW.ApproximationgthenondominatedfrontusingtheParetoarchivedevolutionstrategy[J].EvolutionaryComputation，2000，8（2）：149-172.

[23]MIKKELTJ.ReducingtheruntimecomplexityofmultiobjectiveEAs：theNSGAIIandotheralgorithms[J].IEEETransactionsonEvolutionaryComputation，2003，7（5）：503-515.