Chapitre 2. Etat de l'art sur la reconstruction des
images hv-convexes
forcément l'optimum attendu, c'est à dire que
les reconstructions obtenues par cet algorithme ne sont pas totalement
parfaites. Les méthodes de sélection proportionnelle peuvent en
particulier favoriser ce genre de dérive. Un autre problème
surgit lorsque les différents individus se mettent à avoir des
performances similaires : les bons éléments ne sont alors plus
sélectionnés, et l'algorithme ne progresse plus.
Le choix d'une représentation « intelligente
» pour permettre un remplacement générationnel efficace est
un autre aspect de la question, et l'efficacité d'un algorithme
génétique dépend beaucoup de la façon dont on
opère le croisement des individus.
18
Chapitre3
Reconstruction des Images Binaires
par recherche Taboue
Dans ce chapitre nous allons essayer de présenter notre
paramétrage et le principe de l'algorithme Tabou de même nous
allons présenter les résultats de reconstruction des images
hv-convexes en appliquant cet algorithme.
3.1 Paramétrage de l'algorithme Tabou
La recherche taboue est une méthode de recherche locale
avancée qui fait appel à un ensemble de règles et de
mécanismes généraux pour guider la recherche de
manière intelligente.
a - Paramétrage
Pour cette approche on doit fixer le voisinage, la taille des
listes tabous, le Critère d'arrêt et la sélection du voisin
: Best Fit (le meilleur voisin), First Fit (le premier qui satisfait un certain
critère).
b - Améliorations
On peut utiliser une liste de candidats plutôt que
l'ensemble du voisinage et éventuellement un tirage aléatoire du
successeur en fonction de la valeur de la fonction objective.
Pour améliorer la solution on doit fixer des
Stratégies d'intensification et de diversification, revenir sur une zone
intéressante, dégager des propriétés communes de
bonnes solutions, favoriser l'exploration de régions peu ou pas
explorées et on doit indiquer l'aspiration; il arrive qu'un mouvement
mis à l'état tabou soit intéressant(Conduise à une
solution de nombre '1'adja-cents maximale) alors on accepte de
lever l'état tabou, on utilise un critère d'aspiration pour lever
cet état tabou.
Nous définissons maintenant les composantes de notre
recherche taboue.
On part d'une solution initiale (sous forme de matrice
binaire) construite à l'aide de l'algorithme glouton, qui
vérifie les contraintes de projections orthogonales (horizontale et
verticale);
Ensuite, on essaie d'améliorer cette solution afin
d'augmenter les nombres
Abdessalem DAKHLI 19
Chapitre 3. Reconstruction des Images Binaires par recherche
Taboue
de '1' adjacents en respectant les contraintes de projections
orthogonales (horizontale et verticale), à l'aide d'une recherche
tabou
Algorithme Tabou
Variables
s;s* Configuration courante et
meilleure configuration obtenue jusqu'à pré-
sent
f; f* Fonction d'évaluation et sa
meilleure valeur obtenue jusqu'à présent
début
Initialisation de la liste tabou (liste vide)
Génération d'une configuration initiale s
s* := s
f* := f(s)
Tant que la condition d'arrêt n'est pas
vérifiée Faire
s := un des meilleurs voisins non tabou de
N(s)
si f(s) <=
f* alors
s* := s
f* := f(s)
Sinon si f* n'a pas été
améliorée depuis un certain temps alors
s := s
Vider la liste tabou
Retourner s*
Fin
3.1.1 Définition du voisinage
On associe à chaque configuration s un voisinage
N(s) construit de la manière suivante :
1.2 on recherche une bascule dans la solution initiale
(Matrice binaire)
et on change les 1 et 0 pour les quatre cellules de la
bascule. Une bascule est un ensemble de quatre cellules
(i;j), (i;j + k), (i
+ h;j) et (i + h; j +
k) tel que les cellules (i; j) et
(i + h; j + k) sont de valeur
1 et les cellules (i + h; j) et
(i;j + k) sont de valeur 0.
1.3 Les projections orthogonales de la nouvelle matrice
binaire de-
meurent inchangées après les opérations de
la bascule. On calcule les nombres d'adjacences.
1.4 on choisit les échanges qui ne sont pas dans la
liste tabou et qui
ont les nombres '1'adjacents les plus
élevés.
1.5 on crée le voisinage N(s) de s
correspondant aux échanges choisis
précédemment.
| 
