Genetic operators

Genetic operators

In µGP, new individuals are generated by applying genetic operators to existing solutions. Operators are randomly selected, following the idea that operators producing the best individuals should be activated more often, but no operator able to generate valid individuals should ever be completely removed from the process, no matter how bad the fitness of its children is. For a more detailed discussion on the self-adapting probabilities of activation, see Choosing operators using DMAB.

Standard Mutations (ie. single-parent operators)

Most mutation genetic operators will repeat the mutation described more than once, depending on the current value of sigma.

singleParameterAlterationMutation : chooses randomly a single parameter inside a macro in the individual and mutates it to another possible value. The process is repeated depending on the current value of sigma.

alterationMutation : behaves like singleParameterAlterationMutation, but operates on all parameters in the same macro. The process is iterated on other macros, depending on sigma.

insertionMutation : tries to insert a new macro instance inside a randomly selected subsection. Note that this will NOT work if the size of your individuals is fixed (see More fun with OneMax for an example). The process is repeated depending on the current value of sigma.

removalMutation : will remove a macro instance from one randomly selected subsection of an individual. Again, this will NOT work if the size of your individuals is fixed (see More fun with OneMax for an example). The process is repeated depending on the current value of sigma.

replacementMutation : randomly selects a macro instance inside a subsection and replaces it with an instance of one of the available macros in the subsection. The process is repeated depending on the current value of sigma.

subGraphInsertionMutation : will add a whole new subsection instance to the individual. Note that this will NOT work if your individual has a fixed number of instance for each subsection (or worse, if it has only one subsection repeated one time). The process is repeated depending on the current value of sigma.

subGraphRemovalMutation : will remove a whole subsection instance to the individual. Note that this will NOT work if your individual has a fixed number of instance for each subsection (or worse, if it has only one subsection repeated one time). The process is repeated depending on the current value of sigma.

subGraphReplacementMutation : will replace a whole subsection instance in the individual with another one. Note that this will work POORLY if your individual has a fixed number of instance for each subsection (or worse, if it has only one subsection repeated one time). The process is repeated depending on the current value of sigma.

Scan Mutations

''Scan mutation operators'' select a variable in a macro (see Population's Constraints for more information) and create a child individual for each possible value that the parameter can assume. In some cases, the specified range is sampled with a frequency that depends on the current value of sigma.
Note: this operators produce a huge number of children, so be careful. The offspring, however, won't invade the population thanks to the mechanism named allopatric selection.

scanMutationBITARRAY : selects a bitArray variable in a macro; then creates a child with a Hamming distance of 1 from the value of the parent. The process is iterated depending on sigma, and when all individuals within a Hamming Distance of 1 are produced, individuals with a Hamming Distance of 2 will be produced at the next iteration (and so on).

scanMutationDEFINED : selects a definedType variable in a macro, and creates one child individual for each possible value that the definedType variable can assume. For example, if you have a definedType variable "color" that can assume values "red", "yellow", "blue" and "green", scanMutationDEFINED will take one individual with value "red" and produce three individuals with value "yellow", "blue" and "green".

scanMutationINNERLABEL : selects an innerLabel (or innerForwardLabel, or innerBackwardLabel) variable in a macro, and creates one child individual for each possible node the innerLabel variable can point to.

scanMutationINTEGER : selects an integer variable in a macro, and creates two children individuals, sampling the ranged variable around the original value of the parent. The process is iterated depending on sigma.

scanMutationFLOAT : selects a floating point variable in a macro, and creates two children individuals, sampling the ranged variable around the original value of the parent. The process is iterated depending on sigma.

Differential-Evolution Operators

This class of experimental operators aims at replicating some mechanisms of Differential Evolution. Preliminary results are encouraging, but their performance is still under evaluation. They only work on floating point variables, and thus will constantly fail if your individuals do not contain any floating point parameter.

allopatricDifferential : following closely the Differential Evolution paradigm, this operator creates a considerable number of individuals. Of all individuals created, however, only the one with the highest fitness value will be added at the population in the next generation. See allopatric selection for more information.

simpleDifferential : loosely mimicking the Differential Evolution schema, this operator creates only one child individual for each activation.

Crossovers (ie. multiple-parent operators)

Note: Crossovers and ''imprecise'' crossovers behave '''exactly in the same way''' if individuals do not contain ''outerLabel'' parameters. For more information, see the Parameters section in page Macros.

onePointCrossover : is a crossover operator that uses one cut point. It swap slices at level of a subgraph, and copies from one individual to the other all other subgraphs that are referenced in the slices (by outerLabel). The cut points are chosen in corresponding points if the two individuals have the same size, or as close as possible to each other if the two individuals have different sizes.

twoPointCrossover : same as onePointCrossover, but with two cut points.

onePointImpreciseCrossover : is a crossover operator that uses one cut point. Eventual labels to other subgraphs are reattached to corresponding parts, at the best of possibility, but if the parts are missing they are not copied, but the references are removed or attached to other parts.

twoPointImpreciseCrossover : same as onePointImpreciseCrossover, but with two cut points.

[ver3.34] Group Operators

These operators work on candidate solutions that are defined as Groups.

Other Operators

In many real-world problems, having a quota of individuals randomly created at each generation might prove useful to help the algorithm avoiding getting stuck into local optima. The following, perhaps improperly grouped with the other operators, provides this functionality.

randomizer : generates an individual completely at random, following the constraints provided in the population.

Note: randomizer is unlikely to have good performance, so if you are running µGP with self-adaptation, i.e. with the parameter "inertia" < 1, it's activation probability will drop dramatically in a few generations. If you are using randomizer as mechanism to preserve diversity, we advice setting its minimum activation probability to a value around 5%.}