Cette thése étudie le problème NP-difficile de optimization quadratique en variables binaires (BQO), à savoir le problème de la maximisation d'une fonction quadratique en variables binaires. BQO peut représenter de nombreux problèmes importants de différents domaines et servir de modèle unifié pour un grand nombre de problèmes d'optimisation combinatoire portant sur les graphes. Cette thèse est consacrée au développement d'algorithmes métaheuristiques efficaces pour résoudre le BQO et ses applications. Premièrement, nous proposons algorithmes de "backbone guided" recherche tabou et d'un algorithme mémétique multi-niveaux sur la base de la technique de la fixation de variables. Ces techniques sont toutes deux basées sur l'idée de la réduction du problème afin de mener à bien une exploitation exhaustive d'une petite région de recherche. Ensuite, nous nous concentrons sur des procédés avancés de génération des solutions initiales préférables et développons des algorithmes combinant GRASP avec la recherche tabou et les algorithmes de path-relinking. En outre, nous résolvons des problèmes, y compris le problème de coupe maximum, de clique maximum, de clique maximale de sommets pondérés et la somme coloration minimum, soit en appliquant directement ou avec une légère adaptation de nos algorithmes développés pour BQO, avec l'hypothèse que ces problèmes sont reformulés en BQO. Enfin, nous présentons un algorithme mémétique basé sur la recherche tabou qui s'attaque efficacement au BQO avec contrainte de cardinalité.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00936210 |
| Date | 11 February 2013 |
| Creators | Wang, Yang |
| Publisher | Université d'Angers |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0016 seconds