Chapitre 3. Reconstruction des Images Binaires par
recherche Taboue
TAB. 3.4 -Résultat de Reconstruction des
images 40x40 hv-convexe en appliquant le principe d'intensification
Abdessalem DAKHLI 30
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
|
|
2106
|
1044
|
890
|
|
1854
|
792
|
642
|
|
1854
|
793
|
644
|
|
128,3
|
19,7
|
18,3
|
|
0,797
|
1,670
|
1,720
|
Chapitre 3. Reconstruction des Images Binaires par recherche
Taboue
Test image Taille 70x70
TAB. 3.5 -Résultat de Reconstruction des
images 70x70 hv-convexe en appliquant le principe d'intensification
Abdessalem DAKHLI 31
Abdessalem DAKHLI 32
Chapitre 3. Reconstruction des Images Binaires par
recherche Taboue
Les résultats de l'application montrent bien que la
solution est améliorée en restant dans la même zone
d'espace de recherche, c'est à dire que la recherche est bien
localisée. Cette technique montre bien qu'il peut pénaliser des
solutions éloignées.
Diversification
La diversification permet à l'algorithme de bien
explorer l'espace des solutions, et d'éviter que le processus de
recherche ne soit trop localisé et laisse de grandes régions du
domaine totalement inexplorées.
La plus simple des stratégies de diversification
consiste à interrompre périodiquement l'acheminement normal de la
procédure tabou, et à la faire redémarrer à partir
d'une autre solution, choisie aléatoirement, ou "intelligemment". Une
autre méthode consiste à biaiser la fonction d'évaluation
f, en introduisant un terme qui pénalise les transformations
effectuées fréquemment, afin de favoriser des transformations
nouvelles. Ce type de stratégie de diversification peut être
utilisé de façon continue, sans interrompre la procédure
de recherche taboue.
Dans notre contexte on a utilisé la stratégie de
diversification qui consiste à redémarrer à partir d'une
autre solution et on a augmenté la taille de la liste taboue à 12
au lieu de 7.
Chapitre 3. Reconstruction des Images Binaires par
recherche Taboue
TAB. 3.6 -Résultat de Reconstruction
des images 40x40 hv-convexe en appliquant le principe de diversification
Image
Nombre de '1' adjacents de l'image originale
Nombre de '1' adjacents d'une solution prise par hasard
obtenue en appliquant tabou sans amélioration
Nombre de '1' adjacents de l'image Reconstruite par Tabou avec
amélioration en utilisant le principe de diversification
Temps d'exécution (en seconde)
Taux de Reconstruc-
tion
|
1
|
2
|
3
|
|
842
|
560
|
684
|
|
740
|
445
|
610
|
|
620
|
447
|
620
|
|
10,8
|
4,6
|
8,7
|
|
0,083
|
1,2
|
1,298
|
Abdessalem DAKHLI 33
Les résultats ont montré que le principe de
diversification a amélioré la solution prise dans certain cas,
c'est-à-dire qu'avec cette technique on peut explorer des autres zones
de recherche. Dans ces zones la fonction objective augmente en rapprochant
à l'optimum global.
En résumé, nous disons que la diversification et
l'intensification sont des concepts complémentaires, qui enrichissent la
méthode de recherche taboue et la rendent plus robuste et plus
efficace.
Les résultats prouvent clairement que la reconstruction
est presque parfaite en appliquant la recherche tabou améliorée
c'est-à-dire l'utilisation de principe diversification et de
d'intensification.
On a constaté que le principe de diversification permet
de bien couvrir l'espace des solutions, explorer de nouvelles régions,
loin de la solution et de même, il pénalise les solutions
très proches contrairement au technique d'intensification qui explore
plus en profondeur la 'région'de la solution courante c'est à
dire permet d'approfondir la recherche, et qui pénalise les solutions se
trouvant dans des zones loin de la solution courante.
Abdessalem DAKHLI 34
| 
