A fast hypervolume driven selection mechanism for many-objective optimisation problems

被引:91
作者
Rostami, Shahin [1 ]
Neri, Ferrante [2 ]
机构
[1] Bournemouth Univ, Dept Comp & Informat, Bournemouth BH12 5BB, Dorset, England
[2] De Montfort Univ, Ctr Computat Intelligence, Leicester LE1 9BH, Leics, England
关键词
Multi-objective optimisation; Many-objective optimisation; Hypervolume indicator; Selection mechanism; Evolutionary optimisation; EVOLUTIONARY MULTIOBJECTIVE OPTIMIZATION; NONDOMINATED SORTING APPROACH; LOCAL SEARCH; PART I; ALGORITHM; EFFICIENT; DIVERSITY; OPERATOR; PARETO;
D O I
10.1016/j.swevo.2016.12.002
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Solutions to real-world problems often require the simultaneous optimisation of multiple conflicting objectives. In the presence of four or more objectives, the problem is referred to as a "many-objective optimisation problem". A problem of this category introduces many challenges, one of which is the effective and efficient selection of optimal solutions. The hypervolume indicator (or s-metric), i.e. the size of dominated objective space, is an effective selection criterion for many-objective optimisation. The indicator is used to measure the quality of a non-dominated set, and can be used to sort solutions for selection as part of the contributing hypervolume indicator. However, hypervolume based selection methods can have a very high, if not infeasible, computational cost. The present study proposes a novel hypervolume driven selection mechanism for many-objective problems, whilst maintaining a feasible computational cost. This approach, named the Hypervolume Adaptive Grid Algorithm (HAGA), uses two-phases (narrow and broad) to prevent population-wide calculation of the contributing hypervolume indicator. Instead, HAGA only calculates the contributing hypervolume indicator for grid populations, i.e. for a few solutions, which are close in proximity (in the objective space) to a candidate solution when in competition for survival. The result is a trade-off between complete accuracy in selecting the fittest individuals in regards to hypervolume quality, and a feasible computational time in many-objective space. The real-world efficiency of the proposed selection mechanism is demonstrated within the optimisation of a classifier for concealed weapon detection.
引用
收藏
页码:50 / 67
页数:18
相关论文
共 103 条
[1]   Convergence Acceleration Operator for Multiobjective Optimization [J].
Adra, Salem F. ;
Dodd, Tony J. ;
Griffin, Ian A. ;
Fleming, Peter J. .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2009, 13 (04) :825-847
[2]   A comparative study of variation operators used for evolutionary multi-objective optimization [J].
Alberto, Isolina ;
Coello Coello, Carlos A. ;
Mateo, Pedro M. .
INFORMATION SCIENCES, 2014, 273 :33-48
[3]  
[Anonymous], 1902, Annali di Matematica Pura ed Applicata, DOI DOI 10.1007/BF02420592
[4]  
[Anonymous], THESIS
[5]   A fast and efficient multi-objective evolutionary learning scheme for fuzzy rule-based classifiers [J].
Antonelli, Michela ;
Ducange, Pietro ;
Marcelloni, Francesco .
INFORMATION SCIENCES, 2014, 283 :36-54
[6]   Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications [J].
Auger, Anne ;
Bader, Johannes ;
Brockhoff, Dimo ;
Zitzler, Eckart .
THEORETICAL COMPUTER SCIENCE, 2012, 425 :75-103
[7]   Faster Hypervolume-Based Search Using Monte Carlo Sampling [J].
Bader, Johannes ;
Deb, Kalyanmoy ;
Zitzler, Eckart .
MULTIPLE CRITERIA DECISION MAKING FOR SUSTAINABLE ENERGY AND TRANSPORTATION SYSTEMS: PROCEEDINGS OF THE 19TH INTERNATIONAL CONFERENCE ON MULTIPLE CRITERIA DECISION MAKING, 2010, 634 :313-326
[8]   HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization [J].
Bader, Johannes ;
Zitzler, Eckart .
EVOLUTIONARY COMPUTATION, 2011, 19 (01) :45-76
[9]   SMS-EMOA: Multiobjective selection based on dominated hypervolume [J].
Beume, Nicola ;
Naujoks, Boris ;
Emmerich, Michael .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (03) :1653-1669
[10]  
Bowring N., 2013, P SPIE 8714 RAD SENS, V8714