Combining SMT and Simulated Annealing into a Hybrid Planning Method

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

Abstrakty

EN

We present a new approach to the concrete planning (CP) - a stage of theWeb service composition in the PlanICS framework. A new hybrid algorithm (HSA) based on a combination of Simulated Annealing (SA) with Satisfiability Modulo Theories (SMT) has been designed and implemented. The main idea of our hybrid solution is to use an SMT-based procedure in order to generate an initial individual and then improve it during subsequent iterations of SA. The experimental results show that HSA is superior to the other methods we have applied to the CP problem, including Genetic Algorithm, an SMT-based approach, and our previously developed hybrids.

Słowa kluczowe

EN

concrete planning; genetic algorithm; satisfiability modulo theories; simulated annealing; web service composition; planics

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2015
• Tom: Vol. 1-2(19)
• Strony: 43--48
• Opis fizyczny: Bibliogr. 16 poz., wykr.

Twórcy

autor

Skaruz J.

• Institute of Computer Science, Siedlce University of Natural Sciences and Humanities, Poland

autor

Niewiadomski A.

• Institute of Computer Science, Siedlce University of Natural Sciences and Humanities, Poland

autor

Penczek W.

• Institute of Computer Science, Siedlce University of Natural Sciences and Humanities, Poland
• Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland

Bibliografia

• 1. S. Ambroszkiewicz. Entish: A language for describing data processing in open distributed systems. Fundam. Inform., 60(1-4):41–66, 2003.
• 2. L. Arockiam and N. Sasikaladevi. Simulated annealing versus genetic based service selection algorithms. International Journal of u- and e- Service, Science and Technology, 5:35–49, 2012.
• 3. M. Bell. Introduction to Service-Oriented Modeling (SOA): Service Analysis, Design, and Architecture. John Wiley & Sons, 2008.
• 4. G. Canfora, M. Di 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.
• 5. L. M. de Moura and N. Bjørner. Z3: An efficient SMT solver. In Proc. of TACAS’08, volume 4963 of LNCS, pages 337–340. Springer-Verlag, 2008.
• 6. D. Doliwa et al. PlanICS - a web service compositon toolset. Fundam. Inform., 112(1):47–71, 2011.
• 7. C. Hu, X. Chen, and X. Liang. Dynamic services selection algorithm in web services composition supporting cross-enterprises collaboration. Journal of Central South University of Technology, 16:269–274, 2009.
• 8. N. Jafarpour and M. Khayyambashi. Qos-aware selection of web service compositions using harmony search algorithm. Journal of Digital Information Management, 8:160–166, 2010.
• 9. S. Kirkpatrick, C. Gelatt Jr, and M. Vecchi. Optimization by simulated annealing. Sci., 220:671–680, 1983.
• 10. A. Niewiadomski and W. Penczek. Towards SMT-based Abstract Planning in PlanICS Ontology. In Proc. of KEOD 2013 – International Conference on Knowledge Engineering and Ontology Development, pages 123–131, September 2013.
• 11. A. Niewiadomski,W. Penczek, and J. Skaruz. SMT vs genetic algorithms: Concrete planning in PlanICS framework. In CS&P, pages 309–321, 2013.
• 12. A. Niewiadomski,W. Penczek, and J. Skaruz. A hybrid approach to web service composition problem in the PlanICS framework. In Irfan Awan, Muhammad Younas, Xavier Franch, and Carme Quer, editors, Mobile Web Information Systems, volume 8640 of Lecture Notes in Computer Science, pages 17–28. Springer International Publishing, 2014.
• 13. A. Niewiadomski, W. Penczek, J. Skaruz, M. Szreter, and M. Jarocki. SMT versus Genetic and OpenOpt Algorithms: Concrete Planning in the PlanICS Framework. Fundamenta Informaticae, 135(4):451–466, 2014.
• 14. 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.
• 15. J. Rao and X. Su. A survey of automated web service composition methods. In Proc. of SWSWPC’04, volume 3387 of LNCS, pages 43–54. Springer, 2005.
• 16. J. Skaruz, A. Niewiadomski, and W. Penczek. Automated abstract planning with use of genetic algorithms. In GECCO (Companion), pages 129–130, 2013.