Skip to content

Latest commit

 

History

History
234 lines (181 loc) · 8.2 KB

genetic-operators.md

File metadata and controls

234 lines (181 loc) · 8.2 KB
Raw
  1. Introduction
  2. Fitness functions
  3. Encodings
  4. Algorithms
  5. Genetic operators
  6. Stop conditions
  7. Metrics
  8. Miscellaneous

Genetic operators

The genetic operators are used to create new candidate solutions from the existing ones in the population, providing the basic search mechanism of the genetic algorithms. The 2 main operators are the crossover and mutation, but the library also allows for specifying a repair function.

The selection method is considered to be a part of the algorithms in the library, so they are not discussed here. See algorithms.md for more details about the selection methods.

The library contains implementations of several crossover and mutation methods that can be used. These can be found in the gapp::crossover and gapp::mutation namespaces respectively.

As the genetic operators operate on candidate solutions, their implementations depend on the encoding type used for the GA. A particular crossover or mutation method can therefore only be used with the encoding type it is implemented for. Because of this, the implemented crossover and mutation methods are further broken up into multiple namespaces based on the encoding type they can be used with. For example, the crossover operators are in the following 4 namespaces:

  • crossover::binary
  • crossover::real
  • crossover::perm
  • crossover::integer

Crossover methods in the binary namespace can only be used for the BinaryGA, methods in the real namespace can only be used for the RCGA, and so on. The mutation methods are organized the same way.

The library doesn't provide any repair functions since their use in the GAs is optional, and their implementation is highly dependent on the problem itself. These have to be defined by the user when they are needed.

Crossover

The crossover operator is responsible for generating new solutions from existing ones. The operator takes 2 solutions selected from the population, and performs some operation on them with a given probability to generate 2 new solutions. When the operation is not performed, it returns copies of the parent solutions.

The crossover operator used by the GA can be set either in the constructor or by using the crossover_method method:

PermutationGA GA;
GA.crossover_method(crossover::perm::Edge{});

The probability of performing the crossover operation is a general parameter of the crossovers and it can be set for all of the crossover operators either in their constructors or by using the crossover_rate method:

PermutationGA GA;
GA.crossover_method(crossover::perm::Edge{ /* crossover_rate = */ 0.8 });

The GA classes also provide a crossover_rate method that can be used to set the crossover probability for the current crossover operator used by the GA:

PermutationGA GA;
GA.crossover_method(crossover::perm::Edge{});
GA.crossover_rate(0.8); // same as GA.crossover_method().crossover_rate(0.8)

Note that regardless of how you set the crossover probability, it is associated with a particular crossover operator, not the GA itself, so it will be changed when you change the crossover operator.

Some crossover operators also have additional parameters that are specific to that operator.

Mutation

The mutation operator is applied to each of the solutions generated by the crossovers in order to promote diversity in the population. This helps the GA with exploring more of the search space and avoiding convergence to local optima.

The mutation operator used by the GAs can be chosen similar to the crossover operators, either in the constructor or by using the mutation_method method:

RCGA GA;
GA.mutation_method(mutation::real::NonUniform{});

Similar to the crossovers, the mutation operators also have a mutation probability parameter, but how this probability is interpreted depends on the specific mutation operator. It may either be interpreted on a per-gene or on a per-solution basis.

The mutation probability can be set similar to the crossover probability, either in the constructor of the mutation operator, or by using the mutation_rate method:

RCGA GA;
GA.mutation_method(mutation::real::NonUniform{ /* mutation_rate = */ 0.1 });

The GA classes also provide a mutation_rate method that can be used to set the mutation probability for the current mutation operator of the GA:

RCGA GA;
GA.mutation_method(mutation::real::NonUniform{});
GA.mutation_rate(0.1); // same as GA.mutation_method().mutation_rate(0.1)

Note that just like for the crossovers, the mutation rate is associated with the mutation operator, not the GA itself, which means that it will be changed along with the mutation operator when that is changed.

Similar to the crossovers, some mutation operators also have additional parameters that are specific to that particular operator.

Repair

The repair function is an additional operator that will be applied to each solution after the mutations. Using a repair function is optional, and they are not used in the GAs by default.

The repair function can be specified as some callable object using the repair_function method of the GAs:

ga.repair_function([](const GA<RealGene>&, const Chromosome<RealGene>& chrom)
{
    auto new_chrom = chrom;
    // do something with new_chrom ...
    return new_chrom;
});

The repair function can be reset by setting it to a nullptr:

GA.repair_function(nullptr);

Custom genetic operators

In addition to the operators already implemented in the library, user defined crossover and mutation operators can also be used in the GAs.

The simplest way to do this is to use a lambda function (or some other callable):

RCGA ga;

ga.crossover_method([](const GA<RealGene>&, const Candidate<RealGene>& parent1, const Candidate<RealGene>& parent2)
{
    auto child1 = parent1;
    auto child2 = parent2;

    // perform the crossover ...

    return CandidatePair<RealGene>{ std::move(child1), std::move(child2) };
});

ga.mutation_method([](const GA<RealGene>& ga, const Candidate<RealGene>& sol, Chromosome<RealGene>& chrom)
{
    for (RealGene& gene : chrom)
    {
        if (rng::randomReal() < ga.mutation_rate())
        {
            // modify the gene ...
        }
    }
});

Alternatively, crossover and mutation operators can also be implemented as classes derived from crossover::Crossover<GeneType> and mutation::Mutation<GeneType> respectively. Crossovers must implement the crossover method, while mutations must implement the mutate method:

class MyCrossover : public crossover::Crossover<RealGene>
{
public:
    using Crossover::Crossover;

    CandidatePair<RealGene> crossover(const GA<RealGene>& ga, const Candidate<RealGene>& parent1, const Candidate<RealGene>& parent2) const override
    {
        // perform the crossover ...
    }
};
class MyMutation : public mutation::Mutation<RealGene>
{
public:
    using Mutation::Mutation;

    void mutate(const GA<RealGene>& ga, const Candidate<RealGene>& candidate, Chromosome<RealGene>& chromosome) const override
    {
        // perform the mutation on chromosome ...
    }
};

There are a couple of things that should be kept in mind when implementing these operators regardless of how they are defined:

  • The crossover implementation should just perform the crossover operation without taking the crossover rate into account. Handling the crossover rate is done elsewhere.
  • The mutation implementation must take the mutation rate into account, as the interpretation of the mutation rate depends on the specific mutation method (it can either be a per-gene or per-chromosome probability).
  • The mutation modifies the chromosome parameter directly, and does not return anything.
  • The implementations should be thread-safe. It can be assumed that the mutation operator has exclusive access to its chromosome parameter.

Next: Stop conditions