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

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

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

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 Co- evolution （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.