CHAPITRE 4
TABLE 4.5 - Comparatif du taux d'exploration en utilisation les
variantes de l'algorithme BOA avec une population de taille 5
|
Short-term exploration - House map
|
|
Method
|
Average
|
Min
|
Max
|
|
BOA
|
89.11
|
81.77
|
95.13
|
|
ABOA
|
90.38
|
81.77
|
95.13
|
|
mBOA
|
89.14
|
81.07
|
95.13
|
|
SABOA
|
85.13
|
82.98
|
85.93
|
|
xBOA
|
93.35
|
92.18
|
93.92
|
de recherche au lieu d'intensifier la recherche au niveau
local. Ceci permet à l'algorithme d'échapper au piège de
converger prématurément vers un minima local, ce qui augmente les
chances de trouver l'optimum global.
Toutefois, chaque nouvel individu créé doit
être évalué, ce qui engendre l'augmentation du nombre
d'évaluations de la fonction fitness. Par conséquent, le temps de
calcul de l'al-gorithme augmente aussi. Étant donné que le
paramètre de probabilité de croisement était
fixé à 0.583, il y a donc 58% plus d'individus à
évaluer dans l'algorithme xBOA comparé au BOA classique.
L'algorithme mBOA souffre aussi d'un temps de calcul
élevé, ceci est causé par les calculs
supplémentaires ajoutés à cette variante dans la phase
d'exploitation intensive. Bien que cette nouvelle phase permet
d'accélérer la convergence de l'algorithme par rapport à
la méthode BOA classique, elle reste tout de même dominée
par l'algorithme xBOA que ce soit dans les critères du temps, de la
convergence ou du taux d'exploration de la zone.
ABOA domine les autres variantes dans le critère du
temps d'exécution, mais n'est pas parvenue à dépasser
à un taux d'exploration de 90.38%, alors que xBOA a pu atteindre un
résultat supérieur. Quant à l'algorithme SABOA, il a
donné le résultat le moins performant avec un taux d'exploration
de 85.13%, mais possède néanmoins l'avantage de n'avoir qu'un
seul hyperparamètre en entrée, ce qui réduit la
complexité du paramétrage.
Les deux solutions dominantes sont donc:
-- ABOA : qui possède le meilleur temps de calcul; et --
xBOA : qui obtient le meilleur taux d'exploration.
Il faut donc considérer le choix d'un bon compris entre
la maximisation de la surface explorée et le temps de calcul
nécessaire. Ce choix dépendra de la nature de la mission: dans un
contexte d'une mission de sauvetage par exemple, le facteur « temps »
est très important, ce qui rend envisageable la décision de
privilégier la réduction de la durée d'exécution au
profit de la qualité d'exploration. En revanche, dans un contexte de
déminage, de nettoyage ou de surveillance, il serait judicieux de
privilégier la maximisation de la zone explorée au
dépourvu du temps de calcul, jusqu'à une certaine mesure.
Exploration rate -- House Map
0
Exploration rate
127
50 100 150 250
Step number
Execution time -- House Map
1200 -
1000
!- AB OA
- 0- BOA MBOA SA B OA
- - XBOA
800 -
V
N
V)
600 -
CDE
i-
400-
200 -
sn
0 2 a 40 610
Exploration rate
*Les résultats présentent les valeurs
moyennes de 10 exécutions
FIGURE 4.14 -- Comparaison des variantes de l'algorithme
BOA en utilisant la stratégie à court terme et une population de
taille 5
128
| 
