Solving the abstract planning problem using genetic algorithms

• Autorzy: Skaruz J. , Niewiadomski A. , Penczek W.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a new approach based on genetic algorithms to the abstract planning problem, which is the first stage of the web service composition problem. An abstract plan is defined as an equivalence class of sequences of service types that satisfy a user query. Intuitively, two sequences are equivalent if they are composed of the same service types, but not necessarily occurring in the same order. The objective of our genetic algorithm (GA) is to return representatives of abstract plans without generating all the equivalent sequences. The paper presents experimental results compared with the results obtained from SMT-solver, which show that GA finds solutions for very large sets of service types in a reasonable time.

Słowa kluczowe

EN

abstract planning; genetic algorithms; web service composition

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2013
• Tom: Vol. 1-2(17)
• Strony: 29--48
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Skaruz J.

• Institute of Computer Science, University of Natural Sciences and Humanities, 3 Maja 54, 08-110 Siedlce, Poland

autor

Niewiadomski A.

• Institute of Computer Science, University of Natural Sciences and Humanities, 3 Maja 54, 08-110 Siedlce, Poland

autor

Penczek W.

• Institute of Computer Science, University of Natural Sciences and Humanities, 3 Maja 54, 08-110 Siedlce, Poland
• Institute of Computer Science, Polish Academy of Sciences, Jana Kazimierza 5, 01-248, Warsaw, Poland

Bibliografia

• 1. S. Ambroszkiewicz. Entish: An approach to service description and composition. ISBN 83-910948-7-1, ICS PAS, 2003.
• 2. S. Ambroszkiewicz. Entish: A language for describing data processing in open distributed systems. Fundam. Inform., 60(1-4):41-66, 2004.
• 3. M. Bell. Introduction to Service-Oriented Modeling. John Wiley & Sons, 2008.
• 4. M. Blake, T. Weise, and S. Bleul. A graph-based approach to web services composition. In Proceedings of the Applications and the Internet Symposium, pages 183-189, 2005.
• 5. M. Blake, T. Weise, and S. Bleul. Wsc-2010: Web services composition and evaluation. In Proceedings of the Service-Oriented Computing and Applications (SOCA), 2010 IEEE International Conference, pages 1-4, 2010.
• 6. G. Canfora, M. D. Penta, R. Esposito, and M. L. Villani. An approach for qos aware service composition based on genetic algorithms. In Proceedings of the 2005 conference on Genetic and evolutionary computation, pages 1069-1075, 2005.
• 7. P. Chan and M. Luy. Dynamic web service composition: A new approach in building reliable web service. In Proceedings of the Advanced Information Networking and Applications Conference, pages 20-25, 2008.
• 8. W. Ching-Seh and I. Khoury. Tree-based search algorithm for web service composition in SaaS. In Proc. of the International Conference, Information Technology: New Generations (ITNG), pages 132-138, 2012.
• 9. D. Chiu, S. Deshpande, G. Agrawal, and R. Li. Cost and accuracy sensitive dynamic workflow composition over grid. In Proceedings of the 9th IEEE/ACM Int. Conf on Grid Computing (GRID’08), pages 9-16, 2008.
• 10. H. Chun-hua, C. Xiao-hong, and L. Xi-ming. Dynamic services selection algorithm in web services composition supporting cross-enterprises collaboration. Journal of Central South University of Technology, 16(2):32-45, 2009.
• 11. D. B. Claro, P. Albers, and J. Hao. Selecting web services optimal composition. In Proceedings of the 2nd Int. Workshop On Semantic And Dynamic Web Process, pages 32-45, 2005.
• 12. D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski, W. Penczek, A. Polrola, and J. Skaruz. Harmonics - a tool for composing medical services. In Proc. of ZEUS’12, pages 25-33, 2012.
• 13. D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski, W. Penczek, A. Polrola, and M. Szreter. Web services composition - from ontology to plan by query. Control & Cybernetics, 40(2):315-336, 2011.
• 14. D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski, W. Penczek, A. Polrola, M. Szreter, and A. Zbrzezny. Planics - a web service compositon toolset. Fundamenta Informaticae, 112(1):47-71, 2011.
• 15. S. Eduardo, F. P. Luis, and S. V. Marten. Supporting dynamic service composition at runtime based on end-user requirements. In Proceedings of the 1st Int. Workshop on User-generated Services (UGS2009), pages 464-471, 2009.
• 16. S. Eduardo, F. P. Luis, and S. V. Marten. Towards runtime discovery, selection and composition of semantic services. Computer Communications, 34(2):159- 168, 2011.
• 17. K. Fujii and T. Suda. Semantics-based context-aware dynamic service composition. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 4(2):1-31, 2009.
• 18. I. Garibay, A. S. Wu, and O. Garibay. Emergence of genomic self-similarity in location independent representations. Genetic Programming and Evolvable Machines, 7(1):55-80, 2006.
• 19. Z. Jang, C. Shang, Q. Liu, and C. Zhao. A dynamic web services composition algorithm based on the combination of ant colony algorithm and genetic algorithm. Journal of Computational Information Systems, 6(8):2617-2622, 2010.
• 20. D. Kalyanmoy. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186:311-338, 2000.
• 21. F. Lecue, M. D. Penta, R. Esposito, and M. Villani. Optimizing qos aware semantic web service composition. In Proceedings of the 8th International Semantic Web Conference, pages 375-391, 2009.
• 22. A. Niewiadomski, W. Penczek, and A. Polrola. SMT-based abstract planning in PlanICS ontology. ICS PAS Reports, 127:1-62, 2012.
• 23. J. A. Parejo, P. Fernandez, and A. R. Cortes. Qos-aware services composition using tabu search and hybrid genetic algorithms. Actas de los Talleres de las Jornadas de Ingenieria del Software y Bases de Datos, 2(1):55-66, 2008.
• 24. J. Peer. A pop-based replanning agent for automatic web service composition. Lecture Notes in Computer Science, 3532:189-198, 2005.
• 25. J. Rao and X. Su. A survey of automated web service composition methods. In Proc. of SWSWPC’04, pages 43-54, 2004.
• 26. T. Senivongse and N. Wongsawangpanich. Composing services of different granularity and varying QoS using genetic algorithm. In Proceedings of the World Congress on Engineering and Computer Science, 2011.
• 27. M. Sheshagiri, M. desJardins, and T. Finin. A planner for composing services described in daml-s. In Proceedings of the AAMAS Workshop on Web Services and Agent-based Engineering, pages 45-51, 2003.
• 28. A. S. Wu and R. Lindsay. A comparison of the fixed and floating building block representation in the genetic algorithm. Evolutionary Computation, 4(2):169- 193, 1996.
• 29. Z. Zheng, Y. Zhang, and M. Lyu. Distributed QoS evaluation for real-world web services. In Proc. of the Web Services (ICWS), 2010 IEEE International Conference on Web Services, pages 83-90, 2010.