WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Reconstruction des images hv-convexes par la recherche taboue

( Télécharger le fichier original )
par Abdesselem DAKHLI
ISG-GABES - Master informatique 2010
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

Chapitre 3. Reconstruction des Images Binaires par recherche Taboue

3.1.2 Liste tabou

Un élément fondamental de la recherche tabou est l'utilisation d'une mémoire flexible, à court terme, qui garde une certaine trace des dernières opérations passées. On peut y stocker des informations pertinentes à certaines étapes de la recherche pour en profiter ultérieurement. Cette liste permet d'empêcher les blocages dans les minima locaux en interdisant de passer à nouveau sur des configurations de l'espace de recherche précédemment visitées.

Pour implémenter la liste tabou, on a choisit d'utiliser une structure liste dont chaque élément correspond à l'échange des contenus de quatre cellules de chaque bascule. A chaque itération, on ajoute un échange à la liste tabou.

Quand aucun échange n'est possible ou après un certain nombre d'itération, on vide la liste tabou.

3.1.3 Condition d'arrêt

On doit fixer le nombre maximal d'itération.

3.1.4 Fonction d'évaluation

On définit la fonction d'évaluation comme étant le nombre de '1' adjacents apparents pour chaque solution (matrice trouvé) dans chaque itération. On essaie de maximiser cette fonction afin d'obtenir un nombre de '1'adjacents maximale

Soient Lij et Cij sont respectivement le nombre de '1'adjacents en ligne et le nombre de '1'adjacents en colonne.

F = Max (

Xn i=1

m-1X j=1

Lij +Cij) ,l'objectif c'est de maximiser F c'est à

vj

hi =

Xm i=1

Xn j=1

Abdessalem DAKHLI 20

dire le nombre de '1'adjacents dans la solution en respectant les contraintes projections orthogonales :

Xm
i=1

hi est la projection horizontale de la ligne i, i = 1, : : : , m. Elle donne

le nombre des '1'de chaque ligne.

Xn vj est la projection horizontale de la ligne i, i = 1, : : : , m. Elle donne

j=1

le nombre des '1'de chaque colonne et vjdésigne le nombre de projections

horizontales supérieure ou égales à j.

Abdessalem DAKHLI 21

Chapitre 3. Reconstruction des Images Binaires par recherche Taboue

3.2 L'application de la recherche taboue pour reconstruire des images hv-convexe

Pour réduire la taille de l'espace de recherche de solutions, deux approches sont envisageables. La première consiste à augmenter le nombre des projections à satisfaire. Son inconvénient est que le problème de reconstruction est NP-complet pour un nombre de projections supérieur à deux. La deuxième approche consiste à prendre en compte certaines propriétés connues à priori sur l'objet à reconstruire (convexité, symétrie, périodicité). Cette approche nous semble plus pratique que la première parce qu'on dispose souvent des informations sur la solution. De plus, une solution donnée par la première approche ne respecterait pas forcement ces propriétés malgré le nombre élevé des projections.

La reconstruction d'une matrice hv-convexe à l'aide d'une métaheuris-tique se fait en trois étapes :

- Etape 1 : Reconstruire une solution en utilisant une approche du gloutonne.

- Etape 2 : Reconstruire une solution optimale en utilisant l'approche de la recherche Tabou sans amélioration

- Etape 3 : Reconstruire une solution optimale en utilisant l'approche de la recherche Tabou avec amélioration en utilisant le principe de diversification et l'intensification.

Dans cette étape on doit favoriser une exploration efficace de l'espace des solutions S par des règles d'aspiration, de diversification et d'intensification de la recherche.

L'Aspiration c'est chercher à passer outre le caractère tabou d'un mouvement dans certains cas plusieurs solutions pour déclencher le mécanisme d'aspiration, une solution est proposée par Glover et Laguna [32], cette proposition indique que si t est tabou mais que (t(X)) < f(X*) alors on autorise t appliqué à X. Une autre solution indique que si le mouvement t a été rendu tabou lors du passage de la configuration X à Y = t--1(X), on lève le statut tabou d'un mouvement s'il conduit à une solution meilleure que celle qui avait entraînée son interdiction. Comme dans un autre cas on lève le statut de tabou du plus «ancien».

Donc l'idée de base de la recherche Tabou est la modélisation de la mémoire.

Dans une première phase, la méthode de recherche tabou peut être vue comme une généralisation des méthodes d'amélioration locales. En effet, l'algorithme Glouton génère une solution initiale S sous forme d'une matrice,

Abdessalem DAKHLI 22

Chapitre 3. Reconstruction des Images Binaires par recherche Taboue

CONFIGURATION INITIALE S

(Élaboration de la solution initiale sous forme d'une matrice binaire en utilisant
l'approche Glouton)

LISTE TABOU INITIALE VIDE

NOUVELLE CONFIGURATION
COURANTE S = t

INSERTION DU

MOUVEMENT

t3?S DANS LA LISTE TABOU circulaire

PERTURBATION DE S SUIVANT
N MOUVEMENTS non tabous;
EVALUATION DES N VOISINS

SELECTION DU
MEILLEUR VOISIN t

OUI Amélioration

observée récemment?

FIG. 3.1 -Modélisation de la mémoire dans la recherche Tabou

NON

STOP

en partant de cette solution qui appartient à l'ensemble de solutions X, on se déplace vers une solution s(x) située dans le voisinage [S(x)] de S0. Donc l'algorithme explore itérativement l'espace de solutions X.

Afin de choisir le meilleur voisin s(x) dans S(x), l'algorithme évalue la fonction objectif f qui désigne le nombre de '1' adjacent dans la matrice trouvée en chaque bascule s(x), et retient le voisin qui améliore la valeur de la fonction objectif f, ou au pire celui qui la dégrade le moins.

L'originalité de la méthode de recherche tabou, par rapport aux méthodes locales, qui s'arrêtent dès qu'il n'y a plus de voisin s(x) permettant d'améliorer la valeur de la fonction objectif f, réside dans le fait que l'on retient le meilleur voisin, même si celui-ci est plus mauvais que la solution d'où l'on vient. Ce critère autorisant les dégradations de la fonction objectif évite à l'algorithme d'être piégé dans un minimum local. Mais il induit un risque de cyclage. En effet, lorsque l'algorithme a quitté un minimum quelconque par acceptation de la dégradation de la fonction objectif, il peut revenir sur ses pas, à l'itération suivante.

Pour régler ce problème, l'algorithme a besoin d'une mémoire pour conser-

Abdessalem DAKHLI 23

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Les esprits médiocres condamnent d'ordinaire tout ce qui passe leur portée"   François de la Rochefoucauld