Package smile.gap

Class BitString

java.lang.Object
smile.gap.BitString
All Implemented Interfaces:
Comparable<Chromosome<BitString>>, Chromosome<BitString>
public class BitString extends Object implements Chromosome<BitString>
The standard bit string representation of the solution domain. Here are some general guides on parameter setting.

Crossover rate determines how often will be crossover performed. If there is no crossover, offspring is exact copy of parents. If there is a crossover, offspring is made from parts of parents' chromosome. If crossover rate is 100%, then all offspring is made by crossover. If it is 0%, whole new generation is made from exact copies of chromosomes from old population. However, it this does not mean that the new generation is the same because of mutation. Crossover is made in hope that new chromosomes will have good parts of old chromosomes and maybe the new chromosomes will be better. However, it is good to leave some part of population survive to next generation. Crossover rate generally should be high, about 80% - 95%. However, some results show that for some problems crossover rate about 60% is the best.

Mutation rate determines how often will be parts of chromosome mutated. If there is no mutation, offspring is taken after crossover (or copy) without any change. If mutation is performed, part of chromosome is changed. Mutation is made to prevent falling GA into local extreme, but it should not occur very often, because then GA will in fact change to random search. Best rates reported are about 0.5% - 1%.

  • Constructor Details

    • BitString

      public BitString(int length, Fitness<BitString> measure)
      Constructor. Two point cross over, cross over rate 0.9, mutation rate 0.01.
      Parameters:
      length - the length of bit string.
      measure - the fitness measure.

    • BitString

      public BitString(int length, Fitness<BitString> measure, Crossover crossover, double crossoverRate, double mutationRate)
      Constructor.
      Parameters:
      length - the length of bit string.
      measure - the fitness measure.
      crossover - the strategy of crossover operation.
      crossoverRate - the crossover rate.
      mutationRate - the mutation rate.

    • BitString

      public BitString(byte[] bits, Fitness<BitString> measure)
      Constructor. Two point cross over, cross over rate 0.9, mutation rate 0.01.
      Parameters:
      bits - the bit string of chromosome.
      measure - the fitness measure.

    • BitString

      public BitString(byte[] bits, Fitness<BitString> fitness, Crossover crossover, double crossoverRate, double mutationRate)
      Constructor.
      Parameters:
      bits - the bit string of chromosome.
      fitness - the fitness function.
      crossover - the strategy of crossover operation.
      crossoverRate - the crossover rate.
      mutationRate - the mutation rate.

  • Method Details

    • length

      public int length()
      Returns the length of bit string.
      Returns:
      the length of bit string.

    • bits

      public byte[] bits()
      Returns the bit string of chromosome.
      Returns:
      the bit string.

    • compareTo

      public int compareTo(Chromosome o)
      Specified by:
      compareTo in interface Comparable<Chromosome<BitString>>

    • fitness

      public double fitness()
      Description copied from interface: Chromosome
      Returns the fitness of chromosome.
      Specified by:
      fitness in interface Chromosome<BitString>
      Returns:
      the fitness of chromosome.

    • newInstance

      public BitString newInstance()
      Description copied from interface: Chromosome
      Returns a new random instance.
      Specified by:
      newInstance in interface Chromosome<BitString>
      Returns:
      a new random instance.

    • newInstance

      public BitString newInstance(byte[] bits)
      Creates a new instance with given bits.
      Parameters:
      bits - the bits.
      Returns:
      a new BitString.

    • crossover

      public BitString[] crossover(BitString mother)
      Description copied from interface: Chromosome
      Returns a pair of offsprings by crossovering this one with another one according to the crossover rate, which determines how often will be crossover performed. If there is no crossover, offspring is exact copy of parents. Various crossover strategies can be employed.
      Specified by:
      crossover in interface Chromosome<BitString>
      Parameters:
      mother - the other parent.
      Returns:
      a pair of offsprings.

    • mutate

      public void mutate()
      Description copied from interface: Chromosome
      For genetic algorithms, this method mutates the chromosome randomly. The offspring may have no changes since the mutation rate is usually very low. For Lamarckian algorithms, this method actually does the local search such as hill-climbing.
      Specified by:
      mutate in interface Chromosome<BitString>

    • toString

      public String toString()
      Overrides:
      toString in class Object