一种求解有状态服务选取问题的遗传算法

A Genetic Algorithm for Stateful Service Selection

基于QoS的Web服务选取问题,通常认为应用工作流中的任务是相互独立的,而在很多实际应用中,工作流的某些任务之间往往需要共享状态信息,由此增加了任务绑定约束,使得求解复杂度提高,影响了选取效率.针对现有方法的不足,提出了一种面向有状态服务选取的遗传算法,其中重新定义了交叉操作和变异操作,使得所有个体均满足任务状态关联绑定约束,同时在个体评价策略中引入罚函数,并进行个体相似性判断以防止过早收敛.实验表明,提出的算法在有状态服务选取问题中,可求得质量良好的解,且收敛速度快,选取效率亦优于现有算法.

Tasks in the workflow of an application each other in current web service selection based on are generally considered to be independent of QoS. In practice, however, state information is often shared among some tasks in the workflow, which adds binding constraints between tasks and web services, resulting in higher time complexity and lower selection efficiency. Aiming at drawbacks of the existing methods, a genetic algorithm for stateful service selection was proposed. In the proposed algorithm, genetic operations including crossover and mutation were redefined in order to make all individuals meet state-correlate binding constraints among tasks. In addition, to prevent premature convergence, penalty function was introduced into individual evaluation strategy; moreover, similarity judgment between individuals was also included in the algorithm. The experiments results showed that with regards to stateful service selection, good solution and fast convergence rate can be obtained using the proposed algorithm; furthermore, the proposed algorithm is more efficient than the existing algorithms.