L'algorithme génétique (AG), est fondé sur les méanismes de codage, sélection, croisement, mutation et insertion. Chacun présente plusieurs choix ce qui donne résultat à plusieurs variantes de AG.<br /><br /> Nous avons obtenu une variante meilleure d'algorithme génétique pour le problème du voyageur de commerce. Dans laquelle, nous avons introduit notre nouvel opérateur de croisement Cedrx qui est jumelé avec l'opérateur edrx donne de bons résultats. <br /><br /> Cette étude, nous a permis de créer des variantes efficaces d'algorithme génétique pour les probèmes suivants: <br /><br />+ Le problème d'ordonnancement dans les ateliers de type Job Shop;<br />+ Le problème des atterrissages d'avions (PAA);<br />+ Le problème d'ordonnancement des véhicules sur une chaîe de <br /> production dans une usine (POV).

Thèse. 3ème cycle. Paris III. 1927.

Dans cette thèse, nous étudions des thématiques autour des algorithmes stochastiques et c'est pour cette raison que nous débuterons ce manuscrit par des éléments généraux sur ces algorithmes en donnant des résultats historiques pour poser les bases de nos travaux. Ensuite, nous étudierons un algorithme de bandit issu des travaux de N arendra et Shapiro dont l'objectif est de déterminer parmi un choix de plusieurs sources laquelle profite le plus à l'utilisateur en évitant toutefois de passer trop de temps à tester celles qui sont moins per­formantes. Notre but est dans un premier temps de comprendre les faiblesses structurelles de cet algorithme pour ensuite proposer une procédure optimale pour une quantité qui mesure les performances d'un algorithme de bandit, le regret. Dans nos résultats, nous proposerons un algorithme appelé NS sur-pénalisé qui permet d'obtenir une borne de regret optimale au sens minimax au travers d'une étude fine de l'algorithme stochastique sous-jacent à cette procédure. Un second travail sera de donner des vitesses de convergence pour le processus apparaissant dans l'étude de la convergence en loi de l'algorithme NS sur-pénalisé. La par­ticularité de l'algorithme est qu'il ne converge pas en loi vers une diffusion comme la plupart des algorithmes stochastiques mais vers un processus à sauts non-diffusif ce qui rend l'étude de la convergence à l'équilibre plus technique. Nous emploierons une technique de couplage afin d'étudier cette convergence. Le second travail de cette thèse s'inscrit dans le cadre de l'optimisation d'une fonc­tion au moyen d'un algorithme stochastique. Nous étudierons une version stochastique de l'algorithme déterministe de boule pesante avec amortissement. La particularité de cet al­gorithme est d'être articulé autour d'une dynamique qui utilise une moyennisation sur tout le passé de sa trajectoire. La procédure fait appelle à une fonction dite de mémoire qui, selon les formes qu'elle prend, offre des comportements intéressants. Dans notre étude, nous verrons que deux types de mémoire sont pertinents : les mémoires exponentielles et poly­nomiales. Nous établirons pour commencer des résultats de convergence dans le cas général où la fonction à minimiser est non-convexe. Dans le cas de fonctions fortement convexes, nous obtenons des vitesses de convergence optimales en un sens que nous définirons. En­fin, l'étude se termine par un résultat de convergence en loi du processus après une bonne renormalisation. La troisième partie s'articule autour des algorithmes de McKean-Vlasov qui furent intro­duit par Anatoly Vlasov et étudié, pour la première fois, par Henry McKean dans l'optique de la modélisation de la loi de distribution du plasma. Notre objectif est de proposer un al­gorithme stochastique capable d'approcher la mesure invariante du processus. Les méthodes pour approcher une mesure invariante sont connues dans le cas des diffusions et de certains autre processus mais ici la particularité du processus de McKean-Vlasov est de ne pas être une diffusion linéaire. En effet, le processus a de la mémoire comme les processus de boule pesante. De ce fait, il nous faudra développer une méthode alternative pour contourner ce problème. Nous aurons besoin d'introduire la notion de pseudo-trajectoires afin de proposer une procédure efficace. / In this thesis, we are studying severa! stochastic algorithms with different purposes and this is why we will start this manuscript by giving historicals results to define the framework of our work. Then, we will study a bandit algorithm due to the work of Narendra and Shapiro whose objectif was to determine among a choice of severa! sources which one is the most profitable without spending too much times on the wrong orres. Our goal is to understand the weakness of this algorithm in order to propose an optimal procedure for a quantity measuring the performance of a bandit algorithm, the regret. In our results, we will propose an algorithm called NS over-penalized which allows to obtain a minimax regret bound. A second work will be to understand the convergence in law of this process. The particularity of the algorith is that it converges in law toward a non-diffusive process which makes the study more intricate than the standard case. We will use coupling techniques to study this process and propose rates of convergence. The second work of this thesis falls in the scope of optimization of a function using a stochastic algorithm. We will study a stochastic version of the so-called heavy bali method with friction. The particularity of the algorithm is that its dynamics is based on the ali past of the trajectory. The procedure relies on a memory term which dictates the behavior of the procedure by the form it takes. In our framework, two types of memory will investigated : polynomial and exponential. We will start with general convergence results in the non-convex case. In the case of strongly convex functions, we will provide upper-bounds for the rate of convergence. Finally, a convergence in law result is given in the case of exponential memory. The third part is about the McKean-Vlasov equations which were first introduced by Anatoly Vlasov and first studied by Henry McKean in order to mode! the distribution function of plasma. Our objective is to propose a stochastic algorithm to approach the invariant distribution of the McKean Vlasov equation. Methods in the case of diffusion processes (and sorne more general pro cesses) are known but the particularity of McKean Vlasov process is that it is strongly non-linear. Thus, we will have to develop an alternative approach. We will introduce the notion of asymptotic pseudotrajectory in odrer to get an efficient procedure.

Étant donnés un graphe simple non orienté G = (V, E) et un sommet particulier r dans V appelé racine, un arbre enraciné, ou r-arbre, de G est soit le graphe nul soit un arbre contenant r. Si un vecteur de capacités sur les sommets est donné, un sous-graphe de G est dit borné si le degré de chaque sommet dans le sous-graphe est inférieur ou égal à sa capacité. Soit w un vecteur de poids sur les arêtes et p un vecteur de profits sur les sommets. Le problème du r-arbre borné maximum (MBrT, de l’anglais Maximum Bounded r-Tree) consiste à trouver un r-arbre borné T = (U, F) de G tel que son poids soit maximisé. Si la contrainte de capacité du problème MBrT est relâchée, nous obtenons le problème du r-arbre maximum (MrT, de l’anglais Maximum r-Tree). Cette thèse contribue à l’étude des problèmes MBrT et MrT.Tout d’abord, ces deux problèmes sont formellement définis et leur complexité est étudiée. Nous présentons ensuite des polytopes associés ainsi qu’une formulation pour chacun d’entre eux. Par la suite, nous proposons plusieurs algorithmes combinatoires pour résoudre le problème MBrT (et donc le problème MrT) en temps polynomial sur les arbres, les cycles et les cactus. En particulier, un algorithme de programmation dynamique est utilisé pour résoudre le problème MBrT sur les arbres. Pour les cycles, nous sommes amenés a considérer trois cas différents pour lesquels le problem MBrT se réduit à certains problèmes polynomiaux. Pour les cactus, nous montrons tout d’abord que le problème MBrT peut être résolu en temps polynomial sur un type de graphes appelé cactus basis. En utilisant une série de décompositions en sous-problèmes sur les arbres et les cactus basis, nous obtenons un algorithme pour les graphes de type cactus.La deuxième partie de ce travail étudie la structure polyédrale de trois polytopes associés aux problèmes MBrT et MrT. Les deux premiers polytopes, Bxy(G,r,c) et Bx(G,r,c) sont associés au problème MBrT. Tous deux considèrent des variables sur les arêtes de G, mais seuls Bxy(G,r,c) possède également des variables sur les sommets de G. Le troisième polytope, Rx(G,r), est associé au problème MrT et repose uniquement sur les variables sur les arêtes. Pour chacun de ces trois polytopes, nous étudions sa dimension, caractérisons certaines inégalités définissant des facettes, et présentons les moyens possibles de décomposition. Nous introduisons également de nouvelles familles de contraintes. L’ajout de ces contraintes nous permettent de caractériser ces trois polytopes dans plusieurs classes de graphes.Pour finir, nous étudions les problèmes de séparation pour toutes les inégalités que nous avons trouvées jusqu’ici. Des algorithmes polynomiaux de séparation sont présentés, et lorsqu’un problème de séparation est NP-difficile, nous donnons des heuristiques de séparation. Tous les résultats théoriques développés dans ce travail sont implémentés dans plusieurs algorithmes de coupes et branchements auxquels une matheuristique est également jointe pour générer rapidement des solutions réalisables. Des expérimentations intensives ont été menées via le logiciel CPLEX afin de comparer les formulations renforcées et originales. Les résultats obtenus montrent de manière convaincante la force des formulations renforcées. / Given a simple undirected graph G = (V, E) with a so-called root node r in V, a rooted tree, or an r-tree, of G is either the empty graph, or a tree containing r. If a node-capacity vector c is given, then a subgraph of G is said to be bounded if the degree of each node in the subgraph does not exceed its capacity. Let w be an edge-weight vector and p a node-price vector. The Maximum Bounded r-Tree (MBrT) problem consists of finding a bounded r-tree T = (U, F) of G such that its weight is maximized. If the capacity constraint from the MBrT problem is relaxed, we then obtain the Maximum r-Tree (MrT) problem. This dissertation contributes to the study of the MBrT problem and the MrT problem.First we introduce the problems with their definitions and complexities. We define the associated polytopes along with a formulation for each of them. We present several polynomial-time combinatorial algorithms for both the MBrT problem (and thus the MrT problem) on trees, cycles and cactus graphs. Particularly, a dynamic-programming-based algorithm is used to solve the MBrT problem on trees, whereas on cycles we reduce it to some polynomially solvable problems in three different cases. For cactus graphs, we first show that the MBrT problem can be solved in polynomial time on a so-called cactus basis, then break down the problem on any cactus graph into a series of subproblems on trees and on cactus basis.The second part of this work investigates the polyhedral structure of three polytopes associated with the MBrT problem and the MrT problem, namely Bxy(G, r, c), Bx(G, r, c) and Rx(G, r). Bxy(G, r, c) and Bx(G, r, c) are polytopes associated with the MBrT problem, where Bxy(G, r, c) considers both edge- and node-indexed variables and Bx(G, r, c) considers only edge-indexed variables. Rx(G, r) is the polytope associated with the MrT problem that only considers edge-indexed variables. For each of the three polytopes, we study their dimensions, facets as well as possible ways of decomposition. We introduce some newly discovered constraints for each polytope, and show that these new constraints allow us to characterize them on several graph classes. Specifically, we provide characterization for Bxy (G, r, c) on cactus graphs with the help of a decomposition through 1-sum. On the other hand, a TDI-system that characterizes Bx(G,r,c) is given in each case of trees and cycles. The characterization of Rx(G,r) on trees and cycles then follows as an immediate result.Finally, we discuss the separation problems for all the inequalities we have found so far, and present algorithms or cut-generation heuristics accordingly. A couple of branch-and-cut frameworks are implemented to solve the MBrT problem together with a greedy-based matheuristic. We compare the performances of the enhanced formulations with the original formulations through intensive computational test, where the results demonstrate convincingly the strength of the enhanced formulations.

Le but de cette thèse est d'élaborer des méthodes d'éclatement basées sur les distances de Bregman pour la résolution d'inclusions monotones composites dans les espaces de Banach réels réflexifs. Ces résultats nous permettent d'étendre de nombreuses techniques, jusqu'alors limitées aux espaces hilbertiens. De plus, même dans le cadre restreint d'espaces euclidiens, ils donnent lieu à de nouvelles méthodes de décomposition qui peuvent s'avérer plus avantageuses numériquement que les méthodes classiques basées sur la distance euclidienne. Des applications numériques en traitement de l'image sont proposées. / The goal of this thesis is to design splitting methods based on Bregman distances for solving composite monotone inclusions in reflexive real Banach spaces. These results allow us to extend many techniques that were so far limited to Hilbert spaces. Furthermore, even when restricted to Euclidean spaces, they provide new splitting methods that may be more avantageous numerically than the classical methods based on the Euclidean distance. Numerical applications in image processing are proposed.

Dans les disciplines de l'intelligence artificielle et de la recherche opérationnelle, on rencontre de nombreux problèmes comme l'allocation de ressources, l'ordonnancement, la, conception, le diagnostic automatisé. Ces problèmes se formulent aisément comme des problèmes de satisfaction de contraintes (CSP). Un CSP est défini comme étant un ensemble de contraintes impliquant un certain nombre de variables. L'objectif consiste simplement à trouver un ensemble de valeurs à affecter aux variables, de sorte que toutes les contraintes soient satisfaites. Dans le cas le plus général, les problèmes de satisfaction de contraintes ont un aspect fortement combinatoire qui leur confère une grande complexité. Nous nous intéressons dans le cadre de cette thèse aux problèmes de satisfaction de contraintes binaires en domaines finis. Les méthodes auxquelles nous nous intéressons pour résoudre un CSP sont, les méthodes dites incomplètes : elles font une réparation d'une configuration en parcourant de manière non systématique l'espace des configurations. Dans cette catégorie de méthodes, notre intérêt s'est plus particulièrement tourné vers les Algorithmes Evolutionnistes. Ce sont des méthodes générales d'optimisation combinatoire qui sont inspirées de la théorie de l'évolution. Dans un CSP classique, on recherche une solution, sans avoir à optimiser de fonction. Pour entrer dans le cadre des Algorithmes Évolutionnistes, on se doit de définir une fonction d'évaluation pour les CSP qui prend ses valeurs minimales sur les solutions du problème. Cette fonction pourrait être utilisée par toutes méthodes incomplètes, telles que les techniques min-conflits, GSAT et leurs variantes. Nous montrons dans cette thèse l'application de notre fonction d'évaluation pour la méthode min-conflits ainsi que pour un algorithme évolutionniste. D'un autre côté, dans le contexte plus spécifique des algorithmes génétiques, nous souhaitons guider l'évolution (i.e. recherche d'une solution), en faisant des transformations sur la population plus orientées vers le problème de satisfaction de contraintes. Nous définissons ainsi des opérateurs de mutation et de croisement spécialisés pour les CSP qui sont basés sur la structure du graphe de contraintes. Ensuite, nous incorporons le concept d'adaptation dans l'opérateur de croisement, afin d'améliorer la recherche de l'algorithme. Dans ce mémoire, nous décrivons et justifions les algorithmes mis en oeuvre, en illustrant les techniques implémentées par la résolution de problèmes de coloriage de graphe avec trois couleurs, et de CSP générés aléatoirement.

Cette thése étudie le problème NP-difficile de optimization quadratique en variables binaires (BQO), à savoir le problème de la maximisation d'une fonction quadratique en variables binaires. BQO peut représenter de nombreux problèmes importants de différents domaines et servir de modèle unifié pour un grand nombre de problèmes d'optimisation combinatoire portant sur les graphes. Cette thèse est consacrée au développement d'algorithmes métaheuristiques efficaces pour résoudre le BQO et ses applications. Premièrement, nous proposons algorithmes de "backbone guided" recherche tabou et d'un algorithme mémétique multi-niveaux sur la base de la technique de la fixation de variables. Ces techniques sont toutes deux basées sur l'idée de la réduction du problème afin de mener à bien une exploitation exhaustive d'une petite région de recherche. Ensuite, nous nous concentrons sur des procédés avancés de génération des solutions initiales préférables et développons des algorithmes combinant GRASP avec la recherche tabou et les algorithmes de path-relinking. En outre, nous résolvons des problèmes, y compris le problème de coupe maximum, de clique maximum, de clique maximale de sommets pondérés et la somme coloration minimum, soit en appliquant directement ou avec une légère adaptation de nos algorithmes développés pour BQO, avec l'hypothèse que ces problèmes sont reformulés en BQO. Enfin, nous présentons un algorithme mémétique basé sur la recherche tabou qui s'attaque efficacement au BQO avec contrainte de cardinalité.

Dans cette thèse, on s'intéresse à deux problèmes de conception de réseaux, utilisant la technologie OFDM multi-bandes. Le premier problème concerne la conception d'un réseau mono-couche avec contraintes spécifiques. Nous donnons une formulation en PLNE pour ce problème et étudions le polyèdre associé à sa restriction sur un arc. Nous introduisons deux familles d'inégalités valides définissant des facettes et développons un algorithme de coupes et branchements pour le problème. Nous étudions la variante multicouche du problème précédent et proposons plusieurs PLNE pour le modéliser. Nous identifions plusieurs familles de facettes et discutons des problèmes de séparation associés. Nous développons un algorithme de coupes et branchements utilisant l'ensemble des contraintes identifiées. Enfin, une formulation compacte et deux formulations basées sur des chemins sont proposées pour le problème. Nous présentons deux algorithmes de génération de colonnes et branchements pour le problème. / In this thesis we consider two capacitated network design (CND) problems, using OFDM multi-band technology. The first problem is related to single-layer network design with specific requirements. We give an ILP formulation for this problem and study the polyhedra associated with its arc-set restriction. We describe two families of facet defining inequalities. We devise a Branch-and-Cut algorithm for the problem. Next, we investigate the multilayer version of CND using OFDM technology. We propose several ILP formulations and study the polyhedron associated with the first (cut) formulation. We identify several classes of facets and discuss the related separation problem. We devise a Branch-and-Cut algorithm embedding valid inequalities of both single-layer and multilayer problems. The second formulation is compact, and holds a polynomial number of constraints and variables. Two further path formulations are given which yield two efficient Branch-and-Price algorithms for the problem.

Au cours de cette thèse, nous avons étudié le problème de déploiement des Réseaux de Capteurs Sans-Fil (RCSF) pour des applications indoor tel que le bâtiment intelligent. Le but de notre travail était de développer un outil de déploiement capable d'assister les concepteurs de RCSF lors de la phase de déploiement de ces derniers. Nous avons commencé cette thèse par la modélisation de tous les paramètres qui interviennent lors du déploiement des RCSF, à savoir : coût, connectivité, couverture et durée de vie. Par la suite, nous avons implémenté cinq algorithmes d'optimisation, dont trois multi-objectifs afin de résoudre le problème de déploiement. Deux cas d'études réelles (grande et petite instance) ont été identifiés afin de tester ces algorithmes. Les résultats obtenus ont montré que ces algorithmes sont efficaces quand il s'agit d'un petit bâtiment (petit espace). Par contre, dès que la surface du bâtiment augmente les performances des algorithmes étudiés se dégradent. Pour répondre à cela, nous avons développé et implémenté un algorithme d'optimisation multi-objectifs hybride. Cet algorithme se base sur des notions de clustering et d'analyse de données afin de limiter le nombre d'évaluations directes qu'entreprennent ces méthodes pendant chaque itération. Afin d'assurer cette limitation d'évaluation les fonctions de fitness sont approximées grâce aux réseaux de neurones et l'algorithme de classification K-means. Les résultats obtenus ont montré une très bonne performance sur les deux instances de tailles différentes. Ces résultats ont été comparés à ceux obtenus avec les méthodes classiques utilisées et sont compétitives et prometteuses. / In this thesis, we studied the Wireless Sensor Network deployment for indoor environments with a focus on smart building application. The goal of our work was to develop a WSN deployment tool which is able to assist network designers in the deployment phase. We begin this thesis with network modeling of all the deployment parameters and requirement, such as : cost, coverage, connectivity and network lifetime. Thereafter, we implement five optimisation methods, including three multi-objective optimization agorithms, to resolve WSN deployment problem. Then, two realistics study cases were identified to test the performances of the aforementioned algorithms. The obtained results shows that these algorithms are very efficient for deploying a small scale network in small buildings. However, when the building surface becomes more important the algorithms tends to converge to local optimum while consuming high processing time. To resolve this problem, we develop and implement a new Hybrid multi-objectif optimization algorithm wich limits the number of direct evaluation. This algorithm is based on data-mining methods (Artificial Neural Networks and K-means) and tries to approximate the fitness value of each individual in each generation. At every generation of the algorithm, the population is divided to K clusters and we evaluate only the closest individual to cluster centroide. The fitness value of the rest of population is approximated using a trained ANN. A comparative study was made and the obtained results show that our method outperformes others in the two sudy cases (small and big buildings).

La géométrie de l’information est la théorie mathématique qui applique les méthodes de la géométrie différentielle dans le domaine des statistiques et de la théorie de l’information. C’est une technique très prometteuse pour l’analyse et l’illustration des algorithmes itératifs utilisés en communications numériques. Cette thèse porte sur l’application de cette technique ainsi que d’autre technique d’optimisation bien connue, l’algorithme itératif du point proximal, sur les algorithmes itératifs en général. Nous avons ainsi trouvé des interprétations géométriques (basée sur la géométrie de l’information) et proximales (basée sur l’algorithme du point proximal)intéressantes dans le cas d’un algorithme itératif de calcul de la capacité des canaux discrets sans mémoire, l’algorithme de Blahut-Arimoto. L’idée étant d’étendre cette application sur une classe d’algorithmes itératifs plus complexes. Nous avons ainsi choisi d’analyser l’algorithme de décodage itératif des modulations codées à bits entrelacés afin de trouver quelques interprétations et essayer de proposer des liens existant avec le critère optimal de maximum de vraisemblance et d’autres algorithmes bien connus dans le but d’apporter certaines améliorations par rapport au cas classique de cet algorithme, en particulier l’étude de la convergence.Mots-clefs : Géométrie de l’information, algorithme du point proximal, algorithme de Blahut-Arimoto, décodage itératif, Modulations codées à bits entrelacés, maximum de vraisemblance. / Information geometry is a mathematical theory that applies methods of differential geometryin the fields of statistics and information theory. It is a very promising technique foranalyzing iterative algorithms used in digital communications. In this thesis, we apply this technique, in addition to the proximal point algorithm, to iterative algorithms. First, we have found some geometrical and proximal point interpretations in the case of an iterative algorithmfor computing the capacity of discrete and memoryless channel, the Blahut-Arimoto algorithm.Interesting results obtained motivated us to extend this application to a larger class of iterative algorithms. Then, we have studied in details iterative decoding algorithm of Bit Interleaved Coded Modulation (BICM) in order to analyse and propose some ameliorations of the classical decoding case. We propose a proximal point interpretation of this iterative process and find the link with some well known decoding algorithms, the Maximum likelihood decoding.