Embed Size (px)
Citation preview
L’Evolution ArtificielleUn solveur générique basé sur les systèmes complexes
massivement parallèles
Pr Pierre ColletDépartement d’Informatique de
L’UFR Mathématique et Informatique deL’Université de Strasbourg
Équipe de rechercheBioinformatique Théorique, Fouille de Données et Optimisation Stochastique du
Laboratoire des Sciences de l’Image, de l’Informatique et de la Télédétection (ICUBE)http://lsiit.u-strasbg.fr/bfo_fr
Campus Numérique des Systèmes ComplexesDe l’Université de Strasbourg
Qu’est-ce qu’un Système Complexe ?
Que sont les Systèmes Complexes ?
� Système Complexe : tout système composé d’un grand nombre d’entités autonomes en interaction, créant plusieurs niveaux d’organisation collective aboutissant à des comportements émergents.
� Exemple de comportement collectif par interactions directes entre individus :
https://www.youtube.com/watch?v=qJjeHLcbQJ0https://www.youtube.com/watch?v=Zciq3L5-JU4
https://www.youtube.com/watch?v=Jw7yee-Eaf0https://www.youtube.com/watch?v=b8eZJnbDHIg&feature=related
Question :
Peut-on reconstruire des
phénoménologies complexes
avec des règles simples ?
Boids de Craig Reynolds (1986)
� Trois règles simples !
Suivre ses voisins(ajuster direction et vitesse à
la moyenne de ses voisins)
Cohesion(aller vers le centre degravité de ses voisins)
Eviter lesvoisins
https://www.youtube.com/watch?v=OgXTQQIo6fc
http://www.red3d.com/cwr/boids/
Les Systèmes Complexes sont partout
Émergence par stigmergie
� Des interactions de bas niveau permettent l’émergence de comportements « intelligents » à un niveau supérieur.
� Phrase d’Aristote : le tout est plus que la somme des parties.
� Exemple :
7
les fourmis !
Les Systèmes Complexes sont partout !
8
Comprendre l’émergence : comment 1+1=3 ?
1
1 = 0 !
1+1+1= pas grand chose, sauf si…
12
Évolution Artificielle
Evolution: un SC créatif !
Darwinian evolution is creative !
14
Divesity is huge
Computers are number crunching machines
� Can they be made creative by implementing into them a naturally creative process?
Among the very first things tested on a computer!� 1944: ENIAC (Electronic Numerical Integrator And Calculator)
� 1950: AI has a small headstart: A. Turing writes the first papers on what « intelligent
computers should be » and introduces the Turing Test Shannon publishes a detailed analysis of the game of
Chess using a problem solving approach� 1953: First tests on AE in the US, Austalia and Europe
First commercial computer (IBM650)
Pierre Collet : Introduction àl'Evolution Artificielle
17
IA/EA history� 1955 : « logic theorist » by Newell and Simon, representing a
problem as a tree.� 1956 : McCarthy invites his colleagues for the « Dartmouth
Summer Research Project on Artificial Intelligence ».� 1957: Fraser evolves bitstrings using a crossover operator� 1957: General Problem Solver, by Newell, Shaw et Simon,� 1958: Friedberg suggests that computers could self-program
themselves by successive mutations of their code� 1958 : McCarthy comes up with LISP� 1959: Friedmann writes a paper on how evolution could be
artificially simulated…
Pierre Collet : Introduction àl'Evolution Artificielle
18
Latest developments� Early results: few but interesting� Since 1990, computing power is there many new development
in the field, including Genetic Programming by J. Koza.� Since 2000, routine human-competitive results with Artificial
Evolution and Genetic Programming� Currently: AE widely used in industry (train timetables in Italy,
vehicle routing by DHL, optimal diamond cutting, lenses design, … cf. application tracks of conferences in artificial evolution (GECCO, EvoStar).
� Many companies use them but say otherwise!!!
Standard Artificial Evolution loop
Stop ?Stop ?
PopulationPopulationinitialisationinitialisation
Selection ofSelection ofnn parentsparents
VariationVariationoperatorsoperators(Xover +(Xover +mutation)mutation)
ReductionReduction
ParentsParentsParents
Parents+children
Parents+cParents+childrenhildren
GenerationsGenerations
BestBestIndividualIndividual
Wea
k el
itism
Wea
k el
itism
Chi
ldre
n cr
eatio
nC
hild
ren
crea
tion
Stro
ng e
litis
mSt
rong
elit
ism
evaluationevaluation
evaluationevaluation
20
Practical example with French crêpes...
� What is the genome of a crêpe?� Create a random population of 100 individuals within limits (3 liters mixing bowl)
� Evaluation of an individual:
� Create a population of 50 baby crêpes :
� Objective: Find the best crêpes recipe
� Select the 100 best individuals in the population of 100 parents and 50 children and start over on a new generation.
{Flour(g), Milk(l), Eggs(n), Salt(pinches)}
{232, 2.24, 1, 48}, {1723, 0.02, 5, 7} , …, {5, 0.01, 8, 3}
1.Mix the batter2.Cook a crêpe3.Find a victim to taste the result and take a photo of his face…
Select 2 “good” parents and perform a crossover:{234, 0.34, 8, 7}, {26, 1.4, 5, 22} {234, 0.34, 5, 22}
Mutate the obtained genome:Evaluate the child
{234, 0.34, 6, 22}
Creativity is reacheable within a small domain
� Look at the first generation!
What will Mr Bean probably rate as the best?{232, 2.24, 1, 48}, {1723, 0.02, 5, 7} , …, {5, 0.01, 8, 3}
� The outcome of artificial evolution of crêpes could be…
Synergy with revolution in computer science
Solution for more powerful CPUs:multi-core CPUs
Peak at 3.6 GHzin 2005
Going faster ?
AMD Phenom II X4 940 BE running at 6Ghzin a bath of liquid nitrogen at -195°C...
Multi-core is more energy-efficient� Power consumption grows with the cube of clock speed!� Multiplying slower cores exploits Moore’s law and gets more
operations/second done, albeit in parallel...
2012 Nvidia 690 (300W, $1000):• 2 x 1536 (3072) 915MHz cores• 2 x 2Gb Global memory• 2 x 192 Gb/s bandwidth• 2 x 2.8 TFLOP/s (5.4 TFLOP/s total)
2000 IBM ASCI White supercomputer at Livermore Labs, USA 106 Tons, 3MW +3MW for cooling, $110M 8000 procs @ 375MHz, 6TB, 7.226 TFLOPS
Massively Parallel Computers are here!
And possibly 4 cards per computer !
Nvidia Tesla K20:• 90 FP32 multiprocessors• 30 FP64 multiprocessors• 3840 cores in total• 24 Gb Global memory• 288 Gb/s bandwidth• 6 TFLOP/s SP, 1,7TFLOP/s DP
Artificial Evolution is inherently parallel!
Stop ?Stop ?
PopulationPopulationinitialisationinitialisation
Selection ofSelection ofnn parentsparents
VariationVariationoperatorsoperators(Xover +(Xover +mutation)mutation)
ReductionReduction
ParentsParentsParents
Parents+children
Parents+cParents+childrenhildren
GenerationsGenerations
BestBestIndividualIndividual
Wea
k el
itism
Wea
k el
itism
Chi
ldre
n cr
eatio
nC
hild
ren
crea
tion
Stro
ng e
litis
mSt
rong
elit
ism
evaluationevaluation
evaluationevaluation
Massively parallel EC is very creative
�3 micro-satellites transmit collected data towards earth
27
�NASA ST-5 mission
Problèm: find a small enough antenna
� Nasa engineers unable to find a small enough antenna.� Provided physical electromagnetic equations and antenna
simulators to their team of computer scientists experts in Artificial Evolution.
After 3 weeks of calculation on a NASA massively parallel supercomputer (in 2004)
28
ST- 5 mission launched in 2006
29
First nonFirst non--human technology sent human technology sent in space !in space !
Creativity vs inventivity vs innovation� Inventivity makes massive use of past human discoveries
(databases of patents, inventing new solutions using predefined rules / principles, …)
� No inventivity process could have come up with ST-5 antennae: even though engineers now know they exist, they cannot design new ones => “non-human technology”
� ST-5 antennae are the result of a creative process (evolution) that may come up with unexpected (and even unknown) results, that are certainly innovative.
� Creativity can come up with new solutions within narrow domains
� Inventivity or creativity both lead to innovation.
Why AE will have great impact in the future
� CHEAP project in Strasbourg (14k€): Heterogeneous Cluster for Parallel Artificial EvolutionTotal = 41000 GPU cores + 210 CPU cores ~ 100 Tflops20 machines with 1x NVIDIA GTX680 cards (1536 cores, 4GB, 3.1 TFlops) = 30720 cores / 62 TFlops15 machines with 2x NVIDIA GTX560TI (352 cores, 2GB, 1.26TFlops) = 10560 cores / 37,8 Tflops
8 exaflops/day!!!� June 2012 Top 500 super-computers:
Current EASEA platform in Strasbourg
� What does our 100 Tflops – 8 Exaflops/day supercomputer looks like ?
Artifcial evolution
� Routinely competitive with human intelligence since 2000(cf. http://www.human-competitive.org)
� Currently widely used in the industry to find creative solutionswithout expertise on the domain:
NOZOMI 700 Shinkanzen
� Bright future because: Can exploit loosely coupled massively parallel computers
and exascale computers on generic problems!
Benchmarks
34
1000 dimensions Rastrigin function
Old GTX275 vs Core i7 950
� GPU / CPU speedup
35
Multi-island acceleration on Rastrigin
36
20 machines 10 machines 5 machines 1 machine
Same pop size !
Speedup on Weierstrass with 1x GTX580
37
x284.5
Speedup on Weierstrass function
38
SupralinearSpeedup !
High-level massive parallelism (island model)
AE can run efficiently with loosely coupled computers sending individuals in connection-less mode (UDP)
EAs can exploit loosely coupled clusters
Or clouds of loosely coupled computers
Computing eco-systems
Beowulf cluster of machinesGrid
CloudSingle machine
Application to a real problem: Zeolite search
� Looking for the structure of a zeolite: Zeolites are porous crystalline structures
with many applications in industrymade of oxygen atoms arounda silicon or aluminium atom.
A replication of the unitstructure allows to obtainthe pores.
Zeolites are used for filtering, catalysis, energy storing, medicine, absorbing liquids, odours (cat litter), …
43
GPU acceleration on zeolite pb
44
~120 with GTX275
Island model on zeolite problem
� 1, 5, 10 and 20 GPU machines
45
New zeolitepublished in Science !
Time on one machine:
20x120=2400 speedup40 h EASEA = 96000 h= 10.95 years
GP regression of state space models for drone
� 6 non-linear necessary for an airplane autopilot (3 translations and 3 rotations) but only 3 for an octocopter (3 rotations)
� 10 variables� 3 operators (+, *, -)� 10800 individuals� 300 generations� Max depth: 15
Results in minutes rather than hours
Roll non-linear equation (learning set)
Roll equation test set 1
Roll equation test set 2
Conclusion
� Des règles simples peuvent reconstruire des phénoménologies complexes
� Objectif de la science des systèmes complexes : Trouver un formalisme permettant de trouver un
modèle correspondant au mieux à une phénoménologie observée
� Comportement collectif par interaction directe : Comportement émergent typique : mouvement de
foule, buzz dans les réseaux sociaux, krach boursier, …
CNSC Strasbourg� Complexes Systèmes transverses à l’Université :
Chimie Physique Biologie Mathématiques Informatique Musique Ethologie Sciences Humaines et Sociales … Sciences de la terre ?
CNSC Strasbourg : activité
CNSC Strasbourg : recherche
Conclusion Systèmes Complexes
� Des règles simples peuvent reconstruire des phénoménologies complexes
� Objectif de la science des systèmes complexes : Trouver un formalisme permettant de trouver un
modèle correspondant au mieux à une phénoménologie observée
� Comportement collectif par interaction directe : Comportement émergent typique : mouvement de
foule, buzz dans les réseaux sociaux, krach boursier, …
Evolution artificielle et SC
� Solveur générique fondé sur les Systèmes Complexes� Capable d’utiliser la puissance de calcul de machines
massivement parallèles
