Embed Size (px)
Citation preview
1
Algorithmes Algorithmes Evolut ionnairesEvolut ionnaires
Systèmes Artificielles Complexes
2
La Vie Art if icielle:
Créer des méthodes de résolut ion de problèmes en s'inspirant de la nature
Le cerveau Réseaux de neurones
L'évolut ion Algorithmes évolutionnaire
Méthodes bio- inspirées
Les fou rm is…
3
Algorithmes génétiques
Holland, 1975
"Computational Intelligence"
Algorithmes évolutionnaires Systèmes flous
Programmation évolutionniste
Stratégies d'évolution
Programmation génétique
Réseaux de neurones
Fogel, 1966
Rechenberg & Schwefel,
1973
Koza, 1989
Classification (WCCI)
PBIL
Baluja, 1994
4
Évolution Artificielle
"Meta Heuristiques"
Méthodes Stochastiques
Recherche Locale …
Recherche Tabou
Recuit Simulé
…
Classification (R.O.)
5
30 ans d’histoire, des milliers d’applicat ions dans tous
les domaines, > 4 conférences int l. (GECCO, CEC,
PPSN, EA), > 3 revues (Evolut ionary
Computat ion, IEEE Trans. on Evol.Computing, Complex Systems, BioSystems, J. of Heurist ics, J. of Global Opt imizat ion).
6
Pourquoi l’évolution ?
Résoudre un problème (d'opt imisat ion) :
Principe de l’évolut ion :
Parmi un grand nombre d’ individus, faire survivre ceux qui sont les mieux adaptés
Trouver la (ou les ) solut ion qui s'approche le plus d'un idéal
7
L’évolution
Les populat ions sont soumises à des variat ions aléatoires telles que :
Sélection naturelle
Croisements de gènes (G. Mendel) Mutations de gènes (G. Mendel)NeoDarwinnisme : sélect ion + variat ion aléatoire
Darwin : Théorie de l'évolut ion des espèces :
8
Chaînes d’ADN contenues dans les cellules
Terminologie biologique
Gènes : Part ies élémentaires de chromosome qui codent un trait
Allèles : Valeurs prises par les gènes
Locus : Posit ion d’un gène dans un chromosome
Chromosomes :
9
Les Algorithmes Génétiques
Algorithmes d’explorat ion basés sur la sélect ion naturelle et génét ique: Survie des structures les mieux adaptées Échange pseudo- aléatoire d’ informations
Imaginés dans les 60’s par J. Holland
Passer d’un ensemble de solutions potentielles à un autre en simulant
l’évolution
10
Applications
Optimisation
Apprentissage
Programmation automatique
Modélisation
Optimisation de fonctions, Planif icat ion ...
Programmes Lisp, Automates cellulaires ...
Classif icat ion, Prédict ion, Robotique ...
Marchés économiques, Comportements sociaux, Systèmes immunitaires ...
11
Mod èle Réel
Individu
Adaptat ion d’un individu
Populat ion d’ individus
Solut ion potent ielle
Échant illon de solut ions
Mesure de la qualité de la
solut ion
Métaphore biologique
12
Modèle RéelChromosome Génotype
Allèle
Gène
Solut ion codée
Élément du code (une variable)
Valeur d'une variable
Métaphore biologique
PhénotypeSolut ion
exprimée dans les termes du
problème
13
Cette métaphore facilite l’explicat ion et est source d'inspirat ion
Mais elle ne just if ie pas les choix algorithmiques !
Métaphore biologique
14
Exemples d’optimisation f(x ) = x + |sin (32x )| , 0 ≤ x < π
Chromosome :
Codage binaire Phénotype : Valeurs de x
Trouver les 50 acides aminés d’une protéine donnée
Chromosomes :
Séquence de 50 AA Fonct ion de f itness
: Différence d’énergie potent ielle des séquences
Fonct ion de f itness : f(x )
15
Particularités
Manipulat ion d’un codage des paramètres
Traitement d’une populat ion d’ individus
Évaluat ion de l’apt itude du système
Utilisat ion de règles probabilistes
Chaîne de caractères
« Parallélisme »
Pas de dépendance vis à vis du domaine
Pas d’énumérat ion de l’espace
16
Un exemple sans ordinateur
(Schoenauer / Bentley) Le problème
Trouver la forme d’un morceau de papier
qui met le plus de temps possible à tomber.
Difficultés Pas de simulat ion. Beaucoup de formes possibles.
17
18
19
20
21
22
23
24
25
Cycle d'un A.E.
26
Composantes d’un A.E.Initialisation
Par t irage uniforme dans Ω En tenant compte de connaissances à
priori Comme résultat d’une évolut ion
précédente …
La diversité est essentielle
27
Cycle d'un A.E.
28
Composantes d’un A.E.Sélection
Darwinisme : biais en faveur des plus adaptés
Si biais trop important : convergence prématurée
Si biais trop faible : pas de convergence
Déterministe, sur comparaison de fitness Proport ionnelle Stochastique
Généralement, le même individu peut être sélectionné plusieurs fois
29
Composantes d’un A.E.Sélection
Sélect ion déterministe Sélect ion uniforme Sélect ion stochast ique
Roulette Ranking Tournoi …
30
SélectionPt
« Que les meilleurs gagnent … pas toujours»
Fitness5539
14
8
Pt+ 1
54%33%
9%
4%
Roue de loterie
Proport ionnelle : probabilité dépent de la f itness
Ranking : probabilité dépent du rang dans la populat ion
Composantes d’un A.E.
31
Sélection
Composantes d’un A.E.
Tournoi de taille T: Choix uniforme de T individus (avec ou sans
remise) Rendre le meilleur
Taux t entre 0 et 1: Choix uniforme de 2 individus (avec ou sans
remise) Rendre le meilleur avec probabilité t
32
Remplacement
Composantes d’un A.E.
Générationnel : toute la populat ion Condit ionnel ou non Elit isme : le meilleur individu est préservé
Steady states (états f ixes): Une petite part ie de la populat ion est
remplacé Choix des individus à éliminer
33
Cycle d'un A.E.
34
Croisement 1- point
Recombinaison« Mon cerveau et votre beauté »
Opérateur soumis à une probabilité d’application
Composantes d’un A.E.
35
Recombinaison
Composantes d’un A.E.
Croisement 2- points
Croisement n- points
Croisement uniforme
Adapté à la recombinaison de chaînes de longueur f ixe sur des alphabets f inis
Cas des réels, des arbres, des permutat ions ?
36
Mutat ion 1- point
Mutation« Le hasard fait bien les choses »
Opérateur soumis à une (faible) probabilité d’application
Cas des réels, des arbres, des permutations ?
Composantes d’un A.E.
37
Croisement : Permet de grandes modif ications Les modif icat ions dépendent de la populat ion Plutôt opérateur d’exploitat ion Effets décroissants avec l’évolut ion
Mutation : Nécessaire Nécessité de pouvoir faire de grands pas Plutôt opérateur d’explorat ion Effets destructeurs augmentent avec
l’évolut ion
Croisement vs. Mutat ion
38
Cycle d'un A.E.
39
Evaluat ion des individus
Souvent l’étape la plus coûteuse = > Ne pas recalculer F(X) inutilement Utiliser une estimation de F(X) … mais pas trop longtemps, car
l’optimum approché est différent de l’optimum réel !
40
Critères d’arrêt
Pas si simple ! Quand on a trouvé l’optimum Quand on a trouvé un résultat
satisfaisant Quand on n’espère pas trouver mieux
(perte de diversité) mais il faut une « distance » entre individus
Quand le rapport (gain espéré / surcoût de calcul) est trop élevé
Quand on a épuisé ses ressources (Nb d’évaluations)
41
Diversité génét ique
Si les individus d’une populat ion se ressemblent trop:
La populat ion devient trop homogène L’évolut ion de la populat ion devient l’évolut ion
d’un individu Découverte du plus proche optimum local et
enlisement de la recherche.
En pratique, une populat ion qui a convergé ne se rediversif ie pas !
42
Exploitat ion des bons individus = recherche locale dans le voisinage
Exploration des zones inconnues de Ω = recherche globale : il faut pouvoir aller partout.
Excès d’exploitat ion = convergence prématurée
Excès d’exploration = marche aléatoire sans convergence
Explorat ion vs Exploitat ion
43
Accroissement de la diversité Mutation
Croisement
Diminut ion de la diversité Reproduction
Sélect ion des parents
Remplacement
Croisement
Explorat ion vs Exploitat ion
44
Préserver la diversité
• Traitement direct : augmenter le taux de mutation
• Rupture du compromis explorat ion/ exploitat ion
• Sélection à bruit réduit et croisement restreint• Réinit ialisat ion• Niches écologiques
• Facteur de surpeuplement• Partage des ressources
• Algorithmes évolut ionnaires topologiques• AE en île• AE sur grille
45
Représentat ion
Darwinisme basé sur la performance Opérateurs de variat ion basés sur la
représentation : Représentat ion binaire : Ω = 0,1N
Représentat ion réelle : Ω = RN
Représentat ion par arbres (GP) Représentat ion mixte …
Le choix de la représentat ion est crucial !
46
Paramétrage d'un AE
Représentat ion des individus
Fonct ion d'évaluat ion
Opérateurs Taux d'applicat ion
Choix du croisement
Choix de la sélect ion
47
Mesurer les performances
Object if : Comparer des variantes d'AG Définir des problèmes diff iciles Confronter la théorie avec la
prat ique
48
Mesurer les performances
Plusieurs mesures : Temps moyen pour arriver à l'optimum Moyenne des fitness du meilleur individu
trouvé Nombre de fois où l'opt imum est trouvé
en moins de T générations
Ces mesures, pour être valides doivent être effectuées sur un grand nombre d'essais
49
Bonnes performances à faible coût (de développement ) pour un large éventail de problèmes Parallélisme implicite (robustesse)
Supériorité par rapport à d'autres techniques pour des problèmes complexes avec :
Beaucoup de données
Variables mixtes
Relat ions entre les paramètres
Plusieurs opt ima (locaux)
Variat ions dans le temps
Performances
50
Pas d'hypothèses sur l'espace du problème
Largement applicable
Faibles coûts de développement et d'application
Intégration d'autres méthodes aisée
Solut ions interprétables
Obtention de plusieurs solut ions
Av antages
51
Hybridation
Étude de la dynamique
Améliorat ion des performances
Caractérisation des problèmes faciles/ diff iciles
Recherche
52
En résu m é
son t basés su r d es m étap h ores b iologiqu es on t d e gran d s p oten t iels p rat iqu es d evien n en t p op u laires d an s d e n om breu x d om ain es d on n en t d e bon n es p er form an ces à u n faib le coû t
Les a lgor ithm es év olt ionna iresLes a lgor ithm es év olt ionna ires
53
Mais …En boîte noire : ça ne marche pas
Sur les problèmes déjà résolus : c'est lent
Contextes idéaux :
Problèmes non résolus
Plusieurs optima
Problèmes mal posés
A coupler avec d'autres méthodes
54
Faire at t en t ion à :
La rep résen tat ion
Les op érateu rs
Les ch oix d es p aram èt res
Le calcu l d e la fitn ess
55
Notion de s chémas (1) Exis ten ce d e s im ilar it és en t re les
ch rom osom es
Sch ém a :
Sch ém as
Pat ron d e s im ilar it és qu i d écr it u n sou s- en sem ble d e ch aîn es ayan t d es s im ilar it és à cer ta in s locu s
Utilisat ion d ’u n caractère « joker » :
*
56
Notion de s chémas (2)
Exem p les : Cas d e ch aîn es b in aires *00101*10*
10100 , 10101, 11100, 11101
00010, 10010
Pou r u n ch rom osom e d e lon gu eu r λ d éfin i su r u n alp h abet con ten an t k sym boles il exis te (k+1)λ
sch ém as Les sch ém as son t u t ilisés p ar les
A.G. d e façon im p licite
57
Propriétés des s chémas Ordre d’un s chéma : n om bre d e locu s in s tan ciés
Exem ples : O (0*1001**) O (0***)
= 5
Longueur de définition d’un schéma : d is tan ce en t re le 1 er et le d ern ier locu s in s tan ciéExem ple : δ (0*1001**) δ (0***)
= 6 - 1 = 5
= 1
= 0 Fitnes s d’un schéma : Moyen n e d es fitn ess d es
rep résen tan ts d an s la p op u lat ion
58
Qui doit v iv re , qui doit mourir ?
Notat ion s :λ : Lon gu eu r d es
ch rom osom es
m (H, t) : Nom bre d e rep résen tan ts d u sch ém a H à l’in s tan t t
f (H) : Fitn ess d u sch ém a HF : Fitn ess m oyen n e d e la
p op u lat ion
Qu els sch ém as su rvivron t ?
Étude de l’influence des 3 op éra teurs
59
Influence des opérateurs
Effet de la reproduction :
Effet du croisement :
Seu ls les sch ém as d e valeu r sélect ive élevée seron t rep rod u it s
Des t ru ct ion d u sch ém a s i croisem en t d an s la z on e d e d éfin it ion Effet de la mutation :Dest ru ct ion d u sch ém a s i m u tat ion d ’u n caractère in s tan cié
60
Théorème des s chémas
Les sch ém as courts , d’ordre fa ib le et ayan t u n e fitness sup érieure à la m oy enne au gm en ten t d e façon exp on en t ielle au fil d es gén érat ion s
Ces sch ém as p ar t icu liers s ’ap p ellen t d es« b locs de construction »
( )
−
−−××≥+ )(
1)(
1)(
),()1,( HOpH
pFHf
tHmtHmmc λ
δ
61
(http :/ / w w w .sd l.hitachi.co.jp / eng lish/ sy stem / da ta /test1 0 0 .htm )
Visite de N villes en un m in im um de d is tance sans passer 2 fois par la m êm e ville
Prob lèm e :
Fonction d e fitness :
Ind iv id us :
Distance parcourue Cod a ge :
- Chaîne const ituée d 'au tan t de gènes que d e villes à vis iter- Im p ossibilité d 'avoir 2 gènes iden t iques dans la chaîne
A Ville 1B Ville 2
...
Un exem ple concret : Le v oy ageur de com m erce
62
Croisem ent :
A DB GH EF
D
D
H
H
B
B
A
A
C
C
F
F
G
G
E
E
A
E DG F
B CH
Muta tion :
Méthode 2op t (recherche locale)
C
A
E DG F
B CH
C
C D
H B A
G H
63
Résulta ts :
Générat ion 1
Fitness = 8.99
Générat ion 100
Fitness = 7.39
64
(ht tp :/ / w w w .w i.le id enuniv .nl/ ~ g usz / Fly ing _Circus/ 3 .Dem os/ Ja v a / Pr ism Lens/ ind ex.htm l)
Optim iser la form e d 'une len t ille pour que des rayons parallèles convergen t en un poin t un ique P
Prob lèm e :
Fonction d e fitness :
Ind iv id us :
Som m e d es carrés des d is tances des poin ts d 'im pact de chaque rayon au p oin t P
Cod a ge :
Lent ille découpées en 9 p art ies ayan t une épaisseur codée su r 15 bit s10 fois 15 bit s
Un autre exem ple com ple t : Optim is ation de la form e d'une
lentille
65
Résulta ts :
Gén érat ion 0
Fitn ess = 10209
Gén érat ion 50
Fitn ess = 648
Gén érat ion 100
Fitn ess = 44
Gén érat ion 300
Fitn ess = 17
66
Livres T. Bäck, Ev olutiona ry Alg orithm s in Theory a nd Pra ct ice , Oxford Un ivers ity Press , 1996
L. Davis , The Ha nd b ook of Genetic Alg or ithm s , Van Nost rand & Reinhold , 1991
D.B. Fogel, Ev olutiona ry Com p uta tion , IEEE Press , 1995
D.E. Gold berg, Genetic Alg or ithm s in Sea rch, Op t im iz a t ion a nd Ma chine Lea rning , Ad d ison -Wesley, 1989
J. Koz a, Genetic Prog ra m m ing , MIT Press , 1992
Z. Michalewicz , Genetic Alg or ithm s + Da ta Structures = Ev olutiona ry Prog ra m s , Sp ringer , 3èm e Ed ., 1996
H.P. Schwefel, Ev olution a nd Op tim um Seek ing , Wiley & Sons, 1995
67
Jou rn au x
BioSys tem s , Elsevier
Evolu t ion ary Com p u tat ion , MIT Press
Ar t ificial Life, MIT Press
Ad ap t ive Beh avior , MIT Press
IEEE Tran sact ion on Evolu t ion ary Com p u tat ion
68
Con féren ces ICGA, tou s les 2 an s d ep u is 1985
PPSN, tou s les 2 an s d ep u is 1990
FOGA, tou s les 2 an s d ep u is 1990
EP, tou s les an s d ep u is 1991
IEEE ICEC, tou s les an s d ep u is 1994
GP, tou s les an s d ep u is 1996
GECCO, tou s les an s d ep u is 1999
69
Fonction d e fitness :
Périm ètre de la su rface
Prob lèm e :
Placer 6 carrés con t igus en m in im isan t le périm ètre de la form e ains i créée.
Cod a ge :
Ind iv id us :
Chaînes com posées de 5 gènes
R2 :
R3 : R4 :
(Génotype)
(Phénotype)
R1 R3 R1 R1 R4Fitness
= 14
R1 :
Un exem ple s im ple :Optim is ation de s tructures
Exem p le :
70
R1 R1 R1 R1 R11.
R1 R4 R1 R4 R12.
R4 R1 R4 R4 R23.
R3 R1 R4 R4 R14.
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1R3 R1 R4 R4 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1R1 R1 R1 R1 R1
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4
R4 R1 R4
R4 R1
R4 R2
R4 R1
R4 R2
R4 R1
R4 R2R4 R1
R4 R2
R4 R1
R4 R2
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
R1 R1 R1 R1 R1
Recom b ina ison
Rem p la cem ent
14
12
14
14
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
R4 R1 R4 R4 R2
Sélect ion
R4 R1
R4 R2
R3
R3
R1 R4 R4 R1
R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R1 R4 R4 R1
R1 R4 R4 R1
R1 R4 R4 R1
R1 R4 R4 R1
R2
Pop ula t ion P1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R2
R4 R1 R4 R4 R2
Pop ula tion P0
R3 R1 R4 R4 R14.
R1 R1 R1 R1 R11.
R3 R1 R4 R4 R14.
R4 R1 R4 R4 R23.
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R4 R1 R4 R4 R2
R1 R1 R1 R1 R1
R1 R4 R4 R1R1 R4 R4 R1
71
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R3 R1 R4
R2R4
R3 R1 R4
R4 R1
R3 R1 R4
R2R4
R3 R1 R4
R4 R1
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4R2R3 R1 R4 R4R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1R3 R1 R4 R4 R1
R3 R1 R4 R4 R1 R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R2R3 R1 R4 R4R2R3 R1 R4 R4R2R3 R1 R4 R4R2R3 R1 R4 R4
Rem p la cem entR2R3 R1 R4 R4
Sélect ion
10
12
14
12
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
Recom b ina ison
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R3 R1 R4
R2R4R3 R1 R4
R4 R1
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4 R4 R1
R2R3 R1 R4 R4
R3 R1 R4
R2R4R3 R1 R4
R4 R1
Pop ula t ion P2
12
12
10
10
Pop ula tion P1
R2R3 R1 R4 R41.
R3 R1 R4 R4 R12.
R3 R1 R4 R4 R13.
R4 R1 R4 R4 R24.
R3 R1 R4 R4 R13.
R3 R1 R4 R4 R12.
R2R3 R1 R4 R41.
R2R3 R1 R4 R41.
