un pour les développeurs Artificielle

45 €

isbn

: 978

-2-4

09-0

1709

-4

L’In

telli

genc

e A

rtifi

ciel

le p

our l

es d

ével

oppe

urs

Java

L’Intelligence Artificielle pour les développeurs Concepts et implémentations en JavaCe livre sur l’Intelligence Artificielle s’adresse particulièrement aux développeurs et ne nécessite pas de connaissances mathématiques approfondies. Au fil des chapitres, l’auteur présente les principales techniques d’Intelligence Artificielle et, pour chacune d’elles, les inspirations biologiques, physiques voire mathématiques, puis les différents concepts et principes (sans entrer dans les détails mathématiques), avec des exemples et figures pour chacun de ceux-ci. Les domaines d’application sont illustrés par des applications réelles et actuelles. Chaque chapitre contient un exemple d’implémentation générique, complété par une application pratique, dé-veloppée en Java. Ces exemples de code étant génériques, ils sont facilement adaptables à de nombreuses applications Java 10, sans plugin extérieur. Les techniques d’Intelligence Artificielle décrites sont :- Les systèmes experts, permettant d’appliquer des règles pour prendre des décisions

ou découvrir de nouvelles connaissances.- La logique floue, permettant de contrôler des systèmes informatiques ou mécaniques

de manière beaucoup plus souple que les programmes traditionnels.- Les algorithmes de recherche de chemin, dont le A* très utilisé dans les jeux vidéo

pour trouver les meilleurs itinéraires.- Les algorithmes génétiques, utilisant la puissance de l’évolution pour apporter des

solutions à des problèmes complexes.- Les principales métaheuristiques, dont la recherche tabou, trouvant des optimums

à des problèmes d’optimisation, avec ou sans contraintes.- Les systèmes multi-agents, simulant des foules ou permettant des comportements

émergents à partir de plusieurs agents très simples.- Les réseaux de neurones (et le deep learning), capables de découvrir et de recon-

naître des modèles, dans des suites historiques, des images ou encore des données.Pour aider le lecteur à passer de la théorie à la pratique, l’auteur propose en téléchar-gement, sur le site www.editions-eni.fr, sept projets Java (réalisés avec NetBeans), un par technique d’Intelligence Artificielle. Chaque projet contient un package générique et un ou plusieurs packages spécifiques à l’application proposée.Le livre se termine par une bibliographie, permettant au lecteur de trouver plus d’informa-tions sur ces différentes techniques, une sitographie listant quelques articles présentant des applications réelles, une annexe et un index.

Virginie MATHIVETAprès un diplôme d’ingénieur INSA et un DEA « Documents, Images et Systèmes d’Informations Communicants », Virginie MATHIVET a fait une thèse de doctorat au sein du laboratoire LIRIS, en Intelligence Artificielle, plus précisément sur les algo-rithmes génétiques et les réseaux de neu-rones. Après avoir enseigné l’Intelligence Artificielle, la robotique et des matières liées au développement pendant plus de 10 ans, elle est aujourd’hui directrice de la R&D chez TeamWork. À travers ce livre, elle partage sa passion pour le domaine de l’Intelligence Artificielle et le met à la portée des développeurs pour qu’ils puissent en exploiter tout le potentiel.

Avant-propos • Introduction • Systèmes experts • Logique floue • Recherche de che-mins • Algorithmes génétiques • Métaheuristiques d’optimisation • Systèmes multi-agents • Réseau de neurones • Sitographie • Annexe

Les chapitres du livre

Téléchargementwww.editions-eni.fr.fr

sur www.editions-eni.fr : b Un projet Java Netbeans par

chapitre, illustrant l’exemple proposé dans le chapitre.

Pour plus d’informations :

Concepts et implémentations en Java

L’Intelligence Artificielle pour les développeurs

Virginie MATHIVET 2e édition

Nouvelle édition

1Table des matières

Avant-propos

1. Objectifs du livre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2. Public et prérequis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3. Structure du livre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4. Code en téléchargement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Introduction

1. Présentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2. Définir l’intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3. L’intelligence du vivant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4. L’intelligence artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Chapitre 1Systèmes experts


2. Exemple : un système expert en polygones . . . . . . . . . . . . . . . . . . . . 302.1 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.2 Quadrilatères. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.3 Autres polygones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Les exemples à télécharger sont disponibles à l'adresse suivante :http://www.editions-eni.fr

Saisissez la référence ENI de l'ouvrage DP2JINT dans la zone de rechercheet validez. Cliquez sur le titre du livre puis sur le bouton de téléchargement.

lcroise

Tampon

2pour les développeurs - Concepts et implémentations en Java

L’Intelligence Artificielle

3. Contenu d'un système expert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.1 Base de règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2 Base de faits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.3 Moteur d'inférences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.4 Interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4. Types d'inférences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.1 Chaînage avant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.1.1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1.2 Application à un exemple . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2 Chaînage arrière . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.2 Application à un exemple . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.3 Chaînage mixte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5. Étapes de construction d'un système . . . . . . . . . . . . . . . . . . . . . . . . . 445.1 Extraction des connaissances. . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.2 Création du moteur d'inférences . . . . . . . . . . . . . . . . . . . . . . . . . 455.3 Écriture des règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.4 Création de l'interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . 46

6. Performance et améliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.1 Critères de performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.2 Amélioration des performances par l'écriture des règles . . . . . . 486.3 Importance de la représentation du problème . . . . . . . . . . . . . . 49

7. Ajout d’incertitudes et de probabilités . . . . . . . . . . . . . . . . . . . . . . . . 517.1 Apport des incertitudes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.2 Faits incertains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.3 Règles incertaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

8. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538.1 Aide au diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548.2 Estimation de risques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.3 Planification et logistique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.4 Transfert de compétences et connaissances . . . . . . . . . . . . . . . . 568.5 Autres applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56


9. Création d'un système expert en Java . . . . . . . . . . . . . . . . . . . . . . . . 579.1 Détermination des besoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589.2 Implémentation des faits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599.3 Base de faits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639.4 Règles et base de règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649.5 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679.6 Moteur d'inférences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699.7 Saisie des règles et utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

10. Utilisation de Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7810.1 Présentation du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7810.2 Syntaxe du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

10.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7910.2.2 Prédicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8010.2.3 Poser des questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8010.2.4 Écriture des règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8110.2.5 Autres prédicats utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

10.3 Codage du problème des formes géométriques . . . . . . . . . . . . . 8310.4 Codage du problème des huit reines . . . . . . . . . . . . . . . . . . . . . . 87

10.4.1 Intérêt du chaînage arrière . . . . . . . . . . . . . . . . . . . . . . . . 8710.4.2 Étude du problème. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8810.4.3 Règles à appliquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8810.4.4 Règles de conflits entre reines. . . . . . . . . . . . . . . . . . . . . . 8910.4.5 But du programme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9110.4.6 Exemples d'utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

11. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92



Chapitre 2Logique floue


2. Incertitude et imprécision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.1 Incertitude et probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.2 Imprécision et subjectivité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.3 Nécessité de traiter l'imprécision. . . . . . . . . . . . . . . . . . . . . . . . . 97

3. Ensembles flous et degrés d’appartenance . . . . . . . . . . . . . . . . . . . . . 983.1 Logique booléenne et logique floue . . . . . . . . . . . . . . . . . . . . . . . 983.2 Fonctions d'appartenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993.3 Caractéristiques d'une fonction d'appartenance. . . . . . . . . . . . 1023.4 Valeurs et variables linguistiques . . . . . . . . . . . . . . . . . . . . . . . 103

4. Opérateurs sur les ensembles flous . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.1 Opérateurs booléens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.2 Opérateurs flous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.2.1 Négation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064.2.2 Union et intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

5. Création de règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.1 Règles en logique booléenne . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.2 Règles floues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

6. Fuzzification et défuzzification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1 Valeur de vérité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.2 Fuzzification et application des règles . . . . . . . . . . . . . . . . . . . 1156.3 Défuzzification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

7. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.1 Premières utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.2 Dans les produits électroniques. . . . . . . . . . . . . . . . . . . . . . . . . 1227.3 En automobile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1227.4 Autres domaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123


8. Implémentation d'un moteur de logique floue . . . . . . . . . . . . . . . . . 1238.1 Le cœur du code : les ensembles flous . . . . . . . . . . . . . . . . . . . 124

8.1.1 Point2D : un point d'une fonction d'appartenance . . . 1248.1.2 EnsembleFlou : un ensemble flou . . . . . . . . . . . . . . . . . 1258.1.3 Opérateurs de comparaison et de multiplication . . . . . 1268.1.4 Opérateurs ensemblistes . . . . . . . . . . . . . . . . . . . . . . . . 1278.1.5 Calcul du barycentre . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

8.2 Ensembles flous particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1388.3 Variables et valeurs linguistiques . . . . . . . . . . . . . . . . . . . . . . . 141

8.3.1 Valeur linguistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1418.3.2 Variable linguistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

8.4 Règles floues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1438.4.1 Expression floue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1448.4.2 Valeur numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1448.4.3 Règle floue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

8.5 Système de contrôle flou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1468.6 Synthèse du code créé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

9. Implémentation d'un cas pratique . . . . . . . . . . . . . . . . . . . . . . . . . . 151

10. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

Chapitre 3Recherche de chemins

1. Présentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

2. Chemins et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1602.1 Définition et concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1602.2 Représentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

2.2.1 Représentation graphique . . . . . . . . . . . . . . . . . . . . . . . . 1612.2.2 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

2.3 Coût d'un chemin et matrice des longueurs . . . . . . . . . . . . . . . 164

3. Exemple en cartographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166



4. Algorithmes naïfs de recherche de chemins . . . . . . . . . . . . . . . . . . . 1684.1 Parcours en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

4.1.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1684.1.2 Application à la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

4.2 Parcours en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1724.2.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1734.2.2 Application à la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

5. Algorithmes "intelligents" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1775.1 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

5.1.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1785.1.2 Application à la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

5.2 Algorithme de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1835.2.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1845.2.2 Application à la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

5.3 Algorithme A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1885.3.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1885.3.2 Application à la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

6. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

7. Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1987.1 Nœuds, arcs et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

7.1.1 Implémentation des nœuds . . . . . . . . . . . . . . . . . . . . . . 1987.1.2 Classe représentant les arcs . . . . . . . . . . . . . . . . . . . . . . 1997.1.3 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

7.2 Fin du programme générique . . . . . . . . . . . . . . . . . . . . . . . . . . 2007.2.1 IHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2007.2.2 Algorithme générique . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

7.3 Implémentation des différents algorithmes . . . . . . . . . . . . . . . 2027.3.1 Recherche en profondeur . . . . . . . . . . . . . . . . . . . . . . . . 2027.3.2 Recherche en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . 2047.3.3 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . 2057.3.4 Algorihme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 2067.3.5 Algorithme A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208


7.4 Application à la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2097.4.1 Gestion des tuiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2097.4.2 Implémentation de la carte . . . . . . . . . . . . . . . . . . . . . . 2117.4.3 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

7.5 Comparaison des performances. . . . . . . . . . . . . . . . . . . . . . . . . 221

8. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

Chapitre 4Algorithmes génétiques


2. Évolution biologique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2262.1 Le concept d'évolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2262.2 Les causes des mutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2272.3 Le support de cette information : les facteurs . . . . . . . . . . . . . 2282.4 Des facteurs au code génétique . . . . . . . . . . . . . . . . . . . . . . . . . 2302.5 Le « cycle de la vie ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

3. Évolution artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2333.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2333.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2343.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

3.3.1 Jeu du Mastermind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2353.3.2 Création de la population initiale. . . . . . . . . . . . . . . . . . 2363.3.3 Fonction d'évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 2373.3.4 Phase de reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 2373.3.5 Survie et enchaînement des générations . . . . . . . . . . . . 2393.3.6 Terminaison de l'algorithme . . . . . . . . . . . . . . . . . . . . . . 239

4. Premières phases de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2404.1 Choix des représentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

4.1.1 Population et individus . . . . . . . . . . . . . . . . . . . . . . . . . . 2404.1.2 Gènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2414.1.3 Cas complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241



4.2 Initialisation de la population initiale . . . . . . . . . . . . . . . . . . . . 2434.3 Évaluation des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

5. Création des générations suivantes . . . . . . . . . . . . . . . . . . . . . . . . . . 2455.1 Sélection des parents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2455.2 Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

5.2.1 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2475.2.2 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

5.3 Survie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2515.4 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

6. Coévolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

7. Domaines d'application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

8. Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2558.1 Implémentation générique d'un algorithme . . . . . . . . . . . . . . . 255

8.1.1 Spécifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2558.1.2 Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2568.1.3 Individus et gènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2588.1.4 IHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2608.1.5 Processus évolutionnaire . . . . . . . . . . . . . . . . . . . . . . . . . 260

8.2 Utilisation pour le voyageur de commerce . . . . . . . . . . . . . . . . 2648.2.1 Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . 2648.2.2 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2658.2.3 Gènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2678.2.4 Individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2688.2.5 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2718.2.6 Résultats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

8.3 Utilisation pour la résolution d'un labyrinthe . . . . . . . . . . . . . 2748.3.1 Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . 2748.3.2 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2758.3.3 Gènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2808.3.4 Individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281


8.3.5 Modification de la fabrique. . . . . . . . . . . . . . . . . . . . . . . 2848.3.6 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2868.3.7 Résultats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

9. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

Chapitre 5Métaheuristiques d'optimisation


2. Optimisation et minimums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2922.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2922.2 Le problème du sac à dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2922.3 Formulation des problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2932.4 Résolution mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2942.5 Recherche exhaustive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2962.6 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296

3. Algorithmes gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

4. Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

5. Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

6. Recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

7. Optimisation par essaims particulaires . . . . . . . . . . . . . . . . . . . . . . . 307

8. Méta-optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

9. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

10. Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31010.1 Classes génériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31110.2 Implémentation des différents algorithmes . . . . . . . . . . . . . . . 312

10.2.1 Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31210.2.2 Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31310.2.3 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31410.2.4 Recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31510.2.5 Optimisation par essaims particulaires . . . . . . . . . . . . . 316



10.3 Résolution du problème du sac à dos . . . . . . . . . . . . . . . . . . . . 31710.3.1 Implémentation du problème . . . . . . . . . . . . . . . . . . . . 31810.3.2 Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32410.3.3 Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32610.3.4 Recherche Tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32710.3.5 Recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32910.3.6 Optimisation par essaims particulaires . . . . . . . . . . . . . 33110.3.7 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

10.4 Résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

11. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

Chapitre 6Systèmes multi-agents


2. Origine biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3442.1 Les abeilles et la danse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3442.2 Les termites et le génie civil . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3462.3 Les fourmis et l'optimisation de chemins . . . . . . . . . . . . . . . . . 3472.4 Intelligence sociale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

3. Systèmes multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3483.1 L'environnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3483.2 Les objets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3493.3 Les agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

4. Classification des agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3504.1 Perception du monde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3504.2 Prise des décisions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3504.3 Coopération et communication . . . . . . . . . . . . . . . . . . . . . . . . 3514.4 Capacités de l'agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352


5. Principaux algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3535.1 Algorithmes de meutes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3535.2 Optimisation par colonie de fourmis . . . . . . . . . . . . . . . . . . . . 3545.3 Systèmes immunitaires artificiels . . . . . . . . . . . . . . . . . . . . . . . 3565.4 Automates cellulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

6. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3596.1 Simulation de foules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3596.2 Planification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3606.3 Phénomènes complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3606.4 Autres domaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

7. Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3617.1 Banc de poissons 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

7.1.1 Les objets du monde et les zones à éviter . . . . . . . . . . . 3627.1.2 Les agents-poissons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3647.1.3 L'océan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3727.1.4 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . 3757.1.5 Résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

7.2 Tri sélectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3817.2.1 Les déchets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3817.2.2 Les agents nettoyeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 3837.2.3 L'environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3887.2.4 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . 3917.2.5 Résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

7.3 Le jeu de la vie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3977.3.1 La grille . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3987.3.2 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . 4017.3.3 Résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

8. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406



Chapitre 7Réseau de neurones


2. Origine biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

3. Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4103.1 Formes d'apprentissage et exemples . . . . . . . . . . . . . . . . . . . . . 410

3.1.1 Apprentissage non supervisé. . . . . . . . . . . . . . . . . . . . . . 4113.1.2 Apprentissage supervisé . . . . . . . . . . . . . . . . . . . . . . . . . 4123.1.3 Apprentissage par renforcement. . . . . . . . . . . . . . . . . . . 414

3.2 Régression et algorithme de régression linéaire . . . . . . . . . . . . 4153.3 Classification et algorithme de séparation . . . . . . . . . . . . . . . . 418

4. Neurone formel et perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4204.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4204.2 Réseaux de type "perceptron" . . . . . . . . . . . . . . . . . . . . . . . . . . 4214.3 Fonctions d'agrégation et d'activation . . . . . . . . . . . . . . . . . . . 423

4.3.1 Fonction d'agrégation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4234.3.2 Fonction d'activation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 424

4.4 Exemple de réseau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4284.5 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

5. Réseaux feed-forward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4315.1 Réseaux avec couche cachée . . . . . . . . . . . . . . . . . . . . . . . . . . . 4315.2 Apprentissage par rétropropagation du gradient . . . . . . . . . . . 4335.3 Surapprentissage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4355.4 Améliorations de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 438

5.4.1 Batch, mini-batch et gradient stochastique. . . . . . . . . . 4385.4.2 Régularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4395.4.3 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4395.4.4 Variation de l'algorithme de descente de gradient. . . . . 4405.4.5 Création de nouvelles données : data augmentation . . 440


6. Autres architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4416.1 Réseaux de neurones à convolution . . . . . . . . . . . . . . . . . . . . . 4416.2 Cartes de Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4426.3 Réseaux de neurones récurrents . . . . . . . . . . . . . . . . . . . . . . . . 4426.4 Réseaux de Hopfield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

7. Domaines d'application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4437.1 Reconnaissance de patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4447.2 Estimation de fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4447.3 Création de comportements . . . . . . . . . . . . . . . . . . . . . . . . . . . 4447.4 Applications actuelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

8. Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4468.1 Points et ensembles de points . . . . . . . . . . . . . . . . . . . . . . . . . . 4468.2 Neurone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4498.3 Réseau de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4518.4 Interface homme-machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4558.5 Système complet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4558.6 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4598.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

8.7.1 Application au XOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4608.7.2 Application à Abalone . . . . . . . . . . . . . . . . . . . . . . . . . . . 4628.7.3 Améliorations possibles. . . . . . . . . . . . . . . . . . . . . . . . . . 464

9. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467



Sitographie

1. Pourquoi une sitographie ?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

2. Systèmes experts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

3. Logique floue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474

4. Recherche de chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477

5. Algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478

6. Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480

7. Systèmes multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481

8. Réseaux de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483

Annexe

1. Installation de SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

2. Utilisation de SWI-Prolog sous Windows. . . . . . . . . . . . . . . . . . . . . 488

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

159

Chapitre 3

Recherche de chemins

Recherche de chemins1. Présentation du chapitre

De nombreux domaines font face à un problème de recherche de chemins,appelé "pathfinding" en anglais. On pense tout d'abord aux GPS et auxlogiciels de recherche d'itinéraires (en voiture, en train, en transport encommun...), voire aux jeux vidéo dans lesquels les ennemis doivent arriver surle joueur par le chemin le plus court.

La recherche de chemins est en réalité un domaine bien plus vaste. En effet, denombreux problèmes peuvent être représentés sous la forme d'un graphe,comme l'enchaînement des mouvements dans un jeu d'échecs.

La recherche d'un chemin dans ce cas-là peut être vue comme la recherche dela suite des mouvements à faire pour gagner.

Ce chapitre commence par présenter les différents concepts de théorie desgraphes, et les définitions associées. Les algorithmes fondamentaux sontensuite présentés, avec leur fonctionnement et leurs contraintes.

Les principaux domaines dans lesquels on peut utiliser cette recherche dechemins sont alors indiqués et un exemple d'implémentation des algorithmesen Java est présenté et appliqué à une recherche de chemins dans un environ-nement en 2D.

Le chapitre se termine par une synthèse.

lcroise

Tampon

© E

dit

ions

EN

I -

All r

ights

rese

rved


L'Intelligence Artificielle

2. Chemins et graphes

Un chemin peut être vu comme un parcours dans un graphe. Les principauxalgorithmes se basent donc sur la théorie des graphes.

2.1 Définition et concepts

Un graphe est un ensemble de nœuds ou sommets (qui peuvent représenterpar exemple des villes) liés par des arcs, qui seraient alors des routes.

Voici un graphe qui représente des gares et les liens qui existent entre ces gares(en train, sans changement) :

Les gares de G1 à G6 sont donc les nœuds. L'arc allant de G5 à G6 indique laprésence d'un lien direct entre ces deux gares. Il est noté (G5, G6) ou (G6, G5)selon le sens voulu.

Par contre pour aller de G1 à G6, il n'y a pas de lien direct, il faudra passer parG4 ou G5 si on ne souhaite qu'un changement, ou par G2 puis G3 avec deuxchangements.

Un chemin permet de rejoindre différents sommets liés entre eux par des arcs.Ainsi, G1-G2-G3-G6 est un chemin de longueur 3 (la longueur est le nombred'arcs suivis).

161Recherche de cheminsChapitre 3

On parle de circuit lorsqu'on peut partir d'un nœud et y revenir. Ici, le graphecontient de nombreux circuits, comme G1-G4-G5-G1 ou G4-G5-G6-G4.

L'ordre d'un graphe correspond au nombre de sommets qu'il contient. Notreexemple contient 6 gares, il s'agit donc d'un graphe d'ordre 6.

Deux nœuds sont dits adjacents (ou voisins) s'il existe un lien permettantd'aller de l'un à l'autre. G5 est donc adjacent à G1, G4 et G6.

2.2 Représentations

2.2.1 Représentation graphique

Il existe plusieurs façons de représenter un graphe. La première est la repré-sentation graphique, comme celle vue précédemment.

L'ordre et le placement des nœuds ne sont pas importants, cependant on vachercher à toujours placer les sommets de façon à rendre le graphe le pluslisible possible.

Le graphe est dit orienté si les arcs ont un sens, représentant par exemple desrues à sens unique dans une ville. Si tous les arcs peuvent être pris dans lesdeux sens, on dit alors que le graphe est non orienté, ce qui est généralementle cas de ceux utilisés pour la recherche de chemins.

2.2.2 Matrice d’adjacence

Les représentations graphiques ne sont pas toujours très pratiques, en particu-lier quand il s'agit d'y appliquer des algorithmes ou de les rentrer dans unordinateur.

On préfère souvent utiliser une matrice, appelée matrice d'adjacence.

Remarque

Une matrice est une structure mathématique particulière qui peut être vueplus simplement comme un tableau à deux dimensions.

Dans cette matrice, l'absence d'arc est représentée par un 0, et sa présence parun 1.

© E

dit

ions

EN

I -

All r

ights

rese

rved



Dans l'exemple des gares, on a donc une matrice de 6 par 6 (car il y a 6 gares) :

On voit sur le graphe qu'il existe un lien entre G1 et G4. La case correspondantau trajet de G1 vers G4 contient donc un 1, tout comme celle de G4 à G1 (letrajet est à double sens). On a alors la matrice suivante :

163Recherche de cheminsChapitre 3

De même, il existe un arc de G1 vers G2 et G5 mais pas vers G3 ou G6. Onpeut donc compléter notre matrice :

On fait de même pour tous les autres nœuds et les autres arcs :

© E

dit

ions

EN

I -

All r

ights

rese

rved



Il ne reste que la diagonale. Elle représente la possibilité d'aller d'un nœud à lui-même, c'est ce qu'on appelle une boucle. Ici il n'y a pas de trajet direct allantd'une gare à elle-même, on remplit donc par des 0 cette diagonale.

La matrice d'adjacence est alors complète.

2.3 Coût d'un chemin et matrice des longueurs

Dans le cadre de la recherche du chemin le plus court, le moins cher ou le plusrapide, on doit rajouter des informations. Celles-ci sont appelées de manièrearbitraire longueurs, sans préciser l'unité. Il peut donc s'agir de kilomètres,d'euros, de minutes, de kilos...