Projet ModélisationCo-évolution des Stratégies pour le Jeu du

Dilemme du Prisonnier Itéré

Jonathan Goldwasser, Gian Luca RattacasoHuan Alexandre Bui Manh et Eyal Szombat

Tuteurs : Dr. Joshua D. Knowles et Mauro Birattari

12 décembre 2002

Résumé

Le jeu du dilemme du prisonnier itéré modélise beaucoup de phénomènes desociété très importants comme la course aux armements nucléaires, le compor-tement d’individus partageant une ressource commune ou encore la rédactiondu protocole de Kyoto sur l’environnement. Dans ce genre de situation, les in-dividus ou pays essaient de prendre l’avantage l’un sur l’autre mais coopèrentégalement entre eux. Comment évolue cette coopération et est-elle stable? [1]

The iterated prisoner’s dilemma game models many important and interestingsocial phenomena including nuclear arms race, the behaviour of people sharing acommon resource, trade agreements, the formation of the Kyoto environmentalagreement, etc. In these situations, individuals or countries try to take advan-tage of each other but also sign agreements to share or co-operate. An importantquestion is how does this co-operation evolve and is it stable? [1]

Table des matières

I Le Rapport 3

1 L’énoncé du projet 41.1 Le titre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Le projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Historique 5

3 Le jeu du dilemme du prisonnier 63.1 L’énoncé et ses variantes . . . . . . . . . . . . . . . . . . . . . . . 6

3.1.1 L’énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.1.2 Les variantes . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 Le jeu du dilemme du prisonnier itéré (DPI) . . . . . . . . . . . . 73.2.1 Reformulation de l’énoncé . . . . . . . . . . . . . . . . . . 73.2.2 La version itérée . . . . . . . . . . . . . . . . . . . . . . . 7

4 Les stratégies à mémoire n 104.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2 Exemple dans le cas où n = 3 . . . . . . . . . . . . . . . . . . . . 104.3 Généralisation à la mémoire n . . . . . . . . . . . . . . . . . . . . 114.4 Relation entre la mémoire n et la base 2 (nombres binaires) . . . 124.5 Décodage d’une stratégie à mémoire n . . . . . . . . . . . . . . . 124.6 La stratégie Tit-For-Tat . . . . . . . . . . . . . . . . . . . . . . . 13

5 Les algorithmes génétiques 145.1 Introduction et définition . . . . . . . . . . . . . . . . . . . . . . 145.2 Codage d’un individu et population initiale . . . . . . . . . . . . 145.3 Les opérateurs évolutifs . . . . . . . . . . . . . . . . . . . . . . . 15

5.3.1 La sélection . . . . . . . . . . . . . . . . . . . . . . . . . . 155.3.2 Le croisement . . . . . . . . . . . . . . . . . . . . . . . . . 155.3.3 La mutation . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5.4 Les paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165.5 Exemple simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5.5.1 Tirage et évaluation de la population initiale . . . . . . . 165.5.2 Sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.5.3 Croisement . . . . . . . . . . . . . . . . . . . . . . . . . . 175.5.4 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.5.5 Évaluation de la population finale . . . . . . . . . . . . . 18

1

6 Application des algorithmes génétiques au jeu du dilemme duprisonnier itéré. 196.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.2 Le choix des paramètres . . . . . . . . . . . . . . . . . . . . . . . 206.3 Les faiblesses du codage binaire . . . . . . . . . . . . . . . . . . . 206.4 La mesure de la co-évolution . . . . . . . . . . . . . . . . . . . . 216.5 Le principe de sub-optimisation . . . . . . . . . . . . . . . . . . . 22

7 Dans le code source... 237.1 Le choix du langage de programmation . . . . . . . . . . . . . . . 237.2 Architecture de l’algorithme . . . . . . . . . . . . . . . . . . . . . 237.3 Les problèmes de temps de calcul . . . . . . . . . . . . . . . . . . 247.4 Le code source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

8 Analyse des résultats 268.1 Comment analyser des résultats? . . . . . . . . . . . . . . . . . . 268.2 L’analyse des graphiques . . . . . . . . . . . . . . . . . . . . . . . 27

8.2.1 La méthode n◦1 . . . . . . . . . . . . . . . . . . . . . . . 278.2.2 La méthode n◦2 . . . . . . . . . . . . . . . . . . . . . . . 288.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 28

8.3 Tit-For-Tat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298.3.1 La meilleure stratégie . . . . . . . . . . . . . . . . . . . . 298.3.2 Comment expliquer l’émergence de l’altruisme dans le cas

de l’évolution génétique? . . . . . . . . . . . . . . . . . . 29

9 Conclusion 31

II Les Annexes 32

A Le code source 33A.1 defined_values.h . . . . . . . . . . . . . . . . . . . . . . . . . . . 33A.2 functions.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33A.3 functions.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33A.4 strategy_table.h . . . . . . . . . . . . . . . . . . . . . . . . . . . 34A.5 strategy_table.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . 35A.6 ipd.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

B Les graphiques 45

C L’organisation au sein du groupe 47C.1 Le planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47C.2 La répartition des tâches . . . . . . . . . . . . . . . . . . . . . . . 48

C.2.1 Pour la modélisation . . . . . . . . . . . . . . . . . . . . . 48C.2.2 Pour l’écriture du rapport et la présentation orale . . . . 48

C.3 L’organisation des réunions . . . . . . . . . . . . . . . . . . . . . 48C.4 Internet et l’organisation . . . . . . . . . . . . . . . . . . . . . . . 48C.5 Les ordres du jours, procès verbaux et grilles d’observations . . . 49

2

Première partie

Le Rapport

3

Chapitre 1

L’énoncé du projet

1.1 Le titre“Co-évolution des stratégies pour le jeu du dilemme du prisonnier itéré”

Qu’entend-t-on par co-évolution?La co-évolution est un processus dans lequel des espèces évoluent en fonction

de leurs actions ou effets sur les autres espèces présentes dans ce même proces-sus. On ne considère donc pas les espèces non présentes bien qu’elles existent.

En clair, nous cherchons des stratégies pour un certain jeu et l’on s’intéresseprincipalement à la co-évolution de ces stratégies : Comment évoluent ces stra-tégies ensemble (dans un tournoi par exemple)?

Le titre motive d’autre questions :

– Qu’est ce qu’une stratégie pour le jeu du dilemme du prisonnier?– Qu’est ce qu’une bonne stratégie? Existe-t-il la meilleure stratégie?

1.2 Le projetLe but du projet nous a été énoncé de la manière suivante : “On désire trou-

ver une stratégie qui, amenée dans n’importe quel tournoi, ressortira gagnante”

Pour nous aider a répondre à cette question, il nous a été demandé de réalisercertaines tâches et d’approfondir d’autres questions :

– Écrire un algorithme génétique dans lequel chaque individu de la popula-tion représente une stratégie pour le dilemme du prisonnier. Les individussont évalués en jouant l’un contre l’autre (co-évolution). Les meilleurs in-dividus sont ceux qui remportent le plus de points.

– Les joueurs deviennent-ils meilleurs à force de jouer?– Est-il possible de faire mieux que la stratégie “Tit-For-Tat 1” ?– Que se passe-t-il si les joueurs peuvent signaler leur intention?

1. voir chapitre 4, section 4.6, page 13.

4

Chapitre 2

Historique

Le dilemme du prisonnier fut introduit en 1950 par Merill Flood et Mel-vin Drescher, qui tous deux travaillaient à la Rand Corporation 1. Par la suite,ce dilemme du prisonnier fut formalisé par le mathématicien Albert W. Tu-cker. Il fut le premier à publier un article sur le sujet.

Ce jeu du dilemme du prisonnier fait partie des jeux de somme non-nulle. Ilexiste deux type de jeu :

1. Les jeux de somme nulle : le total des gains est fixe. Ce qui est gagné parl’un est perdu par l’autre : la somme des gains sera nulle.

2. Les jeux de somme non-nulle : ce qui est gagné par l’un n’est pas perdupar l’autre : la somme des gains sera différente de zéro.

Le premier à parler de jeu du dilemme du prisonnier itéré sera Robert Axel-rod en 1970. Il est très célèbre pour ses travaux interdisciplinaires sur l’évolutionde la coopération. Son ouvrage le plus connu est The Evolution of Cooperation(1984). Robert Axelrod créa un tournoi informatique dans lequel il fit serencontrer des stratégies créées par des spécialistes de la théorie des jeux. En-suite, il organisa un second tournoi, celui-ci ouvert à toute personnes souhaitantsoumettre une stratégie, afin de confirmer ou d’infirmer les résultats du premiertournoi. Le second tournoi se déroula avec plus de stratégies que le premier etavait la particularité de faire s’affronter des stratégies identiques. Les observa-tions liées à ces deux tournois lui permirent d’arriver à la conclusion que lastratégie dénommée Tit-For-Tat 2, proposée par le professeur en psychologieAnatol Rapoport, s’avéra être la meilleure.

1. Raccourci pour Research and Development Corporation, une société de recherche amé-ricaine qui assiste entre aute l’armée des États-Unis.

2. voir chapitre 4, section 4.6, page 13.

5

Chapitre 3

Le jeu du dilemme duprisonnier

3.1 L’énoncé et ses variantes

3.1.1 L’énoncéUn malfaiteur et son complice viennent d’être arrêtés par la police. Ils sont

placés dans des cellules séparées en attendant d’être interrogés. La police vientchez chacun d’eux et leur tient le discours suivant :

“Si tu dénonces ton ami et que lui te couvre, tu as auras cinq années deremise de peine mais ton ami aucune.”

“Si tu couvres ton ami et que lui te dénonces, ton ami auras cinq années deremise de peine mais toi aucune.”

“Si tu couvres ton ami et que lui te couvre également, vous aurez tous deuxtrois années de remise de peine.”

“Enfin, si vous vous dénoncez mutuellement, vous aurez chacun une annéede remise de peine.”

On remarque directement que la “moins pire” des solutions est de dénoncerson ami. En effet, en dénonçant son ami, on obtient soit cinq années de remisede peine, soit une année, contre trois ou aucune si l’on décide de couvrir.

3.1.2 Les variantes1. Deux voitures roulent l’une vers l’autre sur une route trop étroite pour

passer à deux. Chaque conducteur se pose la question suivante : “Dois-jele laisser passer (=couvrir) ou y aller moi-même (=dénoncer)?”.Les conséquences sont semblables à celles de l’énoncé 3.1.1

2. Dans le monde du travail : Chaque société décide individuellement deconsolider ses propres profits (=dénoncer), alors qu’une mise en communde l’information et de la décision (=couvrir) aurait permis un plus grandbénéfice commun pour toutes.

3. Le locataire de l’appartement à côté du vôtre pratique le tapage nocturne(=dénoncer) : soit vous réagissez en vous mettant à votre tour à jouer dela musique (=dénoncer), soit vous le laisser faire (=couvrir). Dans tous les

6

cas, vous regrettez votre ancien voisin qui ne faisant aucun bruit (=cou-vrir) et que vous vous efforciez de ne pas déranger (=couvrir).

Il existe encore beaucoup d’autre variantes du dilemme. En fait, une grandepartie des prises de décisions dans notre monde sont régies par des dilemmes duprisonnier (simples et itérés).

3.2 Le jeu du dilemme du prisonnier itéré (DPI)

3.2.1 Reformulation de l’énoncéAvant de parler de la version itérée du jeu, il est utile de reformuler l’énoncé

de façon à pouvoir plus facilement le modéliser au sein d’un quelconque algo-rithme :

T CT (1,1) (5,0)C (0,5) (3,3)

Tab. 3.1 – Tableau des points

Ce tableau croisé s’interprète de la manière suivante :“T” représente “Trahir” (c-à-d dénoncer son complice à la police)“C” représente “Coopérer”(c-à-d couvrir son complice)Les valeurs dans le tableau sont appelées points. Le but du jeu, maintenant,

n’est plus d’avoir la plus petite peine de prison mais d’avoir le plus de pointspossibles.

Dans la suite de ce rapport, “Trahir “ sera remplacé par “T ” et “Coopérer”par “C ”.

3.2.2 La version itéréeComme nous l’avons vu précédemment, s’il l’on joue une seule et unique fois

au jeu, la meilleure stratégie consiste à dénoncer. Par contre, si nous répétons cejeux n fois avec pour but de maximiser les points, il est beaucoup plus compliquéde trouver la meilleure stratégie. On appelle jeu du dilemme du prisonnier itéré ,la répétition n fois du jeu du dilemme du prisonnier simple.

On peux imaginer toutes sortes de stratégies pour la version itérée :

1. La stratégie traître : toujours T.2. La stratégie naïve : toujours C.3. La stratégie périodique : j ∗ C suivi de k ∗ T avec i(j + k) = n. (i,j,k∈ N)4. La stratégie lunatique : C ou T au hasard selon une certaine loi de proba-

bilité c-à-d p ∗ C et q ∗ T lors d’une partie de p + q jeux. (p,q ∈ N)5. La stratégie rancunière : toujours C sauf si son opposant joue T une fois

alors toujours T c-à-d r ∗ C suivi de s ∗ T avec r + s = n si l’opposanttrahi au reme coup. (r,s ∈ N)

7

6. La stratégie markovienne 1 : C ou T au hasard selon une loi de probabilitéqui dépend des derniers coups de son adversaire.

7. La stratégie à mémoire : C ou T en fonction des coups précédents. Cettedernière étant la plus intéressante et celle qui se prête le mieux au al-gorithmes génétiques, c’est elle que nous avons choisi d’approfondir. Lastratégie à mémoire est expliquée en détail au chapitre 4, page 10 .

8. La stratégie intelligente : cette stratégie essaie de modéliser le comporte-ment de ses adversaires : elle se modifie au cours des jeux de façon à jouerde mieux en mieux. Cette stratégie est, bien sûr, la plus complexe et nousne la considérerons pas ici.

Les stratégies 1 à 3 ne sont pas réactives, elle peuvent être comparées àdes fonctions constantes : elle ne dépendent d’aucune variable.Les stratégies 4 & 5 sont “plus ou moins” réactives : l’une dépend d’uneloi de probabilité tandis que l’autre, qui ne sera réactive qu’une seule fois,dépend d’un des coups de son adversaire.Les stratégies 6 & 7 sont totalement réactives : elle dépendent des der-niers coups de leur adversaire et donc réagissent de manière différentes enfonction de ces coups (cf chapitre 4, page 10).

Il est intéressant de regarder les scores obtenus quand ces différentes straté-gies jouent l’une contre l’autre n fois. Ceci étant possible uniquement pour lesstratégies 1 à 5 :

Traître Naïve Périodique Lunatique Rancunière

Traître n 5n i(5j + k) 5p + q 5 + (n− 1)

Naïve 0 3n 3ij 3p 3n

Périodique ik i(3j + 5k) i(3j + k) - i(3j + 5 + (k − 1))

Lunatique q 3p + 5q - - -Rancunière (n− 1) 3n i(3j + (k − 1)) - 3n

Tab. 3.2 – Score de la stratégie ligne lors du match contre la stratégie colonne

Ce tableau aide à comprendre combien il est difficile de trouver la meilleurestratégie pour le jeu du dilemme du prisonnier itéré.

En effet, si on considère que la meilleure stratégie est celle qui, à chaqueconfrontation, finira toujours avec un score plus élevé que celui de son adversairealors la stratégie traître est la meilleure : elle obtient toujours un score plus grandou égal à celui de son adversaire.

Si, par contre, on demande que la meilleure stratégie soit celle qui rapportele plus de points possibles alors il est impossible de trouver une telle stratégie :supposons qu’une telle stratégie existe, alors elle doit forcément trahir au pre-mier coup pour ne pas avoir 5 points de retard contre la stratégie traître. Maissi elle trahi au premier coup alors elle fera un moins bon score que la stratégienaïve lors de la confrontation avec la stratégie rancunière et ce ne sera doncpas la stratégie qui rapporte le plus de points possibles. En fait une stratégie

1. Andreï Markov (1856-1922), mathématicien russe, spécialiste de la théorie desnombres, de la théorie des probabilités et de l’analyse mathématique.

8

sera bonne face à certaines stratégies et mauvaise face à d’autres. Il est doncimpossible de distinguer les stratégies entre elles lors de confrontations 2 à 2.

Rappelons simplement que nous ne cherchons ni la stratégie qui gagne tou-jours ni celle qui rapporte le plus de points lors de confrontations 2 à 2 maisbien celle qui récolte le plus de points lors d’un tournoi quelconque.

9

Chapitre 4

Les stratégies à mémoire n

4.1 DéfinitionLa définition d’une stratégie à mémoire n diffère suivant la parité de n de la

manière suivante :Si n est pair, alors une stratégie à mémoire n tient compte des n derniers

coups joués c-à-d des n/2 jeux précédents.Si n est impair, posons n = 2k + 1, alors une stratégie à mémoire n tient

compte des 2k coups précédents mais aussi du coup de l’adversaire au jeu avantces 2k coups.

Dans les deux cas, la stratégie à mémoire n doit avoir un coup à jouerpour chaque séquence de coups précédents. Il faudra donc envisager tous les caspossible de coups précédents.

4.2 Exemple dans le cas où n = 3

D’après la définition, une stratégie à mémoire 3 tient compte des 2 dernierscoups (ceux du jeu précédent) mais également du coup de l’adversaire durantl’avant-dernier jeu. De plus, elle doit prévoir un coup à jouer pour chaque sé-quence de coups précédents. Nous envisagerons donc tous les cas possible des 3coups auxquels se réfère cette stratégie à mémoire 3.

CoupsJeu i− 2 (Adversaire) T T T T C C C CJeu i− 1 (Moi-même) T T C C T T C CJeu i− 1 (Adversaire) T C T C T C T CStratégie à mémoire 3 T C C T T T C T

Tab. 4.1 – Exemple de stratégie à mémoire 3

Ou encore en associant la valeur 0 à T et la valeur 1 à C (toujours dansl’idée de faciliter la modélisation dans un algorithme) :

10

CoupsJeu i− 2 (Adversaire) 0 0 0 0 1 1 1 1Jeu i− 1 (Moi-même) 0 0 1 1 0 0 1 1Jeu i− 1 (Adversaire) 0 1 0 1 0 1 0 1Stratégie à mémoire 3 0 1 1 0 0 0 1 0

(où i ∈ N \ {0,1,2})

Tab. 4.2 – Exemple de stratégie à mémoire 3

Si, par exemple, l’adversaire coopère au jeu i − 2 et au jeu i − 1 et que lastratégie trahi au jeu i − 1 (cas de la colonne n◦6 du tableau) alors au jeu i(c-à-d le jeu actuel) la stratégie décrite dans cette exemple trahira (cas de lacolonne n◦6 et de la ligne n◦4).

La dernière ligne du tableau définit presque entièrement (i ∈ N \ {0,1,2})cette stratégie à mémoire 3 puisque tous les cas possibles de coups précédentsy sont envisagés. Une question se pose immédiatement : que joue la stratégie àmémoire 3 au jeu n◦1 et au jeu n◦2? Réponse : il faut définir ces coups pourque la stratégie à mémoire 3 soit entièrement définie c-à-d que ∀i ∈ N0, lastratégie possède un coup à jouer :

Stratégie à mémoire 3 entièrement définie : 0 1 1 0 0 0 1 0 1 0

(où les 2 derniers nombres donnent les coups à jouer aux jeu n◦1 et 2)

4.3 Généralisation à la mémoire n

Considérons une stratégie à mémoire n.Pour que cette stratégie soit définie (à ses coups initiaux près), nous avons

vu qu’il faut envisager tous les cas possibles de coups précédents des 2k jeux sin est impair (n = 2k + 1) et des n/2 jeux si n est pair.

En fait, il faut considérer tous les cas possibles des n coups précédents c-à-d toutes les manières possibles de placer 0 et 1 dans une liste de n chiffres.Appelons bits le nombre de cas possibles des n coups précédents, nous avons :

bits = 2n (4.1)

On en déduit donc le nombre de stratégies à mémoire n différentes c-à-dtoutes les manières possible de placer 0 et 1 dans une liste de bits chiffres :

strategies = 2bits = 22n

(4.2)

(et plus encore si on tient compte des coups initiaux)En particulier si n = 3, il y a aura 223

= 256 stratégies chacune codées àl’aide de 23 = 8 bits.

11

4.4 Relation entre la mémoire n et la base 2 (nombresbinaires)

On peut représenter l’ensemble des stratégies à mémoire n dans une matricede 22n

lignes et 2n colonnes :

N◦ de la stratégie Valeur en base 2 Valeur en base 10Stratégie 0 0 0 . . . . . . 0 0 0 0Stratégie 1 0 0 . . . . . . 0 0 1 1

......

......

......

......

...

Stratégie i...

......

......

...... i

......

......

......

......

...Stratégie 22n

1 1 · · · · · · 1 1 1 22n

Tab. 4.4 – Matrice des stratégies de la mémoire n

Chaque stratégie peut être vue comme une suite S = {bit0,bit1 . . . ,bit2n−1}où ∀i biti ∈ V = {0,1}.

On définit alors “la valeur v en base 10 de la stratégie” de la manière suivante :

v =2n−1∑i=0

biti.2bits−i−1 (4.3)

Ainsi si S = {1,0,1,1} , v = 1 ∗ 23 + 0 ∗ 22 + 1 ∗ 21 + 1 ∗ 20 = 11

Chaque stratégie représente un nombre binaire et l’ensemble des stratégiesà mémoire n est l’ensemble des nombres en base 2 allant de 0 à 22n

. Il existe,donc, une bijection entre l’ensemble des stratégies à mémoire n et les nombresen base 2. En effet, la stratégie n◦i n’est rien d’autre que la valeur de i encodéeen base 2 (en rajoutant, si nécessaire, des 0 devant, de façon à avoir 2n bits).Ces notions seront très utiles pour élaborer un algorithme génétique (cf. cha-pitre 5, page 14 & chapitre 6, page 19 ).

4.5 Décodage d’une stratégie à mémoire n

La façon de décoder une stratégie à mémoire n est, bien évidemment, tota-lement arbitraire. Il convient donc de choisir une manière de décoder :

La stratégie à mémoire n joue son ieme bit quand la valeur en base 10 descoups précédents est égale à i

Où “ la valeur en base 10 des coups précédents” est défini de manière analogue à“la valeur en base 10 de la stratégie” de la section 4.4 (formule (4.3)).

C’est cette façon de décoder qui est utilisée en section 4.2.

12

4.6 La stratégie Tit-For-TatLa stratégie Tit-For-Tat 1 est une stratégie à mémoire 1, elle se base sur le

coup de l’adversaire au jeu précédent.Voici son codage :

Tit-For-Tat : 0 1 1

Cette stratégie coopère au premier coup. A tous les coups suivants, elle jouele coup de l’adversaire au jeu précédent.

Il existe aussi une variante de Tit-For-Tat qui consiste à trahir au premiercoup.

Tit-For-Tat est un cas particulier très important des stratégies à mémoire,nous verrons pourquoi plus loin dans ce rapport.

1. En français : Donnant-Donnant

13

Chapitre 5

Les algorithmes génétiques

5.1 Introduction et définitionLes algorithmes génétiques (AGs) sont des algorithmes d’optimisation fondé

sur les mécanismes de la sélection naturelle et de la génétique. Leur fonctionne-ment est extrêmement simple : on part avec une population de solutions poten-tielles tirées au hasard, on évalue les performances (fitness) de cette population.Sur bases de ces performances, on crée une nouvelle population de solutionspotentielles en appliquant des opérateurs évolutifs : la sélection, le croisementet la mutation. On recommence ensuite le cycle jusqu’à ce que l’on trouve unesolution satisfaisante.

Les algorithmes génétiques sont définis par :

Individu (ou chromosome ou séquence) : une solution potentielle du problème.Population : un ensemble d’individus.Fonction de fitness : une fonction positive que l’on cherche à maximiser.

Le domaine d’application principal des AGs reste l’économie. En effet, ces der-nières années, un nombre croissant de travaux en économie utilisant des al-gorithmes génétiques a vu le jour. L’aspect économique des AGs s’est avéréinintéressant lors de la réalisation de ce projet, il ne sera pas développé dans cerapport.

5.2 Codage d’un individu et population initialeLe codage le plus communément utilisé 1 est, bien sûr, le codage binaire. Ce

codage est le plus simple à implémenter et le plus proche de l’aspect “nature”de l’AG.

Un individu est représenté par une suite de bits (0 ou 1) appelée parfoisséquence ou chromosome. Ce codage permet facilement d’appliquer les opé-rateurs évolutifs présentés à la section suivante.

Les individus de la population initiale sont tirés au hasard parmi l’ensembledes solutions admissibles du problème.

1. Mentionnons simplement l’existence du codage réel qui ne sera pas développé ici.

14

5.3 Les opérateurs évolutifsLes opérateurs jouent un rôle fondamental dans l’évolution de l’algorithme,

ce sont eux qui décident de la réussite ou non de l’AG. Le principe de fonction-nement de chacun des ces opérateurs est détaillé ci-après.

5.3.1 La sélectionCet opérateur a droit de vie ou de mort sur les individus de la population.

C’est lui qui sélectionne les individus qui seront recopiés dans la nouvelle popu-lation.

Il existe deux types de sélection :

1. La sélection non-élitiste : dans ce cas, la probabilité avec laquelle unindividu sera recopié dans la nouvelle population dépend de ces perfor-mances dans la population actuelle. Tout le monde a donc une chanced’être sélectionné.

Soit une population de N individus Si évalués chacun à l’aide d’une fonc-tion de fitness f. La probabilité P pour que S1 soit recopié dans la nouvellegénération est donnée par :

P =f(S1)

N∑i=1

f(Si)

(5.1)

2. La sélection élitiste : Un exemple de sélection élitiste consiste à recopierimmédiatement les meilleurs x% de la population. Un avantage de ce typede sélection est le fait qu’un mauvais individu 2 ne sera jamais sélectionnépour la nouvelle génération.

5.3.2 Le croisementContrairement à la sélection, les opérateurs de croisement et mutation créent

de nouveaux chromosomes.L’opérateur de croisement choisi au hasard deux individus parmi la nouvelle

population issue de la sélection. Il détermine ensuite aléatoirement un site decroisement. Enfin, selon une certaine probabilité, le croisement s’effectue c-à-dqu’on échange les segments finaux entre les deux individus à partir de ce site(voir exemple à la section 5.5.3)

L’opérateur de croisement à ses faiblesses : Imaginons une population danslaquelle aucun individu n’a la valeur 1 comme dernier bit. Si la solution optimaledu problème contient en réalité la valeur 1 comme dernier bit, alors, quelque soitle croisement possible, ce dernier ne fera jamais apparaître la valeur 1 commedernier bit et l’AG ne convergera pas vers la solution optimale.

Pour remédier à ce genre de problèmes, on introduit un autre opérateur : lamutation.

2. Un mauvais individu est un individu qui a un fitness beaucoup plus petit que la moyennedes fitness

15

5.3.3 La mutationLa mutation consiste à changer, avec une certaine probabilité et au hasard,

un bit de la séquence par son inverse :

bit′ = 1− bit (5.2)

Son rôle est très important, il permet :

1. d’accéder à tous les individus possibles.2. de sortir l’AG d’une mauvaise convergence 3 : surtout dans le cas où tous

les individus de la population sont semblables ou presque.

5.4 Les paramètresLes algorithmes génétiques dépendent de certains paramètres qui doivent

être fixé à l’avance :

– La taille de la population : il faut faire un bon compromis entre le tempsde calcul et la mauvaise convergence.

– La probabilité de croisement : en général entre 0.5 et 0.9%.– La probabilité de mutation : cette valeur doit être assez faible pour ne pas

perdre les bonnes solutions.

Ces paramètre sont généralement choisis au hasard parmi leur domaine de va-leurs admissibles respectif.

5.5 Exemple simpleSoit à maximiser la fonction 4 f : [0,31] → [0,31] : x → xLa première étape consiste à coder les solutions du problème c-à-d trouver

un codage pour x puisque n’importe quelle valeur de x comprise entre 0 et 31est une solution potentielle (admissible) du problème. Dans cet exemple nousutiliserons un codage binaire de x. La séquence contiendra donc au maximum 5bits (0 ≤ x ≤ 31). A titre d’exemple : x = 2 → {0,0,1,0} et x = 31 → {1,1,1,1,1}.

5.5.1 Tirage et évaluation de la population initialePour illustrer cet exemple, nous allons fixer la taille de la population à N = 4.

Nous tirons donc aléatoirement un population de quatre individus parmi lesindividus admissibles :

3. Les fitness de la population sont extrêmement bas4. Ici, la fonction de fitness est confondue avec celle du problème. Ce n’est pas souvent le

cas, d’ailleurs ce ne sera pas le cas pour le DPI.

16

Séquence Fitness % du Fitness total00101 5 14,310000 16 45,700010 2 5,700110 12 34,3Total 35 100

Tab. 5.1 – Population initiale

On remarque que le maximum est atteint par la séquence 10000 et vaut 16.

5.5.2 SélectionNous allons maintenant sélectionner les parents pour pouvoir effectuer des

croisements ainsi que des mutations. Les individus sont sélectionnés avec uneprobabilité égale à leur pourcentage du fitness total. Imaginons que la sélectionce soit passée de la manière suivante :

Séquence10000011000010110000

Tab. 5.2 – La sélection

5.5.3 CroisementConsidérons que la probabilité de croisement soit de 100%. Nous tirons au

hasard deux couples de parents et un site de croisement pour chacun d’eux :

site = 3 site = 2100 | 00 01 | 100001 | 01 10 | 00010001 0100000100 10100

Tab. 5.3 – Le croisement

5.5.4 MutationFixons la probabilité de mutation à 5%. Pratiquement, nous procédons de

la manière suivante : pour chaque bit, on tire un nombre entre 0 et 100. Si cenombre est inférieur à 5, alors on remplace le bit par son inverse (cf. (5.2)) :

17

Séquence Tirage Nouvelle séquence10001 15 25 36 4 12 1001100100 26 89 13 48 59 0010001000 32 45 87 22 65 0100010100 47 1 85 62 35 11100

Tab. 5.4 – La mutation

5.5.5 Évaluation de la population finaleNous sommes maintenant en mesure d’évaluer la nouvelle population. Es-

sayons de voir si l’algorithme génétique a trouvé une solution plus optimale :

Séquence Fitness % du Fitness total10011 19 32.200100 4 6.801000 8 13.511100 28 47.5Total 59 100

Tab. 5.5 – Population finale (après une génération)

En effet, notre AG a réussi, non seulement, à faire passer le maximum de 16à 28 mais également d’augmenter le fitness total. En poursuivant le processusévolutif au delà de la première génération, l’algorithme génétique atteindra cer-tainement la valeur 31 comme maximum.

Cet exemple illustre bien la simplicité et l’efficacité des AGs : aucun calcul com-pliqué n’est nécessaire et on remarque déjà qu’il sera aisé d’implémenter du codepour cet algorithme (cf. chapitre 7, page 23).

18

Chapitre 6

Application des algorithmesgénétiques au jeu du dilemmedu prisonnier itéré.

6.1 IntroductionLe chapitre 4 montre combien les stratégies à mémoire du jeu du dilemme

du prisonnier se prêtent facilement aux algorithmes génétiques : leur codage estbinaire. Ces stratégies constitueront la population de notre AG.

Nous allons donc essayer de construire un algorithme génétique pour trouverla stratégie à mémoire qui remporte le plus de points possibles. Un AG estdéfini 1, non seulement, par ces individus et sa population mais également parsa fonction de fitness. Nous choisirons comme fonction de fitness la fonctionsuivante :

“Obtenir le plus de points possibles en jouant au DPI contre toutes les autresstratégies de la population”

A chaque génération est organisé un tournoi entre toutes les stratégies pré-sentes. A l’issu du tournoi, les stratégies sont triées de manière décroissanteselon leurs points.

Soit une population de départ contenant N (N ≤ 22n

) stratégies à mé-moire n, voici comment seront définis les différents opérateurs :

La sélection : Les N2 meilleures stratégies sont sélectionnées pour devenir pa-

rents 2.Le croisement : Le croisement s’effectue dans tous les cas. Les couples et sites

sont tirés au hasard.La mutation : Les N

2 stratégies obtenues lors des croisements passent à laphase de mutation. Nous avons laisser la possibilité de modifier la proba-bilité de mutation dans notre algorithme.

1. voir chapitre 5, section 5.1, page 14.2. N doit donc être divisible par 4.

19

Une nouvelle population est alors créée à partir des N2 meilleures stratégies et

des N2 stratégies enfantées.

Ce processus est bien sûr répété jusqu’à obtenir des stratégies satisfaisanteset/ou des résultats intéressants.

6.2 Le choix des paramètresLes opérateurs de croisement et mutation ne jouant un rôle important qu’à

partir d’une certaine longueur de séquence, nous avons choisi de travailler avecles stratégies à mémoire 3 et 4 c-à-d avec des séquences contenant respectivement8 et 16 bits.

Voici les différentes configurations testées, ceci étant rendu possible grâce àla flexibilité de notre AG (cf. chapitre 7) :

Mémoire Taille de la population Coups Générations Pmutation

3 100 750 200 0,999% ou 1,999%3 120 600 200 0,999% ou 1,999%3 200 500 200 0,999% ou 1,999%4 100 750 200 0,999% ou 1,999%4 120 600 200 0,999% ou 1,999%4 200 500 200 0,999% ou 1,999%

Tab. 6.1 – Configurations testées par notre AG

Chaque configuration a elle-même été répétées plusieurs fois de manière àpouvoir faire des moyennes entre les résultats et donc de minimiser les erreurs.

Les différents graphiques se rapportant à ces configuration sont représentésau chapitre 8, section 8.2, page 27.

Le choix de ces configuration est bien évidemment un bon compromis entretemps de calcul et qualité des résultats. Le fait de choisir plusieurs configura-tions a plusieurs avantages :

1. Ne sachant pas pour quelles valeurs des paramètres notre AG donnera desrésultats intéressants, il est utile de tester plusieurs configurations.

2. Il existe peut-être des similitudes et/ou des différences intéressantes entreces configurations.

6.3 Les faiblesses du codage binaireIl est important de mentionner que le codage binaire empêche le codage de

certaines stratégies déjà mentionnées en section 3.2.2. En effet, il est impossiblepar exemple d’effectuer un codage binaire pour une stratégie périodique, unestratégie rancunière ou encore un stratégie lunatique bien que pour toutes lestrois il soit possible d’écrire un algorithme les faisant jouer. Les seules stratégiespouvant être codées en binaire (ou plutôt de manière séquentielle) sont les stra-

20

tégies à mémoire et les stratégies markoviennes 3 (les stratégies naïves et traîtresne sont que des cas particuliers des stratégies à mémoire).

Si on considère que l’espace de recherche tout entier pour le problème dujeu du dilemme du prisonnier itéré est l’ensemble des stratégies possible pource même jeu, alors l’algorithme génétique que nous avons créé a un espace derecherche limité : le sous-espace des stratégies à mémoires n, qui est un sous-espace non négligeable de l’ensemble des stratégies.

6.4 La mesure de la co-évolutionDe manière à suivre l’évolution de notre algorithme génétique nous devons

encore introduire certaines opérations à la fin de chaque génération. Il est évidentque la mesure du fitness au sein même de la population subissant des change-ments continuels est dénuée de sens puisque qu’elle donne une indication relativeà cette même population et non une indication relative à l’espace de recherchetout entier c-à-d l’ensemble des stratégies à mémoire n. Il faut donc trouverune manière de mesurer la “qualité” de nos stratégies et plus particulièrementcelle de la stratégie gagnante 4 de chaque génération. En pratique, on organiseun second tournoi : la stratégie gagnante joue contre toutes les stratégies d’unéchantillon de la mémoire n, la stratégie qui coopère et celle qui trahi toujoursjouent également contre ces stratégies. L’échantillon est tiré aléatoirement àchaque génération, son effectif est suffisamment grand pour que les scores obte-nus lors de ce dernier tournoi ne subissent que de légères fluctuations au coursdes générations (mesure reproductible) et suffisamment petit pour que la vitessede calcul soit acceptable (cf. chapitre 7, section 7.3, page 24). A la fin de ce se-cond tournoi, on relève les points obtenus par la stratégie gagnante, la stratégienaïve et la stratégie traître. Une aute manière de mesurer l’évolution est de fairejouer la stratégie gagnante contre Tit-For-Tat.

Nous avons donc deux méthodes différents pour mesurer l’évolution de notre AG :

1. En suivant le score du gagnant contre l’échantillon.2. En suivant le score du gagnant contre Tit-For-Tat.

La méthode n◦1 ne nous garantit pas que notre stratégie remportera n’im-porte quel tournoi. En effet, elle émet l’hypothèse que toutes les stratégies ontautant de chance se retrouver dans un tournoi. Il serait plus intéressant de pon-dérer le score - du gagnant contre l’échantillon - par la probabilité de la stratégiede se retrouver dans un tournoi. Exemple simple : une équipe de football belgea plus intérêt à être bonne contre d’autres équipes belges et européennes quecontre des équipes brésiliennes ou coréennes.

La méthode n◦2 prend déjà plus en compte la probabilité que la stratégie setrouve dans un tournoi : Tit-For-Tat a toutes les chances de se retrouver dansun tournoi, elle est connue comme une bonne stratégie.

3. Dans ce cas, les bits donnent la probabilité de trahir ou de coopérer.4. La stratégie qui remporte le plus de points, celle pour lequel la fonction de fitness atteint

un maximum.

21

Il est important de souligner que nous possédons une méthode d’optimisationvalable (l’AG) mais nous ne sommes pas capable de mesurer véritablement cequ’on optimise.

C’est à l’aide de ces méthodes que nous serons en mesure de déterminer sila co-évolution des stratégies dans le cas du dilemme du prisonnier itéré est unprocessus efficace ou non.

La mise en graphique des deux méthodes est détaillée au chapitre 8, page 26.

6.5 Le principe de sub-optimisationLorsqu’on essaie d’optimiser le résultat général d’un système qui comprend

des sous-systèmes distincts, on essaie de le faire en optimisant le résultat dechaque sous-système : c’est ce que l’on appelle la sub-optimisation. Dans lecas du DPI, c’est ce que nous faisons puisque nous travaillons avec un sous-espace de stratégies.

Le principe déclare que la sub-optimisation en général ne mène pas à l’op-timisation global. En effet, la sub-optimisation pour chacun des prisonniers estde dénoncer l’autre, mais ceci mène à des gains plus faible que s’ils avaient tousles deux coopéré. Autre exemple : les arbres de la forêt recherchent l’accès à lalumière; si un arbre grandit plus que son voisin, il aura plus de lumière. Ceciforcera les autres arbres à grandir pour ne pas être totalement dans l’ombre.L’effet direct sera que les arbres deviendront de plus en plus grand, dépensantplus de ressources, alors qu’ils auront la même quantité de lumière.

Ce principe est plus connu sous le nom du principe de la Reine Rouge(Red Queen Effect 5). Ce principe n’est pas comparable à une force extérieuremais il est intrinsèque à l’évolution des systèmes et il illustre bien le problèmede sub-optimisation.

5. Le nom provient du livre Alice aux pays des merveilles de Lewis Carroll.

22

Chapitre 7

Dans le code source...

7.1 Le choix du langage de programmationUn langage de programmation orienté objet est indispensable pour la réali-

sation d’un projet d’une telle ampleur. Le langage orienté objet le plus répanduet offrant le plus de possibilités est bien entendu le C++. De plus, ce langage aété enseigné en 1ère candidature. D’autres langages se prêtent également bienaux AGs, citons par exemple le Java.

Nous avons concentré nos efforts sur les résultats de notre AG et non surl’interface du logiciel : nous avons donc choisi de programmer notre AG à l’aidedu C++ en mode console et sous Microsoft Windows.

L’output 1 du programme ainsi que le code source est entièrement en anglais.

7.2 Architecture de l’algorithmeAfin d’entreprendre correctement la réalisation d’un l’algorithme, il est im-

portant de bien visualiser le déroulement de celui-ci. La conception orienté objetdu C++ facilite cet approche.

Il y a deux objets dans notre programme, ces deux objets sont du mêmetype : la classe Strategy_Table.

Le premier objet (ipd 2) contient :

– la matrice des stratégies (table) : elles constituent la population.– un fichier log : un fichier dans lequel est sauvegardé tout l’output du

programme.– un fichier stat : un fichier contenant uniquement les données intéressantes

générations après générations, fichier qui sera traité par la suite à l’aidede Microsoft Excel.

– le deuxième objet (sample) qui n’est rien d’autre que l’échantillon présentéau chapitre 6 en section 6.1. Ce deuxième objet a un contenu identique àcelui d’ipd.

1. L’interface du programme : ce que le programme affiche.2. Pour “Iterated Prisoner’s Dilemma”

23

Voici maintenant le déroulement du programme :

1. Input des paramètres :

(a) mémoire(b) taille de la population(c) nombre de coups par DPI(d) condition d’arrêt sur le score maximum de la génération en cours(e) nombre de générations(f) probabilité de mutation(g) nom du fichier log et du fichier stat

2. Création du l’objet ipd en fonction des paramètres3. Début de la boucle des générations

(a) Évaluation de la population

i. Tout le monde joue contre tout le mondeii. La stratégie qui a fait le score le plus haut joue contre toutes

les stratégie de l’échantillon, les stratégies traître et naïve jouentégalement contre l’échantillon OU la stratégie gagnante joue contreTit-For-Tat.

iii. Écriture des données de la génération en cours dans les fichierlog et stat.

(b) Applications des opérateurs de croisement et mutation.(c) Création de la nouvelle population

4. Recommencer l’étape 3 jusqu’à atteindre le nombre de générations deman-dées ou jusqu’à ce que la condition d’arrêt soit satisfaite.

Les méthodes de la classe Strategy_Table sont déclarées dans le fichier en-têtesde cette classe (strategy_table.h), le nom de chacune de ces méthodes est trèsexplicite.

7.3 Les problèmes de temps de calculLes problèmes de temps de calcul sont surtout liés à au paramètre mémoire,

en effet le temps de calcul est considérablement plus long en mémoire 4 qu’en mé-moire 3. Pour expliquer ce phénomène, il faut comprendre comment fonctionnela méthode nextmove de la classe Strategy_Table : c’est cette méthode quidétermine le coup suivant de la stratégie en fonctions des derniers coups joués.En pratique pour déterminer ce coup, on procède de la manière suivante 3 : oncompare la séquence de coups précédents avec chaque colonne de la table dedécodage (cf. Tableau 4.2) jusqu’à trouver correspondance entre les deux. Onrenvoie alors la valeur du numéro de cette colonne dans la table de décodagequi correspond au bit de la stratégie qu’il faut jouer.

3. Application de la méthode de décodage vue au chapitre 4 en section 4.5.

24

Dans une population de 200 stratégies où l’on joue 500 fois par DPI, la

méthode nextmove est appelée

matchs︷ ︸︸ ︷200 . 201

2.

coups︷︸︸︷500 .

joueurs︷︸︸︷2 = 20.100.000 de fois par

génération rien que pour la première phase d’évaluation. La table de décodagea 8 colonnes en mémoire 3 et 16 colonnes en mémoire 4 : nextmove compareradonc 2 fois plus les coups précédents en mémoire 4 qu’en mémoire 3.

A ceci s’ajoute encore la méthode decode et la fonction code, qui s’occupentrespectivement de décoder et ensuite de coder les stratégies puisque pour unebonne gestion de mémoire les stratégies sont conservées en base 10 dans table.Le temps d’exécution de cet méthode et de cette fonction est lui aussi multipliépar 2 quand on passe de la mémoire 3 à la mémoire 4.

En bref, pour un même nombre de stratégies et de coups par DPI, le temps decalcul va doubler. L’astuce consiste donc à trouver les paramètres qui minimisele temps de calcul mais sans porter atteinte à la qualité des résultats.

7.4 Le code sourceNotre programme est divisé en plusieurs fichiers :

Les fichiers en-tête :

– defined_values.h : les constantes du programme.– functions.h : déclaration des fonctions qui n’appartiennent pas à la classe

Strategy_Table.– strategy_table.h : déclaration de la classe Strategy_Table.

Les fichiers source :

– functions.cpp : les fonctions du programme qui n’appartiennent pas à laclasse Strategy_Table.

– strategy_table.cpp : les méthodes de la classe Strategy_Table.– ipd.cpp : ce fichier contient le main, c’est lui qui initialise le programme.

Le code source ce trouve en annexe A, page 33.

25

Chapitre 8

Analyse des résultats

8.1 Comment analyser des résultats?Analysons premièrement les données fournies pas notre AG. A chaque géné-

ration, le fichier stat contient les valeurs suivantes :

1. Le score maximum de la génération2. La stratégie gagnante (celle qui a le score maximum)3. Le score de la stratégie gagnante contre un échantillon OU le score de la

stratégie gagnante contre Tit-For-Tat.4. Le score de la stratégie traître contre l’échantillon.5. Le score de la stratégie naïve contre l’échantillon.6. Le score de la stratégie Tit-For-Tat contre l’échantillon

Voici un aperçu du fichier stat :

Maximum_score Winner Winner_VS_Sample ADefect ACooperate Tit-For-Tat239720 130 2017362 1843200 921600 1328448212508 16 1858496 1843200 921600 1328448167232 3 1686272 1843200 921600 1328448151160 89 1700520 1843200 921600 1328448161098 151 1446584 1843200 921600 1328448198325 89 1700520 1843200 921600 1328448196358 219 1483608 1843200 921600 1328448204586 215 1364950 1843200 921600 1328448204159 147 1774055 1843200 921600 1328448198597 29 1481670 1843200 921600 1328448

Fig. 8.1 – Aperçu du fichier stat pour les 10 premières générations

Le fichier stat est ensuite lu dans Microsoft Excel 2002 et on peut, dès lors,tracer des graphiques de l’évolution de l’AG au cours des générations.

26

8.2 L’analyse des graphiquesAnalysons le cas de la mémoire 3 avec 120 stratégies qui jouent à chaque

match 600 coups :

8.2.1 La méthode n◦1

Fig. 8.2 – Evolution de l’AG au cours des générations (méthode n◦1)

Le score maximum (—)

Cette courbe ne donne aucune information sur la “qualité” de la stratégiegagnante mais il est intéressant d’analyser l’apparition de maxima et minima.

Comment expliquer par exemple une chute du fitness entre les générations 60et 110?

Un peu avant la génération 60, la population est constituée de stratégies quiont plus tendance à coopérer que trahir. Par mutation apparaissent des stra-tégies plus traîtres, ces dernières vont expulser les stratégies présentes puisquela trahison avec la coopération rapporte 5 points pour celui qui trahi et aucunpoint pour celui qui coopère (cf. Tab. 3.1). La population de l’AG va tout douce-ment se transformer jusqu’à arriver à une population constituée entièrement destratégies assez traîtres. A partir de cet instant, le fitness va fortement diminuerpuisque la trahison avec la trahison ne remporte qu’un seul et unique point (cf.Tab. 3.1). On peut étendre ce raisonnement et dès lors comprendre pourquoile fitness remonte : à nouveau par mutation des stratégies plus altruistes appa-raissent, en jouant entre elles, ces stratégies obtiennent un meilleur score queles stratégies traîtres.

27

Le score du gagnant contre l’échantillon (—)

Cette courbe n’a de sens qu’avec les courbes Traître (—) et Naïve (—), ellesservent de maximum et minimum de référence.

Le score du gagnant contre l’échantillon nous montre que les stratégies quel’on obtient à chaque génération sont des bonnes stratégies : leur score se situeautour du maximum de référence et non autour du minimum de référence.

8.2.2 La méthode n◦2

Fig. 8.3 – Evolution de l’AG au cours des générations (méthode n◦2)

Le score maximum (—)voir section 8.2.1.

Le score du gagnant contre Tit-For-Tat (—)A nouveau, la mesure de l’évolution de l’AG prouve l’efficacité de la co-

évolution : le score se situe autour du maximum de référence et est parfoisconfondu avec celui-ci.

D’autres exemples de graphiques se trouvent en annexe B, page 45.

8.2.3 ConclusionLes deux méthodes montrent que la co-évolution des stratégies est efficace

dans le cas du DPI et pour la fonction de fitness imposée 1, elles montrentégalement que les stratégies ne s’améliorent pas en jouant.

1. voir chapitre 6, section 6.1, page 19.

28

Il est important de citer d’autres exemple de processus différent de la co-évolution :

– Sélection des individus en fonction de leur score contre l’échantillon (etpas contre celui de la population).

– Sélection des individus en fonction de leur score contre Tit-For-Tat.

Il faut bien distinguer la manière dont on sélectionne la population et la manièredont on mesure la qualité de celle-ci. Dans le cas de la co-évolution, la sélectiondépend toujours de la population.

Les résultats obtenus à l’aide des graphiques ne nous permettent évidemmentpas de conclure qu’un autre processus que la co-évolution est ou n’est pas valable.

8.3 Tit-For-Tat

8.3.1 La meilleure stratégieEn mémoire 3, la stratégie qui remporte le plus de fois le tournoi est :

01010001 (8.1)

Cette stratégie est très proche de Tit-For-Tat en mémoire 3, elle joue septfois sur huit de la même manière :

01010101 (8.2)

Pour être plus précis, Tit-For-Tat n’existe pas en mémoire 3 puisqu’en mé-moire 3 il faut définir les deux premiers coups de la stratégie 2 : si on définit ledeuxième coup de (8.2) alors cette stratégie ne sera pas Tit-For-Tat puisque,en théorie, Tit-For-Tat doit jouer le coup de l’adversaire au jeu précédent et cedepuis le deuxième jeu.

Il sera donc impossible 3 pour notre AG de converger vers Tit-For-Tat enmémoire 3 mais nous remarquons quand même qu’il converge vers un straté-gie très proche de Tit-For-Tat, assez proche pour que nous puissions conclureque (8.1) correspond à Tit-For-Tat en mémoire 3.

8.3.2 Comment expliquer l’émergence de l’altruisme dansle cas de l’évolution génétique?

Si on prend l’exemple de deux groupes : l’un coopératif, l’autre égoïste. Legroupe dans lequel les individus coopéreront rassemblera plus de ressources etsera dès lors sélectionné puisqu’il sera meilleur, tandis que le groupe qui necoopérera pas sera éliminé. Mais l’erreur dans ce raisonnement est subtile :

Même s’il est vrai que les individus d’un groupe coopératif auront plus dechance de survivre, au sein même du groupe il existera automatiquement diffé-rents degrés de coopération. Les plus égoïstes auront les mêmes avantages que

2. voir chapitre 4, section 4.2, page 103. Ceci aurait été possible si notre AG permettait de travailler entres les différents mémoires.

29

les meilleurs groupes de coopérateurs mais auront moins de désavantages vuqu’il dépensent moins de ressources ou prennent moins de risques à aider lesautres. Le résultat est que les égoïstes seront meilleurs que les altruistes et leursgènes remplaceront ceux des altruistes. En d’autres mots, la coopération entreles groupes sur une base génétique tend à être auto-destructive.

Les stratégies altruistes peuvent amener à une augmentation du fitness dugroupe mais elles ne sont pas stables : elles peuvents être envahies par des stra-tégies égoïstes. Ces stratégies égoïstes mènent à une diminution du fitness dugroupe mais sont localement plus fortes que les altruistes.

Ceci est une autre expression du principe de sub-optimisation 4 : l’évolutiongénétique fonctionne au niveau des sous-systèmes et ce qui est optimal à unniveau sera sélectionné bien qu’il soit loin d’être optimal au niveau du système.

Comment rendre alors ces stratégies altruistes plus stables?

En introduisant la notion d’altruisme conditionnel : l’individu aidera un autreseulement s’il s’attend à ce que celui-ci lui retourne faveur. Si l’autre ne coopèreplus, l’altruiste conditionnel arrêtera de coopérer et par conséquent ne donnerapas l’occasion à l’égoïste de gagner plus que lui.

Ces stratégies seront donc plus stables dans le sens où elles ne se feront pasfacilement envahir, alors qu’elles garderont les avantages de la coopération avecles individus qui le voudront.

La stratégie altruiste conditionnelle n’est rien d’autre que Tit-For-Tat, sescaractéristiques peuvent êtres résumées par ces trois concepts :

1. Elle est gentille : cela signifie qu’elle ne sera jamais la première à trahir.2. Elle est revancharde : si l’adversaire la trahit, elle trahira immédiatement.3. Elle n’est pas rancunière : aussitôt que l’adversaire se remet à coopérer,

elle oublie les trahisons précédente et se remet à coopérer à son tour.

La gentillesse est avantageuse car elle ouvre la voie à la bénéfique coopérationmutuelle. Le fait d’être revancharde est nécessaire pour éviter de se faire envahirpar des égoïstes mais sa faculté à pardonner lui assure un retour à la gentillesse.

Mais Tit-For-Tat n’est pas une stratégie stable dans le sens strict du terme.En effet, si, durant l’évolution, la population est majoritairement composée destratégies du type Tit-For-Tat, d’autres stratégies moins revanchardes ou encoremoins rancunières deviendront meilleures puisqu’il n’y aura plus de stratégiesqui tire avantage de leur altruisme conditionnel. Cependant, une fois qu’unpourcentage suffisant de stratégies deviennent trop altruistes, à nouveau desstratégies égoïstes pourront augmenter leur fitness en exploitant leur altruisme.

Un autre aspect également dérangeant dans Tit-For-Tat réside dans le faitqu’elle applique durement la loi du Talion 5. Une fois qu’une querelle naît, ellepeut durer indéfiniment. Cela reflète bien des conflits que l’on rencontre enpolitique internationale : conflit israëlo-palestinien, le conflit indo-pakistanais.etc.

4. voir chapitre 6, section 6.5, page 22.5. “Oeil pour oeil, dent pour dent “

30

Chapitre 9

Conclusion

Les chapitres 3 à 8 ont permis de répondre aux questions posées par l’énoncédu projet 1.

Seule une question n’a pas encore été abordée :Que se passe-t-il si les joueurs peuvent signaler leur intention?Imaginons que le malfaiteur et son complice aient eut le temps de se concerter

brièvement lors de l’arrestation. Lors de l’interrogatoire de police, l’inspecteurpose le dilemme que nous connaissons. Le malfaiteur entamera alors la réflexionsuivante :

“Si nous respectons notre arrangement, alors ....““Si je suis le seul à respecter notre arrangement, alors ...”En fait, un deuxième dilemme du prisonnier apparaît : le malfaiteur doit

choisir, non seulement, entre dénoncer ou couvrir son complice mais égalemententre respecter ou non l’arrangement.

C’est un dilemme du prisonnier à l’intérieur d’un autre. Mais cecin’est il pas un seul dilemme du prisonnier?

1. voir chapitre 1, page 4.

31

Deuxième partie

Les Annexes

32

Annexe A

Le code source

A.1 defined_values.h#line 2 "defined_values.h"#ifndef DEFINED_VALUES#define DEFINED_VALUES#define line_53 cout < < "_____________________________________________________\n";#define line_star29t cout < < "\t*****************************\n";#define line_star29ttt cout < < "\t\t\t*****************************\n";const int ASC0 = 48;const int ASC1 = 49;const int K = 3;const int L = 1;const int M = 5;const int N = 0;#endif

A.2 functions.h#line 2 "functions.h"#ifndef FUNCTIONS#define FUNCTIONSbool bincmp(int *buffer1, int *buffer2, int len);bool exist(int value, int *buffer, int len);void getline(int **matrix, int row, int *buffer, int len);void invgetline(int **matrix, int row, int *buffer, int len);int code(int *code, int len);#endif

A.3 functions.cpp#line 2 "functions.cpp"#include "functions.h"#include <math.h>bool bincmp(int *buffer1, int *buffer2, int len) {

int ok=0;for (int i=0; i<len; i++) {

if (buffer1[i] == buffer2[i]) ok++;}return ok == i? true : false;

}bool exist(int value, int *buffer, int len) {

bool ok=false;for (int i=0; i<len; i++) {

33

if (buffer[i] == value) {ok = true; break;}}return ok;

}void getline(int **matrix, int row, int *buffer, int len) {

for (int i=0; i<len; i++) buffer[i] = matrix[row][i];}void invgetline(int **matrix, int row, int *buffer, int len) {

for (int i=0; i<len; i++) buffer[i] = matrix[row][len-i-1];}int code(int *code, int len){

int result=0;for (int i=0; i<len; i++) {

result += ( (code[(len-1)-i]) * pow (2,i) );}return result;

}

A.4 strategy_table.h#line 2 "strategy_table.h"#ifndef STRATEGY_TABLE#define STRATEGY_TABLE#include <fstream>using namespace std;class Strategy_Table {

private:int memory, strategies, bits, max_strategies;int *strategy1d, *strategy2d, *last1, *last2, *last, *temp;int **table, **decrypt, **lastmoves, *present, *wintimes;char *bufferdecode;Strategy_Table *sample;unsigned long n_display, n_decode, n_newgeneration, n_evaluate;unsigned long n_max, n_standard_deviation, n_resetscores;unsigned long n_randmoves, n_play, n_nextmove, n_sort, n_cross;unsigned long n_mutate, n_winner, n_and_the_winner_is, n_reset;ofstream *statfile, *infofile;

public:ofstream *logfile;Strategy_Table(int memory, int pop_size, char *log, char *stat);Strategy_Table(int memory, int strategies, int bits);virtual ~Strategy_Table();void newgeneration(int moves, float mutationp, int i);void evaluate(int moves);void play(int strategy1_row, int strategy2_row, int moves);int nextmove(int strategy_row, int *strategyd, int player, int i);void decode(int row, int *code);void sort();void display(bool binary = false);void cross(int strategy1_row, int strategy2_row);void mutate(int strategy_row, float probability);int max();int winner();float standard_deviation(int column);void reset();void resetscores();void randmoves();int and_the_winner_is();

};#endif

34

A.5 strategy_table.cpp#line 2 "strategy_table.cpp"#include "strategy_table.h"#include <iostream>#include <math.h>#include <time.h>#include <stdlib.h>#include <conio.h>#include "functions.h"#include "defined_values.h"Strategy_Table::Strategy_Table(int memory, int pop_size, char *log, char *stat) {

srand(time(NULL));time_t rawtime;struct tm *timeinfo;time (&rawtime);timeinfo = localtime(&rawtime);

logfile = new ofstream (logfilename);statfile = new ofstream(statfilename);infofile = new ofstream("info.txt");

*logfile < < "Start time : " < < asctime(timeinfo) < < endl;*statfile < < "Maximum_score Winner Winner_VS_Sample ADefect ACooperate TFT\n";*infofile < < "Start time : " < < asctime(timeinfo) < < endl;bits = pow(2, memory);strategies = population_size;max_strategies = pow(2, bits);this->memory = memory;strategy1d = new int [bits],strategy2d = new int [bits];last = new int [memory];temp = new int [memory];bufferdecode = new char [bits];int *population = new int [population_size], p;table = new int *[strategies];for (int i=0; i<strategies; i++) {

table[i] = new int [4];p = rand()%max_strategies;while ( exist(p, population, i+1) ) p = rand()%max_strategies;population[i] = p;table[i][0] = p;table[i][1] = rand()%2;table[i][2] = rand()%2;table[i][3] = 0;

}decrypt = new int *[bits];for (int l=0; l<bits; l++) {

decrypt[l] = new int [memory];itoa(l,bufferdecode,2);int zeros = memory - strlen(bufferdecode);for (int m=0; m<memory; m++) {

if (m<zeros) decrypt[l][m] = 0;else decrypt[l][m] = bufferdecode[m-zeros] - ASC0;

}}

int k;if ( (memory==1) || (memory==2) ) {

lastmoves = new int *[1];for (k=0; k<1; k++) lastmoves[k] = new int [2];

}else {

lastmoves = new int *[2];for (k=0; k<2; k++) lastmoves[k] = new int [2];last1 = new int [2];last2 = new int [2];

35

}

sample = new Strategy_Table(memory, ((4*max_strategies)+4), bits);wintimes = new int [max_strategies];for (int j=0; j<max_strategies; j++) wintimes[j] = 0;n_display=n_decode=n_newgeneration=n_evaluate=n_max=0;

n_standard_deviation=n_resetscores=0;n_randmoves=n_play=n_nextmove=n_sort=n_cross=n_mutate=n_winner=0;

n_and_the_winner_is=n_reset=0;

}Strategy_Table::Strategy_Table(int memory, int strategies, int bits) {

this->bits = bits;this->strategies = strategies;max_strategies = pow(2, bits);this->memory = memory;

strategy1d = new int [bits],strategy2d = new int [bits];last = new int [memory];temp = new int [memory];bufferdecode = new char [bits];

table = new int *[strategies];for (int i=0; i<max_strategies; i++) {

table[i] = new int [4];table[i][0] = i;table[i][1] = 0;table[i][2] = 0;table[i][3] = 0;

}for (i=max_strategies; i<(2*max_strategies); i++) {

table[i] = new int [4];table[i][0] = i-max_strategies;table[i][1] = 0;table[i][2] = 1;table[i][3] = 0;

}

for (i=(2*max_strategies); i<(3*max_strategies); i++) {table[i] = new int [4];table[i][0] = i-(2*max_strategies);table[i][1] = 1;table[i][2] = 0;table[i][3] = 0;

}

for (i=(3*max_strategies); i<(4*max_strategies); i++) {table[i] = new int [4];table[i][0] = i-(3*max_strategies);table[i][1] = 1;table[i][2] = 1;table[i][3] = 0;

}table[(4*max_strategies)] = new int[4];table[(4*max_strategies)+1] = new int[4];table[(4*max_strategies)+2] = new int[4];table[(4*max_strategies)+3] = new int[4];decrypt = new int *[bits];for (int l=0; l<bits; l++) {

decrypt[l] = new int [memory];itoa(l,bufferdecode,2);int zeros = memory - strlen(bufferdecode);for (int m=0; m<memory; m++) {

if (m<zeros) decrypt[l][m] = 0;else decrypt[l][m] = bufferdecode[m-zeros] - ASC0;

}

36

}int k;if ( (memory==1) || (memory==2) ) {

lastmoves = new int *[1];for (k=0; k<1; k++) lastmoves[k] = new int [2];

}else {

lastmoves = new int *[2];for (k=0; k<2; k++) lastmoves[k] = new int [2];last1 = new int [2];last2 = new int [2];

}}Strategy_Table::~Strategy_Table() {

time_t rawtime;struct tm *timeinfo;time (&rawtime);timeinfo = localtime(&rawtime);*logfile < < "End time : " < < asctime(timeinfo);*statfile < < and_the_winner_is();int total = n_newgeneration+n_evaluate+n_play+n_nextmove+n_decode;total += n_sort+n_display+n_cross+n_mutate+n_max;total += n_standard_deviation+n_resetscores+n_randmoves;total += n_winner+n_and_the_winner_is;*infofile < < "End time : " < < asctime(timeinfo) < < endl;*infofile < < "newgeneration(int, float, int) : " < < n_newgeneration;*infofile < < "\tevaluate(int) : " < < n_evaluate;*infofile < < "\t\tplay(int, int, int) : " < < n_play;*infofile < < "\t\t\tnextmove(int, int*, int, int) : " < < n_nextmove;*infofile < < "\t\t\t\tdecode(int, int*) : " < < n_decode;*infofile < < "\tsort() : " < < n_sort;*infofile < < "\tdisplay(bool) : " < < n_display;*infofile < < "\treset() : " < < n_reset;*infofile < < "\tcross(int, int) : " < < n_cross;*infofile < < "\tmutate(int, float) : " < < n_mutate;*infofile < < "\tmax() : " < < n_max;*infofile < < "\twinner() : " < < n_winner;*infofile < < "\tstandard_deviation(int) : " < < n_standard_deviation;*infofile < < "\tresetscores() : " < < n_resetscores;*infofile < < "\trandmoves() : " < < n_randmoves;*infofile < < "and_the_winner_is() : " < < n_and_the_winner_is;*infofile < < "TOTAL : " < < total;*infofile < < " c© Jonathan Goldwasser";

logfile->close();statfile->close();infofile->close();

for (int i=0; i<strategies; i++) {delete[] table[i]; table[i] = NULL;}for (int j=0; j<bits; j++) {delete[] decrypt[j]; decrypt[j] = NULL;}delete[] table, lastmoves, wintimes, strategy1d, strategy2d;delete[] last, temp, bufferdecode;table = NULL;lastmoves = NULL;wintimes = NULL;strategy1d = NULL;strategy2d = NULL;last = NULL;temp = NULL;bufferdecode = NULL;if ( (memory==3) || (memory==4) ) {

delete[] last1, last2;last1 = NULL;last2 = NULL;

}}void Strategy_Table::newgeneration(int moves, float mutationp, int i) {

37

n_newgeneration++;cout < < "Processing generation #" < < i+1 < < " :\n";*logfile < < "Generation #" < < i+1 < < ":\n";

cout < < "Evaluating :\n";evaluate(moves);cout < < "Crossing";int best = strategies/2, *parent_list = new int [best];for (int j=0; j<best; j++) parent_list[j] = -1;for (int k=0; k<best; k++) {

int parent = rand()%best;if (exist(k, parent_list, best)) continue;while ( ( exist(parent, parent_list, k+1) ) || (parent <= k) ) parent

= rand()%best;parent_list[k] = parent;cross(k, parent);

}cout < < "... Done\n";cout < < "Mutating";for (int l = best; l<strategies; l++) {

mutate(l, mutationp);}cout < < "... Done\n";cout < < "Randomizing first moves";randmoves();cout < < "... Done\n\n";

}void Strategy_Table::evaluate(int moves) {

n_evaluate++;cout < < "Step 1";for (int i=0; i<strategies; i++) {

cout < < ".";for (int j=i+1; j<strategies; j++) {

play(i, j, moves);}

}sort();cout < < " Done\n";*statfile < < max() < < " " < < winner() < < " ";

cout < < "Step 2...";sample->reset();sample->table[4*(max_strategies)][0] = winner();sample->table[4*(max_strategies)][1] = table[0][1];sample->table[4*(max_strategies)][2] = table[0][2];sample->table[4*(max_strategies)][3] = 0;

for (int l=0; l<4; l++) {for (int k=0; k<4*(max_strategies); k++) {

if (k%10==0) cout < < ".";sample->play(((4*max_strategies)+l), k, moves);

}sample->sort();*statfile < < sample->max() < < " ";sample->reset();

}*statfile < < endl;cout < < " Done\n\n";display(true);

cout < < "\n Maximum score : " < < max() < < " (" < < winner() < < ")\n";

wintimes[winner()]++;}void Strategy_Table::play(int strategy1_row, int strategy2_row, int moves) {

n_play++;int score1=0, score2=0, move1, move2;

38

decode(strategy1_row, strategy1d);decode(strategy2_row, strategy2d);for (int i=0; i<moves; i++) {

move1 = nextmove(strategy1_row, strategy1d, 1, i);move2 = nextmove(strategy2_row, strategy2d, 2, i);if ( (memory == 1) || (memory == 2) ) {

lastmoves[0][0] = move1;lastmoves[0][1] = move2;

}else {

lastmoves[i%2][0] = move1;lastmoves[i%2][1] = move2;

}if (move1 == 0 && move2 == 0) {score1 += L; score2 += L;}if (move1 == 0 && move2 == 1) {score1 += M; score2 += N;}if (move1 == 1 && move2 == 0) {score1 += N; score2 += M;}if (move1 == 1 && move2 == 1) {score1 += K; score2 += K;}

}table[strategy1_row][3] += score1;table[strategy2_row][3] += score2;

}int Strategy_Table::nextmove(int strategy_row, int *strategyd, int player, int i) {

n_nextmove++;switch (memory) {

case 1:if (i==0) return table[strategy_row][1];else return lastmoves[0][2-player] == 0? strategyd[0] :

strategyd[1];break;

case 2:if (i==0) return table[strategy_row][1];else {

if (player == 1) getline(lastmoves, 0, last, 2);else invgetline(lastmoves, 0, last, 2);for (int j=0; j<4; j++) {

getline(decrypt, j, temp, 2);if (bincmp(last, temp, 2) == true) {

return strategyd[j];}

}}break;

case 3:if (i==0) return table[strategy_row][1];else if (i==1) return table[strategy_row][2];else {

last[0] = lastmoves[0][2-player];if (player == 1) getline(lastmoves, 1, last1, 2);else invgetline(lastmoves, 1, last1, 2);for (int k=1; k<3; k++) last[k] = last1[k-1];for (int j=0; j<8; j++) {

getline(decrypt, j, temp, 3);if (bincmp(last, temp, 3) == true) {return strategyd[j];}

}}break;

case 4:if (i==0) return table[strategy_row][1];else if (i==1) return table[strategy_row][2];else {

if (player == 1) {getline(lastmoves, 0, last1, 2);getline(lastmoves, 1, last2, 2);}

else {invgetline(lastmoves, 0, last1, 2);invgetline(lastmoves, 1, last2, 2);}

for (int k=0; k<4; k++) {

39

if (k<2) last[k] = last1[k];if (k>=2) last[k] = last2[k-2];

}for (int j=0; j<16; j++) {

getline(decrypt, j, temp, 4);if (bincmp(last, temp, 4) == true) {

return strategyd[j];}

}}

}}void Strategy_Table::decode(int row, int *code) {

n_decode++;int zeros;itoa(table[row][0],bufferdecode,2);zeros = bits - strlen(bufferdecode);for (int i=0; i<bits; i++) {

if (i<zeros) code[i]=0;else code[i] = bufferdecode[i-zeros] - ASC0;

}}void Strategy_Table::sort() {

n_sort++;int temp1,temp2,temp3,temp4, ktemp;for (int l=0; l<strategies;l++){

ktemp=l;temp1=table[l][0];temp2=table[l][1];temp3=table[l][2];temp4=table[l][3];for (int k=l+1; k<strategies; k++){

if (temp4<=table [k][3]){temp2=table[k][1];temp1=table[k][0];temp3=table[k][2];

temp4=table[k][3];ktemp=k;

}}if (ktemp != l) {

for (int m=ktemp;m>l; m--) {table[m][0]=table[m-1][0];table[m][1]=table[m-1][1];table[m][2]=table[m-1][2];table[m][3]=table[m-1][3];

}}table[l][0]=temp1;table[l][1]=temp2;table[l][2]=temp3;table[l][3]=temp4;

}}void Strategy_Table::display(bool binary) {

n_display++;if (binary == false) {

for (int i=0; i<strategies; i++) {cout < < table[i][0] < < " " < < table[i][1] < < " " < <

table[i][2] < < " " < < table[i][3] < < endl;}

}else {

for (int i=0; i<strategies; i++) {int *buffer = new int [bits];decode(i, buffer);for (int j=0; j<bits; j++) {cout < < buffer[j]; *logfile < <

40

buffer[j];}cout < < " " < < table[i][1] < < " " < < table[i][2] < < "

" < < table[i][3] < < endl;*logfile < < " " < < table[i][1] < < " " < < table[i][2]

< < " " < < table[i][3] < < endl;delete[] buffer;buffer = NULL;

}*logfile < < endl;

}}void Strategy_Table::cross(int strategy1_row, int strategy2_row) {

n_cross++;int position, temp;decode(strategy1_row, strategy1d);decode(strategy2_row, strategy2d);position = ( rand() % (bits-2) ) + 1;for (int i=position; i<bits; i++) {

temp = strategy1d[i];strategy1d[i] = strategy2d[i];strategy2d[i] = temp;

}int newrow1 = strategy1_row + (strategies/2);int newrow2 = strategy2_row + (strategies/2);table[newrow1][0] = code(strategy1d, bits);table[newrow2][0] = code(strategy2d, bits);

}void Strategy_Table::mutate(int strategy_row, float probability) {

n_mutate++;int *buffer = new int [bits];decode(strategy_row, buffer);for (int j=0; j<bits; j++) {

int p = rand()%100;if ( p < probability ) {

buffer[j] = buffer[j] == 0? 1 : 0;}

table[strategy_row][0] = code(buffer, bits);}delete[] buffer;buffer = NULL;

}int Strategy_Table::max() {

n_max++;return table[0][3];

}int Strategy_Table::winner() {

n_winner++;return table[0][0];

}float Strategy_Table::standard_deviation(int column) {

n_standard_deviation++;float average=0, stdev=0;for (int i=0; i<strategies; i++) average += table[i][column];average /= strategies;for (int j=0; j<strategies; j++) stdev += pow((table[j][column] - average),

2);stdev /= strategies;stdev = sqrt(stdev);return stdev;

}void Strategy_Table::reset() {

n_reset++;for (int i=0; i<max_strategies; i++) {

table[i][0] = i;table[i][1] = 0;table[i][2] = 0;table[i][3] = 0;

41

}for (i=max_strategies; i<(2*max_strategies); i++) {

table[i][0] = i-(max_strategies);table[i][1] = 0;table[i][2] = 1;table[i][3] = 0;

}

for (i=(2*max_strategies); i<(3*max_strategies); i++) {table[i][0] = i-(2*max_strategies);table[i][1] = 1;table[i][2] = 0;table[i][3] = 0;

}

for (i=(3*max_strategies); i<(4*max_strategies); i++) {table[i][0] = i-(3*max_strategies);table[i][1] = 1;table[i][2] = 1;table[i][3] = 0;

}table[4*(max_strategies)+1][0] = 0;table[4*(max_strategies)+1][1] = 0;table[4*(max_strategies)+1][2] = 0;table[4*(max_strategies)+1][3] = 0;

table[4*(max_strategies)+2][0] = 255;table[4*(max_strategies)+2][1] = 1;table[4*(max_strategies)+2][2] = 1;table[4*(max_strategies)+2][3] = 0;table[4*(max_strategies)+3][0] = 55;table[4*(max_strategies)+3][1] = 1;table[4*(max_strategies)+3][2] = 1;table[4*(max_strategies)+3][3] = 0;

}void Strategy_Table::resetscores() {

n_resetscores++;for (int i=0; i<strategies; i++) {

table[i][3] = 0;}

}void Strategy_Table::randmoves() {

n_randmoves++;int best = strategies/2;for (int i=best; i<strategies; i++) {

table[i][1] = rand()%2;table[i][2] = rand()%2;

}}int Strategy_Table::and_the_winner_is() {

n_and_the_winner_is++;int max=wintimes[0], i_max=0;for (int i=1; i<max_strategies; i++) {

if (wintimes[i] > max) {max = wintimes[i]; i_max = i;}}return i_max;

}

42

A.6 ipd.cpp#line 2 "ipd.cpp"#include <iostream>#include <conio.h>#include <math.h>#include "strategy_table.h"#include "defined_values.h"using namespace std;int main() {

int memory, max_strategies, population_size, moves, max, stop, max_generations;float mutationp;char *logfilename = new char [20], *statfilename = new char [20];

bool pause=false;

line_star29t;cout < < "\t* Genetic Algorithm For IPD *\n";line_star29t;cout < < "\t* Using Memory Strategies *\n";line_star29t;cout < < endl;line_53;cout < < "\n Please specify the following parameters :\n\n";cout < < " Memory (1-4) : ";cin > > memory;if ( (memory==0) || (memory>4) ) {

while ( (memory==0) || (memory>4) ) {cout < < " Please enter a number from 1 to 4\n";cout < < " Memory : ";cin > > memory;

}}max_strategies = pow(2, pow(2, memory));cout < < " Population size : ";cin > > population_size;if ( (population_size > max_strategies) || (population_size%4 != 0) ) {

while ( (population_size > max_strategies) || (population_size%4 != 0) ) {cout < < " Please enter a number lower or equal to " < < max_strategies < < " and

divisible by 4\n";cout < < " Population size : ";cin > > population_size;

}}cout < < " Moves per IPD : ";cin > > moves;max = ( moves * ( population_size - 1 ) * M );cout < < " Maximum score for these parameters is : " < < max < < endl;cout < < " 75% of max : " < < (max*3)/4 < < endl;cout < < " 66% of max : " < < (max*2)/3 < < endl;cout < < " Stop condition (0 for maximum) : ";cin > > stop;stop = stop == 0? max : stop;cout < < " Maximum number of generations : ";cin > > max_generations;cout < < " Mutation probability (%) : ";cin > > mutationp;if ( mutationp>100 ) {

while ( mutationp>100 ) {cout < < " Please enter a number lower or equal to 100\n";cout < < " Mutation probabilty (%) : ";cin > > mutationp;

}}char choice=’ ’;cout < < " Pause between generations (y/n)? ";cin > > choice;

43

if ( (choice != ’y’) || (choice != ’n’) ) {while ( (choice != ’y’ ) && (choice != ’n’) ) {

cout < < " Please enter ’y’ or ’n’\n";cout < < " Pause between generations (y/n)? ";cin > > choice;

}}pause = choice == ’y’? true : false;cout < < " Name of log file : ";cin > > logfilename;cout < < " Name of statistic file : ";cin > > statfilename;line_53;cout < < endl;Strategy_Table ipd(memory, population_size, logfilename, statfilename);

*ipd.logfile < < "Memory : " < < memory < < endl;*ipd.logfile < < "Population size : " < < population_size < < endl;*ipd.logfile < < "Moves per IPD : " < < moves < < endl;*ipd.logfile < < "Maximum score : " < < max < < endl;*ipd.logfile < < "Stop condition : " < < stop < < endl;*ipd.logfile < < "Maximum number of generations : " < < max_generations < < endl;*ipd.logfile < < "Mutation probability : " < < mutationp < < endl < < endl;for (int i=0; i<max_generations; i++) {

ipd.newgeneration(moves, mutationp, i);

if ( ( ipd.max() >= stop ) ) break;

ipd.resetscores();

if ( (pause == true) || (i==0) ) {cout < < "Press any key to continue to the next generation...\n\n";getch();

}}line_star29ttt;cout < < "\t\t\t And the winner is : " < < ipd.and_the_winner_is() < < endl;line_star29ttt;*ipd.logfile < < "\t\t\t And the winner is : " < < ipd.and_the_winner_is() < < endl < < endl;cout < < "\n\n\n\n\t\tPress any key to exit\n\n\n";getch();return 0;

}

44

Annexe B

Les graphiques

En mémoire 3 avec 200 stratégies et 600 coups par matchs :

Fig. B.1 – Evolution de l’AG au cours des générations (méthode n◦1)

45

Fig. B.2 – Evolution de l’AG au cours des générations (méthode n◦2)

46

Annexe C

L’organisation au sein dugroupe

C.1 Le planningSemaine 1 Présentation du projet, familiarisation avec le sujet.Semaine 2 Mise en commun des informations recueillies lors des premières

recherche, discussion sur le travail à effectuer.Semaine 3 Détermination de la répartition des tâches pour les réunions sui-

vantes.Semaine 4 Établissements des règles du jeu, des hypothèses. Choix des para-

mètres pour l’algorithme génétique.Semaine 5 Première ébauche de rencontre entre deux stratégies (algorithme

simple). Test et améliorations à apporter.Semaine 6 Choix précis des configurations de notre AG et début de l’implé-

mentation.Semaine 7 Suite de l’implémentation de l’AG.Semaine 8 Suite de l’implémentation de l’AG.Semaine 9 Suite et fin du développement de l’AG, tests et observations.Semaine 10 Début de l’analyse des résultats, premiers graphiques.Semaine 11 Détermination de la répartition des tâches pour l’écriture du rap-

port. Interprétation des graphiques et analyse des résultats.Semaine 12 Écriture du rapport. Analyse des résultats et conclusions par-

tielles.Semaine 13 Conclusion finale et fin de l’écriture du rapport.Semaine 14 Mise au point pour la présentation orale.

47

C.2 La répartition des tâchesLa répartition des tâches a été très équitable puisque la quantité de travail

répartie a été pondérée par les compétences personnelles.

C.2.1 Pour la modélisation– Jonathan Goldwasser & Gian Luca Rattacaso

– Implémentation du code de l’algorithme en C++.– Recherches sur internet.– Recherches sur la manière d’analyser les résultats de l’algorithme.– Mise en graphique des résultats à l’aide de Microsoft Excel 2002.

– Huan Alexandre Bui Manh & Eyal Szombat

– Élaboration du planning.– Recherches approfondies sur les algorithmes génétiques, le dilemme

du prisonnier, la co-évolution et la sub-optimisation.– Recherches bibliographiques.– Recherches sur la manière d’analyser les résultats de l’algorithme.

C.2.2 Pour l’écriture du rapport et la présentation oraleChaque membre du groupe a écrit le quart du rapport, il est inutile de

détailler la répartition des tâches.La défense du projet est présentée par l’entièreté du groupe.

C.3 L’organisation des réunionsL’alternance des animateurs et secrétaires fut assurée chaque semaine.Les réunions n’étaient pas dès le début optimales (cf. grilles d’observations

en section C.5) mais se sont très vite améliorées.En général, les réunions duraient en moyenne une heure. Aucun travail n’a

été effectué en réunion, seules des mises au points et des mises en commund’informations eurent lieu. Les réunions débordaient parfois lors des réflexionssur les différents problèmes et contraintes du projet.

C.4 Internet et l’organisationInternet a grandement contribué à l’organisation du projet :

– Microsoft MSN Messenger : Entre les réunions, certaines mise au pointeurent lieu sur MSN.

– Création d’un site internet : Un site internet été réalisé (http://ipd.goldwasser.net). Chaque membre du groupe avait accès en permanencesau dernières versions du rapport et de l’algorithme et pouvait lui-mêmemettre à jour ceux-ci.

48

C.5 Les ordres du jours, procès verbaux et grillesd’observations

Ci-joint les ordres du jours, procès verbaux et grilles d’observations.

49

Bibliographie

[1] Dr. Joshua Knowles et Dr. Marco Dorigo, L’énoncé du projet (2002).[2] Robert Axelrod, The Evolution of Cooperation (1985), Paperback -

ISBN : 0-465-02121-2[3] Emanuel Falkenauer, Genetic Algorithms and Grouping Problems

(1998), John Wiley & Sons - ISBN : 0-471-97150-2[4] Hugues Bersini, Tutorial on Evolutionary Programming (1992) (Technical

Report)[5] Lawrence Davis, Genectic Algorithms and Simulated Annealing (1998),

Pitman - ISBN : 0-934613-44-3[6] Professeur M. Lacroix, L’évolution de la coopération - Modélisation par

le Dilemme du Prisonnier Itératif (1998), http://www.fapse.ulg.ac.be/Lab/cogsci/clabiouse/prisoner_dilemma.pdf

[7] Gyongyike Gebeova, Miroslav Hudec, Peter Kostelnik et Vrati-slav Kovac, The experimental study of the competitive co-evolution usingPredator-Prey tasks, http://neuron-ai.tuke.sk/~kostelni/publikacie/zdroje/e-isci/2/paper.pdf

[8] Thomas Vallee et Murat Yildizoglu, Présentation des AlgorithmesGénétiques et de leurs Applications en Économie (2001), http://beagle.montesquieu.u-bordeaux.fr/yildi/files/agpresf.pdf

[9] Kristian Lindgren, The Iterated Prisoner’s Dilemma (IPD) as a Testbedof Evolutionary Algorithm (1991), http://www.mdx.ac.uk/www/psychology/cog/psy3260/prisoner.htm

50

Liste des tableaux

3.1 Tableau des points . . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 Score de la stratégie ligne lors du match contre la stratégie colonne . . . . 8

4.1 Exemple de stratégie à mémoire 3 . . . . . . . . . . . . . . . . . 104.2 Exemple de stratégie à mémoire 3 . . . . . . . . . . . . . . . . . 114.4 Matrice des stratégies de la mémoire n . . . . . . . . . . . . . . . 12

5.1 Population initiale . . . . . . . . . . . . . . . . . . . . . . . . . . 175.2 La sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.3 Le croisement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.4 La mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.5 Population finale (après une génération) . . . . . . . . . . . . . . 18

6.1 Configurations testées par notre AG . . . . . . . . . . . . . . . . 20

51

Table des figures

8.1 Aperçu du fichier stat pour les 10 premières générations . . . . . 268.2 Evolution de l’AG au cours des générations (méthode n◦1) . . . . 278.3 Evolution de l’AG au cours des générations (méthode n◦2) . . . . 28

B.1 Evolution de l’AG au cours des générations (méthode n◦1) . . . . 45B.2 Evolution de l’AG au cours des générations (méthode n◦2) . . . . 46

52

Index

échantillon, 21, 23, 24, 28, 29économie, 14égoïste, 29élitiste, 15évolutif, 14, 15, 18évolution, 5, 15, 21, 22, 29, 30

adversaire, 8, 11, 13AG, 14, 22, 26, 27, 47Albert W. Tucker, 5algorithme, 4, 7, 8, 10, 12, 14–16,

18–20, 23, 47, 48altruisme, 29altruiste, 27, 30analyse, 47analyser, 26Anatol Rapoport, 5animateur, 48arbre, 22armement, 1

bénéfice, 6base 10, 12, 25base 2, 12bibliographique, 48bijection, 12bit, 11, 12, 14–17, 20, 24boucle, 24but, 4

C++, 23calcul (temps de), 24chromosome, 14, 15classe, 23, 24co-évolution, 4, 22, 28, 29, 48codage binaire, 14code, 18complice, 6conclusion, 47conditionnel, 30conducteur, 6

configuration, 47converger, 29coopérer, 1, 7, 11, 13, 27, 29, 30coup, 8, 10–13, 24, 25couvrir, 6croisement, 14–17, 19, 20, 24cycle, 14

décoder, 12, 25dénoncer, 6, 22DPI, 7, 22, 24, 25

en-tête, 25entièrement définie, 11Excel, 26exemple, 10, 11, 16, 22, 29

faiblesse, 15fichier, 23–25fitness (fonction de), 14, 15, 17, 18,

21, 27, 30football, 21forêt, 22

généralisation, 11génération, 15, 18, 19, 21, 24, 26, 28génétique, 4, 8, 12, 14, 16, 18, 19,

29, 30, 47, 48gentille, 30graphique, 22, 26, 27, 29, 47, 48

hypothèse, 21, 47

impair, 10, 11implémentation, 47, 48individu, 14–16, 30indo-pakistanais, 30internet, 48ipd, 23israelo-palestinien, 30itéré, 7, 8

53

Java, 23jeu, 11, 13, 47jeu du dilemme du prisonnier, 6, 8,

19, 21joueur, 4, 31

Kyoto, 1

langage, 23log, 23lumière, 22lunatique, 7, 20

mémoire, 8, 10–13, 19–21, 24, 25, 27,29

méthode, 21, 24malfaiteur, 6Markov, 8markovienne, 8, 21match, 27matrice, 12maxima, 27maximum, 16–18, 21, 24, 26–28Melvin Drescher, 5Merill Flood, 5mesurer, 21, 22, 29minima, 27modéliser, 7, 8, 10monde du travail, 6mort, 15mutation, 14–17, 19, 20, 24

naïve, 7, 8, 21, 24, 26nextmove, 24nombres binaires, 12non-élitiste, 15nucléaire, 1

objet, 23observation, 47ombre, 22opérateur, 14, 15, 19, 20, 24optimiser, 22organisation, 47orienté objet, 23output, 23

périodique, 7, 20pair, 10, 11paramètre, 16, 25, 47parité, 10

performance, 14, 15planning, 47, 48point, 7, 21police, 6politique, 30pondérer, 21population, 14–16, 18, 19, 24, 25, 27,

29, 30presque entièrement définie, 11probabilité, 7, 8, 15–17, 19, 21, 24processus, 4, 22, 29profit, 6programme, 23projet, 4protocole, 1

réactive, 8réunion, 47, 48règle, 47rancunière, 7, 8, 20, 30rapport, 47recherche, 48reformuler, 7reine rouge, 22remise de peine, 6ressource, 1, 22, 29, 30revancharde, 30Robert Axelrod, 5route, 6

sélection, 14, 15, 17, 19séquence, 14, 16, 17, 20score, 8, 21, 26–29secrétaire, 48site, 15, 17société, 1, 6solution, 6, 14–16, 18source, 25sous-système, 22sous-systèmes, 30stable, 30stat, 23, 26stratégie, 5, 7, 8, 10–13, 19–22, 24,

26–30, 47stratégies, 25sub-optimisation, 22, 30, 48suite, 12, 14survivre, 29système, 22, 30

tâche, 4, 47, 48

54

Talion (loi du), 30test, 47Tit-For-Tat, 5, 13, 21, 26, 29, 30titre, 4tournoi, 4, 21, 29traître, 7, 8, 21, 24, 26, 27trahir, 7, 8, 11, 13, 27, 30

variante, 6, 13vie, 15voiture, 6

55