Skip to content

Documentation

Jump to bottom
Debabrata Acharya edited this page Feb 6, 2021 · 20 revisions

Welcome to NSGA-II v3 Documentation.

The NSGA2 class

com.debacharya.nsgaii.NSGA2

An instance of this class is used to run the NSGA-II algorithm. This class defines the core algorithm of NSGA-II. Calling the run() method on an instance of NSGA2 gets the algorithm running. It requires an instance of Configuration class to run, which describes all the configuration required for that run. The Configuration class is described later in the documentation.

Constructors

NSGA2 has two constructors:

  • NSGA2(): creates an instance of NSGA2 with a default configuration object that provides a default implementation of every plugin needed by the algorithm to run. While this constructor is not of much use to the user, but this helps run a proof-of-concept for the algorithm itself with all the default plugins filled in. To run the PoC, the user can simply run
(new NSGA2()).run();
  • NSGA2(Configuration): creates an instance of NSGA2 by taking a configuration object as parameter. This will be usually the most useful constructor for NSGA2 for the user. The user can configure his / her plugins to the liking and then pass it to the NSGA2 constructor for the algorithm to be setup according to the users needs.

Methods

  • run(): Runs the actual NSGA-II core algorithm. It returns the Pareto Front or the last child as a Population object. This needs to be called on an instance of NSGA2 to run the actual algorithm.

  • preparePopulation(Population): This method takes a Population object and basically performs all the operations needed to be performed on the parent population in each generation. It executes the following operations on the population instance in order.

    • It calculates the objective values of all the chromosomes in the population based on the objective functions set in the Configuration instance.
    • It then runs fast non-dominated sort on the population as defined in NSGA-II paper [DOI: 10.1109/4235.996017] Section III Part A.
    • It then assigns crowding distance to each chromosome.
    • Finally, it sorts the chromosomes in the population based on its assigned rank.

  • getChildFromCombinedPopulation(Population): This method takes a Population of size 2N (a combination of parent and child, both of size N, according to the originally proposed algorithm) and returns a new Population instance of size N by selecting the first N chromosomes from the combined population, based on their rank. If it has to choose M chromosomes of rank N such that M > N, it then sorts the M chromosomes based on their crowding distance.

  • fastNonDominatedSort(Population): This is an implementation of the fast non-dominated sorting algorithm as defined in the NSGA-II paper [DOI: 10.1109/4235.996017] Section III Part A. It takes as a parameter, the population object that needs to undergo fast non-dominated sorting algorithm.

  • crowdingDistanceAssignment(Population): This is the implementation of the crowding distance assignment algorithm as defined in the NSGA-II paper [DOI: 10.1109/4235.996017] Section III Part B. this ensures diversity preservation. It returns the the population whose crowding distances are tor be calculated.

  • dominates(Chromosome, Chromosome): This method checks whether one chromosome dominates the other chromosome or not. While the actual domination logic has been described in the isDominant(Chromosome, Chromosome) method, the dominates(Chromosome, Chromosome) method returns one among the three values based on whether chromosome1 is dominant over chromosome2, or is inferior to chromosome2 or whether both of them are non-dominating, by returning com.debacharya.nsgaii.NSGA2.DOMINANT, com.debacharya.nsgaii.NSGA2.INFERIOR or com.debacharya.nsgaii.NSGA2.NON_DOMINATED respectively.

  • isDominant(Chromosome, Chromosome): This method checks whether chromosome1 dominates chromosome2. Requires that none of the values of the objective function values of chromosome1 is smaller than the values of the objective function values of chromosome2 and at least one of the values of the objective function of chromosome1 is greater than the corresponding value of the objective function of chromosome2. Returns boolean logic whether chromosome1 dominates chromosome2.

The Configuration class

com.debacharya.nsgaii.Configuration

The Configuration class is used to setup the runtime settings of the NSGA-II algorithm. Since a lot of the settings within the algorithm can be changed, this class manages them all. An instance of this class is needed to be setup before creating an instance of NSGA2 class or running the algorithm. Changing settings of an instance of a Configuration class between runs will also reflect immediately on the result. This means that, if required (but almost rarely), the configuration of the algorithm within the same run can be changed dynamically.

in progress

Alleles

in progress

Crossover

in progress

Mutation

The GeneticCodeProducer interface

com.debacharya.nsgaii.plugin.GeneticCodeProducer

The GeneticCodeProducer interface is used to create a genetic code, which in turn is used to encode a Chromosome for the algorithm to use. It has only one method, produce, which takes as its argument, the length of the genetic code to be produced.

com.debacharya.nsgaii.plugin.PopulationProducer

Methods

  • produce(int): This method is used to create a list of AbstractAlleles which represents the genetic code of a Chromosome and has a size equal to the length argument passed as parameter. It takes, as a parameter, the length argument, which is of type int, which represents the length of the list of AbstractAlleles to be created. This should be the length of the genetic code. It returns a list of AbstractAlleles whose size should be equal to the length argument.

The PopulationProducer interface

The PopulationProducer interface is used to produce a population of chromosomes for the algorithm to use. It has only one method, produce() that produces a fixed amount of chromosomes using the GeneticCodeProvider, each having a fixed chromosome length. It also integrates a FitnessCalculator which can be used to provide any extra computation required to perform during the creation of the population. Note that any concrete implementation of this interface is used to only to generate the initial parent population at the very beginning of the algorithm. For all consecutive population production at later generations, the ChildPopulationProducer interface is used.

Methods

  • produce(int, int, GeneticCodeProducer, FitnessCalculator): This method is used to create a list of AbstractAlleles which represents the genetic code of a Chromosome and has a size equal to the length argument passed as parameter. It takes, as a parameter, the length argument, which is of type int, which represents the length of the list of AbstractAlleles to be created. This should be the length of the genetic code. It returns a list of AbstractAlleles whose size should be equal to the length argument. It takes as arguments, populationSize, which is the size of the population, i.e., the number of chromosomes to be created, chromosomeLength, which is the length of each chromosome to be created, i.e., the length of the genetic code, geneticCodeProducer which is the GeneticCodeProducer object used to generate the genetic code of each chromosome and fitnessCalculator which is the FitnessCalculator object to carry out any additional computation on the chromosome. It returns a Population with populationSize number of chromosomes.

The ChildPopulationProducer interface

The ChildPopulationProducer interface is used to produce a population of chromosomes for the algorithm to use. It has only one method, produce() that produces a child population from a provided parent population. For every child population, a fixed amount of chromosomes is created by executing the provided crossover and mutation operators on the parent population. This interface is used to generate every child population at each generation. Note that the initial parent population is generated using the PopulationProducer interface.

Methods

  • produce(Population, AbstractCrossover, AbstractMutation, int): This method generates a child Population, which is a collection of Chromosomes equal to provided populationSize, from the given parentPopulation. The child chromosomes are created by executing the provided crossover and mutation operators on the parentPopulation. A new Population is hence created. It takes as arguments, parentPopulation, which is the population from which the child population is to be generated, crossover, which is the crossover operator which is a concrete implementation of AbstractCrossover, mutation, which is the mutation operator which is a concrete implementation of AbstractMutation and populationSize, which is the size of the population, i.e., the number of child chromosomes to be created. It returns a new child Population, with populationSize number of chromosomes.

in progress

Clone this wiki locally