Movie that understands in what way "genetic algorithm" works in 2 minutes

ByFdecomite

We select preferentially individuals with high fitness from multiple individuals, repeat recombination / mutation, etc. and search for solutions "Genetic algorithm"Is what it is, the movie described in 2 minutes is released on YouTube.

Two Minute Papers - How Do Genetic Algorithms Work? - YouTube


This is one of YouTube's movie series "Two Minute Papers" that explains things in two minutes,Károly Zsolnai-FehérMade by.

An example that is easy to understand in the movie is to try the purpose of "gen- erally generating vehicles that advance the default courses automatically" as a genetic algorithmBoxCar 2 D.


A computer generates a "car" with a triangle and several tires, aiming to proceed as far as possible. However, since it is random at first, something that can not be called a car can be born, because there is no tire and it can not move forward.


Sometimes, things that work well will be born. By default, 20 individuals will be born in one generation, and genetic algorithms will create the next generation based on some of the "cars" that were able to run this well.


So, when you stack as many as 10 generations, things that seem to be able to run like this are born like this. It is similar to the evolution of nature.


This figure is modeled using four individuals.


We will generate the next generation based on 3 individuals who have left excellent results.


In the living things, the process of breeding and leaving descendants is "recombination" indicated by the orange arrow, replacing the elements of the two individuals. Repeating this will converge to a local optimal solution, so a "mutation" similar to a mutation of an organism's gene will also be done. This is indicated by the red arrow, and there are parts where 0 and 1 are swapped by mutating from left to right. If we increase the probability of mutation, it will be the same as searching for the solution randomly, so we set the probability to be a few percent even though it is high.


Another example cited by Zsolnai-Fehér is "Roger Johansson"Genetic Programming: Evolution of Mona Lisa". This is an attempt to reproduce Mona Lisa with a genetic algorithm using only 50 semi-transparent polygons. "Mona Lisa" produced by the algorithm on the left side of the screen, "Mona Lisa" aimed at the right. Although it is the level that the position of the color vaguely matches if it is roughly 1200 to 1300 generations ... ...


I feel that appearance of Mona Lisa is emerging in the geometric pattern when 12,000 generations are repeated.


By the way, according to Mr. Johansson, if it takes about 900,000 generations, it seems that you can make a picture almost like Mona Lisa.


For those who want to know the genetic algorithm Zsolnai-Fehér mentioned the reference book "Selfish Gene"Richard Dawkins' work known as"The Blind Watchmaker". It is translated under the title of "Blind Watchmaker" and it is available on Amazon and others.

Blind watchmaker | Richard Dawkins, Takataka Hidaka, Yasuhiro Nakajima, Akira Endou, Tomoji Endo, Tsutomu Hikida | Books | Amazon.co.jp