The technology of mashine learning for a composite web service development

We analyze dynamic programming and machine learning algorithms (on example of Q-learning) used for automatic adaptive composition of web services based on service quality assessments, their input parameters and work specifics. Software implementation of these algorithms on sets of services of differ...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Grishanova, I.Yu., Rogushina, J.V.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут програмних систем НАН України 2025
Schlagworte:	web service composition of services machine learning UDC 681.3
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/669
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-669
record_format	ojs
resource_txt_mv	ppisoftskievua/30/fb9625b9826a3866c07a6f166fff2e30.pdf
spelling	pp_isofts_kiev_ua-article-6692025-04-16T13:57:48Z The technology of mashine learning for a composite web service development Технологія використання машинного навчання для побудови композиційного веб-сервісу Grishanova, I.Yu. Rogushina, J.V. web service; composition of services; machine learning UDC 681.3 веб-сервіс; композиція сервісів; машинне навчання УДК 681.3 We analyze dynamic programming and machine learning algorithms (on example of Q-learning) used for automatic adaptive composition of web services based on service quality assessments, their input parameters and work specifics. Software implementation of these algorithms on sets of services of different volumes is developed for comparison their performance parameters. We determine that the considered methods allow finding the optimal set of services only for composition with a predefined fixed-length route. This restriction causes a need to generalize the problem formulation for an arbitrary set of service classes in the composition route. On base of the performed analysis, we developed an algorithm that solves this problem of building a composite service with a route of arbitrary length (using the Q-Learning method), that has the best overall quality ratings. A software implementation of both this algorithm and other algorithms for solving this problem (genetic algorithm, greedy search, dynamic programming, SARSA, etc.) are developed to compare the speed of their work and the evaluation of the resulting composite service on data sets of different volumes.Prombles in programming 2024; 4: 3-13 Проаналізовано алгоритми динамічного програмування та машинного навчання (на прикладі Q-learning), що використовуються для автоматичної адаптивної композиції веб-сервісів на основі оцінок якості сервісів, їхні вхідні параметри та особливості роботи. Для порівняння параметрів роботи цих алгоритмів на наборах сервісів різного обсягу розроблено програмну реалізацію. Визначено, що розглянуті методи дозволяють знаходити оптимальний набір сервісів тільки для композиції з попередньо визначеним маршрутом фіксованої довжини. Тому виникає потреба узагальнити постановку задачі для довільного набору класів у маршруті композиції сервісів. На основі виконаного аналізу розроблено алгоритм розв’язання цієї задачі – побудови композитного сервісу з маршрутом довільної довжини методом Q-Learning, що має найкращі сумарні оцінки якості. Розроблено програмну реалізацію як цього алгоритму, так і інших алгоритмів розв’язання цієї задачі (генетичний алгоритм, жадібний пошук, динамічне програмування, SARSA), яка дозволила порівняти швидкість їх роботи та оцінки результуючого композитного сервісу на наборах даних різного обсягу.Prombles in programming 2024; 4: 3-13 Інститут програмних систем НАН України 2025-04-16 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/669 10.15407/pp2024.04.003 PROBLEMS IN PROGRAMMING; No 4 (2024); 3-13 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2024); 3-13 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2024); 3-13 1727-4907 10.15407/pp2024.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/669/721 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-04-16T13:57:48Z
collection	OJS
language	Ukrainian
topic	web service composition of services machine learning UDC 681.3
spellingShingle	web service composition of services machine learning UDC 681.3 Grishanova, I.Yu. Rogushina, J.V. The technology of mashine learning for a composite web service development
topic_facet	web service composition of services machine learning UDC 681.3 веб-сервіс композиція сервісів машинне навчання УДК 681.3
format	Article
author	Grishanova, I.Yu. Rogushina, J.V.
author_facet	Grishanova, I.Yu. Rogushina, J.V.
author_sort	Grishanova, I.Yu.
title	The technology of mashine learning for a composite web service development
title_short	The technology of mashine learning for a composite web service development
title_full	The technology of mashine learning for a composite web service development
title_fullStr	The technology of mashine learning for a composite web service development
title_full_unstemmed	The technology of mashine learning for a composite web service development
title_sort	technology of mashine learning for a composite web service development
title_alt	Технологія використання машинного навчання для побудови композиційного веб-сервісу
description	We analyze dynamic programming and machine learning algorithms (on example of Q-learning) used for automatic adaptive composition of web services based on service quality assessments, their input parameters and work specifics. Software implementation of these algorithms on sets of services of different volumes is developed for comparison their performance parameters. We determine that the considered methods allow finding the optimal set of services only for composition with a predefined fixed-length route. This restriction causes a need to generalize the problem formulation for an arbitrary set of service classes in the composition route. On base of the performed analysis, we developed an algorithm that solves this problem of building a composite service with a route of arbitrary length (using the Q-Learning method), that has the best overall quality ratings. A software implementation of both this algorithm and other algorithms for solving this problem (genetic algorithm, greedy search, dynamic programming, SARSA, etc.) are developed to compare the speed of their work and the evaluation of the resulting composite service on data sets of different volumes.Prombles in programming 2024; 4: 3-13
publisher	Інститут програмних систем НАН України
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/669
work_keys_str_mv	AT grishanovaiyu thetechnologyofmashinelearningforacompositewebservicedevelopment AT rogushinajv thetechnologyofmashinelearningforacompositewebservicedevelopment AT grishanovaiyu tehnologíâvikoristannâmašinnogonavčannâdlâpobudovikompozicíjnogovebservísu AT rogushinajv tehnologíâvikoristannâmašinnogonavčannâdlâpobudovikompozicíjnogovebservísu AT grishanovaiyu technologyofmashinelearningforacompositewebservicedevelopment AT rogushinajv technologyofmashinelearningforacompositewebservicedevelopment
first_indexed	2025-04-17T04:06:27Z
last_indexed	2025-04-17T04:06:27Z
_version_	1835328723120816128
fulltext	Штучний інтелект 3 УДК 681.3 http://doi.org/10.15407/pp2024.04.003 І. Гришанова, Ю. Рогушина ТЕХНОЛОГІЯ ВИКОРИСТАННЯ МАШИННОГО НАВЧАННЯ ДЛЯ ПОБУДОВИ КОМПОЗИЦІЙНОГО ВЕБ-СЕРВІСУ Проаналізовано алгоритми динамічного програмування та машинного навчання (на прикладі Q- learning), що використовуються для автоматичної адаптивної композиції веб-сервісів на основі оці- нок якості сервісів, їхні вхідні параметри та особливості роботи. Для порівняння параметрів роботи цих алгоритмів на наборах сервісів різного обсягу розроблено програмну реалізацію. Визначено, що розглянуті методи дозволяють знаходити оптимальний набір сервісів тільки для ком- позиції з попередньо визначеним маршрутом фіксованої довжини. Тому виникає потреба узагальни- ти постановку задачі для довільного набору класів у маршруті композиції сервісів. На основі викона- ного аналізу розроблено алгоритм розв’язання цієї задачі – побудови композитного сервісу з марш- рутом довільної довжини методом Q-Learning, що має найкращі сумарні оцінки якості. Розроблено програмну реалізацію як цього алгоритму, так і інших алгоритмів розв’язання цієї задачі (генетичний алгоритм, жадібний пошук, динамічне програмування, SARSA), яка дозволила порівняти швидкість їх роботи та оцінки результуючого композитного сервісу на наборах даних різного обсягу. Ключові слова: веб-сервіс, композиція сервісів, машинне навчання. I. Grishanova, J. Rogushina THE TECHNOLOGY OF MACHINE LEARNING FOR OF A COMPOSITE WEB SERVICE DEVELOPMENT We analyze dynamic programming and machine learning algorithms (on example of Q-learning) used for automatic adaptive composition of web services based on service quality assessments, their input parameters and work specifics. Software implementation of these algorithms on sets of services of different volumes is developed for comparison their performance parameters. We determine that the considered methods allow finding the optimal set of services only for composition with a predefined fixed-length route. This restriction causes a need to generalize the problem formulation for an arbitrary set of service classes in the composition route. On base of the performed analysis, we developed an algorithm that solves this problem of building a composite service with a route of arbitrary length (using the Q-Learning method), that has the best overall quality ratings. A software implementation of both this algorithm and other algorithms for solving this problem (genetic algorithm, greedy search, dynamic programming, SARSA, etc.) are developed to compare the speed of their work and the evaluation of the resulting composite service on data sets of different volumes. Keywords: web service, composition of services, machine learning. Вступ У сучасному світі інформаційних технологій веб-сервіси стали важливим інструментом для надання функціональ- ності через мережу. Веб-сервіси дозво- ляють розробникам об'єднувати окремі програмні компоненти для створення складних, функціональних та інтегрова- них рішень. Композитні веб-сервіси ві- діграють ключову роль у створенні та- ких рішень, дозволяючи використовува- ти кілька сервісів у межах єдиного ро- бочого процесу для досягнення постав- лених цілей. Композиція сервісів є активною сферою досліджень, яка застосовує розро- бки зі сфери машинного навчання та сема- нтичних технологій [1], для перетворення веб-середовища на розподілену обчислю- вальну платформу. Ця діяльність потребує створення та дослідження відповідних концепцій, моделей, алгоритмів, платформ та інструментів. © І.Ю. Гришанова, Ю.В. Рогушина, 2024 ISSN 1727-4907. Проблеми програмування. 2024. №4 Штучний інтелект 4 Процес композиції веб-сервісів є досить складним, особливо в умовах ди- намічного середовища, де сервіси можуть бути тимчасово недоступними або зміню- вати свої характеристики, зокрема, пара- метри якості обслуговування (QoS). Крім того, потрібно швидко адаптувати систему до нових умов, обирати оптимальні серві- си, а також оптимізувати композитний сервіс за допомогою параметрів QoS. Один із перспективних підходів до автоматичної адаптивної композиції веб- сервісів базується на використані машин- ного навчання, зокрема, навчання з підкрі- пленням, у якому агент навчається на ос- нові взаємодії із середовищем через отри- мання винагороди за свої дії. Використання одного з основних алгоритмів навчання з підкріпленням – Q- learning – дозволяє агенту поступово ви- вчати оптимальну стратегію вибору веб- сервісів для побудови композитних серві- сів: він дозволяє агенту коригувати свої рішення на основі зворотного зв'язку від середовища, не потребуючи повної моделі цього середовища. Машинне навчання і Reinforcement Learning Машинне навчання – це підгалузь штучного інтелекту, яка полягає у викори- станні алгоритмів і моделей, що дозволя- ють комп'ютерам здобувати знання з даних та знаходити рішення без чіткої програми. Один із важливих класів машинного нав- чання – навчання з підкріпленням (reinforcement learning, RL). Навчання з підкріпленням вирізня- ється тим, що агент взаємодіє із середови- щем у режимі реального часу, отримуючи зворотний зв'язок у вигляді винагороди або штрафу залежно від того, наскільки успішно його дія привела до досягнення поставленої мети. Однією з найбільш популярних те- хнік RL є група алгоритмів Q-learning, де агент будує таблицю Q-значень для різних станів і дій, поступово знаходячи оптима- льну стратегію (policy) через спроби і по- милки. На відміну від інших алгоритмів RL, Q-learning використовує прості Q- функції. Існує велика кількість підтипів Q- learning – з одним або кількома агентами, з різними типами взаємодії [2]. Завдяки тому, що агент постійно оновлює свої знання на основі отриманих винагород, він здатний адаптуватися до змін у середовищі, що робить його ефек- тивним інструментом для задач, де середо- вище є динамічним або частково відомим. У контексті веб-сервісів навчання з підкріпленням стає особливо важливим, оскільки середовище веб-сервісів є дина- мічним та складним, веб-сервіси можуть змінювати свої характеристики якості (Quality of service – QoS) [3], або ставати недоступними. Тому агент, що навчається, повинен вміти адаптуватися і швидко під- бирати нові рішення для композиції. Для побудови композиції сервісів потрібно спочатку визначити множину можливих маршрутів Flow (автоматизова- но або вручну, як робить більшість дослід- ників), що визначає послідовність вико- нання сервісів, а потім для таких маршру- тів визначити оптимальний набір сервісів. Навчання з підкріпленням дозволяє агенту самостійно знаходити оптимальні комбінації веб-сервісів на основі їхніх па- раметрів QoS, причому значення цих па- раметрів можуть змінюватися динамічно в процесі виконання сервісів. Підхід Q- learning надає можливість вирішувати ці завдання через поступове покращення стратегії складання композитного сервісу, який буде найбільш оптимальним за зада- ними параметрами. Задача композиції веб-сервісів Розглянемо задачу створення ком- позитного сервісу, взявши за основу прик- лад, наданий у роботі [4], поступово змі- нюючи вимоги для досягнення більш ада- птивних можливостей в композиції веб- сервісів. У контексті композиції веб-сервісів, композитний сервіс (КС) складається з на- бору окремих веб-сервісів, що виконують певні завдання, які об'єднуються для дося- гнення конкретної мети або виконання складної операції в певній послідовності. Штучний інтелект 5 Основними компонентами побудо- ви композитного сервісу є: 1. Атомарні вебсервіси: це окремі веб-сервіси, які можуть виконувати певні операції або надавати функці- ональність, наприклад, отримання даних про погоду, конвертацію одиниць виміру тощо. Кожен такий атомарний веб-сервіс має атрибути якості (QoS), такі як: Доступність (Availability): Частота успішних ви- кликів; Час виконання (Execution Time): Час, необхідний для вико- нання запиту; Пропускна здатність (Throughput): Кількість запитів, які можуть бути оброблені за одиницю часу. 2. Класи веб-сервісів: веб-сервіси можуть бути розподілені на класи, залежно від їхньої функціональнос- ті. Наприклад, один клас може міс- тити веб-сервіси для отримання да- них про погоду, інший – для конве- ртації одиниць виміру температури. КС складається з вибору веб- сервісів із кожного класу, які вико- нуються у певній послідовності. 3. Маршрут (Flow): КС має впоряд- ковану послідовність виконання атомарних веб-сервісів, де кожен із сервісів виконує свою задачу, а ви- хід одного сервісу може бути вхід- ним для іншого. Зокрема, перший сервіс отримує дані про температу- ру, а другий конвертує отриману температуру в іншу одиницю вимі- ру (наприклад, з Фаренгейта в Це- льсій). 4. Оптимізація за параметрами яко- сті: КС формується таким чином, щоб мінімізувати або максимізува- ти певні показники якості сервісу, як-от, мінімальний час виконання або максимальну доступність. Постановка задачі В роботі аналізуються існуючі рі- шення для побудови композитних сервісів, що дозволяють це робити для зафіксовано- го маршруту, який визначає послідовності виконання сервісів, і обрати оптимальний набір сервісів. Оптимальність оцінюється на основі характеристик якості атомарних сервісів, що входять до складу КС. Проблема полягає у тому, що біль- шість дослідників цієї задачі використо- вують різні форми опису маршруту та вхі- дних даних сервісів, які значно обмежують сферу застосування методів композиції, звужуючи її до фіксованого плану вико- нання сервісів. Це зменшує потенційну гнучкість сервіс-орієнтованої архітектури та потребує дослідження більш узагальне- них початкових умов. Такий підхід потре- бує також дослідження методів побудови маршрутів та критеріїв їх порівняння, але ці дослідження є поза рамками даної пуб- лікації. Щоб визначити можливості та не- доліки алгоритмів вибору атомарних сер- вісів для побудови композитного сервісу на основі маршруту, потрібно створити програмну реалізацію різних варіантів для алгоритмів композиції сервісів та порівня- ти швидкість і якість їх виконання та нав- чання. Це дозволить визначити, які з цих алгоритмів найбільш придатні для розв’язання задачі композиції у динаміч- ному середовищі і перспективні для пода- льшого удосконалення та які параметри впливають на їхню ефективність. Методи композиції веб-сервісів з використанням QoS Зараз існує велика кількість методів композиції веб-сервісів на основі QoS, що різняться часом виконання, структурою вхідних даних та кількістю ітерацій. Всі вони використовують модель Марковсько- го Процесу Прийняття Рішення - Markov Decision Process (MDP) для ухвалення рі- шення щодо оптимальності кожного з ок- ремих сервісів, що розглядаються як кан- дидати на виконання. Метод динамічного програмування Метод динамічного програмування [5] використовує алгоритми Policy Iteration, Value Iteration та Iterative Policy Evaluation [6]. Штучний інтелект 6 Програмна реалізація цих алгорит- мів1 показала, що алгоритм Policy Iteration найшвидше знаходить оптимальні страте- гії композиції веб-сервісів (з мінімальною кількістю ітерацій), тоді як Value Iteration та Iterative Policy Evaluation показують за- довільні результати, але потребують біль- ше часу. Алгоритм Q-learning з фіксованим маршрутом композитного сервісу Алгоритм Q-learning з фіксованим маршрутом композитного сервісу і без ди- намічної зміни класів сервісів та їх кількос- ті реалізує композицію веб-сервісів за до- помогою навчання RL, а саме – використо- вуючи Q-learning. Цей підхід може викори- стовувати ті ж самі вхідні дані, що й попе- редньо розглянуті динамічні методи, але з акцентом на дослідженні простору станів без попередньо відомої функції переходів. У програмній реалізації2 алгоритм Q-learning для вибору оптимальної послі- довності веб-сервісів використовує такі параметри QoS, як доступність (availability), час виконання (execution time) та пропускна здатність (throughput). КС формується через навчання агента на основі нагород, що відповідають атрибу- там QoS. Агент взаємодіє з середовищем і поступово вчиться вибирати послідовність дій (тобто, виклик веб-сервісів) таким чи- ном, щоб максимізувати сумарну винаго- роду. Наприклад, якщо агент вибирає сер- віс із високою доступністю, але з довгоча- сним виконанням, він отримає меншу ви- нагороду, ніж якщо він обере сервіс із зба- лансованими QoS-показниками. Тестування показало, що алгоритм навчання з підкріпленням потребує більше - - 1 https://github.com/TurtleIren/test- ML- methods/blob/3db8d92c050b5dc66a65914756a9 88b8aad51d1e/WSComposition-VI-PI-IPE- compare.py - 2 https://github.com/TurtleIren/test- ML- methods/blob/55315be65031ab0144ae6beec8c5 5ba01abb59ea/WSCompositionQ-learn-fixed- 1.py часу порівняно з динамічним програмуван- ням (Policy Iteration або Value Iteration), оскільки Q-learning досліджує простір станів через багаторазові ітерації. Q-таблиця після завершення навчання зберігає найкращі очі- кувані винагороди для кожної пари "стан- дія". Це дозволяє агенту обирати оптимальні дії на основі попереднього досвіду. З отриманих результатів можна зробити висновки: динамічні алгоритми (Policy Iteration, Value Iteration): працюють швидше, оскільки не вимагають дослі- дження простору станів та вимагають точ- ного знання функцій переходів між стана- ми, тоді як Q-learning більше відповідає середовищам з невідомими функціями пе- реходів та потребує більше ітерацій, оскі- льки досліджує простір станів експеримен- тальним шляхом. Таким чином, для про- блеми композиції веб-сервісів, якщо відомі функції переходів між станами, динамічні методи показують кращі результати як за часом, так і за ефективністю. Проте, Q- learning є надійним рішенням для випадків, де функції переходів невідомі або зміню- ються динамічно. Отримані нами висновки співпада- ють з результатами інших дослідників, але їхні підходи, а саме структури даних, не дозволяють знаходити оптимальний набір сервісів для композиції з попередньо не визначеним маршрутом. Тому виникає по- треба узагальнити постановку задачі для довільного набору класів у маршруті ком- позиції сервісів. Знаходженням оптимальної композиції сервісів для довільного маршруту Розглянемо використання Q- learning для композиції сервісів і знахо- дженням оптимальної композиції із зада- ними наборами груп вебсервісів і набором Flow композитного сервісу для довільного маршруту, який не зафіксовано явно до початку побудови композитного сервісу. У попередньому прикладі з викори- станням Q-learning для композиції веб- сервісів не було явного опису композитно- го сервісу або Flow, але він був заданий алгоритмічно. КС Flow має на увазі послі- Штучний інтелект 7 довність кількох окремих веб-сервісів, ко- жен з яких виконує частину загального за- вдання. У термінах коду Flow має бути представлене як послідовний вибір кількох дій (веб-сервісів) з різних класів, які спіль- но реалізують КС. Ціллю алгоритму є знаходження оптимального КС із набору існуючих Flow, використовуючи алгоритм Q-learning. Піс- ля тренування алгоритм повинен обирати оптимальний Flow на основі максимальної суми винагород для кожного композитного сервісу. Такий алгоритм має розширений набір вхідних даних: - Класи веб-сервісів (service_classes): кожен клас, як і у розглянутих вище алгоритмах, містить набір веб-сервісів, згрупованих за функціональними характеристиками, із явно заданими параметрами QoS. Класи явно визначені, наприклад, клас 1 містить "сервіс_1", "сервіс_2"; - Flow: до вхідних даних додається опис множини маршрутів Flow, який визначає припустимі послідовності класів веб-сервісів довільної скінченої довжини, які можуть бути використані для створення композитного сервісу. Наприклад, flows = [[1, 2], [1, 3, 4]] означає, що перший Flow складається з веб-сервісу з класу 1 і веб-сервісу з класу 2, а другий Flow – з послідовності веб-сервісів з класів 1, 3 і 4; - Параметри QoS: значення параметрів якості веб-сервісу (такі як доступність, час виконання та пропускна здатність). Для реалізації поставленої задачі пропонується алгоритм композиції веб- сервісів із використанням Q-learning, який може адаптуватися до різної кількості веб- сервісів у класах і Flow, і забезпечити гну- чкість у визначенні композиції (Flow) веб- сервісів. Відповідно до моделі MDP для ада- птивної композиції веб-сервісів, цей алго- ритм описується через наступні терміни: - Стан (state): кожен стан представляє часткову композицію веб-сервісів. - Дії (actions): вибір веб- сервісу з певного класу для додавання в поточний Flow. - Нагорода (reward): враховує атрибути QoS (доступність, час виконання, пропускна здатність). - Q-learning: алгоритм для навчання. Цей алгоритм дозволяє обробляти адаптивні дані, а саме: - кількість класів веб-сервісів може змінюватись; - Flow композитного сервісу може містити різну кількість веб-сервісів на різних етапах; - дані можуть генеруватись випадково для тестування різних сценаріїв. Програмна реалізація цього методу3 містить явно задані дані про веб-сервіси. У масиві service_data кожен веб-сервіс має фіксовані значення для атрибутів QoS: availability, exec_time, та throughput. Однак у процесі експлуатації ці значення можуть змінюватися, і відповідно до цих змін буде змінюватися значення винагороди і відпо- відно оптимальний Flow. Винагорода роз- раховується на основі значень QoS для об- раного веб-сервісу. Для кожного Flow ге- нерується КС. Метод find_optimal_flow() знаходить оптимальний Flow на основі су- ми винагород. Завдяки новій структурі з явним заданням Flow можна мати різну кількість веб-сервісів на різних етапах композиції. Крім того, можна змінювати кількість епізодів для навчання та інші па- раметри. Після навчання для кожного Flow виводиться набір сервісів, які були обрані - - 3 https://github.com/TurtleIren/test- ML- methods/blob/068c4f1fdc0970702b448398e7e1 3dad4988955e/WSCompositionQ-learn- adaptive.py Штучний інтелект 8 як оптимальні саме для цього маршруту. Наприклад: Згенерований композитний сервіс для Flow 1: ['сервіс_1', 'сервіс_3'] із загальною винагоро- дою: 41.233 Згенерований композитний сервіс для Flow 2: ['сервіс_1', 'сервіс_6', 'сервіс_8'] , із загальною винагородою: 48.924 Потім алгоритм обирає найкращий Flow, ґрунтуючись на сукупній винагороді за всі сервіси, що увійшли до отриманого Flow. Таким чином, програма генерує ком- позитний веб-сервіс із найкращою сумар- ною оцінкою якості атомарних сервісів. Найкращий Flow: 2, із загальною винагородою: 48.924 Програма призначена для вирішен- ня задачі композиції веб-сервісів із метою визначення оптимального композитного сервісу на основі наданих класів веб- сервісів і можливих Flow. КС формується на основі вибору сервісів з різних класів за допомогою підходу Q-learning, який нале- жить до методів навчання з підкріпленням (reinforcement learning). Програма здійснює навчання на ос- нові винагород (reward) для вибору веб- сервісів із різних класів так, щоб максимі- зувати загальну якість сервісів (QoS). Ос- новні модулі програми: 1. Ініціалізація (конструктор класу): Програма встановлює список станів та можливих дій для кожного Flow. Станами є різні етапи композитного Flow, а діями – вибраний веб-сервіс з відповідного класу. 2. Генерація станів: Метод generate_states() створює список можливих станів для кожного Flow. 3. Генерація дій: Метод generate_actions() генерує всі мож- ливі дії для кожного стану, де кож- на дія – це вибір одного веб-сервісу з певного класу. 4. Обчислення винагороди (QoS): Метод get_reward() обчислює винагороду за вибір конкретного веб- сервісу на основі його параметрів якості. Формула для винагороди враховує такі параметри, як доступність, час виконання і пропускну здатність: reward=(availability×К1)−(exe cutiontime×К2)+(throughput× К3) Значення коефіцієнтів важливості параметрів К1, К2 та К3 у формулі винагороди визначають вагу кожного параметра якості обслуговування (QoS): доступність (availability), час виконання (execution time) та пропускну здатність (throughput). Ці значення обираються емпірично або за вимогами користувача (наприклад, в даній програмній реалізації обрано К1=0.4, К2=0.4 та К3=0.2). Таким чином, веб-сервіси з високою доступністю та пропускною здатністю і мінімальним часом виконання отримують вищу винагороду. 5. Вибір дій (epsilon-greedy): Для ви- бору дій програма використовує еп- сілон-жадібну (epsilon-greedy) стра- тегію, яка дозволяє знаходити ба- ланс між дослідженням нових сер- вісів та використанням уже знайде- них оптимальних рішень: з імовір- ністю є програма обирає випадко- вий веб-сервіс для дослідження (exploration); з імовірністю 1-ϵ про- грама обирає дію з найвищим Q- значенням на основі поточної Q- таблиці. 6. Оновлення Q-таблиці: Метод update_q_table() використовує стан- дартну формулу Q-learning для оно- влення значень Q у таблиці на ос- нові поточної винагороди та очіку- ваної максимальної винагороди для наступного стану. 7. Навчання: Метод train() виконує на- вчання протягом заданої кількості епізодів (прикладів навчання). Під час навчання система проходить че- рез кожен Flow, вибираючи сервіси, обчислюючи винагороди та онов- люючи Q-таблицю. 8. Генерація композитного сервісу: Метод generate_composite_service() Штучний інтелект 9 генерує КС для кожного Flow на основі навченої Q-таблиці, обираю- чи сервіси з найвищим значенням Q у кожному стані. 9. Пошук оптимального Flow: Метод find_optimal_flow() обчислює зага- льну винагороду для кожного Flow та визначає найкращий КС на осно- ві максимальної суми винагород. Алгоритм адаптується до різних Flow, які представляють різні варіанти складання композитних сервісів із класів веб-сервісів. Підхід із використанням нав- чання з підкріпленням дозволяє знайти оп- тимальний КС, орієнтуючись на параметри якості сервісів (QoS), такі як доступність, час виконання та пропускна здатність. Визначення коефіцієнтів важливості винагороди Визначення коефіцієнтів важливос- ті винагороди може здійснюватися кілько- ма різними способами: Емпіричний підхід: Значення мо- жуть бути підібрані емпірично на основі попереднього досвіду або аналізу системи. Вони можуть бути скориговані після серії експериментів або тестувань для забезпе- чення правильного балансу між різними параметрами QoS. Вимоги системи або користувача: у різних системах або для різних сервісів деякі параметри можуть бути важливіши- ми за інші. Наприклад, у критичних систе- мах доступність може мати найбільший пріоритет, оскільки від неї залежить на- дійність сервісу. Інші системи можуть ви- магати мінімізації часу виконання або оп- тимізації пропускної здатності. Збалансований підхід: коефіцієнти також можуть бути підібрані для збалан- сованого впливу на загальну винагороду. Зокрема, використання однакових коефіці- єнтів для доступності та часу виконання може означати, що система хоче забезпе- чити стабільну роботу сервісів з хорошою доступністю і водночас підтримувати ко- роткий час відповіді. Менша вага для про- пускної здатності свідчить про те, що її важливість у цьому сценарії менша. Для визначення цих значень, необ- хідно здійснити наступне: - Аналіз потреб системи: Якщо деякі параметри QoS є важливі- шими для вашої системи, ці зна- чення можуть бути змінені від- повідно до вимог. Наприклад, якщо в задачі важливий час ви- конання, можна збільшити кое- фіцієнт для execution time. - Тестування і оптимізація: В процесі навчання з підкріплен- ням здійснюються серії тестів з різними значеннями коефіцієн- тів для визначення найкращих налаштувань, які забезпечують оптимальну роботу системи. - Моделювання користувацького досвіду: У деяких випадках ко- ристувачі можуть задати пріо- ритетність параметрів, виходячи з їхніх потреб. Наприклад, у хмарних сервісах для певних користувачів важливіша досту- пність, аніж час виконання, тоді як для інших навпаки. Порівняння алгоритмів композиції сервісів Крім Q-Learning, що розглянутий вище, для композиції сервісів можуть ви- користовуватися інші алгоритми. Розгля- немо найбільш поширені з них. Алгоритм жадібного пошуку (Greedy algorithm): на кожному кроці оби- рається той сервіс, який має максимальну винагороду на поточному етапі, без ураху- вання майбутніх винагород. Такий підхід не враховує довгострокові наслідки вибору на кожному етапі. Хоча він швидкий, але не гарантує глобально оптимальних ре- зультатів, оскільки може пропустити вигі- дніші дії у довгостроковій перспективі. Еволюційні алгоритми (Genetic Algorithms): можуть використовуватися для пошуку оптимальних рішень у просто- рі можливих Flow, але вони потребують значного обчислювального часу та надто залежні від налаштування параметрів; Динамічне програмування: складне завдання розбивається на підзадачі і вирі- Штучний інтелект 10 шує їх шляхом обчислення оптимальних результатів для менших підзадач. Алгоритм зберігає проміжні рішення для уникнення повторних обчислень. Він використовує таблицю для запам'ятовування оптималь- них рішень для кожного стану. Як і жадіб- ний алгоритм, динамічне програмування шукає оптимальні рішення, але на основі глобального аналізу. Цей підхід може бути використаний для знаходження оптималь- них рішень, але він також вимагає поперед- нього знання всіх можливих станів і дій. SARSA: метод навчання з підкріп- ленням, яке, на відміну від Q-learning, оно- влює значення Q-функції на основі вико- наної дії та отриманої наступної дії (Q- Learning використовує максимальне Q- значення для наступної дії). SARSA [7] ро- зглядає поточний стан, дію, винагороду, наступний стан і наступну дію, що робить його менш агресивним, але стабільнішим у змінних середовищах. Отож, SARSA є більш консервативним методом, оскільки оновлює Q-функцію відповідно до реаль- них дій, а не теоретично максимальних. Щоб порівняти Q-Learning із цими методами, проведемо їх тестування на од- накових наборах даних. Для проведення такого тестування ми змінюємо механізм отримання даних, а саме дані будуть бра- тися із згенерованих csv-файлів. Згенеруємо масив текстових даних для сценарію, де максимальна кількість сервісів у класі становить 100, максималь- на довжина Flow – 100 сервісів4. Кожен клас міститиме довільну кількість сервісів, а Flow складатимуться з довільних класів і сервісів. Крім того, для кожного сервісу згенеруємо параметри QoS. Ми викорис- товуємо наступні домовленості: - Класи вебсервісів: У кожного класу випадкова кількість серві- сів від 1 до 100. Для кожного сервісу генеруються параметри якості (QoS), такі як доступ- - - 4 https://github.com/TurtleIren/test- ML- methods/blob/ed6f17d668e9e98382424924664 579dfbc6a8860/generarte_100_services_100_fl ows.py ність, час виконання та пропус- кна здатність. - Flow: Випадковим чином гене- руються Flow з різних класів. Максимальна кількість класів у Flow – 100. Файл services.csv5 містить інформацію про всі сервіси та їхні параметри QoS, а flows.csv6 містить послідовності Flow для тестування. Рис. 1. Порівняння винагород знай- деного композитного сервісу різними ал- горитмами Рис. 2. Порівняння часу навчання побудови композитного сервісу. - - 5 https://github.com/TurtleIren/test- ML- methods/blob/2bb687e16be812e74c613e2b4b9 19e136ca44860/services_100.csv - 6 https://github.com/TurtleIren/test- ML- methods/blob/2bb687e16be812e74c613e2b4b9 19e136ca44860/flows_100.csv Штучний інтелект 11 Результати порівняльного тесту- вання7 показали наступне (Рис.1, Рис.2): 1. Q-Learning: Переваги: Добре підходить для се- редовищ, де система потребує багато дос- лідження і поступового покращення на ос- нові довгострокових вигод. Однак час ви- конання задовгий (50.57 секунд), а резуль- тат є субоптимальним (винагорода 1552.072), порівняно з іншими методами. Недоліки: Час виконання значно більший порівняно з жадібним алгоритмом і динамічним програмуванням. 2. SARSA: Переваги: Стабільніший у середо- вищах з динамічними змінами, оскільки враховує реальні дії. Час виконання (49.99 секунд) дещо менший, ніж у Q-Learning, а результат (винагорода 1574.544) дещо кращий. Недоліки: Час виконання також до- волі високий, і може не завжди знаходити глобально оптимальні рішення. 3. Жадібний алгоритм: Переваги: Найшвидший алгоритм (0.07192 секунд), оскільки він просто оби- рає найкращу дію на кожному кроці без глибоких розрахунків. Він досягає найви- щої винагороди (1992.832), що робить його ефективним для композиції веб-сервісів. Недоліки: Може пропустити опти- мальніші глобальні рішення через корот- козорість, якщо деякі рішення вимагають короткострокових втрат. 4. Динамічне програмування: Переваги: Показує другий найкра- щий результат після жадібного алгоритму, але також знаходить оптимальний Flow з найвищою винагородою (1992.832) і вико- нується дуже швидко (0.14223 секунд). Недоліки: Використовує більше пам'яті, оскільки зберігає всі проміжні ре- зультати, але це виправдано швидкістю та результатами. Нами також була спроба виконати поставлену задачу методом генетичного алгоритму. Цей метод працював довше на - - 7 https://github.com/TurtleIren/test- ML- methods/blob/30b8fd6ed80a44bc776693ac6a35 e6137ca3881c/WSComposition-compare.py невеликих наборах даних, однак на тесто- вому прикладі він не зміг виконати постав- лену задачу. Генетичний алгоритм часто потребує багатьох ітерацій, щоб зійтися до оптимального або навіть близького до оп- тимального рішення. Це призводить до по- вільного виконання порівняно з іншими методами. Генетичний алгоритм не завжди гарантує глобальне оптимальне рішення. Через випадкові процеси він може потрапи- ти у локальні оптимуми, і без належного налаштування може зупинитися на субоп- тимальних рішеннях. Генетичний алгоритм потребує налаштування багатьох гіперпа- раметрів: розмір популяції, ймовірність му- тації, ймовірність кросовера, умови зупин- ки тощо. Неправильне налаштування цих параметрів може значно вплинути на про- дуктивність і точність алгоритму. Випадко- ві операції мутації та кросовера можуть призвести до менш ефективного рішення або навіть віддалити від оптимального. В свою чергу це може призвести до нестабі- льних результатів між різними запускання- ми алгоритму. Отже, генетичний алгоритм має потенціал для знаходження глобальних оптимальних рішень, але для задач компо- зиції веб-сервісів на основі QoS з великими наборами даних він менш ефективний через високу обчислювальну складність і трива- лість конвергенції. Таким чином, можна зробити ви- сновок, що для швидкої композиції веб- сервісів на основі QoS найкраще викорис- товувати жадібний алгоритм або динаміч- не програмування, оскільки вони демон- струють відмінну швидкість виконання і знаходять глобально оптимальні рішення. Q-Learning та SARSA краще підходять для середовищ, де важливіша адаптація до ди- намічних змін і дослідження можливих рішень у довгостроковій перспективі, але вони працюють повільніше і можуть зна- ходити субоптимальні рішення. Висновки В роботі розглянуто застосування Q-learning для знаходження оптимального композитного сервісу з урахуванням даних QoS. Запропонована архітектура та струк- тура даних є більш гнучкими та дозволя- Штучний інтелект 12 ють підтримувати більше класів або типів сервісів і містять потенціал для подальшо- го удосконалення адаптивності процесу автоматизації побудови КС. Структура станів є складнішою, де кожен стан може відображати наявні вхідні та вихідні дані веб-сервісів, що дає змогу використовува- ти більший простір станів і більше можли- вих шляхів для композиції. Використання однієї спільної Q-таблиця для всіх станів і дій дозволяє гнучкіше масштабувати та обробляти складніші комбінації. Запропо- нована програмна реалізація дозволяє про- демонструвати переваги цього рішення. Відповідно до концепції відкритої науки щодо відтворюваності результатів, створе- ний програмний код є у відкритому досту- пі, і його можна отримати за посиланнями, наведеними у статті. Здійснене тестування рішення зада- чі композиції веб-сервісів різними метода- ми, з якого можна зробити висновок, що для швидкої композиції веб-сервісів на ос- нові QoS найкраще використовувати жаді- бний алгоритм або динамічне програму- вання, оскільки вони демонструють від- мінну швидкість виконання і знаходять глобально оптимальні рішення. Але ці ме- тоди не придатні для великих або невідо- мих просторів станів і потребують повного знання середовища. Методи Q-Learning та SARSA краще придатні для середовищ, де важливіше значення мають адаптація до динамічних змін і дослідження можливих рішень у довгостроковій перспективі, але ці методи працюють повільніше і можуть знаходити субоптимальні рішення. Тестування програми, що базується на використанні Q-learning, демонструє його ефективність у знаходженні оптима- льних композитних сервісів на різних тес- тових наборах даних. Найкращий компо- зитний сервіс обирається на основі макси- мізації суми винагород за параметрами якості сервісів QoS. Q-learning є більш гнучким порівняно з альтернативними під- ходами (такими як жадібний пошук та еволюційні алгоритми), оскільки він адап- тується до змін у середовищі та дозволяє оцінювати довгострокові наслідки вибору на кожному етапі. Наступним кроком у подальших до- слідженнях може бути автоматизація скла- дання маршрутів Flows для веб-сервісів з урахуванням змінних параметрів середо- вища. Автоматизація дозволить не тільки динамічно адаптувати сервіси під нові умо- ви, а й покращити якість і швидкість скла- дання оптимальних маршрутів на основі QoS. Крім того, доцільно буде дослідити можливості аналізу семантики складових сервісів та доповнити розглянуті вище під- ходи елементами інтелектуалізації описів сервісів на основі онтологій [8]. References 1. A. L. Lemos, F. Daniel, B. Benatallah, Web service composition: a survey of techniques and tools. ACM Computing Surveys (CSUR), 2015, 48(3), 1-41. 2. B. Jang, M. Kim, G. Harerimana, J. W. Kim, Q-learning algorithms: A comprehensive classification and applications. IEEE access, 2019б 7, 133653-133667. 3. M. Karakus, A. Durresi, Quality of service (QoS) in software defined networking (SDN): A survey. Journal of Network and Computer Applications, 2017, 80, 200-218. 4. V. Uc-Cetina, F. Moo-Mena, R. Hernandez- Ucan, Composition of web services using Markov decision processes and dynamic programming. The Scientific World Journal, 2015, (1), 545308. 5. S. Kalasapur, M. Kumar, B. A. Shirazi, Dynamic service composition in pervasive computing. IEEE Transactions on parallel and distributed systems, 2007, 18(7), 907-918. 6. A. Alla, M. Falcone, D. Kalise, An efficient policy iteration algorithm for dynamic programming equations. SIAM Journal on Scientific Computing, 2015, 37(1), A181- A200. 7. D. Zhao, H. Wang, K. Shao, Y. Zhu, (, December). Deep reinforcement learning with experience replay based on SARSA. In: 2016 IEEE symposium series on computational intelligence (SSCI) 2016, pp. 1-6. 8. J.V. Rogushina, A.Y. Gladun, V.V. Osadchiy, S.M. Pryima Ontological analysis into the Web Melitopol: Bogdan Hmelnitsky MDPU, 2015, 407 p.[in Ukrainian], Одержано: 25.10.2024 Внутрішня рецензія отримана: 02.11.2024 Зовнішня рецензія отримана: 05.11.2024 Штучний інтелект 13 Про авторів: Гришанова Ірина Юріївна, науковий співробітник, ORCID http://orcid.org/0000-0003-4999-6294. Рогушина Юлія Віталіївна, к.ф.-м.н., доцент, старший науковий співробітник, ORCID http://orcid.org/0000-0001-7958-2557. Місце роботи авторів: Інститут програмних систем НАН України, тел. (+38) 066 5501999, e-mail: ladamandraka2010@gmail.com

The technology of mashine learning for a composite web service development

Institution

Ähnliche Einträge