Skrgic Selection in GPdotNET
This document presents Skrgic Selection Method, the one of several selection methods in GPdotNET. While I was developing GPdotNET I have had several conversation with my friend Fikret Skrgic (master in computer scinence and math) regarding selection in Evolutionary algorithms. He is an incredible man, and in just a few minutes while I was describing to him what I want from a new way of selection, he came out with the basic idea of the new selection method. After that time in just a few mails I had a new selection method ready for implementation in GPdotNET. I gave the name to the new selection method by his surname. It is a little thankfulness to him.
In the flowing text it will be presented the idea behind Skrgic Selection.
Liner Skrgic Selection (LSS)
The Idea behind this selection is based on chromosome fitness. The rule is simple: The bigger chromosome fitness gives bigger chance to select better chromosome. In Population, chromosomes are already sorted from best to worst chromosomes.
The process of selection is the following:
- Find the maximum and minimum fitness value from the population.
- The best chromosome (maximum fitness) has position 0 in the population (zero based index), and the worst chromosome has index .
- Let’s give them name as and respectively.
- Choose random number between and .
- Choose random chromosome from the Population .
- Compare the values of and . If the is greater than , select .
- Repeat steps 3 and 4 until you select one chromosome.
- Repeat steps 2,3,4,5 until you select chromosomes.
The following picture shows graph of linear Skrgic selection:
Nonlinear Skrgic Selection (NSS)
In LSS we have linear graph of selection probability. This means that if we have chromosome with fitness value, and another chromosome with fitness value, the probability of selection of two chromosomes is and respectively. This means that probability of selection is growing linearly.
If we want to change probability between chromosomes we can define a factor to be like selection pressure on whole chromosomes in the population. So let the k be a real value, and define the fitness of each chromosome as:
- – fitness value of the chromosome,
- – maximum fitness value(fitness of the best chromosome of the population),
- – selection pressure,
- – nonlinear fitness value of the chromosome.
We can conclude that the maximum nonlinear fitness value of the best chromosome is given by:
For various value of parameter we can define graph of probability selection like on the following picture:
On the picture above we can see if we get the standard Linear Skrgic Selection (LSS). We can also conclude that there is a fitness value when the probability of selection is constant and not depends of parameter . Very interesting graph is when the . In this case the selection probability of the worst and the best chromosome are equal.