Computation and Applications of Hypervolume Indicator in Multiobjective Optimization
多目標優化中超體積指標的計算與應用
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
| Awarding Institution | |
|---|---|
| Supervisors/Advisors |
|
| Award date | 4 Nov 2019 |
Link(s)
| Permanent Link | https://scholars.cityu.edu.hk/en/theses/theses(b5508c71-78c1-44d8-89ee-d68880f60bd5).html |
|---|---|
| Other link(s) | Links |
Abstract
In multiobjective optimization, the hypervolume indicator is one of the most widely used performance indicators. It is used to measure the quality of a solution set and to compare different solutions in multiobjective algorithms.
Since the exact computation of the hypervolume indicator is NP-hard, it is very time-consuming when the number of solutions and dimensions are large. Many approximation algorithms have been developed to reduce the computational complexity. In the thesis, we propose two new approximation algorithms. One algorithm expresses the hypervolume indicator in a lower dimensional space based on the coordinate transformation. The other combines a revised basic Monte Carlo method with an adaptive Monte Carlo method. Both algorithms are tested and compared with some other algorithms to approximate the hypervolume indicator on a broad class of random point sets. We also design the algorithms to exactly compute the hypervolume indicator and hypervolume contributions by using a general algorithm in O(n(d+2)/3) time.
When applied in multiobjective optimization methods, the hypervolume indicator can help guide the search for an optimal distribution with regard to some reference point. In the thesis, we analyze the influence of the reference point in a hypervolume-based multiobjective evolutionary algorithm, and propose a strategy to adaptively set the reference point. The strategy is examined on a set of multiobjective test problems and it improves the performance of the original algorithm.
Since the exact computation of the hypervolume indicator is NP-hard, it is very time-consuming when the number of solutions and dimensions are large. Many approximation algorithms have been developed to reduce the computational complexity. In the thesis, we propose two new approximation algorithms. One algorithm expresses the hypervolume indicator in a lower dimensional space based on the coordinate transformation. The other combines a revised basic Monte Carlo method with an adaptive Monte Carlo method. Both algorithms are tested and compared with some other algorithms to approximate the hypervolume indicator on a broad class of random point sets. We also design the algorithms to exactly compute the hypervolume indicator and hypervolume contributions by using a general algorithm in O(n(d+2)/3) time.
When applied in multiobjective optimization methods, the hypervolume indicator can help guide the search for an optimal distribution with regard to some reference point. In the thesis, we analyze the influence of the reference point in a hypervolume-based multiobjective evolutionary algorithm, and propose a strategy to adaptively set the reference point. The strategy is examined on a set of multiobjective test problems and it improves the performance of the original algorithm.
