Towards Automated Abstract Planning Based on a Genetic Algorithm

• Autorzy: Skaruz J. , Niewiadomski A. , Penczek W.

Warianty tytułu

PL

Zastosowanie algorytmu genetycznego do problemu planowania abstrakcyjnego

• Języki publikacji: EN

Abstrakty

EN

The paper presents a new approach based on nature inspired algorithms to an automated abstract planning problem, which is a part 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, which show that GA finds solutions for very large sets of service types in a reasonable time.

PL

Raport przedstawia nowe podejście do problemu planowania abstrakcyjnego za pomocą algorytmów genetycznych (AG). Problem planowania abstrakcyjnego polega na takiej kompozycji usług sieciowych, która spełnia zapytanie użytkownika. W raporcie pokazano sposób zastosowania AG do rozwiązania problemu planowania abstrakcyjnego oraz zaprezentowano wyniki eksperymentalne.

Słowa kluczowe

EN

genetic algorithms; web service composition; abstract planning

PL

algorytmy genetyczne; kompozycja usług sieciowych; planowanie abstrakcyjne

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2012
• Tom: Nr 1026
• Strony: 1--32
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Skaruz J.

• Instytut Informatyki UPH, ul. 3 Maja 54, 08-110 Siedlce, Polska

autor

Niewiadomski A.

• Instytut Informatyki UPH, ul. 3 Maja 54, 08-110 Siedlce, Polska

autor

Penczek W.

• Instytut Podstaw Informatyki PAN, ul. Jana Kazimierza 5, 01-248 Warszawa, Polska

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(l-4):41-66, 2004.
• [3] M. Bell. Introduction to Service-Oriented Modeling. John Wiley k, 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 Proceedings of the 2012 Ninth 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 International Conference 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 sendces 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 International Workshop On Semantic And Dynamic Web Process, pages 32-45, 2005.
• [12] D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski, W. Penczek, A. Półrola, and M. Szreter. Web sendces composition - from ontology to plan by query. Control & Cybernetics, 40(2):315-336, 2011.
• [13] D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski, W. Penczek, A. Półrola, M. Szreter, and A. Zbrzezny. Planics - a web service compositon toolset. Fundamenta Informaticae, 112(1):47-71, 2011.
• [14] D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski, W. Penczek, A. Półrola, and J. Skaruz. Harmonics - a tool for composing medical services. In Proceedings of the 4th Central-European Workshop on Services and their Composition ZEUS 2012, pages 25-33, 2012.
• [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 International 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] 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.
• [19] F. Lecue, M. D. Penta, R. Esposito, and M. Wlani. Optimizing qos-aware semantic web service composition. In Proceedings of the 8th International Semantic Web Conference, pages 375-391, 2009.
• [20] 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(l):55-66, 2008.
• [21] J. Peer. A pop-based replanning agent for automatic web service composition. Lecture Notes in Computer Science, 3532:189-198, 2005.
• [22] J. Rao and X. Su. A survey of automated web service composition methods. In Proc. of the 1st Int. Workshop on Semantic Web Ser-vices and Web Process Composition (SWSWPC 2004), pages 43-54, 2004.
• [23] 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.
• [24] M. Sheshagiri, M. des Jardins, 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.
• [25] Z. Zheng, Y. Zhang, and M. Lyu. Distributed QoS evaluation for real-world web services. In Proceedings of the Web Services (ICWS), 2010 IEEE International Conference on Web Services, pages 83-90, 2010.