POUR LE DIAGNOSTIC MULTI-FAUTE · Remerciements C’est avec beaucoup de gratitude et de sincérité, que je remercie mon Directeur de thèse, le Professeur HAFFAF Hafid du département

République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université d’Oran Es-Sénia

Facultés des Sciences

Département d’Informatique

MEMOIRE DE MAGISTER

sous le thème :

ALGORITHMES ET OPTIMISATIONS

POUR LE DIAGNOSTIC MULTI-FAUTE

Présenté par :

BOUZIANI LOTFI GHILANE

Spécialité : Informatique

Option : Méthodes et Modèles pour la Sécurité des Systèmes d’Informations

Soutenu le : 13 / 01 /2010

À : la Bibliothèque de l’Université d’Oran

Devant les membres du jury :

M. KHELFI Med Fayçal Président Prof. à l’Université d’Oran, Es-Sénia

M. SENOUCI Mohamed Examinateur M.C. à l’Université d’Oran, Es-Sénia

M. SEKHRI Larbi Examinateur M.C. à l’Université d’Oran, Es-Sénia

M. BOUAZZA Kheireddine Membre invité M.C. (B) à l’Université d’Oran, Es-Sénia

M. HAFFAF Hafid Encadreur Prof. à l’Université d’Oran, Es-Sénia

Remerciements

C’est avec beaucoup de gratitude et de sincérité, que je remercie mon Directeur de thèse, le Professeur HAFFAF Hafid du département d’Informatique de l’Université d’Oran, pour sa présence scientifique et humaine, ainsi que pour tout le soin qu’il a apporté à me diriger et à me conseiller tout au long de ce travail.

Mes vifs remerciements vont également à l’encontre du Professeur KHELFI Mohamed Fayçal de l’Université d’Oran, pour avoir accepté d’honorer le jury et de le présider. Qu’il trouve ici l’expression de mon plus profond respect.

Mes remerciements s’adressent également à Monsieur SENOUCI Mohamed, Maître de conférences à l’Université d’Oran, Monsieur SEKHRI Larbi, Maître de conférences à l’Université d’Oran et Monsieur BOUAZZA Kheireddine, Maître de conférences à l’Université d’Oran, pour avoir porté un intérêt à ce modeste travail, et d’avoir accepté de l’examiner.

Je tiens aussi à remercier Monsieur MIHOUBI Bachir Directeur de la société ITComp à Alger et Monsieur BENABBASSI Youssef de l’Université de Béchar, pour leurs encouragements et leurs judicieux conseils. Mes remerciements s’adressent aussi à Mademoiselle MERABET Latifa de la Direction régionale de la CAAT Oran, pour son soutien et son aide.

Enfin, merci à tous ceux qui ont contribué de près ou de loin à l'aboutissement de ce travail, par leur confiance et leurs encouragements.

PS : merci aussi à Internet ☺

Sommaire

Sommaire

Liste des figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Liste des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Chapitre I : Surveillance et diagnostic de fautes

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2. Principes et concepts généraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

a. Terminologie et définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

i. Etats et signaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

ii. Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

iii. Propriétés des systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

b. Principes de la surveillance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

c. Caractéristiques d’un système de surveillance . . . . . . . . . . . . . . . . . . . . . . . . . . 11

d. Cahier des charges de la surveillance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3. Classification des méthodes de diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

a. Classification par approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

i. Le diagnostic à base de modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

ii. Le diagnostic sans modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

b. Classification par domaine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

i. L’approche par redondance analytique FDI (Automatique) . . . . . . . . . . . . 17

ii. L’approche de diagnostic logique DX (IA) . . . . . . . . . . . . . . . . . . . . . . . . . 21

4. Le diagnostic par l’analyse structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

a. Le modèle comportemental du système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

b. Le modèle structurel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

i. Prise en compte de variables supplémentaires . . . . . . . . . . . . . . . . . . . . . . 29

c. Structure et redondance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Sommaire

i. Extraction de la partie surdéterminée d’un système . . . . . . . . . . . . . . . . . . 30

ii. Le couplage : première étape pour trouver les RRAs . . . . . . . . . . . . . . . . . 32

iii. Relations de redondance analytique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

iv. Signatures de fautes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

d. Analyse de l’isolabilité des fautes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

i. Algorithme d’analyse structurelle pour l’isolation de fautes . . . . . . . . . . . . 39

ii. Exploitation des propriétés structurelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

e. Qualités du diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

i. La réalisabilité des solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

ii. La capacité à gérer différents types de systèmes . . . . . . . . . . . . . . . . . . . . . 43

iii. La complexité temporelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

iv. La complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Chapitre II : Le diagnostic multi-faute

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2. Généralités sur le diagnostic multi-faute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

a. Principe de simplicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

b. Diagnostic de fautes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

c. Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

d. Complexité et classification du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

i. Théorie de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

ii. Complexité du diagnostic multi-faute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3. Caractérisation du comportement des fautes multiples . . . . . . . . . . . . . . . . . . . . . . 50

a. Cas des systèmes statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

b. Cas des systèmes dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

c. Cas des fautes en cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4. Le FDI étendu au cas multi-faute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

a. Modélisation pour le diagnostic multi-faute . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Sommaire

b. L’hypothèse de non compensation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

c. L’isolabilité du système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

d. Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5. Autres approches classiques pour le MFD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

a. L’approche « Intelligence Artificielle » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

b. Autres approches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Chapitre III : Panorama des méthodes de résolutions

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2. Les approches déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

a. L’algorithme exact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

i. Exemple de déroulement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

b. L’algorithme multi-faute générique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

i. Exemple de déroulement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

ii. Interprétation des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

c. L’algorithme multi-faute séquentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

i. Résultats de l’algorithme séquentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

ii. Comparaison avec l’algorithme générique . . . . . . . . . . . . . . . . . . . . . . . . . 64

3. Les approches heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

a. Les méta-heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

i. L’optimum de Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

ii. Types de méta-heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

iii. Les algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

b. Utilisation des algorithmes génétiques pour le MFD . . . . . . . . . . . . . . . . . . . . . 72

i. Principe de fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

ii. Formalisme de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

iii. Exemple de déroulement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

iv. Discussion des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Sommaire

4. Les approches approximatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

a. L’algorithme Branch & Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

i. L’algorithme général de PSEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

ii. Le PSEP appliqué au diagnostic multi-faute . . . . . . . . . . . . . . . . . . . . . . . . 81

b. L’approche gloutonne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

i. Application de la recherche gloutonne au MFD . . . . . . . . . . . . . . . . . . . . . 83

5. Comparaison des différentes méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Chapitre IV : Optimisation et implémentation des algorithmes

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2. Optimisation de l’algorithme exact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

a. Etapes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

i. Réduction du nombre de signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

ii. Comparaison des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

iii. Application du principe de parcimonie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

iv. Autres applications du principe de parcimonie . . . . . . . . . . . . . . . . . . . . . . 92

b. Exemple d’implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

3. Implémentation de l’algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

a. Etapes d’implémentation et d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

i. Le codage des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

ii. Evaluation des composants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

iii. La population initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

iv. Evaluation de la population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

v. La fonction Objectif globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

vi. Les opérateurs génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

vii. Le critère d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

b. Exemple d’implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4. Organisation de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Sommaire

a. Structures et techniques utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

i. Algorithme exact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

ii. Algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

b. Organigramme de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5. Etude comparative des résultats des deux algorithmes . . . . . . . . . . . . . . . . . . . . . . 115

6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Références bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Liste des figures

1

Liste des figures

Fig. 1.1 : Les étapes du diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Fig. 1.2 : Architecture générale de la détection de faute à base de modèles . . . . . . . . 15

Fig. 1.3 : Structure générale d’un système de diagnostic utilisant l’approche FDI . . . 17

Fig. 1.4 : Exemple de deux résidus. A t=5 l’un des résidus répond à une faute . . . . . 26

Fig. 1.5 : Exemples de résidus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Fig. 1.6 : Le graphe biparti du système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Fig. 1.7 : Le graphe biparti pour un système dynamique . . . . . . . . . . . . . . . . . . . . . . . 29

Fig. 1.8 : Décomposition canonique d’un système arbitraire . . . . . . . . . . . . . . . . . . . 31

Fig. 1.9 : Le système initial est décomposé. Le bloc inférieur droit est la partie sur-déterminée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Fig. 1.10 : Deux couplages représentés par des graphes bipartis et leurs matrices d’incidences respectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Fig. 1.11 : Les graphes orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Fig. 1.12 : Exemple des trois types de matrices d’incidences . . . . . . . . . . . . . . . . . . . . 38

Fig. 1.13 : Schéma général de l’algorithme de l’analyse structurelle pour le diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Fig. 2.1 : Un réseau simple et sa table de signatures ; plusieurs exemples de situations de multi-faute peuvent causer des erreurs . . . . . . . . . . . . . . . . 50

Fig. 2.2 : Un système à changements dynamiques : les fautes et les réparations séquentielles causent des modifications dans les résultats des observations et doivent être détectés et diagnostiqués correctement . . . . . . . . . . . . . . . . . 51

Fig. 3.1 : Comparaisons des différents algorithmes déterministes . . . . . . . . . . . . . . . 65

Fig. 3.2 : Classification des méthodes heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Fig. 3.3 : Les trois phases d’une méta-heuristique (les points rouges représentent l’échantillonnage de la fonction objectif) . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

Fig. 3.4 : Comportement des méta-heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Fig. 3.5 : Exemple de front de Pareto (un problème nécessitant la minimisation de deux objectifs f1 et f2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

Fig. 3.6 : Schéma général d’un algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . 71

Fig. 3.7 : Sélection par roue de loterie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Liste des figures

2

Fig. 3.8 : Le tournoi entre deux individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Fig. 3.9 : Croisement simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Fig. 3.10 : Croisement à deux points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Fig. 3.11 : Exemple de mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Fig. 3.12 : Arbre PSEP construit à partir de l’exemple précédent . . . . . . . . . . . . . . . . . 82

Fig. 4.1 : Table de signatures, graphe biparti et signature de faute de l’exemple . . . . 93

Fig. 4.2 : Début de l’application de l’algorithme exact . . . . . . . . . . . . . . . . . . . . . . . . 93

Fig. 4.3 : Table de signatures étendue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Fig. 4.4 : Table de signatures étendue optimisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Fig. 4.5 : Résultat après comparaison avec la signature de faute . . . . . . . . . . . . . . . . . 95

Fig. 4.6 : Composants simples et multiples correspondant à la signature de faute . . . 96

Fig. 4.7 : Détermination des composants en fautes et des composants protégés . . . . . 97

Fig. 4.8 : Les paramètres et options de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Fig. 4.9 : La fonction d’évaluation détermine la frontière Pareto . . . . . . . . . . . . . . . . . 102

Fig. 4.10 : Table de signatures, graphe biparti et signature de faute de l’exemple . . . 105

Fig. 4.11 : Elimination d’une partie des composants . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Fig. 4.12 : Détermination de la population initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Fig. 4.13 : Première évaluation de la population initiale . . . . . . . . . . . . . . . . . . . . . . . . 107

Fig. 4.14 : Calcul des Fitness avant les itérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Fig. 4.15 : Calcul des Fitness après 100 itérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Fig. 4.16 : Les composants constituant des solutions (simples et combinées) . . . . . . . 109

Fig. 4.17 : Le paramétrage de l’algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Fig. 4.18 : Les nouveaux individus obtenus après 500 itérations . . . . . . . . . . . . . . . . . . 110

Fig. 4.19 : Les nouveaux composants constituant des solutions (simples et combinées) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Fig. 4.20 : Organigramme général de l’application développée . . . . . . . . . . . . . . . . . . 114

Fig. 4.21 : Evolution du temps d’exécution pour l’algorithme exact . . . . . . . . . . . . . . . 115

Liste des tableaux

3

Liste des tableaux

Tab. 1.1 : Matrice de sensibilité aux fautes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Tab. 1.2 : Matrice d’incidence de l’exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Tab. 1.3 : Table de signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Tab. 2.1 : Exemple d’une table de signatures étendue à partir de 4 composants simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

Tab. 3.1 : Exemple des résultats obtenus avec un algorithme génétique . . . . . . . . . 79

Tab. 3.2 : Comparaison des caractéristiques des différentes approches . . . . . . . . . . 85

Tab. 3.3 : Comparatif des résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

Tab. 4.1 : Calcul des fonctions d’évaluations sur l’exemple . . . . . . . . . . . . . . . . . . . 101

Tab. 4.2 : Calcul de la fonction Objectif (Fitness) sur l’exemple . . . . . . . . . . . . . . . 103

Introduction générale

4


Les systèmes automatisés deviennent de plus en plus complexes et lorsque des défaillances surviennent, les conséquences sur leur fonctionnement peuvent en être désastreuses. Afin de garantir des niveaux de performance de fonctionnement élevés, il est nécessaire d’implanter un modèle de surveillance et de diagnostic, permettant de détecter rapidement toute anomalie. Il est aussi indispensable de déterminer et de localiser précisément les éléments défaillants, afin de permettre une intervention efficace, pour la maintenance ou la reconfiguration du système.

Les travaux de recherche sur le diagnostic de fautes ont mobilisé ces dernières années une large communauté de chercheurs. Leur point commun est l’analyse structurelle, qui est un outil puissant permettant de déterminer de nombreuses propriétés des systèmes étudiés. Les algorithmes de surveillance sont tous basés sur le principe de la redondance des sources d’information. Cette redondance est obtenue par la comparaison des données réelles issues du processus et des données théoriques fournies par un type de modèle, ce qui permet de vérifier si l’information obtenue à un instant donné est conforme aux normes de fonctionnement normal.

Problématique

La problématique à l’origine de cette étude, est d’étudier la possibilité de l’occurrence de plusieurs défaillances (ou fautes) simultanément dans un système, et que celui-ci ne soit pas interrompu ou corrigé après la première faute. Le système de surveillance dans ce cas là doit, diagnostiquer la présence des différentes fautes en exploitant au mieux les propriétés structurelles du système étudié.

Le diagnostic multi-faute (MFD) identifie les fautes multiples dans un système, à partir d'un ou plusieurs symptômes et peut être utilisé comme une partie d'un système global de diagnostic ou bien comme un système à part. Son importance est évidente dans les systèmes complexes modernes, car ce sont des systèmes caractérisés par l’interconnexion de plusieurs composants et les relations décrivant les processus peuvent être de types différents (algébriques, différentielles, …). D’un autre coté, la complexité de ce type de diagnostic joue un rôle important dans la performance d’un système global.

L’objectif du travail présenté dans ce mémoire est d’arriver donc, à déduire les possibilités de combinaisons des effets de plusieurs fautes sur les composants d’un système, sachant que cette situation n’est pas prise en compte par les propriétés structurelles. En plus, et pour bien étudier le cas, plusieurs algorithmes sont présentés et deux d’entre eux sont complètement implémentés. L’un reposant sur l’approche habituelle qui consiste à trouver et à parcourir toutes les combinaisons possibles de fautes, avec tous ce qu’elle incombe comme inconvénients temporels et combinatoires. L’autre algorithme, utilise une technique évolutionnaire, basée sur les théories de l’évolution des espèces


5

biologiques, afin de déduire à partir d’éléments simples, les combinaisons de fautes adéquates.

Organisation du mémoire

Le présent mémoire se compose de quatre chapitres. Le premier, intitulé « Surveillance et diagnostic de fautes » est destiné à introduire les définitions et les concepts nécessaires dans le domaine du diagnostic de fautes et de la surveillance des systèmes. Les principales méthodes de diagnostic de fautes sont présentées et les méthodes fondées sur un modèle mathématique sont détaillées, en particulier, l’approche basée sur l’analyse structurelle.

Le deuxième chapitre présente la problématique du diagnostic multi-faute ainsi que les spécificités du comportement des fautes multiples dans un système. Une extension de la méthode de diagnostic FDI pour le diagnostic multi-faute y est présentée et discutée. D’autres approches pour le diagnostic multi-faute basées sur d’autres types de modélisation sont aussi présentées.

Dans le troisième chapitre intitulé « Panorama des algorithmes multi-fautes », quelques extensions de l’algorithme FDI adapté au cas des fautes multiples sont présentées. Ces extensions sont classées en plusieurs catégories : les algorithmes déterministes, les algorithmes heuristiques et les algorithmes approximatifs. La dernière partie est consacrée à une comparaison sur les propriétés et les résultats de ces différents algorithmes.

Le quatrième chapitre intitulé « Optimisation et implémentation des algorithmes » décrit une implémentation de deux algorithmes de diagnostic multi-fautes, à savoir, l’algorithme exact et l’algorithme génétique. Plusieurs améliorations sur ces deux algorithmes sont présentées ainsi que des exemples d’exécution. La dernière partie de ce chapitre, s’achève par une comparaison entre les résultats obtenus par les deux méthodes.

La conclusion générale enfin, commente les résultats obtenus et introduit les perspectives envisageables pour parfaire ce travail.

Chapitre 1 : Surveillance et diagnostic de fautes

6

1. Introduction

Les premiers travaux concernant la détection et la localisation de fautes proviennent des recherches dans le domaine médical par une application de systèmes experts en intelligence artificielle. E. H. Shortliffe [Sho 74] expose un système de diagnostic de maladies du sang où la connaissance représente l’expertise qu’a pu acquérir le médecin sur les relations qui existent entre les symptômes observés et les causes de dysfonctionnement du système à diagnostiquer (le malade). On peut aussi citer la publication de [Pot 77] à propos de l’utilisation de la redondance pour la détection de défauts de capteurs de type accéléromètre ou encore les livres de [Him 78] et de [Pau 81], posant les principes fondamentaux de la détection et du diagnostic de défauts.

Depuis ces travaux fondateurs, cette thématique a fait l’objet de nombreux travaux de recherche et a acquis une certaine maturité. Ces développements ont non seulement concerné la formalisation théorique des problèmes rencontrés et leur résolution mais également la mise en œuvre pratique sur des processus réels.

Compte tenu de l’importance des enjeux en termes de productivité (arrêt inutile des installations), de sécurité (anomalie non détectée) ou de qualité de production (mesure incorrecte d’une grandeur à contrôler), de nombreuses approches ont été utilisées pour apporter une contribution à la solution de ce problème. On distingue cependant, parmi les différentes méthodes, deux familles principales ; celles qui utilisent un modèle du système à surveiller et celles pour qui, seules les données acquises sur le processus considéré permettent de caractériser son mode de fonctionnement. Parmi les méthodes basées sur l’utilisation d’un modèle du processus, deux sous-familles importantes peuvent également être dégagées ; celles utilisant les techniques de l’automatique et celles recourant à l’intelligence artificielle [Coc 04].

Ce chapitre débutera par la présentation des notions générales de la surveillance des systèmes. Il s’agit de surveiller et contrôler l’exécution d’une opération ou la réalisation d’un travail accompli. Dans le contexte de l’automatisation, cela revient à amener et à maintenir un système en un point de fonctionnement choisi, et puis de surveiller qu’il ne s’en écarte pas, et si le fonctionnement n’est pas conforme aux prévisions, agir de façon à éviter des dommages sur l’installation. Parmi les tâches à réaliser, la surveillance (ou monitoring) s’appuie sur la capacité à reconnaître un comportement anormal et à le signaler. Les notions et les termes utilisés seront d’abord précisément définis (défaut, défaillance, diagnostic, détection, localisation, …etc). Les principales méthodes de diagnostic de fautes seront ensuite présentées (méthodes avec ou sans modèle). Enfin, on reviendra sur les méthodes de surveillance fondées sur un modèle mathématique du système à surveiller et on présentera de façon détaillée l’approche basée sur l’analyse structurelle pour établir un diagnostic complet du système à surveiller.


7

2. Principes et concepts généraux

La Fédération Internationale du Control Automatique (IFAC) a créée en 1991 un comité technique SAFEPROCESS qui organise des réunions tous les trois (03) ans, afin de standardiser les concepts et les définitions dans le domaine de la surveillance et du diagnostic de fautes pour le bien de l’industrie et de la communauté scientifique [Ise 97b].

2.1. Terminologie et définitions

Nous présentons dans ce paragraphe la définition des termes principaux utilisés dans le domaine du diagnostic ainsi que dans ce mémoire. Les définitions suivantes, résumées ici par ordre chronologique, sont proposées par le comité technique SAFEPROCESS de l’IFAC et sont aussi utilisées dans [Ise 97b] :

2.1.1. Etats et signaux

• Faute (fault) : Action, volontaire ou non, dont le résultat est la non prise en compte correcte d’une directive ou d’une contrainte exprimée par le cahier des charges.

• Défaut (defect) : Dérive inadmissible du comportement standard (habituel) ou acceptable, d’au moins une propriété caractéristique ou d’un composant du système.

• Défaillance (failure) : Interruption permanente de la capacité d’un système à effectuer ses fonctions attendues dans des conditions de fonctionnement spécifiées.

• Dysfonctionnement (Malfunction) : Irrégularité intermittente dans la réalisation des fonctions désirables d’un système.

• Erreur (Error) : Déviation entre une valeur mesurée ou calculée (d’une variable de sortie) et la valeur attendue, ou théoriquement correcte.

• Perturbation (Perturbation) : Entrée qui agit sur un système et dont le résultat est une déviation temporaire de l’état courant.

• Résidu (Residual) : Indicateur de défaut basé sur la différence entre les mesures et les calculs obtenus à partir du modèle.

• Symptôme (Symptom) : Changement d’une valeur observable de son comportement normal.

2.1.2. Fonctions

• Détection des défauts (Faults detection) : Détermination des défauts présents dans un système.

• Isolation des défauts (Faults isolation) : Détermination du type, de la localisation et des instants de détection des défauts.


8

• Identification des défauts (Faults identification) : Détermination de l’amplitude et du comportement temporel des défauts.

• Diagnostic des défauts (Faults diagnostic) : Détermination du type, de l’amplitude, de la localisation et des instants de détection des défauts.

• Surveillance (Monitoring) : Tâche continue (réalisée en temps réel) de détermination de l’état d’un système physique qui consiste à enregistrer les informations et indiquer les anomalies du comportement.

• Supervision (Supervision) : La surveillance d’un système physique et la prise de décisions appropriées en vue de maintenir son fonctionnement lors de l’apparition de défauts.

• Protection (Protection) : Moyens par lesquels un comportement potentiellement dangereux du système est maîtrisé, ou moyens par lesquels les conséquences d’un comportement dangereux sont évitées.

2.1.3. Propriétés des systèmes

• Fiabilité (Reliability) : Capacité d’un système à accomplir une fonction requise sous des conditions énoncées, pendant une période de temps donnée. Elle est mesurée en temps moyen entre les défaillances (MTBF : Mean Time Between Failure).

• Sureté (Safety) : Capacité d’un système à ne pas causer un danger pour les personnes, les équipements ou l’environnement.

• Disponibilité (Availability) : Probabilité qu’un système soit opérationnel de façon effective et satisfaisante à tout moment. Elle est mesurée en temps moyen de réparation (MTTR : Mean Time To Repair).

Pour la définition du terme « diagnostic des défauts », une autre définition existe dans la littérature et elle est donnée par [Ger 91] en précisant que le diagnostic de défaut inclut également la détection des défauts. C’est également la définition adoptée dans ce mémoire. Si la détection de défaut est exclue du terme de diagnostic, comme le propose le Comité Technique SAFEPROCESS, aucune expression ne permet de décrire le secteur en entier. Ce problème de définition est en partie résolu en adoptant l’abréviation FDI (Fault Detection and Isolation).

Par ailleurs, les défaillances peuvent aussi être classées selon leur origine ou bien selon leur degré d’importance ou de sévérité :

• Selon l’origine : Suivant le type du composant du système qui est à l’origine de la défaillance, on peut distinguer trois types :

� Défaillance de capteur : elle se produit lorsque la mesure fournie par un capteur ne correspond pas à la réalité (concerne les sorties du système).


9

� Défaillance d’actionneur : elle se produit lorsque l’actionneur ne réagit pas correctement à la commande qui lui est imposée (concerne les entrées du système).

� Défaillance du système : elle correspond à une modification permanente des caractéristiques physiques du système (telle qu’une fuite dans une cuve, une cassure d’une tuyauterie, une usure, …).

• Selon leur sévérité : Ce classement permet de décider quelle sera la suite du traitement à appliquer (traitement d’urgence, diagnostic,...) en fonction de la classe de la défaillance. On peut distinguer plusieurs classes :

� Défaillance absorbable : elle peut être ignorée, dans un premier temps au moins.

� Défaillance significative : elle nécessite un processus de traitement.

� Défaillance critique : elle nécessite une intervention d’urgence.

2.2. Principes de la surveillance

Le système de surveillance constitue une partie très importante du système d’information des processus de production automatisés. Les algorithmes de surveillance traitent les données des variables de commande (issues des actionneurs) et des variables mesurées (issues des capteurs), pour produire des données validées et enrichies. Les données validées sont celles dont la véracité a été « prouvée » par le système, par exemple, en garantissant le fonctionnement correct d’un capteur, ou en remplaçant une mesure erronée par une estimation.

Les algorithmes de diagnostic permettent de compléter la liste des prestations et puis, en fonction de la nature des défaillances localisées et de leur importance (fuite d’eau, défaut de calorifugeage, etc...), une planification des interventions pourra être établie. Ces algorithmes sont basés sur le principe de la redondance des sources d’information. La redondance est obtenue par comparaison des données réelles issues du processus et des données théoriques fournies par un modèle (connaissance a priori). La comparaison des données réelles (transmises par les capteurs) et celles théoriques permet de vérifier si l’information obtenue à un instant donné est conforme aux normes de fonctionnement normal (ou dans les limites fixées de tolérance).

Le diagnostic se réalise donc, en suivant les étapes suivantes (Fig. 1.1) :

1. L’acquisition des informations : Cette opération est destinée à obtenir les informations sur le processus réel à surveiller et celles fournies par la connaissance théorique du système. Elle se réalise à l’aide de capteurs dédiés.

2. La détection : On surveille le fonctionnement réel en testant la cohérence entre le modèle et les observations. Si celles-ci ne vérifient pas les équations du modèle, on en déduit que le fonctionnement réel n’est pas normal. Ces changements sont alors


10

détectés et traduits en termes de symptômes ou d’événements. On produit alors une alarme ou un résidu. Une procédure de décision permet ensuite de comparer ces résidus avec des seuils de tolérance afin d’éviter les risques de non-détection (faux négatif) ou de fausse alarme (faux positif).

3. La localisation (ou l’isolation) : Dans cette phase, un (ou plusieurs) modèle(s) de mauvais fonctionnement est (sont) utilisé(s) pour déterminer la (les) défaillance(s) présente(s). Cette étape se déclenche quand la comparaison ne correspond pas à un état normal de fonctionnement et que la procédure de détection a indiquée que c’est une vraie alarme.

4. L’identification : Lorsque la faute est localisée, il faut alors identifier les causes précises de l’anomalie. On fait alors appel à des signatures répertoriées et validées pour identifier les causes de dysfonctionnement.

Fig. 1.1 : Les étapes du diagnostic.

Eta

pe

d’identifica

tion

Capteurs

Comparaison

Décision

Poursuite du

fonctionnement

normal

Etat normal

Isolation

Identification

Processus réel

Données

théoriques

Résidus

Eta

pe d

e d

éte

ctio

n

Oui

Non

Eta

pe

d’iso

lation

Eta

pe d

’acq

uisitio

n


11

2.3. Caractéristiques d’un système de surveillance

Un système de surveillance idéal doit avoir les caractéristiques suivantes [Ven 02] :

• Stabilité dans la détection et le diagnostic : La détection et le diagnostic précoce impliquent une réponse rapide à une faute naissante. La difficulté principale d’atteindre ce but est que les signaux de faux diagnostics peuvent apparaître pendant le déroulement normal si le système de diagnostic de fautes est très sensible.

• Résolution : La capacité d’un système de diagnostic de fautes pour isoler, c’est-à-dire distinguer les différentes fautes, est un attribut important.

• Robustesse : Le diagnostic correct en présence de bruit et d’incertitudes doit être équilibré avec une performance tolérable. Des seuils de tolérance doivent être choisis d’une manière conservatrice en présence de bruit.

• Identification des nouveautés : Une exigence importante d’un système de diagnostic de fautes est de déterminer si la condition anormale détectée est connue ou non. Parfois, le système de diagnostic de fautes peut associer une nouvelle faute non reconnue avec une faute connue. Autrement, il pourrait associer la nouvelle faute non reconnue a une condition normale.

• Identification des fautes multiples : La capacité de diagnostiquer les fautes multiples peut être réalisée par un système de diagnostic de fautes s’il est conçu pour toutes les combinaisons de fautes possibles. Cependant, cette conception est du point de vue quantitatif, prohibitive pour les grands processus. De là, un système de diagnostic de fautes idéal doit modéliser l’effet combiné des fautes. Dans ce mémoire nous nous intéressons à ce cas particulier et nous détaillons plusieurs solutions possibles.

• Facilité d’explication : Le système de diagnostic de fautes doit fournir des explications à l’opérateur sur l’origine de la faute.

• Adaptabilité : Le système de diagnostic de fautes doit être capable de s’adapter facilement pendant l’utilisation. Ceci est important si l’on souhaite tenir compte du comportement dynamique du système.

• Exigence calculatoire raisonnable : La complexité du système informatique pourrait affecter les performances du système de diagnostic de fautes. D’un autre coté, un système de diagnostic de fautes simple avec peu d’exigences calculatoires pourrait avoir besoin de grandes capacités de stockage pour avoir des performances tolérables.

2.4. Cahier des charges de la surveillance

Le but principal du cahier de charge de la surveillance est la définition d’un sous-ensemble (sous-système) de composants du système que l’on souhaite surveiller pour des raisons de sécurité, de qualité, de production ou de maintenance [Bel 04]. On associe à chaque composant à surveiller, la relation du système qui matérialise son mode de comportement


12

normal et l’ensemble de ces relations est noté F. Ainsi, le cahier des charges de la

surveillance doit permettre de définir un sous-ensemble de relations FS ⊂ F ainsi qu’un sous-ensemble de variables (ou grandeurs physiques) qui doivent impérativement être connues. Il doit aussi permettre de stipuler un sous-ensemble d’inconnues qui ne sont pas mesurables physiquement [Car 96]. Il doit aussi préciser les composants et les défaillances associés qui doivent être détectés et/ou localisés.

Le cahier de charge de la surveillance peut aussi contenir les performances attendues en termes de détection, de prédiction de pannes et de reconfiguration du système. Pour cela, on peut déterminer trois (03) indices permettant de caractériser ces performances [Car 99] :

• La probabilité de fausse alarme (ou faux positif) : c’est-à-dire la détection d’une anomalie alors que le fonctionnement est normal.

• La probabilité de non détection (ou faux négatif) : c’est-à-dire la non détection d’une défaillance.

• Le délai de détection : temps imparti pour la détection d’une faute, et au-delà duquel, cette opération est obsolète.

Enfin, il est possible de définir dans le cahier des charges de la surveillance, la capacité de localisation qui indique la possibilité de déterminer l’origine de la défaillance, et aussi d’identifier la cause de la panne parmi les causes prises en compte par le système de surveillance. Dans le cas idéal, il serait souhaitable de pouvoir localiser et identifier toutes les causes de défaillance.

Dans le cadre de notre travail, les points essentiels que nous mentionnons dans le cahier des charges sont sous forme de besoins et de mécanismes pour une surveillance optimale des fautes multiples.


13

3. Classification des méthodes de diagnostic

3.1. Classification par approches

Les méthodes conventionnelles permettant d’automatiser la surveillance des systèmes complexes se classent généralement en deux grandes catégories [Maq 03] :

• Les approches qui se basent sur l’utilisation d’un modèle de comportement construit à partir de la physique du système ou d’une expertise humaine. Les méthodes qui en découlent sont appelées également méthodes internes de diagnostic. Elles impliquent une connaissance approfondie du fonctionnement sous la forme de modèles mathématiques qui devront obligatoirement être validés expérimentalement avant toute utilisation.

• Les approches qui supposent que la connaissance disponible sur le système se limite à son observation passée et présente. Ces méthodes supposent qu’aucun modèle n’est disponible pour décrire les relations de cause à effet et que la seule connaissance repose sur l’expertise humaine.

Notons cependant que cette répartition n’est pas très stricte car les systèmes experts ou les réseaux de neurones peuvent être utilisés pour élaborer des modèles de comportement des systèmes qui seront ensuite utilisés par des méthodes de diagnostic interne. De manière réciproque, les méthodes à base de modèles peuvent générer des indicateurs ou caractères qui pourront ensuite êtres classés à l’aide de méthodes de reconnaissance de forme de manière à émettre un diagnostic [Maq 03].

3.1.1. Le diagnostic à base de modèle

Les différentes approches de la détection de défauts basées sur l’utilisation de modèles peuvent être résumées à quelques méthodes génériques parmi lesquelles on recense l’approche à base d’observateurs d’événements (observateurs de Luenberger [Lue 71] ou filtres de Kalman [Kal 60]), l’approche à base d’estimateurs paramétriques (états) ou l’utilisation de systèmes experts. Selon la méthode, différents types de modèles sont utilisés. Par exemple, pour les approches utilisant l’estimation d’état ou l’estimation paramétrique, on utilisera des modèles analytiques alors que pour l’approche systèmes experts, on recourra à des modèles de type base de connaissances. Puisque le modèle sert directement comme référence pour la détection de défaillance, la qualité du résultat dépend directement de la qualité de ce modèle. La mise en œuvre de ces méthodes nécessite donc une modélisation précise. Cependant, de nombreux travaux ont été menés pour assouplir cette contrainte [Cor 02].

La détection de défaut basée sur l’utilisation de modèles peut être divisée en deux étapes principales : la génération de résidus et la prise de décision. Lors de la première étape, les signaux d’entrée et de sortie du système sont utilisés pour générer un résidu, ou


14

alarme, c’est-à-dire un signal mettant en évidence la présence d’un défaut. En général, en régime de fonctionnement normal, ce signal est statistiquement nul et s’écarte notablement de zéro en présence de défauts. La génération de résidus est propre à la méthode utilisée. Durant la seconde étape, les résidus sont analysés pour décider s’il y a ou non présence de défaut, sur quel composant du système il est intervenu (opération souvent appelée localisation), et dans certains cas, déterminer la nature du défaut et sa cause (identification). La décision peut s’effectuer à l’aide d’un simple test de dépassement de seuil sur les valeurs instantanées ou des moyennes de résidus, ou faire appel à la théorie de la décision statistique [Bas 93]. L’évaluation des résidus peut également être non booléenne ; elle consiste alors à attribuer un « facteur de croyance » à un ensemble d’hypothèses de défaillances. La combinaison des informations peut alors être effectuée à l’aide de la théorie de l’évidence ou en utilisant des fonctions floues. Cette décision peut également faire appel à la reconnaissance des formes [Dub 90] [Zwi 95]. D’un point de vue pratique, la logique de décision à seuils joue un rôle important, car la plupart des méthodes citées se ramènent, à terme, à un seuillage. Si le seuil choisi est constant, les entrées inconnues qui excitent le système perturbent la décision. Si le seuil est choisi trop petit, on observe beaucoup de fausses alarmes, et s’il est trop grand, les défauts de faible amplitude ne sont pas détectés. Il est donc indispensable d’utiliser des seuils adaptatifs qui évoluent en fonction du point de fonctionnement du processus surveillé.

La figure (Fig. 1.2) présente l’architecture générale de la détection de défauts basée sur l’utilisation de modèles. La génération de résidus s’effectue sur la base d’estimations (états ou paramètres) ou à l’aide d’un raisonnement heuristique. L’étape de décision permet ensuite de détecter, ou même de localiser les éventuels défauts.

Un modèle consiste de manière générale en un ensemble de variables Z, contraintes par un ensemble de relations R. L’ensemble Z est partitionné en variables observables K et en variables non-observables X. Par souci de performance, il est possible d’utiliser des modèles qualitatifs, dans lesquels les variables ont des domaines plus restreints. Il est possible par exemple dans une approche basée sur la cohérence, dans laquelle seul le comportement normal est modélisé, d’établir un ensemble de tests (Relations de Redondance Analytique) qui permet d’utiliser des variables booléennes. Dans le cas d’un système continu modélisé par un système d’équations différentielles linéaires, l’établissement de ces RRAs est la phase la plus importante de la modélisation.


15

Fig. 1.2 : Architecture générale de la détection de faute à base de modèles.

Les observations arrivent sous la forme de tuples contenant les variables observables (directement observées ou bien issues des tests sur les RRAs). Le système peut être soumis à plusieurs fautes ce qui entraîne son passage en mode de faute simple ou multiple. On associe à chaque mode de faute possible f, l’ensemble des observations qui peuvent être faites à partir du système lorsqu’il est dans ce mode. Cet ensemble d’observables est appelé la signature du mode de faute f et il est noté Sig(f ).

3.1.2. Le diagnostic sans modèle

Cette classe de méthodes est celle qui suppose que la connaissance disponible sur le système se limite à son observation passée et présente, et à l’analyse des données qu’il fournit pour décider de son état. Ces méthodes sont également appelées « méthodes externes de diagnostic ». Au sens strict, ces méthodes supposent qu’aucun modèle n’est disponible pour décrire les relations de causes à effets (le modèle de fonctionnement du processus). La seule connaissance repose sur l’expertise humaine confortée par un solide retour d’expérience. Dans cette catégorie, on trouve plusieurs méthodes basées sur l’intelligence artificielle. Au sens large, elle inclue la reconnaissance de formes, les systèmes experts et les réseaux de neurones artificiels.

Actionneur Système Capteur

Défauts

Perturbations

Adaptation des lois de commande

Génération des résidus Détection

Localisation

Sortie

Prise de décision

Modèle de référence

- Estimation d’état - Estimation paramétrique - Raisonnement heuristique

Module de diagnostic


16

Les méthodes de reconnaissance de formes constituent des outils privilégiés pour la classification de signatures associées aux modes normaux et anormaux de fonctionnement. Ces méthodes permettent l’élaboration d’algorithmes permettant de classer des objets dont l’aspect a varié par rapport à un objet type. En fait, il s’agit de définir à quelle forme-type une forme observée ressemble le plus.

Quant aux méthodes utilisant les réseaux de neurones artificiels, leur inconvénient majeur est le temps nécessaire pour la phase d’apprentissage. En effet, si celle-ci est trop courte, le système de diagnostic ne sera pas très efficace, car il n’aura pas une connaissance approfondie sur le système. Si celle-ci est trop longue, la mise en place du système de diagnostic risque d’être une opération très couteuse en termes de temps.

Le diagnostic par système expert, quant à lui, se base sur l’expérience disponible sur le système pour construire une table de correspondance permettant d’associer efficacement les observations aux diagnostics correspondants. L’expérience peut être fournie :

• Par un opérateur humain : Dans ce cas, la connaissance humaine doit être traduite en langage informatique ;

• Par un enregistrement éventuellement annoté des précédentes exécutions du système. Dans ce cas, un algorithme d’apprentissage automatique doit être utilisé.

Les principaux inconvénients des méthodes utilisant les systèmes experts sont :

• L’acquisition de l’expertise : L’expertise n’est disponible qu’après un certain temps d’utilisation du système, ce qui exclue l’application pour des systèmes critiques (centrales nucléaire ou robot spatiaux, par exemple). D’autre part, la complétude de l’expertise n’est jamais assurée. Ainsi, lorsqu’un comportement inconnu a lieu sur le système, le diagnostic fourni sera erroné.

• La taille du système expert : Puisque qu’un système expert capture toutes les observations possibles, il nécessite parfois une taille très importante tandis qu’un modèle du système serait plus compact. Il arrive cependant qu’au contraire, le système expert soit plus compact que le modèle puisqu’il ne comporte que les informations pertinentes pour le diagnostic.

• La non robustesse : en cas de modification même légère du système, le système expert doit être entièrement recalculé.

3.2. Classification par domaines

Deux communautés distinctes et parallèles de recherche utilisent l’approche à base de modèle pour le diagnostic. La communauté FDI qui s’est développée dans le domaine du contrôle automatique à partir des années soixante-dix et qui emploie les techniques de la théorie de contrôle et de la théorie de décision statistique [Pat 91b] [Ger 93] [Ise 97a] et la communauté DX, et qui se base sur l’intelligence artificielle [Rei 87] [Kle 87].


17

Bien que les principes soient les mêmes, chaque communauté a développé ses propres concepts, outils et techniques, guidées par des contextes de modélisation différents. En effet, les formalismes de modélisation utilisés appartiennent à des domaines techniques très différents : modèles analytiques et algèbre linéaire d’une part et modèles symboliques, qualitatifs et logique d’autre part.

3.2.1. L’approche par redondance analytique FDI (Automatique)

Au sein de la communauté « Automatique » le diagnostic se retrouve sous l’appellation « Fault Detection and Isolation » ou (FDI). Cette approche a été essentiellement adoptée par le Laboratoire d’Automatique et d’Informatique Industrielle de Lille (France) qui a réalisé des travaux très intéressants et qui a développé des algorithmes pour les différents cas de figures [Sta 89] [Tag 95] [Car 99] [Bus 02] [Mra 04] [Ost 05] en se basant sur les techniques de l’analyse structurelle et la génération de relations de redondances analytiques (RRAs) qui seront utilisées dans l’algorithme de diagnostic. Cependant, et parallèlement à cela, le Département d’Ingénierie Electrique de l’Université de Linköping (Suède) a développé une autre technique qui repose sur l’utilisation du plus petit ensemble de relations de consistance (MSS Sets) [Kry 02] [Rat 04] et qui possède plusieurs points de similitude avec l’algorithme de l’université de Lille.

Le diagnostic par FDI regroupe la détection d’une déviation de comportement qui donne lieu à la génération d’un symptôme (fonction détection) et l’isolation de la défaillance qui mène à la localisation de l’élément responsable de cette défaillance (fonction localisation). Cette tâche peut être décomposée en trois étapes [The 03] (voir la figure Fig. 1.3) :

Fig. 1.3 : Structure générale d’un système de diagnostic utilisant l’approche FDI [The 03].

Génération de résidus

Evaluation des résidus

Décision

Référence (Modèle)

Seuils

Signatures de référence

Observations

Résidus

Symptômes

Diagnostic


18

1. La génération des résidus : qui permet d’évaluer les différences par rapport aux conditions normales de fonctionnement ;

2. L’évaluation de ces résidus : les différences sont comparées avec des limites définies préalablement, et de cette comparaison résulte des symptômes générant un vecteur de cohérence. Un seul résidu suffit pour connaître l’existence d’un défaut au sein du système, plusieurs résidus sont nécessaires afin de trouver la cause du défaut ;

3. La décision : Consiste à comparer le vecteur de cohérence avec l’ensemble des signatures de référence, de bon et de mauvais fonctionnement, rassemblées dans un tableau de signatures, appelé également table de signatures.

3.2.1.1. Le modèle du système

En FDI, un système est composé d’un ensemble de composants et d’un ensemble de capteurs, qui fournissent un ensemble d’observations. Le modèle de comportement du système exprime les contraintes qui lient ses variables descriptives. Il est exprimé par un ensemble de relations, dont l’expression formelle dépend du type de connaissance utilisé (analytique, qualitatif, règles de production ou tables numériques, …). Il repose généralement sur une description basée sur les composants qui relie un ensemble de contraintes à chaque composant.

Le modèle du système SM est défini par un modèle comportemental BM, c’est-à-dire l’ensemble des relations définissant le comportement de système, ainsi qu’un modèle d’observation OM, c’est-à-dire l’ensemble des relations définissant les observations qui sont faites sur le système.

L’ensemble Z des variables est décomposé en un ensemble de variables inconnues X et

un ensemble de variables connues ou observées K = U ∪ Y (variable de référence U et variable mesurée Y).

3.2.1.2. Le problème du diagnostic

Définition 1.1 : un problème de diagnostic est défini par le modèle du système SM, un ensemble d’observations OBS et un ensemble de fautes F [Cor 02].

Pour les besoins du diagnostic, on définit l’ensemble {Fc} comme l’ensemble des fautes F qui peuvent se produire sur un composant c. L’ensemble des observations OBS est un

ensemble des relations de la forme vobs = val, où vobs ∈ K et val est dans le domaine de vobs.

3.2.1.3. Les relations de redondances analytiques

Une relation de redondance analytique (RRA) est une contrainte calculée à partir du modèle du système et qui ne contient que les variables observées, ce qui lui permet donc d’être évaluée à partir de n’importe quel ensemble OBS. On note r = 0, où r est le résidu de la RRA.


19

Les RRAs sont utilisées pour vérifier la cohérence des observations par rapport au modèle du système SM. Les RRAs sont satisfaites si le comportement de système observé satisfait les contraintes du modèle. Les RRAs peuvent être obtenues à partir du modèle de système en éliminant les variables inconnues. On verra par la suite, comment obtenir et évaluer les RRAs.

3.2.1.4. La table de signatures des fautes

En plus des relations de redondance analytiques, un concept fondamental dans l’approche FDI est celui de « signature de faute ». La signature théorique d’une faute peut être vue comme la trace attendue d’une faute sur les différents RRAs, étant donné le modèle du système.

Définition 1.2 : Etant donné un ensemble de RRAs R : Ri = 0, avec Card(R) = n, la signature (théorique) d’une faute Fj est donné par le vecteur binaire FSj = [s1j, s2j, ..., snj]

T

où sij est donné par :

s : R × F → {0,1}

(Ri, Fj) → sij = 1 si le composant affecté par Fj est utilisé dans Ri,

sij = 0 sinon.

Lorsque sij égale 0, l’occurrence de la faute Fj n’affecte pas la RRA Ri (val(Ri) = 0). D’autre part, lorsque sij est égale à 1, on suppose que l’occurrence de la faute Fj affecte la RRA Ri (val(Ri) ≠ 0). Cette interprétation suppose implicitement que l’occurrence de Fj est observable sur le résultat de Ri, c’est-à-dire que, si la RRA Ri est satisfaite, alors la faute Fj ne s’est pas produite. Cela est appelé la supposition d’exonération de faute simple (FS-exo).

Définition 1.3 : Quand un composant ne manifeste pas un comportement anormal (faute) au niveau des observations (RRA), il est exonéré [Cor 02].

Définition 1.4 : Etant donné un ensemble R de n RRAs, les signatures d’un ensemble de fautes F = {F1, F2, …, Fm} toutes réunies constituent la table de signatures FS de dimensions

n × m.

Cette matrice est la base de la localisation de défauts dans l’approche FDI, car elle fait correspondre les RRAs avec les fautes auxquelles elles sont sensibles.

3.2.1.5. Le diagnostic

Les ensembles de diagnostic dans l’approche FDI sont donnés en termes de fautes représentées dans la table de signatures. La génération de ces ensembles est basée sur une interprétation des colonnes de la table de signatures. Les RRAs sont instanciées par les valeurs observées OBS et les résidus associés sont déterminés, fournissant une signature


20

observée, qui peut être comparée avec les signatures théoriques de fautes. Cette comparaison constitue un problème décisionnel.

Définition 1.5 : La signature d’une observation donnée OBS est un vecteur binaire OS = [OS1, …, OSn]

T où OSi = 0 si et seulement si, val(Ri, OBS) = 0 et OSi = 1 sinon.

La première étape est de décider si une valeur de résidu est égale à zéro ou non, en présence de bruits et de perturbations. Ce problème a été largement étudié par la communauté FDI et il est généralement considéré comme un problème statistique ou décisionnel, utilisant les modèles de bruit et de perturbation [Bas 93].

La deuxième étape est de comparer la signature observée avec les signatures de fautes. Une solution à ce problème de décision est de définir un critère de cohérence comme suit :

Définition 1.6 : Une signature observée OS = [OS1, …, OSn]T est cohérente avec une

signature de faute FSj = [s1j, …, snj]T si et seulement si, OSi = sij pour tout i.

Définition 1.7 : Les ensembles de diagnostic sont donnés par les fautes dont les signatures sont cohérentes avec la signature observée.

Il faut noter que la communauté FDI a réalisé un travail important pour obtenir des résidus structurés, tel que chaque résidu est sensible à un sous-ensemble de fautes [Ger 93] [Sta 93], ce qui donne une structure spécifique à la table de signatures. La puissance de localisation d’un ensemble de résidus peut être calculée à partir des propriétés structurelles de la table de signatures.

3.2.1.6. La redondance par les ensembles MSS

Une partie de la communauté Automatique focalise son travail sur la recherche et l’amélioration des RRAs, alors que d’autre part, des chercheurs de l’université suédoise de Linköping présentent une autre variante des algorithmes du diagnostic. Cette nouvelle vue se base sur la recherche du plus petit ensemble de relations de consistance (MSS Sets : Minimal Structurally Singular Sets of equations).

Cet algorithme, a pour idée principale de trouver tous les ensembles de relations structurellement singulières possibles et ensuite de trouver le plus petit ensemble parmi eux, et qui possède les mêmes propriétés d’isolabilité qu’eux. Ensuite cet ensemble minimal (MSS) est utilisé pour générer les résidus et obtenir une table de signatures [Kry 02].

Définition 1.8 : Un ensemble fini d’équations C est structurellement singulier (SS) par rapport à l’ensemble des variables X si |C| > |varx(C)|, où |C| est le nombre d’éléments dans C et |varx(C)| est le nombre de variables inconnues dans C.

Définition 1.9 : Un ensemble structurellement singulier est un ensemble structurellement singulier minimal (MSS) si aucun de ses sous-ensembles n’est structurellement singulier.


21

Donc si un ensemble est structurellement singulier, le nombre de variables qui apparaissent dans cet ensemble est plus petit que le nombre d’équations dans cet ensemble. Ceci implique que c’est un système surdéterminé. Le MSS est minimal dans le sens où c’est un système surdéterminé avec seulement une relation redondante. A partir d’un ensemble qui est structurellement singulier, il est possible de trouver plusieurs ensembles MSS différents [Rat 04].

3.2.2. L’approche de diagnostic logique DX (IA)

Contrairement aux techniques utilisées en automatique classique où l’on traite les problèmes numériquement en utilisant les propriétés des équations, en intelligence artificielle, on travaille essentiellement en symbolique. Les problèmes sont alors combinatoires et l’on utilise la logique ; on cherche à représenter les connaissances de sens commun, à modéliser la façon dont un individu raisonne. L’intelligence artificielle apporte des solutions intéressantes aux problèmes de supervision, comme un outil de plus dans la panoplie des techniques utilisées [Gen 96].

C’est Reiter dans [Rei 87] qui a proposé en premier, la théorie logique du diagnostic. Cette théorie est souvent appelée le diagnostic des premiers principes ; c’est-à-dire qu’étant donné une description d’un système et des observations sur son comportement qui rentrent en conflit avec la manière dont il est censé se comporter, le problème est de déterminer les composants qui, quand ils sont supposés ne pas fonctionner normalement, retournent une cohérence avec le comportement observé.

Cette approche, appelée aussi, approche basée sur la cohérence, a était par la suite développée et formalisée dans [Kle 87] [Kle 06].

3.2.2.1. Le modèle du système

La description du comportement du système est orientée vers les composants et repose sur la logique de premier ordre. Les composants sont des éléments soumis aux fautes et cela fait partie du diagnostic du système.

Définition 1.10 : Un modèle du système est une paire (SD, COMPS) où : SD est la description de système, représentée par un ensemble de formules logiques de premier ordre avec égalités, et COMPS représente les composants du système par un ensemble fini de constantes [Cor 02].

La description du système emploie un prédicat spécifique AB, qui signifie

« Abnormal ». ¬AB(c) avec c appartenant à COMPS décrit le cas où le composant c se comporte correctement.

Les formules décrivant le comportement des composants sont généralement exprimées par des contraintes et nécessitent un solveur de contraintes pour être traitées. En l’absence d’un tel solveur, elles doivent être calculées manuellement.


22

3.2.2.2. Le problème du diagnostic

Un problème de diagnostic résulte de la non-conformité entre le comportement normal d’un système décrit par son modèle et un jeu d’observations.

Définition 1.11 : Un problème de diagnostic est un triplet (SD, COMPS, OBS) où (SD, COMPS) est le modèle du système et OBS est un ensemble d’observations (formules de premier ordre) [Maq 03].

3.2.2.3. Le diagnostic

Un diagnostic est une conjecture que certains composants du système se comportent incorrectement. Cette conjecture doit être compatible avec les connaissances sur le système et avec les observations.

Ainsi, un diagnostic est donné par une désignation d’un mode comportemental, AB ou ¬AB, pour chaque composant du système de façon consistante avec les observations et le modèle.

Définition 1.12 : Un diagnostic pour (SD, COMPS, OBS) est un ensemble de

composants ∆ ⊆ COMPS tel que : SD ∪ OBS ∪ { AB(c) | c ∈ ∆} ∪ {¬AB(c) | c ∈ COMPS

– ∆} est satisfiable. Un diagnostic minimal est un diagnostic ∆ tel que ∀∆’ ⊂ ∆, ∆’ n’est pas un diagnostic [Maq 03].

Proposition 1.1 : si toute occurrence d’un littéral AB dans la forme clausale de SD ∪

OBS est positive, ce qui est en particulier le cas en l’absence de modèles de fautes et de modèles d’exonérations, les diagnostics minimaux sont suffisants pour caractériser tous les diagnostics, c’est-à-dire que les diagnostics sont exactement les sur-ensembles des diagnostics minimaux [Cor 02].

3.2.2.3.1. Les R-conflits

Une méthode directe pour calculer les diagnostics est un algorithme de génération et de tests où des sous-ensembles de composants sont sélectionnés, générant d’abord les ensembles minimums parmi-eux, puis évalués pour la satisfiabilité. Cependant, cette méthode reste inefficace. Une autre méthode basée sur le concept d’ensemble de conflit a été proposée et elle est à la base de la plupart des algorithmes mis en œuvre en DX. Ce concept a été présenté par [Rei 87] et il est désigné par « R-conflit ».

Définition 1.13 : un R-conflit pour (SD, COMPS, OBS) est un ensemble de composants

C = {c1..., ck} ⊆ COMPS tel que SD ∪ OBS ∪ {¬AB(c) | c ∈ C} est insatisfiable, c’est-à-

dire que : SD ∪ OBS |= ⋀ ��(�)�∈ . Un R-conflit minimal est un R-conflit, qui n’inclut

strictement aucun R-conflit [Cor 02].

Un R-conflit peut être interprété comme suit : au moins un des composants du R-conflit est défectueux par rapport aux observations, ou de façon équivalente, il est impossible que tous les composants du R-conflit se comportent normalement.


23

3.2.2.3.2. Calcul des diagnostics minimaux en utilisant les R-conflits

En employant les R-conflits minimaux, il est possible de donner une caractérisation aux diagnostics minimaux, et de fournir une base pour leur calcul. Cette caractérisation est basée sur la définition de l’ensemble minimal de candidats (ou Minimal Hitting Set).

Définition 1.14 : un ensemble candidat pour une collection d’ensembles C est un ensemble

H ⊆ ∪ {S / S ∈ C} tel que H ∩ C ≠ { } pour chaque S ∈ C. Un ensemble candidats croise chaque ensemble de la collection. Un ensemble candidat est minimal si et seulement si, aucun de ses sous-ensemble n’est un ensemble candidat pour C. Evidemment, pour calculer les jeux de candidats minimaux d’une collection d’ensembles C, seuls les éléments minimaux de C doivent être considérés [Cor 02].

Proposition 1.2 : ∆ est un diagnostic minimal pour (SD, COMPS, OBS) si et seulement

si ∆ est un ensemble candidat minimal pour l’ensemble des R-conflits de (SD, COMPS, OBS) [Cor 02].

Une caractérisation plus approfondie des conflits et des ensembles de candidats avec des modèles de fautes et d’exonérations, peuvent être trouvés dans [Kle 92].


24

4. Le diagnostic par l’analyse structurelle

L’analyse structurelle est l’analyse des propriétés structurelles d’un système, c’est-à-dire, des propriétés qui sont indépendantes des valeurs réelles des paramètres (propriétés qui sont vraies presque partout dans l’espace des paramètres) [Sta 00]. Cette analyse se base sur l’existence de relations entre es variables et les contraintes dans un modèle. En effet, dans les modèles, les variables et les contraintes sont reliés via des fonctions analytiques. Dans l’analyse structurelle, seul le fait qu’une variable apparaît dans une équation, est considéré. Cette façon de voir le système permet d’effectuer des traitements sur la structure en évitant la complexité des fonctions analytiques.

L’application de l’analyse structurelle peut être, par exemple, dans l’industrie des processus où les systèmes sont très complexes et qu’il est difficile de réaliser des modèles détaillés des processus en entiers. Avec l’analyse structurelle on peut, à partir d’un modèle analytique existant, extraire la structure du modèle, exécuter une analyse d’isolabilité de faute et savoir s’il y a des parties spécifiques qui doivent être modélisées plus encore afin d’obtenir l’isolabilité de faute désirable.

Cette approche a été introduite dans les années 70 pour analyser certaines propriétés structurelles telles que la commandabilité et l’observabilité structurelle des systèmes [Lin 74]. Sa mise en œuvre pour la détection et la localisation des fautes remonte entre autres aux travaux de Declerck [Dec 91]. Cependant, on peut constater que trois écoles différentes travaillent sur ce domaine de recherche. Ces différentes écoles peuvent être classées par rapport au modèle adopté pour représenter la structure du système. Ces écoles sont [Dus 05] :

1. Les bond-graphs : L’outil de modélisation bond-graph a été défini par Paynter [Pay 61]. C’est une représentation graphique des systèmes physiques qui montre explicitement les transferts énergétiques entre les différentes parties du système. La modélisation par bond-graph est en plein essor dans le monde industriel, notamment dans les domaines de l’automobile et de l’énergie.

2. Les équations d’état : Dans cette représentation, nous pouvons extraire trois matrices structurées : celle qui met en évidence la structure des interactions des variables d’état entre elles, celle qui met en évidence la structure des liens entre les commandes et les variables d’état et celle qui met en évidence la structure des liens entre les variables d’état et les mesures (sorties). Le système est alors représenté par un digraphe orienté.

3. Graphe biparti : Le troisième modèle est un modèle général qui considère le système comme un ensemble de variables reliées entre elles par un ensemble de relations ou « contraintes ». Cette manière de modéliser un système, permet de le représenter par un graphe biparti, non orienté initialement. Une matrice d’incidence (variables - contraintes) structurelle peut lui être associée. Cette représentation sera adoptée dans la suite de ce mémoire.


25

Dans cette partie, nous allons décrire les étapes principales pour réaliser une analyse structurelle.

4.1. Le modèle comportemental du système

Le modèle de comportement de chaque composant du système exprime les contraintes qu’impose ce composant aux variables qui lui sont liées. On peut ainsi associer à chaque composant un ensemble de relations dont l’expression dépend du type de connaissance disponibles sur l’activité du composant à modéliser. Les modèles de comportement des composants du système peuvent avoir des représentations variées. Ils peuvent être linéaires, non-linéaires, statiques, dynamiques, qualitatifs, à base de règles d’évolution ou de tables numériques (par exemple pour des modèles bond graphs) [Haf 97].

Quand le comportement attendu est calculé, il est basé sur un modèle où les fautes sont supposées inexistantes et cela pour décrire le système dans un mode de fonctionnement normal. Si le comportement attendu ne correspond pas aux observations, certains tests de diagnostics vont déclencher une alarme. En déterminant quels tests ont réagi et en connaissant quelles sont les fautes qui peuvent influencer chaque test, un diagnostic peut être fait.

Le choix des tests de diagnostics est important. Chaque test consiste en une Relation de Redondance Analytique, RRA (appelé aussi, relation de cohérence ou relation de parité) [Maq 03]. Une RRA est une équation basée seulement sur les signaux connus, comme les signaux des actionneurs ou des capteurs. Elle est toujours égale à zéro lorsqu’aucune faute n’est présente et diffère de zéro en cas de présence d’un certain ensemble de fautes. Le signal résultant de la RRA est appelé un résidu.

Un résidu est un signal généré à partir des mesures et d’un modèle mathématique. Idéalement, un résidu doit être nul en l’absence de fautes et s’éloigner significativement de zéro en présence de pannes. Ceci n’est possible que si la modélisation du système est extrêmement précise. Avec des erreurs de modélisation et des bruits de mesures, un résidu ne peut pas rester identique à zéro en l’absence de pannes. Il en résulte que l’évaluation de résidu n’est pas une tâche triviale et une approche possible est de la formuler dans un cadre statistique.

Dans la Figure (Fig. 1.4) un résidu est montré. On peut voir qu’il est quasi-nul jusqu’au temps t=5, ce qui signifie qu’aucune faute n’a été détectée. A t=5 il réagit à cause d’une faute. En créant plusieurs résidus, chacun sensible à un ensemble différent de fautes, le diagnostic peut être réalisé.


26

Fig. 1.4 : Exemple de deux résidus. A t=5 l’un des résidus répond à une faute [Rat 04].

Prenons un autre exemple d’un système de diagnostic basé sur trois résidus. Chaque résidu étant sensible aux fautes selon la table ci-dessous :

f1 f2 f3

r1 1 0 0

r2 1 1 0

r3 0 1 1

Tab. 1.1 : Matrice de sensibilité aux fautes.

A partir de la Figure (Fig. 1.5), on peut déduire que c’est la faute f2 qui s’est produite. Ce résultat est déduit comme suit : Pour le résidu r2, f3 n’est pas la cause de la réaction puisque r2 n’est pas sensible à f3 selon la table de sensibilité. Aussi, f1 n’a pas pu causer la réponse dans r3. Il ne reste que la faute f2.

Fig. 1.5 : Exemples de résidus [Rat 04].

(a) Le résidus r1 sensible à la faute f1.

(b) Le résidus r2 sensible aux fautes f1 et f2.

(c) Le résidus r3 sensible aux fautes f2 et f3.

0 1 2 3 4 5 6 7 8 9 10

1,4

1,2

1

0,8

0,6

0,4

0,2

0

-0,2

-0,4


27

4.2. Le modèle structurel

L’objectif de l’analyse structurelle est de dégager les propriétés structurelles du système qui serviront à la mise en œuvre du système de surveillance. Le modèle structurel est obtenu à partir du modèle de comportement, en ne gardant que les informations qui expriment l’existence de relations entre les variables, sans prendre en compte leur forme particulière [Bel 06].

Le besoin d’un formalisme unifié pour déterminer les éléments communs des différents modèles des composants justifie l’approche structurelle. Nous allons définir un modèle structurel à partir d’un modèle analytique. Un système peut mathématiquement, être décrit par un ensemble d’équations, qui à leur tour, se composent de variables.

Pour tout système S nous pouvons définir les ensembles suivants : F, l’ensemble des relations (où contraintes), X, l’ensemble des variables inconnues (par exemple états internes, le bruit et les fautes), C, l’ensemble des variables connues (par exemple les signaux des capteurs et actionneurs) et Z l’ensemble de toutes les variables du système (Z =

X ∪ C).

Dans l’exemple suivant, un petit système est utilisé pour montrer comment les relations et les variables sont répartis dans les différents ensembles. Considérons un petit système avec deux états x1, x2, deux signaux de capteurs y1, y2, un signal d’actionneur u :

Avec la notation introduite, les différents ensembles contiendront les éléments suivants :

F = { f1, f2, f3}

Z = C ∪ X

X = {x1, x2} ; C = {u, y1, y2}

Le modèle structurel est donc défini par une application binaire S tels que:

S : F × Z → {0.1}

S (f, z) = 1 si z apparaît dans la relation f, 0 sinon.

Comme on l’a vu, c’est les relations entre des contraintes de F et les variables de Z qui nous intéressent. Pour représenter ces relations, une matrice appelée « matrice d’incidence » peut être employée. Dans cette matrice les lignes correspondent aux

f1 : x1 = x2 + u

f2 : y2 = x2

f3 : y1 = x1


28

contraintes et les colonnes aux variables. Dans le tableau (Tab. 1.2), on présente la matrice d’incidence du système de l’exemple précédent.

x1 x2 u y1 y2

f1 1 1 1 0 0

f2 0 1 0 0 1

f3 1 0 0 1 0

Tab. 1.2 : Matrice d’incidence de l’exemple.

L’avantage de cette représentation est quelle est facile à utiliser comme entrée pour l’algorithme de diagnostic. Cependant, il existe d’autres façons de représenter le système structurel, comme par exemple, les graphes bipartis.

Définition 1.15 : Un graphe biparti est un graphe qui se compose de deux ensembles disjoints de nœuds tels que, chaque arc possède un nœud dans le premier ensemble et l’autre dans le deuxième ensemble [Ber 75].

Les deux ensembles de nœuds disjoints dans notre cas sont les contraintes et les variables. Les arcs entre eux représentent les relations. La figure (Fig. 1.6) présente le graphe biparti du système de l’exemple précédent.

Fig. 1.6 : Le graphe biparti du système.

L’avantage d’utiliser les graphes bipartis est que l’on peut utiliser des résultats de la théorie des graphes. Un modèle structurel peut donc être défini comme suit, en employant la théorie des graphes.

Définition 1.16 : Le modèle structurel du système composé d’un ensemble de contraintes F et d’un ensemble de variables Z, peut être représenté par un graphe biparti G(F, Z, A)

où A ⊂ F × Z est l’ensemble des arcs défini par : (fi, zj) ∈ A si la variable zj apparait dans la contrainte fi [Sta 00].

Les deux représentations sont équivalentes et le choix d’employer l’une ou l’autre dépend de l’application.

Contraintes

Connexions

Variables

Nœuds Arcs (ou arrêtes) Nœuds y1 x1 u x2 y2

f3 f1 f2


29

4.2.1. Prise en compte de variables supplémentaires

4.2.1.1. Le cas des systèmes dynamiques

Jusqu’ici, nous nous sommes basé sur un système statique, mais beaucoup de systèmes réels sont dynamiques. Il est donc nécessaire de trouver une façon de traiter ce genre de systèmes et de manipuler les dérivées. Considérons par exemple, le système suivant :

f1 : x1 = x2 + u

f2 : y = x1

En employant les mêmes techniques vues précédemment, son graphe biparti est le suivant (les variables connues sont représentés en pointillés pour les séparer des variables inconnues).

Fig. 1.7 : Le graphe biparti pour un système dynamique.

Comme on peut le voir dans la première partie de la figure (Fig. 1.7), il y a deux variables inconnues, x2 et ẋi et seulement une connue, u. Il est donc impossible de calculer x2 et ẋi

seulement à partir de u. Dans la deuxième partie, il y a une variable connue y, et une inconnue x1, qui peut être calculée.

En ajoutant l’information que ẋ est une dérivée de x, les deux parties peuvent être combinées et toutes les variables inconnues peuvent être calculées. Cependant, cela peut être fait de différentes manières :

1. Connexion par contrainte différentielle : la variable et sa dérivée sont considérés comme étant deux variables différentes connectées via la contrainte différentielle. Le

modèle est étendu par des équations différentielles, comme x = dx/dt pour chaque variable différenciée (ajout de contraintes différentielles supplémentaires) [Pat 00].

2. Différentiation structurelle : la variable x et sa dérivée x sont considérés comme étant deux variables différentes et elles sont combinées via la différentiation structurelle. Cette différentiation peut être répétée plusieurs fois, avec une condition d’arrêt sur le nombre de dérivation par exemple [Rat 04].

3. Traitement des variables dynamiques comme statiques : la variable x et sa dérivée ẋ sont considérées comme étant structurellement les mêmes [Cor 02].

u x2 x1 y x1

f1 f2


30

Par la suite nous adopterons la dernière approche qui considère la variable et sa dérivée comme étant deux variables différentes mais faisant agir les mêmes contraintes.

4.2.1.2. La gestion des variables de défaillance

Pour assurer la surveillance du système, la prise en compte des défaillances est nécessaire afin de caractériser le comportement défaillant du système. En tenant en compte de ces défaillances, trois cas sont possibles [Ben 07] :

• Indiquer les équations (contraintes) du modèle qui ne sont plus valides en cas de défaillances, c’est le cas le plus élémentaire.

• Décrire comment sont modifiées les équations de fonctionnement normal lorsqu’une défaillance survient, ceci est fait grâce à des variables supplémentaires (variables de défaillances).

• Modéliser l’évolution dynamique de la défaillance ; on fait appel dans ce cas, à des équations supplémentaires liant les variables de défaillances pour enrichir le modèle bon fonctionnement du système.

4.3. Structure et redondance

La redondance peut être décrite comme étant l’information supplémentaire dans un système, et utilisée pour vérifier des résultats précédents. Elle existe lorsque le nombre d’équations est supérieur au nombre de variables inconnues, c’est à dire quand le système est surdéterminé.

Considérons l’exemple suivant :

f1 : x1 = x2 + u

f2 : y2 = x2 + fy2

f3 : y1 = x1

Le système possède deux variables inconnues, x1 et x2 et trois contraintes. Deux contraintes sont nécessaires pour calculer x1 et x2 et la redondance est présente avec la troisième contrainte. Par exemple, x1 peut être calculé par f3 et x2 par f2. Insérées dans f1, la relation devient :

y1 - y2 - u = 0

Cette nouvelle relation est une RRA. Notons que seules les variables connues sont utilisées.

4.3.1. Extraction de la partie surdéterminée d’un système

Ayant un modèle structurel, il n’est pas toujours facile de trouver les parties redondantes. Actuellement, il y a des outils qui permettent d’extraire la partie d’un système qui contient de la redondance. La méthode la plus connue est celle appelée la « décomposition


31

canonique » qui utilise seulement les permutations des lignes et des colonnes de la matrice d’incidence pour diviser le système en trois parties [Dul 58] :

• La partie sous-déterminée, notée S −, contient plus de variables que de contraintes et donc il y a infiniment de solutions.

• La partie juste-déterminée, S 0, contient autant de variables que de contraintes et donc toutes les variables peuvent être calculées.

• La partie surdéterminée, S +, contient plus de contraintes que de variables et donc toutes les variables peuvent être calculées et vérifiées.

Fig. 1.8 : Décomposition canonique d’un système arbitraire [Dul 58].

En pratique, cette décomposition peut être faite sur le logiciel « MatLab » par la commande « dmperm », dont le principe a été développé par Duhlmage et Mendelsohn [Duh 58]. Puisque les parties sous et juste-déterminés ne contiennent aucune redondance et ne sont donc d’aucun intérêt, c’est seulement la partie surdéterminée du système qui sera considéré. L’exemple de la figure (Fig. 1.9) montre comment réaliser une décomposition.

La partie (a) de la figure représente la structure initiale d’une matrice d’incidence. Elle consiste en neuf contraintes et huit variables inconnues. Il est difficile à partir de cette représentation de déterminer s’il existe une redondance. Après l’utilisation de la commande dmperm, la matrice est décomposée et la nouvelle structure est représentée dans la partie (b) de la figure. Le sous-système surdéterminé consiste en trois variables inconnues et cinq relations, {3, 4, 6, 8, 9}.

n variables

m c

on

trai

nte

s

Equations redondantes

S -

S 0

S +

X

0 0 0… 0


32

Fig. 1.9 : Le système initial est décomposé. Le bloc inférieur droit est la partie surdéterminée.

4.3.2. Le couplage : première étape pour trouver les RRAs

Une fois que la redondance du système est garantie, nous pouvons commencer à chercher les RRAs. Le but de cette section est de trouver une méthode pour créer les RRAs.

La partie surdéterminée peut être divisée en deux parties, une partie juste déterminée où les variables inconnues peuvent être calculées et une partie redondante où les résultats peuvent être testés avec les relations redondantes. La connexion entre les variables et les relations est appelé couplage (matching).

Notons que les relations redondantes ne sont pas toujours les mêmes et en n’employant que des permutations de lignes, on pourra avoir plusieurs possibilités.

Pour chacune de ces relations redondantes, on peut montrer qu’une RRA peut être créée. Le nombre de RRAs possible est donc le nombre de correspondances (couplages) différentes entre variables et relations.

Nous avons vu que pour calculer les variables inconnues, le nombre de contraintes doit égaler au nombre de variables inconnues. Un couplage est utilisé pour représenter cette calculabilité en assignant une contrainte à une variable. C’est-à-dire que l’équation assignée est utilisée pour calculer la variable. Ceci implique que dans un couplage la contrainte et la variable ne peuvent être couplés qu’une seule fois. Dans un couplage complet, toutes les variables doivent être couplées avec des contraintes.

Dans la matrice d’incidence un couplage peut être matérialisé, par exemple, par des valeurs entourées. Un couplage complet correspond donc, au cas où, pour toute variable (chaque colonne), on a une et seulement une valeur entourée. Quant aux contraintes, chaque ligne peut avoir au maximum une valeur entourée.

1

2

3

4

5

6

7

8

9

7

2

1

5

8

9

3

6

4

(a) Le système initial (b) Le système décomposé

1 2 3 4 5 6 7 8 8 3 5 1 6 4 7 2


33

L’exemple suivant montre deux couplages différents possibles, correspondant à la matrice d’incidence de l’exemple précédent. Dans le graphe de la figure (Fig. 1.10 (a)), les variables connues sont en pointillés. Une redondance se trouve dans c3 où la valeur calculée de x1 peut être comparée à celle donnée par la variable du capteur y1. Une autre possibilité de couplage est présentée dans la figure (Fig. 1.10 (c)). Notons que les variables connues ne doivent pas être couplées, leur but ici est seulement de faciliter la compréhension de la structure du système.

Dans la théorie des graphes, il existe plusieurs algorithmes qui permettent de trouver les différents couplages dans un graphe biparti et de spécifier les couplages complets et les couplages maximaux [Dul 58] [Cha 93] [Iza 02]. En plus, plusieurs couplages maximaux distincts peuvent donner lieu au même sous-ensemble de RRAs [Car 99].

Définition 1.17 : Un couplage dans un graphe biparti est un sous-ensemble d’arcs qui n’ont aucun nœud en commun. Si tous les nœuds correspondants aux variables ont des arcs dans le couplage, alors on dit que c’est un couplage complet sur les variables. Si le maximum des nœuds sont utilisés dans le couplage, on dit que c’est un couplage maximal [Ber 75].

Fig. 1.10 : Deux couplages représentés par des graphes bipartis et leurs matrices d’incidences

respectives.

y1 x1 u x2 y2

f3 f1 f2

y1 x1 u x2 y2

f3 f1 f2

x1 x2 u y1 y2

f1 1 1 1 0 0

f2 0 1 0 0 1

f3 1 0 0 1 0

x1 x2 u y1 y2

f1 1 1 1 0 0

f2 0 1 0 0 1

f3 1 0 0 1 0

(a) Le premier couplage

(c) Le deuxième couplage (d) La matrice d’incidence du deuxième couplage

(b) La matrice d’incidence du premier couplage


34

Pour représenter le fait que dans une équation, toutes les variables sauf celles couplées doivent être connues, des arcs orientés sont introduits. Si un arc pointe vers une variable cela signifie que cette variable est donnée par cette contrainte. Si un arc pointe vers une contrainte cela signifie que la variable est nécessaire dans cette contrainte afin de calculer une autre variable. Autrement dit, pour qu’un couplage soit complet, toutes les variables inconnues doivent posséder un et seulement un arc qui pointe vers elles.

Dans la figure (Fig. 1.11) les deux graphes de l’exemple précédents sont représentés par des graphes bipartis dirigés.

Fig. 1.11 : Les graphes orientés.

Avec ces arcs orientés, un ordre de calcul est introduit. Dans la figure (Fig. 1.11 (a)) les calculs commencent par y1, u et y2 et d’après la direction des arcs, les calculs s’arrêteront à la contrainte redondante f3, qui sera ensuite utilisée pour créer une RRA. Dans le cas d’absence de fautes, la RRA basée sur cette contrainte redondante doit être nulle. Dans la figure (Fig. 1.11 (b)) toutes les variables de la contrainte f1 sont connues et seront utilisées pour créer une RRA.

Notons que le nombre de couplages complets possibles dans un graphe biparti est un problème de complexité exponentielle. Cependant, des algorithmes avec une complexité polynômiale existent [Ber 75].

Dans [Bel 06] une autre méthode pour l’extraction des RRAs est présentée. Cette méthode consiste à énumérer les cycles dans un graphe triparti au lieu d’énumérer les couplages dans un graphe biparti. On obtient ainsi un meilleur résultat combinatoire.

Basés sur la théorie des matroïdes [Haf 00], cette méthode engendre certains résultats sur le nombre minimum de cycles qui assure l’isolabilité du système de surveillance qui peuvent être appliqués en vue d’améliorer la procédure d’énumération. Il est prouvé que le calcul de tout les cycles du graphe triparti et donc, des RRAs, se fait en un temps polynômial.

y1 x1 u

x2 y2

f3

f1

f2

zéro

y1 x1 u

x2 y2

f3

f1

f2

zéro

(a) Graphe orienté du 1er couplage (b) Graphe orienté du 2ème couplage


35

4.3.3. Relations de redondance analytique

Les relations de redondance analytique RRAs, (appelé aussi équations de parités), sont des relations dont la structure ne contient que des variables et des paramètres connus. Elles peuvent donc être directement évaluées.

Une relation de redondance analytique permet de vérifier la cohérence entre les valeurs des variables et ne peut être vérifiée que lorsque le comportement du système correspond au comportement issu du modèle. Une défaillance sur la mesure d’une variable ou un changement de la valeur d’un paramètre de la relation de redondance entraînera la non vérification de celle-ci [Cas 94b] [Sta 00].

Définition 1.18 : Le support d’une relation de redondance analytique r i est l’ensemble des composants (colonnes dans la table de signatures) avec un élément non nul sur la ième ligne (correspondant à cette RRA) [Cor 02].

Définition 1.19 : La portée d’un composant cj est l’ensemble des RRAs (lignes de la table de signatures) avec un élément non nul sur la colonne correspondant à cj [Cor 02].

Une RRA est donc une relation décrivant une combinaison de variables connues de façon à être toujours nulle en l’absence de fautes et non nulle lorsqu’un certain ensemble de fautes se produit. Considérons l’exemple initial :

f1 : x1 = x2 + u

f2 : y2 = x2

f3 : y1 = x1

Supposons que x1 et x2 soient couplés avec f3 et f2 respectivement. Cela implique que la première équation est redondante et quelle peut être utilisée pour créer une RAA. La RRA est construite en remplaçant x1 et x2 dans f1 par les variables de capteurs dans f2 et f3.

x1 = y1 (f3)

x2 = y2 (f2)

Ensuite l’équation c1 devient donc :

y1 = y2 + u ⇔ y2 - y1 + u = 0

On obtient ainsi une relation redondante qui n’utilise que des variables connues et mesurables (u, y1, y2).

4.3.3.1. Exemple récapitulatif

Dans cet exemple, un couplage va être utilisé pour trouver une RRA qui pourra être employée dans le système de diagnostic. Soit les contraintes suivantes :


36

f1 : x3 = y3

f2 : x1 = 2x2 + u

f3 : x1 + x2 = y2

f4 : x2 = x3 – x1

f5 : x2 + x3 = y1

Le système se compose de trois variables inconnues { x1, x2, x3}, un actionneur {u} et trois capteurs {y1, y2, y3}. Le système est surdéterminé car le nombre de contraintes (5) est supérieur au nombre de variables inconnues (3). Considérons le couplage suivant :

f1 - x3

f3 - x1

f5 - x2

L’utilisation de ces relations pour exprimer les variables inconnues à partir de celles connues, donne les relations ci-dessous (on montre quelles sont les relations utilisées dans les calculs pour chaque variable).

x3 = y3 {1}

x2 = y1 − y3 {1, 5}

x1 = y2 – y1 + y3 {1, 3, 5}

Les relations redondantes peuvent maintenant être utilisées pour créer les RRAs suivantes :

y2 − y1 + y3 = 2y1 – 2y3 + u

R1 : 3y1 – 3y3 − y2 + u = 0

y1 – y3 = y3 − y2 – y1 + y3

R2 : 2y1 + y2 − 3y3 = 0

Notons qu’à partir d’un ensemble de RRAs, n’importe quelle combinaison de RRAs donne aussi une RRA. C’est le cas dans l’exemple précédent où une troisième RRA R3 peut être obtenue à partir de R1 et R2.

3y1 – 3y3 − y2 + u = 2y1 + y2 − 3y3

R3 : y1 − 2y2 + u = 0

Les RRAs additionnels ainsi obtenues correspondent à celles qui auraient pu être obtenues à partir d’autres couplages sur la structure du système.


37

4.3.4. Signatures de fautes

Les relations de redondance analytique, conduisent au concept fondamental de signature de faute. Pour déterminer les performances structurelles d’un système de surveillance conçu sur la base d’un ensemble de relations de redondance R, on associe à l’ensemble des causes de défaillances à surveiller (fixé par le cahier des charges), un sous-ensemble de l’ensemble des variables à surveiller Z (défini dans le cahier des charges).

Définition 1.20 : Etant donné un ensemble R = { R1, R2, ..., Rn} de n RRAs. On appelle signature de faute dj relative à l’ensemble R, le vecteur binaire Sj = [a1j , a2j , ..., aij , ..., anj ]

T, tel que, [Ger 93] :

aij = 1 si Ri est sensible à la défaillance dj

0 sinon.

L’interprétation des aij = 0 est que l’occurrence de la défaillance dj n’affecte pas la RRA Ri, c’est-à-dire que Ri = 0. En d’autres termes, le résidu Ri ne réagit pas à la présence de la défaillance dj.

L’interprétation des aij = 1 est que l’occurrence de la défaillance dj affecte Ri, c’est-à-

dire que Ri ≠ 0. Ce qui nous permet de détecter la présence de la défaillance dj.

Dans notre exemple, d’après le cahier des charges qu’on s’est fixé Z = {x1, x2, x3, y1, y2, y3, u} et R = { R1, R2, R3}. On obtient alors la table de signatures suivantes :

y1 y2 y3 u

R1 1 0 1 1

R2 1 1 1 0

R3 1 1 0 1

Tab. 1.3 : Table de signatures.

Les ensembles de diagnostic dans le processus FDI sont donnés en termes de pannes présentes dans la table de signatures. La génération de ces ensembles est basée sur une interprétation des colonnes de la table de signatures et consiste à comparer la signature des observations avec celle des pannes. Cette comparaison est considérée comme un problème de décision [Maq 03].

La première étape (tâche de détection) est de construire la signature des observations, c’est-à-dire, de décider si la valeur d’un résidu est nulle ou non, en présence de bruit et de perturbations.

Par exemple, à partir de la table de signatures obtenue précédemment (Tab. 1.3), et avec une signature d’observation OS = [1, 1, 0]T, en l’absence de bruit et de perturbations,


38

on peut conclure que la colonne y3 de la table de signatures de fautes correspond parfaitement aux observations. Dans ce cas de figure, on peut affirmer que le capteur y3 de notre système est défaillant. La même affirmation serait vraie pour le capteur y2 si on avait OS = [0, 1, 1]T.

4.4. Analyse de l’isolabilité des fautes

La détection de fautes est souvent suivie d’une procédure d’isolation, qui sert à distinguer (isoler) une faute particulière. Un seul résidu peut suffire pour détecter les fautes, cependant plusieurs résidus (ou un vecteur de résidus) sont souvent requis pour les isoler [Luo 94].

A partir de la table de signatures des fautes, l’analyse de l’isolabilité est possible puisqu’on connait les sensibilités aux fautes de toutes les RRAs. Une RRA peut être sensible à différentes fautes et les combinaisons de RRAs peuvent nous informer sur l’isolabilité du système [Xu 02]. Par contre, il est certains que les RRAs ne peuvent pas réagir aux fautes non incluses dans leur ensemble de sensibilité.

Pour que toutes les fautes puissent être détectées, aucune colonne de la table de signatures théoriques de défauts ne doit être nulle, et pour que toutes les fautes puissent être localisées, toutes les signatures théoriques doivent être distinctes sans l’hypothèse d’exonération [Cor 02].

En étudiant l’isolabilité des composants en fautes, on distingue trois types de tables des signatures (Fig. 1.12) [Ger 91] :

Fig. 1.12 : Exemple des trois types de tables dse signatures [Ger 91].

• non localisante : une colonne est nulle ou au moins deux colonnes sont identiques,

• faiblement localisante : les colonnes sont non nulles et distinctes deux à deux,

f1 f2 f3

R1 1 1 1

R2 1 1 1

R3 1 0 0

f1 f2 f3

R1 1 1 1

R2 1 0 1

R3 1 1 0

f1 f2 f3

R1 1 1 0

R2 1 0 1

R3 0 1 1

Non localisante Faiblement localisante

Fortement localisante


39

• fortement localisante : en plus d’être faiblement localisante, aucune colonne ne peut être obtenue à partir d’une autre en remplaçant un « 1 » par un « 0 » et inversement.

Une table non localisante ne permet pas de distinguer certaines fautes entre elles. Une table faiblement localisante permet de localiser les fautes simples sous hypothèse d’exonération. Une table fortement localisante garantit que les différentes sensibilités des résidus par rapport aux fautes ne conduisent pas à un diagnostic erroné.

4.4.1. Algorithme d’analyse structurelle pour l’isolation de fautes

Cette section résume les étapes de l’algorithme de diagnostic de fautes. L’un des buts de cet algorithme est bien sûr d’analyser les propriétés de détection et d’isolation de fautes dans un système en créant des RRAs réalisables, mais aussi l’étude des propriétés structurelles.

Fig. 1.13 : Schéma général de l’algorithme de l’analyse structurelle pour le diagnostic [Dus 05].

4.4.1.1. Le modèle structurel

Le modèle structurel utilisé est dérivé à partir d’un modèle analytique. En utilisant l’approche par table de signatures, à chaque contrainte correspond une ligne où les variables présentes sont marquées. Une variable dérivée et sa variable originale sont considérées comme deux variables différentes faisant réagir les mêmes contraintes.

Modèle analytique

Modèle structurel

Matrice d’incidence

Ajout des variables supplémentaires

Décomposition canonique

Recherche des couplages complets

Calculer les RRAs

Table de signatures


40

4.4.1.2. Décomposition de la table de signatures

La table de signatures étendue (avec des contraintes différentielles) du système est décomposée afin d’obtenir le sous-système surdéterminé. Cette décomposition peut être réalisée par la méthode de Duhlmage et Mendelsohn, puis améliorée par la génération des blocs de König-Hall [Dus 05].

4.4.1.3. Recherche des couplages complets

Un algorithme de couplage récursif est utilisé pour trouver tous les couplages possibles. Le résultat est une matrice où chaque ligne est un couplage et les colonnes sont les différentes variables. Les valeurs dans la matrice correspondent aux liaisons entre contraintes et variables.

4.4.1.4. Trouver les RRAs possibles et les fautes qui les affectent

Lorsque toutes les variables ont été couplées, l’étape suivante est d’analyser comment utiliser la redondance du système. Pour chaque couplage, chaque contrainte redondante (non incluse dans le couplage), peut être utilisée pour créer une RRA. Cela est fait en substituant, dans chaque contrainte redondante, les variables de cette expression, par l’expression utilisée dans le couplage. Le résultat est un ensemble d’équations qui sont nécessaires pour créer une RRA. A cette matrice on fait correspondre une matrice de sensibilité de faute qui défini les fautes auxquelles chaque ensemble de RRAs est sensible.

4.4.1.5. Créer la table de signatures

La dernière étape de l’algorithme est de construire la table de signatures qui fait correspondre les RRAs et les fautes auxquelles elles sont sensibles.

Un exemple complet et détaillé de cet algorithme (appliqué sur un système de réservoir d’eau) peut être trouvé dans [Rat 04] [Cor 02].

4.4.2. Exploitation des propriétés structurelles

L’analyse structurelle s’intéresse aux propriétés du modèle structurel. Les propriétés obtenues sont donc valides quelle que soit la nature des équations et la valeur des paramètres. Cette approche s’avère particulièrement intéressante dans la phase de conception d’un système ou lorsqu’il s’agit de modifier ou d’étendre les fonctionnalités d’un système existant [Dus 05].

Les systèmes ayant le même modèle structurel sont structurellement équivalents. Les propriétés structurelles sont des propriétés propres à la structure du système, et elles sont partagées par tous les systèmes structurellement équivalents [Oul 05].

Les propriétés structurelles qui nous intéressent dans notre travail sont les possibilités d’observabilité, de détection (détectabilité) et de localisation (isolabilité) des fautes. L’analyse de ces propriétés conduit à la détermination d’un sous-système surveillable.


41

4.4.2.1. Observabilité structurelle

La détermination des valeurs d’une variable (inconnue) dans un système est (structurellement) possible s’il existe un lien entre cette variable et un ensemble de variables connues (mesurées). On dit alors que la variable est observable.

Définition 1.21 : une variable xj ∈ X, j ∈ {1, …, |X|} est structurellement observable si et

seulement si on peut calculer sa valeur à partir d’un ensemble K [Iza 01].

A partir de cette définition on peut conclure que tous sous-système juste-déterminé ou surdéterminé est structurellement observable.

4.4.2.2. Surveillabilité structurelle

L’analyse de la table des signatures permet de déterminer les propriétés de surveillabilité, c’est-à-dire, détectabilité et isolabilité structurelles des fautes. Une faute est détectable si sa signature comporte au moins un « 1 ». Deux fautes sont isolables si leurs signatures sont différentes. Afin d’étudier et visualiser l’isolabilité des fautes, il est possible de construire une matrice appelée table d’isolabilité [Ben 08]. Par permutation des lignes et des colonnes, cette table peut être mise sous forme de blocs-diagonales, où chaque bloc est une matrice carrée constituée uniquement de « 1 ». Chaque bloc représente un sous-ensemble de défaillances non localisables entre elles.

La matrice d’isolabilité permet d’indiquer les sous-ensembles de fautes non isolables entre elles, c’est-à-dire ne pouvant être différenciées à l’aide des résidus.

Afin d’améliorer l’isolabilité des fautes, une connaissance supplémentaire sur le système doit être utilisée. Un moyen possible consiste à ajouter des capteurs [Car 99]. Un autre moyen consiste à utiliser les modèles des fautes lorsque ceux-ci sont disponibles. L’utilisation de ces modèles peut permettre en effet d’améliorer les performances du système de surveillance en termes d’isolabilité des fautes. L’analyse de la table d’isolabilité structurelle permet d’indiquer sur quelles défaillances un effort de modélisation doit être porté afin de respecter le cahier des charges de la surveillance [Dus 05].

Définition 1.22 : La partie structurellement surveillable d’un système est le sous-ensemble de variables, tel qu’il existe des RRAs qui sont structurellement sensibles à leurs changements [Dus 05].

A partir de cette définition on peut obtenir le résultat suivant :

Théorème 1.1 : Une condition nécessaire pour qu’une faute f soit surveillable (ou « monitorable ») est que f appartiennent à la partie surdéterminée du système, tel qu’il existe au moins un couplage complet sur les variables inconnues [Bla 03].


42

4.5. Qualités du diagnostic

Lorsque la signature observée ne correspond à aucune signature de faute, quelques applications FDI acceptent les signatures de faute les plus proches en employant un critère de cohérence basé sur la similitude. La raison pour laquelle on accepte cette correspondance approximative est que c’est une façon de prendre en compte les incertitudes du modèle et les perturbations extérieures. Comme l’incertitude n’est pas bien caractérisée, la sémantique de la distance n’est pas clairement définie. Cependant, le but est de garantir une certaine robustesse en ce qui concerne la procédure de décision, qui évalue si un résidu est nul ou pas. Par exemple, en utilisant de la distance de Hamming comme critère, l’interprétation correcte de la signature observée en présence de k erreurs de décision est garantit si les signatures de faute se trouvent toutes au moins à une distance de 2k+1 l’une de l’autre.

Définition 1.23 : La distance de Hamming entre deux composants représente le nombre de bits différents entre leurs signatures respectives [Cas 94a].

Une autre manière de traiter les incertitudes dans l’approche FDI est de se servir d’autant de RRAs que possibles, même si elles sont redondantes d’un point de vue de localisation et de détection. En effet, les bits des signatures additionnelles assurent une meilleure détection en présence de bruit et de perturbations et cela suggère d’utiliser toutes les RRAs possibles.

D’un autre côté, plusieurs qualités sont requises pour l’algorithme de diagnostic utilisé, basé sur l’analyse structurelle. Ces qualités sont : la réalisabilité, la prise en charge de différents types de systèmes, le temps de calcul et la complétude [Dus 05].

4.5.1. La réalisabilité des solutions

Est-ce que les RRAs trouvées sont réalisables ou non ? Avec « réalisable » on veut dire qu’avec un ensemble d’équations nécessaires pour une RRA, l’expression analytique résultante doit avoir une solution. Ceci n’est pas évident car le modèle structurel est une simplification du modèle analytique. Ensuite, quelques problèmes peuvent exister du fait que les calculs numériques perturbés par le bruit sont difficiles à exécuter correctement.

D’autres problèmes peuvent apparaitre avec les contraintes différentielles du type

=��

�� où peut être calculé à partir de x, mais pas l’inverse, car pour exécuter

l’intégration on doit connaître la valeur initiale, et ce n’est pas toujours le cas. Le même type de problème arrive aussi avec les fonctions injectives, qui peuvent être considérées comme des relations à un seul sens. Par exemple, la fonction carrée :

x² = u

y = x


43

Pour vérifier le signal du capteur y, x doit être calculé à partir de la première équation, ce qui donne :

= √�

Comme x peut être positif ou négatif, il ne peut pas être calculé ici.

4.5.2. La capacité à gérer différents types de systèmes

Bien qu’on suppose souvent que les systèmes sont linéaires pour simplifier des calculs, ce n’est pas toujours le cas réel. L’algorithme de diagnostic doit être compatible avec les systèmes non-linéaires pour être applicable à tous les systèmes.

Un système quelconque peut être statique ou dynamique ; linéaire ou non linéaire. Les systèmes statiques sont beaucoup plus simples à manipuler puisqu’il ne contient pas de dérivées. Cependant, les systèmes réels sont généralement dynamiques, c’est-à-dire que les équations qui les décrivent, contiennent des variables différentielles. En général, il est important que la dynamique du système soit traitée d’une façon correcte.

4.5.3. La complexité temporelle

La consommation majeure en temps de calcul se situe au niveau de l’exécution du processus de couplage. Cette consommation est en fonction de la taille de la table de signatures et surtout du nombre de « 1 » qui sont présents dans cette matrice. Diminuer le nombre d’opérations et essayer d’éliminer les informations inutiles sont donc très important.

4.5.4. La complétude

Si plusieurs RRAs différentes sont trouvées, il est sûr qu’elles contiennent en totalité plus d’information pouvant être utile pour la localisation de fautes. Cela signifie qu’ils y a plus de relations qui sont sensibles aux différentes fautes. L’idéal serait donc de trouver toutes les RRAs possibles.


44

5. Conclusion

Dans ce chapitre, nous avons présenté les concepts de base de la surveillance et du diagnostic des fautes simples. Nous avons commencé par présenter la terminologie employée dans le domaine, puis nous nous sommes intéressés aux concepts de base de cette discipline. Par la suite, nous avons essayé de classifier les méthodes de diagnostic existantes, selon le type d’approche (avec ou sans modèle) et selon le domaine de recherche (Automatique versus IA).

Ensuite, nous avons détaillé l’approche de diagnostic qui utilise les techniques de l’analyse structurelle, afin de bien comprendre les mécanismes qui permettent de détecter les défaillances dans un système et de les localiser. L’algorithme de cette approche repose sur le concept de résidus, pour la détection, et de redondance, pour la localisation. Il utilise les notions de décomposition canonique, de couplage et de signature de faute, qui ont été largement commentés. Grâce à cette approche, la connaissance des conditions structurelles d’observabilité et de surveillabilité sont réalisables, Enfin, nous avons clôturé ce chapitre par un résumé des qualités requises pour un diagnostic.

L’objectif de ce chapitre a été d’introduire les notions de bases en matière de diagnostic, afin de les étendre et de les utiliser dans les chapitres suivants. En effet, le prochain chapitre sera consacré à l’étude du diagnostic multi-faute. Le comportement des fautes multiples dans un système sera étudié ainsi que quelques approches d’extensions et de solutions existantes.

Chapitre 2 : Le diagnostic multi-faute

45

1. Introduction

Dans les systèmes industriels réels, plusieurs défaillances ou fautes peuvent apparaître simultanément. En général, on rencontre cette situation quand le système n’a pas été interrompu ou corrigé après une première occurrence de faute, ou lorsque la défaillance n’est pas critique et que son effet est graduel et qu’entre temps, d’autres fautes apparaissent. Elle est plus fréquente lorsqu’une méthode de reconfiguration est employée. Les méthodes de reconfiguration adaptent la loi de contrôle, permettant de continuer la production malgré la présence de fautes [Pat 91a].

Le but du diagnostic multi-faute (ou Multi-Fault Diagnostic, MFD) est d’identifier les fautes multiples dans un système spécifique à partir d’un ou plusieurs symptômes. Le diagnostic multi-faute peut être utilisé comme une partie d’un système global de diagnostic ou bien comme un système complet dépendant du type de système dans lequel il est utilisé.

L’importance et l’utilité du diagnostic multi-faute est évidente et inévitable dans les systèmes complexes modernes. Dans ces systèmes, n’importe quel nombre de symptômes peut provoquer un très grand nombre de pannes qui doivent toutes être évaluées. L’espace de solution évolue donc de façon exponentielle et le problème du diagnostic multi-faute est qu’il est difficilement calculable ou NP-Difficile. Plusieurs efforts considérables ont été déployés, indépendamment des domaines où des systèmes étudiés, afin de résoudre le problème du diagnostic multi-faute en employant différentes méthodes et approches.

Dans ce chapitre, nous allons présenter la problématique du diagnostic multi-faute ainsi que les spécificités du comportement des fautes multiples dans un système. Les travaux existant dans ce domaine se sont concentrés surtout sur les systèmes statiques mais quelques recherches ont été élaborées concernant les cas dynamiques, étant donné que l’occurrence d’une séquence de fautes peut être traitée comme un cas de fautes multiples.

Nous verrons par la suite, une extension de la méthode de diagnostic FDI pour le diagnostic multi-faute et nous discuterons les résultats obtenus et les limitations de cette approche.

Finalement, nous présenterons d’autres approches pour le MFD basées sur différents types de modélisation (logique, graphique et probabiliste).


46

2. Généralités sur le diagnostic multi-faute

Les avancées importantes dans les technologies de conception et de fabrication ont donnés lieu à des dispositifs très complexes, comme par exemple, les circuits VLSI (Very Large Scale Integration), les systèmes de communications ou les réacteurs nucléaires. La complexité physique dans ces systèmes est due au nombre élevé de composants physiques qu’ils contiennent (par exemple, plus d’un million de portes logiques dans un circuit VLSI). Pour des raisons inconnues, les composants physiques de ces systèmes tombent en panne, provoquant des disfonctionnements complets ou partiels du dispositif. A cause de la complexité inhérente de ces systèmes, la définition exacte des causes du mauvais fonctionnement est extrêmement difficile.

Concernant les VLSI, de récentes études statistiques dans un environnement de conception réel ont montrés que pour 453 dispositifs qui présentés des disfonctionnements, 41 % des défauts trouvés ne pouvaient pas être modélisé par une faute simple [Hui 04]. En plus, 22 % du reste des cas de fautes (soit 59%) ne peuvent être modélisé en employant le modèle de faute-lié simple. Donc, dans plus de 60 % des cas où un circuit est analysé pour défaut, le diagnostic de faute multiple est nécessaire [Liu 05].

Un autre exemple serait le cas du diagnostic médical, car même pour un médecin spécialiste il est difficile d’assimiler toute l’information nécessaire pour établir un diagnostic clinique optimal des symptômes observés. Ainsi, le diagnostic de faute multiple (MFD) est utilisé dans plusieurs secteurs impliquant l’analyse du diagnostic de fautes.

2.1. Principe de parcimonie

La parcimonie est un principe consistant à n’utiliser que le minimum de causes élémentaires pour expliquer un phénomène. Par exemple en diagnostic de fautes, ce principe privilégie l’occurrence d’un nombre minimum de fautes (voir une seule faute) pour expliquer les symptômes observés.

En MFD, ce principe est utilisé afin de simplifier la procédure de diagnostic. Il est aussi appelé « principe de simplicité » ou encore « principe d’économie », car il exclut la multiplication des raisons et des démonstrations à l’intérieur d’une construction logique.

Ainsi, lors du diagnostic multi-faute, on applique le principe de parcimonie en cas de difficulté à déterminer quelles fautes sont les plus probables : ce sont a priori celles qui sont les plus simples et on préfère ainsi minimiser l’ensemble des combinaisons de composants en fautes.

Le principe de parcimonie peut apparaître comme une application du « rasoir d’Ockham ». Le rasoir d’Ockham (ou Occam) est un principe de raisonnement formulé comme suit : « Les multiples ne doivent pas être utilisés sans nécessité ».

Le principe du rasoir d’Occam consiste à ne pas utiliser de nouvelles données tant que celles déjà existantes suffisent, ou, autrement dit, à ne pas apporter aux problèmes une


47

réponse spécifique, ad hoc, avant d’être certain que cela est indispensable, sans quoi on risque de compliquer la solution du problème. On traduit souvent ce principe sous la forme d’une préférence de l’hypothèse « la plus simple » parmi toutes celles qui sont échafaudées.

Dans ce mémoire, nous allons utiliser le principe de parcimonie comme moyen d’optimisation et de simplification de l’algorithme de diagnostic multi-faute.

2.2. Diagnostic de fautes

Dans le diagnostic de faute, un composant du système peut être considéré comme responsable d’une défaillance, appelée aussi disfonctionnement ou faute, et l’ensemble de tels composants constituent le diagnostic.

Un symptôme dans le diagnostic de faute est défini comme n’importe quelle différence entre une prédiction (ou signature) faite par le processus d’inférence (ou modèle du système) et une observation [Kle 87].

On peut imaginer dans un système complexe, qu’un ensemble de symptômes puisse provoquer un grand nombre de diagnostics possibles. Comme le but du MFD est de déterminer les causes responsables du symptôme, l’espace de solution de diagnostic évolue exponentiellement avec le nombre de défaillances.

Dans le diagnostic de faute simple (SFD), on peut expliquer tous les symptômes par la défaillance d’un seul composant, tandis que, dans le MFD, pour chaque symptôme, il y a une possibilité d’une multitude de fautes [Pen 87] [Rei 87].

Les suppositions faites en MFD sont que le modèle est supposé être correct, c’est-à-dire, que n’importe quelles déviations dans le comportement indiquent des défaillances de composants.

Il arrive souvent, que le cahier des charges de la surveillance ne spécifie que quelques composants importants à surveiller. Dans ce cas, le diagnostic est simplifié, car il ne concerne qu’une partie du système.

2.3. Domaines d’application

Un grand nombre de systèmes experts qui réalisent des décisions de diagnostics essayent de résoudre les problèmes de MFD.

Comme exemple, on peut considérer un système expert qui réalise le diagnostic médical à partir d’un ensemble de maladies basées sur un ensemble de symptômes. Ces systèmes experts sont connus comme des systèmes de diagnostic médicaux ou système d’aide à la décision médicale.

Un autre exemple pourrait être la classe des systèmes experts qui exécutent des diagnostics dans le domaine de la commande de processus. Dans ce genre de systèmes, un


48

opérateur peut utiliser un système de diagnostic pour identifier les composants en fautes et agir pour les corriger.

Aussi, dans le domaine des circuits électroniques VLSI, le MFD est utilisé fréquemment pour évaluer le fonctionnement d’importants circuits intégrés composés de milliers de portes logiques en appliquant des modèles de tests.

Finalement, quel que soit le domaine dans lequel le MFD est utilisé, les deux caractéristiques suivantes son recherchées :

1. Diagnostic rapide, c’est-à-dire que le temps pour diagnostiquer une faute doit être minimal, ce qui est en particulier le cas des systèmes en ligne (comme des réacteurs nucléaires), ou les systèmes dynamiques en général ;

2. Diagnostic précis, c’est-à-dire que le diagnostic établit doit être correcte et concis.

Ces caractéristiques permettront d’obtenir des gains importants en productivité, en coût et en temps.

2.4. Complexité et classification du problème

2.4.1. Théorie de la complexité

La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes. Elle se concentre donc sur les problèmes qui peuvent effectivement être résolus, la question étant de savoir s'ils peuvent être résolus efficacement ou pas en se basant sur une estimation (théorique) des temps de calcul et des besoins en mémoire.

La théorie de la complexité repose sur la définition de classes de complexité qui permettent de classer les problèmes en fonction de la complexité des algorithmes qui existent pour les résoudre. Parmi les classes les plus connues, citons [Las 96] :

• Classe P : Un problème de décision est dans P s'il peut être décidé par un algorithme déterministe en un temps polynomial par rapport à la taille de l'instance. On qualifie alors le problème de polynomial. Prenons par exemple un algorithme de tri dans un tableau. S'il y a n éléments dans le tableau, l'algorithme de tri fera, dans le pire des cas, n² opérations. On dit alors que l'algorithme a une complexité polynômiale car sa complexité peut-être exprimée par un polynôme. Le problème du tri est donc dans P. Les problèmes dans P correspondent en fait à tous les problèmes facilement résolubles.

• Classe NP : Un problème est Non-déterministe Polynomial (NP) s’il appartient à la classe des problèmes de décision pour lesquels la réponse peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l'instance. Intuitivement, les problèmes dans NP sont tous les problèmes qui peuvent être résolus en énumérant l'ensemble des solutions possibles et en les testant avec un algorithme polynomial.


49

Par exemple, la recherche de cycle hamiltonien dans un graphe peut se faire avec deux algorithmes : le premier fera la génération de l'ensemble des cycles (ce qui est exponentiel) ; le second testera les solutions (temps polynomial).

• Classe NP-Difficile : Un problème est NP-difficile (ou NP-Hard) s’il est au moins aussi difficile que tous les problèmes dans NP. Formellement on définit une notion de réduction : soient p et p' deux problèmes, une réduction de p' à p est un algorithme transformant toute instance de p' en une instance de p. Ainsi, si on a un algorithme pour résoudre p, on sait aussi résoudre p'. p est donc au moins aussi difficile à résoudre que p'. p est alors NP-Difficile si pour tout problème p' de NP, p' se réduit à p. Quand on parle de problèmes NP-Difficiles on s'autorise uniquement des réductions dans P, c'est-à-dire que l'algorithme qui calcule le passage d'une instance de p' à une instance de p est polynomial.

De manière intuitive, dire qu'un problème peut être décidé à l'aide d'un algorithme non-déterministe polynomial signifie qu'il est facile, pour une solution donnée, de vérifier en un temps polynomial si celle-ci répond au problème pour une instance donnée ; mais que le nombre de solutions à tester pour résoudre le problème est exponentiel par rapport à la taille de l'instance.

Le non-déterminisme permet de masquer la taille exponentielle des solutions à tester tout en permettant à l'algorithme de rester polynomial. Notons enfin, qu’il existe une autre classe de problèmes qui est la classe NP-Complet qui regroupe tous les problèmes qui sont dans NP et NP-Difficile.

2.4.2. Complexité du diagnostic multi-faute

La complexité de résolution d’un problème MFD conduit à une difficulté combinatoire, car, la découverte d’une solution qui explique le mieux l’ensemble des symptômes ne peut pas se faire en un « temps raisonnable ». Ce temps fait référence à un temps polynômial, et en termes de calcul, tout algorithme avec une complexité en temps polynômiale est considérée comme « solvable » ou « facile ». Par contre, tout autre algorithme avec une complexité en temps non-polynômial ou exponentielle est considéré comme « insolvable » ou « difficile ».

Un nombre important de tels problèmes insolvables ont été rencontrés par les concepteurs d’algorithmes dans plusieurs domaines d’activités. Tous ces problèmes ont été classés comme ayant une complexité NP. Cela signifie qu’ils peuvent être résolus en employant le non-déterminisme, c’est-à-dire, une heuristique ou un parallélisme. S’il n’existe aucun algorithme pour résoudre un problème alors ce problème n’est pas NP mais NP-Difficile.

Nous pouvons conclure donc, et d’après les définitions du problème du diagnostic multi-faute qu’il s’agit bien d’un problème NP-Difficile, car sa résolution ne peut se faire en un temps polynômial.


50

3. Caractérisation du comportement des fautes multiples

3.1. Cas des systèmes statiques

Une combinaison de fautes multiples peut produire un symptôme similaire à un autre symptôme de faute simple. Par exemple, considérons le réseau dans la figure (Fig. 2.1) et supposons que les deux nœuds, x4 et x5 sont en panne. Alors, la signature de faute obtenue est (1, 1, 0, 0)T. Cependant, c’est la signature de la panne de x3, et il est impossible de distinguer cette faute des fautes simultanées de x4 et x5. Ainsi, la table de signatures des fautes entraînera trois erreurs : l’oubli de deux fautes (2 erreurs de faux-négatifs) et le blâme d’un nœud « innocent » x3 (1 faux-positif) [Odi 04].

Fig. 2.1 : Un réseau simple et sa table de signatures ; plusieurs exemples de situations de multi-

faute peuvent causer des erreurs [Odi 04].

Une autre situation de faute se produit quand une signature de fautes multiples est absente de la table de signatures, comme par exemple, la colonne (1, 1, 0, 1)T qui correspond à la panne de x1 et x4. La matrice retournera x3 comme faute, puisque sa signature est la plus proche de (1, 1, 0, 1)T selon la distance de Hamming.

Un autre problème peut survenir par exemple, à cause de contraintes d’ordre topologique. Ainsi, quelques situations multi-fautes peuvent être non-reconnaissables parce que quelques composants peuvent devenir « protégés » par les pannes d’autres composants.

Définition 2.1 : Un composant x est protégé par la panne du composant y, si la signature de faute de x est incluse dans celle de y [Odi 04].

Par exemple, dans la figure Fig. 2.1, la panne du nœud x3 protège x4 et x5 et il est impossible de savoir si x4 et x5 sont en panne. Cependant, supposons que x4 soit tombé en panne avant x3 ; un algorithme capable de suivre les changements dynamiques du système diagnostiquerait l’échec de x4 d’abord et diagnostiquerait ensuite l’échec de x3 une fois produit (bien sûr, si x3 est tombé en panne avant x4). Même un tel diagnostic séquentiel serait incapable de garantir un diagnostic correct pour x4 puisqu’il sera déjà protégé par x3.

x4 x5

x1 x2

x3

x1 x2 x3 x4 x5

r1 1 0 1 0 1

r2 0 1 1 1 0

r3 0 1 0 0 0

r4 1 0 0 0 0


51

3.2. Cas des systèmes dynamiques

Une autre limitation des approches existantes en MFD est leur incapacité à suivre les changements qui résultent des erreurs qui se sont produites auparavant, en raison des observations probablement contradictoires rassemblées avant et après les changements. Dans l’exemple de la figure (Fig. 2.2), nous considérons un système dynamique très simple contenant deux composants, A et B (par exemple deux serveurs) et trois observations (ou mesures) : Obs1 est une transaction impliquant les deux composants (par exemple, ouvrir une page Web sur un serveur Web qui demande des données à partir d’un serveur de base de données), tandis que Obs2 et Obs3 sont des commandes ping qui testent les serveurs A et B, respectivement. Au départ, A et B sont dans un état normal (A=0 et B=0) et les mesures Obs2 et Obs3 effectuées à cet instant retournent toutes les deux un résultat normal. Ensuite, le composant B tombe en panne ; Obs1 qui a été exécuté après l’échec de B retourne un échec, qui correspond à A ou B et contredit les observations précédentes. Le moteur de diagnostic doit détecter cette contradiction, identifier le changement dans le système et le reporter (A ou B sont en panne) et ainsi de suite. Il est clair, que dans les scénarios réalistes, il pourrait y avoir de multiples observations qui impliqueraient différentes intersections des sous-ensembles de nœuds, de telle façon que la détection de changements exige une inférence plus complexe.

Fig. 2.2 : Un système à changements dynamiques : les fautes et les réparations séquentielles

causent des modifications dans les résultats des observations et doivent être détectés et

diagnostiqués correctement [Odi 04].

A ou B

en panne

B en panne

A suspecté

A suspecté

B normal

A normal

B normal

Nœud A

Nœud B

Observations

en entrée

Diagnostic en

sortie

Moteur de Diagnostic en temps réel

Obs2 : OK

Obs3 : OK

Obs3 : échec Obs3 : OK Obs1 : OK Obs1 : échec

Normal

Normal

Panne

Panne


52

3.3. Cas des fautes en cascade

Un autre point non résolus par les approches existantes en MFD est l’effet cascade entre les fautes. En effet, dans certaines situations, l’apparition d’une faute dans le système entraine l’apparition en cascade d’autres fautes suite aux défaillances causées par la première défaillance. On doit donc utiliser un mécanisme de filtrage d’alarmes afin de détecter l’origine de la faute et de ne pas incriminer des composants qui en dépendent.

Pour cela, le système à surveiller peut être modélisé sous forme d’un Graphe Fonctionnel qui représente un modèle causal illustrant comment les fonctions initiales des composants de base du système permettent de mettre en œuvre ses fonctionnalités principales. Ce graphe est composé de nœuds qui modélisent les fonctions du système et d’arcs orientés qui modélisent les relations de dépendance fonctionnelle qui lient les différentes fonctions. Le concept de la surveillabilité est formalisé à l’aide des notions d’état et de calculabilité de l’état d’une fonction. L’algèbre des relations est utilisée pour caractériser les propriétés structurelles du graphe fonctionnel [Sek 04].

L’équipe de recherches dans le Laboratoire d’Automatique, Génie Informatique et Signal (LAGIS) de l’Université des Sciences et Technologies de Lille, a développé le modèle Bond Graph. L’outil Bond Graph est un langage graphique unifié pour tous les domaines des sciences de l’ingénieur et confirmé comme une approche structurée à la modélisation et à la simulation des systèmes pluridisciplinaires. La modélisation d'un système technique par bond graph ne nécessite pas l'écriture de lois générales de conservation. Elle repose essentiellement sur la caractérisation des phénomènes d'échanges d’énergie au sein du système [Haf 97].

Cet aspect de filtrage des alarmes ne sera pas développé dans ce travail mais nous le proposons comme perspective pour compléter la solution proposée.


53

4. Le FDI étendu au cas multi-faute

Dans la littérature, il existe plusieurs types de modélisations utilisées dans les systèmes de diagnostic multi-fautes. Celle qui nous intéresse dans ce mémoire, est la modélisation structurelle. Elle est représentée par des relations ou associations entre les différents composants du système comme, par exemple, les associations entre les maladies et les symptômes dans un système de diagnostic médical, où « le symptôme X est causé par la maladie Y » ou « le symptôme X est causé par la maladie Y et non pas par la maladie Z ». Ce type de connaissance peut être représenté sous la forme de table de signatures dans lesquelles les colonnes représentent tous les composants du système et les lignes représentent toutes les relations entre ces composants.

Dans ce qui suit, nous allons montrer comment on peut étendre la méthode de diagnostic FDI présentée dans le chapitre précédent, afin quelle puisse prendre en considération, la possibilité d’existence de plusieurs fautes simultanées lors des opérations de détection et de localisation.

4.1. Modélisation pour le diagnostic multi-faute

Dans le cas du diagnostic de fautes multiples, la matrice de diagnostic doit inclure les signatures des fautes multiples afin que celles-ci soient considérées lors de la phase de décision. Cependant, le nombre de possibilités évolue exponentiellement avec le nombre de fautes. De plus, les fautes multiples dans les systèmes dynamiques sont difficiles à détecter, parce qu’elles peuvent masquer ou compenser leurs effets mutuellement. Toute supposition d’une faute simple peut mener à un diagnostic erroné quand des fautes multiples se produisent [Dai 06].

Les algorithmes de diagnostic de fautes multiples sont donc plus complexes que ceux des fautes simples pour deux raisons : d’abord, les effets d’une faute peuvent être masqués ou compensés (on dit aussi protégés) par les effets d’une autre faute. La deuxième difficulté est que les mêmes fautes multiples peuvent se manifester de différentes manières selon l’ordre dans lequel elles se sont produites.

Selon [Web 99] et sous l’hypothèse de linéarité, l’isolation de fautes multiples peut être traitée en employant une table de signatures étendue, incluant une nouvelle colonne pour chaque combinaison de faute, menant à une solution combinatoire. Le nombre de colonnes de la matrice d’incidence étendue, peut être égal à 2n-1 si toutes les fautes multiples sont considérées (n étant le nombre de composants simples du système).

La signature théorique d’une faute multiple est généralement obtenue à partir des signatures des fautes simples. Considérons que Fj est une faute multiple correspondant à l’occurrence simultanée de k fautes simples F1,…Fk, alors, les entrées du vecteur de signature de Fj est donnée par :


54

sij = 0 si si1 = si2 = … = sik = 0

sij = 1 sinon, c’est-à-dire que ∃ sil avec l ∈ {1,.., k} tel que sil = 1.

Ainsi, les effets des fautes sont rajoutés et la nouvelle signature produite par les fautes multiples est donnée par un « OU » logique entre les signatures des différentes fautes simples [Web 99]. De plus, le fait que les signatures des fautes multiples soient obtenues à partir des signatures de fautes simples, exprime l’idée intuitive qu’une faute multiple ne peut affecter une RRA que si et seulement si, au moins une des fautes simples dont elle se compose affecte cette RRA. Cela signifie que la portée d’une faute multiple est l’union des portées de ses constituants en faute simples.

Notons que la table de signatures étendue ainsi obtenue, peut avoir une dimension exponentielle (2n-1).nous verrons par la suite quelques méthodes pour pallier à cette contrainte et réduire le nombre de colonnes.

4.2. L’hypothèse de non compensation

L’interprétation des signatures de fautes multiples est la même que celle des fautes simples, étant donné que les signatures de fautes multiples sont dérivées à partir des signatures de fautes simples. Ceci implique que l’occurrence simultanée de plusieurs fautes produisant des situations de compensation n’est pas observable. Ceci est appelé « la supposition de non compensation multi-faute » qui est une généralisation de la supposition d’exonération définie pour les fautes simples et qui est justifiée par la faible probabilité d’occurrence de tels cas.

Définition 2.2 : L’hypothèse de non compensation suppose que deux (ou plusieurs) fautes ne peuvent pas se compenser mutuellement [Cor 02].

Cette supposition n’est pas toujours vraie, mais vu les contraintes de la modélisation structurelle adoptée, ainsi que le principe de parcimonie vu précédemment, il est préférable de supposer que les fautes ne se compensent pas afin d’avoir une meilleure détectabilité et donc un meilleur diagnostic.

4.3. L’isolabilité du système

Pour une meilleure isolabilité du système, il serait souhaitable d’enrichir le modèle du système en ajoutant de nouvelles RRAs. En effet, la signature de chaque composants (simple ou multiple) doit être différente et donc, le nombre de RRAs nécessaires devrait être au moins égal au nombre de composants simples du système, sinon des composants seront « protégés » par d’autres composants du système. De nouvelles RRAs peuvent être obtenues par addition des RRAs existantes ou par ré-examination du modèle proposé pour


55

le système. On peut également prévoir l’ajout de nouveaux capteurs pour améliorer l’isolabilité.

4.4. Exemple

Pour un système composé de 4 éléments simples {C1, C2, C3, C4}, on obtient 15 (ou 24 – 1) éléments multiples {C1, C2, C3, C4, C1C2, C1C3, C1C4, C2C3, C2C4, C3C4, C1C2C3, C1C2C4, C1C3C4, C2C3C4, C1C2C3C4}.

Pour avoir une signature de faute différente pour chaque élément, on doit avoir au minimum 4 RRAs (c’est-à-dire le même nombre d’éléments simples). En effet, avec 4 RRAs, on peut avoir 24 signatures différentes.

La table de signatures étendue pourrait, par exemple, ressembler à celle de la figure Fig. 2.4. Dans ce cas, chaque colonne est différente d’au moins une valeur des autres colonnes, ce qui permet une isolabilité moyenne du système, car pour une forte isolabilité, il faut avoir des signatures distantes de plus de 1 selon la distance de Hamming.

C1 C2 C3 C4 C1C2 C1C3 C1C4 C2C3 C2C4 C3C4 C1C2C3 C1C2C4 C1C3C4 C2C3C4 C1C2C3C4

RRA1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0

RRA2 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0

RRA3 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0

RRA4 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

Tab. 2.1 : Exemple d’une table de signatures étendue à partir de 4 composants simples.


56

5. Autres approches classiques pour le MFD

5.1. L’approche « Intelligence Artificielle »

Selon la théorie du diagnostic logique de Reiter [Rei 87], un diagnostic est défini par un

ensemble minimal ∆ de composants tel que la supposition que, tous les composants dans ∆

sont défectueux et que tous les autres composants hors ∆ sont normaux, est consistante avec le modèle du système et ses observations. A partir de cette définition, on peut avoir plusieurs diagnostics où, aucun n’est un sous-ensemble de l’autre. Le diagnostic doit être minimal selon la théorie de parcimonie du diagnostic : seul un petit ensemble de composants sont défectueux.

Différentes approches de diagnostic multi-fautes existent dans la littérature de l’intelligence artificielle (IA). Une approche « classique » basée sur un modèle, considère le diagnostic comme une inférence logique, ou, en général, un problème de satisfaction de contraintes, où le diagnostic consiste à trouver une nomination satisfaisante aux composants du système (l’état normal ou l’état de panne), étant donné un ensemble de contraintes décrivant le système (par exemple, un ensemble de propositions logiques représentées par une matrice d’incidence) et un ensemble d’observations [Kle 06]. Cette approche est basée sur l’identification de conflits et la génération de candidats.

Le système proposé par [Kle 06], GDE pour General Diagnostic Engine, utilise la notion de candidats minimaux et choisit les meilleures mesures à effectuer en se basant sur les probabilités des fautes a priori. L’approche GDE est parallèle à l’approche de diagnostic basée sur la cohérence [Rei 87]. Une autre approche basée sur le contrôle théorique des structures résiduelles est décrite dans [Ger 98]. Dans ce cas, une structure résiduelle est dérivée pour trouver les propriétés d’isolation désirables. Cependant, le problème avec ce type d’approches est leur complexité de calcul, car, en général les diagnostics logiques sont des problèmes NP-difficiles. Ainsi, la gestion des fautes multiples exige souvent quelques approximations.

5.2. Autres approches

Dans la littérature, il existe aussi des algorithmes de diagnostic multi-faute, qui utilisent comme modèles du système, des graphes (appelés digraphes), où chaque nœud peut évaluer d’autres nœuds, en supposant qu’au plus, t composants du système sont défectueux. Par exemple, nous avons l’algorithme d’identification de faute de Dahburas et Masson [Dah 84], l’algorithme de Sullivan [Sul 88] et l’approche de [Fed 98]. Ces algorithmes supposent que le système est t-diagnosticable, c’est-à-dire que le système peut correctement être diagnostiqué quand il y a au plus t éléments défectueux.

Une autre approche de traiter les problèmes de diagnostic de faute multiples est d’utiliser les modèles probabilistiques, comme les réseaux Bayesians [Nie 98] qui décrivent un modèle probabiliste du système et l’utilisent pour trouver le diagnostic le plus


57

probable (cette approche a était utilisée par exemple, par Microsoft pour son système d’aide sous MS-Windows 95/98). Dans ces modèles, au lieu de limiter le nombre de composants défectueux, une probabilité de faute, indépendante pour chaque composant, est attribuée a priori. Le diagnostic se concentre sur la recherche des ensembles de composants défectueux de probabilité a posteriori suffisamment haute. Blough dans [Blo 92] a présenté un algorithme en temps linéaire pour exécuter le diagnostic optimal des systèmes en employant un modèle probabiliste. Cependant, pour les systèmes arbitraires, le diagnostic optimal employant un modèle probabiliste est NP-Difficile.

Dans le chapitre suivant, nous allons présenter une panoplie d’approches déterministes et non-déterministes qui peuvent être utilisées dans le cadre du diagnostic multi-faute.


58

6. Conclusion

Dans ce chapitre, nous avons présenté la problématique du diagnostic multi-faute à travers un certains nombre de concepts et d’exemples, afin de cerner le cadre de notre travail et d’appréhender les prochains chapitres de ce mémoire.

Nous avons commencé par définir le problème et sa complexité dans un contexte algorithmique et nous avons étudié les caractéristiques de la combinaison de plusieurs fautes dans le cas statique et dynamique.

Ensuite, nous avons présenté une extension de l’approche de diagnostic FDI afin de prendre en compte les fautes multiples. Cette extension reste d’une complexité exponentielle et nous verrons dans le reste de ce mémoire quelques propositions de solutions qui pourraient être apportées afin de réduire la complexité à un ordre polynomial.

Dans le chapitre suivant, nous allons présenter une panoplie de méthodes qui pourraient être utilisés pour compléter l’algorithme FDI présenté dans ce chapitre, tout en étudiant leurs caractéristiques en matière de diagnosticabilité.

Chapitre 3 : Panorama des algorithmes multi-fautes

59

1. Introduction

Dans le chapitre précédent nous avons présenté une extension de l’approche de diagnostic FDI afin de prendre en compte les fautes multiples. Cependant, cette extension doit être complétée par une technique d’exploration de la matrice de diagnostic.

Dans ce chapitre, nous présentons quelques extensions qui pourraient être employées pour compléter cet algorithme. Ces approches peuvent être classées en trois groupes :

• Les algorithmes déterministes : ces algorithmes trouvent la solution optimale mais peuvent prendre un nombre exponentiel d’itérations.

• Les algorithmes heuristiques : ces algorithmes produisent une solution sous-optimale mais pas de mesure de qualité de la solution. En général, ils ne prennent pas de nombre exponentiel d’itérations et on observe qu’ils trouvent rapidement une bonne solution.

• Les algorithmes d’approximation : ces algorithmes produisent une solution sous-optimale ainsi qu’une mesure de qualité de la solution. D’un autre côté, ils ne prennent pas un nombre exponentiel d’itérations.

Un seul et même exemple a été repris pour toutes les méthodes présentées, et ceci afin d’évaluer les solutions trouvées et de comparer leurs résultats.

Ce chapitre se termine par des tableaux comparatifs sur les différents algorithmes présentés et sur la qualité des résultats obtenus.


60

2. Les approches déterministes

2.1. L’algorithme exact

Nous avons vu dans le chapitre précédent, qu’un problème MFD est NP-Difficile et que l’évolution de l’espace de recherche du diagnostic est exponentielle. Cette conclusion a plusieurs conséquences. Par exemple, le fait de résoudre le problème en énumérant explicitement toutes les possibilités (c’est-à-dire construire l’arbre de recherche en entier), n’est pas réalisable et ne correspond à aucune puissance de calcul possible (le problème ne peut jamais vraiment être résolu dans un temps polynomial).

Cependant, il existe des cas spéciaux, comme lorsque le nombre de composants n=4, car un algorithme en O(2n) devient plus rapide qu’un algorithme en O(5n). Donc, on peut tout de même employer ces algorithmes exacts afin de faire des comparaisons entre les diagnostics obtenus par les autres méthodes présentées plus loin dans ce mémoire, en termes de durée d’exécution et de résultats.

L’algorithme exact appelé aussi « méthode de recherche complète et exhaustive » est la façon la plus simple de trouver un diagnostic optimal car toutes les possibilités sont énumérées, leurs valeurs sont calculées et le meilleur diagnostic est désigné comme un diagnostic optimal. Comme entrée, il utilise la table de signatures de faute étendue ainsi que la signature de faute observée. Ensuite, il parcourt cette matrice à la recherche de correspondances. Toutes les signatures trouvées sont reportées et classifiées et si aucune correspondance n’est trouvée, ce sont les signatures les plus proches (selon la distance de Hamming) qui sont reportées.

Remarquons que cet algorithme n’est applicable qu’aux systèmes statiques car aucune information sur le comportement du système n’est exprimée. Cependant, en ajoutant des

relations de redondances RRAs qui évoqueraient les variables (x) et leurs dérivées (x), alors on pourra avoir un suivi des modifications apportées sur le système.

La complexité de ce genre d’algorithmes est doublement exponentielle, car il nécessite de générer une table de signatures étendue à 2n-1 colonnes, puis de la parcourir afin de trouver les correspondances.

2.1.1. Exemple de déroulement

Pour illustrer cet algorithme considérons l’exemple de la table de signatures et de l’observation de faute suivante :

A B C D E F Observation

R1 1 1 0 0 0 0 1

R2 0 1 1 1 0 1 1

R3 1 0 1 0 0 0 0

R4 0 0 0 0 1 1 1


61

1. Dans ce système, nous avons 6 composants simples {A, B, C, D, E, F} et 4 RRAs. La matrice étendue contiendra alors 63 colonnes (26-1). Voici un extrait du contenu de cette matrice.

A B C D E F A-B

A-C

A-D

A-E

A-F

B-C

B-D

B-E

B-F

C-D

C-E

C-F

D-E

…

R1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0

R2 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1

R3 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0

R4 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1

2. Avec 4 RRAs on pourra avoir seulement 15 (24-1) signatures différentes. En réalité,

seulement 11 signatures différentes sont recensées pour ce système. Les composants qui possèdent la même signature seront donc considérés comme protégés et l’on suppose toujours que ce sont les groupes les plus composés qui protègent les groupes les plus simples.

3. Pour la comparaison avec la signature de faute observée, il faut parcourir toute la matrice. Les composants (ou groupes de composants) qui possèdent la même signature dans notre exemple sont les suivant : {B-E, B-F, B-D-E, B-D-F, B-E-F, B-D-E-F}.

4. Donc, les composants susceptibles d’être à l’origine de la faute, sont B, D, E et F. Etant donné que la signature de D est complètement incluse dans celle de B, on peut dire que B protège D dans ce cas. La même chose pourra être dite de E et F où F protège complètement E.

5. Finalement, nous aurons comme résultats : les composants en panne sont {B-F}, les composants protégés {D, E} et les composants normaux sont {A, C}.

2.2. L’algorithme multi-faute générique

Cet algorithme a été proposé et présenté par [Odi 04]. Il ne fait aucune supposition sur le nombre de fautes dans le système, mais il suppose toujours que le système est statique, c’est-à-dire qu’aucun changement ne se produit pendant le cycle de diagnostic et qu’ainsi tous les résultats sont cohérents les uns avec les autres. A partir de la table de signatures et des observations, l’algorithme opère comme suit :

1. Trouver les composants normaux : ce sont tous les composants qui appartiennent aux portées des RRAs qui ne sont pas sensibles à la faute.

2. Trouver les composants en panne : ce sont les composants qui appartiennent aux portées des RRAs sensibles à la faute et tel que tous les autres composants de la portée de la RRA soient normaux, comme déterminé dans la première étape.

3. Trouver des composants « protégés » : ce sont les composants qui n’appartiennent à aucune portée de RRA mis à part les RRAs qui utilisent les composants qui sont déjà


62

en panne. Ainsi, il est impossible de déterminer l’état de ces composants, ou, autrement dit, les composants sont « protégés » par les échecs des composants trouvés dans la deuxième étape.

4. Les composants restants sont des « échecs possibles » dans le sens où certaines combinaisons de leurs échecs peuvent produire l’ensemble donné des résultats d’observation. En principe, nous pouvons énumérer toutes ces combinaisons mais cela est peu pratique. Nous reportons simplement tous ces composants comme des échecs possibles.


Pour illustrer cet algorithme considérons l’exemple suivant : supposons que nous avons la table de signatures et l’observation de faute suivante :


R1 1 1 0 0 0 0 1

R2 0 1 1 1 0 1 1

R3 1 0 1 0 0 0 0

R4 0 0 0 0 1 1 1

1. Puisque R3 n’est pas sensible à la faute, les composants A et C sont normaux. 2. Nous enlevons maintenant les lignes et les colonnes correspondant à R3 et les

composants A et C :

B D E F Observation

R1 1 0 0 0 1

R2 1 1 0 1 1

R4 0 0 1 1 1

Puisque R1 est sensibilisée et qu’elle possède seulement un composant dans sa portée, ce composant (B) est en panne.

3. En plus, en enlevant la colonne B et les lignes qui correspondent aux RRAs utilisant B, on obtient :

D E F Observation

R4 0 1 1 1

Maintenant le composant D n’a plus de RRAs qui le concernent sans passer par B, et donc D devient protégé par la panne de B.

4. Les composants restants E et F sont des échecs possibles. On peut expliquer le résultat de R4 par la panne de E, ou de F, ou des deux (E et F). Nous ajouterons E et F à l’ensemble des composants en panne.


63

Ainsi, le résultat dans cet exemple sera : Les composants normaux : {A, C} ; Les composants en panne : {B, E-F} ; Les composants protégés : {D}.

2.2.2. Interprétation des résultats

Sans aucune supposition sur le nombre d’échecs dans le système, nous ne pouvons pas faire de nouvelles conclusions vue les RRAs disponibles. Si les composants protégés sont interprétés comme en panne, l’erreur de faux-négatif de l’algorithme (des fautes manquées) est nulle. Cependant, son erreur de faux-positif (des composants normaux diagnostiqués comme défaillants) peut être élevée si beaucoup de « protection » se produit dans le système. La construction de l’ensemble de RRAs de façon à réduire au minimum la protection des composants par l’échec d’autres composants améliorera significativement les performances de l’algorithme.

L’algorithme multi-faute générique qui marque les composants protégés comme des composants en panne ne laisse passer aucune faute, mais son erreur de faux-positif peut être élevée pour certaine matrices de signatures. Nous qualifierons cet algorithme de « sûr », par opposition à celui « non sûr » qui marque les composants protégés comme normaux. En réalité, il appartient à l’utilisateur de décider comment interpréter ces composants.

En raison de sa simplicité, l’algorithme multi-faute générique a une faible complexité de calcul par rapport au nombre de RRAs et de composants. Cependant, tandis que les approches exactes peuvent trouver la combinaison la plus probable de fautes, ou toutes les combinaisons de faute expliquant les résultats d’observations, cet algorithme simple, trouve seulement un sur-ensemble contenant tous les composants défectueux (une borne supérieure) et peut avoir une erreur de faux-positif élevée. D’un autre côté, l’algorithme suppose que le système n’est pas dynamique.

2.3. L’algorithme multi-faute séquentiel

L’algorithme séquentiel complète l’algorithme générique afin de considérer les systèmes dynamiques. À la différence du premier algorithme, celui-ci manipule l’environnement dynamique en gardant la trace des changements sur le système. L’algorithme ne considère pas que les résultats d’observations entrantes soient cohérents entre eux ; de plus, une telle incohérence aide à détecter les changements du système. L’algorithme ne limite pas le nombre de composants défectueux dans le système, mais il suppose que seul un changement peut se produire à la fois (c’est-à-dire, la panne ou la réparation d’un composant) et que le traitement de chaque changement est assez rapide pour qu’aucun autre changement ne se produise pendant que le changement actuel est traité. De telles suppositions permettent un traitement de calcul efficace des fautes multiples dans le système en appliquant l’approche du diagnostic de faute simple pour localiser chacune des fautes séquentiellement.


64

L’algorithme contrôle les changements des états du système en employant deux ensembles d’observations : un ensemble pour détecter les réparations et contrôler les composants qui sont en panne et un ensemble pour détecter les pannes et contrôler les composants qui sont normaux. Si aucun changement du système ne s’est produit, les observations du premier ensemble sont sensées continuer à retourner « échec », tandis que celles du deuxième ensemble sont sensées continuer à retourner « normal ». Un résultat d’observation différent de celui attendu indique un changement du système. Quand l’algorithme détecte un changement, il diagnostique (localise) le composant qui a changé.

Puisque l’algorithme suit à la trace les changements séquentiellement, il est nécessaire de connaitre l’état initial du système. Après qu’un changement ait été localisé et traité, l’algorithme met à jour ses ensembles d’observations pour la détection des pannes et des réparations. Il détermine aussi l’ensemble des composants protégés par l’ensemble actuel des pannes.

2.3.1. Résultats de l’algorithme séquentiel

L’algorithme de multi-faute séquentiel possède, des erreurs de faux-positifs et de faux-négatifs. Il suppose que les composants protégés sont normaux à moins qu’ils ne soient tombés en panne avant qu’ils ne soient devenus protégés. Il est clair que cela peut mener à une erreur de faux-négatif (c’est-à-dire que quelques fautes seront manquées s’ils se produisent sur des composants protégés). Aussi, si leur ensemble d’observation est insuffisant, certaines combinaisons de fautes peuvent aboutir à la matrice de dépendance restante qui est employée pour localiser la faute (simple) suivante (c’est-à-dire, la matrice qui reste après l’enlèvement de composants défectueux et toutes les observations qui y passent) qui ne fournit pas de diagnostic unique (c’est-à-dire la matrice qui a deux ou plus colonnes identiques). Dans le cas où l’un des composants non-distinguables est en panne, la déclaration que le groupe entier de composants non-distinguables est en panne est une erreur de faux-positif.

Une approche alternative consiste à traiter tous les composants protégés comme défectueux ; cela éliminera l’erreur de faux-négatif, c’est-à-dire qu’aucune faute ne sera jamais manquée. Nous appellerons cette version l’algorithme multi-faute séquentiel « sûr », par opposition à la version « non-sûre » décrite en amont.

2.3.2. Comparaison avec l’algorithme générique

Une étude comparative détaillée des deux algorithmes générique et séquentiel peut être trouvé dans [Odi 04]. Nous la résumons par le graphe de la figure (Fig. 3.1) qui comparent les taux d’erreurs constatés (statistiquement) pour chaque algorithme, et cela sur un système de 65 composants, en supposant que 10% de ces composants sont en panne.


65

Fig. 3.1 : Comparaisons des différents algorithmes déterministes [Odi 04].

0

5

10

15

20

1 2 3 4 5 6 7 8 9 10

% d'erreurs

Nbr de RRAs

Algorithme génériquesûr

Algorithme génériquenon-sûr

Algorithme séquentielsûr

Algorithme séquentielnon-sûr


66

3. Les approches heuristiques

Le mot « Heuristique » (du grec heuriskêin, qui veut dire « trouver ») est un terme qui signifie l’art d’inventer, de faire des découvertes.

Dans notre domaine, une heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution réalisable, pas nécessairement optimale, pour un problème d’optimisation NP-difficile. Cette méthode approximative, est donc le contraire d’un algorithme exact qui trouve une solution optimale pour un problème donné. Les algorithmes de résolution exacts étant de complexité exponentielle, il est généralement plus judicieux de faire appel à des méthodes heuristiques pour des problèmes difficiles. L’usage d’une heuristique est pertinent pour calculer une solution approchée d’un problème et ainsi accélérer le processus de résolution exacte.

Généralement une heuristique (spécifique) est conçue pour un problème particulier, en s’appuyant sur sa structure propre, mais les approches peuvent contenir des principes plus généraux. On parle de méta-heuristique pour les méthodes approximatives générales, pouvant s’appliquer à différents problèmes.

Les heuristiques peuvent être classées selon le schéma suivant :

Fig. 3.2 : Classification des méthodes heuristiques [Tal 01].

Une approche heuristique consiste donc, à trouver la meilleure solution dans un ensemble discret dit ensemble des solutions réalisables. En général, cet ensemble est fini mais compte un très grand nombre d’éléments et il est décrit de manière implicite, c’est-à-dire par une liste, relativement courte, de contraintes que doivent satisfaire les solutions réalisables.

Pour définir la notion de meilleure solution, une fonction, dite fonction « objectif », est introduite. La meilleure solution (ou solution optimale) est celle qui minimise ou maximise la fonction objectif. Il est clair que plusieurs solutions optimales peuvent exister.

Par exemple, le problème du plus court chemin entre deux sommets A et B d’un graphe est un exemple classique de problème d’optimisation combinatoire qu’on peut

Heuristiques

Heuristiques

spécifiques

Méta-heuristiques

Recuit

simulé

Algorithmes

génétiques

Recherche

tabou

Algorithmes

hybrides


67

résoudre par les méthodes heuristiques. L’ensemble des solutions réalisables est l’ensemble des chemins entre A et B tandis que la fonction Objectif est la longueur du chemin [Ben 97].

3.1. Les méta-heuristiques

Les méta-heuristiques forment une famille d’algorithmes visant à résoudre des problèmes d’optimisation difficile issus de la recherche opérationnelle pour lesquels on ne connaît pas de méthode classique plus efficace. Généralement, on recherche un ensemble de solutions non dominées, appelée le « front de Pareto », parmi lesquelles on ne peut décider si une solution est meilleure qu’une autre, car aucune n’étant mieux que les autres sur tous les objectifs.

Définition 3.1 : Une solution y = (y1,…, yn) domine une autre solution z = (z1,…, zn) si et seulement si :

∀i ∈ [1..n], yi ≤ zi et ∃i ∈ [1..n] tel que yi < zi

Avec Y = F(C) qui représente l’ensemble des points réalisables dans l’espace des critères, et y = (y1,…, yn) avec yi = fi(x) est un point dans cet espace.

D’une manière générale, les méta-heuristiques s’articulent autour de trois notions principales (Fig. 3.3) :

• La diversification ou exploration : désigne les processus visant à récolter de l’information sur le problème optimisé ;

• L’intensification et exploitation : vise à utiliser l’information déjà récoltée pour définir et parcourir les zones intéressantes de l’espace de recherche ;

• L’apprentissage : c’est ce qui permet à l’algorithme de ne tenir compte que des zones où l’optimum global est susceptible de se trouver, évitant ainsi les optima locaux.

Fig. 3.3 : Les trois phases d’une méta-heuristique (les points rouges représentent

l’échantillonnage de la fonction objectif).

Diversification

Apprentissage Intensification


68

La figure suivante (Fig. 3.4) représente des méta-heuristiques M qui tentent de trouver l’optimum global G d’un problème d’optimisation difficile (avec des discontinuités dans D, par exemple), sans être piégé par les optimums locaux (comme le point L).

Fig. 3.4 : Comportement des méta-heuristiques.

3.1.1. L’optimum de Pareto

Par définition, un optimum de Pareto est un état dans lequel on ne peut pas améliorer le bien-être d’un individu sans détériorer celui d’un autre. Cette notion est issue des travaux de V. Pareto qui lui a donné son nom [Par 96].

La définition de solution Pareto optimale découle directement de la notion de dominance. Celle-ci signifie qu’il est impossible de trouver une solution qui améliore les performances sur un critère sans que cela n’entraîne une dégradation des performances sur au moins un autre critère. Les solutions Pareto optimales sont aussi connues sous le nom de solutions non-dominés.

Définition 3.2 : Une solution x* ∈ C est dite Pareto optimale si et seulement s� il

n’existe pas de solution x ∈ C tel F(x) domine F(x*).

La figure (Fig. 3.5) représente un front de Pareto dans un problème nécessitant la minimisation de deux objectifs (f1 et f2). Les points A et B sont « non dominés » alors que le point C n’est optimum pour aucun des objectifs.

x

f(x) D

M

L

G


69

Fig. 3.5 : Exemple de front de Pareto (un problème nécessitant la minimisation

de deux objectifs f1 et f2).

3.1.2. Types de méta-heuristiques

Les méta-heuristiques sont souvent inspirées par des systèmes naturels, qu’ils soient pris en physique (cas du recuit simulé), en biologie de l’évolution (cas des algorithmes génétiques) ou encore en éthologie (cas des algorithmes de colonies de fourmis ou de l’optimisation par essaims de particules).

• Le recuit simulé : c’est une méta-heuristique inspirée d’un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l’énergie du matériau. Elle a été mise au point par trois chercheurs de la société IBM, S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983, et indépendamment par V. Cerny en 1985.

• Les algorithmes génétiques : parfois appelés algorithmes évolutionnaires, ces algorithmes utilisent la notion de sélection naturelle développée au XIXe siècle par C. Darwin et l’appliquent à une population de solutions potentielles au problème donné.

• Les algorithmes de colonies de fourmis : proposé par F. Moyson et B. Manderick [Moy 88] puis par M. Dorigo [Dor 92] pour la recherche de chemins optimaux dans un graphe. L’algorithme original s’inspire du comportement des fourmis recherchant un chemin allant de leur colonie vers une source de nourriture. L’idée originale est depuis déclinée pour résoudre une classe plus large de problèmes.

• La recherche taboue : c’est une méta-heuristique d’optimisation présentée par F. Glover en 1986. L’idée consiste, à partir d’une position donnée, à en explorer le voisinage et à choisir la position dans ce voisinage qui minimise la fonction objectif. Le mécanisme doit interdire (d’où le nom de tabou) de revenir sur les dernières positions explorées.

Dans le cadre de notre travail, et afin d’utiliser les techniques heuristiques dans l’interprétation de la matrice de diagnostic, nous avons opté pour l’utilisation des méta-

f2

f1

f1(A)> f1(B)

f2(A)< f2(B)

A

B

C


70

heuristiques, et notamment les algorithmes génétiques, qui sont souvent employés dans ce genre de problèmes.

3.1.3. Les algorithmes génétiques

La génétique a mis en évidence l’existence de plusieurs opérations au sein d’un organisme donnant lieu au brassage génétique. Ces opérations interviennent lors de la phase de reproduction lorsque les chromosomes de deux organismes fusionnent. Ces opérations sont imitées par les algorithmes génétiques afin de faire évoluer les populations de solutions de manière progressive.

Un algorithme génétique va faire évoluer une population dans le but d’en améliorer les individus et c’est donc, à chaque génération, un ensemble d’individus qui sera mis en avant et non un individu particulier. Nous obtiendrons donc un ensemble de solutions pour un problème et pas une solution unique. Les solutions trouvées seront généralement différentes, mais seront d’une qualité équivalente [Che 93].

Le déroulement d’un algorithme génétique se fait en cinq étapes (voir Fig. 3.6) :

1. La création de la population initiale : Pour démarrer un algorithme génétique, il faut lui fournir une population à faire évoluer. Il suffit que tous les individus créés soient de la forme d’une solution potentielle, et il n’est nullement besoin de créer des bons individus. Ils doivent juste fournir une réponse, même mauvaise, au problème posé.

2. L’évaluation des individus : Une fois que la population initiale a été créée, nous allons en sortir les individus les plus prometteurs, ceux qui vont participer à l’amélioration de notre population. Nous allons donc attribuer une « note » ou un « rang » à chacun de nos individus.

3. La création de nouveaux individus : Il existe trois méthodes pour créer les nouveaux individus : la sélection (analogue à la sélection naturelle, les individus les plus adaptés gagnent la compétition de la reproduction tandis que les moins adaptés meurent avant la reproduction), le croisement (comme en génétique, où deux chromosomes s’échangent des parties de leurs chaînes, pour donner de nouveaux chromosomes) et la mutation (modification aléatoire de quelques individus de la population en modifiant un gène, bien que rien ne garantit que l’individu muté sera meilleur ou moins bon, mais il apportera des possibilités supplémentaires qui pourraient bien être utiles pour la création de bonnes solutions).

4. L’insertion des nouveaux individus dans la population : Une fois les nouveaux individus créés, il faut sélectionner ceux qui vont continuer à participer à l’amélioration de la population. Une méthode relativement efficace consiste à insérer les nouveaux individus dans la population, à trier cette population selon l’évaluation de ses membres, et à ne conserver que les n meilleurs individus.


71

5. Réitération du processus : Pour le nombre de génération, il n’est généralement pas possible de trouver des solutions convenables en moins de 10 générations tandis qu’au bout de 500 générations, les solutions n’évoluent plus.

Fig. 3.6 : Schéma général d’un algorithme génétique.

Parmi les applications industrielles et scientifiques des algorithmes génétiques, notons leur utilisation par la société Sony® dans son robot appelé « Aibo ». En effet, ce robot a « appris » à marcher dans un dispositif expérimental où son système de commande a été soumis à une évolution artificielle. Différents modes de commandes ont été testés, les plus performants ont été croisés et le résultat a été très positif. De génération en génération, le robot s’est redressé, puis a commencé à marcher en chutant souvent et a fini par marcher d’un pas assuré.

1. Population initiale

2. Evaluation

3. Sélection Croisement Mutation

4. Insertion

Terminé ?

Résultats

(Après plusieurs itérations)

Oui

Non


72

3.2. Utilisation des algorithmes génétiques pour le MFD

Les algorithmes génétiques ont été largement utilisés pour la résolution des problèmes NP-Difficiles, étant donné qu’ils travaillent sur une population de solutions. Nous proposons de les utiliser dans le diagnostic multi-faute, et notamment pour travailler sur la table des signatures. Deux objectifs doivent être pris en considération :

• Converger vers la frontière Pareto : la plupart des travaux de recherche sur l’application des algorithmes génétiques se sont concentré sur l’étape de sélection. Dans cette étape, des méthodes de ranking sont appliquées lors de l’étape de sélection afin d’établir un ordre (rank) entre les individus. Cet ordre dépend de la notion de dominance et donc directement de l’optimalité Pareto.

• Trouver des solutions diversifiées dans la frontière Pareto : les méthodes de maintenance de la diversité peuvent être particulièrement utiles pour stabiliser des sous-populations multiples le long de la frontière Pareto.

Un algorithme génétique utilise donc, des techniques évolutionnaires observées en biologie pour trouver des solutions aux problèmes complexes de recherche et d’optimisation.

Dans notre cas, nous allons essayer de trouver les solutions qui se rapprochent le plus de la signature de faute observée, et pour cela nous allons commencer par une population de signatures de fautes simples. Ces signatures seront comparées avec l’observation et celles qui s’en approchent le plus (selon la distance de Hamming) seront sélectionnées. Ensuite, un croisement entre fautes sera effectué afin de générer de nouvelles signatures qui seront à leurs tours comparées et les meilleures seront sélectionnées. Cette opération doit être répétée un nombre de fois défini dans le paramétrage de l’algorithme. D’autres points sont à paramétrer tels que le choix et la taille de la solution initiale.

Remarquons que le but de l’algorithme n’est pas de trouver toutes les solutions possibles, comme dans l’approche exacte, mais de trouver des solutions qui se rapprochent le plus de la signature de l’observation et qui font intervenir le moins de composants possibles. En effet, plus il y a de composants qui rentrent dans la génération d’une signature, plus l’effet de protection est amplifié et donc plus on s’éloigne de la solution réelle. Ces deux objectifs, c’est-à-dire, se rapprocher de la signature de faute et minimiser le nombre de composants par solution, définissent la fonction Objectif de l’algorithme génétique qu’on souhaite utiliser.

3.2.1. Principe de fonctionnement

3.2.1.1. Le codage des données

L’étape du codage est fondamentale dans les algorithmes génétiques, car elle associe à chacun des points de l’espace considéré une structure de données. Cette structure conditionne le succès de l’algorithme. Le codage binaire est celui qui est généralement utilisé, car il peut facilement coder plusieurs types d’objets (réels, entiers, chaînes de


73

caractères, …) et permet la création d’opérateurs de croisement et de mutation simples [Gol 89]. Cela nécessite simplement l’usage de fonctions de codage et décodage pour passer d’une représentation à l’autre.

Il existe d’autres méthodes de codages comme le codage par permutation des entiers ou le codage par valeur qui est inclut dans le codage des réels et évite la phase coûteuse du décodage.

3.2.1.2. Génération de la population initiale

La population initiale conditionne fortement la rapidité et la convergence de l’algorithme génétique. On distingue deux cas :

• Si la position de l’optimum dans l’espace d’état est totalement inconnue, il est essentiel que la population initiale soit répartie sur tout le domaine de recherche.

• Si on a des informations à priori sur le problème, on génère les individus dans un sous domaine particulier (relativement aux informations disponibles) afin d’accélérer la convergence. C’est cette démarche qui sera adoptée dans notre cas.

3.2.1.3. La fonction à optimiser

La fonction d’adaptation, ou de « fitness », associe une valeur pour chaque individu. Cette valeur a pour but d’évaluer si un individu est mieux adapté qu’un autre à son environnement. Ce qui signifie qu’elle quantifie la réponse fournie au problème pour une solution potentielle donnée.

Ainsi les individus peuvent être comparés entre eux. Cette fonction, propre au problème, est souvent simple à formuler lorsqu’il existe peu de paramètres. Au contraire, lorsqu’il y a beaucoup de paramètres ou lorsqu’ils sont corrélés, elle est plus difficile à définir.

3.2.1.4. Les opérateurs génétiques

Afin de diversifier le milieu d’une génération à l’autre, il est nécessaire d’introduire divers opérateurs selon la complexité de l’application. On peut citer [Gol 94] :

3.2.1.4.1 La sélection (ou la reproduction)

La sélection a pour objectif d’identifier les individus qui doivent se reproduire. Cet opérateur ne crée pas de nouveaux individus mais identifie les individus sur la base de leur fonction d’adaptation, les individus les mieux adaptés sont sélectionnés alors que les moins adaptés sont écartés. On distingue deux types de sélection :

• Sélection déterministe : On sélectionne toujours les meilleurs individus et on écarte totalement les plus mauvais. Cela suppose un tri de l’ensemble de la population. On parle aussi d’élitisme.


74

• Sélection stochastiques : On favorise toujours les meilleurs individus mais de manière stochastique ce qui laisse une chance aux individus moins performants. Il se peut que le meilleur individu ne soit pas sélectionné aux dépens du plus faible et qu’aucun des enfants ne soit au niveau du meilleur parent.

En général, la sélection doit favoriser les meilleurs éléments selon le critère à optimiser. Ceci permet de donner aux individus dont la valeur est plus grande, une probabilité plus élevée de contribuer à la génération suivante. Il existe plusieurs méthodes de sélection, les plus connues étant la « roulette » et la « sélection par tournoi » :

1. Sélection par roue de loterie : Le principe de sélection le plus simple est celui de la sélection par roue de loterie (ou Roulette Wheel Sélection) conçu par J. Holland. Il consiste à associer à chaque individu un segment dont la longueur est proportionnelle à son adaptation (fitness) ; ces segments sont ensuite concaténés sur un disque qui ressemble à une roue de loterie (voir figure Fig. 3.7). La sélection d’un segment se déroulera par le tirage d’un nombre aléatoire de distributions uniformes entre 0 et 1. A l’aide de ce système, les grands segments, c’est-à-dire les bons individus auront plus de chance d’être tirés au sort lors du déroulement du jeu et vont être reproduits et soumis à d’autres opérateurs génétiques. Parfois, on peut avoir un bon individu qui se reproduit trop souvent en provoquant l’élimination de ses congénères (Convergence prématurée) et convergera vers un optimum local (un bon individu qui prend le contrôle de la population) [Gol 94].

2. Sélection de Holland (par restes stochastiques) : Chaque individu de la population est caractérisé par une note, représentant le rapport de son adaptation (sa fitness) sur l’adaptation moyenne de la population, dont la partie entière représente le nombre de copie de l’individu dans la population à créer. Si la population est incomplète (nombre d’individus insuffisant), on sélectionne les meilleurs individus de la population après l’avoir trié.

3. Sélection par tournoi (Fig. 3.8) : Elle consiste à choisir aléatoirement un nombre d’individus (participants à un tournoi) et à reproduire le meilleur d’entre eux (c’est-à-dire, celui qui a la plus grande adaptation). Les individus sont de nouveau disponibles pour les tournois restants (il y a autant de tournois que d’individus à remplacer).

4. Élitisme : Cette méthode de sélection permet de mettre en avant les meilleurs individus de la population. On trie l’ensemble de la population suivant leur adaptation et on sélectionne les premiers (les faibles n’ont aucune chance, contrairement aux forts qui sont toujours sélectionnés).


75

Fig. 3.7 : Sélection par roue de loterie.

Fig. 3.8 : Le tournoi entre deux individus.

3.2.1.4.2. L’opérateur de croisement (ou le cross-over)

Cet opérateur a pour but d’enrichir la diversité de la population et d’exploiter l’espace de recherche. Les croisements sont envisagés avec deux parents et génèrent deux enfants. Les descendants doivent hériter quelques caractères de chaque parent. C’est donc un essai d’amélioration des meilleurs individus (parents) produits jusqu’au moment du croisement. Pour cela, plusieurs techniques sont utilisées selon le codage adopté.

La plus simple est celle du croisement à découpage de chromosomes associé au codage par chaîne de bits. Pour effectuer ce type de croisements sur des chromosomes constitués de M gènes, on tire aléatoirement une position dans chacun des parents ; On échange ensuite les deux sous chaînes terminales de chacun des deux chromosomes, ce qui produit deux enfants (voir Fig. 3.9).

On peut étendre ce principe en découpant les chromosomes non pas en 2 sous chaînes mais en plusieurs (Fig. 3.10).


76

Fig. 3.9 : Croisement simple.

Fig. 3.10 : Croisement à deux points.

3.2.1.4.3. L’opérateur de mutation

Cet opérateur permet aux algorithmes génétiques d’explorer tout l’espace de recherche en modifiant aléatoirement une partie de la population. Il a été conçu pour renforcer les deux opérateurs, reproduction et croisement, qui par leurs caractères pseudo-aléatoires peuvent avoir le désavantage d’oublier des solutions. Sur le plan théorique, les propriétés de convergence des algorithmes génétiques sont fortement dépendantes de cet opérateur, et un algorithme peut même converger, rien qu’en utilisant des mutations.

Comme pour le croisement, plusieurs techniques de mutation peuvent être utilisées. Pour les problèmes discrets, l’opérateur de mutation consiste généralement à tirer aléatoirement un gène dans le chromosome et à le remplacer par une valeur aléatoire.

Si la notion de voisinage existe (utilisation de distance) dans le modèle retenu, il pourra être judicieux de choisir à chaque fois des valeurs mutées dans le voisinage des valeurs originales. La figure suivante (Fig. 3.11) présente un exemple d’application de cet opérateur sur une chaîne de bits [Gol 94].

Avant croisement Après croisement

Avant croisement Après croisement


77

Fig. 3.11 : Exemple de mutation.

Les opérateurs de croisement et de mutation sont appelés opérateurs génétiques car ils simulent le processus d’héritage des gènes, pour créer une nouvelle génération. Par contre l’opérateur de sélection est un opérateur d’évolution qui simule le processus d’évolution darwinien, pour produire de nouvelles populations qui serviront à la création des générations.

3.2.1.5. Les paramètres de dimensionnement

Plusieurs paramètres doivent être spécifiés avant l’utilisation d’un algorithme génétique, à savoir :

• La taille de la population : c’est-à-dire le nombre d’individus dans la population initiale. Si la taille est trop petite, l’algorithme génétique peut ne pas converger. Par contre si elle est trop grande, l’évaluation des individus peut être très longue.

• Le critère d’arrêt de l’algorithme : ce critère n’est pas fixe, il peut changer d’une application à une autre. Il peut s’agir du :

� Nombre total de générations atteint. � Limites sur utilisation des ressources CPU. � Optimum atteint. � Nombre maximum d’évaluation de la fonction fitness. � Plusieurs générations sans améliorations. � Combinaison entre deux ou plusieurs critères cités ci-dessus.

• La probabilité d’application des opérateurs génétiques : détermine le choix du taux de mutation et de croisement. Le taux de croisement est généralement assez fort et se situe entre 70% et 95% de la population totale, par contre celui de la mutation est généralement faible, et se situe entre 0.5% et 1% de la population totale.

Ce paramétrage n’est pas universel, car il n’est pas adapté à la résolution de tous les problèmes, mais peut être pris comme point de départ pour démarrer une recherche de solutions à un problème donné.

Avant mutation Après mutation

Lieu de mutation

(choisi aléatoirement)

Bit muté

1 0 0 0 1

1 0 1 0 1


78

3.2.2. Formalisation de l’algorithme

Pour l’implémentation de cet algorithme, nous avons adopté la méthode suivante :

1. Codage : Chaque individu de la population est un ensemble de composants, qui peuvent être en faute. Il est représenté par une suite de bits indiquant les composants qu’il représente.

2. Population initiale : Individus généré aléatoirement. 3. Evaluation de la population : Deux fonctions déterminent la qualité de chaque

individu de la population. D’abord la distance de Hamming entre sa signature et celle de la faute, et ensuite le nombre de composants qui constituent l’individu.

4. Fonction objectif : Cette fonction essaye de minimiser les deux fonctions citées précédemment. Elle doit être soigneusement calculée afin d’obtenir les meilleurs résultats.

5. Opérateurs génétiques : Les opérateurs de sélection, de croisement et de mutation sont utilisés avec des taux variables, pour converger vers la solution.

6. Condition d’arrêt : Cette condition a été fixée à 100 itérations mais reste paramétrable.

Le formalisme détaillé sera présenté dans le chapitre suivant.




R1 1 1 0 0 0 0 1

R2 0 1 1 1 0 1 1

R3 1 0 1 0 0 0 0

R4 0 0 0 0 1 1 1

La solution proposée peut se résumer comme suit (voir le tableau Tab. 3.1) :

1. Parcourir la matrice à la recherche des signatures qui se rapprochent le plus de la signature de faute observée. Il serait possible ici de trouver des signatures qui représentent des solutions exactes (au cas où la faute provient d’un composant simple). Les solutions trouvées vont être utilisées comme population initiale pour l’algorithme génétique. Dans notre exemple, les signatures trouvées sont celles des composants {( A, B, C), (D, E, F)}.

2. Enrichir ces signatures initiales par d’autres signatures afin de se rapprocher encore plus de la signature de faute observée. Pour cela, les opérations de sélection, de croisement et de mutation sont appliqués. Pour notre exemple, les nouvelles signatures sont celles de : {(D, B, C), (D, B, F)}. Déjà à ce niveau, nous avons une première solution exacte pour le problème qui est {(D, B, F)}.


79

3. L’étape 2 est réitérée et à chaque fois on ajoute et on retire des composants afin que les signatures obtenues se rapprochent le plus de la solution. Le nombre d’itérations est un paramètre de l’algorithme et le fait de trouver des solutions exactes ne signifie pas l’arrêt d’exécution, car nous sommes devant une situation ou plusieurs solutions totalement différentes peuvent exister et le but de l’algorithme génétique est d’en trouver le maximum.

4. La condition d’arrêt est un certain nombre d’itérations défini dans les paramètres. Dans notre exemple, nous nous sommes arrêtés à trois (03) itérations et nous avons trouvé deux (02) solutions. Statistiquement, et pour avoir de bons résultats, un algorithme génétique doit être réitéré au moins 100 fois.

Itérations Sol. 1 Sol. 2

Initial. A, B D, E, F

1ère D, B D, B, F

2ème C, B

3ème E, B

Tab. 3.1 : Exemple des résultats obtenus avec un algorithme génétique.

3.2.4. Discussion des résultats

Comme nous l’avons mentionné, l’algorithme ne s’arrête pas à la première solution trouvée mais continue, afin de trouver plus de solutions. Quant à la qualité des solutions, et en appliquant le principe de parcimonie vu précédemment, ce sont les combinaisons les plus simples qui sont favorisées. Cependant, une étude comparative des différentes solutions trouvées doit être faite afin d’optimiser l’ensemble des solutions et de dégager l’ensemble des composants en fautes et ceux qui sont protégés.

D’un autre coté, la fonction qui permet de rajouter ou d’enlever des composants de l’ensemble des solutions possibles doit être bien définie, car on doit être sûr, que chaque composant ajouté apporte une nouveauté à la solution (sinon ce composant est considéré comme un composant protégé). De la même manière, et avant d’enlever un composant de la solution, il faut être sûr que toutes les possibilités de combinaisons ont été explorées.

Nous verrons dans le chapitre suivant, une implémentation de cette méthode et nous verrons quelques améliorations concernant la fonction de sélection des nouveaux composants.


80

4. Les approches approximatives

4.1. L’algorithme Branch & Bound

La méthode « Branch & Bound » ou « Programmation par Séparation et Evaluation Progressive » (PSEP) consiste à énumérer les solutions possibles d’une manière intelligente, en ce sens que, en utilisant certaines propriétés du problème, cette technique arrive à éliminer des solutions partielles qui ne mènent pas à la solution que l’on recherche. De ce fait, on arrive souvent à obtenir la solution recherchée en des temps raisonnables et dans le pire des cas, on retombe toujours sur l’élimination explicite de toutes les solutions du problème [Ulu 95].

Pour ce faire, cette méthode se dote d’une fonction qui permet de mettre une borne sur certaines solutions pour soit les exclure soit les maintenir comme des solutions potentielles. Bien entendu, la performance d’une méthode PSEP dépend, entre autres, de la qualité de cette fonction (de sa capacité d’exclure des solutions partielles de la meilleure façon et le plus tôt possible) [Boy 03].

Le principe est de séparer (branch) les solutions du problème en plusieurs ensembles de solutions et d’utiliser une évaluation partielle pour éliminer quelques unes grâce à des bornes sur les valeurs possibles de celles-ci (bound). Sans cette étape d’élimination on énumère explicitement toutes les solutions. Grâce aux bornes, l’énumération est implicite (certaines solutions ne sont pas calculées car on sait que c’est inutile).

On décompose l’ensemble des solutions S, tels que [Moo 91] :

S = ∪i=1, ..., m Si |Si| < |S| pour i = 1, ..., n

Ensuite, on itère la décomposition jusqu’à ce qu’on obtienne des ensembles de solutions calculables (typiquement quand |S| = 1).

4.1.1. L’algorithme général de PSEP

Par convenance, on représente l’exécution de la méthode PSEP par une arborescence. La racine de cette arborescence représente l’ensemble de toutes les solutions du problème considéré.

Pour appliquer la méthode PSEP, nous devons être en possession :

1. d’un moyen de calcul d’une borne inférieure d’une solution partielle ; 2. d’une stratégie de subdiviser l’espace de recherche pour créer des espaces de recherche

de plus en plus petits. 3. d’un moyen de calcul d’une borne supérieure pour au moins une solution.

La méthode commence par considérer le problème de départ avec son ensemble de solutions, appelé la racine. Des procédures de bornes inférieures et supérieures sont


81

appliquées à la racine. Si ces deux bornes sont égales, alors une solution optimale est trouvée. Sinon, l’ensemble des solutions est divisé en deux ou plusieurs sous-problèmes, devenant ainsi des enfants de la racine. La méthode est ensuite appliquée récursivement à ces sous-problèmes, engendrant ainsi une arborescence. Si une solution optimale est trouvée pour un sous-problème, elle est réalisable, mais pas nécessairement optimale, pour le problème de départ. Comme elle est réalisable, elle peut être utilisée pour éliminer toute sa descendance : si la borne inférieure d’un nœud dépasse la valeur d’une solution déjà connue, alors on peut affirmer que la solution optimale globale ne peut être contenue dans le sous-ensemble de solutions représenté par ce nœud. La recherche continue jusqu’à ce que tous les nœuds soient explorés ou éliminés.

4.1.2. Le PSEP appliqué au diagnostic multi-faute

Dans le cadre du diagnostic multi-faute et pour la construction de l’arbre PSEP, on commence par la solution la plus générale, c’est-à-dire, celle qui suppose que tous les composants sont en panne. La fonction qui calcule les espaces de recherche élimine à chaque itération un composant de la liste des composants et ne revient jamais vers un sous-espace déjà exploré.



R1 1 1 0 0 0 0 1

R2 0 1 1 1 0 1 1

R3 1 0 1 0 0 0 0

R4 0 0 0 0 1 1 1

A partir de la table des signatures et de l’observation de faute suivante, nous pouvons appliquer l’algorithme PSEP de la façon suivante :

1. Comme point de départ (racine) nous avons l’ensemble vide, car l’on suppose que tous les composants sont normaux. La signature de cet ensemble ne correspond pas à l’observation de faute faite.

2. On déduit alors les premières branches de l’arbre en utilisant une fonction qui calcule pour chaque nœud les branches qui peuvent être déduites. Ce calcul se base sur la combinaison de signatures qui couvrent la signature de faute observée. On ajoute un composant qui n’a pas encore été utilisé dans cette branche et on calcule la signature de la combinaison. Si elle couvre la signature de l’observation alors on continue sur cette branche sinon l’on s’arrête.

3. L’opération est réitérée jusqu’à ce qu’il ne soit plus possible de déduire d’autres nœuds. On construit ainsi l’arbre PSEP de la figure (Fig. 3.12).

4. D’après cet arbre simplifié, il est clair que les composants en panne sont {BE, BF}, que les composants protégés sont {D}, alors que les composants normaux sont {A, C}.


82

Fig. 3.12 : Arbre PSEP construit à partir de l’exemple précédent.

On peut remarquer que la méthode PSEP a tendance à converger vers une solution dans un temps relativement cours si l’arbre de recherche n’est pas très étendu. La fonction de calcul joue donc un rôle très important et son choix constitue une étape importante dans l’élaboration d’un tel algorithme. Les solutions qui n’aboutissent pas sont très vite repérées, évitant ainsi une perte en temps et en effort de calcul.

4.2. L’approche gloutonne

On appelle algorithme glouton un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l’espoir d’obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l’algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Dans les cas où l’algorithme ne fournit pas systématiquement la solution optimale, il est appelé une heuristique gloutonne.

Les algorithmes gloutons (appelés aussi, voraces) ont la particularité de ne jamais remettre en cause les choix qu’ils effectuent. La succession des choix ne mène pas forcément à une bonne solution ou à une solution optimale, mais il existe cependant des algorithmes gloutons qui trouvent toujours la solution cherchée, qu’on qualifie d’algorithmes exacts. Il faut prouver ou infirmer qu’un algorithme glouton est exact pour chaque problème traité [Tuy 98].

L’avantage des algorithmes gloutons est leur faible complexité. Dans certains problèmes (comme celui qui nous intéresse), il est parfois préférable d’obtenir une solution approchée par un algorithme glouton qu’une solution optimale par un algorithme trop coûteux.

φ

A

C

E F

B

E F D

0000

1010 1100

1110 1100

1101 1101

1101 1101


83

4.2.1. Application de la recherche gloutonne au MFD

Afin d’illustrer l’approche gloutonne dans l’étude du diagnostic multi-faute, considérons la table de signatures suivante :


R1 1 1 0 0 0 0 1

R2 0 1 1 1 0 1 1

R3 1 0 1 0 0 0 0

R4 0 0 0 0 1 1 1

L’entrée de l’algorithme glouton est cette table de signatures à partir de laquelle nous allons choisir la solution localement optimale (c’est-à-dire, la signature la plus proche de l’observation faite). Le déroulement de l’algorithme sur cet exemple sera, par exemple, le suivant :

1. Choisir la signature de composant qui soit la plus proche (selon la distance de Hamming) de l’observation. Ici ce sera la signature de B ou de F. Commençons par le composant B.

2. Améliorer la solution trouvée en ajoutant un autre composant (en fusionnant sa signature avec celle de B). Nous pouvons calculer la meilleure combinaison et supposer que c’est la bonne solution. Dans notre cas ce sera la signature de E qui apporte la meilleure solution car la signature de BE est égale à celle de l’observation (et non seulement proche).

3. Réitérer l’étape 2 jusqu’à ce qu’un optimum soit atteint ou que la solution soit trouvée. Dans notre cas la solution trouvée est déjà satisfaisante.

Ce qu’il faut remarquer, c’est que cet algorithme risque de trouver très rapidement la solution (comme dans notre exemple) ou de s’en écarter pleinement et tomber dans le piège des optimums locaux (comme par exemple, le fait de choisir F ensuite A). D’autre part, il risque d’y avoir plusieurs solutions pour le même problème, mais l’algorithme glouton se contente d’une seule (la première trouvée).

Une des conséquences de cet algorithme serait de considérer tous les composants dont la signature n’a pas été retenue comme étant normaux. Les composants protégés ne sont donc pas détectés par cette approche.


84

5. Comparaison des différentes méthodes

Nous avons vus, tout au long des chapitres précédents, différentes possibilités pour résoudre le problème de l’interprétation de la matrice de diagnostic afin de localiser les composants en fautes.

Le tableau suivant (Tab. 3.2) récapitule les caractéristiques de ces différentes méthodes afin de les comparer. Nous avons établis comme critères de comparaison, les propriétés suivantes :

• Trouve au moins une solution : Si l’algorithme garantit de trouver au moins une solution au problème, alors, même s’il présente d’autres contraintes, comme le temps d’exécution, il est toujours intéressant de l’essayer.

• Trouve toutes les solutions : Quelques algorithmes trouves toutes les solutions (ou plusieurs), alors que d’autres se limitent à la première solution trouvée. Cette propriété est importante, dans le cas d’une recherche exhaustive.

• Solutions exactes / approximatives : Plusieurs algorithmes (notamment les heuristiques), s’approchent de la solution sans garantir qu’elle soit la meilleure, privilégiant le temps d’exécution.

• Temps d’exécution : Certains algorithmes (de complexité polynomiale) trouvent la (ou les) solution(s) en des temps relativement acceptables. Cette propriété doit être prise en considération avant toute implémentation de solutions.

• Trouve les composants protégés : Les composants protégés sont dans un état inconnu au moment du diagnostic. Certains algorithmes les considèrent comme étant défectueux ou normaux, alors que d’autres ne les prennent pas du tous en considération.

• Comportement dynamique : Le comportement dynamique du système peut être pris en compte de façon implicite, c’est-à-dire que c’est la matrice de diagnostic qui doit posséder des colonnes qui mettent en relation les composants et leurs dérivées, ou explicite, c’est-à-dire que l’algorithme propose une solution pour traiter la dynamique du système.


85

Ap

pro

ches

Algorithmes et méthodes

Trouve au moins une solution

Trouve toutes les solutions

Solutions exactes/

approximatives

Temps d’exécution (Expo/Poly)

Trouve les composants

protégés

Comport. Dynamique

Dét

erm

inis

tes

Algo. exact Oui Oui Exact Expo. Oui Implic.

MF générique

Non Oui Exact Poly. Oui Implic.

MF séquentiel

Non Oui Exact Poly. Oui Explic.

Heu

rist

iqu

es

Algo. Génétique

Non Oui * Approx. Poly. Non Implic.

Ap

pro

xim

ativ

es

PSEP Non Non Approx. Expo. Oui Implic.

Algo. glouton

Non Non Approx. Poly. Non Implic.

* Si on lui donne le temps nécessaire.

Tab. 3.2 : Comparaison des caractéristiques des différentes approches.

Les six (06) algorithmes présentés dans ce tableau font partie d’un ensemble très important d’algorithmes pouvant être utilisés dans le domaine de l’analyse de la table de signatures multi-faute. On peut les compléter par d’autres méthodes heuristiques ou méta-heuristiques [Tal 01], par les programmes linéaires en nombres entiers (ou MILP : Mixed-Integer Linear Program) [Ata 05], par l’algorithme A* [Ste 91] et ses variantes, l’analyse en composantes principale [Tha 07] ainsi que plusieurs autres méthodes qu’on retrouve dans la littérature.

Concernant l’exemple traité dans ce chapitre, nous présentons dans le tableau suivant (Tab. 3.3), le comparatif des résultats obtenus :


86

Ap

pro

ches

Algorithmes et méthodes

Composants en panne (solution)

Composants normaux

Composants protégés

Dét

erm

inis

tes

Algo. exact B, F A, C D, E

MF générique

B, E-F A, C D

MF séquentiel

- - -

Heu

rist

iqu

es

Algo. Génétique

E-B, D-E-B A, C -

Ap

pro

xim

ativ

es

PSEP B-E, B-F A, C D

Algo. glouton

B-E A, C, D, F -

Tab. 3.3 : Comparatif des résultats obtenus.

D’après ces résultats, nous remarquons que toutes les méthodes convergent vers les mêmes

solutions cependant, la différence réside dans la détermination des composants protégés et aussi dans le temps d’exécution. D’un autre coté, il est clair que cette convergence ne sera pas la même en cas de problèmes plus complexes (plus de 10 composants par exemple).


87

6. Conclusion

Dans ce chapitre, nous avons exposé trois types d’approches pouvant être utilisées pour résoudre le problème du diagnostic multi-faute. Chaque approche offre une multitude d’algorithmes qui présentent chacun des avantages et des inconvénients par rapport aux résultats attendus.

Les algorithmes exacts offrent des résultats exacts dans des temps excessivement longs. Par contre les heuristiques ont l’avantage de se rapprocher de la solution en des temps relativement cours, et enfin les autres approches (probabiliste, gloutonne, …) offrent un compromis entre les deux aspects temps et précision.

Cependant, une implémentation est nécessaire afin de pouvoir comparer les différents algorithmes. Les points sur lesquels la comparaison pourrait être faite, sont les suivants : l’exactitude des résultats, la vitesse d’exécution, le taux de composants observables, interprétations des cas où les composants sont protégés, etc...

Dans le chapitre suivant nous allons implémenter un algorithme exact ainsi qu’une heuristique afin de mettre en évidence l’apport de ces deux types d’approches et de comparer leurs résultats.

Chapitre 4 : Optimisation et implémentation des algorithmes

88

1. Introduction

Dans ce chapitre, nous allons présenter une implémentation de deux algorithmes de résolutions du problème du diagnostic multi-faute, parmi ceux présentés dans le chapitre précédent. Les algorithmes en question, sont l’algorithme exact et l’algorithme génétique. Nous proposons aussi quelques améliorations sur ces deux algorithmes.

Ce choix a été guidé par le fait, que l’algorithme exact reste la référence en matière de solutions complètes, exhaustives et exactes, et que l’algorithme génétique offre le meilleur rapport qualité/performance, surtout, lorsque le système est important.

Les techniques ont été implémentées sur une application logicielle afin de mieux comprendre les enjeux et les notions présentés. Les tests ont été réalisés sur un ordinateur doté d’un processeur Core2Duo cadencé à 1,83 GHz et d’une mémoire de 4 Go, fonctionnant sous le système d’exploitation Microsoft Windows Vista Entreprise 32bits.

Ce chapitre présente donc l’implémentation de ces algorithmes avec des exemples et des captures d’écrans, ainsi qu’une comparaison entre les résultats obtenus par les deux méthodes.


89

2. Optimisation de l’algorithme exact

Nous avons vu dans le chapitre précédent que l’algorithme de traitement de la table de signatures dit « exact » est la façon la plus simple de trouver un diagnostic optimal car toutes les possibilités sont énumérées, leurs valeurs sont calculées et le meilleur diagnostic est désigné comme un diagnostic optimal. Comme entrée, il utilise la table de signatures de faute étendue ainsi que la signature de faute observée. Ensuite, il parcourt cette matrice à la recherche de correspondances. Toutes les signatures trouvées sont reportées et classifiées et si aucune correspondance n’est trouvée, ce sont les signatures les plus proches (selon la distance de Hamming) qui sont reportées.

Remarquons que cet algorithme n’est applicable qu’aux systèmes statiques car aucune information sur le comportement du système n’est exprimée. Cependant, en ajoutant des

relations de redondances RRAs qui évoqueraient les variables (x) et leurs dérivées (x ), alors on pourrait avoir un suivi des modifications apportées sur le système.

Plusieurs améliorations peuvent être apportées à cet algorithme afin d’optimiser les résultats et le temps de calcul. Dans ce qui suit nous allons présenter ces améliorations en utilisant un exemple qui utilise quatre (04) RRAs appliquées à dix (10) composants simples.

C1 C2 C3 C4 C5 C6 C7 C8 C9 C10

RRA1 1 0 0 0 1 0 0 1 0 1

RRA2 0 1 0 0 1 1 0 0 1 0

RRA3 0 0 1 0 0 1 1 1 0 0

RRA4 0 0 0 1 0 0 1 0 1 1

Nous supposerons aussi qu’une faute a été détectée et que sa signature est la suivante :

Sign. faute

RRA1 1

RRA2 0

RRA3 1

RRA4 0

D’après ce vecteur, nous constatons que la première et la troisième RRA sont sensibles à la faute.

2.1. Etapes d’optimisation

En utilisant l’algorithme exact, l’isolation de fautes multiples peut être traitée en employant une matrice d’incidence étendue, incluant une nouvelle colonne pour chaque combinaison de faute, menant à une solution combinatoire. Le nombre de colonnes de la matrice d’incidence ainsi étendue, peut atteindre 2n-1 colonnes si toutes les fautes multiples sont considérées (n étant le nombre de composants simples du système).


90

La signature théorique d’une faute multiple est généralement obtenue à partir des signatures des fautes simples.

Pour une meilleure isolabilité du système, il serait souhaitable d’enrichir le modèle du système en ajoutant de nouvelles RRAs. En effet, la signature de chaque composant (simple ou multiple) doit être différente et donc, le nombre de RRAs nécessaires devrait être au moins égal au nombre de composants simples du système, sinon des composants seront « protégés » par d’autres composants du système.

Cependant, l’obtention de nouvelles RRAs n’est pas toujours possible et très souvent les signatures obtenues dans la matrice d’incidence étendue sont similaires. Dans ce cas, d’autres techniques d’optimisation peuvent être utilisées afin d’améliorer l’isolabilité du système.

2.1.1. Réduction du nombre de signatures

Nous proposons comme première optimisation de regrouper les éléments simples ou multiples ayant la même signature en une seule colonne. Ceci permettra de réduire considérablement le nombre de colonnes de la matrice d’incidence étendue et ainsi de réduire le temps nécessaire pour la parcourir. Dans l’exemple précédent, une matrice de 10 composants avec ses signatures respectives est étendue aux 1032 colonnes possibles, puis elle est réduite à 15 colonnes différentes seulement, en regroupant tous les vecteurs possédant une signature identique.

Notons que cette technique ne peut être réalisée que sur les petits systèmes (n <= 30) vu la complexité en O(2n) de l’algorithme de parcours et de regroupement des éléments ayant la même signature.

C1 C2 C3 C4 C5, C1-C2, C1-C5, C2-C5, C1-C2-C5

C6, C2-C3, C2-C6, C3-C6, C2-C3-C6

C7, C3-C4, C3-C7, C4-C7, C3-C4-C7

C8, C1-C3, C1-C8, C3-C8, C1-C3-C8

C9, C2-C4, C2-C9, C4-C9, C2-C4-C9

C10, C1-C4, C1-C10, C4-C10, C1-C4-C10

C1-C6, …

C1-C2-C3-C5-C6-C8

C1-C7, …

C1-C3-C4-C7-C8-C10

C1-C9, … C1-C2-C4-C5-C9-C10

C2-C7, …

C2-C3-C4-C6-C7-C9

C5-C7, C8-C9, …

C1-C2-C3-C4-C5-C6-C7-C8-C9-C10

RRA1 1 0 0 0 1 0 0 1 0 1 1 1 1 0 1

RRA2 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1

RRA3 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1

RRA4 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1


91

2.1.2. Comparaison des résultats

Une fois cette matrice optimisée obtenue, il est facile maintenant de la parcourir à la recherche de la colonne qui correspond à la signature de fautes. En effet, il n’y aura qu’une seule colonne qui correspond puisque l’optimisation de la matrice étendue a permis de regrouper toutes les signatures équivalente en une seule. Cette colonne contiendra l’ensemble des composants, simples ou multiples, qui sont suspectés.

Dans notre exemple, ce sera la colonne suivante qui correspond :

C8, C1-C3, C1-C8, C3-C8, C1-C3-C8

RRA1 1

RRA2 0

RRA3 1

RRA4 0

Il ne reste plus maintenant qu’à analyser les composants suspectés, afin de déterminer ceux qui sont en fautes et ceux qui sont cachés (leur signature est une partie de la signature de faute).

2.1.3. Application du principe de parcimonie

Une fois les composants (ou groupes de composants) dont la signature correspond trouvés, on peut les examiner de près afin de les simplifier. En effet, dans l’exemple précédent, la dernière colonne de la matrice étendue optimisée comporte à elle seule 809 éléments possédant tous la même signature. Si c’est cette colonne qui correspond à la signature de faute, le résultat ne serait pas très concluant.

Selon le principe de parcimonie, il est préférable de garder les combinaisons les plus simples au détriment de celles qui contiennent beaucoup de composants.

Prenons dans notre exemple, la colonne trouvée à l’étape précédente et qui correspond aux composants {C8, C1-C3, C1-C8, C3-C8, C1-C3-C8}. La signature de cette colonne est (1, 0, 1, 0)T et correspond à l’observation de faute.

Sachant que la signature de C1 (1, 0, 0, 0)T est incluse dans celle de C8 (1, 0, 1, 0)T, la combinaison C1-C8 n’apporte aucune nouvelle information. Il est donc préférable de l’éliminer, de même que celle de C3-C8 et C1-C3-C8.

Par contre, la combinaison C1-C3 possède la même signature que C8, mais comme ce sont des composants disjoints, et qui n’ont pas de bits en commun dans leurs signatures respectives, on doit prendre en compte cette possibilité. Ainsi, l’ensemble des combinaisons de composants (simples ou multiples) qui possèdent la signature (1, 0, 1, 0)T est réduit à {C8, C1-C3}.

Notons enfin, que ce principe de simplification permet aussi de déterminer les composants dits « protégés ». Dans notre exemple, puisque la combinaison C1-C8


92

n’apporte aucune nouvelle information par rapport à C8, alors C1 peut être considéré comme un composant protégé. Cependant, comme C1 participe avec C3 à une autre solution du problème il a été exclu des composants protégés.

En résumé donc, tout composant, dont la signature n’apporte pas d’éléments nouveaux pour la solution du problème est considéré comme protégé, même si sa signature se rapproche de celle de la faute. Cette méthode d’optimisation peut être appliquée à chaque colonne qui contient un nombre important de combinaisons possibles.

2.1.4. Autres applications du principe de parcimonie

Une autre technique reposant toujours sur le principe de parcimonie, consiste à éliminer les combinaisons trop complexes ayant comme signature (1, 1, 1, 1)T comme celles qui regroupent tous les composants du système. Dans l’exemple présenté précédemment, la combinaison C1-C2-C3-C4-C5-C6-C7-C8-C9-C10 n’apporte aucune nouvelle information sur l’isolabilité du système puisque tous les composants sont suspectés. De tels combinaisons ne doivent donc pas être considérées ainsi que celles dont la signature est (0, 0, 0, 0)T, c’est-à-dire, auxquelles aucune RRA n’est sensible.

De façon générale, il est inutile d’avoir des combinaisons de composants dont le nombre d’éléments dépasse le nombre de RRA. Car en ayant plus d’éléments que de RRA, on est sûr qu’au moins l’un des éléments est protégé par les autres.

2.2. Exemple d’implémentation

Nous allons maintenant dérouler l’application que nous avons développé sur l’exemple vu précédemment. Nous commencerons par entrer la table de signatures relative aux dix (10) composants du système, car nous supposons que cette matrice a été engendrée par un autre outil parmi les outils existants. Nous donnons aussi à ce niveau, la signature de faute observée. La figure Fig. 4.1 représente l’interface de saisie des différentes matrices ainsi que le graphe biparti correspondant.

La figure Fig. 4.2 représente la première étape d’exécution de l’algorithme exact. On reprend la table de signatures et on détermine le nombre de composants simples.

L’étape suivante consiste à calculer la table de signatures étendue, c’est-à-dire, celle qui donne la signature de faute pour chaque combinaison de composants. Dans notre exemple, la figure Fig. 4.3 montre cette nouvelle table. Cependant, pour des raisons techniques d’affichage, nous n’avons montré que les premières et les dernières colonnes de cette matrice qui en contient 1023 (210 - 1). Le temps nécessaire pour cette opération a été calculé sur la machine présentée dans l’introduction. Il est égal à 0,779 sec sur l’exemple et varie considérablement, selon la taille de la table de départ.


93

Fig. 4.1 : Table de signatures, graphe biparti et signature de faute de l’exemple.

Fig. 4.2 : Début de l’application de l’algorithme exact.


94

Fig. 4.3 : Table de signatures étendue.

Fig. 4.4 : Table de signatures étendue optimisée.


95

L’étape suivante consiste à optimiser la table étendue. Cette opération est la plus importante dans le processus d’optimisation, puisqu’elle permet de réduire considérablement le nombre de colonnes de la table étendue. Dans notre exemple, nous sommes passés de 1023 colonnes, à seulement 15 colonnes différentes. La figure Fig. 4.4 représente la nouvelle table optimisée. Notons ici que chaque colonne contient maintenant un nombre important de composants (simples ou combinés), comme par exemple la dernière colonne, qui contient à elle seule 809 éléments.

En termes de temps d’exécution, nous remarquons que malgré la complexité et l’importance de cette étape, qui consiste à parcourir toute la table étendue à la recherche de similitudes, le temps consommé ne dépasse guère les 0,157 secs, soit le un cinquième (1/5) du temps nécessaire à la création de cette matrice.

Une fois un nombre réduit de colonnes trouvé, il est aisé maintenant de faire la comparaison avec la signature de faute et d’obtenir ainsi l’ensemble ou le groupe de composants (simples et combinés) qui sont en faute. Dans notre exemple, et comme le montre la figure Fig. 4.5, c’est l’ensemble de composants {C8, C1-C3, C1-C8, C3-C8, C1-C3-C8} qui est incriminé, car tous ses composants possèdent la même signature que la faute.

Fig. 4.5 : Résultat après comparaison avec la signature de faute.

Cette opération ne consomme que quelques millièmes de secondes (0,001 sec) et n’entraîne aucun retard.


96

Fig. 4.6 : Composants simples et multiples correspondant à la signature de faute.

Cet ensemble de composants est mis dans une liste (Fig. 4.6) et chacun est traité séparément, afin de trouver les composants en fautes et ceux qui sont protégés. Le résultat est présenté dans la figure (Fig. 4.7), où l’ensemble des composants en faute est réduit à

{ C8, C1-C3} et l’ensemble des composants protégés reste vide { φ} (pour cet exemple seulement).

Cette dernière étape aussi ne constitue pas de problème en termes de temps d’exécution car elle s’effectue en quelques millièmes de secondes (0,001 sec dans notre cas).


97

Fig. 4.7 : Détermination des composants en fautes et des composants protégés.

Notons enfin, que plusieurs paramètres et options sont modifiables au sein de l’application, comme par exemple, les noms des composants et leurs nombres par défaut, les couleurs dans le graphe biparti, …

Fig. 4.8 : Les paramètres et options de l’application.


98

3. Implémentation de l’algorithme génétique

Nous avons vu dans le chapitre précédent qu’un algorithme génétique utilise les techniques évolutionnaires observées en biologie pour trouver des solutions aux problèmes complexes de recherche et d’optimisation. Pour cela, il fait évoluer une population constituée de plusieurs solutions dans le but d’en améliorer les individus et à chaque génération, un nouvel ensemble d’individus est proposé. Nous obtenons donc un ensemble de solutions équivalentes.

Dans notre cas, nous allons essayer de trouver les solutions qui se rapprochent le plus de la signature de faute observée, et pour cela nous allons commencer par une population de signatures de fautes simples. Ces signatures seront comparées avec l’observation et celles qui s’en approchent le plus (selon la distance de Hamming) seront sélectionnées. Ensuite, un croisement entre fautes sera effectué afin de générer de nouvelles signatures qui seront à leurs tours comparées et les meilleures seront sélectionnées. Cette opération doit être répétée un nombre de fois défini dans le paramétrage de l’algorithme. D’autres points sont à paramétrer tels que le choix et la taille de la solution initiale.

Plusieurs améliorations peuvent être apportées à cet algorithme afin d’optimiser les résultats et le temps de calcul. Dans ce qui suit nous allons présenter ces différentes améliorations en utilisant l’exemple suivant, qui repose sur une table de signatures de vingt-cinq (25) composants et six (06) RRAs.

C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

RRA1 1 0 0 0 0 0 1 0 0 0 0 1

RRA2 0 1 0 0 0 0 1 1 0 0 0 0

RRA3 0 0 1 0 0 0 0 1 1 0 0 1

RRA4 0 0 0 1 0 0 0 0 1 1 0 0

RRA5 0 0 0 0 1 0 0 0 0 1 1 0

RRA6 0 0 0 0 0 1 0 0 0 0 1 0

C13 C14 C15 C16 C17 C18 C19 C20 C21 C22 C23 C24 C25

0 0 0 1 0 0 1 0 1 1 0 0 1

1 0 0 0 1 0 0 1 0 0 1 0 0

0 1 0 0 0 1 0 0 0 0 0 1 1

1 0 1 1 0 0 0 0 0 0 0 0 0

0 1 0 0 1 0 1 0 0 0 0 0 1

0 0 1 0 0 1 0 1 1 0 0 0 1


99

On utilisera la signature de faute suivante :

Sign. faute

RRA1 1

RRA2 0

RRA3 1

RRA4 0

RRA5 1

RRA6 1

3.1. Etapes d’implémentation et d’optimisation

Le but de l’algorithme génétique n’est pas de trouver toutes les solutions possibles, comme dans l’approche exacte, mais de trouver des solutions qui se rapprochent le plus de la signature de l’observation et qui font intervenir le moins de composants possibles. En effet, plus il y a de composants qui rentrent dans la génération d’une signature, plus l’effet de protection est amplifié et donc plus on s’éloigne de la solution réelle. Ces deux objectifs, c’est-à-dire, se rapprocher de la signature de faute et minimiser le nombre de composants par solution, définissent la fonction Objectif de l’algorithme génétique qu’on souhaite utiliser.

3.1.1. Le codage des individus

Chaque solution du problème traité représente un individu de la population. L’individu est un ensemble de composants du système, et chaque individu est représenté sous forme d’une suite de bits (codage binaire), où chaque bit à un (01) indique que le composant correspondant est utilisé par l’individu.

Ainsi, un individu I est représenté par un chromosome {100010100000}, qui indique que cet individu utilise le premier, le cinquième et le septième composant de la liste des composants admis comme solution. Le nombre de bits du chromosome est égale au nombre de composants admis à participer aux solutions. En effet, nous verrons par la suite que ce ne sont pas tous les composants qui peuvent être utilisés (admis).

D’autre part, la signature d’un individu est la somme (binaire) des signatures de ses différents composants. Ainsi, Sign(I) = Sign(c1) + Sign(c5) + Sign(c7).

3.1.2. Evaluation des composants

Lorsque cela est possible, il serait plus intéressant de ne générer que des éléments de population respectant les contraintes. Ceci permettra d’accélérer la convergence [All 98].

Pour cela, nous effectuons un parcours global de la table de signatures à la recherche de composants ayant la même signature que l’observation, et cela, avant de générer la population initiale. Ces composants seront exclus de la génération des individus, car leur signature est exactement la même que celle de l’observation. Ainsi toute variation


100

n’aboutirait pas à une meilleure solution et toute combinaison avec un autre composant n’apporterait aucune amélioration à l’individu, mais au contraire, protégerait ce nouvel composant ajouté. Ces composants qui ne sont d’aucun apport à l’individu, sont affichés à la fin de l’algorithme comme solutions exactes du problème.

Dans l’exemple que nous abordons, le composant {C25} sera dès le départ exclus de toute participation à un individu de la population. Il sera réaffiché à la fin comme résultat exact.

D’un autre côté, et lors de l’insertion d’un composant dans un individu, il faut s’assurer que la signature du composant est un sous-ensemble de la signature de la faute. C’est-à-dire, que le composant ne doit pas être sensible à une RRA à laquelle la faute n’est pas sensible. Pour implémenter cette contrainte, nous allons associer à chaque composant, sa somme binaire qui est la somme des bits de sa signature. Ainsi la signature de C1 qui n’est sensible qu’à la première RRA sera le nombre binaire (100000). Nous utiliserons la

fonction σB pour calculer ce nombre pour chaque composant. Ainsi la condition citée préalablement, et pour tout composant Ci à rajouter à l’individu, s’écrira :

σ B (Ci) + σ B (faute) = σ B (faute)

où l’opérateur (+) qui représente le AND binaire.

Dans l’exemple que nous développons, les composants {C2, C4, C7, C8, C9, C10, C13, C15, C16, C17, C20, C23} ne satisfont pas cette condition et seront donc exclus de toute participation à la génération des individus.

3.1.3. La population initiale

Pour générer la population initiale, nous avons le choix entre les deux méthodes suivantes :

• Saisir les éléments des individus manuellement, parmi ceux qui sont admis. • Laisser le système choisir aléatoirement les composants des individus. Ce choix sera

aléatoire, mais seuls les individus admis seront utilisés.

Le nombre d’individu est un paramètre de l’algorithme qui doit être précisé au départ. Dans notre exemple, nous l’avons fixé à six (06). Ce nombre se verra augmenter avec un nombre de composants élevé (> 50). Pour des contraintes d’implémentation, et afin de traiter les individus couple par couple, en vue de leur appliquer les opérations génétiques, nous exigeons que le nombre d’individus de la population soit un nombre pair.

Dans notre exemple, nous allons générer aléatoirement des individus en faisant des tirages uniformes parmi les composants admis du système. Pour illustrer cette étape, et à partir de l’exemple présenté précédemment, nous avons choisi les individus suivants, en respectant les conditions pré-requises :

I1 = {101000000000},

I2 = {000000001000},


101

I3 = {000010000100},

I4 = {011000100101},

I5 = {010000001000},

I6 = {000000000111}.

Ce choix a été fait de façon complètement aléatoire afin d’exploiter au mieux les performances de l’algorithme génétique.

3.1.4. Evaluation de la population

Une fois que la population initiale a été créée, nous allons en sortir les individus les plus prometteurs, c’est-à-dire, ceux qui vont participer à l’amélioration de la population. Nous allons pour cela attribuer une « note » ou un indice de qualité à chacun de nos individus. Cette note est calculée à travers une fonction Objectif. Cette fonction permet de montrer la notion de dominance entre individus.

Chaque individu de la population est défini par deux (02) fonctions :

• ∆H : qui représente la distance de Hamming entre sa signature et la signature de faute (sa valeur varie entre 0 et |RRA|). En d’autres termes, cette fonction calcule le nombre de bits différents entre la signature de l’individu et celle de la faute ;

• Nb : qui donne le nombre d’éléments dont est composé l’individu (sa valeur varie entre 02 et |RRA|).

La valeur maximale de la fonction Nb est conditionnée par le fait qu’une combinaison de plus de |RRA| éléments dans un individu serait non-localisable par la table de signatures initiale du système.

Dans notre exemple, le calcul de ces deux fonctions sur les différents individus est représenté dans le tableau suivant :

Individus Chromosomes Signatures Distance de

Hamming (∆H)

Nombre d’éléments (Nb)

1 101000000000 100010 2 2

2 000000001000 100010 2 1

3 000010000100 100011 1 2

4 011000100101 101011 0 5

5 010000001000 101010 1 3

6 000000000111 101001 1 3

Tab. 4.1 : Calcul des fonctions d’évaluations sur l’exemple.


102

L’individu est plus intéressant si la valeur de ∆H avoisine le 0 (c’est-à-dire la même signature que la faute) et si celle de Nb avoisine le 2 (c’est-à-dire le nombre minimum d’éléments). Par conséquent, l’algorithme vise à atteindre ces deux objectifs.

Ces résultats sont encore plus expressifs lorsqu’ils sont représentés par un graphe, comme dans la figure (Fig. 4.9). En effet, les individus les plus proches des deux axes en même temps constituent des solutions Pareto-optimales.

Fig. 4.9 : La fonction d’évaluation détermine la frontière Pareto.

3.1.5. La fonction Objectif globale

En optimisation multi-objective, plusieurs algorithmes existent pour le calcul de la fitness global. Les plus utilisés sont : VEGA (Vector Evaluated Genetic Algorithm) [Sch 85], MOGA (Multi Objective Genetic Algorithm) [Fon 93], NSGA (Non-Dominated Sorting Genetic Algorithm) [Sri 94], NSGA II [Deb 00], PAES (Pareto Archived Evolution Strategy) [Kno 00] et SPEA (Strength Pareto Evolutionary Algorithm) [Zit 99]. Les stratégies employées dans ces contributions sont différentes. Les résultats obtenus diffèrent essentiellement au niveau de la vitesse de convergence et de la répartition des solutions sur le front. Un très bon état de l’art est reporté dans [Coe 01].

Pour notre cas, et pour déterminer la fonction Objectif de chaque individu, nous allons utiliser les deux fonctions ∆H et Nb dans une nouvelle fonction Fitness, tel que :

�� =|��| − ∆��

|��|×

|��| − �� + 1

|��|

où |RRA| est le nombre maximal de RRA dans la table de signatures.

Il est clair dans ce cas là, qu’une Fitness égale à un (01) correspond à une solution simple

et exacte du problème (c’est-à-dire, Nb = 1 et ∆H = 0). Nous obtenons ainsi, les résultats suivants pour notre exemple :

∆H

Nb

0 1 2

5 -

4 -

3 -

2 -

1 -

Ind 1

Ind 2

Ind 4

Ind 3

Ind 5 et 6


103

Individus Chromosomes Fitness

1 101000000000 0,555556

2 000000001000 0,666667

3 000010000100 0,694444

4 011000100101 0,333333

5 010000001000 0,555556

6 000000000111 0,555556

Tab. 4.2 : Calcul de la fonction Objectif (Fitness) sur l’exemple.

3.1.6. Les opérateurs génétiques

Une fois la fonction d’adaptation calculée, il serait intéressant de classer les individus selon cette fonction, et de procéder à une série d’opérations dites « génétiques » afin d’améliorer ces individus et d’en ressortir les meilleurs. Cette opération peut être répétée plusieurs fois, et à chaque itération, l’individu le moins intéressant (selon sa fonction Fitness) est remplacé par un nouvel individu obtenu par les opérateurs génétiques.

La sélection, le croisement et la mutation constituent les trois opérations génétiques que nous allons utiliser.

3.1.6.1. La sélection

La sélection a pour objectif d’identifier les individus qui doivent se reproduire. Cet opérateur ne crée pas de nouveaux individus mais identifie les individus sur la base de leur fonction d’adaptation, les individus les mieux adaptés sont sélectionnés alors que les moins bien adaptés sont écartés [Deb 00]. La sélection doit favoriser les meilleurs éléments selon le critère à optimiser. Ceci permet de donner aux individus dont la valeur est plus grande, une probabilité plus élevée de contribuer à la génération suivante.

Il existe plusieurs méthodes de sélection, et dans notre cas, nous allons utiliser la sélection par roue de loterie (ou roue de la fortune). Chaque individu de la population de taille maximale Jmax , occupe une section de la roue proportionnellement à sa fonction d’adaptation Fitness( j) , la probabilité de sélection d’un individu j s’écrit alors :

�� =��

∑ ��

��

À chaque fois qu’un individu doit être sélectionné, un tirage à la loterie s’effectue et propose un candidat, les individus possédant une plus grande fonction d’adaptation auront plus de chance d’être sélectionnés.

Nous proposons comme amélioration de ne pas sélectionner les individus dont la Fitness est égale à un (01), car ce sont des solutions exactes qui ne doivent plus être améliorées.


104

Dans notre exemple, une première sélection peut être faite sur les individus 2 et 3 car leurs Fitness est importante. Ils peuvent donc donner une nouvelle génération ayant de meilleurs attributs.

3.1.6.2. Le croisement (cross-over)

Le croisement permet de créer de nouveaux individus en échangeant de l’information entre deux individus. Le croisement s’effectue en deux étapes. D’abord les deux (02) individus trouvés par l’étape de sélection sont assemblés, et ensuite, ils subissent un croisement comme suit : un entier k représentant une position sur la chaîne est choisi aléatoirement entre 1 et la longueur du chromosome (l) de l’individu moins un (l – 1). Deux nouveaux chromosomes sont créés en échangeant tous les bits compris entre les positions k +1 et l inclusivement.

Le taux de croisement est un paramètre important de l’algorithme, car il détermine l’intervalle des valeurs que peut prendre l’entier k. Sa valeur varie entre zéro (00) et un (01) et doit être ajustée afin d’obtenir les meilleurs croisements possibles.

Pour notre exemple, et après avoir fait plusieurs tentatives, nous l’avons fixé à 0,7.

3.1.6.3. La mutation

La mutation est exécutée seulement sur un seul individu. Elle représente la modification aléatoire et occasionnelle de faible probabilité de la valeur d’un bit de l’individu. Pour un codage binaire, cela revient à changer un 1 en 0 et vice versa. Cet opérateur introduit de la diversité dans le processus de recherche des solutions et peut aider l’algorithme à ne pas stagner dans un optimum local.

Le taux de mutation détermine cette propriété. Sa valeur aussi varie entre zéro (00) et un (01), mais plus il est petit, moins on aura de chances d’avoir des mutations. Plus il est grand, plus on aura de chances d’en avoir. Pour notre exemple, nous l’avons fixé à 0,05.

3.1.7. Le critère d’arrêt

Après chaque application des opérateurs génétiques, de nouveaux individus sont obtenus. Ces individus vont remplacer ceux de la population dont la fonction Fitness est plus faible. Cette stratégie de remplacement est appelée : Remplacement stationnaire (steady-state), et permet de sélectionner les individus à remplacer parmi ceux qui ont les plus petites Fitness [Rya 00].

Ce processus doit être répété plusieurs fois afin d’obtenir la meilleure population possible. Le critère d’arrêt est déterminé par le nombre de générations que doit engendrer l’algorithme et qui varie selon les systèmes. Après plusieurs expérimentations, nous l’avons fixé à 100 itérations. Nous pouvons aussi recommencer à nouveau le processus, si les résultats trouvés sont insatisfaisants.


105

Un autre critère d’arrêt, concerne la convergence rapide vers une solution exacte. Ce cas arrive fréquemment, lorsque le nombre d’individus ou d’éléments qui composent les individus n’est pas très important et que tous les individus sont des solutions exactes.

3.2. Exemple d’implémentation

Nous allons maintenant dérouler l’application que nous avons développée sur l’exemple vu précédemment. Nous commencerons par entrer la table de signatures relative aux vingt cinq (25) composants du système, en supposant que cette table a été engendrée par un autre outil parmi les outils existants. Nous donnons aussi à ce niveau, la signature de faute observée. La figure (Fig. 4.10) représente l’interface de saisie des différentes tables ainsi que le graphe biparti correspondant.

Fig. 4.10 : Table de signatures, graphe biparti et signature de faute de l’exemple.

La figure (Fig. 4.11) représente la première étape d’exécution de l’algorithme génétique. Dans cette étape, on reprend la table de signatures et on élimine tous les composants simples qui constituent une solution exacte au problème, afin de ne pas les inclure dans le processus génétique. Ensuite, ce sont les composants qui ne peuvent appartenir à aucune solution qui sont éliminés. Ces composants sont ceux qui sont sensibles à des RRAs auxquelles la faute n’est pas sensible. Ils sont appelés : composants non-admis.

Les composants simples et les composants non-admis sont affichés sous le titre « Remarques ».


106

Fig. 4.11 : Elimination d’une partie des composants.

Fig. 4.12 : Détermination de la population initiale.


107

L’étape suivante consiste à déterminer la population initiale et la figure (Fig. 4.12) représente cette étape. Remarquons que ce choix peut être aléatoire, d’où le lien « Remplissage aléatoire » pour exploiter au mieux cette possibilité.

Une première évaluation de cette population est présentée dans la figure (Fig. 4.13).

Cette évaluation se base sur les fonctions ∆H et Nb présentées précédemment. Ces fonctions sont calculées pour chaque individu afin de déterminer son apport à la solution.

Fig. 4.13 : Première évaluation de la population initiale.

L’étape suivante constitue la base du processus itératif de l’algorithme génétique. En effet, la figure (Fig. 4.14) représente chaque individu par sa fonction Objectif ou « Fitness » et permet ainsi de lancer les itérations à partir du lien « Commencer l’itération ». Plusieurs paramètres de l’algorithme sont visibles, tels que le nombre d’itérations, le taux d’acceptation des solutions, le nombre de générations, …

La figure (Fig. 4.15) montre quant à elle, les résultats obtenus après une centaine d’itérations. Jusqu’alors, une seule solution acceptable a été trouvée et correspond au quatrième individu de la population. Le chromosome de cet individu, indique qu’il correspond aux composants C18 et C19. La figure (Fig. 4. 16) confirme cela, car cette figure montre les résultats finaux, tout en incluant les composants simples qui constituent des solutions exactes et qui ont étaient retenues au début de l’exécution de l’algorithme. Notons aussi que le temps d’exécution n’a pas dépassé 0,075 secondes pour effectuer les 100 itérations.


108

4.14 : Calcul des Fitness avant les itérations.

4.15 : Calcul des Fitness après 100 itérations.


109

4.16 : Les composants constituant des solutions (simples et combinées).

Les résultats obtenus jusqu’à présent ne sont pas très satisfaisants, car un seul individu a donné une solution. Nous allons donc, relancer les itérations après avoir modifié le paramètre du nombre d’itération au niveau des options de paramétrage (voir la figure Fig. 4.17). La nouvelle valeur est de 500 ce qui permettra de faire plus d’essais et d’obtenir plus de solutions.

Fig. 4.17 : Le paramétrage de l’algorithme génétique.


110

La figure (Fig. 4.18) montre les nouveaux résultats obtenus après la modification du paramètre d’itération. Après seulement 0,078 secondes de traitements, trois (03) nouveaux individus proposent maintenant des solutions. Il s’agit des individus 3, 4 et 5. Leurs signatures sont équivalentes à celle de la faute et leurs Fitness dépassent le seuil d’acceptation (ici réglé à 0,70).

4.18 : Les nouveaux individus obtenus après 500 itérations.

L’individu 3 correspond aux composants C11-C12, l’individu 4 à C18-C19 et l’individu 5 à C14-C21, comme le montre la figure (Fig. 4.19).

A partir de ces constatations, nous pouvons dire que le paramètre du nombre d’itérations, joue un rôle très important pour le nombre de résultats trouvés. La même chose peut aussi être dite des autres paramètres, tels que le taux d’acceptation des solutions, les taux de croisement et celui de mutation. Les valeurs de ces taux doivent être soigneusement réglées afin d’optimiser au mieux les résultats de l’algorithme, car ils dépendent de la taille du système, du nombre d’individus souhaités et de la complexité de la table de signatures.

Notons enfin, que nous avons effectué des tests avec 10000 itérations et que le temps d’exécution n’a jamais dépassé une (01) seconde.


111

4.19 : Les nouveaux composants constituant des solutions (simples et combinées).


112

4. Organisation de l’application

Les résultats montrés dans ce chapitre sont extraits de l’application développée dans le cadre de ce travail. Nous avons pour cela utilisé l’environnement de développement intégré Borland Delphi version 7, sur un système d’exploitation Microsoft Windows Vista. Les tests quant à eux, ont étés réalisés sur un ordinateur doté d’un processeur Core2Duo cadencé à 1,83 GHz et d’une mémoire de 4 Go.

4.1. Structures et techniques utilisées

Pour développer cette application, nous avons adopté différentes techniques de développement, et nous avons utilisé plusieurs structures de données. Tout d’abord la table de signatures initiale sur laquelle travaille chaque algorithme a été représentée par un tableau dynamique permettant l’extension ou la réduction du nombre de lignes/colonnes.

4.1.1. Algorithme exact

Pour implémenter l’algorithme exact, nous avons utilisé un tableau dynamique afin de contenir la table de signatures étendue afin de pouvoir faire une extension du nombre de colonnes selon le nombre de combinaisons de fautes possibles.

L’algorithme qui a permis de calculer toutes les combinaisons possibles de composants est le suivant :

Données : n = Nombre de composants simples,

Bits = Chaîne de n caractère (‘0’ ou ‘1’),

Tableau des composants TAB = Tableau des noms de composants simples,

Nouv_Cmp = Nouvelle combinaison de composants à insérer dans TAB,

Résultats : Tableau TAB des différentes combinaisons possibles.

Début

// Initialisation de Bits à n ‘0’

Pour i de 1 à n

Bits ← Bits + ‘0’

// Boucle de calcul des possibilités

Répéter

Bits ← Bits + ‘1’ // Addition (+) dans le sens binaire

// Le nouveau composant est la combinaison de ceux qui sont à 1 dans Bits

Pour i de 1 à n

Si Bits[i] = ‘1’

Nouv_Cmp ← Nouv_Cmp + TAB[i]

// Insertion

Augmenter la longueur de TAB

TAB ← TAB + Nouv_Cmp

// Condition d’arrêt : 2n possibilités

Jusqu’à Bits ne contient que des ‘1’

Fin.


113

Il est clair que cet algorithme a une complexité exponentielle en O(2n), où n est le nombre de composants simples du système.

Ensuite, et concernant le parcours de la table de signatures et la comparaison des signatures avec celle de la faute, l’algorithme est de complexité polynômiale de l’ordre de O(n, m), avec n le nombre de colonnes et m le nombre de lignes du tableau.

4.1.2. Algorithme génétique

Pour implémenter l’algorithme génétique nous avons utilisé une structure d’objet « Individu » contenant plusieurs informations sur l’individu, à savoir, le bitmap des composants qu’il représente, la signature (somme des signatures de ses composants) ainsi que la fonction Objectif calculée pour cet individu. L’ensemble des individus de la population a été regroupé dans un tableau dynamique pour la représentation mémoire.

L’algorithme qui a permis d’appliquer les opérations génétiques est le suivant :

Données : Tableau des individus POP = Tableau de (bits, signature, fitness) de taille POP_SIZE,

n = Nombre de composants et longueur de POP[i].bits et de Ind1 et Ind2,

CROSS_RATE, MUTATE_RATE = Paramètres génétiques,

Ind1, Ind2 = Individus (bits, signature, fitness) de POP,

Bits = Chaîne de bits (0 ou 1),

Aleat = Nombre aléatoire généré automatiquement.

Résultats : Le tableau POP modifiés par les opérations génétiques.

Début

// Evaluation

Pour i de 1 à POP_SIZE

Evaluer POP[i] et calculer les Fitness des individus (soit POP[i].fitness)

// Application des opérations génétiques

// Sélection par roue de loterie

Pour i de 1 à POP_SIZE

Calculer Prob(i)

Choisir les deux individus de POP qui ont la plus grande Prob(i) : soit Ind1 et Ind2

// Croisement

Bits ← Ind1[CROSS_RATE..n]

Ind1[CROSS_RATE..n] ← Ind2[CROSS_RATE..n]

Ind2[CROSS_RATE..n] ← Bits

// Mutation

Pour j de 1 à n

Choisir Aleat entre 0 et 1

Si Aleat < MUTATE_RATE alors

Ind1[j] est inversée (devient 0 si c’était 1 et devient 1 si c’était 0)

Pour j de 1 à n

Choisir Aleat entre 0 et 1

Si Aleat < MUTATE_RATE alors

Ind2[j] est inversée (devient 0 si c’était 1 et devient 1 si c’était 0)


114

// Insertion

Les individus Ind1 et Ind2 sont insérés dans la population POP pour remplacer les individus qui ont

la Fitness la plus faible

// Cet algorithme doit être répété plusieurs fois jusqu’à la condition d’arrêt

Fin.

Cet algorithme a une complexité polynômiale de O(m, n), où m est le nombre d’individus de la population et n est le nombre de composants par individu.

4.2. Organigramme de l’application

La figure (Fig. 4.20) présente l’organigramme générale de l’application développée dans ce travail.

Fig. 4.20 : Organigramme général de l’application développée.

Table de signatures

+

Signature de faute observée

Algorithme exact Algorithme génétique

Table de signatures étendue

Création de la population initiale

Table de signatures étendue

optimisée

Comparaison avec la signature

de faute

Détermination des composants

en fautes et ceux qui sont

protégés

Opérations génétiques

Evaluation des générations

Détermination des composants

en fautes (simples

et combinés)

Options et paramétrages

Evaluation de la population

Options et paramétrages


115

5. Etude comparative des résultats des deux algorithmes

Dans l’exemple de l’algorithme exact, le temps total d’exécution sur la table de signatures de dix composants présentée, n’a guère dépassé une (01) seconde (exactement 0,938 sec). Mais après plusieurs exécutions, nous avons pu déterminer une moyenne du temps d’exécution que nous avons reporté sur le graphe de la figure (Fig. 4.21).

Fig. 4.21 : Evolution du temps d’exécution pour l’algorithme exact.

Cette estimation reste bien sûr dépendante de la mémoire vive disponible sur la machine de test ainsi que de son horloge interne, mais elle montre bien que les algorithmes exacts ne sont pas adaptés aux systèmes de taille importante.

Concernant l’algorithme génétique, la complexité temporelle n’est pas un souci majeur, mais c’est plutôt l’exactitude et la complétude des résultats obtenus. Ainsi ce ne sont pas toutes les solutions possibles qui sont trouvées dans un grand système, car l’algorithme a tendance à converger vers des solutions localement optimales parfois.

D’autre part, les résultats fournis par cet algorithme ne permettent pas de restituer les composants pouvant être protégés lors de l’apparition de la faute. En effet, le principe même de l’évolution (simulé par cet algorithme) élimine les éléments qui n’apportent aucune amélioration aux solutions, et écarte donc tous les composants pouvant être protégés.

Finalement, et comme il a été montré dans le tableau Tab. 3.2, les qualités des deux algorithmes dépendent de l’importance du système. Nous pouvons donc dire, qu’ils peuvent être utilisés de façon combinée afin que l’algorithme exact réagisse aux petits systèmes et que l’algorithme génétique intervienne dans le cas contraire.

0

5000

10000

15000

20000

25000

30000

35000

10 15 20 25 30

Temps (sec)

Nbr composants

Temps (sec)

Expon.

(Temps (sec))


116

6. Conclusion

Dans ce chapitre, nous avons présenté notre apport quand au problème du diagnostic multi-faute basé sur l’approche FDI. Nous nous somme intéressés à deux algorithmes, à savoir, l’algorithme exact et l’algorithme génétique. Nous avons aussi proposé quelques améliorations sur ces deux algorithmes par rapport à leurs versions initiales.

Des exemples ont été implémentés sur une application logicielle et les résultats ont été présentés et commentés. Ces résultats varient selon les paramètres retenus pour les deux algorithmes.

Enfin, une comparaison entre les résultats des deux méthodes a été développée, tenant compte des exemples utilisés ainsi que d’autres simulations effectuées sur l’application. Cette comparaison a permis de déduire que l’algorithme exact reste acceptable sur les petits systèmes car il engendre des résultats très précis. Cependant, sur les grands systèmes, l’algorithme génétique présente bien plus d’avantages en termes de complexité temporelle mais les résultats qu’il fournit manquent de précision et reste incomplets.

Conclusion générale

117


La mise en place des procédures de la surveillance constitue l’une des premières étapes dans l’automatisation des systèmes. Les méthodes sont basées principalement sur deux approches : les méthodes utilisant des modèles de diagnostic et celles utilisant des modèles opératoires. On les classe souvent en méthodes avec ou sans modèle. Les deux algorithmes traités dans cette étude sont classés parmi les méthodes avec modèle.

L’approche par analyse structurelle a apporté un surplus à la modélisation et l’analyse des systèmes complexes, car elle permet d’analyser tous les types de systèmes possibles : statique, dynamique, linéaire et non linéaire ; d’une part, en ne tenant compte que de l’aspect structurel du système, d’autre part, en s’intéressant uniquement à la présence ou l’absence d’une variable dans une contrainte, sans avoir à comprendre les détails physiques.

Dans notre travail de recherche, nous nous sommes intéressés à la possibilité de l’occurrence de plusieurs défaillances ou fautes simultanément dans un système. Le mécanisme de surveillance dans ce cas là, doit diagnostiquer la présence des différentes fautes en exploitant au mieux, les propriétés structurelles du système étudié.

Le diagnostic multi-faute (MFD) identifie les fautes multiples dans un système, à partir d'un ou plusieurs symptômes et peut être utilisé comme une partie d'un système global de diagnostic ou bien comme un système à part. Son importance est évidente dans les systèmes complexes modernes, car ces systèmes sont caractérisés par l’interconnexion de plusieurs composants et les relations décrivant les processus peuvent être de types différents (algébriques, différentielles, …). D’un autre coté, la complexité de ce type de diagnostic joue un rôle important dans la performance d’un système global.

Notre étude qui avait pour objet de déduire les possibilités de combinaisons des effets de plusieurs fautes sur les composants d’un système, sachant que cette situation n’est pas prise en compte par les propriétés structurelles, nous a permis d’analyser et de bien étudier le cas que nous avons illustrer par plusieurs algorithmes, en particulier par deux algorithmes qui sont complètement implémentés.

Le premier algorithme présenté repose sur l’approche habituelle qui consiste à trouver et à parcourir toutes les combinaisons possibles de fautes, avec tous ce qu’elle incombe comme inconvénients temporels et combinatoires. Le second, utilise une technique évolutionnaire, basée sur les notions d’évolution des espèces biologiques, afin de déduire à partir d’éléments simples, les combinaisons de fautes adéquates.

Notre contribution dans ce travail a porté donc essentiellement sur deux volets : d’une part, l’étude comparative et critique de deux algorithmes de diagnostic multi-faute, à savoir, l’algorithme exact et l’algorithme génétique, et d’autre part, l’implémentation de


118

ces deux méthodes afin d’explorer leurs possibilités et d’évaluer la qualité de leurs résultats respectifs.

Perspectives

Tout au long de cette étude, nous avons relevé quelques aspects dans le diagnostic multi-faute qui restent cependant à améliorer. D’abord, l’isolabilité multi-faute a été étudiée à partir de la table des signatures obtenue à partir des propriétés structurelles du système. A ce propos, et comme perspective, il nous parait nécessaire de revenir plus en amont et d’étudier la génération des RRAs dans le cas spécial des fautes multiples, en utilisant des graphes n-partis au lieu des graphes bipartis.

Dans le même contexte, il nous parait nécessaire d’ajouter une couche de filtrage des alarmes afin de réduire les effets en cascades entre faute et de simplifier encore plus la table des signatures.

Par ailleurs, sur le plan applicatif, il nous parait plus approprié d’intégrer un outil d’analyse structurel, afin de générer la table des signatures automatiquement au niveau de l’application développée, sans pour cela avoir à en faire la saisie par la méthode manuelle.

Références bibliographiques

119


[All 98] Alliot J. M. (1998), Techniques d'optimisation stochastique appliquées à certains problèmes du trafic aérien. Thèse d'habilitation PhD, Institut National Polytechnique de Toulouse.

[Ata 05] Atamtürk A., Savelsbergh M. W. P. (2005), Integer-programming software systems. Annals of Operations Research.

[Bas 93] Basseville M., Nikiforov I. (1993), Detection of abrupt changes : Theory and applications. Information and System Sciences Serie. T. Kailath ed., Prentice Hall, Englewoods Cliffs, New Jersey.

[Bel 04] Belaguid M. (2004), Optimisation des Algorithmes de Génération des RRAs en Analyse Structurelle pour la Surveillance. Thèse de Magister, Université d’Oran.

[Bel 06] Belaguid M., Haffaf H. (2006), Optimisation du processus de génération des relations de redondances analytiques pour l’analyse structurelle. Journée d’étude sur les technologies de l’information et de la communication JETIC’06, Béchar.

[Ben 07] Benabbassi Y., Haffaf H. (2007), Différentes méthodes d'analyse structurelle pour le diagnostic. 4th International Conference on Computer Integrated Manufacturing CIP’2007, Sétif.

[Ben 08] Benabbassi Y. (2008), Optimisation des algorithmes de la surveillance. Thèse de Magister, Centre Universitaire de Béchar.

[Ben 97] Bentley P. J., Wakefield J. P. (1997), Soft Computing in Engineering Design and Manifacturing - Chapitre Finding Acceptable Pareto-optimal Solutions Using Multiobjective Generic Algorithms. Springer-Verlag, London.

[Ber 75] Berge C. (1975), Théorie des graphes et ses applications, Dunod.

[Bla 03] Blanke M., Kinnaert M., Lunze J., Staroswiecki M. (2003), Fault diagnosis and fault tolerant control, Springer-Verlag, 2003.

[Blo 92] Blough D. M., Pelc A. (1992), Complexity of Fault Diagnosis in Comparison Models. IEEE Transactions on Computers, vol. 41, n° 3.

[Boy 03] Boyd S., Ghosh A., Magnani A. (2003), Branch and Bound Methods. Notes for EE392, Stanford University.


120

[Bus 02] Busson F. (2002), Les Bond-graphs Multiénergies pour la Modélisation et la Surveillance en Génie des Procédés. Thèse de Doctorat, Université de Sciences et technologies de Lille.

[Car 96] Carpentier T., Litwak R. (1996), Une Approche Structurelle pour le positionnement de Capteurs en Vue de la Surveillance. AGI’96, Automatique Génie informatique et Images, Forum des Doctorants.

[Car 99] Carpentier T. (1999), Placement de capteurs pour la surveillance de processus complexes, Doctorat de l’Université des Sciences et Technologies de Lille.

[Cas 94a] Cassar J. P., Staroswiecki M. (1994), Advanced Design of the Decision Procedure in Failure Detection and Isolation Systems, IFAC Symposium on Fault Detection, Supervision and Safety for Technical Processes SAFEPROCESS'94, Espoo.

[Cas 94b] Cassar J. P., Litwak R., Cocquempot V., Staroswiecki M. (1994), Approche structurelle de la conception de systèmes de surveillance pour des procédés industriels complexes. Revue Européenne Diagnostic et Sûreté de Fonctionnement, vol. 4, n°2.

[Cha 93] Chartrand G., Oellermann O. R. (1993), Applied and Algorithmic Graph Theory. Pure and Applied Mathematics. McGraw-Hill, Inc.

[Che 93] Chen J., Patton R.J., Zhang H.Y. (1993), A multi-criteria optimization approach to the design of robust fault detection algorithms, International Conference on Fault Diagnosis Tooldiag'93, Toulouse.

[Coe 01] Coello C. A. (2001), A short tutorial on evolutionary multiobjective optimization. First International Conference on Evolutionary Multi-Criterion Optimization, Springer-Verlag. Lecture Notes in Computer Science No. 1993.

[Coc 04] Cocquempot V. (2004), Contribution à la surveillance des systèmes industriels complexes. Thèse de PhD, Université de Lille.

[Cor 02] Cordier M-O., Dague P., Lévy F., Montmain J., Staroswiecki M., Travé-Massuyès L. (2002), Diagnosis of Complex Systems: Bridging the methodologies of the FDI and DX Communities. IEEE SMC Transactions.

[Dah 84] Dahbura A. T., Masson G. M. (1984), An O(n2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, vol. 33, n° 6.

[Dai 06] Daigle M., Koutsoukos X., Biswas G. (2006), Multiple Fault Diagnosis in Complex Physical Systems. Vanderbilt University. Nashville, TN 37235.


121

[Deb 00] Deb K., Agrawal S., Pratap A., Meyarivan T. (2000), A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation : NSGA-II, Parallel Problem Solving from Nature.

[Dec 91] Declerck P. (1991), Analyse structurale et fonctionnelle des grands systèmes. Application à une centrale PWR 900 MW, Ph.D. thesis, Université des sciences et technologies de Lille.

[Dor 92] Dorigo M. (1992), Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano.

[Dub 90] Dubuisson B. (1990), Diagnostic et reconnaissance des formes. Traité des Nouvelles Technologies. Série Diagnostic et Maintenance. ISBN 2-86601-240-2, Hermès, Paris.

[Duh 58] Duhlmage A. L., Mendelsohn N. S. (1958), Coverings of bipartite graphs. Canadian Journal of Mathematics n° 10.

[Dus 05] Düştegor D. (2005), Aspects algorithmiques de l’analyse structurelle pour la surveillance. Thèse de Doctorat, Université de Lille.

[Fed 98] Fedi G., Giomi R., Luchetta A., Manetti S., Piccirilli M. C. (1998), On the Application of Symbolic Techniques to the Multiple Fault Location in Low Testability Analog Circuits. IEEE Transactions on Circuits and Systems : Analog and Digital Signal Processing, vol. 45, n° 10.

[Fon 93] Fonseca C. M., Fleming P. J. (1993), Genetic Algorithms for Multiobjective Optimization : Formulation-Discussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms.

[Gen 96] Gentil S. (1996), Intelligence artificielle pour la surveillance des procédés continus. In Actes de l’école d’été d’automatique de Grenoble, Tome 1, Grenoble.

[Ger 91] Gertler J. (1991), Analytical redundancy methods in fault detection and isolation; survey and synthesis, IFAC Fault Detection, Supervision and Safety for Technical Processes.

[Ger 93] Gertler J. (1993), Analytical redundancy methods in fault detection and isolation. International Conference on Fault Diagnosis Tooldiag'93, Toulouse.

[Ger 98] Gertler J. (1998), Fault detection and diagnosis in engineering systems, Marcel Dekker Inc.

[Gol 89] Goldberg D. E (1989), Genetic algorithms in search, optimization and machine learning, Addison-Wesley Longman.


122

[Gol 94] Goldberg D. E. (1994), Algorithmes génétiques : Exploration, optimisation et apprentissage automatique. Traduit par Corruble V., Edition Addison- Wesley, France.

[Haf 97] Haffaf H. Tanguy G. D. (1997), Matroïd theory for structural analysis of systems modelled by bond-graphs. Scientific Computation and Applied Mathematics, 15th World Congress IMACS, Berlin.

[Haf 00] Haffaf H. (2000), Contribution à la résolution des problèmes combinatoires sur les bond-graphs par la théorie des Matroïdes. PhD thesis, Université d’Oran.

[Him 78] Himmelblau D.M. (1978), Fault detection and diagnosis in chemical and petrochemical processes. Elsevier, Amsterdam.

[Hui 04] Huisman L. M. (2004), Diagnosing arbitrary defects in logic designs using single location at a time (slat). IEEE Trans. Computer-Aided Design Integr. Circuits Systems, vol. 23, no. 1.

[Ise 97a] Isermann R. (1997), Supervision, fault detection and fault-diagnosis methods: An introduction. Control Engineering Practice, vol. 5, n° 5.

[Ise 97b] Isermann R. et Balle P. (1997), Trends in the application of model-based fault detection and diagnosis of technical processes. Control Engineering Practice, vol. 5, n° 5.

[Iza 01] Izadi-Zamanabadi R., (2001), Structural analysis approach for fault diagnosis and disturbance decoupling. Elsevier Science.

[Iza 02] Izadi-Zamanabadi R., Blanke M. (2002), Structural analysis for diagnosis. The matching problem revisited. Proceedings of the 15th IFAC World congress. Barcelona.

[Kal 60] Kalman R.E. (1960), A new approach to linear filtering and prediction problems. Trans. ASME, Journal of basic Engineering, vol. 82.

[Kle 87] De Kleer J., Williams B.C. (1987), Diagnosing multiple faults, Artificial Intelligence vol. 32, n° 1.

[Kle 92] De Kleer J., Mackworth A., Reiter, R. (1992), Characterizing diagnoses and systems, Artificial Intelligence vol. 56, n° 2-3.

[Kle 06] De Kleer J., Williams B.C. (2006), Diagnosing multiple faults, Xerox Palo Alto Research Center.

[Kno 00] Knowles J. D., Corne D. (2000), Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy, Evolutionary Computation, vol. 8, n° 2.


123

[Kry 02] Krysander M., Nyberg M. (2002), Structural Analysis for Fault Diagnosis of DAE Systems Utilizing Graph Theory and MSS Sets, Department of Electrical Engineering, Linköping University.

[Las 96] Lassaigne R., de Rougemont M. (1996), Logique et Complexité, Hermès. ISBN 2-86601-496-0.

[Lin 74] Lin C.T. (1974), Structural controllability, IEEE Transactions on Automatic Control, vol. 19, n° 3.

[Liu 05] Liu J. B., Veneris A. (2005), Incremental Fault Diagnosis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, n° 2,

[Lue 71] Luenberger D.G. (1971), An introduction to observers. IEEE Transactions on Automatic Control, vol. 16, n° 6.

[Luo 94] Luong M., Maquin D., Huynh C.T., Ragot J. (1994), Observability, redundancy, reliability, and integrated design of measurement systems, 2nd IFAC Symposium on Intelligent Components for Control Applications SICICA’94, Budapest.

[Maq 03] Maquin D. (2003), Surveillance des processus. Cours de 3ème année ENSEM.

[Moo 91] Moore R. E. (1991), Global optimization to prescribed accuracy. Computers and Mathematics with Applications, vol. 21, n° 6/7.

[Moy 88] Moyson F., Manderick B. (1988), The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Californie.

[Mra 04] Mrani Alaoui R. (2004), Conception d’un module de diagnostic à base des suites de bandes temporelles en vue de la supervision des procédés énergétique. Application en ligne à un générateur de vapeur. Thèse Doctorat, Université de Lille.

[Nie 98] Niedermayer D. (1998), An Introduction to Bayesian Networks and their Contemporary Applications.

[Odi 04] Odintsova N., Rish I., Ma S. (2004), Multi-fault Diagnosis in Dynamic Systems. IBM T.J. Watson Research Center.

[Ost 05] El Osta W. (2005), Surveillabilité Structurelle et Platitude pour le Diagnostic des Modèles Bond-graph Couplés. Thèse de Doctorat, Université de Sciences et technologies de Lille.

[Oul 05] Ould Bouamama B. (2005), Structural analysis using bipartite graphs.

[Par 96] Pareto, V. (1896), Cours d’économie politique. Rouge, Lausanne.


124

[Pat 91a] Patton R. J. (1991), Fault detection and diagnostic in aerospace systems using analytical redundancy. Computing and control engineering journal.

[Pat 91b] Patton R. J., Chen J. (1991), A review of parity space approaches to fault diagnosis. IFAC Symposium on Fault Detection, Supervision and Safety for Technical Processes SAFEPROCESS’91, Baden-Baden.

[Pat 00] Patton, R. J., Frank P., Clark R. (eds.) (2000), Issues of Fault Diagnosis for Dynamic Systems. Springer Verlag.

[Pau 81] Pau L.F. (1981), Failure diagnosis and performance monitoring. Marcel Dekker, New York.

[Pay 61] Paynter H. (1961), Analysis and design of engineering systems, MIT Press.

[Pen 87] Peng, Y., Reggia J. A. (1987), "A Probabilistic Causal Model for Diagnostic Problem Solving, Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference," in IEEE Transactions on Systems, Man and Cybernetics, vol. 17, n° 2.

[Pot 77] Potter J.E. et Suman M.C. (1977), Thresholdless redundancy management with arrays of skewed instruments. Integrity in Electronic, Flight Control Systems, AGARDOGRAPH-224.

[Rat 04] Rattfält L. (2004), A comparative study of two structural methods for fault isolability analysis, Master's thesis, Department of Vehicular Systems, Linköping University.

[Rei 87] Reiter R. (1987), A Theory of Diagnosis from First Principles. Artificial Intelligence, n° 32.

[Rya 00] Ryan C. (2000), Automatic Re-Engineering of Software using Genetic Programming. Kluwer Academic Publishers.

[Sch 85] Schaffer J. D., Grefenstette J. J. (1985), Multi-Objective Learning via Genetic Algorithms, International Joint Conference on Artificial Intelligence.

[Sek 04] Sekhri L., Toguyéni A. K. A., Craye E. (2004), Surveillabilité d’un système automatisé de production modélisé par un graphe fonctionnel. Laboratoire d’Automatique et d’Informatique Industrielle de Lille (L.A.I.L), Ecole Centrale de Lille. JESA vol. 38 n° 3-4, pages 243 à 268.

[Sho 74] Shortliffe E. H. (1974), Mycin : A rule-based computer program for advising physicians regarding anti-microbial therapy selection. Memo AIM, (251).

[Sri 94] Srinivas N., Deb K. (1994), Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms, Evolutionary Computation, vol. 2, n° 3.


125

[Sta 89] Staroswiecki M., Declerck P. (1989), Analytical Redundancy in Non-linear Interconnected Systems by means of Structural Analysis, IFAC / IMACS / IFORS Symposium on Advanced Information Processing in Automatic Control, AIPAC’ 89, Nancy.

[Sta 93] Staroswiecki M., Cassar J.-P., Cocquempot V. (1993), Generation of optimal structured residuals in the parity space, 12th IFAC Word Congress, Sydney, Australia, Vol. 5.

[Sta 00] Staroswiecki M., Cassar J.Ph., Declerck Ph. (2000), A structural framework for the design of FDI in large scale industrial plants. in Issue of Fault Diagnosis for Dynamic System. Ed. R. Patton, P. Frank and R. Clark, Springer Verlag.

[Ste 91] Stewart B. S., White C. C. (1991), Multiobjective A*, Journal of the ACM, vol. 38, n° 4.

[Sul 88] Sullivan G. F. (1988), An O(t3) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, vol. 37, n° 4.

[Tag 95] Tagina M. (1995), Application de la Modélisation Bond-graph à la Surveillance des Systèmes Complexes. Thèse de doctorat, Université des Sciences et Technologies de Lille.

[Tal 01] Talbi E. G. (2001), Méta-heuristiques pour l’optimisation combinatoire multi-objectif : Etat de l’art. Laboratoire d’Informatique Fondamentale de Lille, Université des Sciences et Technologies de Lille.

[Tha 07] Tharrault Y., Mourot G., Ragot J., Harkat M. F. (2007), Détection et Isolation de Défauts par Analyse en Composantes Principales Robuste.

[The 03] Theilliol D. (2003), Contribution à l’Etude et au Développement des Systèmes Tolérants aux Défauts : Diagnostic et Accommodation à Base de Modèles Linéaires et au-delà. Thèse de Doctorat, Université Nancy 1.

[Tuy 98] Tuyttens D. (1998), An Improved MOSA Method for Solving Multi-Objective Combinatorial Optimization Problems.

[Ven 02] Venkatasubramanian V., Rengaswamy R., Yin K., Kavuri S.N. (2002), A review of process fault detection and diagnosis - Part I : Quantitative model-based methods. School of Chemical Engineering, Perdue University, West Lafayette.

[Web 99] Weber P., Gentil S., Ripoll P., Foulloy L. (1999), Multiple Fault Detection and Isolation. 14th World Congress of IFAC. Beijing.


126

[Ulu 95] Ulungu E. L., Teghem J. (1995), The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. In Foundation of Computing and Decision Sciences, vol. 20.

[Xu 02] Xu A. (2002), Observateurs Adaptatifs Non-Linéaires et Diagnostic de Pannes. Thèse de Doctorat de l'Université de Rennes 1.

[Zit 99] Zitzler E., Thiele L. (1999), Multiobjective evolutionary algorithms : A comparative case study and the strength pareto approach, Evolutionary Computation, vol. 3.

[Zwi 95] Zwingelstein G. (1995), Diagnostic des défaillances. Théorie et pratique pour les systèmes industriels. Traité des Nouvelles Technologies. Série Diagnostic et Maintenance. Hermès, Paris.

Résumé

Ce mémoire présente une synthèse des méthodes de surveillance des systèmes complexes. Une étude détaillée est réalisée sur les approches existantes afin de les évaluer et de les comparer. On s’intéresse particulièrement au diagnostic sur la base des propriétés structurelles du système (méthode FDI) et on propose une extension de cette méthode afin de prendre en compte les possibilités d’occurrence de plusieurs fautes simultanément.

En effet, dans les systèmes industriels réels, plusieurs défaillances ou fautes peuvent apparaître simultanément et le but du diagnostic multi-faute (MFD) est d'identifier et de localiser ces fautes multiples.

Dans le cadre de ce mémoire, deux approches différentes du diagnostic multi-faute sont étudiées et leurs algorithmes sont implémentés afin de comparer leurs propriétés et leurs résultats. Il s’agit de l’algorithme dit « exact » et d’un algorithme génétique. Nous verrons les avantages et les inconvénients de chacune des deux méthodes et dans quels cas utiliser l’une ou l’autre.

Mots clés : Diagnostic de faute, Diagnostic multi-faute, Analyse structurelle, Relations de redondances analytiques (RRAs), Algorithmes génétiques.

Abstract

This thesis presents a synthesis of the methods of surveillance of complex systems. A detailed study is realized on existing approaches to estimate and compare them. We are particularly interested in the diagnosis on the basis of the structural properties of the system (FDI method) and we propose an extension for this method to take into account the possibilities of occurrence of several faults simultaneously.

Indeed, in real industrial systems, several failings or faults can appear simultaneously and the purpose of the multi-fault diagnosis (MFD) is to identify and to localize these multiple faults.

Within the framework of this thesis, two different approaches of the multi-fault diagnosis are studied and their algorithms are implemented to compare their properties and their results. It is about an "exact" algorithm and a genetic one. We shall see advantages and inconveniences of each of the two methods and in which cases to use one or the other.

Key words : Fault diagnosis, Multi-fault diagnosis, Structural analysis, Analytical redundancy relations (RRAs), Fault Detection and Isolation (FDI), Genetic algorithms,

Documents

POUR LE DIAGNOSTIC MULTI-FAUTE · Remerciements C’est avec beaucoup de gratitude et de sincérité, que je remercie mon Directeur de thèse, le Professeur HAFFAF Hafid du département