Fitness-based NSGA-II Example

FitnessBasedNSGAIIExample.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Properties;

import org.moeaframework.Executor;
import org.moeaframework.algorithm.AbstractEvolutionaryAlgorithm;
import org.moeaframework.analysis.plot.Plot;
import org.moeaframework.core.Algorithm;
import org.moeaframework.core.EpsilonBoxDominanceArchive;
import org.moeaframework.core.EpsilonBoxEvolutionaryAlgorithm;
import org.moeaframework.core.Initialization;
import org.moeaframework.core.NondominatedPopulation;
import org.moeaframework.core.NondominatedSortingPopulation;
import org.moeaframework.core.PRNG;
import org.moeaframework.core.Population;
import org.moeaframework.core.Problem;
import org.moeaframework.core.Selection;
import org.moeaframework.core.Solution;
import org.moeaframework.core.Variation;
import org.moeaframework.core.comparator.ChainedComparator;
import org.moeaframework.core.comparator.CrowdingComparator;
import org.moeaframework.core.comparator.DominanceComparator;
import org.moeaframework.core.comparator.ParetoDominanceComparator;
import org.moeaframework.core.fitness.AdditiveEpsilonIndicatorFitnessEvaluator;
import org.moeaframework.core.fitness.FitnessBasedArchive;
import org.moeaframework.core.fitness.HypervolumeFitnessEvaluator;
import org.moeaframework.core.fitness.IndicatorFitnessEvaluator;
import org.moeaframework.core.operator.RandomInitialization;
import org.moeaframework.core.operator.TournamentSelection;
import org.moeaframework.core.spi.AlgorithmFactory;
import org.moeaframework.core.spi.AlgorithmProvider;
import org.moeaframework.core.spi.OperatorFactory;
import org.moeaframework.util.TypedProperties;

public class FitnessBasedNSGAIIExample {
	
	public static class FitnessBasedNSGAII extends AbstractEvolutionaryAlgorithm {
	
		private final Selection selection;
		
		private final Variation variation;
		
		public FitnessBasedNSGAII(Problem problem, NondominatedSortingPopulation population,
				FitnessBasedArchive archive, Selection selection,
				Variation variation, Initialization initialization) {
			super(problem, population, archive, initialization);
			this.selection = selection;
			this.variation = variation;
		}
		
		@Override
		public void iterate() {
			NondominatedSortingPopulation population = getPopulation();
			FitnessBasedArchive archive = getArchive();
			Population offspring = new Population();
			int populationSize = population.size();
		
			if (selection == null) {
				// recreate the original NSGA-II implementation using binary
				// tournament selection without replacement; this version works by
				// maintaining a pool of candidate parents.
				LinkedList<Solution> pool = new LinkedList<Solution>();
				
				DominanceComparator comparator = new ChainedComparator(
						new ParetoDominanceComparator(),
						new CrowdingComparator());
				
				while (offspring.size() < populationSize) {
					// ensure the pool has enough solutions
					while (pool.size() < 2*variation.getArity()) {
						List<Solution> poolAdditions = new ArrayList<Solution>();
						
						for (Solution solution : population) {
							poolAdditions.add(solution);
						}
						
						PRNG.shuffle(poolAdditions);
						pool.addAll(poolAdditions);
					}
					
					// select the parents using a binary tournament
					Solution[] parents = new Solution[variation.getArity()];
					
					for (int i = 0; i < parents.length; i++) {
						parents[i] = TournamentSelection.binaryTournament(
								pool.removeFirst(),
								pool.removeFirst(),
								comparator);
					}
					
					// evolve the children
					offspring.addAll(variation.evolve(parents));
				}
			} else {
				// run NSGA-II using selection with replacement; this version allows
				// using custom selection operators
				while (offspring.size() < populationSize) {
					Solution[] parents = selection.select(variation.getArity(),
							population);
		
					offspring.addAll(variation.evolve(parents));
				}
			}
		
			evaluateAll(offspring);
		
			if (archive != null) {
				archive.addAll(offspring);
			}
		
			population.addAll(offspring);
			population.truncate(populationSize);
		}
		
		@Override
		public FitnessBasedArchive getArchive() {
			return (FitnessBasedArchive)super.getArchive();
		}
		
		@Override
		public NondominatedSortingPopulation getPopulation() {
			return (NondominatedSortingPopulation)super.getPopulation();
		}
		
	}
	
	public static class FitnessBasedNSGAIIProvider extends AlgorithmProvider {

		@Override
		public Algorithm getAlgorithm(String name, Properties properties, Problem problem) {
			if (name.equalsIgnoreCase("FitnessBasedNSGAII")) {
				TypedProperties typedProperties = new TypedProperties(properties);

				int populationSize = (int)typedProperties.getDouble("populationSize", 100);
				int archiveSize = (int)typedProperties.getDouble("archiveSize", 100);
				String indicator = typedProperties.getString("indicator", "hypervolume");
				
				Initialization initialization = new RandomInitialization(problem, populationSize);

				NondominatedSortingPopulation population = new NondominatedSortingPopulation();
				
				IndicatorFitnessEvaluator fitnessEvaluator = null;

				if ("hypervolume".equals(indicator)) {
					fitnessEvaluator = new HypervolumeFitnessEvaluator(problem);
				} else if ("epsilon".equals(indicator)) {
					fitnessEvaluator = new AdditiveEpsilonIndicatorFitnessEvaluator(problem);
				} else {
					throw new IllegalArgumentException("invalid indicator: " + indicator);
				}

				FitnessBasedArchive archive = new FitnessBasedArchive(fitnessEvaluator, archiveSize);

				TournamentSelection selection = null;
				
				if (typedProperties.getBoolean("withReplacement", true)) {
					selection = new TournamentSelection(2, new ChainedComparator(
							new ParetoDominanceComparator(),
							new CrowdingComparator()));
				}

				Variation variation = OperatorFactory.getInstance().getVariation(null, properties, problem);

				return new FitnessBasedNSGAII(problem, population, archive, selection, variation, initialization);
			} else {
				return null;
			}
		}
		
	}
	
	public static void main(String[] args) {
		// Register our provider that constructs the fitness-based NSGAII implementation
		AlgorithmFactory.getInstance().addProvider(new FitnessBasedNSGAIIProvider());
		
		// Run an experiment
		Executor executor = new Executor()
				.withProblem("DTLZ2_2")
				.withMaxEvaluations(10000);
		
		NondominatedPopulation originalResult = executor
				.withAlgorithm("NSGAII")
				.run();
		
		NondominatedPopulation fitnessResult = executor
				.withAlgorithm("FitnessBasedNSGAII")
				.withProperty("indicator", "hypervolume") // "epsilon" or "hypervolume"
				.run();
		
		// Display the result
		new Plot()
			.add("NSGAII", originalResult)
			.add("FitnessBasedNSGAII", fitnessResult)
			.show();
	}

}