Genetic algorithms, image recognition

Genetic algorithms are widely used in problems of optimization and training of neural networks.
The algorithms themselves are iterative, and give only an approximation, which, however, is more than offset by their area of ​​application.
Let us analyze the device of one of such algorithms on the example of recognition of the simplest image.
We will operate on chromosome populations (individuals), since the algorithm is iterative, the current iteration number is called the current epoch.
Before drawing up the algorithm, we will determine what will be our task and what will be its solution:
Consider an example of finding the coefficients in the parabola equation, based on a hand-drawn image. In this case, the task is to find such coefficients at which the parabola will coincide as closely as possible with the figure, the solution to the problem is a set of three coefficients in the parabola equation.

The algorithm provides for a population of certain objects (chromosomes) that will fight for survival.
So, the Chromosome is a possible solution to our problem, no matter which one is correct or not.
The gene is an elementary piece of information, within the framework of this task, we will have three genes, respectively, one for each coefficient.
Population - a set of chromosomes of the current era.
Initially, we create a population (preferably of several thousand chromosomes), and fill the genes with arbitrary information that does not contradict the condition of the problem.
As in the real world, our chromosomes will multiply and undergo various mutations. Crossover operators and mutations are responsible for these actions.

The crossover is responsible for transferring the signs of parents to their descendants; in the simplest implementation, it creates a new chromosome from the genes of two parents, the “donor” of the next gene is selected at random.
The mutation operator is designed to bring diversity to our island of digital life; under its influence, an arbitrary gene changes on the chromosome.
Fitness-function : As in life - non-adapted species must die, “clean” our population will be the last function, called the function of the device, or the Fitness-function.
For each chromosome, this function returns a number inversely proportional to the “fitness” of this chromosome, and the following conditions are imposed on it:
Fitness value from ideal solution = 0
This is a basic condition, but it is still desirable to choose a function so that its value grows as the solution moves away from the ideal. In other words - that she had only one minimum.
')
Now we can formulate a variant of the algorithm
1. Designate the number of the epoch = 0, create a population of chromosomes, in the genes of which there will be arbitrary, not contradicting to the task, information
2. Calculate the fitness of the population.
3. Choose individual A from the population
4. With probability P (crossing), select individual B and apply the crossover operator, the resulting individual to bring into the new population.
5. With the probability P (mutations) to perform a mutation of an arbitrary individual, the resulting individual to bring in a new population
6. Perform operations 3,4,5 n times, where n> = population size
7. Create a new population of the best individuals of the existing and newly formed population.
8. Increase the number of the current era
9. If the result of the work is satisfactory - stop the algorithm, otherwise - go to step 2.

The genetic algorithm is not strictly deterministic, for example, we can first perform the crossing of all individuals, and then the mutation (for this problem, this approach turned out to be more efficient). So, we will try, on the basis of the described, to solve the problem. First we need to determine the chromosome, which will be the repository of information about genes.

public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .

1. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
2. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
3. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
4. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
6. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
7. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
8. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
10. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
11. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
12. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
13. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
14. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
15. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
16. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .
17. public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .

public class Chromosome : IComparable { public double [] gens; static Random random = new Random (); public Chromosome() { this .gens = new double [3]; for ( int i = 0; i < 3; i++) { this .gens[i] = random.NextDouble() * 100; } this .fit = fitness( this ); } public int CompareTo( object obj) } * This source code was highlighted with Source Code Highlighter .

A value of 100 is chosen as an example; this will not limit the generality, even if the desired parabola will have cof 100
Note the CompareTo method, which allows us to sort the lists of Chromosome objects.

1. public class Population
2. {
3. Random random = new Random ();
4. public List <Chromosome> population;
5. public int count;
6. public double crossProbability;
7. public double MutationProbability;
8. public int age;
10. public Population ()
11. {
12. for ( int i = 0; i <5000; i ++)
13. {
14. this .population.Add ( new Chromosome ());
15. }
16. }
18. public void GoToNextGeneration ()
19. {
20. Chromosome chromosome;
21. for ( int i = 0; i <count; i ++)
22. {
23. chromosome = population [i];
25. if (random.NextDouble () <crossProbability)
26. {
27. population.Add (Cross (chromosome, population [random.Next (count)]));
28. }
29. }
31. for ( int i = 0; i <population.Count; i ++)
32. {
33. if (random.NextDouble () <MutationProbability)
34. {
35. population.Add (Mutate (population [i]));
36. }
37. }
39. population.Sort ();
40. population.RemoveRange (count, population.Count-count);
42. age ++;
43. }
45. Chromosome Cross (Chromosome a, Chromosome b)
46. Chromosome Mutate (Chromosome a)
47. double Fitness (Chromosome a)
48. }

* This source code was highlighted with Source Code Highlighter .

Here it is, the evolution in twenty lines! This will be the heart of our program.
In the first part, we get the progeny from the already existing population, and add it to the end of the list, i.e. All "children" will be located under the number greater than count.
The second step is a mutation, it would be logical to mutate the chromosome itself, rather than add a mutated clone, but in this case we lose the solution contained in the original chromosome, and it may be the best in the population.
Finally, at the end we sort our entire resulting population by the ascending Fitness function, (hence, by decreasing the correctness of the solution) we remove the least “adapted” chromosomes, and increase the number of the current epoch.

Let's look at what are the last three functions that perform operations on our chromosomes?

1. Chromosome Cross (Chromosome a, Chromosome b)
2. {
3. double [] pair = new double [3];
5. for (int i = 0; i <3; i ++)
6. {
7. if ((random. Next ()% 2) == 0)
8. {
9. pair [i] = a.Gens [i] + (b.Gens [i] - a.Gens [i]) * 0.1;
10. }
11. else
12. {
13. pair [i] = b.Gens [i] - (b.Gens [i] - a.Gens [i]) * 0.1;
14. }
15. }
17. Chromosome result = new Chromosome (pair);
18. return result;
19. }

* This source code was highlighted with Source Code Highlighter .

The implementation of the crossover operator can be quite diverse, and, usually, is selected for a specific task. Here, with a probability of 0.5, for each gene, the descendant will receive it from the first parent or, with the same probability, from the second parent.
The amendment (b.Gens [i] - a.Gens [i]) * 0.1 is made to somehow diversify the population with a new genotype.

1. Chromosome Mutate (Chromosome a)
2. {
3. double [] pair = ( double []) a.Gens.Clone ();
4. int geneNum = random.Next (3);
5. pair [geneNum] = random.NextDouble () * 100;
6. return new Chromosome (pair, a.chromosomeSettings);
7. }

* This source code was highlighted with Source Code Highlighter .

As promised, the mutation operator changes one random gene.
Let's take a look at the most interesting, how are we going to determine how close our chromosome is to the ideal solution?

1. double GetFitness (Chromosome a)
2. {
3. double result = 0;
4. double temp;
5. for ( int i = 0; i <funcLength; i ++)
6. {
7. temp = Math .Abs (Func (i, a.Gens) - funcArray [i]);
8. result + = temp;
9. }
11. return result;
12. }
14. double Func ( double x, double [] gens)
15. {
16. double result = 0;
17. for ( int i = 2; i> = 0; i--)
18. {
19. result + = gens [2-i] * Math .Pow (x, i);
20. }
21. return result;
22. }

* This source code was highlighted with Source Code Highlighter .

The funcArray array is obtained by scanning the image from the bottom up through the columns, each column is an array index, the height of the first black point found in the column is a value.
Function Func - returns the value of the 2nd degree equation at the point x, with coefficients from the gens array
It turns out Fitness is the sum of “errors”, for each point of our parabola, which is in the figure. Such a function does not have a single minimum, but, nevertheless, provides sufficient convergence of the algorithm.

Result:


With the number of chromosomes in the population = 5000, on the 25th generation we get a fairly close similarity.
This algorithm can be extended to curves of any order =)

Sources: slil.ru/27874467
UPD : Transfer to Artificial Intelligence