Application à la segmentation d'images

République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche ScientifiqueUniversité Constantine 2

Faculté des Nouvelles Technologies de l'information et de la Communication

Département Informatique Fondamentale et ses Applications

.

MémoireEn vue de l’obtention du diplôme de

Magister en informatiqueOption : Systèmes Distribués et Méthodes Formelles (SDMF)

.Thème

Traitement d'images par des approches bio-inspirées

Application à la segmentation d’images

Présenté par

Mohamed SANDELI

Soutenu le 27/02/2014 devant un jury constitué de :

Pr. Mohamed Benmohammed . Université Constantine 2 Président Pr. Mohamed Batouche Université Constantine 2 Rapporteur Pr. Salim Chikhi Université Constantine 2 Examinateur Dr. Mourad Bouzenada Université Constantine 2 Examinateur

ANNÉE UNIVERSITAIRE 2013/2014

N° d’ordre : ……………………………….

Série : ……………………………………….

DÉDICACES

Je dédie ce modeste travail :

A toute ma famille

A tous mes amis

A tous ceux qui m’ont aidé

REMERCIEMENTS

Je remercie Mr BATOUCHE Mohamed, Professeur à l’Université de

Constantine de m’avoir proposé un tel intéressant sujet, m’ouvrant ainsi

les portes sur un domaine de recherche assez vivant.

Je remercie tous les membres du jury qui ont accepté d'évaluer mon

travail.

Je remercie MME MESHOUL Souham, Maître de conférences à

l’Université de Constantine pour l’attention qu’elle m’a apporté durant

toutes cette période ainsi que pour sa lecture et ses commentaires qui

m’ont permis d’améliorer ce mémoire.

Je tiens aussi à remercier tous ceux qui ont, de près ou de loin, aidé

à rendre ce travail possible, que ce soit par des idées ou par des

encouragements.

RÉSUMÉ

Le traitement d'images joue aujourd'hui un rôle important dans de nombreux domaines.Cependant les contraintes d’exploitation (complexité algorithmique, aspect temps réel) justifientla multiplicité des techniques développées dans le domaine du traitement d’images. Dans unsystème de traitement d’images, l’opération la plus importante est la segmentation d’image.Jusqu’à ce jour, il n’existe pas de méthode universelle de segmentation d’image. Toutetechnique n’est efficace que pour un type d’image donné, pour un type d’application donné, etdans un contexte informatique donné. En raison de ces contraintes, les diverses stratégies detraitement d’image qui ont été proposées ont affirmé leurs insuffisances et leurs limitations. Ilest donc tout à fait normal d’explorer de nouveaux horizons et de trouver de nouvelles méthodesplus souples et plus efficaces. Parmi ces dernières, nous avons les approches bio-inspirées quiont été utilisées pour résoudre le problème de segmentation.

L’objectif de ce mémoire consiste donc à améliorer la segmentation d’image par lesapproches bio-inspirées en faisant appel aux techniques d’optimisation parallèles coopératives.

SUMMARY

Image processing plays an important role today in many fields. However with the operatingconstraints (computational complexity, real-time appearance), justify the multiplicity developedin the field of image processing techniques. Image segmentation is the most important operationin image processing system. To date, there is no universal method of image segmentation. Anytechnique is only effective for a given image type for a given type of application, and in a givencontext data. Because of these constraints, various strategies have been proposed in imageprocessing affirmed their shortcomings and limitations, so it is quite normal to explore newhorizons and find new, more flexible and more efficient methods. Among the latter, we havebio-inspired approaches that have been used to solve the segmentation problem.

Consequently, the objective of this thesis is to improve the image segmentation problem bybio-inspired approaches by using cooperative parallel optimization techniques.

الموجز

والمعالجةالحسابي،التعقیدمن بینھاالتشغیلقیودلكن. المجاالتمنالعدیدفيالیومھامادوراالصورتلعب معالجةأو ما یعرف تقسیم الصور إلى اجزاء متجانسة، مما فیھ الصورمعالجةتقنیاتمجالفيالحاصلتعددالتبررالحقیقيالوقتفي

. في تجزئة الصورعامةطریقةھناكلیساآلن،حتى. في نظام معالجة الصورأھمیةاألكثرالعملیةالتي تعتبربتجزأة الصوراقترحتقدالقیود،ھذهبسبب. معینسیاقفيالتطبیقات،منمعینلنوعالصورمعین من لنوعفعالةطریقةحیث أن كل جدیدةآفاقتماما الذھاب الستكشافالطبیعيفمنولذلكالصور أكدت تلك المثالب و القیود،في معالجةمختلفةاستراتیجیات

.تجزئة الصورمشكلةلحلطبیعةمن المستوحاةمناھجاستخدمتوقد. كفاءةأكثرومرونةوأكثرمتطورةأسالیبوإیجاد

باستخدامطبیعةالعملیة تجزأة صورة بإستخدام الطرق المستوحاة منتحسینھوالرسالةھذهمنالھدففإنوبالتالي،.طبیعةرزمیات التحسین المستوحات من الالموازیة لمختلف خواالتحسینتقنیات

Table des matières

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

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

Introduction générale……………………………………………………………………………….1

Chapitre 1 Les systèmes Bio-inspirés…………………………….……………………………........3

1.1 Introduction………………………………………………………………………………….……3

1.2 Définition du domaine de la Bio-inspirée……………….…………………………………..........4

1.3 Taxonomie….…………………………………………………………………...………………...4

1.3.1 Algorithmes évolutionnaires …………………………………………………………...........5

1.3.1.1 Principes d’inspiration…………………………………………………………...........5

1.3.1.2 Cycle de base d’un algorithme évolutionnaire…………………………………...........5

1.3.1.3 Principes de base………………………………………………………………………6

1.3.1.4 Variantes d’algorithmes évolutionnaires………………………………………............6

1.3.1.4 Avantages et inconvénients …………………………………………………………10

1.3.2 Intelligence en essaim………………………………………………………………………11

1.3.2.1 Principes d’inspiration………………………………………………………….........11

1.3.2.2 les principes de l’intelligence en essaim……………………………………………..11

1.3.2.3 Variantes d’algorithmes basés essaim………………………………………………..11

1.3.2.4 Avantages et inconvénients …………………………………………………….........15

1.4 Conclusion…………………………………………………………………………………........16

Chapitre 2 La segmentation d’images……………………………………………………………..17

2.1 Introduction……………………………………………………………………………………..17

2.2 Définition de l'image………………………………………………………………………........18

2.3 Image numérique………………………………………………………………………………..18

2.4 Caractéristiques d'une image numérique………………………………………………………..19

2.5 Types d’images……………………………………………...…………..………………………22

2.6 Qualité d'image numérique …………………………………………………………………..…24

2.7 Images bitmap et images vectorielles……………………………………………………….......24

2.8 Les différentes techniques de traitement d'image……………………………………………….25

2.8.1 Extraction des caractéristiques (Feature Extraction from images)………………….……...25

2.8.2 Segmentation d'image (Image Segmentation)……………………………………………...26

2.8.3 Rehaussement d'image (Image Enhancement)……………………………………………..26

2.8.4 Recalage d'image (Image Registration)…………………………………………….………27

2.9 Segmentation d’image ………………………………………………………………………….28

2.9.1 Définition de la segmentation d’image ……………………………………………….……28

2.9.2 Techniques de Segmentation ………………………………………………………………29

2.9.2.1 Approche Contour …………………………………………………………………….29

2.9.2.2 Approche région ……………………………………………………………………….32

2.9.2.2 Approche coopérative ………………………………………………………………….34

2.9.3 Segmentation par seuillage …………………………………………………………...……36

2.9.3.1 Définition du seuillage …………………………………………………………...……36

2.9.3.2 Méthodes de seuillage globale …………………………………………………...……37

2.9.3.3 Méthode de seuillage locale ou adaptatif ……………………………………...………39

2.10 Application du Bio-inspirée dans la segmentation d’image par seuillage……………...……..39

2.11 Conclusion…………………………………………………………………………...………...40

Chapitre 3 Les métaheuristiques parallèles………………………………………………………..41

3.1 Introduction………………………………………………………………………………..……41

3.2 Classification des métaheuristiques parallèles…………………………………………..….…...42

3.2.1 Classification de Crainic et Toulouse (1998)…………………………………….…….....…42

3.2.2 Classification de Cung et al. (2002) ……………………………………………..………...44

3.2.3 Classification de Cras et al. (2003)………………………………………………..…..…….44

3.3 Conception des métaheuristiques parallèles……………………………………….……..……..45

3.4 Modèles parallèles des algorithmes évolutionnaires…………………………………………….45

3.4.1 Parallèlisation globale des algorithmes évolutionnaires……………………………..…….46

3.4.2 Les approuches à gros grains (modèle des îles)……………………………………..……..48

3.4.2.1 Source d’inspiration ……………………………………………………..………..48

3.4.2.2 Le modèle d’île………………………………………………………...……….....48

3.4.2.3 Le modèle d’île généralisé...…………………………………………………...…..50

3.5 Plate-formes de métaheuristiques parallèles……………………………………………...……..53

3.6 Conclusion…………………………………………………………………………………..…..59

Chapitre 4 L’approche proposée pour la segmentation d’image par multiseuillage…………….....60

4.1 Introduction…………………………………………………………………………….….……60

4.2 Démarche de conception………………………………………………………………………....60

4.2.1 Problématique…………………………………………………………………………….…60

4.2.2 Approche proposée………………………………………………………………………….60

4.2.3 Le modèle de conception……………………………………………………………...……61

.4.2.4 L’architecture du modèle……………………………………………………………………61

4.2.5 L’implémentation……………………………………………………………………………66

4.2.6 Architecture détaillée du modèle proposé……………………..……………………………68

4.3 Conclusion………………………………………………………………………………………70

Chapitre 5 Expérimentation & validation.......................................................................................71

5.1 Introduction..................................................................................................................................71

5.2 Mesures d’évaluation de la qualité de segmentation ...................................................................71

5.3 Images de tests utilisées (Benchmarks) .......................................................................................71

5.5 Résultats et discussions................................................................................................................74

5.6 Conclusion……………………………………………………………………………………….86

Conclusion générale et perspectives………………………………………………………………87

Bibliographie………………………………………………………………………………………88

ANNEXE……………………………………………………………………………………………..94

Table des figures

Figure 1.1 Le passage d'un phénomène naturel à un algorithme inspiré de la nature......................... 4Figure 1.2 Classification de Méthodes Bio-inspirées. ........................................................................ 5Figure 1.3 Recueil de ressources par des fourmis…………………………………………………..13Figure 2.1 Image engineering et segmentation d’image ................................................................... 17Figure 2.2 Image peinture ................................................................................................................. 18Figure 2.3 Image photographique ..................................................................................................... 18Figure 2.4 Représentation d’image numérique ................................................................................. 19Figure 2.5 La lettre A affichée comme un groupe de pixels ............................................................. 19Figure 2.6 Image sans bruit ............................................................................................................... 21Figure 2.7 Image Bruitée .................................................................................................................. 21Figure 2.8 Image avec histogramme ................................................................................................. 21Figure 2.9 Contour d’une image ....................................................................................................... 22Figure 2.10 Types d’images.............................................................................................................. 24Figure 2.11 Difference entre l’image vectorielle et l’image matricielle ........................................... 24Figure 2.12 Recalage d’une image référence et d’une image source................................................ 27Figure 2.13 Techniques de segmentation d’image............................................................................ 29Figure 2.14 Processus de division de l’image I utilisant le quad-tree............................................... 33Figure 2.15 La segmentation par division / fusion............................................................................ 34Figure 2.16 Principe de la coopération séquentielle ......................................................................... 35Figure 2.17 Principe de la coopération des résultats......................................................................... 35Figure 2.18 Principe de la coopération Mutuelle ............................................................................. 35Figure 2.19 Seuillage simple d’un histogramme............................................................................... 36

Figure 2.20 Seuillage multiple d’un histogramme………………………………………………...……37

Figure 3.1 Un scénario d'exécution dans le modèle Maître/Esclave................................................. 46Figure 3.2 Le modèle Maître/Esclave ............................................................................................... 47Figure 3.3 Modèle Maître/Esclave pour un algorithme evomutionnaire parallèle .......................... 47Figure 3.4 Modèle d’île..................................................................................................................... 49Figure 3.5 Algorithme Modèle d’île ................................................................................................. 50Figure 3.6 Topologie de Migration .................................................................................................. 53Figure 3.7 Architecture DREAM ..................................................................................................... 56Figure 3.8 Architecture MAGMA…………………………………………….……….…………....57Figure 4.1 Le modèle proposé GIM .................................................................................................61Figure 4.2 Architecture détaillé du modèle……...………………………………………...………..69Figure 5.1 Image Airplane.gif avec son Histogramme………… ..………...………………………72Figure 5.2 Image Butterfly.gif avec son Histogramme..................................................................... 72Figure 5.3 Image Hunter.gif avec son Histogramme ........................................................................ 73Figure 5.4 Image Map.gif avec son Histogramme............................................................................ 73Figure 5.5 Image Road.gif avec son Histogramme........................................................................... 74Figure 5.6 Image Airplane segmenté par GIM_PSO_ABC_GA ...................................................... 80

Figure 5.7 Image Hunter segmenté par GIM_PSO_ABC_GA......................................................... 81Figure 5.8 Image Butterfly segmenté par GIM_PSO_ABC_GA...................................................... 82Figure 5.9 Image Map segmenté par GIM_PSO_ABC_GA............................................................. 83Figure 5.10 Image Road segmenté par GIM_PSO_ABC_GA.......................................................... 84Figure 5.11 Différentes valeurs de STD pour les différents algorithmes face à différents cas de test(pour chaque cas de test, 2, 3, 4, 5 seuils, respectivement)………………………………………….83

Table des tableaux

Tableau 3.1 : Taxonomie des Plates-formes de métaheuristiques parallèles………………………54Tableau 4.1 : Les paramètres du modèle…………………………………………………………...62Tableau 5.1: Moyenne ± écart-type valeurs de fitness de différentes méthodes pour différents casde test……………………………………………………………………………………………….76Tableau 5.2: Moyenne ± écart-type valeurs de fitness de différentes méthodes pour différents cas detest…………………………………………………………………………………………………..77Tableau 5.3 : Moyenne de meilleurs seuils optimaux de différents algorithmes de segmentation....78Tableau 5.4 : Moyenne de meilleurs seuils optimaux de différents algorithmes de segmentation....79

1

Introduction générale

Le traitement d'images est l'ensemble des méthodes et techniques utilisées pouraméliorer le contenu d’une image pour en extraire de l’information, par exemple identifierune séquence de texte ou un chromosome, éviter un obstacle (robotique), ou détecter deszones soumises à l’érosion (télédétection). Les techniques les plus connus utilisées pour letraitement d’images sont : extraction des caractéristiques de l’image, la segmentation d’image,le rehaussement d’image (amélioration de la qualité d’image) et le recalage d'image.

La segmentation d’image est l’opération la plus importante dans un système detraitement d’images, car elle est située à l’articulation entre le traitement et l’analyse desimages. L’intérêt de la segmentation est de partitionner une image en plusieurs régionshomogènes, au sens d’un critère fixé a priori. L’intérêt de disposer de régions homogènes estde fournir des données simplifiées qui facilitent la tâche d’un système de reconnaissance deformes, ou autre système d’extraction des objets contenus dans l’image.

Les techniques de segmentation d’image sont généralement fondées sur la recherchedes discontinuités locales (détection de contours) ou la détection de zones de l’imageprésentant des caractéristiques d’homogénéité (extraction de régions). Une autre approche,appelée approche coopérative, consiste en une coopération entre ces deux approches.

Nous considérons que le problème de la segmentation d’image est un cas particulier duproblème de partitionnement des données. Ce dernier étant un problème NP-difficile. Cesproblèmes peuvent être exprimés sous la forme générale d’un problème d’optimisation.

Jusqu’à ce jour, il n’existe pas de méthode universelle de segmentation d’images.Toute technique n’est efficace que pour un type d’images donné, pour un type d’applicationsdonné, et dans un contexte informatique donné. En raison de ces contraintes, plusieursstratégies de segmentation ont été proposées.

Afin d’améliorer les résultats de segmentation, des méthodes bio-inspirés ou inspiréesde la nature ont été alors utilisées pour résoudre le problème posé. Depuis quelques années,les chercheurs informaticiens ont trouvé dans le monde naturel, une source d’inspirationinépuisable pour la conception de nouveaux systèmes informatiques. Il s’agit de puiser dansles comportements des êtres naturels de nouvelles approches pour la résolution de problèmesdifficiles. Le rôle de l’informaticien est d’observer et comprendre les mécanismes etprocessus qui régissent les comportements dits « intelligents » de ces individus pour larésolution des problèmes courants, puis extraire à partir de ces études des modèlesimplantables sur des machines dont les résultats pourront être validés par rapport à ceuxobservés dans la nature.

Le problème de segmentation d’image est de type NP-difficile, signifiant qu’il n’existepas d’algorithmes produisant une solution optimale en un temps d’exécution polynômial parrapport à la taille des données manipulées. Leur résolution est donc toujours limitée par lacapacité des ressources matérielles utilisées (puissance de calcul, mémoire, etc.).

2

Même si les méthodes bio-inspirés offrent des stratégies efficaces pour la recherche desolutions de problèmes de segmentation d’image, les temps de calcul associés à l’explorationde l’espace de recherche peuvent être très importants et aussi le risque de rester bloquer auniveau des minimums locaux. Une façon d’éviter ces problèmes est l’utilisation de lacoopération des métaheuristiques parallèles.

Nous proposons dans ce mémoire une nouvelle approche pour la segmentationd’image par multiseuillage utilisant le modèle d’île généralisé. Ce dernier est un modèle quipermet d’utiliser différents types d’algorithmes, les exécuter en parallèle sur des îles àcondition que les îles aient le même type de codage de solutions. L’exécution de l’ensembledes îles est effectuée en parallèle, et le résultat final de l’optimisation est la meilleure solutiontrouvé sur toutes les îles.

Par voie de conséquence, le mémoire est organisé en cinq chapitres :

Le premier chapitre s’intéresse au domaine bio-inspiré et passe en revue les différentsalgorithmes inhérents à ce domaine.

Dans le deuxième chapitre, nous introduisons brièvement le domaine du traitementd’images. Une synthèse bibliographique sur les différentes approches de segmentationd’images est présentée.

Le troisième chapitre est consacré à la présentation des métaheuristiques parallèles.Dans ce chapitre, nous commençons par introduire les métaheuristiques parallèles pourterminer par les plates-formes supportant les métaheuristiques parallèles.

Le quatrième chapitre est dédié au vif du sujet à savoir la conception de notreapproche pour la segmentation des images.

Le cinquième chapitre est la partie tests et résultats ou nous montrons l’apport de notreapproche.

Une conclusion générale et des perspectives viennent alors clôturer ce modeste travailde Magister.

3

CHAPITRE 1: LES SYSTEMES BIO-INSPIRES

1.1 Introduction

La nature est une source puissante d’inspiration pour résoudre des problèmescomplexes en informatique, puisqu'elle montre des phénomènes extrêmement divers,dynamiques, robustes, complexes et fascinants. Elle trouve toujours la solution optimale pourrésoudre son problème, et maintien l'équilibre parfait entre ses composantes. Nouvelle ère estouverte avec les algorithmes inspirés de la nature (Bio-inspiré) qui sont des métaheuristiquesimitant la nature pour résoudre des problèmes d'optimisation. Dans les décennies passées, denombreux efforts de recherches ont été concentrés dans ce secteur particulier. Ce chapitreprésente une vue d’ensemble sur les algorithmes inspirés de la nature, groupés par le champbiologique qui a inspiré chacun d’eux.

Pourquoi le bio-inspiré

La nature avec ses phénomènes extraordinaires nous fournit des solutions grâce à descaractéristiques telles que :

Emergence : les éléments simples qui interagissent vont accomplir des tachesextraordinaires.

La simplicité de la mise en œuvre. L’auto-organisation : l’organisation interne du système se structure

automatiquement sans être dirigée par une source extérieure. La modularité : le système est composé d’éléments simples qui coopèrent ensemble

pour atteindre l’objectif global. Le système est donc évolutif. La décentralisation : ceci garantit un système robuste, capable de continuer à

fonctionner en cas de défaillance d’un de ses composants. La réactivité : les éléments du système coopèrent et communiquent entre eux via des

interactions locales. Ils sont capables de réagir instantanément aux changementsd’environnement.

L’auto-adaptation : l’aptitude d'un système à modifier ses paramètres de manière queson fonctionnement demeure satisfaisant en dépit des variations de sonenvironnement.

Les algorithmes d’optimisation inspirés de la nature peuvent être déterministes oustochastiques (probabiliste). Les méthodes formelles qui ont été utilisées pour résoudre desproblèmes d'optimisation exigent d’énormes efforts de calcul, qui tendent à échouer avecl’augmentation de la taille des problèmes. C'est la motivation pour utiliser les algorithmesd'optimisation bio-inspirés en tant qu’une solution informatique efficace à la place desapproches déterministes.

Les métaheuristiques sont basées sur l'amélioration itérative d'une population dessolutions (comme dans le cas des algorithmes évolutionnaires, des algorithmes basés essaim)

4

ou d'une solution simple (par exemple recherche Tabou) et utilisent la plupart du temps larandomisation et la recherche locale pour résoudre un problème d'optimisation donné.

1.2 Définition du domaine bio-inspiré Processus de création d’un algorithme inspiré de la nature : Tout d'abord, la nature

donne l’inspiration aux chercheurs de développer une observation d’un phénomènenaturel particulier. Premièrement, Les développeurs créent et testent un modèle,utilisent des simulations mathématiques qui aident à raffiner le modèle original.Ensuite, le modèle raffiné sera utilisé pour extraire une métaheuristique qui peut êtreutilisée comme une base pour finalement concevoir un algorithme inspiré de la nature.La Figure 1.1 illustre le cadre utilisé pour passer d'un phénomène naturel à unalgorithme inspiré de la nature.

1.3 Taxonomie

Les plus prédominantes classes des algorithmes bio-inspirés sont les algorithmesévolutionnaires (inspirés de la sélection naturelle) et les algorithmes basés essaim (inspirés ducomportement collectif chez les animaux). La figure 1.2 illustre ces deux classes du domainebio-inspiré.

Figure 1.1 Passage d'un phénomène naturel à un algorithme inspiré de la nature [Ahmed, 12].

5

1.3.1 Algorithmes évolutionnaires

1.3.1.1 Principe d’inspiration

Les Algorithmes Evolutionnaires (appelés aussi les Algorithmes Evolutionnistes)(Evolutionary Algorithms en anglais), sont une famille d'algorithmes s'inspirant de lathéorie de l'évolution pour résoudre plusieurs problèmes connus dans le domained’informatique. Ils font ainsi évoluer un ensemble de solutions à un problème donné, dansle but de trouver de meilleurs résultats. Ce sont des algorithmes stochastiques, car ilsutilisent itérativement des processus aléatoires. La grande majorité de ces méthodes sontutilisée pour résoudre des problèmes d'optimisation.

1.3.1.2 Cycle de base d’un algorithme évolutionnaire

Pour se faire, on utilise l'algorithme général suivant:1-Construction et évaluation d'une population initiale ;2-Jusqu'à atteindre un critère d'arrêt :

3-Sélection d'une partie de la population,4-Reproduction des individus sélectionnés,5-Mutation de la descendance,6-Evaluation du degré d'adaptation de chaque individu,7-Remplacement de la population initiale par une nouvelle population.

Figure 1.2 Classification de Méthodes bio-inspirées.

Bio-inspiré

AlgorithmesBasée Essaim

L’optimisation par essaimde particules

Les Colonies de FourmisArtificielles

Optimisation par lacolonie d’abeilles

La méthode Recherchecoucou

AlgorithmesEvolutionnaires

Algorithmes génétiques

Programmationgénétiques

Stratégies d’évolution

Evolutions différentiel

6

Après avoir initialisé une première population d'individus, on itère un nombre fini defois, jusqu'à atteindre un critère d'arrêt (par exemple, un nombre maximum de générations).La première étape de sélection permet de séparer les individus qui participeront à lareproduction de ceux qui n'y participeront pas. Les individus sélectionnés (les « parents ») sereproduisent (on dit aussi que l'on effectue des croisements), donnant un ensemble d'«enfants»partageant une partie des caractéristiques de leurs ascendants. Ces enfants subissent alors uneétape de mutation qui modifie aléatoirement leur génotype. Les nouveaux individus sont alorsévalués (on met à jour leur valeur en faisant appel à la fonction objectif). Enfin, on choisit unnombre d'individus déterminé parmi l'ensemble parents plus leurs enfants, pour former lagénération suivante.

1.3.1.3 Principes de base

Ces algorithmes manipulent des populations de solutions. Les algorithmesévolutionnaires s'inspirent de l'évolution des êtres vivants, en considérant que celle-ci tend àproduire des organismes plus adaptés à leur environnement. Selon la théorie de l'évolution,plusieurs mécanismes sont à l'œuvre pour se faire. Schématiquement :

Les caractéristiques d'un organisme sont en grande partie codées dans ses gènes, Chaque population d'organismes est composée d'individus tous différents, Les différences entre individus leur confèrent une adaptation plus ou moins grande à

leur environnement, Les organismes transmettent une partie de leurs caractéristiques à leurs descendants, Les individus les plus adaptés se reproduisent plus « efficacement ». Leurscaractéristiques ont donc tendance à davantage se répandre dans la population.

Tous les algorithmes évolutionnaires font évoluer un ensemble (une « population ») desolutions (les « individus »). Les individus sont représentés par leur génotype, qui s'exprimesous la forme d'un phénotype, auxquels on associe une qualité (la « fitness »). Les algorithmessont conçus de façon à ce que plus la fitness d'un individu est élevée, plus il doit avoir dechances de transmettre son génotype au sein de la population.

À chaque étape de l'algorithme est associé un «opérateur», qui décrit la façon demanipuler les individus. On regroupe parfois les différents opérateurs sous des termesgénériques :

Opérateurs de sélection pour la sélection et le remplacement. Opérateurs de variation pour la mutation et le croisement.

1.3.1.4 Variantes d’algorithmes évolutionnaires

Les plus connus sont :

Algorithmes génétiques (Genetic Algorithms en Anglais), Programmation génétiques (Genetic Programming en Anglais), Stratégies évolutionnaire (Evolutionary Strategy en Anglais),

7

Évolutions différentielle (Differential Evolution en Anglais).

A. Algorithmes génétiques

Définition : les algorithmes génétiques (AG) sont des algorithmes d’optimisationsstochastiques fondées sur les mécanismes de la sélection naturelle et de la génétique.Ils ont été initialement développés par John Holland (1975) [Holland, 75].

Source d’inspiration : les AGs s’inspirent des mécanismes de l’évolution biologiquepour les transposer à la recherche de solutions adaptées au problème qu’on cherche àrésoudre. L’évolution biologique procède en sélectionnant des génotypes (intégrés auxchromosomes), sur la base de l’adaptation relative à leur environnement desphénotypes qu’ils génèrent (la qualité de cette adaptation est mesurée par laperformance - fitness - relative de chaque génotype). Les génotypes qui sont les mieuxadaptés à leur environnement ont une plus grande facilité à se reproduire et lareproduction (croisement) assure le croisement des gènes les plus performants dans lapopulation.

Présentation de l’algorithme génétique (AG) : un algorithme génétique implémenteune version très simplifiée et très schématique des mécanismes de l’évolutionbiologique. A` partir d’un problème qu’on cherche à résoudre, un algorithmegénétique est défini, selon Lerman et Ngouenet (1995) [Lerman, 95], par quatreéléments de base suivants: Individu/chromosome/séquence : une solution potentielle du problème qui

correspond à une valeur codée de la variable (ou des variables) en considération; Population : un ensemble de chromosomes ou de points de l’espace de

recherche (donc des valeurs codées des variables); Environnement : l’espace de recherche (caractérisé en termes de performance

correspondant à chaque individu possible); Fonction de performance(fitness) : la fonction - positive - que nous cherchons

à maximiser, car elle représente l’adaptation de l’individu à son environnement.

L’avantage des AGs est leur simplicité. Néanmoins, les AGs seuls ne sont pas trèsefficaces dans la résolution d'un problème. Cependant, ils apportent une solution acceptableassez rapidement. Sa combinaison avec un algorithme déterministe peut améliorer la solutiond’une manière assez efficace.

B. Programmation génétiques

Définition : la programmation génétiques PG est une branche récente mise au goût dujour par John Koza [Koza, 90]. La PG se classe dans la grande famille des algorithmesévolutionnaires qui s'inspire du paradigme de l'évolution darwinienne afin de faireévoluer des populations de solutions potentielles. Elle a pour but de trouver desprogrammes qui répondent au mieux à une tâche définie. Pour se faire, elle permet à lamachine d'apprendre, en utilisant un algorithme évolutionniste afin d’optimiser lapopulation de programmes. Koza a défini un paradigme standard [Koza, 92]. Ce

8

paradigme inclut plusieurs concepts : programmation structurée en expressionarborescentes, définition d’une grammaire de langage, type de retour unique pourchaque fonction, définition des proportions de mutation et de croisement pour chaquegénération, etc.

Principes de base : l'algorithme consiste à faire évoluer une population constituéed'un grand nombre de programmes. Au départ, la population est constituée deprogrammes créés aléatoirement. Chaque programme est évalué selonune méthode propre au problème posé. A` chaque itération (génération) on classe lesprogrammes en fonction des notes qu'ils ont obtenues, et on crée une nouvellepopulation, où les meilleurs programmes auront une plus grande chance de survivreou d'avoir des enfants que les autres. Ce principe est le même qu'en algorithmegénétique classique, mais les opérateurs de croisement et de mutation sont un peudifférents. En effet, ils travaillent directement sur la structure d'arbre du programme.

Voici un algorithme synthétique pour la PG :

1. Génération aléatoire de la population (1 individu = 1 programme)2. Évaluation du fitness de chacun des individus de la population

(Évaluation de l'adéquation des programmes au problème à résoudre)

3. Application des opérateurs de croisement, mutation, reproduction sur lapopulation afin de créer une nouvelle population

4. Sélection des individus les mieux adaptés5. Répéter les étapes 2 et 3 un certain nombre de fois

La première étape algorithmique du processus de programmation génétique consiste àgénérer une population d'individus (un individu=un arbre=un programme). Unepopulation est généralement constituée de plusieurs milliers de programmes quicoexistent.

L'étape suivante consistera à évaluer la performance de chacun des programmesgénérés aléatoirement afin de leur donner une valeur de fitness.

Chaque arbre généré est susceptible d'être croisé avec d'autres arbres afin de générerd'autres possibilités.

La supposition très importante de la programmation génétique est la suivante : des S-expressions de petite taille et de fitness élevé vont se recombiner afin de donner des S-expressions plus complexes et de fitness encore plus élevé.

La méthode PG est très efficace dans certains domaines où aucune autre méthode ne peutfournir de bons résultats. Néanmoins, son paramétrage est très délicat et des paramètres tropmoyens peuvent mener à une très mauvaise solution.

C. Stratégies d’évolution

La Stratégie d'évolution a été développée par trois étudiants (Bienert, Rechenberg,Schwefel) à l'université technique de Berlin en 1964 [Beyer, 02]. Elle est, à ce titre, lapremière véritable métaheuristique et le premier algorithme évolutionnaire, bien avant

9

les algorithmes génétiques. La méthode fut ensuite développée durant la fin des années1960, principalement par les travaux de IngoRechenberg, P. Bienert et Hans-PaulSchwefel sur la conception de profils aérodynamiques1.

Appliqué à l’optimisation numérique, l'algorithme manipule itérativement unensemble de vecteurs de variables réelles, à l'aide d'opérateurs de mutation et desélection.

L'étape de mutation est classiquement effectuée par l'ajout d'une valeur aléatoire,tirée au sein d'une distribution normale.

La sélection s'effectue par un choix déterministe des meilleurs individus, selonl'échelle de valeur de la fonction objectif.

Principes de base :

Représentation est faite par un Vecteur de valeurs réelles Mutation : par une perturbation Gaussienne. La sélection des parents : utilise une probabilité uniforme. La sélection de

survie : on distingue trois modes qui sont : (1 + 1)-ES. La stratégie la plus simple l’évolution fonctionne sur une

population de taille deux: le point courant (parent) et le résultat de samutation. si la fitness fils>parents, il devient le parent de la prochainegénération. Sinon, le mutant est ignoré.

(,) – ES: avec >= les meilleure formant la nouvelle génération.

(+) – ES: après Union (,), les meilleures parant restent pour lagénération suivante.

Algorithme (,)-ES

Les stratégies d'évolutions utilisent un ensemble de µ « parents » pour produire λ« enfants ».

Pour produire chaque enfant, ρ parents se « recombinent ». Une itération del'algorithme général procède comme suit:

1. À partir d'un ensemble de µ parents, produire une population de λ enfants :

1. choisir ρ parents,

2. recombiner ces parents entre eux pour former un unique individu,

3. faire muter cet individu,

3. sélectionner les meilleurs individus.

1 [Wikipedia1] http://fr.wikipedia.org/wiki/Stratégie_d'évolution

10

D. Evolutions Différentielle

C’est une méthode proposée par Storn & Price en 1995 [Storn, 97], basé sur leprincipe de l’évolution naturelle. L'évolution différentielle est une méthode utilisée pourl'optimisation mathématique des fonctions multidimensionnelles. Elle est très utilelorsque les paramètres ne peuvent pas être codés comme des vecteurs réels.

Principes de base

L'idée principale derrière l'évolution différentielle est l'utilisation d'un opérateurde recombinaison ternaire pour la création de nouvelles générations. La création d’unnouvel individu consiste à ajouter la différence entre deux individus à un troisième.Depuis le modèle de base, cette méthode a beaucoup évoluéeet plusieurs améliorationsont été proposées.

Les principales différences entre l’algorithme génétique et l’évolutiondifférentielle sont :

L’opérateur de Mutation est le résultat d’une petite perturbation dans les gènes duchromosome (individus), par contre dans la méthode Evolution Différentielle laMutation est le résultat d’une combinaison arithmétique des individus.

Au démarrage du processus d’évolution, l’opérateur de Mutation favorisel’exploration, et dans la progression d’évolution l’opérateur de Mutation favorisel’exploitation.

Avantage

Elle est facile à implémenter, ne demande pas beaucoup de paramètres de réglage.

Montre une convergence rapide. Elle est considérée en générale comme une technique d’optimisation Robuste, exacte

(précis), fiable.

Limite

Le bruit peut affecter la performance de la méthode due à sa nature gourmande. L’utilisateur doit trouver les meilleures valeurs des paramètres de contrôle au

problème en question.

1.3.1.5 Avantages et inconvénients

Les algorithmes évolutionnaires travaillent sur une population de solutions potentiellesce qui leurs permettent d’explorer plusieurs zones de l’espace des configurations à la fois.Elles développent ainsi une sorte de parallélisme implicite, qui l’en fait des méthodesparticulièrement adaptées à une implémentation sur ordinateurs parallèles. A cela s’ajoutel’innovation produite par les opérateurs de croisement et de mutation, qui permettent d’éviter

11

de se focaliser sur un extremum local. Ces algorithmes sont relativement simples à mettre enœuvre, et ne nécessitent pour fonctionner que la connaissance des valeurs prises par lafonction d’adaptation en différents points. Aucune caractéristique telle que la continuité, ladérivabilité, la convexité,… n’est requise pour cette fonction. Les Algorithmesévolutionnaires apparaissent donc comme particulièrement robustes et polyvalents.Cependant, comme toute méthode, elles présentent aussi des défauts. Tout d’abord, elles nefournissent aucune garantie quant à la qualité des solutions obtenues. En outre, elles sontgénéralement de gros consommateurs de temps de calcul, d’où l’intérêt d’une implémentationsur ordinateurs parallèles. Pour améliorer leurs performances, il est souvent intéressant de leshybrider avec d’autres méthodes d’optimisation (méthode tabou,…).

1.3.2 Intelligence en essaim

1.3.2.1 Source d’inspiration

L'intelligence en essaim (Swarm Intelligence en Anglais) est le comportement collectifdécentralisées, auto-organisés des systèmes naturels ou artificiels. Le concept est employédans les travaux sur l'intelligence artificielle. L'expression a été introduite par Gerardo Beni etJing Wang en 1989, dans le cadre de systèmes robotiques cellulaires.

La source d’inspiration de cette approche vient de l’observation du comportement desinsectes sociaux: une population d’agents extrêmement simples, interagissant etcommuniquant indirectement à travers leur environnement, constitue un algorithmemassivement parallèle pour résoudre une tâche donnée (par exemple le fourragementl’attroupement ou flocking, la division de tâches, la capture de proies…) [Boumaza, 08].

1.3.2.2 Les principes de l’intelligence en essaim

Les algorithmes basé essaim sont généralement constitués d'une population de simplesagents ou boids qui interagissent localement les uns avec les autres et avec leurenvironnement. L'inspiration vient souvent de la nature, en particulier les systèmesbiologiques. Les agents suivent des règles très simples, et bien qu'il n'y ait pas de structure decontrôle centralisé qui dicte la façon dont les agents individuels devraient se comporterlocalement. En Inspirant de la nature, des algorithmes basé essaim incluent les colonies defourmis, oiseaux flocage, la croissance bactérienne et les poissons de scolarisation.L'application des principes essaim au robots est appelée essaim robotique, tandis que «l'intelligence en essaim » fait référence à l'ensemble plus général des algorithmes. « PredictionSwarm » a été utilisée dans le cadre des problèmes de prévision.

1.3.2.3 Variantes d’algorithmes basés essaim

A. Optimisation par essaim particulaire

Introduction: L'optimisation par essaim particulaire OEP (Particle SwarmOptimization en anglais) est une métaheuristique d'optimisation, inventée par RusselEberhart (ingénieur en électricité) et James Kennedy (socio-psychologue) en 1995

12

[Kennedy, 95 ; Eberhart, 95]. Elle s'appuie notamment sur un modèle développé parCraig Reynolds à la fin des années 1980, permettant de simuler le déplacement d'ungroupe d'oiseaux. Une autre source d'inspiration, revendiquée par les auteurs, est lasocio-psychologie. Cette méthode d'optimisation se base sur la collaboration desindividus entre eux. Elle a d'ailleurs des similarités avec les algorithmes de colonies defourmis, qui s'appuient eux aussi sur le concept d'auto-organisation. Cette idée veutqu'un groupe d'individus peu intelligents puisse posséder une organisation globalecomplexe.

Ainsi, grâce à des règles de déplacement très simples (dans l'espace dessolutions), les particules peuvent converger progressivement vers un minimum local.Cette métaheuristique semble cependant mieux fonctionner pour des espaces envariables continues. Ce comportement social basé sur l’analyse de l’environnement etdu voisinage constitue alors une méthode de recherche d’optimum par l’observationdes tendances des individus voisins. Chaque individu cherche à optimiser ses chancesen suivant une tendance qu’il modère par ces propres vécus [Calas, 09].

Présentation de la méthode : L’optimisation par essaim de particules repose sur unensemble d’individus originalement disposé de façon aléatoire et homogène, que nousappellerons dés lors des particules, qui se déplacent dans l’hyper-espace de rechercheet constituent, chacune, une solution potentielle. Chaque particule dispose d’unemémoire concernant sa meilleure solution visitée ainsi que la capacité decommuniquer avec les particules constituant son entourage. A partir de cesinformations, la particule va suivre une tendance faite, d’une part, de sa volonté àretourner vers sa solution optimale, et d’autre part, de son mimétisme par rapport auxsolutions trouvées dans son voisinage. A partir d’optimums locaux et empiriques,l’ensemble des particules va, normalement, converger vers la solution optimaleglobale du problème traité.

Les points forts et Limites :

Les points forts :

OEP utilise la mémoire pour stoker l’historique de la meilleure position locale etla meilleure position globale des essaims, qui aide non seulement chaqueparticule pour sauvegarder leur expérience locale, mais aussi pour aident lesautres particules de communiquer par leur expérience social entre eux, ce quipermet de converger vers les régions les plus prometteuses dans l’espace derecherche, et accélère le processus d’optimisation vers la solution optimal.

la simplicité de l’algorithme.

Les limitations de OEP

L'original OEP suppose que toutes les particules de l'essaim entier sonttotalement homogènes, et emploie donc les mêmes configurations de valeur demasse d'inertie, les paramètres cognitifs et sociaux (C1 et C2) pour l'essaimentier. Cette hypothèse, cependant, ignore les différences internes entre les

13

oiseaux de l'essaim même dans la vraie vie, comme les âges, les expériences devol, et les étirements des muscles.

L'original OEP ne parvient pas à localiser plusieurs optima, puisque l'idée del'original OEP était d'ajuster la direction essaim près de l'essaim meilleureglobale particule de guider l'essaim entier de converger vers un optimum unique.Cependant, de nombreuses variantes de l'original PSO ont été proposées dans lalittérature pour surmonter cette limitation.

B. Algorithme de colonies de fourmis

Présentation des algorithmes de fourmis : optimisation par colonie de fourmis(AntColonyOptimization ACO en Anglais) est un algorithme d'optimisation inspiré dela nature [Dorigo, 04 ; Dorigo, 07], qui est motivé par le comportement naturel derecherche de nourriture des espèces de fourmis. Son principe repose sur lecomportement particulier des fourmis qui, lorsqu’elles quittent leur fourmilière pourexplorer leur environnement à la recherche de nourriture, finissent par élaborer deschemins qui s’avèrent fréquemment être les plus courts pour aller de la fourmilière àune source de nourriture intéressante. Chaque fourmi laisse en effet derrière elle unetraînée de phéromone à l’attention de ses congénères; les fourmis choisissant avec uneplus grande probabilité les chemins contenant les plus fortes concentrations dephéromones. Il se forme ainsi ces « autoroutes » de fourmis, qui sillonnent le paysage.Ce mode de communication particulier, qui fait intervenir des modifications dansl’environnement, est appelé stigmergie.

Figure 1.3 Recueil de ressources par des fourmis.

Principe de l’algorithme : Le premier algorithme conçu selon ce modèle était destinéà résoudre le problème du voyageur de commerce. Le principe consiste à « lancer »des fourmis, et à les laisser élaborer pas à pas la solution, en allant d’une ville àl’autre. Au début, plusieurs chemins de longueurs différentes sont possibles, et lesfourmis les empruntent tous en s’orientant au hasard. Ce faisant, elles laissent derrièreelles des traces de phéromones. Sachant que ces traces s’évaporent petit à petit, et quele chemin le plus court permet par définition un plus grand nombre d’aller-retour. Lestraces de phéromone se concentrent assez rapidement sur l’itinéraire optimal. C’estdonc un algorithme qui repose sur la construction progressive de solutions, un peucomme dans la méthode GRASP (pour Greedy Randomized Adaptive Search

13







13







14

Procedure en Anglais), qui inclut également une phase de construction. Afin de ne pasrevenir sur ses pas, une fourmi tient à jour une liste Tabou, qui contient la liste desvilles déjà visitées.

Avantages et Inconvénients :

L’algorithme de colonies de fourmis offre beaucoup de souplesse, et il estpossible de l’adapter à tous les grands problèmes combinatoires classiques. Parailleurs, l’algorithme de colonies de fourmis se parallélise de façon très naturelle, enaffectant par exemple un processus différent pour traiter la marche de chaque fourmi,et un autre pour mettre à jour les pistes de phéromones. L’algorithme, de par sondynamisme intrinsèque, s’adapte aussi très bien aux espaces de solutions qui varientdynamiquement dans le temps. Malgré ces avantages, il comporte certaines limites.Par exemple, il ne fonctionne pas bien quand un grand nombre d'arcs sur le graphe deconstruction font partie des bons chemins qui ont des valeurs de probabilité égale.

C. La colonie d’abeille artificielle

Définition : l’algorithme de colonie d’abeille artificielle (Artificial Bee Colony ABCen Anglais) est l’un des plus récemment introduit dans la base des Algorithmes basésessaim. ABC simule le comportement intelligent de recherche de nourriture d’unessaim d’abeilles. L’algorithme de colonie d’abeille artificielle a été introduit parKaraboga [Karaboga, 05].

Principes de base : chaque solution représente une position de nourriture potentielledans l’espace de recherche et la qualité de la solution correspond à la qualité de laposition alimentaire. Agents (abeilles artificielles) recherche à exploiter les sources denourriture dans l’espace de recherche.

L’ABC utilise trois types d’agents : les abeilles employés (Employed Bee enAnglais), les abeilles spectateur (Onlookers Bee en Anglais), et les scouts (Scouts Beeen Anglais). Les abeilles employées (AE) sont associés à des solutions actuelles del’algorithme. À chaque étape de l’algorithme un AE tente d’améliorer la solution, il lareprésente en utilisant une étape de recherche locale, après il va essayer de recruter desabeilles spectateur (AS) pour sa position actuelle. Les ASs choisissent parmi les postespromus en fonction de leur qualité, ce qui signifie que de meilleures solutionsattireront plus d’AS. Une fois un AS a choisi un AE et donc une solution, il cherche àoptimiser la position de l’AE par une étape de recherche locale. AE mise à jour saposition si un AS recruté était en mesure de repérer une meilleure position, sinon ilreste sur sa position actuelle. En outre, un AE va abandonner sa position si elle n’étaitpas en mesure d’améliorer sa position pour certain nombre d’étapes. Quand une AEabandonne sa position, il devient une Abeille éclaireuse, ce qui signifie qu’ellesélectionne une position aléatoire dans l’espace de recherche et devienne une Abeilleemployée à cette position.

15

Avantages : l’algorithme de la colonie d’abeille artificiel présente les avantages d'unegrande robustesse, une convergence rapide, une grande flexibilité et moins deparamètres de contrôle [Balasubramani, 13].

D. La recherche Coucou

Principes : l’algorithme de la recherche coucou est un algorithme d’optimisationrécent, inspiré par le parasitisme des oiseaux coucous en pondant leurs œufs dans lesnids des autres oiseaux (d'autres espèces) créer par Yang et Deb [Yang, 09 ; Yang,10].

La méthode de recherche coucou (Cuckoo Search CS en Anglais) s'appuie surla stratégie agressive de reproduction Coucou complétée par un comportement Lévyflights dans les habitudes alimentaires des autres espèces. Ce faisant, il vise à« l'élevage » des solutions de haute qualité pour le problème d'optimisation proche.Par conséquent, il utilise deux mécanismes fondamentaux: l'intensification, en seréférant à l'exploitation dans le voisinage de la meilleure solution trouvée à ce jour, etde la diversification, en se référant à une exploration efficace de l'ensemble dudomaine de recherche.

Dans la recherche de coucou, un " œuf " se réfère à une solution du problèmed'optimisation à portée de main. Un « œuf coucou » se réfère à une solution vientd'être généré, et un «nid» signifie un ensemble de solutions possibles. Le nombre denids d'oiseaux hôtes est fixé à N. En général, un nid peut contenir plusieurs ovules.Cependant, la mise en œuvre des auteurs utilise un œuf par nid seulement. L'idéederrière CS est de générer de nouvelles (peut-être) trouvé de meilleures solutions pourremplacer des solutions moins bonnes dans le nid.CS suit trois règles de base:

1. Chaque coucou pond un œuf à la fois et le place dans un nid choisi au hasard.Cette intensification se fait en avançant une solution au moyen d'une marchealéatoire locale dans laquelle la longueur de pas est tirée d'une distribution(queue lourde) Lévy. Cela s'avère être plus efficace que les longueurs des pasordinaires gaussiennes.

2. Les œufs de haute qualité sont reportés à la prochaine itération (la survie du plusfort).

3. Un oiseau hôte découvre un œuf de coucou avec une probabilité p. Il jette l'œufsoit loin du coucou ou abandonne ses nids d'en construire une nouvelle ailleurs.Cette diversification se fait à faire en sorte que l'algorithme n'est pas piégé dansun minimum local.

Avantage : Un avantage important de cet algorithme est sa simplicité. En fait, lacomparaison avec d'autres méta heuristiques basé population tels que l'optimisationpar essaim de particules et de recherche de l'harmonie, il ya essentiellement un seulP(A) de paramètre dans CS (en dehors de la taille de la population n). Par conséquent,il est très facile à mettre en œuvre.

16

2.3.2.4 Avantage et inconvénients

En raison de ses nombreux avantages, intelligence en essaim est aujourd'huiconsidérée comme l'une des techniques d'intelligence Artificielle les plus prometteuse.

Avantage :

Évolutivité : les systèmes intelligence basés essaim sont hautement évolutive ; leurscapacités impressionnantes sont généralement maintenues lors de l'utilisation desgroupes allant de petit nombre d'individus à des millions d’individus.

Capacité d'adaptation : intelligence en essaim répondent bien à l'évolution rapide del’environnement, faisant usage de leurs capacités hérité d'auto-configuration et d'auto-organisation. Cela leur permet de s'adapter de manière autonome le comportement deleurs individus à l'environnement externe de façon dynamique sur la durée, avec unegrande souplesse.

Robustesse collective : les systèmes d’Intelligence en essaim sont robustes car ilstravaillent ensemble sans contrôle central, et il n'ya pas un seul individu crucial pourl'essaim de continuer à fonctionner.

Simplicité individuel : les systèmes d’Intelligence en essaim se composent d'uncertain nombre d'individus simples avec des possibilités assez limitées sur leurspropres comportements, pourtant il est pratiquement suffisant d’émerger à uncomportement sophistiqué.

Limitations

Application en temps réel : ils ne sont pas appropriés aux applications temps-réel. Stagnation : en raison du manque de coordination centrale, les systèmes de SI

pourraient souffrir d'une situation de stagnation ou d'une convergence prématurée àun optimum local.

2.3 Conclusion

Dans ce chapitre, nous avons dressé un état de l’art sur les méthodes d’optimisationbio-inspirés. Ces dernières sont divisées en deux classes : les algorithmes évolutionnaires quis'inspirent de la théorie de l'évolution pour résoudre des problèmes divers utilisentitérativement des processus aléatoires (stochastiques) et les algorithmes basé essaim inspirantdu comportement collectif décentralisées, auto-organisés des systèmes naturels où une populationd’agents extrêmement simples, interagissant et communiquant indirectement à travers leurenvironnement, constitue un algorithme massivement parallèle pour résoudre une tâche donnée.

17

CHAPITRE 2 : LA SEGMENTATION D’IMAGES

2.1 Introduction

L’image constitue l'un des moyens les plus importants qu'utilise l'homme pourcommuniquer avec autrui. C'est un moyen de communication universel dont la richesse ducontenu permet aux êtres humains de tout âge et de toute culture de se comprendre. C'est aussile moyen le plus efficace pour communiquer, chacun peut analyser l'image à sa manière, pouren dégager une impression et d'en extraire des informations précises. De ce fait, le traitementd'image est l'ensemble des méthodes et techniques opérant sur celles-ci, dans le but de rendrecette opération possible, plus simple, plus efficace et plus agréable, d'améliorer l'aspect visuelde l'image et d'en extraire des informations jugées pertinentes.

On peut regrouper les opérations sur l'image sous un Framework « image engineering(IE) », qui se compose de trois couches [Zhang, 02]: traitement d'image (couche basse),analyse d'image (couche intermédiaire) et compréhension d'image (couche haute), comme lemontre la Figure 2.1.

La segmentation est le cœur d’un système d’analyse automatique d’images. Elleintervient dans de nombreuses applications importantes, comme l'indexation d'une base dedonnées d'image, le suivi et l'estimation de mouvement dans une séquence vidéo, etl'interprétation automatique d'images biomédicales et satellitaires, etc.

Nous présentons dans ce chapitre une brève introduction aux concepts de base dudomaine de traitement d’image, puis nous détaillerons les techniques de segmentationd’images avec quelques méthodes de seuillage d’histogrammes. On termine le chapitre parune description d’un ensemble d’applications des méthodes bio-inspirés dans la segmentationd’images à base du seuillage.

Figure 2.1 Image engineering et segmentation d’image [Melliani, 12].

18

2.2 Définition de l'image

L'image est une représentation d'une personne ou d'un objet par la peinture, lasculpture, le dessin, la photographie, le film, etc. C'est aussi un ensemble structuréd'informations qui, après affichage sur l'écran, ont une signification pour l'œil humain. Ellepeut être décrite sous la forme d'une fonction I(x,y) de brillance analogique continue, définiedans un domaine borné, Les x et y sont les coordonnées spatiales d'un point de l'image et I estune fonction d'intensité lumineuse et de couleurs. Sous cet aspect, l'image est inexploitablepar la machine, ce qui nécessite sa numérisation.

Ci-dessous sont représentées deux type d’image peinture et photographie.

Figure 2.2 Image peinture Figure 2.3 Image photographique.

2.3 Image numérique

Contrairement aux images obtenues à l'aide d'un appareil photo, ou dessinées sur unpapier, les images manipulées par un ordinateur sont numériques (représentées par une sériede bits).

L'image numérique est l'image dont la surface est divisée en éléments de taille fixeappelés cellules ou pixels, ayant chacun comme caractéristique un niveau de gris ou decouleurs prélevé à l'emplacement correspondant dans l'image réelle, ou calculé à partir d'unedescription interne de la scène à représenter.

La numérisation d'une image est la conversion de celle-ci de son état analogique enune image numérique représentée par une matrice bidimensionnelle de valeurs numériquesf(x,y), comme la montre la figure 1.4 où :

x,y : coordonnées cartésiennes d'un point de l'image.

f(x, y) : niveau d’intensité.

Pour des raisons de commodité de représentation pour l'affichage et l'adressage, lesdonnées images sont généralement rangées sous formes de tableau I de n lignes et p colonnes.

19

Chaque élément I(x, y) représente un pixel de l'image et sa valeur est associée à un niveau degris codé sur m bits

(2m niveaux de gris ; 0 = noir ; 2m-1 = blanc).

La valeur en chaque point exprime la mesure d'intensité lumineuse perçue par lecapteur.

Figure 2.4 Représentation d’image numérique.

2.4 Caractéristiques d'une image numérique

L'image est un ensemble structuré d'informations caractérisé par les paramètressuivants [Biringanine, 08] :

2.4.1 Pixel

Contraction de l'expression anglaise " Picture Elément " élément d'image, le pixel estle plus petit point de l'image. C'est une entité calculable qui peut recevoir une structure et unequantification. Si le bit est la plus petite unité d'information que peut traiter un ordinateur, lepixel est le plus petit élément qui peut manipuler les matériels et les logiciels d'affichage oud'impression. La lettre A, par exemple, peut être affichée comme un groupe de pixels commese montre la figure ci-dessous :

Figure 2.5 La lettre A affichée comme un groupe de pixels.

La quantité d'informations que véhicule chaque pixel donne des nuances entre imagesmonochromes et images couleurs. Dans le cas d'une image monochrome, chaque pixel estcodé sur 1octet, et la taille mémoire nécessaire pour afficher une telle image est directement

Largeur yIndice de colonne

Indice de ligne

x

Hauteur

Le pixel (x,y)

19







2.4.1 Pixel





Indice de ligne

x

Hauteur

Le pixel (x,y)

19







2.4.1 Pixel





Indice de ligne

x

Hauteur

Le pixel (x,y)

20

liée à la taille de l'image. Dans une image couleur (R.V.B.), un pixel peut être représenté sur 3octets : 1 octet pour chacune des couleurs: rouge (R), vert (V) et bleu (B).

2.4.2 Dimension

C'est la taille de l'image. Cette dernière se présente sous forme de matrice dont leséléments sont des valeurs numériques représentatives des intensités lumineuses (pixels). Lenombre de lignes de cette matrice multiplié par le nombre de colonnes nous donne le nombretotal de pixels dans une image.

2.4.3 Résolution

La résolution est définie par un nombre de pixels par unité de longueur de l'image ànumériser en dpi (dots per inch) ou ppp (points par pouce). On parle de définition pour unécran et de résolution pour une image. Plus le nombre de pixels est élevé par unité delongueur de l'image à numériser, plus la quantité d'informations qui décrit l'image estimportante et plus la résolution est élevée (et plus le poids de l'image est élevé).

La résolution d'une image correspond au niveau de détail qui va être représenté surcette image. Pour la numérisation il faut considérer les 2 équations suivantes :

(X*résolution) = x pixels

(Y*résolution) = y pixels

Telle que :

X et Y représentent la taille (pouce ou cm, 1 pouce=2,54 centimètres) de la structure ànumériser.

résolution représente la résolution de numérisation.

x et y représentent la taille (en pixels) de l'image.

2.4.4 La taille d'une image

Pour connaître la taille d'une image, il est nécessaire de compter le nombre de pixelsque contient l'image, cela revient à calculer le nombre des cases du tableau, soit la hauteur decelui-ci que multiplie sa largeur. La taille de l'image est alors le nombre des pixels quemultiplie la taille (en octet) de chacun de ces éléments.

Exemple : pour une image de 240 * 420 en TrueColor :

Nombre de pixels :

240 * 420 = 100800

Taille de chaque pixel : 24 bits / 8 = 3 octets

Le poids de l'image est ainsi égal à :

100800 * 3 = 302.400 égal 302.400/1024 = 295 Ko

21

2.4.5 Bruit

Un bruit (parasite) dans une image est considéré comme un phénomène de brusquevariation de l'intensité d'un pixel par rapport à ses voisins, il provient de l'éclairage desdispositifs optiques et électroniques du capteur.

Figure 2.6 Image sans bruit. Figure 2.7 Image Bruitée.

2.4.6 Histogramme

L'histogramme des niveaux de gris ou des couleurs d'une image est une fonction quidonne la fréquence d'apparition de chaque niveau de gris (couleur) dans l'image. Pourdiminuer l'erreur de quantification, pour comparer deux images obtenues sous des éclairagesdifférents, ou encore pour mesurer certaines propriétés sur une image, on modifie souventl'histogramme correspondant. Il permet de donner un grand nombre d'information sur ladistribution des niveaux de gris (couleur) et de voir entre quelles bornes est repartie lamajorité des niveaux de gris (couleur) dans les cas d'une image trop claire ou d'une image tropfoncée. Il peut être utilisé pour améliorer la qualité d'une image (Rehaussement d'image) enintroduisant quelques modifications, pour pouvoir extraire les informations utiles de celle-ci.La figure 2.8 montre une image avec son histogramme.

Figure 2.8 Image avec histogramme.

2.4.7 Contours et textures

Les contours représentent la frontière entre les objets de l'image, ou la limite entredeux pixels dont les niveaux de gris représentent une différence significative. Les textures

22

décrivent la structure de ceux-ci. L'extraction de contour consiste à identifier dans l'image lespoints qui séparent deux textures différentes.

Figure 2.9 Contour d’une image.

2.4.8 Luminance

C'est le degré de luminosité des points de l'image. Elle est définie aussi comme étant lequotient de l'intensité lumineuse d'une surface par l'aire apparente de cette surface, pour unobservateur lointain, le mot luminance est substitué au mot brillance, qui correspond à l'éclatd'un objet. Une bonne luminance se caractérise par :

1. Des images lumineuses (brillantes);2. Un bon contraste : il faut éviter les images où la gamme de contraste tend

vers le blanc ou le noir; ces images entraînent des pertes de détails dans leszones sombres ou lumineuses.

3. L'absence de parasites.

2.4.9 Contraste

C'est l'opposition marquée entre deux régions d'une image, plus précisément entre lesrégions sombres et les régions claires de cette image. Le contraste est défini en fonction desluminances de deux zones d'images.

Si L1 et L2 sont les degrés de luminosité respectivement de deux zones voisines A1 etA2 d'une image, le contraste C est défini par le rapport :

C=

2.5 Types d’images

On distingue trois types d’images :

Binaire : 2 couleurs (arrière-plan et avant-plan).

Monochrome : variations d’une même teinte. Polychrome : ‘’ vraies‘’ couleurs.

La figure 1.9 montre la représentation d’une image par les trois familles.

23

2.5.1 Images binaires (en noir et blanc)

Les images binaires sont les plus simples. Bichromes (la plupart du temps noire etblanche) elles sont ontologiquement numériques c'est-à-dire que leur codage et leur décodagepeuvent être faits directement vers la base 2.

2.5.2 Images à niveaux de gris (Monochromes)

Le niveau de gris est la valeur de l'intensité lumineuse en un point. La couleur du pixelpeut prendre des valeurs allant du noir au blanc en passant par un nombre fini de niveauxintermédiaires. Donc pour représenter les images à niveaux de gris, on peut attribuer à chaquepixel de l'image une valeur correspondant à la quantité de lumière renvoyée. Cette valeur peutêtre comprise par exemple entre 0 et 255. Chaque pixel n'est donc plus représenté par 1 bit,mais par 1 octet. Pour cela, il faut que le matériel utilisé pour afficher l'image, soit capable deproduire les différents niveaux de gris correspondant.

Le nombre de niveaux de gris dépend du nombre de bits utilisés pour décrire la" couleur " de chaque pixel de l'image. Plus ce nombre est important, plus les niveauxpossibles sont nombreux.

2.5.3 Images en couleurs (Polychromes)

Même s'il est parfois utile de pouvoir représenter des images en noir et blanc, lesapplications multimédias utilisent le plus souvent des images en couleurs. La représentationdes couleurs s'effectue de la même manière que les images monochromes avec cependantquelques particularités. En effet, il faut tout d'abord choisir un modèle de représentation. Onpeut représenter les couleurs à l'aide de leurs composantes primaires. Les systèmes émettantde la lumière (écrans d'ordinateurs,...) sont basés sur le principe de la synthèse additive : lescouleurs sont composées d'un mélange de rouge, vert et bleu (modèle R.V.B.).

La représentation en couleurs réelles : Elle consiste à utiliser 24 bits pour chaquepoint de l'image. 8 bits sont employés pour décrire la composante rouge (R), 8 pour levert (V) et 8 pour le bleu (B). Il est ainsi possible de représenter environ 16,7 millionsde couleurs différentes simultanément. Cela est cependant théorique, car aucun écrann'est capable d'afficher 16 millions de points. Dans la plus haute résolution (1600 x1200), l'écran n'affiche que 1 920 000 points. Par ailleurs, l'œil humain n'est pascapable de distinguer autant de couleurs.

24

Image binaire (2 couleurs) Image Monochrome (256couleurs)

Image polychrome (65536couleurs)

Figure 2.10 Types d’images.

2.6 Qualité d'image numérique

Elle dépend, d'une part, de la qualité des images d'origine et, d'autre part, des moyensmis en œuvre pour convertir un signal analogique en signal numérique. Elle dépend aussi de :

1. La qualité des périphériques de numérisation de l'image, du nombre de niveaux degris ou de couleurs enregistrées, etc.

2. La qualité de l'affichage à l'écran : définition de l'écran, nombre de teintesdisponibles simultanément, calibrage de l'écran, etc.

Les critères d'appréciation de la qualité d'une image, tels que cités succinctement ci-dessus, dépendent largement de la structure même de l'image réaliste ou conceptuelle et deson mode de représentation (bitmap ou vectorielle).

2.7 Images bitmap et images vectorielles

Les images appartiennent à deux grandes familles : bitmap (image-bit) ou raster etvectorielle. Alors qu'une image vectorielle est décrite à l'aide des équations mathématiques,une image bitmap est constituée de pixels et se réduit donc à une matrice de points. Si lesimages vectorielles peuvent être manipulées avec beaucoup de facilité, les modifications detaille, par exemple, apportées à une image bitmap ne sont pas sans incidence. La figure ci-dessous montre la différence entre les deux familles.

Figure 2.11 Difference entre l’image vectorielle et l’image matricielle [wikipedia2].

25

2.8 Les différentes techniques de traitement d’image

Le traitement d’image consiste à améliorer le contenu d’une image pour en extraire del’information, par exemple identifier une séquence de texte ou un chromosome, éviter unobstacle (robotique), détecter des zones soumises à l’érosion (télédétection). En bref traiterune image, c’est d’ajouter du sens par un procédé automatique, par la suite on va citer lesdifférentes techniques de traitement d’image les plus connus tels que : Extraction decaractéristiques d’image, la segmentation d’image, rehaussement d’image (amélioration dequalité d’image) et le recalage d'image.

2.8.1 Extraction des caractéristiques (Feature Extraction from Images en Anglais)

En vision par ordinateur, une caractéristique est définie en fonction d'une ou plusieursmesures, dont chacun spécifie une propriété mesurable d'un objet, est calculée de telle sortequ'il quantifie des caractéristiques importantes de l'objet [Castleman, 96].

Les images sont des objets numériques très riches en termes d’informations. En plusde l’espace mémoire gigantesque exigé, la manipulation directe de ces images dans unsystème de reconnaissance d’images par le contenu ne permet pas d’obtenir des temps deréponse réalistes. Il convient donc d’utiliser une représentation de dimension réduite pourcaractériser le contenu de ces images. L’objectif principal de l’extraction d’attributs est dedéterminer pour chaque image, une représentation (signature) qui soit, d’une part compacte,pour être rapidement accessible et facilement comparable, et d’autre part suffisammentcomplète pour bien caractériser l’image. Il est recommandé d’employer des attributsinvariants aux transformations colorimétriques telles que le changement d’éclairage et auxtransformations géométriques telles que le changement d’échelle. Ceci permet de palier auxdifférentes transformations que peut subir une image. Cependant, la caractérisation robuste etdiscriminante des images reste un grand défi en traitement d’images. Généralement, lesattributs dits de bas niveau sont souvent les plus utilisés pour la description d’images par lecontenu. Ces attributs décrivent les principales caractéristiques visuelles existant dans uneimage, à savoir la couleur, la texture et la forme [Kachouri, 10].

Nous classons les diverses caractéristiques actuellement utilisées comme suit [Lei, 99 ;Nixon, 02]:

Caractéristiques générales : caractéristiques d’applications indépendantestelles que la couleur, la texture et la forme. Selon le niveau d'abstraction, ellespeuvent être divisées en : Caractéristiques au niveau des pixels (Pixel-level features) :

caractéristiques calculées à chaque pixel, par exemple couleur,l'emplacement.

Caractéristiques locales (Local features) : caractéristiques calculéessur les résultats de la subdivision de la bande image sur la segmentationd'images ou de détection des bords.

26

Caractéristiques globales (Global features) : caractéristiquescalculées sur toute l'image ou tout simplement régulièrement sous-zoned'une image.

Domaine des fonctionnalités spécifiques : Fonctionnalités dépendantes desapplications telles que des visages humains, des empreintes digitales et descaractéristiques conceptuelles. Ces caractéristiques sont souvent une synthèsedes caractéristiques de bas niveau pour un domaine spécifique.

2.8.2 Segmentation d’images (Image Segmentation en Anglais)

La segmentation des images constitue le cœur de tout système de vision et une étapeimportante dans le processus d’analyse des images. Elle a pour objectif de fournir unedescription des objets contenus dans l’image par l’extraction de différents indices visuels telsque les contours des objets, les régions homogènes. Ils seront exploités ensuite pour unedescription symbolique de la scène permettant une interprétation et éventuellement une prisede décision. La phase de segmentation d’images n’est pas considérée comme un but en soi,mais dépend fortement aussi bien du type de traitement fixé par l'utilisateur sur les objetsprésents dans l’image, que de la nature de l’image (présence de bruit, présence de zonestexturées, contours flous....), ainsi que des primitives que l’on cherche à extraire de l’image etqui dépendent des opérations situées en aval de la segmentation (localisation, calcul 3D,reconnaissance de formes, interprétation). La segmentation d’images sera présentée en détaildans la section suivante.

2.8.3 Rehaussement d'image (Image Enhancement en Anglais)

Le processus d'amélioration d'image (le rehaussement des images) est constitué d'unensemble de techniques qui visent à améliorer l'aspect visuel d'une image ou pour convertirl'image en une forme mieux adaptée à l'analyse par un humain ou une machine [Pratt, 07]. Onapplique le rehaussement des images afin de faciliter l'interprétation visuelle et lacompréhension des images. Les images numériques ont l'avantage de nous permettre demanipuler assez facilement les valeurs enregistrées pour chaque pixel. Comme la qualitévisuelle d’une image est une notion subjective, la plupart de ces méthodes et techniques sontinteractives permettant ainsi à l’analyste, par essai et erreur, de transformer les images afind’adapter leur contenu en fonction de ses propres critères de qualité visuelle.

On distingue les familles suivantes d’algorithmes de rehaussement d’images:

a) la manipulation du contraste

b) le rehaussement par pseudo-couleurs

c) le nettoyage du bruit

d) le rehaussement des arêtes

e) la création des composés couleurs

f) le rehaussement d’images multi-bandes

27

g) la fusion d’images multi-composantes.

Les 4 premières familles d’algorithmes sont applicables sur une image mono-bandetandis que les algorithmes des deux dernières familles opèrent à partir d’images multi-bandes.

2.8.4 Recalage d’image (Image Registration en Anglais)

En traitement d'image, le recalage est une technique qui consiste en la mise encorrespondance d'images, ceci afin de pouvoir comparer ou combiner leurs informationsrespectives. Cette mise en correspondance se fait par la recherche d'une transformationgéométrique permettant de passer d'une image à une autre (Figure 1.12 Recalage d’uneimage). Cette technique comprend de nombreuses applications allant de l'imagerie médicaleafin par exemple de fusionner plusieurs modalités d'imagerie, au traitement de vidéos commele suivi de mouvement et la compression, ou encore la création de mosaïques d'images(panoramas).

(a)

(b)

Figure 2.12 Recalage d’une image référence et d’une image source (a) image àrecaler, (b) superposition de leur partie commune [Meshoul, 04].

Néanmoins, la majorité des méthodes de recalage d'image comprennent les quatreétapes suivantes [Zitová, 03]:

28

1. Détection des Caractéristiques (primitives) (Feature detection en Anglais) :Objets marquants et distinctifs (des arêtes, des contours, des intersections delignes, des angles) sont manuellement ou, de préférence, automatiquementdétecté. Pour le traitement ultérieur, ces caractéristiques peuvent êtrereprésentées par leurs représentants ponctuelles (centres de gravité, les fins deligne, les points distinctifs), qui sont appelés points de contrôle (CP) dans lalittérature.

2. Mise en correspondance de primitives (Feature matching en Anglais) : danscette étape, la correspondance entre les caractéristiques détectées dans l'imagedétectée et ceux détectés dans l'image de référence est établie. Des différentesDescripteurs de caractéristiques et des mesures de similarité ainsi que lesrelations spatiales entre les éléments sont utilisés dans ce but.

3. Estimation du modèle de transformation (Transform model estimation enAnglais) : le type et les paramètres des fonctions de mappage, d'alignement del'image captée avec l'image de référence, est estimé. Les paramètres desfonctions de mappage sont calculés par moyen de la fonction decorrespondance établie.

4. Rééchantillonnage d'image et transformation (Image resampling andtransformation en Anglais) : l'image détectée est transformée parl'intermédiaire des fonctions de mappage. Des valeurs d'image en coordonnéesnon-entières sont calculées par la technique d'interpolation appropriée.

2.9 Segmentation d’image

2.9.1 Définition de la segmentation d’image

Dans [Cocquerez, 95] la segmentation d’image est : "La segmentation est un traitementde bas niveau qui consiste à créer une partition de l'image A en sous-ensembles Ri, appelésrégions tels qu’aucune région ne soit vide, l'intersection entre deux régions soit vide etl'ensemble des régions recouvre toute l'image. Une région est un ensemble de pixels connexesayant des propriétés communes qui les différencient des pixels des régions voisines".

La segmentation d’image permet de partitionner l’image en zones homogènes ayant descaractéristiques (niveau de gris, couleur, texture) identiques où une zone peut correspondre unobjet ou une partie d’un objet.

Formellement, la segmentation d’image est définie comme suit [Monga, 87] :

Une segmentation d'une image I utilisant le prédicat P est généralement défini commeune partition :

S = { R1, R 2, . . . , Rn } de I telle que :

1. I= ⋃ , ;

2. Ri est constituée de pixels connexes pour tout i, ∀ ∈ [1, ];3. P(i)=vrai, ∀ ∈ [1, ];

29

4. P(Ri U Rj)=faux, ∀i≠j, Ri et Rj étant deux ensembles connexes.

La première condition demande simplement que la segmentation soit complète :tout pixel de l'image doit appartenir à une région et une seule. Tout algorithme nedoit pas s'arrêter avant d'avoir traité tous les points de l'image.

La seconde condition demande que les régions soient des ensembles de pointsconnexes. C'est la raison pour laquelle les algorithmes prennent généralement encompte le voisinage des points.

Les critères qui définissent la segmentation sont introduits à la troisième condition.

La quatrième condition exprime la maximalité de chaque région indiquant que lafusion de deux régions ne doit pas être homogène.

Jusqu’à ce jour, il n’existe pas de méthode universelle de segmentation d’images. Toutetechnique n’est efficace que pour un type d’image donné, pour un type d’application donné, etdans un contexte informatique donné. En raison de ces contraintes, plusieurs stratégies desegmentation ont été proposées.

2.9.2 Techniques de segmentation

Les techniques de segmentations existantes sont nombreuses, mais elles sontgénéralement regroupées en trois principales approches qui sont l’approche contour,l’approche région et l’approche coopérative. Une classification de ces méthodes est montréedans la figure 2.13:

2.9.2.1 Approche Contour

Un contour est un ensemble des points d'une image numérique qui correspond à unchangement brutal de l'intensité lumineuse.

Figure 2.13 Techniques de segmentation d’image.

Approche Contour Approche Région Approche Coopérative

Approches de segmentationd’image

Méthodes dérivatives

Méthodes analytiques

Méthodes déformables

Croissance des régions

Division des régions

Division / Fusion

Séquentielle

Des résultats

Mutuelle

Classification

30

Dans l’approche ” contour ”, on considère que les primitives à extraire sont les lignes decontrastes séparant des régions de niveaux de gris différents et relativement homogènes, oubien des régions de texture différentes. En pratique, il s’agit de reconnaître les zones detransition et de localiser au mieux la frontière entre les régions.

Dans l’approche de segmentation basée contour Il existe plusieurs méthodes qu’on peutregrouper en trois catégories : les méthodes dérivatives, les méthodes Analytiques et lesméthodes déformables.

Méthodes dérivatives

Elles consistent à calculer la dérivée en chaque point de l’image afin de mettre enévidence les variations de niveau de gris. On peut classer les méthodes dérivatives en deuxgroupes selon qu’on utilise la dérivée première (approche Gradient) ou dérivée seconde(approche Laplacien).

1. L’approche Gradient

Ce type de détecteur se base sur la première dérivée de l’image I en chacun de ces pointsdans les deux directions horizontale et verticale. Un point de contours aura une amplitudeA(i,j) et une direction Dir (i,j).

Dans un premier temps, la détermination des points contours est ramenée à la recherchede filtre linéaire permettant d’estimer le gradient en chaque point.

De nombreux opérateurs sont ainsi apparus dans la littérature parmi lesquels nous pouvonsciter les masques de Sobel, Prewit, Robert … etc.

La valeur du gradient est ainsi disponible en tout point de l’image permettant d’effectuerune recherche des maxima locaux. Ceux-ci correspondent aux passages par zéro de la dérivéeseconde dans la direction du gradient ou encore aux points contours recherchés.

2. L’approche Laplacien

On utilise le deuxième dérivé pour calculer le Laplacien. Les points de contour sontsitués aux passages par zéro du Laplacien :

En faisant une approximation par différences finies, on trouve les masques suivants :

31

Masque isotrope pour une rotation : 2 0 1 01 −4 10 1 0Masque isotrope pour une rotation : 4 1 1 11 −8 11 1 1

Le Laplacien permet d’obtenir des contours fermés et d’un pixel d’épaisseur, par contreil a l’inconvénient d’être plus sensible au bruit que le gradient.

Méthodes analytiques

1. Approche de Canny

Canny [Canny, 86] a proposé un filtre déterminé analytiquement à partir de troiscritères :

1. Une bonne détection : l'opérateur donne une réponse au voisinage d'un contour ;2. Une bonne localisation : optimisation de la précision avec laquelle le contour est

détecté;3. Unicité de la réponse : le contour doit provoquer une réponse unique de l'opérateur.

La solution qui vérifie ces trois critères, proposée par Canny est la suivante [Bloch, 05]:( ) = ⁄ sin + ⁄ sin + ⁄ sin + ⁄ sinOù les coefficients ai et w sont déterminés à partir de la taille du filtre. Le

paramètre est un paramètre de grande importance que nous retrouverons dans tous lesautres filtres dérivé de l’approche de Canny. C’est un paramètre d’échelle qui indique en-deça de quelle distance deux contours parallèles seront confondus en un seul. Cannymontre que la dérivée d’une gaussienne est une bonne approximation de son filtre.

2. Approche de Deriche

Au filtre de Canny, nous préférons souvent le détecteur de Deriche [Deriche, 87], quirépond exactement aux mêmes critères de qualité que celui de Canny, mais qui possèdeune réponse impulsionnelle finie. Il a pu donc être synthétisé de façon récursiveparticulièrement efficace. Le filtre de Deriche a une expression générale de la forme :

a,w et c sont des réels positifs

Méthodes déformables

Les modèles déformables, introduits par Kass [Kass, 87] sont aussi connus sous les nomsde «snakes» ou «contours actifs». Ils se présentent comme un modèle pour l’extraction descaractéristiques visuelles dans une image comme les contours d’objet ou les éléments de

32

frontières. L’idée de base est de positionner une courbe qui sera l’initialisation du contouractif et de la déformer successivement jusqu’à ce qu’elle coïncide avec la frontière de l’objet.

Les limites de segmentation par contour

Les principales limites des méthodes de détection de contour sont les suivantes[Melliani, 12] :

Les contours extraits selon les méthodes classiques souvent ne correspondent pasnécessairement à la limite des objets. Dans de nombreuses images de basse qualité,quelques-unes des méthodes produisent des faux contours.

Les techniques de détection de contour dépendent de l'information contenue dans levoisinage local de l'image. Il n’y a pas d’information globale.

Dans la plupart des cas, les stratégies de détection des contours ignorent l'organisationd'ordre supérieur qui peut être utilement présent dans l'image.

Après l’extraction des points de contours, ces derniers sont reliés afin de déterminerles frontières. Le processus de fermeture des contours peut parfois conduire à desdiscontinuités et des lacunes dans l'image.

Il est souvent difficile d'identifier et de classer les contours parasites.

2.9.2.2 Approche région

Contrairement à la segmentation par contours dont le principe est la recherche des pointsessentiels qui donnent la forme des objets composant l'image, la segmentation en régionsconsiste à décomposer l'image en des régions homogènes [Gonzalez, 92; Jain, 00; Fuh, 00].Une région est composée de l'ensemble des pixels connexes possédant les mêmes propriétésau sens d'un prédicat d'homogénéité donné. On distingue quatre types de méthodes.

A. Croissance de régions

Cette technique consiste à faire progressivement grossir les régions autour de leurpoint de départ. L’initialisation de cette méthode consiste à considérer chaque pixel commeune région. On va essayer de les regrouper entre elles avec un double critère de similarité desniveaux de gris et d’adjacence. Le critère de similarité peut par exemple être : la variance desniveaux de gris de la région R est inférieure à un seuil.

Le principe de l’agrégation de pixel est le suivant : on choisit un germe (Le point dedépart est le choix d'un ensemble de pixels appelés « germes ») et on fait croitre ce germe tantque des pixels de son voisinage vérifient le test d’homogénéité. Lorsqu’il n’y a plus de pixelscandidats dans le voisinage, on choisit un nouveau germe et on itère le processus.

33

B. Division des régions

L’image est divisée d’une manière récursive tant que le critère d’homogénéité n’estpas vérifié. Le critère d’homogénéité est validé d’une manière globale sur l'image originale. Sile critère est vérifié l'algorithme s'arrête. Sinon, on divise l’image en des zones. Chaque zoneest testée et redivisée si elle ne valide pas le critère. L’algorithme se termine lorsque toutes lesrégions sont homogènes ou bien leur taille est en dessous d’un seuil de taille minimal fixé.

La division de l’image est réalisée selon une structure géométrique. Citons parexemple l’arbre quartenaire (structure ‘ Quadtree ’).

Le Quadtree est une arborescence dont la racine est l’image tout entière et dont chaquenœud parent (sauf les nœuds terminaux) possède exactement 4 fils. Il est défini de manièrerécursive: l’image est partagée d’abord en quatre blocs. À chacun de ces blocs est ensuiteassocié un nœud fils de la racine. Puis le processus de découpage en quatre est itéré pourchacun des fils sans chevauchement des blocs. L’analyse récursive s’arrête lorsque chaquesous-bloc respecte un prédicat d’homogénéité. Après cette phase de division des petitesrégions, certains blocs adjacents présentent des caractéristiques identiques d’où la nécessité deles fusionner. Cette fusion s’arrête lorsqu’il n’existe plus de couples qui respectent le prédicatde fusion.

C. Division / Fusion

Ces méthodes combinent les deux méthodes décrites précédemment, la division del’image en des petites régions homogènes, puis la fusion des régions connexes et similaires ausens d’un prédicat de regroupement. Horowitz et Pavlidis sont les premiers à avoir proposéune telle approche de segmentation [Horowitz, 76]. Le processus de segmentation utilise lastructure pyramidale du Quadtree est peut être décrit comme suit: en premier lieu chaque blocassocié à un nœud du Quadtree est analysé de façon récursive afin de décider s’il doit êtredivisé en quatre sous-blocs. L’analyse récursive s’arrête lorsque chaque sous-bloc respecte unprédicat d’homogénéité. Ensuite, à chaque fois que 4 sous-blocs satisfont un critèred'homogénéité ils sont regroupés à un niveau supérieur du Quadtree. La fusion continue tantqu'il est possible de le faire, c'est à dire tant que le critère d'homogénéité est satisfait. Lorsqu'iln'est plus possible de fusionner, il reste encore une étape pour examiner les blocs adjacents

Figure 2.14 Processus de division de l’image I utilisant le quad-tree [Merzougui, 12].

34

qui n’étaient pas au même niveau dans le Quadtree et les fusionner s’ils satisfont le critèred'homogénéité. La figure 2.15 illustre le principe de la division / fusion.

D. Segmentation par classification

La classification permet de partitionner un ensemble de données multidimensionnellesen un ensemble de k classes disjointes. En segmentation d’image, les donnéesmultidimensionnelles correspondent aux pixels de l’image ou chaque pixel est caractérisé parun vecteur d’attributs tels que les attributs de texture ou les composantes couleurs. Chaqueclasse regroupe des pixels ayant des vecteurs de caractéristiques aussi similaires que possible.Sachant que les pixels de deux classes distinctes ont des attributs très différents [Jain, 99].

Donc la classification est définie comme une procédure dans laquelle les pixelssimilaires d’une image sont identifiés et regroupés dans une même classe. Il existe deuxgrandes tendances:

La classification non supervisée : elle vise à séparer automatiquement l’image en clusterssans aucune connaissance a priori sur les classes. Elle se base sur une mesure de distanceentre les vecteurs d’attributs. Les algorithmes les plus fréquemment cités dans la littératurepour cette catégorie sont K-means, Isodata, et Fuzzy c-means…

La classification supervisée : elle s’opère à partir de la connaissance de chacune desclasses définies par une approche probabiliste. Elle se base sur l’apprentissage depropriétés discriminantes sur un échantillon de données déjà classées. Les algorithmes decette catégorie sont Minimum-Distance-to-Means, Likelihood et Parallelopiped.

L’inconvénient des méthodes de classification est qu’elles sont très sensibles au bruit.

2.9.2.3 Approche coopérative

L’approche contour et l’approche région sont en fait des approches duales. On peut lescombiner afin d’aboutir à une segmentation plus efficace. Comme, il possible de combinerplusieurs techniques d’une même approche.

La segmentation par coopération région-contour suscite un grand intérêt. Elle combineles deux techniques de segmentation (basées régions, basées contours), prend avantage de la

Figure 2.15 La segmentation par division / fusion [Ouadfel, 06].

35

nature complémentaire de l’information sur la région et sur le contour. Ainsi, unesegmentation par coopération régions-contours peut être exprimée comme une entraide entreces deux concepts afin d’améliorer le résultat final de segmentation.

Il existe trois formes de coopération région-contour [Sebari, 07]:

A. Coopération séquentielle

L’une des techniques de segmentation (région ou contour) est réalisée en premier lieu;son résultat va être exploité par l’autre technique pour renforcer la définition des critères oudes paramètres de la segmentation ; L’intégration de l’information provenant de lasegmentation par contours dans une segmentation par régions est l’une des formes decoopération les plus courantes (Figure 2.16).

Figure 2.16 Principe de la coopération séquentielle [Sebari, 07].

B. Coopération des résultats

Les deux types de segmentation seront réalisés indépendamment ; la coopération concerneraleurs résultats qui seront intégrés afin d’atteindre une meilleure segmentation (Figure 2.17),cette intégration peut être faite sous forme de complémentarité ou de recherche de consensus.

Figure 2.17 Principe de la coopération des résultats [Sebari, 07].

36

C. Coopération Mutuelle

Dans l’approche de coopération mutuelle, les deux techniques de segmentation sont exécutéesen parallèle, elles coopèrent mutuellement au cours de leur processus d’exécution(Figure2.18). La coopération permet de prendre des décisions plus sures et plus fiable.

Figure 2.18 Principe de la coopération Mutuelle [Sebari, 07].

2.9.3 Segmentation par seuillage

2.9.3.1 Définition du seuillage

Le seuillage (thresholding en Anglais) représente un outil largement utilisé dans lasegmentation d’image pour extraire des objets de leurs fonds en fonction d’un seuil. Toutproblème de seuillage consiste alors à rechercher la valeur du seuil. La plupart des méthodesde seuillage déterminent le seuil en optimisant une fonction objective.

On distingue le Seuillage de base (simple) (2 classes) où le résultat du seuillage est uneimage binaire (0 : 1, parfois en 0 :255 pour l’affichage) (Figure 2.19), et le multi-seuillage(multi-level thresholding en Anglais) qui est utile quand on a affaire à des images quicontiennent plusieurs objets ayant des luminances différentes. Pour extraire ces objets,plusieurs seuils sont nécessaires. Le résultat du seuillage est une image avec n+1 classes pourn seuils (Figure2.20).

Figure 2.19 Seuillage simple d’un histogramme.

G(x,y)=1 ( , ) ≥0 ( , ) <

37

Figure 2.20 Seuillage multiple d’un histogramme.

La segmentation par seuillage d’histogramme constitue un cas particulier de lasegmentation par classification. Elle permet de répartir les pixels en classes en fonction deleurs niveaux de gris. Les classes sont alors délimitées par des seuils.

Les méthodes de seuillage peuvent être réparties en deux catégories [Abdelli, 11]:Seuillage globale et seuillage local ou adaptatif.

2.9.3.2 Méthode de seuillage globale

Seuillage globale : un seuil pour toute l’image. Il existe plusieurs méthodes de seuillagesglobales qu’on peut classer en deux catégories :

1. Méthodes paramétriques : ces méthodes supposent que l’histogramme peut êtreapproximé par une combinaison linéaire de densité de probabilité dont lemodèle est connu à priori.

2. Méthodes non-paramétriques : permettent de trouver les seuils optimaux sanstenir compte d’aucune hypothèse sur la forme de l’histogramme. Elles sontbasées sur l’optimisation d’une fonction objective. Nous présentons dans ce quisuit la méthode Otsu.

Méthode d’Otsu

Elle est considérée comme la méthode de référence dans le domaine du seuillaged’histogrammes. Dans cette méthode [Otsu, 79], l’opération de seuillage est vue commeune séparation (partitionnement) des pixels d’une image en deux classes C1 (fond), C2

(objet) à partir d’un seuil t. La classe fond regroupe tous les pixels ayant un niveau de grisinférieur au seuil t alors que la classe objet contient tous les pixels de niveau de grissupérieur à t. Ces deux classes peuvent être désignées en fonction du seuil t comme suit :

C1={0,1,…t} et C2={t+1 ,…L-1}.

Soient :

= P1P2(m2-m1)2 la variance d’une classe,

=∑ (i-m1)2 + ∑ (i-m1)

2 la variance interclasse,

= ∑ ( i-m)2 la variance totale telles que:= +

G(x,y)=2 ( , ) ≥1 ≤ ( , ) <0 ( , ) <

38

m1 , m2 et m désignent respectivement les niveau de gris moyen des classes C1 et C2 etde l’image tels que :On considère L les niveaux d'intensité d'une image donnée, et ces niveaux sont dansl’intervalle {0, 1, 2,. . . , L-1}. Ensuite, on peut définir:

= , ∑ = 1 ,

Où i représente un niveau d'intensité spécifique, N représente le nombre total de pixelsdans l'image et ℎ désigne le nombre de pixels pour un niveau d'intensité i. En d'autrestermes, ℎ représente un histogramme de l'image, qui peut être normalisée etconsidéré comme la distribution de probabilité .

m1=∑ . , m2= ∑ . , m= ∑ . ,

P1 et P2 représentent respectivement les probabilités à priori des classes C1 et C2 telsque:

P1 =∑ , P2 =∑ et P1+P2= 1.

Le seuil optimum t*peut être déterminé en maximisant un des trois critères suivant:

l(t)= ; h(t)= ; k(t)= .

Les trois critères sont équivalents, mai pour des raisons de simplicité, la varianceinterclasse est la plus utilisée. Le seuil optimal t* est celui qui maximise cette variance:

t* =Arg0 ≤ ≤ − 1Dans le cas du multiseuillage, la méthode d’Otsu peut être généralisé au calcul d’unensemble de seuils T=(t1,t2,…,tk,…tK-1) en maximise la variance interclasses.

T * =Arg0 ≤ ≤ − 1 ( )J(T) = = ∑ (mk – m)2

Où

représente la proportion de pixels dans la classe [tk-1 ;tk],

mkreprésente l’intensité moyenne de cette même classe,

m représente l’intensité moyenne de la classe [0 :L] .

39

=⎩⎪⎪⎪⎨⎪⎪⎪⎧ , = 1

, 1 < <, =

La moyenne de chaque classe mk peut alors être calculée comme suit:

=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧ , = 1

, 1 < <, =

Cette méthode est simple à implanter et donne de bons résultats en général.

2.9.3.3 Méthode de seuillage locale ou adaptatif

Seuillage local ou adaptatif : un seuil pour chaque pixel. Les méthodes de seuillagelocale prennent en considération la valeur des pixels voisins pour le calcul des seuils.

2.10 Application du bio-inspiré dans segmentation d’image par seuillage

Algorithmes évolutionnaire : les Algorithmes Evolutionnaires ont été largementutilisés pour le problème de segmentation par seuillage d’histogramme. Les algorithmesgénétique sont utilisé dans [Hammouche, 08] où une méthode combine un algorithmegénétique avec une transformée en ondelettes, on peut citer également les méthodesbasées sur la minimisation de l’entropie floue dans [Yang, 03] et l’optimisation desfonctions d’Otsu et de Kapur dans [Hammouche, 10], ainsi afin d'obtenir rapidement leseuil optimal pour la segmentation d'image, une nouvelle méthode de segmentationbasée sur l'amélioration de l'algorithme génétique adaptative est présentée dans [Yu,11], de même que dans [Truong, 13], ils ont développés de nombreux algorithmesdifférents pour la sélection automatique de seuil basé sur la méthode évolutive enutilisant l'algorithme génétique adaptative de modification et l’algorithme de l'escaladede la colline (Hill Climbing Algorithm en Anglais). L’algorithme d’évolutiondifférentielle est appliqué pour l’approximer l’histogramme par mélange dedistributions dans [Cuevas, 10].

40

Intelligence basé essaim : Les systèmes d’intelligence basés essaim ont été appliquéspour résoudre le problème de la segmentation d’image par l’approche du seuillage.L'optimisation par essaims particulaires (OEP) avec une version adaptative a étéappliquée dans [Guo, 07] pour obtenir le maximum d'entropie de multi-seuillage, aussidans [Gao, 10] en préservant le taux de convergence rapide des OEP, le quantum OEPemployant la méthode coopérative (CQPSO) est proposé pour gagner du temps decalcul et de conquérir la malédiction de la dimensionnalité, de même que dans[Ghamisi, 12] ils ont présentés deux nouvelles méthodes de segmentation d'images enfonction de l'ordre fractionnaire darwinienne optimisation par essaim de particules(Fractional-Order Darwinian Particle Swarm Optimization FODPSO en Anglais ) etdarwinienne optimisation par essaim de particules (DPSO) pour déterminer n-1 seuilsoptimaux pour n-niveau seuillage sur une image donnée.L’algorithme de Colonies des abeilles Artificielle a été utilisé dans [Cuevas, 13] pourcalculer sélection de seuil pour la segmentation d'images, aussi dans [Zhihui, 13] ils ontproposés une méthode de segmentation d'image multi-seuillage basé sur PSNR enutilisant l'algorithme des colonies d'abeilles artificiel (ABCA).

2.11 Conclusion

Dans ce chapitre, nous avons présenté le domaine du traitement d’image en seconcentrant sur les méthodes de segmentation d’image les plus connues. C’est uneprésentation générale et non exhaustive à savoir celles de l’approche contour, de l’approcherégion et de l’approche coopérative. Nous nous sommes particulièrement intéressés àl’approche région dans laquelle les méthodes basées sur la classification et plus précisémentde seuillage ont attiré notre attention.

Le problème de segmentation d’image par multiseuillage peut être formulé sous formede problèmes d’optimisation. La recherche de la solution optimale est une tâche très coûteusevoire impossible à effectuer par les méthodes exhaustives (Otsu exhaustive). Ceci a favoriséle développement de méthodes approchées parallèles dont le principe est de trouver, enutilisant des processus stochastiques répartie, une solution proche de l’optimale voireoptimale. Dans le prochain chapitre sera présentée l’optimisation distribuée.

41

CHAPITRE 3 : LES METAHEURISTIQUES PARALLELES

3.1 Introduction

Les algorithmes d'optimisation combinatoire (algorithmes exacts et métaheuristiques)servent en général à résoudre les problèmes NP-Difficiles. Ces algorithmes explorent souventun espace de recherche des solutions potentielles de très grande taille. Ils atteignent cetobjectif en réduisant la taille effective de l'espace, et en l’explorant efficacement l’espace derecherche. Même si les métaheuristiques offrent des stratégies efficaces pour la recherche desolutions dans les problèmes d’optimisation combinatoire, le temps de calcul associés àl’exploration de l’espace de recherche peut être très importants [Cung, 02]. Une façond’accélérer la tache de l’exploration est l’utilisation du parallélisme.

Le calcul parallèle est un outil indispensable de la science moderne. Diviser la tâchedonnée en plusieurs unités indépendantes qui peuvent être exécutées en parallèle peutconduire à une réduction significative du temps nécessaire pour le calcul. La distribution estun cas particulier du parallélisme ou les différents processeurs (unités de calcul) sont situéssur différentes machines dans un réseau.

Alors que dans les dernières décennies les machines de calcul parallèle sont desressources rares, disponibles exclusivement pour les clients de centres de calcul, de nos jourspratiquement tous les ordinateurs personnels vendus ont des capacités de calcul parallèle sousforme de CPU « multi-core/multi-threaded ». Il n'est donc pas surprenant que de nombreusesrecherches sont en cours sur la façon d'utiliser au mieux ces capacités désormaisomniprésentes.

Le calcul parallèle et distribué peut être utilisé dans la conception et la mise en œuvrede métaheuristiques pour les raisons suivantes:

1. Accélérer la recherche : un des principaux objectifs de la parallélisation d'unemétaheuristique est de réduire le temps de recherche. Cela, permet de concevoir desméthodes d'optimisation en temps réel et interactives. C'est un aspect très importantpour une classe de problèmes où il y a des exigences précises sur le temps derecherche telle que des problèmes d'optimisation dynamique et les problèmes decontrôle de temps critiques tels que la planification en temps réel.

2. Améliorer la qualité des solutions obtenues : certains modèles parallèles demétaheuristiques permettent d'améliorer la qualité de la recherche. En effet, l'échanged'informations entre métaheuristiques coopératives va modifier leurs comportementsen matière de recherche dans le domaine associé au problème. L'objectif principald'une coopération parallèle entre les métaheuristiques est d'améliorer la qualité dessolutions. Cela, dans deux aspects la convergence et la réduction du temps derecherche. Notons qu’une métaheuristique parallèle peut être plus efficace qu'unemétaheuristique séquentielle, même sur un seul processeur.

42

3. Améliorer la robustesse : une métaheuristique parallèle peut être plus robuste entermes de résolution d'une manière différentes des problèmes d'optimisation et lesdifférentes instances d'un problème donné. La robustesse peut également êtremesurée en fonction de la sensibilité de la métaheuristique à ses paramètres.

4. Résoudre des problèmes à grande échelle : les métaheuristiques parallèlespermettent de résoudre des cas à grande échelle des problèmes d'optimisationcomplexes. Un défi est de résoudre de très grandes instances de problèmes qui nepeuvent pas être résolues par une machine séquentielle. Un autre défi semblable estde développer des modèles mathématiques plus précis associés aux différentsproblèmes d'optimisation. L’amélioration de la précision des modèles mathématiquesaugmente, en général, la taille des problèmes associés à résoudre. En outre, certainsproblèmes d'optimisation ont besoin de la manipulation d'énormes bases de donnéestelles que les problèmes de feuille de donnée.

Dans ce chapitre on va commencer par décrire la classification des métaheuristiquesparallèles avec leurs méthodes de conception. Par la suite, nous présentons les modèlesparallèles des algorithmes évolutionnaires. On détaille le modèle d’île et d’île généralisécomme un paradigme. Nous commençons par la source d’inspiration et les motivationsderrière l’utilisation de ce modèle. Nous donnons ensuite une définition formelle du modèleavec ces principaux paramètres, pour terminer par une description détaillée de l’opérateur demigration, l’aspect implémentation ainsi que les langages de programmation et les plates-formes utilisés pour les métaheuristiques parallèles.

3.2 Classification des métaheuristiques

Crainic et Toulouse (1998) [Cung, 02 ; Gras, 03] ont tenté d’établir une classificationaux différentes implémentations dans le monde des métaheuristiques. La plus intéressante estcelle de Crainic et Toulouse (1998).

3.2.1 Classification de Crainic et Toulouse (1998)

Cette classification est basée sur le degré d’impact de la stratégie de parallélisation sur lastructure algorithmique de la métaheuristique, elle est divisée en trois catégories qui sont :

1. Stratégie du parallélisme à l’intérieur d’une itération de la métaheuristique : estune parallélisation de bas niveau (parallélisation interne), pour but d’accélérer lescalculs sans chercher à effectuer une meilleure exploration. La méthode de résolutionparallèle est la même que son équivalent séquentiel dans la mesure où le nombre totald’opérations est identique pour les deux versions. À cet effet, il est possible de profiterde la puissance de calcul disponible et d’améliorer ainsi la recherche de solutions enutilisant cette stratégie sans changer fondamentalement l’algorithme. Le principeconsiste à effectuer un maximum d’opérations en parallèle tout en conservant untemps d’exécution global égal ou inférieur à la version séquentielle.

43

2. Stratégie de décomposition : le principe est la décomposition du domaine duproblème ou de l’espace de recherche, qui consiste à diviser le problème en sous-problèmes et à utiliser la puissance du calcul afin de résoudre ces sous-problèmes enparallèle.

Un modèle maître-esclave est généralement utilisé pour appliquer cette stratégietel que :

Le maître : détermine séquentiellement les partitions initiales et les modifiesdurant l’exécution à des intervalles qui peuvent être prédéfinis ou déterminésdynamiquement durant l’exécution.

Les esclaves : explorent de façon concurrente et indépendante l’espace derecherche qui leurs a été assigné par le maître et ce dernier assemble lessolutions partielles trouvées par les esclaves en une solution complète auproblème.

3. Plusieurs processus de recherche (multi-search threads) : sont appliqués avecdifférents degrés de synchronisation et de coopération. On cherche à effectuer unerecherche plus complète en mettant en œuvre plusieurs processus qui opèrentsimultanément et qui sont guidés par de différentes façons. La métaheuristique peutêtre calibrée différemment pour chacune des recherches, mais il est également possibled’utiliser de façon concurrente différentes métaheuristiques. Les processus peuventcommuniquer entre eux durant leurs recherches ou seulement à la fin pour identifier lameilleure solution. Cette catégorie peut être divisée en deux classes :

Approches indépendantes : plusieurs recherches sont initiées et le meilleurrésultat est sélectionné parmi celles-ci à la fin. Cette approche est alorséquivalente à une stratégie de redémarrage accéléré. Plutôt que de redémarrerl’algorithme plusieurs fois et selon différents paramètres, toutes les exécutionssont effectuées en parallèle.

Approches coopératives : afin de définir une recherche multiple et coopérative,plusieurs paramètres importants doivent être déterminés: La topologie du réseau d’interconnexions qui définit comment les

processus sont reliés entre eux ; La méthode de communication entre les processus (diffusion, point à

point, mémoire centrale, etc.) ; Le choix des processus participant aux échanges d’informations ; Le type de communication (synchrone ou asynchrone) ; Les moments où l’information sera échangée ; L’information à échanger.

L’ajustement de ces paramètres peut avoir un impact significatif sur lecomportement et la performance de la recherche.

44

3.2.2 Classification de Cung et al. (2002)

Les métaheuristiques basées sur la recherche locale peuvent être vues comme uneexploration d’un graphe de voisinage associé à une instance de problème. Les solutionsvisitées durant cette recherche définissent une trajectoire, aussi appelée marche, dans legraphe de voisinage. On distingue deux approches, la première est la parallélisation à marchesimple représentée par des tâches de granularité fine à moyenne et la deuxième est laparallélisation à marches multiples représentée par des tâches de granularité moyenne àgrosse des processus de recherche indépendants et des processus de recherche coopératifs.

1. Parallélisation à marche simple : une trajectoire unique est traversée dans le graphe devoisinage. À chaque itération, la recherche du meilleur voisin est effectuée en parallèle,soit par la décomposition de domaine ou par la parallélisation de la fonction d’évaluationdes solutions. Une accélération substantielle peut être atteinte si la fonction d’évaluationdes solutions voisines est parallélisée, sans modifier la trajectoire parcourue par laméthode séquentielle. Dans l’autre cas, la trajectoire suivie peut être mieux guidée etconduire ainsi à de meilleures solutions avec la décomposition du voisinage et sarépartition sur plusieurs processeurs, qui permettent d’examiner une partie plus large duvoisinage que par une approche séquentielle.

2. Parallélisation à marches multiples : elle consiste à effectuer l’exploration de plusieurstrajectoires en parallèle sur des processeurs distincts. Cette approche, se subdivise selonle caractère indépendant ou coopératif des processus de recherche.

1. Processus de recherche indépendants : on distingue deux approches, lapremière est l’exploration de plusieurs trajectoires provenant de différentsendroits du graphe. La recherche est initiée à partir de différentes solutions oupopulations de départ. La deuxième correspond à l’exploration en parallèle dessous-graphes obtenus par la décomposition du domaine sans qu’il n’y aitd’intersection entre les trajectoires correspondantes.

2. Les Processus de recherche coopératifs : ils échangent ou partagentl’information qu’ils ont accumulée durant leur parcours pour améliorer leurrecherche respective. La principale difficulté dans ce modèle de parallélisationest de déterminer la nature des partages ou des échanges d’informations afind’améliorer la recherche sans trop sacrifier de temps ou de mémoire.

3.2.3 Classification de Gras et al. (2003)

Basée sur la propriété de la coopération entre les entités qui explorent l’espace derecherche. Cette classification comprend trois sous-classes : centralisée, individuelle etcoopération, selon la manière dont la coopération est accomplie. Ils ont mis de nouvellesdéfinitions et décrit les nouveaux développements de ces approches. Ils démontrent que ladivision hiérarchique du problème en taches indépendantes peut conduire à étendre et àsimplifier les étapes d’optimisation.

45

3.3 Conception des métaheuristiques parallèles

La conception des métaheuristiques parallèles consiste à créer et fournir un modèlegénérique pour être réutilisé lors de la conception de différentes applications. Il existe troisprincipales approches de réutilisation et d’exploitation des métaheuristiques parallèles[Belkhelladi, 10] :

À partir de rien (From scratch).

Seule la réutilisation du code. Des modèles de conception (plate-forme).

3.3.1 A’ partir de rien

Le développeur tente de coder lui-même les métaheuristiques parallèles. Une telledémarche n’est pas souhaitable puisqu’elle nécessite beaucoup de temps et d’énergie.

3.3.2 Seule la réutilisation du code

Elle consiste à utiliser du code sous forme de programmes indépendants et libres, oùde librairies. Il est nécessaire à l’utilisateur de réécrire certaines parties spécifiques auproblème traité. La maintenance et l’efficacité sont grandement facilitées. L’objectif principalde l’approche est de minimisé aux utilisateurs la quantité de code développé à chaque foisqu’un nouveau problème d’optimisation est considéré.

3.3.2 Approche plate-forme

Une plate-forme est un ensemble de classes intégrant des modèles de solutionslogicielles dédiées à une famille de problèmes apparentés [Fink, 98]. Les plates-formesgarantissent le contrôle de la partie invariante des algorithmes. L’utilisateur fournit seulementla partie spécifique à son problème. Par conséquent, l’approche plate-forme lui permet depasser plus de temps sur la modélisation de son problème que sur l’implémentation de laméthode de résolution appropriée.

3.4 Modèles parallèles des algorithmes évolutionnaires

La parallélisation des algorithmes évolutionnaires suit plusieurs idées principales, lapremière, étant que les algorithmes évolutionnaires sont intrinsèquement parallèles. En effet,dans ces algorithmes, la population contient les individus, qui sont indépendants les uns desautres, et seulement quelques phases de l'algorithme nécessite une interaction entre eux,notamment le croisement et la réduction de la population.

Cant'u-Paz [Cahon, 04] a divisé les algorithmes évolutionnaires parallèles en deuxclasses principales :

Parallèlisation globale des algorithmes parallèles : chaque individu de la populationpeut (probablement) toujours se croise avec n'importe autre individu.

46

Les approches à gros grains (modèle d’île) : la population est divisée en plusieurssous-populations où l'accouplement à l'intérieur d'une sous-population est libre, maisl'accouplement entre individus de différentes sous-populations ne peut avoir lieu detemps en temps selon une règle.

3.4.1 Parallélisation globale des algorithmes évolutionnaires

L’évaluation d’un individu est, en général, indépendante de l'évaluation des autresindividus. En effet, pour évaluer un individu il suffit d'accéder à son génome d’unemanière lecture seule. Finalement, seule la valeur du fitness doit être retournée. Dansl’architecture parallèle, il est possible de découper la population (parents ou enfants) onsous-ensembles, et relier chaque sous-ensemble par un processeur pour l’évaluer. Cetteparallélisation ne change pas le comportement de l’algorithme, seulement le tempsd’évaluation est réduit par l’utilisation de plusieurs processeurs pour l’évaluation de lapopulation.

Figure 3.1 Un scénario d'exécution dans le modèle Maître/Esclave [Maitre, 11].

La population est divisée en sous-groupes qui sont envoyés à des nœuds ou desprocesseurs qui effectuent l'évaluation. Une fois cela fait, les valeurs de fitness sontrenvoyées vers le nœud principal, qui dirige la boucle évolutive et affecte les valeurs defitness juste reçus aux individus. Après ces étapes d'évaluation parallèles, la boucleévolutive peut retourner à son fonctionnement séquentiel normal. Ce type deparallélisation est représenté sur la figure 3.1, l'algorithme correspond présenté dans (a)et la phase d'évaluation présentée dans (b) de la figure 3.2.

47

(a) (b)

Figure 3.2 Le modèle Maître/Esclave : (a) Evaluation dans le modèle, (b) AlgorithmeEvolutionnaire par le modèle Maître/Esclave [Maitre, 11].

Ce modèle n'impose pas une architecture matérielle spécifique, comme il existe desvariantes dans de nombreux types de machines, qui sont soit à mémoire partagée oudistribuée, processeurs de type SIMD ou MIMD. La figure 3.3 (a) montre la mise en œuvred'un tel modèle sur une machine à mémoire distribuée, tandis que 3,3 (b) utilise unemachine à mémoire partagée.

(a) (b)

Figure 3.3 Modèle Maître/Esclave pour un algorithme Evolutionnaire parallèle : (a)ModèleMaître/Esclave dans l’architecture à mémoire distribuée. (b) Modèle Maître/Esclave dans

l’architecture à mémoire partagée.à mémoire distribuée. à mémoire partagée.

[Maitre, 11].

48

Avantages

La méthode est totalement comparable avec l’algorithme séquentiel. La portabilité de ce modèle, qui peut être implémentée dans plusieurs architectures

parallèles. L'absence de paramètres supplémentaires par rapport aux algorithmes séquentiels. En

effet, seul le nombre de nœuds doit être spécifié, mais elle n'affecte pas lecomportement de l'algorithme.

Inconvénients

Le traitement de la tâche est rapide par rapport à la quantité de temps nécessaire pourl'échange de données entre le client et le serveur. En d'autres termes, si les messagesqui doivent être échangés prend plus long que le travail prendrait, si elle est effectuéelocalement, la méthode client/serveur ralenti le système.

3.4.2 Les approches à gros grains (modèle d’île)

3.4.2.1 Source d’inspiration

Il y a longtemps, Darwin a indiqué que les populations peuvent avoir une structurespatiale et que cette structure spatiale peut avoir une influence sur la dynamique despopulations. Par exemple, il a remarqué comment, certaines espèces ont évolué différemmentdes autres qui vivaient dans des environnements plus ouverts, quand ils ont été isolés sur desîles. Aussi au début des années 1960 dans le livre de MacArthur et Wilson [MacArthur, 67]ils ont utilisé le modèle de séparation et de migration géographique pour expliquer lesphénomènes de propagation et l’extinction des espèces. Ainsi, les observations de populationsbiologiques réelles offrent un certain nombre d'idées aux chercheurs de calcul évolutif quitentent d'améliorer l'efficacité de leurs algorithmes d’optimisation dans le domaine bio-inspiré[Tomassini, 05].

Les chercheurs n’ont pas tardé à s’inspirer du monde biologique multi-populationscommençant dans les années 1980, on peut citer entre autres, le travail de Grefenstette[Grefenstette, 81], Grosso [Grosso, 85], Tanese [Tanese, 87], et Cohoon [Cohoon, 87] dansles algorithmes génétiques. Dans le cas de méthode Stratégie d’évolution, Rudolph [Rudolph,91] a implémenté l’un des premiers modèles distribués, et aussi Duncan dans [Duncan, 93]était une étape importante dans la programmation évolutive.

3.4.2.2 Le modèle d’île

Le modèle d’île a été proposé comme une extension des algorithmes génétiquetraditionnelle, avec l’intention d’améliorer la diversité des solutions et donc retarder lastagnation. Les premiers travaux ont mentionné l’idée d’utiliser un certain nombre de souspopulations peuvent être datés dès 1967. L’idée de base derrière le modèle d’île estl’introduction d’une structure à la population utilisée dans l’algorithme génétique d’origine, etau lieu de permettre une recombinaison (croisement) entre deux individus quelconque dans

49

l’ensemble de solution, cette possibilité devient restreinte à des solutions appartenant à lamême sous-population dont le nombre varie habituellement de quelques une à quelquesdizaines. Les sous-populations évoluent la plupart du temps de façon indépendante, cependantà certains moments relativement peu abondamment distribués de temps on leur permetd’échanger des solutions dans un processus appelé ‘ La Migration ‘.

De point de vue de la théorie de l’algorithme génétique, le passage du modèle originalau modèle d’île est souvent considéré comme une modification de l’opérateur de sélection,encore on peut considérer le modèle d’île comme l’exécution d’un certain nombred’algorithmes génétique en parallèle avec l’introduction supplémentaire d’un nouveauopérateur appelé ‘ Operateur de Migration ‘ [Izzo, 12].

Operateur de Migration : cet opérateur est lancé sur certains points de temps entre deuxgénérations consécutives de l’algorithme génétique original, et son travail est à la fois desélectionner des individus à partir de l’île courant doivent être envoyé à d’autres îles, ainsiintroduire des individus étrangers à la population locale.

Les algorithmes génétiques sur différente île pourraient facilement utiliser desparamètres différents, par exemple la règle de sélection, l’opérateur de croisement etprobabilité de mutation. Le processus d’optimisation fonctionnerait toujours, et qu’il pourraitencore être plus performant que la variante avec des paramètres fixes dans des îles grâce à lavariabilité supplémentaire. La modification de la structure de l’algorithme génétique de baseest présenté dans la figure 3.4 et l’algorithme dans la figure 3.5.

Figure 3.4 Modèle d’île [Maitre, 11].

50

On peut aller encore plus loin et dire que pour l’opérateur de migration, il n’y a pasd’importance sur le type d’algorithme utilisé dans des îles utilisant les mêmes algorithmes àcondition que toutes les îles utilisent le même codage de solution du problème, et la migrationpeut être branchée sur chaque île.

3.4.2.3 Le modèle d’île généralisé

Le modèle d’île généralisé est un modèle qui permet d’utilisé différents typesd’algorithme sur les îles à condition que les îles ont le même type du codage de solution. Ladéfinition formelle du modèle est donnée comme suite [Izzo, 12]:

On définit un archipel A comme un coupleA=<I,T>

Où : I={I1,I2...In} des îles.

T : La topologie de migration (un graphe orienté avec I comme un ensemble des sommets).

chaque île est un quadruplé : Ii=<Ai , Pi ,S i ,Ri > i=1,2,…n Telles que : Ai : est l’algorithme d’optimisation utilisé par l’île i.

Pi : la population d’île. Si : la politique de sélection de migration.

Ri : la politique de remplacement de migration.

Population Pi : c’est un couple<P ,P > contenant l’ensemble des individus P où la valeur de

fitness est toujours référer au problème P considéré.

Figure 3.5 Algorithme Modèle d’île [Maitre, 11].

51

L’Algorithme d’optimisation Ai : est un processus d’optimisation quelconque, suivant un

opérateur d’évolution P’ A (P,µ) , où µ : dénote l’intervalle de migration (le nombred’itération algorithmiques autorisés avant que une migration est autorisée ). Notons aussi que Apeut également fonctionner sur les populations contenant un seul individu, dans ce cas nousécrivons | P | = 1 (exemple : recuit simulé).

La politique de sélection de migration Si : la politique de sélection S dans l’opérateur de

migration détermine le dème (sous-population) M⊆ P doivent être envoyé à d’autres îles par le

biais de la migration MS (P).

La politique de remplacement de migration Ri : la politique de remplacement dans l’opérateur de

migration spécifié comment M pourrait être insérer dans une population P telle que :

P’R (P , M).

Pseudo-code

L’optimisation de l’ensemble des îles est effectuée en parallèle, et le résultat final del’optimisation est la meilleure solution trouvé sur toutes les îles. Sur chaque île i, le traitement suitle pseudo-code suivant:

Pseudo-code pour l’ île i

1. Initialisation P2. Tant que !(critère-D’arrêt)3. P’ A ( P , µi )4. M S ( P’ )5. /* Envoyer M aux îles adjacents de l’île Ii dans T */6. /*Soit M' l'ensemble des solutions reçues en provenance des îles voisines*/

7. P’’ R (P’ , M’)8. P P’’

Les Paramètres :

(a) Implémentation de Migration : d’après la définition formelle on peut distinguer deux typesd’implémentation Synchrone et Asynchrone. En d’autre terme la communication de toutes lesîles passe à la ligne 5 de 1 block jusqu'à ce que la communication est terminée?.

Asynchrone : c’est le choix évident pour les architectures distribuées.

Avantages

Pas de contrôle global de l’exécution du code sur les îles (peu de contrôle global pourl’initialisation des taches et la collecte des résultats définitifs).

Il offre une bonne évolutivité (scalability).

Utilisation maximale des ressources de calcul disponibles.

52

Inconvénients

Puisque le temps de traitement sur les îles est généralement imprévisible (impossible deprévoir quand les évènements de migration se produisent).

Algorithmes non déterministe, difficile à contrôler ou à déboguer.

Synchrone : La communication entre toutes les îles est synchronisée.

Avantages

Il est possible d’obtenir un processus déterministe. Réglé tous les problèmes (inconvénients) de la méthode asynchrone.

Inconvénients

Une surcharge potentiellement importante résultant de la synchronisation de toutes les îles(la plus lente île détermine le temps d’exécution de l’ensemble du processus, ainsi laprésence d’un mécanisme de synchronisation globale limite la vitesse et l’évolutivité dusystème).

(b) Nombre des îles N : il peut y avoir des facteurs influençant le choix de N pour uneapplication particulière : La plateforme de calcul utilisé.

Le nombre des machines disponible.

Le choix de la topologie de migration.

Avec les progrès en technologie de calcul, ce choix devient maintenant de moins en moinscontraint par le matériel. On peut créer un archipel dans lequel les différentes îles utilisentdifférentes combinaisons de paramètre et nous espérons que les îles de bons paramètresconduisent le processus d’optimisation, ce qui compense pour l’autre (île sous-performant)[Izzo, 09]. Plus le nombre des îles est grand, plus le choix devient important de la topologie demigration, par exemple, on compare les archipels de 8 et de 1024 îles, pour une topologieentièrement connectée, cela signifié près de 20000 connections entre les îles, alors que pour latopologie hyper cube l’augmentation n’est que de 500 fois.

(c) La topologie de Migration T : un autre paramètre de l’archipel est la topologie de migrationT , aujourd’hui la disponibilité des architectures de calcul distribuer offrent une grandeflexibilité, et la topologie de migration peut être choisit de manière approprié pour la tâche àaccomplir. Le choix de la topologie de migration a fait l’objet d’une étude précédente[Rucinski, 10] où l’effet du choix de topologie a été lié à la qualité du résultat final.

De point de vue de la circulation de l’information dans un archipel, les paramètres lesplus pertinents du graphe de topologie sont :

La durée moyenne d’un trajet entre deux îles. Le nombre d’arrêts (qui peut être considéré comme la mesure des frais généraux de

communication).

Le degré de connectivité (nombre maximum ou moyen de voisins par île).

53

Différents types de topologie de Migration sont représentés dans la figure 3.6.

(d) L’intervalle de Migrationµ : l’intervalle de migration µ (fréquence de Migration)

détermine le nombre d’itérations de l’algorithme d’optimisation A avant la production

d’une Migration. La valeur de µ doit être choisir en tenant compte des propriétés de

l’algorithme de d’optimisation A i en particulier le taux de convergence de l’algorithme par

rapport à P’ .Le choix de l’intervalle de migration doit être poursuivi au moins par

l’observation expérimentale de l’état d’avancement de l’optimisation sur une île isolée.

Une autre idée est d’utilisée un intervalle de migration qui change dynamiquement, eteffectuant seulement la migration quand l’algorithme arrive à une stagnation [Izzo, 12].

(e) La politique de sélection S i et de remplacement Ri de Migration : le modèle d’îlenécessite la spécification de deux opérateurs :

Opérateur de sélection : la stratégie de la sélection des individus de la population localequi doivent être envoyés à l’île adjacente.

Opérateur de remplacement : la stratégie de remplacement ou d’intégration des individusentrant dans la population locale.

Pour ces deux opérateurs, on peut utiliser plusieurs politiques tell que : la roulette(Roulette Wheel selection), sélection par tournois, sélection par rang, élitisme, aléatoire.

3.5 Plates-formes de métaheuristiques parallèles

De nombreuses plates-formes pour l’optimisation combinatoire ont été développées.Dans le tableau 3.1, une étude comparative et non-exhaustive de quatorze plates-formeslogicielles de métaheuristiques a été présentée dans [Belkhelladi, 10]. Toutes ces plates-

Figure 3.6 Topologies de migration [Izzo, 12].

54

formes sont orientées-objet, excepté CSM-PGA et sont dédiées à la réutilisation de code et deconception.

Les différentes plates-formes sont classées selon les critères suivants : la classe desmétaheuristiques supportées (algorithmes Évolutionnaires (AE) et/ou métaheuristiques à basede Recherche Locale (RL)), les modèles parallèles implémentés (topologies), le langage deprogrammation utilisé pour son développement, et enfin le support sous-jacent utilisé pour lamise en œuvre de la concurrence et/ou des communications (conc./com.). Le (-) dans letableau indique que l’information n’est pas renseignée. Selon les deux premiers critères, lesplates-formes de métaheuristiques sont divisées en trois catégories : celles dédiées aux AE,aux RL et celles supportant ces deux classes.

Plate-forme R.L A.E Topologies Langage Conc/Comm.

EasyLocal++ √ × - C++ -

MAFRA √ √ - Java -

J-DEAL × √ M./E. Java Sockets TCP/IP

EO × √ - C++ -

Localizer++ √ × - C++ -

DREAM × √ Coop. Insulaire Java Threads,Sockets TCP/IP

CoP √ √ Cellulaire C++ MPI,PVM

D-BEAGLE × √ M./E. C++ Sockets TCP/IP

ParadisEO √ √ Toutes C++ MPI,PVM, PThreads

MAGMA √ √ - C++ MPI,PVM, PThreads

ECJ × √ Coop. Insulaire Java Threads, Sockets TCP/IP

MALLBA √ √ Toutes C++ Netstream, MPI

CSM-PGA × √ Centralisée C SocketsTCP/IP

MAF-DISTA × √ Coop. Insulaire Java Java events, Java RMI

Table 3.1 Taxonomie des Plates-formes de métaheuristiques parallèles [Belkhelladi, 10].

Easylocal++(An object-oriented plate-forme for flexible desi&gn of local searchalgorithms)EasyLocal++ est une plate-forme C++ pour le développement de métaheuristiques à base

de recherche locale (grimpeurs, récuit simulé et recherche tabou), conçue par Di Gaspero et

55

Schaerf (2000). L’architecture pertinente de composante adoptée à la conception favorise unegrande réutilisation de modèles et de code.

MAFRA(A java Memetic Algorithms FRAmework)

MAFRA est une plate-forme Java pour le développement d’algorithmes mémétiques (i.e.,algorithmes évolutionnaires hybridés avec une recherche locale se substituant généralement àla mutation). La conception de modèles co-évolutionnaires d’AEs est aussi supportée, mais ledéploiement à l’exécution reste séquentiel.

J-DEAL (the Java Distributed Evolutionary Algorithms Library)

Est une autre plate-forme portable, développée en Java, pour la conception de méthodesévolutionnaires. Elle est libre de tout paradigme (algorithmes génétiques, stratégiesévolutionnistes, etc.). J-DEAL permet le déploiement sur architectures distribuées de modèlesreposant sur le paradigme « Maître/Esclave ». J-DEAL intègre des outils pour la générationautomatique de statistiques à l’exécution et le repli/dépli de l’état d’exécution au niveauapplicatif de façon transparente.

EO (Evolving Objects)

EO est une plate-forme libre et portable en C++ pour le développement d’applications àbase d’algorithmes évolutionnaires. Elle autorise différents paradigmes (algorithmesgénétiques, programmation évolutionnaire, stratégies évolutionnistes, programmationgénétique), et supporte la modélisation de problèmes multi-objectifs. EO couvre une grandediversité d’opérateurs génétiques génériques (sélection, remplacement, etc.). Aucun supportpour le parallélisme ou l’hybridation n’est assuré. La plate-forme EO assure différentsservices tels que la sauvegarde/reprise au niveau applicatif, la production de statistiques,l’analyse de paramètres en ligne caractérisant les aspects génériques du processus del’évolution, etc.

Localizer++(An open library for local search)

Localizer++ constitue une autre plateforme C++ pour l’implémentation demétaheuristiques à base de solution unique très proche de EasyLocal++. Comme cettedernière, elle permet la mise en œuvre de différentes formes d’hybridation mais ne supportepas le déploiement de modèles coopératifs sur environnements parallèles ou distribués.

DREAM(A framework for distributed evolutionary algorithms)

DREAM désigne une infrastructure logicielle de type « pair à pair » et considère un «pool » virtuel de ressources de calcul distribuées, où les différentes étapes d’un AE sontexécutés de manière automatique et transparente. La portabilité est assurée par le langageJava. DREAM est couplée avec l’interface utilisateur GUIDE, le langage de spécificationEASEA et la plate-forme évolutionnaire JEO (cf. figure 3.7). L’originalité de DREAM résidedans une facilité d’utilisation variable à l’exploitation. Il est en effet possible pour l’utilisateurd’opter pour une interface de spécification adaptée à son niveau de maîtrise technique.

56

L’interface graphique GUIDE constitue la plus simple d’entre elles, et permet l’exploitationde la plate-forme par des non-informaticiens. Différents panneaux sont respectivement dédiésà la modélisation du génome et des opérateurs de variation (à partir de structures prédéfinies),à la caractérisation du processus d’évolution (sélection, remplacement, etc.) et enfin à ladéfinition de paramètres liés au déploiement sur environnements distribués. Seul le modèlecoopératif insulaire est intégré dans la plate-forme. Aussi, GUIDE permet de définir lesstratégies de sélection, remplacement, et topologies mis en œuvre.

CoP (Cooperating Populations)

CoP est une plate-forme pour la modélisation et l’implémentation séquentielle et parallèledes algorithmes évolutionnaires en tant qu’un ensemble de populations en coopération. Ils’agit d’un modèle récursif multi-niveau permettant la mise en œuvre de tout type d’AE entout genre de matériel, CoP peut être décrit comme suit : Le premier niveau est constitué depopulations d’individus vivant dans des îlots qui sont en mesure de communiquer les uns avecles autres. À un deuxième niveau, les populations des îlots peuvent constituer une entité plusimportante avec l’îlot considéré comme un individu. À un niveau plus élevé, ces grandesentités peuvent également former une population, chacune considérée comme un individu. Laprocédure peut continuer jusqu’au niveau requis. Le niveau initial de CoP (CoP0) peut décrireà la fois les implémentations cellulaire et séquentielle de l’AE mis en œuvre, de sorte quechaque individu de (CoP0) correspond à un gène. CoPDEB est au niveau 1, c’est-à-dire,(CoP1). Dans (CoP1), chaque individu est une (CoP0) et correspond à un îlot. Chaque îlot a sapropre population, qui évolue en parallèle avec les populations des autres îlots.

Figure 3.7 Architecture DREAM [Belkhelladi, 10].

57

D-BEAGLE (Distributed beagle : An environment for parallel and distributedevolutionary computations)

Elle se définit comme une version distribuée de la plate-forme portable C++ OpenBAEAGLE. Elle couvre deux paradigmes que sont les algorithmes génétiques et laprogrammation génétique. Les modèles de conception de ces méthodes évolutionnairesreposent sur STL9. Le parallélisme à l’exécution est restreint au paradigme «Maître/Esclave»,la communication repose sur le mécanisme des sockets TCP/IP.

MAGMA (Multi-AGentMetaheuristics Architecture)

Les objectifs recherchés sont de pouvoir comparer les métaheuristiques existantes afin defaciliter leur hybridation et leur implantation. Dans cette approche, une métaheuristique est unsystème multi-agents composé de quatre niveaux. Chaque niveau dispose d’agents spécialisésdans le traitement d’une tâche générique. La figure 3.8 représente les différents niveauxidentifiés dans l’approche MAGMA. Le niveau 0 est composé d’agents chargés de générer denouvelles solutions pour les niveaux supérieurs. Le niveau 1 permet d’améliorer des solutionsen utilisant des procédures telles que la recherche locale. Les agents du niveau 2 servent àcontrôler le rapport diversification/intensification. Enfin, si plusieurs stratégies de recherchecoexistent déjà dans le niveau 2, les agents de niveau 3 permettent de les coordonner.

ParadisEO

ParadisEO est une plate-forme Open Source développée par l’INRIA de Lille. C’est uneextension de la plate-forme EO (Evolving Objects) initialement conçue pour l’implantationd’algorithmes évolutionnaires. Les principaux objectifs de cette plateforme sont tout d’abord,de pouvoir réutiliser du code pour faciliter et accélérer le développement de métaheuristiques.

Figure 3.8 Architecture MAGMA [Belkhelladi, 10].

58

Ensuite, l’architecture de la plate-forme a été conçue de manière à permettre ledéveloppement de nouvelles métaheuristiques ou de métaheuristiques hybrides.

Enfin, ParadisEO fournit des solutions pour l’exécution distribuée des algorithmes.L’architecture de ParadisEO est composée de trois couches : Solvers, Runners et Helpers. LesHelpers forment la « couche basse » de la librairie qui fournit les composants de base desmétaheuristiques tels que les opérateurs évolutionnaires (mutation, croisement, sélection) oules méthodes de déplacement dans un voisinage. Les Runners correspondent aux différentesmétaheuristiques définies à partir des Helpers. Les Solvers correspondent aux processuschargés d’exécuter et éventuellement de coordonner la ou les métaheuristiques. ECJ (A java-based evolutionary computation research system)

ECJ constitue une plate-forme Java très riche et portable couvrant les méthodesévolutionnaires et la programmation génétique. Elle apparaît très flexible et simple àl’utilisation puisque la majorité des classes et composants sont identifiés dynamiquement àl’exécution après l’analyse d’un fichier de paramètres. ECJ intègre des représentationsprédéfinies, mais autorise la définition de nouvelles structures. La plate-forme supporte lamise en œuvre du modèle coopératif insulaire d’AEs et son déploiement sur architecturesparallèles ou distribuées par une utilisation des technologies « TCP/IP sockets » et « JavaThreads ». D’autres aspects couvrent l’optimisation multi-objectif, la sauvegarde/reprise del’exécution, des outils pour le traçage, etc.

Mallba(a software library to design efficient optimisation algorithms)

Mallba intègre un ensemble de « squelettes » logiciels implémentant la plupart desmétaheuristiques (algorithmes génétiques, recuit simulé, recherche Tabou, etc.) mais aussi lesméthodes exactes (Branch&Bound, Programmation dynamique, Divide&Conquer). Lessquelettes définissent les patrons d’algorithmes génériques. La performance à l’exécution estassurée par de nombreux modèles parallèles facilement déployables sur environnementsd’exécution distribués de différentes échelles (LAN/WAN). Mallba repose sur l’interface decommunication ah hoc Netstream pour la communication.

MAF-DISTA (Mobile Agent Framework for Distributed Algorithms)

MAF-DISTA est une plate-forme permettant de modéliser et d’implémenter lesalgorithmes à population sous forme de plusieurs agents de recherche. Dans une instance deMAF-DISTA, chaque algorithme de recherche est encapsulé dans un agent, une entitéautonome qui doit garder la connaissance du problème d’optimisation à résoudre. Les agentssont coordonnés par un ensemble de règles stipulant les aspects topologiques et decommunication (migration), ces règles pouvant être fixées a priori ou être changées lors del’exécution par l’intermédiaire d’une entité de coordination dite « méta-agent».

MAF-DISTA se distingue des plates-formes existantes en introduisant les conceptspermettant de traiter la distribution et l’adaptation dans les métaheuristiques parallèles à basede population. Dans cette plate-forme, les composants (agents) ne sont pas stationnaires et

59

sont capables de migrer d’une machine à une autre pour une meilleure exploitation desressources inutilisées.

3.6 Conclusion

Ce chapitre nous a permis de présenter les métaheuristiques parallèles. Nous avonscommencé par une classification des métaheuristiques parallèles, pour présenter par la suiteles approches de conception utilisées pour les métaheuristiques. On a pris ensuite lesalgorithmes évolutionnaires parallèles, et comme exemple d’application le modèle d’île etgénéralisé avec le modèle d’île généralisé. Enfin, une étude comparative et une analysecritique de quelques plates-formes logicielles dédiées aux métaheuristiques parallèles entenant compte de quelques-uns de ces critères sont présentées. D’après cette étude la majoritédes plates-formes se focalisent généralement sur une classe de métaheuristiques (AlgorithmesEvolutionnaires, Métaheuristique à base de recherche locale) excepté la plate-formeParadisEO qui se focalise sur les deux classes.

60

CHAPITRE 4 : L’APPROCHE PROPOSEE POUR LA SEGMENTATION D’IMAGEPAR MULTISEUILLAGE

4.1 Introduction

L’utilisation du calcul parallèle et les métaheuristiques dans le traitement d’image estun volet vaste. Dans ce qui suit, nous allons aborder l’approche proposée pour lasegmentation d’image par multiseuillage qui est basée sur l’utilisation de l’optimisationdistribuée dans le but d’obtenir à la fin une meilleure segmentation d’image.

4.2 Démarche de conception

4.2.1 Problématique

Le problème de la segmentation d’image est un cas particulier du problème departitionnement des données. Ce dernier étant un problème NP-Difficile. Ces problèmespeuvent être exprimés sous la forme générale d’un problème d’optimisation.

Jusqu’à ce jour, il n’existe pas de méthode universelle de segmentation d’images. Toutetechnique n’est efficace que pour un type d’images donné, pour un type d’applications donnéet dans un contexte informatique donné. En raison de ces contraintes, plusieurs stratégies desegmentation ont été proposées.

Afin d’améliorer les résultats de segmentation, des méthodes bio-inspirés ou inspirées dela nature ont été alors utilisées pour résoudre le problème posé.

Le problème de segmentation d’image est de type NP-difficile, signifiant qu’il n’existe pasd’algorithmes produisant une solution optimale en un temps d’exécution polynômial parrapport à la taille des données manipulées. La résolution du problème est toujours limitée parla capacité des ressources matérielles utilisées (puissance de calcul, mémoire, etc.).

Pour le problème de segmentation d’image par multiseuillage, pour une image en 256niveaux de gris, l’ensemble des cas possibles à évaluer pour déterminer les seuils optimumspeut être calculé comme suit :

Nombres des cas possibles = + + +…+

= 1,15792 * 10 77

4.2.2 Approche proposée

Même si les méthodes bio-inspirés offrent des stratégies efficaces pour la recherche desolutions de problèmes de segmentation d’image, le temps de calcul associés à l’explorationde l’espace de recherche peut être très important. Il y a aussi le risque de rester bloquer au

61

niveau des minimums locaux. Une façon d’éviter ces problèmes est l’utilisation de lacoopération des métaheuristiques parallèles.

Pour résoudre le problème d’optimisation de la segmentation d’image par multiseuillage,notre approche consiste à utiliser le modèle d’île généralisé GIM décrit dans le chapitreprécédent.

4.2.3 Le modèle de conception

Notre système se compose d’un nombre d’îles, chacune est une instance d’unalgorithme de segmentation d’image suivants : l’algorithme essaim de particule (PSO),l’algorithme des abeilles (ABC) et l’algorithme génétique (GA). Tous les algorithmes utiliséssont basés population. Les îles s’exécutent en parallèle et en coopération par l’utilisation del’opérateur de migration qui consiste en l’échange d’un sous-ensemble de solutions à chaquenombre d’itérations µ . Le flux de communication circule entre les îles dans les deuxdirections (bi-direction). La topologie de migration est entièrement connectée. La figure ci-dessous illustre la conception du modèle proposé pour résoudre le problème de lasegmentation d’image par multiseuillage.

Figure 4.1 Le modèle proposé GIM.

4.2.4 L’architecture du modèle

Nous commençons par la description du modèle d’île avec ces différents paramètresqui sont: le type d’implémentation de migration, la topologie de migration, l’intervalle demigration, la politique de sélection et de remplacement de migration et le nombre des îlesutilisées. Le tableau 4.1 récapitule les différents paramètres utilisés dans le modèle GIM.Ensuite nous détaillons les algorithmes d’optimisation utilisés dans chaque île (adaptation auproblème de la segmentation d’image par multiseuillage, les paramètres utilisés pour chaquealgorithme). Les résultats seront décrits au chapitre suivant.

Migration

GIM

EntréeSortie

Image, NbSeuilsImage

Segmentée

ÏLE 1

ÏLE 2

ÏLE 4

ÏLE 3

62

Paramètres Type

Type d’implémentation de migration Asynchrone

La topologie de migration Entièrement connecté

L’intervalle de migration Plusieurs tests ont été faits.

La politique de sélection de migration Elitiste

La politique de remplacement de migration Remplacement élitiste

Le nombre des îles utilisé Deux & trois

Algorithmes utilisés

Algorithme génétique Optimisation par essaim de

particules La colonie d’abeilles artificielles

Table 4.1 Les paramètres du modèle.

Les algorithmes d’optimisation utilisés :

A. Algorithme génétique AG :

La version adoptée de l’algorithme génétique est celle définie dans [Mitchell, 96] qui

consiste en cinq étapes :

Algorithme :

1. La génération de population de N chromosomes

1. N : sois la taille de population2. L : le nombre de seuils pour un chromosome x.

2. Calculer la valeur de fitness φ(x) pour chaque chromosome x dans lapopulation.

3. Répéter jusqu’à la création de N enfants.1. Sélectionner deux parents pour faire le croisement.

2. Produire l’enfant y en utilisant l’opération de croisement et de mutation

4. Remplacer la population actuelle par la nouvelle crée.5. Aller à l’étape 2.

63

Codage de donnée :

Chaque chromosome est défini par un vecteur d’entiers positifs (valeur ∈ [0, 255]).

Pour un algorithme de seuil = 2, la taille du chromosome=2, ex :




Fonction d’adaptation

La fonction calculée est celle de la formule d’Otsu généralisée utilisant la variance

interclasse pour la détermination de meilleurs seuils (décrite au chapitre 2).

Opération de sélection

Pour chaque individu, la probabilité d'être sélectionné est proportionnelle à sonadaptation au problème (fitness). La méthode de sélection utilisée est la sélection parroulette (Roulette Wheel selection). Le principe de la sélection par roulette est celui de laroue de la fortune biaisée. Cette roue est une roue de la fortune classique sur laquelle onassocie à chaque individu un segment dont la longueur est proportionnelle à son fitness.On effectue ensuite un tirage aléatoire utilisé dans les roulettes de casinos avec unestructure linéaire. Avec ce système, les grands segments, c'est-à-dire les bonschromosomes seront plus souvent adressés que les petits.

Opération de Croisement

Nous utilisons le croisement à un point, pour notre modèle on a utilisé 2, 3, 4 et 5 seuils :

Exemple 2 seuils :

Parent 1 Croisement Parent 2

Enfant1 Enfant 2

Après on choisit le premier enfant comme résultat.

Opération de Mutation

Génération d’un nombre aléatoire entre [0,1]. Si le nombre généré aléatoirement estinférieur ou égal à 0.02, on génère un nombre aléatoire dans l’intervalle [1, Nombre deseuils] et un autre nombre aléatoire entre [0.255], puis on l’insère à l’intérieur del’enfant.

65 154 230

65 95 154 230

6 40 95 154 230

65 95

65 126 90 220×65 220 90 126

64

B. Optimisation par Essaim de particules OEP

Codage de donnée :

Chaque particule est défini par un vecteur d’entiers positifs (valeur ∈ [0,255]).

Pour un algorithme OEP de seuil = 2, la taille de particule=2, ex :




Fonction d’adaptationLa fonction calculée est celle de la formule d’Otsu généralisée utilisant la variance


Algorithme utilisé

La version utilisée est la suivante :

Algorithme

Initialisation des essaims particulaires (initialise , , , )

Répéter

Pour chaque particule.

Calculé la fitness ( ) de chaque particule

Mise à jour ,

Mise à jour ,Fin pour

Jusqu'à (critère d’arrêt).

A chaque itération de l'algorithme, une fonction de fitness est utilisée pour évaluer laréussite de la particule. Pour modéliser l'essaim, chaque particule n se déplace dans unespace multidimensionnel selon la position et la vitesse qui dépendent fortementde , .

=W +p1r1( - )+p2r2( - )

65 154 230

65 95 154 230

6 40 95 154 230

65 95

65

= +

La première équation met à jour la vitesse de la particule. Le terme signifie lavitesse au temps t + 1. La nouvelle vitesse dépend de trois termes :

le premier terme est W* : le facteur W est appelé la masse d'inertie, est lavitesse actuelle au temps t.

le second terme est p1r1( - ) : le facteur de p1 est une constante appelée lepoids cognitif (ou personnel ou local), r1 est une variable aléatoire dansl’intervalle ]0, 1[, le est la position idéale de la particule trouvée jusqu'àprésent, le est la position actuelle de la particule.

Le troisième terme est p2r2( - ) : le facteur de p2 est une constante nomméepoids social (globale), le facteur r2 est une variable aléatoire dans l’intervalle]0, 1[ et est la meilleure position trouvée jusqu'à présent.

Une fois la vitesse est déterminée, elle est utilisée pour calculer la nouvelleposition de particule n.

Le réglage minutieux de ces paramètres mènera à de meilleurs résultats.

C. Algorithme de colonie d’abeilles artificielles

Codage de donnée :

Chaque abeille est définie par un vecteur d’entiers positifs (valeur ∈ [0,255]).

Pour un algorithme d’abeille de seuil = 2, la taille d’abeille=2, ex :




Fonction d’adaptation

La fonction calculée est celle de la formule d’Otsu généralisée utilisant la variance


Algorithme utilisé

La version utilisée est la suivante :

65 154 230

65 95 154 230

6 40 95 154 230

65 95

66

Algorithme

1/ Initialisation de population N

Créer un ensemble de population qui représente des solutions de manière aléatoire. Chaquesolution est représentée dans un vecteur d’entiers de taille égale au nombre de seuils donné.

2/ La phase des abeilles employées

Pour chaque abeille employée

Choisir un voisin xj

Créer une nouvelle solution v = xi + rand()(xi - xj)

Comparer la fitness de fit(xi) et fit(v) et choisir la meilleur.

Le compteur ‘traili’ est incrémenté si fit(xi) >fit(v).

3/ la phase des abeilles spectateur

Pour chaque solution

Calculer fit(xi)

Calculer la probabilité de sélection prob(xi) =( )∑ ( )

Pour chaque solution :

Choisir xi on utilise (sélection par la roulette) Choisir un voisin xj

Créer une nouvelle solution v = xi + rand()(xi - xj)

Comparer la fitness de fit(xi) et fit(v) et choisir la meilleur. Le compteur ‘traili’ est incrémenté si fit(xi) >fit(v).

4/ la phase des abeilles scouts

Pour chaque solution i on vérifié si ( ‘traili’ > Limite) alors on crée une nouvelle solution xi .

Fin de l’algorithme

4.2.5 L’implémentation

L'approche proposée est mise en œuvre en utilisant l'environnement Matlab et sesboites à outils ‘ Matlab toolboxes ’. L'ensemble des images sont lues et manipulées à l'aide de« Matlab toolbox » et ‘ Parallel Computing Toolbox ’ pour le parallélisme.

Pour ce faire, nous utilisons la commande SPMD qui permet de définir un bloc decode à exécuter simultanément sur plusieurs configurations (workers). La forme généraled'une déclaration SPMD est comme suit :

67

spmd

<Instructions>

Fin

Les applications typiques appropriées pour SPMD sont ceux qui requièrent l'exécutionsimultanée d'un programme sur des ensembles de données multiples lorsque lacommunication ou la synchronisation est nécessaire entre les configurations. SPMD permet àplusieurs configurations "workers" de calculer des solutions simultanément.

Dans ce qui suit, nous expliquons la façon dont nous avons mis en œuvre notreapproche en utilisant le parallélisme en MATLAB. Il y a deux façons de mettre en œuvrenotre approche dans MATLAB. Nous pouvons utiliser le calcul parallèle de Matlab PCT(Parallel Computing Toolbox) ou le serveur de calcul distribué de Matlab MDCS (MatlabDistributed Computing Server). Dans le présent travail, nous utilisons PCT de MATLAB quis'exécute sur une seule machine de bureau. Le pseudo-code en Matlab en ce qui concernenotre approche peut être résumé comme suit:

Pseudo-code pour la segmentation d’image dans MATLAB

Entrée: Image, nombre de seuilsmyCluster = parcluster(‘local’); myCluster.NumWorkers = 3;

Matlabpool (3);Spmd

Switch labindex

Case 1, Appliquer l'algorithme d’île 1Case 2, Appliquer l'algorithme d’île 2Case 3, Appliquer l'algorithme d’île 3

Fin / * switch / *Fin / * spmd / *

Recueillir les trois fitness des îles 1, 2, 3.Choisir la plus grande fitness pour obtenir la meilleure segmentationMatlabpool close

Sortie: Les meilleurs seuils pour la segmentation

68

Pseudo-code pour l’ île i

Algorithme : île(img, nombseuils)

Entrées : img, nombseuils /*une image et le nombre de seuils*/

P : la population initiale

S : la stratégie de sélection

R : la stratégie de remplacement

A : l’algorithme d’optimisation appliquer dans l’île i

µi : nombre d’itérations dans A.

1. Initialisation P2. Tant que !(critère-d’arrêt)3. P’ A ( P , µi )4. M S ( P’ )5. LabSend M /* Envoyer M aux îles adjacents de l’île Ii dans T */6. M’LabReceive /*Soit M' l'ensemble des solutions reçues en provenance des

îles voisines*/7. P’’ R (P’ , M’)8. P P’’

Fin.

Les deux instructions LabSend et LabReceive sont deux fonctions de la boîte à outilsdu calcul parallèle dans Matlab (Parallel Computing Toolbox). Elles sont utilisées pour lacoopération entre les îles.

4.2.6 Architecture détaillée du modèle proposé

Au départ, chaque île (métaheuristique) dans GIM évolue indépendamment en fonction desa propre dynamique. Après μ itérations un ensemble de solutions est sélectionné pour lamigration. Une fois que les îles reçoivent un ensemble d'individus émigrés, une stratégied'intégration est utilisée pour générer une nouvelle population dans chaque île. Dans notretravail, une certaine forme d'élitisme (sélection de la meilleure solution) est utilisée dans:

1. La stratégie de sélection: choisir la meilleure solution dans chaque île et l'envoyer.

2. Stratégie d'intégration (remplacement): dans chaque île toutes les solutions reçuessont classées et le choix des meilleures est utilisé pour intégrer la nouvelle solutiondans l'île avec l’élimination du même nombre de mauvaises solutions.

L'architecture générale du modèle GIM proposé est illustrée dans la figure 4.2.

69

Figure 4.2 Architecture détaillée du modèle.

GIM

GA ABC PSO

Population P2Indiv1

Inten1 Inten2 … IntenJ

:IndivNInten1 Inten2 … IntenJ

Abeilles employées

Abeilles spectateurs

Les scouts

Population P1Indiv1



Selection(IndivX,IndivY) (Roulette Wheel)

Croisement(IndivX)X(IndivY)

MutationIndivXY


Après µ itérations

Population P3Indiv1



Pour toutes les particules

Evaluer la fitness

Mise à jour Vt+1

Mise à jour xt+1

Fin

M=(bestIndiv)

Envoyervers-ABC(M)

Envoyervers-PSO(M)

M1=Recevoir (ABC)

M2=Recevoir (PSO)

M=(bestIndiv)

Envoyervers-PSO(M)

Envoyervers-GA(M)

M1=Recevoir(PSO)

M2=Recevoir(GA)

M=(Meilleure Indiv)

Envoyervers-GA (M)

Envoyervers-ABC(M)

M1=Recevoir(GA)

M2=Recevoir(ABC)

Intégrer(M1,P1)

Intégrer (M2,P1)

Intégrer (M1,P2)

Intégrer (M2,P2)

Intégrer (M1,P3)

Intégrer (M2,P3)

70

4.6 Conclusion

Nous avons présenté dans ce chapitre une nouvelle approche d’optimisation desegmentation d’image par mutliseuillage. L’approche utilise le modèle d’île généralisé avecun ensemble d’algorithmes bio-inspirés tels que l’algorithme génétique, l’algorithmed’optimisation par essaim de particules et l’algorithme de colonie d’abeilles. Tous lesalgorithmes sont basés population. Les îles s’exécutent en parallèle et coopèrent en utilisantl’opérateur de migration. Une fois que les îles ont reçu un ensemble d'individus émigrés, unestratégie d'intégration est utilisée pour générer une nouvelle population dans chaque île.

Cette approche a été implémentée en parallèle en utilisant la boîte à outils PCT(Parallel Computing Toolbox) de Matlab, et a été testée sur des images standards. Lesrésultats expérimentaux ont montré que l’approche est efficace et fournit des résultats trèsencourageants et très prometteurs (voir chapitre suivant).

71

CHAPITRE 5 : EXPÉRIMENTATION & VALIDATION

5.1 Introduction

Après avoir décrit l’approche proposée avec ces différents algorithmes utilisés, nousexposons dans ce chapitre les résultats de l’implémentation des différentes combinaisons del’approche proposée.

5.2 Mesures d’évaluation de la qualité de segmentation

Afin de pouvoir évaluer la qualité de la segmentation d’image obtenue parmultiseuillage, nous avons utilisé la fonction de fitness qui représente la variance interclassed’une image sélectionnée. L'évaluation de la valeur de fitness semble extrêmement importantepour montrer l'efficacité de la nouvelle méthode. En outre, puisque toutes les méthodes bio-inspirés sont aléatoires et stochastiques, les résultats ne sont pas tout à fait les mêmes danschaque itération. Par conséquent, la stabilité des différentes méthodes doit être évaluée par unindice approprié comme la valeur de l'écart type.

STD= ∑ (σ )

où STD est l'écart type, σ est la meilleure valeur de fitness du ième terme del'algorithme, u est la valeur moyenne de , et N est le nombre de fois d’exécutions répétées dechaque algorithme. Nous avons exécuté l’algorithme 20 fois.

5.3 Images de tests utilisées (Benchmarks)

Afin de mieux évaluer les nombreuses méthodes programmées et de valider lesrésultats obtenus, nous avons choisi cinq images de tests. Les images utilisées dans notreapproche sont: Airplane, Butterfly, Hunter, Road et Map. Ces images sont des images enniveaux de gris de taille 512 × 512 codées sur 8 bits.

L’histogramme correspondant de chaque image est le suivant :

72

Figure 5.1 Image Airplane.gif avec son Histogramme.

Figure 5.2 Image Butterfly.gif avec son Histogramme.

73

Figure 5.3 Image Hunter.gif avec son Histogramme.

Figure 5.4 Image Map.gif avec son Histogramme.

74

Figure 5.5 Image Road.gif avec son Histogramme.

5.5 Résultats et discussions

Notre approche consiste à utiliser le modèle d’île généralisé avec trois algorithmes quisont: algorithme génétique, algorithme de colonie d’abeilles et algorithme essaim departicules avec différentes combinaisons, et les tester où chaque algorithme a été exécuté àpart, plus deux variantes de l’algorithme essaim de particules Darwinian essaim de particules(Darwinian PSO [Ghamisi, 12] ) et Ordre Fractionnel d’une Optimisation Darwinienne parEssaim de Particules (Fractional-Order DPSO [Ghamisi, 12] ).

Les différentes variantes de notre approche sont: GIM avec trois OEP (GIM_PSO3),GIM avec trois AG (GIM_GA3), GIM avec trois algorithmes d’abeilles (GIM_ABC3), GIMavec OEP et AG (GIM_PSO_GA), GIM avec OEP et algorithme d’abeilles(GIM_PSO_ABC), GIM avec AG et algorithme d’abeilles (GIM_ABC_GA) et GIM avectrois algorithmes algorithme génétique, algorithme de colonie d’abeilles et algorithme essaimde particules (GIM_PSO_ABC_GA).

Les paramètres utilisés pour l’algorithme essaim de particules et ses variantes ont étéchoisis en tenant compte de plusieurs travaux portant sur l'analyse de convergence del’algorithme PSO traditionnelle [Ghamisi, 12]: p1=1.5, p2=1.5, W=1.2, Vmax=2, Vmin=-2,Xmin=0, Xmax=255.

Le paramètre de l’algorithme génétique utilisé Probabilité_de_mutation=0.02 et pourl’algorithme d’abeilles valeur_Limite=100.

Pour notre modèle les paramètres ont été choisis après plusieurs tests de différentsparamètres (pour plus de détails voir l’annexe). Les paramètres utilisés pour la comparaisonavec d’autres algorithmes sont les suivants :

Nombre d’individus migrant=2,

75

Taux de migration =20,

Nombre d’itération=100, Taille de population=5 pour chaque métaheuristique utilisée.

Toutes les méthodes d'optimisation utilisées sont stochastiques basée population,chacune d'elles est exécutée 20 fois. Les valeurs moyennes et l'écart-type de fitness sontportés dans les tableaux 5.1 et 5.2. Toutes les valeurs de fitness sont calculées pour 2, 3, 4, 5seuils. Aussi les valeurs des seuils optimaux sont portées dans les tableaux 5.3 et 5.4.

Afin d'améliorer la compréhension des tableaux 5.1 et 5.2, la figure 5.11 montre lesvaleurs d'écart-type de fitness pour les algorithmes GIM_PSO_ABC_GA, PSO, DPSO etFODPSO face à différents cas de tests avec différents seuils.

Pour comparer visuellement les résultats de la segmentation par GIM (pour la varianteGIM_PSO_ABC_GA), différents cas d'essai sur les images segmentées à des niveaux deseuils (2, 3, 4, 5) sont données dans les figure.5.6 ; 5.7; 5.8; 5.9; 5.10.

76

Images detests

Seuil GIM_PSO3 GIM_ABC3 GIM_GA3 GIMPSO_ABC

GIMPSO_GA

GIMABC_GA

Airplane

2 1837,7974±0,0000 1837,7974±0,0000 1823,1173±0,0000 1837,7974±0,0000 1837,7974±0,0000 1835,0830±0,00003 1911,7235±0,0000 1911,3198±0,0000 1761,2207±0,0000 1911,5643±0,0000 1911,5954±0,0000 1781,2637±0,00004 1950,2338±0,0000 1953,4491±0,0000 1848,4364±0,0000 1941,4632±0,0000 1936,5389±0,0000 1894,2328±0,00005 1979,0636±0,0000 1965,3480±0,0000 2819,6872±0,0000 1970,9824±0,0000 2785,1663±0,0000 3457,8583±0,0000

Hunter

2 3064,2112±0,0000 3013,2370±0,0000 3016,7380±0,0000 3064,0421±0,0000 3064,2112±0,0000 3044,0109±0,00003 3213,4020±0,0000 3209,7354±0,0000 3261,3710±0,0000 3212,9636±0,0000 3204,1101±0,0000 3792,0856±0,00004 3266,5003±0,0000 4391,4009±0,0000 4406,6031±0,0000 3269,4872±0,0000 3823,9956±0,0000 4460,3776±0,00005 3298,4611±0,0000 5179,4654±0,0000 3885,6031±0,0000 4618,8556±0,0000 4193,1910±0,0000 4392,0891±0,0000

Butterfly

2 1553,0734±0,0000 1553,0734±0,0000 1528,9340±0,0000 1553,0734±0,0000 1553,0734±0,0000 1552,6399±0,00003 1669,2783±0,0000 1553,0734±0,0000 1501,8400±0,0000 1642,5496±0,0000 1642,5496±0,0000 1656,5469±0,00004 1710,2210±0,0000 2269,9939±0,0000 1395,4708±0,0000 1671,8320±0,0000 1696,7289±0,0000 1663,3078±0,00005 1720,5762±0,0000 2245,4472±0,0000 2256,9643±0,0000 1679,1521±0,0000 2275,4268±0,0000 2000,9285±0,0000

Read

2 1321,3739±0,0000 1321,3366±0,0000 2230,6044±0,0000 1321,3739±0,0000 1321,3739±0,0000 1318,3875±0,00003 1433,9844±0,0000 1433,7717±0,0000 1294,4052±0,0000 1433,9844±0,0000 1435,0027±0,0000 1362,0549±0,00004 1489,8798±0,0000 1476,5194±0,0000 1672,0296±0,0000 1488,8495±0,0000 1488,8495±0,0000 1502,2211±0,00005 1519,9751±0,0000 1990,1990±0,0000 1857,2505±0,0000 1496,6914±0,0000 1496,5424±0,0000 1458,8490±0,0000

Map

2 2340,3950±0,0000 2340,3950±0,0000 2230,6044±0,0000 2340,3950±0,0000 2340,3950±0,0000 2340,3950±0,00003 2529,9384±0,0000 2529,9384±0,0000 2393,9667±0,0000 2523,8673±0,0000 2523,8673±0,0000 2343,9571±0,00004 2621,1476±0,0000 2567,1891±0,0000 2785,4254±0,0000 2621,1476±0,0000 2621,1476±0,0000 2541,1432±0,00005 2670,0640±0,0000 3177,2335±0,0000 2766,3166±0,0000 2641,3359±0,0000 2617,2963±0,0000 2679,0217±0,0000

Table 5.1: Moyenne ± écart-type valeurs de fitness de différentes méthodes pour différents cas de test.

77

Images detests

SeuilGIM

PSO_ABC_GAPSO DPSO FODPSO ABC GA

Airplane

2 1837,7974±0.0000 1837,7310±0,1018 1836,8138±1,2976 1835,7028±2,4037 1803,9942±54,6139 1678,0305±175,90763 1911,5643±0.0000 1909,6157±2,0224 1906,1426±4,6765 1906,0265±4,5902 1855,5674±61,8255 1929,8225±354,96574 1947,7398±0.0000 1951,3422±2,5273 1945,8687±5,1840 1944,2988±6,1697 1977,9077±312,9484 1953,2363±760,62245 2748,1524±0.0000 1973,9205±3,1488 1970,2721±5,4231 1968,8307±8,0050 2638,8344±631,0924 2284,5193±936,9975

Hunter

2 3064,0421±0.0000 3064,1011±0,1169 3062,1472±4,1876 3061,2085±5,3224 2952,1878±157,4443 2638,6326±340,59613 3212,9636±0.0000 3208,8812±5,5492 3207,2647±6,1878 3197,8231±12,0415 3132,7237±80,2824 3131,2078±512,00714 4031,5225±0.0000 3265,6467±3,3608 3259,2264±7,9854 3257,1540±7,2163 3503,0862±531,2454 3386,1193±496,42115 5702,7598±0.0000 3301,1374±4,8927 3290,8260±10,3814 3292,2227±7,1411 4362,7121±513,9246 4064,2108±579,9306

Butterfly

2 1553,0734±0.0000 1552,9461±0,2495 1551,0461±4,1422 1549,5025±3,5650 1403,2972±164,3180 1305,1311±208,46203 1667,7736±0.0000 1666,6558±3,8450 1660,1752±10,0777 1657,6316±14,4243 1473,7464±215,5030 1305,9368±449,57274 1689,4965±0.0000 1705,0772±4,1611 1692,9992±13,6045 1692,8054±10,3390 1559,2420±421,1454 1353,1159±637,77715 1737,5037±0.0000 1725,2421±7,7469 1716,4750±8,3681 1714,9299±10,6187 1476,4781±546,1395 1416,7870±839,4405

Road

2 1321,3739±0.0000 1321,2026±0,6282 1319,9599±1,9766 1320,4875±1,5183 1268,7535±95,0756 1107,0246±174,23113 1433,9844±0.0000 1432,1169±1,8746 1429,1783±3,8233 1425,0570±6,3098 1377,1935±53,1370 1072,5665±332,25944 1603,0139±0.0000 1485,6145±3,7683 1481,5790±7,4168 1479,1646±7,6112 1425,4916±51,6392 1370,7494±156,13045 1718,0013±0.0000 1514,8469±3,1983 1509,7751±5,6727 1505,9589±6,6323 1558,5341±205,0645 1420,7718±304,9680

Map

2 2340,3950±0.0000 2340,3950±0.0000 2338,7860±4,9523 2336,3725±7,1481 2207,3962±195,4171 1991,7843±268.66953 2529,9384±0.0000 2529,0651±1,8501 2525,8072±7,2890 2524,6285±11,4847 2384,3791±160,0829 2024,9845±489.43954 2621,1476±0.0000 2617,9777±6,0990 2612,6259±8,7051 2611,5385±6,5741 2503,4032±75,2925 2316,8186±526.88805 2635,3355±0.0000 2666,0617±3,3462 2659,2044±7,2403 2659,5653±4,0575 2746,5528±260,9359 2431,7201±370.6632

Table 5.2: Moyenne ± écart-type valeurs de fitness de différentes méthodes pour différents cas de test.

78

Images detests

Seuil GIM_PSO GIM_ABC GIM_GA GIM_PSO_ABC GIM_PSO_GA GIM_ABC_GA

Airplane

2 115,173 116,174 94 , 164 115,173 115,173 125,1723 94,145,190 91 ;144,189 83,179,224 92,142,188 93,143,188 32,150,2094 72,117,161,196 85,127,168,199 32,116,169,170 53,111,153,193 21,53,149,184 32,129,167,1995 65,102,139,177,202 64,101,149,189,213 28,35,124,143,161 48,91,131,171,200 23,24,29,123,184 1,100,106,126,169

Hunter

2 50,115 28,103 38,93 49,115 50,115 38 ,1033 34,84,133 32,78,131 38,77,163 33,82,132 25,77,129 38,111,2124 20,54,95,138 4 ,28,70,162 6,75 ,83,171 26,64,103,142 28,64,103,142 47,102,134,2475 13,40,73,109,144 49,108,135,176,188 1,14,38,84,144 47,98,110,155,189 55,116,122,190,234 1,17,69,82,228

Butterfly

2 98,150 98,151 100,166 98,150 98,150 100,1523 80,118,159 90,135,184 32,85,129 80,127,180 80,127,180 74,115,1664 97,95,124,160 21,61,130,166 32,51,59,132 67,81,153,213 63,89,118,152 44,76,107,1575 53,72,96,123,159 30 ,32,98,115,255 46,83,123,139,241 18,39,116,162,229 111,127,129,146,211 9,35,76,114,230

Road

2 89,153 90,155 94,159 89,153 89,153 87,1493 85,129,184 86,129,185 14,55,118 85,129,184 85,145,211 6,56,784 71,103,134,185 60,97,137,204 26,82,100 ,171 67,101,133,187 67,101,133,187 6,100,132,1715 64,94,119,145,194 1,2,75,87,194 27,41,73,86,193 0 ,72,104,135,189 0 ,71,103,135,189 2,73,172,203,243

Map

2 115,175 110,188 118,159 118,179 107,177 121,1783 97,140,200 101,148,197 73 ,156,226 94,160,213 94,160,213 18,108,1784 89,133,165,216 42,95,135,189 51,108,133,147 82,126,164,228 85,126,166,228 43,109,153,2235 75,107,139,185,215 38,50,104,117,164 11,144,179,229,245 46,86,131,173,203 42,92,146,185,216 14,73,167 ,203,252

Table 5.3 : Moyenne de meilleurs seuils optimaux de différents algorithmes de segmentation.

79

Images detests

SeuilGIM

PSO_ABC_GAPSO DPSO FODPSO ABC GA

Airplane

2 115,173 108,170 116,175 118,175 116,176 119,1713 92,142,188 78,130,181 97,147,189 95,144,189 73,133,191 62,113,1584 68,112,156,194 56,102,145,189 86,131,169,201 78,124,168,202 45,97,147,194 47,80,121,1715 27,62,67,184,190 47,90,124,164,201 68,106,143,177,204 70,105,143,179,204 29,72,114,159,196 32,65,103,147,186

Hunter

2 49,115 49,114 51,116 51,116 55,131 63,1503 33,82,132 30,79,133 34,86,134 32,82,132 40,88,157 29,91,1804 28,50,105,150 22,56,97,138 28,70,110,147 32,72,110,147 26,77,121,186 34,78,130,2095 42,78,116,166,217 16,43,78,113,152 26,60,93,126,158 22,55,89,122,155 25,58,92,132,204 36,70,92,143,197

Butterfly

2 98,150 95,146 99,150 101,151 78,148 97,1443 79,113,157 68,112,164 83,119,160 83,118,159 65,111,164 62,114,1654 48,84,119,159 53,95,128,171 72,101,134,168 73,102,134,169 65,107,144,190 48,91,125,1835 28,81,150,184,252 49,77,103,138,172 68,96,121,150,181 71,97,119,146,173 43,75,114,155,206 33,76,112,154,204

Road

2 89,153 88,152 90,154 90,154 89,168 88,1703 85,129,184 78,122,175 87,132,187 85,131,186 70,117,182 43,127,1844 68,101,133,188 52,92,128,179 72,104,139,192 75,108,139,195 50,100,140,202 47,81,135,1805 1,6,80,83,189 40,78,107,136,187 67,99,125,157,202 62,93,123,154,200 22,63,98,140,196 25,62,100,142,189

Map

2 118,179 107,179 116,182 113,185 107,180 116,1893 95,134,199 84,134,196 97,143,196 97,143,199 66,123,187 65,132,1834 82,121,169,227 68,113,165,208 79,119,161,210 83,123,162,217 34,91,140,202 31,85,133,1915 41,94,144,184,215 54,102,135,173,218 79,113,142,178,220 73,110,146,182,223 37,82,127,163,213 25,59,88,129,198

Table 5.4 : Moyenne des seuils optimaux de différents algorithmes de segmentation.

80

2 seuils 3 seuils

4 seuils 5 seuils

Figure 5.6 Image Airplane segmenté par GIM_PSO_ABC_GA.

81

2 seuils 3seuils

4 seuils 5 seuils

Figure 5.7 Image Hunter segmenté par GIM_PSO_ABC_GA.

82

2 seuils 3seuils

4 seuils 5 seuils

Figure 5.8 Image Butterfly segmenté par GIM_PSO_ABC_GA

83

2 seuils 3seuils

4 seuils 5 seuils

Figure 5.9 Image Road segmenté par GIM_PSO_ABC_GA.

84

2 seuils 3seuils

4 seuils 5 seuils

Figure 5.10 Image Map segmenté par GIM_PSO_ABC_GA.

85

Figure 5.11 Différentes valeurs de STD pour les différents algorithmes face àdifférents cas de test (pour chaque cas de test, 2, 3, 4, 5 seuils, respectivement).

GIM avec ses différentes variantes conduit à une fitness (variance interclasse) un peuplus élevée que les fitness des algorithmes de l’optimisation essaim de particules (PSO, DPSO,FODPSO), l’algorithme d’abeilles et l’algorithme génétique. En plus GIM utilise lacoopération entre ces sous populations afin d’éviter la stagnation et améliorer la qualité desegmentation d’image.

Dans la figure 7, les images avec un niveau plus élevé de segmentation ont plus dedétails que les autres images. En revanche, l'image segmentée avec le niveau 3 est considéréecomme l’image la plus approximative dans différents cas d'essai. Il est facile de conclurequ'en augmentant le niveau de la segmentation, l'image segmentée inclut plus de détails. Enconséquence, l'image segmentée avec le niveau 6 dans différents cas d'essai est plus lisse quecelle qui est segmentée avec le niveau 3.

Il est facile de détecter qu’une valeur élevée de STD représente une plus grandeinstabilité de l'algorithme. A partir des tableaux 1 et 2, on peut dire que la méthode GIMproposée avec ces différentes variantes est stable par rapport aux autres algorithmes. Ainsi GAmontre la mauvaise stabilité après vient ABC.

0

2

4

6

8

10

12

14

16GI

M_P

SO_A

BC_G

A

PSO

DPSO

FODP

SO

GIM

_PSO

_ABC

_GA

PSO

DPSO

FODP

SO

GIM

_PSO

_ABC

_GA

PSO

DPSO

FODP

SO

GIM

_PSO

_ABC

_GA

PSO

DPSO

FODP

SO

GIM

_PSO

_ABC

_GA

PSO

DPSO

FODP

SO

Airplane Hunter Butterfly Road Map

2 seuils 3 seuils 4 seuils 5 seuils

86

5.6 Conclusion

Dans ce chapitre, une nouvelle approche de segmentation d'images a été proposée quirepose sur le modèle d’île généralisé. Les performances de la méthode ont été évaluées sur labase de statistiques dérivées des valeurs de la fonction objective utilisée (variance interclasse).Les résultats indiquent que GIM est plus efficace que les autres méthodes de base prisesséparément, donc capable de trouver les meilleurs seuils avec une plus grande stabilité.

87

Conclusion générale

La segmentation d’images est une étape cruciale dans tout processus d’analysed’images. Elle consiste à préparer l’image afin de la rendre plus exploitable par un processusautomatique telle que l’interprétation.

De manière non exhaustive, nous avons présenté dans le premier chapitre un panoramadu domaine bio-inspiré. Une taxonomie comprenant trois classes a été élaborée à savoir lesalgorithmes évolutionnaires, les algorithmes basés essaim, et les algorithmes basés écologie.

Nous avons présenté les différentes techniques de la segmentation. Il existe deuxgrandes approches purement locales. L’approche contour consiste à localiser les frontières desrégions, elle est basée sur la notion de dissimilarité. Parmi ces point fort : sa simplicité et sarapidité mais elle donne parfois des contours ouverts. L’approche région consiste à réunir lespixels connexes dans une région homogène, elle est basée sur la notion de similarité. Elle estsimple et rapide mais l’utilisation uniquement des informations locales donne parfois demauvais résultats (sous-segmentation, sur-segmentation). La coopération de ces deuxapproches qui sont par nature dual améliore les résultats de la segmentation. Nous noussommes particulièrement intéressés à l’approche région dans laquelle les méthodes basées surla classification et plus précisément de seuillage ont attiré notre attention.

La recherche de la solution optimale est une tâche très couteuse voire impossible àeffectuer par les méthodes exhaustives (Otsu exhaustive). Ceci a favorisé le développement deméthodes approchées parallèles dont le principe est de trouver, en utilisant des processusstochastiques répartie, une solution acceptable (optimal). Dans le chapitre trois nous avonsprésentés les sujets d’optimisation distribuée.

Notre approche de la segmentation d’images est basée sur le modèle d’île généralisé.Nous avons implémenté trois algorithmes d’optimisation, à savoir l’algorithme génétique,l’algorithme d’essaim de particules et l’algorithme de la colonie d’abeille.

Afin d'évaluer la performance et valider notre approche, nous avons expérimenté notresystème sur différentes images. Les résultats expérimentaux sont très encourageants etmontrent clairement la robustesse d'une telle approche. D’après les résultats obtenus pardifférentes expériences appliquées sur différents types d’images, nous avons conclu au vu desrésultats que la méthode de segmentation basée sur le modèle d’île généralisé permetd’obtenir de bons résultats.

Comme perspectives, nous envisageons d’apporter les améliorations suivantes :

Appliquer le modèle d’île généralisé sur une plus grande classe d’algorithmesd’optimisation comme par exemple ACO, DE, CS, etc.

Faire varier le nombre d’iles. Utiliser le serveur de calcul distribué de Matlab, le calcul sur GPU, Grid Computing

et Cloud computing.

88

Références

[Abdelli, 11] O. Abdelli, Segmentation d’images par seuillage d’histogrammesbidimensionnels, Mémoire Magistère en Automatique, université Mouloud Mammeri de Tizi-Ouzou, 2011.

[Ahmed, 12] H. Ahmed And J. Glasgow, Swarm Intelligence: Concepts, Models andApplications, Technical Report 585, Queen’s University, Kingston, Ontario, Canada, 2012.

[Balasubramani, 13] K. Balasubramani And K. Marcus, A Comprehensive review of ArtificialBee Colony Algorithm, International Journal of Computers & Technology Volume 5, No. 1,May -June, 2013.

[Belkhelladi, 10] K. Belkhelladi, Stratégies d’échange d’informations dans un système decalcul distribué pour l’optimisation des problèmes combinatoires, Thèse Doctorat Universitéd’Angers, 2010.

[Beyer, 02] H.G. Beyer And H.P. Schwefel, Evolution strategies, Natural Computing 1,3–52, 2002.

[Biringanine, 08] J.M Biringanine, La liaison automatique des plusieurs images perçues surun scanner, ISP (Institut Supérieur Pédagogique de Bukavu) - licencié en pédagogie; Option :Informatique de Gestion, 2008.

[Bloch, 05] I. Bloch, Y. Gousseau, H. Maitre, D. Matignon, B. Pesquet-Popescu, F. Schmitt,M. Sigelle And F. Tupin, Le traitement des images, Polycopie du cours ANIM DépartementTSI - Télécom-Paris, 2005.

[Boumaza, 08] A. Boumaza And B. Scherrer, Analyse d’un algorithme d’intelligence enessaim pour le fourragement, In La Revue d’intelligence Artificielle, 22 (6) :pp 791-816,2008.

[Cahon, 04] S. Cahon, N. Melab And E. Talbi, Paradiseo: A framework for the reusabledesign of parallel and distributed metaheuristics, Journal of Heuristics, 10(3) pp 357–380,May 2004.

[Calas, 09] G. Calas, Optimisation par essaim de particulaire, Ecole à la pointe del'informatique et des technologies de l'information EPITA, guillaume.calas.free.fr, 2009.

[Canny , 86] J. Canny, A computational approach to edge detection, IEEE Trans. On PatternAnalysis and Machine Intelligence, vol. 8, n°6, pp. 679-698, novembre 1986.

[Castleman, 96] K.R. Castleman, Digital image processing , Prentice Hall, 1996.

[Chen, 08] H. Chen And Y. Zhu, Optimization based on symbiotic multi-species coevolution,journal on Applied Mathematics and Computation 205, 2008.

89

[Cocquerez, 95] J.-P. Cocquerez And S. Philipp, Analyse d’Images : filtrage et segmentation,Masson, 1995.

[Cohoon, 87] J. P. Cohoon, S. U. Hedge, W. N. Martin And D. Richards, Punctuatedequilibria: a parallel genetic algorithm, Proceedings of the Second International Conferenceon Genetic Algorithms, pages 148–154, Lawrence Erlbaum Associates, Mahwah, NJ, 1987.

[Cuevas, 10] E. Cuevas, D. Zaldivar And M. Pérez-Cisneros, A novel multi-thresholdsegmentation approach based on differential evolution optimization, Expert Systems withApplications 37, pp. 5265–5271. 2010.

[Cuevas, 12] E. Cuevas, F. Sención, D. Zaldivar, M. Pérez-Cisneros And H. Sossa, A multi-threshold segmentation approach based on Artificial Bee Colony optimization, ApplIntell 37:pp 321–336. 2012.

[Cung, 02] V.-D. Cung, S. L. Martins, C. C. Ribeiro And C. Roucairol, Strategies for theparallel implementation of metaheuristics, Essays and Surveys in Metaheuristics, pp 263–308. Kluwer Academic Publishers, 2002.

[Deriche, 87] R. Deriche, Using Canny's criteria to derive a recursively implemented optimaledge detector, International Journal of Computer Vision, pp. 167-187, 1987.

[Dorigo, 04] M. Dorigo And T. Stützle, Ant Colony Optimization, Cambridge: MIT Press,2004.

[Dorigo, 07] M. Dorigo, Ant Colony Optimization, Scholarpedia, 2(3):1461.http://www.scholarpedia.org/article/Ant_colon y_optimization, 2007.

[Duncan, 93] B. S. Duncan, Parallel evolutionary programming, Proceedings of the SecondAnnual Conference on Evolutionary Programming, pp 202–208. Evolutionary ProgrammingSociety, San Diego, CA, 1993.

[Eberhart, 95] R. C. EberhartAnd J. Kennedy, A new optimizer using particle swarm theory.In Proceedings of the Sixth International Symposium on Micro Machine and Human Science,Nagoya, Japan, pp. 39 43, 1995.

[Fink, 98]A. Fink, S. Vo And D. Woodruff, Building reusable software components forheuristic search, Operations Research Proceedings, pp 210-219, 1998.

[Fuh, 00] C. Fuh, S. Cho And K. Essig, Hierarchical Color Image Region Segmentation forContent-Based Image Retreival Systems, IEEE Transactions on Image Processing, vol. 9, no.1, pp. 156-162, 2000.

[Gao, 10] H. Gao, W. Xu, J. Sun And Y. Tang, Multilevel Thresholding for ImageSegmentation Through an Improved Quantum-Behaved Particle Swarm Algorithm, IEEETRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 59, NO. 4,2010.

90

[Ghamisi, 12] P. Ghamisi, M.S. Couceiro, J.A. Benediktsson And N.M.F. Ferreira, Anefficient method for segmentation of images based on fractional calculus and naturalselection. Expert Systems with Applications 39, pp 12407–12417, 2012.

[Gonzalez, 92] R.C. Gonzalez And R.E, Woods, Digital image processing, Addison-Wesley,Reading, MA, 1992.

[Gras, 03] R. Gras, D. Hernandez, P. Hernandez, N. Zangge, Y. Mescam, J. Frey, O. Martin,J. Nicolas And R.D. Appel, Cooperative metaheuristics for exploring proteomic data.Artificial Intelligence, Rev., 20(1-2): pp 95–120, 2003.

[Grefenstette, 81] J. J Grefenstette, Parallel adaptive algorithms for function optimization,Technical Report CS-81-19, Vanderbilt University, Computer Science Department, Nashville,1981.

[Grosso, 85] P.B. Grosso, Computer Simulation of Genetic Adaptation: ParallelSubcomponent Interaction in a Multilocus Model, PhD thesis, University of Michigan,University Microfilms No. 8520908, 1985.

[Guo, 07] C. Guo And H. Li, Multilevel Thresholding Method for Image SegmentationBased on an Adaptive Particle Swarm Optimization Algorithm, AI 2007, LNAI 4830, pp.654–658, 2007, Springer-Verlag Berlin Heidelberg 2007.

[Hammouche, 2008] K.Hammouche, M. Diaf And P. Siarry, A multilevel automaticthresholding method based on a genetic algorithm for a fast image segmentation, ComputerVision and Image Understanding 109, pp 163–175, 2008.

[Hammouche, 2010] K.Hammouche, M. Diaf And P. Siarry, A comparative study of variousmeta-heuristic techniques applied to the multilevel thresholdingproblem .journal home page,2009.

[Holland, 75] J.Holland, Adaptation In Natural And Artificial Systems, University ofMichigan Press, 1975.

[Horowitz, 76] S.L. Horowitz, And T. Pavlidis, Picture segmentation by a tree traversalalgorithm, Journal of the association for computing matchinery, 23(2): 368-388, 1976.

[Izzo, 09] D. Izzo, M. Rucinski And C. Ampatzis, Parallel global optimisationmetaheuristicsusing an asynchronous island model, IEEE Congress on Evolutionary Computation, CEC2009, pp. 2301–2308. IEEE 2009.

[Izzo, 12] D. Izzo, M. Rucinski And F. Biscani, The Generalized Island Model, ParallelArchitectures & Bioinspired Algorithms, SCI 415, pp. 151–169. Springer-Verlag BerlinHeidelberg 2012.

[Jain, 00] A. Jain, R. Duin And J. Mao, Statistical Pattern Recognition : A review, IEEETransactions on Pattern Analysis and Machine Intelligence, Vol. 22, No.1, pp 4-37 , 2000.

91

[Jain, 99] A.K. Jain, M.N. Murty And P.J. Flynn, Data clustering : a review, ACMComputing Surveys, 31(3) : pp 264-322, 1999.

[Kachouri, 10] R. Kachouri, Classification multi-modèles des images dans les baseshétérogènes. Thèse doctorat, Université d’Evry-val d’essonne, 2010.

[Karaboga, 05] D. Karaboga, An idea based on honey bee swarm for numerical optimization,Technical Report TR06, Erciyes University, Engineering Faculty, Computer EngineeringDepartment, 2005.

[Kass, 87] M. Kass, A. Witkin And D. Terzopoulos, Snakes : active contour models,International Journal of Computer Vision, 1(4): pp321–331, 1987.

[Kennedy, 95] J. Kennedy And R. C. Eberhart, Particle Swarm Optimization. In Proceedingsof IEEE International Conference on Neural Networks, Perth, Australia, pp. 1942– 1948,1995.

[Koza, 90] J. R. Koza, Genetic Programming: a paradigm for genetically breedingpopulations of computer programs to solve problems, Computer Science Department StanfordUniversity, 1990.

[Koza, 92] J.R. Koza, Genetic Programming: On the Programming of Computers by Meansof Natural Selection, MIT Press, 1992.

[Lei, 99] B. J. Lei, E.A. Hendriks And M.J.T. Reinders, On Feature Extraction from Images,MCCWS project ,Technical report on inventory properties for MCCWS, June 1999.

[Lerman, 95] I. Lerman And F. Ngouenet, Algorithmes génétiques séquentiels et parallèlespour une représentation affine des proximités, Rapport de Recherche de l’INRIA Rennes -Projet REPCO 2570, INRIA 1995.

[MacArthur, 67] R. H. MacArthur And E. O. Wilson, The Theory of Island Biogeography,Princeton University Press, Princeton, 1967.

[Maitre, 11] O. Maitre, GPGPU forEvolutionaryAlgorithms,Thèse Doctorat Université deStrasbourg, 2011.

[Mehrabian, 06] A.R. Mehrabian And C. Lucas, A novel numerical optimization algorithminspired from weed colonization, Ecological Informatics 1, pp 355–366, 2006.

[Melliani, 12] M. Melliani, Segmentation d’image par coopération régions-contours,Magistère en informatique, Ecole national Supérieur d’Informatique, 2012.

[Merzougui, 12] N. Merzougui, Un algorithme évolutionnaire pour la segmentationd'images basé sur le diagramme de Voronoï, Mémoire MAGISTER, UNIVERSITE KASDIMERBAH-OUARGLA, 2012.

92

[Meshoul, 04] S. Meshoul, Optimisation par les systèmes complexes pour le recalage et lamise en correspondance en analyse d’images, Thèse doctorat en informatique, universitéConstantine, 2004.

[Mitchell, 96] M. Mitchell, An introduction to genetic algorithms, The MIT Press , 1996.

[Monga, 87] O. Monga And B. Wrobel, Segmentation d’image: vers une méthodologie,Traitement du Signal,volume 4 - n° 3 –, 1987.

[Nixon, 02] M. S. Nixon And A.S. Aguado, Feature Extraction and Image Processing,Newnes, 2002.

[Ouadfel, 06] S. Ouadfel, Contributions à la Segmentation d’images basées sur la résolutioncollective par colonies de fourmis artificielles, thèse doctorat en informatique, UniversitéHadj Lakhdar de Batna, 2006.

[Pratt, 07] W. K. Pratt, Digital Image Processing, PIKS Scientific Inside, Wiley 4th ed, 2007.

[Rucinski, 10] M. Rucinski, D. IzzoAnd F. Biscani, On the impact of the migration topologyon the Island Model, Parallel Computing 36(10-11), pp 555–571, 2010.

[Rudolph, 91] G. Rudolph, Global optimization by means of distributed evolution strategies,Parallel Problem Solving from Nature, volume 496 of Lecture Notes in Computer Science, pp209–213. Springer, Berlin, Heidelberg, New York, 1991.

[Sebari, 07] I. Sebari And D-C. He, Les approches de segmentation d’image par coopérationrégions-contours, Centre d’applications et de recherches en télédétection (CARTEL),Département de géomatique appliquée, Université de Sherbrooke, Canada J1K 2R1RevueTélédétection, vol. 7, n° 1-2-3-4, pp 499-506, 2007.

[Simon, 08] D. Simon, Biogeography-based optimization, IEEE Transactions onEvolutionary Computation, 12 (6), pp 702–713, 2008.

[Storn, 97] R. Storn And K. Price, Differential evolution – a simple and efficient heuristic forglobal optimization over continuous spaces, Journal of Global Optimization 11,pp 341–359,1997.

[Tanese, 87] R. Tanese, Parallel genetic algorithms for a hypercube, Proceedings of theSecond International Conference on Genetic Algorithms, pp 177–183. Lawrence ErlbaumAssociates, Hillsdale, NJ, 1987.

[Tomassini, 05] M. Tomassini, Spatially Structured Evolutionary Algorithms: ArtificialEvolution in Space and Time, (Natural Computing Series), 2005.

[Truong, 13] Q.B. Truong And B.R. Lee, Automatic Multi-thresholds Selection for ImageSegmentation based on Evolutionary Approach. International Journal of Control, Automation,and Systems, pp834-844, Springer 2013.

[wikipedia2] http://fr.wikipedia.org/wiki/Image_vectorielle

93

[Wikipedia1] http://fr.wikipedia.org/wiki/Stratégie_d'évolution

[Yang, 03] Z. Yang, Z. Pu And Z. Qi, Relative entropy multilevel thresholding method basedon genetic optimization, IEEE Int. Conf. Neural Networks & Signal Processing Nanjing,China, 2003.

[Yang, 09] X.-S. Yang And S. Deb, Cuckoo search via L´evyflights, in: Proc. Of WorldCongress on Nature & Biologically Inspired Computing (NaBIC 2009), IEEE Publications,USA, pp. 210-214, 2009.

[Yang, 10] X. S. Yang and S. Deb, Engineering Optimisation by Cuckoo Search, Int. J.Mathematical Modelling and Numerical Optimisation, Vol. 1, No. 4, pp. 330–343, 2010.

[Yu, 11] W. Yu, M. Huang, D. Zhu And X.Li, A Method of Image Segmentation Based onImproved Adaptive Genetic Algorithm, Foundations of Intelligent Systems, AISC 122, pp.507–516. Springer-Verlag Berlin Heidelberg 2011.

[Zhang, 02] Y. Zhang, Image engineering and related publications, International Journal ofImage and Graphics, 2(3), pp. 441-452, 2002.

[zhihui, 13] H. zhihui, Y. weiyu, L. shanxiang And F. jiuchao, Multi-level threshold ImageSegmentation using Artificial Bee Colony Algorithm, Fifth Conference on MeasuringTechnology and Mechatronics Automation IEEE, 2013.

[Zitová,03] B.Zitová And J.Flusser, Image registration methods: a survey, Image and VisionComputing 21, pp 977–1000, 2003.

94

ANNEXES

La variante GIM_PSO_ABC_GA du modèle proposé étant stochastique, nous avons effectué 20 exécutions sur l’ensemble des 5 images.

Taille de la population

Nombre de

solution migrant

Nombre d’itération

Taux de migration

Fitness Airplane.gif

2 seuils 3 seuils 4 seuils 5 seuils Fitness STD Fitness Fitness Fitness STD Fitness STD

5 2

5 2 1835,49975 0 1832,15704 9,3312E-13 2233,71262 9,3312E-13 2901,79197 9,3312E-13 10 3 1837,79741 2,3328E-13 2019,73289 0 2479,65043 4,6656E-13 2592,22941 0

50 10 1837,79741 2,3328E-13 1910,40446 1,1664E-12 2655,62357 4,6656E-13 2786,27691 9,3312E-13

100 20 1837,79741 2,3328E-13 1911,56435 2,3328E-13 1947,73986 6,9984E-13 2748,15246 9,3312E-13

200 40 1837,79741 2,3328E-13 1911,71616 0 1951,39312 0 4045,98132 9,3312E-13

10 4

5 2 1837,17714 4,6656E-13 2809,54853 9,3312E-13 2829,67176 9,3312E-13 3141,33558 9,3312E-13 10 3 1837,74352 0 2637,4961 4,6656E-13 2393,59015 9,3312E-13 3330,00891 9,3312E-13

50 10 1837,79741 2,3328E-13 2345,2781 0 2446,68407 4,6656E-13 3481,99896 9,3312E-13

100 20 1837,79741 2,3328E-13 2324,05625 0 2964,07561 4,6656E-13 3832,8372 4,6656E-13

200 40 1837,79741 2,3328E-13 2950,89996 1,3997E-12 2905,68386 1,3997E-12 3300,5659 0

20 8

5 2 1837,75172 6,9984E-13 2896,27351 1,3997E-12 2908,22745 9,3312E-13 3359,74289 4,6656E-13 10 3 1837,79741 2,3328E-13 2860,79557 9,3312E-13 2960,65693 9,3312E-13 2994,58633 9,3312E-13

50 10 1837,79741 2,3328E-13 2012,5521 6,9984E-13 2968,0391 1,3997E-12 3484,53113 0

100 20 1837,79741 2,3328E-13 2321,18576 9,3312E-13 3147,04245 9,3312E-13 3863,17091 1,3997E-12

200 40 1837,79741 2,3328E-13 2427,96276 9,3312E-13 2997,95575 9,3312E-13 3789,12724 4,6656E-13

50 15

5 2 1837,64753 2,3328E-13 2879,38769 9,33122E-

13

3297,4206 0 3394,80166 1,86624E-12 10 3 1837,79741 2,3328E-13 2933,47434 9,33122E-

13

3082,88136 1,3997E-12 3591,86104 9,33122E-13

50 10 1837,79741 2,3328E-13 2956,10253 0 3085,81745 9,3312E-13 3544,30331 4,66561E-13

100 20 1837,79741 2,3328E-13 2952,39068 9,33122E-

13

3077,32735 4,6656E-13 4045,35866 4,66561E-13

200 40 1837,79741 2,3328E-13 2980,84557 0 3258,5041 9,3312E-13 4102,67919 0

100 30

5 2 1837,75172 6,99841E-

13

2842,68159 4,66561E-

13

3005,01075 0 3463,25114 4,66561E-13 10 3 1837,79741 2,3328E-13 2945,01602 0 3076,74095 9,3312E-13 3770,11932 4,66561E-13

50 10 1837,79741 2,3328E-13 2822,75346 0 3192,34387 0 3938,01134 9,33122E-13

100 20 1837,79741 2,3328E-13 2991,33755 9,33122E-

13

3127,45045 4,6656E-13 4079,67425 9,33122E-13

200 40 1837,79741 2,3328E-13 2952,90501 1,39968E-

12

3370,25757 9,3312E-13 3897,44204 2,3328E-12

95


Nombre de

solution migrant


Taux de migration

Fitness Hunter.gif


5 2

5 2 3021,7183 0 3198,27736 4,6656E-13 4155,65552 9,3312E-13 3213,56771 0 10 3 3063,85869 9,3312E-13 3198,24151 9,3312E-13 4292,38384 0 4418,22444 0

50 10 3061,44793 9,3312E-13 3207,74809 0 4291,40214 0 4442,59448 9,3312E-13

100 20 3064,04212 9,3312E-13 3212,96361 1,3997E-12 4031,5225 2,3328E-12 5702,75982 9,3312E-13

200 40 3064,2112 1,3997E-12 3397,96902 4,6656E-13 3747,1849 4,6656E-13 4763,04049 0

10 4

5 2 3061,79797 9,3312E-13 4046,21221 4,6656E-13 3995,80261 9,3312E-13 4739,39869 9,3312E-13 10 3 3058,98765 9,3312E-13 4099,52672 0 4241,79576 1,8662E-12 4497,02363 9,3312E-13

50 10 3064,2112 1,3997E-12 3671,4217 4,6656E-13 4322,83641 9,3312E-13 4634,81513 9,3312E-13

100 20 3064,2112 1,3997E-12 3610,11327 0 4438,64595 9,3312E-13 5429,11365 2,7994E-12

200 40 3064,2112 1,3997E-12 3476,56045 1,3997E-12 4258,30474 0 4886,66957 9,3312E-13

20 8

5 2 3064,06886 9,3312E-13 4183,65329 0 4542,38244 9,3312E-13 4895,41364 9,3312E-13 10 3 3064,2112 1,3997E-12 3566,18851 0 4356,65041 0 4776,35268 1,8662E-12

50 10 3064,2112 1,3997E-12 3282,33165 0 4454,72994 9,3312E-13 5317,24586 0

100 20 3064,2112 1,3997E-12 3708,51521 4,6656E-13 4482,36676 9,3312E-13 5146,37005 1,8662E-12

200 40 3064,2112 1,3997E-12 3507,4217 9,3312E-13 4496,17564 1,8662E-12 4881,08845 1,8662E-12

50 15

5 2 3064,06886 9,3312E-13 4112,32335 9,3312E-13 4537,77893 0 4894,72784 1,8662E-12 10 3 3064,2112 1,3997E-12 4063,62472 1,8662E-12 4474,90525 0 4915,77342 1,8662E-12

50 10 3064,2112 1,3997E-12 3753,86345 9,3312E-13 4563,94653 1,8662E-12 5678,68313 0

100 20 3064,2112 1,3997E-12 4068,09665 4,6656E-13 4603,73465 1,8662E-12 5447,18351 1,8662E-12

200 40 3064,2112 1,3997E-12 3726,51655 4,6656E-13 4606,1871 9,3312E-13 5562,55952 1,8662E-12

100 30

5 2 3064,2112 1,3997E-12 4215,71576 1,8662E-12 4554,14198 9,3312E-13 5136,21152 9,3312E-13 10 3 3064,2112 1,3997E-12 4200,1339 1,8662E-12 4814,77562 1,8662E-12 5326,27161 9,3312E-13

50 10 3064,2112 1,3997E-12 3330,52472 0 5013,13214 9,3312E-13 5411,5496 9,3312E-13

100 20 3064,2112 1,3997E-12 3734,75657 0 4822,03332 0 5725,70326 1,8662E-12

200 40 3064,2112 1,3997E-12 3744,02272 1,8662E-12 4559,0449 0 5396,01602 0

96


Nombre de

solution migrant


Taux de migration

Fitness Batterfly.gif


5 2

5 2 1552,73631 4,6656E-13 1566,27484 4,6656E-13 1812,06751 6,9984E-13 2038,86342 2,3328E-13 10 3 1552,59201 4,6656E-13 1600,47158 4,6656E-13 1793,6513 0 1804,5887 0

50 10 1553,0734 4,6656E-13 1664,30833 4,6656E-13 1876,0018 6,9984E-13 1829,39554 2,3328E-13

100 20 1553,0734 4,6656E-13 1667,77369 0 1689,49655 6,9984E-13 1737,50378 0

200 40 1553,0734 4,6656E-13 1669,27833 9,3312E-13 1988,77347 1,1664E-12 2171,35002 4,6656E-13

10 4

5 2 1552,34345 4,6656E-13 1783,13201 9,3312E-13 1784,69168 6,9984E-13 2204,13019 4,6656E-13 10 3 1553,0734 4,6656E-13 1558,73572 0 2017,23221 2,3328E-13 2341,35991 9,3312E-13

50 10 1553,0734 4,6656E-13 1831,66528 2,3328E-13 2201,76245 4,6656E-13 1764,01705 0

100 20 1553,0734 4,6656E-13 1669,27833 9,3312E-13 2268,16207 0 1864,55512 6,9984E-13

200 40 1553,0734 4,6656E-13 1669,27833 9,3312E-13 2173,9877 9,3312E-13 1928,20055 4,6656E-13

20 8

5 2 1550,86122 4,6656E-13 2062,63568 4,6656E-13 2158,47124 0 2597,8124 9,3312E-13 10 3 1553,06872 4,6656E-13 1792,80486 4,6656E-13 2236,01327 0 2321,96237 0

50 10 1553,0734 4,6656E-13 1890,35478 2,3328E-13 2337,19952 0 2357,99035 4,6656E-13

100 20 1553,0734 4,6656E-13 1669,27833 9,3312E-13 2232,87526 4,6656E-13 2416,75251 4,6656E-13

200 40 1553,0734 4,6656E-13 1669,27833 9,3312E-13 2361,8653 4,6656E-13 2579,99309 9,3312E-13

50 15

5 2 1552,74534 4,6656E-13 2106,11793 4,6656E-13 2361,18847 4,6656E-13 2537,80485 4,6656E-13 10 3 1553,0734 4,6656E-13 1927,7906 2,3328E-13 2246,59151 4,6656E-13 2464,2778 4,6656E-13

50 10 1553,0734 4,6656E-13 1669,27833 9,3312E-13 2272,38934 9,3312E-13 2645,85476 9,3312E-13

100 20 1553,0734 4,6656E-13 1919,09477 9,3312E-13 2351,58784 0 2695,0947 4,6656E-13

200 40 1553,0734 4,6656E-13 1880,36274 4,6656E-13 2306,6817 9,3312E-13 2549,57717 4,6656E-13

100 30

5 2 1553,0734 4,6656E-13 1969,77559 2,3328E-13 2218,10189 4,6656E-13 2632,15299 9,3312E-13 10 3 1553,0734 4,6656E-13 2080,11776 4,6656E-13 2331,78412 9,3312E-13 2635,03087 1,3997E-12

50 10 1553,0734 4,6656E-13 1714,45978 9,3312E-13 2343,25148 4,6656E-13 2715,09559 0

100 20 1553,0734 4,6656E-13 1669,27833 9,3312E-13 2340,16681 0 2852,39624 9,3312E-13

200 40 1553,0734 4,6656E-13 1882,24118 0 2339,04421 4,6656E-13 2744,69067 9,3312E-13

97


Nombre de

solution migrant


Taux de migration

Fitness Map.gif


5 2

5 2 2340,39503 4,6656E-13 2454,42116 4,6656E-13 2543,73198 4,6656E-13 2667,42767 9,3312E-13 10 3 2340,39503 4,6656E-13 2512,98821 9,3312E-13 2607,07426 9,3312E-13 3032,23047 9,3312E-13

50 10 2340,39503 4,6656E-13 2523,86732 9,3312E-13 2665,81814 9,3312E-13 2612,56298 4,6656E-13

100 20 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2621,14763 0 2635,33556 9,3312E-13

200 40 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2621,14763 0 2987,23539 1,3997E-12

10 4

5 2 2324,30505 0 2530,80288 4,6656E-13 2656,83423 0 3190,8815 4,6656E-13 10 3 2316,14073 0 2525,81486 9,3312E-13 2837,0688 4,6656E-13 3093,37157 9,3312E-13

50 10 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2767,37887 0 3483,08061 9,3312E-13

100 20 2340,39503 4,6656E-13 2537,8858 4,6656E-13 2817,17566 9,3312E-13 2825,95708 9,3312E-13

200 40 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2817,17566 9,3312E-13 3217,05223 9,3312E-13

20 8

5 2 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2603,19488 4,6656E-13 3037,78602 0 10 3 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2847,8551 9,3312E-13 3152,63672 9,3312E-13

50 10 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2826,27292 4,6656E-13 3057,96079 4,6656E-13

100 20 2340,39503 4,6656E-13 2769,04559 9,3312E-13 2872,33223 1,3997E-12 3542,28155 0

200 40 2340,39503 4,6656E-13 2693,20062 9,3312E-13 2784,84776 9,3312E-13 3224,89231 4,6656E-13

50 15

5 2 2340,39503 4,6656E-13 2529,93843 9,3312E-13 2850,75516 4,6656E-13 3535,75783 0 10 3 2340,39503 4,6656E-13 2529,93843 9,3312E-13 3327,4626 0 3429,72204 1,3997E-12

50 10 2340,39503 4,6656E-13 2760,89648 4,6656E-13 2621,14763 0 3433,51987 1,3997E-12

100 20 2340,39503 4,6656E-13 2682,94142 9,3312E-13 2821,09995 0 3411,09457 9,3312E-13

200 40 2340,39503 4,6656E-13 2597,29755 9,3312E-13 2777,35482 4,6656E-13 3592,88111 4,6656E-13

100 30

5 2 2340,39503 4,6656E-13 2760,89648 4,6656E-13 3100,54545 4,6656E-13 3537,79112 9,3312E-13 10 3 2340,39503 4,6656E-13 2692,67207 0 3192,61259 4,6656E-13 3737,47972 2,3328E-12

50 10 2340,39503 4,6656E-13 2742,77405 4,6656E-13 3241,5681 9,3312E-13 3551,82339 9,3312E-13

100 20 2340,39503 4,6656E-13 2602,59685 0 3299,30633 9,3312E-13 3635,08642 1,3997E-12

200 40 2340,39503 4,6656E-13 2529,93843 9,3312E-13 3054,60215 9,3312E-13 3637,5812 0

98


Nombre de

solution migrant


Taux de migration

Fitness Road.gif


5 2

5 2 1320,56306 4,6656E-13 1350,2908 0 1454,17802 4,6656E-13 1925,05429 4,6656E-13 10 3 1321,37393 6,9984E-13 1495,83971 4,6656E-13 1423,7662 4,6656E-13 1943,92727 0

50 10 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1561,549 0 1780,36948 2,3328E-13

100 20 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1496,50142 4,6656E-13 1718,00139 0

200 40 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1490,27623 6,9984E-13 1587,02524 4,6656E-13

10 4

5 2 1321,37393 6,9984E-13 1428,10978 4,6656E-13 1473,56532 2,3328E-13 1768,17739 0 10 3 1321,20922 2,3328E-13 1429,81311 2,3328E-13 1473,89365 4,6656E-13 2015,80881 0

50 10 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1615,56701 4,6656E-13 1874,11592 1,1664E-12

100 20 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1592,09127 2,3328E-13 2041,70858 2,3328E-13

200 40 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1520,11422 4,6656E-13 1705,75834 6,9984E-13

20 8

5 2 1321,33663 2,3328E-13 1422,80695 4,6656E-13 1480,19539 2,3328E-13 1926,91716 6,9984E-13 10 3 1321,37393 6,9984E-13 1598,7661 6,9984E-13 1774,94039 9,3312E-13 2056,13851 0

50 10 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1876,72587 2,3328E-13 1953,86256 2,3328E-13

100 20 1321,37393 6,9984E-13 1452,93786 0 1815,40791 6,9984E-13 1775,19629 6,9984E-13

200 40 1321,37393 6,9984E-13 1570,44278 4,6656E-13 1544,86422 6,9984E-13 2008,81442 0

50 15

5 2 1321,37393 6,9984E-13 1609,04333 0 1660,88889 6,9984E-13 1919,53014 1,1664E-12 10 3 1321,37393 6,9984E-13 1530,70378 6,9984E-13 1658,00054 6,9984E-13 2028,25152 4,6656E-13

50 10 1321,37393 6,9984E-13 1433,98441 6,9984E-13 1533,27862 4,6656E-13 2070,08535 0

100 20 1321,37393 6,9984E-13 1567,46597 4,6656E-13 1909,38861 1,1664E-12 2054,10494 0

200 40 1321,37393 6,9984E-13 1483,66472 2,3328E-13 1779,6394 0 2018,25575 0

100 30

5 2 1321,3012 2,3328E-13 1590,9721 4,6656E-13 1907,13607 2,3328E-13 2166,78216 0 10 3 1321,37393 6,9984E-13 1590,25661 0 1907,88066 1,1664E-12 2097,25563 0

50 10 1321,37393 6,9984E-13 1607,91259 4,6656E-13 1895,87286 1,1664E-12 2177,07983 4,6656E-13

100 20 1321,37393 6,9984E-13 1469,23919 4,6656E-13 1836,5303 0 2051,48912 9,3312E-13

200 40 1321,37393 6,9984E-13 1487,14499 4,6656E-13 1909,49808 0 2103,91407 0

Documents

Application à la segmentation d'images