Home // International Journal On Advances in Software, volume 7, numbers 3 and 4, 2014 // View article

Combining Genetic Algorithm and SMT into Hybrid Approaches to Web Service Composition Problem

Authors:
Artur Niewiadomski
Wojciech Penczek
Jaroslaw Skaruz

Keywords: Web Service Composition; Concrete Planning; Genetic Algorithm; Satisfiability Modulo Theories; Hybrid Algorithm

Abstract:
The paper deals with the concrete planning problem – a stage of the Web Service Composition in the Plan ICS framework, which consists in choosing the best service offers in order to satisfy the user query and to maximize the quality function. We introduce a novel planning technique based on a combination of a Genetic Algorithm (GA) with a Satisfiability Modulo Theories (SMT) solver, which allows to obtain better results than each of the methods separately. We give three versions of a hybrid algorithm. Two of them involve a modification of the standard GA in such a way that after every couple of iterations of GA, several top-ranked individuals are processed by the SMT-based algorithm in order to improve them. The third one exploits an SMT-solver in order to generate the initial populations for GA, which results in a substantial improvement in the overall algorithm efficiency. The paper presents experimental results, which seem to be very encouraging.

Pages: 675 to 685

Copyright: Copyright (c) to authors, 2014. Used with permission.

Publication date: December 30, 2014

Published in: journal

ISSN: 1942-2628