OPTIMISATION COMBINATOIRE

Introduction

Les problèmes d’optimisation occupent actuellement une place importante dans la communauté scientifique où il est nécessaire de trouver des solutions optimales pour des problèmes très compliqués et difficiles à résoudre. Parmi les méthodes les plus utilisées pour la résolution de tels problèmes, on trouve les métaheuristiques qui englobent un ensemble d’algorithmes capables de résoudre des problèmes assez compliqués en s’inspirant d’analogies avec la physique (recuit simulé), avec la biologie (algorithmes évolutionnaires)ou encore l’éthologie (colonies de fourmis, essaims particulaires). Dans ce chapitre, nous avons présenter le concept d’optimisation combinatoire et ses différentes techniques, où nous avons concentrer sur les métaheuristiques vu que c’est la méthode d’optimisation que nous allons utiliser pour générer notre modèle de détection d’intrusions. Plus particulièrement, la méthode de recuit simulé et celle de recherche tabou qui sont utilisées dans ce travail conjointement avec le réseau de neurones multicouches pour optimiser les poids de ce dernier afin de perfectionner notre modèle de détection d’intrusions.

Optimisation Combinatoire

L’optimisation combinatoire recouvre toutes les méthodes qui permettent de déterminer l’optimum d’une fonction avec ou sans contraintes. En théorie, un problème d’optimisation combinatoire est défini par un ensemble d’instances. A chaque instance du problème est associé un ensemble discret de solutions S, un sous­ensemble X de S représentant les solutions admissibles (réalisables) et une fonction de coût f (ou fonction objectif) qui assigne à chaque solution s ∈X le nombre réel (ou entier) f (s). Résoudre un tel problème (plus précisément une telle instance du problème) consiste à trouver une solution s* ∈ X optimisant la valeur de la fonction de coût f. Une telle solution s* s’appelle une solution optimale ou un optimum global.

Classification des méthodes d’optimisation combinatoire

 La résolution d’un problème d’optimisation combinatoire est réalisée à l’aide des méthodes illustrées dans la figure suivante : 

 Méthodes exactes

 Le principe essentiel d’une méthode exacte consiste généralement à énumérer, souvent de manière implicite, l’ensemble des solutions de l’espace de recherche. Pour améliorer l’énumération des solutions, une telle méthode dispose de techniques pour détecter le plus tôt possible les échecs (calculs de bornes) et d’heuristiques spécifiques pour orienter les différents choix. Parmi les méthodes exactes, on trouve la plupart des méthodes traditionnelles (développées depuis une trentaine d’années) telles les techniques de séparation et évaluation (Branch and Bound) ou la programmation dynamique. Les méthodes exactes ont permis de trouver des solutions optimales pour des problèmes de taille raisonnable.

Méthodes approchées

 Lorsque l’on dispose d’un temps de calcul limité ou lorsqu’on est confronté à des problèmes difficiles ou de taille importante, on peut avoir recours aux méthodes approchées, en se contentant de rechercher une solution de bonne qualité. Dans ce cas le choix est parfois possible entre une heuristique spécialisée et une métaheuristique :

• Heuristique : Le mot heuristique vient du grec « eurisko »qui signifie « je trouve »d’où la célèbre Eureka d’Archimède. Une heuristique, ou méthode approximative, est un algorithme qui fournit rapidement(en temps polynomial) une solution réalisable, pas nécessairement optimale, pour un problème d’optimisation difficile. Une méthode heuristique est généralement conçue pour un problème particulier, en s’appuyant sur sa structure propre. 
• Métaheuristique : Le mot métaheuristique est dérivé de la composition de deux mots grecs : méta signifiant « au­delà »et heuristique. En effet, ces algorithmes se veulent des méthodes génériques pouvant optimiser une large gamme de problèmes différents, sans nécessiter de changement profond dans l’algorithme employé

Métaheuristiques 

Définition

 Contrairement aux méthodes exactes, les métaheuristiques permettent de s’attaquer aux instances problématiques de grande taille en fournissant des solutions satisfaisantes dans un délai raisonnable. Il n’y a aucune garantie de trouver des solutions globales optimales ou même des solutions limitées. Les métaheuristiques ont reçu de plus en plus de popularité au cours des 20 dernières années. Leur utilisation dans de nombreuses applications montre leur efficacité pour résoudre des problèmes vastes et complexes. Parmi ces domaines, on peut citer les suivants : 

• Conception technique, optimisation de la topologie et optimisation structurelle en électronique et VLSI, aérodynamique, dynamique des fluides, télécommunications, automobile, et la robotique
• Apprentissage automatique et fouille de données en bioinformatique et biologie computationnelle, et les finances.
• Simulation et identification en chimie, physique et biologie, traitement du signal et de l’image…etc.
• Planification des problèmes de routage, planification des robots, problèmes d’ordonnancement et de production, logistique et transport, gestion de la chaîne d’approvisionnement…etc. 

Concepts fondamentaux des métaheuristiques 

Les métaheuristiques ne nécessitent pas une connaissance particulière sur les problèmes d’optimisation à résoudre. Il suffit d’associer une ou plusieurs variables à une ou plusieurs solutions (optimum). Il existe deux points critiques pour toute métaheuristique :

• Diversification : Le principe de diversification d’une méthode d’optimisation donnée correspond à sa capacité de parcourir aisément l’espace de recherche pour obtenir des solutions très différentes les unes des autres. Autrement dit, c’est une mécanisme pour une exploration assez large de l’espace de recherche.