Chapitre 3. Reconstruction des Images Binaires par
recherche Taboue
Ces deux types d'images montrent bien que le temps
d'exécution augmente lorsque la taille de matrice carrée
augmente.
La solution obtenue par la recherche taboue a une fonction
objective assez important par rapport à la solution obtenue de
même par rapport au test image de taille 40x40, c'est-à-dire
l'image reconstruite a un nombre de '1'adjacents important. La reconstruction
montre bien l'existence d'un grand nombre de blocs de composants de bascules.
Cette solution a un taux de reconstruction faible par rapport à l'image
originale, malgré le nombre d'objets dans les solutions
élaborées est assez important par rapport à l'image
origine.
On a constaté encore que la solution obtenue par la
recherche taboue, est une amélioration pour la solution gloutonne,
c'est-à-dire amélioration de la fonction objective qui
désigne le nombre de '1'adjacents.
3.2.2 Reconstruction des images HV-CONVEXES par la
recherche taboue avec amélioration
On reconstruit une solution optimale en utilisant l'approche
de la recherche Tabou avec amélioration en utilisant les principes de
diversification et l'intensification.
Intensification
L'intensification consiste à approfondir la recherche
dans certaines régions du domaine, identifiées comme susceptibles
de contenir un optimum global. Cette technique est appliquée
périodiquement, et pour une durée limitée. Pour mieux
intensifier la recherche dans une zone bien localisée, plusieurs
stratégies sont proposées dans la littérature. La plus
simple consiste à retourner à l'une des meilleures solutions
trouvée jusqu'à présent, puis de reprendre la recherche
à partir de cette solution, en réduisant la longueur de la liste
taboue pour un nombre limité d'itérations. Dans ce cas, on adapte
la procédure de recherche taboue, en élargissant le voisinage de
la solution courante (en augmentant la taille de l'échantillon
8(x)), tout en diminuant le pas des transformations. On peut aussi
remplacer simplement l'heuristique taboue par une autre méthode plus
puissante, ou mieux adaptée, pour une recherche locale.
Dans notre contexte on a démarré par la solution
obtenue par tabou sans amélioration et on a diminué la taille de
la liste taboue à 4 au lieu de 7. Les résultats de l'application
de cet algorithme en appliquant le principe d'intensification, sont
illustrés dans la table ci-dessous :
Image
Nombre de '1' adjacents de l'image originale
Nombre de '1' adjacents de la meilleure solution obtenue en
appliquant tabou sans amélioration
Nombre de '1' adjacents de l'image Reconstruite par Tabou avec
amélioration en utilisant le principe d'intensification
Temps d'exécution (en seconde)
Taux de Reconstruc-
tion
|
1
|
2
|
3
|
|
842
|
560
|
684
|
|
761
|
477
|
618
|
|
764
|
481
|
618
|
|
10,8
|
4,6
|
8,7
|
|
0,083
|
1,2
|
1,298
|
| 
