Hybrid Genetic Algorithms in Combinatorial Optimisation ; Algorithmes génétiques hybrides en optimisation combinatoire

In this thesis, we are interested in solving combinatorial problems with genetic algorithms. These algorithms are interested but they often need a lot of computations. Thus, we are focused on hybrid algorithms. Hybrids algorithms are algorithms built using several different methods. In our work, we build such algorithms by merging genetic algorithms and heuristics. There is two ways to do it. One is called the direct representation scheme and the other the indirect representation scheme. This two ways are studied by using them on three different problems: Multiprocessor tasks graph scheduling, VLSI cells placements, optimisation of cellular networks. For each of these problems, hybrids algorithms have shown their efficiency. For the probklem of optimisation of cellular networks, a new modelization have been made. This new approach allows us to do in one step the choice of emitters and the frequency's allocations. ; Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.