Izvorni znanstveni članak
https://doi.org/10.1080/00051144.2020.1789364
An evolutionary algorithm for the robust maximum weighted independent set problem
Ana Klobučar
; aFaculty of Mechanical Engineering and Naval Architecture, University of Zagreb, Zagreb, Croatia
Robert Manger
orcid.org/0000-0003-0953-6517
; Department of Mathematics, Faculty of Science, University of Zagreb, Zagreb, Croatia
Sažetak
This work deals with the robust maximum weighted independent set problem, i.e. finding a subset of graph vertices that are not adjacent to each other and whose sum of weights is as large as possible. Uncertainty in problem formulation is restricted to vertex weights and expressed explicitly by a finite set of scenarios. Three criteria of robustness are considered: absolute robustness (max-min), robust deviation (min-max regret), and relative robustness (relative min-max regret). Since the conventional maximum weighted independent set problem is already NP-hard, finding the exact solution of its robust counterpart should obviously have a prohibitive computational complexity. Therefore, we propose an approximate algorithm for solving the considered
robust problem, which is based on evolutionary computing and on various crossover and mutation operators. The algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for any of the three robustness criteria in reasonable time.
Ključne riječi
Robust optimization; maximum weighted independent set; approximation; evolutionary algorithm; complexity
Hrčak ID:
258282
URI
Datum izdavanja:
23.9.2020.
Posjeta: 424 *