Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem
IntroductionWhen solving multi-objective combinatorial optimization problems using a search algorithm without a priori information, the result is a Pareto front. Selecting a solution from it is a laborious task if the number of solutions to be analyzed is large. This task would benefit from a system...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2023-05-01
|
| Series: | Frontiers in Computer Science |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/articles/10.3389/fcomp.2023.1179059/full |
| _version_ | 1797821492693565440 |
|---|---|
| author | Carlos Casanova Esteban Schab Lucas Prado Giovanni Daián Rottoli |
| author_facet | Carlos Casanova Esteban Schab Lucas Prado Giovanni Daián Rottoli |
| author_sort | Carlos Casanova |
| collection | DOAJ |
| description | IntroductionWhen solving multi-objective combinatorial optimization problems using a search algorithm without a priori information, the result is a Pareto front. Selecting a solution from it is a laborious task if the number of solutions to be analyzed is large. This task would benefit from a systematic approach that facilitates the analysis, comparison and selection of a solution or a group of solutions based on the preferences of the decision makers. In the last decade, the research and development of algorithms for solving multi-objective combinatorial optimization problems has been growing steadily. In contrast, efforts in the a posteriori exploration of non-dominated solutions are still scarce.MethodsThis paper proposes an abstract framework based on hierarchical clustering in order to facilitate decision makers to explore such a Pareto front in search of a solution or a group of solutions according to their preferences. An extension of that abstract framework aimed at addressing the bi-objective Next Release Problem is presented, together with a Dashboard that implements that extension. Based on this implementation, two studies are conducted. The first is a usability study performed with a small group of experts. The second is a performance analysis based on computation time consumed by the clustering algorithm.ResultsThe results of the initial empirical usability study are promising and indicate directions for future improvements. The experts were able to correctly use the dashboard and properly interpret the visualizations in a very short time. In the same direction, the results of the performance comparison highlight the advantage of the hierarchical clustering-based approach in terms of response time.DiscussionBased on these excellent results, the extension of the framework to new problems is planned, as well as the implementation of new validity tests with expert decision makers using real-world data. |
| first_indexed | 2024-03-13T09:53:28Z |
| format | Article |
| id | doaj.art-4f4ca5392569416d96c7b36641dd4ed4 |
| institution | Directory Open Access Journal |
| issn | 2624-9898 |
| language | English |
| last_indexed | 2024-03-13T09:53:28Z |
| publishDate | 2023-05-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Computer Science |
| spelling | doaj.art-4f4ca5392569416d96c7b36641dd4ed42023-05-24T04:50:52ZengFrontiers Media S.A.Frontiers in Computer Science2624-98982023-05-01510.3389/fcomp.2023.11790591179059Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problemCarlos CasanovaEsteban SchabLucas PradoGiovanni Daián RottoliIntroductionWhen solving multi-objective combinatorial optimization problems using a search algorithm without a priori information, the result is a Pareto front. Selecting a solution from it is a laborious task if the number of solutions to be analyzed is large. This task would benefit from a systematic approach that facilitates the analysis, comparison and selection of a solution or a group of solutions based on the preferences of the decision makers. In the last decade, the research and development of algorithms for solving multi-objective combinatorial optimization problems has been growing steadily. In contrast, efforts in the a posteriori exploration of non-dominated solutions are still scarce.MethodsThis paper proposes an abstract framework based on hierarchical clustering in order to facilitate decision makers to explore such a Pareto front in search of a solution or a group of solutions according to their preferences. An extension of that abstract framework aimed at addressing the bi-objective Next Release Problem is presented, together with a Dashboard that implements that extension. Based on this implementation, two studies are conducted. The first is a usability study performed with a small group of experts. The second is a performance analysis based on computation time consumed by the clustering algorithm.ResultsThe results of the initial empirical usability study are promising and indicate directions for future improvements. The experts were able to correctly use the dashboard and properly interpret the visualizations in a very short time. In the same direction, the results of the performance comparison highlight the advantage of the hierarchical clustering-based approach in terms of response time.DiscussionBased on these excellent results, the extension of the framework to new problems is planned, as well as the implementation of new validity tests with expert decision makers using real-world data.https://www.frontiersin.org/articles/10.3389/fcomp.2023.1179059/fullsearch-based software engineeringpreference-based algorithmsa posteriori approachhierarchical clusteringmultiobjective optimizationPareto front |
| spellingShingle | Carlos Casanova Esteban Schab Lucas Prado Giovanni Daián Rottoli Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem Frontiers in Computer Science search-based software engineering preference-based algorithms a posteriori approach hierarchical clustering multiobjective optimization Pareto front |
| title | Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem |
| title_full | Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem |
| title_fullStr | Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem |
| title_full_unstemmed | Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem |
| title_short | Hierarchical clustering-based framework for a posteriori exploration of Pareto fronts: application on the bi-objective next release problem |
| title_sort | hierarchical clustering based framework for a posteriori exploration of pareto fronts application on the bi objective next release problem |
| topic | search-based software engineering preference-based algorithms a posteriori approach hierarchical clustering multiobjective optimization Pareto front |
| url | https://www.frontiersin.org/articles/10.3389/fcomp.2023.1179059/full |
| work_keys_str_mv | AT carloscasanova hierarchicalclusteringbasedframeworkforaposterioriexplorationofparetofrontsapplicationonthebiobjectivenextreleaseproblem AT estebanschab hierarchicalclusteringbasedframeworkforaposterioriexplorationofparetofrontsapplicationonthebiobjectivenextreleaseproblem AT lucasprado hierarchicalclusteringbasedframeworkforaposterioriexplorationofparetofrontsapplicationonthebiobjectivenextreleaseproblem AT giovannidaianrottoli hierarchicalclusteringbasedframeworkforaposterioriexplorationofparetofrontsapplicationonthebiobjectivenextreleaseproblem |