Etude de l’hybridation de TRIBES-Multiobjectif avec des techniques de recherche locale

Présentation des stratégies d’hybridation 

Définition de la notion d’hybridation Dans la littérature, il n’y a pas un moyen permettant de garantir qu’une méthode d’optimisation donnera les meilleurs résultats sur toutes les instances possibles, pour un problème donné. Dans la pratique, on peut toujours mettre en défaut une méthode par rapport à d’autres. L’hybridation peut être alors considérée comme un moyen efficace permettant de trouver un compromis entre les avantages et les inconvénients de plusieurs méthodes d’optimisation. Il y a plusieurs approches pour classifier les méthodes hybrides. Nous considérons par la suite celle qui considère le niveau et le mode d’hybridation. 

Niveaux d’hybridation

Il existe deux niveaux d’hybridation : haut et bas niveaux. Le premier niveau concerne le cas où les méthodes communiquent entre elles et coopèrent ensemble mais chacune d’entre elles garde sa propre intégrité. Le deuxième niveau concerne le cas où une méthode devient un bloc fonctionnel dans une autre méthode qui l’englobe. Les figures 4.1 et 4.2 illustrent la différence entre les deux modes. 

Modes d’hybridation

Dans la littérature, il existe deux modes d’hybridation : le mode relais et le mode coévolutionnaire. Dans le mode relais, les méthodes d’optimisation sont exécutées d’une manière séquentielle et les résultats d’une méthode vont servir comme entrée pour l’autre. En revanche, les méthodes travaillent en parallèle dans le mode co-évolutionnaire. Les figures 4.3 et 4.4 présentent les deux différents modes. Selon le niveau et le mode d’hybridation, on aura quatre classes d’hybridation possibles : relais de bas niveau, relais de haut niveau, co-évolution de bas niveau, co-évolution de haut niveau. Notons que dans la littérature, c’est la classe co-évolution de bas niveau qui a été la plus exploitée. De plus, dans cette classe, la méthode initiale garde généralement son intégrité. En revanche, pour le reste des classes, les méthodes hybridées perdent généralement leur intégrité. Dans la suite, nous proposons trois schémas différents d’hybridation de TRIBESMultiobjectif avec des techniques de recherche locale. Ces schémas appartiennent tous à la classe co-évolution de bas niveau. En effet, les schémas proposés visent à améliorer TRIBESMéthode 1 Méthode 2 Méthode 1 Méthode 2 Méthode 1 Méthode 2 Méthode n Méthode 1 Méthode 2 Méthode n Méthode 3 Figure 4.1 : Hybridation de bas niveau Figure 4.2 : Hybridation de haut niveau Figure 4.3 : Hybridation en mode relais Figure 4.4 : Hybridation en mode co-évolution 78 Multiobjectif sans perdre son intégrité. Les approches proposées réalisent une collaboration entre TRIBES et une méthode de recherche locale afin de profiter de leurs comportements respectifs.

Présentation

Comme tout algorithme d’optimisation par essaim particulaire, TRIBES ne peut être considéré ni comme un algorithme d’optimisation globale ni comme un algorithme d’optimisation locale. En effet, les résultats trouvés précédemment montrent que TRIBESMultiobjectif converge rapidement vers des fronts locaux. L’essaim stagne et les particules se trouvent piégées au niveau des optima locaux. C’est pour cette raison que l’introduction d’une technique de recherche locale peut constituer une solution pour franchir les pièges des optima locaux. De ce fait, l’hybridation entre TRIBES et un algorithme de recherche locale peut être considérée comme une approche compétitive pour traiter des problèmes difficiles d’optimisation multiobjectif : pour améliorer la capacité d’exploitation de TRIBES, nous appliquons une méthode de recherche locale (R.L). L’idée générale de nos schémas d’hybridation est d’utiliser TRIBES comme algorithme principal et de lancer régulièrement une méthode de recherche locale afin d’alterner entre phases d’exploitation et phases d’exploration. Nous proposons également deux manières de lancement de la recherche locale : une manière périodique dans laquelle la recherche locale est lancée à chaque itération de TRIBES, et une manière adaptative, dans laquelle la recherche locale ne serait lancée que si une condition dépendant de l’état d’avancement de la recherche dans TRIBES était vérifiée. De plus, la recherche locale ne va pas être nécessairement appliquée d’une manière canonique, c’est-à-dire sur toutes les particules de l’essaim : nous pouvons envisager deux autres manières, à savoir l’appliquer uniquement sur la meilleure particule de chaque tribu ou bien aussi sur toutes les particules de l’archive. Les figures 4.5, 4.6 et 4.7 montrent les différentes possibilités pour appliquer la recherche locale.