fr | en

Séparés par des virgules

VISIOCONFERENCE | Soutenance de thèse de Monsieur Jintong REN

10h00 | Faculté des Sciences | 2, boulevard Lavoisier | ANGERS

Sujet : Optimization algorithms for graph layout problems

Directeur de thèse : Monsieur Jin-Kao HAO

RÉSUMÉ

Cette thèse considère deux problèmes de disposition des graphes : le problème de la bande passante cyclique (CBP) et le problème de l’agencement linéaire minimum (MinLA). Le CBP est une extension naturelle du problème de minimisation de la bande passante (BMP) et le MinLA est un problème de somme minimale. Ces problèmes sont largement appliqués dans la vie réelle. Puisqu’ils sont NP-difficile, il est difficile de les résoudre dans le cas général. Par conséquent, cette thèse est consacrée au développement d’algorithmes heuristiques efficaces pour faire face à ces problèmes. Plus précisément, nous introduisons deux algorithmes de recherche locale itétée, un algorithme mémétique avec différents opérateurs de recombinaison pour le CBP et une heuristique de voisinage basée sur un ensemble pour résoudre le MinLA. On montre expérimentalement que pour le CBP, les deux algorithmes de recherche locale itéré pouvaient concurrencer  favorablement les méthodes de l’état de l’art, le croisement approprié est identifié pour l’algorithme mémétique. On montre également que pour le MinLA, l’heuristique de voisinage basée sur l’ensemble s’est avérée plus efficace que des algorithmes avec voisinage traditionnel à 2-flip.

Télécharger l'avis de soutenance de thèse

Scroll