#17 - IBD - Indicator Based Distance

IBD is what I'd like to call an indicator based distance measure between two points.  It works exactly the same way in which a binary quality indicator works.  To recap, we're talking about optimizing multiple objectives (MOO), typically when there are trade-offs among the objectives in a multi-objective problem (MOP) with any number of decision (input) variables.  To perform the optimization, an evolutionary algorithm (MOEA) is typically applied, until there is an acceptable convergence of optimization across the objectives.

A recent class of MOEA that has been researched is the Indicator Based Evolutionary Algorithm (IBEA), in which a binary quality indicator is used as a means to improve each generation as opposed to standard domination measures.  Standard domination asks the question of whether an individual and its objective scores is dominated by another individual, which requires total winning across each objective and never losing.  But this question is not an informative question; regardless of whether we dominate or not, we lack knowing by how much domination occurs, or not.  And so an indicator based approach was suggested instead.

Zitzler proposes a indicator to use for IBEA in [1], which is as follows.  The "loss in quality" is measured between an objective and its residing population using formulation shown just below:

Figure 1.  The IBEA quality indicator for a point, X1.  I(P1, P2) =  delta(P1, P2).

To replace standard domination between two points, P1 and P2, we first compute F(P1) and F(P2) using the IBEA quality indicator above, and then compare F(P1) versus F(P2).  F(P1) measures the loss in quality of removing P1 from the population, while F(P2) measures the loss in quality of removing P2 from the population.  If F(P1) is a higher number than F(P2), then it has a higher loss in quality, and is thus more important to keep in the population.

Going further; we have need for a summarizing method to distinctly identify how well we have optimized the search space.  For this, the hypervolume indicator is typically used with respect to a reference point.  However, hypervolume is a very complex metric to compute as shown just below.  I want to propose an Indicator Based Distance as follows.

Figure 2.  The red box outlines the hypervolume to be calculated for the set of blue points and a purple reference point.

Using the reference point as part of the population, R, compute the IBEA quality, F(R), measuring the loss in quality of removing R, which should not be very high - since the reference point is typically close to "Hell" - the worst possible space of the search space.  Then we also calculate F(Pi) for each member of the population.  We can then create an i-length vector in (F(R) - F(Pi)) which is a list of values measuring their distance back to the reference point.  The average of this vector approximates the hypervolume metric and is much simpler to perform.

Figure 3.  Instead of euclidean distance to each blue population point, we use a differences of qualities method to approximate distances to the purple reference point.  Note that euclidean distance would be a poor metric, as the black pareto-frontier curve contains varying distances to the purple reference point.

The reference point can be chosen by electing the median of the initial population.  For each iteration of a generational MOEA approach, I propose the above as an Indicator-based distance (IBD) metric to summarize how much optimization has occurred since the algorithm's start.  In this way, two MOEA's can more easily be compared.

[1] E. Zitzler and S. Künzli. Indicator-Based Selection in Multiobjective Search. In Conference on Parallel Problem Solving from Nature (PPSN VIII), pages 832--842, 2004. Springer