Skrgic Selection in GPdotNET


Introduction

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:

  1. Find the maximum and minimum fitness value from the population.
  2. The best chromosome (maximum fitness) has position 0 in the population (zero based index), and the worst chromosome has index N-1.
  3. Let’s give them name as f_{max} and f_{min} respectively.
  4. Choose random number r between f_{min} and f_{max}.
  5. Choose random chromosome from the Population chrom.
  6. Compare the values of r and f_{chrom}. If the f_{chrom} is greater than r, select chrom.
  7. Repeat steps 3 and 4 until you select one chromosome.
  8. Repeat steps 2,3,4,5 until you select n chromosomes.

The following picture shows graph of linear Skrgic selection:

Linear Skrgic Selection (LSS)

Nonlinear Skrgic Selection (NSS)

In LSS we have linear graph of selection probability. This means that if we have chromosome with f_{chrom} fitness value, and another chromosome with \frac{f_{chrom}}{2} fitness value, the probability of selection of two chromosomes is p and \frac{p}{2} respectively. This means that probability of selection is growing linearly.
If we want to change probability between chromosomes we can define a factor k 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:

f_{nss}=f_{chrom} (1+k \frac{f_{chrom}}{f_{max}}),

where:

  • f_{chrom} – fitness value of the chromosome,
  • f_{max} – maximum fitness value(fitness of the best chromosome of the population),
  • k – selection pressure,
  • f_{nss} – nonlinear fitness value of the chromosome.

We can conclude that the maximum nonlinear fitness value of the best chromosome is given by:

f_{max(nss)}=f_{max}(1+k).

For various value of parameter k  we can define graph of probability selection like on the following picture:

Graph for various sample of NonLinear Skrgic Selection (NLSS)

On the picture above we can see if k=0 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 k. Very interesting graph is when the k=-1. In this case the selection probability of the worst and the best chromosome are equal.

GPdotNET settings of GP parameters

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 20/10/2011, in GPdotNET, Programiranje and tagged , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s