Les Algorithmes Évolutionnaires (AEs) sont des méthodes de recherche inspirées par la théorie darwinienne de l'évolution, travaillant sur une population de solutions potentielles, par itération de phases de sélections et de variations aléatoires. La sélection d'une représentation, la définition des paramètres ou l'attribution de leurs propres valeurs ont une influence cruciale sur les performances de l'algorithme. Un choix qui ne s'accorde pas à la fonction de fitness peut rendre le problème plus difficile à résoudre. Trouver une configuration appropriée pour un AE est donc depuis longtemps un grand défi. Bien que les AEs soient reconnus comme des méthodes compétitives sur des problèmes de grande taille, ils sont sujets à un certain nombre de critiques tel celui du réglage/contrôle des paramètres. Par réglage, nous entendons l'approche qui consiste à trouver des valeurs satisfaisantes pour les paramètres avant l'exécution de l'algorithme. Dans cette thèse, nous fournissons des arguments qu'un jeu de paramètres constants durant l'exécution semble être inadéquat. Notre contribution au vaste domaine de l'optimisation concerne le réglage automatique des paramètres selon le problème traité. Dans la première partie, nous exposons la problématique du réglage/contrôle des paramètres ainsi que les principales heuristiques existantes. Dans la deuxième, nous proposons deux méthodes pour le contrôle dynamique des paramètres associés à la représentation des solutions. Dans la troisième, nous proposons l'algorithme évolutionnaire à états (SEA), une variante parallèle des AEs ; cette nouvelle approche gère simultanément plusieurs AEs afin de contrôler dynamiquement les paramètres au cours du processus d'optimisation. Dans la dernière partie, nous présentons une instanciation du SEA qui intègre différents taux de mutation afin d'adapter le meilleur taux à la recherche. Cette nouvelle instance est testée sur le problème du sac à dos multidimensionnel. Des résultats comparables ont été obtenus, ce qui prouve que le SEA est capable de contrôler dynamiquement le compromis exploration/exploitation.

Enjeux :<br />Le pétrole ne se manifeste à distance par aucune propriété physique permettant sa découverte. C'est pourquoi<br />l'exploration pétrolière consiste à imager par la méthode sismique les pièges susceptibles d'en contenir. Le but de la<br />migration, ou rétropropagation numérique des enregistrements sismiques, est de former une image des structures<br />géologiques en replaçant en profondeur les réflecteurs qui ont causé les échos enregistrés. Les variations de la<br />vitesse de propagation des ondes, de 1500 m/s dans l'eau à 6000 m/s et plus dans les roches sédimentaires<br />compactes, rendent cette tâche critique car un modèle de vitesse erroné donne une image très distordue. Le coût<br />énorme des forages effectués sur des structures fausses impose l'obtention d'images précises du sous-sol et donc la<br />détermination du champ des vitesses sismiques, surtout en contexte de piémonts lorsque les images sont peu<br />lisibles.<br />Positionnement du sujet :<br />Toutes les méthodes de détermination des vitesses exploitent la redondance des données sismiques : chaque portion<br />de réflecteur renvoie plusieurs échos correspondant à des couples source-récepteur dont le déport, la distance de la<br />source au récepteur, diffère. Certaines méthodes telles que la tomographie fonctionnent bien lorsque les structures<br />géologiques sont assez simples pour que les réflexions soient bien reconnaissables sur l'ensemble des<br />enregistrements, mais ce n'est pas le cas dans les piémonts. Nous avons donc choisi la migration itérative, dont le<br />principe est que, la Terre étant unique, les images obtenues avec les différents déports doivent être superposables.<br />Ce critère ne suffisant généralement pas à déterminer les vitesses correctes, il est nécessaire d'introduire des<br />informations géologiques. Pour l'optimisation du champ des vitesses, les méthodes de gradient étant<br />d'implémentation fort lourde, nous avons choisi un algorithme évolutionnaire pour sa simplicité, son adaptabilité, et<br />surtout son automaticité. De plus, la diversité de la population optimale donne une idée de l'incertitude qui entache<br />le résultat.<br />Résultats :<br />Parmi tous les champs de vitesses possibles, bien peu ont une géométrie géologiquement acceptables, d'où l'idée de<br />ne manipuler que des modèles satisfaisant au critère de coupe équilibrée. Une coupe est équilibrée lorsqu'elle est<br />compatible avec les hypothèses de conservation des épaisseurs et des longueurs mesurées le long des couches.<br />Dans une première partie, nous avons montré que l'on pouvait non seulement générer des modèles<br />géométriquement plausibles, mais aussi les optimiser relativement à des données de pendage de couches ou de<br />position de chevauchements disponibles à l'affleurement ou dans des puits. La seconde partie concernant<br />l'optimisation des vitesses n'a pu être reliée à la première. Dans cette seconde partie, nous avons représenté le<br />champ de vitesses par des grilles. Par le choix d'un algorithme évolutionnaire multi objectif, nous avons pu faire<br />coopérer efficacement les critères de semblance et de semblance différentielle qui, tous deux, mesurent l'invariance<br />de l'image migrée quant au déport. Nous avons amélioré le réalisme des solutions en les lissant dans la direction du<br />pendage. Enfin, nous avons extrait, des écarts à cette invariance, des corrections des grilles de vitesse qui<br />accélèrent notablement la convergence. Les résultats obtenus sur les données Marmousi, un cas synthétique<br />réaliste, sont satisfaisants. Sur les données réelles de Mer du Nord, le dôme de sel reste un problème non résolu par<br />les méthodes automatiques, mais ses environs sont bien imagés.<br />Transfert des résultats vers l'industrie :<br />Le principal intérêt de la méthode développée est son automaticité et sa souplesse. Son créneau est le dégrossisage<br />rapide de problèmes difficiles, avant qu'un interprétateur ne reprenne la main avec des méthodes interactives plus<br />poussées, mais aussi plus exigeantes en expérience et plus consommatrices de temps humain.

Thèse de doctorat--Informatique et réseaux--Paris--ENST, 2005. / Bibliogr. p. 165-177. Résumé.

Il est de plus en plus fréquent de faire appel à des opérateurs spécifiques en conception de circuits. Les opérateurs spécifiques peuvent être mis en oeuvre par des unités matérielles dédiées, en vue de réduire la taille du code, d'améliorer les performances et de réduire la surface du circuit. Dans cette thèse, nous proposons un flot de conception basé sur l'identification d'opérateurs spécifiques pour la synthèse de haut niveau. Les points clés de ce flot de conception sont l'énumération automatique et la sélection des opérateurs spécifiques à partir d'un code de l'application de haut niveau et la re-génération du code source intégrant les opérateurs spécifiques sélectionnés. Contrairement aux approches proposées précédemment, notre flot de conception est adaptable et est indépendant des outils de synthèse de haut niveau (il ne nécessite pas d'intervenir sur les algorithmes d'ordonnancement et de projection des outils de synthèse de haut niveau). Les résultats expérimentaux montrent que notre approche permet de réduire la surface du circuit de 19% en moyenne, et jusqu'à 37% dans certains cas, par rapport à une synthèse de haut niveau traditionnelle. La latence du circuit est réduite en moyenne de 22%, et atteint jusqu'à 59%. De plus, la taille du code est réduite de 74% en moyenne.

Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.

De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles. / Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs.

Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé « Diffusion dans une Clique Congestionnée ». Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphes. / This thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes.

Le génome est très organisé au sein du noyau cellulaire. Cette organisation et plus spécifiquement la localisation et la dynamique des gènes et chromosomes contribuent à l'expression génétique et la différenciation des cellules que ce soit dans le cas de pathologies ou non. L'exploration de cette organisation pourrait dans le futur aider à diagnostiquer et identifier de nouvelles cibles thérapeutiques. La conformation des chromosomes peut être analysée grâce au marquage ADN sur plusieurs sites et aux mesures de distances entre ces différents marquages fluorescents. Dans ce contexte, l'organisation spatiale du chromosome III de levure a montré que les deux types de cellules, MATa et MATalpha, sont différents. Par contre, les données issues de l'imagerie electronique sont bruitées à cause de la résolution des systèmes de microscope et du fait du caractère vivant des cellules observées. Dans cette thèse, nous nous intéressons au développement de méthodes de classification pour différencier les types de cellules sur la base de mesures de distances entre 3 loci du chromosome III et d'une estimation du bruit. Dans un premier temps, nous nous intéressons de façon générale aux problèmes de classification binaire à l'aide de SVM de grandes tailles et passons en revue les algorithmes d'optimisation stochastiques du premier ordre. Afin de prendre en compte les incertudes, nous proposons un modèle d'apprentissage qui ajuste sa robustesse en fonction du bruit. La méthode évite les situations où le modèle est trop conservatif et que l'on rencontre parfois avec les formulations SVM robustes. L'amplitude des pertubations liées au bruit qui sont incorporées dans le modèle est controllée par l'optimisation d'une erreur de généralisation. Aucune hypothèse n'est faite sur la distribution de probabilité du bruit. Seule une borne estimée des pertubations est nécessaire. Le problème peut s'écrire sous la forme d'un programme biniveaux de grande taille. Afin de le résoudre, nous proposons un algorithme biniveau qui réalise des déplacements stochastiques très peu coûteux et donc adapté aux problèmes de grandes tailles. La convergence de l'algorithme est prouvée pour une classe générale de problèmes. Nous présentons des résultats numériques très encourageants qui confirment que la technique est meilleure que l'approche SOCP (Second Order Cone Programming) pour plusieurs bases de données publiques. Les expériences numériques montrent également que la nonlinéarité additionnelle générée par l'incertitude sur les données pénalise la classification des chromosomes et motivent des recherches futures sur une version nonlinéaire de la technique proposée. Enfin, nous présentons également des résultats numériques de l'algorithme biniveau stochastique pour la sélection automatique de l'hyperparamètre de pénalité dans les SVM. L'approche évite les coûteux calculs que l'on doit inévitablement réaliser lorsque l'on effectue une validation croisée sur des problèmes de grandes tailles. / The genome is highly organized within the cell nucleus. This organization, in particular the localization and dynamics of genes and chromosomes, is known to contribute to gene expression and cell differentiation in normal and pathological contexts. The exploration of this organization may help to diagnose disease and to identify new therapeutic targets. Conformation of chromosomes can be analyzed by distance measurements of distinct fluorescently labeled DNA sites. In this context, the spatial organization of yeast chromosome III was shown to differ between two cell types, MATa and MATa. However, imaging data are subject to noise, due to microscope resolution and the living state of yeast cells. In this thesis, the aim is to develop new classification methods to discriminate two mating types of yeast cells based on distance measurements between three loci on chromosome III aided by estimation the bound of the perturbations. We first address the issue of solving large scale SVM binary classification problems and review state of the art first order optimization stochastic algorithms. To deal with uncertainty, we propose a learning model that adjusts its robustness to noise. The method avoids over conservative situations that can be encountered with worst case robust support vector machine formulations. The magnitude of the noise perturbations that is incorporated in the model is controlled by optimizing a generalization error. No assumption on the distribution of noise is taken. Only rough estimates of perturbations bounds are required. The resulting problem is a large scale bi-level program. To solve it, we propose a bi-level algorithm that performs very cheap stochastic gradient moves and is therefore well suited to large datasets. The convergence is proven for a class of general problems. We present encouraging experimental results confirming that the technique outperforms robust second order cone programming formulations on public datasets. The experiments also show that the extra nonlinearity generated by the uncertainty in the data penalizes the classification of chromosome data and advocates for further research on nonlinear robust models. Additionally, we provide the experimenting results of the bilevel stochastic algorithm used to perform automatic selection of the penalty parameter in linear and non-linear support vector machines. This approach avoids expensive computations that usually arise in k-fold cross validation.

Dans cette thèse, on présente nos travaux sur la virtualisation dans le contexte de la réplication des serveurs de contenu vidéo. Les travaux couvrent la conception d’une architecture de virtualisation pour laquelle on présente aussi plusieurs algorithmes qui peuvent réduire les couts globaux à long terme et améliorer la performance du système. Le travail est divisé en plusieurs parties : les solutions optimales, les solutions heuristiques pour des raisons de passage à l’échelle, l’orchestration des services, l’optimisation multi-objective, la planification de services dans des réseaux actifs et complexes et l'intégration d'algorithmes dans une plate-forme réelle / In this thesis, we designed and implemented a tool which performs optimizations that reduce the number of migrations necessary for a delivery task. We present our work on virtualization in the context of replication of video content servers. The work covers the design of a virtualization architecture for which there are also several algorithms that can reduce overall costs and improve system performance. The thesis is divided into several parts: optimal solutions, greedy (heuristic) solutions for reasons of scalability, orchestration of services, multi-objective optimization, service planning in complex active networks, and integration of algorithms in real platform. This thesis is supported by models, implementations and simulations which provide results that showcase our work, quantify the importance of evaluating optimization techniques and analyze the trade-off between reducing operator cost and enhancing end user satisfaction index

Le radar à ouverture synthétique inverse (ISAR) est normalement utilisé pour produire l'image à haute résolution d'une cible éloignée en mouvement. Le mouvement de la cible est essentiel à l'imagerie mais un mouvement de translation produit une migration en portée des réflecteurs de la cible et introduit aussi un terme de phase additif et tous deux produisent une défocalisation de l'image. Dans ce mémoire, nous explorons comment l'algorithme génétique peut être utile à ISAR en le combinant à différentes méthodes connues de compensations du mouvement, plus particulièrement à l'algorithme AutoClean. Nous comparerons la performance de l'algorithme Auto-Clean telle qu'elle, de l'algorithme AutoClean avec sa combinaison à l'algorithme génétique et à d'autres combinaisons dont la méthode de projection AJTF et la méthode de minimisation de l'entropie MEM.