Module org.cicirello.chips_n_salsa
Package org.cicirello.search.evo

Class OnePlusOneGeneticAlgorithm

java.lang.Object
org.cicirello.search.evo.OnePlusOneEvolutionaryAlgorithm<BitVector>
org.cicirello.search.evo.OnePlusOneGeneticAlgorithm
All Implemented Interfaces:
Splittable<TrackableSearch<BitVector>>, Metaheuristic<BitVector>, ReoptimizableMetaheuristic<BitVector>, SingleSolutionMetaheuristic<BitVector>, TrackableSearch<BitVector>
public final class OnePlusOneGeneticAlgorithm extends OnePlusOneEvolutionaryAlgorithm<BitVector>
This class implements a (1+1)-GA, a special case of a (1+1)-EA, where solutions are represented with a vector of bits. In a (1+1)-EA, the evolutionary algorithm has a population size of 1, in each cycle of the algorithm a single mutant is created from that single population member, forming a population of size 2, and finally the EA keeps the better of the two solutions. This is perhaps the simplest case of an EA. This class supports optimizing BitVector objects. Mutation is the standard bit-flip mutation of a genetic algorithm, where a mutation rate M specifies the probability that each bit flips (from 0 to 1 or vice versa) during a mutation.

  • Constructor Details

    • OnePlusOneGeneticAlgorithm

      public OnePlusOneGeneticAlgorithm(OptimizationProblem<BitVector> problem, double m, int bitLength)
      Creates a OnePlusOneGeneticAlgorithm instance for real-valued optimization problems. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      m - The probability of flipping each bit during a mutation, which must be greater than 0.0 and less than 1.0.
      bitLength - The length of BitVectors required to represent solutions to the problem.
      Throws:
      IllegalArgumentException - if m ≤ 0 or m ≥ 1 or if bitLength is negative.
      NullPointerException - if problem is null.

    • OnePlusOneGeneticAlgorithm

      public OnePlusOneGeneticAlgorithm(IntegerCostOptimizationProblem<BitVector> problem, double m, int bitLength)
      Creates a OnePlusOneGeneticAlgorithm instance for integer-valued optimization problems. A ProgressTracker is created for you.
      Parameters:
      problem - An instance of an optimization problem to solve.
      m - The probability of flipping each bit during a mutation, which must be greater than 0.0 and less than 1.0.
      bitLength - The length of BitVectors required to represent solutions to the problem.
      Throws:
      IllegalArgumentException - if m ≤ 0 or m ≥ 1 or if bitLength is negative.
      NullPointerException - if problem is null.

    • OnePlusOneGeneticAlgorithm

      public OnePlusOneGeneticAlgorithm(OptimizationProblem<BitVector> problem, double m, int bitLength, ProgressTracker<BitVector> tracker)
      Creates a OnePlusOneGeneticAlgorithm instance for real-valued optimization problems.
      Parameters:
      problem - An instance of an optimization problem to solve.
      m - The probability of flipping each bit during a mutation, which must be greater than 0.0 and less than 1.0.
      bitLength - The length of BitVectors required to represent solutions to the problem.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      Throws:
      IllegalArgumentException - if m ≤ 0 or m ≥ 1 or if bitLength is negative.
      NullPointerException - if problem is null or if tracker is null.

    • OnePlusOneGeneticAlgorithm

      public OnePlusOneGeneticAlgorithm(IntegerCostOptimizationProblem<BitVector> problem, double m, int bitLength, ProgressTracker<BitVector> tracker)
      Creates a OnePlusOneGeneticAlgorithm instance for integer-valued optimization problems.
      Parameters:
      problem - An instance of an optimization problem to solve.
      m - The probability of flipping each bit during a mutation, which must be greater than 0.0 and less than 1.0.
      bitLength - The length of BitVectors required to represent solutions to the problem.
      tracker - A ProgressTracker object, which is used to keep track of the best solution found during the run, the time when it was found, and other related data.
      Throws:
      IllegalArgumentException - if m ≤ 0 or m ≥ 1 or if bitLength is negative.
      NullPointerException - if problem is null or if tracker is null.

  • Method Details

    • split

      public OnePlusOneGeneticAlgorithm split()
      Description copied from interface: Splittable
      Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of the Copyable interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state.
      Specified by:
      split in interface Metaheuristic<BitVector>
      Specified by:
      split in interface ReoptimizableMetaheuristic<BitVector>
      Specified by:
      split in interface Splittable<TrackableSearch<BitVector>>
      Overrides:
      split in class OnePlusOneEvolutionaryAlgorithm<BitVector>
      Returns:
      A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.