Brest State Technical University, Course "Contemporary Intelligent Information Technology (CIIT)"

From students' works (2016)


All One Problem
Start with random 50 chromosome each with 1000 genes - An example of result ... By Vechorko Anna (2015)

1000 genes seem to be too big to converge to all one chromosome!

"../flg.png" width="25"> Then let's apply mutation ... By Aliaksandra Kivachuk (2015)


By applying mutation, we obtained a perfectly good chromosome even with number of genes being 1000 and for population 50 again (Collection: x-axis is not "generate" but "generation")






Traveling Salesperson Problem (TSP)

Assume a salesperson, starting with his city, should visit N cities once and only once after visiting all the sities, he/she should return his city. Traveling Salesperson problem is the problem to look for the route of minimum distance out of all possible (n-1)!/2 such routes.

5 cities located at random
An example of result ... By Muzyka Alexandr (2016)



Let's evolve!

Shortest route in the population - from the bigining to the final.


With cities located at random
An example of 30 cities located in 2-D space from (0,0) to (100,100) ... By Lishko Yuliai (2014)

Her map


Distance matrix


Evolution of tours from the 1st generation to the final generation


It's graph of fitness vs. generation.

When N is large, no one knows the solution of the shortest route. So we it assume that it evolution reaches the solution when fitness do not change any more for quite a long time. In this example shortest route is aproximately 800 (it would have been better if exact distance had been shown in the graph).


15 cities rondomly located on the circle (x-5)^2+(y-5)^2=25
An example of result ... By Kolesnikov Dmitry (2016)

Map, Distance-matrix and fitness vs generation




Let's see the evovlution of best tour in population










25 cities located at fixed points (not random) on the grid like chess board
An example of result (2016)
Map ... By Kaminets Kiryl (2016) (Left) or Map ... By Harhun Tsimafei (2016) (Right)

Distance Matrix ... By

Evolution - Fitness vs. Generation ... By Kaminets Kiryli(2016)

Evolution of shortest tour ... By Kaminets Kiryl (2016)

Or










Lucky Dog
Lucky dog problem in gridworld (0,0)-(1000,1000) with dog house at (500,500) and sausage at (200,800). Dog is made up of chromosome with 1000 genes each of whose value is 1, 2, 3 or 4, which means one step up, down, to left or to right. Hence each dog allows 1000 steps. Fitness is manhattan distance to the sausage from the current position of the dog.
An example of result ... By Vechorko Anna (2015)
(i) fitness vs generation, and (ii) The course of luckiest dog in the final generation



The other examples of the luckiest dog in the final generation
(i) Left ... By Aliona Radchuk and (ii) Right ... By Dmitry Verenich (2015)


Lucky dog problem in the same gridworld as above except for two sausages this time at (200,800) and (800,200)
An example of result ... By Belous Sophia (2015)
(i) Fitness vs generation, and (ii) The course of lucky dog in the final generation

Important message of the result is, all the dogs arrive to only one sausage despite that two sausages exsist.

Lucky dog problem with four sausages this time at (200,200), (200,800), (800,800) and (800,200)
An example of result ... By Marchanka Ilya (2015)
(i) Fitness vs generation, (ii) the route of luckiest dog in the final generation

Despite of 4 sausages, all the dogs evolved to reach only one of the four sausages.



What if we have solutions more than one?

A minimization of a 2-D function
An example of y = sin^6 (5*Pi*x) ... By Vyshinskaya Natalia
All the binary chromosomes to apply 2-D graph are also shown.




All the chromosomes eventually go to one of the six minimum points Like all guys gathered one bottle of vodka (or girl), while there were six bottles (beautiful girls). If we run the algorithm again, those choromosomes might go the other different minimum (Not shown here though).


Another example of y = (1-x)*sin^4{5*pi/(1+x^4)} (0,1) with 10-bit binary chromosome & population 20 ... By Kanashuk Anton (2014)





Then a Fitness Sharing was applied to the same function ... also by Kanashuk Anton (2014)





Knapsack Problem
Assuming N different items each of whose price p_i and size w_i are given. The problem is maximize the total price in the knapsak by optimumly choose items with total size is smaller than the size of knapsak W.
An example of 20 items ... By Lishko Yulia (2014)

Price and size of each item.


Fitness vs. Generation.


The best combination with maximum total price.




Iterated Prisnner's Dilemma (IPD)
An example of result ... By Vechorko Anna i(2015)
20 players each having 64-bit binary chromosomes. One game is made up of 12 rounds with 3 random preparation rounds + 9 serious rounds where 1 against 1 gets 5; 1 against 0 gets 2; 0 against 1 gets 0; and 0 against 0 gets 3 are counted in last 9 rounds. Each player plays with other 19 players in the population and Fitness is a total points of these 19





Dimension reduction from 3D sphere to 2D circle
An example of result ... By Katolik Alexandr

At the begining, a target 3D spere was created and select 20 points randomly from the surface.



Then the original 3D distance matrix and its normalization were calculated.


At the end of evolution, the 2D normalized distance matrix of the best chromosom was obtained.


Good work! But the final figure of those 20 points probably on the circle mapped from the original 3D target is missing. What a shame!





What if two, for example, fitness functions? - Parete Optimum Solution
y=(x-2)^2 and y=(x-4)^2 for x from 0 to 6 with an algorithm using "rank"
An example of result ... By Magomedova Aminat



Wondering how many generation was necessary to the final population?



A sorting network problem
Try to observe how a random chromosome with 150 genes with each value being 01-16 can sort 16 integers from 1 to 16 An example 1. ... By Radchuk Aliona
A randomly created chromosome (Left), and its graphic representation (Right)

Those indentical comparisons should be removed from the diagram. One comparison will be enough for a same pair! E.g. "11" and "12" are compared three times.
I found the 95th gene and the 96th gene are both 14, right? Then the comparison is meaningless in this case. Then how many meaningful comparisons in the chromosome, after removing multipul identical comparisons and comparison between identical items.

A result of applying the chromosome to a set of 4 random order of integers from 1 to 16. The goal is to sort them from small to large.


How a diploydy chromosome of length 480 genes sort string of 16 letters to alphabetical order? (also max 120 comparisons)
An example ... By Koroluk Andrew
His diploydy chromosome created at random


Actual comparisons that his diploydy chromosome above means are:


Then this diploydy chromosom compares the 16 letters one pair after another and exchange if necessary

Beautiful! But unfortunately his diploydy chromosome is only a pair of 64-bit length while what was indicated was 480-bit length

Sorting network with Diploydy chromosomes by evolution with a pair of binary-chromosomes with 480 genes (max 120 comparisons)
An example ... By Marchanka Ilya




Biologicaly (0-0) & (1-1) pair tend to inclease, and as such, real nubmer of comparisons decreases in this case, which I expected the same goes here but not indeed, for some reason we don't know...