# How Do Genetic Algorithms Work? | Two Minute Papers #32 ## Метаданные - **Канал:** Two Minute Papers - **YouTube:** https://www.youtube.com/watch?v=ziMHaGQJuSI - **Дата:** 16.12.2015 - **Длительность:** 3:15 - **Просмотры:** 75,290 ## Описание Genetic algorithms are in the class of evolutionary algorithms that build on the principle of "survival of the fittest". By recombining the best solutions of a population and every now and then mutating them, one can solve remarkably difficult problems that would otherwise be hopelessly difficult to write programs for. One of the first works of genetic algorithms, "Adaptation in Natural and Artificial Systems" by John H. Holland: https://mitpress.mit.edu/books/adaptation-natural-and-artificial-systems _____________________ A parallel genetic algorithm for the Mona Lisa problem: https://cg.tuwien.ac.at/~zsolnai/gfx/mona_lisa_parallel_genetic_algorithm/ A parallel, console genetic algorithm for the 0-1 knapsack problem: https://cg.tuwien.ac.at/~zsolnai/gfx/knapsack_genetic/ John Henry Holland, the father of genetic algorithms: https://en.wikipedia.org/wiki/John_Henry_Holland Try this out, it's really fun! - http://boxcar2d.com The mentioned book is called "The Blind Watchmaker" by Richard Dawkins. The thumbnail background image was created by Karen Roe (CC BY 2.0) - https://flic.kr/p/ezxAbk Subscribe if you would like to see more of these! - http://www.youtube.com/subscription_center?add_user=keeroyz Splash screen/thumbnail design: Felícia Fehér - http://felicia.hu Károly Zsolnai-Fehér's links: Patreon → https://www.patreon.com/TwoMinutePapers Facebook → https://www.facebook.com/TwoMinutePapers/ Twitter → https://twitter.com/karoly_zsolnai Web → https://cg.tuwien.ac.at/~zsolnai/ ## Содержание ### [0:00](https://www.youtube.com/watch?v=ziMHaGQJuSI) Segment 1 (00:00 - 03:00) Dear fellow scholars, this is two minute papers with Kohaa Eher. Genetic algorithms help us solve problems that are very difficult, if not impossible, to otherwise write programs for. For instance, in this application, we have to build a simple car model to traverse this terrain. Put some number of wheels on it somewhere, add a set of triangles as a chassis, and off you go. This is essentially the DNA of a solution. The farther it goes, the better the car is. And the goal is to design the best car you possibly can. First, the algorithm will try random solutions. And as it has no idea about the concept of a car or gravity, it will create a lot of bad solutions that don't work at all. However, after a point, it will create something that is at least remotely similar to a car, which will immediately perform so much better than the other solutions in the population. A genetic algorithm then creates a new set of solutions. However, now not randomly, it respects a rule that we call survival of the fittest, which means that the best existing solutions are taken and mixed together to breed new solutions that are also expected to do well. Like in evolution, in nature, mutations can also happen, which means random changes are also applied to the DNA code of a solution. We know from nature that evolution works extraordinarily well and the more we run this genetic optimization program, the better the solutions get. It's quite delightful for a programmer to see their own children trying vigorously and succeeding at solving a difficult task. Even more so if the programmer wouldn't be able to solve this problem by himself. Let's run a quick example. We start with a set of solutions. The DNA of a solution is a set of zeros and ones which can encode some decision about the solution whether we turn left or right in the maze or it can also be an integer or any real number. We then compute how good these solutions are according to our taste. In the example with cars, how far these designs can get. Then we take for instance the best three solutions and combine them together to create a new DNA. Some of the better solutions may remain in the population unchanged. Then probabilistically random mutations happen to some of the solutions which help us explore the vast search space better. Rinse and repeat. And there you have it. Genetic algorithms. I have also coded up a version of Roger Oing's Evola problem where the famous Mona painting is to be reproduced by a computer program with a few tens of triangles. The goal is to paint a version that is as faithful to the original as possible. This would be quite a difficult problem for humans, but apparently a genetic algorithm can deal with this really well. The code is available for everyone to learn, experiment, and play with, and it's super fun. And if you're interested in the concept of evolution, maybe read the excellent book, The Blind Watchmaker by Richard Dawkins. Thanks for watching and for your generous support. And I'll see you next time. --- *Источник: https://ekstraktznaniy.ru/video/14903*