Dissertations / Theses on the topic 'Heuristiques de recherche locale'
To see the other types of publications on this topic, follow the link: Heuristiques de recherche locale.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Heuristiques de recherche locale.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Danna, Emilie. "Intégration des techniques de recherche locale à la programmation linéaire en nombres entiers." Avignon, 2004. http://www.theses.fr/2004AVIG0132.
Full textAbstract:
Cette thèse présente plusieurs algorithmes pour l'intégration des techniques de recherche locale à la programmation linéaire en nombres entiers (PLNE). Premièrement, nous introduisons un schéma de coopération entre recherche locale et génération de colonnes qui généralise le concept d'heuristiques pour le branch-and-cut au branch-and-price et nous l'appliquons avec succès au problème de tournées de véhicules avec fenêtres de temps. Deuxièmement, nous présentons une nouvelle heuristique pour les problèmes linéaires quelconques en nombres entiers : Relaxation Induced Neighborhood Search (RINS). Cette heuristique produit des solutions entières de qualité pour des modèles qu'il était très difficile de résoudre auparavant. Elle est maintenant implantée dans le logiciel ILOG CPLEX 9. RINS exploite les trois concepts fondamentaux de la recherche locale (voisinage, intensification et diversification) en les transposant à la programmation linéaire en nombres entiers. Cette heuristique est générique : elle peut être appliquée à n'importe quel modèle de PLNE, sans aucune connaissance préalable de sa structure. RINS nous permet de formaliser la notion d'algorithme "conceptuellement hybride". Ce paradigme de développement consiste à utiliser une seule technique de résolution et à intégrer dans ce cadre les concepts d'autres techniques plutôt qu'à faire coopérer des composants logiciels. Les performances de RINS et notre analyse des difficultés des algorithmes hybrides existants laissent à penser que cette classe d'algorithmes est prometteuse. Troisièmement, nous nous intéressons plus en détail au problème d'ordonnancement d'atelier avec coûts d'avance et de retard sur lequel RINS est particulièrement efficace. Nous proposons plusieurs améliorations et extensions du modèle disjonctif pour ce problème et une heuristique (MCORE: big-M COefficient REduction) qui pourrait être généralisée à d'autres modèles de structure similaire. MCORE est également un algorithme "conceptuellement hybride"We present several algorithms for integrating local search technique into mixed integer programming (MIP). We first introduce a cooperation scheme between local search and branch-and-price that generalizes the concept of branch-and-cut heuristics to branch-and-price and we apply it successfully to the vehicle routing problem with time windows. We then present a new MIP heuristic that we call Relaxation Induced Neighborhood Search (RINS). This heuristic finds good integer solutions on models that previously were very difficult to solve. It is now implemented in ILOG CPLEX 9. RINS exploits the three fundamental concepts of local search (neighborhood, intensification, and diversification) and transposes them to mixed integer programming. This heuristic is generic : it can be applied to any MIP model, with no other input than the model itself. RINS allows us to formalize the notion of "hybrid in spirit'' algorithms. This development paradigm consists in using only one optimization technique and integrating into its framework concepts of other resolution techniques instead of having several software components cooperate. RINS performances and our analysis of difficulties encountered by existing hybrid algorithms suggest that this class of algorithms is promising. We finally concentrate on the job-shop scheduling problem with earliness and tardiness costs on which RINS is particularly effective. We propose several improvements and extensions of the disjunctive model for this problem and a heuristic (MCORE : big-M COefficient REduction) that could be generalized to other MIP models of similar structure. MCORE is also a "hybrid in spirit'' algorithm
2
Mynard, Laurent. "Exploration locale oscillante heuristiquement ordonnée." Paris 6, 1998. http://www.theses.fr/1998PA066255.
Full textAbstract:
Cette thèse présente un nouvel algorithme d'exploration par voisinage pour la résolution de problèmes d'optimisation combinatoire. Cet algorithme se nomme HOLSA, acronyme de Heuristic Oscillating Local Search Algorithm. Son originalité vient de l'utilisation de techniques issues de l'énumeration implicite au sein d'un schéma général d'exploration locale et de l'usage systématique d'une stratégie oscillante. L'énumération implicite, en particulier A*, a inspiré tout d'abord la méthode d'évaluation des éléments, qui permet d'inclure un aspect prédictif dans l'exploration, aspect en général ignoré des méthodes d'exploration locale. Ensuite, elle a influencé la méthode de mémorisation retenue, qui se démarque fortement de la mémoire flexible de la recherche tabou, processus de mémorisation le plus utilisé en exploration locale. HOLSA a été expérimenté pour la résolution du sac à dos multidimensionnel, en variables 0 - 1 ou en variables entières, sur une librairie de problèmes de la littérature comme sur des instances aléatoires. Mais son application n'est pas restreinte à un seul type de problèmes, et il fonctionne également pour des problèmes d'optimisation non linéaire. Les comparaisons avec les principaux algorithmes d'exploration locale et avec la méthode par évaluation et séparation (Branch and Bound) montrent que cette approche présente un intérêt et permet d'obtenir un rapport performant entre la qualité de la solution trouvée et le temps de résolution requis.
3
Goëffon, Adrien. "Nouvelles heuristiques de voisinage et mémétiques pour le problème Maximum de Parcimonie." Phd thesis, Université d'Angers, 2006. http://tel.archives-ouvertes.fr/tel-00256670.
Full textAbstract:
La reconstruction phylogénétique vise à reconstituer l'histoire évolutive d'un ensemble d'espèces sous forme d'un arbre. Parmi les méthodes de reconstruction, le problème Maximum de Parcimonie (MP) consiste à trouver un arbre binaire dont les feuilles sont associées à des séquences de caractères données, et qui minimise le score de parcimonie. Les méthodes de résolution existantes de ce problème NP-complet s'attachent généralement à appliquer des méthodes heuristiques traditionnelles, comme des algorithmes gloutons et de recherche locale. L'une des diffcultés du problème repose sur la manipulation d'arbres et la définition de voisinages d'arbres.Dans cette thèse, nous nous intéressons en premier lieu à l'amélioration des techniques de résolution du problème MP basées sur un algorithme de descente. Après avoir montré de manière empirique les limites des voisinages existants, nous introduisons un voisinage progressif qui évolue au cours de la recherche afin de limiter l'évaluation de voisins infructueux lors d'une descente. L'algorithme obtenu est ensuite hybridé à un algorithme génétique utilisant un croisement d'arbres spécifique fondé sur les mesures de distance entre chaque couple d'espèces dans l'arbre. Cet algorithme mémétique exhibe des résultats très compétitifs, tant sur des jeux de test tirés de la littérature que sur des jeux générés aléatoirement.
4
Luong, Thé Van. "Métaheuristiques parallèles sur GPU." Thesis, Lille 1, 2011. http://www.theses.fr/2011LIL10058/document.
Full textAbstract:
Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leurdéploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on ComputersReal-world optimization problems are often complex and NP-hard. Their modeling is continuously evolving in terms of constraints and objectives, and their resolution is CPU time-consuming. Although near-optimal algorithms such as metaheuristics (generic heuristics) make it possible to reduce the temporal complexity of their resolution, they fail to tackle large problems satisfactorily. Over the last decades, parallel computing has been revealed as an unavoidable way to deal with large problem instances of difficult optimization problems. The design and implementation of parallel metaheuristics are strongly influenced by the computing platform. Nowadays, GPU computing has recently been revealed effective to deal with time-intensive problems. This new emerging technology is believed to be extremely useful to speed up many complex algorithms. One of the major issues for metaheuristics is to rethink existing parallel models and programming paradigms to allow their deployment on GPU accelerators. Generally speaking, the major issues we have to deal with are: the distribution of data processing between CPU and GPU, the thread synchronization, the optimization of data transfer between the different memories, the memory capacity constraints, etc. The contribution of this thesis is to deal with such issues for the redesign of parallel models of metaheuristics to allow solving of large scale optimization problems on GPU architectures. Our objective is to rethink the existing parallel models and to enable their deployment on GPUs. Thereby, we propose in this document a new generic guideline for building efficient parallel metaheuristics on GPU. Our challenge is to come out with the GPU-based design of the whole hierarchy of parallel models.In this purpose, very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of solutions to GPU threadsor memory management. These approaches have been exhaustively experimented using five optimization problems and four GPU configurations. Compared to a CPU-based execution, experiments report up to 80-fold acceleration for large combinatorial problems and up to 2000-fold speed-up for a continuous problem. The different works related to this thesis have been accepted in a dozen of publications, including the IEEE Transactions on Computers journal
5
Kessaci, Marie-Éléonore. "Recherche locale et optimisation combinatoire : de l'analyse structurelle d'un problème à la conception d'algorithmes efficaces." Thesis, Lille 1, 2011. http://www.theses.fr/2011LIL10169/document.
Full textAbstract:
Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficacesMany problems from combinatorial optimization are NP-hard, so that exact methods remain inefficient to solve them efficiently. However, metaheuristics are approximation methods known and used for their efficiency. But they often require a lot of parameters, which are very difficult to set in order to provide good performance. As a consequence, a challenging question is to perform such parameter tuning easier, or adaptive.The fitness landscape of given combinatorial optimization problem, based on a search space, a fitness function and a neighborhood relation, allow to characterize the problem structure and make the understanding of the dynamics of search approches possible.This thesis deals with fitness landscape analysis, together with the link with some neighborhood-based metaheuristic classes. We show the influence of the landscape structure on the dynamics of metaheuristics, for two challenging problems from the field of logistics. We analyze the landscape characteristics which help to design efficient local search metaheuristics and/or to set their parameters.Neutrality is one of the main structural characteristic of a landscape. Such landscapes have numerous plateaus, which often inhibits the progress of local search algorithms. After a deep analysis of these plateaus, we prove that this neutral structure cannot be ignored. Then, we use several information linked with neutrality, and particularly with blocking plateaus, in order to design a first local search approach, which appear to efficient and easy to implement. At last, in order to extend our work on the neutral structure, we chose to exploit the neutrality involved in the whole landscape. We propose a new local search algorithm, based on the ability of solutions of a plateau to produce improvement by means of a guiding strategy.The thesis ends with an experimental analysis of the two local search methods presented for neutral problems in order to exploit new characteristics, and then to strengthen the link between fitness landscape analysis and efficient algorithm design
6
Laroum, Sami. "Prédiction de la localisation des protéines membranaires : méthodes méta-heuristiques pour la détermination du potentiel d'insertion des acides aminés." Phd thesis, Université d'Angers, 2011. http://tel.archives-ouvertes.fr/tel-01064309.
Full textAbstract:
Dans ce travail, nous nous intéressons à la localisation des protéines adressées vers la membrane du réticulum endoplasmique, et plus spécifiquement à la reconnaissance des segments transmembranaires et des peptides signaux. En utilisant les dernières connaissances acquises sur les mécanismes d'insertion d'un segment dans la membrane, nous proposons une méthode de discrimination de ces deux types de séquences basée sur le potentiel d'insertion de chaque acide aminé dans la membrane. Cela amène à rechercher pour chaque acide aminé une courbe donnant son potentiel d'insertion en fonction de sa place dans une fenêtre correspondant à l'épaisseur de la membrane. Notre objectif est de déterminer ≪ in silico ≫ une courbe pour chaque acide aminé, afin d'obtenir les meilleures performances pour notre méthode de classification. L'optimisation, sur des jeux de données construits à partir des banques de données de protéines, des courbes est un problème difficile que nous abordons grâce aux méthodes méta-heuristiques. Nous présentons tout d'abord un premier algorithme de recherche locale permettant d'apprendre un ensemble de courbes. Son évaluation sur les différents jeux de données montre de bons résultats de classification. Cependant, nous constatons une difficulté d'ajustement pour les courbes de certains acides aminés. La restriction de l'espace de recherche grâce à des informations pertinentes sur les acides aminés et l'introduction d'un voisinage multiple nous permettent d'améliorer les performances de notre méthode et en même temps de stabiliser les courbes apprises. Nous présentons également un algorithme génétique développé afin d'explorer de manière plus diversifiée l'espace de recherche de ce problème.
7
Laroum, Sami. "Prédiction de la localisation des protéines membranaires : méthodes méta-heuristiques pour la détermination du potentiel d'insertion des acides aminés." Phd thesis, Angers, 2011. https://theses.hal.science/tel-01064309.
Full textAbstract:
Dans ce travail, nous nous intéressons à la localisation des protéines adressées vers la membrane du réticulum endoplasmique, et plus spécifiquement à la reconnaissance des segments transmembranaires et des peptides signaux. En utilisant les dernières connaissances acquises sur les mécanismes d'insertion d'un segment dans la membrane, nous proposons une méthode de discrimination de ces deux types de séquences basée sur le potentiel d'insertion de chaque acide aminé dans la membrane. Cela amène à rechercher pour chaque acide aminé une courbe donnant son potentiel d'insertion en fonction de sa place dans une fenêtre correspondant à l'épaisseur de la membrane. Notre objectif est de déterminer ≪ in silico ≫ une courbe pour chaque acide aminé, afin d'obtenir les meilleures performances pour notre méthode de classification. L'optimisation, sur des jeux de données construits à partir des banques de données de protéines, des courbes est un problème difficile que nous abordons grâce aux méthodes méta-heuristiques. Nous présentons tout d'abord un premier algorithme de recherche locale permettant d'apprendre un ensemble de courbes. Son évaluation sur les différents jeux de données montre de bons résultats de classification. Cependant, nous constatons une difficulté d'ajustement pour les courbes de certains acides aminés. La restriction de l'espace de recherche grâce à des informations pertinentes sur les acides aminés et l'introduction d'un voisinage multiple nous permettent d'améliorer les performances de notre méthode et en même temps de stabiliser les courbes apprises. Nous présentons également un algorithme génétique développé afin d'explorer de manière plus diversifiée l'espace de recherche de ce problèmeIn this work, we are interested in the localization of proteins transported towards the endoplasmic reticulum membrane, and more specifically to the recognition of transmembrane segments and signal peptides. By using the last knowledges acquired on the mechanisms of insertion of a segment in the membrane, we propose a discrimination method of these two types of sequences based on the potential of insertion of each amino acid in the membrane. This leads to search for each amino acid a curve giving its potential of insertion according to its place in a window corresponding to the thickness of the membrane. Our goal is to determine "in silico" a curve for each amino acid to obtain the best performances for our method of classification. The optimization, on data sets constructed from data banks of proteins, of the curves is a difficult problem that we address through the meta-heuristic methods. We first present a local search algorithm for learning a set of curves. Its assessment on the different data sets shows good classification results. However, we notice a difficulty in adjusting the curves of certain amino acids. The restriction of the search space with relevant information on amino acids and the introduction of multiple neighborhood allow us to improve the performances of our method and at the same time to stabilize the learnt curves. We also developed a genetic algorithm to explore in a more diversified way the space of search for this problem
8
Belaïdouni, Mériéma. "Métaheuristiques et paysages de recherche." Angers, 2001. http://www.theses.fr/2001ANGE0022.
Full textAbstract:
Les métaheuristiques sont une classe de méthodes qui fournissent des solutions de bonne qualité en temps raisonnable à des problèmes combinatoires réputés difficiles. Il existe de nombreux travaux d'application de ces méthodes mais très peu d'études s'intéressent à leur aspect fondamental. Ainsi la dynamique et le comportement des métaheuristiques restent méconnus. Cette thèse est dédiée à l'étude de quelques questions fondamentales sur les métaheuristiques. Nous avons adopté une méthodologie en trois axes : 1) l'étude des propriétés et mesures des problèmes combinatoires, 2) l'étude des comportements des métaheuristiques, 3) la mise en relation des mesures des problèmes et des comportements de métaheuristiques. Pour valider cette approche nous l'avons appliquée à deux problèmes NP-complets : MAX-CSP et SAT. Nous avons développé pour le premier axe un état de l'art qui réunit un grand nombre de mesures existantes, puis nous avons classé ces mesures. Nous avons ensuite appliqué et analysé les mesures densité d'état (DOS), distance dans un niveau (DDN), distance entre niveaux (DEN), autocorrélation et densité des coûts du processus (DCP). Concernant le deuxième axe nous avons développé la notion de performance qui fait partie des comportements d'une métaheuristique et nous avons proposé un nouveau critère d'évaluation de la performance basé sur la mesure DCP. Enfin, nous avons dans le troisième axe mis en évidence des relations entre comportements et mesures en analysant les conséquences sur les métaheuristiques, des mesures que nous avons étudiées. Ces mises en relation nous permettent de prévoir ou d'expliquer le comportement et la dynamique des métaheuristiquesMetaheuristics are a class of methods which are able to provide solutions of good quality in a reasonnable amount of time for difficult combinatorial problems. There exist a large number of applications of these methods but only few studies concern their fondamental aspects. This thesis is devoted to study some fondamental issues of metaheuristics. Three tightly related axis are explored : 1)the study of problems properties and measures, 2)the study of dynamics of metaheuristics, 3)the establishment of the relations between measures of problems and dynamics of metaheuristics. To validate this approach we have apllied it to two NP-complete problems : MAX-CSP and SAT
9
Marmion, Marie-Eleonore. "Recherche locale et optimisation combinatoire : de l'analyse structurelle d'un problème à la conception d'algorithmes efficaces." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2011. http://tel.archives-ouvertes.fr/tel-00682776.
Full textAbstract:
Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces.
10
Dupin, Nicolas. "Modélisation et résolution de grands problèmes stochastiques combinatoires : application à la gestion de production d'électricité." Thesis, Lille 1, 2015. http://www.theses.fr/2015LIL10107/document.
Full textAbstract:
La Programmation Linéaire en Nombres Entiers (PLNE) est couramment utilisée pour modéliser des problèmes d'optimisation du monde industriel, de par la facilité à modéliser des problèmes complexes d'optimisation et par l’existence d’une résolution générique par l'algorithme de Branch&Bound (B&B). La résolution B&B est souvent limitée pour des problèmes de taille réelle, les méthodes heuristiques sont alors utilisées pour trouver des solutions de bonne qualité sans avoir de preuve d'optimalité. Cette thèse étudie les limites de la résolution exacte et des heuristiques sur des problèmes industriels d'EDF, en vue de leur insertion dans le processus décisionnel opérationnel. L'application principale concerne la planification des arrêts de maintenance et de rechargement des centrales nucléaires, sujet du Challenge ROADEF 2010. Nous avons aussi traité un problème de production journalière d'un parc thermique à flammes. La méthodologie suivie est analogue pour les deux cas. On modélise tout d'abord le problème avec une formulation compacte PLNE, pour en analyser les limites de la résolution frontale, avant d’envisager des méthodes de décomposition. On dérive ensuite les méthodes exactes en matheuristiques pour résoudre des instances de taille réelle. Dans cette optique, l'hybridation de Variable Neighborhood Search (VNS) avec des voisinages définis par PLNE a donné des résultats très probants sur les deux problèmes en termes de qualités de solutions. Le fait d'avoir travaillé avec des méthodes exactes a permis également de chiffrer l'impact d'hypothèses de résolutions, de répondre à des considérations opérationnelles, mais également d'obtenir des bornes inférieuresMixed Integer Linear Programming (MILP) is a very popular and useful framework to model industrial optimization problems. This success is due to the facility to model complex optimization problems, the work can be focused on modeling, with a black box generic resolution to optimality with Branch&Bound (B&B) algorithm, or with a specialized decomposition algorithm. If MILP made lots of progresses on the last decades, it is often not sufficient to tackle real world size instances. In such cases, heuristic methods are commonly used to find good quality solutions, without any guarantee to reach the optimum and any proven bound to the optimum. Our work focus on two complex optimization problems from energy management. First application is a discretized daily Unit Commitment Problem of thermal units with specific dynamic constraints. Second application comes from the EURO/ROADEF 2010 challenge, scheduling problem of nuclear power plants' outages for maintenances and refueling. In both cases the methodology was first to model efficiently the considered problem with a MILP compact formulation, and analyze the frontal resolution's limits with B&B. Decomposition methods could also be investigated, before the exact methods are derived in a matheuristic, to be able to tackle real size instances. In particular, Variable Neighborhood Search (VNS) with MILP neighborhoods gave outstanding results on our problems. Our work allowed to estimate the impacts of usual and natural hypothesis. Furthermore, we derived dual bounds for these optimizations problems
11
Larabi, Mohand. "Le problème de job-shop avec transport : modélisation et optimisation." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2010. http://tel.archives-ouvertes.fr/tel-00625528.
Full textAbstract:
Dans cette thèse nous nous sommes intéressés à l'extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l'existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu'un robot ne peut transporter qu'un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu'un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :* Une modélisation linéaire ;* Une modélisation sous forme de graphe disjonctif ;* Plusieurs heuristiques de construction de solutions ;* Plusieurs recherches locales qui améliorent les solutions obtenues ;* Utilisation des algorithmes génétiques / mémétiques comme schéma global d'optimisation ;* De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.
12
Guo, Yuhan. "Metaheuristics for solving large size long-term car pooling problem and an extension." Thesis, Artois, 2012. http://www.theses.fr/2012ARTO0206/document.
Full textAbstract:
La dispersion spatiale de l'habitat et des activités de ces dernières décennies a fortement contribué à un allongement des distances et des temps de trajets domicile-travail. Cela a pour conséquence un accroissement de l'utilisation des voitures particulières, notamment au sein et aux abords des grandes agglomérations. Afin de réduire les impacts dus à l'augmentation du trafic routier, des services de covoiturage, où des usagers ayant la même destination se regroupent en équipage pour se déplacer, ont été mis en place partout dans le monde. Nous présentons ici nos travaux sur le problème de covoiturage régulier. Dans cette thèse, le problème de covoiturage régulier a été modélisé et plusieurs métaheuristiques de résolution ont été implémentées, testées et comparées. La thèse est organisée de la façon suivante: tout d'abord, nous commençons par présenter la définition et la description du problème ainsi que le modèle mathématique associé. Ensuite, plusieurs métaheuristiques pour résoudre le problème sont présentées. Ces approches sont au nombre de quatre: un algorithme de recherche locale à voisinage variable, un algorithme à base de colonies de fourmis, un algorithme génétique guidée et un système multi-agents génétiques auto-adaptatif. Des expériences ont été menées pour démontrer l'efficacité de nos approches. Nous continuons ensuite avec la présentation et la résolution d'une extension du problème de covoiturage occasionel comportant plusieurs destinations. Pour terminer, une plate-forme de test et d'analyse pour évaluer nos approches et une plate-forme de covoiturage sont présentées dans l'annexeNowadays, the increased human mobility combined with high use of private cars increases the load on environment and raises issues about quality of life. The extensive use of private cars lends to high levels of air pollution, parking problem, traffic congestion and low transfer velocity. In order to ease these shortcomings, the car pooling program, where sets of car owners having the same travel destination share their vehicles, has emerged all around the world. We present here our research on the long-term car pooling problem. In this thesis, the long-term car pooling problem is modeled and metaheuristics for solving the problem are investigated. The thesis is organized as follows. First, the definition and description of the problem as well as its mathematical model are introduced. Then, several metaheuristics to effectively and efficiently solve the problem are presented. These approaches include a Variable Neighborhood Search Algorithm, a Clustering Ant Colony Algorithm, a Guided Genetic Algorithm and a Multi-agent Self-adaptive Genetic Algorithm. Experiments have been conducted to demonstrate the effectiveness of these approaches on solving the long-term car pooling problem. Afterwards, we extend our research to a multi-destination daily car pooling problem, which is introduced in detail manner along with its resolution method. At last, an algorithm test and analysis platform for evaluating the algorithms and a car pooling platform are presented in the appendix
13
Gu, Wenjuan. "Problèmes de tournées de véhicules avec plusieurs produits et applications à la livraison de produits frais en circuits courts et locaux." Thesis, Ecole centrale de Lille, 2019. http://www.theses.fr/2019ECLI0013.
Full textAbstract:
Nous étudions les problèmes de tournées de véhicules pour la livraison de plusieurs produits, avec des applications dans les chaînes logistiques en circuit court et local. La chaîne logistique est composée de trois groupes d’acteurs: les fournisseurs, les plateformes de distribution et les clients. Les fournisseurs sont des agriculteurs. Les plateformes de distribution sont chargées de la consolidation. Les plateformes de distribution collectent les produits auprès des fournisseurs en faisant aller-retours. Les produits sont livrés aux clients avec une flotte de véhicules effectuant des tournées. Chaque client demande plusieurs produits. Pour minimiser les coûts de transport, il est avantageux qu’un même client soit livré par plusieurs véhicules. Mais pour le confort du client, il est imposé qu’un produit soit livré en une seule fois par un seul véhicule. En conséquence, les différents produits sont pris en compte dans les modèles et méthodes de résolution. Le problème complet est nommé Multi-Commodity two-echelon Distribution Problem (MC2DP). Le problème restreint qui concerne la livraison à partir d’une seule plateforme de distribution est nommé Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP). Nous proposons d’abord une heuristique basée sur un ALNS pour résoudre le C-SDVRP. Nous abordons ensuite le MC2DP avec des opérations de collecte et de livraison et plusieurs plateformes de distribution. Nous proposons de décomposer le problème: la collecte et la livraison sont résolues de manière séquentielle. De plus, nous développons une approche intégrée pour le MC2DP afin d’améliorer les solutions obtenues par l’approche de décompositionWe study vehicle routing problems considering multiple commodities, with applications in the local fresh food supply chains. The studied supply chain contains two echelons with three sets of actors: suppliers, distribution centers and customers. Suppliers are farmers that produce some fresh foods. Distribution centers are in charge of consolidation and delivery of the products to customers. Distribution centers collect products from the suppliers that perform direct trips. Products are delivered to the customers with a fleet of vehicles performing routes. Each customer requires several commodities, and the farmers produce a limited quantity of these commodities. For the minimization of the transportation cost, it is beneficial that a single customer is delivered by several vehicles. However, for the convenience of the customer, it is imposed that a single commodity is delivered at once by a single vehicle. Hence, different commodities have been considered. The complete problem is named Multi-Commodity two-echelon Distribution Problem (MC2DP). The restricted problem that addresses only the delivery from a single distribution center is named Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP). We first propose a heuristic based on the Adaptive Large Neighborhood Search (ALNS) for the C-SDVRP. Then, we address the whole problem (MC2DP) with collection and delivery operations and multiple distribution centers. In order to tackle this complex problem, we propose to decompose the problem: collection and delivery are sequentially solved. Furthermore, we develop an integrated approach for the MC2DP to improve the solutions obtained by the sequential approach
14
Esseghir, Mohamed Amir. "Metaheuristics for the feature selection problem : adaptive, memetic and swarm approaches." Thesis, Artois, 2011. http://www.theses.fr/2011ARTO0206/document.
Full textAbstract:
Afin d’améliorer la qualité de prédiction des techniques de classification automatique et de fouilles de données, plusieurs modèles ont été proposés dans la littérature en vue d’extraire des connaissances à partir des données. Toutefois, avec l’expansion des systèmes d’information et des technologies associées, ces techniques d’apprentissage s’avèrent de moins en moins adaptées aux nouvelles tailles et dimensions des données. On s’intéresse dans cette étude aux problèmes de grande dimensionnalité et à l’amélioration du processus d’apprentissage des méthodes de classification à travers les techniques de filtrage et de sélection d’attributs. Le problème « d’identification d’attributs pertinents » (Feature Selection Problem), tel qu’il est défini dans la littérature, relève d’une nature combinatoire. Dans le cadre de cette thèse, on s’est intéressé au développement de nouvelles techniques d’optimisation approchées et spécifiques au problème traité ainsi qu’à l’amélioration d’algorithmes existants. La conception, l’implémentation et l’étude empirique ont montré l’efficacité et la pertinence des métaheuristiques proposéesAlthough the expansion of storage technologies, networking systems, and information system methodologies, the capabilities of conventional data processing techniques remain limited. The need to knowledge extraction, compact representation and data analysis are highly motivated by data expansion. Nevertheless, learning from data might be a complex task, particularly when it includes noisy, redundant and information-less attributes. Feature Selection (FS) tries to select the most relevant attributes from raw data, and hence guides the construction of final classification models or decision support systems. Selected features should be representative of the underlying data and provide effective usefulness to the targeted learning paradigm (i.e. classification). In this thesis, we investigate different optimization paradigms as well as its adaptation to the requirements of the feature selection challenges, namely the problem combinatorial nature. Both theoritical and empirical aspects were studied, and confirm the effectiveness of the adopted methodology as well as the proposed metaheuristic based approaches
15
Bäerecke, Thomas. "Isomorphisme inexact de graphes par optimisation évolutionnaire." Paris 6, 2009. http://www.theses.fr/2009PA066335.
Full textAbstract:
L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.
16
Cornu, Marek. "Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED043/document.
Full textAbstract:
De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaisesMany Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions
17
Levasseur, Nicolas. "Heuristiques de recherche pour la résolution des WCSP." Caen, 2008. http://www.theses.fr/2008CAEN2071.
Full textAbstract:
Les Weighted Constraint Satisfaction Problem (WCSP) qui sont une généralisation à l’optimisation des CSP, sont souvent résolus par des méthodes de recherche arborescentes combinées avec des algorithmes de filtrage ou recherches locales. Bien que de nombreuses heuristiques génériques aient été proposées dans les CSP, cela est loin d’être le cas pour les WCSP. L’objectif de ce travail consistait à mettre en oeuvre de nouvelles heuristiques génériques, adaptées aux WCSP et guidant efficacement les méthodes de résolution. Pour les recherches arborescentes, nous avons proposé plusieurs heuristiques de choix de valeur et de variable basées sur un critere global, la H-Quality, moins indépendant du mécanisme de filtrage (critère local). Pour les méta-heuristiques à voisinage variable (VNS), nous avons proposé diféerentes heuristiques de voisinage basées sur la notion de degré de liberté qui dépendent de la topologie du graphe de contraintes. Puis, nous avons proposé d'étendre celles-ci aux WCSP afin de tenir compte du coût des contraintes. Afin de valider nos contributions, nous avons réalisé des expérimentations sur des problèmes réels d’affectation de liens radio (CELAR), aléatoires avec structures (GRAPH) et purement alétoires. De ces expérimentations, il ressort que le critère d’H-Quality est pertinent pour guider les heuristiques de choix de valeur, et intéressant pour les heuristiques de choix de variable sur les instances à forte connectivité et forte densité. Les heuristiques de choix de voisinage augmentant le degré de liberté des variables et tenant compte des coûts des contraintes offrent de meilleurs résultatsWeighted Constraint Satisfaction Problem (WCSP) which are a generalization to the optimization of CSP, are usually solved by tree search methods combined with filtering algorithms or local search methods. Although many generic heuristics have been proposed for such methods in the CSP framework, this is not the case for WCSP yet. Our objective was to define and implement new generic heuristics dedicated to WCSP in order to efficiently guide search methods. For tree search methods, we have proposed several value ordering and variable ordering heuristics based on a global criterion, the H-Quality, which is less dependent on filtering mechanisms. For VNS based metaheuristics, we have proposed new neighborhood heuristics based on the concept of degree of freedom wich depend on the topology of graph of constraints. Then, we have proposed to extend them to the WCSP framework in order to take into account cost of constraints. In order to validate our contribution, we have made experiments on real-world problems (Radio Link Frequency Assignment Problem) (CELAR), random structured instances (GRAPH) and random instances. From these experiments, it appears that the concept of H-Quality is a relevant criterion to guide value ordering heuristics and interesting to guide variable ordering heuristics for high connectivity and high density instances. Neighborhood heuristics based degree of freedom and taking into account cost constraints offer better performance
18
Bärecke, Thomas. "Isomorphisme Inexact de Graphes par Optimisation Évolutionnaire." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2009. http://tel.archives-ouvertes.fr/tel-00494519.
Full textAbstract:
L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.
19
Batnini, Heikel. "Contraintes globales et heuristiques de recherche pour les CSPs continus." Phd thesis, Université de Nice Sophia-Antipolis, 2005. http://tel.archives-ouvertes.fr/tel-00091375.
Full textAbstract:
Les systèmes de contraintes de distance euclidienne apparaissent dans de nombreux domaines d'applications, comme en robotique, en biochimiemoléculaire ou en CAO. Les techniques issues de la programmation par contraintes permettent de résoudre ces problèmes en combinant une technique de bissection avec des méthodes de réduction des domaines (consistances locales ou partielles). Or, ces consistances sont des méthodes systématiques qui ne prennent pas en compte les propriétés spécifiques des contraintes.
Nous présentons dans cette thèse deux approches pour la conception d'une contrainte globale pour la résolution de systèmes de contraintes de distance. La première approche est basée sur l'inférence de contraintes
redondantes directement issues de propriétés géométriques du système.
La deuxième approche est basée sur l'introduction d'un algorithme de filtrage global dédié aux systèmes d'équations de distance.
Ces travaux ont débouché sur la conception d'une
technique de décomposition de domaines qui exploite la structure particulière des contraintes de distance. Enfin, nous présentons une généralisation de cette heuristique de recherche à des contraintes numériques quelconques.
20
Veerapen, Nadarajen. "Contrôle autonome d'opérateurs pour la recherche locale." Phd thesis, Université d'Angers, 2012. http://tel.archives-ouvertes.fr/tel-00995607.
Full textAbstract:
Au fil des années, un nombre croissant de méthodes de résolution ont été proposées afin de traiter des problèmes plus grands et plus complexes. Parmi ces méthodes, les métaheuristiques sont largement utilisées dans le monde académique et industriel afin de résoudre efficacement des problèmes d'optimisation et de satisfaction de contraintes. Toutefois la conception de métaheuristiques de plus en plus performantes produit souvent des systèmes fortement complexes dont l'utilisation demande une expertise non négligeable aussi bien du problème lui-même que de la façon de paramétrer la méthode de résolution. Concevoir des algorithmes de recherche autonomes est donc une question importante. Cette thèse traite du problème de la gestion et de la sélection d'opérateurs dans le contexte de la recherche locale, au sein d'un contrôleur générique. Celui a pour but de pouvoir être réutilisé facilement pour traiter différents problèmes. Nous nous attachons donc à concevoir des méthodes simples et robustes. La sélection des opérateurs se base sur un apprentissage des performances antérieures de chaque opérateur afin de déterminer les opérateurs vraisemblablement les plus bénéfiques à chaque pas de la recherche. Pour effectuer ces choix, le contrôleur se base sur la capacité des opérateurs à améliorer la qualité des solutions ainsi que sur la faculté de produire des solutions qui diffèrent de celles déjà obtenues. Les méthodes proposées sont testées sur différents problèmes théoriques et pratiques d'optimisation combinatoire et de satisfaction de contraintes. Les résultats obtenus montrent qu'il est possible d'obtenir des résultats corrects avec des méthodes simples. Les mécanismes adaptatifs proposés se révèlent robustes sur différents problèmes.
21
Févrot, Olivier. "Recherche sur la notion de démocratie locale." Paris 2, 2003. http://www.theses.fr/2003PA020067.
Full text
22
Masingue, Antoine. "Recherche-intervention en management et team building : apports d'outils heuristiques et transformatifs." Paris 2, 2008. http://www.theses.fr/2008PA020065.
Full textAbstract:
La recherche-intervention en management a une triple finalité : transformer (répondre à une demande managériale à visée transformative), découvrir et comprendre (produire des connaissances). Cette triple finalité est elle-même au service d’un dessein cardinal : améliorer la performance du management de l’organisation étudiée. Le team building désigne l’ensemble des actions visant à agir sur les processus permettant de produire de la cohésion au sein d’une équipe. Cette recherche vise à proposer, et à articuler de façon cohérente sur le plan épistémologique, un ensemble d’outils susceptibles d’aider le chercheur-intervenant en management confronté à une problématique de team building. L’instrumentation proposée (et centrée sur l’usage conjoint de l’inventaire typologique de développement de Golden, de l’approche communicationnelle et systémique de l’école de Palo Alto, du méta-modèle linguistique, des principes de décodages des schémas cognitifs de Robert Dilts et des drivers de Taïbi Kahler) est évaluée tant au regard de la théorie que de la pratique, au travers d’une étude de cas portant sur plusieurs équipes de marketing direct d’un grand groupe international de V. A. D. Coté au C. A. C. 40. Les résultats sont fructueux et font l’objet d’une discussion critique. Ils font apparaître le caractère fondamental et premier, dans une démarche de team building, de la « qualité » de la relation managériale, déjà souligné par THEVENET (2000) dans ses recherches sur l’implication au travail.
23
Devarenne, Isabelle. "Etudes en recherche locale adaptative pour l'optimisation combinatoire." Besançon, 2007. http://www.theses.fr/2007BESA2012.
Full textAbstract:
Toutes les méthodes d'optimisation ont des paramètres internes qui prennent une part prépondérante dans leurs performances. La difficulté pour les utilisateurs est de trouver un bon réglage pour chaque problème. Depuis quelques années une part importante de la recherche en optimisation combinatoire porte sur la conception de méthodes adaptives. L'objectif de cette démarche est de définir les procédés qui tentent d'adapter dynamiquement le paramétrage des méthodes en fonction du problème. Dans ce contexte, cette thèse porte sur les mécanismes de mémoire et d'adaptation dans le but de mettre au point une méthode de Recherche Locale Adapative (RLA) combinant des mécanismes d'extension et de restriction du voisinage. L'extension du voisinage est définie par une procédure de détection de blocage de la recherche en étudiant l'historique des choix effectués par la méthode afin d'intervenir sur son comportement. Le mécanisme de restriction quant à lui est basé sur l'utilisation d'une liste Tabou à paramétrage adaptatif pour gérer l'accès aux variables. La méthode ainsi obtenue a été appliquée à deux problèmes : un problème académique, la k-coloration de graphes, et un problème réel, l'affectation de fréquences en réseaux de radiocommunications. Plusieurs variantes de RLA ont élé développées et comparées à des résultats publics sur les deux problèmesAll optimization methods have internal parameters that influenced their performance. The challenge for users is to find a good adjustment for each problem. In recent years an important part of research in combinatorial optimization focuses on the conception of adaptive methods. The objective of the approach is to define processes that attempt to adapt dynamically parameters of methods according to each problem. In this context, this thesis focuses on the mechanisms of memory and adaptation in order to develop an Adaptative Local Search (ALS) method combining mechanisms of extension and restriction of the neighborhood. The neighborhood extension is defined as a procedure which detect blockage during the search by studying the historic of the choices made by the method in order to intervene on his behavior. The restriction mechanism is based on the use of an adaptative tabu list to manage access to the variables. The resulting method has been applied to two problems: an academic problem, graph k-coloring problem, and a real problem, the frequency allocation in radio networks. Several variants of ALS were developed and compared to public results on the two issues
24
Cherkaoui, Sidi Rachid. "Méthodes heuristiques pour la recherche de configurations optimales d'un réseau électrique de distribution /." [S.l.] : [s.n.], 1992. http://library.epfl.ch/theses/?nr=1058.
Full text
25
Hail, Nourredine. "Méthodes algorithmiques pour les lignes de production avec des machines parallèles." Université Joseph Fourier (Grenoble), 1995. http://www.theses.fr/1995GRE10019.
Full textAbstract:
Cette thèse présente un problème d'ordonnancement sur une ligne de production flexible. Dans une telle ligne, les postes de travail sont disposes séquentiellement, et chacun d'eux contient un certain nombre de machines parallèles identiques. Les pièces passent de poste en poste selon le même ordre et sont usinées par une des machines de chaque poste. Nos travaux portent sur l'étude de la minimisation de la date d'achèvement de la dernière pièce sur le dernier poste (makespan). Ce problème est np-difficile au sens fort. Nous étudions d'abord l'intérêt de ce type de ligne notamment en ce qui concerne la flexibilité, ensuite un état de l'art de ce domaine est présenté. Puis nous entamerons l'étude du flow shop flexible. Dans une première partie, nous proposons une borne inferieure pour le problème d'affectation (réduction à un seul poste). Ensuite nous développerons une heuristique pour ce cas particulier, en utilisant les algorithmes génétiques. Dans une seconde partie, nous présentons une heuristique pour un cas particulier du flow shop flexible à deux postes, puis on fera une étude théorique de sa performance. Nous proposons à la fin de cette thèse trois heuristiques pour le flow shop flexible, en utilisant trois méthodes différentes: l'amélioration locale, la méthode tabou et les algorithmes génétiques
26
Ytier, David. "Recherche sur la fiscalité locale au prisme de l’égalité." Electronic Thesis or Diss., Aix-Marseille, 2019. https://buadistant.univ-angers.fr/login?url=https://bibliotheque.lefebvre-dalloz.fr/secure/isbn/9782247210268.
Full textAbstract:
Étudier la fiscalité locale au prisme de l’égalité, c’est observer deux notions juridiques reliées ensemble dans un système complexe qui révèle tout à la fois l’antinomie et la conciliation qui les unissent. L’intérêt du sujet surgit au constat des critiques subies par un système d’impositions considéré comme vecteur d’injustices majeures, et de la radicalité des solutions qui conduit à un certain déclin de la fiscalité locale. Dès lors, il convient de corréler les deux notions pour déterminer le rapport qu’elles entretiennent. La problématique s’inscrit là dans un vaste champ de réflexion qui entoure plus largement la mise en œuvre d’une décentralisation dont l’organisation entraîne mécaniquement des ruptures de l’égalité, de surcroît lorsqu’une autonomie financière est consentie aux organes décentralisés. En ce sens, la recherche nécessite, au-delà d’une vision historique permettant de relativiser les inégalités actuelles, de procéder à une conceptualisation de la notion de fiscalité locale. Celle-ci permet de comprendre l’antinomie qui oppose les deux notions, mais également d’imposer une conciliation qui s’opère entre elles. En effet, la fiscalité locale doit poursuivre l’objectif d’égalité. Le législateur met en œuvre cette conciliation par la conception technique de l’impôt ainsi qu’à travers le cadre territorial dans lequel l’impôt local se développe. Ce n’est qu’au prix de cette double conciliation que la fiscalité locale peut s’inscrire dans une démarche globalement égalitaireTaking a look at local taxation through equality means observing two legal notions linked to one another, in a complex system that reveals what sets them apart, and what brings them together. The interest of the subject stems from the criticism of a taxation system considered as a vector of major inequalities, and the radical solutions that lead to a decline in local taxation. As such, it is necessary to link the two concepts to determine their relation. This problem is part of broader study that more generally addresses the implementation of government decentralization, whose organization inevitably leads to inequalities, especially when decentralized authorities are given financial autonomy. This is why this research not only looks back on our past in order to take some perspective on the current inequalities, but also aims at conceptualizing the notion of local taxation. This allows us to understand why those two notions are polarised, as well as striking the right balance between them. The objective of local taxation should be equality. Lawmakers find this balance though the conception of taxation itself, and through the local framework where the local tax is developed. This balance must be found if we want local taxation to fully meet equality
27
Porumbel, Daniel Cosmin. "Algorithmes Heuristiques et Techniques d'Apprentissage - Applications au Probleme de Coloration de Graphe." Phd thesis, Université d'Angers, 2009. http://tel.archives-ouvertes.fr/tel-00481253.
Full textAbstract:
Au cours des trois dernieres decennies, les algorithmes heuristiques ont permis de realiser des progres remarquables dans la resolution des problemes diciles d'optimisation combinatoire. Cependant, la conception de ces algorithmes releve encore plusieurs challenges importants { en particulier, il semble qu'il est toujours dicile d'integrer dans une heuristique une vue d'ensemble sur l'evolution de la recherche ou sur sa trajectoire. Prenant comme cadre experimental le probleme bien connu de la coloration de graphe, nous presentons de nouvelles strategies qui font appel a certains mecanismes d'apprentissage pour rendre le processus de recherche plus \auto-conscient". Nous introduisons un algorithme qui est capable d'enregistrer sa trajectoire et d'interpreter sa propre evolution. Une analyse de l'espace de recherche a montre que les meilleures congurations visitees sont relativement proches les unes des autres, regroupees dans des spheres de rayon xe. Avec ce type d'informations apprises, nous avons concu : (i) des algorithmes de diversication qui \prennent garde" a ne pas visiter la m^eme sphere a plusieurs reprises, (ii) des algorithmes d'intensication qui se focalisent sur l'exploration d'un perimetre limite en utilisant un parcours en largeur des spheres de ce perimetre, et (iii) des approches evolutionnistes pour gerer la diversite de sorte que les individus soient a la fois de bonne qualite eu egard a la fonction objectif et susamment distants les uns des autres. En fait, nous presentons une gamme de techniques (e.g. nouvelles fonctions d'evaluation) qui peuvent rendre la recherche heuristique \bien informee".
28
Al-Douri, Thekra. "Méthodes heuristiques pour les problèmes de type knapsack." Thesis, Amiens, 2018. http://www.theses.fr/2018AMIE0023/document.
Full textAbstract:
Les travaux de recherche de cette thèse s'articulent autour de la résolution du problème du sac à dos en min-max avec de multiples scénarios (en anglais, max-min knapsack problem with multi-scenarios). Cette thèse propose trois approches, plutôt complémentaires, en s'appuyant principalement sur l'aspect perturbation des solutions puis la reconstruction. En partant de ce principe, trois algorithmes approchés ont été étudiés, en partant d'une approche mono-solution vers des approches à base de population. Dans une première partie, un algorithme réactif a été proposé ; il s'appuie sur deux phases imbriquées dans une recherche itérative : la phase de restauration / exploration et la phase de perturbation. La première phase part d'une solution réalisable et tente de l'améliorer en utilisant une stratégie d'exploration spécifique. Cette dernière est basée sur une série d'échanges entre les éléments appartenant ou pas à la solution courante. La deuxième phase commence par construire une solution partielle, en supprimant certains éléments de la solution courante, alors qu'une stratégie de ré-optimisation tente de sélectionner de nouveaux éléments et de les inclure dans une solution dégradée. La stratégie de destruction tente également de diversifier le processus de recherche en dégradant la qualité des solutions dans le but d'éviter des stagnations locales. Dans une deuxième partie, une méthode à base de population a été proposée. Elle s'appuie sur trois phases. Une phase de construction de la population de départ par application d'un algorithme glouton aléatoire, une deuxième phase qui combine une série de solutions deux-à -deux, par l'utilisation de l'opérateur d'intersection et, une troisième phase qui agit sur les successeurs afin d'augmenter la qualité des solutions induites. Les deux dernières phases sont répétées jusqu'à la stabilité de la population. Dans une troisième partie, le problème est résolu en combinant le GRASP (Greedy Randomized Adaptive Search Procedure) et le Path-relinking. Cette approche combine deux stratégies: une stratégie de construction et une autre d'amélioration. D'une part, la première stratégie produit une solution (de départ) réalisable en appliquant le GRASP. D'autre part, chaque solution courante (de départ) est améliorée en appliquant une stratégie basée sur le path-relinking : partir d’un couple de solutions « départ-arrivée », puis tenter de reconstruire le lien entre ces deux solutions en espérant rencontrer des solutions de meilleures qualités sur le chemin. Ce processus est répété sur une série de solutionsThe aim of this thesis is to propose approximate algorithms for tackling the max-min Multi-Scenarios Knapsack Problem (MSKP). Three methods have been proposed (which can be considered as complementary), where each of them is based on the perturbation aspect of the solutions and their re-buildings. The proposed methods are declined in three parts. In the first part, we propose to solve the MSKP by using a hybrid reactive search algorithm that uses two main features: (i) the restoring/exploring phase and (ii) the perturbation phase. The first phase yields a feasible solution and tries to improve it by using an intensification search. The second phase can be viewed as a diversification search in which a series of subspaces are investigated in order to make a quick convergence to a global optimum. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature, whereby its obtained results are compared to those reached by recent methods available in the literature. The results show that the method is competitive and it is able to provide better solutions. The second part discusses a population-based method which combines three complementary stages: (i) the building stage, (ii) the combination stage and (iii) the two-stage rebuild stage. First, the building stage serves to provide a starting feasible solution by using a greedy procedure; each item is randomly chosen for reaching a starting population of solutions. Second, the combination stage tries to provide each new solution by combining subsets of (starting) solutions. Third, the rebuild stage tries to make an intensification in order to improve the solutions at hand. The proposed method is evaluated on a set of benchmark instances taken from the literature, where its obtained results are compared to those reached by the best algorithms available in the literature. The results show that the proposed method provides better solutions than those already published. In the third part, both greedy randomized adaptive search procedure and path-relinking are combined for tackling the MSKP. The proposed method iterates both building and improvement phases that are based upon an extended search process. The first phase yields a (starting) feasible solution for the problem by applying a greedy randomized search procedure. The second phase tries to enhance each current solution by applying the path-relinking based strategy. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature. The obtained results are compared to those reached by some best algorithms available in the literature. Encouraging results have been obtained
29
Porumbel, Daniel Cosmin. "Algorithmes Heuristiques et Techniques d'Apprentissage : Applications au Problème de Coloration de Graphe." Phd thesis, Université d'Angers, 2009. http://tel.archives-ouvertes.fr/tel-00476541.
Full textAbstract:
Au cours des trois dernières décennies, les algorithmes heuristiques ont permis de réaliser des progrès remarquables dans la résolution des problèmes difficiles d'optimisation combinatoire. Cependant, la conception de ces algorithmes relève encore plusieurs challenges importants - en particulier, il semble qu'il est toujours difficile d'intégrer dans une heuristique une vue d'ensemble sur l'évolution de la recherche ou sur sa trajectoire. Prenant comme cadre expérimental le problème bien connu de la coloration de graphe, nous présentons de nouvelles stratégies qui font appel à certains mécanismes d'apprentissage pour rendre le processus de recherche plus "auto-conscient". Nous introduisons un algorithme qui est capable d'enregistrer sa trajectoire et d'interpréter sa propre évolution. Une analyse de l'espace de recherche a montré que les meilleures configurations visitées sont relativement proches les unes des autres, regroupées dans des sphères de rayon fixe. Avec ce type d'informations apprises, nous avons conçu : (i) des algorithmes de diversification qui "prennent garde" à ne pas visiter la même sphère à plusieurs reprises, (ii) des algorithmes d'intensification qui se focalisent sur l'exploration d'un périmètre limité en utilisant un parcours en largeur des sphères de ce périmètre, et (iii) des approches évolutionnistes pour gérer la diversité de sorte que les individus soient à la fois de bonne qualité eu égard à la fonction objectif et suffisamment distants les uns des autres. En fait, nous présentons une gamme de techniques (e.g. nouvelles fonctions d'évaluation) qui peuvent rendre la recherche heuristique "bien informée".
30
Durand, Guy. "Recherche sur la nature de la société d'économie mixte locale." Montpellier 1, 1994. http://www.theses.fr/1994MON10026.
Full textAbstract:
La societe d'economie mixte locale connait un engouement pratique tres important, particulierement depuis la loi du 7 juillet 1983 adoptee a l'unanimite de la representation nationale dans le sillage des lois de decentralisation. Paradoxalement sa nature reste encore largement dans l'ombre comme si les chercheurs cosideraient que le legislateur en l'integrant dans la categorite juridique de la societe anonyme avait ferme la porte a cette analyse theorique. La seml est expressement dotee d'une personnalite privee qui resulte de sa forme commerciale. Cette personnalite privee est neanmoins incapable de resumer la seml et il faut rechercher quelle est la structure intime de cette personnalite. C'est l'ambivalence qui caracterise sa nature juridique car elle est constituee comme une corporation privee mais elle vit et fonctionne a l'image d'une fondation publique. Cette mixite juridique s'accompagne d'une mission clairement economique dont la finalite est le developpement local. Traditionnellement l'entreprise publique emprunte une forme privee ou une forme publique a travers la societe ou l'etablissement public industriel et commercial. Elle se prive ainsi d'une identite propre pour se contenter d'une identite en negatif. L'evolution de la societe d'economie mixte locale prefigure ce que pourrait etre la categorie juridique de l'entreprise publique localeThe company of mixed public and private ownership (cmpp) has acheived a major success, particularly since the uninimous passage of the low of 7th july 1983 in the continuing move towards decentralisation. Paradorically its true nature remains largely unknown, as if the scholars thought that the legislator, in the process of including this entiry in the juridical category of a ltd company, had closed the door on any theoretical analysis. The cmpp is expressely included in the category ltd company because of its commercial aspelct. This categorisation is however incapable of characteresing the cmpp and a closer examination of the entitys structure is requited. Ambivalence is the term which caracterises the legal status of the cmpp since its constitution is similar to a ltd company, but it functions like a public foundation. The mixed nature of this legal entity must accomodate clear commercial aims alongside the target of local infrastructural development. Traditionally the public company (ltd company) takes the form of either public or private because of its state or local government or its purely commercial aims. In this way the company deprives itself of a posotive identity in favour of one that emprhasises what it is not. The evolution of the cmpp anticipates what could become the new legal category of the local authority public company
31
Boulanger, Célia. "Heuristiques basées sur la programmation mathématique pour des problèmes de localisation et de routage." Valenciennes, 2010. http://ged.univ-valenciennes.fr/nuxeo/site/esupversions/097f03a9-5364-4c57-afd3-697ff1edf975.
Full textAbstract:
Les travaux de cette thèse portent sur la définition et la résolution de deux problèmes de transport dans le domaine de la recherche opérationnelle. Ces deux problèmes entrent dans le cadre des problèmes de tournées de véhicules et des problèmes de localisation. Le premier problème abordé est le problème de localisation et routage avec contraintes de capacités aux dépôts. Trois méthodes de résolution sont proposées pour résoudre ce problème. Les deux premières sont des heuristiques hybrides, combinant programmes linéaires et une recherche tabou. La troisième méthode est également une méthode approchée, elle est basée sur une approche par génération de colonnes. Ces trois contributions ont ensuite été implémentées afin de tester leur efficacité. Les résultats obtenus sont de bonne qualité, la meilleure méthode implémentée améliorant la majorité des trente instances testées. Le second problème abordé est un problème de voyageur de commerce bi-objectif adapté à un graphe particulier où seuls certains des sommets sont à visiter obligatoirement. Une méthode approchée a été développée pour résoudre ce problème bi-objectif. Afin d’évaluer les qualités des solutions obtenues par cette méthode, une méthode exacte a également été développéeThe aim of this PHD is the modelisation of two transportation problems of operationnal research. . These problems are routing problem and location problem. The first one studied is the location-routing problem with capacity constraints on facilities. Three methods are proposed to solve this problem. The two first are hybrid heuristics, mixing linear programs and a tabou search. The third method is based on a column generation method. These three contributions have been developped and tested to see their efficienty. We obtain good results, the best method giving most of the best results of the thirty instances. The second problem studied is a biobjectif travelling salesman problem on a particular graphe where some vertices have to be visited. A heuristic has been developed to solve this biobjective problem. To evaluate results obtained, an exacte method has been developed too
32
Khemakhem, Mahdi. "Heuristiques pour un Problème de m-Tournées Sélectives." Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2008. http://tel.archives-ouvertes.fr/tel-00440494.
Full textAbstract:
Cette thèse aborde un problème de transport appelé le Problème de m-Tournées Sélectives (PmTS) ou ”Team Orienteering Problem” en anglais. Le PmTS consiste à construire m tournées pour une flotte de véhicules afin de desservir un sous-ensemble sélectionné de clients. Dans le PmTS un service est fourni à chaque client visité en contrepartie de quoi, un gain est récolté. La tournée de chaque véhicule part d'un dépôt, passe par un sous-ensemble de clients et revient en un autre sans dépasser la longueur maximale autorisée. Chaque client peut être desservi au plus une fois par un unique véhicule. L'objectif est de maximiser le gain total récolté. Le PmTS étant un problème NP-difficile, notre objectif de recherche a consisté à proposer des heuristiques basées sur le principe général de ”Cluster first - Route second”. Ces algorithmes sont prévus pour être intégrés dans un logiciel de planification des tournées de techniciens de maintenance.
33
Gómez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions." Angers, 2010. http://www.theses.fr/2010ANGE0022.
Full textAbstract:
Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine. . . ). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i. E. N'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégiesPacking problems are usually NP-hard, or NP-complete according to the objective. One has to locate a set of objects into one or more “container(s)”, with fix dimensions or of infinite height, while respecting constraints related to some characteristics (weight, quantity, rotation, stability, guillotine cuts. . . ). Themain interest of these problems are the numerous practical applications from various domains. The most effective solution strategies for these problems are usually approximate methods, local search in particular. In this thesis, we are interested in a particular two-dimensional packing problem (without rotation nor guillotine cuts) known as “strip packing” (SPP). The objective of this problem, after locating rectangular objects without overlap, is to minimize the height of the resulting packing. We developed two “meta-heuristic” approaches for the SPP, both including innovative components based on problem knowledge. The first one is a genetic algorithm with a new (highly “visual”) crossover and a hierarchical fitness function. The second one is a tabu search with “direct” representation (i. E. Not using the classical permutations) whose main characteristics are a consistent neighborhood, a “well-informed” diversification (based on the search history), and a fitness function able to evaluate possibly partial solutions. The two proposed approaches, assessed on a well-known and very difficult benchmark, show good performances compared with other strategies
34
Grand, Florence. "Recherche sur la coopération entre les communes et les départements." Renne 1, 1997. http://www.theses.fr/1997REN1A001.
Full text
35
Doat, Mathieu Mazères Jean-Arnaud. "Recherche sur la notion de collectivité locale en droit administratif français /." Paris : LGDJ, 2003. http://catalogue.bnf.fr/ark:/12148/cb38985552h.
Full text
36
Jeanjean, Antoine. "Recherche locale pour l'optimisation en variables mixtes : méthodologie et applications industrielles." Phd thesis, Ecole Polytechnique X, 2011. http://pastel.archives-ouvertes.fr/pastel-00670147.
Full textAbstract:
Les problèmes d'optimisation en variables mixtes sont souvent résolus par décomposition quand ils sont de grande taille, avec quelques inconvénients : difficultés de garantir la qualité voire l'admissibilité des solutions et complexité technique des projets de développement. Dans cette thèse, nous proposons une approche directe, en utilisant la recherche locale, pour résoudre des problèmes d'optimisation mixte. Notre méthodologie se concentre sur deux points : un vaste ensemble de mouvements et une évaluation incrémentale basée sur des algorithmes approximatifs, travaillant simultanément sur les dimensions combinatoire et continue. Tout d'abord, nous présentons un problème d'optimisation des stocks de banches sur chantiers. Ensuite, nous appliquons cette technique pour optimiser l'ordonnancement des mouvements de terre pour le terrassement d'autoroutes et de voies ferrées. En n, nous discutons d'un problème de routage de véhicules avec gestion des stocks. Les coûts logistiques sont optimisés pour livrer un produit fluide par camion dans des zones géographiques d'une centaine de clients, avec la gestion de l'inventaire con ée au fournisseur.
37
Jeanjean, Antoine. "Recherche locale pour l'optimisation en variables mixtes : méthodologie et applications industrielles." Phd thesis, Palaiseau, Ecole polytechnique, 2011. https://pastel.hal.science/docs/00/67/01/47/PDF/these_antoine_jeanjean_bouygues_elab_lix.pdf.
Full textAbstract:
Les problèmes d'optimisation en variables mixtes sont souvent résolus par décomposition quand ils sont de grande taille, avec quelques inconvénients : difficultés de garantir la qualité voire l'admissibilité des solutions et complexité technique des projets de développement. Dans cette thèse, nous proposons une approche directe, en utilisant la recherche locale, pour résoudre des problèmes d'optimisation mixte. Notre méthodologie se concentre sur deux points : un vaste ensemble de mouvements et une évaluation incrémentale basée sur des algorithmes approximatifs, travaillant simultanément sur les dimensions combinatoire et continue. Tout d'abord, nous présentons un problème d'optimisation des stocks de banches sur chantiers. Ensuite, nous appliquons cette technique pour optimiser l'ordonnancement des mouvements de terre pour le terrassement d'autoroutes et de voies ferrées. En n, nous discutons d'un problème de routage de véhicules avec gestion des stocks. Les coûts logistiques sont optimisés pour livrer un produit fluide par camion dans des zones géographiques d'une centaine de clients, avec la gestion de l'inventaire con ée au fournisseurLarge mixed-variable optimization problems are often solved by decomposition, with some drawbacks : di culties to guarantee quality or even feasible solutions and technical complexity of development projects. In this thesis, we propose a direct approach, using local search, for solving mixed-variable optimization problems. Our methodology focuses on two points : a large pool of varied moves and an incremental evaluation based on approximate but highly e cient algorithms, working on combinatorial and continuous dimensions simultaneously. First, we present a formwork stocks optimization problem on construction sites. Then, we rely on this methodology to optimize earthworks scheduling for highway and railway projects. Finally, we solve a vehicle routing problem with inventory management. Inventory routing refers to the optimization of transportation costs for the replenishment of customers' inventories : based on consumption forecasts, the vendor organizes delivery routes
38
Gomez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions." Phd thesis, Université d'Angers, 2010. http://tel.archives-ouvertes.fr/tel-00575859.
Full textAbstract:
Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.
39
Dorne, Raphae͏̈l. "Etude des méthodes heuristiques pour la coloration, la T-coloration et l'affectation des séquences." Montpellier 2, 1998. http://www.theses.fr/1998MON20081.
Full textAbstract:
Les methodes heuristiques sont une classe generale de methodes qui, de maniere schematique, utilisent des criteres empiriques au cours de leur resolution pour fournir, en un temps raisonnable, des solutions sous-optimales de bonne qualite. Ces methodes posent des problemes de conception et de mise au point pour lesquels, a l'heure actuelle, aucune methodologie n'a ete clairement definie. Le premier objectif de notre travail consiste donc a repondre, meme de maniere partielle, a ces problemes. Pour cela, nous avons defini une architecture et une methodologie adaptees a la conception et a l'analyse des methodes heuristiques. Pour valider notre approche, nous avons applique cette methodologie et cette architecture sur une famille de problemes np-complet : la coloration et la t-coloration, et sur une application reelle : l'affectation de frequences dans les reseaux radio-mobiles. Des methodes de recherche locale, evolutives et hybrides ont ete developpees pour chacun de ces problemes et testees sur de nombreux jeux de tests references (> 150 benchmarks) comprenant jusqu'a 2000 variables et plus de quatre millions de contraintes. Au niveau des performances, nos algorithmes rejoignent les meilleurs resultats connus sur ces problemes. En particulier pour la coloration de graphes, nous obtenons, grace a un croisement adapte, les meilleurs resultats actuels sur certaines instances aleatoires. De meme, les resultats obtenus dans le cadre de l'affectation de frequences ont ete integres au progiciel actuellement en exploitation a france telecom. Il s'en suit que la qualite de l'ensemble des resultats obtenus dans cette etude confirme l'interet de notre approche pour la conception de methodes heuristiques.
40
Sbihi, Abdelkader. "Les Méthodes Hybrides en Optimisation Combinatoire :Algorithmes Exacts et Heuristiques." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2003. http://tel.archives-ouvertes.fr/tel-00012188.
Full textAbstract:
La thèse se situe dans le domaine de l'optimisation combinatoire, en particulier celui de lamodélisation et de la résolution algorithmique. Dans cette thèse, nous étudions deux variantes
NP-difficiles de problèmes de type sac-à-dos. Plus précisément, nous traitons le problème de
la distribution équitable (le Knapsack Sharing Problem : KSP) et le problème du sac-à-dos
généralisé à choix multiple (le Multiple-choice Multidimensional Knapasck Problem : MMKP).
Dans la première partie de cette thèse, nous nous intéressons au développement d'algorithmes
approchés pour les deux variantes évoquées du problème de type sac-à-dos. La deuxième partie
traite essentiellement de la résolution exacte du problème du sac-à-dos généralisé à choix multiple.
L'approche exacte que nous proposons est de type séparation et évaluation s'appuyant
principalement sur : (i) le calcul des bornes inférieure et supérieure et (ii) l'utilisation de la
stratégie par le meilleur d'abord en développant des branches à double noeuds fils et frère.
La première partie porte sur l'étude et la résolution approchée des deux problèmes KSP et
MMKP. Concernant le problème de la distribution équitable, nous proposons dans un premier
temps, une première version de l'algorithme exploitant certaines caractéristiques de la
recherche tabou. Dans un deuxième temps, nous développons une deuxième version de l'algorithme dont l'idée principale consiste à tenter de combiner l'intensification de la recherche dans l'espace des solutions et la diversification de la solution obtenue. Nous soulignons la rapidité
de la première version et l'efficacité de la deuxième. Ensuite nous nous intéressons au problème
de sac-à-dos généralisé à choix multiple. Nous proposons deux heuristiques de recherche locale
itérative. Le premier algorithme s'appuie sur une “recherche guidée”. Le deuxième algorithme
est une recherche locale que nous appelons réactive avec stratégies de déblocage et de dégradtion améliorantes de la solution et basées sur l'inter-change local.
Dans la deuxième partie de cette thèse, nous proposons une méthode de résolution exacte de type séparation et évaluation pour le problème du sac-à-dos généralisé à choix multiple. D'une part, nous nous proposons la réduction du problème initial au problème auxiliaire MMKPaux qui n'est autre que le problème de sac-à-dos à choix multiple MCKP. Nous calculons une borne supérieure pour le MMKPaux et nous établissons le résultat théorique pour lequel une borne supérieure pour le MMKPaux est une borne supérieure pour le MMKP. D'autre part, nous proposons le calcul d'une borne supérieure ainsi qu'une borne inférieure de départ pour le problème étudié qui sont nécessaires pour la réduction de l'espace de recherche. L'étude expérimentale montre l'efficacité de la méthode proposée sur différents groupes d'instances de petite et moyenne taille.
Nous expliquons enfin pourquoi cet algorithme exact atteint ses limites de résolution, dˆues
principalement à la complexité intrinsèque du modèle étudié. D'autant la résolution dépend de
la taille et la densité des instances traitées.
41
Bailleux, Olivier. "Contribution à l'étude des paysages de recherche locale associés au problème SAT." Dijon, 1996. http://www.theses.fr/1996DIJOS005.
Full textAbstract:
Dans cette thèse, nous abordons la problématique de la difficulté des instances de problèmes vis a vis de la recherche locale stochastique. Notre approche consiste à considérer qu'un processus de recherche locale stochastique est caractérisé par deux entités distinctes: d'une part un algorithme de recherche, d'autre part un paysage spécifique à l'instance de problème à traiter. Nous nous intéressons à une classe de paysages associés au problème de satisfaction d'une formule booléenne. La difficulté de ces paysages est liée à la présence d'extremums locaux. Notre contribution se situe à trois niveaux. En premier lieu, nous développons un outillage dédié à l'étude expérimentale des paysages. Cet outillage comprend un algorithme d'échantillonnage stratifié, permettant notamment d'effectuer des mesures de densité d'extremums locaux dans certaines régions critiques, et deux algorithmes pour le dénombrement approché des extremums globaux. Nous proposons également une méthode originale de production d'instances SAT atypiques en terme de difficulté de résolution, notamment avec l'approche locale stochastique, et en terme de nombre de solutions. Enfin, nous présentons quelques résultats expérimentaux visant à mettre en parallèle, pour un panel d'instances SAT, des données spécifiques aux paysages et des informations relatives au comportement des processus de recherche.
42
Boughaci, Dalila. "Recherche locale et méthodes évolutives pour les problèmes MAX-SAT et PDG." Aix-Marseille 1, 2008. http://www.theses.fr/2008AIX11064.
Full textAbstract:
Dans cette thèse, deux problèmes réputés NP-difficiles sont étudiés, à savoir : le problème de satisfiabilité maximale MAX-SAT et le problème de la détermination du gagnant dans les enchères combinatoires PDG. Notre but principal est de contribuer à la résolution de ces deux problèmes par des méthodes évolutives et de recherche locale. Nous proposons, tout d’abord, une nouvelle stratégie de sélection qui se base sur la diversité et la qualité pour choisir une collection d’individus qui vont participer à la phase de reproduction et donner une descendance. Ensuite, nous utilisons un opérateur de combinaison spécifique au problème à étudier pour générer de nouveaux enfants qui sont améliorés par une recherche locale stochastique (SLS). Dans le but de tester et de prouver l’efficacité de nos approches, une étude comparative avec quelques algorithmes de l’état de l’art concernant MAX-SAT et PDG est faite dans la thèse.
43
Bouchakhchoukha, Adel. "Modèles de résolution approchée et efficace pour les problèmes des réseaux de transport et de télécommunication." Thesis, Paris 1, 2015. http://www.theses.fr/2015PA010046.
Full textAbstract:
La capacité à gagner du temps et à diminuer ses efforts est l'une des qualités de l'être humain, qui a conduit à exercer la pensée depuis l'Antiquité jusqu'à ces dernières décennies, caractérisées par l'émergence du mélange entre la rapidité des calculs et la précision des résultats, et ce dans plusieurs domaines. Le problème des tournées de véhicules et ses extensions sont, pour les théoriciens de ces utilités, d'une réelle importance quant aux applications du monde réel. Des recherches récentes dans ce domaine ont permis des avancées significatives dans la formulation des problèmes ainsi que dans la conception et l'analyse d'algorithmes. Dans cette étude, nous nous intéressons au problème de la logistique. Notre attention se porte en particulier sur un cas des réseaux de télécommunication, 2ECON-NDPR, et sur la façon de créer des designs d'une manière intelligente pour assurer la vitalité et la durabilité de la circulation de l'information. En outre. Nous choisissons les variantes problème de tournées de véhicules avec fenêtres de temps et problème de tournées de véhicules sélectives des familles VRP et OP respectivement. C'est dans ce cadre que s'inscrit cette thèse. La conception des solutions pour ces problèmes fait appel à la technique de programmation approchée connue pour sa rapidité de calcul. Il s’agit de Beam-search et de la recherche locale à grand voisinage. Nous présentons tout d’abord une étude détaillée des dernières problématiques précitées ainsi que différents types de méthodes de résolutions. Puis, nous exposons une méthode de recherche locale à grand voisinage adaptée pour la conception de réseau de survie avec relais, une proposition d’un algorithme de résolution approchée à trois phases pour le CVRPTW et, enfin, une proposition d'un algorithme de résolution approchée hybride pour le TOPThe need to save time as well as minimize effort is part of the human condition and it has driven our though s from antiquity until these last few decades, now characterized by the emergence of a mix in all fields between rapidity of calculation and precision in the result. The vehicle routing problem and its extensions are an important field for theorists of these utilities for real-world applications. Recent research in the field has led to significant advantages in problem formulation and designing algorithm analyses. This study considers logistics problems. A particular locus was given to a certain case of telecommunications networks 2ECONNDPR, as well as the method of intelligently creating designs to ensure vitality and durability in information circulation. Furthermore, the study considered vehicle routing problems, with time windows and orienteering problems from the VRP and OP families, respectively. This is the framework for this thesis. Solutions to these problems use programming techniques known for their calculation speed, i .e ., Beam-search and very large-scale neighborhood searching. First, a detailed study is presented of these above mentioned problems, along with the various types or resolution methods. Next, a very large-scale neighborhood search method is presented, suited to the design of a survivable network with relay, a proposition for a three-stage heuristic for the capacitated vehicle routing problem with time windows and, finally, a proposition for a hybrid heuristic for the team orienteering problem
44
Duvivier, David. "Étude de l'hybridation des méta-heuristiques, application à un problème d'ordonnancement de type jobshop." Phd thesis, Université du Littoral Côte d'Opale, 2000. http://tel.archives-ouvertes.fr/tel-00008729.
Full textAbstract:
Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshopPlus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.
Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.
Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques.
Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.
45
Wilbaut, Christophe. "Heuristiques hybrides pour la résolution de problèmes en variables 0-1 mixtes." Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2006. http://tel.archives-ouvertes.fr/tel-00409493.
Full textAbstract:
Les problèmes d'optimisation en variables 0-1 mixtes permettent de modéliser de nombreux problèmes réels difficiles à résoudre. Cette thèse s'intéresse à la mise en oeuvre de méthodes de résolution hybrides pour obtenir des solutions de bonne qualité en des temps raisonnables pour ces problèmes. L'ensemble des algorithmes présentés dans cette thèse est testé sur le problème du sac-à-dos multidimensionnel. Il consiste à maximiser une fonction linéaire en respectant un ensemble de contraintes linéaires. Après une présentation de quelques concepts fondamentaux utilisés en recherche opérationnelle pour résoudre les problèmes d'optimisation, nous présentons dans le premier chapitre différents problèmes de la famille du sac-à-dos. Nous abordons dans le second chapitre un ensemble de méthodes efficaces existantes pour résoudre le problème du sac-à-dos multidimensionnel. Nous proposons dans le chapitre 3 une première méthode hybride qui combine la programmation dynamique et la recherche tabou au sein d'un processus dit d'intensification globale. Des concepts de réduction sont également intégrés dans la programmation dynamique de manière à essayer de réduire la taille du problème. La seconde approche décrite dans le chapitre 4 combine la recherche dispersée avec des éléments de la recherche tabou et des chemins reliants pour affiner la recherche. Une étude expérimentale est menée pour mesurer l'impact de différents composants de l'algorithme. Nous terminons dans le chapitre 5 par une méthode utilisant conjointement la relaxation en continu et la relaxation en nombres entiers mixtes pour résoudre efficacement les problèmes en variables 0-1. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes. La dernière approche permet d'améliorer quelques meilleures valeurs connues sur des instances existantes du problème du sac-à-dos multidimensionnel.
46
Chauvin, Sophie. "Visualisations heuristiques pour la recherche et l'exploration de données dynamiques : l'art informationnel en tant que révélateur de sens." Paris 8, 2005. http://www.theses.fr/2005PA083708.
Full textAbstract:
Malgré la performance des systèmes de recherche d'informations, la production documentaire électronique génère désorientation, surcharges cognitive et informationnelle. La visualisation et ses potentialités heuristiques offre des perspectives encourageantes quant à la capacité de synthétiser les résultats de recherche, de déceler une pertinence globale et d'amplifier la perception d'un domaine. Cependant, les préceptes de la communication visuelle, du design et de l'architecture d'information butent sur une problématique de taille : celle de la réception de l'information destinée à une multiplicité de profils d'usages et d'usagers. Cette thèse introduit les perspectives d'un art informationnel dans le cadre d'un processus de médiation sociale instrumentalisée visant à améliorer les dispositifs de recherche d'informations textuelles. Une expérimentation menée au sein de la bibliothèque universitaire de Paris 8 sur les données bibliographiques a alimenté la problématique de cette rechercheIn spite of the information retrieval systems performance, the electronic document production generate cognitive and information overload and disorientation. The heuristic potential of visualization gives encouraging perspectives on ability to synthesize research results, to reveal global relevance and to highlight disciplinary perception. However, precepts of visual communication and information design come up against the specific problematic of end-users perception and their multiple profiles in information use. This thesis introduce perspectives of information art as part of an instrumentalized social mediation process to improve textual retrieval system. An experiment developed within Paris 8 University library on bibliographical datas provided this research problematic
47
Chauvin, Sophie Balpe Jean-Pierre. "Visualisations heuristiques pour la recherche et l'exploration de données dynamiques l'art informationnel en tant que révélateur de sens /." Saint-Denis : Université de Paris VIII, 2006. http://www.bu.univ-paris8.fr/web/collections/theses/SChauvin2.pdf.
Full text
48
Louvel, Séverine. "La construction locale des laboratoires : approche ethnographique de dynamiques d'évolution de laboratoires académiques en France." Grenoble 2, 2005. http://www.theses.fr/2005GRE29019.
Full textAbstract:
Les laboratoires académiques sont au centre du système national de la recherche publique. Bien connus comme fabriques de la recherche grâce à la sociologie des sciences, leurs dynamiques concrètes comme organisations sont pourtant moins bien analysées. Les modalités de recrutement des chercheurs titulaires et contractuels, la définition des échanges avec les tutelles, les relations internes entre des acteurs ou des collectifs, restent par exemple mal connues. Cette thèse reformule alors deux hypothèses qui traversent les analyses existantes. Elle suggère d'une part que les logiques d'organisation des laboratoires ne se limitent pas à la division du travail et qu'elles ne se déduisent pas simplement de la production réalisée ; elle avance d'autre part que leurs évolutions ne s'orientent pas selon un schéma d'acquisition de ressources applicable à toutes les situations. Une longue enquête ethnographique dans quatre laboratoires académiques de sciences du vivant éprouve la pertinence de cette perspective. Le croisement de plusieurs matériaux (archives conservées au laboratoire, nombreux entretiens, observations de situations) a permis de reconstituer précisément les trajectoires et d'analyser les dynamiques actuelles. Ce travail fait apparaître que la configuration des ressources et des contraintes des contextes (scientifiques, institutionnels. . . ) ne détermine pas la construction des laboratoires. Celle-ci s'explique en grande partie par une activité locale de régulation, dans laquelle interviennent en particulier des projets collectifs, des choix d'organisation, des enjeux de pouvoir, des engagements acceptés entre les membres du laboratoire et vis-à-vis de l'extérieur.
49
Bekele, Araya-Yohannes. "L'utilisation des lasers de faible puissance en thérapie réflexe et en thérapie locale." [S.l.] : [s.n.], 2002. http://www.enssib.fr/bibliotheque/documents/dessride/rrbaraya.pdf.
Full text
50
Berrada, Mohamed. "Une approche variationnelle de l'inversion : de la recherche locale à la recherche globale par carte topologique : application en inversion géoacoustique." Paris 6, 2008. http://www.theses.fr/2008PA066016.
Full textAbstract:
La propagation acoustique dans la colonne d'eau peu profond et à basse fréquence dépend fortement des caractéristiques géoacoustiques du sous sol marin et de la colonne d'eau. Il s'agit dans cette thèse d'élaborer un modèle d'inversion variationnelle des données géoacoustiques permettant de retrouver ces caractéristiques d'une manière précise. Les méthodes d'inversion variationnelles consistent à introduire des fonctions coûts qui mesure le degré d'adaptation entre les observations et leurs équivalentes modèle. Notre modèle d'inversion est basé sur deux approches: une approche modulaire du calcul de l'adjoint du modèle de propagation direct, nécessaire pour calculer le gradient des fonctions coûts, et une approche neuronale, ou plus particulièrement les cartes topologiques, permettant une recherche aussi globale que locale. Nous étudions d'abord l'approche modulaire que nous allons appliquer en inversion géoacoustique sur des données synthétiques, puis une validation dans le cadre d'une expérience avec des données réelles sera présentée. Nous présentons ensuite une méthode d'inversion globale basée sur un modèle d'ACP probabiliste et les cartes topologiques. Les tests de validation de cette méthode, en inversion géoacoustique sur des données synthétiques bruitées, montrent son efficacité.