Package org.moeaframework.core.population

Class AdaptiveGridArchive

java.lang.Object
org.moeaframework.core.population.Population
org.moeaframework.core.population.NondominatedPopulation
org.moeaframework.core.population.AdaptiveGridArchive
All Implemented Interfaces:
Iterable<Solution>, Copyable<Population>, Stateful, Displayable, Formattable<Solution>
public class AdaptiveGridArchive extends NondominatedPopulation
Adaptive grid archive. Divides objective space into a number of grid cells, maintaining a count of the number of solutions within each grid cell. When the size of the archive exceeds a specified capacity, a solution from the most crowded grid cell is selected and removed from the archive.

This implementation currently stores the density of each grid cell in an array. As such, pow(numberOfDivisions, numberOfObjectives) can not exceed the storage capacity of an array, or pow(2, 32). We may consider at some point using sparse arrays to remove this limitation.

References:

  1. Knowles, J.D. and Corne, D.W., "Approximating the Nondominated Front using the Pareto Archived Evolution Strategy," Evolutionary Computation, vol. 8, no. 2, pp. 149-172, 2000.
  2. Knowles, J.D. and Corne, D.W., "Properties of an Adaptive Archiving for Storing Nondominated Vectors," IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 100-116, 2003.

  • Field Details

    • capacity

      protected final int capacity
      The maximum capacity of this archive.

    • problem

      protected final Problem problem
      The problem for which this archive is used.

    • numberOfDivisions

      protected final int numberOfDivisions
      The number of divisions this archive uses to split each objective.

    • minimum

      protected double[] minimum
      The minimum objective value for each dimension.

    • maximum

      protected double[] maximum
      The maximum objective value for each dimension.

    • density

      protected Map<Integer,Integer> density
      The number of solutions in each grid cell.

  • Constructor Details

    • AdaptiveGridArchive

      public AdaptiveGridArchive(int capacity, Problem problem, int numberOfDivisions)
      Constructs an adaptive grid archive with the specified capacity with the specified number of divisions along each objective.
      Parameters:
      capacity - the capacity of this archive
      problem - the problem for which this archive is used
      numberOfDivisions - the number of divisions this archive uses to split each objective
      Throws:
      FrameworkException - if pow(numberOfDivisions, numberOfObjectives) exceeds the storage capacity of an array

  • Method Details

    • getMaximumBisections

      public static int getMaximumBisections(int numberOfObjectives)
      Calculates the largest possible value for the bisections parameter. This is limited by the available Java heap size and the maximum integer value (2^31-1), whichever is smaller.
      Parameters:
      numberOfObjectives - the number of objectives
      Returns:
      the maximum number of bisections

    • getBisections

      public int getBisections()
      Returns the equivalent number of bisections to produce the number of divisions.
      Returns:
      the number of bisections

    • getCapacity

      public int getCapacity()
      Returns the maximum number of solutions stored in this archive.
      Returns:
      the maximum number of solutions stored in this archive

    • getNumberOfDivisions

      public int getNumberOfDivisions()
      Returns the number of divisions this archive uses to split each objective.
      Returns:
      the number of divisions this archive uses to split each objective

    • getProblem

      public Problem getProblem()
      Returns the problem for which this archive is used.
      Returns:
      the problem for which this archive is used

    • add

      public boolean add(Solution solution)
      Description copied from class: NondominatedPopulation
      If newSolution is dominates any solution or is non-dominated with all solutions in this population, the dominated solutions are removed and newSolution is added to this population. Otherwise, newSolution is dominated and is not added to this population.
      Overrides:
      add in class NondominatedPopulation
      Parameters:
      solution - the solution to be added
      Returns:
      true if the population was modified as a result of this method; false otherwise.

    • remove

      public void remove(int index)
      Description copied from class: Population
      Removes the solution at the specified index from this population.
      Overrides:
      remove in class Population
      Parameters:
      index - the index of the solution to be removed

    • remove

      public boolean remove(Solution solution)
      Description copied from class: Population
      Removes the specified solution from this population, if present.
      Overrides:
      remove in class Population
      Parameters:
      solution - the solution to be removed
      Returns:
      true if this population was modified as a result of this method; false otherwise

    • clear

      public void clear()
      Description copied from class: Population
      Removes all solutions from this population.
      Overrides:
      clear in class Population

    • findDensestCell

      protected int findDensestCell()
      Returns the index of the grid cell with the largest density.
      Returns:
      the index of the grid cell with the largest density

    • pickSolutionFromDensestCell

      protected Solution pickSolutionFromDensestCell()
      Returns a solution residing in the densest grid cell. If there are more than one such solution or multiple cells with the same density, the first solution encountered is returned.
      Returns:
      a solution residing in the densest grid cell

    • adaptGrid

      protected void adaptGrid()
      Computes new lower and upper bounds and recalculates the densities of each grid cell.

    • findIndex

      public int findIndex(Solution solution)
      Returns the index of the specified solution in this adaptive grid archive, or -1 if the solution is not within the current lower and upper bounds.
      Parameters:
      solution - the specified solution
      Returns:
      the index of the specified solution in this adaptive grid archive, or -1 if the solution is not within the current lower and upper bounds

    • getDensity

      public int getDensity(int index)
      Returns the density of the solution at the given index.
      Parameters:
      index - the solution index
      Returns:
      the density of the solution at the given index

    • copy

      public AdaptiveGridArchive copy()
      Description copied from class: Population
      Returns a copy of this population. This can be thought of as a "deep copy", which creates a copy of both the population itself and copies of the individual solutions in the population. Consequently, the returned copy is completely independent, such that any modifications to the contents or order will not impact the original.

      Since creating such a "deep copy" can be expensive, prefer using the constructor Population(Iterable) or Population.addAll(Iterable) whenever possible. These alternatives are useful when filtering or reordering the solutions, but the solutions themselves are left unchanged.

      Specified by:
      copy in interface Copyable<Population>
      Overrides:
      copy in class NondominatedPopulation
      Returns:
      the copy of this population

    • saveState

      public void saveState(ObjectOutputStream stream) throws IOException
      Description copied from interface: Stateful
      Writes the state of this object to the stream. The order that objects are written to the stream is important. We recommend first calling super.saveState(stream) followed by writing each field.
      Specified by:
      saveState in interface Stateful
      Overrides:
      saveState in class Population
      Parameters:
      stream - the stream
      Throws:
      IOException - if an I/O error occurred

    • loadState

      public void loadState(ObjectInputStream stream) throws IOException, ClassNotFoundException
      Description copied from interface: Stateful
      Loads the state of this object from the stream. The order for reading objects from the stream must match the order they are written to the stream in Stateful.saveState(ObjectOutputStream).
      Specified by:
      loadState in interface Stateful
      Overrides:
      loadState in class Population
      Parameters:
      stream - the stream
      Throws:
      IOException - if an I/O error occurred
      ClassNotFoundException - if the stream referenced a class that is not defined