2. Genetic algorithms, unlike a number of the other optimization techniques (Bessière, Talbi, Ahuactzin, & Mazer, 1996), are very easy to implement on parallel architectures. We have previously developed a parallel genetic algorithm ( PGA ) and we have

already had significant experience using it (Talbi, 1993).

3. PGA, unlike most parallel programs, shows linear speed-up (when you double the nmber of processors you reduce the computation time by half) and even super-linear speed-up under certain circumstances (Talbi & Bessière, 1996).

## 4.1 Parallel Genetic Algorithm

Genetic algorithms are stochastic optimization techniques introduced by Holland (1975)
twenty years ago. They are used in a large variety of domains including robotics (Ahuactzin et al., 1992; Lawrence, 1991; Falkenauer & Bouffouix, 1991; Falkenauer & Delchambre, 1992; Meygret & Levine, 1992) because they are easy to implement and do not require algebraic expression for the function to be optimized.

## 4.1.1 Principle Of Genetic Algorithm

The goal of the algorithm is to find a point reaching a "good" value of a given function F over a search space S . First, a quantization step is defined for S and the search is conducted over a discrete subset, S d of S. S d contains 2 N elements. In practice, the cardinality of S d can be extremely large. For example, in our implementation of EXPLORE, N = 116. Thus, a continuous domain is discretized with a given resolution.

During an initialization phase a small subset of S d is drawn at random. This subset is called a population. Each element of this population is coded by a string of N bits.

The genetic algorithm iterates the following four steps until a solution is found.

1. Evaluation : Rank the population according to the value of F for each element of S d .

Decide if the best element can serve as an acceptable solution; if yes, exit.
2. Selection : Use the function F to define a probability distribution over the population.

Select a pair of elements randomly according to this probability distribution.

3. Reproduction: Produce a new element from each pair using "genetic" operators. 4. Replacement: Replace the elements of the starting population by better new ele-

ments produced in step 3.
Many genetic operators (Davidor, 1989) are available. However, the more commonly used are the mutation and the cross-over operators.  The mutation operator consists of randomly flipping some bits of an element of the population.  The cross-over operator consists of first randomly choosing a place where to cut the two strings of bits, and then building two new elements from this pair by simply gluing the right and the left parts of the initial pair of strings (see Figure 9).

We use both operators to produce new elements. First, we use the cross-over operator to get an intermediate string. Then, the mutation operator is used on this intermediate string to get the final string.