Abstract
Web service composition can be thought of as the combination of reusable functionality modules available over the network to create applications that accomplish more complex tasks, and Evolutionary Computation (EC) techniques have been applied with success to this problem. Genetic Programming (GP) is a traditionally employed EC technique in this domain, and it encodes solutions as trees instead of their natural Directed Acyclic Graph (DAG) form. This complicates the enforcement of dependencies between service nodes, which is much easier to accomplish in a DAG. To overcome this we propose GraphEvol, an evolutionary technique that uses DAGs directly to represent and evolve Web service composition solutions. GraphEvol is analogous to GP, but it implements the mutation and crossover operators differently. Experiments were carried out comparing GraphEvol with GP for a series of composition tasks, with results showing that GraphEvol solutions either match or surpass the quality of those obtained using GP, at the same time relying on a more intuitive representation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ardagna, D., Pernici, B.: Adaptive service composition in flexible processes. IEEE Trans. Softw. Eng. 33(6), 369–384 (2007)
Aversano, L., Di Penta, M., Taneja, K.: A genetic programming approach to support the design of service compositions. Int. J. Comput. Syst. Sci. Eng. 21(4), 247–254 (2006)
Bansal, A., Blake, M.B., Kona, S., Bleul, S., Weise, T., Jaeger, M.C.: Wsc-08: continuing the web services challenge. In: 2008 10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services, pp. 351–354, IEEE (2008)
Channabasavaiah, K., Holley, K., Tuggle, E.: Migrating to a service-oriented architecture. In: IBM DeveloperWorks, 16 Dec 2003
Chen, M., Yan, Y.: Qos-aware service composition over graphplan through graph reachability. In: 2014 IEEE International Conference on Services Computing (SCC), pp. 544–551, IEEE (2014)
Gottschalk, K., Graham, S., Kreger, H., Snell, J.: Introduction to web services architecture. IBM Syst. J. 41(2), 170–177 (2002)
Kuster, U., Konig-Ries, B., Krug, A.: Opossum-an online portal to collect and share sws descriptions. In: 2008 IEEE International Conference on Semantic Computing, pp. 480–481, IEEE (2008)
Milanovic, N., Malek, M.: Current solutions for web service composition. IEEE Int. Comput. 8(6), 51–59 (2004)
Perrey, R., Lycett, M.: Service-oriented architecture. In: 2003 Symposium on Applications and the Internet Workshops, Proceedings, pp. 116–119, IEEE (2003)
Rodriguez-Mier, P., Mucientes, M., Lama, M., Couto, M.I.: Composition of web services through genetic programming. Evol. Intell. 3(3–4), 171–186 (2010)
da Silva, A., Ma, H., Zhang, M.: A graph-based particle swarm optimisation approach to qos-aware web service composition and selection. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 3127–3134, July 2014
Su, K., Liangli, M., Xiaoming, G., Yufei, S.: An efficient parameter-adaptive genetic algorithm for service selection with end-to-end qos constraints. J. Comput. Inf. Syst. 10(2), 581–588 (2014)
Wang, A., Ma, H., Zhang, M.: Genetic programming with greedy search for web service composition. In: Decker, H., Lhotská, L., Link, S., Basl, J., Tjoa, A.M. (eds.) DEXA 2013, Part II. LNCS, vol. 8056, pp. 9–17. Springer, Heidelberg (2013)
Wang, L., Shen, J., Yong, J.: A survey on bio-inspired algorithms for web service composition. In: 2012 IEEE 16th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 569–574, IEEE (2012)
Yoo, J.J.W., Kumara, S., Lee, D., Oh, S.C.: A web service composition framework using integer programming with non-functional objectives and constraints. Algorithms 1, 7 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
da Silva, A.S., Ma, H., Zhang, M. (2015). GraphEvol: A Graph Evolution Technique for Web Service Composition. In: Chen, Q., Hameurlain, A., Toumani, F., Wagner, R., Decker, H. (eds) Database and Expert Systems Applications. Globe DEXA 2015 2015. Lecture Notes in Computer Science(), vol 9262. Springer, Cham. https://doi.org/10.1007/978-3-319-22852-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-22852-5_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22851-8
Online ISBN: 978-3-319-22852-5
eBook Packages: Computer ScienceComputer Science (R0)