Composition of web services through genetic programming | Evolutionary Intelligence Skip to main content

Advertisement

Springer Nature Link
Log in

Composition of web services through genetic programming

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

Abstract

Web Services are interfaces that describe a collection of operations that are network-accessible through standardized web protocols. When a required operation is not found, several services can be compounded to get a composite service that performs the desired task. To find this composite service a search process in a, generally, huge search space must be performed. The algorithm that composes the services must select the adequate atomic processes and, also, must choose the correct way to combine them using the different available control structures. In this paper a genetic programming algorithm for web services composition is presented. The algorithm has a context-free grammar to generate the valid structures of the composite services and, also, it includes a method to update the attributes of each node. Moreover, the proposal tries to minimize the number of services, and looks for compositions with the minimum execution path. A full experimental validation with four different repositories with up to 1,090 web services has been done, showing a great performance in all the tests as the algorithm finds a valid solution with a short execution path.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. In OWL-S a process is used with the same meaning as a service. Thus a single service is named as an atomic process, and composite services are named as composite processes. We use this notation in the grammar that describes the chromosomes of our evolutionary algorithm.

  2. This complexity is for the worst case: a composition which uses all the services of the repository. However, if we knew in advance the size of the composition (this is, in general, not truth), the complexity would be \(O\left({\frac{n!} {(n-p)!}}\right)\), where p is the number of services of the composition.

  3. In a complete binary tree every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

  4. http://projects.semwebcentral.org/frs/download.php/386/owls-tc2_2_rev_2.zip.

  5. http://cec2008.cs.georgetown.edu/wsc08/downloads/ChallengeResults.rar.

  6. These times have been obtained with an Intel Xeon(R) Quadcore E5320 1.86GHz processor with 8GB of RAM, and the algorithm was implemented in Java and run on Linux.

References

  1. Aiello M, van Benthem N, Khoury E (2008) Visualizing compositions of services from large repositories. In: Proceedings of the fifth IEEE conference on enterprise computing, e-commerce and e-services (EEE’08). IEEE Computer Society, Washington, DC, pp 359–362.

  2. Alamri A, Eid M, Saddik AE (2006) Classification of the state of the art dynamic web services composition techniques. Int J Web Grid Serv 2(2):148–166

    Article  Google Scholar 

  3. Alonso G, Casati F, Kuno H, Machiraju V (2003) Web services. Springer, Berlin

  4. Anderson BB, Hansen JV, Lowry PB (2009) Creating automated plans for semantic web applications through planning as model checking. Expert Syst Appl 36(7):10595–10603

    Article  Google Scholar 

  5. Aversano L, di Penta M, Taneja K (2006) A genetic programming approach to support the design of service compositions. Int J Comput Syst Sci Eng 4:247–254

    Google Scholar 

  6. Bansal A, Blake MB, Kona S, Bleul S, Weise T, Jaeger MC (2008) WSC-08: continuing the web services challenge. In: Proceedings of the 5th IEEE international conference on enterprise computing, e-commerce and e-services (EEE’08). IEEE, pp 351–354

  7. Bertoli P, Pistore M, Traverso P (2010) Automated composition of web services via planning in asynchronous domains. Artif Intell 174(3–4):316–361

    Article  MathSciNet  Google Scholar 

  8. Blum AL, Furst ML (1997) Fast planning through planning graph analysis. Artif Intell 90(1–2):281–300

    Article  MATH  Google Scholar 

  9. Chang W-C, Wu C-S, Chang C (2005) Optimizing dynamic web service component composition by using evolutionary algorithms. In: Proceedings of the 2005 IEEE/WIC/ACM international conference on web intelligence (WI’05). IEEE Computer Society, Washington, DC, pp 708–711

  10. Curbera F, Goland Y, Klein J, Leymann F, Roller D, Thatte S, Weerawarana S (2002) Business process execution language for web services, version 1.0, November 2002. Standards proposal by BEA Systems, International Business Machines Corporation, and Microsoft Corporation

  11. Curbera Francisco, Nagy William A., Weerawana Sanjiva (2001) Web Service: Why and How. In: Proceedings of the OOPSLA-2001 workshop on object-oriented services. Tampa, Florida, USA

  12. Dustdar S, Schreiner W (2005) A survey on web services composition. Int J Web Grid Serv 1(1):1–30

    Article  Google Scholar 

  13. Hoffmann Jörg, BP, Pistore M (2007) Web service composition as planning, revisited: in between background theories and initial state uncertainty. In: Proceedings of the 22nd national conference on artificial intelligence (AAAI’07). AAAI Press, pp 1013–1018

  14. Klusch M, Gerber A (2006) Fast composition planning of owl-s services and application. In: Proceedings of the European conference on web services (ECOWS’06). IEEE Computer Society, Washington, DC, pp 181–190

  15. Kuster U, Konig-Ries B, Krug A (2008) Opossum—an online portal to collect and share sws descriptions. In: Proceedings of the 2th IEEE international conference on semantic computing (ICSC 2008). IEEE Computer Society, Santa Clara, pp 480–481

  16. Madhusudan T, Uttamsingh N (2006) A declarative approach to composing web services in dynamic environments. Decis Support Syst 41(2):325–357

    Article  Google Scholar 

  17. Martin D, Burstein M, Hobbs J, Lassila O, McDermott D, McIlraith S, Narayanan S, Paolucci M, Parsia B, Payne T, Sirin E, Srinivasan N, Sycara K (2004) OWL-S: semantic markup for web services. World Wide Web Consortium (W3C), November 2004. Available at http://www.w3.org/Submission/OWL-S/

  18. Nau D, Au T-C, Ilghami O, Kuter U, Murdock W, Wu D, Yaman F (2003) SHOP2: an HTN planning system. J Artif Intell Res 20(4):379–404

    MATH  Google Scholar 

  19. Oh S-C, Lee D, Kumara SRT (2006) A comparative illustration of ai planning-based web services composition. SIGecom Exch 5(5):1–10

    Article  Google Scholar 

  20. Oh S-C, Lee D, Kumara SRT (2008) Effective web service composition in diverse and large-scale service networks. IEEE Trans Serv Comput 1(1):15–32

    Article  Google Scholar 

  21. Pistore M, Marconi A, Bertoli P, Traverso P (2005) Automated composition of web services by planning at the knowledge level. In Proceedings of the 19th international joint conference on artificial intelligence (IJCAI’05). Morgan Kaufmann Publishers Inc, San Francisco, pp 1252–1259

  22. Rao J, Küngas P, Matskin M (2006) Composition of semantic web services using linear logic theorem proving. Inform Syst 31(4):340–360

    Article  Google Scholar 

  23. Ren K, Liu X, Chen J, Xiao N, Song J, Zhang W (2008). A QSQL-based efficient planning algorithm for fully-automated service composition in dynamic service environments. In: Proceedings of the 2008 IEEE international conference on services computing (SCC’08). IEEE Computer Society, Washington, DC, pp 301–308

  24. Russell SJ, Norvig P (2009) Artificial intelligence: a modern approach. Prentice Hall, Englewood Cliffs

    Google Scholar 

  25. Sirin E, Parsia B, Wu D, Hendler J, Nau D (2004) Htn planning for web service composition using shop2. J Web Semant 1(4):377–396

    Google Scholar 

  26. Vanrompay Y, Rigole P, Berbers Y (2008) Genetic algorithm-based optimization of service composition and deployment. In: Proceedings of the 3rd international workshop on services integration in pervasive environments (SIPE’08). ACM, New York, pp 13–18

  27. Wu Z, Gomadam K, Ranabahu A, Sheth AP, Miller JA (2007) Automatic composition of semantic web services using process and data mediation. In: Proceedings of the 9th international conference on enterprise information systems (ICEIS’07). Funchal, Portugal, pp 453–461

  28. Xiangbing Z (2010) Semantics web service characteristic composition approach based on particle swarm optimization volume 56 of Lecture Notes in Electrical Engineering. Springer, pp 279–287

  29. Zheng X, Yan Y (2008) An efficient syntactic web service composition algorithm based on the planning graph model. In: Proceedings of the 2008 IEEE international conference on web services (ICWS’08). IEEE Computer Society, Washington, DC, pp 691–699

Download references

Acknowledgments

This work was supported by the Spanish Ministry of Science and Innovation under Grant TSI2007-65677-C02-02. Manuel Mucientes is supported by the Ramón y Cajal program of the Spanish Ministry of Science and Innovation.

Author information

Authors and Affiliations

  1. Department of Electronics and Computer Science, University of Santiago de Compostela, E-15782, Galicia, Spain

    Pablo Rodríguez-Mier, Manuel Mucientes, Manuel Lama & Miguel I. Couto

Authors
  1. Pablo Rodríguez-Mier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manuel Mucientes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manuel Lama
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Miguel I. Couto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Manuel Mucientes.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rodríguez-Mier, P., Mucientes, M., Lama, M. et al. Composition of web services through genetic programming. Evol. Intel. 3, 171–186 (2010). https://doi.org/10.1007/s12065-010-0042-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-010-0042-z

Keywords

Search

Navigation