Using Metaheuristics for NP-Hard and Big Data Optimization Problems: Conception, Adaptation, and a Proposal for a Smarter application

Abstract

Ce mémoire décrit des travaux de recherche menés pour la conception de nouvelles métaheuristiques/leurs applications aux problèmes d'optimisation NP-Difficiles/Big Data. En effet, quatre contributions majeures sont apportées. La première contribution présente un nouveau modèle de recherche inspiré de la nature appelé « Lightning-Inspired Search Algorithm ». Le modèle utilise un mécanisme constructif, similaire au modèle de la formation naturelle de la foudre, qui favorise la diversité pendant la recherche pour éviter une convergence prématurée. Les expériences réalisées sur le problème du voyageur de commerce montrent un comportement très compétitif de l'algorithme. La deuxième contribution présente une adaptation de l'algorithme « Fireworks Algorithm (FA) » aux problèmes d'ordonnancement à une seule machine. L'algorithme proposé modifie le mécanisme d'exploration/d'exploitation de la phase de génération d’étincelles. Les résultats expérimentaux sont satisfaisants par rapport aux algorithmes de l'état de l'art. La troisième contribution concerne l'application de FA à des problèmes d'optimisation de big data. L'algorithme original FA est revisité pour améliorer sa vitesse de convergence tout en préservant sa robustesse. Les résultats montrent que la solution proposée surpasse toutes les méthodes proposées pour BigOPT. La dernière contribution introduit de nouvelles idées sur le développement des métaheuristiques, en introduisant des techniques de configuration automatique d'algorithmes/de sélection d'algorithmes par instance, pour une utilisation plus intelligente des métaheuristiques dans les applications futures.