B2 · Episode 3 · 5:46
Evolution as an algorithm
Evolution is compared to searching for a peak. Simple problems are easy to compute; harder ones need a method that looks more like biological evolution.
Source：Nathan / skeptikon.fr · License：CC0 1.0
Transcript
En x égal à- 3, on a en fait ce qui est appelé un minimum local.
At x equals -3, we actually have what is called a local minimum.
Faire le forcing, c'est une façon de résoudre numériquement le problème avec
Forcing is a numerical way to solve the problem,
précision qui marche bien pour des expressions simples.
with accuracy that works well for simple expressions.
Mais dans le cas d'expressions plus complexes, souvent rencontrées en recherche,
But for more complex expressions—often encountered in research—
on arrive très vite aux limites même des meilleurs ordinateurs de la planète.
we quickly hit the limits even of the planet’s best computers.
Le forcing implique tout simplement trop de calculs.
Forcing simply involves too many calculations.
Dans l'univers des méthodes de résolution numérique,
Within the universe of numerical solution methods,
l'enjeu c'est de trouver des méthodes qui s'éloignent le plus possible du forcing,
the challenge is to find methods that stray as far as possible from forcing,
sans pour autant s'arrêter au premier minimum local.
without stopping prematurely at the first local minimum.
Aujourd'hui encore, c'est un important domaine de recherche dans les universités du
Even today, this remains an important research area in universities worldwide.
monde entier. Ce que je vais vous présenter maintenant,
What I’ll present to you now is
c'est la méthode la plus folle que j'ai croisée durant mes années de thèse.
the most astonishing method I encountered during my doctoral studies.
qui mimique rien de moins que les mécanismes de l'évolution pour arriver à ses fins.
It mimics nothing less than the mechanisms of evolution to achieve its goals.
L'évolution, en voilà un phénomène passionnant.
Evolution—an absolutely fascinating phenomenon!
Il concerne des choses qu'on appelle des êtres vivants.
It concerns things we call living beings.
Alors le vivant, en gros, est constitué d'organismes capables de faire des copies
Roughly speaking, life consists of organisms capable of making copies of themselves.
d'eux- mêmes. Ces copies sont imparfaites,
These copies are imperfect,
et donc les individus présentent un certain nombre de différences les uns avec les
so individuals differ from one another in various ways.
autres. Au fil des générations, ces différences vont s'accumuler,
Over generations, these differences accumulate,
peuvent devenir hyper importantes,
and may become extremely significant,
et elles aboutissent à une grande diversité dans les formes que prend le vivant,
ultimately leading to great diversity in the forms life takes.
puisqu'on parle un peu du vivant.
Since we’re talking about life, let’s say a bit more.
Quand un caractère rend l'individu moins apte à se reproduire,
When a trait makes an individual less fit to reproduce,
l'environnement, qui n'est pas très charitable, va
the environment—which is not very charitable—will
éliminer la variation.
eliminate that variation.
Ça, en résumé, c'est ce qu'on appelle la sélection naturelle.
This, in short, is what we call natural selection.
Et selon les différents types de milieux, la forêt, la toundra,
And depending on different types of environments—such as forests or tundra—
le sous- sol ou votre intestin,
underground soil, or even your gut—
ce sont différents caractères qui apporteront assez d'avantages pour être
different traits will provide enough advantage to be selected.
sélectionnés. Et le truc, c'est que l'environnement est une chose changeante.
The key point is that the environment itself is constantly changing.
Le climat, le relief, l'altitude.
Climate, terrain, and altitude—
la présence de proies, de compétiteurs, de dangers ou de ressources,
the presence of prey, competitors, dangers, or resources—
tout ça est très dynamique à l'échelle du temps géologique.
all of these are highly dynamic on a geological timescale.
Nous ne vivons plus dans le même monde qu'il y a vingt mille ans,
We no longer live in the same world as twenty thousand years ago—
quand une calotte polaire d'un kilomètre d'épaisseur descendait jusqu'au massif
back then, a one-kilometer-thick ice sheet extended down to the Massif Central—
central, de toute évidence.
that much is clear.
Ce qui permet aux organismes de ne pas tous crever dès que le temps change,
What prevents organisms from all dying immediately when conditions change is
c'est leur diversité.
their diversity.
Et ce réservoir d'adaptation face aux incertitudes de l'environnement est alimenté
This reservoir of adaptability to environmental uncertainties is fueled by
par des phénomènes qui modifient les génomes.
phenomena that alter genomes.
Ce sont les mutations.
These are mutations.
Chaque individu, à chaque génération,
Each individual, in every generation,
porte dans toutes ses cellules des petits changements par rapport au code de ses
carries small changes in all its cells compared to its parents’ genetic code.
parents. Si le changement touche une séquence absolument vitale,
If the change affects an absolutely vital sequence,
c'est dommage pour lui, il ne finira pas son développement.
it’s bad luck for him—he won’t complete development.
D'autres fois, il naîtra mais mal portant.
Other times, he’ll be born but in poor health.
Le plus souvent, il ne sera pas différent de ses sœurs, frères et cousins.
Most often, he’ll be no different from his siblings and cousins.
Mais de façon exceptionnelle, sa différence pourra le rendre plus apte à,
Yet exceptionally, this difference may make him better able to—
au choix, grandir, survivre, séduire un
choose one: grow, survive, attract a mate,
partenaire, engendrer des descendants ou les protéger.
produce offspring, or protect them.
Ce qui fait l'affaire de ces mutations,
What makes these mutations successful is that
car aura plus de chances de se propager au sein de la population.
it has a greater chance of spreading within the population.
Vous imaginez bien que le monde réel est plus compliqué que ce que je viens de vous
You can well imagine that the real world is more complicated than what I've just described,
raconter, mais si vous avez compris ça,
but if you've grasped this,
vous disposez des concepts essentiels et vous devriez pouvoir suivre le reste de la
you now have the essential concepts,
vidéo sans plus de difficulté qu'un félin moyen.
and you should be able to follow the rest of the video with no more difficulty than an average cat.
Vive les chiens.
Long live dogs!
À bientôt Nathan.
See you soon, Nathan!
D'ailleurs tu peux couper si tu veux le vive les chiens,
By the way, feel free to cut the 'Long live dogs!' part,
je peux comprendre que tu sois extrêmement intolérant.
I can understand you finding it extremely intolerable.
Repartons de l'expression dont le minimum global se trouvait en x égal zéro,
Let's start again from the expression whose global minimum occurs at x equals zero,
mais ça on va l'oublier et repartir de rien.
but we'll set that aside and start from scratch.
Je commence par choisir une douzaine de points au pif entre moins cinq et cinq,
I begin by randomly selecting about a dozen points between minus five and plus five,
c'est l'étape d'initialisation.
this is the initialization step.
Ces douze points représentent douze organismes qui vivent leur vie.
These twelve points represent twelve organisms living their lives.
La seule caractéristique biologique de ces organismes, c'est leur valeur de x:
The only biological trait of these organisms is their x-value:
celui le plus à droite a la plus grande valeur de x,
the one farthest right has the largest x-value,
celui tout à gauche la plus faible.
and the one farthest left has the smallest x-value.
L'environnement dans lequel ces organismes vivent, comme le disait Thomas,
The environment in which these organisms live—as Thomas put it—
il n'est pas très charitable.
is not very kind.
Il va éliminer sans pitié, disons, 25% des organismes à chaque cycle.
It ruthlessly eliminates, say, 25% of the organisms each cycle.
Pour déterminer lesquels, on va calculer notre expression pour chacun d'eux.
To determine which ones get eliminated, we'll compute our expression for each organism.
Plus le résultat est élevé, moins on dira que l'organisme est adapté à son
The higher the result,
environnement.
the less adapted the organism is to its environment.
Plus le résultat est faible, plus l'organisme sera considéré adapté.
The lower the result, the better adapted the organism is.
Les trois points en rouge passent donc à la trappe.
So, the three red points are eliminated.
Les organismes qui restent vont maintenant faire des bébés pour remplacer les trois
The remaining organisms now reproduce to replace the three that died.
morts. Disons que deux de ces nouveau- nés seront le fruit d'une mutation aléatoire.
Let’s say two of these newborns result from random mutations.
Ça veut juste dire que leur valeur de x est prise au hasard entre- 5 et 5.
This simply means their x-values are randomly chosen between -5 and 5.
Le troisième nouveau- né, lui, sera similaire aux neuf survivants.
The third newborn, however, resembles the nine survivors.
Je vais le simuler simplement en faisant la moyenne des neuf survivants.
I’ll simulate it simply by taking the average of the nine survivors.
Voilà. Un premier cycle est passé, passons au second.
There we go—first cycle complete; let’s move on to the second.
L'environnement élimine à nouveau les trois organismes les moins adaptés.
The environment again eliminates the three least-adapted organisms.
Souvent les mutants y passent car c'est le propre des mutations,
Mutants often get eliminated, because it’s in the nature of mutations—
elles donnent généralement des individus mal adaptés.
they usually produce poorly adapted individuals.
Afin de remplacer les morts, deux nouveau nés sont obtenus par mutation à nouveau,
To replace the dead, two more newborns arise from mutation,
un autre est la moyenne des neuf survivants.
and another is the average of the nine survivors.
Le second cycle est complet.
The second cycle is complete.
On a l'impression que ce petit jeu ne rime pas à grand- chose,
This little game may seem pointless,
mais si je presse sur l'accélérateur et multiplie les cycles,
but if I hit the accelerator and run many more cycles,
regardez ce qui se passe.
look at what happens.
À l'exception des mutants, les organismes se ressemblent de plus en plus,
Except for mutants, the organisms grow increasingly similar,
c'est- à- dire que leur différence, la diversité de l'ensemble,
meaning their differences—the population’s diversity—
est en baisse.
is decreasing.
Les organismes sont de mieux en mieux adaptés à leur environnement,
Organisms become better and better adapted to their environment,
se concentrant autour de x égale zéro.
converging around x = 0.
C'est lent et il faut 57 cycles avant d'obtenir une convergence satisfaisante.
It’s slow: 57 cycles are needed before we achieve satisfactory convergence.
On peut recycler la même approche pour résoudre le problème de Caju,
We can reuse this same approach to solve Caju’s problem:
à savoir trouver un diamètre de boîte de conserve qui minimise la surface de métal
finding the can diameter that minimizes metal surface area while keeping volume constant.
de la boîte lorsque le volume est maintenu constant.
—i.e., the metal surface area of the can.
Une convergence satisfaisante autour de 5,
A satisfactory convergence around 5.9,
9 est cette fois obtenue après seulement quatorze cycles.
is achieved this time after only fourteen cycles.
Je ne sais pas pour vous, mais moi, la première fois qu'on m'a montré ce bazar,
I don’t know how you feel, but for me,
j'en suis tombé de ma chaise.
the first time I saw this thing, I fell off my chair.
Ce dont je viens de vous faire la démonstration est appelé un algorithme
What I’ve just demonstrated to you is called an evolutionary algorithm,
évolutionnaire, et je trouve ça dingue que ça marche si bien.
and I find it mind-blowing that it works so well.