›› 2015, Vol. 21 ›› Issue (第8期): 2213-2227.DOI: 10.13196/j.cims.2015.08.027

Previous Articles     Next Articles

Multiple service processes optimization with slack temporal constraints based on cooperative coevolution algorithm

  

  • Online:2015-08-31 Published:2015-08-31
  • Supported by:
    Project supported by the National Natural Science Foundation,China(No.61473035),and the Fundamental Research Funds for the Central Universities,China(No.FRF-TP-14-017A2).

基于协同进化的松弛时序约束多服务流程优化

梁合兰1,杜彦华2,李苏剑2   

  1. 1.苏州大学计算机科学与技术学院
    2.北京科技大学机械工程学院
  • 基金资助:
    国家自然科学基金资助项目(61473035);中央高校基本科研业务费专项资金资助项目(FRF-TP-14-017A2)。

Abstract: To meet the requirements of complex service processes application,an optimization approach for multiple processes with slack temporal constraints was proposed.A formal model for multi-processes optimization with slack temporal constraints was designed,and the satisfaction principle on slack temporal constraints was defined,which could lay a foundation for the temporal verification and process optimization.Aiming at the problems of large-scale searching and slack temporal coordination between different processes,a Non-uniform based Hybrid Cooperative Coevolution (NHCC) algorithm was proposed to solve the problem.By referencing Potter's cooperative coevolution framework,some improved strategies such as sub-population evolution based on pheromone crossing,sub-populations collaboration based on non-uniform probability and elite sub-individuals migration were designed to increase the searching efficiency and population diversity.Several experiments were executed and the results showed the effectiveness and advantage of proposed method in both speed and accuracy.

Key words: service processes, quality of service, temporal constraints, cooperative coevolution, non-uniform probability

摘要: 为满足复杂服务流程优化的需求,提出一种新的松弛时序约束下的多服务流程优化方法。建立了多服务流程优化问题的形式化模型,并通过定义带松弛量的时序约束满足性,为实现时序约束的量化判定及流程优化求解奠定基础。针对问题模型具有搜索规模大且需考虑跨流程间松弛时序协调的难点,提出基于非均衡协作的混合协同进化算法实现模型求解。该算法参考Potter的协同进化框架,设计了基于信息素交叉的子种群进化、非均衡概率的种群间协作及精英迁移等改进策略,有利于提高种群搜索导向性及保持种群多样性。通过与现有方法的多组实验对比,证明了该算法在求解精度及执行时间上的优越性。

关键词: 服务流程, 服务质量, 时序约束, 协同进化, 非均衡概率

CLC Number: