Standing on the shoulders of giants: Seeding search-based multi-objective optimization with prior knowledge for software service composition

Context: Search-Based Software Engineering, in particular multi-objective evolutionary algorithm, is a promising approach to engineering software service composition while simultaneously optimizing multiple conflicting Quality-of-Service (QoS) objectives. Yet, existing applications of evolutionary algorithms have failed to consider domain knowledge about the problem into the optimization, which is a perhaps obvious but challenging task. Objective: This paper aims to investigate different strategies of exploring and injecting knowledge about the problem into the Multi-Objective Evolutionary Algorithm (MOEA) by seeding. Further, we investigate various factors that contribute to the effectiveness of seeding, including the number of seeds, the importance of crossover operation and the similarity of historical problems. Method: We conduced empirical evaluations with NSGA-II, MOEA/D and IBEA based on a wide spectrum of problem instances, including 10 different workflow structures, from 5 to 100 abstract services and 510 to 5.529 × 10203 candidate concrete services with diverse QoS on latency, throughput and cost, which was chosen from the real-world WS-DREAM dataset that contains 4500 QoS values. Results: We found that, (i) all seeding strategies generally outperform their non-seeded counterparts under the same search budget with large statistical significance. Yet, they may involve relatively smaller compromise on one or two of the quality aspects among convergence, uniformity and spread. (ii) The implication of the number of seeds on the service composition problems is minimal in general (except for IBEA). (iii) In contrast to the non-seeded counterparts, the seeding strategies suffer much less implications by the crossover operation. (iv) The differences of historical problems, which are important for two proposed seeding strategies, can indeed affect the results in a non-linear manner; however, the results are still greatly better than the non-seeded counterparts even with up to 90% difference of the problem settings. Conclusion: The paper concludes that (i) When applying the seeding strategies, the number of seeds to be placed in is less important in general, except for the pre-optimization based strategies under IBEA. (ii) Eliminating or having less crossover is harmful for multi-objective service composition optimization, but the seeding strategies are much less sensitive to this operator than their non-seeded counterparts. (iii) For the history based seeding strategies, the seeds do not have to come from the most similar historical composition problem to achieve the best HV value, but a largely different historical problem should usually be avoided, unless they are the only available seeds.