On Objective Conflicts and Objective Reduction in Multiple Criteria Optimization
Metadata only
Datum
2006-02Typ
- Report
ETH Bibliographie
yes
Altmetrics
Abstract
A common approach in multiobjective optimization is to perform the decision making process after the search process: first, a search heuristic approximates the set of Pareto-optimal
solutions, and then the decision maker chooses an appropriate trade-off solution from the resulting approximation set. Both processes are strongly affected by the number of optimization
criteria. The more objectives are involved the more complex is the optimization problem and the choice for the decision maker. In this context, the question arises whether all objectives are
actually necessary and whether some of the objectives may be omitted; this question in turn is closely linked to the fundamental issue of conflicting and non-conflicting optimization
criteria. Besides a general definition of conflicts between objective sets, we here introduce the problem of computing a minimum subset of objectives without losing information (MOSS) and
show that this is an NP-hard problem. Furthermore, we present for MOSS both an approximation algorithm with optimum approximation ratio and an exact algorithm which works well for small input
instances. The paper concludes with experimental results for random sets and the multiobjective 0/1-knapsack problem. Mehr anzeigen
Publikationsstatus
publishedZeitschrift / Serie
TIK ReportBand
Verlag
ETH Zurich, Computer Engineering and Networks LaboratoryOrganisationseinheit
03429 - Thiele, Lothar (emeritus) / Thiele, Lothar (emeritus)
ETH Bibliographie
yes
Altmetrics