#23 - JMOO Source Code Release

Search Based Software Engineering brings us a need to simulate real world problems and experiment with optimization of objectives.  For this, we need a way to model the simulations and the algorithms used to optimize objectives.  Formally, this is the field of Multi-Objective Optimization (MOO).  Sometimes, when there is only a single objective optimize, it is called Single-Objective Optimization instead.  In slightly older times, SOO was the more-studied, simplified case before its maturation and generalization into MOO.

MOO can best be described in mathematical terms.  MOO is used to optimize a Multi-Objective Problem (MOP).  A MOP consists of a set (X1, X2, …, Xn) of n decision explanatory variables, a set (Y1, Y2, …, Yk) of k objective response variables, and either a set of objective evaluation functions (f1(X1, X2, …, Xn), f2(X1, X2, …, Xn), …, fk(X1, X2, …, Xn)) or an evaluation model, either of which assigns values to each of the k objectives.   The decision variables each have their respective lower and upper bounds and in the case of constrained MOPs, the set of decisions as a whole is constrained to some set of bounds.  The objectives include an indication of which direction (minimizing, or maximizing) is optimal.  Typically, the optimization direction is ignored and an assumption is made, but I feel a need for its generalization.

As a broad overview, MOO is both: 1) an MOP and 2) an Algorithm to solve the MOP.  We just described the MOP above.  Now we discuss algorithmic approaches.  Most used is the MOEA (Multi-Objective Evolutionary Algorithm).  Two very state-of-the-art MOEAs are NSGA-II and SPEA2.  The MOEA is a standard type of algorithm that we build upon when presenting JMOEA (Joe's MOEA).

1. Initialization
2. Load Initial Population
3. Collect Initial Stats
4. Generational Evolution:
 - - 4a. Selector
 - - 4b. Adjustor
 - - 4c. Recombiner
 - - 4d. Collect New Stats
 - - 4e. Evaluate Stopping Criteria
5. Generational Representative Search

The outline above constitutes our JMOEA.  First, parameters are initialized, including MU, which defines the number of individuals in a population.  Each individual is a listing of decisions and objective fitness (when evaluated).  In the second step, an initial population is loaded - not generated.  This is so that when two algorithms try to optimize the same problem, they both begin with the same initial set of individuals.  Thirdly, stats are collected for the initial population.  The initial stats collection involves setting the reference point at the median of the population.  This median is then used to calculate our measures of quality and spread of the individuals in the population.  These measures help us determined how good we're doing in the algorithm.  Other stats include the medians of each objective and the number of evaluations accumulated thus far.

The core of our JMOEA is in step four when evolution starts.  Evolution is carried for a number of generations or until the stopping criteria of step 4e says to stop.  The methods of 4a, 4b and 4c are the steps that define the algorithm.  The selector first identifies a number of individuals from the population to use as "selectees", or offspring.  Then, the adjustor in step 4b modifies these selectees (usually per some chance rate).  Finally in 4c, the selectees and population are recombined, to either prune the size back down to MU-many individuals, or to grow back up to MU-many individuals.

The definition of an algorithm follows by assigning specific methods to each of 4a, 4b and 4c.  For instance, NSGA-II is defined when the selector is a tournament selection, adjustor is crossover and mutation, and the recombiner is the NSGA-II elite method (as described in its original paper reference).  SPEA2 is similarly defined, except its recombiner is defined to be the SPEA2 elitist method.

Finally, in step 5, we search through all the generations of the evolutionary process until we find a representing generation; ideally one of the better generations that we can use to say this is how good the algorithm worked.

The code that we use to develop JMOEA is contained in our JMOO package (Joe's MOO).  JMOO allows us to define decisions, objectives, problems, algorithms, individuals and the JMOEA.  It is very versatile in that new problems can very easily be defined, as well as new algorithms.  For fun: JMOO is our purple cow:

The code repository (python) for jmoo: http://unbox.org/things/tags/jmoo/

The rrsl method in jmoo_algorithms.py will require parts of http://unbox.org/things/tags/rrsl/

And the POM3 problem is at: http://unbox.org/things/tags/pom3/

#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

# 3: Multiobjective Optimization (MOO)

In search based software engineering (SBSE), we come across the problem of multiobjective optimization (MOO).  This problem can best be explained in terms of math functions.  Given an input vector X = [x1, x2, ..., xi], and a set of objective functions, Y = [f1(X), f2(X), ..., fj(X)], we'd like to know for which X are the Y optimized.

An example is my own dumb "moo problem":
 - We start with three input variables: X  = [x1, x2, x3], each xi bounded between [-2,2]
 - And define two output Y variables as follows:
 - - - f1(X) = -3*x1 + 2*x2
 - -  -f2(X) = 3*x3 + -2*x2

Imagine generating thousands of random sample inputs for the X.  Then evaluate the objective functions f1 and f2.  Create the goal of minimizing f1 and minimizing f2.  For which input vectors X are f1 and f2 the smallest?  In SBSE, the input vector X is a set of "decisions", and the output vector Y is a set of "objectives" that we want to minimize.

The example I used here is a very simple made-up random problem.  In reality there are dozens of such models such as Fonseca, Sriniva, ConstrEx, ZDT1, Golinski, and many more.  Note that some of these are constrained models, and some aren't.  The idea of constraints comes into play about additional bounds to the input X variables.

There are algorithms that can optimize solutions for such problems like this automatically for us, most notably NSGAII and SPEA2.  In my own research, we are experimenting with a newer technology known as RRSL (Rapid Recursive Spectral Learning.)  The use of these algorithms for MOO is often known as MOEA (Multiobjective Evolutionary Algorithm).

In a simpler world, where is only one objective to optimize, we can employ simpler methods such as KEYS or KEYS2.  But more than often, we're interested in more than just a single objective.