Metaheuristic methods for optimizing the quality of service of composite web services
With the advent of service-oriented architectures, it has become possible to register, invoke, and aggregate web services based on their identical quality of service attributes to create composite web services with added value that meet user needs. However, the rapid introduction of new web services...
Збережено в:
| Дата: | 2025 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2025
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/854 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-854 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/40/53274b581309f7f23e499837f16e6e40.pdf |
| spelling |
pp_isofts_kiev_ua-article-8542025-11-20T15:15:19Z Metaheuristic methods for optimizing the quality of service of composite web services Метаевристичні методи оптимізації якості обслуговування композитних вебсервісів Moroz, H.B. service-oriented computing; quality of service; web service composition; composite web service; metaheuristics UDC 004.41 cервісно-орієнтоване обчислення; якість обслуговування; композиція вебсервісів; композитний вебсервіс; метаевристика УДК 004.41 With the advent of service-oriented architectures, it has become possible to register, invoke, and aggregate web services based on their identical quality of service attributes to create composite web services with added value that meet user needs. However, the rapid introduction of new web services into a dynamic business environment can negatively affect their quality of service. Therefore, the question of how to capture, aggregate, and use information about the quality of service of individual web services to obtain an optimal end-to-end quality of service of a composite web service is currently one of the priority research areas in software engineering and service-oriented computing. This paper presents the basic theoretical information necessary to understand the importance, multifacetedness, and complexity of the problem of web service composition taking into account their quality of service, as well as a representative overview of the use of methods global optimization metaheuristic, which have been the dominant methods for solving this problem over the past two decades. The purpose of the work is to draw the attention of students and the scientific community to the current problems of web service composition that arise in the Internet of Things, cloud computing, social networks, mobile computer and smartphone technologies, etc., and to involve them in active participation in solving these problems.Problems in programming 2025; 3: 3-18 З появою сервіс-орієнтованих архітектур стало можливим реєструвати, викликати та об'єднувати вебсер віси за їхніми ідентичними атрибутами якості обслуговування для створення композитних вебсервісів з доданою вартістю, які відповідають потребам користувачів. Проте швидке впровадження нових веб сервісів у динамічне бізнес-середовище може негативно вплинути на їхню якість обслуговування. Тому питання про те, як залучити, агрегувати та використати інформацію про якість обслуговування окремих вебсервісів для отримання оптимальної наскрізної якості обслуговування композитного вебсервіса, є на разі одним із приорітетних напрямків дослідження в програмній інженерії та сервіс-орієнтованих обчис леннях. У цій роботі представлені базова теоретична інформація, необхідна для розуміння важливості, багатогранності та складності проблеми композиції вебсервісів з урахуванням їхньої якості обслугову вання, а також репрезентативний огляд використання метаевристичних методів глобальної оптимізації, які протягом останніх двох десятиліть є домінуючими методами вирішення даної проблеми. Мета роботи - привернути увагу студентів та наукової спільноти до актуальних проблем композиції вебсервісів, які виникають в Інтернеті речей, хмарних обчисленнях, соціальних мережах, технологіях мобільних комп’ютерів, смартфонів тощо, і залучити їх до активної участі в розв’язанні цих проблем.Problems in programming 2025; 3: 3-18 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-11-14 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/854 10.15407/pp2025.03.003 PROBLEMS IN PROGRAMMING; No 3 (2025); 3-18 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2025); 3-18 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2025); 3-18 1727-4907 10.15407/pp2025.03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/854/905 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-11-20T15:15:19Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
service-oriented computing quality of service web service composition composite web service metaheuristics UDC 004.41 |
| spellingShingle |
service-oriented computing quality of service web service composition composite web service metaheuristics UDC 004.41 Moroz, H.B. Metaheuristic methods for optimizing the quality of service of composite web services |
| topic_facet |
service-oriented computing quality of service web service composition composite web service metaheuristics UDC 004.41 cервісно-орієнтоване обчислення якість обслуговування композиція вебсервісів композитний вебсервіс метаевристика УДК 004.41 |
| format |
Article |
| author |
Moroz, H.B. |
| author_facet |
Moroz, H.B. |
| author_sort |
Moroz, H.B. |
| title |
Metaheuristic methods for optimizing the quality of service of composite web services |
| title_short |
Metaheuristic methods for optimizing the quality of service of composite web services |
| title_full |
Metaheuristic methods for optimizing the quality of service of composite web services |
| title_fullStr |
Metaheuristic methods for optimizing the quality of service of composite web services |
| title_full_unstemmed |
Metaheuristic methods for optimizing the quality of service of composite web services |
| title_sort |
metaheuristic methods for optimizing the quality of service of composite web services |
| title_alt |
Метаевристичні методи оптимізації якості обслуговування композитних вебсервісів |
| description |
With the advent of service-oriented architectures, it has become possible to register, invoke, and aggregate web services based on their identical quality of service attributes to create composite web services with added value that meet user needs. However, the rapid introduction of new web services into a dynamic business environment can negatively affect their quality of service. Therefore, the question of how to capture, aggregate, and use information about the quality of service of individual web services to obtain an optimal end-to-end quality of service of a composite web service is currently one of the priority research areas in software engineering and service-oriented computing. This paper presents the basic theoretical information necessary to understand the importance, multifacetedness, and complexity of the problem of web service composition taking into account their quality of service, as well as a representative overview of the use of methods global optimization metaheuristic, which have been the dominant methods for solving this problem over the past two decades. The purpose of the work is to draw the attention of students and the scientific community to the current problems of web service composition that arise in the Internet of Things, cloud computing, social networks, mobile computer and smartphone technologies, etc., and to involve them in active participation in solving these problems.Problems in programming 2025; 3: 3-18 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/854 |
| work_keys_str_mv |
AT morozhb metaheuristicmethodsforoptimizingthequalityofserviceofcompositewebservices AT morozhb metaevrističnímetodioptimízacííâkostíobslugovuvannâkompozitnihvebservísív |
| first_indexed |
2025-11-15T02:08:47Z |
| last_indexed |
2025-11-21T02:19:40Z |
| _version_ |
1850423536603103232 |
| fulltext |
Програмна інженерія - прикладні методи
3
УДК 004.41 http://doi.org/10.15407/pp2025.03.003
Г.Б. Мороз
МЕТАЕВРИСТИЧНІ МЕТОДИ ОПТИМІЗАЦІЇ ЯКОСТІ
ОБСЛУГОВУВАННЯ КОМПОЗИТНИХ ВЕБСЕРВІСІВ
З появою сервіс-орієнтованих архітектур стало можливим реєструвати, викликати та об'єднувати вебсер-
віси за їхніми ідентичними атрибутами якості обслуговування для створення композитних вебсервісів з
доданою вартістю, які відповідають потребам користувачів. Проте швидке впровадження нових веб-
сервісів у динамічне бізнес-середовище може негативно вплинути на їхню якість обслуговування. Тому
питання про те, як залучити, агрегувати та використати інформацію про якість обслуговування окремих
вебсервісів для отримання оптимальної наскрізної якості обслуговування композитного вебсервіса, є на-
разі одним із приорітетних напрямків дослідження в програмній інженерії та сервіс-орієнтованих обчис-
леннях. У цій роботі представлені базова теоретична інформація, необхідна для розуміння важливості,
багатогранності та складності проблеми композиції вебсервісів з урахуванням їхньої якості обслугову-
вання, а також репрезентативний огляд використання метаевристичних методів глобальної оптимізації,
які протягом останніх двох десятиліть є домінуючими методами вирішення даної проблеми. Мета роботи
- привернути увагу студентів та наукової спільноти до актуальних проблем композиції вебсервісів, які
виникають в Інтернеті речей, хмарних обчисленнях, соціальних мережах, технологіях мобільних
комп’ютерів, смартфонів тощо, і залучити їх до активної участі в розв’язанні цих проблем.
Ключові слова: Сервісно-орієнтоване обчислення, якість обслуговування, композиція вебсервісів, компо-
зитний вебсервіс, метаевристика.
H.B. Moroz
METAHEURISTIC METHODS FOR OPTIMIZING
THE QUALITY OF SERVICE OF COMPOSITE WEB SERVICES
With the advent of service-oriented architectures, it has become possible to register, invoke, and aggregate web
services based on their identical quality of service attributes to create composite web services with added value
that meet user needs. However, the rapid introduction of new web services into a dynamic business environment
can negatively affect their quality of service. Therefore, the question of how to capture, aggregate, and use
information about the quality of service of individual web services to obtain an optimal end-to-end quality of
service of a composite web service is currently one of the priority research areas in software engineering and
service-oriented computing. This paper presents the basic theoretical information necessary to understand the
importance, multifacetedness, and complexity of the problem of web service composition taking into account
their quality of service, as well as a representative overview of the use of methods global optimization
metaheuristic, which have been the dominant methods for solving this problem over the past two decades. The
purpose of the work is to draw the attention of students and the scientific community to the current problems of
web service composition that arise in the Internet of Things, cloud computing, social networks, mobile computer
and smartphone technologies, etc., and to involve them in active participation in solving these problems.
Key words: Service-oriented computing, quality of service, web service composition, composite web service,
metaheuristics.
Вступ
Із кінця ХХ століття сервіс-орієнто-
ване обчислення (SOC) є важливою обчис-
лювальною парадигмою, яка змінила спосіб
розробки та використання програмних до-
датків [1], а також стала підгрунтям для ево-
люції компонентно-орієнтованої інженерії
програмного забезпечення до більш прогре-
сивної сервіс-орієнтованої програмної ін-
женерії. У цій парадигмі вебсервіси (або
сервіси) розглядаються як фундаментальні
будівельні блоки для підтримки швидкої,
гнучкої та економічно ефективної розробки
розподілених програм у гетерогенних сере-
довищах [2]. Із появою сервіс-орієнтованих
архітектур (SОА) стало можливо сервіси
реєструвати, виявляти, викликати в розпо-
ділених середовищах, публікувати та ві-
льно об’єднувати між собою в один потуж-
© Г.Б. Мороз, 2025
ISSN 1727-4907. Проблеми програмування. 2025. №3
Програмна інженерія - прикладні методи
4
ніший, так званий, композитний вебсервіс
(СWS, composite web service). Об’єднання
(або композиція) сервісів є однією з ключо-
вих проблем для технології SOA та сервісів.
Воно дозволяє організаціям створювати
альянси, передавати функціональні можли-
вості аутсорсингу та надавати своїм клієн-
там комплексне обслуговування. З точки
зору бізнесу композиція вебсервісів (WSC,
web services composition) різко знижує вар-
тість і ризики створення нових бізнес-дода-
тків у тому сенсі, що існуючі бізнес-логіки
представлені як сервіси та можуть бути по-
вторно використані [3].
З роками популярність і викорис-
тання сервісів експоненційно зростає.
Швидке впровадження соціальних мереж,
хмарних обчислень, мереж речей тощо
тільки сприяє стрімкому збільшенняю дос-
тупних в Інтернеті сервісів. Щоденно кліє-
нти по всьому світу генерують міл’ярди за-
питів на різноманітні сервіси, а тисячі про-
вайдерів (постачальників, розробників)
пропонують нові або модифіковані існуючі
сервіси. Серед величезної кількості наяв-
них нині сервісів від різних провайдерів со-
тні, а то і тисячі можуть мати однакову або
дуже схожу функціональність. За такого ро-
звитку подій першорядного значення, як
для провайдерів, так і для клієнтів, набуває
якість обслуговування сервісів (QoS, quality
of service) або, у більш вузькому сенсі, не-
функціональні властивості сервісів. З од-
ного боку, диференціація сервісів відносно
QoS надає можливість провайдерам відріз-
няти свої сервіси від інших функціонально
подібних сервісів, а, отже, QoS стає ключо-
вим інструментом конкуренції провайдерів.
З іншого боку, клієнти, оцінюючи QoS сер-
вісів з однаковою функціональностю, отри-
мують можливість визначити, який сервіс, а
отже і провайдер, їх найбільше влаштовує.
Проте в реальному житті це зробити незав-
жди просто, оскільки QoS, що надається
клієнту, залежить від багатьох як внутріш-
ніх, так і зовнішних факторів. Зокрема, та-
ких як обчислювальні ресурси провайдера,
продуктивність самого сервісу, хостингової
платформи, географічне положення корис-
тувача, швидкість підключення до Інтер-
нету між користувачами та сервісами тощо
[2]. На цьому фоні критичною для техноло-
гії SОА та сервісів стає проблема композиції
вебсервісів з урахуванням QoS (QWSC),
суть якої зводиться до пошуку серед вели-
чезної кількості можливих СWS з однако-
вою функціональністю такого, наскрізна
QoS якого буде оптимальною (з точки зору
клієнта) [4]. На ранніх етапах розвитку
SOC, коли кількість провайдерів і розміри
репозиторію сервісів були незначні, про-
блему QWSС можна було вирішити за до-
помогою точних та евристичних методів
[5,6]. Ефективність цих методів, які погано
масштабвалисяся, почала швидко зменшу-
ватись при стрімкому зростанні як кількості
сервісів, так і їх користивачів. Наразі для
проблеми QWSС характерні багатовимір-
ність, нелінійність цільових функцій, конф-
ліктуючі атрибути QoS, величезний пошу-
ковий простір та значний об’єм вхідних да-
них тощо. Отже ця проблема є NP-
складною і для свого вирішення потребує
нових підходів та методів. Наразі серед най-
більш успішних розглядаються метаеврис-
тичні методи глобальної оптимізації. На ві-
дміну від точних методів оптимізації, мета-
евристика не гарантує оптимальність отри-
маних рішень. У порівнянні з методами
наближення вони не забезпечують доказову
точність розв’язку та доказові межі часу ви-
конання. Проте вони здатні забезпечити
“практично прийнятні” рішення протягом
задовільної тривалості часу.
У статті подано базові знання, необхідні
для розуміння особливостей проблеми
QWSC, а також представлені сучасні мета-
евристичні методи її вирішення. Завер-
шується робота висновком.
Передмова
В даному розділі надається коротка
базова інформація, яка допоможе краще
зрозуміти особливості та складність про-
блеми QWSC.
Сервіси та їхні властивості. Сер-
віси — це самоописні, самодостатні, слабко
пов’язані, незалежні від платформи та бага-
торазово використовувані компоненти про-
грамного забезпечення, призначені для під-
тримки взаємодії між машинами в мережі
[3,4]. Вони описуються, публікуються, ви-
являються та викликаються в розподілених
середовищах за допомогою набору станда-
Програмна інженерія - прикладні методи
5
ртів на основі XML (розширювана мова ро-
змітки), включаючи WSDL (мова опису сер-
вісів), SOAP (простий протокол доступу до
об’єктів) і UDDI (універсальне виявлення
та інтеграція описів).
SAO, яка підпримує життєвий цикл
сервісів, складається з трьох основних ком-
понентів: провайдера (постачальника), ре-
єстру сервісів та замовника (користувача,
клієнта). На Рис.1 представлена абстрактна
модель такої архітектури та взаємозв'язки
між її компонентами. Провайдер розробляє
сервіс, генерує його опис (WSDL) і
публікує його в загальнодоступному
реєстрі сервісів (UDDI), роблячи його до-
ступним для виклику. Реєстр містить інфор-
мацію для ідентифікації сервісу, включа-
ючи URL-адресу, яка вказує на розташу-
вання файлу WSDL, а також технічні відо-
мості про сервіс. Клієнт отримує інформа-
цію про сервіс з реєстру і, якщо вона його
влаштовує, використовує відповідний файл
WSDL для взаємодії з сервісом через пові-
домлення SOAP [4].
Виклик /Прив'язка
(WSDL, SOAP)
Виявлення
(WSDL, UDDI)
Замовник
(клієнт) Провайдер
Реєстр
сервісів Опублікування
(WSDL, UDDI)
Рис.1. Модель SOA, що використовується
сервісами (адаптовано з [2])
Сервіс вважається повністю пред-
ставлений, якщо добре описані його як фу-
нкціональні, так і нефункціональні власти-
вості, виражені через певні атрибути QoS
[3]. Функціональні властивості описують
операційну поведінку сервісів, тобто, яка
інформація потрібна для успішного ви-
клику сервісу та яка інформація буде пове-
рнена після його виконання. З формальної
точки зору функціональність сервісу як чо-
рного ящика можна розглядати як певне ві-
дображення набору вхідних даних І в на-
бір вихідних даних О, (:I→O). Оскільки
користувача передусім цікавить, що робить
сервіс, то пари (І, О) здебільшого достатньо
для розуміння цього. В більшісті літератур-
них джерел дотримуються саме такого пог-
ляду на функціональність сервісів.
Нефункціональні властивості серві-
сів або атрибути QoS є обмеженнями, ви-
значеними над їхньою функціональністю і
використовуються для ранжування сервісів,
які мають однакову функціональність. Існує
безліч атрибутів QoS для оцінки сервісів з
точки зору їхніх нефункціональних власти-
востей. Проте є декілька атрибутів QoS, які
вважаються типовими та поширеними для
переважної більшості сервісів від різних
провайдерів [4,7]. Це, зокрема:
вартість, C(Sі), що описує, скільки коштує
виконання i-им сервісом завдання Si;
час відповіді, T(Si) - тобто час, протягом
якого можна отримати відповідь від i-го
сервісу після відправлення запиту на за-
вдання Si. Значення цієї метрики фактично
залежать не тільки від QoS цільового сер-
вісу, а й від якості проміжної мережі;
надійність, R(Si), що описує, наскільки
ймовірно, що i-ий сервіс дасть очікувану ві-
дповідь на завдання Si;
доступність, A(Si), що описує, наскільки
вірогідно отримати доступ до i-го сервіса
при необхідності виконання завдання Si;
репутація, Reр(Si), що описує, наскільки
завдання i-го сервісу Si , користується пере-
вагою або довірою серед користувачів.
Композиція сервісів з урахуван-
ням QoS. Композиція сервісів — це керова-
ний QoS процес об’єднання (агрегації) кіль-
кох існуючих в мережі Інтернет сервісів в
новий CWS з доданою вартістю, який має
необхідні клієнту функціональність та на-
скрізну QoS. Наразі найбільш поширеним
підходом до (напів)автоматичної WSC є
підхід на основі робочого бізнес-процесу
[4,5]. Підгрунтям цього підходу є подіб-
ність абстрактного CWS до абстрактного
бізнес-процесу, який являє собою набір за-
гальних сервісів (службових) завдань із ви-
значеними залежностями між потоком уп-
равління та потоком даних.
На Рис. 2 показано два ключові
етапи життєвого циклу WSC, а саме етапи
Виявлення та Вибору сервісів. На етапі Ви-
явлення для кожного і-го абстрактного сер-
віса з функціональністю Оі із множини всіх
Програмна інженерія - прикладні методи
6
доступних в Інтернет сервісів створюється
клас конкретних сервісів-кандидатів, які та-
кож мають функціональністю Оі, але відріз-
нятися між собою за QoS. Вхідними даними
етапу Вибір є набір класів сервісів-кандита-
тів, отриманих на попередньому етапі.
Вибираючи з кожного класу по одному
сервісу-кандитату, отримаємо множину
всіх екземплярів СWS, серед яких необ-
хідно знайти такий, що найкраще
відповідає заявленим вимогам та обмежен-
ням користовача до наскрізної QoS.
Реєстр
сервісів
1
2
3
1
2
1 1
2
3
1
2
Вибір
сервісів
Виявлення
сервісів
Абстрактний
бізнес процeс
Абстрактні сервіси
1
3 1
2 2
Композитний сервіс
Класи конкретних
сервісів-кандитатів
Рис.2. Ключові етапи життєвого циклу
композиції сервісу (адаптовано з [4]).
Функції агрегації. В існуючих мо-
вах моделювання бізнес-процесу, таких як
BPEL-WS, OWL-S тощо виділяються чо-
тири структури управління завданнями, а
саме: послідовна, паралельна, розгалужена
та циклічна [8]. Ці ж структури є базовими
і для абстрактних CWS (Рис. 3). При послі-
довній структурі завдання Si виконуються в
послідовному порядку, і=1,…,m. В парале-
льній структурі всі паралельні завдання ви-
конуються одночасно. Перехід до завдання
за межами структури відбувається після за-
вершення всіх паралельних завдань. В роз-
галуженій структурі з імовірністю рі вико-
нується завдання Si і після його завершення
відбувається перехід до завдання за межами
структури, pi=1. В структурі циклу сер-
віси, створені за її допомогою, виконуються
неодноразово, доки не буде виконано певну
умову, наприклад, кількість циклів l.
SmS1
S1
Sm
a) послідовна b) паралельна
S1
Sm
pm
p1
l
SmS1
c) розгалужена d) циклічна
Рис. 3. Базові структури абстрактних CWS
В Табл. 1 наведені функції агрегації для ба-
зових структур абстрактних CWS і основ-
них атрибутів QoS [4].
Таблиця 1.
Функції агрегації для QoS, де l — кількість циклів
Атрибут
QoS
Cтруктури абстрактних композитних сервісів
Послідовна Паралельна Розгалужена Циклічна
Час відповіді ∑ 𝑇𝑇(𝑚𝑚
𝑖𝑖=1 ) 𝑚𝑚𝑚𝑚𝑚𝑚𝑖𝑖=1𝑚𝑚 𝑇𝑇(𝑆𝑆𝑖𝑖) ∑ 𝑇𝑇(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)𝑝𝑝𝑖𝑖 𝑙𝑙∑ 𝑇𝑇(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)
Надійність ∏ 𝑅𝑅(𝑆𝑆𝑖𝑖)
𝑚𝑚
𝑖𝑖=1
∏ 𝑅𝑅(𝑆𝑆𝑖𝑖)
𝑚𝑚
𝑖𝑖=1
∑ 𝑅𝑅(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)𝑝𝑝𝑖𝑖 ∏ 𝑅𝑅(𝑆𝑆𝑖𝑖)
𝑚𝑚
𝑖𝑖=1
Доступність ∏ 𝐴𝐴(𝑆𝑆𝑖𝑖)
𝑚𝑚
𝑖𝑖=1
∏ 𝐴𝐴(𝑆𝑆𝑖𝑖)
𝑚𝑚
𝑖𝑖=1
∑ 𝐴𝐴(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)𝑝𝑝𝑖𝑖 ∏ 𝐴𝐴(𝑆𝑆𝑖𝑖)
𝑚𝑚
𝑖𝑖=1
Вартість ∑ 𝐶𝐶(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖) ∑ 𝐶𝐶(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖) ∑ 𝐶𝐶(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)𝑝𝑝𝑖𝑖 𝑙𝑙∑ 𝐶𝐶(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)
Pепутація 1
𝑚𝑚∑ 𝑅𝑅𝑅𝑅𝑝𝑝(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)
1
𝑚𝑚∑ 𝑅𝑅𝑅𝑅𝑝𝑝(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖) ∑ 𝑃𝑃(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)𝑝𝑝𝑖𝑖 𝑙𝑙∑ 𝑃𝑃(
𝑚𝑚
𝑖𝑖=1
𝑆𝑆𝑖𝑖)
Програмна інженерія - прикладні методи
7
Формальна постановка задачі QWSC.
Нехай
m – кількість абстрактних сервісів в абстра-
ктному композитному сервісі;
k – кількість атрибутів QoS;
Gi – упорядкована множина конкретних
сервісів-кандидатів, що мають функціона-
льність і-го абстрактного сервіса, 1 і m;
nі – кількість сервісів в класі Gi;
хi – порядковий номер сервісу в класі Gi,
(1 хi nі);
vj(хi) – значення j-го атрибута хi-го конкрет-
ного сервісу із Gi, 1 j k, 1 1 хi nі);
𝑚𝑚 – множина всіх можливих CWS
X = [x1, x2,…, xm], 1 xi ni, i=1,…,m;
𝑓𝑓𝑗𝑗(𝑋𝑋) = 𝑓𝑓𝑗𝑗(𝑣𝑣𝑗𝑗(𝑥𝑥1), … , 𝑣𝑣𝑗𝑗(𝑥𝑥𝑚𝑚) ) - агрегатна
функція j-го атрибута QoS CWS, 1 j k;
Необхідно знайти такий вектор
𝑋𝑋∗ = [𝑥𝑥1
∗, 𝑥𝑥2
∗, … , 𝑥𝑥𝑚𝑚
∗ ], 1 xi nі,
який оптимізує вектор агрегатних функцій
𝐹𝐹(𝑋𝑋) = [𝑓𝑓1(𝑋𝑋), 𝑓𝑓2(𝑋𝑋), … , 𝑓𝑓𝑘𝑘(𝑋𝑋)]
У разі наявності обмежень
gi(X) ≤ 0, i = 1,..., r, r k;
hj(X) 0, j = 0,..., k-r,
де X*m– (суб)оптимальний розв’язок
(тобто прийнятний композитний сервіс).
Метаевристичні методи
оптимізації QoS композитних
сервісів
Одними з перших метаевристик, ви-
користаних для вирішення проблеми
QWSC, були метаевристики на основі трає-
кторії, такі як табу пошук [9] та моделю-
вання відпалу [10]. Проте згодом вони пос-
тупились потужнішим метаевристикам на
основі популяції, зокрема, алгоритмам ро-
йового інтелекту, еволюційним алгоритмам
тощо. Оскільки проблема QWSC має тенде-
нцію ускладнюватися, то з часом вияви-
лось, що застосування будь-якого одного
алгоритму оптимізації далеко не завжди
приводить до успіху. Теоретичним підгрун-
тям для розуміння подібних емпіричних фа-
ктів є відома NFL-теорема Волперта - Мак-
реді про відсутність безкоштовного обіду,
яка стверджує, що не існує універсального
алгоритму оптимізації, який може розв’язу-
вати всі проблеми краще за інші алгоритми.
Одним із очевидних шляхів подолання не-
гативних наслідків NFL-теореми і підви-
щення ефективності вирішення завдань
глобального оптимізації є розробка гібрид-
них алгоритмів, які об'єднують різні або од-
накові алгоритми, але з різними значеннями
вільних параметрів. Мотивацією гібридиза-
ції є можливість подолання недоліків окре-
мих алгоритмів, не втрачаючи їхніх переваг,
що робить гібридні алгоритми ефективні-
шими за автономні.
Еволюційні алгоритми
Зазвичай під термінами «еволюційні
алгоритми» або «еволюційне обчислення»
розуміють велику групу алгоритмів до якої
входять, зокрема, генетичні алгоритми
(genetic algorithm, GA), еволюційні страте-
гії, еволюційнe та генетичне програмування
(genetic programing, GP), диференціальна
еволюція тощо. Вони мають загальну кон-
цептуальну базу моделювання еволюції
окремих структур і відрізняються за спосо-
бом формулювання задачі, процесами
відбору і використання операторів репро-
дукції (відтворення).
Генетичні алгоритми. Canfora G.
та ін. [11] першими застосували генетичний
алгоритм для композиції сервісу з ураху-
ванням QoS. Ними був описаний підхід для
швидкої, грубозернистої WSC на основі
GA, який виявився більш маштабованим,
однак повільнішим за цілочисельне програ-
мування. Мета підходу полягала в забезпе-
ченні швидкого способу знаходження субо-
птимального композитного сервісу. В ро-
боті [12] запропоновано GA, що характери-
зується схемою кодування хромосом спеці-
альною матрицею відношень і обробкою рі-
зноманітності популяції з моделюванням
відпалу. Матриця відношень має здатність
одночасно представляти перепланування
композитного сервісу, циклічні шляхи та
багато сценаріїв сервіса, таких як імовірні-
Програмна інженерія - прикладні методи
8
сний виклик, паралельний виклик, послідо-
вна активація тощо. Zhang С., Ma Y. [13]
для вибору сервісів із глобальними обме-
женнями QoS запропонували швидкий кон-
вергентний GA з розширеною політикою
початкової популяції та еволюційною полі-
тикою на основі схеми кодування матриці
відношень. А також динамічний GA, пред-
ставлений політикою оцінки динамічної
еволюції на основі схеми кодування генома
матриці відношень, що забезпечує кращі
плани CWS. Vanrompay Y. та ін. [14] для
мобільних систем, що складаються з кіль-
кох вузлів, запропонували GA для ефектив-
ного пошуку майже оптимального щодо за-
гальних атрибутів QoS складу композит-
ного сервісу та його розгортанні на наборі
підключених вузлів таким чином, щоб роз-
поділ відповідав заданим обмеженням яко-
сті обслуговування (QoS) та мінімізував ва-
ртість зв'язку між вузлами.
Gong X.R. та ін. в [15] представили GA ком-
позиції сервісу, який підтримує глобальне
оптимальне та динамічне перепланування.
Алгоритм використовує схему кодування
матриці позицій, щоб одночасно виражати
всі композитні шляхи та інформацію про
перепланування QoS. Jiang Z.Y. та ін. [16]
запропонували модель оптимізації запитів і
відповідний GA на основі багатоатрибут-
ного агрегування QoS різних сервісів для
індивідуальності та ефективності в оцінках.
Модель налаштовує QoS з глобальними об-
меженнями та уподобаннями користувачів,
динамічною схемою рейтингу та багаторів-
невою відповідністю. Авторами роботи
[17] для вирішення проблеми QWSC по-пе-
рше, представлено GA відновлення з міні-
мальними конфліктами, в якому окремі
особини можуть бути швидко виправлені за
допомогою евристики впорядкування зна-
чень, коли вони порушують обмеження мі-
жсервісних залежностей і конфліктів. По-
друге, для вирішення проблеми розподі-
лення CWS запропоновано GA на основі
штрафів, оскільки розумне розподілення
композитних сервісів між паралельними
серверами може збільшити пропускну зда-
тність. У GA вбудований швидкий локаль-
ний оптимізатор та ранговий відбір із еліта-
рністю. Cao J. та ін. [18] запропонували
удосконалений GA для оптимізації якості
моделі процесу обслуговування сервісів,
яка спочатку перетворюється на дерево
структури процесу для розрахунку якості, а
потім GA використовується для уточнення
процесу обслуговування. В роботі [19]
представлено інтегровану структуру запи-
тів до сервісів, яка включає в себе модель
запитів до сервісів і двофазову стратегію
оптимізації. Модель запиту визначає серві-
сні спільноти для організації великого та
неоднорідного простору обслуговування.
Двофазова стратегія оптимізації з жадібним
алгоритмом і GA здатна «спільно розви-
вати» кілька можливих планів виконання
одночасно. Klein A. та ін. [20] описали ме-
режевий підхід до композиції сервісів у
хмарі, що складається з мережевої моделі
розрахунку QoS та алгоритму вибору, який
ґрунтується на GA. Ukor R. та ін. в [21]
представили задачу оптимізації вибору сер-
вісу з поняттям маркерів запиту та трьома
підходами (цілочисельне програмування,
евристичний пошук по дереву та GA) для
вирішення цієї задачі. Автори роботи [22],
розглядаючи одночасно функціональні та
нефункціональні вимоги, запропонували
семантичний, заснований на GA, підхід до
автоматичної композиції сервісів. У роботі
[23] запропоновано коеволюційний GA для
створення сервісу на основі QoS, який пов-
ністю враховує індивідуальні відносини
між популяціями.
Багатоцільові GA. Claro D.B. та ін.
[24] для вибору сервісів для оптимальної
композиції реалізували багатоцільовий ево-
люційний підхід, заснований на NSGA-II
(генетичний алгоритм недомінованого сор-
тування), який ідентифікує набір оптималь-
них рішень за Парето без введення ранжи-
рування серед різних параметрів QoS. В
[25] також використовано структуру NSGA-
II для композиції сервісів з урахуванням
QoS. Водночас для полегшення ухвалення
рішення споживачам сервісів надавали кі-
лька різних можливих розв’язків. Hashmi K.
та ін. [26] на основі NSGA-II представили
сервіс переговорів, який використовується
як споживачем, так і сервісом провайдера
для проведення переговорів щодо залежних
параметрів QoS. Авторами [27] запропоно-
вано алгоритм глобальної багатоцільової
оптимізації WSSPEA2. Суть його полягає в
Програмна інженерія - прикладні методи
9
тому, що задача вибору вебсервісів на ос-
нові QoS трансформується в багатоцільову
задачу оптимізації композиції сервісів з об-
меженнями QoS. Силовий еволюційний ал-
горитм Парето (SPEA2) використовується
для отримання набору оптимальних за Па-
рето рішень за допомогою одночасної опти-
мізації ряду цільових функцій, і користувачі
можуть вибрати одне з цих рішень за своїми
перевагами. В [28] представлено алгоритм
GODSS (глобальний оптимальний вибір ди-
намічних сервісів) для вирішення динаміч-
ного вибору сервісів із глобальними опти-
мальними QoS у композиції сервісів. Суть
алгоритму полягає в тому, що задача дина-
мічного вибору сервісу з глобальними оп-
тимальними QoS трансформується в бага-
тоцільову оптимізацію композиції сервісів з
обмеженнями QoS. Wang J. та ін. [29] запро-
понували багатоцільовий GA для оптималь-
ного вибору сервісів на основі QoS, врахо-
вуючи такі обмеження у процесі вибору
сервісу, як структура управління в плані
композиції, взаємозв’язок між конкретними
сервісами та компроміс між кількома атри-
бутами QoS. В [30] запропоновано багато-
цільовий GA, на ефективність якого не
впливає еволюціонуючий набір рішень на
кожній ітерації. Набір оптимальних рішень
за Парето будується за правилом псевдобі-
нарного дерева. Потім оптимальні за Па-
рето рішення упорядковуються, і придат-
ність кожного оптимального рішення за Па-
рето визначається подібністю окремих рі-
шень. Wagner F. та ін. [31] описали розши-
рену операцію відновлення та надали бага-
тоцільовий алгоритм оптимізації, який ви-
користовує базові знання для виявлення на-
дійних оптимізованих за QoS виборів серві-
сів у відкритому сервісному середовищі.
Алгоритм враховує вартість потенційних
збоїв та ранжує рішення на основі переваг
ризику особи, яка ухвалює рішення.
Ramirez A. та ін. [32] досліджували придат-
ність еволюційного алгоритму з багатьма
цілями для вирішення проблеми зв’язу-
вання сервісів на основі реального тесту з
дев’ятьма атрибутами QoS.
Гібридні GA. Ma X. та ін. [33] впе-
рше обговорили обмеження методу простих
адитивних ваг через те, що ці ваги не мають
фізичного значення і їх важко встановити.
Потім пропонується новий ефективний об-
числювальний підхід, лінійне фізичне про-
грамування у співпраці з GA для вибору
сервісу, керованого якістю. Liang W. та та
ін. [34] запропонували гібридний алгоритм
для композиції сервісів, який включає GA
та грубу теорію множин. Цей алгоритм
може: (i) вирішувати проблеми, які можна
розкласти на функціональні вимоги, і (ii)
покращувати продуктивність GA, виявляти
нездійснені рішення та винятки шляхом
зменшення діапазону домену початкової
популяції та обмеженого перетину, викори-
стовуючи грубу теорію множин. Liu Z. та ін.
[35], базуючись на декомпозиції глобальних
обмежень QoS, запропонували метод дина-
мічної композиції, який складається з трьох
етапів: (i) глобальні обмеження QoS розкла-
даються на локальні обмеження культур-
ного GA; (ii) правила визначення QoS ви-
значають значення QoS сервісів-кандида-
тів; (iii) найкращі сервіси, що задовольня-
ють локальні обмеження, вибираються для
кожного завдання протягом часу виконання.
Que Y. та ін. [36] базуючись на ідеї деком-
позиції QoS, реалізували гібридне рішення
з інформаційною ентальпією, успадкова-
ною від штучної імунної системи, для вирі-
шення проблеми детермінованої ймовірно-
сті оператора GA, яка призводить до про-
блеми передчасної конвергенції. В [37] ро-
зроблено керований кластером GA шляхом
впровадження k-середніх у процес генера-
ції початкової популяції. Крім того, Jatoth C.
та ін. [38] представили oптимальну компо-
зицію хмарного сервісу з використанням
GA на основі адаптивної еволюції генотипу,
що має справу з кількома атрибутами QoS і
забезпечує рішення, які задовольняють ба-
ланс параметрів QoS і обмежень підклю-
чення композиції сервісу
Генетичне програмування. В ро-
боті [39] запропоновано алгоритм GP ком-
позиції сервісів, який може об’єднувати
сервіси, використовуючи різні керуючі
структури, генерувати композиції відпо-
відно до контекстно-вільної граматики та
явно керувати оновленням атрибутів. А та-
кож мінімізує кількість сервісів і шукає
композиції з мінімальним шляхом вико-
нання. Авторами роботи [40] запропоно-
вано алгоритм адаптивного GP, спрямова-
Програмна інженерія - прикладні методи
10
ний на створення бажаних виходів на ос-
нові доступних вхідних даних, а також на
забезпечення того, щоб композитний сервіс
мав оптимальне значення QoS. В роботі [41]
представлено підхід на основі GP до компо-
зиції розподіленого сервісу з урахуванням
QoS. Вплив каналів зв'язку на атрибути QoS
вибраних сервісів розглядається явно. Щоб
впоратися з розподіленим середовищем
сервісів, була прийнята мережева система
координат для оцінки часу, витраченого на
зв’язок між сервісами, а також між серві-
сами та кінцевими користувачами.
Гібридне GP — це особливе за-
стосування GA, яке широко використо-
вується у повністю автоматизованій стра-
тегії композиції з графовим поданням. У
повністю автоматизованій композиції аб-
страктні робочі процеси створюють
вихідно-вхідні зв’язки між сервісами, де
оператор алгоритму використовується в
еволюційному процесі для вибору сервісу
композиції без обмежень. В [42] пропо-
нується гібридний підхід до складання
сервісів, який поєднує GP та випадковий
жадібний пошук. Жадібний алгоритм вико-
ристовується для генерації допустимих та
локально оптимізованих особин для GP та
для виконання операцій мутації під час ге-
нетичного програмування. Yu Y. та ін. [43]
пропонують гібридний підхід, який об’єд-
нує використання GP та табу-пошуку для
композиції сервісу з інтенсивним викорис-
танням даних з урахуванням QoS. Ефек-
тивність запропонованого підходу
оцінюється за допомогою загальнодоступ-
них наборів даних. У статті [44] запропоно-
вано комбінацію GP та випадкового жадіб-
ного пошуку для композиції сервісу.
Жадібний алгоритм використовується для
створення дійсних і локально оптимізова-
них особин для заповнення початкового по-
коління для GP та для виконання операцій
мутації під час генетичного програмування.
Алгоритми ройового інтелекту
Це парасольковий термін для вели-
кої групи алгоритмів, до якої, зокрема, вхо-
дять алгоритми оптимізації рою частинок
(рarticle swarm optimisation, PSO), оптимі-
зації мурашиної колонії (аnt colony
optimisation, ACO), оптимізації штучної
бджолиної колонії, (artificial bee colony al-
gorithm, ABC) тощо.
Оптимізація рою частинок. Wang
W. та ін. [45] для вирішення проблеми
QWSC запропонували вдосконалений алго-
ритм оптимізації рою частинок (iPSOA) із
стратегіями нерівномірної мутації та адап-
тивного коригування ваги для покращення
швидкості конвергенції на глобальному та
локальному рівнях відповідно. А також
представлено модель пулу сервісів, яка до-
помогає користувачам зберегти більше ком-
позитних планів за один процес вибору та
ефективний алгоритм побудови пулу серві-
сів, заснований на вдосконаленій оптиміза-
ції дискретного рою частинок (IDPSO). Вод-
ночас стратегія нерівномірної мутації була
введена в глобальну найкращу частинку в
IDPSO для підвищення якості складних пла-
нів у пулі сервісів. Wang S. та ін. [46] запро-
понували швидкий PSO у середовищі хмар-
них обчислень для створення хмарних CWS.
Спочатку оператор горизонту повинен вида-
лити надлишкові кандидати CWS, а потім
PSO вибрає CWS із решти кандидатів для
створення композитних сервісів. В роботі
[47] розроблено PSO для полегшення дина-
мічного вибору сервісу, в якому запропоно-
вано три типи операторів швидкості та одне
рівняння еволюції положення. Критерій no-
hope/re-hope гарантує різноманітність PSO
та покращує можливість глобального по-
шуку. Wang L. та ін. [48] розробили автома-
тичний алгоритм композиції сервісів, засно-
ваний на глобальній оптимізації QoS та хао-
тичному PSO. Водночас модель вибору сер-
вісів із глобальною оптимізацією QoS пере-
творюється на задачу багатоцільової оптимі-
зації. В роботі [49], для реалізації ефектив-
ної інтеграції та уніфікованого управління
ресурсами логістичного центру запропону-
вано метод вираження логістичних ресурсів
та інкапсуляції сервісів, щоб знайти найкра-
щий конкретний сервіс, прив’язаний до кож-
ного відповідного абстрактного сервісу. Ав-
тори [50] запропонували групування PSO на
основі переваг користувача у виборі сервісу.
Алгоритм не тільки досягає балансу між
швидкістю конвергенції та розмаїттям роїв,
а й дозволяє максимально задовольнити ко-
ристувачів за рахунок стратегій угруповання
частинок, розвитку різних кластерів окремо,
Програмна інженерія - прикладні методи
11
своєчасного оновлення кожного кластера та
використання нечітких обмежень для вира-
ження уподобань користувача. В роботі [51]
об'єднано PSO з aлгоритмом присвоєння
Мункреса для композиції сервісу, який відрі-
зняється від споріднених робіт двома аспек-
тами: (i) для вирішення проблеми оптиміза-
ції вводяться два метаевристичні методи, за-
сновані на PSO та (ii) одночасно обробля-
ються декілька запитів робочого процесу.
Багатоцільовa PSO. Cao J. та ін. [52] запро-
понували багатоцільовий алгоритм вибору
сервісів на основі PSO, який моделює про-
блему вибору сервісів як обмежену оптимі-
заційну задачу з кількома цілями. Сервіси в
кожному наборі суб-сервісів спочатку сор-
туються відповідно до концепції доміну-
вання Парето. Потім створюється новий на-
бір суб-сервісів, розмір якого набагато мен-
ший за початковий, і, нарешті, виводиться
оптимальний набір за Парето. Автори ро-
боти [53] перетворили задачу ранжиру-
вання top-k у задачу багатокритеріального
програмування, коли переваги користувачів
розглядаються разом із запитами користу-
вачів. Потім пропонується вдосконалений
дискретний PSO, щоб зведені рейтинги за-
довольняли як запити користувачів, так і
їхні переваги. Guha T. та ін. [54] запропо-
нувано та порівняно два алгоритми вибору
сервісів в Grid: багатоцільовий алгоритм
оптимізації рою частинок з кількома цілями
з використанням методу відстаней скупче-
ності (MOPSO-CD) до алгоритму встанов-
лення відповідності на основі задоволення
обмежень (CS-MM). Fan X. [55] побудував
ефективний багатоцільовий алгоритм PSO з
кількома обмеженнями за допомогою ніше-
вої технології для вирішення проблеми ви-
бору та композиції персоналізованого сер-
вісу. Авторами [56], враховуючи кореляції
між ресурсними сервісами, запропоновано
багатоцільовий PSO для вирішення про-
блеми вибору та композиції ресурсів мно-
жинної мережі. Основні особливості: (i) він
поєднує техніку недомінованого сорту-
вання для вибору найкращих глобальної та
локальної позицій; (ii) формула оновлення
частинок динамічно змінюється для досяг-
нення компромісу між глобальним дослі-
дженням та локальною експлуатацією; і (iii)
для підтримки різноманітності популяції
застосовуються оператори обрізання попу-
ляції на основі перестановок і цілей.
Гібриднa PSO — це одна із найвідоміших
груп алгоритмів ройового інтелекту, яка у
існуючій літературі згадується як друга за
частотою гібридна метаевристика. Xu X. та
ін. [57] для збільшення ефективністі по-
шуку оптимального композитного сервіса
запропонували гібридний алгоритм оптимі-
зації хаосу (PS-CTPSO), який є поєднанням
PSO та стратегії хижацького пошуку. Liu Y.
та ін. [58] для вирішення проблеми компо-
зиції сервісів пропонують гібридний алго-
ритм оптимізації рою квантових частинок
(HQPSO), який поєднує PSO з деякими
принципами квантової механіки. Yin H. та
ін. [59] для покращення різноманітності
роїв впроваджують генетичні оператори в
PSO. Крім того, Wang S. та ін. [60] запропо-
нували покращити ефективність PSO за до-
помогою методів горизонту для видалення
надмірностей у сховищі сервісів. У цьому ж
контексті Hossain M. S. та ін. [61] для
розв’язання проблеми отримання опти-
мальної композиції за мінімальний час із
численних наборів динамічних сервісів, за-
пропонували гібридний алгоритм, який
поєднує PSO і кластеризацію k-середніх.
Він працює паралельно за допомогою
MapReduce на платформі Hadoop. Це важ-
ливо для обробки великих обсягів
різнорідних даних і сервісів із різних дже-
рел у мобільному середовищі. Chifu V. та
ін. [62] застосували метод кластеризації да-
них для визначення щільної області у прос-
торі пошуку для створення надійної можли-
вості пошуку для знаходження глобальних
оптимумів та уникнення локальних пасток.
Gharbi М. та ін. [63] запропонували метод
під назвою реляційний аналіз концепції
(RCA) для зменшення простору пошуку.
Евристичні методи, такі як алгоритм кло-
нального відбору [64] і гармонійний пошук
[65], об’єднані з оператором горизонту та
стратегією хижацького пошуку [57], для
підвищення можливостей пошуку тра-
диційного PSO. В [66] реалізувано по-
вністю автоматичну композицію сервісів за
допомогою алгоритму планування. Гібрид-
ний PSO з метаевристиками, включаючи
алгоритм штучної імунної системи [67] і
гармонійний пошук [65], запропонований
Програмна інженерія - прикладні методи
12
для гарантування тонкого балансу між дос-
лідженням та експлуатацією. Haytamy S. та
ін. [68] розробили двоступінчасту гібридну
модель, в якій вихідні дані рекурентної ней-
ронної мережі LSTM подавалися в PSO для
перетворення даних QoS у послідовну ін-
формацію. Крім того, Hosseinzadeh M. та ін.
[69] розробили гібридний PSO зі штучною
нейронною мережею для покращення пара-
метрів QoS. Sun та ін. [70] запропонували
підхід швидкого вибору сервісів, який пов-
ністю використовує PSO з адаптивними
стрибками та нечітким логічним керуван-
ням для адаптивного розкладання глобаль-
них обмежень QoS на локальні з адаптив-
ним рівнем якості. В [71] для проблеми
QWSC запропоновано гібридний PSO з
принципом клонального відбору та кіль-
кома корисними стратегіями. Удосконалена
локальна стратегія «кращий перший» пред-
ставлена для досягнення однакових впливів
на локальну придатність компонентного за-
вдання та функцію придатності композит-
ного сервісу, коли замінюється інший сер-
віс-кандидат. У роботі [72] запропоновано
новий алгоритм кооперативної еволюції на
основі PSO та SA, який успадковує швидку
конвергенцію PSO та глобальну конверген-
цію SA, а також долає недоліки схильності
до захоплення локального оптимуму PSO та
повільної конвергенції SA. Багатоцільова
PSO розроблена також для багатоцільової
композиції сервісів із глобальною оптиміза-
цією QoS. У роботі [73] представлена мо-
дель вибору сервісів на основі PSO для ви-
значення оптимальної комбінації сервісів
шляхом оцінки атрибутів QoS для динаміч-
ної програми електронного бізнесу. Модель
реалізована багатоагентною системою, де
агенти можуть представляти автономних
запитувачів сервісів, постачальників серві-
сів та інші функції в програмах електроного
бізнесу. Fethallah H. та ін. [74] для про-
блеми QWSC запропонували реактивне ба-
гатоагентне рішення на основі локальної
версії PSO, у якій кожна група має повну сі-
тчасту топологію, яка більш несприйнят-
лива до локальних оптимумів, ніж глоба-
льна версія.
Оптимізація мурашиної колонії.
Zheng X. в [75] представив алгоритм вибору
сервісу з урахуванням QoS, до якого вклю-
чена модель ступеня задоволеності корис-
тувача для грід-сервісів і розширений ACO
з новим правилом мурашиного клонування.
Авторами роботи [76] запропоновано мо-
дель мінімізації вартості композиції серві-
сів для додатків з інтенсивним об’ємом да-
них і розроблено відповідний алгоритм
ACO для її реалізації. Сервіси навколиш-
нього медіа в середовищі моніторингу розу-
много будинку повинні бути повсюдними,
адаптивними та надійними щодо доступу та
доставки. Hossain M. та ін. [77] запропоно-
вано структуру вибору сервісів у “розум-
них” середовищах, яка використовує потен-
ціал підходу до вибору сервісів на основі
мурашок, враховуючи динамічність уподо-
бань та задоволеності користувачів. А це є
ключовим фактором для вибору медіа-сер-
вісів, щоб знайти найкращий спосіб вибору
відповідних медіа-сервісів. Це також дозво-
ляє різним категоріям мешканців отриму-
вати доступ до різноманітних медіа-серві-
сів таким чином, що їхній досвід оптимізу-
ється з огляду на навколишнє середовище.
В роботі [78] запропоновано натхненний
мурашками метод вибору семантичного
сервісу, який використовує граф композиції
та багатокритеріальну функцію для визна-
чення оптимального рішення композиції
відповідно до вподобань користувача щодо
QoS та семантичної якості. Щоб підвищити
ефективність і точність процесу виявлення
сервісів, вони організували набір доступ-
них сервісів зі схожою функціональністю в
кластери сервісів. Wang R. та ін. [79] у по-
єднанні з механізмом позитивного зворот-
ного зв’язку ACO спочатку проаналізували
проблему вибору сервісів із базовим прин-
ципом ACO, а потім перетворили проблему
вибору сервісів з урахуванням QoS у про-
блему найкоротшого шляху. Нарешті вони
вказали кроки вирішення проблеми вибору
сервісу на основі ACO та порівняли ефек-
тивність алгоритму за різними парамет-
рами. В роботі [80] представлено жадібний
алгоритм під назвою Greedy-WSC і алго-
ритм на основі оптимізації колонії мурашок
під назвою ACO-WSC, які намагаються ви-
брати можливі комбінації хмар і використо-
вувати мінімальну кількість хмар. Eкспери-
ментальні результати показують, що запро-
понований метод оптимізації мурашиної
Програмна інженерія - прикладні методи
13
колонії може ефективно та результативно
знаходити хмарні комбінації з мінімальною
кількістю хмар.
Багатоцільовa ACO. Fang Q. та ін. [81] за-
стосували багатоцільовий алгоритм опти-
мізації мурашиної колонії для вирішення
проблеми вибору динамічного сервісу. Мо-
дель вибору сервісу з глобальними обме-
женнями QoS перетворюється на задачу
багатоцільової оптимізації з обмеженнями
користувача. Zhang W. та ін. [82] запропо-
нували багатоцільове моделювання вибору
оптимального шляху для композиції дина-
мічних сервісів на основі QoS. Представ-
лено стратегію декомпозиції композитного
сервісу із загальною структурою потоку на
паралельні шляхи виконання, яка є масш-
табованою для підтримки композиції дуже
складних сервісів. Dahan F. та ін. в [83] ро-
зробили алгоритм оптимізації колонії літа-
ючих мурашок під назвою FACO (Flying
Ant Colony Optimization), який модифікує
ACO для вирішення проблеми композиції
сервісу з урахуванням QoS. Вони також
представили алгоритм EFACO (Enhanced
Flying Ant Colony Optimization), який зме-
ншує складність обчислень FACO, запро-
вадивши в ньому три вдосконалення 1)
щоб уникнути проблеми з часом вико-
нання, EFACO обмежує процес польоту
лише тоді, коли якість рішення покращу-
ється; 2) щоб уникнути сканування всіх су-
сідніх вузлів застосували метод вибору су-
сідніх вузлів; 3) ввели третю модифікацію,
яка перетворила алгоритм на мультиферо-
монний алгоритм.
Гібриднa ACO. Yang Z. та ін. [84] ро-
зробили гібридний ACO, за допомогою
якого використовувався генетичний алго-
ритм для вибору критичного параметра
для ACO. Генетичний алгоритм відомий
своїм гнучким, надійним механізмом по-
шуку, але інколи він страждає від відсут-
ності надійних можливостей пошуку гло-
бальних оптимумів. З іншого боку, ACO
має репутацію глобального пошукового ал-
горитму, але страждає від повільної кон-
вергенції, особливо великомасштабних
проблем. Отже, Yang Y. та ін. [85] запропо-
нували гібридизацію, де алгоритм мура-
шиної колонії служив зачатком генетичної
операції. Liu Z.-Z. та ін. [86] інтегрували
систему мурахи в алгоритм культури. По-
гана стагнація була описана як підводне
каміння ACO в існуючій літературі. Alayed
H. та ін. [87] покращили алгоритм ACO,
щоб збільшити різноманітність і уникнути
стагнації, втіливши процес обміну. Гібрид-
ний метод композиції динамічних сервісів
[88] представлено на основі методу опти-
мального шляху зваженого орієнтованого
ациклічного графа, який поєднує ACO та
GA для проблеми QWSC. Пропонується
новий динамічний генетичний гібридний
алгоритм мурашиної колонії [89] для ви-
значення часу запуску генетичних алгори-
тмів і алгоритмів мурашиної колонії для
найкращої стратегії оцінки злиття. Отже,
здатність до оптимізації максимізується, а
загальна швидкість конвергенції приско-
рюється. В роботі [90] для проблеми
QWSC пропонується алгоритм оптимізації
C-MMAS (culture max-min ant system),
отриманий шляхом інтеграції системи
Max–Min ant у структуру культурного ал-
горитму. Алгоритм складається з простору
популяцій, простору переконань і протоко-
лів зв’язку між ними. Популяційний прос-
тір містить ряд рішень. Простір переко-
нань зберігає кращі рішення, отримані в
еволюційному процесі популяційного про-
стору; ці рішення розглядаються як досвід
і знання та використовуються для скеру-
вання еволюції C-MMAS у популяційному
просторі. Окрім того, розроблено комплек-
сну модель (DGQoS) оцінки CWS, заснова-
ній на загальній QoS та доменній QoS, і но-
вий алгоритм оптимізації C-MMAS для ви-
рішення проблеми вибору сервісу на ос-
нові DGQoS.
В останні роки зі швидким розвит-
ком мереж мобільного зв’язку продовжу-
ють з’являтися деякі нові сервіси, такі як
хмарна віртуальна реальність, голографіч-
ний зв’язок тощо. Тому потрібні більш гну-
чкі та інтелектуальні алгоритми композиції
сервісів. Виходячи з цього, в [91] запропо-
новано стратегію композиції сервісу в бага-
тохмарному середовищі, а також алгоритм
ACO на основі механізму мультиферомонів
для оптимізації QoS. Щоб уникнути появи
локальних оптимумів, ми додатково вво-
димо операцію мутації генетичного алго-
ритму.
Програмна інженерія - прикладні методи
14
Інші метаевристики композиції
сервісів
Jiang B. та ін. [92] для підвищення
ефективності композиції сервісу запропо-
нували підхід на основі вдосконаленого ал-
горитму феєрверків (fireworks algorithm). В
[93] представлено розширений багатоцільо-
вий алгоритм диференціальної еволюції
для пошуку репрезентативного набору рі-
шень із хорошою близькістю та дистрибу-
тивністю. У [94] для вирішення проблеми
композиції сервісу використовується варі-
ант алгоритму пошуку гармонії (Harmony
Search), який знаходить оптимальний ком-
позитний сервіс, що задовольняє локальні
та глобальні обмеження користувача щодо
атрибутів якості. Ghobaei-Arani M. та ін.
[95] представили алгоритм пошуку зозулі
(cuckoo search, CS), який здійснює компози-
цію сервісу для покращення QoS у розподі-
леному хмарному середовищі. Dahan F.
[96] запропонував покращений алгоритм
оптимізації кита (IWOA), який містить три
різні стратегії для підвищення продуктив-
ності базового алгоритму оптимізації кита
(Whale Optimization Algorithm, WOA) за ра-
хунок збільшення швидкості збіжності, яка
створює низьку точність рішення для про-
блеми композиції сервісів. У [97] для зна-
ходження композиції хмарного сервісу з оп-
тимальними значеннями QoS запропоно-
вано гібридний алгоритм, який поєднує ал-
горитми стратегії орла (Eagle Strategy
Algorithm) з WOA, що покращало швид-
кість збіжності та забезпечило належний
баланс між дослідженням та експлуата-
цією. Dahan F. [98] пропонує алгоритм, за-
снований на поведінці мікрокажанів під час
полювання на здобич. Запропонований ал-
горитм усуває деякі недоліки класичного
алгоритму кажана (Bat Algorithm, BA) і ви-
значає оптимальну комбінацію сервісів для
задоволення потреб користувача. У роботі
[99] вдосконалено алгоритм штучної бджо-
линої колонії, щоб зробити його більш при-
датним для проблеми композиції сервісів.
Запропоноване вдосконалення контролює
стратегії експлуатації та дослідження таким
чином, щоб заохочувати дослідження на
ранніх стадіях, а експлуатацію на більш пі-
зніх стадіях. Pop C. та ін. [100] представили
гібридний алгоритм, який поєднує нав-
чання з підкріпленням із метаевристиками
CS та табу пошук. У цьому алгоритмі нав-
чання з підкріпленням відстежує заміну
сервісу, тоді як табу пошук використову-
ється для оптимізації процесу вибору з то-
чки зору часу виконання та досліджуваного
простору пошуку. Простір пошуку моделю-
ється як структура розширеного графа пла-
нування, яка кодує всі можливі рішення
композиції для заданого запиту користу-
вача. Щоб встановити, чи є рішення опти-
мальним, атрибути QoS сервісів, а також се-
мантична подібність між ними, розгляда-
ються як критерії оцінки. Chifu V. та ін
[101] запропонували алгоритм оптимізації
спаровування медоносних бджіл у поєд-
нанні з компонентами генетичного алгори-
тму, табу пошуку та навчання з підкріплен-
ням. У роботі [102] запропоновано алго-
ритм пошуку вусиків жука (Beetle Antennae
Searching Algorithm) інтегрувати в PSO для
створення кращої початкової популяції та,
як наслідок, досягнення швидшої конверге-
нції. Dahan F. та ін. [103] представили гіб-
ридний алгоритм між ABC та CS, щоб збі-
льшити ефективність композиції сервісів.
Алгоритм CS використовується для подо-
лання повільної конвергенції ABC, дозволя-
ючи покинутим бджолам покращити свій
пошук і перекрити локальний оптимум.
Ahanger T. та ін. [04] запропонували гібри-
дний алгоритм між ABC і BA для досяг-
нення кращого компромісу між локальним
використанням і глобальним пошуком.
Peng та ін. [105] запропонували багатоклас-
терну адаптивну оптимізацію мозкового
штурму, об’єднану з подвійною опорною
векторною машиною для зменшення прос-
тору пошуку.
Висновки
З появою і розвитком SAO еволюція
складності проблеми композиції сервісів
проходила в напрямку її зростання у міру
збільшення кількості та асортименту серві-
сів, обчислювальних парадигм та можливо-
стей мереж Інтернет. Водночас методи її
розв’язання переходили від точних (без ев-
ристичних) підходів до майже оптимальних
евристик і, нарешті, до метаевристик глоба-
льної отимізації, які є домінуючими протя-
Програмна інженерія - прикладні методи
15
гом останніх двох десятиліть. Проведений в
даній роботі репрезентативний огляд і ана-
ліз метаевристичних методів дозволяє зро-
бити ряд висновків, зокрема:
Фундаментальна мета дослідження
композиції сервісу полягала в досягнені
швидкої конвергенції та стабільних мето-
дів, які можуть знайти високоякісні рі-
шення для користувачів, в умовах динамі-
чно змінного середовища сервісів, незале-
жно від скадності проблеми QWSC.
Метаевристики значною мірою ви-
правдали покладені на них очікування.
Проте поява останніми роками нових обчи-
слювальних парадигм з обмеженими ресур-
сами, таких як інтернет речей, туманне та
хмарне обчислення тощо суттєво усклад-
нили проблему QWSC. Емпіричні дані по-
казують, що досягнення фундаментальної
мети в рамках автономних метаевристик
стає все складнішим. Швидка конвергенція,
уникнення локального захоплення, робота з
великим простором пошуку та досягнення
високоякісного рішення зміщують дослі-
дження композиції сервісів у бік розробки
гібридних метаевристик, які можуть дося-
гти тонкого балансу між дослідженням та
експлуатацією. Гібридна метаевристика є
багатообіцяючою спробою вийти за межі
метаевристики через об'єднання декількох
метаевристик таким чином, щоб подолати
недоліки кожної з них, не втрачаючи водно-
час їхніх переваг. Поєднання машинного
навчання з метаевристикою стало остан-
ньою тенденцією в цій галузі. Більше того,
нещодавня гібридизація машинного нав-
чання та генетичного програмування в рам-
ках повністю автоматизованої композиції
сигналізує про рух до парадигми гіпереври-
стики.
References
1. Huhns M. N., Singh M. P., Service-oriented compu-
ting: Key concepts and principles, IEEE Internet
Comput., vol. 9, no. 1, pp. 75–81, Jan. 2005.
2. Papazoglou M. P., Heuvel W.-J., Service oriented
architectures: approaches, technologies and re-
search issues, VLDB J. Vol.16 (3) (2007) 389–415.
3. O’Sullivan J., Edmond D., Hofstede A.T., What’s in
a service?, Distrib. Parallel Databases, 2002, 12,
(2–3), pp. 117–133
4. Bouguettaya A., Sheng Q.Z., Daniel F. (Eds.), Web
Services Foundations, Springer, 2013, P.739
5. Gabrel V., Manouvrier M., Murat C., Optimal and
automatic transactional web service composition
with dependency graph and 0-1 linear program-
ming, in Proc. Int. Conf. Service-Oriented Comput.
Berlin: Springer, Nov. 2014, pp. 108–122.
6. Li J., Zhao Y., Liu M., et al.: An adaptive heuristic
approach for distributed QoS-based service compo-
sition, in Proc. IEEE Symp. Comput. Commun.,
Jun. 2010, pp. 687–694.
7. Dongre Y., Ingle R.: An investigation of QoS
criteria for optimal services selection in
composition, in Proc. 2nd Int. Conf. Innov. Mech.
Ind. Appl. (ICIMIA), Mar. 2020, pp. 705–710.
8. Mili H., Tremblay G., et al.: Business Process Mod-
eling Languages: Sorting Through the Alphabet
Soup. ACM Computing Surveys, 11, 2010, P.57
9. Pop C., Vlad M., Chifu V., et al.: A tabu search op-
timization approach for semantic web service com-
position, in Proc. 10th Int. Symp. Parallel Distrib.
Comput., Jul. 2011, pp. 274–277.
10. Liu Q., Zhang S.-L., Yang R., et al.: Web services
composition with QoS bound based on simulated
annealing algorithm, J. Southeast Univ., vol. 24, no.
3, 2008, pp. 308–311.
11. Canfora G., Penta M.D., Esposito R., et al.: A light-
weight approach for QoS-aware service composi-
tion, Proc. 2nd Int. Conf. on Service Oriented Com-
puting (ICSOC’04), NY, USA, 2004, pp. 36–47
12. Zhang C.W., Su S., Chen J.L.: DiGA: population
diversity handling genetic algorithm for QoS-aware
web services selection, Comput. Commun., 2007,
30, pp. 1082–1090
13. Zhang C.W., Ma Y.: Dynamic genetic algorithm for
search in web service compositions based on global
QoS evaluations. IEEE Int. Conf. on Scalable Com-
puting and Communications, 2009, pp. 644–649
14. Vanrompay Y., Rigole P., et al.: Genetic algorithm-
based optimization of service composition and de-
ployment. 3rd Int. workshop on Services integra-
tion in pervasive environments, 2008, pp. 13–17
15. Gong X.R., Zhu Q.S., Wu C.L., et al.: Web services
composition supporting global optimal and dy-
namic re-planningof QoS, Comput. Integr. Manuf.
Syst.,2008, 14, (10), pp. 2068–2075
16. Jiang Z., Han J., Wang Z.: An optimization model
for dynamic QoS-aware web services selection and
composition, Chin. J. Comput., 2009, 32, (5), pp.
1014–1025
17. Ai L., Tang M., Fidge C.: Partitioning composite web
services for decentralized execution using a genetic
algorithm, Future Gener. Comput. Syst., 2011, 27,
pp. 157–172
18. Cao J., Wang J., Zhao H., et al.: A service process
optimization method based on model refinement, J.
Supercomput., 2013, 63, pp. 72–88
19. Yu Q., Rege M., Bouguettaya A., et al.: A two-phase
framework for quality-aware web service selection,
Serv. Oriented Comput. Appl., 2010, 4, pp. 63–79
20. Klein A., Ishikawa F., Honiden S.: Towards net-
work-aware service composition in the cloud.
WWW 2012, Lyon, France, 2012, pp. 959–968
Програмна інженерія - прикладні методи
16
21. Ukor R.: Service selection and horizontal multi-
sourcing in process-oriented capability outsourcing,
J. Softw., Evol. Process, 2012, 24, pp. 259–283
22. Fanjiang Y.-Y., Syu Y.: Semantic-based automatic
service composition with functional and non-func-
tional requirements in design time: a GA approach,
Inf. Softw. Technol., 2014, 56, (3), pp. 352–373
23. Li Y.Z., Hu J., et al.: Research on QoS service com-
position based on coevolutionary genetic algorithm,
Soft Comput., 2018, 22, pp. 7865–7874
24. Claro D.B., Albers P., Hao J.K.: Selecting web ser-
vices for optimal composition. Int’l Conf. Web Ser-
vices (ICWS’05), Orlando, FL, USA, 2005
25. Yao Y.J., Chen H.P.: Qos-aware service composi-
tion using NSGA-II. 2nd Int. Conf. on Interaction
Sciences, Seoul, Korea, 2009, pp. 358–363
26. Hashmi K., Alhosban A., Najmi E., et al.: Auto-
mated web service quality component negotiation
using NSGA-2. ACS Int. Conf. on Computer Sys-
tems and Applications, Ifrane, 2013, pp. 1–6
27. Li J.Z., Luo W.L., Zeng J.T., et al.: Application of
SPEA2 algorithm in web services selection. IEEE
Youth Conf. on Information Computing and Tele-
communications, Beijing, 2010, pp. 387–390
28. Liu S., Liu Y.: A dynamic web services selection al-
gorithm with QoS global optimal in web services
composition, J. Softw., 2007, 18, (3), pp. 646–656
29. Wang J.L. et al.: Optimal web service selection
based on multi-objective GA. Int. Symp. on Comp.
Intellig. and Design, 2008, pp. 553–556
30. Hu H., Dong W., et al.: Pareto optimality based ge-
netic algorithm in web services composition, J.
Xi’an Jiao Tong Univ., 2009, 43, (12), pp. 50–54
31. Wagner F., Klopper B., et al.: Towards robust ser-
vice compositions in the context of functionally di-
verse services. WWW, 2012, pp. 969–978
32. Ramĺłrez A., Parejo J., Romero J., et al.: Evolution-
ary composition of QoS-aware web services: A
many-objective perspective, Expert Syst. Appl.,
2017, 72, pp. 357–370
33. Ma X.N., Dong B.T.: Linear physical programming
based approach for web service selection. 2008 Int.
Conf. on Information Management, Innovation
Management and Industrial Engineering, Xian,
China, 2008, pp. 398–401
34. Liang W.Y., Huang C.C.: The generic genetic algo-
rithm incorporates with rough set theory – An ap-
plication of the web services composition, Expert
Syst. Appl., 2009, 36, pp. 5549–5556
35. Liu Z., Xue X., Shen J., et al.: Web service dynamic
composition based on decomposition of global QoS
constraints, Int. J. Adv. Manuf. Technol., 2013, 69,
pp. 2247–2260
36. Que Y., Zhong W., Chen H., et al.: Improved adap-
tive immune genetic algorithm for optimal QoS-
aware service composition selection in cloud man-
ufacturing, Int. J. Adv. Manuf. Technol., vol. 96,
nos. 9-12, pp. 4455-4465, Jun. 2018.
37. Sadeghiram S., Ma H., Chen G.: Cluster-guided ge-
netic algorithm for distributed data-intensive web
service composition, in Proc. IEEE Congr. Evol.
Comput. (CEC), Jul. 2018, pp. 1-7.
38. Jatoth C., Gangadharan G.: Optimal fitness aware
cloud service composition using an adaptive geno-
types evolution based genetic algorithm, Future
Gener. Comput. Syst., vol. 94, pp. 185-198, 2019.
39. Rodriguez-Mier P., Mucientes M., Lama M., et al.:
Composition of web services through genetic pro-
gramming, Evol. Intell., 2010, 3, pp. 171–186
40. Yu Y., Ma H., Zhang M.: An adaptive genetic pro-
gramming approach to QoS-aware web services
composition. IEEE Congress on Evolutionary
Computation, Cancun, 2013, pp. 1740–1747
41. Yu Y., Ma H., Zhang M.: A Genetic Programming
approach to distributed QoS-aware web service
composition. IEEE Congress on Evolutionary
Computation 2014: 1840-1846
42. Ma H., Wang A., Zhang M.: A hybrid approach us-
ing genetic programming and greedy search for
QoS-aware web service composition, in Transac-
tions on Large-Scale Data-and Knowledge-Cen-
tered Systems XVIII. Springer, 2015, pp. 180-205.
43. Yu Y., Ma H., Zhang M.: A hybrid GP-tabu ap-
proach to QoSaware data intensive web service
composition, in Proc. Asia-Pacific Conf. Simulated
Evol. Learn.: Springer, Dec. 2014, pp. 106-118.
44. Wang A., Ma H., Zhang M.: Genetic programming
with greedy search for web service composition, in
Database and Expert Systems Applications, vol.
8056, pp. 9-17.
45. Yang F.C., et al.: An improved particle swarm op-
timization algorithm for QoS-aware web service se-
lection in service oriented communication, Int. J.
Comput. Intell. Syst., 2010, 4, (s), pp. 18–30
46. Wang S.G., Sun Q.B., Zou H., et al.: Particle swarm
optimization with skyline operator for fast cloud-
based web service composition, Mobile Netw.
Appl., 2013, 18, pp. 116–121
47. Fan X.Q., Jiang C.J., Fang X.W., et al.: Dynamic
web service selection based on discrete PSO, J.
Comput. Res. Dev., 2010, 47, (1), pp. 147–156
48. Wang L., He Y.X.: Web service composition based
on QoS with chaos particle swarm optimization. 6th
Int. Conf. on Wireless Communications Network-
ing and Mobile Computing, 2010, pp. 1–4
49. Li W.F., Zhong Y., Wang X., et al.: Resource virtu-
alization and service selection in cloud logistics, J.
Netw. Comput. Appl., 2013, 36, pp. 1696–1704
50. Li S.Z., Shen P., Yang S.X.: A grouping particle
swarm optimization algorithm for web service se-
lection based on user preference. 2011 IEEE Int.
Conf. on Computer Science and Automation Engi-
neering, Shanghai, China, 2011, v3, pp. 427–431
51. Ludwig S.A.: Applying particle swarm optimiza-
tion to quality-of-service driven web service com-
position. IEEE 26th Int. Conf. on Advanced Infor-
mation Networking and Applications (AINA), Fu-
kuoka, Japan, 2012, pp. 613–620
52. Cao J.X., Sun X.S., Zheng X., et al.: Efficient multi-
objective services selection algorithm based on
particle swarm optimization. IEEE Asia-Pacific
Services Computing Conf., 2010, pp. 603–608
53. Yu W., Li S., Tang X., et al.: An efficient top-k
ranking method for service selection based on ɛ-
Програмна інженерія - прикладні методи
17
ADMOPSO algorithm, Neural Comput. Appl.,
2018, 31, pp. 77–92
54. Guha T., Ludwig S.A.: Comparison of service se-
lection algorithms for grid services: multiple objec-
tive PSO and constraint satisfaction based service
selection. 20th IEEE Int. Conf. on Tools with Arti-
ficial Intelligence, 2008, pp. 172–179
55. Fan X.Q. A decision-making method for personal-
ized composite service, Expert Syst. Appl., 2013,
40, pp. 5804–5810
56. Tao F., Zhao D.M., Hu Y.F., et al.: Correlation-
aware resource service composition and optimal-se-
lection in manufacturing grid, Eur. J. Oper. Res.,
2010, v. 201, pp. 129–143
57. Xu X., Rong H., et al.: Predatory search-based
chaos turbo particle swarm optimisation (PS-
CTPSO): A new PSO algorithm for web service
combination probems, Future Gener. Comput.
Syst., v. 89, pp. 375–386, 2018.
58. Liu Y., Miao H., Li Z., et al.: QoS-aware web ser-
vices composition based on HQPSO algorithm, in
Proc. 1st ACIS/JNU Int. Conf.Comput., Netw., Syst.
Ind. Eng., May 2011, pp. 400–405.
59. Yin H., Zhang C., et al.: A hybrid multiobjective
discrete PSO algorithm for a SLA-aware service
composition problem, Math. Problems Eng., vol. 4,
2014, pp.1-14
60. Wang S., Sun Q., Zou H., et al.: Particle swarm op-
timization with skyline operator for fast cloud-
based web service composition, Mobile Netw.
Appl., vol. 18, no. 1, pp. 116-121, 2013.
61. Hossain M. S., Moniruzzaman M, et al.: Big data-
driven service composition using parallel clustered
PSO in mobile environment, IEEE Trans. Services
Comput., vol. 9, no. 5, pp. 806-817, Sep. 2016.
62. Chifu V. R., Pop C. B., et al.: Web service compo-
sition technique based on a service graph and PSO,
in Proc. IEEE 6th Int. Conf. Intell.Comput. Com-
mun. Process., 2010, pp. 265-272.
63. Gharbi M., Mezni H.: Towards big services compo-
sition, Int. J.Web Grid Services, vol. 16, no. 4, pp.
393–421, 2020.
64. Zhao X., Huang P., et al.: A hybrid clonal selection
algorithm for quality of service-aware web service
selection problem, Int. J. Innov. Comput. Inf. Con-
trol, vol. 8, no. 12, pp. 8527–8544, 2012.
65. Fekih H., Mtibaa S., Bouamama S.: An efficient
user-centric web service composition based on har-
mony particle swarm optimization, Int. J. Web Ser-
vices Res., vol. 16, no. 1, pp. 1–21, Jan. 2019.
66. da Silva A. S., Mei Y., Ma H., et al.: Particle swarm
optimization with sequence-like indirect represen-
tation for web service composition, in Evolutionary
Computation in Combinatorial Optimization, vol.
9595, Chicano F., Hu B., García-Sánchez P., Eds.
Cham, Switzerland: Springer, 2016, 8-14.
67. Zhao X., Song B., et al.: An improved discrete im-
mune optimization algorithm based on PSO for
QoS-driven web service composition, Appl. Soft
Comput., vol. 12, no. 8, pp. 2208–2216, 2012.
68. Haytamy S., Omara F.: A deep learning based
framework for optimizing cloud consumer QoS-
based service composition, Computing, vol. 102,
no. 5, pp. 1117–1137, May 2020.
69. Hosseinzadeh M., Tho Q., Ali S., et al.: A hybrid
service selection and composition model for cloud-
edge computing in the Internet of Things, IEEE
Access, vol. 8, pp. 85939-85949, 2020.
70. Sun Q., Wang S., Yang F.: Quick service selection
approach based on particle swarm optimization.
IEEE Fifth Int. Conf. on Bio-Inspired Computing:
Theories and Applications, 2010, pp. 278–284
71. Zhao X.C., Song B.Q., et al.: An improved discrete
immune optimization algorithm based on PSO for
QoS-driven web service composition, Appl. Soft
Comput., 2012, 12, (8), pp. 2208–2216
72. Fan X.Q., Fang X.W., Jiang C.J.: Research on web
service selection based on cooperative evolution,
Expert Syst. Appl., 2011, 38, pp. 9736–9743
73. Yu C.X., Wang G.: A multi-agent based architec-
ture for web service selection in E-business. Eighth
IEEE Int. Conf. on e-Business Engineering, Bei-
jing, China, 2011, pp. 245–250
74. Fethallah H., Chikh M.A., Mohammed M., et al.:
Qos-aware service selection based on swarm parti-
cle optimization. Int. Conf. on Information Tech-
nology and e-Services, Sousse, 2012, pp. 1–6
75. Zheng X.: Ant colony intelligence based solution
for grid services selection. 7th World Congress on
Intelligent Control and Automation, 2008, pp.
2512–2517
76. Wang L.J., Shen J., et al.: Towards minimizing cost
for composite data-intensive services. Proc. of the
2013 IEEE 17th Int. Conf. on Computer Supported
Cooperative Work in Design, 2013, pp. 293–298
77. Hossain M.S., Hossain S.K.A., Alamri A., et al.:
Ant-based services election framework for a smart
home monitoring environment, Multimed. Tools.
Appl., 2013, 67, pp. 433–453
78. Pop C.B., Chifu V.R., Salomie I., et al.: Ant-in-
spired technique for automatic web service compo-
sition and selection. 12th Int. Symp. on Symbolic
and Numeric Algorithms for Scientific Computing,
Timisoara, Romania, 2010, pp. 449–455
79. Wang R., Ma L., Chen Y.P.: The application of ant
colony algorithm in web service selection. 2010 Int.
Conf. on Computational Intelligence and Software
Engineering (CiSE), Wuhan, China, 2010, pp. 1–4.
80. Yu Q., Chen L., Li B. Ant colony optimization ap-
plied to web service compositions in cloud compu-
ting, Computers & Electrical Engineering Vol. 41,
2015, pp. 18–27
81. Fang Q., Peng X., Liu Q., et al.: A global QoS opti-
mizing web service selection algorithm based on
MOACO for dynamic web service composition.
Int. Forum on Information Technology and Appli-
cation, Chengdu, China, 2009, v.1, pp. 37–42
82. Zhang W., Chang C.K., Feng T.M., et al.: Qos-
based dynamic web service composition with ant
colony optimization. IEEE 34th Annual Computer
Software and Applications Conf., Seoul, Korea,
2010, pp. 493–502
83. Dahan F., Hindi K., Ghoneim A., et al.: An En-
hanced Ant Colony Optimization Based Algorithm
Програмна інженерія - прикладні методи
18
to Solve QoS-Aware Web Service Composition,
IEEE Access ,Vol.9, pp. 34098 – 4111, 2021
84. Yang Z., Shang C., Liu Q., et al.: A dynamic web
services composition algorithm based on the com-
bination of ant colony algorithm and genetic algo-
rithm, J. Comput. Inf. Syst., vol. 6, no. 8, pp. 2617–
2622, 2010.
85. Yang Y., Yang B., Wang S., et al.: A dynamic ant-
colony genetic algorithm for cloud service compo-
sition optimization, Int. J. Adv. Manuf. Technol.,
vol. 102, (1-4), pp. 355–368, 2019.
86. Liu Z.-Z., Wang Z.-J., Zhou X.-F, et al.: A new al-
gorithm for QoS-aware composite web services se-
lection, in Proc. 2nd Int. Workshop Intell. Syst.
Appl., May 2010, pp. 1–4.
87. Alayed H., Dahan F., Alfakih T., et al.: Enhance-
ment of ant colony optimization for QoS-aware web
service selection, IEEE Access, vol. 7, pp. 97041–
97051, 2019.
88. Yang Z.K., Shang C.W., Liu Q.T., et al.: A dy-
namic web services composition algorithm based
on the combination of ant colony algorithm and ge-
netic algorithm, J. Comput. Inf. Syst., 2010, 6, (8),
pp. 2617–2622
89. Yang Y., Yang B., Wang S., et al.: A dynamic ant-
colony genetic algorithm for cloud service compo-
sition optimization, Int. J. Adv. Manuf. Technol.,
2019,102, (1–4), pp. 355–368
90. Liu Z., Wang Z., Zhou X., et al.: A new algorithm
for QoS-aware composite web services selection.
2nd Int. Workshop on Intelligent Systems and Ap-
plications (ISA), Kyiv, 2010, pp. 1–4
91. Bei L., Wenlin L., Xin S., et al.: An improved ACO
based service composition algorithm in multi‑cloud
networks. Journal of Cloud Computing (2024)
Vol.13, №1, pp.1-12
92. Jiang B., Qin Y., Yang Y., et al.: Web Service
Composition Optimization with the Improved Fire-
works Algorithm. Mobile Information Systems.
Volume 2022, pp.1-13
93. Peng S., Guo T.: Multi-Objective Service Compo-
sition Using Enhanced Multi-Objective Differen-
tial Evolution Algorithm. Computational Intelli-
gence and Neuroscience. 2023(1), pp.1-10.
94. Jafarpour N., Khayyambashi M.: A new approach
for QoS-aware web service composition based on
harmony search algorithm. 11th IEEE Int. Symp. on
Web Systems Evolution, 2009, pp. 75–78
95. Ghobaei-Arani M., Rahmanian A., et al.: CSA-
WSC: cuckoo search algorithm for web service
composition in cloud environments, Soft Comput.,
2018, 22, (24), pp. 8353–8378
96. Dahan F. An Improved Whale Optimization Algo-
rithm for Web Service Composition: Axioms 2022,
11, 725. pp. 1-14
97. Gavvala S., Jatoth C., et al.: Qos-aware cloud ser-
vice composition using eagle strategy, Future
Gener. Comput. Syst., 2019, 90, pp. 273–290
98. Dahan F. Neighborhood Search Based Improved
Bat Algorithm for Web Service Composition. Com-
puter Systems Science & Engineering CSSE, 2023,
vol.45, no.2 pp.1343-1356
99. Dahan F., Hindi K.E.: Enhanced artificial bee col-
ony algorithm for QoS-aware web service selection
problem, Computing, 2017, 99, (5), pp. 507–517
100. Pop C. B., Chifu V. R., Salomie I., et al.: Cuckoo-
inspired hybrid algorithm for selecting the optimal
web service composition, in Proc. IEEE 7th Int.
Conf. Intell. Comput. Commun. Process., Aug.
2011, pp. 33-40.
101.Chifu V. R, Pop C. B., Salomie I., et al.: Hybrid
honey bees mating optimization algorithm for iden-
tifying the near-optimal solution in web service
composition, Comput. Informat., vol. 36, no. 5, pp.
1143-1172, 2017.
102. Yang H., Xue F., Zhu H., et al.: Web service com-
position optimization based on adaptive mutant
beetle swarm, J. Phys., Conf. Ser., vol. 1651, no. 1,
Nov. 2020, pp.347-501
103. Dahan F., Alwabel A.: Artificial Bee Colony with
Cuckoo Search for Solving Service Composition.
Intelligent Automation & Soft Computing IASC,
2023, vol.35, no.3 pp.3385-3402
104. Ahanger T. A., Dahan F.: Hybridizing Artificial
Bee Colony with Bat Algorithm for Web Service
Composition. Computer Systems Science and En-
gineering CSSE, 2023, vol.46, no.2, pp.2429-2445
105. Peng S., Wang H., Yu Q.: Multi-clusters adaptive
brain storm optimization algorithm for QoS-aware
service composition, IEEE Access, vol. 8, pp.
48822-48835, 2020.
Одержано: 14.07.2025
Внутрішня рецензія оримана: 07.08.2025
Зовнішня рецензія оримана: 15.08.2025
Про авторa:
Мороз Григорій Борисович,
кандидат технічних наук,
с.н.с., провідний науковий співробітник.
https://orcid.org/0000-0001-8666-9503
Місце роботи автора:
Інститут програмних систем
НАН України
|