projet abeilles .pdf



Nom original: projet abeilles.pdf

Ce document au format PDF 1.4 a été généré par TeX / MiKTeX pdfTeX-1.40.10, et a été envoyé sur fichier-pdf.fr le 28/04/2014 à 16:19, depuis l'adresse IP 194.199.x.x. La présente page de téléchargement du fichier a été vue 777 fois.
Taille du document: 658 Ko (12 pages).
Confidentialité: fichier public


Aperçu du document


Projet d’algorithme g´en´etique sur les Abeilles
Thomas Schmitt
Mars 2014

Sommaire
1 Motivation

2

2 Impl´
ementation
2.1 Cerveau des abeilles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Population et S´election . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
3

3 Courbes de fitness
3.1 Estimation des param`etres . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Interpr´etation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 R´esultats (simulation sans ruche) sur les jeux de param`etres . . . . . . . . .

5
5
5
9

4 Suite...

12

5 Annexe

12

1

1

Motivation

Je voulais simuler des populations, de fa¸con non supervis´e, pour observer une s´election
naturelle conduisant a` des ph´enom`enes ´emergents. Ayant entendu parler des r´eseaux de
neurones, je voulais aussi faire un projet qui me permettrai de les ´etudier, afin de m’en
impr´egner. Finalement, j’ai choisis Matlab, pour ses structures simples. Dans ce projet, je me
suis efforc´e de laisser tout mes param`etres variables. J’ai d´evelopp´e une interface graphique
a` cette fin (cf Figure 2)

But du jeu
Dans cette simulation, les abeilles devront parcourir la carte pour chercher du miel. Elles
devront apprendre a` ´eviter le feu et dans une seconde partie (non aboutie) apprendre `a
ramener le miel a` la ruche. Elle devront apprendre cela sans supervision. Il n’y aura qu’une
s´election entre chaque g´en´eration, qui gardera les mieux adapt´es.
Une petite vid´eo pour voir les abeilles se d´eplacer :
http://youtu.be/YfdQGzU3yo0

2
2.1

Impl´
ementation
Cerveau des abeilles

Le cerveau des abeilles est un r´eseau de neurones classique. Le nombre de couches cach´ees
est variable (nb couches cachees), ainsi que le nombre de neurones de chaque couches.

Figure 1 – R´eseau de neurones utilis´e pour les cerveaux.
Il y a 4 neurones de r´etine pour voir le miel (chacun codant une direction), 4 pour le feu,
4 pour la position de la ruche et 1 pour savoir s’il l’on transporte d´ej`a un miel. Les abeilles
ne voient pas plus loin que dist vision autours d’elle (sauf la ruche). Il y a 4 neurones de
sorties. L’abeille choisit alors le max pour se diriger. L’apprentissage se fait par s´election
naturelle (cf section suivante).
2

2.2

Population et S´
election

Figure 2 – Interface lors d’un test de simulation.
Sur un damier de X × Y, il y a :
– nb abeilles abeilles qui vont se d´eplacer chaque tours.
– nb miel miel plac´e al´eatoirement. Qui, une fois pris, r´eapparaissent ailleurs.
– nb feu feu plac´e al´eatoirement. R´epartit en plusieurs ilˆot, qui seront g´en´er´e `a chaque
nouvelle g´en´eration d’abeilles(cf Remarque).
– La ruche, au centre de la carte. (Qui permet aux abeilles de ramener leur miel).
A la premi`ere g´en´eration, les abeilles ont chacune un cerveau ind´ependant et tir´e au
hasard (i.e. chaque coefficients synaptique est tir´e au hasard). A la premi`ere g´en´eration,
certaines sont attir´e par le feu, d’autre continue toujours en ligne droite etc.
A la fin d’une g´en´eration, (de nb tours), on s´electionne les abeilles avec la meilleure
fitness. On garde une copie de chacune d’elles inchang´es, puis on en cr´e´e de nouvelles copies,
en modifiant leurs g´enomes (avec un taux moyen de taux mutation % et une amplitude
moyenne de amplitude).
Remarque Apr`es observations, j’ai remarqu´e qu’il faut g´en´erer une nouvelle map a` chaque
g´en´eration, sinon c’est plus la connaissance de la carte, que la capacit´e `a chercher du miel,
qui s’inscrit dans les neurones.
Fitness d’une abeille Le calcul du score (fitness) se fait par trois param`etres : score miel, score feu
(n´egatif) et score ruche (rapporter un miel `a la ruche). Il est int´eressant de chercher `a optimiser ses valeurs, qui servent `a la s´election naturelle et `a l’´evaluation de la fitness d’une
population.

3

3

Courbes de fitness

Figure 3 – Courbes de fitness. En abscisse le nombre de g´en´eration, en ordonn´ee le score (en
rouge : pour la meilleur abeille, en vert : la moyenne pour les meilleurs venant de l’ancienne
g´en´eration et en bleu la moyenne sur toutes les abeilles) Dans la suite, on ne s’int´eressera qu’`a
la courbe verte (moins bruit´e et plus significative - car ne tient pas compte des mutations
d´el´et`eres cr´e´e).

• Le r´esultat qui nous int´eresse est la courbe qui repr´esente la fitness d’une population au
cours des g´en´erations. Soit : le score moyen, (cumul´e sur nb tours) de chaque g´en´eration.

3.1

Estimation des param`
etres

On estime l’´evolution (de la fitness) d’une population a` l’aide d’une fonction sigmo¨ıde,
d’une fonction exponentielle (ou de deux fonction exponentielles - si il y a deux sauts) de
param`etre a max et τ .
1
1 + e−(t−τ )
exp(t) = a max(1 − exp(−t/τ )
sigmo(t) = a max

Ici, τ est le temps caract´eristique que prend une population a` obtenir une ´evolution
significative (0 < τ < 600) et a max repr´esente la fitness maximale d’un population (apr`es
600 g´en´erations).

3.2

Interpr´
etation

On observe plusieurs ph´enom`enes :
4

Figure 4 – Une fonction de fitness ordinaire, approch´e par une courbe param´etr´e

– La hauteur du palier (a max) : fitness maximal.
– La vitesse de convergence vers un palier (τ ) : traduit le temps caract´eristique d’apprentissage.
– Un ´eventuel deuxi`eme palier, traduisant l’apparition d’un nouveau saut dans l’´evolution.
– (un temps de lag au d´ebut, une d´ecroissance du score, des effets stochastiques plus ou
moins fort, etc)
Deuxi`
eme palier L’existence de plusieurs palier dans le graphe du score traduit un saut
dans l’´evolution, une mutation qui va se r´epandre dans la population. (cf Figure 5 et Figure 6
ligne 1, colonne 1 et 2) En observant des simulations j’ai remarqu´e que dans une premi`ere
phase, les abeilles ne se d´eplacent que dans un direction privil´egi´e (`a droite par exemple)
et ´eventuellement dans une autre (en haut). Puis, elle apprennent (en ´equilibrant les poids
synaptiques je suppose) `a aller aussi en bas. Une ´evolution notable arrive lorsqu’elle savent
faire demi tour.

ecroissance du score On observe parfois des d´ecroissances dans la courbe des score. Car
nous n’analysons toujours qu’un pourcentage des meilleures abeilles (celles qui existaient `a
la g´en´eration pr´ec´edente). Lorsqu’une mutation favorable est trouv´e, elle se r´epand et profite
a` toutes les abeilles. Les miels sont donc plus rares, pour les quelques unes privil´egi´ees qui
poss´edaient la mutation.

5

Figure 5 – La courbe pr´esente deux palier

6

Figure 6 – 9 courbes de g´en´erations
7

3.3


esultats (simulation sans ruche) sur les jeux de param`
etres

Dans ces analyses, nous nous sommes restreint au cas sans ruche. Les abeilles ne voient
que le miel et le feu, elles ont donc 8 neurones de r´etines. Nous avons ici 71 jeux de param`etres.
(exemple de cinq abeilles s´electionn´es : http://youtu.be/buskLCRXCX4)
Les param`etres que j’ai test´e sont :
– Le nombre de couches cach´ees de neurones.
– Le nombre de neurones dans chaque couches cach´ees.
– Le taux de mutation.
– l’amplitude des mutations.
– le nombre d’abeilles s´electionn´ee pour se reproduire.

Figure 7 – Influence du nombre de couches cach´ees sur τ et a max. Il est clair que le
nombre de couches cach´ees optimal ici est 0. (Minimise le temps caract´eristique et maximise
la fitness maximale

´
Figure 8 – Influence du nombre de coefficients synaptique. Etant
proportionnel au nombre
de couches cach´ees, les r´esultats ´etaient pr´evisibles.

8

Figure 9 – Influence du pourcentage de mutation (nombre de coefficients synaptique qui
varient lors d’une mutation). On ne remarque pas de tendance particuli`ere. Beaucoup de
r´esultats exclue au del`a de 80%

Figure 10 – Influence de l’amplitude lors des mutations. L`a non plus, pas de tendance
significative.

9

Figure 11 – Observation de 9 jeux de param`etres. La courbe 9 n’est pas s´electionn´ee pour
les r´egression (car a max et τ n’ont pas de signification dans ce cas).

10

4

Suite...

Analyse des donn´
ees Il reste encore `a bien analyser la corr´elation entre les param`etres
que nous avons fait varier et les les mesures τ et a max obtenue. (il faudrait faire plus de
simulations avec des param`etres qui varient plus.)
Optimisation de la fonction score Le score des abeilles augmente a` chaque fois qu’elle
passe sur un miel. On pourrait imaginer un score qui ne d´epende que du nombre de miels
ramen´es a` la ruche (et de feux travers´es). Mais des probl`emes surviennent : le saut entre un
cerveau al´eatoire et un cerveau adapt´e semble trop grand. (Le fait de r´ecompenser le passage
sur un miel permet de ”guider” la s´election). (Probl`eme d’amor¸cage.)
Plusieurs esp`
eces Dans le future, j’aimerai que plusieurs esp`eces puissent ´evoluer simultan´ement, pour faire ´emerger des adaptations entre les esp`eces. Car pour l’instant, au final,
toutes les abeilles ont la mˆeme strat´egie. Parfois, il est plus int´eressant d’avoir deux groupes
avec des strat´egie diff´erentes.

5

Annexe

Figure 12 – L’arbre g´en´ealogique des abeilles sur le terrain. A la 67`eme g´en´erations, trois
lign´ees ont surv´ecut. (En g´en´eral, a` la 500`eme g´en´eration, il n’y a plus qu’un seul ancˆetre
commun)

11

Figure 13 – Apr`es 1700 g´en´erations. En haut : les coefficients synaptiques des deux couches
cach´ees. En bas : leur variance dans la population (´echelle `a 10−16 : l’ancˆetre commun est
proche, et les abeilles n’´evoluent plus - d’o`
u la n´ecessite d’une autre esp`ece, qui ´evolueraient
de fa¸con ind´ependante.)

Figure 14 – 16 arbres g´en´ealogiques (presque tous ´ecras´es). A mettre en rapport avec la
Figure 13

12


Aperçu du document projet abeilles.pdf - page 1/12
 
projet abeilles.pdf - page 2/12
projet abeilles.pdf - page 3/12
projet abeilles.pdf - page 4/12
projet abeilles.pdf - page 5/12
projet abeilles.pdf - page 6/12
 




Télécharger le fichier (PDF)


projet abeilles.pdf (PDF, 658 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


projet abeilles 1
projet abeilles
gestion de donnees massives lecocq sitbon
la ruche n 1 edition du 20 avril 2017
projet dona gombert lecocq
allen institue challenge lecocq sitbon

Sur le même sujet..