Home Overview People Algorithms Publication Softwares

HEMO: HFC for evolutionary multi-objective optimization (EMO)

Overview

The major difficulty of applying HFC principle to evolutionary multi-objective optimization is which criteria should be used to segment the individuals to ensure fair competition. Since in EMO, there exist multiple objective criteria, we can't use any single objective function as the standard to divide the fitness levels. One approach is to use aggregate EMO approach. We combine the multiple objective values into a single fitness and then the standard HFC algorithms can be used. However, in HEMO, a more clever scheme is used to enable HFC be appled to some modern EMO algorithms like PESA, NSGA-II, and SPEA. In [1] we combine HFC technique with PESA to achieve robust and sustainable EMO search. 

Approach

Essentially, HEMO  is an extension of PESA enhanced with the continuing search capability of HFC. In addition to the Pareto archive and the Pareto workshop population, a succession of archives for maintaining individuals of different fitness levels is added to allow mixing of lower- and intermediate-level building blocks. A random individual generator is located at the bottom to feed raw genetic material into this building block mixing machine continually. The structure of HEMO is illustrated in Fig. 1:  

The key idea of applying HFC to EMO is that using average rank of an individual over all objective criteria for segmenting the population into different fitness levels:

How HEMO compares to NSGA-II with controlled elitism

Comparing HEMO with NSGA-II (and other EMO algorithms), the major difference is that NSGA-II  search (even with controlled elitism) (Fig 1) is a convergent process. Most of the individuals converge into the possible local pareto front and becomes increasing difficult to jump out. While HEMO search (Fig 2) is a sustainable process without getting trapped anywhere. 

References:

[1] Jianjun Hu, Kisung Seo,  Zhun Fan, Ronald C. Rosenberg, Erik D. Goodman. HEMO: A Sustainable Multi-Objective Evolutionary Optimization Framework. (To appear in Genetic and Evolutionary Computation Conference 2003, Chicago)

HFC Home [Overview] [People] [Algorithms] [Publication] [Softwares]