* The object contains two items: an array of floating point values representing * the various multiple fitnesses, and a flag (maximize) indicating whether * higher is considered better. By default, isIdealFitness() always returns * false; you might want to override that, though it'd be unusual -- what is the * ideal fitness from the perspective of a pareto front? * *
* The object also contains maximum and minimum fitness values suggested for the * problem, on a per-objective basis. By default the maximum values are all 1.0 * and the minimum values are all 0.0, but you can change these. Note that * maximum does not mean "best" unless maximize is true. * *
The class also contains utility methods or computing pareto dominance, * Pareto Fronts and Pareto Front Ranks, and distance in multiobjective space. * The default comparison operators use Pareto Dominance, though this is often * overridden by subclasses. * *
The fitness() method returns the maximum of the fitness values, which is * clearly nonsensical: you should not be using this method. * *
Subclasses of this class may add certain auxiliary fitness measures which * are printed out by MultiObjectiveStatistics along with the multiple objectives. * To have these values printed out, override the getAuxiliaryFitnessNames() * and getAuxiliaryFitnessValues() methods. * *
* Parameters
*
| base.num-objectives * (else)multi.num-objectives * int >= 1 |
* (the number of fitnesses in the objectives array) | *
| base.maximize * bool = true (default) or false |
* (are higher values considered "better"?) * |
* Default Base
* multi.fitness
*
* @author Sean Luke
* @version 1.1
*/
public class MultiObjectiveFitness extends Fitness
{
public static final String MULTI_FITNESS_POSTAMBLE = "[";
public static final String FITNESS_POSTAMBLE = "]";
/** parameter for size of objectives */
public static final String P_NUMOBJECTIVES = "num-objectives";
/** parameter for max fitness values */
public static final String P_MAXOBJECTIVES = "max";
/** parameter for min fitness values */
public static final String P_MINOBJECTIVES = "min";
/** Is higher better? */
public static final String P_MAXIMIZE = "maximize";
/** Desired maximum fitness values. By default these are 1.0. Shared. */
public float[] maxObjective;
/** Desired minimum fitness values. By default these are 0.0. Shared. */
public float[] minObjective;
/** The various fitnesses. */
protected float[] objectives; // values range from 0 (worst) to 1 INCLUSIVE
protected boolean maximize = true;
/** Returns auxilliary fitness value names to be printed by the statistics object.
By default, an empty array is returned, but various algorithms may override this to provide additional columns.
*/
public String[] getAuxilliaryFitnessNames() { return new String[] { }; }
/** Returns auxilliary fitness values to be printed by the statistics object.
By default, an empty array is returned, but various algorithms may override this to provide additional columns.
*/
public double[] getAuxilliaryFitnessValues() { return new double[] { }; }
public boolean isMaximizing()
{
return maximize;
}
public int getNumObjectives() { return objectives.length; }
/**
* Returns the objectives as an array. Note that this is the *actual array*.
* Though you could set values in this array, you should NOT do this --
* rather, set them using setObjectives().
*/
public float[] getObjectives()
{
return objectives;
}
public float getObjective(int i)
{
return objectives[i];
}
public void setObjectives(final EvolutionState state, float[] newObjectives)
{
if (newObjectives == null)
{
state.output.fatal("Null objective array provided to MultiObjectiveFitness.");
}
if (newObjectives.length != objectives.length)
{
state.output.fatal("New objective array length does not match current length.");
}
for (int i = 0; i < newObjectives.length; i++)
{
float _f = newObjectives[i];
if (_f == Float.POSITIVE_INFINITY || _f == Float.NEGATIVE_INFINITY || Float.isNaN(_f))
{
state.output.warning("Bad objective #" + i + ": " + _f + ", setting to worst value for that objective.");
if (maximize)
newObjectives[i] = minObjective[i];
else
newObjectives[i] = maxObjective[i];
}
}
objectives = newObjectives;
}
public Parameter defaultBase()
{
return MultiObjectiveDefaults.base().push(P_FITNESS);
}
public Object clone()
{
MultiObjectiveFitness f = (MultiObjectiveFitness) (super.clone());
f.objectives = (float[]) (objectives.clone()); // cloning an array
// note that we do NOT clone max and min fitness -- they're shared
return f;
}
/**
* Returns the Max() of objectives, which adheres to Fitness.java's protocol
* for this method. Though you should not rely on a selection or statistics
* method which requires this.
*/
public float fitness()
{
float fit = objectives[0];
for (int x = 1; x < objectives.length; x++)
if (fit < objectives[x])
fit = objectives[x];
return fit;
}
/**
* Sets up. This must be called at least once in the prototype before
* instantiating any fitnesses that will actually be used in evolution.
*/
public void setup(EvolutionState state, Parameter base)
{
super.setup(state, base); // unnecessary really
Parameter def = defaultBase();
int numFitnesses;
numFitnesses = state.parameters.getInt(base.push(P_NUMOBJECTIVES), def.push(P_NUMOBJECTIVES), 0);
if (numFitnesses <= 0)
state.output.fatal("The number of objectives must be an integer >= 1.", base.push(P_NUMOBJECTIVES), def.push(P_NUMOBJECTIVES));
maximize = state.parameters.getBoolean(base.push(P_MAXIMIZE), def.push(P_MAXIMIZE), true);
objectives = new float[numFitnesses];
maxObjective = new float[numFitnesses];
minObjective = new float[numFitnesses];
for (int i = 0; i < numFitnesses; i++)
{
// load default globals
minObjective[i] = state.parameters.getFloatWithDefault(base.push(P_MINOBJECTIVES), def.push(P_MINOBJECTIVES), 0.0f);
maxObjective[i] = state.parameters.getFloatWithDefault(base.push(P_MAXOBJECTIVES), def.push(P_MAXOBJECTIVES), 1.0f);
// load specifics if any
minObjective[i] = state.parameters.getFloatWithDefault(base.push(P_MINOBJECTIVES).push("" + i), def.push(P_MINOBJECTIVES).push("" + i), minObjective[i]);
maxObjective[i] = state.parameters.getFloatWithDefault(base.push(P_MAXOBJECTIVES).push("" + i), def.push(P_MAXOBJECTIVES).push("" + i), maxObjective[i]);
// test for validity
if (minObjective[i] >= maxObjective[i])
state.output.error("For objective " + i + "the min fitness must be strictly less than the max fitness.");
}
state.output.exitIfErrors();
}
/**
* Returns true if this fitness is the "ideal" fitness. Default always
* returns false. You may want to override this.
*/
public boolean isIdealFitness()
{
return false;
}
/**
* Returns true if I'm equivalent in fitness (neither better nor worse) to
* _fitness. The rule I'm using is this: If one of us is better in one or
* more criteria, and we are equal in the others, then equivalentTo is
* false. If each of us is better in one or more criteria each, or we are
* equal in all criteria, then equivalentTo is true. Multiobjective optimization algorithms may
* choose to override this to do something else.
*/
public boolean equivalentTo(Fitness _fitness)
{
MultiObjectiveFitness other = (MultiObjectiveFitness) _fitness;
boolean abeatsb = false;
boolean bbeatsa = false;
if (maximize != other.maximize)
throw new RuntimeException(
"Attempt made to compare two multiobjective fitnesses; but one expects higher values to be better and the other expectes lower values to be better.");
if (objectives.length != other.objectives.length)
throw new RuntimeException("Attempt made to compare two multiobjective fitnesses; but they have different numbers of objectives.");
if (maximize)
{
for (int x = 0; x < objectives.length; x++)
{
if (objectives[x] > other.objectives[x])
abeatsb = true;
if (objectives[x] < other.objectives[x])
bbeatsa = true;
if (abeatsb && bbeatsa)
return true;
}
}
else
// lower is better
{
for (int x = 0; x < objectives.length; x++)
{
if (objectives[x] < other.objectives[x])
abeatsb = true;
if (objectives[x] > other.objectives[x])
bbeatsa = true;
if (abeatsb && bbeatsa)
return true;
}
}
if (abeatsb || bbeatsa)
return false;
return true;
}
/**
* Returns true if I'm better than _fitness. The DEFAULT rule I'm using is this: if
* I am better in one or more criteria, and we are equal in the others, then
* betterThan is true, else it is false. Multiobjective optimization algorithms may
* choose to override this to do something else.
*/
public boolean betterThan(Fitness fitness)
{
return paretoDominates((MultiObjectiveFitness)fitness);
}
/**
* Returns true if I'm better than _fitness. The rule I'm using is this: if
* I am better in one or more criteria, and we are equal in the others, then
* betterThan is true, else it is false.
*/
public boolean paretoDominates(MultiObjectiveFitness other)
{
boolean abeatsb = false;
if (maximize != other.maximize)
throw new RuntimeException(
"Attempt made to compare two multiobjective fitnesses; but one expects higher values to be better and the other expectes lower values to be better.");
if (objectives.length != other.objectives.length)
throw new RuntimeException("Attempt made to compare two multiobjective fitnesses; but they have different numbers of objectives.");
if (maximize)
{
for (int x = 0; x < objectives.length; x++)
{
if (objectives[x] > other.objectives[x])
abeatsb = true;
else if (objectives[x] < other.objectives[x])
return false;
}
}
else
{
for (int x = 0; x < objectives.length; x++)
{
if (objectives[x] < other.objectives[x])
abeatsb = true;
else if (objectives[x] > other.objectives[x])
return false;
}
}
return abeatsb;
}
// Remove an individual from the ArrayList, shifting the topmost
// individual in his place
static void yank(int val, ArrayList list)
{
int size = list.size();
list.set(val, list.get(size - 1));
list.remove(size - 1);
}
/**
* Divides an array of Individuals into the Pareto front and the "nonFront" (everyone else).
* The Pareto front is returned. You may provide ArrayLists for the front and a nonFront.
* If you provide null for the front, an ArrayList will be created for you. If you provide
* null for the nonFront, non-front individuals will not be added to it. This algorithm is
* O(n^2).
*/
public static ArrayList partitionIntoParetoFront(Individual[] inds, ArrayList front, ArrayList nonFront)
{
if (front == null)
front = new ArrayList();
// put the first guy in the front
front.add(inds[0]);
// iterate over all the remaining individuals
for (int i = 1; i < inds.length; i++)
{
Individual ind = (Individual) (inds[i]);
boolean noOneWasBetter = true;
int frontSize = front.size();
// iterate over the entire front
for (int j = 0; j < frontSize; j++)
{
Individual frontmember = (Individual) (front.get(j));
// if the front member is better than the individual, dump the individual and go to the next one
if (((MultiObjectiveFitness) (frontmember.fitness)).paretoDominates((MultiObjectiveFitness) (ind.fitness)))
{
if (nonFront != null) nonFront.add(ind);
noOneWasBetter = false;
break; // failed. He's not in the front
}
// if the individual was better than the front member, dump the front member. But look over the
// other front members (don't break) because others might be dominated by the individual as well.
else if (((MultiObjectiveFitness) (ind.fitness)).paretoDominates((MultiObjectiveFitness) (frontmember.fitness)))
{
yank(j, front);
// a front member is dominated by the new individual. Replace him
frontSize--; // member got removed
j--; // because there's another guy we now need to consider in his place
if (nonFront != null) nonFront.add(frontmember);
}
}
if (noOneWasBetter)
front.add(ind);
}
return front;
}
/** Divides inds into pareto front ranks (each an ArrayList), and returns them, in order,
stored in an ArrayList. */
public static ArrayList partitionIntoRanks(Individual[] inds)
{
Individual[] dummy = new Individual[0];
ArrayList frontsByRank = new ArrayList();
while(inds.length > 0)
{
ArrayList front = new ArrayList();
ArrayList nonFront = new ArrayList();
MultiObjectiveFitness.partitionIntoParetoFront(inds, front, nonFront);
// build inds out of remainder
inds = (Individual[]) nonFront.toArray(dummy);
frontsByRank.add(front);
}
return frontsByRank;
}
/**
* Returns the sum of the squared difference between two Fitnesses in Objective space.
*/
public double sumSquaredObjectiveDistance(MultiObjectiveFitness other)
{
double s = 0;
for (int i = 0; i < objectives.length; i++)
{
double a = (objectives[i] - other.objectives[i]);
s += a * a;
}
return s;
}
/**
* Returns the Manhattan difference between two Fitnesses in Objective space.
*/
public double manhattanObjectiveDistance(MultiObjectiveFitness other)
{
double s = 0;
for (int i = 0; i < objectives.length; i++)
{
s += Math.abs(objectives[i] - other.objectives[i]);
}
return s;
}
public String fitnessToString()
{
String s = FITNESS_PREAMBLE + MULTI_FITNESS_POSTAMBLE;
for (int x = 0; x < objectives.length; x++)
{
if (x > 0)
s = s + " ";
s = s + Code.encode(objectives[x]);
}
s = s + " ";
s = s + Code.encode(maximize);
return s + FITNESS_POSTAMBLE;
}
public String fitnessToStringForHumans()
{
String s = FITNESS_PREAMBLE + MULTI_FITNESS_POSTAMBLE;
for (int x = 0; x < objectives.length; x++)
{
if (x > 0)
s = s + " ";
s = s + objectives[x];
}
s = s + " ";
s = s + (maximize ? "max" : "min");
return s + FITNESS_POSTAMBLE;
}
public void readFitness(final EvolutionState state, final LineNumberReader reader) throws IOException
{
DecodeReturn d = Code.checkPreamble(FITNESS_PREAMBLE + MULTI_FITNESS_POSTAMBLE, state, reader);
for (int x = 0; x < objectives.length; x++)
{
Code.decode(d);
if (d.type != DecodeReturn.T_FLOAT)
state.output.fatal("Reading Line " + d.lineNumber + ": " + "Bad Fitness (objectives value #" + x + ").");
objectives[x] = (float) d.d;
}
Code.decode(d);
if (d.type != DecodeReturn.T_BOOLEAN)
state.output.fatal("Reading Line " + d.lineNumber + ": " + "Information missing about whether higher is better");
maximize = (boolean) (d.l != 0);
}
public void writeFitness(final EvolutionState state, final DataOutput dataOutput) throws IOException
{
dataOutput.writeInt(objectives.length);
for (int x = 0; x < objectives.length; x++)
dataOutput.writeFloat(objectives[x]);
dataOutput.writeBoolean(maximize);
}
public void readFitness(final EvolutionState state, final DataInput dataInput) throws IOException
{
int len = dataInput.readInt();
if (objectives == null || objectives.length != len)
objectives = new float[len];
for (int x = 0; x < objectives.length; x++)
objectives[x] = dataInput.readFloat();
maximize = dataInput.readBoolean();
}
}