Constructing genetic maps is a prerequisite for most in-depth genetic studies of an organism. The problem of constructing reliable genetic maps for any organism can be considered as a complex optimization problem with both discrete and continuous parameters. This paper shows how genetic algorithms can been used to tackle this problem on simple pedigree. The approach is embodied in an hybrid algorithm that relies on the statistical optimization algorithm EM to handle the continuous variables while genetic algorithms handle the discrete side. The efficiency of the approach lies critically in the introduction of greedy local search in the fitness evaluation of the genetic algorithm, using a neighborhood structure which has been inspired by an analogy between the marker ordering problem and a variant of the famous traveling salesman problem. This shows how genetic algorithms can easily benefit from existing efficient neighborhood stuctures developed for local search algorithms. The resulting program, called CARTHAGENE, has been applied both to real data, from a small parasitoid wasp, and simulated data. In both cases, it compares quite favorably to existing packages.