My research in genetic algorithms

My interest in genetic algorithms grew from my search of an
algorithmic mean to reproduce the mechanisms of natural evolution. I
could not have found better!

Being rather complex, I first tried to understand how genetic
algorithms work. My readings had given me the feeling that there was
something mysterious going on there. However, all that was going on a
mere computer, so the mystery could not stand for long. I used very
simple problems and studied how population of a canonical GA evolves
in these cases.

In the same time, I read much about natural selection and I was struck
and fascinated by the mechanisms described there, and the dynamics I
saw in GAs. Those concepts of the theory of evolution known as genetic
drifts, epistasis, hitch-hiker genes, fitness landscapes, ... where
happening in these simple simulations. I figured out that there was
something profound here about the dynamics of systems in general,
which was shared among them, regardless of their biological, or
silicon nature.

I then took interest in the resolution of real problems with GAs. In
particular, I turned myself towards problems of combinatorial
optimization, namely, the traveling salesman problem, the job-shop
scheduling problem, and the quadratic assignment problem. We designed
hybrid algorithms, combining genetic algorithms, tabu search, and basic
hill-climber, and used the concept of fitness landscapes to understand
what the algorithms were doing, and how we could improve them.

To study the fitness landscapes, I had the idea to use hill-climbers
as probes and gather information along their path in the
landscape. Starting from points sampled at random (in the case of the
problems under study, these were typically bad solutions), studying
the length of trajectories, the increase in the quality of solutions
found along the trajectories, the correlation between the solutions at
the end-points of the trajectories, ... gave me many interesting
information to be able to figure out what the fitness landscape looked
like. It gave me a certain knowledge of the so-called massif central,
that is, this region in the landscape where the global optima are
located.

In the case of the traveling salesman problem, going on along this
experimental approach of the study of (combinatoiral optimization
problems) fitness landscapes, I generated instances with particular
characteristics to test my hypotheses regarding issues like:

- most instances in TSP benchmarks are planar; this fact implies many properties in the landscape; so, it is natural to ask what's going on in non planar instances?
- what's going on (w.r.t. to search) when there are many global optima? How do the massif central structures interact?

Finding answers to these questions leads to some sort of a spectrum of
fitness landscapes, ranging from those made of a Fujiyama sort --
that is, a single very good optimum (by "very good", we mean an
optimum which quality is much better than random solution), where
hill-climbers can easily travel starting from the large valley made of
random solutions -- to rather flat and dull landscapes with a
very large number of small local optima (by "small", we mean that the
quality of the optima are not much better than those of random
solutions). This variety of landscapes is also well-known in so-called
Nk-landscapes, introduced by S. Kauffman.

This improved knowledge on the TSP helped me figure out the landscape
of other problems, namely the QAP and the JSP. All NP-hard problems
being equivalent (up to a polynomial transformation), there must be
some equivalence between these TSP landscapes and those of all other
NP-hard problems.