Models and Approaches for Multi-Population and Multi-Region Optimization in Dynamic Environments: Application to Online Feature Selection Modèle et Approches pour l’Optimisation Multi-Populations et Multi-Régions dans les Environnements Dynamiques : Application à la sélection d’attributs en ligne

This thesis addresses issues related to optimization in dynamic environments where the matter is not only being able to identify optima in ever changing objective functions landscapes but also to track them over time at each change of the landscape. Many real world problems are of this nature and require the development of effective approaches to solve them. The contribution of this thesis covers several aspects including the development of a model from which approaches have been derived and an application has been considered. In a first step, a variant of the Wind Driven Optimization (WDO) metaheuristic was developed leading to the Modified Wind Driven Optimization (MWDO) algorithm for static optimization and which outperforms the basic WDO when applied to numerical optimization. Such a development has provided a framework for the formulation of a model for dynamic optimization based on the impact of earth phenomena on the movement of air particles. By introducing multi-population and multi-region concepts, a new approach to dynamic optimization has been developed called Wind Driven Dynamic Optimization (WD2O) with the following capabilities : maintaining diversity, economically detecting changes and preventing collisions. Its basic idea is to associate promising and non-promising regions in the dynamic landscape of the objective function with the high pressure and low pressure regions in the natural metaphor. Tested on the Moving Peak Benchmark (MPB), WD2O has been shown very competitive if not better than state-of-the-art approaches and especially on high dimensional instances. Secondly, a second new approach has been developed to solve the problem of obsolete memory induced by the useless information accumulated during the optimization process while avoiding the problem of change. The developed mechanism called pressure mechanism has enabled solving the outdated memory problem efficiently. The proposed approache has been validated and compared with the literature approaches where we can see very promising results. Finally, the application of the concepts developed to the problem of on-line feature selection has been undertaken showing the potential of the algorithm developed to solve the dynamic optimization problems in practical cases. Cette thèse traite les problèmes inhérents à l’optimisation dans les environnements dynamiques où il ne s’agit pas uniquement d’identifier les optima dans le paysage de la fonction objectif mais aussi de pouvoir les suivre à chaque changement du paysage au cours du temps. Beaucoup de problèmes réels sont de cette nature et imposent le développement d’approches efficaces pour les résoudre. La contribution de cette thèse couvre plusieurs aspects dont notamment le développement d’un modèle duquel des approches ont été dérivées et une application a été envisagée. Dans un premier temps, une variante améliorant les performances de la métaheuristique Wind Driven optimization (WDO) a été développée donnant lieu à l’algorithme Modified Wind Driven Optimization (MWDO) pour l’optimisation statique et qui surpasse l’algorithme de base WDO appliquée à l’optimisation numérique. Un tel développement a constitué un cadre pour la formulation d’un modèle pour l’optimisation dynamique en s’inspirant de l’impact des phénomènes terrestres sur le mouvement des particules d’air. En introduisant les concepts de multi-populations et multi-régions, une nouvelle approche pour l’optimisation dynamique a été développée appelée Wind Driven Dynamic Optimization (WD2O) dotée des capacités suivantes : maintien de la diversité, détection économique des changements et prévention des collisions. Son idée de base consiste à associer les régions prometteuses et non prometteuses dans le paysage dynamique de la fonction objectif aux régions haute pression et basse pression dans la métaphore naturelle. Testée sur le problème Moving Peak Benchmark (MPB), WD2O s’est montrée très compétitive voir meilleure que les approches d’état de l’art et notamment sur des instances de grandes de dimension. Dans un second temps, une deuxième nouvelle approche a été développée pour résoudre le problème de la mémoire obsolète induit par les informations accumulées au cours du processus d’optimisation et sans utilité après un changement tout en s’affranchissant du problème de la détection de changements. Nous avons appelé le nouveau mécanisme ainsi développé : le mécanisme de pression qui a permis de résoudre le problème de la mémoire obsolète de manière efficace. Cette approche a été validée et comparée aux approches de la littérature où l’on peut constater des résultats très prometteurs. Enfin, l’application des concepts développés au problème dela sélection d’attributs en ligne ou en streaming a été abordée montrant le potentiel de l’algorithme développé à résoudre les problèmes d’optimisation dynamiques dans les cas réels.