Fixed set search applied to the multi-objective minimum weighted vertex cover problem
<p dir="ltr">The Fixed Set Search (FSS) is a novel metaheuristic that adds a learning mechanism to the Greedy Randomized Adaptive Search Procedure (GRASP). In recent publications, its efficiency has been shown on different types of combinatorial optimization problems like routing, ma...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| منشور في: |
2022
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513506566471680 |
|---|---|
| author | Raka Jovanovic (17947838) |
| author2 | Antonio P. Sanfilippo (19122049) Stefan Voß (6943367) |
| author2_role | author author |
| author_facet | Raka Jovanovic (17947838) Antonio P. Sanfilippo (19122049) Stefan Voß (6943367) |
| author_role | author |
| dc.creator.none.fl_str_mv | Raka Jovanovic (17947838) Antonio P. Sanfilippo (19122049) Stefan Voß (6943367) |
| dc.date.none.fl_str_mv | 2022-05-12T09:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1007/s10732-022-09499-z |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/Fixed_set_search_applied_to_the_multi-objective_minimum_weighted_vertex_cover_problem/26888797 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Information and computing sciences Artificial intelligence Computer vision and multimedia computation Metaheuristics Minimum weighted vertex cover problem GRASP Fixed set search Pareto front |
| dc.title.none.fl_str_mv | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">The Fixed Set Search (FSS) is a novel metaheuristic that adds a learning mechanism to the Greedy Randomized Adaptive Search Procedure (GRASP). In recent publications, its efficiency has been shown on different types of combinatorial optimization problems like routing, machine scheduling and covering. In this paper the FSS is adapted to multi-objective problems for finding Pareto Front approximations. This adaptation is illustrated for the bi-objective Minimum Weighted Vertex Cover Problem (MWVCP). In this work, a simple and effective bi-objective GRASP algorithm for the MWVCP is developed in the first stage. One important characteristic of the proposed GRASP is that it avoids the use of weighted sums of objective functions in the local search and the greedy algorithm. In the second stage, the bi-objective GRASP is extended to the FSS by adding a learning mechanism adapted to multi-objective problems. The conducted computational experiments show that the proposed FSS and GRASP algorithm significantly outperforms existing methods for the bi-objective MWVCP. To fully evaluate the learning mechanism of the FSS, it is compared to the underlying GRASP algorithm on a wide range of performance indicators related to convergence, distribution, spread and cardinality.</p><h2>Other Information</h2><p dir="ltr">Published in: Journal of Heuristics<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1007/s10732-022-09499-z" target="_blank">https://dx.doi.org/10.1007/s10732-022-09499-z</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_2bd8c09176825b790063dbc0f2b933a4 |
| identifier_str_mv | 10.1007/s10732-022-09499-z |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/26888797 |
| publishDate | 2022 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | Fixed set search applied to the multi-objective minimum weighted vertex cover problemRaka Jovanovic (17947838)Antonio P. Sanfilippo (19122049)Stefan Voß (6943367)Information and computing sciencesArtificial intelligenceComputer vision and multimedia computationMetaheuristicsMinimum weighted vertex cover problemGRASPFixed set searchPareto front<p dir="ltr">The Fixed Set Search (FSS) is a novel metaheuristic that adds a learning mechanism to the Greedy Randomized Adaptive Search Procedure (GRASP). In recent publications, its efficiency has been shown on different types of combinatorial optimization problems like routing, machine scheduling and covering. In this paper the FSS is adapted to multi-objective problems for finding Pareto Front approximations. This adaptation is illustrated for the bi-objective Minimum Weighted Vertex Cover Problem (MWVCP). In this work, a simple and effective bi-objective GRASP algorithm for the MWVCP is developed in the first stage. One important characteristic of the proposed GRASP is that it avoids the use of weighted sums of objective functions in the local search and the greedy algorithm. In the second stage, the bi-objective GRASP is extended to the FSS by adding a learning mechanism adapted to multi-objective problems. The conducted computational experiments show that the proposed FSS and GRASP algorithm significantly outperforms existing methods for the bi-objective MWVCP. To fully evaluate the learning mechanism of the FSS, it is compared to the underlying GRASP algorithm on a wide range of performance indicators related to convergence, distribution, spread and cardinality.</p><h2>Other Information</h2><p dir="ltr">Published in: Journal of Heuristics<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1007/s10732-022-09499-z" target="_blank">https://dx.doi.org/10.1007/s10732-022-09499-z</a></p>2022-05-12T09:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1007/s10732-022-09499-zhttps://figshare.com/articles/journal_contribution/Fixed_set_search_applied_to_the_multi-objective_minimum_weighted_vertex_cover_problem/26888797CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/268887972022-05-12T09:00:00Z |
| spellingShingle | Fixed set search applied to the multi-objective minimum weighted vertex cover problem Raka Jovanovic (17947838) Information and computing sciences Artificial intelligence Computer vision and multimedia computation Metaheuristics Minimum weighted vertex cover problem GRASP Fixed set search Pareto front |
| status_str | publishedVersion |
| title | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| title_full | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| title_fullStr | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| title_full_unstemmed | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| title_short | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| title_sort | Fixed set search applied to the multi-objective minimum weighted vertex cover problem |
| topic | Information and computing sciences Artificial intelligence Computer vision and multimedia computation Metaheuristics Minimum weighted vertex cover problem GRASP Fixed set search Pareto front |