1. [Introduction](introduction.md) 2. [Fitness functions](fitness-functions.md) 3. [Encodings](encodings.md) 4. [Algorithms](algorithms.md) 5. **Genetic operators** 6. [Stop conditions](stop-conditions.md) 7. [Metrics](metrics.md) 8. [Miscellaneous](miscellaneous.md) ------------------------------------------------------------------------------------------------ # 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](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: ```cpp 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: ```cpp 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: ```cpp 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: ```cpp 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: ```cpp 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: ```cpp 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: ```cpp ga.repair_function([](const GA&, const Chromosome& 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: ```cpp 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): ```cpp RCGA ga; ga.crossover_method([](const GA&, const Candidate& parent1, const Candidate& parent2) { auto child1 = parent1; auto child2 = parent2; // perform the crossover ... return CandidatePair{ std::move(child1), std::move(child2) }; }); ga.mutation_method([](const GA& ga, const Candidate& sol, Chromosome& 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` and `mutation::Mutation` respectively. Crossovers must implement the `crossover` method, while mutations must implement the `mutate` method: ```cpp class MyCrossover : public crossover::Crossover { public: using Crossover::Crossover; CandidatePair crossover(const GA& ga, const Candidate& parent1, const Candidate& parent2) const override { // perform the crossover ... } }; ``` ```cpp class MyMutation : public mutation::Mutation { public: using Mutation::Mutation; void mutate(const GA& ga, const Candidate& candidate, Chromosome& 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

](stop-conditions.md)