The goal of QoS aware web service composition (QoS-WSC) is to provide new functionalities and find a best combination of services to meet complex needs of users. QoS of the resulting composite service should be optimized. QoS-WSC is a global multi-objective optimization problem belonging to NP-hard class given the number of available services. Most of existing approaches reduce this problem to a single-objective problem by aggregating different objectives, which leads to a loss of information. An alternative issue is to use Pareto-based approaches. The Pareto-optimal set contains solutions that ensure the best trade-off between conflicting objectives. In this paper, a new multi-objective meta-heuristic bio-inspired Pareto-based approach is presented to address the QoS-WSC, it is based on Elephants Herding Optimization (EHO) algorithm. EHO is characterised by a strategy of dividing and combining the population to sub population (clan) which allows exchange of information between local searches to get a global optimum. However, the application of others evolutionary algorithms to this problem cannot avoids the early stagnancy in a local optimum. In this paper a discrete and multi-objective version of EHO will be presented based on a crossover operator. Compared with SPEA2 (Strength Pareto Evolutionary Algorithm 2) and MOPSO (Multi-Objective Particle Swarm Optimization algorithm), the results of experimental evaluation show that our improvements significantly outperform the existing algorithms in term of Hypervolume, Set Coverage and Spacing metrics.
Accepté le :
DOI : 10.1051/ro/2017049
Mots-clés : QoS, Multi-Objective optimization, Pareto Set, Bio-inspired Algorithms, Elephants Herding optimization, Web service composition
@article{RO_2019__53_2_445_0, author = {Chibani Sadouki, Samia and Tari, Abdelkamel}, title = {Multi-objective and discrete {Elephants} {Herding} {Optimization} algorithm for {QoS} aware web service composition}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {445--459}, publisher = {EDP-Sciences}, volume = {53}, number = {2}, year = {2019}, doi = {10.1051/ro/2017049}, zbl = {1436.68388}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2017049/} }
TY - JOUR AU - Chibani Sadouki, Samia AU - Tari, Abdelkamel TI - Multi-objective and discrete Elephants Herding Optimization algorithm for QoS aware web service composition JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 445 EP - 459 VL - 53 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017049/ DO - 10.1051/ro/2017049 LA - en ID - RO_2019__53_2_445_0 ER -
%0 Journal Article %A Chibani Sadouki, Samia %A Tari, Abdelkamel %T Multi-objective and discrete Elephants Herding Optimization algorithm for QoS aware web service composition %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 445-459 %V 53 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017049/ %R 10.1051/ro/2017049 %G en %F RO_2019__53_2_445_0
Chibani Sadouki, Samia; Tari, Abdelkamel. Multi-objective and discrete Elephants Herding Optimization algorithm for QoS aware web service composition. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 445-459. doi : 10.1051/ro/2017049. http://www.numdam.org/articles/10.1051/ro/2017049/
[1] QoS-based discovery and ranking of web services. In Proceedings of 16th International Conference on Computer Communications and Networks, ICCCN (2007) 529–534.
and ,[2] Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation). Springer; 2nd Edition (2007). | Zbl
, and ,[3] MOPSO: a proposal for multiple objective particle swarm optimization. In Proceedings of the 2002 Congress on Evolutionary Computation, CEC ’02 (2002) 1051–1056.
and ,[4] An approach for QoS-aware service composition based on genetic algorithms. In GECCO ‘05 Proceedings of the 2002 Congress on Evolutionary Computation (2005) 1069–1075.
, , and ,[5] Optimizing dynamic web service component composition by using evolutionary algorithms. In IEEE International Conference on Web Intelligence (2005) 708–711.
, and ,[6] Comparative analysis of multi-objective evolutionary algorithms for QoS-aware web service composition. Inter. J. Appl. Soft Comput. 39 (2016) 124–139.
, , and ,[7] QoS based web services composition using ant colony optimization: mobile agent approach. Inter. J. Adv. Res. Comput. Commun. Eng. 1 (2012) 519–527.
and ,[8] A novel web service composition using ant colony optimization with agent based approach. Inter. J. Emerging Technologies and Innovative Res. 2 (2015) 1685–1688.
and ,[9] QoS-based selection of services: The implementation of a genetic algorithm. In Commun. Distributed Syst. (KiVS), ITG-GI Confer. (2007) 1–12.
and ,[10] Fault tolerant design using single and multicriteria genetic algorithm optimization. In Technical report, DTIC Document (1995).
,[11] Consistencies and contradictions of performance metrics in multiobjective optimization. IEEE Trans. Cybernetics 44 (2014) 2391–2404.
, , and ,[12] Les Web services Techniques, dmarches et outils XML, WSDL, SOAP, UDDI, Rosetta, UML. Edition Dunod (2003).
and ,[13] Verity: A QoS metric for selecting web services and providers. In Proceedings of the Fourth International Conference on Web Information Systems Engineering Workshops (WISEW03) (2004) 131–139.
, and ,[14] Web service composition: A survey of techniques and tools. ACM Computing Surveys 48 (2015) 33, 41.
, and ,[15] Applying multi-objective evolutionary algorithms to QoS-aware web service composition. In 6th International Conference on Advanced Data Mining and Applications (2010) 270–281.
, , and ,[16] A multi-objective service selection algorithm for service composition. In 19th Asia-Pacific Conference on Communications (APCC), Bali Indonesia (2013) 75–80.
, , , and ,[17] Performance metrics in multi-objective optimization. In IEEE Latin American Computing Conference (CLEI) (2015) 1–11.
, and ,[18] Survey of multi-objective optimization methods for engineering. Inter. J. Structural Multidisciplinary Optimiz. 26 (2004) 369–395. | Zbl
and ,[19] Elephant herding optimization. In 3rd International Symposium on Computational and Business Intelligence (2015) 1–5.
, and ,[20] A new metaheuristic optimisation algorithm motivated by elephant herding behaviour. Inter. J. Bio-Inspired Comput. 8 (2016) 394–409.
, , and ,[21] An improved particle swarm optimization algorithm for QoS-aware web service selection in service oriented communication. Inter. J. Comput. Intell. Syst. 3 (2010) 18–30.
, , and ,[22] Transactional and QoS-aware dynamic service composition based on ant colony optimization. Future Generation Comput. Syst. 29 (2013) 1112–1119.
and ,[23] QoS-aware service composition using NSGA-II1. In ICIS ’09 Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human (2009) 358–363.
and ,[24] Multi-objective approach for energy-aware workflow scheduling in cloud computing environments. The Scientific World Journal 2013 (2013) 350934.
, , and ,[25] A survey on QoS-aware web service composition. In Third Inter. Confer. Multimedia Information Networking and Security (MINES) (2011) 283–287.
and ,[26] QoS-aware middleware for web services composition. IEEE Trans. Software Eng. 3 (2004) 311–327.
, , , , and ,[27] Comparison of multi-objective evolutionary algorithms: Empirical results. J. Evolutionary Comput. 8 (2000) 173–195.
, and ,[28] Web service dynamic composition based on decomposition of global QoS constraints. Inter. J. Adv. Manufacturing Technology 69 (2013) 2247–2260.
, , and ,[29] SPEA2: improving the strength pareto evolutionary algorithm for multi-objective optimization. In Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems. Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, edited by , , , , . International Center for Numerical Methods in Engineering (2001) 95–100.
, and[30] Multi-objective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Trans. Evolutionary Comput. 3 (1999) 257–271.
and ,[31] Multi-objective optimization using evolutionary algorithms- A comparative case study. In Parallel Problem Solving from Nature. Edited by , , , . In Vol. 1798 of Lecture Notes in Computer Science. Springer, Berlin (1998).
and ,Cité par Sources :