Virginie MATHIVET C# pour les développeurs … · · Les algorithmes de recherche de chemin, dont le A* très utilisé dans les jeux vidéo pour trouver les meilleurs itinéraires

45

isbn

: 978

-2-4

09-0

1140

-5

LIn

telli

genc

e A

rtifi

ciel

le p

our l

es d

vel

oppe

urs

C#

LIntelligence Artificielle pour les dveloppeurs Concepts et implmentations en C#Ce livre sur lIntelligence Artificielle sadresse particulirement aux dveloppeurs et ne ncessite pas de connaissances mathmatiques approfondies. Au fil des chapitres, lauteur prsente les principales techniques dIntelligence Artificielle et, pour cha-cune delles, les inspirations biologiques, physiques voire mathmatiques, puis les diff-rents concepts et principes (sans entrer dans les dtails mathmatiques), avec des exemples et figures pour chacun de ceux-ci. Les domaines dapplication sont illustrs par des applications relles et actuelles. Chaque chapitre contient un exemple dimplmentation gnrique, complt par une application pratique, dvelop-pe en C#. Ces exemples de code tant gnriques, ils sont facilement adaptables de nombreuses applications C#, que ce soit dans des applications .NET classiques, pour ASP.NET, ou encore des applications Windows (versions 8 et 10). Les techniques dIntelli-gence Artificielle dcrites sont : Les systmes experts, permettant dappliquer des rgles pour prendre des dcisions

ou dcouvrir de nouvelles connaissances. La logique floue, permettant de contrler des systmes informatiques ou mcaniques

de manire beaucoup plus souple que les programmes traditionnels. Les algorithmes de recherche de chemin, dont le A* trs utilis dans les jeux vido

pour trouver les meilleurs itinraires. Les algorithmes gntiques, utilisant la puissance de lvolution pour apporter des

solutions des problmes complexes. Les principales mtaheuristiques, dont la recherche tabou, trouvant des optimums

des problmes doptimisation, avec ou sans contraintes. Les systmes multi-agents, simulant des foules ou permettant des comportements

mergents partir de plusieurs agents trs simples. Les rseaux de neurones (ou deep learning), capables de dcouvrir et de recon-

natre des modles, dans des suites historiques, des images ou encore des donnes.Pour aider le lecteur passer de la thorie la pratique, lauteur propose en tlchar-gement sur le site www.editions-eni.fr, sept projets Visual Studio 2017 (un par technique dIntelligence Artificielle), dvelopps en C#. Chaque projet contient une PCL, pour la partie gnrique, et une application (en mode console ou WPF selon les chapitres) pour la partie spcifique lapplication propose. Le livre se termine par une bibliographie permettant au lecteur de trouver plus dinforma-tions sur ces diffrentes techniques, une sitographie listant quelques articles prsentant des applications relles, une annexe et un index.

Virginie MATHIVETAprs un diplme dingnieur INSA et un DEA "Documents, Images et Systmes dInformations Communicants", Virginie MATHIVET a fait une thse de doctorat au sein du laboratoire LIRIS, en Intelligence Artificielle, plus prcisment sur les algorithmes gntiques et les rseaux de neurones. Aprs avoir enseign lintelligence artificielle, la robo-tique et des matires lies au dveloppement pendant plus de 10 ans, elle est aujourdhui charge de R&D chez TeamWork SI. A travers ce livre, elle partage sa passion pour le domaine de lIntelligence Artificielle et le met la porte des dveloppeurs pour quils puissent en exploiter tout le potentiel.

Avant-propos Introduction Systmes experts Logique floue Recherche de chemins Algorithmes gntiques Mtaheuristiques doptimisation Systmes multi-agents Rseau de neurones Bibliographie Sitographie Annexe

Les chapitres du livre

Tlchargementwww.editions-eni.fr.fr

sur www.editions-eni.fr : b un projet Visual Studio par

chapitre, contenant la PCL et lapplication illustrant lexemple propos dans le chapitre.

Pour plus dinformations :

Virginie MATHIVET

Concepts et implmentations en C#

LIntelligence Artificielle pour les dveloppeurs

2e dition

Nouvelle dition

1Table des matires

Avant-propos

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

2. Public et prrequis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

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

4. Code en tlchargement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Introduction

1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Les exemples tlcharger sont disponibles l'adresse suivante :http://www.editions-eni.fr

Saisissez la rfrence ENI de l'ouvrage DP2INT dans la zone de rechercheet validez. Cliquez sur le titre du livre puis sur le bouton de tlchargement.

2. Dfinir lintelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3. Lintelligence du vivant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4. Lintelligence artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Chapitre 1

Systmes experts


2. Exemple : un systme expert en polygones . . . . . . . . . . . . . . . . . . . . 302.1 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.2 Quadrilatres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.3 Autres polygones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

lcroiseTampon

2

pour les dveloppeurs - Concepts et implmentations en C#

L'Intelligence Artificielle

3. Contenu d'un systme expert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.1 Base de rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2 Base de faits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.3 Moteur d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.4 Interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4. Types d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1 Chanage avant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.1.1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1.2 Application un exemple . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2 Chanage arrire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.2 Application un exemple . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.3 Chanage mixte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5. tapes de construction d'un systme . . . . . . . . . . . . . . . . . . . . . . . . . 455.1 Extraction des connaissances. . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.2 Cration du moteur d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . 465.3 criture des rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.4 Cration de l'interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . 47

6. Performance et amliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.1 Critres de performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.2 Amlioration des performances par l'criture des rgles . . . . . . 496.3 Importance de la reprsentation du problme . . . . . . . . . . . . . . 50

7. Ajout dincertitudes et de probabilits . . . . . . . . . . . . . . . . . . . . . . . . 527.1 Apport des incertitudes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.2 Faits incertains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537.3 Rgles incertaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

8. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.1 Aide au diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558.2 Estimation de risques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568.3 Planification et logistique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568.4 Transfert de comptences et connaissances . . . . . . . . . . . . . . . . 578.5 Autres applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3Table des matires

9. Cration dun systme expert en C# . . . . . . . . . . . . . . . . . . . . . . . . . 589.1 Dtermination des besoins. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599.2 Implmentation des faits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609.3 Base de faits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649.4 Rgles et base de rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659.5 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679.6 Moteur d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699.7 Saisie des rgles et utilisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

10. Utilisation de Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7910.1 Prsentation du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7910.2 Syntaxe du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

10.2.1 Gnralits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8010.2.2 Prdicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8010.2.3 Poser des questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8110.2.4 criture des rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8210.2.5 Autres prdicats utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

10.3 Codage du problme des formes gomtriques . . . . . . . . . . . . . 8310.4 Codage du problme des huit reines . . . . . . . . . . . . . . . . . . . . . . 88

10.4.1 Intrt du chanage arrire . . . . . . . . . . . . . . . . . . . . . . . . 8810.4.2 tude du problme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8810.4.3 Rgles appliquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8910.4.4 Rgles de conflits entre reines. . . . . . . . . . . . . . . . . . . . . . 9010.4.5 But du programme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9210.4.6 Exemples d'utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

11. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4



Chapitre 2

Logique floue


2. Incertitude et imprcision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.1 Incertitude et probabilits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.2 Imprcision et subjectivit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.3 Ncessit de traiter l'imprcision. . . . . . . . . . . . . . . . . . . . . . . . . 97

3. Ensembles flous et degrs dappartenance . . . . . . . . . . . . . . . . . . . . . 983.1 Logique boolenne et logique floue . . . . . . . . . . . . . . . . . . . . . . . 983.2 Fonctions d'appartenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993.3 Caractristiques d'une fonction d'appartenance. . . . . . . . . . . . 1023.4 Valeurs et variables linguistiques . . . . . . . . . . . . . . . . . . . . . . . 103

4. Oprateurs sur les ensembles flous . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.1 Oprateurs boolens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.2 Oprateurs flous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.2.1 Ngation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064.2.2 Union et intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

5. Cration de rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.1 Rgles en logique boolenne . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.2 Rgles floues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

6. Fuzzification et dfuzzification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1 Valeur de vrit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.2 Fuzzification et application des rgles . . . . . . . . . . . . . . . . . . . 1156.3 Dfuzzification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

7. Domaines dapplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.1 Premire utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.2 Dans les produits lectroniques. . . . . . . . . . . . . . . . . . . . . . . . . 1227.3 En automobile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1227.4 Autres domaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

5Table des matires

8. Implmentation dun moteur de logique floue. . . . . . . . . . . . . . . . . 1248.1 Le cur du code : les ensembles flous . . . . . . . . . . . . . . . . . . . . 124

8.1.1 Point2D : un point d'une fonction d'appartenance . . . . 1248.1.2 FuzzySet : un ensemble flou. . . . . . . . . . . . . . . . . . . . . . 1258.1.3 Oprateurs de comparaison et de multiplication . . . . . 1278.1.4 Oprateurs ensemblistes . . . . . . . . . . . . . . . . . . . . . . . . . 1278.1.5 Calcul du barycentre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

8.2 Ensembles flous particuliers. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1418.3 Variables et valeurs linguistiques . . . . . . . . . . . . . . . . . . . . . . . 143

8.3.1 LinguisticValue : valeur linguistique . . . . . . . . . . . . . . . 1438.3.2 LinguisticVariable : variable linguistique . . . . . . . . . . . . 144

8.4 Rgles floues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1468.4.1 FuzzyExpression : expression floue . . . . . . . . . . . . . . . . 1468.4.2 FuzzyValue : valeur floue . . . . . . . . . . . . . . . . . . . . . . . . 1468.4.3 FuzzyRule : rgle floue . . . . . . . . . . . . . . . . . . . . . . . . . . 147

8.5 Systme de contrle flou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1508.6 Synthse du code cr. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

9. Implmentation dun cas pratique . . . . . . . . . . . . . . . . . . . . . . . . . . 154

10. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

Chapitre 3

Recherche de chemins

1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

2. Chemins et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1622.1 Dfinition et concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1622.2 Reprsentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

2.2.1 Reprsentation graphique . . . . . . . . . . . . . . . . . . . . . . . . 1632.2.2 Matrice dadjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

2.3 Cot d'un chemin et matrice des longueurs . . . . . . . . . . . . . . . 167

3. Exemple en cartographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

6



4. Algorithmes nafs de recherche de chemins . . . . . . . . . . . . . . . . . . . 1704.1 Parcours en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

4.1.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1704.1.2 Application la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

4.2 Parcours en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1754.2.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1764.2.2 Application la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

5. Algorithmes "intelligents" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1805.1 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

5.1.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1815.1.2 Application la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

5.2 Algorithme de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1875.2.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1875.2.2 Application la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

5.3 Algorithme A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1915.3.1 Principe et pseudo-code. . . . . . . . . . . . . . . . . . . . . . . . . . 1915.3.2 Application la carte. . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

6. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

7. Implmentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2027.1 Nuds, arcs et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

7.1.1 Implmentation des nuds . . . . . . . . . . . . . . . . . . . . . . 2037.1.2 Classe reprsentant les arcs. . . . . . . . . . . . . . . . . . . . . . . 2047.1.3 Interface des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

7.2 Fin du programme gnrique . . . . . . . . . . . . . . . . . . . . . . . . . . . 2067.2.1 IHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2067.2.2 Algorithme gnrique . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

7.3 Codage des diffrents algorithmes . . . . . . . . . . . . . . . . . . . . . . 2077.3.1 Recherche en profondeur . . . . . . . . . . . . . . . . . . . . . . . . 2077.3.2 Recherche en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2097.3.3 Algorithme de Bellman-Ford. . . . . . . . . . . . . . . . . . . . . . 2117.3.4 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 2127.3.5 Algorithme A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

7Table des matires

7.4 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2167.4.1 Tile et Tiletype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2167.4.2 Implmentation de la carte. . . . . . . . . . . . . . . . . . . . . . . 2197.4.3 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

7.5 Comparaison des performances. . . . . . . . . . . . . . . . . . . . . . . . . 229

8. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

Chapitre 4

Algorithmes gntiques


2. volution biologique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2342.1 Le concept d'volution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2342.2 Les causes des mutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2352.3 Le support de cette information : les facteurs . . . . . . . . . . . . . 2362.4 Des facteurs au code gntique . . . . . . . . . . . . . . . . . . . . . . . . . 2392.5 Le cycle de la vie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

3. volution artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

3.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2423.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2433.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

3.3.1 Jeu du Mastermind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2433.3.2 Cration de la population initiale. . . . . . . . . . . . . . . . . . 2453.3.3 Fonction d'valuation . . . . . . . . . . . . . . . . . . . . . . . . . . . 2453.3.4 Phase de reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 2463.3.5 Survie et enchanement des gnrations . . . . . . . . . . . . 2483.3.6 Terminaison de l'algorithme . . . . . . . . . . . . . . . . . . . . . . 249

4. Premires phases de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2494.1 Choix des reprsentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

4.1.1 Population et individus . . . . . . . . . . . . . . . . . . . . . . . . . . 2494.1.2 Gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2504.1.3 Cas complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

8



4.2 Initialisation de la population initiale . . . . . . . . . . . . . . . . . . . . 2524.3 valuation des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

5. Cration des gnrations suivantes . . . . . . . . . . . . . . . . . . . . . . . . . . 2545.1 Slection des parents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2555.2 Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

5.2.1 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2565.2.2 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

5.3 Survie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2605.4 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

6. Covolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

7. Domaines d'application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

8. Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2648.1 Implmentation gnrique d'un algorithme . . . . . . . . . . . . . . . 265

8.1.1 Spcifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2658.1.2 Paramtres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2668.1.3 Individus et gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2678.1.4 IHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

8.1.5 Processus volutionnaire . . . . . . . . . . . . . . . . . . . . . . . . . 270

8.2 Utilisation pour le voyageur de commerce . . . . . . . . . . . . . . . . 2758.2.1 Prsentation du problme . . . . . . . . . . . . . . . . . . . . . . . . 2758.2.2 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2768.2.3 Gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2798.2.4 Individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2808.2.5 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2848.2.6 Rsultats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.3 Utilisation pour la rsolution d'un labyrinthe . . . . . . . . . . . . . 2868.3.1 Prsentation du problme . . . . . . . . . . . . . . . . . . . . . . . . 2868.3.2 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2888.3.3 Gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2948.3.4 Individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2968.3.5 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . 3008.3.6 Rsultats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

9Table des matires

9. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

Chapitre 5

Mtaheuristiques d'optimisation


2. Optimisation et minimums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3062.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3062.2 Le problme du sac dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3062.3 Formulation des problmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3082.4 Rsolution mathmatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3092.5 Recherche exhaustive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3102.6 Mtaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

3. Algorithmes gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

4. Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

5. Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

6. Recuit simul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

7. Optimisation par essaims particulaires . . . . . . . . . . . . . . . . . . . . . . . 320

8. Mta-optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

9. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

10. Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32410.1 Classes gnriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32410.2 Implmentation des diffrents algorithmes . . . . . . . . . . . . . . . 326

10.2.1 Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32610.2.2 Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32710.2.3 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32810.2.4 Recuit simul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32910.2.5 Optimisation par essaims particulaires . . . . . . . . . . . . . 331

10.3 Rsolution du problme du sac dos . . . . . . . . . . . . . . . . . . . . 33210.3.1 Implmentation du problme. . . . . . . . . . . . . . . . . . . . . 33210.3.2 Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

10



10.3.3 Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34110.3.4 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34210.3.5 Recuit simul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34510.3.6 Optimisation par essaims particulaires . . . . . . . . . . . . . 34710.3.7 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

10.4 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

11. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

Chapitre 6

Systmes multi-agents


2. Origine biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3602.1 Les abeilles et la danse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3602.2 Les termites et le gnie civil . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3622.3 Les fourmis et l'optimisation de chemins . . . . . . . . . . . . . . . . . 3632.4 Intelligence sociale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

3. Systmes multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

3.1 L'environnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3643.2 Les objets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3653.3 Les agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

4. Classification des agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3664.1 Perception du monde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3664.2 Prise des dcisions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3664.3 Coopration et communication . . . . . . . . . . . . . . . . . . . . . . . . 3674.4 Capacits de l'agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

5. Principaux algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3695.1 Algorithmes de meutes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3695.2 Optimisation par colonie de fourmis . . . . . . . . . . . . . . . . . . . . 3705.3 Systmes immunitaires artificiels . . . . . . . . . . . . . . . . . . . . . . . 3725.4 Automates cellulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

1
1Table des matires
6. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3756.1 Simulation de foules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3756.2 Planification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3766.3 Phnomnes complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3766.4 Autres domaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

7. Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3777.1 Banc de poissons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378

7.1.1 Les objets du monde et les zones viter . . . . . . . . . . . 3787.1.2 Les agents-poissons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3807.1.3 L'ocan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3897.1.4 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . 3927.1.5 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

7.2 Tri slectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3987.2.1 Les dchets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3987.2.2 Les agents nettoyeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 4017.2.3 L'environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4067.2.4 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . 4097.2.5 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413

7.3 Le jeu de la vie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4157.3.1 La grille . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4157.3.2 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . 4187.3.3 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422

8. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

Chapitre 7

Rseaux de neurones


2. Origine biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426

3. Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4283.1 Formes d'apprentissage et exemples . . . . . . . . . . . . . . . . . . . . . 428

3.1.1 Apprentissage non supervis. . . . . . . . . . . . . . . . . . . . . . 429

12



3.1.2 Apprentissage supervis . . . . . . . . . . . . . . . . . . . . . . . . . 4303.1.3 Apprentissage par renforcement. . . . . . . . . . . . . . . . . . . 432

3.2 Rgression et algorithme de rgression linaire . . . . . . . . . . . . 4333.3 Classification et algorithme de rgression logistique . . . . . . . . 436

4. Neurone formel et perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4384.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4384.2 Rseaux de type "perceptron" . . . . . . . . . . . . . . . . . . . . . . . . . . 4394.3 Fonctions d'agrgation et d'activation . . . . . . . . . . . . . . . . . . . 441

4.3.1 Fonction d'agrgation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4414.3.2 Fonction d'activation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

4.4 Exemple de rseau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4464.5 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

5. Rseaux feed-forward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4495.1 Rseaux avec couche cache . . . . . . . . . . . . . . . . . . . . . . . . . . . 4505.2 Apprentissage par rtropropagation du gradient . . . . . . . . . . . 4515.3 Surapprentissage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4545.4 Amliorations de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 456

5.4.1 Batch, mini-batch et gradient stochastique. . . . . . . . . . 456

5.4.2 Rgularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4575.4.3 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4575.4.4 Variation de l'algorithme de descente de gradient. . . . . 4585.4.5 Cration de nouvelles donnes . . . . . . . . . . . . . . . . . . . . 458

6. Autres architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4596.1 Rseaux de neurones convolution . . . . . . . . . . . . . . . . . . . . . 4596.2 Cartes de Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4606.3 Rseaux de neurones rcurrents . . . . . . . . . . . . . . . . . . . . . . . . 4606.4 Rseaux de Hopfield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461

7. Domaines d'application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4617.1 Reconnaissance de patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4627.2 Estimation de fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4627.3 Cration de comportements . . . . . . . . . . . . . . . . . . . . . . . . . . . 4627.4 Applications actuelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463

3
1Table des matires
8. Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4648.1 Points et ensembles de points . . . . . . . . . . . . . . . . . . . . . . . . . . 4648.2 Neurone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4688.3 Rseau de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4718.4 Interface Homme-Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4758.5 Systme complet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4768.6 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4808.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482

8.7.1 Application au XOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4828.7.2 Application Abalone . . . . . . . . . . . . . . . . . . . . . . . . . . . 4848.7.3 Amliorations possibles. . . . . . . . . . . . . . . . . . . . . . . . . . 486

9. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

Bibliographie

1. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489

Sitographie

1. Pourquoi une sitographie ?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

2. Systmes experts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

3. Logique floue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497

4. Recherche de chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499

5. Algorithmes gntiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500

6. Mtaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502

7. Systmes multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503

8. Rseaux de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505

14



Annexe

1. Installation de SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

2. Utilisation de SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513

61
1
Chapitre 3

Recherche de chemins

Recherche de chemins1. Prsentation du chapitre

De nombreux domaines font face un problme de recherche de chemins,appel pathfinding en anglais. On pense tout d'abord aux GPS et aux logicielsde recherche d'itinraires (en voiture, en train, en transport en commun...),voire aux jeux vido dans lesquels les ennemis doivent arriver sur le joueur par

le chemin le plus court.

La recherche de chemins est en ralit un domaine bien plus vaste. En effet, denombreux problmes peuvent tre reprsents sous la forme d'un graphe,comme l'enchanement des mouvements dans un jeu d'checs.

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

Ce chapitre commence par prsenter les diffrents concepts de thorie desgraphes, et les dfinitions associes. Les algorithmes fondamentaux sontensuite prsents, avec leur fonctionnement et leurs contraintes.

Les principaux domaines dans lesquels on peut utiliser cette recherche de che-mins sont alors indiqus et un exemple d'implmentation des algorithmes enC# est prsent et appliqu une recherche de chemins dans un environne-ment en 2D.

Le chapitre se termine par une synthse.

lcroiseTampon

162pour les dveloppeurs - Concepts et implmentations en C#


2. Chemins et graphes

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

2.1 Dfinition et concepts

Un graphe est un ensemble de nuds ou sommets (qui peuvent reprsenterpar exemple des villes) lis par des arcs, qui seraient alors des routes.

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

E

dit

ions

EN

I -

All r

ights

rese

rved

Les gares de G1 G6 sont donc les nuds. L'arc allant de G5 G6 indique laprsence 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.

63
1Recherche de cheminsChapitre 3
Un chemin permet de rejoindre diffrents sommets lis entre eux par des arcs.Ainsi, G1-G2-G3-G6 est un chemin de longueur 3 (la longueur est le nombred'arcs suivis).

On parle de circuit lorsqu'on peut partir d'un nud 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 nuds 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 Reprsentations

2.2.1 Reprsentation graphique

Il existe plusieurs faons de reprsenter un graphe. La premire est la repr-sentation graphique, comme celle vue prcdemment.

L'ordre et le placement des nuds ne sont pas importants, cependant on vachercher toujours placer les sommets de faon rendre le graphe le plus

lisible possible.

Le graphe est dit orient si les arcs ont un sens, reprsentant 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 gnralementle cas de ceux utiliss pour la recherche de chemins.

2.2.2 Matrice dadjacence

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

On prfre souvent utiliser une matrice, appele matrice d'adjacence.



Remarque

Une matrice est une structure mathmatique particulire qui peut tre vueplus simplement comme un tableau deux dimensions.

Dans cette matrice, l'absence d'arc est reprsente par un 0, et sa prsence parun 1.

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

E

dit

ions

EN

I -

All r

ights

rese

rved

65
1Recherche de cheminsChapitre 3
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 :

De mme, il existe un arc de G1 vers G2 et G5 mais pas vers G3 ou G6. On

peut donc complter notre matrice :



On fait de mme pour tous les autres nuds et les autres arcs :

Il ne reste que la diagonale. Elle reprsente la possibilit d'aller d'un nud lui-mme, c'est ce qu'on appelle une boucle. Ici il n'y a pas de trajet direct allant

E

dit

ions

EN

I -

All r

ights

rese

rved

d'une gare elle-mme, on remplit donc par des 0 cette diagonale.

DP2INT_T.pdfCopyright - Editions ENI - Dcembre 2017ISBN : 978-2-409-01140-5Imprim en FranceLes exemples tlcharger sont disponibles l'adresse suivante : http://www.editions-eni.fr Saisissez la rfrence ENI de l'ouvrage DP2INT dans la zone de recherche et validez. Cliquez sur le titre du livre puis sur le bouton de tlchargementAvant-proposIntroductionSystmes expertsLogique floueRecherche de cheminsAlgorithmes gntiquesMtaheuristiques d'optimisationSystmes multi-agentsRseaux de neuronesBibliographieSitographieAnnexe

Avant-proposAvant-proposL'Intelligence Artificielle1. Objectifs du livre1. Objectifs du livreL'intelligence artificielle ou I.A. est un domaine qui passionne les amateurs de science-fiction. Cependant, dans notre monde actuel, de nombreux dveloppeurs n'utilisent pas les techniques associes, par manque de connaissances de celles-ci.Ce livre prsente donc les principales techniques d'intelligence artificielle, en commenant par les concepts principaux comprendre, puis en donnant des exemples de code en C#.

2. Public et prrequis2. Public et prrequisCe livre s'adresse tous ceux qui souhaitent dcouvrir l'intelligence artificielle. Chaque chapitre dtaille une technique.Aucun prrequis en mathmatiques n'est requis, les formules et quations ayant t limites au strict minimum. En effet, ce livre est surtout orient sur les concepts et les principes sous-jacents aux diffrentes techniques.La deuxime partie de chaque chapitre prsente des exemples de code en C#. Une connaissance du langage, au moins basique, est ncessaire. Ce livre est donc surtout destin aux dveloppeurs, en particulier : Les Les Les tudiants en cole post-bac

Les Les dveloppeurs

Les Les passionns

Tout Tout curieux

3. Structure du livre3. Structure du livreCe livre commence par une introduction

Le livre contient ensuite sept chapitres. Chacun d'eux porte sur une technique ou un ensemble de techniques. l'intrieur de ceux-ci, on trouve tout d'abord l'explication des principes et des concepts. Ensuite suivent des exemples d'application de...Le lecteur curieux ou voulant apprendre plusieurs techniques pourra lire le livre dans l'ordre. Sinon, le lecteur cherchant des informations sur une technique particulire pourra aller directement au chapitre la concernant, ceux-ci tant indpendantsLe premier chapitre prsente les systmes experts

Le deuxime chapitre s'intresse la logique floue

Le troisime chapitre porte sur la recherche de chemins

Le quatrime chapitre concerne les algorithmes gntiques

Le cinquime chapitre prsente plusieurs mtaheuristiques d'optimisation

Le sixime chapitre s'intresse aux systmes multi-agents

Le dernier chapitre concerne les rseaux de neuronesmachine learningdeeplearning

la fin de ce livre se trouvent : Une Une Une bibliographie

Une Une sitographie

Une Une annexe

Un Un index

4. Code en tlchargement4. Code en tlchargementLe code des diffrents chapitres est propos en tlchargement sur le site de l'diteur. Une solution

Pour ouvrir ces solutions, il est possible de tlcharger une version gratuite de Visual Studiohttps://www.visualstudio.com/fr/downloads/

Dans chacune de ces solutions, la majorit du code (au moins toutes les classes au cur des algorithmes) a t code dans des bibliothques de classes portables

Les classes permettant la liaison avec l'utilisateur, en entre ou en sortie, sont stockes dans un projet Windows de type consoleWindows Presentation Foundation

Les variables et mthodes sont nommes en anglais

La visibilitModel View ViewModel

De mme, les algorithmes prsents n'ont pas t optimiss lorsque ces optimisations allaient l'encontre de la facilit de lecture du code.Bonne lecture tous !

IntroductionIntroductionL'Intelligence Artificielle1. Prsentation du chapitre1. Prsentation du chapitreLintelligence artificielleintelligence

Cette introduction s'intresse d'abord lintelligence chez les humains et la faon de la dfinir. Ensuite il est expliqu comment cette dfinition peut sappliquer dautres formes de vie, que ce soient les animaux ou les vgtau...Une fois pos le fait que lintelligence peut se trouver en tout tre vivant, nous verrons comment dfinir lintelligence artificielle, ainsi que les grands courants de pense que lon y retrouve. Enfin, cette introduction se termine par un...

2. Dfinir lintelligence2. Dfinir lintelligenceIl est important de comprendre tout dabord ce quest lintelligence

Le terme dintelligence vient du latin intelligentia qui signifie la facult de comprendre et de mettre en relation des lments entre eux.Lintelligence est cependant multiple, et tous les auteurs actuels saccordent sur le fait quil ny a pas une mais des intelligences, et que chacun dentre nous peut prsenter des forces et/ou des faiblesses dans les diffrentes formes d... Lintelligence logico-mathmatique : capacit travailler laide de chiffres, analyser des situations, mettre au point des raisonnements. Elle est mise en avant chez les scientifiques, en particulier en physique et mathmatiques. Lintelligence logico-mathmatique : capacit travailler laide de chiffres, analyser des situations, mettre au point des raisonnements. Elle est mise en avant chez les scientifiques, en particulier en physique et mathmatiques. Lintelligence logico-mathmatique : capacit travailler laide de chiffres, analyser des situations, mettre au point des raisonnements. Elle est mise en avant chez les scientifiques, en particulier en physique et mathmatiques. Lintelligence logico-mathmatique

Lintelligence visuo-spatiale : capacit se reprsenter un objet ou un environnement en 3D, utilise pour suivre une carte, se rappeler un chemin ou imaginer ce que donne une forme dans lespace partir de son plan. Elle est ncessaire Lintelligence visuo-spatiale : capacit se reprsenter un objet ou un environnement en 3D, utilise pour suivre une carte, se rappeler un chemin ou imaginer ce que donne une forme dans lespace partir de son plan. Elle est ncessaire Lintelligence visuo-spatiale

Lintelligence verbo-linguistique : capacit comprendre et noncer des ides par le langage. Elle requiert une bonne connaissance et matrise du vocabulaire, ainsi que de la syntaxe et des figures de style. Elle aide les avocats, les pol Lintelligence verbo-linguistique : capacit comprendre et noncer des ides par le langage. Elle requiert une bonne connaissance et matrise du vocabulaire, ainsi que de la syntaxe et des figures de style. Elle aide les avocats, les pol Lintelligence verbo-linguistique

Lintelligence intrapersonnelle : capacit avoir une image fidle de soi, ce qui signifie pouvoir dterminer son tat motionnel, ses envies, ses forces et ses faiblesses. Lintelligence intrapersonnelle : capacit avoir une image fidle de soi, ce qui signifie pouvoir dterminer son tat motionnel, ses envies, ses forces et ses faiblesses. Lintelligence intrapersonnelle

Lintelligence interpersonnelle : capacit comprendre les autres et ragir de la faon adquate. Elle est donc lie la notion dempathie, la tolrance, la sociabilit. Mais elle peut aussi permettre de manipuler et est ains Lintelligence interpersonnelle : capacit comprendre les autres et ragir de la faon adquate. Elle est donc lie la notion dempathie, la tolrance, la sociabilit. Mais elle peut aussi permettre de manipuler et est ains Lintelligence interpersonnelle

Lintelligence corporelle/kinesthsique : capacit avoir une reprsentation mentale de son corps dans lespace et pouvoir mener un mouvement particulier. Trs utilise chez les athltes, cest elle qui permet davoir le bon geste Lintelligence corporelle/kinesthsique : capacit avoir une reprsentation mentale de son corps dans lespace et pouvoir mener un mouvement particulier. Trs utilise chez les athltes, cest elle qui permet davoir le bon geste Lintelligence corporelle/kinesthsique

Lintelligence naturaliste : capacit trier, organiser et hirarchiser les objets qui nous entourent. Elle permet ainsi de dfinir des espces, des sous- espces, ou de construire des classifications. Elle est par exemple trs utilise p Lintelligence naturaliste : capacit trier, organiser et hirarchiser les objets qui nous entourent. Elle permet ainsi de dfinir des espces, des sous- espces, ou de construire des classifications. Elle est par exemple trs utilise p Lintelligence naturaliste

Lintelligence musicale : capacit reconnatre les mlodies, les notes et les harmonies, ou les crer. Elle est ainsi ncessaire aux compositeurs et aux chanteurs et sexprime chez tous les mlomanes. Lintelligence musicale : capacit reconnatre les mlodies, les notes et les harmonies, ou les crer. Elle est ainsi ncessaire aux compositeurs et aux chanteurs et sexprime chez tous les mlomanes. Lintelligence musicale

Lintelligence existentielle ou spirituelle : capacit se poser des questions sur le sens de la vie, sur notre but. Elle se rapproche de notre notion de moralit. Elle nest pas forcment lie la notion de religion mais plus notre p Lintelligence existentielle ou spirituelle : capacit se poser des questions sur le sens de la vie, sur notre but. Elle se rapproche de notre notion de moralit. Elle nest pas forcment lie la notion de religion mais plus notre p Lintelligence existentielle ou spirituelle

De nombreux tests ont essay de mesurer lintelligence, le plus connu tant le test de Q.I.

De plus, les principaux tests de Q.I. que lon trouve sont biaiss par lexprience : il suffit de faire et refaire plusieurs fois des entranements sur ces tests pour obtenir des rsultats significativement amliors. Pour autant, est- on ...Le systme scolaire lui-mme met principalement en avant ces trois formes dintelligence (logico-mathmatique, visuo-spatiale et verbo-linguisitique). Les autres formes d'intelligence sont dlaisses, et tudies dans les matires dites "an...Il faut donc accepter que lintelligence nest pas facilement mesurable, ni facilement dfinissable, car elle couvre de trop nombreux domaines. De plus, certains types sont souvent sous-estims voire ignors.La meilleure dfinition est donc aussi la plus vaste : lintelligence est la capacit sadapter

3. Lintelligence du vivant3. Lintelligence du vivantLintelligence est trop souvent lie de prs celle de lhumain. En effet, les humains ont cherch se montrer suprieurs aux animaux, et tout ce qui pouvait les diffrencier tait bon prendre pour se distinguer des btes . Ce ...Pourtant, la dfinition de lintelligence comme capacit sadapter permet de prendre en compte de nombreux comportements que lon trouve chez les animaux, et mme plus globalement chez les tres vivants.Quand on parle d intelligence du vivant

On peut aussi parler des animaux montrant une intelligence collective

Chez les abeilles, lintelligence linguistique

Mais lintelligence est en ralit prsente pour toutes les formes vivantes. De nombreuses espces vgtales se sont adaptes pour attirer certaines proies (comme les plantes carnivores) ou les insectes qui vont dissminer leur pollen. Au c...Dautres enfin attirent les prdateurs naturels de leurs propres prdateurs. Par exemple, certaines plantes de la famille des Acacias attirent les fourmis pour se protger des herbivores. Elles appliquent ainsi le fameux dicton les ennemis de...On peut aller encore plus loin. Certains champignons ont dvelopp des stratgies trs complexes pour survivre et se reproduire, et certains prsents dans les forts amazoniennes du Brsil sont ainsi capables dutiliser des fourmis comme h...Certes, tous les individus dune mme espce nont pas le mme niveau dintelligence, mais il est impossible de nier que lon peut trouver des formes dintelligence dans les espces vivantes.

4. Lintelligence artificielle4. Lintelligence artificielleLa nature prsente de nombreux cas dintelligence : elle nest pas spcifique lhomme. En fait, elle nest mme pas spcifique au vivant : tout systme qui pourrait sadapter pour donner une rponse adquate son environnement p...intelligence artificielle

Le domaine de lintelligence artificielle est trs vaste et peut couvrir de nombreuses techniques diffrentes. Les capacits de calcul toujours plus importantes des ordinateurs, une meilleure comprhension de certains processus naturels lis ...Pour autant, toutes les facults que lon peut donner un ordinateur ne sont pas considres comme faisant partie de lintelligence artificielle. Ainsi, un ordinateur qui peut rsoudre des quations complexes dans un temps trs court (bea...Comme pour les humains (ou les animaux), il existe des tests pour dterminer si on peut considrer que le programme est, ou non, intelligent. Le plus connu est le test de Turing

Ce test subit, comme pour les tests de Q.I., de nombreuses critiques. Tout dabord, il ne sapplique pas toutes les formes dintelligence et ne peut pas tester tous les programmes (uniquement ceux destins la communication). De plus, un ...Celui-ci reconnat des structures de phrases pour en extraire les mots importants et les rutilise dans les questions suivantes. Par exemple, la phrase Jaime le chocolat , le programme rpondra Pourquoi dites-vous que vous aimez le c...Enfin, un programme trop intelligent qui pourrait rpondre toutes les questions de manire correcte ou qui ne ferait aucune faute dorthographe, de grammaire ou simplement de frappe serait vite reconnu et chouerait le test.Il est donc difficile de dfinir exactement lintelligence artificielle : il faut surtout que la machine donne limpression dtre intelligenteadaptabilit

Il est par contre important de noter quil ny a aucune notion de technologie, de langage ou de domaine dapplication dans cette dfinition. Il sagit dun champ trs vaste, que lon peut nanmoins sparer en deux grands courants : Lapproche symbolique : lenvironnement est dcrit le plus prcisment possible, ainsi que les lois qui sy appliquent, et cest au programme de choisir la meilleure option. Cest lapproche utilise dans les systmes experts ou la Lapproche symbolique : lenvironnement est dcrit le plus prcisment possible, ainsi que les lois qui sy appliquent, et cest au programme de choisir la meilleure option. Cest lapproche utilise dans les systmes experts ou la Lapproche symbolique : lenvironnement est dcrit le plus prcisment possible, ainsi que les lois qui sy appliquent, et cest au programme de choisir la meilleure option. Cest lapproche utilise dans les systmes experts ou la Lapproche symbolique

Lapproche connexionniste : on donne au logiciel un moyen dvaluer si ce quil fait est bien ou non, et on le laisse trouver des solutions seul, par mergence. Cette approche est celle des rseaux de neurones ou des systmes multi-agents. Lapproche connexionniste : on donne au logiciel un moyen dvaluer si ce quil fait est bien ou non, et on le laisse trouver des solutions seul, par mergence. Cette approche est celle des rseaux de neurones ou des systmes multi-agents. Lapproche connexionniste

Ces deux approches ne sont cependant pas totalement contradictoires, et peuvent donc tre complmentaires pour rsoudre certains problmes : on peut par exemple partir dune base symbolique qui pourra tre complte par une approche connexio...

5. Domaines dapplication5. Domaines dapplicationLintelligence artificielle est souvent associe la science-fiction

Actuellement, lintelligence artificielle est effectivement utilise dans le monde de la robotique

Les militaires

Un autre grand domaine de lintelligence artificielle est le jeu vido

Mme dans le titre Pac-Man, les diffrents fantmes sont chacun dots dune intelligence artificielle pour contrler leurs mouvements : Blinky (le fantme rouge) essaie datteindre la case dans laquelle se trouve actuellement le joueur ; Pi...Si la robotique et les jeux vido sont des domaines vidents dapplication de lintelligence artificielle, ils ne sont cependant que la partie immerge de liceberg. De nombreux autres domaines utilisent lI.A., du milieu bancairemdecine

En effet, les systmes experts qui permettent de prendre une dcision grce des rgles plus ou moins volues sont utiliss pour dtecter des fraudes (par exemple les fraudes la carte bancaire) ou pour dtecter des modifications de com...LI.A. peut se retrouver dans des domaines de la vie courante comme linformatique personnelle

Linformatique industrielle

Enfin, ces dernires annes, on observe une explosion de lIoT (Internet of Things

6. Synthse6. SynthseLintelligence est un concept difficile dfinir prcisment, car celle-ci peut prendre de nombreuses formes. Il est tout aussi difficile de la mesurer et les tests de Q.I. sont biaiss. Elle peut se rsumer comme tant la capacit dada...Le rgne animal est donc lui aussi dot dintelligence, certes diffrente dans ses exemples, mais bien prsente. Plus gnralement, tous les tres vivants, par leur adaptation leur environnement et la cration de stratgies de survie co...Celle-ci peut tre implante dans des machines. Lintelligence artificielle revient donc doter un systme dun mcanisme lui permettant de simuler le comportement dun tre vivant, de mieux le comprendre ou encore dadapter sa s...Les technologies, les langages et les algorithmes sont aussi nombreux que les domaines dapplication, et lI.A. nest pas rserve la robotique ou aux jeux vido. En effet, on peut la retrouver dans quasiment tous les domaines informatis...Il sagit dun domaine en plein essor et les capacits grandissantes des ordinateurs ont permis de mettre au point des algorithmes jusqualors impossibles. Sans aucun doute, lI.A. va faire partie de notre futur et il est donc important que ...

Systmes expertsSystmes expertsL'Intelligence Artificielle1. Prsentation du chapitre1. Prsentation du chapitreBien souvent, on aimerait qu'un ordinateur soit capable de nous donner une information que l'on ne connat pas partir de faits connus. Les tres humains eux-mmes ne savent pas toujours dduire de nouveaux faits partir d'autres faits qui leur sont connus et ncessitent l'aide d'un expert

Beaucoup d'emplois sont tenus par ces experts. Les mdecins, les assureurs ou les agents immobiliers n'en sont que quelques exemples.L'intelligence artificielle peut nous aider, en crant un programme informatique appel systme expert

Ce chapitre prsente donc les systmes experts en commenant par leurs concepts. Un exemple sert de fil rouge, pour bien comprendre comment toutes les parties d'un systme expert communiquent. Ensuite les grands domaines d'application sont prsents. Puis est abord le cas dans lequel les connaissances du domaine prsentent un degr dincertitude, et les modifications ncessaires pour grer celle-ci sont alors expliques. Enfin, ...Ce chapitre se termine par une petite synthse.

2. Exemple : un systme expert en polygones2. Exemple : un systme expert en polygonesCette section permet dtudier le fonctionnement dtaill d'un systme expert dont le but est de dterminer le nom d'un polygone (par exemple un rectangle) en fonction de caractristiques sur la forme (le nombre de cts, les angles droits....Un polygone est dfini comme une forme gomtrique possdant au moins trois cts. L'ordre

2.1 Triangles2.1 TrianglesSi l'ordre d'un polygone vaut 3, il possde donc trois cts et il s'agit dun triangle. Celui-ci peut tre quelconque, rectangle, isocle, rectangle isocle ou quilatral. Les figures suivantes rappellent les particularits de chacun.

Triangle quelconque : possde trois cts de tailles diffrentes et aucun angle droit.Triangle quelconque : possde trois cts de tailles diffrentes et aucun angle droit.Triangle quelconque

Triangle rectangle : possde trois cts de tailles diffrentes et un angle droit.Triangle rectangle : possde trois cts de tailles diffrentes et un angle droit.Triangle rectangle

Triangle isocle : possde deux cts de mme taille, mais pas d'angle droit.Triangle isocle : possde deux cts de mme taille, mais pas d'angle droit.Triangle isocle

Triangle rectangle isocle : cumule les deux cts gaux du triangle isocle et l'angle droit du triangle rectangle.Triangle rectangle isocle : cumule les deux cts gaux du triangle isocle et l'angle droit du triangle rectangle.Triangle rectangle isocle

Triangle quilatral : possde trois cts de mme taille (et ne peut pas possder d'angle droit).Triangle quilatral : possde trois cts de mme taille (et ne peut pas possder d'angle droit).Triangle quilatral

2.2 Quadrilatres2.2 QuadrilatresLorsque l'ordre d'un polygone vaut 4, on parle de quadrilatre. Celui-ci peut tre quelconque, ou il peut s'agir d'un trapze, d'un paralllogramme, d'un losange, d'un rectangle ou d'un carr. Les figures suivantes prsentent ces diffrents qu...

Quadrilatre quelconque : possde quatre cts non parallles.Quadrilatre quelconque : possde quatre cts non parallles.Quadrilatre quelconque

Trapze : possde deux cts (et uniquement deux) parallles.Trapze : possde deux cts (et uniquement deux) parallles.Trapze

Paralllogramme : possde quatre cts parallles deux deux. Possde aussi des cts opposs de mme taille.Paralllogramme : possde quatre cts parallles deux deux. Possde aussi des cts opposs de mme taille.Paralllogramme

Losange : paralllogramme dont les cts sont tous de la mme taille.Losange : paralllogramme dont les cts sont tous de la mme taille.Losange

Rectangle : paralllogramme possdant des angles droits.Rectangle : paralllogramme possdant des angles droits.Rectangle

Carr : paralllogramme cumulant les cts de mme taille du losange et les angles droits du rectangle.Carr : paralllogramme cumulant les cts de mme taille du losange et les angles droits du rectangle.Carr

2.3 Autres polygones2.3 Autres polygonesLorsque l'ordre est suprieur 4, le nom du polygone est donn dans le tableau suivant pour les cas les plus courants. On parle de polygone rgulier lorsque tous les cts sont de la mme taille.OrdreOrdre

Nom du polygoneNom du polygone

55

PentagonePentagone

66

HexagoneHexagone

88

OctogoneOctogone

1010

DcagoneDcagone

1212

DodcagoneDodcagone

2020

IcosagoneIcosagone

Tous les polygones, quel que soit leur ordre, possdent un nom particulier. Ainsi un polygone d'ordre 26 s'appelle un hexaicosagone. Cependant, seuls les noms les plus courants sont rappels dans le tableau prcdent.Tous les polygones, quel que soit leur ordre, possdent un nom particulier. Ainsi un polygone d'ordre 26 s'appelle un hexaicosagone. Cependant, seuls les noms les plus courants sont rappels dans le tableau prcdent.

3. Contenu d'un systme expert3. Contenu d'un systme expertUn systme expert est constitu de diffrentes parties lies entre elles : Une Une Une base de rgles

Une Une base de faits

Un Un moteur d'infrences

Une Une interface

Le schma suivant indique les liens entre ces diffrentes parties, qui seront dtailles ensuite.

3.1 Base de rgles3.1 Base de rglesUn systme expert contient un ensemble de rgles nomm base de rgles

Ces rgles sont toujours de la forme :SI (ensemble de conditions) ALORS nouvelle connaissanceLes conditions d'application d'une rgle sont appeles les prmisses

Si la rgle ncessite une coordination OU, on la dcoupera en deux rgles distinctes quivalentes. Ainsi, la rgle:Si la rgle ncessite une coordination OU, on la dcoupera en deux rgles distinctes quivalentes. Ainsi, la rgle:

Si (A OU B) alors CDeviendra:Deviendra:

Si A alors C Si B alors CLes nouvelles connaissances sont appeles conclusions

Pour notre systme expert sur les formes gomtriques, voici les rgles concernant les triangles :SI (ordre vaut 3) ALORS c'est un triangleSI (triangle ET 1 angle droit) ALORS c'est un triangle rectangleSI (triangle ET 2 cts de mme taille) ALORS c'est un triangle isocleSI (triangle rectangle ET triangle isocle) ALORS c'est un triangle rectangle isocleSI (triangle ET cts tous gaux) ALORS c'est un triangle quilatralIl existerait d'autres rgles pour les quadrilatres et les polygones d'ordre suprieur. On voit que trs rapidement le nombre de rgles peut tre important. De plus, selon le systme utilis, chaque rgle doit suivre une syntaxe prcise et impose. En particulier, les prmisses et conclusions peuvent tre demandes sous la forme attribut(valeur)

SI (ordre(3) ET angleDroit(1)) ALORS polygone(TriangleRectangle)Lorsque le systme expert est construit de toutes pices, il est possible de choisir le format des rgles de manire ce qu'il se rapproche le plus possible du domaine tudi. Cela facilitera la mise en place et la cration du moteur.Lorsque le systme expert est construit de toutes pices, il est possible de choisir le format des rgles de manire ce qu'il se rapproche le plus possible du domaine tudi. Cela facilitera la mise en place et la cration du moteur.

3.2 Base de faits3.2 Base de faitsLes prmisses d'une rgle peuvent tre de deux types : Des connaissances sur le problme fournies par l'utilisateur du systme : ce sont les Des connaissances sur le problme fournies par l'utilisateur du systme : ce sont les Des connaissances sur le problme fournies par l'utilisateur du systme : ce sont les entres

Des connaissances issues de l'application de rgles : ce sont les Des connaissances issues de l'application de rgles : ce sont les faits infrs

Ces deux types de connaissances doivent tre enregistrs dans une base de faits

Supposons que nous ayons affaire une forme d'ordre 4, possdant 4 cts parallles, de mme taille et 4 angles droits. Ce sont nos connaissances initiales. ces faits en entre va se rajouter le fait que la figure est un quadrilatre (elle est d'ordre 4) et un paralllogramme (un quadrilatre avec 4 cts parallles), qu'il s'agit plus prcisment d'un losange (un paralllogramme dont les 4 ...Gnralement, c'est le dernier fait ajout qui intresse vraiment l'utilisateur : il s'agit du but du programme

Cependant, on peut aussi concevoir un systme expert qui permet de savoir si un fait est vrai ou non. Dans ce cas, on regarde si le fait donn est dans la base de faits aprs application des rgles.Dans l'exemple de notre quadrilatre prcdent, au lieu de demander quel est le nom de ce polygone (il s'agit d'un carr), on pourrait demander s'il s'agit d'un losange ou s'il s'agit d'un triangle rectangle. On obtiendrait une rponse affirmati...

3.3 Moteur d'infrences3.3 Moteur d'infrencesLe moteur d'infrencessystme d'infrences

Le moteur va permettre de slectionner et d'appliquer les rgles. Cette tche n'est pas forcment aise car il peut exister des milliers de rgles. De plus, il ne sert rien d'appliquer une rgle dj utilise prcdemment ou qui ne cor...Par exemple, si on cr un systme expert permettant de reconnatre la faune et la flore d'une fort et que l'on cherche savoir de quelle famille est un insecte trouv, il ne sert rien d'essayer d'appliquer les rgles concernant les arbr...C'est aussi le moteur d'infrences qui va ajouter les nouveaux faits la base de faits, ou y accder pour vrifier qu'un fait est dj connu. L'ajout des faits que l'on sait faux est tout aussi intressant que celui des faits que l'on sait ju...Une analogie simple est le jeu du Qui est-ce ? . Dans ce jeu, il faut retrouver un personnage parmi plusieurs en ne posant que des questions dont les rponses sont oui ou non (par exemple le personnage porte-t-il un chapeau ? ). Que la r...Une analogie simple est le jeu du Qui est-ce ? . Dans ce jeu, il faut retrouver un personnage parmi plusieurs en ne posant que des questions dont les rponses sont oui ou non (par exemple le personnage porte-t-il un chapeau ? ). Que la r...

Enfin, le moteur doit pouvoir prendre une dcision importante : celle de s'arrter pour prsenter l'utilisateur la rponse sa question. Il doit donc savoir quand un but est atteint, ou quand il ne le sera jamais.L'avantage des systmes experts sur de nombreuses autres techniques d'intelligence artificielle est leur capacit expliquer le raisonnement suivi : les moteurs implmentent donc souvent un mcanisme permettant de retrouver toutes les rgles u...De nombreux moteurs d'infrences sont disponibles ou peuvent tre cods de toutes pices, et ce dans n'importe quel langage de programmation. Certains langages ont cependant t crs dans le but dimplmenter des moteurs d'infrences. Il...programmation logique

3.4 Interface utilisateur3.4 Interface utilisateurLe dernier lment d'un systme expert est l'interface utilisateur

Comme pour tout logiciel, si l'interface n'est pas agrable utiliser ou si elle est trop complexe, voire contre-intuitive, le systme sera peu ou pas utilis.De plus, dans un systme expert, il est primordial que les choix dont dispose l'utilisateur soient clairs, pour qu'il puisse rpondre correctement aux questions poses, sans quoi le rsultat retourn serait faux.Dans le cas du systme expert sur les polygones, il y a peu de chances d'erreur, car les rgles sont bases sur le nombre de cts, les angles droits, les cts parallles et les tailles des cts. Pourtant, une interface demandant l'ordre ...Dans le cas de la reconnaissance d'insectes, si le logiciel demande si celui-ci possde des cerques ou des cornicules, il y a peu de chances qu'un utilisateur non entomologiste puisse rpondre correctement. Par contre, si on lui demande si le corps...Il est donc important de travailler sur l'ergonomie du systme expert avec de futurs utilisateurs ou des reprsentants des utilisateurs, de manire savoir quels termes seraient les plus adapts, ainsi que la disposition des crans, pour limit...

4. Types d'infrences4. Types d'infrencesLes moteurs d'infrences peuvent enchaner les rgles de diffrentes faons : c'est ce que l'on appelle le chanage

4.1 Chanage avant4.1 Chanage avant4.1.1 Principe4.1.1 PrincipeUn moteur chanage avantdirig par les donnes

Dans ce mode de chanage, on part des donnes disponibles dans la base de faits, et on teste pour chaque rgle si elle peut s'appliquer ou non. Si oui, on l'applique et on rajoute la conclusion la base de faits.Le moteur explore donc toutes les possibilits, jusqu' trouver le fait recherch ou jusqu' ne plus pouvoir appliquer de nouvelles rgles.Ce mode de chanage est celui propos par dfaut dans des langages de type CLIPS (C Language Integrated Production System

4.1.2 Application un exemple4.1.2 Application un exempleDans le cas de notre systme expert sur les polygones, supposons que nous partions des faits suivants : L'ordre vaut 3. L'ordre vaut 3. L'ordre vaut 3.

Il y a un angle droit. Il y a un angle droit.

Deux cts sont de mme taille. Deux cts sont de mme taille.

On commence par appliquer la rgle suivante qui ajoute dans la base de faits que la forme est un triangle :SI (ordre vaut 3) ALORS c'est un triangleOn peut ensuite en dduire que c'est un triangle rectangle grce la rgle suivante : SI (triangle ET 1 angle droit) ALORS c'est un triangle rectangleDe mme, on sait que c'est un triangle isocle :SI (triangle ET 2 cts de mme taille) ALORS c'est un triangle isocleEnfin, en sachant qu'il s'agit d'un triangle rectangle et d'un triangle isocle, on peut appliquer :SI (triangle rectangle ET triangle isocle) ALORS c'est un triangle rectangle isocleOn rajoute donc enfin le fait qu'il s'agit d'un triangle rectangle isocle. Comme il n'y a plus de rgles applicables, le moteur d'infrences s'arrte. L'utilisateur est inform que son polygone est un triangle rectangle isocle.On peut rsumer la logique du moteur par le schma suivant :

4.2 Chanage arrire4.2 Chanage arrire4.2.1 Principe4.2.1 PrincipeLes moteurs d'infrences chanage arriredirigs par le but

Ce coup-ci, on part des faits que l'on souhaiterait obtenir et on cherche une rgle qui pourrait permettre d'obtenir ce fait. On rajoute alors toutes les prmisses de cette rgle dans les nouveaux buts atteindre.On ritre, jusqu' ce que les nouveaux buts atteindre soient prsents dans la base de faits. Si un fait est absent de la base de faits ou prouv comme faux, alors on sait que la rgle ne peut pas s'appliquer. Ces moteurs ont donc un mcani...backtracking

Si plus aucune rgle ne peut mener au but recherch, alors celui-ci est considr comme faux.Ce mode de chanage est celui prsent par dfaut dans le langage Prolog, ddi aux systmes experts.

4.2.2 Application un exemple4.2.2 Application un exempleOn reprend l'exemple prcdent, savoir un polygone pour lequel : L'ordre vaut 3. L'ordre vaut 3. L'ordre vaut 3.

Il y a un angle droit. Il y a un angle droit.

Deux cts sont de mme taille. Deux cts sont de mme taille.

On demande au logiciel si le triangle est rectangle isocle. C'est notre premier but. Le moteur recherche une rgle permettant d'obtenir ce fait, il n'y en a qu'une :SI (triangle rectangle ET triangle isocle) ALORS c'est un triangle rectangle isocleLe moteur ajoute donc les buts triangle rectangle et triangle isocle sa liste de buts. Il commence par chercher une rgle permettant de prouver qu'il s'agit d'un triangle rectangle. L encore, nous n'avons qu'une rgle :SI (triangle ET un angle droit) ALORS c'est un triangle rectangleIl obtient ainsi deux nouveaux buts : s'agit-il d'un triangle et a-t-il un angle droit ? La prsence d'un angle droit est dj en base de faits, ce but est donc atteint. Pour le triangle, il a besoin de la rgle suivante :SI (ordre vaut 3) ALORS c'est un triangleLa base de faits prcise que l'ordre a une valeur de 3, la rgle est donc prouve. Le fait triangle peut ainsi tre ajout la base de faits et enlev des buts atteindre, tout comme le fait triangle rectangle . Il ne lui reste alors p...De la mme faon, il cherche une rgle possdant ce but :SI (triangle ET 2 cts de mme taille) ALORS c'est un triangle isocleLe fait que la forme soit un triangle est dj en base de faits (on l'a obtenu juste avant) et la prsence de deux cts de mme taille aussi. On rajoute que c'est un triangle isocle.Le programme finit par retourner son but initial, savoir s'il s'agissait d'un triangle rectangle isocle. Comme les faits triangle rectangle et triangle isocle sont maintenant prouvs, il peut en conclure que oui, la forme est u...La logique est donc ce coup-ci la suivante : on part du but atteindre et on essaie de prouver que les prmisses sont vraies.

4.3 Chanage mixte4.3 Chanage mixteChaque mode de chanage a ses avantages et ses inconvnients : Le chanage avant permet de dcouvrir en permanence de nouveaux faits, mais il risque d'appliquer et de tester de nombreuses rgles qui ne concernent pas l'information recherche par l'utilisateur. Il est donc plus adapt l'exploration. Le chanage avant permet de dcouvrir en permanence de nouveaux faits, mais il risque d'appliquer et de tester de nombreuses rgles qui ne concernent pas l'information recherche par l'utilisateur. Il est donc plus adapt l'exploration. Le chanage avant permet de dcouvrir en permanence de nouveaux faits, mais il risque d'appliquer et de tester de nombreuses rgles qui ne concernent pas l'information recherche par l'utilisateur. Il est donc plus adapt l'exploration.

Le chanage arrire permet de se concentrer sur un but prcis (ou plusieurs buts), mais il va tester de nombreuses possibilits qui seront finalement dmontres comme fausses. Ainsi, il va essayer de prouver des rgles qui ne pourront pas ... Le chanage arrire permet de se concentrer sur un but prcis (ou plusieurs buts), mais il va tester de nombreuses possibilits qui seront finalement dmontres comme fausses. Ainsi, il va essayer de prouver des rgles qui ne pourront pas ...

Un mlange des deux chanages a alors t propos : le chanage mixte

C'est donc un savant quilibre entre les deux mthodes de recherche, en fonction de rgles de recherche. De plus, on peut alterner les phases de recherche en profondeur aux phases de recherche en largeur selon les buts. On dpasse cependant ici l...Le chanage mixte est cependant peu utilis, car il ajoute de la complexit au moteur d'infrences. Il est pourtant beaucoup plus efficace.Le chanage mixte est cependant peu utilis, car il ajoute de la complexit au moteur d'infrences. Il est pourtant beaucoup plus efficace.

5. tapes de construction d'un systme5. tapes de construction d'un systmePour crer intgralement un systme expert, il est important de suivre diffrentes tapes qui font entrer en jeu des comptences et donc des profils professionnels diffrents.Globalement, il y a quatre tapes prsentes dans la figure suivante, avec les principaux rles ncessaires sous chaque tape :

5.1 Extraction des connaissances5.1 Extraction des connaissancesLa premire tape consiste extraire les connaissances

Prenons l'exemple des insectes. Face des insectes peu courants ou inconnus, il parat assez facile de dterminer des rgles qui permettent d'arriver au rsultat voulu. Mais quelles rgles applique-t-on pour reconnatre une mouche d'un mousti...C'est donc en posant diffrentes questions l'expert que l'on pourra l'amener dterminer lui-mme les rgles qu'il applique, souvent inconsciemment. Le travail de l'interrogateur est donc primordial, car ce dernier doit indiquer les zones d'...Cette tape peut tre trs longue, en particulier sur des domaines vastes. De plus, si le domaine d'application possde des risques, il est important de faire vrifier les rgles par plusieurs experts, qui pourront les complter ou les modifie...La russite du systme dpend en trs grande partie de cette phase. Il ne faut donc pas la ngliger en voulant aller trop vite.

5.2 Cration du moteur d'infrences5.2 Cration du moteur d'infrencesSi le projet utilise un moteur d'infrences existant, cette phase consistera juste acqurir celui-ci, voire le configurer.Sinon, il faudra implmenter un moteur d'infrences

Le formalisme des rgles sera alors fix, ce qui pourra avoir un impact important sur les phases suivantes.

5.3 criture des rgles5.3 criture des rglesLa phase suivante consiste transformer les diffrentes rgles

la fin de cette tape, la base de rgles doit tre complte. Il ne faut pas hsiter vrifier plusieurs fois la prsence de toutes les rgles et leur exactitude, car une erreur ce niveau peut fausser tout le travail fait avec le ou le...Un spcialiste du langage du moteur ainsi qu'en systme expert sera donc ncessaire pour cette tape.

5.4 Cration de l'interface utilisateur5.4 Cration de l'interface utilisateurLa dernire tape consiste crer l'interface utilisateur

Dans une premire version, on peut imaginer une interface sous la forme d'entres/sorties dans une console. Cependant, pour une application grand public, une interface graphique sera prfrer. Il est important de faire intervenir au plus tt ...Il existe nanmoins un cas particulier : si le systme expert est utilis par un autre systme informatique (et non un humain), il faudra la place crer les canaux de communication entre les programmes (via des API, des fichiers, des flux, de...Une fois le systme expert cr, il peut tre utilis.

6. Performance et amliorations6. Performance et amliorationsUn point n'a jamais t voqu jusqu' prsent : celui des performances. Celui- ci est pourtant primordial pour la russite du systme. Nous allons donc voir quels sont les critres de performance et comment construire un systme permettant...6.1 Critres de performance6.1 Critres de performanceLes performances d'un systme expert sont primordiales, surtout s'il est compos de nombreuses rgles. Le premier critre de performance est le temps de rponse

Ce temps dpend du problme pos. Par exemple, dans notre systme expert de gomtrie, le temps de rponse sera acceptable s'il reste de l'ordre de la seconde. Et au vu du nombre de rgles, il y a peu de risques d'avoir un temps suprieur.Dans un systme expert mdical, ou pour aider un garagiste, l encore le temps n'est pas la priorit tant qu'il reste de l'ordre de quelques secondes.Cependant, si le systme expert doit tre utilis dans un environnement dangereux pour prendre une dcision (par exemple pour arrter ou non une machine) ou doit communiquer avec d'autres systmes, le temps de rponse va devenir un critre pr...En plus du temps de rponse, il existe un deuxime critre de performance : l'utilisation de la mmoire

Enfin, gnralement tous les moyens mis en uvre pour optimiser le temps de rponse auront un impact ngatif sur la mmoire et vice-versa. Il faut donc trouver le bon compromis en fonction des besoins.

6.2 Amlioration des performances par l'criture des rgles6.2 Amlioration des performances par l'criture des rglesLa premire faon d'amliorer les performances est de bien travailler sur l'criture des rgles. En effet, il est souvent possible de limiter leur nombre.Dans notre exemple avec les triangles, on a dfini le triangle rectangle isocle comme tant un triangle rectangle qui est aussi isocle, mais on aurait pu dire qu'un triangle rectangle isocle tait un triangle possdant un angle droit et deu...Il faut aussi savoir quels faits seront ou non entrs par l'utilisateur. Ainsi, on aurait pu dfinir nos quadrilatres non par leurs cts parallles et leurs angles droits, mais par des proprits sur les diagonales (par exemple qu'elles se ...L'ordre des rgles est lui aussi important. En effet, la plupart des moteurs choisissent la premire rgle qui correspond ce qu'ils cherchent, donc la premire dont ils possdent toutes les prmisses en chanage avant ou la premire ayant ...Certains moteurs utilisent des critres supplmentaires pour choisir les rgles, comme le nombre de prmisses ou la fracheur des faits utiliss (pour utiliser au maximum les derniers faits obtenus). Il est donc primordial de bien conna...La dernire grande faon d'optimiser cette base est de lui ajouter des index. Ceux-ci ont le mme but que les index dans les bases de donnes : ils permettent de trouver plus rapidement les rgles utilisant un fait donn, que ce soit en prmis...

6.3 Importance de la reprsentation du problme6.3 Importance de la reprsentation du problmeUn moteur d'infrences, avant d'arriver au rsultat attendu, va faire de nombreuses tentatives. Il est important de limiter celles-ci pour optimiser les performances du systme expert.Nous allons pour cela nous intresser un problme trs classique : le problme des 8 reines . Le but est de placer sur un chiquier (donc un damier de 8 * 8 cases), huit reines, qui ne doivent pas entrer en conflit, sans s'intresser au...Les deux figures suivantes indiquent un cas de russite de placement et un cas incorrect o plusieurs dames entrent en conflit :

Dans cette disposition, il n'y a aucun conflit entre les reines. Il s'agit donc d'une solution possible.Dans cette disposition, il n'y a aucun conflit entre les reines. Il s'agit donc d'une solution possible.

Dans cette disposition par contre, 5 reines sont en conflit entre elles. Les reines 1 et 3 sont sur la mme diagonale montante alors que les reines 1 et 5 sont sur la mme colonne. 2, 4 et 5 sont sur la mme diagonale descendante.Dans cette disposition par contre, 5 reines sont en conflit entre elles. Les reines 1 et 3 sont sur la mme diagonale montante alors que les reines 1 et 5 sont sur la mme colonne. 2, 4 et 5 sont sur la mme diagonale descendante.

Au total, il y a 92 positions possibles rpondant au problme des 8 reines.Si nous dfinissons notre problme comme devant nous donner les positions possibles des 8 reines sous la forme (x,y), on voit qu'il y a 64 positions possibles par reine (vu qu'il y a 64 cases). Cela nous amne donc devoir tester 648 possibilit...On peut prendre en compte le fait que chaque reine doit tre sur une case diffrente des prcdentes. Ainsi, pour la premire reine, on a 64 possibilits. Lorsque l'on cherche placer la deuxime reine, une case est dj prise, il ne reste...En mathmatiques, on parle d'arrangements. Celui-ci se note En mathmatiques, on parle d'arrangements. Celui-ci se note

Une rflexion un peu plus pousse peut nous mener comprendre que les reines doivent tre dans des colonnes diffrentes (sinon elles seraient en conflit comme c'est le cas des reines 1 et 5 dans la figure prcdente). On cherche donc pour cha...8

Enfin, en prenant en compte le fait que les lignes sont, elles aussi, diffrentes, on voit que si la premire reine est place sur la ligne 1, la deuxime reine n'a plus que 7 lignes possibles pour se placer. On obtient alors 8 * 7 * 6 * 5 * 4 * ...En changeant simplement la reprsentation du problme, grce aux contraintes connues, on est donc pass de plus de 200 mille-milliards de possibilits environ 40 000. Si le temps ncessaire pour tester toutes les possibilits dans le premie...Le choix de la reprsentation du problme n'est donc pas anodin, et il est important de bien y rflchir avant de se lancer dans la cration des rgles. Les performances peuvent en tre fortement impactes.Plus loin dans ce chapitre sera propose une implmentation pour le systme expert sur les polygones et pour les 8 reines en Prolog. C'est la dernire version, utilisant les permutations, qui sera utilise pour ce problme.Plus loin dans ce chapitre sera propose une implmentation pour le systme expert sur les polygones et pour les 8 reine