An Improved Artificial Bee Colony Approach to QoS-Aware Service Selection

摘要

As available services accumulate on the Internet, QoS-aware service selection (SSP) becomes an increasingly difficult task. Since Artificial Bee Colony algorithm (ABC) has been successful in solving many problems as a simpler implementation of swarm intelligence, its application to SSP is promising. However, ABC was initially designed for numerical optimization, and its effectiveness highly depends on what we call optimality continuity property of the solution space, i.e., similar variable values (or neighboring solutions) result in similar objective values (or evaluation results). We will show that SSP does not possess such property. We further propose an approximation approach based on greedy search strategies for ABC, to overcome this problem. In this approach, neighboring solutions are generated for a composition greedily based on the neighboring services of its component services. Two algorithms with different neighborhood measures are presented based on this approach. The resulting neighborhood structure of the proposed algorithms is analogical to that of continuous functions, so that the advantages of ABC can be fully leveraged in solving SSP. Also, they are pure online algorithms which are as simple as canonical ABC. The rationale of the proposed approach is discussed and the complexity of the algorithms is analyzed. Experiments conducted against canonical ABC indicate that the proposed algorithms can achieve better optimality within limited time.