La majorité de problèmes réels d'optimisation (ex. gérer grandes infrastructures, planifier les ressources pour les communautés, villes ou entreprises, etc.) sont combinatoire par la nature et impliquent l'utilisation de plusieurs objectifs, souvent contradictoire ou différent par le type. Comme déterminé par la nature contradictoire des objectifs, une solution "idéale" n'existe pas, sur une base générale, le but étant fixée d’atteindre un ensemble des meilleures solutions de compromis. Les résultats de cette thèse font partie de l'effort d'améliorer les capacités de méthodes d'optimisation combinatoire multi-objectif (MOCO), pour des instances de grand taille. La thèse propose l'utilisation de l'analyse de paysage en tant qu'outil de guidage pour des méthodes d'optimisation, mais également en tant que moyen de mesurer la difficulté des problèmes en s'appuyant sur l'analyse topologique. L'étude est principalement basée sur les études d'analyse de paysage qui fournissent des informations au sujet de la distribution des solutions faisables dans l'espace objectif. Les approches d'analyse de paysage proposées traitent un aspect quelque peu nouvel des problèmes MOCO, c'est-à-dire les études topologiques réalisées au-dessus de l'ensemble de solutions faisables ou pour les ensembles spécifiques d'intérêts comme l'ensemble de Pareto (l'ensemble des meilleures solutions de compromis) ou l'ensemble de e-Pareto. En outre, les études de structuralité sont intégrées dans des techniques interactives afin d'aider le processus de recherche et fournir des garanties de performance même pour des recherches stochastiques dans le cas combinatoire à objectifs multiples. / The majority of real-life optimization problems (e.g. managing large infrastructures, the planning of resources for communities, cities or enterprises, etc.) are combinatorial by nature and imply the use of several objectives, often conflicting or different by type. As determined by the conflicting nature of the objectives, there exists no single "ideal" best compromise solution, on a general basis, the goal being set on attaining a set of best compromise solutions. The results of this thesis are part of the effort of improving Multi-Objective Combinatorial Optimization (MOCO) methods capabilities, for large instances.The thesis proposes the use of landscape analysis as guiding tool for optimization methods, but also as mean of quantifying the difficulty of problems based on topological analysis. The present study is mainly based on landscape analysis studies that provide information about the distribution of feasible solutions in the objective space. The proposed landscape analysis approaches tackle a somewhat new aspect of MOCO problems, i.e. the topological studies performed over the set of feasible solutions or for specific sets of interests as the Pareto set (the set of best compromise solutions) or the e-Pareto set. These techniques are seen as a priori techniques, providing useful information for the design of approximation methods. Furthermore, the structurality studies are integrated in online interactive techniques in order to help the search process and to provide performance guarantees even for stochastic searches in the multi-objective combinatorial case.

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. / Many 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.

Les accords mondiaux parrainés par l’ONU pour le développement durable et la réduction des émissions de gaz d'effet de serre, proposent la réduction de la déforestation et l'augmentation de la productivité des zones occupées par les systèmes de production agropastoraux. En Amazonie brésilienne, la déforestation couvre une zone de 760,305.5 km2 en 2014. Les différents usages de la zone déforestée ont des impacts environnementaux et des rendements financiers et sociaux spécifiques. Connaître l'occupation et l'usage des terres ainsi que les systèmes de production prédominants dans cet espace est une condition de base de la planification des actions dédiées au développement durable. Cette étude propose des méthodologies destinées à la cartographie détaillée de l'occupation et de l'usage des terres (LULC), et à l'identification de la régionalisation des systèmes de production agropastoraux. La cartographie LULC de l'Amazonie brésilienne a confirmé les résultats des études antérieures montrant que la plupart des surfaces déboisées sont utilisées principalement pour l'élevage (environ 60%), qu’environ 20% sont couvertes par une végétation secondaire et 5% par l’agriculture annuelle de large échelle. La régionalisation des systèmes de production agropastoraux a été réalisée en deux étapes. La première étape a été effectuée au niveau des divisions administratives municipales, en utilisant des données spatialement explicites de LULC et de déforestation, analysées conjointement avec des données socio-économiques spatialisées au niveau municipal. Les résultats de cette première étape de traitement ont permis d'identifier cinq systèmes de production agropastoraux à l'échelle de l'Etat. La configuration territoriale a ainsi montré que chaque système de production crée différents types de paysages. La deuxième étape a été menée sur des cellules de 10x10 km avec des données spatialement explicites de LULC, de déforestation et une matrice de distance aux infrastructures, et en utilisant des métriques paysagères. Il est alors possible de classer le système de production prédominant dans chaque cellule, et d'identifier l'effet de chaque système de production sur le paysage. Neuf systèmes de production agropastoraux ont été mis en évidence : deux dans les forêts (domaine forestier, phase initiale), trois dans l'agriculture (agriculture stricte, agriculture dominante et aires de coexistence) et quatre dans l'élevage (élevage intensifié pour la viande, élevage non intensifié pour la viande, élevage intensifié pour la viande et le lait et élevage non intensifié pour la viande et le lait). Les méthodologies qui résultent de cette thèse permettront la création d'un système opérationnel de surveillance continu et à faible coût de LULC et des systèmes de production agropastoraux dans les territoires déboisés. Grâce à ce système de surveillance, il sera possible de suivre les impacts des politiques publiques qui visent à un développement durable de la région / Recent global agreements sponsored by UN to sustainable development and reduction of greenhouse gases emission, undergo by the reduction of deforestation and an increase of productivity of the areas occupied by agricultural production systems. In 2014 the Brazilian Amazon deforestation reached 760.305,5 km2. This area has different land uses with different financial and social returns and different environmental impacts. To know the land use and land cover (LULC) and the predominant production systems in this deforested area is a basic condition for planning actions and public policies for sustainable development. This study developed methodologies for detailed LULC mapping, and to regionalization of agricultural production systems. The mapping of LULC of Brazilian Amazon confirmed previous studies, showing that most of the deforested area is used for livestock activity (about 60%), followed by secondary vegetation (about 20%) and annual crops (about 5%). Regionalization of agricultural production systems was carried out in two stages. The first one was carried out at local administrative boundary, using spatially explicit data of LULC and deforestation, analyzed in conjunction with municipal socioeconomic data spatialized at local level. Based on these results we identified, among five agricultural production systems at the state level. The dimension of territorial configuration showed that each agricultural production system form different types of landscapes. The second stage was conduced with cells of 10 X 10 Km, with LULC spatially explicit data, deforestation and a matrix of distance to infrastructure elements, and using landscape metrics. Was possible to classify the predominant agricultural production system in each cell, and identify the effect of these systems on the landscape. Nine agricultural production systems were found: two in forest domains (Forest Domain, Initial Front), three in agriculture domain (Strict Agriculture, Dominant Agriculture and Coexistence Area) and four in livestock domain (Intensified Beef, Not Intensified Beef, Intensified Beef-Milk and Not Intensified Beef-Milk). The methodologies resulted from this thesis will enable the creation of an operational monitoring system of LULC, continuous and at low cost, and also of the prevailing agricultural production system in each of the deforested territory. With this monitoring system, it will be possible to follow up the effect of public policies in the region, looking for sustainable development.

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.