*multiple*objectives to satisfy simultaneously: time, price, and quality is a traditional triple. However, multiple objectives are often in conflict, and so it is not possible to optimise them all simultaneously: there are

*tradeoffs*. “Pick any two of three” is the stated tradeoff for time, price, and quality; more nuanced tradeoffs are available.

One common technique is simply to add the various objective values together, with some weight for each, to reduce the problem to a single optimisation. But which weights? Different weights imply different tradeoffs.

So the next step is a full multi-objective optimisation system. To see what is going on, the crucial concept of

**needs to be understood.**

*dominated solution*Let’s assume that a candidate solution

*s*has objective values (

*f*

_{1},

*f*

_{2}, ...,

*f*). And let’s assume we want to

_{n}*minimise*each of those objectives (the maximisation case is similar,

*mutatis mutandis*). Then solution

*s*

_{1}

**dominates**solution

*s*

_{2}if every one of its objective values is less than the corresponding value for

*s*

_{2}. If on the other hand, s2 is better in all its objectives than

*s*

_{1}, then

*s*

_{2}dominates

*s*

_{1}. And in the case when neither dominates the other, these solutions are non-dominated. The figure below illustrates these concepts.

def dominates_min(a,b): # for minimisation problems # a and b are nD tuples of the respective n objective values # a dominates b if a.x < b.x and a.y < b.y and ... return all([(a < b) for a, b in zip(a,b)])

How this works: Let the tuples by (ax, ay, az) and (bx, by, bz). ThenIn a complete collection of candidate solutions, the ones not dominated by any other solution form the Pareto front. These are the best possible solutions: no other candidate performs better in all objectives. The front describes the possible tradeoffs: values along the front represent different tradeoffs.zipping them together gives the list of tuples [(ax,bx),(ay,by),(az,bz)]. The set comprehension gives a list of booleans,TrueorFalsedepending if the respective ai<bi or not. Then theallfunction tests whether all the values areTrue.

When we don’t have all candidate solutions to hand, maybe just a sample of solutions, we need an optimisation algorithm to find those candidates close to the actual Pareto front, and to use them to find even better ones.

But first, we need to calculate the points on the Pareto front of a given population, that is, all the candidate solutions that are not dominated by any other solutions (the green points in the figure above). The obvious algorithm (for each candidate solution, test it against all other solutions for all objectives) is rather inefficient, being

*O*(

*MN*

^{2}), where

*M*is the number of objectives, and

*N*is the number of solutions to test. Deb et al (2000) give a more efficient algorithm:

We can code this up in python as follows (with comments showing how it relates to the algorithm above):

def fast_nondominated_sort_single_front(pop): # pop = list of individuals # individual of form { 'state': (s1,s2,s3,...), 'fitness':(f1,f2,f3,...) } # pfront = list of individuals on the calculated "pareto front" pfront = [ pop[0] ] # P' = {1} for pi,p in enumerate(pop): # for each p in P and p notin P' if pi == 0 : continue # (so not the first element) pfront = pfront + [ p ] # P' = P' cup {p} # make a copy to iterate over, because pfront is being modified; # don't need the last item, which is p (makes q neq p below True) pfrontcopy = pfront[:-1] pf = p['fitness'] for qi,q in enumerate(pfrontcopy): # for each q in P' and q neq p qf = q['fitness'] if dominates_min(pf,qf): # if p dom q pfront.remove(q) # then P' = P' \ {q} elif dominates_min(qf,pf): # else if q dom p del pfront[-1] # then P' = P' \ {p} break # don't have to check any more qs as p already gone return(pfront)Once we have the front, we could remove it from the population, and calculate the next front, and so on. This is useful in an optimisation algorithm, to find less fit (not on the current best front) but still possibly good solutions, for use in building even better ones.

The multiple front calculation is as follows:

def fast_nondominated_sort(pop): # find a list of ever decreasing fronts # pop = list of individuals # pfrontlist = list of fronts = list of lists of individuals popcopy = pop[:] pfrontlist = [] while popcopy: pfront = fast_nondominated_sort_single_front(popcopy) pfrontlist += [pfront] # remove the found pfront from the pop popcopy = [ ind for ind in popcopy if ind not in pfront ] # check that no-one has been lost assert len(pop) == len([item for pfront in pfrontlist for item in pfront]) return(pfrontlist)Given some population of candidate solutions, we can plot out the relevant fronts so calculated (plotting code always seems much more complicated than the actual algorithms!):

import matplotlib.pyplot as plt def plot_fronts(pfrontlist): # pfrontlist = list of fronts; each front is a list of individuals fig = plt.figure() ax1 = fig.add_subplot(111) # one colour per front colors = matplotlib.cm.rainbow(np.linspace(0, 1, len(pfrontlist))) # iterate backwards, to draw better fronts on top of less good ones for i in range(len(pfrontlist)-1, -1, -1) : pfront = pfrontlist[i] # sort members of front in order of fitness; draw a line along the front data = sorted([ pf['fitness'] for pf in pfront ]) xs = [ i[0] for i in data ] ys = [ i[1] for i in data ] ax11.plot(xs, ys, ':o', color=colors[i], mew=0) plt.show()This gives a plot like:

A sequence of fronts, found by finding the Pareto front of a population of candidate solutions, removing it from the population, finding the front of the remaining candidates, and so on. |

In a later post, I will go through the rest of the Deb et al (2000) algorithm, and show how they incorporate this front-finding into a full-blown multi-objective optimiser.

### Reference

Deb, Kalyanmoy; Agrawal, Samir; Pratap, Amrit; Meyarivan, T. (2000) A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. In

*Parallel Problem Solving from Nature, PPSN VI*. LNCS**1917**:849–858. Springer. doi:10.1007/3-540-45356-3_83
## No comments:

## Post a Comment