Abstract FR:

Cette these porte sur les problemes d'optimisation combinatoire et sur leur resolution grace aux algorithmes genetiques, notamment ceux hybrides. Cette these traite les trois problemes suivants : l'ordonnancement de programmes paralleles, le placement de composants sur circuits imprimes et la construction de reseaux de telephonie cellulaire. Ces problemes sont resolus par l'utilisation d'algorithmes genetiques hybrides. Les algorithmes genetiques sont une methode interessante et facilement parallelisable pour trouver une solution sous-optimale d'un probleme combinatoire. Ils sont bases sur la theorie de l'evolution des especes. Leur methode consiste donc a faire evoluer une population d'individus ou de solutions. Cette these examine et compare les deux principales facons de coupler un algorithme genetique avec une heuristique. Ces deux methodes sont nommees representation directe et representation indirecte. Dans le cas de la representation directe, l'heuristique est introduite au sein de l'algorithme genetique en modifiant les operateurs de croisement ou de mutation. La representation indirecte consiste a utiliser l'algorithme genetique pour determiner un ordre total sur les elements du probleme. On utilise alors une heuristique ou algorithme de liste qui construit la solution pas a pas en tenant compte de cet ordre. A part le probleme de l'ordonnancement, cette these presente et explique la modelisation de chaque probleme, modelisation qui est necessaire afin de pouvoir exploiter au mieux les caracteristiques des algorithmes genetiques. Les trois problemes etudies ont permis d'experimenter les deux types d'algorithmes genetiques hybrides. Les algorithmes hybrides testes ont montre leur efficacite par rapport aux heuristiques classiques. Les resultats obtenus confirment l'interet d'adapter l'algorithme genetique au probleme traite.