A hybrid imperialist competitive-gravitational attraction search algorithm to optimize cloud service composition

Service composition is among the most important challenges that cloud providers have ever faced. Optimization of QoS attributes when composing simple atomic services to obtain a complex service can be considered to be an NP-hard problem, which could be solved properly by using Hybrid optimization algorithms. In this research, the hybridization of an improved Gravitational Attraction Search (as a local search algorithm) with an Imperialist Competitive Algorithm has led us to introduce and apply a new memetic algorithm for gaining optimal or near optimal response time and execution fees simultaneously, for cloud computing service composition. Using a roulette wheel selection algorithm to make well-advised and non-blind decisions to choose the number of countries in each empire that should be selected to apply a local search to has assisted the hybrid algorithm at achieving better solutions. Introducing a new equation to calculate the QoS eligibility of the solutions that were generated based on the normalization of the response time and execution fee has also led us to compute the results fairly and in a scientifically based manner.