Conception d'un algorithme d'optimisation multi-objectif et application dans un réseau de télécommunication.

Abstract

L'optimisation multi-objectif est une branche très importante dans la résolution des problèmes réels. La présence de différentes approches de résolution des problèmes multi- objectif offre aux chercheurs la possibilité de choisir un axe de résolution très vaste. Malgré la restriction des deux approches (approche à base de transformation d'un problème multi- objectif vers un problème multi-objectif et l'approche non-Pareto), elles restent toujours utilisées dans certains problèmes avec une faible indépendance entre les critères à optimiser. Les approches Pareto, qui forment le pole le plus important dans la résolution des problèmes multi-objectif, reposent sur le principe d'optimalité Pareto des solutions: Toute solution de cet ensemble est optimale dans le sens qu'aucune amélioration ne peut être faite sur une composante du vecteur sans dégradation d'au moins une composante du vecteur. Cette propriété permet de maintenir l'aspect multi-objectif du problème à résoudre et assure qu'une solution n'appartenant pas à cet ensemble n'est plus intéressante. Nous avons présenté dans ce travail un algorithme très efficace pour la résolution de problèmes multi-objectif. L'algorithme MOA*, tel qu'il a été proposé par BRADLEY S. STEWART et CHELSEA C. WHITE, peut résoudre des problèmes très complexes de façon exacte, avec la garantie de toujours trouver les meilleures solutions. Cette caractéristique a été hérité de l'algorithme A* qui reste l'algorithme le plus utilisé dans la résolution des problèmes mono-objectif sous forme de graphes d'état. Faisant partie des approches Pareto, le MOA* travaille avec une organisation très apparente pour l'utilisateur. Les étapes d'évolution de cet algorithme sont transparentes du moment que chaque ensemble contient des données spécifiques de l'état du graphe à une certaine itération de l'algorithme. Ce qui contribue énormément dans la facilité d'implémentation de l'algorithme et le manipuler de telle sorte qu'il soit adéquat avec le problème à résoudre. Nous avons jugé les améliorations apportées à l'algorithme MOA* de pertinentes, et ceci en faisant référence aux performances enregistrées sur le nombre d'itérations de l'algorithme, qui agit d'une manière directe sur le temps d'exécution de l'algorithme. Les performances des heuristiques et la métaheuristique introduites pour cet algorithme (sélection aléatoire, sélection selon l'ordre d'arrivée, sélection avec moins de pères et la métaheuristique de recherche Tabou) varient selon le type du problème. Nous avons prouvé cette thèse sur des exemples différents où chaque heuristique apporte des améliorations sur un exemple possédant des caractéristiques différentes de celles des autres exemples. Ces caractéristiques peuvent être résumé es comme suit: - l'heuristique avec moins de pères est intéressante sauf dans les graphes où la plupart des nœuds possèdent le même nombre de pères. L'heuristique d'ordre d'arrivée de la liste OPEN est la concurrente de la première. Elle est la plus intéressante dans les graphes riches en matière de nœuds et d'arcs possédant la caractéristique non favorable à la première (même nombre de pères pour la plupart des noeuds). Les améliorations qu'apporte la sélection aléatoire sont du pur hasard. Elle n'est pas intéressante dans la plupart des cas. Les performances de la métaheuristique de recherche Tabou ne sont pas loin des deux premières heuristiques, malgré qu'elle perde des itérations lors des déplacements des nœuds vers la liste TABOU. Le choix d'une version parmi les quatre nécessite une connaissance à priori du problème par l'utilisateur, ainsi qu'un aperçu sur le graphe d'état. La difficulté de l'algorithme MOA* apparaît dans certains problèmes où les données varient selon l'environnement du problème. Ces problèmes sont connus sous le nom de problèmes à environnement dynamique. L'état des données ne peut pas être prédéfini dans ce genre de problèmes. Cette difficulté incite les chercheurs à travailler avec les méthodes approchées (algorithmes évolutionnaires avec métaheuristiques) où l'on définit une solution aléatoire, et on essaye de rapprocher la solution exacte à l'aide de la notion de voisinage. Ces méthodes sont très utilisées dans des problèmes dont on ne connaît pas le comportement. Ceci ne remet pas en cause l'efficacité de l'algorithme MOA* puisqu'il est présenté comme méthode exacte applicable sur une classe de problèmes à caractère déterministe. L'application du MOA* sur un réseau de télécommunication, proposé par France Télécom, a donné des résultats répondant aux besoins du domaine de télécommunication. L'ensemble non-dominé de solutions (ensemble Pareto Optimal) laisse aux décideurs le choix de la solution selon leurs préférences. Ce type d'applications, qui consistent à minimiser le nombre de sites et à maximiser le trafic en assurant la couverture de la totalité du réseau, est un problème très fréquent ces dernières années. Il constitue la préoccupation majeure des compagnies de télécommunication, vue la demande croissante dans ce domaine. Il reste à noter que nos contributions dans ce travail ont été faites de telle manière qu'elles soient adéquates avec la classe des problèmes multi-objectif, et qu'elles répondent aux besoins de cette classe. Ceci implique l'introduction de quelques perspectives concernant l'implémentation de l'algorithme MOA* dans ces différentes versions et les améliorations qui peuvent être apportées dans les prochains travaux concernant cette approche. Ces perspectives peuvent être résumées comme suit :

- l'introduction des outils permettant de mieux estimer le parcours restant dans le graphe (la fonction h de l'algorithme MOA*). Ces heuristiques doivent satisfaire la propriété d'admissibilité (les estimations ne doivent pas être loin des valeurs réelles) - Introduire des outils d'aide à la décision pour le choix des nœuds à traiter durant les itérations de l'algorithme - Introduire un mécanisme de rapprochement de la solution durant l'évolution du MOA* pour prendre en compte l'aspect dynamique du problème, en faisant appel à la notion de génération utilisée par les algorithmes génétiques. Ces perspectives seront intéressantes dans les prochains travaux qui porteront sur le développement de l'algorithme A* multi-objectif en particulier et sur les méthodes exactes en général.