Au cours de cette thèse, l'exploration de l'espace de solutions par des métaheuristiques est abordée. Les métaheuristiques sont des méthodes d'optimisation utilisées pour résoudre des problèmes NP-difficile. Elles explorent aléatoirement l'espace de recherche pour trouver les meilleures solutions. Dans un premier temps, l'ensemble des solutions est modélisé par un espace unidimensionnel par une Méthode de Conversion de l'Espace de recherche (MCE). Des métriques sont proposées pour évaluer l'exploration de l'espace de recherche par une métaheuristique en identifiant les zones explorées et inexplorées. Ces métriques sont utilisées pour orienter l'exploration de l'espace de recherche d'une méthode d'optimisation.La convergence est améliorée en accentuant le recherche dans les zones explorées. Pour sortir des minimums locaux, l'exploration est diversifiée en la dirigeant vers les zones inexplorées. En associant l'exploration du voisinage des solutions et ces métriques cartographiques, il est possible d'améliorer les performances des métaheuristiques. Plusieurs algorithmes mono-objectifs et multiobjectifs sont implémentés en version classique, hybridé par la recherche locale et par la MCE. Le Flexible Job Shop Problem (FJSP) est utilisé comme problème de référence. Les expérimentations avec les algorithmes hybridés montrent une amélioration des performances / In this thesis, the solution space exploration by the metaheuristic is developed. The metaheuristics optimization methods are used to solve NP-hard problems. They explore randomly the search space to look for the best solutions. In a first step, the solution set is modeled by a one-dimensional space by a Mapping Method (MaM). Metrics are proposed to evaluate the search space exploration by a metaheuristic, identifying the explored and unexplored zones. These metrics are used to guide the search space exploration of an optimization method. The convergence is improved by emphasizing the research in the zones explored. To get out local minima, the exploration is diversified by pointing it towards the unexplored zones. Combining the neighbour discovery of the solutions and these mapping metrics, it is possible to improve the performance of metaheuristics. Several single-objective and multi-objective algorithms are implemented in the classic version, hybridized with local search and MaM. The Flexible Job Shop Problem (FJSP) is used as a reference problem. The experimentations with hybridized algorithms show performance improved
Identifer | oai:union.ndltd.org:theses.fr/2014TROY0036 |
Date | 05 December 2014 |
Creators | Autuori, Julien |
Contributors | Troyes, Hnaien, Faicel, Hamzaoui, Abdelaziz |
Source Sets | Dépôt national des thèses électroniques françaises |
Language | French |
Detected Language | French |
Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0023 seconds