Etudes de problèmes de transport : Erosion côtière et aménagement urbain

 Méthode des volumes finis 

La méthode des Volumes Finis est une méthode de discrétisation qui est bien adaptée pour la simulation numérique de divers types d’équation aux dérivées partielles (elliptique, parabolique ou hyperbolique).La méthode a été largement utilisée dans plusieurs domaines de l’ingénierie : en mécanique des fluides, en calorimétrie, les problèmes transfert de masse, en ingénierie pétrolière etc. La méthode de Volumes Finis est construite à partir d’une formulation intégrale basée directement sur la forme forte des équations à résoudre. Les intégrales ne portent pas sur tout le domaine dans lequel sont posées les équations, mais sur des cellules disjointes appelées volumes de contrôles. En comparaison, la méthode des Eléments Finis s’appuie également sur une formulation intégrale des équations, appelée formulation variationnelle (ou encore formulation faible) faisant intervenir des “fonctions tests” et où les intégrales portent sur tout le domaine. Dans la méthode des Volumes Finis, les termes de divergence apparaissant dans les EDP à résoudre sont traités en utilisant le théorème de la divergence. Ainsi, les intégrales de volume d’un terme de divergence sont transformées en intégrales de surface. Ces termes de flux sont ensuite évalués aux interfaces entre les volumes de contrôle et les flux aux interfaces sont approchés par une fonction de flux numérique. La méthode des Volumes Finis a été initialement développée et mise au point pour des lois de conservation hyperboliques. Elle est conservative car on impose que le flux entrant dans un volume de contrôle soit égal au flux sortant du volume adjacent. Cette méthode est par conséquent très bien adaptée à la résolution de lois de conservation. Son développement pour des équations elliptiques et paraboliques est plus récent. Un avantage de la méthode des Volumes Finis par rapport à la méthode des Différences Finies est qu’elle permet de résoudre des EDP avec des géométries complexes dans la mesure où elle utilise des maillages non-structurés. Dans la méthode des Volumes Finis, le domaine (supposé polygonal) est discrétisé par un maillage constitué de volumes de contrôles qui sont des (petits) volumes disjoints en 3D, des polygones en 2D, des segments en 1D. 

Problèmes combinatoires 

Problèmes et Formulations

 Un problème d’optimisation combinatoire est un problème mathématique consistant à trouver dans un ensemble discret la ou les “meilleures” solutions minimisant ou maximisant une fonction donnée. En général, l’ensemble discret où les solutions sont cherchées est trop grand pour être exploré exhaustivement. La résolution du problème se heurte à une explosion dite combinatoire du nombre de combinaisons possibles. On peut formellement caractériser cette explosion par la théorie de la complexité qui propose une classification des problèmes en fonction de la complexité de leur résolution. Par complexité, on comprend généralement une estimation du nombre d’instructions à exécuter ou du temps d’exécution pour résoudre les instances de ce problème, par un algorithme donné. Cette estimation est un ordre de grandeur par rapport à la taille de l’instance. Les travaux théoriques dans ce domaine ont permis d’identifier différentes classes de problèmes en fonction de la complexité de leur résolution

NP-difficile et polynomiale 

Les classes de complexité ont été introduites pour les problèmes de décision, c’est-à-dire les problèmes posant une question dont la réponse est “oui” ou “non”. Pour ces problèmes, on définit notamment les classes suivantes : — La classe 𝒫 : c’est l’ensemble des problèmes polynomiaux, i.e., pouvant être résolus par un algorithme de complexité polynomiale. Cette classe caractérise l’ensemble des problèmes que l’on peut résoudre “efficacement”. — La classe 𝒩 𝒫 : c’est l’ensemble des problèmes polynomiaux non déterministes, i.e., pouvant être résolus par un algorithme de complexité polynomiale pour une machine non déterministe (que l’on peut voir comme une machine capable d’exécuter en parallèle un nombre fini d’alternatives). Intuitivement, cela signifie que la résolution des problèmes de 𝒩 𝒫 peut nécessiter l’examen d’un grand nombre (éventuellement exponentiel) de cas, mais que l’examen de chaque cas doit pouvoir être fait en temps polynomial. — La classe 𝒩 𝒫𝒞 ou 𝒩 𝒫-complets : c’est l’ensemble des problèmes 𝒩 𝒫 qui ne sont pas plus compliqués à résoudre, à un facteur polynomial près, que n’importe quel autre problème 𝒩 𝒫-complet. Ainsi l’existence d’un algorithme capable de résoudre un problème 𝒩 𝒫-complet en temps polynomiale entraine l’obtention d’un algorithme efficace pour la résolution de tous les autres problèmes de cette classe. Du fait de la conjecture 𝒫 ̸= 𝒩 𝒫, largement approuvée, il n’existe aucun algorithme à ce jour capable de résoudre en temps polynomiale un problème 𝒩 𝒫- complet. Dans le cas d’un problème d’optimisation associé à un problème de décision 𝒩 𝒫-complet on parle de problème 𝒩 𝒫-difficile(𝒩 𝒫-hard). Malgré la puissance actuelle des ordinateurs le temps d’exécution d’un algorithme exacte de résolution d’un problème 𝒩 𝒫-difficile reste très élevé dès que les instances deviennent “grandes”. Le “problème du voyageur de commerce” est par exemple l’un des problèmes combinatoires NP-difficile les plus connus en optimisation. Il est étudié depuis le 19ème siècle. Il consiste à déterminer une tournée de coût minimal pour un voyageur de commerce lui permettant de rendre visite à ses clients supposés se trouver dans des villes différentes. Cette tournée doit passer sur chaque ville une et une seule fois avant de revenir à la ville de départ. Le problème a d’innombrables applications pratiques notamment pour la collecte d’entités ou les tournées de véhicules. La plus grande instance qui ait été traité jusqu’à présent compte 7397 villes. Il a fallu trois années à une station Sun pour déterminer la solution optimale. La difficulté de résoudre exactement ces problèmes couplée à la nécessité de trouver des solutions pour les applications pratiques a favorisé l’émergence de méthodes heuristiques ou méta-heuristiques permettant de calculer rapidement (en temps polynomial) de bonnes solutions mais sans garantie d’optimalité. 1.4.3 Les heuristiques et métaheuristiques Les heuristiques sont des méthodes de résolution de problèmes d’optimisation qui n’offrent pas de garantie d’optimalité mais qui peuvent fournir une bonne solution approchée en temps raisonnable. Les métaheuristiques sont généralement des algorithmes pouvant optimiser une large gamme de problèmes différents, sans nécessiter de changements profonds dans l’algorithme employé contrairement aux heuristiques qui sont des algorithmes particulièrement adaptés pour un type de problèmes. On compte de nos jours une grande variété d’heuristiques et métaheuristiques : recherche tabou, algorithme génétique, essaims particulaires, colonie de fourmis etc. Suivant les cas, ces méthodes se sont avérées être très efficaces pour donner de très bonnes solutions. N’ayant pas de garanti d’optimalité les valeurs correspondantes à ces solutions sont des bornes supérieures (resp. inférieures) dans le cas d’un problème de minimisation (resp. maximisation). En calculant par une autre technique, une borne inférieure à la valeur optimale, on obtient ainsi un encadrement de la solution optimale, appelé Gap en anglais qui permet de mesurer l’erreur ou l’erreur (ou écart) relative entre la borne supérieure et la borne inférieure. Une petite erreur indique une solution heuristique proche de la valeur optimale. Nous allons donner quelques détails sur certaines des heuristiques que nous avons utilisées dans cette thèse. D’une manière générale, toutes ces heuristiques sont soit sur la notion de voisinage ou sur celle de population. Le voisinage d’une solution donnée est l’ensemble des solutions que l’on peut atteindre depuis la solution de départ par une ou des séries d’opération élémentaires de transformation. La population quant à elle est un ensemble de solutions que l’on fait évoluer en essayant de l’améliorer par rapport à l’objectif recherché.

Heuristiques gloutonnes 

Le fonctionnement d’une heuristique gloutonne est similaire à celui d’un algorithme glouton exact. En effet un algorithme glouton construit pas à pas une solution localement optimale dans l’espoir que ce choix mènera à la solution globalement optimale. De plus, sans jamais revenir sur ses décisions, à chaque étape il effectue le choix censé être le meilleur. Ainsi dans certains cas cette approche permet d’arriver à une solution globalement optimale, on parle d’algorithme glouton exact, mais en général c’est une heuristique dite gloutonne. 1 Initialisation 𝐸𝑛𝑠 = 𝐸; 2 𝑆𝑜𝑙𝑝𝑎𝑟𝑡𝑖𝑒𝑙𝑙𝑒= ensemble (ou suite) « vide »; 3 Calcul « glouton » 4 while Solpartielle non Solution ( et Ens non vide) do 5 𝑠𝑒𝑙𝑒𝑐𝑡(𝑥, 𝐸𝑛𝑠) on choisit 𝑥 selon critère glouton; 6 if 𝑆𝑜𝑙𝑝𝑎𝑟𝑡𝑖𝑒𝑙𝑙𝑒 + 𝑥 est une solution partielle then 7 𝑆 = 𝑆 + 𝑥; 8 end 9 dans certains problèmes, c’est toujours le cas 10 𝐸𝑛𝑠 = 𝐸𝑛𝑠 − 𝑥, 𝑥 ne sera plus considéré; 11 end Algorithme 1 : Heuristiques gloutonnes Il existe de nombreuses heuristiques gloutonnes dédiées à des problèmes classiques : coloriage de graphes, affectation, mise en sachets,… certaines donnant de bons résultats et étant très utilisées. Recherche d’un optimum local (Hill Climbing)

 Les méthodes de recherche locale consiste à partir d’une solution données, à explorer le voisinage de celle-ci à la recherche d’une meilleure solution. S’il n’existe pas de voisin meilleur que notre solution, le processus s’arrête. Un optimum local a été trouvé. Sinon, le meilleur des voisins est choisi et on recommence. Une autre implémentation consiste non pas à passer au meilleur des voisins à chaque étape  mais au premier meilleur. La convergence vers un optimum local pouvant être très lente, on peut éventuellement fixer un nombre de boucles maximum, si on veut limiter le temps d’exécution. Cette méthode a l’inconvénient de “rester bloqué” dans un optimum local qui peut être très bon ou très mauvais selon le point de départ. Si la solution de départ est donnée par une heuristique déterministe, l’algorithme sera déterministe. Si elle est tirée au hasard, on a un algorithme stochastique. Dans ce cas, plusieurs exécutions sur la même instance pourront donner des solutions différentes. La taille du voisinage d’une solution est ici importante. Si les voisins sont très nombreux, on a de fortes chances de trouver l’optimum global mais les visiter tous peut prendre du temps. Inversement, un voisinage restreint permet une exploration plus rapide mais avec le risque de rester bloqué dans un optimum local de “mauvaise qualité”. La taille du voisinage est donc un compromis entre efficacité et qualité. 

Recherche Taboue 

Dans ce type de métaheuristique, on recherche à chaque étape le meilleur voisin, mais en limitant la recherche aux voisins non tabous. Un voisin est considéré comme tabou si on a exploré cette solution durant les 𝑁 précédentes itérations. La maintenance d’une liste tabou de voisins peut être très coûteuse. On se borne donc souvent à stocker les transformations effectuées et non les solutions tabous. A chaque itération, on choisit le meilleur voisin (ou un meilleur voisin selon le cas) correspondant à une transformation non tabou. On effectue cette transformation, puis on la place dans la liste (file) tabou, et on élimine la plus ancienne transformation de cette liste si la file est pleine. Si la solution actuelle est la meilleure trouvée depuis le début, on la stocke. On s’arrête soit après un nombre fixé d’itérations, soit après un nombre fixé d’étapes n’ayant pas améliorées la solution. La méthode « tabou » peut être vue comme une généralisation de la recherche d’un optimum local qui correspond au cas où 𝑁 = 0. 

Le recuit simulé (simulated annealing)

 La méthode du recuit simulé est inspirée de la technique dite du recuit utilisée dans la fabrication du verre ou de métaux . L’idée de la technique physique du recuit consiste à porter d’abord à très haute température la matière que l’on veut façonner. La forte chaleur a pour conséquence la mise en mouvement des atomes constituant la matière qui ainsi s’entrechoquent et changent souvent de position. La matière est ensuite portée progressivement à des températures basses qui ont pour effet de ralentir le mouvement des atomes jusqu’à l’atteinte d’un niveau d’énergie minimale où la matière prend sa forme définitive. L’interprétation de ce procédé en terme d’algorithme d’optimisation est la suivante. Partant d’une  solution quelconque, on tire au hasard une autre solution dans son voisinage. Si elle est meilleure, on l’adopte ; sinon elle n’est retenu qu’avec une certaine probabilité. Cette probabilité va dépendre de la dégradation de la valeur de la fonction objectif et du temps écoulé depuis le lancement de l’algorithme. Au début cette probabilité sera forte à l’image de la haute température du procédé du recuit induisant de multiples changement de position pour les atomes. A mesure que le temps avance, cette probabilité va diminuer à l’image de la diminution de la température. L’algorithme s’arrête quand aucune solution ne permet de réduire le coût de l’objectif, et qu’aucune de celle-ci ne peut être choisie pour une nouvelle exploration. 

Algorithme génétique 

Les algorithmes génétiques ont été créés par J. Holland (75)[8] puis développés par David Goldberg. Ils sont basés sur la notion de population et sur des principes de génétique dont la survie des individus les mieux adaptés et la recombinaison génétique. Contrairement aux algorithmes précédents qui essaient d’améliorer un unique “individu-solution”, les algorithmes génétiques font évoluer une population de solutions. Le principe de base est de simuler l’évolution d’une population de solutions avec les règles citées ci-dessus en vue d’obtenir une solution ou un ensemble de solutions les plus adaptées. Le principe de la méthode comme énoncé par Goldberg est qu’à chaque génération, un nouvel ensemble de créatures artificielles est créé en utilisant des parties des meilleures solutions précédentes avec éventuellement des parties innovatrices .