MAROUENE BEN JABEUR

RESOLUTION DU PROBLEME D'ALLOCATION OPTIMALE DE RESSOURCES MULTIPLES À

L'AIDE D'UN ALGORITHME GÉNÉTIQUE

Mémoire présenté à la Faculté des études supérieures de l'Université Laval dans le cadre du programme de maîtrise en informatique pour l'obtention du grade de maître es sciences (M.Sc.)

DEPARTEMENT D'INFORMATIQUE ET GENIE LOGICIEL FACULTÉ DES SCIENCES ET DE GÉNIE

UNIVERSITÉ LAVAL QUÉBEC

2010

© Marouene Ben Jabeur, 2010

Résumé

Les opérations de recherche et de sauvetage font partie des activités humanitaires que

le gouvernement canadien offre. Ces opérations doivent être mises à la disposition de tous les

vols aériens dans un espace de plus de vingt millions de kilomètres carrés et de tous les bateaux

naviguant dans les eaux maritimes du gouvernement fédéral dont les océans, le fleuve Saint-

Laurent et les Grands Lacs. L'ultime objectif que se fixe le gouvernement canadien en mettant à

l'œuvre ce genre d'opérations consiste à « prévenir les pertes de vie et les blessures en utilisant

les ressources privées et publiques pour alerter, répondre et aider dans les situations de

détresse ». Leur travail, humanitaire, consiste à trouver un objet perdu dans les meilleurs délais

afin de ne pas risquer de perdre des vies. Ce but pourrait être atteint si l'on arrive à trouver un

moyen d'affecter d'une manière optimale les ressources dont on dispose à des secteurs sur

lesquels les opérations de recherche vont être effectuées.

L'objectif de nos travaux est d'examiner de plus près et d'essayer de résoudre le

problème d'allocation de ressources multiples que vivent les centres de coordination des

opérations de recherche et de sauvetage. Ce problème se résume à mettre en place un plan

d'affectation des ressources à des zones de recherche permettant de maximiser l'efficience de

leurs utilisations et d'augmenter les chances de trouver des survivants en peu de temps.

Pour ce faire, nous définissons un algorithme génétique capable de trouver une solution

au problème à résoudre. Ensuite, nous adapterons la solution proposée afin de prendre en

charge et manipuler les contraintes imposées par le problème. Lors de nos expérimentations,

nous avons cherché à améliorer la performance et l'efficacité de notre algorithme en y

introduisant plusieurs méthodes basées sur le principe de la satisfaction des contraintes.

Notre bilan nous indique que nos meilleurs résultats sont obtenus en mettant en place

un algorithme génétique dont le fonctionnement des opérateurs de reproduction ne tolère

aucune violation de contraintes. En les comparant à ceux obtenus en résolvant le problème par

l'approche d'optimisation combinatoire, nous avons constaté qu'on n'a pas pu égaler le niveau

de succès atteint. Ceci est dû à l'aspect aléatoire sur lequel les algorithmes génétiques se basent

pour parcourir l'espace de recherche, sélectionner et améliorer une solution.

Ill

Dédicaces

A mon père

Je vous suis reconnaissant pour les conseils prodigieux et les directives insistantes dont vous

m'avez généreusement entouré.

Je vous sais gré de votre bienveillance, de vos attentions, de vos scrupules et des principes que

vous m'avez insinués.

A vous je dédie cet humble travail, preuve de mon éternelle gratitude.

A ma mère

Millions de douceurs qui ne vieillissent pas d'une ride, millions de prières, de bénédictions et

d'espoirs que ne fait taire aucune déconvenue.

Vous m'avez nourri de patience, de persévérance et d'ambitions, vous avez été capables de

lourds sacrifices, vous méritez tant d'amour.

Que mon travail soit le témoignage indubitable de cet amour et de ce legs précieux.

A mes frères et à tous les membres de ma famille

• A mon frère Bile! et ma sœur Maissa qui m'ont toujours encouragé par leur amour et

leur soutien.

• À mon cousin Nidhal pour m'avoir prêté main-forte.

A tous mes amis

Surtout Mahjoub, Hatem, Hamza, Shedly, Mohamed et Houcine pour leur aide respective et la

motivation que chacun m'a apportée à sa manière.

Un grand merci à tous ceux qui m'ont soutenu, aidé et que je risque d'oublier.

IV

Remerciements

A mon directeur Luc Lamontagne

Nulle dédicace ne saurait vous faire part de mes considérations les plus vives, de ma

reconnaissance la plus profonde et de mes remerciements les plus naturels.

Vous avez accepté de me faire profiter d'un précieux encadrement.

Vos conseils toujours prodigués avec amabilité m'ont été d'un immense soutien dans

l'élaboration de ce mémoire.

Permettez-moi de saluer en vous le don continu, le savoir intarissable, les remarques

constructives et la modestie inégalable.

Que vous trouviez dans ce mémoire le témoignage de ma sincère gratitude.

Aux professeurs, Dr Irène Abi-Zeid et Dr Bernard Moulin

Merci de vouloir accepter de lire et d'évaluer ce travail.

Table des matières

Résumé i Dédicaces iii Remerciements iv Table des matières v Table des figures viii Liste des tableaux x Introduction 1 Chapitre 1 Analyse du problème 3

1.1 Problématique 3 1.2 La théorie de recherche 5

1.2.1 La distribution de la densité de probabilité 6

1.2.2 La probabilité de détection 8

1.2.3 L'effort de recherche 10

1.3 Recours aux algorithmes génétiques 11 Chapitre 2 Revue de littérature 13

2.1 Les algorithmes génétiques 13 2.1.1 Introduction aux algorithmes génétiques 13

2.1.1.1 Historique 14 2.1.1.2 De la science génétique aux algorithmes génétiques 14 2.1.1.3 Vocabulaire emprunté à la Génétique 15

2.1.2 Description des Algorithmes Génétiques 17

2.1.2.1 Principes généraux 17 2.1.2.2 Description détaillée 19

2.1.3 Extensions et améliorations des algorithmes génétiques 26

2.1.3.1 La technique Élitiste 26 2.1.3.2 Algorithme génétique modifié 27

2.2 Les problèmes de satisfaction de contraintes 29 2.2.1 Présentation 29

2.2.2 Concepts et Notations 29

2.2.3 Méthodes de résolutions des problèmes de satisfaction de contraintes 33

2.2.3.1 Méthodes constructives 33 2.2.3.2 Méthodes de recherche locale 37 2.2.3.3 Méthodes à population 40

2.3 La manipulation des contraintes dans un algorithme génétique 41 2.3.1 Introduction 41

VI

2.3.2 Manipulation directe 42

2.3.2.1 La faisabilité des solutions 42 2.3.2.2 La consistance de contraintes 44 2.3.2.3 L'insertion d'heuristiques 46

2.3.3 Manipulation indirecte 51

2.3.3.1 Pondération des contraintes 51 2.3.3.2 Fonctions objectif modifiées 52 2.3.3.3 Fonctions de fitness adaptables 54

Chapitre 3. Approches de résolution 56 3.1 Schéma général d'un algorithme génétique 60 3.2 Algorithme génétique classique 63

3.2.1 Présentation du modèle 64

3.2.1.1 Génome 64 3.2.1.2 Création de la population initiale 71 3.2.1.3 Fonction objectif 72 3.2.1.4 Opérateurs de reproduction 74

3.2.2 Présentation et analyse des résultats 77

Chapitre 4. Manipulation des contraintes 83 4.1 Mécanisme de création de la population initiale 84

4.2 Opérateur de mutation 85

4.2.1 Opérateur de mutation avec étirement 86 4.2.2 Opérateur de mutation avec préservation de faisabilité 90 4.2.3 Opérateurs de mutation avec préservation de faisabilité garantissant une amélioration de la probabilité de succès 92

4.3 Présentation des versions du modèle implémentées 95

4.4 Présentation et analyse des résultats 97

4.4.1 Version 2 du modèle 98 4.4.2 Version 3 du modèle 100 4.4.3 Version 4 du modèle 103 4.4.4 Version 5 du modèle 106 4.4.5 Version 6 du modèle 109

4.5 Conclusion 112

Chapitre 5. Optimisation avec fonction de fitness variable 113 5.1 Présentation des modèles 114

5.1.1 Fitnessl 114 5.1.2 Fitness! 115

5.2 Présentation des versions du modèle implémentées 117

5.3 Présentation et analyse des résultats 118

VII

5.3.1 Version 7 du modèle 118 5.3.2 Version 8 du modèle 121

5.4 Comparaison des résultats des trois approches 126 5.5 Comparaison AG/ILOG Solver 128

Chapitre 6. Conclusion 131 Référence 133

V I I I

Table des figures

Figure 1- Un plan pour plusieurs unités de recherche 4 Figure 2- Carte de probabilité 7 Figure 3- Circuit de ratissage et largeur de balayage 8 Figure 4- Courbe de la fonction de portée latérale 9 Figure 5-Algorithme génétique classique 19 Figure 6-Codage par permutation 20 Figure 7-Codage par valeurs 20 Figure 8-Codage binaire 20 Figure 9-Le croisement à un point 24 Figure 10-La mutation avec le codage binaire 25 Figure 11-Principe de la technique Élitiste 27 Figure 12-Principe de l'algorithme génétique modifié 28 Figure 13-Exemple de répartition des ressources sur une grille donnée 57 Figure 14-Distribution "Point datum" de la probabilité de localisation sur une grille de recherche 58 Figure 15-Distribution "CSAD" de la probabilité de localisation sur une grille de recherche 59 Figure 16-Distribution "Line Datum" de la probabilité de localisation sur une grille de recherche 59 Figure 17-Fonction principale d'un algorithme génétique 62 Figure 18-Exemple de génome 65 Figure 19-Les abscisses et les ordonnées des deux points marqueurs d'un rectangle 66 Figure 20-Intersection de deux rectangles 67 Figure 21-Surface de superposition 68 Figure 22- Fonction de calcul du nombre d'intersection entre rectangles 69 Figure 23- Fonction de calcul de la surface de superposition entre rectangles 70 Figure 24- Fonction de création de population initiale 72 Figure 25-Formule de base de la fonction AQ fitness 74 Figure 26-Formule de la fonction deftness 74 Figure 27- Fonction de mutation 75 Figure 28-Croisement à un point 76 Figure 29-La variation du POS en fonction de p sur Point Grid (version 1) 81 Figure 30-Fonction de création de la population initiale avec préservation de faisabilité 85 Figure 31-Cas d'intersections de rectangles 87 Figure 32-Résolutions du premier cas d'intersection 88 Figure 33-Résolutions du deuxième cas d'intersection 89 Figure 34-Résolution du troisième et quatrième cas d'intersection 90 Figure 35- Fonction de mutation avec préservation de faisabilité 91 Figure 36- Fonction de mutation avec préservation de faisabilité et amélioration de probabilité 1 93 Figure 37- Fonction de mutation avec préservation de faisabilité et amélioration de probabilité 2 95 Figure 38-Fonction deftness selon le modèle de Carlson 115

IX

Figure 39-Fonction de fitness selon le modèle de Joines et Houk 116 Figure 40-La variation du POS en fonction de P sur Point Grid (version7) 121 Figure 41-La variation du taux d'infaisabilité POS en fonction de a sur Line Grid (version8) 124

Liste des tableaux

Tableau 1-Algorithme ESP-GA 47 Tableau 2-Algorithme H-GA 48 Tableau 3-Algorithme Arc-GA 51 Chapitre 3. Approches de résolution 56 Tableau 4-Tableau récapitulatif de la version 1 de l'algorithme 78 Tableau 5-Résultats obtenus avec la versionl de l'algorithme 80 Tableau 6-Tableau récapitulatif de la version 2 du modèle 98 Tableau 7-Résultats obtenus avec la version2 de l'algorithme 99 Tableau 8-Tableau récapitulatif de la version 3 du modèle 101 Tableau 9-Résultats obtenus avec la version3 de l'algorithme 102 Tableau 10-Tableau récapitulatif de la version 4 du modèle 103 Tableau 11-Résultats obtenus avec la version4 de l'algorithme 105 Tableau 13-Résultats obtenus avec la version5 de l'algorithme 108 Tableau 14-Tableau récapitulatif de la version 6 du modèle 109 Tableau 15-Résultats obtenus avec la versionô de l'algorithme 111 Tableau 16-Tableau récapitulatif de la version 7 de l'algorithme 118 Tableau 17-Résultats obtenus avec la version7 de l'algorithme 120 Tableau 18 -Tableau récapitulatif de la version 8 de l'algorithme 122 Tableau 19-Résultats obtenus avec la version8 de l'algorithme 123 Tableau 20-Comparaison des résultats des versions 1,6 et 7 127 Tableau 21-Résultats obtenus avec ILOG Solver 129 Tableau 22-Meilleures moyennes des POS par scénario de recherche 129

Introduction

Nous abordons dans le présent travail le problème de l'allocation optimale de

ressources. La résolution de ce problème permet une optimisation des plans de recherches

élaborés par les centres de coordination des opérations de recherche et de sauvetage du

Canada et ceci dans le but de trouver un objet perdu dans le meilleur des délais. Ces opérations

sont effectuées par des unités de recherche (avions) qui survolent des aires de recherche

présentant les meilleures chances de trouver l'objet recherché. La principale tâche à assurer

consiste à trouver l'assignation (Unité de recherche - Aire de recherche) qui possède une

probabilité de succès maximale. Cette tâche semble être difficile à réaliser vu l'espace de

solutions important dont nous pouvons disposer. Le problème que nous devons résoudre est

donc considéré comme un problème d'optimisation combinatoire.

Les méthodes de résolution traditionnelles telles les méthodes d'exploration

arborescente ou énumératives s'avèrent prohibitives en termes de temps de calcul. Pour traiter

le genre de problèmes semblables à celui que nous rencontrons, nous devons donc faire appel à

des approches de résolution approximatives : nous troquons alors la garantie d'optimalité

présente dans les méthodes exactes contre l'espérance d'obtenir une solution de bonne qualité

en un temps raisonnable. Par ailleurs, diverses techniques ont été développées pour résoudre

les problèmes d'optimisation combinatoire. Celles-ci peuvent être classées sous différentes

catégories : constructives, stochastiques, etc. Ces dernières sont incapables de progresser au-

delà du premier optimum local rencontré. Or la plupart des problèmes d'optimisation

combinatoire comportent de nombreux optima locaux dont la valeur peut être fort éloignée de

celle des optima globaux.

Pour faire face à cette situation, plusieurs approches ont été développées dont

notamment les algorithmes génétiques. L'utilisation de ces algorithmes constitue une

alternative avantageuse vu leur capacité de surmonter l'obstacle de l'optimalité locale, leur

flexibilité et leur grande adaptabilité. Ces atouts leur permettent aussi une manipulation aisée

de contraintes qu'on peut trouver dans des problèmes réels.

L'objectif de ce travail est d'étudier les principes fondamentaux des algorithmes

génétiques et d'examiner les différentes pistes leur permettant de prendre en considération la

satisfaction de contraintes et ceci afin de développer un algorithme génétique permettant de

résoudre le problème de l'allocation optimale de ressources.

Ce mémoire est divisé en quatre parties. Nous présentons dans la première une analyse

du problème.

La deuxième partie est consacrée à la présentation de la revue de littérature des

approches que la résolution de problème fait intervenir. Nous abordons en premier lieu les

algorithmes génétiques, par la suite, nous nous intéressons aux problèmes de satisfaction de

contraintes. Nous terminons cette section par l'exposition des différentes méthodes utilisées

pour pouvoir manipuler des contraintes dans un algorithme génétique.

La troisième partie est consacrée à la présentation de nos contributions. Nous allons

tout d'abord proposer un algorithme génétique classique capable de résoudre le problème.

Nous présentons, par la suite, les différentes versions améliorées que nous avons pu

implémenter en nous basant sur l'algorithme décrit dans le premier chapitre de cette partie.

Nous terminons cette partie avec une comparaison des résultats obtenus avec les différentes

versions de l'algorithme. Les meilleurs résultats seront par la suite comparés à ceux obtenus

avec ILOG Solver pour la résolution du même problème.

Nous conclurons ce mémoire par une synthèse du travail effectué et une suggestion de

quelques pistes d'amélioration.

Chapitre 1 Analyse du problème

1.1 Problématique

Nous nous intéressons dans le présent travail aux opérations de recherche et de

sauvetage connues sous le nom des opérations SAR (Search And Rescue). Ayant des objectifs

humanitaires, elles consistent à chercher et prêter assistance aux personnes qui sont (ou qui

risquent d'être) en détresse ou qui font face à un réel danger de perte de vie. Ces opérations

peuvent intervenir lors d'incidents aéronautiques (avions), maritimes (bateaux, sous-marins,...)

ou terrestres (personnes perdues ou portées disparues).

Dans le cas où l'un de ces trois types d'incidents se produirait, les coordonnateurs des

missions de recherche seront les premiers à être avertis. La tâche qui leur est confiée consiste à

planifier, coordonner et diriger les opérations de recherche. Le coordonnateur des missions de

recherche est appelé à se mobiliser dès la réception d'une alerte. La première tâche à accomplir,

dans ce cas, est de déterminer le degré d'urgence de l'incident. S'il s'agit d'une situation de

détresse, il doit envoyer immédiatement une première équipe d'exploration pour effectuer une

recherche initiale. Si l'on n'arrive pas à établir un contact avec l'objet perdu après une certaine

période de temps, l'incident dont on veut limiter les dégâts sera classé comme un incident qui

nécessite une opération de recherche majeure. Une telle opération exige d'une part que les

bases de commandement soient installées sur un secteur assez proche de la zone de recherche

et d'autre part que le nombre d'unités suffise pour couvrir le plus possible cette zone et pour

accélérer les recherches. C'est ce dernier élément qui rend la planification des recherches une

tâche de plus en plus ardue pour les coordonnateurs de missions, surtout s'ils comptent opérer

sur des zones assez larges.

En fait, cette tâche de planification consiste à vérifier la disponibilité des ressources, à

sélectionner les ressources nécessaires et à déterminer les aires de recherches. Ces éléments

servent à développer un plan de recherche qui permet la distribution optimale des ressources à

travers les aires de recherche identifiées. Un exemple de plan de recherche est illustré dans la

figure 1.

y A r - " ^ T * i i 2 3 4 5

1

-u X J I L Ztl -i T L ► 6 7 8 9 K

1 " * '

y T y X y - k. u \ ~ m . . . . . . . ,

• n 12 J " 13 M 14 j 15 /

1 / 1 ^ /

^ L J t 17f 18 19. t 20

T-++f V-H f 1 1 1 i i 1 1 v / x 1 /

Ressources Aires de recherche

Figure 1- Un plan pour plusieurs unités de recherche

Pour développer un plan de recherche, le coordonnateur des missions de recherche doit

considérer plusieurs facteurs, dont les altitudes, la dimension de l'aire de recherche, la taille de

l'objet recherché, le type de capteurs et de végétation. II est aussi recommandé de tenir compte

de la couverture désirée de la zone et du circuit de ratissage des unités de recherches. En les

prenant en considération, il s'assure qu'aucun des secteurs constituant la zone globale de

recherche ne sera balayé par plus d'une unité de recherche. Ces secteurs sont délimités de

manière à former des rectangles disjoints représentant les sous-secteurs sur lesquels on place

l'effort disponible pour élaborer le plan de recherche à suivre. L'objectif à atteindre est de

distribuer l'effort global sur des secteurs rectangulaires disjoints de manière à maximiser les

chances de retrouver l'objet perdu.

En partant de cette description, nous pouvons considérer le problème auquel nous

faisons face comme un problème de recherche. En général, pour résoudre ce genre de

problème, on fait appel aux principes de la théorie de recherche. Cette théorie est abordée dans

la section suivante.

1.2 La théorie de recherche

La théorie de la recherche [RICH 86] a vu le jour durant la deuxième guerre mondiale

avec les travaux de B.O. Koopman et ses collègues du groupe de recherche sur les opérations de

lutte contre les sous-marins de guerre. P.M. Morse, directeur de ce groupe à cette époque, a

contribué à l'instauration de plusieurs concepts fondamentaux de la théorie de la recherche tels

que la largeur et le taux de balayage. C'est à partir de ce temps que cette théorie a commencé à

évoluer pour devenir plus tard une discipline majeure à laquelle on fait référence dans le

domaine des opérations de recherche. Partant de la recherche sous-marine, son application

s'étend sur tout type de recherches, dont la surveillance spatiale.

Cette théorie consiste à rechercher un ou plusieurs objets dans un espace donné en

mettant le maximum de chances pour les trouver avec les moyens disponibles dans les meilleurs

délais. Pour pouvoir examiner de plus près les bases de cette théorie, nous énumérons les

différentes étapes [GUEN 59] par lesquelles toute opération de recherche passe :

L'évaluation de la loi de répartition de l'objet recherché dans l'espace où il est censé

se trouver;

Le calcul de la probabilité de détection de l'objectif lorsqu'il est dans le secteur où on

le cherche;

La répartition optimale de l'effort disponible.

Ces étapes correspondent respectivement à trois concepts qui dominent la théorie de la

recherche. Ces derniers, présentés par J.R. Frost dans [FRO 99], sont :

La distribution de la densité de probabilité;

La probabilité de détection;

L'effort de recherche.

1.2.1 La distribution de la densité de probabilité

Ce facteur intervient lors de la première étape de la recherche qui consiste à estimer le

secteur dans lequel l'objet perdu se trouve.

L'objectif est de déterminer non seulement le lieu où les recherches vont être

effectuées, mais aussi la manière avec laquelle l'effort disponible va être déployé. Un facteur

essentiel, auquel on fait référence pour décider de l'effort à placer dans chacune des portions

de l'aire de recherche, correspond à l'estimation de la répartition de la densité de probabilité

sur l'espace de recherche. Cette probabilité, comme le montre la formule suivante, est calculée

en fonction de la probabilité de localisation et la taille de la zone de recherche.

POC Tien - A

Dans cette formule, on désigne par POC la probabilité de localisation qui correspond à la

probabilité que l'objet recherché soit contenu dans une zone de recherche de taille A.

La distribution de la densité de probabilité est souvent représentée sous une carte de

probabilité couvrant une grille donnée. Les cellules de cette dernière correspondent aux sous-

secteurs de la zone de recherche à balayer. Chacune d'elles est étiquetée avec sa probabilité de

localisation. Ce type d'illustration a l'avantage de montrer à la fois la probabilité que chaque

cellule possède et l'emplacement où la probabilité de densité est la plus élevée [FRO 99] (Figure

2).

Cellules

Figure 2- Carte de probabilité

Ainsi, pour déterminer la zone de recherche où l'objectif se trouve, nous devons bien

estimer la probabilité de localisation. Ceci requiert une bonne évaluation des informations

disponibles ainsi qu'une continuelle recherche d'informations additionnelles collectées à partir

des différentes sources disponibles. Ces informations rassemblent en général tout type de

données capables de nous conduire à l'emplacement probable de l'objet perdu. Par exemple, les

coordonnées de l'objet lors de la dernière liaison qu'on a pu établir avec. Ces informations

peuvent être aussi constituées de données historiques ou de données statistiques collectées

dans des situations similaires à celle à laquelle on fait face.

En ce qui concerne les opérations SAR, ces informations sont fréquemment obtenues à

partir de différentes sources et ne sont pas toujours consistantes. Cependant, ces données

tendent à constituer un nombre d'ensembles. Chacun de ces derniers correspond à un scénario

détaillant les circonstances dans lesquelles l'objet a été perdu et où il pourrait être situé. Une

analyse attentive de chaque scénario est donc recommandée pour pouvoir bien estimer

l'emplacement probable de l'objectif. Ces estimations sont par la suite quantifiées sous forme

de cartes de probabilités. Cela permet de définir la distribution de la densité de probabilité des

scénarios. Ces derniers vont être pondérés selon la perception du planificateur, de leur

précision, leur fiabilité et leur importance.

1.2.2 La probabilité de détection

Cette probabilité, désignée par POD (Probability Of Detection), correspond à la

probabilité de détecter l'objet perdu à l'intérieur d'un secteur donné. Elle peut être considérée

comme une mesure de la performance du capteur dans le sens où elle indique la capacité d'un

capteur particulier à repérer un type particulier d'objets sous un ensemble de conditions

opérationnelles et environnementales. Elle peut être aussi perçue comme une mesure indiquant

à quel point la zone de recherche a été couverte par les différentes unités de recherche.

La probabilité de détection telle que définie par J.R Frost [FRO 99] est calculée suivant

cette formule :

POD = 1 - e~c où C = w / s

C correspond à la couverture de la recherche. Elle est obtenue en fonction de la largeur de

balayage Wet le circuit de ratissage S.

Dans le cas où nous nous référons au modèle commun de recherche, le circuit de

ratissage S correspond à la distance séparant les pistes empruntées par l'unité de recherche

(Figure 3). II est le résultat de la division de A, la taille de la zone de recherche, par z, l'effort de

recherche à déployer. Ce dernier représente la distance à parcourir par l'unité de recherche.

k"i±tH"f"t——— OBJET * ^ ~ .. y , _ i _ _ _ _ _ _ _ _ _ _ _ _

± : . -

-L ' • L _ „ _ L_ j> . ^ y ,

j

Point de dé aÀt

I T T Figure 3- Circuit de ratissage et largeur de balayage

Ce modèle de recherche correspond au modèle parallèle de recherche. II se différencie

des autres modèles par ses pistes de recherche parfaitement droites, parallèles et

uniformément espacées.

La largeur de balayage, quant à elle, est une mesure du potentiel de détection d'un

détecteur sous des conditions spécifiques. Elle est, en général, exprimée en miles nautiques

pour les recherches aériennes. Pour une distribution uniforme d'objets sur une zone, la largeur

de balayage W est calculée suivant cette formule :

. . . _ Nombre d'objets détectés par unité de temps (Nombre d'objets par zone unitaire)x(yitesse du chercheur)

Où toutes les valeurs sont des moyennes sur une période d'échantillonnage statistiquement

significative.

Théoriquement, la largeur de balayage correspond à la largeur se trouvant en dessous

de la courbe de la fonction de portée latérale P(x). Cette fonction, appelée aussi « Profil de

détection », caractérise les capteurs utilisés dans les opérations de recherche. Elle décrit la

probabilité de détecter un objet se trouvant à une distance X de la trajectoire emprunté par

l'unité de recherche (Figure 3). Un profile de détection possible est présenté dans la figure 4.

Ceci correspond à la courbe de portée latérale pour une détection visuelle. Ce modèle a été

développé par B.O. Koopman pour la détection d'objets sur les océans et les mers. Néanmoins, il

est le modèle le plus reconnu et utilisé dans les opérations SAR.

• P<«)

W = Jp{x)dx

Figure 4- Courbe de la fonction de portée latérale

Selon J.R Frost, il existe trois classes de facteurs qui peuvent affecter la détection et par

conséquent la largeur de balayage :

Les caractéristiques de l'objet recherché incluant sa taille, sa couleur, sa luminosité,

etc.

Les caractéristiques des détecteurs utilisés : leur type du capteur, les capacités de

l'observateur, le genre d'engin utilisé pour assurer les recherches et la vitesse du

chercheur par rapport à celle de l'objet cherché.

Les conditions environnementales durant les recherches et sur leurs lieux. On

prend par exemple le type du terrain sur lequel les recherches s'effectuent, son

taux de couverture, les conditions d'éclairage, etc.

Pour résumer, nous pouvons dire que la largeur de balayage dépend essentiellement de

l'endroit considéré, des conditions ambiantes et de la méthode de recherche utilisée.

1.2.3 L'effort de recherche

L'effort total d'une mission de recherche, souvent exprimé en miles nautiques,

correspondant à la distance parcourue par les unités de recherche durant l'opération de

recherche et de sauvetage. L'ultime objectif des planificateurs de ces opérations est de mettre

en place un plan de déploiement de l'effort disponible sur l'espace de recherche de manière à

maximiser les chances de trouver l'objet perdu dans le minimum des délais. Ce plan de

recherche doit correspondre à la meilleure exploitation des ressources disponibles. L'efficacité

de telles opérations est mesurée à l'aide d'une valeur appelée probabilité de succès. Cette

dernière est définie comme étant le produit de la probabilité que la zone balayée contienne

l'objet perdu au moment de la recherche (POC) et la probabilité de le détecter s'il y est (POD).

Selon J.R. Frost [FRO 99], la formule générale, à utiliser pour calculer la probabilité de

succès est la suivante :

POS = POD x POC

10

L'efficacité globale des opérations de recherche menées est donnée par la probabilité de

succès globale cumulative. Cette valeur correspond à la somme des valeurs des probabilités de

succès sur tous les segments de l'espace de recherche depuis le début des opérations.

Le bon fonctionnement des opérations de recherche est mesuré par la vitesse avec

laquelle la probabilité de succès augmente au fur et à mesure que la recherche avance. Le plan

qui permet d'élever la probabilité de succès à son taux maximal est appelé plan de recherche

optimal. Le plan, établi avec le même effort, qui permet d'avoir la même probabilité de succès,

mais qui a mis plus de temps pour être finalisé ou qui n'a pas élevé la probabilité de succès à son

taux maximal possible depuis les premières étapes de la recherche est appelé plan de recherche

T-optimal où T est le temps passé pour épuiser l'effort qu'on lui a alloué.

1.3 Recours aux algorithmes génétiques

Résoudre le problème d'allocation optimale de ressources revient à trouver un moyen

pour maximiser la probabilité de succès dans des secteurs, disjoints, sur lesquels les opérations

de recherche vont être menées. Pour y arriver, nous avons opté pour l'utilisation des

algorithmes génétiques.

Cette décision a été, d'abord, prise grâce aux succès qu'ont connus les algorithmes

génétiques avec les problèmes à espace important de recherche. La taille considérable de notre

problème est due au nombre d'unités de recherche et à la grandeur de la taille des zones

géographiques. La deuxième raison est liée à l'utilisation de l'aspect aléatoire lors du choix des

rectangles à manipuler. Ces derniers constituent l'espace de recherche duquel la solution au

problème va être extraite. C'est une bonne méthode à utiliser pour parcourir le plus possible

l'espace de recherche et pour assurer la diversification des solutions. Cette particularité est aussi

assurée par les algorithmes génétiques et ceci ne peut que confirmer notre choix.

11

Notre problème, en plus du fait qu'il est considéré comme un problème d'optimisation,

fait partie des problèmes de satisfaction de contraintes. La solution à trouver doit à la fois offrir

le maximum de chances de retrouver l'objet perdu (une probabilité de succès maximale) et

satisfaire la totalité des contraintes opérationnelles. Par exemple, un secteur ne peut être

balayé que par une et une seule unité de recherche.

Ainsi, il est fortement recommandé de pouvoir manipuler les contraintes imposées dans

le modèle de résolution. Cette option est aussi réalisable avec les algorithmes génétiques.

Ces raisons nous motivent à nous servir des algorithmes génétiques pour implémenter

nos tentatives de résolution. Nous présentons cette famille d'algorithmes dans le chapitre

suivant.

12

Chapitre 2 Revue de littérature

Ce chapitre comporte une description détaillée de chacune des trois approches utilisées

dans la résolution du problème d'allocation optimale des ressources. La première partie porte

sur les algorithmes génétiques. Dans la deuxième, nous présentons les problèmes de

satisfaction de contraintes. Nous terminons ce chapitre par l'énumération et l'explication des

différentes méthodes qu'on peut mettre en place afin d'arriver à manipuler des contraintes

dans un algorithme génétique.

2.1 Les algorithmes génétiques

Cette section comporte à son tour trois sous-sections. Dans la première, nous

introduisons les algorithmes génétiques. La deuxième, quant à elle, englobe une présentation

des principes généraux de ces algorithmes ainsi qu'une description détaillée des éléments qui

les composent. Nous terminons cette section par l'évocation de quelques améliorations des

algorithmes génétiques proposées dans la littérature.

2.1.1 Introduction aux algorithmes génétiques

La programmation génétique fait partie des algorithmes évolutionnaires. L'idée

commune à tous ces algorithmes est d'appliquer le principe de la sélection naturelle à des objets

informatiques. La famille des algorithmes évolutionnaires comprend quatre classes principales :

la programmation évolutive, les stratégies évolutionnaires, la programmation génétique, et les

algorithmes génétiques (AG). D'une manière générale, les algorithmes génétiques sont des

algorithmes d'optimisation s'appuyant sur des techniques dérivées de la génétique et des

13

mécanismes d'évolution de la nature : croisements, mutations, sélections, etc. L'idée de base de

ces derniers est de simuler les méthodes d'amélioration génétique ou de sélection naturelle.

2.1.1.1 Historique

Dans les années 1960, John Holland étudie les systèmes évolutifs et, en 1975, il introduit

le premier modèle formel des algorithmes génétiques. Ce modèle servira de base aux

recherches ultérieures. En 1989, David Goldberg publie un ouvrage de vulgarisation des

algorithmes génétiques [GOLD 89]. Au cours des années 1990, Davis adapte les algorithmes

génétiques pour remédier à des problèmes d'optimisation en développant une analogie entre

un individu dans une population et une solution d'un problème dans un ensemble de solutions

[DAV 91]. Ces années ont été aussi marquées par la programmation d'une panoplie

d'algorithmes génétiques transcrits en C++, appelée Galib. Cette librairie contient des outils pour

des problèmes d'optimisation en utilisant les AG. Elle est conçue pour servir de support de

programmation.

Ces dernières années, les méthodes basées sur les algorithmes génétiques ont connu un

succès grandissant dans les domaines de la recherche opérationnelle et de l'intelligence

artificielle, où elles sont utilisées pour résoudre des problèmes d'optimisation et

d'apprentissage. Elles se sont aussi révélées efficaces dans des domaines variés tels que

l'économie, les sciences politiques, la psychologie, l'immunologie, la biologie ou l'informatique.

2.1.1.2 De la science génétique aux algorithmes génétiques

Dans une population, l'individu est résumé par un seul chromosome (individu haploïde).

Les chromosomes sont eux-mêmes constitués de gènes qui contiennent les caractères

héréditaires de l'individu. On retrouve aussi les principes fondamentaux de l'évolution naturelle,

à savoir les principes de sélection, de croisement, de mutation, etc.

14

2.1.1.2.1 Le croisement ou évolution naturelle

Le crossover, qui symbolise la reproduction sexuée (toujours par métaphore du

mécanisme de sélection naturelle), est une des étapes importantes de l'AG. C'est l'instrument

majeur des innovations au sein de l'algorithme. C'est lui qui insuffle le changement. II peut être

effectué de plusieurs manières. La plus courante d'entre elles croise les chaînes de caractères de

deux individus parents pour former des chaînes de caractère enfants. Le taux de croisement est

en général assez fort et se situe entre 70 % et 95 % de la population totale.

2.1.1.2.2 La mutation ou évolution accidentelle

Comme pour le croisement, la mutation vise à modifier de façon aléatoire une partie de

la population. C'est le second mécanisme d'innovation d'un algorithme génétique. Ici, le principe

est de choisir une valeur de remplacement aléatoire pour l'un des gènes des individus de la

population concernée. D'autres méthodes de mutation peuvent aussi être utilisées comme la

mutation par soustraction numérique fixée sur un gène, ou remplacée par une valeur aléatoire

choisie dans un sous ensemble de valeur. À la différence du croisement, le taux de mutation est

généralement faible et se situe entre 0.2 % et 1 % de la population totale. Ce taux permet

d'éviter une dispersion aléatoire de la population et n'entraîne que quelques modifications sur

un nombre limité d'individus. La mutation prend une place de plus en plus importante dans les

algorithmes génétiques, alors qu'il y a encore quelques années son rôle était considéré comme

accessoire.

2.1.1.3 Vocabulaire emprunté à la Génétique

Individu :

C'est une entité représentant une solution potentielle du problème.

Population :

Ensemble d'individus qui doivent évoluer à travers un certain nombre de générations.

15

Chromosomes :

Un chromosome est une unité organisatrice qui code la structure des êtres vivants. Ce sont des

chaînes de molécules qui se trouvent dans le noyau de toute cellule de tout être vivant

renfermant l'information génétique de chacun. Dans les algorithmes génétiques classiques, les

chromosomes sont les ensembles à partir desquels sont déterminées les solutions. Un

chromosome correspond à un individu. Ce qui peut facilement induire en erreur, car dans la

nature un individu (ou organisme) possède plusieurs paires de chromosomes (l'homme possède

23 paires de chromosomes). II est donc important de noter que nous allons parler d'individu

mono chromosomique.

Population de chromosomes :

Une population de chromosomes est un ensemble limité d'individus de même espèce.

Gène :

C'est un point de chromosome responsable d'un caractère héréditaire.

Sélection naturelle :

La sélection naturelle correspond simplement à un tri des individus les plus aptes à survivre ou à

se reproduire, quelle que soit la raison pour laquelle ils possèdent une telle aptitude. En effet,

les espèces naturelles qui possèdent des caractéristiques plus utiles que les autres ont une

probabilité plus forte de s'adapter à leur environnement.

Évolution :

L'évolution génétique est le processus qui opère sur les chromosomes et qui détermine le

développement des êtres vivants. Elle tend à sélectionner les gènes les plus stables et à les

reproduire.

L'information sur la population est contenue dans l'ensemble des gènes et transmise aux

générations futures par le biais de l'hérédité.

16

2.1.2 Description des Algorithmes Génétiques

2.1.2.1 Principes généraux

Les algorithmes génétiques suivent un processus bien établi qui peut être défini comme

un cycle de l'évolution. Ils travaillent sur une population composée d'individus, tous différents,

qui sont des solutions potentielles du problème à résoudre. Un algorithme génétique recherche

le ou les extrema d'une fonction définie sur un espace de données. Pour l'utiliser, nous devons

disposer des cinq éléments suivants :

Un principe de codage de l'élément de population

Cette étape associe à chacun des points de l'espace d'état une structure de données.

Elle se place généralement après une phase de modélisation mathématique du problème traité.

La qualité du codage des données conditionne le succès des algorithmes génétiques. Les

codages binaires ont été très utilisés à l'origine. Les codages réels sont désormais largement

utilisés, notamment dans les domaines applicatifs pour l'optimisation de problèmes à variables

réelles.

Un mécanisme de génération de la population initiale

Ce mécanisme doit être capable de produire une population d'individus non homogène

qui servira de base pour les générations futures. Le choix de la population initiale est important,

car il peut rendre plus ou moins rapide la convergence vers l'optimum global.

Une fonction à optimiser

Celle-ci retourne une valeur réelle positive appelée fitness ou fonction d'évaluation de

l'individu.

17

Les opérateurs

Ils permettent de diversifier la population au cours des générations et d'explorer

l'espace d'états. L'opérateur de croisement recompose les gènes d'individus existant dans la

population. L'opérateur de mutation a pour but de garantir le plus possible l'exploration de

l'espace d'états.

Les paramètres de dimensionnement

Parmi ces paramètres, nous trouvons : la taille de la population, le nombre total de

générations ou critère d'arrêt, les probabilités d'application des opérateurs de croisement et de

mutation.

En résumé, pour mettre en œuvre un algorithme génétique, il est nécessaire de définir :

Une « représentation génétique » du problème, c'est-à-dire d'un codage approprié des

solutions sous forme de chromosomes;

Un moyen de création la population initiale;

Une fonction d'évaluation pour mesurer la force de chaque chromosome;

Un mode de sélection des chromosomes à reproduire;

Les paramètres qu'utilise l'algorithme (taille de la population, probabilité d'appliquer tel

ou tel opérateur).

L'algorithme d'optimisation

Dans la figure 5, nous présentons le pseudo-code de l'algorithme génétique classique

Données

Définir un codage du problème

Fixer la probabilité de croisement et de mutation

Initialisation

Générer une population initiale P (0) de N individus : x l , x2. .xN

Évaluation

Calculer la fitness F (xi) de chaque individu xi, i=l...N

18

Mémoriser le meilleur individu

Tant que la condition d'arrêt n'est pas vérifiée,

Faire

Sélection

Sélectionner N individus de P (t) pour former un ensemble S (t).

Reproduction

Grouper les individus de S (t) par paire.

Pour chaque paire d'individus :

Avec la probabilité de croisement, appliquer le croisement à la paire et recopier

la progéniture dans une population temporaire P (temp).

Pour chaque individu de P (temp):

Avec la probabilité de mutation, appliquer la mutation et recopier l'individu

muté dans P (temp).

Remplacement

Ajouter P (temp) aux populations précédentes.

Produire une nouvelle population P (t+1) en éliminant des populations générées

les plus faibles individus de manière à ce que la population actuelle ne contienne

que les N meilleurs individus.

Évaluation

Calculer la fitness F (xi) de chaque individu xi, i=l...N.

Mémoriser le meilleur individu.

Fin Faire

Figure 5-Algorithme génétique classique

2.1.2.2 Description détaillée

2.1.2.2.1 Le codage

Le codage est une partie très importante des algorithmes génétiques. II permet de

présenter l'individu sous la forme d'un chromosome. Ce chromosome est constitué de gènes qui

prennent des valeurs dans un alphabet binaire ou non binaire. Le choix du codage est délicat. II

doit permettre de coder toutes les solutions et de mettre en œuvre des opérateurs de

19

reproduction. C'est ainsi que le bon déroulement des algorithmes génétiques sera assuré. Parmi

les codages les plus utilisés, nous citons :

Le codage par permutation de valeurs entières (Figure 6) où tout gène sera codé par une

valeur entière dans un ensemble de cardinalité égale au nombre de gènes. Ce codage est

bien adapté aux problèmes d'ordonnancement.

Chromosome A 1 3 6 2 5 8 4 7

Chromosome B 1 6 | 1 | 3 | 2 | 7 ] 4 | 3 | 8 |

Figure 6-Codage par permutation

Le codage par valeurs (Figure 7). Cette technique consiste à coder le gène par une valeur

prise dans un ensemble fini ou infini. Ce codage est généralement utilisé pour des valeurs

qu'on ne peut pas mettre sous la forme du premier codage. Ces valeurs sont bien entendu

liées au problème à résoudre.

Chromosome A A A C G T T C G

Chromosome B 2,34 5.67 0.50 0.34 1.87 5.78 3.67 9.12

Chromosome C BLUE RED GREEN BLUE WHITE RED RED BLACK

Figure 7-Codage par valeurs

Le codage binaire (Figure 8). Le gène est codé par un caractère binaire, 0 ou 1. C'est le plus

courant. II a été employé lors de la première application des algorithmes génétiques.

Chromosome A 0 1 0 0 1 1 0 1

Chromosome B 1 1 1 0 0 1 0 1

Figure 8-Codage binaire

20

2.1.2.2.2 La construction de la population initiale

La population initiale peut être construite de plusieurs façons, selon le problème. Parmi

les méthodes proposées dans la littérature, nous ne mentionnons dans cette section que les

plus utilisées.

La première est le tirage au hasard qui consiste à générer aléatoirement les différents

individus constituant la population initiale. Cette méthode satisfait le besoin d'avoir une

population variée qui permettra d'explorer des zones diverses de l'espace des solutions.

Une deuxième manière se base principalement sur l'application d'heuristiques lors du

processus de choix d'individus et cela dans l'espoir d'en trouver d'autres meilleurs lors des

générations suivantes. Cependant, une telle pratique peut influencer l'algorithme génétique et

le faire converger trop rapidement vers un optimal local [SELM 92].

Des deux premières méthodes, une troisième peut résulter. Cela consiste à incorporer

des solutions provenant d'heuristiques à une population de solutions aléatoires permettant

ainsi d'introduire la variété nécessaire.

2.1.2.2.3 Une fonction à optimiser

Nous avons dit précédemment qu'un algorithme génétique est un algorithme

d'optimisation globale. II faut donc définir une fonction à optimiser qui permettra de quantifier

l'adaptabilité de chaque individu au milieu qui l'entoure. L'algorithme génétique tend aussi à

maximiser la force F(x) d'un individu x de la population. La fonction d'adaptation, ou fitness,

associe une valeur de critère à chaque individu. Cette valeur a pour but d'évaluer si un individu

est mieux adapté qu'un autre à son environnement. Soit C(x) la valeur de critère à optimiser

relatif à un individu x. Dans le cas d'une minimisation de ce critère, Goldberg propose, dans

21

[GOLD 89], de prendre le complément pour se ramener à un cas de maximisation et cela en

procédant de la façon suivante :

Si C(x)>0

Alors F(x)=Cmax-C(x)

Sinon F(x)=0

Où : Cmax peut être un coefficient fixé préalablement ou la plus grande valeur observée de

C(x).

Cette fonction, propre au problème, est souvent simple à formuler lorsqu'il y a peu de

paramètres. Par contre, lorsqu'il y a beaucoup de paramètres, elle est plus difficile à définir.

Dans ce cas, la fonction devient une somme pondérée de plusieurs fonctions. Un ajustement des

coefficients est alors nécessaire. Un élément de population qui viole une contrainte se verra

attribuer une faible fitness et aura une probabilité forte d'être éliminé par le processus de

sélection.

2.1.2.2.4 Les opérateurs de reproduction

Disposant d'une population d'individus non homogène, la diversité de la population doit

être entretenue au cours des générations afin de parcourir le plus largement possible l'espace

d'état. C'est le rôle des opérateurs de sélection, de croisement et de mutation.

2.1.2.2.4.1 La sélection

La sélection sert à choisir dans l'ensemble de la population les individus qui

participeront à la reproduction. Plusieurs méthodes existent, et sont généralement basées sur la

théorie de Darwin. Ainsi, les meilleurs individus ont plus de chance de survivre et de se

reproduire. Nous présentons les plus connus :

22

a) la Roulette (Probabilité de sélection proportionnelle à l'adaptation)

Cette méthode exploite la métaphore d'une roulette de casino. La roue est divisée en

autant de secteurs que d'individus dans la population. La taille de ces secteurs est

proportionnelle à l'adaptation de chaque individu. En faisant tourner la roue, l'individu pointé à

l'arrêt de la boule est sélectionné. Les meilleurs individus peuvent ainsi être tirés plusieurs fois

et les plus mauvais ne sont jamais sélectionnés. Autrement dit, les mieux adaptés ont plus de

chance d'être tirés au sort lors du déroulement du jeu, contrairement aux moins adaptés.

b) Sélection par rang

La sélection précédente rencontre des problèmes lorsque la valeur d'adaptation des

chromosomes varie énormément. Si la meilleure fonction d'évaluation d'un chromosome

représente 90% de la roulette alors les autres chromosomes auront très peu de chance d'être

sélectionnés et on arriverait à une stagnation de l'évolution. La sélection par rang trie d'abord la

population par fitness. Ensuite, chaque chromosome se voit associer un rang en fonction de sa

position. Ainsi, le plus mauvais chromosome aura le rang 1, le suivant 2, et ainsi de suite

jusqu'au meilleur chromosome qui aura le rang N (pour une population de N chromosomes). La

sélection par rang d'un chromosome est la même que par roulette, mais les proportions sont en

relation avec le rang plutôt qu'avec la valeur de l'évaluation. Avec cette méthode de sélection,

tous les chromosomes ont une chance d'être sélectionnés. Cependant, elle conduit à une

convergence plus lente vers la bonne solution. Ceci est dû au fait que les meilleurs

chromosomes ne diffèrent pas beaucoup des plus mauvais.

c) Le tournoi

Cette méthode ressemble plus à ce qui se passe dans la réalité. Comme son nom

l'indique, elle fait affronter deux ou plusieurs individus afin que le meilleur gagne. Plusieurs

variantes existent. On peut par exemple faire varier le nombre d'individus qui doivent

s'affronter au départ, ou encore permettre ou non que le même individu soit eligible plusieurs

fois lors d'un même tournoi.

23

2.1.2.2.4.2 Le croisement

L'opérateur de croisement a pour but d'enrichir la diversité de la population en

manipulant la structure des chromosomes. II combine les gènes des deux individus parents pour

donner deux nouveaux chromosomes d'individus enfants. La zone de croisement est

généralement choisie aléatoirement dans les chromosomes. Les méthodes de croisement sont

liées au codage. Le croisement de chromosomes codé en binaire n'est pas le même que celui

d'un chromosome codé par valeur entière, mais leur principe est identique.

a) Le croisement à un point

Dans le chromosome, un point de croisement est choisi. La première partie du

chromosome de l'individu dit parent 1 est alors copiée sur un individu de la prochaine

génération enfant 1. Celle du parent 2 est copiée sur un enfant 2. Pour la deuxième partie du

chromosome, les parents échangent leurs enfants, ainsi le parent 1 est copié sur l'enfant 2 et le

parent 2 sur l'enfant 1 (Figure 9).

Parents

Enfants

Figure 9-Le croisement à un point

Ce même principe peut être étendu pour découper le chromosome non pas en 2, mais

en 3,4, etc.

2.1.2.2.4.3 La mutation

Comme les individus les mieux adaptés sont les plus susceptibles d'être choisis lors de la

sélection, la perte de certains gènes est inévitable avec le temps. La mutation est l'opérateur qui

permet d'éviter la dégénérescence de la population et d'enrichir l'ensemble de gènes. Cette

24

dégénérescence peut se traduire par une convergence des individus vers un optimum local, d'où

l'importance de la mutation. Classiquement, la mutation modifie aléatoirement, un petit

nombre de gènes, avec un faible taux de probabilité. Pour mieux illustrer le fonctionnement de

cet opérateur, nous prenons l'exemple d'un chromosome binaire (Figure 10). La mutation

s'applique sur un gène choisi aléatoirement. Comme il s'agit d'un gène contenant un nombre

binaire, sa modification consiste juste à l'inverser (l->0 et 0->l).

r^TôTTWTTÔTTTÔI

r ô T o i i M i i o i u o i

Figure 10-La mutation avec le codage binaire

II existe bien d'autres façons d'effectuer la mutation parmi lesquelles nous citons :

La transposition de deux gènes consécutifs/non consécutifs qui consiste à échanger la

valeur de deux gènes consécutifs/non consécutifs d'un chromosome.

L'inversion de gènes qui agit seulement sur l'ordre des gènes présents dans un

chromosome.

2.1.2.2.5 Le remplacement

Une fois que l'on possède un nouvel individu, il doit être remplacé dans la population.

Cette opération comprend deux phases :

1. Sélection du membre de la population qui va être remplacé.

2. Décision d'effectuer le remplacement ou non, selon un certain critère.

Le schéma de remplacement influence la convergence de l'algorithme. En principe un

remplacement inconditionnel accélère le processus en diminuant la diversité dans la population

avec le risque de diminuer la qualité. Au contraire, un remplacement plus modéré ralentit la

convergence pour augmenter la qualité. Cependant, seule une expérimentation permet de le

25

vérifier. Les différents types de remplacement que nous avons rencontrés dans la littérature se

résument dans ces trois choix :

Remplacement du plus mauvais parent sans condition.

Remplacement du plus mauvais de la population sans condition.

Remplacement du plus mauvais parent si et seulement si le descendant est meilleur.

2.1.2.2.6 Le critère d'arrêt

Les algorithmes génétiques font partie des algorithmes itératifs. Or, pour ce type

d'algorithme, une condition d'arrêt doit être spécifiée. II existe plusieurs manières de décider de

l'arrêt d'un algorithme génétique :

La spécification d'un nombre maximal de générations à examiner.

Lorsque la population devient stable et converge vers un optimum.

L'atteinte d'une certaine valeur objective.

2.1.3 Extensions et améliorations des algorithmes génétiques

2.1.3.1 La technique Élitiste

Elle permet de garder l'individu le mieux adapté d'une génération à la suivante et

d'améliorer la qualité et le temps de convergence. En effet, l'opérateur de sélection peut ne pas

le sélectionner, le croisement avec un autre individu peut donner des individus moins adaptés si

les gènes ne sont pas bien recombinés ou encore sa mutation peut également le rendre moins

adapté. Cette technique remplace la simple mémorisation du meilleur individu.

26

SI Le meilleur individu de la génération courante est moins bon que

celui de la génération précédente.

ALORS Celui de la génération précédente remplace le plus mauvais de la

population courante.

SINON Le meilleur individu est mémorisé.

FINSI

Figure 11-Principe de la technique Élitiste

Cette technique est utilisée dans les différentes versions de l'algorithme que nous avons

mises en place. Au moment de la création de la nouvelle population, on procède à la réunion

des individus récemment générés et ceux obtenus lors des générations précédentes afin de les

comparer. À l'issu de cette comparaison, seuls les meilleurs individus sont gardés pour former la

prochaine génération.

2.1.3.2 Algorithme génétique modifié

L'algorithme modifié de Michalewicz [MICH 94 a] se distingue non seulement par sa

manière de sélectionner, mais aussi par celle de remplacer les individus.

Données

Définir un codage du problème.

Initialisation

Créer une population initiale P (0) de N individus : x l , x2....xN

Évaluation

Calculer la force F (xi) de chaque individu xi, i=l...N

Tant que la condition d'arrêt n'est pas vérifiée,

Faire

Sélection des parents

Sélectionner N individus de P (t) pour former un ensemble S(t) de parents.

27

Un même individu de P (t) peut apparaître plusieurs fois dans S (t).

En fait, au lieu de copier les individus sélectionnés, on les associe à un

compteur, qui indique combien de fois ils vont se reproduire.

Sélection des morts

Sélectionner r individus de P (t) qui doivent être remplacés par la progéniture

(ils sont en fait marqués comme morts).

Reproduction ou (recombinaison)

Grouper les individus de S (t) par paire, puis pour chaque paire d'individus :

Avec la probabilité de croisement appliquer le croisement à la paire et recopier

la progéniture dans S (t+1).

La paire d'individus est éliminée, elle est remplacée par sa progéniture.

Pour chaque individu de S (t+1) :

Avec la probabilité de mutation, appliquer la mutation à l'individu, le recopier

dans S (t+2)

Remplacement

Produire une nouvelle population P (t+1) en remplaçant les r individus

sélectionnés comme morts de P (t) par ceux de S (t+2).

Évaluation

Calculer la force F (xi) de chaque individu xi, i=l...N

Fin Faire

Figure 12-Principe de l'algorithme génétique modifié

Cette extension semble être intéressante du moment qu'elle nous permet d'agir sur la

manière avec laquelle le remplacement est effectué. Au lieu de remplacer toute la population

par sa progéniture, on peut sélectionner, pour se rapprocher plus rapidement de la meilleure

solution, un nombre d'individus à supprimer. Le remplacement ne s'effectuera que sur ces

derniers.

28

2.2 Les problèmes de satisfaction de contraintes

L'objectif de cette section est d'introduire les problèmes de satisfaction de contraintes

(que nous noterons CSP pour Constraint Satisfaction Problem). Après une brève présentation,

nous introduirons un certain nombre de concepts, notations et définitions. Par la suite, nous

présenterons les principales méthodes de résolution utilisées actuellement.

2.2.1 Présentation

Les problèmes de satisfaction de contraintes sont constitués d'un ensemble de

variables, un ensemble de valeurs associées à chaque variable, ainsi qu'un ensemble de

contraintes. Chaque contrainte limite les combinaisons de valeurs que peuvent prendre les

variables.

Le problème de satisfaction de contraintes consiste à trouver une affectation pour

chaque variable, de telle façon qu'aucune contrainte ne soit violée. Ce formalisme assez simple

et générique permet de modéliser un grand nombre de problèmes de la vie courante, dont les

suivants :

Les problèmes d'emploi du temps;

Les problèmes d'ordonnancement de tâches;

Les problèmes d'affectation de fréquences;

Les problèmes de rangement d'objets.

2.2.2 Concepts et Notations

Un problème de satisfaction de contraintes (CSP) est constitué d'un ensemble de

variables dont les valeurs sont issues d'un ensemble de valeurs appelé domaine, et dont

l'affectation est soumise à certaines conditions appelées contraintes.

29

Définition 2.2.1 Les contraintes

Une contrainte peut-être :

Numérique quand elle porte sur des variables dont les valeurs sont réelles ou entières,

Numérique linéaire si elle est exprimée sous forme arithmétique linéaire.

Numérique non linéaire dans le cas où elle contient des expressions de produits entre

variables ou des fonctions logarithmiques ou exponentielles,

Booléenne si elle fait intervenir des expressions logiques, telles que des implications, des

équivalences et des non-équivalences.

L'expression formelle des contraintes peut se faire en extension, auquel cas elles sont

représentées par l'ensemble des tuples que les différentes contraintes autorisent. Elle peut

aussi se faire en intention. Elles sont représentées, dans ce cas, en utilisant les propriétés

mathématiques entre les variables qu'elles font intervenir.

Étant donnée une instance CSP, on appelle la portée d'une contrainte l'ensemble des

variables sur laquelle elle s'applique, l'arité étant le nombre de variables dans la portée. Une

contrainte d'arité 1 est dite unaire (elle se contente de limiter le domaine d'une variable à

certaines valeurs), une contrainte d'arité 2 est dite binaire, et plus généralement, une contrainte

d'arité n est dite n-aire. La dureté d'une contrainte est le nombre de tuples qu'elle interdit.

Définition 2.2.2 Instance CSP [MONT 74]

Une instance CSP est un quadruplet (X, D, C, R), où

Xest un ensemble {x^ x2,x3,...,xn} de variables,

D est un ensemble de domaines finis { d x l , dx 2 ,dx 3 , ...,dxn} tel que le domaine d x i

contienne les valeurs que la variable xs peut prendre,

C est un ensemble {c1( c2,c3, ...,cm} de contraintes, chaque contrainte q est une

relation entre un certain nombre de variables,

30

R est un ensemble { r c l , rc2,rc3,...,rcn} de relations, tel que rci représente l'ensemble

des affectations compatibles (ou autorisées) sur l'ensemble des variables contraintes

par q .

Définition 2.2.3 Hypergraphe de contraintes

Toute instance CSP peut être représentée graphiquement grâce à l'hypergraphe de

contraintes. Étant donnée une instance CSP P=(X, D, C, R), l'hypergraphe (X, C) est l'hypergraphe

de graphe associé à l'instance P. Si toutes les contraintes de P sont binaires (X, C) est un graphe

appelé graphe de contraintes.

Définition 2.2.4 Instanciation

Étant donné Y £ X avec Y = {y\, — ,yk} ; une instanciation (ou affectation) des

variables d'Y est un k-uplet de£>yl x . . .x Dyk . Une instanciation est dite complète si elle

porte sur toutes les variables de X, partielle sinon.

Étant donnée une instanciation A sur un ensemble V de variables, on notera A[W] la

projection de cette instanciation sur l'ensemble W c V. De même, on appelle projection d'une

contrainte c sur un ensemble W (que l'on notera c[W]) l'ensemble des projections sur W des

tuples de la relation associée à c. En particulier, si W = {x}, c[W] sera appelée support de c.

La définition du CSP est intimement liée à la notion de violation de contraintes, et à celle

de cohérence, que nous allons définir comme suit :

Définition 2.2.5 Affectation consistante

Une affectation A satisfait une contrainte c de C si A [c] G rc. Si elle porte sur au moins

toutes les variables de c et que A[c] g rc, on dit que A viole c. On dit que A est consistante si Vc G

C, c Ç XA, A[C] Grc. Elle est dite inconsistante sinon.

31

Définition 2.2.6 Instanciation partielle localement cohérente

Une instanciation partielle d'un ensemble de variables S est localement cohérente si et

seulement si elle satisfait toutes les contraintes portant uniquement sur les variables de S.

Définition 2.2.7 Solution

Une solution d'un CSP P=(X, D, C, R) est une instanciation complète de X localement

cohérente.

Définition 2.2.8 Instanciation partielle globalement cohérente

Une instanciation partielle est globalement cohérente si et seulement si elle peut être

étendue à une solution.

Définition 2.2.9 CSP sur-contraint

Le CSP est dit sur-contraint s'il n'admet pas de solutions, étant donné le nombre de

contraintes à satisfaire. Si le CSP admet plusieurs solutions distinctes, il est dans ce cas de figure

sous-contraint.

Définition 2.2.10 Espace de recherche

L'espace de recherche d'un CSP P= (X, D, C, R) est l'ensemble des instanciations

possibles de X, c'est-à-dire Dx x D2 x . . .x Dn

32

2.2.3 Méthodes de résolutions des problèmes de satisfaction de contraintes

Nous allons maintenant présenter les principales méthodes de résolution classiques du

problème de satisfaction de contraintes qui ont été proposées dans la littérature [BLA 02]. Nous

pouvons cependant distinguer trois grandes familles d'algorithmes pour résoudre de tels

problèmes. Dans la première section, nous présentons les méthodes constructives qui

procèdent par construction itérative de la solution. Dans la deuxième section, nous présentons

des algorithmes qui utilisent l'approche locale. Ces algorithmes opèrent par réparation locale

d'une instanciation complète globalement incohérente. Dans la troisième section, nous

présentons l'approche par algorithme à population, qui fait évoluer une population de solutions

potentielles. Ces deux dernières approches font partie des algorithmes dits non systématiques

(aussi appelés métaheuristiques), donc incomplets, c'est-à-dire qu'ils ne garantissent pas

l'obtention d'une solution optimale en un temps fini. Ces algorithmes sont souvent associés à un

processus stochastique, pour éviter qu'un mauvais choix de départ ne les pénalise.

2.2.3.1 Méthodes constructives

Comme leur nom l'indique, ces méthodes construisent une solution par instanciation

successives des variables. Cette approche regroupe la plupart des méthodes systématiques, des

méthodes qui garantissent, en un temps fini, soit d'obtenir une solution, soit qu'aucune solution

n'existe. Cependant, elles se révèlent relativement peu efficaces sur des problèmes de grande

taille. La première partie de cette section est consacrée à l'algorithme Backtrack, la deuxième

partie présente différentes heuristiques qu'on peut intégrer dans la recherche de solutions, et

enfin, la troisième partie évoque rapidement les CSP sur-contraints.

33

2.2.3.1.1 L'algorithme Backtrack

Cet algorithme représente la méthode sur laquelle toutes les méthodes constructives se

basent [GOLU 89]. L'arbre de recherche est généralement exploré en utilisant une recherche

arborescente en profondeur. Cette méthode explore successivement tout l'espace de

recherche. Cela consiste à construire la solution en instanciant successivement les variables du

problème et en suivant un ordre défini au départ. À chaque nouvelle instanciation, on vérifie si

l'instanciation partielle est localement cohérente. Si c'est le cas, on passe à l'instanciation d'une

nouvelle variable, sinon on essaie avec une autre valeur du domaine de la variable courante. Si

toutes les valeurs du domaine ont été essayées, on tente d'atteindre la dernière variable

instanciée en appliquant un retour en arrière.

Un arbre de recherche est utilisé pour représenter le parcours de l'espace de recherche.

Chacun des nœuds de cet arbre représente la valeur d'une variable. L'affectation de l'ième

variable de l'instanciation partielle a donc lieu à la profondeur i de l'arbre. Le problème est

qu'on peut se trouver dans des situations où on a affecté la totalité des variables avant de

s'apercevoir qu'il ne s'agit pas d'une solution. En effet, l'algorithme du Backtrack ne filtre pas les

domaines des variables non instanciées à partir de l'instanciation partielle courante.

Cet algorithme n'est pas pratique vu sa lenteur en terme de temps d'exécution.

Cependant, on retrouve dans la littérature de nombreuses améliorations dont nous allons voir

quelques exemples.

Les méthodes que nous allons présenter dans cette section sont toutes inspirées de

l'algorithme Backtrack. Ces méthodes cherchent toutes à construire une solution en instanciant

une par une les variables et en effectuant des retours arrière à chaque fois où l'instanciation

partielle n'est plus cohérente.

34

2.2.3.1.2 Heuristiques

Les heuristiques permettent de faciliter la recherche de solution, en introduisant une

certaine connaissance de la structure du problème à traiter. Nous présentons dans ce qui suit les

heuristiques de choix de variables et les heuristiques de choix de valeurs.

Choix de variables

La manière avec laquelle on choisit les variables à instancier affecte de façon

déterminante la rapidité à trouver la solution. Par exemple, si l'arbre de recherche contient

moins de nœuds intermédiaires, il engendre moins de retours arrière, et peut donc être

parcouru plus efficacement. Nous pouvons générer de tels arbres en choisissant d'abord les

variables ayant le plus petit domaine.

Le Fail First Principle [HAR 80], consiste à choisir la variable qui a le plus de chance de

mener à un échec et cela dans le but d'élaguer rapidement de grands sous-arbres sans solution.

Sous cette catégorie, on distingue d'autres heuristiques qui ont été proposées dans la

littérature, comme choisir d'abord la variable ayant le plus grand degré dans le graphe de

contraintes ou bien choisir d'abord la variable contrainte par le plus grand nombre de variables

déjà instanciées. Ces heuristiques peuvent être combinées entre elles [GENT 96, BES 96] afin

d'obtenir un critère plus fin. Ces combinaisons peuvent cependant devenir coûteuses, il faut

chercher le meilleur compromis entre le temps de calcul et la rapidité à trouver la solution.

Choix de valeurs

Le deuxième critère qui a de l'impact sur le temps à dépenser pour trouver la solution

est l'ordre d'instanciation des valeurs pour chaque variable. Si on ne cherche qu'une solution, il

est généralement plus efficace de choisir la valeur qui est compatible avec un maximum de

valeurs des variables non instanciées. Nous aimerions pouvoir choisir pour chaque variable la

35

valeur qui nous conduit à la bonne solution, nous allons donc chercher des heuristiques qui vont

nous permettre de nous rapprocher de cet état idéal. La technique Lookahead Value Ordering

[FROS 95], par exemple, ordonne les valeurs en comptant le nombre de conflits qui opposent la

valeur de la variable courante aux valeurs des variables non encore instanciées. Une autre

technique consiste à compter le nombre de solutions potentielles [GEEL 92]. Lorsqu'on traite

des CSP sur-contraints, on a plutôt intérêt à choisir les valeurs qui minimisent les conflits avec

les variables déjà instanciées [MINT 92].

Ces heuristiques permettent d'améliorer la recherche de solution, mais ne suffisent

généralement pas. Nous citons ici, à titre indicatif, deux types de méthodes d'amélioration du

Backtrack :

Les premières sont rétrospectives : elles cherchent à identifier les causes de l'échec

afin de ne pas retomber dans des configurations pareilles.

Les secondes sont prospectives, on élimine certaines valeurs du domaine des

variables non encore instanciées en fonction de la connaissance apportée par les

variables déjà instanciées.

2.2.3.1.3 CSP sur-contraint

Lorsque nous traitons des CSP sur-contraints, le but n'est plus de trouver une solution

puisque par définition il n'y en a pas, mais de minimiser un critère comme la somme des coûts

des contraintes non satisfaites. Les méthodes utilisées pour résoudre de tels problèmes sont

légèrement différentes de celles utilisées pour résoudre les CSP classiques.

Branch and Bound

La méthode de séparation/évaluation (Branch and bound) en profondeur permet

d'abord d'élaguer l'arbre de recherche en éliminant les branches qui mènent à des solutions

ayant un coût supérieur au coût de la meilleure solution trouvée. Pour ce faire, elle utilise une

36

borne B qui correspond au coût de la meilleure solution trouvée. Après chaque nœud généré

dans l'arbre de recherche, on doit déterminer s'il va mener à l'obtention d'une solution moins

bonne. On calcule, pour y arriver, une minoration des coûts des solutions constructibles à partir

de ce nœud. Si la somme de cette minoration et du coût de la solution partielle est supérieure à

B, on rejette le nœud.

2.2.3.2 Méthodes de recherche locale

Les méthodes de recherche locale ne sont pas systématiques, elles ne peuvent pas

garantir l'obtention d'une solution. Elles vont généralement utiliser, au cours de la recherche,

des processus stochastiques afin d'introduire de la diversification dans le parcours de l'espace

de recherche. Ces méthodes se révèlent généralement efficaces, et permettent de traiter des

problèmes trop ardus pour être traités efficacement par les méthodes constructives.

Les méthodes de recherche locale ne procèdent pas par construction d'une solution,

mais par améliorations successives d'une solution initiale. Pour cela, plusieurs outils sont

nécessaires dont principalement, une fonction de voisinage qui permettra de se déplacer dans

l'espace de recherche à partir de la solution initiale et une fonction d'évaluation qui permettra,

entre autres, de choisir parmi les voisins. On peut schématiser la procédure générale de la

plupart des méthodes locales comme suit :

1. choisir une solution initiale s.

2. choisir parmi les voisins de s une solution s

3. vérifier si la condition de terminaison est vraie.

4. décider si s doit remplacer s et revenir à l'étape 2

Les trois derniers points de cette procédure changent de stratégies et cela en fonction

de la méthode de recherche locale mise en place. Pour les différentes méthodes de recherche

locale que nous allons présenter, nous appellerons s la solution courante, s la nouvelle solution

37

prise dans le voisinage V (s), et enfin E(s) la fonction qui calcule le coût de la solution s. Ce coût

correspond au nombre de contraintes violées (ou satisfaites). De nombreuses fonctions de

voisinage peuvent être définies, cependant on choisit généralement, dans le cadre des CSP, la

fonction qui associe à s l'ensemble des solutions qui ne diffèrent que par la valeur d'une

variable. On peut restreindre ce voisinage en ne choisissant que les variables qui sont en conflit

[BES96].

2.2.3.2.1 Hill climbing et GSAT

La méthode du Hill climbing ou méthode de descente stricte procède par améliorations

successives strictes. On choisit un voisin strictement meilleur, qui remplace la solution courante

et on s'arrête lorsque l'on est sur un optimum.

Cette méthode est très simple, mais pêche sur plusieurs points. Tout d'abord, différents

choix s'offrent à nous, et vont déterminer l'efficacité de l'algorithme : doit-on choisir le premier

voisin qui améliore la solution courante ou bien le meilleur ? Si on cherche le meilleur voisin,

est-il possible d'évaluer rapidement tous ses voisins ? Dans le cadre des CSP, il est facile de ne

compter que les incohérences locales générées par le nouveau choix de valeur. Ensuite,

l'algorithme s'arrête au premier optimum trouvé, ce qui fait que l'initialisation a un rôle très

important. De plus si le problème contient beaucoup d'optima locaux, et peu de globaux, il y a

de grandes chances pour que ce soit un optimum local qui soit trouvé. II existe de nombreuses

améliorations possibles parmi lesquelles nous citons la relance aléatoire (GSAT [SELM 92]). Elle

consiste à recommencer avec une nouvelle solution initiale à chaque fois qu'un optimum local a

été atteint en mémorisant le meilleur trouvé et ceci pour un certain nombre de fois fixé à

l'avance. Cette méthode permet en fait de donner à la méthode de descente stricte plus de

chance d'obtenir une bonne solution. Une autre variante consiste à autoriser le choix d'un voisin

équivalent (en termes d'évaluation) s'il n'y a pas de meilleur voisin.

38

2.2.3.2.2 Recuit simulé

Le recuit simulé est une méthode locale inspirée du recuit thermique utilisé dans

l'industrie métallurgique pour obtenir un cristal parfait. La technique industrielle utilisée

consiste à abaisser progressivement la température du métal en fusion, de manière à ce qu'en

refroidissant lentement, les molécules prennent un « axe parfait ». L'algorithme qui s'inspire de

cette méthode a été introduit par Kirkpatrick et al. [KIRP 90].

Le principe du recuit simulé est le suivant : on choisit aléatoirement une solution

potentielle s, et on fixe la température T. On va ensuite entrer dans la boucle de l'algorithme :

1. Choisir aléatoirement un voisin s de la solution courante

2. Calculer la différence entre l'évaluation de s et de s : A= E(s) — E(s) A

3. s «- s avec une probabilité er si A est négatif, 1 sinon

4. Décroître T.

Différents critères d'arrêt peuvent être envisagés : lorsque les diminutions de

température s'avèrent inefficaces, lorsqu'un certain nombre de mouvements a été effectué, etc.

On va généralement démarrer en utilisant une température très élevée qu'il va falloir diminuer

par paliers successifs au cours de l'exécution. Cet algorithme garde systématiquement la

nouvelle solution si elle améliore la solution courante, sinon la nouvelle solution qui dégrade la

solution courante est choisie avec une probabilité qui diminue au cours du temps. Donc, au

début de l'exécution on aura tendance à choisir n'importe quel voisin, pour ensuite focaliser

progressivement sur un sous-espace de l'espace de recherche en acceptant de moins en moins

de solutions dégradant la solution courante. L'avantage de cette méthode par rapport à la

méthode de descente est qu'elle peut sortir des optima locaux (tant que la température est

suffisamment élevée). Cependant, le choix de la température initiale et la fonction de

décroissance associée à cette température restent des paramètres assez difficiles à régler. Une

variante appelée algorithme de Metropolis, et consistant à utiliser une température constante

(généralement faible) pour toute l'exécution, a été proposée dans [CONN 90].

39

2.2.3.3 Méthodes à population

L'originalité de ces méthodes réside dans le fait qu'elles utilisent un ensemble de

solutions potentielles (appelé population) qui vont être confrontées à des processus

stochastiques via des opérateurs dédiés. Cela leur permet d'exploiter plus largement l'espace de

recherche, mais peut aussi induire un surcoût dû au traitement de cette population. Nous

présentons brièvement dans cette section deux différentes méthodes utilisant des populations

de solutions.

2.2.3.3.1 Go With the Winners

Cette méthode (« Va avec les gagnants » en français) [ALD 94, DIMI 96] ne fait pas partie

des algorithmes évolutionnaires. Elle utilise une population de particules (les solutions

potentielles) choisies aléatoirement. Ces particules sont évaluées, et ne doivent pas dépasser un

certain seuil sous peine d'être éliminées et remplacées par une copie d'autres particules plus

compétitives de la population courante. Ensuite on effectue une marche aléatoire à partir des

particules sélectionnées pour diversifier les particules regroupées, et enfin le seuil est

décrémenté. Différentes améliorations ont été testées, notamment en essayant de guider la

recherche de nouvelles particules plutôt que d'effectuer une marche aléatoire.

2.2.3.3.2 Algorithmes génétiques

Ces algorithmes ont été détaillés dans la sous-section précédente. C'est sur eux que

notre choix s'est arrêté pour la résolution du problème qui nous intéresse.

40

2.3 La manipulation des contraintes dans un algorithme génétique

Dans cette section, nous allons nous intéresser aux différentes méthodes utilisées dans

le but d'améliorer l'efficacité d'un algorithme génétique.

2.3.1 Introduction

De nos jours, plusieurs problèmes pratiques peuvent être formalisés comme des

problèmes d'optimisation contraints. Vu la complexité de ces problèmes, il est préférable

d'essayer de les résoudre en utilisant des algorithmes qui se basent sur des heuristiques. Parmi

ces derniers, nous citons les algorithmes évolutionnaires que nous jugeons efficaces pour la

résolution de ce genre de problèmes. Les algorithmes génétiques, utilisés pour faire face à notre

problème, font partie de la famille des algorithmes évolutionnaires.

Pour garantir une meilleure résolution de ce type de problème, il vaut mieux s'assurer

que l'algorithme génétique qu'on compte mettre en place soit capable de tenir compte des

contraintes imposées par le problème. II s'avère qu'une combinaison des algorithmes

génétiques et des problèmes de satisfaction de contraintes peut remédier à ce problème. En

d'autres termes, il faut que notre algorithme soit capable de manipuler les contraintes que toute

solution doit respecter. Cette manipulation de contraintes peut se faire de deux différentes

manières :

Manipulation directe qui consiste à essayer d'incorporer les contraintes lors de la

création de la population initiale et dans les opérateurs de reproduction. Cette approche

est présentée dans la section 2.3.2.

Manipulation indirecte qui consiste à définir la fonction objectif de manière à ce qu'on

respecte la totalité des contraintes. Cette approche est détaillée dans la section 2.3.3.

41

Dans ce qui suit, nous présentons une synthèse des principaux travaux du domaine.

2.3.2 Manipulation directe

Ce type de manipulation élimine tout lien direct entre la fonction objectif et la

manipulation de contraintes. En fait, traiter les contraintes directement implique que leur

violation n'affecte pas la fonction objectif. II faut donc incorporer la manipulation des

contraintes dans la création et la gestion des populations. Plus précisément, la manipulation des

contraintes peut intervenir lors des étapes suivantes d'un algorithme génétique :

Création initiale d'une nouvelle population,

Génération aléatoire d'un individu,

Mutation d'un individu,

Croisement de plusieurs individus.

En mettant en place cette façon de manipuler les contraintes, nous visons à maintenir la

faisabilité des chromosomes en agissant seulement sur la population initiale et les opérateurs de

reproduction. Trois approches, que nous détaillerons par la suite, ont été proposées se basant

chacune sur :

La faisabilité de solutions,

La consistance de contraintes,

L'insertion d'heuristiques.

2.3.2.1 La faisabilité des solutions

Cette approche, proposée par A.E. Eiben [EIB 01], consiste à essayer de ne garder que

des solutions réalisables dans la population courante sans même garantir la consistance de

toutes les populations générées durant la résolution du problème. Ceci est assuré par la mise en

place de plusieurs méthodes parmi lesquelles nous citons :

42

2.3.2.1.1 Elimination des solutions infaisables

L'élimination des solutions infaisables consiste à supprimer tout chromosome non

réalisable de la population d'individus. Cette méthode peut être utilisée pour résoudre des

problèmes peu contraints, mais elle ne sera pas en mesure de prêter main-forte au cas où nous

nous trouverions face à des problèmes fortement contraints, car les chances de trouver une

solution réalisable à ces derniers sont quasiment nulles. En mettant en place une telle méthode,

nous risquons de n'aboutir à aucune solution vu le grand nombre de solutions que nous

pouvons écarter. Ces derniers représentent des chromosomes qui, après croisement et

mutation, peuvent donner naissance à des individus respectant toutes les contraintes.

2.3.2.1.2 Réparation de solutions infaisables

Cette méthode exige la définition d'une heuristique capable de modifier un

chromosome de manière à ce qu'il ne viole aucune contrainte. Cette heuristique dépend

toujours du problème à résoudre. Elle vise à améliorer une mesure de qualité qui n'est pas

reflétée dans la fonction de fitness.

Les méthodes basées sur la réparation des solutions infaisables semblent être efficaces

dans le cas où on serait amené à manipuler des contraintes en extension. Ce type de contrainte

permet d'énumérer le n-uplet de valeurs appartenant à la relation. Au lieu d'exprimer celle-ci

sous forme d'équation, ce sera l'ensemble des combinaisons de valeurs qui vérifient la relation.

La réparation de solutions, dans ce cas-là, consiste à limiter le domaine de définition des

variables impliquées aux valeurs permettant l'obtention de combinaisons autorisées. On ne

dispose pas de cette alternative si on a à faire à des contraintes en intention. La réparation de

solutions ne pourra plus être envisageable dans le cas où les contraintes imposées n'utilisent

que les propriétés mathématiques (<, >, =, *) pour définir les relations entre variables.

43

2.3.2.1.3 Préservation de faisabilité

Cette approche consiste à concevoir et à appliquer des opérateurs de reproduction

spécifiques à des problèmes bien précis afin de préserver la faisabilité des chromosomes

parents. En utilisant de tels opérateurs, notre recherche ne sera plus limitée puisque la

progéniture fera toujours partie de l'espace de recherche réalisable, dans le cas où les parents

seraient des solutions candidates faisables. Pour que cela réussisse, une population initiale ne

contenant que des solutions faisables doit être créée.

Ces différentes méthodes peuvent être utilisées simultanément afin de résoudre un

problème donné.

Pour terminer, il faut mentionner que ces méthodes sont difficiles à implémenter

puisque leurs définitions dépendent toujours du problème à résoudre. II n'existe pas de

formulation standard de ces méthodes qui nous garantisse la résolution de n'importe quel

problème. II faut préciser que, dans la littérature, nous n'avons pas trouvé assez de

connaissances nous permettant de savoir comment utiliser ces méthodes.

2.3.2.2 La consistance de contraintes

Cette approche est proposée par Ryszard Kowalczyk [KOW 96]. Elle consiste à intégrer

dans un algorithme génétique les principes de la consistance des contraintes afin d'éviter que

les attributions de valeurs aux variables de problème violent une ou plusieurs contraintes.

Ces principes peuvent être utilisés durant différentes étapes d'un algorithme génétique :

- Création de la population initiale : La première étape de l'algorithme génétique où la

consistance de contrainte peut être bénéfique est la génération de la population initiale.

Les gènes du chromosome, qui vont être instancies par des valeurs choisies aléatoirement

44

de leurs domaines de définition, subiront un test de consistance de contraintes. La

propagation de contraintes permet de s'assurer que les domaines de définition des

variables non encore instanciées ne contiennent pas des valeurs pouvant violer les

contraintes intervariables. De cette façon, nous pouvons affirmer que les chromosomes

initiaux générés ne peuvent être que des solutions faisables du problème.

Croisement : Dans cette étape, les principes de la consistance des contraintes doivent

intervenir dans la manière avec laquelle on va définir l'opérateur de croisement. Ce dernier

doit être modifié de façon à ce qu'il ne donne naissance qu'à des chromosomes capables de

satisfaire la totalité des contraintes.

- Mutation : Durant la mutation, le gène modifié devrait prendre une valeur de son domaine

qui ne doit contenir que des valeurs faisables. L'objectif de la consistance des contraintes

ici, est de s'assurer que la mutation ne produit que des solutions faisables du problème.

Ceci améliore sans doute l'efficacité de l'algorithme génétique.

Cette approche nous montre où on doit intervenir dans un algorithme génétique pour

assurer que les contraintes imposées ne soient pas violées.

On peut conclure, à partir des expérimentations répertoriées dans la littérature, que la

consistance des contraintes peut contribuer à l'amélioration de l'efficacité et la flexibilité d'un

algorithme génétique utilisé pour résoudre un problème d'optimisation et de satisfaction de

contraintes. Mais il faut mentionner aussi que le fait de tenir compte de la consistance de

contraintes s'avère coûteux en termes de temps de calcul.

45

2.3.2.3 L'insertion d'heuristiques

Cette approche, proposée par Craenen et al. [CRAE 00], regroupe trois algorithmes

évolutionnaires qui utilisent des heuristiques pour manipuler des contraintes. Les trois

algorithmes que nous allons présenter sont nommés ESP-GA, H-GA et Arc-GA.

2.3.2.3.1 ESP-GA

Cet algorithme, introduit par E. Marchiori [MAR 97], représente les contraintes sous une

forme canonique de façon à ce qu'il n'y ait qu'une seule contrainte primitive à satisfaire. Cette

approche, appelée glass box, est utilisée surtout dans la programmation de contraintes

[HENT95] où les problèmes de satisfaction de contraintes sont donnés sous forme implicite par

le moyen de formules. On prend par exemple le problème des N-reines dont les contraintes sont

formulées ainsi :

Deux reines ne peuvent pas se placer sur la même ligne : V, * Vj pour i * j

Deux reines ne peuvent pas se placer sur la même diagonale : | Vj —Vj | * | i - j | pour i * j

La décomposition des contraintes complexes en des contraintes primitives nous permet

d'avoir des contraintes ayant le même niveau de granularité d'où la même difficulté à être

résolue. Les contraintes primitives choisies dans [MAR 97], le problème des N-reines et du

puzzle à cinq maisons, sont des inégalités linéaires qui prennent cette forme : a* V - |3* Vj * X.

Une fois toutes les contraintes réduites à cette forme, une règle de réparation doit être définie

pour être appliquée. Dans l'exemple des N-reines, la règle de réparation prend cette forme :

Si a* P| - P* Pj = \ alors, changer Pi ou Pj

La réparation d'une contrainte violée peut donner naissance à des nouvelles contraintes

violées qui ne pourront jamais être résolues. Ainsi, la réparation de contraintes peut produire

des chromosomes qui ne seront pas forcément des solutions au problème.

46

Les caractéristiques du ESP-GA sont résumées dans ce tableau :

Opérateur de croisement Croisement à un point

Opérateur de mutation Mutation aléatoire

Fonction de fitness En fonction du nombre des contraintes violées

Extra Règle de réparation

Tableau 1 - Algorithme ESP-GA

2.3.2.3.2 H-GA

Dans [EIB 94], Eiben et al. ont proposé d'incorporer des heuristiques de CSPs dans les

opérateurs de reproduction d'un algorithme génétique. Deux opérateurs génétiques ont été

spécifiés :

Un opérateur asexué qui, à partir d'un individu, crée un nouveau en modifiant les gènes

du premier, et

Un opérateur multi-parents qui crée une progéniture en partant d'un ou de plusieurs

parents.

Dans la littérature, nous trouvons que l'objectif, pour lequel cette méthode a été mise

en place, est atteint. Nous trouvons que, après l'intégration d'heuristiques utilisées dans les

algorithmes traditionnels de recherche et la sélection d'une représentation adéquate des

connaissances dont on dispose, il est possible de résoudre les CSPs par le moyen d'un

algorithme génétique.

a. Opérateurs asexués

Ces opérateurs ne s'appliquent qu'à un et un seul parent. Ils se basent sur l'idée

d'améliorer un individu en modifiant ses gènes. Cet opérateur est défini à l'aide de trois

47

paramètres : le nombre de valeurs à modifier, le critère d'identification de la position des

valeurs à modifier, le critère de définition des nouvelles valeurs à attribuer.

Pour la sélection des valeurs à modifier, plusieurs mesures peuvent être mises en place.

La plus simple d'entre elles prend en considération le nombre de contraintes violées par la

variable en question. La sélection des nouvelles valeurs prend en considération le nombre de

contraintes respectées qui font intervenir cette variable.

b. Opérateur multi-parents

Le principe de base de cet opérateur de croisement est le balayage : pour chaque

position, les valeurs des variables des chromosomes parents à cette position sont utilisées pour

déterminer la valeur de la variable à cette même position, mais dans le chromosome fils. La

sélection de cette valeur est effectuée en utilisant la même heuristique employée dans

l'opérateur asexué. La différence entre les deux opérateurs se résume au fait que l'heuristique,

pour l'opérateur multi-parents, évalue seulement les variables dans les chromosomes parents.

Ce tableau résume les caractéristiques de trois différents algorithmes génétiques se

basant sur des heuristiques :

Version 1 Version 2 Version3

Opérateur de

croisement

Opérateur asexué

avec heuristiques

multi-parents avec

heuristiques

multi-parents avec

heuristiques

Opérateur de

mutation Mutation aléatoire Mutation aléatoire

Opérateur asexué avec

heuristiques

Fonction de fitness Nombre de contraintes violées

Extra Aucun

Tableau 2- Algorithme H-GA

48

Les résultats obtenus sont encourageants, mais malgré cela nous remarquons

l'existence de plusieurs obstacles auxquels il faut faire face. L'un de ces problèmes se résume

dans le fait que l'ajout d'heuristiques à un algorithme génétique améliore la performance de ce

dernier, mais seulement pour les premières générations. Cette performance va se dégrader par

la suite à cause du fait que les opérateurs de croisement basés sur des heuristiques tendent à

réduire la diversité génétique beaucoup plus que les opérateurs de croisement classiques. Une

solution à ce problème peut être trouvée en générant une première partie de la progéniture en

utilisant les opérateurs de croisement basés sur les heuristiques et une deuxième partie en

utilisant les opérateurs de croisement classiques. Nous remarquons aussi que la majorité des

algorithmes de ce type, c'est-à-dire les algorithmes génétiques se basant sur des heuristiques,

sont lents. Cela est dû peut-être à leurs implementations qui ne sont pas faites pour être

rapides, mais pour être faciles à comprendre.

2.3.2.3.3 Arc-GA

Dans [RIFF 97, RIFF 96], M. C. Riff a présenté un algorithme évolutionnaire qui utilise des

informations extraites du réseau de contraintes dans l'élaboration de la fonction de fitness et

dans la définition du comportement des opérateurs de reproductions.

La fonction de fitness est basée sur la notion d'évaluation d'erreurs d'une contrainte.

L'évaluation d'erreurs d'une contrainte est la somme du nombre de variables qu'elle implique et

le nombre de variables liées à ces variables dans le réseau de contraintes. La fonction de fitness

d'un individu, appelée arc-fitness, est la somme des évaluations d'erreurs des contraintes que

cet individu viole.

L'opérateur de mutation, appelé arc-mutation, sélectionne aléatoirement une variable

d'un individu et lui assigne une valeur qui minimise la somme des évaluations d'erreurs des

contraintes impliquant cette variable.

L'opérateur de croisement, appelé arc-croisement, sélectionne aléatoirement deux

parents et construit à partir de cette base et par le moyen des procédures itératives une

49

progéniture tout en tenant compte des contraintes imposées par le problème de satisfaction de

contraintes à résoudre. Pour définir ces procédures, nous supposons que les contraintes sont

binaires. Soient V| et Vj les deux variables qu'une contrainte c implique.

a) Si les deux variables ne sont pas encore instanciées et si les deux parents ne

satisfont pas la contrainte c, alors on doit choisir les valeurs à attribuer à ces deux

variables des chromosomes parents d'une manière à minimiser la somme des

évaluations d'erreurs des contraintes impliquant Vi et Vj.

b) Si les deux variables ne sont pas encore instanciées et si l'un des deux parents

satisfait la contrainte c, alors les valeurs à attribuer à la progéniture doivent être

prises du chromosome de ce parent.

c) Si les deux variables ne sont pas encore instanciées et si les deux parents satisfont la

contrainte c, alors le parent ayant la meilleure fitness fournit ces valeurs à la

progéniture.

d) Si l'une des deux variables n'est pas encore instanciée, alors on lui attribue une

valeur choisie de l'un des chromosomes parents d'une manière à minimiser la

somme des évaluations d'erreurs des contraintes qui l'impliquent.

e) Si les deux variables sont instanciées alors on passe à la prochaine contrainte.

50

Ce tableau résume les principes de cette approche.

Opérateur de croisement Opérateur Arc- croisement

Opérateur de mutation Opérateur Arc-mutation

Fonction de fitness Arc-fitness

Extra Aucun

Tableau 3- Algorithme Arc-GA

2.3.3 Manipulation indirecte

La manipulation indirecte des contraintes consiste à les incorporer dans la fonction de

fitness de manière à ce que l'optimalité de cette dernière implique la satisfaction de la totalité

des contraintes. La majorité des fonctions de fitness, définies pour répondre à cela, se basent

sur l'utilisation des pénalités. Nous distinguons, dans la littérature, trois différentes manières de

définir les fonctions de pénalité. Elles sont présentées dans les prochains paragraphes.

2.3.3.1 Pondération des contraintes

La première, proposée par A.E. Eiben [EIB 01], consiste à remplacer les contraintes par

des fonctions objectifs. Ceci est vu comme étant une attribution de pénalités à toute violation

de contraintes. En principe chaque fonction de pénalité est une estimation de la médiocrité

d'une solution candidate qui peut être déterminée en calculant soit la distance entre la solution

candidate et la solution réalisable soit le coût de réparation de l'infaisabilité. Dans ce sens, deux

types de fonctions de fitness peuvent être définis servant chacune à :

Pénaliser toute violation de contraintes.

Pénaliser toute mauvaise instanciation de variables.

La valeur que retourne la première fonction correspondra au poids de la contrainte à

vérifier si cette dernière est violée et sera égale à 0 sinon. La deuxième fonction retourne le

51

poids d'une variable si une contrainte faisant intervenir cette dernière est violée et sera égale à

0 sinon. Voici une illustration de ces deux fonctions :

Soit C l'ensemble des contraintes q (i = {1,..., m}) et V l'ensemble des variables

Vj(j={l,...,n}). C' est l'ensemble des contraintes faisant intervenir la variable v,. Les fonctions de

pénalités peuvent être exprimées comme suit :

tr r \ ^T vr \ vr \ f 1 S l s VWle C; F-L(S) = ) w i*X(s,c i)avecX(s,c i) = \ . ' L-i y U sinon

i = l

i i

F2(s) = V Wi * X(s,C1) avecX(s,c t) = I 1

i = l

si s viole au moins une contrainte c £ C1

0 sinon

Cette manière de manipuler les contraintes semble être avantageuse puisqu'elle nous

permet de réduire le problème à une seule fonction d'optimisation. Elle nous permet aussi de

tenir compte des préférences des utilisateurs en les laissant agir sur l'attribution des poids aux

contraintes ou aux variables. Mais cette manière a aussi des inconvénients. En l'appliquant, on

risque de perdre de l'information puisqu'elle regroupe tout en un seul et simple nombre qu'on

ne peut pas interpréter. Ce nombre ne nous permettra pas, par exemple, de savoir quelle est la

contrainte qui a été violée ou celle qui a été respectée.

2.3.3.2 Fonctions objectifs modifiées

La deuxième manière utilisée pour définir les fonctions de pénalité est proposée par S.E.

Carlson [CARL 95]. Elle consiste à pénaliser les solutions qui violent une ou plusieurs contraintes.

Cela peut se faire en utilisant deux différentes méthodes :

Multiplier la fitness par un facteur afin de la réduire

Soustraire la distance entre la solution et la faisabilité

52

La première méthode, détaillée en [CARL 93], multiplie la fonction objectif par un

nombre généré en fonction du nombre d'itérations. Cette fonction, pour un problème de

maximisation, suit ce modèle :

nuit \ t r \ - f I s iX G F Obj(x) = cp * f(x)ou <p = [e_.n ( 1 + t ) s . x ç F

La valeur de t correspond au nombre d'itérations et F représente l'ensemble des

solutions faisables.

La deuxième méthode, proposée à l'origine par Michalewicz et Attia [MICH 94 b], a été

modifiée et énoncée par Joines et Houk [JOIN 94]. Elle consiste à soustraire la somme des

contraintes violées de la fonction de fitness. Plusieurs paramètres ont été intégrés dans cette

méthode :

ohm = f(X) + (c * tr * £ // oo

Où c, a et 6 sont des constantes et t est le nombre d'itérations.

La troisième, qui a été proposée par Powell et Skolnick [EIB 98], consiste à séparer les

solutions faisables des solutions infaisables. Cette approche, basée sur la somme des contraintes

violées, est recommandée vu le nombre d'avantages qu'on retrouve parmi ces caractéristiques :

Elle manipule les contraintes en intention

Son application ne nécessite pas la définition de paramètres

Elle ne demande que peu de simulations pour aboutir à la solution optimale

Elle ne nécessite pas un classement de contraintes.

Elle est aussi l'approche la plus sure à utiliser pour résoudre un problème peu détaillé et cela

parce qu'elle sépare les solutions faisables de celles infaisables pour les placer dans différents

intervalles. De cette manière, une solution qui viole une contrainte ne peut jamais être classée

au dessus d'une solution qui n'en viole aucune.

53

2.3.3.3 Fonctions de fitness adaptables

La troisième manière, proposée par A.E. Eiben et al. dans [DOZ 94], consiste à définir des

fonctions de fitness adaptables permettant ainsi de valoriser les contraintes difficiles à satisfaire

en leur attribuant un poids supérieur à celui du reste des contraintes.

Cette idée n'est pas aussi simple à implémenter pour les deux raisons suivantes :

L'estimation de la difficulté d'une contrainte afin de fixer son poids approprié peut être

coûteuse en termes de temps de calcul.

Les poids attribués à chaque contrainte peuvent changer au cours de l'exécution de

l'algorithme.

Une solution à ces deux problèmes peut être trouvée dans un algorithme qui fixe lui-

même les poids et les réajuste durant son exécution.

Dans ce qui suit, nous présentons deux algorithmes évolutionnaires qui, afin de

manipuler les contraintes, utilisent les pénalités et actualisent les fonctions objectifs durant

l'exécution.

Le premier algorithme est basé sur l'approche Co-évolutionnaire. Cela correspond à

l'idée d'avoir deux populations qui se battent constamment entre elles. L'algorithme utilisé dans

les expérimentations possède deux populations. La première est appelée la population solution

tandis que la deuxième est appelée la population de contraintes. La fitness d'un individu

appartenant à l'une de ces deux populations se base sur la notion de rencontres. Une rencontre,

dans ce cadre, s'explique par le fait qu'un individu de la population des contraintes sera apparié

avec un individu de la population solution. Si la contrainte est violée alors l'individu de la

population de contraintes aura un point sinon c'est l'individu de la population solution qui aura

ce point. La fitness d'un individu correspondra au nombre de points qu'il a pu obtenir durant les

dernières 25 rencontres. À chaque génération de l'algorithme évolutionnaire, 20 rencontres

54

sont exécutées par une sélection répétitive d'individus de chacune des deux populations. À

chaque rencontre, deux chromosomes parents subiront un croisement à deux points pour

donner naissance à deux enfants qui seront par la suite mutés. La taille de la population de

contraintes est déterminée en fonction du nombre de contraintes du problème tandis que la

taille de la population solution est fixée à 50 individus.

Le deuxième algorithme évolutionnaire se base sur un mécanisme appelé SAW

(Stepwise Adaptation of Weights). II a été introduit par Eiben et Hauw [EIB 95] comme étant une

version améliorée du mécanisme d'adaptation de poids introduit par Eiben, Raué et Ruttkay [EIB

97]. L'idée principale de ce mécanisme se résume dans le fait qu'une contrainte qui n'est pas

satisfaite après un certain nombre d'étapes doit être classifiée comme étant une contrainte

difficile. Une telle contrainte doit avoir un poids supérieur à celui attribué au reste des

contraintes. Afin d'implémenter cette idée, on pourrait commencer notre algorithme par

l'initialisation de tous les poids des contraintes à 1 et on procédera au fur à mesure au

réajustement de ces poids en ajoutant une valeur A après une certaine période. Ce

réajustement ne pourra être appliqué qu'aux contraintes qui sont violées par le meilleur

individu de la population.

En prenant appui sur la littérature consultée, nous nous sommes basés sur trois

approches de résolution pour élaborer nos contributions. Nous les détaillerons tout au long des

trois prochains chapitres.

55

Chapitre 3. Approches de résolution

Nous présenterons dans ce chapitre les différentes approches que nous avons mises en

œuvre pour résoudre le problème d'allocation optimale de plusieurs unités de recherche. Ces

approches de résolution sont formulées à partir d'algorithmes génétiques.

Nous voulons contribuer par ce travail à évaluer l'efficacité des algorithmes génétiques

dans la résolution de la tâche d'affectation de multiples ressources aux opérations SAR. Cette

tâche, qui est assurée par les coordonnateurs de missions (SMCs), consiste à déterminer le

meilleur emplacement pour affecter les unités de recherches disponibles aux différentes régions

de la zone d'intérêt. À terme, les techniques proposées dans ce chapitre pourraient être

intégrées dans un système d'aide à la décision et viseraient à augmenter les chances de trouver

l'objet recherché en un délai minimum.

Notre contribution consiste à associer, en partant d'une grille décomposant l'espace de

recherche en sous-secteurs, un rectangle à chaque unité de façon à maximiser la probabilité de

retrouver l'objet recherché. De plus, nous imposons la contrainte que tous des rectangles

attribués ne se chevauchent pas. En fin de compte, nous obtenons comme solution un nombre

de rectangles disjoints égal au nombre d'unités de recherche.

Nous présentons sur la figure suivante un exemple de grille appliquée à une région de

recherche bien délimitée.

56

Figure 13-Exemple de répartition des ressources sur une grille donnée

Cette grille, formée de 30 cellules, est décomposée en un nombre de rectangles égal au

nombre d'unités de recherche. Ce dernier correspond, dans notre cas, à cinq unités réparties de

la manière suivante :

La première unité couvre les secteurs 1, 2,3, 7, 8, 9,13,14 et 15.

La deuxième unité couvre les secteurs 4, 5,6 10,11 et 12.

La troisième unité couvre les secteurs 16,17,18,22, 23, 24.

La quatrième unité couvre les secteurs 19, 20, 21, 22,25, 26, 27, 28.

La cinquième unité couvre les secteurs 29 et 30.

Dans l'exemple illustré, nous avons voulu mettre l'accent sur un problème qu'on peut

fréquemment rencontrer. Ce dernier surviendrait lors du chevauchement d'au moins deux

rectangles. Comme on peut le voir dans la figure 13, les rectangles balayés respectivement par

les unités de recherche 3 et 4 se chevauchent au niveau du secteur 22. Pour éviter toute

collision possible durant leur vol et pour mieux utiliser les ressources, il nous est recommandé

de veiller à ce que cela ne se produise pas lors de l'assignation des zones de recherche

(rectangles) aux unités de recherche.

57

Nos expérimentations ont été menées sur une zone de recherche, semblable à celle

illustrée dans la figure précédente, qui s'étend sur 57,000km2. Nous discrétions cette zone par

une grille composée de 95 par 7 cellules de superficies égales. Chacune des cellules mesure 5

par 5 miles nautiques, avec 1 mile nautique=l, 852 kilomètres. C'est à partir de ces dernières

que les rectangles sont formés. Ces rectangles représentent les espaces qui sont ratisses par les

unités de recherche afin de localiser l'objet. Plus la taille des cellules est petite, plus grand sera

le nombre de rectangles possibles.

Nous avons utilisé trois différentes distributions de probabilité de localisation : point de

référence (point datum), la distribution CSAD et ligne de référence (line datum) [ABI 10]. À

chacune de ces trois distributions correspond une grille illustrant la probabilité que l'objet

recherché soit à l'intérieur d'une cellule quelconque.

1. Point de référence (point datum) : c'est une distribution normale, à deux variables. Elle

est centrée sur le dernier point connu de l'objet recherché (Figure 14). L'écart type o des

deux variables est supposé égal et la corrélation entre les deux variables est nulle. La

figure suivante illustre la variation de la probabilité de localisation sur une grille suivant

cette distribution.

I Figure 14-Distribution « Point datum » de la probabilité de localisation sur une grille de recherche

2. La distribution CSAD (Canadian Search Area Definition) [SAU 87] : cette distribution est

basée sur l'analyse de données rassemblées entre 1981 et 1986 sur des sites connus

d'écrasement correspondant à des avions perdus dont la trajectoire est connue à

l'avance. Cette distribution ne peut être utilisée que dans le cas où on connaît la

trajectoire de l'avion et qu'on veut utiliser des données historiques pour estimer la

58

probabilité de la localisation. Nous notons ici que ces dernières portent seulement sur

les avions qui ont été retrouvés. C'est la raison pour laquelle nous signalons une

concentration des meilleures probabilités de localisation sur des secteurs bien

particuliers le long de la trajectoire prévue (Figure 15). Nous illustrons sur cette figure la

dispersion de la probabilité de localisation sur une grille de recherche suivant ce type de

distribution.

Figure 15-Distribution « CSAD » de la probabilité de localisation sur une grille de recherche

3. Ligne de référence (line datum) : c'est une distribution uniforme sur la trajectoire de

l'objet recherché et une distribution normale autour de la trajectoire (Figure 16). Cette

distribution est souvent utilisée quand le dernier point et la destination sont connus. La

figure suivante illustre la distribution Line Datum de la probabilité de localisation sur une

grille de recherche.

. . .

Illllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

iiimimiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiimiiiiiiiiii [....LUI i i.nnr__i i i. Figure 16-Distribution « Line Datum » de la probabilité de localisation sur une grille de recherche

Les approches de résolution que nous avons mises en place peuvent être classées sous

trois différentes catégories. La première utilise un algorithme génétique classique afin d'obtenir

une solution. La deuxième consiste à manipuler les contraintes à satisfaire dans un algorithme

génétique. Nous essayons de modifier les opérateurs de reproduction de l'algorithme génétique

dans le but de nous assurer que le maximum possible de solutions respecte les contraintes

imposées. Dans la troisième catégorie, nous nous penchons sur les possibilités dont on dispose

59

pour mettre en place une fonction de fitness qui s'adapte au fur et à mesure que notre

population s'élargit d'une génération à une autre. Le but est d'arriver à définir une fonction

capable de prendre en considération le nombre de générations et ceci dans l'espoir de trouver

de meilleurs résultats que ceux obtenus avec les deux catégories précédentes.

En partant de ces catégories, nous avons implémenté différentes versions de

l'application qui sont toutes formulées à partir du modèle d'un algorithme génétique. D'une

version à une autre, des modifications sont apportées sur l'une des phases de l'algorithme

génétique et ceci dans le but d'améliorer la qualité des solutions obtenues. Dans ce chapitre,

nous commençons par la présentation d'un schéma général d'un algorithme génétique, les

étapes le constituant et le rôle de chacune d'elles. Par la suite, nous présentons notre première

contribution qui se résume à mettre en place un algorithme génétique classique pour résoudre

notre problème. Les deux autres approches de résolution sont présentées dans les chapitres 4 et

5.

3.1 Schéma général d'un algorithme génétique

Un algorithme génétique suit un processus bien établi, défini comme un cycle

d'évolution. II opère sur une population composée d'individus, tous différents, constituant des

solutions potentielles au problème. Un algorithme génétique est caractérisé par a) son type, b)

le type du génome représentant chaque individu de la population, c) la manière avec laquelle il

crée la population initiale, d) ses opérateurs de croisement et de mutation et e) sa fonction

objectif.

La figure suivante illustre le programme principal de tous les algorithmes implémentés

pour chacune des versions mises en place. Ce sont les étapes par lesquelles doit passer tout

algorithme génétique.

60

Algorithmel Fonction principale d'un algorithme génétique

1: Input

2: Fitness, la fonction de fitness qui évalue la qualité d'un individu

3 : N, le nombre d'individus

4: Début

5: //Définition des paramètres de l'algorithme génétique :

population, un ensemble de N individus ;

époque, le nombre de générations ;

P-croisement, la probabilité de croisement ;

P-mutation, la probabilité de mutation.//

6: Définition du génome

//Préciser un format sous lequel les données seront stockées, traitées et affichées. Dans

notre cas, la définition du génome est assurée par la mise en place d'une classe

rectangle.//

7: population <- création de la population initiale de N individus

8: For each individu de population do

9: calculer la fitness de l'individu

10: End For

11: best <- mémoriser le meilleur individu

//Sauvegarder l'individu ayant la meilleure fitness

12 : For i=0 to époque

13 : indl<- sélection d'un individu de la population

14 : ind2<- sélection d'un autre individu de la population

15: childl<- croisement (indl, ind2)

//On sélectionne à la fois une paire d'individus ou de génomes sur laquelle on

applique le croisement avec une probabilité P-croisement//

16 : child2<- mutation (childl)

//La mutation est appliquée sur un seul individu ou génome avec une probabilité

P-mutation//

61

17 population=population +childl + child2

//Ajouter la progéniture à la population déjà existante

18: For each individu de population do

19 calculer la fitness de l'individu

20 End For

21 population^- garder les N meilleurs individus

22 best <- le meilleur individu de population

23 End For

24 Retourner best

//le meilleur individu de toutes les générations

25 Fin

Figure 17-Fonction principale d'un algorithme génétique

Nous dégageons à partir de cet algorithme les éléments clés suivants :

La définition du génome,

le mécanisme de création de la population initiale,

la fonction objectif,

les opérateurs de reproduction.

Ces éléments sont présentés, une première fois, avec l'approche des algorithmes

génétiques classiques dans la prochaine section. Nous les aborderons de nouveau par la suite

lorsqu'ils seront sujets à des modifications pour les autres approches de résolution.

Nous précisons ici que l'implémentation de toutes les versions de l'algorithme a été

effectuée en utilisant GALib. C'est une librairie évolutive, programmée en C++, qui permet

d'utiliser plusieurs types d'algorithmes génétiques. En plus des fonctions classiques d'un

programme génétique, cette librairie inclut des algorithmes d'optimisation tels que le scaling et

le sharing.

62

L'utilisation de cette librairie permet, en plus de la résolution d'un problème,

l'amélioration de sa solution et ce, grâce à l'application des différentes méthodes de sélection et

des méthodes de calcul de la fitness nécessaires à la sélection.

GALib propose plusieurs types d'algorithmes génétiques dont l'utilisation nous permet

aussi de tester plusieurs avenues de création des populations d'individus. Une multitude

d'alternatives serait donc envisageable pour aboutir à une solution. Parmi les types disponibles,

nous avons préféré utiliser « GAsteadystateGA ». Afin de créer la population initiale d'individus,

ce type d'algorithme sauvegarde une copie de celle proposée par l'utilisateur pour qu'il puisse

s'en servir. À chaque génération il crée une population d'individus temporaires, l'ajoute à la

dernière population et élimine les plus mauvais individus afin de rendre à la population actuelle

sa taille originale. Cet algorithme est le seul parmi les différents types d'algorithmes génétiques

qui permet un aussi large chevauchement entre les populations de deux générations

successives. Nous trouvons parmi les autres types ceux qui utilisent des populations séparées ou

ceux qui n'autorisent le chevauchement que sur un nombre limité d'individus (seulement un ou

deux individus peuvent être remplacés d'une génération à une autre). L'utilisation d'un

algorithme « GAsteadystateGA » permet une meilleure exploration de l'espace de recherche,

l'évaluation d'un plus grand nombre de solutions possibles et l'élimination continue des plus

faibles individus. Ce sont les raisons pour lesquelles nous avons choisi de travailler avec ce type

d'algorithmes.

3.2 Algorithme génétique classique

Dans cette section, nous présenterons la première version de l'algorithme sur laquelle

nous construisons toutes les autres versions étudiées dans ce mémoire. Nous avons choisi de le

nommer ainsi parce qu'il s'appuie sur la formulation standard d'un algorithme génétique : la

création de la population initiale, la mutation et le croisement s'effectueront tous de manière

aléatoire tout en respectant le modèle que nous nous sommes fixé.

63

3.2.1 Présentation du modèle

Cette section comporte une description détaillée de chacune des étapes clés de

l'algorithme développé. Nous définissons le codage utilisé pour représenter un génome, la

procédure suivie pour créer la population initiale, les critères que la fonction objectif doit

respecter et la manière avec laquelle les opérateurs de reproduction sont effectués.

3.2.1.1 Génome

Un génome doit présenter une solution au problème à résoudre. Dans notre problème,

il décrit un certain nombre de rectangles (secteurs de recherche) disjoints sur lesquels la

recherche des objets perdus sera effectuée. Un génome peut être codé de plusieurs façons :

sous forme binaire, sous forme de tableau ou de liste. Pour répondre à nos besoins, nous codons

le génome sous forme d'une liste de rectangles. La liste aura comme longueur le nombre

d'unités qui effectueront la recherche. De cette manière, on pourrait attribuer chaque secteur à

une unité de recherche. Chaque élément de la liste correspond à l'objet rectangle décrivant

l'aire de recherche d'une unité.

La figure 18 nous donne une idée de la structure que peut prendre un génome. Dans cet

exemple, le nombre de rectangles que le génome contient est 6. Ceci correspond également au

nombre d'unités de recherche qui effectueront le balayage des sous-secteurs.

64

. 1 *m

-

wm I SJ

USSA

^ T Num rectangle POS XinfG YmfG Nbre hçne s Nbre colonnes EffoitrNumSRU)

1&9211 1^2514 6^054 88691 Î321 81596 0.01 0.06 0.07 0.02 0.01 0.08 2 3 15 23 31 29 2 12 6 17 3 22 4 4 5 4 4 4 6 9 4 9 5 14 0 1 — 3 4 5

Figure 18-Exemple de génome

3.2.1.1.1 Les attributs d'un rectangle de recherche

Les attributs permettant de décrire un rectangle sont les suivants :

Numéro : C'est une variable entière qui désigne l'identifiant du rectangle sur lequel les

recherches vont être effectuées.

POS : C'est une variable réelle qui représente la probabilité de succès de chaque paire

(rectangle, unité de recherche).

XinfG : C'est une variable entière qui désigne l'abscisse du coin inférieur à gauche du

rectangle.

YinfG : C'est une variable entière qui désigne l'ordonnée du coin inférieur à gauche du

rectangle.

nbligne : C'est une variable entière qui représente le nombre de lignes d'un rectangle.

65

nbcolonne : C'est une variable entière qui représente le nombre de colonnes d'un

rectangle.

Effort : C'est une variable entière qui représente l'unité de recherche qui sera allouée

pour balayer le rectangle durant la recherche.

3.2.1.1.2 Les méthodes associées à un rectangle

Pendant le processus d'optimisation, nous devons effectuer certaines manipulations des

rectangles. Les principales sont les suivantes : la superposition de rectangles, la surface de

superposition, la superficie d'un rectangle, le calcul du nombre d'intersections et le calcul de la

surface d'intersection.

a) Superposition de rectangles

C'est une fonction qui retourne une valeur booléenne indiquant si deux rectangles se

superposent ou non. Pour déterminer s'il y a superposition, nous commençons par déterminer

les coordonnées du coin supérieur droit des deux rectangles. Ceci est déterminé à partir des

coordonnées du coin inférieur gauche, du nombre de lignes et du nombre de colonnes. Un

exemple de rectangle est illustré dans la figure suivante. Notons que o et d représentent

respectivement le coin supérieur gauche et le coin supérieur droit.

v Y i

> d= Y » ♦ NL < i J

h ..„ h de N t <

Y, a

—►■

— > r l r X. = Xa + Nc Y . 1 T 1 1 1 1 ! 1 1 1 1 i 1

i>i s

Figure 19-Les abscisses et les ordonnées des deux points marqueurs d'un rectangle

66

Après avoir déterminé les coordonnées des deux points marqueurs des rectangles, nous

procédons à la comparaison des abscisses et des ordonnées des points des deux rectangles afin

de déterminer s'il y a intersection. Nous illustrons dans la figure 20 deux cas d'intersection que

nous pouvons rencontrer.

i y

i . Y d i i d

O r i

«2 i i i

a i « 1

Y > y

1 e r cas -.eme 2 cas

Figure 20-lntersection de deux rectangles

Dans ces deux cas, nous désignons par Oj et a2 les deux coins inférieurs gauches des

deux rectangles. Les deux coins supérieurs droits sont nommés dx et d2.

Dans le premier cas d'intersection (Figure 20), o2 se trouve à l'extérieur du premier

rectangle. Pour qu'il y soit intersection, il faut que a2 soit placé de façon à ce qu'il ne dépasse

pas di en abscisse et en ordonnée. Quant à d2, il faut que son abscisse et son ordonnée soient

supérieurs respectivement à l'abscisse et à l'ordonnée du coin Oj.

Dans le deuxième cas (Figure 20), a2 se trouve à l'intérieur du premier rectangle. Dans ce

cas, et peu importe où se trouve d2, il y aura toujours intersection.

b) Surface de superposition

C'est une fonction qui calcule la surface de superposition de deux rectangles. S'il y a

superposition des deux rectangles, nous déterminons la hauteur et la largeur de la zone

67

commune entre les deux rectangles. Ce qui nous permet de calculer la surface de superposition.

Pour une meilleure illustration, on reprend les deux cas présentés dans la figure 20. La surface

de superposition est colorée différemment.

» i I -.ème 2 cas 1 cas

Figure 21-Surface de superposition

Dans le premier cas, la hauteur de la zone de superposition est égale à la différence des

ordonnées des points d2 et ai. La largeur correspond à la différence des abscisses des points a2

etdi .

Dans le deuxième cas, la surface de superposition correspond exactement à la surface

du deuxième rectangle puisqu'il est totalement à l'intérieur du premier rectangle. Dans le cas où

le deuxième rectangle déborde, on soustrait de sa surface la superficie de la zone qui n'est pas

commune aux deux rectangles.

c) Superficie d'un rectangle

Cette fonction permet de calculer la superficie d'un rectangle donné et cela en

multipliant le nombre de lignes par le nombre de colonnes.

68

d) Calcul du nombre d'intersections

Cette fonction calcule le nombre d'intersections qu'un rectangle peut avoir avec les

autres rectangles du même génome. Elle reçoit en entrée l'indice du rectangle en question et le

vecteur contenant la totalité des rectangles d'un génome. On parcourt ce vecteur de rectangles

en appliquant la méthode de superpos i t ion de rec tang les . À chaque fois que le

rectangle en question en croise un autre du même génome, un compteur est incrémenté. Ce

compteur représentera à la fin le nombre d'intersections qu'un a.

Algorithme2 Fonction calculant le nombre d'intersections entre rectangles

Fonction Calcul nombre intersection (X : indice rectangle, vecteur de rectangles)

1: Début

2 : nbr_inter=0

3 : //Initialisation de la variable correspondant au nombre d'intersections

4: For (i=0 ; knombre de rectangles dans le vecteur ; i++)

5: l f X * i

6: If Superpose (Rectangle^ RectangleJ

7: Then nbr_inter = nbr_inter + 1

8: End If

9: End If

10: End For

11: Retourner nbr_inter

12 : Fin

Figure 22 — Fonction de calcul du nombre d'intersections entre rectangles

e) Calcul de la surface d'intersection

Cette fonction calcule la surface résultante de l'intersection d'un rectangle avec les

autres rectangles du même génome. Elle reçoit en entrée, comme la dernière, l'indice d'un

69

rectangle et le vecteur contenant la totalité des rectangles d'un génome. En parcourant ce

vecteur, on peut constater la superposition entre deux rectangles. Dans ce cas, on calcule la

surface d'intersection en utilisant la méthode Surf ace de superpos i t i on déjà définie dans

la classe rectangle. Cette superficie est ajoutée à une variable qui contiendra la somme de

toutes les surfaces d'intersection que peut avoir un rectangle avec d'autres du même génome.

Algorithmes Fonction calculant la surface de superposition

Fonction Calcul surface intersection (X : indice rectangle, vecteur de rectangles)

1: Début

2 : surf=0

3 : //Initialisation de la variable correspondant à la surface de superposition du rectangle

en question avec chacun des autres rectangles du génome//

4: surf_totale_inter=0

5: //Initialisation de la variable contenant la surface totale de superposition

6: For (i=0 ; knombre de rectangles dans le vecteur ; i++)

7: l f X * i

8: If Superpose (Rectanglex, Rectangle;)

9: //S'il y a superposition entre les deux rectangles

10: Then surf= surface de superposition (Rectanglex, Rectangle^

11: surf_totale_inter = surf_totale_inter + surf

12: End If

13: End If

14: End For

15 : Retourner surf_totale_inter

16 : Fin

Figure 23 — Fonction de calcul de la surface de superposition entre rectangles

70

3.2.1.2 Création de la population initiale

Cette étape de l'algorithme génétique consiste à générer, à partir de l'ensemble de

connaissances dont on dispose, un nombre déterminé d'individus afin de former une

population. Cette population initiale représente le point de départ du processus de résolution

du problème.

Pour la version de base de l'algorithme, la création de la population initiale est effectuée

aléatoirement. Elle consiste à générer les rectangles pour une grille donnée. Ces rectangles sont

par la suite regroupés dans des chromosomes dont la longueur est égale au nombre d'unités de

recherche disponibles. Même s'il s'effectue aléatoirement, le choix de ces rectangles doit

s'assurer que chaque rectangle soit balayé par une unité différente. Par exemple, pour un

génome à 7 gènes, il faut sélectionner 7 rectangles différents balayés par 7 unités différentes.

Cette condition doit être vérifiée lors de l'insertion de chaque rectangle dans le génome. Le

génome est, à son tour, ajouté à la population initiale jusqu'à l'atteinte du nombre maximal

d'individus fixé par l'utilisateur. La fonction d'initialisation, sur laquelle se base cette tâche de

création, est détaillée dans l'algorithme 4.

Algorithme4 Fonction d'initialisation permettant la création de la population initiale

Fonction initialisation(Génome)

Début

For (i=0 à knombre d'unités de recherche ; i++)

Do

num_rect = random (0, nombre total de rectangles)

//Choisir aléatoirement un numéro de rectangle

Rect = vecteur_de_rectangles[num_rect]

//Extraire le rectangle correspondant au numéro choisi aléatoirement

Until (Rect.numéro_unité = i)

//Garder seulement le rectangle dont le numéro de l'unité de recherche est égal à i

71

7: Add (génome, Rect)

//Ajouter ce rectangle au génome en cours de construction

8: End for

9: Insertion du génome dans la population

10: Fin

Figure 24 — Fonction de création de population initiale

Le nombre de fois où cette fonction est appelée correspond exactement au nombre

d'individus défini par l'utilisateur.

3.2.1.3 Fonction objectif

Cette fonction permet de déterminer la fitness de chaque individu de la population. Tout

individu d'une population est représenté par un chromosome qui est constitué par un ensemble

de gènes. Tel que vu précédemment, ces derniers correspondent aux rectangles qui forment les

chromosomes de la population. Cette fonction nous permet de valoriser un rectangle en lui

attribuant une valeur qui reflétera son degré d'adaptation à la population qu'on veut atteindre.

De plus, cette valeur de fitness permet de comparer les individus entre eux.

Une solution à notre problème est un chromosome dont la somme des probabilités de

succès (POS) des rectangles solutions est maximale et dont les rectangles, le constituant, ne se

superposent pas.

Nous avons fait intervenir dans le calcul de la fonction objectif, définie pour cette version de

l'algorithme, deux composantes :

La première se rapportant à la probabilité de succès. Nous rappelons que la probabilité de

succès désigne la probabilité de localiser un objet dans le rectangle en tenant compte de

l'effort de recherche et la probabilité que l'objet y soit présent. Cette probabilité valorise

72

les rectangles offrant une meilleure performance. Le meilleur d'entre eux aura plus de

chance d'être sélectionné.

La deuxième se rapporte à l'intersection qu'il peut y avoir entre les rectangles. Notre

objectif est de trouver un certain nombre de rectangles qui ne se superposent pas. Ce

facteur vise à pénaliser tout rectangle pouvant se superposer avec un autre. II est calculé en

fonction du nombre d'intersections et de la surface d'intersection d'un rectangle. Pour

ramener ces valeurs de pénalité sur une échelle [0, 1], nous les pondérons respectivement

par rapport au nombre d'intersections maximal et à la surface du rectangle i. Le nombre

d'intersections maximal dépend essentiellement du nombre de rectangles qu'un génome

peut contenir. Par exemple, pour un génome de 7 rectangles, le nombre d'intersections

maximal de chaque rectangle sera égal à 6.

Pour faire le calcul de la cote de chaque rectangle, nous avons utilisé deux fonctions (Calcul

du nombre d'intersections et Calcul de la surface d'intersection d'un rectangle) que nous avons

définies dans la section 3.2.1.1.2.

La fonction objectif définie pour cette version est présentée à la figure 25. Elle prend en

considération la probabilité de succès et la superposition des rectangles.

Avec

Cote rectangle t — /? x (Succèsi) + (1 — /?) X (1 — intert)

i r , t p r _„. v /'nombre d'intersection s / \ inier «. * ^ 'nombre d'intersection max/ T

( . „s ^/'surface d intersection. / \ t1-*-* * l IsurfaceJ

Et

Succèsi — ' / POSmax

Où:

Inter i : Le facteur d'intersection du rectangle i.

Succès i : La probabilité de succès normalisée du rectangle i.

73

POS i : La probabilité de succès du rectangle i.

POSmax : La probabilité de succès la plus importante de tous les rectangles possibles.

Nombre d'intersections i : Le nombre d'intersections du rectangle i avec les autres rectangles du

même chromosome.

Nombre d'intersections max : Le nombre d'intersections maximal entre rectangles. II

correspond au nombre de rectangles dans un génome décrémenté de 1.

Surface d'intersection i : La somme des surfaces d'intersection du rectangle i avec les autres

rectangles du même chromosome.

Surface i : La surface du rectangle i.

Figure 25-Formule de base de la fonction de fitness

La fitness d'un individu de la population correspond à la somme des fitness des gènes de

ce chromosome, c'est-à-dire la somme des valeurs des rectangles qui le constituent. La fonction

objectif globale d'un individu prendra dans ce cas cette forme :

avec:

Fitness(chromosome) = y cote rectangle i 1 = 1

n: le nombre de rectangles d'un chromosome

Figure 2 6-Formule de la fonction de fitness

3.2.1.4 Opérateurs de reproduction 3.2.1.4.1 Opérateur de mutation

Cet opérateur nous permet d'apporter des modifications sur le génome afin d'améliorer

notre solution. La plupart des versions de l'opérateur de mutation que nous avons implémenté

durant l'expérimentation de notre application se basent toutes sur un même principe. II consiste

à supprimer le gène le plus faible du génome qu'on est entrain de manipuler. Ce gène,

représentant un rectangle, est par la suite remplacé par un autre dans le but d'avoir une

solution meilleure.

74

L'opérateur, défini pour cette version simplifiée, évalue en premier lieu les rectangles du

génome dans le but de déterminer le plus faible d'entre eux. Ce dernier est supprimé et

remplacé par un autre qu'on choisit aléatoirement. Pour augmenter nos chances d'avoir des

solutions réalisables, nous insérons un rectangle ayant le même numéro d'unité de recherche

que celui qui est supprimé.

Algorithmes Opérateur de mutation

Début

Extraire le génome dans un vecteur de rectangles

f = max (fitness)

//Définir un réel pour la comparaison entre les fitness des rectangles du génome

4: For (i=0 ; knombre de rectangles du génome ; i++)

5: Appliquer la fonction de fitness sur les rectangles du génome

6: If (fitness (rectangle,) < f)

7: Then f = fitness (rectangle:)

8: X = i //Mémoriser le numéro d'unité de recherche du plus faible rectangle

9: End If

10: End For

11: Supprimer le rectangle d'indice X

12: Do

13: num_rect = random (0, nombre total de rectangles)

//Choisir aléatoirement un numéro de rectangle

14: Rectjnsert = vecteur_de_rectangles[num_rect]

//Extraire le rectangle correspondant au numéro choisi aléatoirement

15: Until (Rect_lnsert.numéro_unité = X)

//Refaire le traitement jusqu'à ce que le numéro de l'unité du rectangle choisi soit

égal à X//

16: Insérer Rectjnsert à l'indice X 17: Fin

Figure 27 — Fonction de mutation

75

3.2.1.4.2 Opérateur de croisement

Cet opérateur permet d'explorer un plus large espace de recherche. D'une génération à

une autre, les populations évoluent et sont différentes de celles qui les précèdent. Le type de

croisement que nous avons retenu est le croisement à un point. II consiste à choisir

aléatoirement une position où nous croisons les deux gènes des deux chromosomes parents. Ce

croisement donne naissance à deux autres chromosomes qu'on appelle chromosomes enfants.

Le point de croisement doit être inférieur à la longueur du génome. Ce croisement est, en

d'autres termes, une permutation de gènes de deux chromosomes.

L'exemple de la figure 28 illustre bien le fonctionnement de cet opérateur. Nous

choisissons comme point de croisement le 4lème rectangle. Suite au croisement des deux

chromosomes parents, les deux chromosomes enfants qu'on obtient sont l'inverse de leurs

parents pour les trois derniers gènes.

P i P2

109 620 102 SS6 132 815 0.01 0.06 0.07 0.02 0.01 0.08 4 -> 4 3 0 2 38 5 - 19 1 81 1 1 1 4 1 3 1 1 -> 1 1 1 0 1 2 3 4 5

I Point de croisement chois» aléatoirement

Fl F2

109 620 102 6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4

0.01 006 0.07 6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4

4 4

6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4

38 5 ~7

6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4 1 1 1

6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4

1 1 1

6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4

0 1 2

6SS 0.09 0 S

321 0.06 1 6

1 4

158 0.01 3 IS 4

190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1

886 132 815 190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1

0.02 0.01 0.08 190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1

3 0 ■ >

190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1

19 1 81

190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1 4 1 3

190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1

1 2 1

190 0.03

20 1 1 0

260 0.0"

4

1

122 0.04 6 9 1

3 4 5

Figure 28-Croisement à un point

76

3.2.2 Présentation et analyse des résultats

Nous présentons dans cette section les résultats expérimentaux obtenus avec la

première version de l'algorithme. Cette dernière met en œuvre un algorithme génétique

classique faisant intervenir les opérateurs de reproduction que nous venons de définir.

Le but de ces expérimentations est d'évaluer la capacité d'un algorithme génétique

classique à trouver une solution réalisable à notre problème. Cette évaluation se base

essentiellement sur l'évolution de la probabilité de succès (POS) des solutions en fonction de la

variation du paramètre (3 utilisé dans la fonction objectif. Ces expérimentations ont été utiles,

car elles nous ont permis de fixer les paramètres de l'algorithme génétique pour obtenir de

meilleurs résultats. On note parmi ces paramètres le nombre de générations, le nombre

d'individus, le pourcentage de croisement et la probabilité de mutation.

Comme nous l'avons déjà précisé, nos expérimentations sont menées sur trois

différentes grilles : Point Grid, CSAD Grid et Line Grid. Elles correspondent respectivement à

l'une des distributions de probabilité de localisation suivantes : point de référence, la

distribution CSAD et ligne de référence. Sur chacune de ces grilles, nous avons fixé trois

scénarios d'allocation d'effort allant de 5 à 7 unités de recherche disponibles.

Avant de présenter les résultats obtenus avec cette version, nous rappelons dans le

tableau récapitulatif suivant le mode de fonctionnement des éléments sur lesquels se base

notre algorithme :

77

Versionl :

Élément Mode de fonctionnement

Création de la population initiale Choix aléatoire des individus à ajouter à la population

Mutation Choix aléatoire des gènes à insérer dans le génome muté

Croisement Choix aléatoire du point de croisement

Fonction objectif P x (Succès^ + (1 - p) x (1 - inter,)

Tableau 4-Tableau récapitulatif de la version 1 de l'algorithme

Après avoir lancé les premiers essais, il s'est avéré que la variation du paramètre oc,

utilisé dans la fonction objectif présentée dans 3.2.1.3, n'affecte pas réellement les résultats

obtenus. C'est la raison pour laquelle nous l'avons fixé à 0 dans les expérimentations

correspondant à cette version et à toutes les versions d'amélioration. Nous avons également

remarqué que si on veut avoir une meilleure observation sur l'évolution de la probabilité de

succès (POS) en fonction du paramètre p, il vaut mieux fixer le nombre d'individus à 100, le

nombre de générations à 5000, le pourcentage de croisement à 90% et la probabilité de

mutation à 0,2.

II est important de prendre note que notre application ne nous retourne pas la même

solution même si on attribue les mêmes valeurs aux paramètres de l'algorithme. Ceci est dû au

fait qu'il s'agit d'un algorithme génétique faisant intervenir des opérateurs dont le

fonctionnement s'effectue selon un mode aléatoire. Pour obtenir nos résultats, nous avons fixé

un nombre d'essais pour lequel l'algorithme est ré exécuté. Le nombre choisi est 200. Cela

implique que pour chaque valeur de P l'algorithme est exécuté 200 fois. La probabilité de succès

qu'on retient pour cette valeur de P est la moyenne des probabilités de succès des solutions

réalisables obtenues lors de ces itérations. Ceci est valide pour toutes les versions implémentées

de l'algorithme.

78

Nous nous soucions, dans les résultats que nous allons présenter, de la qualité des solutions

obtenues dont les critères sont les suivants :

La valeur moyenne des probabilités de succès des 200 solutions obtenues pour chaque

valeur de p;

Le nombre de solutions infaisables qu'on retrouve parmi les 200 solutions que

l'algorithme nous retourne pour chaque valeur de p. Ce critère est représenté sous

forme de pourcentage qu'on nommera pourcentage d'infaisabilité.

Nous observons l'évolution de ces deux critères en fonction du type de grille sur laquelle

les recherches vont être effectuées, du nombre d'unités de recherche disponibles et bien

évidemment en fonction de la valeur de p.

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,42 11,20 11,16 11,31 11,11 11,23 11,56 11,36 11,48 11,61 11,69

%infaisabilité 12,5 % 25,5% 23,5 % 2 1 % 27,5% 18,5% 23% 28% 29% 39,5% 56%

6 Unités

Moyenne POS 1,77 11,83 11,48 11,40 11,58 12,01 11,75 11,94 12,02 12,10 12,60

%infaisabilité 34% 34,5% 33,5% 32% 35,5% 33% 32,5% 39,5% 54,5% 60% 72%

7 Unités

Moyenne POS 2,97 17,24 17,07 17,70 17,87 18,43 18,16 17,86 19 19,73 20,69

%infaisabilité 39% 47,5% 43% 40,5% 48% 47% 46,5% 54% 56,5% 72% 82,5%

79

Grille : CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 0,97 3,55 3,49 3,54 3,54 3,51 3,49 3,52 3,63 3,67 3,75

%infaisabilité 15,5% 15,5% 17% 19,5% 21,5% 19,5% 22,5% 25% 27,5% 32% 55,5%

6 Unités

Moyenne POS 1,24 4,05 4,02 4,08 4,03 4,04 4,08 4,08 4,16 4,23 4,43

%infaisabilité 28,5% 25% 39% 31,5% 35,5% 26,5% 31% 33,5% 36% 51% 69%

7 Unités

Moyenne POS 2,08 5,51 5,60 5,629 5,51 5,51 5,65 5,59 5,72 6,04 6,24

%infaisabilité 39% 46,5% 52% 37,5% 42% 46% 49,5% 43,5% 62,5% 65,5% 83%

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,22 2,84 2,84 2,81 2,83 2,87 2,80 2,88 2,89 2,90 2,98

%infaisabilité 18,5% 22% 20,5% 20,5% 19% 25,5% 27% 24,5% 26% 35,5% 58,5%

6 Unités

Moyenne POS 1,55 3,17 3,17 3,12 3,21 3,20 3,20 3,22 3,29 3,33 3,45

%infaisabilité 33% 35% 38,5% 39,5% 27,5% 31% 36,5% 33,5% 40% 52% 73,5%

7 Unités

Moyenne POS 2,60 4,72 4,72 4,70 4,73 4,75 4,75 4,75 4,81 4,88 5,17

%infaisabilité 35% 42% 41% 45,5% 44% 47,5% 41% 49,5% 63,5% 72,5% 86,5%

Tableau 5-Résultats obtenus avec la versionl de l'algorithme

80

Le premier constat que nous pouvons faire par rapport à ces résultats concerne la

probabilité de succès qui augmente en fonction du nombre d'unités de recherche utilisées. Plus

on utilise d'unités de recherche plus la qualité des solutions s'améliore et plus le choix entre les

solutions proposées se limite.

On note également que les taux d'infaisabilité varient. Le déploiement d'un nombre

supérieur d'unités implique l'augmentation du nombre de rectangles à balayer. Ceci accroît les

chances de trouver l'objet perdu, mais également la probabilité de superposition de ces

rectangles. Cela explique l'effet de l'augmentation du nombre d'unités de recherche sur la

probabilité de succès et le taux d'infaisabilité. L'augmentation de ce dernier est due au fait que

le nombre de solutions réalisables diminue au fur et à mesure que le nombre d'unités

augmente.

Nous avons utilisé, dans l'étude de l'évolution de la probabilité de succès en fonction de

P, la figure suivante qui illustre les résultats obtenus avec la grille « Point Grid » sous la forme de

trois courbes. Ces dernières correspondent aux trois différents scénarios qu'on s'est fixés pour

chaque grille.

25 -25 -

20 -20 -

15 - pour 5 unités 15 - pour 5 unités POS

m -— — — Moyenne POS

pour 6 unités Moyenne POS

c . pour 7 unités

0 J i 0 J

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

i

Figure 29-La variation du POS moyen en fonction de P sur Point Grid (versionl)

81

Cette figure confirme l'effet de l'augmentation du nombre d'unités de recherche sur la

probabilité de succès. Plus on utilise un nombre supérieur d'unités de recherche, plus la

probabilité de succès augmente. Cette augmentation est nettement visible si nous comparons le

niveau de POS que les courbes peuvent atteindre. On passe de 12,6 pour une opération de

recherche effectuée avec 6 unités à 20,6 pour une effectuée sous les mêmes conditions, mais

avec 7 unités. Malgré cette différence de niveau, les trois courbes de la figure 29 suivent

presque la même allure. La probabilité de succès augmente au fur et à mesure que P augmente.

Cette observation suit exactement le comportement de la fonction objectif.

Comme nous l'avons déjà précisé, le calcul de cette fonction fait intervenir deux

facteurs. Le premier s'intéresse à la probabilité de succès de la solution. Le deuxième varie en

fonction du nombre de rectangles superposables qu'une solution peut regrouper. En analysant

la fonction objectif, nous nous sommes rendu compte qu'au fur et à mesure que p augmente

nous accordons plus d'importance au facteur succès et nous nous intéressons moins au facteur

d'intersection d'une solution. Les solutions qu'on retient avec des valeurs faibles de P tendent

plus à satisfaire la contrainte de l'intersection qu'à avoir une importante probabilité de succès.

En augmentant P, cette tendance s'inverse progressivement. Quoiqu'elles comptent parmi elles

de moins en moins de solutions réalisables, ces solutions obtenues pour les grandes valeurs de P

possèdent les meilleures probabilités de succès. C'est ce qui explique l'allure ascendante des

courbes de probabilités de succès illustrées dans la figure 29.

Nous précisons ici que le comportement de courbes illustrant l'évolution du POS en

fonction de p est le même pour tous les scénarios et toutes les grilles. C'est la raison pour

laquelle nous nous sommes limités à une seule grille dans notre analyse.

82

Chapitre 4. Manipulation des contraintes

Nous présentons dans cette section la deuxième catégorie d'approches de résolution

que nous étudions. Le point commun entre les différentes approches est qu'elles visent toutes

l'obtention de solutions de qualité meilleure. Le but des modifications apportées dans cette

catégorie est de diminuer le taux d'infaisabilité et d'essayer de garder un bon niveau de

probabilités de succès. Nous comptons, en mettant en oeuvre ces approches, optimiser les

probabilités de succès des solutions tout en réduisant le nombre de solutions infaisables. Pour

atteindre cet objectif, nous intervenons sur deux éléments de l'algorithme, soit le mécanisme de

création de la population initiale et l'opérateur de mutation. Ces éléments affectent

directement les populations de toutes les générations ainsi que les individus qui les constituent.

On rappelle ici que les contraintes à satisfaire sont les suivantes :

Chaque rectangle (gène) d'une solution (génome) doit être affecté à une unité de

recherche différente ;

II ne doit pas y avoir d'intersection entre les rectangles d'une même solution.

Cinq modèles ont été mis en place pour les approches avec manipulation de contraintes.

Chacun de ces modèles correspond à une version implémentée de l'algorithme. La différence

entre eux se trouve principalement au niveau de l'opérateur de mutation ou de la fonction

assurant la création de la population initiale. Au lieu de présenter chacun des modèles, nous

préférons détailler les modifications qui peuvent être apportées sur ces deux éléments de

l'algorithme. Ensuite, nous précisons pour chacune des versions de l'algorithme les éléments sur

lesquels elles se basent ainsi que leurs modes de fonctionnement.

83

4.1 Mécanisme de création de la population initiale

En partant de ce que nous avons trouvé dans la littérature, nous n'avons pu envisager

qu'une seule amélioration de cet élément. Cette amélioration consiste à modifier la fonction

d'initialisation d'une manière qui nous permettra de partir avec une population initiale

contenant le maximum possible d'individus réalisables et ceci dans le but de préserver la

faisabilité des solutions. Cette fonction part du même principe que celle présentée dans la

section 3.2.1.2. Elle s'assure que chaque rectangle est balayé par une unité différente de celles

qui balayent le reste des rectangles du génome. Sauf que dans cette version, elle prend en

considération la superposition des rectangles. Tout génome contenant au moins deux rectangles

qui se superposent sera retiré de la population initiale. Ce fait de bâtir notre espace de

recherche à partir d'une population d'individus totalement réalisable ne peut qu'augmenter nos

chances d'avoir une solution qui puisse satisfaire toutes les contraintes à respecter.

Le fonctionnement de la nouvelle fonction d'initialisation est détaillé dans l'algorithme suivant :

Algorithme 6 Fonction d'initialisation avec préservation de faisabilité

Fonction initialisation(Génome)

Début

Définir un vecteur V pour contenir les rectangles constituant le génome en cours de construction

For (i = 0 à i < nombre d'unités de recherche ; i++)

If (1 = 0)

Choisir aléatoirement un rectangle 'Premier_ Rec' dont le numéro de l'unité de recherche

égal à i

6 : Ajouter 'Premier_Rec' à V

7 : //Insertion du premier rectangle. S'assurer que le vecteur contient au moins un rectangle

8 : Else

9 : bool=false

10 : //Définir une variable booléenne qu'on utilisera pour déterminer s'il y a superposition

entre les rectangles d'un même génome//

11: Do

84

12: Choisir aléatoirement un rectangle Rec dont le numéro de l'unité de recherche égal à i

13: Forj = 0 à j < taille actuelle de V

14: If Superpose (Rec, Vj)

15: //Rec se superpose avec au moins un des rectangles du vecteur V

16: bool=vrai

17: End If

18: End For

19: While (bool=vrai)

20: //S'assurer de la non-superposition des rectangles d'un même génome

21: Ajouter Rec à V

22: //L'ajout du reste des rectangles au vecteur V

23: End If

24: End For

25: For (i = 0 à i < taille de V ; i++)

26: Insert (génome, V[i])

27: End For

28: //L'insertion des rectangles constituant le vecteur dans le génome en cours de construction

29: Insert (population, génome)

30: //Insertion du génome dans la population

31: Fin

Figure 30-Fonction de création de la population initiale avec préservation de faisabilité

4.2 Opérateur de mutation

Comme c'est le cas pour l'élément précédent, notre intervention concerne

principalement la faisabilité des solutions. Dans ce sens, nous avons défini deux nouveaux

opérateurs de mutation qui ne donnent naissance qu'à des individus respectant la totalité des

contraintes imposées. Ces opérateurs, nommés opérateur de mutation avec étirement et

opérateur de mutation avec préservation de faisabilité, sont détaillés respectivement dans la

section 4.2.1 et 4.2.2.

85

Avec le deuxième type d'opérateur de mutation, notre intervention s'étend pour

garantir une amélioration de la probabilité du succès des solutions. II suffit de remplacer le

rectangle à supprimer par un rectangle dont la probabilité de succès est supérieure à celle du

premier à condition que cela ne viole aucune des contraintes imposées. Cette alternative est

expliquée davantage sous la section 4.2.3.

4.2.1 Opérateur de mutation avec étirement

Contrairement au premier opérateur de mutation présenté dans la première version de

l'algorithme, cet opérateur ne supprime pas le plus faible rectangle pour le remplacer par un

deuxième rectangle. II garde les mêmes rectangles du génome et essaie de modifier les valeurs

que les éléments, identifiant ces rectangles, peuvent prendre. On note, parmi ces éléments, les

coordonnées du coin inférieur gauche, le nombre de lignes et le nombre de colonnes.

En partant de cela, nous précisons que cet opérateur n'utilise pas la fonction objectif

pour déterminer lequel des rectangles il faut remplacer. Et puisqu'il est conçu pour préserver la

faisabilité des solutions, il n'intervient que pour muter un individu, violant une ou plusieurs

contraintes, afin d'obtenir une solution réalisable au problème. Ainsi, cet opérateur n'est utilisé

que s'il y a intersection entre au moins deux rectangles du même génome. II essaie alors de

l'éliminer en étirant l'un de ces deux rectangles. Nous détaillons dans la figure suivante les

différents cas d'intersection que nous pouvons rencontrer.

1 ' ' V . - — A V .. .1 T - ~ — ~ -

m d i T d i

1 r- n \i\7l d , —> " 2 IM fàfl

133 w» m ■' ^ ■

! j a> i i i .

-L \~

>: y z i i i

1e r cas 2 cas

86

k | a 1 i / j V T T r i

| « i

1$ I* l A . 1$ j 1 - z

»i rtt î« i

a —r a,

1 ) ;

3 cas .ème 4 cas

Figure 31-Cas d'intersections de rectangles

Nous désignons par RI et R2 les deux rectangles illustrés dans chacun des cas

d'intersection de la figure 31. Lorsque ces cas surviennent, notre opérateur fera appel à une

fonction d'étirement qui, selon l'emplacement d'un rectangle par rapport à l'autre, modifie les

propriétés du premier rectangle pour qu'il n'y ait plus d'intersection. Dans ce qui suit, nous

traitons un par un les quatre cas présentés dans la figure 31. Nous présentons pour chaque cas

les positions de départ des deux rectangles ainsi que les modifications que nous pouvons

apporter afin d'éviter que ces rectangles se superposent. II est important de préciser que, pour

déterminer la position d'un rectangle, nous nous référons aux coordonnées de son coin inférieur

gauche. Pour le premier rectangle, on nomme le coin inférieur gauche ai et le coin supérieur

droit di. Pour le deuxième rectangle, on nomme le coin inférieur gauche a2 et le coin supérieur

droit d2.

Dans le premier cas d'intersection (voir Figure 31), le coin inférieur gauche du premier

rectangle se trouve à l'intérieur du deuxième rectangle. Ceci est équivalant au fait que l'abscisse

de ax est comprise entre l'abscisse de a2 et de d2. Dans ce cas, deux possibilités d'étirement sont

envisageables pour éliminer l'intersection entre ces deux rectangles :

Déplacer at de manière à ce que son abscisse soit supérieure à celle de d2 et garder les

mêmes coordonnées pour dx. Cette méthode est applicable dans le cas où la différence

entre l'abscisse de di et l'abscisse de d2 serait supérieure ou égale à deux cellules.

87

Déplacer ai de manière à ce que son ordonnée soit supérieure à celle de d2 et garder les

mêmes coordonnées pour dx. Ceci n'est valable que si la différence entre l'ordonnée de

di et l'ordonnée de d2 est supérieure ou égale à deux cellules.

Le résultat de l'application de ces deux méthodes est illustré dans la figure suivante :

. . 11

i / < t °M i u 1 U l

F ' S-<* 2 IXi ll à2

•M \i 1 ■ t \tà A

1 2 h

) >

l6re résolution 2

ime résolution

Figure 32-Résolutions du premier cas d'intersection

Nous supposons dans le deuxième cas d'intersection que l'abscisse de ai est inférieure à

celle de a2 et son ordonnée est aussi inférieure à celle de a2. La méthode utilisée, pour éliminer

l'intersection entre les deux rectangles, consiste à garder les mêmes coordonnées pour ax et

rétrécir le premier rectangle de manière à ce que l'emplacement de di ne cause plus

d'intersection. Pour atteindre cet objectif, il faut agir sur le nombre de lignes et de colonnes du

premier rectangle et selon les modalités suivantes :

Si la différence A entre l'abscisse de ai et l'abscisse de a2 est supérieure ou égale

à deux cellules, le nombre de colonnes correspondra à A-l .

Si la différence A entre l'ordonnée de at et l'ordonnée de a2 est supérieure ou

égale à deux cellules, le nombre de lignes sera égal à A-l .

Nous précisons ici que la soustraction appliquée à la différence A est effectuée dans le

but de garantir un minimum d'espacement entre les deux rectangles. La figure 33 illustre le

résultat de l'application de ces deux dernières méthodes.

88

' i .

' i ,

1 i H ' / a 1

» m r j 1 w H

"—

il A m 1 « J i

"—

' 2

"—

a? «

"— "—

m "—

Si i )

"— "— "— J ) "— "—

lère résolution 2 me résolution

Figure 33-Résolutions du deuxième cas d'intersection

Dans le troisième cas d'intersection, l'ordonnée de ai est comprise entre l'ordonnée de

a2 et d2. Si nous décidons de conserver ses coordonnées, il faudrait que nous agissions sur soit le

nombre de lignes ou le nombre de colonnes du premier rectangle. Or, nous remarquons aussi

que l'abscisse de di est comprise entre l'abscisse de a2 et d2. Dans ce cas, la diminution du

nombre de lignes s'avère inutile. La solution à envisager consiste à pousser le point supérieur

droit vers la gauche de façon à ce que son abscisse soit inférieure à celui de a2. Ceci se résume à

fixer le nombre de colonnes du premier rectangle à A-l tout en sachant que A égale à la

différence d'abscisses de ai et a2. Le résultat de cette manipulation est illustré dans la figure 34.

Dans le quatrième cas, le premier rectangle est placé en dessous du deuxième

rectangle : l'abscisse de ai est inférieure à celui de a2, son ordonnée est comprise entre

l'ordonnée de a2 et celui de d2. Pour éliminer l'intersection, il faut réduire le nombre de lignes

du premier rectangle (figure 34).

89

| , .

i i

1 i d i i { A i 1

| d i l a i \171

ffô -h — »i

- -L m ld i _

»2 - | I a i ■ >

A i A

Résolution 3 me cas Résolution 4emc cas

Figure 34-Résolution du troisième et quatrième cas d'intersection

4.2.2 Opérateur de mutation avec préservation de faisabilité

Cet opérateur de mutation part du même principe que celui présenté dans la première

version de l'algorithme : supprimer, dans une première étape, le plus faible rectangle pour le

remplacer, dans une deuxième étape, par un autre dans le but d'avoir une meilleure solution. La

première étape s'effectue de la même manière puisque le rectangle à supprimer est celui qui a

la plus faible fitness. C'est à la deuxième étape qu'on signale une différence entre les deux

opérateurs. Le choix du rectangle à insérer n'est plus effectué aléatoirement comme pour la

première version de l'algorithme. II n'est finalisé que si le rectangle, choisi pour être inséré, ne

viole aucune des contraintes imposées. II doit être balayé par la même unité de recherche qui

balayait le rectangle supprimé et ne doit se superposer avec aucun des rectangles constituant le

génome dans lequel nous allons l'insérer.

Algorithme? Opérateur de mutation avec préservation de faisabilité

1: Début

2: Extraire le génome dans un vecteur de rectangles

3 f = max (fitness)

/ /Définir un réel pour la comparaison entre les fitness des rectangles du génome

4: For (i=0 ; knombre de rectangles du génome ; i++)

5: Appliquer la fonction de fitness sur les rectangles du génome

//Évaluer es rectangles

90

6: If (fitness (rectangle^ < f)

7: Then f = fitness (rectangle,)

8: X = i

//Mémoriser le numéro d'unité de recherche du plus faible rectangle

9: End If

10 End For

11 Supprimer le rectangle d'indice X

12 bool=false

//Définir une variable booléenne qu'on utilisera pour déterminer s'il y a superposition

13 Do

14 Do

15 num_rect = random (0, nombre total de rectangles)

16 //Choisir aléatoirement un numéro de rectangle

17 Rectjnsert = vecteur_de_rectangles[num_rect]

//Extraire le rectangle correspondant au numéro choisi aléatoirement

18 Until (Rectjnsert.numéro_unité = X)

//Refaire le traitement jusqu'à ce que le numéro de l'unité du rectangle choisi soit

égal à X//

19 For (j = 0; j < taille du vecteur ; j++)

20 If (Rectjnsert se supperpose avec au moins un des rectangles du vecteur)

21. bool=vrai

22: End If

23: End For

24: While (bool=vrai)

//S'assurer qu'il n'y a pas de superposition entre les rectangles d'un même génome

25: Insérer Rectjnsert à l'indice X

26: Fin

Figure 35 — Fonction de mutation avec préservation de faisabilité

91

4.2.3 Opérateurs de mutation avec préservation de faisabilité garantissant une amélioration de la probabilité de succès

Nous proposons un opérateur de mutation qui ne se soucierait pas uniquement de la

faisabilité des individus, mais qui doit s'assurer aussi que l'individu après mutation ait une

meilleure probabilité de succès. Pour y arriver, nous avons conçu deux opérateurs fortement

semblables à celui que nous venons de présenter.

4.2.3.1 Opérateur 1

Cet opérateur ne se contente pas de vérifier s'il y a intersection entre deux rectangles, il

s'assure que le rectangle à insérer ait une meilleure probabilité de succès. Mais le choix reste

aléatoire, il peut intégrer le meilleur élément ou n'importe quel autre tant qu'il a une probabilité

de succès supérieure à celle du rectangle supprimé. L'algorithme est présenté dans la figure

suivante.

Algorithmes Opérateur de mutation 1

1: Début

2: Extraire le génome dans un vecteur de rectangles

3 : f = max (Fitness)

//Définir un réel pour la comparaison entre les//'tness des rectangles du génome

4: For (i=0 ; knombre de rectangles du génome ; i++)

5: Appliquer la fonction de fitness sur les rectangles du génome

//Évaluer les rectangles

6: If (fitness (rectangle;) < f)

7: Then f= fitness (rectangle;)

8: X = i

//Mémoriser le numéro d'unité de recherche du plus faible rectangle

End If 9:

10 End For

92

11: P0S1= rectanglex.POS

//Sauvegarder la probabilité de succès du plus faible rectangle

12: Supprimer le rectangle d'indice X

13: bool=false

//Définir une variable booléenne qu'on utilisera pour déterminer s'il y a superposition

14: Do

15: Do

16: num_rect = random (0, nombre total de rectangles)

//Choisir aléatoirement un numéro de rectangle

17: Rectjnsert = vecteur_de_rectangles[num_rect]

//Extraire le rectangle correspondant au numéro choisi aléatoirement

18: Until (Rectjnsert.numéro_unité = X)

For (j = 0; j < taille du vecteur ; j++)

19: If (Rectjnsert se superpose avec au moins un des rectangles du vecteur)

20: bool=vrai

21: End If

22: End For

23: POS2= RectJnsert.POS

//Sauvegarder la probabilité de succès du rectangle à insérer

24: While (bool=vrai et POS2<POSl)

//S'assurer que les rectangles d'un même génome ne se superposent pas et que la POS du

rectangle inséré est meilleure de celle du rectangle supprimé//

25: Insérer Rectjnsert

26: Fin

Figure 36 — Fonction de mutation avec préservation de faisabilité et amélioration de probabilité 1

4.2.3.2 Opérateur 2

Avec cet opérateur, nous imposons plus de restrictions dans le choix du rectangle à

insérer. Nous privilégions toujours les rectangles ayant les meilleures probabilités de succès tout

en respectant les critères à satisfaire. Pour cela, et au lieu de procéder à un choix aléatoire de

rectangle, nous avons choisi de procéder ainsi : après avoir sauvegardé le numéro de l'unité qui

balaie le rectangle supprimé, nous rassemblons les rectangles de la même unité dans une liste

qu'on trie en fonction de la probabilité de succès. Pour choisir le rectangle à insérer, nous nous

93

plaçons sur le premier rectangle de la liste triée. Ce dernier doit satisfaire toutes les contraintes

pour que l'insertion soit effectuée. Dans le cas contraire, nous soumettrons le rectangle suivant

aux tests de faisabilité et ceci jusqu'à l'obtention du bon élément. De cette manière, il sera plus

probable qu'on insère le meilleur rectangle parmi ceux dont on dispose.

Algorithme9 Opérateur de mutation 2

1: Début

2: Extraire le génome dans un vecteur de rectangles

3 : f = max(Frtness)

//Définir un réel pour la comparaison entre les//tness des rectangles du génome

4: For i=0 ; knombre de rectangles du génome

5: Appliquer la fonction de fitness sur les rectangles du génome

//Évaluer les rectangles

6: If (fitness (rectangle,) <f)

7: Then f = fitness (rectangle,)

10: X = i

//Mémoriser le numéro d'unité de recherche du plus faible rectangle

12

13

14

15

End If

End For

Supprimer le rectangle d'indice X

j=0

//Définir l'indice j pour créer une liste de rectangles

16: For ail rectangles

17: if (rectangle est balayé par X)

18: Then Liste[j] = rectangle

19: j=j+l

20: End If

21: End For

//Rassembler dans une liste les rectangles balayés par l'unité qui couvrait le rectangle supprimé

22: Trier la liste de rectangles

23: bool=false

//Définir une variable booléenne qu'on utilisera pour déterminer s'il y a superposition

24: i=0

94

//Défi lir un indice i pour parcourir la liste

25: Do

26: RectJnsert=Liste[i]

//Commencer par le premier rectangle de la liste. Celui qui a forcément la meilleure POS

27: i=i+l

//Incrémenter le compteur dans le cas où ce rectangle ne satisfait pas les contraintes

28: For (j = 0; j < taille du vecteur ; j++)

29: If (Rectjnsert se supperpose avec au moins un des rectangles du vecteur)

30: bool=vrai

31: End If

32: End For

33: While (bool=vrai)

//S'assurer que les rectangles d'un même génome ne se superposent pas

34: Insérer Rectjnsert

35: Fin

Figure 37 — Fonction de mutation avec préservation de faisabilité et amélioration de probabilité 2

4.3 Présentation des versions du modèle implémentées

À partir des opérateurs définis dans les sections précédentes, nous sommes en mesure

de proposer différents modèles de résolution pour notre problème d'allocation d'unités de

recherche. Chaque modèle correspond à une version de l'algorithme implémenté. D'une version

à l'autre, nous allons nous concentrer seulement sur les éléments qui ont été modifiés et seules

les différences entre les versions seront mentionnées.

Version 2 du modèle :

On modifie pour cette version la manière avec laquelle la mutation est effectuée. Au lieu

de s'exécuter aléatoirement, elle va se baser sur le principe de retirement. Cet opérateur a été

présenté dans la section 4.2.1.

95

Version 3 du modèle :

Pour cette version, la seule modification apportée concerne l'opérateur de mutation qui

se soucie uniquement de la faisabilité des individus sur lesquels il va agir. Cet opérateur a été

présenté dans la section 4.2.2.

Version 4 du modèle :

On garde pour cette version le même opérateur utilisé dans la version3 de l'algorithme

et nous allons agir seulement sur le mécanisme de création de la population initiale. L'idée de

base consiste à s'assurer que les individus intégrés satisferont la totalité des contraintes

imposées. Ce mécanisme a été défini dans la section 4.1.

Version 5 du modèle :

La différence entre cette version et celle qui la précède se trouve au niveau de

l'opérateur de mutation. Ce dernier assure, en plus de la faisabilité des individus qu'il manipule,

une amélioration de la probabilité de succès. Les détails concernant le fonctionnement de cet

opérateur ont été donnés dans la section 4.2.3.1.

Version 6 du modèle :

Cette version est une amélioration de la version 5. Cette amélioration touche

principalement l'opérateur de mutation. Le nouvel opérateur mis en place part du même

principe que de celui utilisé dans la version précédente. La seule différence se résume dans le

fait que l'amélioration de la probabilité de succès est assurée autrement. Le mode de

fonctionnement de cet opérateur a été détaillé dans la section 4.2.3.2.

96

4.4 Présentation et analyse des résultats

Nous présentons dans cette section les résultats expérimentaux correspondant aux cinq

versions de l'algorithme que nous venons de proposer. II s'agit de versions qui visent toutes

l'amélioration de la qualité de solution et cela en tenant compte des contraintes à satisfaire.

Le but de ces expérimentations consiste à déterminer à quel point la satisfaction de

contraintes dans un algorithme génétique peut contribuer à améliorer la qualité des solutions

obtenues. Comme nous l'avons déjà précisé, la qualité d'une solution est déterminée en

fonction du taux d'infaisabilité et de la probabilité de succès. Nous avons remarqué dans les

premières expérimentations que l'obtention des meilleures probabilités de succès coïncide avec

les plus importants taux d'infaisabilité. En adoptant des opérateurs qui prennent en compte les

contraintes, nous espérons augmenter la proportion de solutions réalisables tout en préservant

autant que possible l'atteinte de solution optimum.

Pour mener nos expérimentations, nous gardons les mêmes modalités que celles fixées

pour générer les résultats de la première version au chapitre 3. Ainsi, le taux d'infaisabilité

correspond au nombre de solutions infaisables parmi les solutions générées durant les 200

essais. La probabilité de succès, quant à elle, est égale à la moyenne des probabilités de succès

des 200 solutions obtenues. On rappelle également que nous gardons pour ces cinq versions la

même fonction objectif utilisée avec la première version de l'algorithme. Ce qui veut dire que

nous allons aussi faire varier le paramètre P pour ces tentatives de résolution, et cela, afin de

suivre l'évolution de la probabilité de succès en fonction de cette variation. Ceci implique aussi

que le nombre d'essais choisi sera gardé pour chaque valeur de P . II nous est imposé de garder

les mêmes valeurs des paramètres de dimensionnement et de ceux appliqués aux deux

opérateurs de reproduction pour que la comparaison entre les versions de l'algorithme soit

effectuée sur la même base. Nous travaillons aussi sur les mêmes grilles tout en gardant les

mêmes scénarios d'allocation d'effort.

97

Nous présentons dans ce qui suit les résultats obtenus pour chacune des cinq versions

que nous avons définies.

4.4.1 Version 2 du modèle

Cette version est marquée par l'utilisation d'un opérateur de mutation se basant sur le

principe d'étirement pour corriger l'infaisabilité des individus sur lesquels il est appliqué. Nous

présentons dans le tableau suivant le mode de fonctionnement des éléments sur lesquels cette

version se base.

Élément Mode de fonctionnement

Création de la population initiale Choix aléatoire des individus à ajouter à la population

Mutation Mutation avec étirement

Croisement Choix aléatoire du point de croisement

Fonction objectif P x (Succès,) + (1 - P) x (1 - interj)

Tableau 6-Tableau récapitulatif de la version 2 du modèle

Les résultats obtenus avec cette version sont présentés dans les tableaux suivants

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,47 9,02 8,97 9,01 9,06 8,95 9,15 9,42 9,83 10,02 11,08

%infaisabilité 15,5% 9,5% 11,6% 15,3% 14,7% 13,9% 12,8% 14,8% 20% 25,6% 43,1%

6 Unités

Moyenne POS 1,77 9,51 9,42 9,34 9,54 9,60 9,67 9,98 10,55 11,10 11,70

%infaisabilité 25,5% 14,2% 17,7% 13,5% 15,1% 20,8% 20,8% 22% 21,9% 35,9% 58,2%

98

7 Unités

Moyenne POS 3,15 12,62 12,33 12,26 12,31 12,32 12,56 12,82 13,57 14,16 16,87

%infaisabilité 41,4% 26,3% 24,6% 41,2% 23,1% 27,2% 31,1% 35,4% 41,1% 54,4% 76,2%

Grille : CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 0,97 2,97 2,95 2,94 2,93 2,96 2,97 3,05 3,03 3,26 3,41

%infaisabilité 18,1% 11,8% 11,6% 11,7% 10,2% 8,6% 9,2% 5,2% 8,5% 14,2% 51,5%

6 Unités

Moyenne POS 1,25 3,22 3,24 3,19 3,25 3,22 3,20 3,30 3,40 3,53 3,77

% i n f a i s a b i li t é 31,1% 14,1% 14,2% 9,2% 12,2% 17% 18,9% 19,7% 17,7% 29,4% 69%

7 Unités

Moyenne POS 2,00 4,45 4,46 4,45 4,50 4,47 4,49 4,53 4,71 4,90 5,32

%infaisabilité 46,2% 25,6% 21,9% 25,4% 21,8% 17,8% 20,6% 25,3% 26,8% 42,7% 86,6%

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,23 2,96 2,95 2,94 2,93 2,96 2,98 3,04 3,12 3,28 3,45

%infaisabilité 23% 9,5% 14,5% 12,5% 11,5% 10,5% 8,5% 7,5% 16,4% 23% 62,2%

6 Unités

Moyenne POS 1,54 3,28 3,27 3,29 3,29 3,31 3,32 3,35 3,51 3,59 3,84

%infaisabilité 27,5% 16,7% 16,3% 12,2% 16,1% 14,1% 17,8% 12,6% 16,4% 30,5% 85,5%

7 Unités

Moyenne POS 2,65 4,66 4,64 4,67 4,68 4,64 4,66 4,76 4,91 5,14 5,61

%infaisabilité 38,8% 30,5% 26,4% 29,2% 26,7% 18,4% 24,8% 32,5% 19,6% 45,7% 93,1%

Tableau 7-Résultats obtenus avec la version2 de l'algorithme

99

À partir de ces résultats, nous remarquons que l'augmentation de P ou du nombre

d'unités de recherche entraîne, comme pour la première version de l'algorithme, une hausse du

côté des probabilités de succès et des taux d'infaisabilité. Ceci paraît totalement logique

puisqu'on a gardé la même fonction objectif.

Si nous comparons les résultats générés à ceux obtenus avec la première version, nous

remarquons une baisse de niveau dans les taux d'infaisabilités et dans les probabilités de succès.

Prenons pour exemple la deuxième grille (CSAD Grid). Si nous nous limitons au premier scénario

(5 unités de recherche), nous remarquons, pour une valeur de P égale à 0.5, une baisse de

10,88% du côté du taux d'infaisabilité (de 19,50% à 8,62%) et de 15% du côté de la probabilité

de succès (de 3,51 à 2,96). Avec la même grille et le même scénario, nous signalons, pour une

valeur de p égale à 1, une baisse de 4% dans le taux d'infaisabilité (de 55,5% à 51,5%) et de 8%

dans la probabilité de succès (de 3,75 à 3,41).

Ces observations nous permettent de conclure que le remplacement d'un opérateur de

mutation aléatoire par un opérateur de mutation avec étirement peut être bénéfique, car il

permet d'obtenir plus de solutions réalisables. Du côté de la performance, ces dernières sont

moins convaincantes si nous les comparons à ceux obtenus avec la première version. On prend

par exemple la première grille (Point Grid). Dans une opération de recherche à 7 unités

(troisième scénario) et pour une valeur de P égale à 1, nous remarquons une baisse de 18% dans

la probabilité de succès (de 20,69 à 16,87). Pour cette raison, nous doutons de l'efficacité de ce

nouvel opérateur.

4.4.2 Version 3 du modèle

Cette version se distingue par l'utilisation d'un opérateur de mutation visant à préserver

la faisabilité des individus. Le tableau suivant illustre les éléments sur lesquels cette version se

base ainsi que leurs modes de fonctionnement.

100

Élément Mode de fonctionnement

Création de la population initiale Choix aléatoire des individus à ajouter à la population

Mutation Mutation avec préservation de faisabilité

Croisement Choix aléatoire du point de croisement

Fonction objectif P x (SuccèSj) + (1 - P) x (1 - interO

Tableau 8-Tableau récapitulatif de la version 3 du modèle

Les tableaux suivants renferment les résultats des expérimentations menées avec cette version.

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,33 9,86 10,11 10,37 10,33 10,52 10,14 10,41 10,85 10,62 10,47

%infaisabilité 10,5% 17,5% 16% 11% 14% 15% 22% 14% 19% 27% 42,5%

6 Unités

Moyenne POS 1,80 10,93 10,47 10,29 11,04 10,82 11,06 10,82 11,27 11,18 11,62

%infaisabilité 27% 22,5% 23,5% 23% 25,5% 30,5% 33% 24% 37% 40% 55,5%

7 Unités

Moyenne POS 2,80 16,49 15,82 16,12 16,21 15,84 16,68 16,57 16,43 17,64 17,95

%infaisabilité 43% 32,5% 40,5% 38% 39,5% 38,5% 34,5% 37,5% 48% 55% 73%

Grille : CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,02 3,20 3,16 3,12 3,15 3,15 3,20 3,24 3,23 3,25 3,25

%infaisabilité 18% 15% 16% 16,5% 11% 15% 17% 16% 20% 22,5% 43,5%

101

6 Unités

Moyenne POS 1,19 3,44 3,50 3,42 3,46 3,46 3,53 3,53 3,56 3,68 3,68

%infaisabilité 26% 20,5% 24,5% 23,5% 22% 18% 19,5% 26,5% 24% 50% 59%

7 Unités

Moyenne POS 2,17 5,23 5,11 5,07 5,17 5,23 5,22 5,29 5,19 5,59 5,49

%infaisabilité 39,5% 29,5% 34% 31% 35,5% 39,5% 34,5% 41% 44,5% 51,5% 71%

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,22 2,67 2,67 2,69 2,67 2,71 2,70 2,70 2,73 2,78 2,77

%infaisabilité 18% 22,5% 22,5% 18,5% 22% 20% 27% 22,5% 26,5% 36% 58%

6 Unités

Moyenne POS 1,51 3,04 3,02 3,03 2,98 3,03 3,01 3,05 3,09 3,09 3,20

%infaisabilité 26,5% 30% 31,5% 33,5% 28% 37,5% 30% 30% 40,5% 49% 70,5%

7 Unités

Moyenne POS 2,51 4,46 4,55 4,56 4,59 4,56 4,64 4,53 4,69 4,72 4,85

%infaisabilité 35,5% 39% 42,5% 42,5% 41,5% 42,5% 45,5% 50% 56% 71% 83%

Tableau 9-Résultats obtenus avec la version3 de l'algorithme

En partant des résultats présentés au tableau 9, nous pouvons affirmer que l'utilisation

de ce nouvel opérateur permet l'obtention de meilleures solutions que ce soit sur le plan de la

performance ou sur le plan de la faisabilité. Nous ajoutons à cela le fait que sa mise en place n'a

pas affecté la variation de la probabilité de succès et du taux d'infaisabilité en fonction de P et

du nombre d'unités de recherche. Ce qui demeure une indication du bon fonctionnement de

notre algorithme.

102

Si nous comparons ces résultats à ceux obtenus avec la version précédente, nous

remarquons l'atteinte, sous la plupart des scénarios, des niveaux supérieurs de probabilité de

succès. Nous voyons aussi que les chances d'obtenir une solution réalisable sont meilleures

même si la différence entre les taux d'infaisabilité des deux versions n'est pas importante. Pour

appuyer ces observations par un exemple, on suppose qu'on est sur la première grille (Point

Grid) et qu'on dispose de 7 unités de recherche (3ème scénario). Au sujet de la probabilité de

succès, nous observons une hausse de 6 % (de 16,8 à 17,9). Le taux d'infaisabilité, quant à lui, a

diminué de 3,24%.

Malgré sa contribution minime dans l'amélioration de la qualité des résultats, cet

opérateur de mutation est à garder du moment qu'il nous permet d'obtenir de meilleures

solutions.

4.4.3 Version 4 du modèle

La différence entre cette version et celle qui la précède se trouve au niveau de la

création de la population initiale. Cette étape, contrairement aux versions précédentes, permet

de définir une population ne renfermant que des individus satisfaisant la totalité de contraintes.

Les éléments sur lesquels se base cette version sont détaillés dans le tableau suivant.

Élément Mode de fonctionnement

Création de la population initiale Création de la population initiale avec préservation de faisabilité

Mutation Mutation avec préservation de faisabilité

Croisement Choix aléatoire du point de croisement

Fonction objectif p x (SuccèSj) + (1 - P) x (1 - interj)

Tableau 10-Tableau récapitulatif de la version 4 du modèle

Nous présentons sous ces tableaux les résultats obtenus avec cette version sous les différents

scénarios et grilles fixés.

103

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,39 10,57 10,54 10,48 10,06 10,53 10,53 10,48 10,34 10,54 11,06

%infaisabilité 10% 9% 9% 4% 6,5% 13% 9,5% 9,5% 16% 19,5% 18,5%

6 Unités

Moyenne POS 1,60 11,38 11,38 11,34 11,48 11,16 11,28 11,39 11,37 11,65 11,86

%infaisabilité 13,5% 12% 11,5% 13% 12% 11% 10,5% 13,5% 12,5% 23,5% 31,5%

7 Unités

Moyenne POS 2,98 16,93 17,41 17,41 17,10 17,47 17,40 17,09 17,93 18,31 18,00

%infaisabilité 15% 12,5% 16% 17% 17,5% 12% 16,5% 17% 22,5% 22,5% 38,5%

Grille : CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 0,95 3,23 3,21 3,21 3,23 3,18 3,2 3,24 3,28 3,21 3,25

%infaisabilité 8% 8% 8% 8,5% 10,5% 10,5% 10,5% 7% 15,5% 18% 22%

6 Unités

Moyenne POS 1,28 3,58 3,60 3,56 3,57 3,61 3,51 3,59 3,64 3,68 3,66

%infaisabilité 11% 8,5% 10% 9,5% 12,5% 9,5% 10,5% 8% 11,5% 17,5% 30,5%

7 Unités

Moyenne POS 2,10 5,32 5,40 5,38 5,40 5,35 5,38 5,40 5,41 5,41 5,48

%infaisabilité 15% 10,5% 12,5% 12% 12% 15,5% 12,5% 14,5% 15% 25,5% 39,5%

104

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,24 2,75 2,74 2,73 2,73 2,72 2,74 2,73 2,73 2,74 2,77

%infaisabilité 7,5% 11,5% 12,5% 11% 12,5% 11,5% 12% 12% 14% 16,5% 28,5%

6 Unités

Moyenne POS 1,56 3,10 3,12 3,12 3,10 3,09 3,08 3,10 3,12 3,14 3,17

%infaisabilité 9,5% 16% 13% 13% 10,5% 18,5% 16% 15% 21,5% 28,5% 40,5%

7 Unités

Moyenne POS 2,60 4,68 4,71 4,68 4,73 4,71 4,68 4,75 4,78 4,72 4,81

%infaisabilité 16% 16,5% 15% 18% 18,5% 23% 19% 21,5% 22% 37,5% 53,5%

Tableau 11-Résultats obtenus avec la version4 de l'algorithme

Nous avons constaté, lors de la comparaison de ces résultats avec ceux de la version

précédente, que les améliorations ne touchent pas toutes les grilles. Avec la première grille

(Point Grid), nous remarquons qu'il y a une petite hausse dans les probabilités de succès (avec 7

unités on est passé de 17,9 à 18) et une baisse remarquable dans les taux d'infaisabilité (de 73%

à 38,5%). Cette baisse est aussi signalée avec la deuxième et la troisième grille (CSAD Grid et

Line Grid). Le problème qu'on rencontre ici se résume au fait qu'avec ces deux dernières grilles,

et contrairement à la première, les probabilités de succès n'ont pas connu une amélioration. On

parle même d'une diminution dans la majorité des cas. Ceci revient au fait qu'on n'a rien mis en

place au de niveau de cet opérateur qui puisse préserver ou améliorer le niveau de succès

atteint. Limiter le choix de rectangles à insérer dans la population s'avère peu contraignant

surtout quand les meilleurs parmi eux, en termes de probabilité de succès, se trouvent sur des

régions géographiques rapprochées. Dans une telle situation, il est recommandé de choisir des

rectangles éloignés pour éviter qu'ils chevauchent. Ceci pourrait engendrer une baisse dans la

probabilité de succès si nous nous comparons à l'ancienne manière de faire qui consiste à choisir

un rectangle indépendamment de son emplacement géographique par rapport aux autres

105

rectangles du même génome. C'est ce qui explique la légère diminution des probabilités de

succès avec cette version.

Malgré ce dernier petit détail, cet opérateur semble intervenir dans l'augmentation du

nombre de solutions réalisables. L'idéal serait de le garder et d'essayer d'améliorer les autres

opérateurs de reproduction de façon à ce qu'ils ne prennent en considération que les meilleurs

rectangles en termes de probabilité de succès. C'est ce que nous allons tenter de réaliser dans

les deux versions suivantes.

4.4.4 Version 5 du modèle

Le changement apporté à cette version consiste à modifier le fonctionnement de

l'opérateur de mutation de façon à ce qu'il se soucie, en plus de la faisabilité des individus, de

l'amélioration de leurs probabilités de succès. Si un rectangle doit être remplacé dans un

génome, nous nous assurons avec cette version améliorée de l'opérateur que son substitut, qui

ne doit pas se superposer avec aucun des autres rectangles, ait une meilleure probabilité de

succès. Le tableau suivant résume les étapes de l'algorithme génétique défini sous cette version

ainsi que leurs modes de fonctionnement. Nous présentons par la suite les résultats obtenus

avec sa mise en place.

Élément Mode de fonctionnement

Création de la population initiale Création de la population initiale avec préservation de faisabilité

Mutation Mutation avec préservation de faisabilité garantissant une

amélioration de la probabilité de succès (opérateurl)

Croisement Choix aléatoire du point de croisement

Fonction objectif p x (SuccèsO + (1 - P) x (1 - interO

Tableau 12-Tableau récapitulatif de la version 5 du modèle

106

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,38 11,51 11,48 11,31 11,51 11,22 11,63 11,47 11,73 11,83 12,17

%infaisabilité 11% 15% 12% 11,5% 11,5% 15,5% 14,5% 13% 23% 27% 33%

6 Unités

Moyenne POS 1,68 12,01 12,04 12,16 12,53 12,28 12,47 12,84 12,47 12,72 12,57

%infaisabilité 14% 21% 17% 20% 17% 20% 25,5% 23,5% 27,5% 35,5% 39%

7 Unités

Moyenne POS 2,61 19,29 19,28 18,58 19,05 19,41 19,25 19,79 19,52 20,35 20,45

%infaisabilité 15% 23% 24,5% 21% 27,5% 27% 30,5% 21,5% 34% 43% 50,5%

Grille : CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 0,95 3,64 3,61 3,65 3,63 3,58 3,63 3,62 3,67 3,76 3,75

%infaisabilité 10% 9% 14% 13,5% 12% 15% 9,5% 15% 15,5% 26% 23%

6 Unités

Moyenne POS 1,25 3,92 3,94 4,01 3,96 3,97 3,9 4,03 4,04 4,21 4,19

%infaisabilité 12,5% 19% 18,5% 18% 20,5% 17,5% 17,5% 14% 24,5% 28,5% 43,5%

7 Unités

Moyenne POS 2,13 5,86 5,93 5,80 5,83 5,77 5,86 5,97 5,98 6,09 6,14

%infaisabilité 17,5% 26,5% 17% 27,5% 21% 24% 19% 23,5% 24,5% 36% 53%

107

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,22 2,89 2,91 2,91 2,89 2,89 2,92 2,90 2,94 2,96 2,98

%infaisabilité 12% 12,5% 15,5% 14,5% 15% 15,5% 14% 13,5% 21% 20% 37,5%

6 Unités

Moyenne POS 1,53 3,31 3,27 3,28 3,24 3,31 3,26 3,30 3,35 3,32 3,41

%infaisabilité 13,5% 24% 21% 18% 20,5% 15,5% 24,5% 19,5% 24,5% 30,5% 50%

7 Unités

Moyenne POS 2,65 4,90 4,94 4,95 4,93 4,96 4,92 4,95 4,92 5,02 5,10

%infaisabilité 17% 20% 18,5% 20% 20% 23% 25,5% 29% 30% 37,5% 50,5%

Tableau 13-Résultats obtenus avec la versions de l'algorithme

En partant du fait qu'on vise avec la mise en place de cette version l'amélioration de la

probabilité de succès cette base, nous allons nous concentrer dans notre analyse seulement sur

les changements que connaîtront les niveaux de cette probabilité et leurs répercussions sur les

taux d'infaisabilité.

Selon nos résultats, les modifications apportées sur l'opérateur de mutation ont

engendré une augmentation remarquable de la probabilité de succès des solutions. Si on balaie

la première grille (Point Grid) avec 7 unités (3ème scénario), nous remarquons que pour p égale à

1 la probabilité de succès a augmenté de 13% (de 18 à 20,4). Cette hausse de probabilité de

succès a entraîné une augmentation des taux d'infaisabilité. À partir de cette observation, nous

concluons que plus on a de meilleures solutions en terme de performance moins on a de

solutions réalisables.

II est à signaler ici que si nous comparons ces résultats à ceux obtenus avec la version3

de l'algorithme, nous remarquons une augmentation nette des probabilités de succès et une

diminution remarquable des taux d'infaisabilité sur toutes les grilles et avec tous les scénarios

108

que nous nous sommes fixés. Nous n'avions pu atteindre un tel comportement avec la version 4

de l'algorithme. Ainsi, le nouvel opérateur de mutation, qui est une version améliorée de celui

utilisé précédemment, s'avère plus efficace. Nous tenterons, dans la version suivante de

l'algorithme, d'améliorer davantage cet opérateur afin d'obtenir de meilleures solutions sur le

plan de la performance et celui de la faisabilité.

4.4.5 Version 6 du modèle

Elle se distingue par la mise en place d'une version améliorée de l'opérateur de

mutation défini précédemment dans le but d'améliorer davantage les probabilités de succès des

solutions. Nous présentons dans le tableau suivant les principes des éléments sur lesquels se

base cette version.

Élément Mode de fonctionnement

Création de la population initiale Création de la population initiale avec préservation de faisabilité

Mutation Mutation avec préservation de faisabilité garantissant une

amélioration de la probabilité de succès (opérateur2)

Croisement Choix aléatoire du point de croisement

Fonction objectif P x (SuccèsO + (1 - P) x (1 - inten)

Tableau 14-Tableau récapitulatif de la version 6 du modèle

Nous illustrons dans ces tableaux les résultats obtenus avec cette version.

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,37 11,43 11,15 11,20 11,18 11,42 11,58 11,51 11,52 11,83 12,16

%infaisabilité 10% 7% 8% 12% 6,5% 8,5% 14% 14% 14% 21,5% 28%

109

6 Unités

Moyenne POS 1,72 12,19 11,89 12,10 11,90 12,17 11,82 12,3 12,26 12,72 12,93

%infaisabilité 12,5% 16% 16,5% 15% 13% 15% 19,5% 15,5% 21% 26% 39%

7 Unités

Moyenne POS 2,84 18,46 18,66 18,47 18,74 18,31 18,92 19,22 19,46 20,23 20,92

%infaisabilité 14,5% 13,5% 14,5% 11,5% 15,5% 14,5% 21,5% 15% 26% 31,5% 47%

Grille : CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,00 3,62 3,65 3,64 3,67 3,64 3,65 3,67 3,74 3,82 3,90

%infaisabilité 8% 8% 9% 9,5% 8% 11% 8,5% 7,5% 8% 19,5% 22%

6 Unités

Moyenne POS 1,25 3,96 3,96 3,98 3,95 3,97 4,01 4,00 4,09 4,10 4,23

%infaisabilité 16,5% 17,5% 11,5% 16% 11% 10% 10% 12,5% 11% 22% 37%

7 Unités

Moyenne POS 2,13 5,78 5,75 5,70 5,71 5,86 5,79 5,84 5,95 5,99 6,29

%infaisabilité 17% 15% 15,5% 15,5% 14,5% 17% 13,5% 14,5% 18,5% 28,5% 45,5%

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,24 2,80 2,80 2,82 2,82 2,82 2,81 2,86 2,90 2,97 3,00

%infaisabilité 10% 12,5% 13% 12,5% 14% 15,5% 11% 11,5% 14% 21% 36%

6 Unités

Moyenne POS 1,54 3,13 3,16 3,12 3,16 3,17 3,21 3,24 3,31 3,35 3,61

%infaisabilité 10,5% 19% 17,5% 14% 17% 16,5% 17,5% 18% 12,5% 34,5% 46,5%

110

7 Unités

Moyenne POS 2,62 4,65 4,69 4,67 4,68 4,73 4,76 4,80 4,94 5,00 5,13

%infaisabilité 14% 20% 21% 23,5% 21,5% 20% 16% 20% 24,5% 39% 51%

Tableau 15-Résultats obtenus avec la version6 de l'algorithme

L'objectif que nous avions pour cette version a été atteint puisqu'on note pour la

plupart des résultats, comparés à ceux obtenus avec la version précédente, une augmentation

de la probabilité de succès et une diminution des taux d'infaisabilité. Nous prenons ici trois

exemples de scénarios pour illustrer le changement de valeurs des deux derniers critères.

Si on effectue les recherches sur la troisième grille (Line Grid) en utilisant 5 unités de

recherches (1er scénario), la meilleure probabilité de succès est de 3. Sous les mêmes

conditions, nous n'avons pu atteindre avec la version précédente que 2,9. Quant aux

taux d'infaisabilité, nous notons une diminution de 1,5% (de 37,5% à 36%).

Pour une opération de recherche à 6 unités (2ème scénario) effectuée sur la deuxième

grille (CSAD Grid), nous précisons que la probabilité de succès a subi une légère

augmentation (de 4,19 à 4,23). Le taux de faisabilité a diminué de 6,5% (de 43,5% à

Si on lance une opération de recherche à 7 unités (3ème scénario) sur la première grille

(Point Grid), nous remarquons que la probabilité de succès augmente de 2% (de 20,4 à

20,9). Le taux d'infaisabilité, quant à lui, est passé de 50,5% à 47%.

Ces trois cas montrent un même comportement de l'évolution de la probabilité de

succès et du taux d'infaisabilité qu'on pourrait généraliser sur la totalité des configurations de

recherche. II s'agit bien d'une augmentation de la probabilité de succès et d'une diminution du

taux d'infaisabilité.

En partant de cela, nous pouvons dire que les modifications apportées sur l'opérateur

de mutation ont été fructueuses même si les améliorations enregistrées par rapport à la

dernière version ne sont pas très grandes. Malgré ceci, cette version s'avère la meilleure

111

puisqu'en la mettant en place, nous avons pu obtenir les meilleures probabilités de succès et les

plus faibles taux d'infaisabilité.

4.5 Conclusion

Pour conclure, nous tenons à préciser que l'objectif visé, avec cette catégorie

d'approches, a été atteint. En mettant en place un algorithme génétique prenant en

considération la satisfaction des contraintes, nous avons pu baisser le taux d'infaisabilité des

solutions et préserver, ou même améliorer dans quelques cas, le niveau de succès des résultats

retournés. Les différentes modifications apportées sous cette catégorie d'approches nous ont

permis de ressortir avec la meilleure version de l'algorithme. Cette dernière, qui est la version 6,

regroupe les opérateurs de reproduction assurant l'obtention des meilleures solutions en

termes de probabilité de succès et de taux d'infaisabilité.

112

Chapitre 5. Optimisation avec fonction de fitness variable

Nous nous intéressons dans cette section à la troisième catégorie d'approches de

résolution. Dans ces approches, nous tentons d'améliorer l'utilisation de la fonction de fitness.

L'objectif que nous voulons atteindre consiste à définir une fonction objectif capable de mieux

évaluer les individus constituant les populations de différentes générations. Nous faisons

toujours intervenir, comme dans la fonction utilisée dans les versions précédentes, les critères

d'évaluation de la probabilité de succès d'un individu et de son degré de faisabilité.

Notre approche consiste à mettre en place une fonction objectif variable d'une

génération à une autre. Pour cette fin, nous ferons en sorte que l'importance relative de chacun

des deux critères d'évaluation soit accordée en fonction de l'évolution des populations.

Deux modèles ont été mis en place pour cette catégorie d'approches. Chacun d'eux

correspond à une version de l'algorithme. Nous précisons ici que nous nous sommes basés sur la

version6 de l'algorithme pour implémenter ces deux modèles. Cette version correspond, jusqu'à

maintenant, à notre meilleure solution au problème d'allocation de plusieurs unités de

recherche. C'est en essayant de lui apporter quelques modifications que nous pourrions obtenir

une meilleure qualité de solutions. La création de la population initiale, le croisement et la

mutation s'effectueront de la même manière qu'à la version 6. La seule différence se trouve au

niveau de la fonction objectif. Nous appliquerons, dans les deux versions de l'algorithme

implémentées sous cette catégorie d'approches, les modèles présentés par Carlson dans

[CARL95] et Joines et Houk dans [JOIN 94].

113

5.1 Présentation des modèles

Tel que mentionné précédemment, l'idée de base consiste à préserver la même manière

dont fonctionnent les opérateurs de reproduction dans la version 6 de l'algorithme et à

appliquer l'une des fonctions objectifs définies dans les sections 5.1.1 et 5.1.2. Nous tenons à

préciser ici que la fitness d'un individu correspond, comme dans les précédentes versions, à la

somme des fitness des gènes de ce chromosome. Cependant, nous allons agir sur le moyen avec

lequel un rectangle est évalué. Autrement dit, il n'y aura modifications que sur le calcul de la

cote de chaque rectangle individuel.

Nous présenterons, pour conclure cette section, les versions implémentées de l'algorithme.

5.1.1 Fitnessl

Nous nous sommes inspirés, pour définir cette fonction, du modèle présenté par

Carlson. Ce dernier consiste à multiplier la fitness d'un individu par un nombre généré en

fonction du nombre d'itérations ou de générations. II est égal à e~Ln(-1+t\ Pour nous ajuster à

notre cas, nous avons dû apporter quelques modifications qui concernent :

Le facteur de la multiplication. Si nous voulons améliorer la qualité des solutions en

termes de probabilité de succès, il vaut mieux qu'on prenne plus en considération ce

facteur. C'est la raison pour laquelle qu'on a remplacée e_ I n ( 1 + t ) pare(n^1+t^. Ceci fera

du facteur de la multiplication un nombre positif qui grandit d'une génération à une

autre.

La portée de l'application de cette multiplication. Nous avons choisi de l'appliquer qu'au

facteur succès. Ceci est dû aux faits que :

o Son application à toute la fonction n'a en aucun cas pu améliorer la

performance de notre algorithme.

o La maximisation doit porter seulement sur la probabilité de succès.

114

Le facteur d'intersection, quant à lui, est calculé de la même méthode appliquée dans

les versions précédentes. Nous utilisons aussi dans cette fonction le paramètre /? qui nous

permet de suivre la variation des résultats en fonction de l'importance accordée à chacun des

deux critères d'évaluation.

Cote rectangle t = \3 x e ' n ( 1 + t ) x (Succès?) + (1 - /?)(1 - inter{)

Aver inter - a x fnombre d'intersection / \ A v e c i n t e r ~ a x l /nombre d'intersection maxj +

t^ \ s , /surface d'intersection^ / \ 1 1 " a ) X V f sur face j

Et Succèst — f p n ç

Sachant que t correspond au nombre d'itérations

Figure 38-Fonction de fitness selon le modèle de Carlson

En mettant en place cette fonction, nous nous attendons à ce que :

On mette l'accent sur la maximisation des probabilités de succès que sur la

minimisation du nombre de solutions infaisables.

On atteigne un niveau supérieur de probabilité de succès tout en gardant les mêmes

taux d'infaisabilité.

La variation de /? ait une influence sur la qualité des solutions générées. Son

augmentation doit normalement engendrer une amélioration des probabilités de

succès et une diminution du nombre des solutions réalisables.

La probabilité de succès et les taux d'infaisabilités augmentent au fur et à mesure

qu'on augmente le nombre d'unités de recherche.

5.1.2 Fitness!

La deuxième fonction de fitness qu'on propose se base sur le modèle proposé par Joines

et Houk. Celle-ci consiste à multiplier une partie de la fonction par un nombre généré en

115

fonction du nombre d'itérations dans le but de mettre plus en valeur la violation de contraintes.

Ceci revient à sanctionner les individus violant le plus de contraintes.

Si nous nous ajustons à notre problème, il serait recommandé de pénaliser un rectangle

en fonction de la superficie de superposition qu'il a en commun avec d'autres rectangles du

même chromosome. On devrait faire en sorte que la cote d'un rectangle satisfaisant toutes les

contraintes soit supérieure à celle d'un rectangle qui en viole une ou plus. C'est pour cette

raison que le facteur d'intersection de cette fonction considère plutôt le complément du degré

de superposition. Ce degré est le résultat de la division de la somme des surfaces d'intersection,

que partage le rectangle à évaluer avec le reste des rectangles du chromosome, par sa

superficie. Plus ce rectangle chevauche avec d'autres, plus la valeur du facteur d'intersection

diminue. Un rectangle chevauchant avec aucun rectangle se voit attribuer la valeur maximale

que le facteur intersection peut atteindre. Ce dernier fait intervenir aussi le nombre généré en

fonction du nombre d'itérations. Ceci nous permet d'augmenter davantage la cote des meilleurs

rectangles en termes de faisabilité. L'utilisation du paramètre a nous permet de suivre la

variation de la qualité des solutions en fonction de l'importance accordée au facteur

intersection.

Cote rectangle, = (Succès i) + (1 + a) 1 x (1 - intert)

Avec inter = _ /surface d'intersection^ / " v 'surface ,)

Et SuccèSi = f p n ç r u j m a x

Sachant que t représente le nombre d'itérations

Figure 39-Fonction de fitness selon le modèle de Joines et Houk

Nous nous attendons, avec la mise en place de cette fonction, à ce que :

Les taux d'infaisabilité diminuent par rapport à ce qu'on a obtenu avec les autres

fonctions.

116

L'évolution des taux d'infaisabilité suive la variation du paramètre a.

L'augmentation de ce dernier devrait impliquer une augmentation du nombre de

solutions réalisables.

Les probabilités de succès et les taux d'infaisabilité augmentent en fonction du

nombre d'unités de recherche.

5.2 Présentation des versions du modèle implémentées

À partir des fonctions objectif définies dans les sections précédentes, nous proposons

deux nouveaux modèles de résolution pour notre problème d'allocation d'unités de recherche.

Pour la mise en œuvre de ces derniers, nous nous sommes référés, comme nous l'avons précisé

au début de ce chapitre, au modèle proposé pour la version 6 de l'algorithme. La seule

modification apportée aux versions que nous présentons se trouve au niveau de la fonction

objectif. Nous précisons ici que les opérateurs de reproduction fonctionneront de la même

façon qu'à la version 6.

Version 7 du modèle :

Nous utilisons, dans cette version, la fonction de fitness définis dans la section 5.1.1.

Nous visons l'obtention de meilleures solutions en termes de probabilité de succès sans que cela

se répercute négativement sur les taux d'infaisabilité.

Version 8 du modèle :

La modification apportée avec cette version consiste à mettre en place la fonction de

fitness présentée dans 5.1.2. Cette dernière prend plus en considération la faisabilité des

solutions que leurs probabilités de succès.

117

5.3 Présentation et analyse des résultats

Les résultats expérimentaux que nous avons obtenus avec les versions modifiées de

l'algorithme (version7 et version8) sont présentés dans cette section. Nous rappelons que nos

expérimentations ont été effectuées dans les mêmes conditions que celles fixées pour mener

nos tests sur les versions précédentes de l'algorithme. Nous utilisons le même nombre

d'individus, le même nombre de générations, le même pourcentage de croisement et la même

probabilité de mutation.

5.3.1 Version 7 du modèle

Cette version est marquée par l'utilisation de la nouvelle fonction objectif définie dans la

section 5.1.1. Cette dernière est constituée de deux facteurs pour évaluer les solutions suivant

leurs probabilités de succès et le nombre de rectangles superposables qu'elles contiennent.

Nous utilisons dans la nouvelle fonction le paramètre 3 pour suivre de près l'évolution de la

probabilité de succès et du taux d'infaisabilité suivant l'intérêt qu'on accorde à chacun d'eux.

Avant de présenter et commenter les résultats obtenus avec cette version, nous

résumons dans le tableau suivant les éléments sur lesquels repose cette version ainsi que leurs

modes de fonctionnement.

Élément Mode de fonctionnement

Création de la population initiale Création de la population initiale avec préservation de faisabilité

Mutation Mutation avec préservation de faisabilité garantissant une

amélioration de la probabilité de succès (opérateur2)

Croisement Choix aléatoire du point de croisement

Fonction objectif P x eLn(-1+V x (Succès^ + (1 - /?)(! - inter t)

Tableau 16-Tableau récapitulatif de la version 7 de l'algorithme

118

Grille : Point Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,39 11,20 11,25 11,57 11,64 11,75 11,79 11,84 11,81 11,97 12,22

%infaisabilité 10,5% 22,5% 28,5% 27% 27,5% 38,5% 41% 39% 45,5% 39,5% 56%

6 Unités

Moyenne POS 1,82 11,86 12 12,06 12,39 12,29 12,38 12,42 12,52 12,76 12,59

%infaisabilité 13% 24,5% 23,5% 32% 23,5% 33% 39,5% 37% 44,5% 56% 61%

7 Unités

Moyenne POS 2,97 18,64 18,27 18,70 18,87 18,43 18,65 19,86 19,57 20,33 20,79

%infaisabilité 29% 37,5% 47% 41,5% 42% 48% 45,5% 56% 57,5% 74% 80,5%

Grille: CSAD Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 0,97 3,59 3,69 3,64 3,68 3,71 3,59 3,72 3,73 3,87 3,95

%infaisabilité 17,5% 15,5% 17% 20% 21,5% 22,5% 20,5% 25% 28,5% 34% 45,5%

6 Unités

Moyenne POS 1,24 3,84 3,82 3,90 4,02 4,04 3,98 4,09 4,14 4,23 4,32

%infaisabilité 20,5% 25% 29% 31,5% 33% 29,5% 31% 36% 42% 46.5% 58%

7 Unités

Moyenne POS 2,17 5,51 5,68 5,62 5,73 5,82 5,76 5,90 5,86 6,03 6,25

%infaisabilité 19% 27% 31% 36,5% 36% 41,5% 48% 43,5% 52,5% 55,5% 73%

119

Grille : Line Grid

P 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 1,22 2,87 2,84 2,77 2,81 2,86 2,89 2,93 2,85 2,95 3,03

%infaisabilité 10,5% 22% 20,5% 23% 19% 27,5% 27% 33% 31% 35,5% 43%

6 Unités

Moyenne POS 1,55 3,23 3,13 3,21 3,35 3,30 3,32 3,41 3,37 3,52 3,65

%infaisabilité 13% 32% 28,5% 29,5% 37% 33% 36,5% 43,5% 43% 47% 64,5%

7 Unités

Moyenne POS 2,60 4,62 4,69 4,65 4,71 4,75 4,73 4,81 4,89 4,98 5,07

%infaisabilité 23% 32,5% 36,5% 34,5% 38% 37,5% 41% 48% 57% 69,5% 85%

Tableau 17-Résultats obtenus avec la version7 de l'algorithme

L'évaluation des résultats se fera sur deux volets. Nous nous intéressons en premier lieu

aux taux d'infaisabilité. Pour une grille et un scénario donnés, nous remarquons que le niveau

d'infaisabilité évolue au fur et à mesure que le paramètre p augmente. Sur la troisième grille

(Line Grid) et avec le troisième scénario (7 unités de recherches), le taux d'infaisabilité est passé

de 23% à 37,5% entre 3=0 et P=0,5. L'écart se creuse davantage pour des valeurs plus grandes

de ce paramètre. On arrive même à atteindre un taux de 85% pour une valeur de 3 égale 1.

Cette observation, valide pour tous les scénarios possibles de recherche, confirme le

comportement des taux d'infaisabilité qu'on visait atteindre avec la nouvelle fonction objectif

mise en place. D'autre part, on voit bien que les taux d'infaisabilité, conformément à nos

attentes, augmentent significativement en fonction du nombre d'unités de recherche.

Du côté des probabilités de succès, nous signalons une augmentation en fonction du

nombre d'unités de recherche. Cette augmentation est expliquée par le fait qu'une opération de

recherche pourrait être plus fructueuse si nous disposions d'un nombre important d'équipes de

recherche. Ceci nous permettra d'élargir au maximum la zone de recherche et ainsi augmenter

les chances de trouver l'objet perdu. Nous remarquons aussi que les probabilités de succès

augmentent en fonction de 3 comme le montre la figure suivante. Cette dernière illustre

120

révolution de la probabilité de succès en fonction de 3 sous les différentes configurations de

recherche appliquées à la première grille.

Moyenne POS pour 5 unités

— — Moyenne POS pour 6 unités Moyenne POS pour 7 unités

~i 1 1 1 1 i 1 1 1 1 1

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Figure 40-La variation du POS moyen en fonction de P sur Point Grid (version7)

Pour conclure l'évaluation de cette version, nous précisons que, pour la plupart des

résultats obtenus et si nous nous comparons à ceux de la version précédente (Version6), nous

remarquons une légère hausse dans les probabilités de succès. Ceci ne peut pas être généralisé

sur tous les scénarios et les configurations de recherche puisque nous signalons dans quelques

rares cas une baisse de performance. Cette baisse, malgré qu'elle ne soit pas fréquente, reste à

préciser pour qu'on puisse la considérer dans la comparaison des versions qu'on effectuera dans

la prochaine section. II faut mentionner aussi que le nombre des solutions réalisables a chuté

remarquablement avec cette version. Si on effectue une opération de recherche sur la troisième

grille avec 7 unités et avec P =1, le taux d'infaisabilité est passé de 51% à 85%. Cette observation

est due principalement à l'importance que nous accordons au facteur succès.

5.3.2 Version 8 du modèle

Cette version est marquée par la mise de la fonction objectif définie dans la section

5.1.2. La modification que nous avons apportée consiste à multiplier le facteur intersection par

une variable qui augmente en fonction du nombre de générations. Nous avons inséré dans cette

variable le paramètre a. Ce dernier nous permettra de suivre les variations de la probabilité de

121

succès et du taux d'infaisabilité à chaque fois qu'on accorde plus d'importance au facteur

intersection.

Nous commençons par illustrer dans un tableau récapitulatif le mode de fonctionnement des

différents éléments sur lesquels cette version du modèle se base. Nous présentons par la suite

les résultats obtenus au cours des expérimentations menées sur cette même version.

Élément Mode de fonctionnement

Création de la population initiale Création de la population initiale avec préservation de faisabilité

Mutation Mutation avec préservation de faisabilité garantissant une

amélioration de la probabilité de succès (opérateur2)

Croisement Choix aléatoire du point de croisement

Fonction objectif (Succèsi) + ( l + a ) t x ( l - inter?)

Tableau 18 — Tableau récapitulatif de la version 8 de l'algorithme

Grille : Point Grid

a 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 11,62 11,93 11,71 11,79 12,11 11,86 11,65 11,88 11,87 11,85 11,61

%infaisabilité 20% 22% 23,5% 24% 27% 21% 20,5% 21,5% 21% 23% 22,5%

6 Unités

Moyenne POS 11,67 11,78 11,80 11,89 12,11 12,49 12,22 12,28 11,70 11,80 12,21

%infaisabilité 30,5% 32% 33% 34,5% 37% 41% 38% 39% 32,5% 33,5% 36,5%

7 Unités

Moyenne POS 20,39 19,91 20,03 19,41 19,84 19,55 19,11 19,76 19,87 20,12 19,43

%infaisabilité 54% 52% 53% 48,5% 51% 50% 46% 50,5% 51,5% 52,5% 49,5%

122

Grille : CSAD Grid

a 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 3,72 3,71 3,73 3,84 3,82 3,69 3,85 3,77 3,79 3,81 3,65

%infaisabilité 15,5% 17% 16,5% 24% 25% 15% 26% 20% 21,5% 23% 15%

6 Unités

Moyenne POS 4,05 4,13 4,15 4,24 4,20 4,14 4,11 3,98 4,00 4,19 4,08

%infaisabilité 38% 38% 42,5% 49,5% 46% 40,5% 39,5% 34% 33% 44% 40%

7 Unités

Moyenne POS 6,23 6,27 6,04 6,11 6,08 6,20 6,02 6,10 6,07 6,13 6,24

%infaisabilité 59% 60% 64,5% 55,5% 55% 62% 63,5% 49% 64% 66% 57,5%

Grille : Une Grid

a 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

5 Unités

Moyenne POS 2,87 2,83 2,88 2,79 2,89 2,95 2,84 2,84 2,86 2,89 2,94

%infaisabilité 20,5% 16,5% 21% 15% 21% 23,5% 19% 20,5% 19% 22,5% 22%

6 Unités

Moyenne POS 3,53 3,62 3,54 3,51 3,57 3,48 3,50 3,58 3,59 3,52 3,51

%infaisabilité 43% 47,5% 49% 48,5% 58,5% 45,5% 51,5% 60% 57% 53,5% 52%

7 Unités

Moyenne POS 5,11 5,15 4,99 4,93 4,98 4,89 4,95 5,01 5,09 4,87 5,13

%infaisabilité 76% 72,5% 73,5% 72% 67% 75% 68,5% 69% 73,5% 68% 76%

Tableau 19-Résultats obtenus avec la version8 de l'algorithme

123

À l'observation de ces résultats, nous remarquons que la variation du paramètre a

n'affecte presque pas la probabilité de succès. Dans la plupart de cas, nous signalons une légère

variation de cette probabilité qui ne suit pas forcément l'augmentation du paramètre a. Nous

prenons par exemple la deuxième grille (CSAD Grid). Pour une recherche à 6 unités, l'évolution

des probabilités de succès, comprises entre 3,98 et 4,24, ne suit pas une même allure lors de

l'augmentation de a. Entre a =0,1 et a =0,2, nous signalons remarque une légère hausse (de

4,13 à 4,15). Le même comportement persiste entre a =0,2 et a =0,3 (de 4,15 à 4,24). Entre

a=0,3 et a =0,4, la hausse cède sa place à une légère baisse (de 4,24 à 4,20) qui dure jusqu'à ce

qu'on atteigne une valeur de a=0,7 (de 4,20 à 3,98). C'est à partir de cette valeur que nous

remarquons de nouveau une hausse dans les probabilités de succès.

Le taux d'infaisabilité de ces solutions, quant à lui, ne varie pas de la manière souhaitée.

Son évolution ne suit pas la variation du paramètre a. Lorsque ce dernier augmente, nous nous

attendons à ce qu'on ait des taux d'infaisabilité de moins en moins importants. Ce qui n'est pas

le cas avec les résultats obtenus. Nous signalons une variation non uniforme des taux

d'infaisabilité. Comme la figure 41 le montre, cette variation est, dans la majorité des cas,

insignifiante puisqu'elle ne garde pas la même tendance durant l'évolution du paramètre a.

Cette figure dresse le comportement des taux d'infaisabilité sur la 3ème grille sous les 3 différents

scénarios :

100%

80%

60%

40%

20%

0%

* " " " ■ " " " ^*

,4~""""»«»>><- pour 5 u

\ + + * " " - - - %infaisa

%infaisabilité nités

%infaisabilité pour 6 unités %infaisabilité pour 7 unités

— \ 1 i 1 1 1 1 1 1 1

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Figure 41-La variation du taux d'infaisabilité POS en fonction de a sur Line Grid (version8)

124

Cette figure montre que les taux d'infaisabilité augmentent au fur et à mesure que le

nombre d'unités de recherche augmente. Elle confirme que la variation des taux d'infaisabilité

n'est ni remarquable ni régulière. Ceci ne nous permet pas de juger l'effet de a sur les solutions

obtenues.

Nous ajoutons à ces observations le fait que la fonction utilisée, en la comparant à celle

d'avant, ne permet pas d'obtenir de meilleurs résultats que ce soit sur le plan du succès ou sur

le plan de la faisabilité. En nous appuyant sur ces faits, nous avons préféré ne pas tenir compte

des résultats de cette version dans la comparaison entre versions que nous aborderons dans la

prochaine section.

125

5.4 Comparaison des résultats des trois approches

Notre objectif consiste, après avoir implémenté et testé différentes versions de

l'algorithme d'allocation d'unités de recherche, à identifier la meilleure d'entre elles. Cette

dernière devra permettre l'obtention d'un maximum possible de solutions faisables pouvant

atteindre une probabilité de succès maximale. Pour mener nos comparaisons, nous nous

référons pour chacune des trois approches, à une et une seule version de l'algorithme. Cette

dernière devra être la meilleure dans sa catégorie. Pour les algorithmes génétiques capables de

manipuler les contraintes, la version 6 est retenue en raison de la qualité des résultats qu'elle

retourne. En ce qui concerne les algorithmes génétiques avec fonction objectif variable, ils

seront représentés par la version 7 de l'algorithme.

Pour comparer les résultats obtenus avec les trois approches, nous avons dressé le

tableau 20 qui illustre pour chaque grille et chaque scénario le meilleur résultat obtenu avec la

versionl, la version 6 et la version7 de l'algorithme.

Type de grille Scénario Critères de comparaison Versionl Version6 Version7

Point Grid

5 unités Probabilité de succès 11,69 12,16 12,22

Point Grid

5 unités Taux d'infaisabilité 56% 28% 56%

Point Grid 6 unités Probabilité de succès 12,60 12,93 12,59

Point Grid 6 unités Taux d'infaisabilité 72% 39% 61%

Point Grid

7 unités Probabilité de succès 20,69 20,92 20,79

Point Grid

7 unités Taux d'infaisabilité 82,5% 47% 80,5%

CSAD Grid

5 unités Probabilité de succès 3,75 3,90 3,95

CSAD Grid

5 unités Taux d'infaisabilité 55,5% 22% 45,5%

CSAD Grid

6 unités Probabilité de succès 4,43 4,23 4,32

CSAD Grid

6 unités Taux d'infaisabilité 69% 37% 58%

126

7 unités Probabilité de succès 6,24 6,29 6,25

7 unités Taux d'infaisabilité 83% 45,5% 73%

Line Grid

5 unités Probabilité de succès 2,98 3,00 3,03

Line Grid

5 unités Taux d'infaisabilité 58,5% 36% 43%

Line Grid 6 unités Probabilité de succès 3,45 3,61 3,65

Line Grid 6 unités Taux d'infaisabilité 73,5% 46,5% 64,5%

Line Grid

7 unités Probabilité de succès 5,17 5,13 5,07

Line Grid

7 unités Taux d'infaisabilité 86,5% 51% 85%

Tableau 20-Comparaison des résultats des versions 1,6 et 7

Nous remarquons à partir de ce tableau comparatif :

Une diminution significative des taux d'infaisabilité des solutions obtenues avec la

version 6 de l'algorithme. Avec cette dernière, nous sommes arrivés à réduire ce taux,

dans le meilleur cas, de plus de la moitié. À titre d'exemple, pour la deuxième grille

(CSAD Grid) avec 5 unités, le taux d'infaisabilité a été réduit de 55,5% (version 1) à 22%

(version6), tandis qu'il n'a pu être ramené qu'à 45.5% avec la version7.

Une augmentation dans les probabilités de succès des solutions obtenues avec la

version 6. II est important de mentionner ici que cette augmentation ne peut pas être

généralisée sur toutes les grilles et tous les scénarios puisqu'on a signalé à sa place une

diminution sur deux différentes grilles : sur CSAD Grid avec 6 unités et sur Line Grid avec

7 unités. Ces exceptions ne nous empêchent pas de confirmer que les probabilités de

succès ont connu une amélioration avec la version 6 de l'algorithme.

Une augmentation dans les probabilités de succès des solutions avec la version 7 en les

comparant à ceux obtenus avec la version 6. Nous précisons ici que cette hausse ne peut

pas être généralisée sur toutes les configurations de recherche puisqu'elle n'est signalée

que dans cinq parmi neuf cas. Les quatre autres cas ont été marqués par une baisse de

la probabilité de succès. Nous ajoutons que, avec cette version de l'algorithme, le

nombre de solutions non réalisables a augmenté significativement. Ceci rendra

l'obtention d'une solution réalisable beaucoup moins fréquente si nous nous comparons

aux versions précédentes. Entre une probabilité de succès qui n'est pas nettement la

127

meilleure et un taux d'infaisabilité qui n'est pas satisfaisant, on peut dire que cette

version ne permet pas l'obtention des meilleurs résultats qui puissent exister.

En nous basant sur ces observations, nous concluons que la version 6 est la plus

performante de ces trois versions puisqu'elle permet l'obtention de solutions de qualité

meilleure. Ceci implique qu'il vaut mieux travailler avec des algorithmes génétiques capables de

manipuler des contraintes qu'avec des algorithmes génétiques classiques ou même des

algorithmes génétiques à fonction objectif variable. Ceci ne fera qu'augmenter la capacité de

l'algorithme à parcourir la totalité de l'espace de recherche et à identifier des meilleurs

résultats.

5.5 Comparaison AG/ILOG Solver

Dans les travaux de Abi-Zeid, I. ; Nilo, O. ; Lamontagne [ABI 10], le problème d'allocation

optimale de ressources a été résolu par optimisation combinatoire en ayant recours à l'outil

ILOG SOLVER. Ce dernier est un moteur qui utilise la programmation par contrainte pour la

résolution des problèmes combinatoires complexes. II se base sur la technologie D'ILOG Concert

qui est une bibliothèque C++ [YAH 07]. Cette approche a été appliquée au même problème, sur

les mêmes grilles et avec les mêmes scénarios que les nôtres. Les résultats obtenus sont illustrés

dans le tableau suivant. Nous précisons pour chaque scénario la première et la meilleure

probabilité de succès obtenus ainsi le temps d'exécution, en secondes, qu'il a fallu au

programme pour les retourner.

ILOG Solver Point Grid CSAD Grid Line Grid

1er POS Meilleur POS 1er POS Meilleur POS 1er POS Meilleur POS

5 unités Valeur 21,82 24,77 5,42 5,75 4,57 4,7

5 unités T. Exécution 8,75 131,438 24,719 120,938 13,094 28,891

6 unités Valeur 25,54 28,8 6,21 6,71 5,27 5,39

128

T. Exécution 12,391 1635,891 38,063 4412,047 37,219 145,766

7 unités Valeur 34,85 35,67 9,03 9,06 6,73 6,85

7 unités T. Exécution 46,031 144,047 95,047 1558,859 261,938 268,906

Tableau 21-Résultats obtenus avec ILOG Solver

Nous comparons les résultats de l'approche ILOG avec notre version 6 de l'algorithme.

Or, en modifiant les paramètres de dimensionnement dans cette version, nous avons réussi à

obtenir des solutions meilleures. Après avoir testé notre algorithme sur une population de 100

individus et une reproduction sur 5000 générations, nous avons essayé de régénérer les

résultats pour un nombre d'individus de 500, 1000, 2000 et pour un nombre de générations

égal à 5000 et 10000. Les meilleurs résultats ont été obtenus avec 2000 individus et 5000

générations. Le tableau suivant illustre la moyenne des probabilités de succès des solutions

réalisables obtenues parmi les 200 solutions proposées et le temps d'exécution moyen passé

pour générer une solution. Les essais ont été effectués, comme pour le reste des

expérimentations, sur les trois grilles en considérant trois scénarios de recherche (5, 6 et 7

unités).

AG

(Moyenne des POS) Point Grid CSAD Grid Line Grid

5 unités POS 15,21 4,60 3,45

5 unités Temps d'exécution 121.2 142.8 143

6 unités POS 16,43 4,92 3,88

6 unités Temps d'exécution 148 165 180.4

7 unités POS 25,80 7,12 5,77

7 unités Temps d'exécution 186,25 195.5 208.8

Tableau 22-Meilleures moyennes des POS par scénario de recherche

129

Pour une meilleure interprétation, nous nous sommes référés dans notre comparaison

aux premiers résultats qu'ILOG Solver génère. Ceci est dans le but de comparer des solutions

obtenues avec des temps d'exécution semblables.

Le premier constat concerne le temps d'exécution. Nous remarquons, à partir des

tableaux 21 et 22, qu'ILOG Solver fournit plus rapidement une solution au problème. Ceci est

valide sur tous les scénarios définis pour chacune des grilles. Nous tenons à préciser ici que la

lenteur signalée avec les algorithmes génétiques est principalement due aux changements

apportés sur le nombre de générations et le nombre d'individus. Notons que, pour un nombre

de générations égal à 1000 et un nombre d'individus égal à 100, nous obtenons,

indépendamment de la grille et du scénario choisis, une solution dans un délai maximal de 7

secondes. Cependant, cette configuration ne nous permet pas d'atteindre le niveau de

performance obtenu avec une population de 2000 individus évoluant sur 5000 générations.

En ce qui concerne les probabilités de succès, nous constatons que, malgré

l'amélioration qu'elles ont connue, nous n'avons pas réussi à surpasser ou même égaler le degré

de succès atteint par ILOG Solver. Ceci est dû à l'aspect aléatoire sur lequel se basent les

algorithmes génétiques pour parcourir l'espace de recherche, sélectionner et améliorer une

solution. Nous avons essayé, dans nos versions d'amélioration de l'algorithme, de limiter la

portée de cet aspect dans les différents opérateurs de reproduction définis en y amenant

plusieurs restrictions au niveau du choix des individus. II semble que cette manière de faire a pu

contribuer à l'amélioration des solutions obtenues, mais reste incapable de cibler les meilleurs

individus dont on dispose.

130

Chapitre 6. Conclusion

L'objectif de nos travaux était de mettre en place un algorithme génétique qui pourrait

contribuer à la résolution du problème d'allocation de ressources. Pour arriver à cette fin, nous

avons mené une étude détaillée sur le fonctionnement des algorithmes génétiques. Nous avons

aussi abordé, puisque nous faisons face à un problème fortement contraint, les problèmes de

satisfaction de contraintes et les méthodes de manipulation de contraintes dans un algorithme

génétique. En nous référant à ces approches, nous avons pu implémenter un algorithme

génétique qui répond à nos besoins. L'idée était de pouvoir fournir aux coordonnateurs des

missions de recherche un plan d'action composé de multiples assignations distinctes (zone de

recherche - unité de recherche) qui ne se chevauchent pas et qui assurent une probabilité de

succès maximale. L'idéal serait d'attribuer les rectangles avec les meilleures probabilités de

succès aux différentes unités de recherche dont on dispose. Le problème qu'on rencontre dans

ce cas réside dans le fait que ces rectangles se trouveront presque sur le même emplacement

géographique. Ceci ne fera qu'augmenter les risques de chevauchement. C'est cette

caractéristique qui contraint grossièrement notre problème.

Pour faire face à cet obstacle, nous avons dû apporter quelques transformations sur les

algorithmes génétiques classiques. Les algorithmes résultants peuvent être classés sous deux

catégories. Dans la première, nous avons modifié les opérateurs de reproduction de l'algorithme

afin de les forcer à ne garder, insérer ou donner naissance qu'à des solutions réalisables. Notre

deuxième catégorie d'approches consiste à mettre en place une fonction objectif variable dans

l'objectif de mieux explorer l'espace de recherche pour en ressortir avec de meilleures solutions

que ce soit sur le plan du succès ou sur le plan de la faisabilité.

Par la suite, nous avons essayé d'évaluer la performance des différents modèles que

nous avons mis en place en les faisant exécuter sur trois types de grilles suivant trois différents

131

scénarios. II s'est avéré, après avoir comparé les résultats obtenus avec chacune des versions du

programme, que les algorithmes capables des manipuler des contraintes sont les meilleurs. Le

plus performant d'entre eux est celui qui ne garde pour sa population initiale que des individus

réalisables. II ne les mute que si une augmentation de POS est envisageable sans que cela

touche à la faisabilité des candidats.

Nous avons finalement effectué une comparaison entre nos résultats et ceux obtenus

avec ILOG Solver. Cette comparaison nous a permis de conclure que nous n'avons pas pu obtenir

de meilleurs résultats qu'avec ILOG Solver.

Nous ne voulons cependant pas conclure sur cette note pessimiste, mais plutôt sur les

perspectives qui nous paraissent les plus prometteuses. Celles-ci se résument à :

• trouver un moyen de guider l'algorithme vers les meilleures solutions. Ceci pourrait

réduire la différence signalée au niveau des probabilités de succès.

• modifier l'opérateur de croisement de façon à ce qu'il ne génère que des solutions

réalisables ayant une probabilité de succès supérieure à celle des solutions que la

génération en cours renferme.

• régénérer les résultats avec un plus grand nombre d'individus et de générations

même si cette alternative s'avère coûteuse en termes de temps d'exécution.

• utiliser la fonction Comparator de la librairie GALib. Cette fonction permet de

comparer deux solutions et peut, donc, être utile durant la phase de sélection. En

l'utilisant, on pourrait par exemple favoriser l'individu ayant un meilleur POS.

• remplacer le modèle de notre algorithme (GASteadyStateGA) par celui d'un

algorithme génétique simple (GASimpleGA).

• automatiser le choix de grilles et de scénarios au lieu de le faire manuellement pour

chaque jeu d'essais.

132

Référence :

[ABI 10] Abi-Zeid I. ; Nilo O. ; Lamontagne L. Ressource allocation algorithms for

planning Search and Rescue Operations, 2010.

[ALD 94] David Aldous and Umesh V. Vazirani. "Go with the winners" algorithms.

In IEEE Symposium on Foundations of Computer Science pages 492-

501, 1994.

[BES 96] C. Bessière and J.C. Régin. MAC and combined heuristics. In Proc. of

CP'96 volume 1113 of LNCS pages 61-75, 1996.

[BLA 02] Blaise Madeline. Algorithmes évolutionnaires et résolution de problèmes

de satisfaction de contraintes en domaines finis. Thèse de doctorat

Université de Nice-Sophia Antipolis, 2002.

[CARL 93] Carlson Susan E. Component selection optimization using genetic

algorithms Doctoral thesis Department of mechanical engineering

Georgia Institute of technology Atlanta Georgia August, 1993.

[CARL 95] S.E. Carlson: A general Method for handling constraints in genetic

algorithm. University of Virginia. Charlottesville VA, 1995

[CONN 90] D. T. Connolly. An improved annealing scheme for the qap. European

Journal of Operational Research (46):93-100, 1990.

[CRAE 00] B.G.W Craenen A.E. Eiben E. Marchiori. Solving constraint satisfaction

problems with heuristic based evolutionary algorithms, 2000

133

[DAV 91] Davis T.E. and Principe J.C. A Simulated Annealing Like Convergence

Theory for the Simple genetic Algorithms proceedings of the fourth

Internation conference on Genetic Algorithm Morgan Kaufmann

Publishers Los Altos CA pp.174-181,1991.

[DIMI96] T. Dimitriou and R. Impagliazzo. Towards an analysis of local

optimization algorithms. In ACM Symposium on Theory of Computing

pages 304-313, 1996.

[DOZ 94] G. Dozier J. Bowen and D. Bahler. Solving small and large constraint

problems using heuristic-based micro genetic algorithms. In IEEE pages

306-311, 1994.

[EIB 01] A.E. Eiben. Evolutionary Algorithms and Constraint Satisfaction:

Definitions Survey Methodology and Research directions. Free University

Amsterdam and Leiden University, 2001. The Netherlands

[EIB 94] A.E. Eiben P-E. Raué and Zs. Ruttkay. Solving constraint satisfaction

problems using genetic algorithms. In IEEE pages 542-547, 1994.

[EIB 95] A.E. Eiben P-E. Raué and Zs. Ruttkay. Constrained problems. In

L.Chambers editor Practical handbook of genetic algorithms pages 307-

365. CRC Press, 1995.

[EIB 97] A.E. Eiben and Zs. Ruttkay. Constraint satisfaction problems. In th.

Back. D.fogel and M.Michalewicz editors' handbook of evolutionary

algorithms. IOP Publishing Ltd. And Oxford University Press, 1997.

134

[EIB 98] A.E.Eiben J.I. Van Hemert E. Marchoiri and A.G. Steenbeek: Solving

binary constraint satisfaction problems using EA with an adaptive

fitness, 1998.

[FRO 99] J.R. Frost. Principles of Search Theory, 1999.

[FROS 95] Daniel Frost and Rina Dechter. Look-ahead value ordering for constraint

satisfaction problems. In Proceedings of the International Joint

Conference on Articial Intelligence IJCAI'95 pages 572-578 Montreal

Canada, 1995.

[GEEL 92] P. A. Geelen. Dual viewpoint heuristics for binary constraint satisfaction

problems. In Tenth European Conference on Artificial Intelligence

(ECAI92) pages 3135, 1992.

[GENT 96] Ian P. Gent Ewan Maclntyre Patrick Prosser Barbara M. Smith and Toby

Walsh. An empirical study of dynamic variable ordering heuristics for

the constraint satisfaction problem. In E. C. Freuder editor Principles

and Practice of Constraint Programming - CP96 volume 1118 pages

179-193. Springer- Verlag, 1996.

[GOLD 89] Goldberg D.E. Genetic algorithm in search Optimisation and Machine

Learning addison-Wesley, 1989.

[GOLU 89] G.H. Golub and CF. Van Loan. Matrix Computations. Johns Hopkins

University Press Baltimore 2nd edition, 1989.

135

[GUEN 59] Jacques de Guenin. Les fondements d'une théorie de la recherche.

Revue de statistique appliquée tome 7 n° 4 p.41-71, 1959.

[HAR 80] R. Haralick and G. Elliott. Increasing tree search efficiency for constraint

satisfaction problems. Artificial Intelligence 14:263-313, 1980.

[HENT 95] P. van Hentenryck V. Saraswat and Y. Deville. Constraint processing in

cc (fd). In A. Podelski editor Constraint Programming: Basics and

Trends. Springer-Verlag Berlin, 1995.

[JOIN 94] Joines J. and C. R. Houck "On the use of non-stationary penalty

functions to solve nonlinear constrained optimization problems with

Gas" Proceedings of the evolutionary computation conference- Poster

session IEEE World congress on computational intelligence 579-584,

1994.

[KIRP 90] S. Kirpatrick CD. Gelatt and M.P. Vecchi. Optimization by simulated

annealing. Science 220:671-680, 1983.

[KOW 96] Ryszard Kowaczyk. Using constraint satisfaction in genetic algorithm.

Proc. 1996 Australian New Zealand Conf. On intelligent Information

Systems 18-20 November, 1996. Adelaide Australia Editors Narasimhan

and Jain.

[MAR 97] E. Marchiori. Combining constraint processing and genetic algorithms

for constraint satisfaction problems. In Th. Back editor Proceedings of

the 7th International Conference on Genetic Algorithms pages 330-337

San Francisco CA, 1997. Morgan Kaufmann Publishers Inc.

136

[MICH 94 a] MICHAELWICZ Z. Genetic Algorithm- Data Structures = Evolution

programs Second Extended Edition Springer- Verlag, 1994.

[MICH 94 b] Michalewicz Z. and N.Attia "In evolutionary optimization of constrained

problems" Proceedings of the 3rd annual conference of evolutionary

algorithms world scientific publishing 98-108, 1994.

[MINT 92] S. Minton M. Johnston A. Philips and P. Laird. Minimizing conflict: a

heuristic repair method for constraint satisfaction and scheduling

problems. Artificial Intelligence 58:161-205, 1992.

[MONT 74] U. Montanari. Network of constraints: Fundamental properties and

applications to picture processing. Inf. Sci. 7:95-132, 1974.

[RICH 86] Henry R. Richardson. Search Theory Professional Paper 449/April 1986.

Center for Naval Analyses.

[RIFF 96] M.C. Riff-Rojas. Using the knowledge of the constraint network to

design an evolutionary algorithm that solves CSP. In Belew and Booker

pages 279-284, 1996.

[RIFF 97] M.C. Riff-Rojas. Evolutionary search guided by the constraint network to

solve CSP. In Belew and Booker pages 337-348, 1997.

[SAU 87] Sauders P H. Anew Search Method Based on an Analysis of Air Distress

Cases: 1981-1986. Department of National Defense Canada;

Operational Research Branch Air Transport Group Headquarters CFB

Trenton Astra Ontario ATGOR Staff Note 2/87 1987.

137

[SELM 92] B. Selman H. Levesque and D. Mitchell. A new method for solving hard

satisfiability problems. In Tenth National Conference on Artificial

Intelligence pages 440-446, 1992.

[YAH 07] Assia Yahi : "Programmation par contrainte et algorithme génétique :

Comparaison des algorithmes de recherche dans le cadre de l'allocation

optimale des ressources ». Essai de MBA Université Laval Faculté des

sciences de l'administration, Hiver2007.

138