Package smile.gap

Interface Selection

public interface Selection
The way to select chromosomes from the population as parents to crossover.

  • Method Summary

    Modifier and Type
    Method
    Description
    <T extends Chromosome>
    T
    apply(T[] population)
    Select a chromosome with replacement from the population based on their fitness.
    static Selection
    Rank()
    Rank Selection.
    static Selection
    RouletteWheel()
    Roulette Wheel Selection, also called fitness proportionate selection.
    static Selection
    ScaledRouletteWheel()
    Scaled Roulette Wheel Selection.
    static Selection
    Tournament(int size, double probability)
    Tournament Selection.

  • Method Details

    • apply

      <T extends Chromosome> T apply(T[] population)
      Select a chromosome with replacement from the population based on their fitness. Note that the population should be in ascending order in terms of fitness.
      Type Parameters:
      T - the type of Chromosome.
      Parameters:
      population - the population to select from.
      Returns:
      the chromosomes as parents to crossover.

    • RouletteWheel

      static Selection RouletteWheel()
      Roulette Wheel Selection, also called fitness proportionate selection. Parents are selected by the ratio of its fitness to the fitness of other members of the current population.
      Returns:
      the roulette wheel selection algorithm.

    • ScaledRouletteWheel

      static Selection ScaledRouletteWheel()
      Scaled Roulette Wheel Selection. As the average fitness of chromosomes in the population increases, the variance of fitness decreases in the population. There may be little difference between the best and worst chromosome in the population after several generations, and the selective pressure based on fitness is corresponding reduced. This problem can partially be addressed by using some form of fitness scaling. In the simplest case, on can subtract the fitness of the worst chromosome in the population from the fitnesses of all chromosomes in the population. Alternatively, one may use rank based selection.
      Returns:
      the scaled roulette wheel selection algorithm.

    • Rank

      static Selection Rank()
      Rank Selection. The Roulette Wheel Selection will have problems when the fitnesses differ very much. For example, if the best chromosome fitness is 90% of all the roulette wheel then the other chromosomes will have very few chances to be selected. Rank selection first ranks the population and then every chromosome receives fitness from this ranking. The worst will have fitness 1 and the best will have fitness N (number of chromosomes in population). After this all the chromosomes have a chance to be selected. But this method can lead to slower convergence, because the best chromosomes do not differ so much from other ones.
      Returns:
      the rank selection algorithm.

    • Tournament

      static Selection Tournament(int size, double probability)
      Tournament Selection. Tournament selection returns the fittest individual of some t individuals picked at random, with replacement, from the population. First choose t (the tournament size) individuals from the population at random. Then choose the best individual from tournament with probability p, choose the second-best individual with probability p*(1-p), choose the third-best individual with probability p*((1-p)2), and so on... Tournament Selection has become the primary selection technique used for the Genetic Algorithm. First, it's not sensitive to the particulars of the fitness function. Second, it's very simple, requires no preprocessing, and works well with parallel algorithms. Third, it's tunable: by setting the tournament size t, you can change how selective the technique is. At the extremes, if t = 1, this is just random search. If t is very large (much larger than the population size itself), then the probability that the fittest individual in the population will appear in the tournament approaches 1.0, and so Tournament Selection just picks the fittest individual each time.
      Parameters:
      size - the size of tournament pool.
      probability - the best-player-wins probability.
      Returns:
      the tournament selection algorithm.