Concrete Planning in PlanICS Framework by Combining SMT with GEO and Simulated Annealing

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

Identyfikatory

DOI

10.3233/FI-2016-1409

• Konferencja: International Workshop on CONCURRENCY, SPECIFICATION, and PROGRAMMING (CS&P 2015), (24; 28-30.09.2015, Rzeszów, Poland).
• Języki publikacji: EN

Abstrakty

EN

The paper deals with the concrete planning problem – a stage of the web service composition in the PlanICS framework. We present several known and new methods of concrete planning including those based on Satisfiability Modulo Theories (SMT), Genetic Algorithm (GA), as well as methods combining SMT with GA and other nature-inspired algorithms such as Simulated Annealing (SA) and Generalised Extremal Optimization (GEO). The discussion of all the approaches is supported by the complexity analysis, extensive experimental results, and illustrated by a running example.

Słowa kluczowe

EN

web service composition; concrete planning; planICS; SMT; satisfiability modulo theories; genetic algorithm; hybrid algorithm; simulated annealing; GEO; generalised extremal optimization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 147, nr 2/3
• Strony: 289--313
• Opis fizyczny: Bibliogr. 34 poz., rys., tab., wykr.

Twórcy

autor

Niewiadomski A.

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

autor

Skaruz J.

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

autor

Switalski P.

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

autor

Penczek W.

• Institute of Computer Science, Polish Academy of Sciences, Jana Kazimierza 5, 01-248 Warsaw, Poland

Bibliografia

• [1] Erl T. Service-Oriented Architecture: Concepts, Technology, and Design. Upper Saddle River, NJ, USA: Prentice Hall PTR; 2005. ISBN: 10.0131858580, 13.978-0131858589.
• [2] Ambroszkiewicz S. Entish: A Language for Describing Data Processing in Open Distributed Systems. Fundam Inform. 2004;60(1-4):41–66. Available from: http://content.iospress.com/articles/fundamenta-informaticae/fi60-1-4-05.
• [3] Bell M. Introduction to Service-Oriented Modeling (SOA): Service Analysis, Design, and Architecture. John Wiley & Sons; 2008. ISBN: 978-0-470-14111-3.
• [4] Rao J, Su X. A Survey of Automated Web Service Composition Methods. In: Proc. of SWSWPC’04. vol. 3387 of LNCS. Springer; 2005. p. 43–54. doi:10.1007/978-3-540-30581-1_5.
• [5] Doliwa D, Horzelski W, Jarocki M, Niewiadomski A, Penczek W, Półrola A, et al. Harmon ICS - a tool for composing medical services. In: ZEUS; 2012;847:25–33. Available from: http://dblp.uni-trier.de/db/conf/zeus/zeus2012.html#DoliwaHJNPPS12.
• [6] Doliwa D, Horzelski W, Jarocki M, Niewiadomski A, Penczek W, Pólrola A, et al. PlanICS - a Web Service Composition Toolset. Fundam Inform. 2011;112(1):47–71. Available from: http://dx.doi.org/10.3233/FI-2011-578. doi:10.3233/FI-2011-578.
• [7] Niewiadomski A, Penczek W, Skaruz J, Szreter M, Jarocki M. SMT versus Genetic and OpenOpt Algorithms: Concrete Planning in the PlanICS Framework. Fundamenta Informaticae. 2014;135(4):451–466. Available from: http://dx.doi.org/10.3233/FI-2014-1134.
• [8] Skaruz J, Niewiadomski A, Penczek W. Hybrid Planning by Combining SMT and Simulated Annealing. In: Suraj Z, Czaja L, editors. Proceedings of the 24th International Workshop on Concurrency, Specification and Programming, Rzeszow, Poland, September 28-30, 2015, vol. 1492 of CEUR Workshop Proceedings. CEUR-WS.org; 2015. p. 173–176. Available from: http://ceur-ws.org/Vol-1492/Paper_41.pdf.
• [9] De Moura L, Bjorner N. Satisfiability Modulo Theories: Introduction and Applications. Commun ACM. 2011;54(9):69–77. Available from: http://doi.acm.org/10.1145/1995376.1995394. doi:10.1145/1995376.1995394.
• [10] Kirkpatrick S, Jr CG, Vecchi M. Optimization by simulated annealing. Sci. 1983;220:671–680. doi:10.1126/science.220.4598.671.
• [11] Sousa FL, Ramos FM, Galski RL, Muraoka I. Generalized Extremal Optimization: A New Meta-heuristic Inspired by a Model of Natural Evolution. Recent Developments in Biologically Inspired Computing. 2004;p. 41–60.
• [12] Skaruz J, Niewiadomski A, Penczek W. Combining SMT and Simulated Annealing into a Hybrid Planning Method. Studia Informatica. 2015;1-2(19):43–48. Available from: http://www.studiainformatica.ii.uph.edu.pl/jsp/publikacje.jsf?id_publikacji=19#.
• [13] Goldberg DE. Genetic Algorithms in Search, Optimization and Machine Learning. 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.; 1989. ISBN: 0201157675.
• [14] Niewiadomski A, Penczek W, Skaruz J. A Hybrid Approach to Web Service Composition Problem in the PlanICS Framework. In: Awan I, Younas M, Franch X, Quer C, editors. Mobile Web Information Systems. vol. 8640 of Lecture Notes in Computer Science. Springer International Publishing; 2014. p. 17–28. doi:10.1007/978-3-319-10359-4_2.
• [15] Niewiadomski A, Penczek W, Skaruz J. Combining Genetic Algorithm and SMT into Hybrid Approaches to Web Service Composition Problem. Int Journal On Advances in Software. 2014;7(3, 4):675–685. Available from: http://www.iariajournals.org/software.
• [16] Canfora G, Penta MD, Esposito R, Villani ML. An Approach for QoS-aware Service Composition based on Genetic Algorithms. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation; 2005. p. 1069–1075. doi:10.1145/1068009.1068189.
• [17] Jafarpour N, Khayyambashi M. QoS-aware Selection of Web Service Compositions using Harmony Search Algorithm. Journal of Digital Information Management. 2010;8:160–166. Available from: http://icact.org/upload/2010/0348/20100348_Abstract_B.pdf.
• [18] Arockiam L, Sasikaladevi N. Simulated Annealing Versus Genetic Based Service Selection Algorithms. International Journal of u- and e- Service, Science and Technology. 2012;5:35–49. Available from: http://www.sersc.org/journals/IJUNESST/vol5_no1/3.pdf.
• [19] Hu C, Chen X, Liang X. Dynamic services selection algorithm in Web services composition supporting cross-enterprises collaboration. Journal of Central South University of Technology. 2009;16:269–274. doi:10.1007/s11771-009-0046-y.
• [20] LY T, SC L. A hybrid metaheuristic for the quadratic assignment problem. Computational Optimization and Applications. 2005;34(1):85–113. doi:10.1007/s10589-005-3069-9.
• [21] J Chen ZG S Y Zhang, Yang LX. Feature-based initial population generation for the optimization of job shop problems. Journal of Zhejiang University SCIENCE C. 2010;11(10):767–777. doi:10.1631/jzus.C0910707.
• [22] Deng Y, Liu Y, Zhou D. An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP. Mathematical Problems in Engineering. 2015;(2015):ID 212794. Available from: http://dx.doi.org/10.1155/2015/212794.
• [23] Switalski P, Seredynski F. Multiprocessor Scheduling by Generalized Extremal Optimization. Journal of Scheduling. 2010;13:531–543. doi:10.1007/s10951-009-0141-9.
• [24] OWL 2 Web Ontology Language Document Overview; 2009. Available from: http://www.w3.org/TR/owl2-overwiew.
• [25] Martin D, Burstein M, Hobbs E, Lassila O, Mcdermott D, Mcilraith S, et al. OWL-S: Semantic Markup for Web Services; 2004. Available from: http://www.w3.org/Submission/OWL-S/.
• [26] Niewiadomski A, Penczek W. Towards SMT-based Abstract Planning in PlanICS Ontology. In: Proc. of KEOD 2013, International Conference on Knowledge Engineering and Ontology Development; 2013. p. 123–131. doi:10.5220/0004514901230131.
• [27] Web Services Business Process Execution Language vol 2.0; 2007. Available from: http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.html.
• [28] Skaruz J, Niewiadomski A, PenczekW. Evolutionary Algorithms for Abstract Planning. In: Wyrzykowski R, Dongarra J, Karczewski K, Wasniewski J, editors. PPAM (1). vol. 8384 of Lecture Notes in Computer Science. Springer; 2013. p. 392–401. doi:10.1007/978-3-642-55224-3_37.
• [29] Barrett C, Stump A, Tinelli C. The SMT-LIB Standard – Version 2.0. In: Proc. of the 8th Int. Workshop on Satisfiability Modulo Theories (SMT’10); 2010. Available from: http://www.cs.nyu.edu/~barrett/pubs/BST10.pdf.
• [30] Bak P. How nature works. New York: Copernicus: Springer-Verlag; 1996. ISBN: 978-0-387-98738-5, 978-1-4757-5426-1.
• [31] Bak P, Sneppen K. Punctuated equilibrium and criticality in a simple model of evolution. Physical Review Letters. 1993;71:4083–4086. Available from: http://dx.doi.org/10.1103/PhysRevLett.71.4083.
• [32] Bak P, Tang C, Wiesenfeld K. Self-Organized Criticality. Physical Review Letters. 1987;59:381–384. Available from: http://dx.doi.org/10.1103/PhysRevLett.59.381.
• [33] Papadimitriou CH. On the Complexity of Integer Programming. J ACM. 1981 Oct;28(4):765–768. doi:10.1145/322276.322287.
• [34] Ganesh V, Berezin S, Dill DL. Deciding Presburger Arithmetic by Model Checking and Comparisons with Other Methods. In: In Proceedings of FMCAD 02. LNCS 2517, Springer-Verlag; 2002. p. 171–186. doi:10.1007/3-540-36126-X_11.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).