Bulletin 106, September 99 

Biology and operations research are two domains that have come closer to each other over the last twenty years, each one bringing ideas or models to the other. Among the contributions of biology to combinatorial optimisation, we find some population-based algorithms (genetic algorithms, ant algorithms, etc). Since their appearance, these solution methods have evolved, and now form an important class among the heuristics for combinatorial optimisation. But various problems of terminology and algorithmic description have appeared over the years. In the first part of this thesis, we tackle these problems, seldom studied in the literature, and their consequences. In order to remedy the induced conflicting situations, we study the functioning of the population-based algorithms used in combinatorial optimisation, and propose as solution a taxonomy of these algorithms. This taxonomy allows to describe the main features of such an algorithm in a simple way.

We then consider, in the second part, graph colouring problems. These problems are studied from the point of view of both the complexity and the practical resolution. Concerning the complexity, we prove various new results and generalisations of known results. We thus precise the border between the polynomially solvable and the NP-complete instances. For the practical resolution, we propose various algorithms for the colouring problem with cardinality constraints on the colours (a population-based algorithm, a tabu search algorithm and two constructive algorithms). The study of the results obtained permits the observation of interesting behaviours.

Finally, we are interested in one of the contributions of mathematics to genetics. More precisely, we consider the rôle played by graph theory in the study of DNA chains. The second phase of a DNA sequencing method is indeed a combinatorial one, and can be expressed as a graph problem. Therefore, the third part of this thesis is dedicated to the study of the graphs concerned by this application. In particular, we determine various properties of these graphs. We also consider the corresponding recognition problem and partly solve it.

For further information, please contact Professor Alain Hertz (alain.hertz@epfl.ch)