Brest State Technical University, Course "Intelligent Information Technology Department"

From Students' Works (2012)

20 dimensional function y = x1^2+x2^2+...+x^20 is called "Sphere Model." The minimum value of y is 0 as you can easily guess. Let's apply a Genetic Algorithm to this function. Typically you may show the success by maximum fitness and average fitness of the population as a function of generation.

• An example ... by many who is the original author I don't know
  
  

• Or yet another example ... By Slusareva Maria
  
  

The next basic toy example is called "All-one-problem" in which 20 bit binary chromosome evolve, assuming gene '0' is bad and gene '1' is good. As such fitness is a number of '1' in the chromosome.

• An example of evolution from random chromosome, fitness graph and population evolved ... By Slusareva Maria
  
  

Let's find a minimum y of y = 3 + x^2 - 3*cos(2*pi*x) when applied Deterministic Crowding Genetic Algorithm.

• An example of being trapped in two local minimum ... By Shevchuk Seregei
  
  

• An example of almost successful ... By Belovusova Katerina
  
  
  
  

• In this example all chromosomes are going to converge to the global minimum ... By Alena Loziuk
  
  

Then what if a function has multiple optima?

• When we apply a simple Genetic algorithm it converges only one of those optima ... By Dima Golovko
  
  

• Let's try a Genetic Algorithm called Deterministic Crowding ... By Kulesha Roman
  
  

• It works even 10 opitma ... By Belovusova Katerina
  
  

Let's find a lucky dog!

• A dog explored in a grid-world find a sausage avoiding dangerous pond, river etc ... By Slusareva Maria

Gene is either 1, 2, 3, 4 meaning one step up, down, right, left. Then the dog can move N steps, where N is a length of chromosome. After N stemps the dog cannot move with hunger, and then distance to the sausage is the fitness of the chromosome of this dog. Thus after an evolution a lucky dog appears.

It's fitness vs. generation was shown below

In another run of genetic algorithm a different lucky dog was found

• The other lucky dog ... By Sadko Viktoria

We can see quite an early convergence from fitness vs generation

Traveling Salese-person Problem (TSP)

• 10 cities TSP ... By Kisel Nikolay
  
  
  This is by tarting generating coordinates of the 10 cities at random as A (5.29,7.99), B (4.65, 2.47), C (6.10, 9.70), D (7.12, 4.39), E (7.85, 0.50), F (4.95, 0.60), G (1.12, 2.40), H (9.74, 0.09), I (9.37, 7.89), and J (5.95, 8.60)
  
  
  Then distance matrix between all possible combination of 2 cities is calculated as
  
  
  
  And we can calculate the total distance of tour like:
  A-> I-> J-> G-> E-> C-> D-> H-> F-> B-> A => 54.52
  A-> E-> F-> C-> G-> B-> H-> I-> D-> J-> A => 55.23
  A-> B-> F-> H-> I-> G-> E-> J-> D-> C-> A => 56.99
  A-> I-> J-> D-> C-> B-> H-> F-> E-> G-> A => 52.04
  A-> C-> E-> F-> J-> G-> I-> H-> D-> B-> A => 61.54
  Theoreticall all the tour-length can be thus calculated, but the number of possible toure is (10-1)!/2. Too many, right?
  
  
  Then by applying a Genetic Algorithm, the shortest route is obtained, seemingly successfully.
  
  The tour and its length are found to be: A-> G-> B-> F-> E-> H-> D-> I-> J-> C-> A => 32.94. This is much shorter than the 5 example tours above, right?
  
  
  
  Demension Reduction from 20-D to 2-D
  • Randamly picked up 10 points from 20-D sphere with radius 1 ... By Alna Loziuk
  
  
  
  Its distant matrix
  
  
  
  Then create 10 points in 2-D space at random, and also create its distance matrix. A genetic algorithme will be applied with a chromosome being these 10 random points in 2-D and fitness being how similar between distance matrix in 20-D and 2-D.

Iterated Prisonner's Dillema (IPL)

• With strategy being 64 bit chromosomes ... By Antonyan Tigran

Neural Network to solve even parity problem

• A configuration of weights and all possible input-output cases ... By Igor Borihin