Analyzing the Influence of Domain Features on the Optimality of Service Composition Algorithm

The problem of service composition with end-to-end QoS constraints has been proven to be an NP-hard problem and various evolutionary algorithms have been successfully applied to look for approximately optimal solutions within limited computation time. Favorable heuristic rules are considered as the key of such algorithms, and historical service usage data are widely utilized to help identify the distinct features of problem domains, used as heuristic that would greatly improve the optimality. However, our experiments show that the historical usage data is not always valid on the performance improvement, and there exist underlying dependencies between domain features and optimality of service composition algorithms, and different domain feature values require the composition algorithm to have different parameter settings to ensure the higher optimality. In this paper, we consider two domain features called Priori and Similarity along with some metrics measuring their richness and confidence level. Taking the service domain-oriented artificial bee colony algorithm (S-ABCSC) as an example, we try to discover the underlying dependencies between the domain features, the algorithm parameter settings, and the optimality of the algorithm to help algorithm designers judge whether the given historical usage data delineates valuable domain features that contribute to the optimality improvement, and setting up the best values of S-ABCSC parameters. Several experiments are conducted on different historical service usage data sets, and the results have been partially shown the effectiveness of our approach.