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
| 
