多目标服务工作流混合粒子群调度算法  

Hybrid particle swarm optimization algorithm for multi-objective scheduling in service-workflows

作　　者：张晓东[1] 王茜[2] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]东南大学计算机网络和信息集成教育部重点实验室,南京210096

出　　处：《东南大学学报（自然科学版）》2010年第3期491-495,共5页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60873236;60973073);国家高技术研究发展计划(863计划)资助项目(2008AA04Z103)

摘　　要：针对NP难的服务工作流时间-费用优化问题,提出多目标混合粒子群算法(HMOPSO)来优化工作流调度问题.HMOPSO算法包括:初始种群生成、适应值分配、种群多样性保持、外部种群和极值选择.通过分析服务工作流的特征,构建有效的粒子结构使之离散化;通过设定单目标最优初始解,优化初始种群;通过引入外部种群和基于小生境技术的网格方法,获得分布均匀的Pareto最优解集.实验结果表明,HMOPSO具有更快的收敛速度和更好的寻优能力,并且在不同特征的问题实例上获得了数量众多、分布均匀、有较高质量的Pareto最优解集.A multi-objective hybrid PSO（particle swarm optimization） method is proposed for the time-cost optimization problem in service-workflows,a NP-Hard problem.Characteristics of service-workflows are analyzed.Discrete particles are constructed.HMOPSO is included： initial population generation,fitness distribution,population diversity maintainance,outside population and extreme choice.The initial population is generated by setting optimal solutions to single-objective problems.To obtain an evenly distributed Pareto set,an outside population and a meshing method based on the niche technique are introduced.Experimental results show that the proposed algorithm is efficient and effective for the considered problem.Many evenly distributed Pareto sets with high quality are obtained for various characteristic instances.

关 键 词：服务工作流 有向无环图(DAG) 粒子群优化(PSO) 多目标优化 PARETO解集 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]