Nicolas Durand
email: durand@cenatls.cena.dgac.fr

Jean-Marc Alliot
email: alliot@recherche.enac.fr

Genetic crossover operator for partially separable functions

Partial separation is a mathematical technique that has been used in optimization for the last 15 years. On the other hand, genetic algorithms are widely used as global optimizers. This paper investigates how partial separability can be used in conjunction with GA. In the first part of this paper, a crossover operator designed to solve partially separable global optimization problems involving many variables is introduced. Then, a theoretical analysis is presented on a test case, along with practical experiments on fixed size populations, with different kinds of selection methods.

Introduction

This paper deals with minimization problems for which the function to minimize is the sum of many positive terms, each term only involving a subset of variables. Griewank and Toint gave first definition of such functions (i.e partially separable functions) about 15 years ago [START_REF] Griewank | On the unconstrained optimization of partially separable functions[END_REF]. Properties of partial separability are commonly used to solve local optimization problems.

On the other hand, it is quite widely accepted that on real problems, when a crossover operator that makes sense can be defined, the efficiency of GA (compared to other stochastic optimization methods) is closely related to the use of the crossover operator: considering large size problems, the use of random crossover operator can penalize GAs performance. Classical crossover operators described in the literature [START_REF] Goldberg | Genetic Algorithms[END_REF][START_REF] Michalewicz | Genetic algorithms+data struc-tures=evolution programs[END_REF][START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF] create two children from two parents chosen in the population. Initial operators on bit strings simply cut the two parents strings in two parts. The main drawback of these operators is that short schemes have a greater probability to survive than long ones. Consequently the encoding problem becomes very important. Multi-points crossovers and Gray codes are introduced to solve this problem. When using real variable coding, programmers very often use arithmetic crossover. However, none of these methods recognizes and favors good schemes. Heuristics are sometimes used to favor "good" crossovers and "good" mutations [START_REF] Ravise | Optimisation guidée par l'induction[END_REF] or try to reduce disruption of superior building blocks [START_REF] Corcoran | Reducing disrupton of superior building blocks in genetic algorithms[END_REF].

We will show in this paper that taking advantage of the structure of partially separable functions to define a new crossover operator improves the converging speed and converging rate of a genetic algorithm.

1 Partial separability

Definition

Partially separable problems considered in this paper have the following characteristics: the function to minimize depends on ✁ variables ✂ ✄ , ✂ ☎ , .., ✂ ✆ (✁ large) and is a sum of ✝ positive functions ✞ involving only a subset of variables. Partially separable functions can be written:

✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛ ☞ ✌ ✍ ✞ ✎ ✄ ✞ ✟ ✂ ✏ ✑ ✠ ✂ ✏ ✒ ✠ ✡ ✡ ✠ ✂ ✏ ✓ ✔ ☛

Adapted crossover principle

The crossover operator introduced in this article does not require any particular coding. The chromosome is directly coded with the variables of the problem (these variables may be real, integer,...). The intuitive idea is the following: for a completely separable problem, optimizing the global function can be done by optimizing each variable separately. This strategy is adapted to partially separable functions. When creating a child from two parents, the idea is to take for each variable the one that locally fits better (more or less ✕ , where ✕ controls the determinism of the operator). First, we define a local fitness

✖ ✗ ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛ for vari- able ✂ ✗ as follows: ✖ ✗ ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛ ☞ ✍ ✞ ✘ ✙ ✚ ✞ ✟ ✂ ✏ ✑ ✠ ✂ ✏ ✒ ✠ ✡ ✡ ✠ ✂ ✏ ✓ ✔ ☛ ✁ ✞
where ✛ ✗ is the set of ✜ such as ✂ ✗ is a a variable of ✞ and ✁ ✞ the number of variables of ✞ .

Intuitively, the local fitness associated to a variable isolates its contribution to the global fitness 1 . Furthermore, it has the following good property:

✆ ✍ ✗ ✎ ✄ ✖ ✗ ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛ ☞ ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛
When minimizing , if:

✖ ✗ ✟ ✢ ✣ ✤ ✥ ✁ ✦ ✄ ☛ ✧ ✖ ✗ ✟ ✢ ✣ ✤ ✥ ✁ ✦ ☎ ☛ ★ ✕ then child ✩ will contain variable ✂ ✗ of parent ✩ . Else, if: ✖ ✗ ✟ ✢ ✣ ✤ ✥ ✁ ✦ ✄ ☛ ✪ ✖ ✗ ✟ ✢ ✣ ✤ ✥ ✁ ✦ ☎ ☛ ✫ ✕ then child ✩ will contain variable ✂ ✗ of parent ✬ . If: ✭ ✖ ✗ ✟ ✢ ✣ ✤ ✥ ✁ ✦ ✄ ☛ ★ ✖ ✗ ✟ ✢ ✣ ✤ ✥ ✁ ✦ ☎ ☛ ✭ ✮ ✕
then variable ✂ ✗ of child ✩ will be randomly chosen, or can be a random linear combination of the ✯ ✰ ✱ variable of each parent when dealing with real variables. If the same strategy is applied to child ✩ and to child ✬ , children may be identical, especially if ✕ is small. This problem can be avoided by taking a new pair of parents for each child. Let's consider the following completely separable function:

✟ ✂ ✄ ✠ ✂ ☎ ✠ ✂ ✲ ☛ ☞ ✂ ✄ ✫ ✂ ☎ ✫ ✂ ✲ for ✂ ✄ , ✂ ☎ and ✂ ✲ integers include in ✳ ✴ ✠ ✬ ✵ . Variable ✯ 's local fitness is: ✖ ✗ ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✂ ✲ ☛ ☞ ✂ ✗ . Let's cross parents ✟ ✩ ✠ ✴ ✠ ✬ ☛ and ✟ ✬ ✠ ✩ ✠ ✴ ☛ which have the same fitness ☞ ✶ . With ✕ ☞ ✴ , child ✩ will be ✟ ✩ ✠ ✴ ✠ ✴ ☛ : ☞ ✩ . With ✕ ☞ ✩ , child ✬ may be ✟ ✬ ✠ ✩ ✠ ✴ ☛ , ✟ ✬ ✠ ✴ ✠ ✴ ☛ , ✟ ✩ ✠ ✩ ✠ ✴ ☛ , or ✟ ✩ ✠ ✴ ✠ ✴ ☛ .
The children's fitness are always better than the parents fitness when ✕ ☞ ✴ which is not the case with a classical crossover operator.

As it is completely separable, this function is obviously too simple to show the interest of the adapted crossover operator. In the next paragraph, a simple partially separable function is introduced and the improvement achieved is theoretically measured.

Theoretical study

Let's define the following function:

✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛ ☞ ✍ ✷ ✸ ✞ ✹ ✎ ✏ ✺ ✆ ✻ ✟ ✂ ✞ ✠ ✂ ✏ ☛ (1) ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✠ ✂ ✆ ☛ is a bit string and ✻ ✟ ✂ ✞ ✠ ✂ ✏ ☛ ☞ ✩ if ✂ ✞ ✼ ☞ ✂ ✏ and ✴ if ✂ ✞ ☞ ✂ ✏ .
It must be noticed that the function is only partially separable and has ✬ global minima,

✟ ✩ ✠ ✩ ✠ ✩ ✠ ✡ ✡ ✠ ✩ ☛ and ✟ ✴ ✠ ✴ ✠ ✴ ✠ ✡ ✡ ✠ ✴ ☛ .
1 There are often many different ways to define a local fitness that can favour more or less competing optima. Discussing this subject in the present paper would be too long.

For ✂ ☞ ✟ ✂ ✄ ✠ ✂ ☎ ✠ ✡ ✡ ✂ ✆ ☛ , we define the local fitness ✖ ✗ ✟ ✂ ☛ by: ✖ ✗ ✟ ✂ ☛ ☞ ✩ ✬ ✆ ✍ ✞ ✎ ✄ ✻ ✟ ✂ ✗ ✠ ✂ ✞ ☛
We define ✽ ✟ ✂ ☛ as the number of bits equal to 1 in ✂ . Then, it is easy to establish that:

✟ ✂ ☛ ☞ ✽ ✟ ✂ ☛ ✟ ✁ ★ ✽ ✟ ✂ ☛ ☛ ✖ ✗ ✟ ✂ ☛ ☞ ✽ ✟ ✂ ☛ ✬ ✜ ✾ ✂ ✗ ☞ ✴ ☞ ✁ ★ ✽ ✟ ✂ ☛ ✬ ✜ ✾ ✂ ✗ ☞ ✩
In the following paragraphs, we use a classical ✁ point crossover operator; ✿ ✄ and ✿ ☎ represent ✬ parents randomly chosen in a population and ❀ represents their child.

In paragraph 2.1, the probability of fitness increase when using the adapted or the classical crossover operator are compared. Then, the adapted crossover converging rate is computed in a simple genetic algorithm, with no selection and no mutation (paragraph 2.2). In paragraph 2.3, a GA with selection is used to compare the two crossovers

Probability of fitness increase

For function (1), the probability of fitness increase when using the classical or the adapted operator can be mathematically computed for every possible couple of parents.

Let's define ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ✯ ☛ as the probability to find ✯ bits equal to ✩ at the same position in both parents ✿ ✄ and ✿ ☎ , with

✽ ✟ ✿ ✄ ☛ ☞ ✜ and ✽ ✟ ✿ ☎ ☛ ☞ ❃ . As ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❁ ✄ ❂ ✄ ✟ ❃ ✠ ✜ ✠ ✯ ☛
, we will suppose that ✜ ✮ ❃ in the following. It can be shown that:

❄ if ✯ ✪ ✜ , then: ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ✴ ❄ if ✯ ✮ ✜ , then: ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❀ ✗ ✞ ✗ ❂ ✄ ❅ ❆ ✎ ✷ ❃ ★ ❇ ✁ ★ ❇ ✞ ❂ ✄ ❅ ❆ ✎ ✗ ✟ ✁ ★ ❇ ☛ ★ ✟ ❃ ★ ✯ ☛ ✁ ★ ❇
The classical crossover used is the ✁ point crossover that randomly chooses bits from ✿ ✄ or ✿ ☎ (the order of the bit string has no influence on the fitness).

For the adapted crossover (respectively for the classical crossover), let's define

❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ (resp. ❁ ❉ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ) as the probability that if ✽ ✟ ✿ ✄ ☛ ☞ ✜ and ✽ ✟ ✿ ☎ ☛ ☞ ❃ then ✽ ✟ ❀ ☛ ☞ ✯ . As ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❁ ❈ ✟ ❃ ✠ ✜ ✠ ✯ ☛ and ❁ ❉ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❁ ❉ ✟ ❃ ✠ ✜ ✠ ✯ ☛
, we will suppose that ✜ ✮ ❃ in the following. Then, it can be shown that for the classical crossover:

❁ ❉ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❊ ❋ • ❍ ✗ ■ ✞ ❏ ✏ ❂ ✗ ❑ ✍ ❆ ✎ ❊ ▲ ▼ ❍ ✷ ■ ✔ ◆ ❖ ◆ ✑ ✓ ✒ ❑ ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ❇ ☛ ❀ ✗ ❂ ❆ ✞ ❏ ✏ ❂ ☎ ❆ ✬ ✞ ❏ ✏ ❂ ☎ ❆
I(A1) > 0.0001 > 0.001 >0.01 >0.1 > 0.2 > 0.5 Figure 1 ❁ ✤ ◗ | ✟ ✟ ❀ ☛ ✪ ❙ ❚ ❯ ✳ ✟ ✿ ✄ ☛ ✠ ✟ ✿ ☎ ☛ ✵ ☛ function of ✳ ✽ ✟ ✿ ✄ ☛ ✠ ✽ ✟ ✿ ☎ ☛ ✵ classical crossover -✁ ☞ ❱ ✴ .
Figure 2 ❁ ✤ ◗ | ✟ ✟ ❀ ☛ ✪ ❙ ❚ ❯ ✳ ✟ ✿ ✄ ☛ ✠ ✟ ✿ ☎ ☛ ✵ ☛ function of ✳ ✽ ✟ ✿ ✄ ☛ ✠ ✽ ✟ ✿ ☎ ☛ ✵ -adapted crossover -✁ ☞ ❱ ✴ .
For the adapted crossover(with

✝ ☞ ❙ ❲ ❳ ✟ ✯ ✠ ✁ ★ ✯ ☛ ): ✜ ✫ ❃ ✧ ✁ ( ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ✜ ✫ ❃ ✪ ✁ ( ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ❁ ✄ ❂ ✄ ✟ ✁ ★ ✜ ✠ ✁ ★ ❃ ✠ ✁ ★ ✯ ☛ ✜ ✫ ❃ ☞ ✁ ( ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ✌ ✍ ❆ ✎ ✷ ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ❇ ☛ ❀ ✗ ❂ ❆ ✞ ❏ ✏ ❂ ☎ ❆ ✬ ✞ ❏ ✏ ❂ ☎ ❆ As ❁ ✄ ❂ ✄ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ✴ if ✯ ✪ ❙ ❲ ❳ ✟ ✜ ✠ ❃ ☛ , then: ❄ if ✜ ✫ ❃ ✧ ✁ and ✯ ✪ ❙ ❲ ❳ ✟ ✜ ✠ ❃ ☛ , then ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ✴ ❄ if ✜ ✫ ❃ ✪ ✁ and ✯ ✧ ❙ ❚ ❯ ✟ ✜ ✠ ❃ ☛ , then ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ☞ ✴
Consequently:

❄ if ✜ ✫ ❃ ✧ ✁ and ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ✪ ✴ , then ✯ ✧ ❙ ❲ ❳ ✟ ✜ ✠ ❃ ✠ ✁ ★ ✜ ✠ ✁ ★ ❃ ☛ ❄ if ✜ ✫ ❃ ✪ ✁ and ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ✪ ✴ , then ✯ ✪ ❙ ❚ ❯ ✟ ✜ ✠ ❃ ✠ ✁ ★ ✜ ✠ ✁ ★ ❃ ☛ Thus, if ✜ ✫ ❃ ✼ ☞ ✁ , then ✟ ❀ ☛ ) ❙ ❚ ❯ ✳ ✟ ✿ ✄ ☛ ✠ ✟ ✿ ☎ ☛ ✵ . If ✜ ✫ ❃ ☞ ✁ ,
local fitness of variables of each parent are equal and the adapted crossover behaves like a classical ✁ points crossover.

Figures 1 and2 give the probability for a child to have a better fitness than its parents (for all the possible combinations of parents). On this example, the adapted crossover widely improves crossover efficiency. The small square in the center of figure 1 represents a probability of improvement larger than ✴ ✡ ❱ . It becomes a very large square on figure 2.

Adapted crossover converging rate

As ❁ ❈ and ❁ ❉ are known, it is possible to evaluate the probability to find an optimal solution after ✝ generations. The GA only uses a crossover operator without any selection, or mutation operator. Let's define ❬ ❈ ✟ ✝ ✠ ✯ ☛ as the probability that

✽ ✟ ❀ ☛ ☞ ✯ if ❀ is a randomly chosen element at generation ✝ . At generation ✴ : ❬ ❈ ✟ ✴ ✠ ✯ ☛ ☞ ❀ ✗ ✆ ✬ ✆ At generation ✝ ✫ ✩ : ❬ ❈ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ☞ ✆ ✍ ✞ ✎ ✷ ✆ ✍ ✏ ✎ ✷ ❬ ❈ ✟ ✝ ✠ ✜ ☛ ❬ ❈ ✟ ✝ ✠ ❃ ☛ ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ Figure 3 gives the evolution of ❬ ❈ ✟ ✝ ✠ ✴ ☛ ☞ ❬ ❈ ✟ ✝ ✠ ✁ ☛ for different values of ✁ . It appears that the probability to find ✟ ✴ ✠ ✴ ✠ ✴ ✡ ✡ ✠ ✴ ☛ or ✟ ✩ ✠ ✩ ✠ ✩ ✡ ✡ ✠ ✩ ☛ stabilizes around ✄ ✲ after genera- tion ❭ .
It was decided that when local fitness are equal, the crossover used was the classical crossover. If it had been decided that each time local fitness are equal, the same parent would give its value to the child, then probabilities to find

✟ ✴ ✠ ✴ ✠ ✴ ✡ ✡ ✠ ✴ ☛ or ✟ ✩ ✠ ✩ ✠ ✩ ✡ ✡ ✠ ✩ ☛ would have stabilized around ✄ ☎ .
It is important to note that ✁ has little influence on the convergence speed.

It is obviously useless to expect that the same GA using the classical crossover converges. In fact, we have:

( ✝ ) ❴ ✠ ❬ ❉ ✟ ✝ ✠ ✯ ☛ ☞ ❀ ✗ ✆ ✬ ✆

Selection probability

As the fitness function takes its values in ✳ ✴ ✠ ✁ ☎ ❵ ❛ ✵ , we will select chromosomes proportionally to ✁ ☎ ❵ ❛ ★ ✟ ✿ ☛ . Let's study the simple GA that selects individuals according to the previous criteria and then uses the adapted or classical crossover. Therefore, let's define ✛ ❈ ✟ ✝ ✠ ✯ ☛ and ✛ ❉ ✟ ✝ ✠ ✯ ☛ as the probability that ✽ ✟ ❀ ☛ ☞ ✯ if ❀ is a randomly chosen element at generation ✝ , just after the selection operator.

Then, it is easy to prove that:

✛ ❈ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ☞ ❜ ❈ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ❝ ✆ ✗ ✎ ✷ ❜ ❈ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ✛ ❉ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ☞ ❜ ❉ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ❝ ✆ ✗ ✎ ✷ ❜ ❉ ✟ ✝ ✫ ✩ ✠ ✯ ☛ with ❞ ✟ ✯ ☛ ☞ ✁ ☎ ❛ ★ ✯ ✟ ✁ ★ ✯ ☛ ❜ ❈ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ☞ ✆ ✍ ✞ ✎ ✷ ✆ ✍ ✏ ✎ ✷ ❞ ✟ ✯ ☛ ✛ ❈ ✟ ✝ ✠ ✜ ☛ ✛ ❈ ✟ ✝ ✠ ❃ ☛ ❁ ❈ ✟ ✜ ✠ ❃ ✠ ✯ ☛ ❜ ❉ ✟ ✝ ✫ ✩ ✠ ✯ ☛ ☞ ✆ ✍ ✞ ✎ ✷ ✆ ✍ ✏ ✎ ✷ ❞ ✟ ✯ ☛ ✛ ❉ ✟ ✝ ✠ ✜ ☛ ✛ ❉ ✟ ✝ ✠ ❃ ☛ ❁ ❉ ✟ ✜ ✠ ❃ ✠ ✯ ☛
On figure 4, the four curves on the top represent ✛ ❈ ✟ ✝ ✠ ✴ ☛ for chromosomes of size ✬ ✴ , ❱ ✴ , ✩ ✴ ✴ and ✬ ✴ ✴ bits. The four curves on the bottom represent ✛ ❉ ✟ ✝ ✠ ✴ ☛ for chromosomes of sizes ✬ ✴ , ❱ ✴ , ✩ ✴ ✴ and ✬ ✴ ✴ .

The efficiency of the adapted crossover appears clearly, particularly for large sized chromosomes. The converging rate is not very dependent on the size of the chromosome with the adapted crossover, whereas it is very dependent on the size of the chromosome with the classical crossover.

Experimental tests

In the previous study, the size of the population was not limited. However, population size does have an influence on the converging rate. Moreover, the previous example has only ✬ global optima and we did not measure the ability of the GA to find every global optimum. We are going to tackle these two issues in this section.

Let's consider the same function as previously:

✟ ✂ ✄ ✠ ✡ ✡ ✠ ✂ ✆ ☛ ☞ ✍ ✄ ✺ ✞ ✹ ✎ ✏ ✺ ✆ ✻ ✟ ✂ ✞ ✠ ✂ ✏ ☛ (2) but with ✂ ✞ integer in ✳ ✴ ✠ ❛ ✵
. This function has ❱ optima defined by The number of optima found and the converging speeds are compared. In paragraph 3.2, a sharing operator is added to find as many optima as possible. The efficiency of classical and adapted crossover are also measured.

GA without sharing

Function ( 2) is optimized with a GA on ✬ ✴ ✴ runs (generations: ✩ ✴ ✴ ✴ , population size: ❱ ✴ ✴ , proportion crossed: ❱ ✴ %, selection: stochastic reminder without replacement, elitism: yes, sharing: no, mutation:no). The first ✩ ✴ ✴ tests are done with a classical ✁ point crossover 2 . The ✩ ✴ ✴ other tests are done with the adapted crossover previously described.

Figure 5 gives the number of runs for which 1, 2, 3 or 4 optima are found when using the adapted crossover. It is important to note that the 5 optima are never found. The figure also gives the number of runs for which 1 optimum is found when using the classical crossover. The GA with classical crossover never finds 2 optima.

GA with sharing

The GA is performed on the same function, but with a sharing process. Therefore, a distance between two chromosomes is defined. Let's define ❡ ✟ ❀ ✄ ✠ ❀ ☎ ☛ as the Hamming distance between chromosome ✩ and ✬ . If ✁ is the size of the chromosome, then let's define: before applying the selection process. Figure 6 gives the number of runs for which the 5 optima are found when using the adapted crossover and sharing. The figure also gives the number of runs for which 1 or 2 optima are found when using the classical crossover and sharing. The GA with classical crossover and sharing never finds more than 2 optima.

❢ ✜ ❜ ✦ ✟ ❀ ✄ ✠ ❀ ☎ ☛ ☞ ✩ ✠ if ❡ ✟ ❀ ✄ ✠ ❀ ☎ ☛ ✧ ✁ ✬ ✴ ✠

Influence of sharing

A "good" crossover can be defined as a crossover for which the fitness of the child is better than the fitness of both parents. In order to measure the influence of sharing on the crossover's efficiency, figures 7 (resp 8) give the percentage of "good" crossovers with the classical (resp adapted) operator without sharing and with sharing.

Figure 7 shows that the sharing process delays the convergence to the optimum. Comparing figures 5 and 6 shows that the converging rate is penalized by the sharing process. However, it is difficult to say if the sharing process has an influence on the efficiency of the crossover.

Figure 8 shows that the adapted operator is all the more efficient because population is diversified. Figure 6 shows that the 5 optima are always found before generation ✬ ✴ . Its seems that the sharing process has little influence on the converging rate.

Classical test functions

Corana's function

This function is presented in [START_REF] Corana | Minimizing multimodal unctions of continuous variables with the "simulated annealing" algorithm[END_REF]. We use here the restriction used by Ingber in its article [START_REF] Ingber | Genetic algorithm and very fast simulated reannealing: a comparison[END_REF]. The function must be optimized on

✳ ★ ✩ ✴ ✴ ✴ ✴ ✠ ✩ ✴ ✴ ✴ ✴ ✵ ❤ . It is defined by : ✾ ✷ ✟ ✂ ☛ ☞ ❤ ✍ ✞ ✎ ✄ ✐ ✴ ✡ ✩ ❱ • ✞ ✟ ✴ ✡ ✴ ❱ ✛ ✟ ❦ ✞ ☛ ✫ ❦ ✞ ☛ ☎ for ✭ ✂ ✞ ★ ❦ ✞ ✭ ✧ ✴ ✡ ✴ ❱ • ✞ ✂ ☎ ✞ otherwise • ❦ ✞ ☞ ✴ ✡ ✬ ♠ ✭ ✂ ✞ ❵ ✴ ✡ ✬ ✭ ✫ ✴ ✡ ❛ ♥ ♥ ♥ ♥ ♦ ✛ ✟ ✂ ✞ ☛ ✛ ✟ ❦ ✞ ☛ ☞ ♣ q r ✩ if ❦ ✞ ✪ ✴ ✴ if ❦ ✞ ☞ ✴ ★ ✩ if ❦ ✞ ✧ ✴
✞ ❊ t ✉ ✈ ☞ ✇ ✩ ✡ ✴ ✠ ✩ ✴ ✴ ✴ ✡ ✴ ✠ ✩ ✴ ✡ ✴ ✠ ✩ ✴ ✴ ✡ ✴ ①
This function has ✩ ✴ ② ❤ local optima and all points of ✳ ★ ✴ ✡ ✴ ❱ ✠ ✴ ✡ ✴ ❱ ✵ ❤ are global optima. Ingber presents this function as an excellent test for all global optimization techniques, and it is interesting to compare GA with adapted crossover with VFSR, which is currently the best simulated annealing technique. It is easy to define a local fitness for adapted crossover as the function is completely separable.

✖ ✞ ✟ ✂ ✞ ☛ ☞ ✐ ✴ ✡ ✩ ❱ • ✞ ✟ ✴ ✡ ✴ ❱ ✛ ✟ ❦ ✞ ☛ ✫ ❦ ✞ ☛ ☎ ✠ ✭ ✂ ✞ ★ ❦ ✞ ✭ ✧ ✴ ✡ ✴ ❱ • ✞ ✂ ☎ ✞
otherwise As it could have been expected, the adapted crossover is of course very efficient: both classical GA and VFSR fail in finding an optimum for ❴ ✪ ✬ ❛ ; the GA with adapted crossover finds the optimum up to ❴ ☞ ✩ ✴ ✴ ✴ .

Griewank's function

This function is much more interesting than Corana's, as it is not completely separable. It is defined by:

✟ ✂ ✄ ✠ ✡ ✡ ✠ ✂ ✆ ☛ ☞ ✩ ❛ ✴ ✴ ✴ ✆ ✍ ✞ ✎ ✄ ✂ ☎ ✞ ★ ✆ ❅ ✞ ✎ ✄ ③ ④ ⑤ ✟ ✂ ✞ ⑥ ✜ ☛
We will use here ✁ ☞ ✩ ✴ . This function has only one global minimum, for ✂ ☞ ✟ ✴ ✠ ✡ ✡ ✡ ✠ ✴ ☛ . We define the local fitness by:

✖ ✞ ✟ ✂ ✄ ✠ ✡ ✡ ✠ ✂ ✄ ✷ ☛ ☞ ✩ ❛ ✴ ✴ ✴ ✂ ☎ ✞ ★ ✄ ✷ ❅ ✞ ✎ ✄ ③ ④ ⑤ ✟ ✂ ✞ ⑥ ✜ ☛
4 series of 100 tests were conducted: (classical crossover, no sharing), (classical crossover, sharing), (adapted crossover, no sharing), (adapted crossover, sharing). We say that the GA has found the optimal solution when a local optimization function applied to the best element finds the optimum. Results are presented on table 1. They give the min, max, mean and standard deviation number of generations to find the optimum. The adapted crossover is clearly much more efficient than the classical one.

Conclusion

The crossover operator introduced in this paper can be adapted to various global optimization problems, and specially difficult problems with many variables. The method was in fact developed during a work conducted jointly with the French Civil Aviation Administration. The goal was to build a system able to solve automatically air traffic conflict involving up to 30 planes with real traffic. The problem involves up to 90 variables. The GA with adapted crossover outperformed every other method tried (simulated annealing, ✿ ⑦ , B&B based on interval programming). It was able to tackle the problem while classical GA were limited to problems involving less than 10 planes (30 variables) [START_REF] Durand | Optimisation de Trajectoires pour la Résolution de Conflits en Route[END_REF][START_REF] Durand | Optimisation de Trajectoires pour la Résolution de Conflits en Route[END_REF].

In this paper, we hadn't the place to discuss the influence of parameter ✕ . It can be used to control the determinism of the adapted crossover. Too small values can push the GA into local minima, while too large ones slow down the convergence. It seems that it should decrease while the algorithm converges as, at the beginning, the space is explored randomly and at the end, the algorithm becomes more deterministic.

Figure 5

 5 Figure 3 ❬ ❈ ✟ ✝ ✠ ✴ ☛ as a function of the generation ✝ for different values of ✁ .

Figure 6

 6 Figure 6 Number of runs for which 5 optima are found with the adapted crossover, 1, or 2 optima are found with the classical crossover, as a function of the generation.

2

  Figure 7 percentage of improved chromosome with the classical crossover without and with sharing.

Table 1 Convergence for Griewank's function

 1

		min max mean	s
	classical	76	294 179.44 178.47
	adapted	42	204	92.33	91.81
	classical / sharing 79	357 248.87 247.32
	adapted / sharing	42	186	96.57	95.95


Nicolas Durand
email: durand@cenatls.cena.dgac.fr

Jean-Marc Alliot
email: alliot@recherche.enac.fr

Boris Bartolomé
email: boris.bartolome@supaero.fr

Turbo Codes Optimization Using Genetic Algorithms

Introduction

The evolving world of telecommunications requires an increasing reliability and speed in communications. Reliability in information stocking and transmission is provided by coding techniques. Information is usually coded and stocked in bit strings. The communication medium can generate errors that have to be detected and corrected when decoding. Therefore, more bits than required are transmitted in order to check the errors due to the communication medium. The code rate can be defined as the information bit string length divided by the number of transmitted bits.

A simple way to code can be to assign to any incoming word (or bit string) a longer fixed coded word; decoding can then be very long as a transmitted coded word must be associated to the nearest (according to the Hamming distance) existing coded word. This technique is called the maximum likelihood technique. Consequently, the larger the Hamming distance between any pair of coded words, the easier the decision on a received coded word. For linear codes (generally used), the minimum Hamming distance between any pair of coded words (also called the Free Distance of a code) is also the minimum Hamming distance between the zero coded word ( ✁✁✁ ) and any non zero coded word.

One of the challenging problems today is to find a coding technique that maximizes the Free Distance of a code. The problem is very difficult as in real applications, the Free Distance of a code cannot be measured exactly. After introducing the coding techniques, a Genetic Algorithm is detailed in order to optimize the interleaving matrix of a Parallelly Concatenated Recursive Convolutive Turbo Code (PCRCTC). Results on a problem of size ✂ ✄ are compared to existing interleaving matrices.

Forward Convolutive Coding

Figure (1) gives the general scheme of a simple forward convolutive coder.

At each clock tick, a bit enters the coder, additions on bits are done according to figure (1). In this example, the rate of the coder is ✞ ✟ . Bits enter the coder one by one and are not grouped.

Recursive Convolutive Coding

1 0 0 (1+0+0)=1 (1+0+0+0+0) 1 0 0 + + 1 0 0 0 (1+0+0)=1 1 (1+1+0+0+0) 0 + + 1 0 0 (1+0+0)=1 1 1 (1+1+1+0+0) 1 + + 1 0 1 1 1 1 (1+1+0)=0 (0+1+1+1+0) + + Figure 2 Sample of recursive convolutive coder: input string (✂ ☎ ✂ ☎ ✂ ☎ ✂) -output string (✂ ☎ ☎ ✂ ☎ ✂)
Figure ( 2) gives the general scheme of a recursive convolutive coder. The coded bits at time ✠ depend on all former information bits, whereas in section (2.1) they didn't. This is a very important property for the turbo decoding algorithm.

Systematic Recursive Convolutive Coding

Figure (3) gives an example of a systematic recursive convolutive coder. A systematic coder also sends the uncoded bit along with the coded bits. This is also a very important property for the decoding algorithm.

Block Codes

Block codes are linear codes in which bits are grouped and a linear transformation is applied to all the block. Block codes can usually be described with a linear application (interleaving matrix), but it is not necessary. An interleaving matrix has been added in between the two coders. If the size of the interleaving matrix is ✡ , then the bits which enter the coder are grouped in blocks of size ✡ and:

☛ are directly transmitted (because of systematicity);

☛ are coded with the first recursive convolutive coder and are then transmitted ;

☛ are scrambled by the interleaver (which is simply a permuter) and are then coded with the second recursive convolutive coder before being transmitted.

The interleaver matrix is one of the key pieces in this scheme because it determines the Free Distance of the overall code, and therefore the performances of the code. This is the scheme used to code Parallely Concatenated Recursive Systematic Turbo Codes. Properties from convolutive coders (the individual coders) and block coders (because of the interleaving matrix) are mixed. The coding rate is ✞ ☞ . The aim of this article is to introduce a technique to optimize the interleaving matrix in order to maximize the Free Distance of the code.

The following definitions will help the understanding of the paper:

Worst Vector: a worst vector is a vector that leads to the minimum Free Distance or more precisely Parallel Convolutive Turbo Codes distance of a given matrix.

Self Terminating vector: a vector is self-terminating if it allows the first encoder (that is, with no interleaving) to end in state zero. modulation-demodulation operation did not affect the transmitted signal (a perfect synchronization and demodulation is supposed) and the Additive White Gaussian Noise (AWGN) channel was chosen. This channel adds noise over every transmitted bit, and the noise is a centered gaussian random variable whose variance depends upon the energy of the transmitted bit.

Transmission Channel

The Turbo Decoding Principle

In this article, the Turbo Decoding principle will not be detailed because of its complexity. People interested in decoding will find a very detailed presentation in [START_REF] Robertson | Illuminating the structure of decoders for parallel concatenated recursive systematic (turbo) codes[END_REF]. A decoding engine was built to show the benefit of improving the Free Distance on the example detailed in part (4).

Why maximizing the Free Distance

The asymptotic performance for a Turbo Code approaches [START_REF] Lance | A distance spectrum interpretation of turbo codes[END_REF]:

✌ ✍ ✎ ✡ ✏ ✑ ✒✒ ✓ ✔ ✏ ✑ ✒✒ ✡ ✕ ✖ ✗ ✘ ✏ ✑ ✒✒ ✙✚ ✛ ✜ ✍ ✡ ✢ ✣ (1)
where:

☛ ✡ ✏ ✑ ✒✒ is the multiplicity of the codewords giving the Free Distance of the code ☛ ✓ ✔ ✏ ✑ ✒✒ is the mean Hamming weight of the words giving the Free Distance of the code ☛ N is the interleaver size

☛ Q equals ✕ ✆✤ ✝ ✥ ✞ ✦ ✟✧ ★ ✩ ✪ ✫ ✬ ✭ ✮✯ ✯ ✘✰ ☛ ✘ ✏ ✑ ✒✒ is the Free Distance of the code ☛ ✚ ✛
is the rate of the code ( ✞ ☞ in our case)

☛ ✜ ✍
is the bit energy ☛ ✡ ✢ is the spectral power density for the white gaussian noise

Maximizing the Free Distance using GAs

In this paper, classical Genetic Algorithms and Evolutionary Computation principles such as described in the literature [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF][START_REF] Michalewicz | Genetic algorithms + Data Structures = Evolution Programs[END_REF]) are used. The algorithm is first described for an interleaving depth of 105 bits; adaptations to higher interleaving depths are then discussed.

A depth length of 105 bits was chosen because:

1. In [START_REF] Maseng | Methodical interleaver design for turbo codes[END_REF], an impressive algorithm is detailed to improve the Free Distance of a PCSRCC with a depth length of 105 bits.

2. This same paper compares, in a very detailed manner, 5 algorithms to improve the Free Distance of PCSRCCs.

3. This small depth length allows to extensively test the faithful of results.

Extensive results with size 105 are given in part ( 4), but the algorithm can be used with larger depths.

The Search Space

The search space is the space of all possible interleaving matrices of depth 105. So, a population element is an interleaving matrix. To generate them, we consider any permutation matrix of depth N as the product of (N-1) transpositions.

The Test space

As stated in [START_REF] Seghers | On the free distance of turbo codes and related product codes[END_REF], Benedetto and Montorsi 1996b[START_REF] Maseng | Methodical interleaver design for turbo codes[END_REF][START_REF] Lance | A distance spectrum interpretation of turbo codes[END_REF], the Free Distance of a PCSRCC code is led by self-terminating vectors of low weight. So, the test space is the space of the self-terminating vectors of weight less than 6. We will first define the partial weight of a vector for a given coder.

Définition 3.1 (Partial Weight)

The partial weight of a vector for a given coder, is the sum of the systematic part weight and the weight obtained by coding the vector with the first coder (equivalent to a ✞ ✟ systematic recursive convolutional encoder).

An example of "partial weight" is given on figure (7). First a list of self-terminating vectors of weight less than 6, having a "1" in first position is and a partial weight less than

✆ ✲ ☎ ✙ ✝
(where ✲ is an upper bound of the estimated achievable Free Distance) is generated.

✲ ☎ ✙
is chosen because the minimum weight led by a vector with weight different from zero to a recursive convolutional coder is ✔ ✳ ✴✵ ✥ ✙ (Benedetto and Montorsi 1996a). In part (4),

✲ ✥ ✙✶

; as a solution better than ✙✶ is never found, a larger value for ✲ is useless. Each vector is translated for as many positions as possible to the right, and the list is ordered according to the increasing partial weight.

Crossover

It is difficult to find a good crossover operator with interleaving matrices and it is also very time-consuming for the computer. Moreover, results were not improved by the use of crossover at the cost of a very larger complexity in the program. Thus the crossover was not used ( ✌ ✷ ✥ ).

Mutation

A random position of a worst-vector is chosen, and this position is changed with a random position in the matrix. This is illustrated on figure (8). Mutation is applied to half the population (

✌ ✳ ✥ ✁✄ ).

Evaluation Function

The most simple and logical way to associate a value to each matrix, telling how "good" the matrix is, seems to be to associate to it the worst distance it had led to until the current generation. This criteria does not take into account the ancientness of a matrice, and maybe a very young population element population would kick out an elder one which would have been evaluated over almost all the search space. For instance, a matrix with ✘ ✏ ✑ ✒✒ ✥ ✂✺ that has already been evaluated over 1.000.000 vectors can be better than a matrix with ✘ ✏ ✑ ✒✒ ✥ ✂ ✹ but which has only been evaluated over 1.000 vectors. In order to consider this problem, the concept of reliability (as defined in [START_REF] Alliot | A genetic algorithm to improve an othello program[END_REF] for optimizing an Othello program) was used. In order to evaluate an Othello program, the number of victories against a reference program is used. The reliability of a program depends on this number, but also on the number of games already played. A program that won 46 games out of 48 may be more reliable than one that won 6 games out of 6. If ✸ is the probability to win a game, the probability to win ✻ games out of ✼ is given by:

✌ ✆✸ ✽ ✻ ✽ ✼ ✝ ✥ ✾ ✼ ✻ ✿ ✸ ✳ ✆✂ ☎ ✸ ✝ ❀ ✵ ✭ ✳ ❁
(2)

Let's now find the value of ✸ according to the number of winning games ✻ over the number of played games ✼. A confidence rate ✸ ✏ ❂ ❃ ✽ ✂❄ is chosen. It can be then shown that for ✸ ✏ ❂ ❃ ✽ ✂❄, ✸ is higher than a certain value ✸ ✳ ❅✵ ❅ ❆ ❇ with probability ✸ ✏ , with the following implicit definition of

✸ ✳ ❅✵ ❅ ❆ ❇ : -7 -6 -5 -4 -3 -2 -1 0 0.5 1 1.5 2 2.5 3 3.5 Log(B.E.R) Eb/N0 (dB)
Free distance 14 Free distance 22 / 8 worst vectors Free distance 22 / 1 worst vector Free distance 23 / 29 worst vectors Shannon"s limit

✞ ❆ ❉ ❊❋ ❊ • ❇ ✌ ✆✸ ✽ ✻ ✽ ✼ ✝ ✘ ✸ ✥ ✸ ✏ ✼ ❍ ✂ (3)
In part (4), ✸ ✏ ✥ ✁✹ ✄ , figure (9) gives the values of ✸ ✵ ❅✵ ❅ ❆ ❇ for different values of ✼.

The vocabulary used in [START_REF] Alliot | A genetic algorithm to improve an othello program[END_REF] was adapted: a winning game will correspond to X "good" evaluations for a matrix. This means that, for instance, if a matrix is evaluated over Y vectors from the sample group during a generation and, if its minimum distance is better than the current worst one, this matrix will add ■ ❏ more winning games at this generation. The winning games are added to the "surviving" matrices throughout the generations.

At each generation, a matrix is tested over 1000 (

✲ ✥ ✂
) vectors of the list and also over every vector that has decreased the Free Distance of an "ancient" element (a matrice which has been tested over 5000 times and led to a Free Distance greater than 19 before it was "broken"). Actually, this has been a great improvement: vectors that have "broken" a former good matrix are kept and first tested on new generated matrices. Indeed, as new matrices are generated by mutation, they have common characteristics and the same vector often "breaks" lots of matrices. Consequently, the number of tests operated on the matrices increases as generations go on: for instance, in the following results, it starts at 1000 and ends at about 10000.

The final fitness function is:

❑ ✥ ✆▲ ✏ ❍ ✂ ✂ ❍ ✡ ▼ ✝ ◆ ✸ ✆✡ ❖ ✝
where ▲ ✏ is the minimal distance found, ✡ ▼ is the number of worst vectors corresponding to the minimal distance and ✡ ❖ is the number of games played.

This method is empirical, and the underlying idea is to allow the population to get old (in order to have strong matrices) slowly (in order to allow new matrices, maybe better than the elder ones, to arise).

General Remarks

In the results presented in part (4), an unpunctured code is used (its rate is ✞ ☞ ). Afterwards, as all the worst vectors are kept for the final matrix, an adapted puncturing scheme can be found in order to have the same Free Distance but a higher coding rate. The program was stopped after 24 hours.

Results

105 bits sized problem

The coder described on figure (4) and the Forward-Backward algorithm with no simplification for the Turbo Decoding algorithm are used. Matrices with ✘ ✏ ✑ ✒✒ ✥19 are found in about 3 minutes (on a Pentium pro 300), with Our first remark is that in 40 minutes, a better result (because of a lower number of worst vectors) than the best interleaving matrices for PCSRCCs [START_REF] Maseng | Methodical interleaver design for turbo codes[END_REF]) (which was been obtained in one week) is obtained. Second, the algorithm can be applied to larger sizes of interleavers.

The efficiency (in terms of B.E.R.) of different matrices is given on figure (10). The highest curve shows a randomly chosen interleaving matrix. Its Free Distance is 14. The second curve shows the performance of the best matrix found in [START_REF] Maseng | Methodical interleaver design for turbo codes[END_REF], which has a Free Distance of 22 and 8 worst vectors. The third curve corresponds to one of the matrices found with the genetic algorithm, with a Free Distance of 22 but only 1 worst vector. The influence of the number of worst vectors for the same Free Distance can be seen: the less worst vectors, the better the perfomance. The fourth curve of figure (10), shows the performance of a matrix leading to a Free Distance of 23 with 29 worst vectors. This is the best matrix obtained (see figure (11)). Indeed, it has the greater Free Distance, but also a good spectrum (at least until a weight of 29). The last curve is Shannon's asympotic limit.

Table (1) gives the spectrum of vectors for different Free Distance optimization algorithm [START_REF] Maseng | Methodical interleaver design for turbo codes[END_REF]. The two last lines correspond to the results obtained with genetic algorithms.

Genetic algorithms can improve substantially the performances compared to those of classical existing methods. Extension of the method to larger size problems is discussed in the last part.

Extension to larger sizes

The method discribed in this article can be adapted to larger problems. However, the set of self-terminating vectors increases quickly. Indeed, a self-terminating vector can be a combination of

Conclusion

Improving the effective Free Distance to lower the error floor as proposed by (Benedetto and Montorsi 1996a) does not work, at least on our example. But, the Free Distance and the distances spectrum seems to be a good criteria to optimize. It

Figure 1

 1 Figure 1 Sample of forward convolutive coder: first and second step -input: ✂ ☎ ✂ -output: ✆✂✂✝ ☎ ✆ ✂✝

  Figure 3Sample of systematic recursive convolutive coder

Figure ( 5 Figure 5

 55 Figure (5) gives a very simplified scheme of a general transmission. In the following it was supposed that the

Figure 6

 6 Figure 6 Example of floor phenomenon

Figure 7

 7 Figure 7 Partial weight of the coder

Figure 9

 9 Figure 8 Mutation Principle

FigureFigure 11

 11 Figure 10 Comparison in terms of B.E.R. of different matrices

  ✥20 in about 10 minutes, with ✘ ✏ ✑ ✒✒ ✥21 in about 20 minutes, with ✘ ✏ ✑ ✒✒ ✥22 in about 40 minutes and finally with ✘ ✏ ✑ ✒✒ ✥23 in 6 hours.

  terminating vectors with a ✂ at the first position and a partial cost lower than ✙ ✂. If we delete the combinations of ✙ or more self-terminating vectors, only ◗ ◗ ✂ ✶ simple self-terminationg vectors remain. For a problem of size ✙ ✄| , the number of self-terminating vectors increases to || ✹ ◗ whereas we still have ◗ ◗ ✂ ✶ simple selfterminating vectors. Consequently, for larger size problems, self-terminating vectors can be built by dynamically combining self-terminating vectors. First trials are being performed giving Free Distances of ✙ | for the ✙ ✄| bits size problem described earlier. Simulations are still being performed and the size of the problem will be increased to

was observed that the higher the Free Distance, the better performance and for equal Free Distances, the less worst vectors, the better performances.

Applying genetic algorithms to difficult information theory optimization problems seems to be a very promising direction. In the case of our concern, genetic algorithms have proved their efficiency by giving the best published results on an interleaving depth of 105 bits. Moreover, this algorithm is not limited by the size and higher interleaver sizes are already being tested.


Yasser Fadlallah

Abdeldjalil Aïssa-El-Bey

Karine Amis

Dominique Pastor

Ramesh Pyndiah

NEW DECODING STRATEGY FOR UNDERDETERMINED MIMO TRANSMISSION USING SPARSE DECOMPOSITION

In this paper we address the problem of large dimension decoding in MIMO systems. The complexity of the optimal maximum likelihood detection makes it unfeasible in practice when the number of antennas, the channel impulse response length or the source constellation size become too high. We consider a MIMO system with finite constellation and model it as a system with sparse signal sources. We formulate the decoding problem as an underdetermined sparse source recovering problem and apply the ℓ 1 -minimization to solve it. The resulting decoding scheme is applied to large MIMO systems and to frequency selective channel . We also review the computational cost of some ℓ 1 -minimization algorithms. Simulation results show significant improvement compared to other existing receivers.

INTRODUCTION

Multiple input multiple output (MIMO) systems have known a regain of interest since the mid nineties as a solution to increase the data rate in wireless point-to-point networks at the expense of a multi-antenna interference (MAI) [START_REF] Telatar | Capacity of multi-antenna gaussian channels[END_REF]. The performance of the MIMO system is conditioned to a clever management of the MAI. Maximum likelihood joint detection enables to detect at once the signals transmitted in the same time interval [START_REF] Damen | On maximum-likelihood detection and the search for the closest lattice point[END_REF]. It has been proved to minimize the error probability for medium to high signal to noise ratio (SNR) values. It can be applied even if the decoding problem is underdetermined [START_REF] Grant | Further analytical results on the joint detection of cochannel signals using diversity arrays[END_REF] (for example when the number of transmit antennas is higher than the number of receive antennas). However, its complexity grows exponentially with the constellation size and the antenna dimensions, and makes it unfeasible in practice. Linear equalizers such as minimum mean square error (MMSE) and zero-forcing (ZF) present rather low complexity but achieve poor performance when used in underdetermined MIMO systems. Solutions alternative to ML detection and with reduced complexity have been proposed, among which the sphere decoder performs the best provided the searching sphere is well defined. The sphere decoder suffers from three major weaknesses. First its performance depends on the searching sphere radius value. Secondly it is based on an iterative algorithm and the required iteration number is not bounded. Thirdly, the computation cost keeps high in the lowto-medium SNR region and for large MIMO dimensions [START_REF] Hassibi | On the sphere decoding algorithm i. expected complexity[END_REF].

In this paper, we consider an underdetermined MIMO system with finite constellations. We aim to find an efficient decoder with polynomial time complexity . We adapt the detection algorithm that we have proposed in [START_REF] Aziz-Sbai | Underdetermined Source Separation of Finite Alphabet Signals via L1 Minimization[END_REF] to the underdetermined MIMO decoding problem. The first step is the transformation of the MIMO channel with input belonging to a finite alphabet into an equivalent higher-dimensional MIMO channel with sparse input vector. Then the decoding problem becomes equivalent to the ℓ 0 -norm minimization problem subject to some constraints that we define. This problem is usually solved using exhaustive search; also NP-hard. On the other hand, the ℓ 0 -norm minimization problem can be relaxed by ℓ 1 -norm minimization [START_REF] Foucart | A note on guaranted sparse recovery via L1 minimization[END_REF]. Based on this relaxation, the transmitted data can be decoded or recovered using iterative algorithms reviewed in [START_REF] Foucart | A note on guaranted sparse recovery via L1 minimization[END_REF][START_REF] Yang | Alternating direction algorithms for L1-problems in compressive sensing[END_REF]. In addition, we show the performance of the proposed decoding scheme for the following applications i) large MIMO systems, and ii) frequency selective MIMO channel. This paper is organized as follows. In Section 2, we describe the system model. In Section 3, we reformulate the MIMO channel with finite input constellation, and we introduce the decoding strategy based on ℓ 1 -norm minimization. This decoding strategy is then applied to two different applications described in Section 4. The computational requirements are discussed in Section 5. In Section 6, the simulation results enable to evaluate our work. Finally, Section 7 concludes the paper.

Notations: boldface upper case letters and boldface lower case letters denote matrices and vectors, respectively. For the transpose, transpose conjugate and conjugate matrices we use (.) T , (.) H and (.) * , respectively, ||.|| p denotes the norm ℓ p and ⊗ is defined as the Kronecker product.

SYSTEM MODEL

We consider a MIMO transmission over a flat fading channel, where the transmitter and the receiver are equipped with N and n antennas, respectively. We assume no prior knowledge of the channel state information (CSI) at the transmitter and a perfect CSI knowledge at the receiver. The received signal for MIMO transmission channel is defined as

y = Hx + z, (1)
where H is an n × N random channel (or mixing) matrix (n < N ), x is the N × 1 data vector, and z is the n × 1 circularly symmetric additive Gaussian noise vector with zero mean and covariance σ 2 I. The components of x belong to a finite alphabet constellation defined as

Q = {q 1 , q 2 , • • • , q M }. For example, assuming 4-QAM con- stellation yields Q = { 1+i √ 2 , 1-i √ 2 , -1+i √ 2 , -1-i √ 2 }
and M = 4. The goal of our work is to find out an efficient decoding scheme of the transmitted data symbols with moderate computational complexity order on the whole SNR region. To this end, we exploit the fact that the transmitted data vector components belong to a finite alphabet, and we transform the MIMO channel above into an equivalent MIMO channel where the input data vector becomes sparse. The sparse source vector is then recovered using iterative algorithms usually employed to resolve ℓ 1 -minimization problems.

MIMO DECODING SCHEME OF AN EQUIVALENT SPARSE INPUT

In this section we exploit the fact that transmitted data symbols belong to the finite alphabet set Q, and we formulate the vector x as

x = B q s, (2) where
s = [s 1 , s 2 , • • • , s N ] T , and
s i = [I(x i = q 1 ), I(x i = q 2 ), • • • , I(x i = q M )], I(x i = q j ) = 1 if x i = q j 0 otherwise B q = I N ⊗ q M q M = [q 1 , q 2 , • • • , q M ]. (3)
I(x i = q j ) is the indicator function indexed by i, 0 M is the zeros vector of length M , and B q is a block diagonal matrix with dimension N × N M . Substituting (2) into (1) yields

y = HB q s + z. (4)
The new problem is the decoding of the binary source vector s, it is equivalent to the following minimization problem arg min||s|| 0 , subject to s ∈ S,

where S = ||y -HB q s|| 2 2 < ǫ, and B 1 s = 1 N . The ℓ 0minimization problems are usually solved using exhaustive search where all coefficients of s belong to {0, 1}. The N × N M matrix B 1 is defined as

B 1 = I M ⊗ 1 T M (6)
where 1 M is the ones vector of length M . The equality constraint B 1 s = 1 N ensures that the solution B q s has N nonzero components, and that the decoded symbols belong to the finite input constellation. The other inequality constraint aims to select a codeword within an euclidean less than a constant ǫ from the received signal. Hence, the problem in ( 5) is somehow similar to the ML decoding problem. However, in our problem the decoded symbols depend heavily on the choice of ǫ, which in turn depends on the current SNR value. In order to judiciously select ǫ, we define it as follows

ǫ = F -1 χ 2 d (ρ 2 ) (1 -γ), (7)
where

F χ 2 d (ρ 2 ) is the cumulative distribution function of the non-central χ 2 distribution χ 2 d (ρ 2
) with d degrees of freedom and non-central parameter ρ 2 . The threshold parameters in our problem are defined as follows: d = 2n due to the complex noise, ρ 2 = (2 log(n))σ 2 i.e. the universal threshold, and γ ∈ (0, 1]. Discussion on the optimality of the chosen ǫ is given in the Appendix.

When the minimization problem in ( 5) is solved via an exhaustive search, the complexity grows exponentially with the number of transmitted symbols per channel use; resulting in an NP-hard problem. That is why the authors in [START_REF] Foucart | A note on guaranted sparse recovery via L1 minimization[END_REF] have proposed to replace the ℓ 0 -minimization problem by the ℓ 1 -minimization, and have shown that the equivalence holds when the restricted isometry property (RIP) is less than a small constant. On the other hand, as mentioned in [START_REF] Aissa-El-Bey | Recovery of Finit Alphabet Solutions of Underdetermined Linear System[END_REF], in our case, the RIP condition is sufficient and not necessary. It is also shown that for binary alphabet, when the random mixing matrix satisfies n ≥ N/2 the convergence to the optimal solution obtained by the problem in ( 5) is guaranteed for large N using ℓ 1 minimization. Thus, more transmitted symbols per channel use results in a robuster decoding scheme.

APPLICATIONS

In this section, we apply the decoding scheme based on ℓ 1minimization to the following applications: i) Large MIMO systems, ii) Frequency selective MIMO channel.

large MIMO systems

Large MIMO systems, also known as large-scale antenna systems, is a research topic proposed recently in communication theory, antenna systems, and some other fields [START_REF] Larson | Very Large MIMO Systems[END_REF][START_REF] Rusek | Scaling up MIMO: Opportunities and Challenges with very Large Arrays[END_REF]. The increased attention is mainly due to their high spectral efficiencies [START_REF] Telatar | Capacity of multi-antenna gaussian channels[END_REF]. Large MIMO scheme involves tens to hundreds of antennas at the transmitter and the receiver sides. The model is similar to the standard MIMO scheme except that the dimensions are larger. Assuming a point-to-point MIMO transmission in flat fading channel, the received signal is expressed as:

y = Hx + z = HB q s + z, (8)
where H is the n × N channel matrix, and x is the N × 1 data vector. The equivalence between ( 8) and ( 1) is obvious.

The decoding problem can be solved using the following minimization problem

arg min||s|| 1 , subject to s ∈ S. ( 9
)
where S is given in (5).

Frequency Selective MIMO channel

Another application is the frequency selective MIMO channel where L + 1 multipaths interfere at every channel use. The transmitter and the receiver are equipped with N and n antennas, respectively. We consider a transmission over a frame, and for every transmitted symbols L + 1 copies are received through L + 1 different paths. A guard interval is inserted between consecutive frames to avoid inter-symbol interference from one frame to another. The frequency selective channel output at instant n is expressed as

y(n) = L l=0 H l x(n -l) + z = L l=0 H l B a s(n -l) + z, (10)
where H l represents the l th path in the frequency selective channel. In order to decode the original symbol vector, we propose a joint detection over the whole frame. Thus, instead of applying the decoding process T times, one time for each data vector, we only decode at once a concatenated vector which consists of all transmitted vectors. The channel model is reformulated as

y T1 = I N.T ⊗ H T 0 • • • H T L T .x + z, (11)
where

T 1 = T + L, y T1 = y T (1), • • • , y T (T 1 )
T is the n.T 1 × 1 vector with all received vectors stacked over one frame observation,

x = x T (1), • • • , x T (T ) T and z = z T (1), • • • , z T (T 1 ) T .
One can notice that the performance of the proposed decoding scheme is heavily dependent on the number of multipaths. So when there are no multipaths, the channel matrix H becomes block diagonal, and the problem of ( 10) is then equivalent to decoding each N × 1 data vector independently, and the joint decoding over the received frame is no longer exploited. In contrast, more multipaths results in higher achievable diversity order implying more reliable joint decoding via ℓ 1 -minimization. This explanation is better clarified in section 6.

COMPUTATIONAL REQUIREMENTS OF THE ℓ 1 -MINIMIZATION

In order to solve ℓ 1 -minimization problems, different algorithms have been proposed [START_REF] Yang | Fast L1-Minimization Algorithms and An Application in Robust Face Recognition: A Review[END_REF]. In this section we review the complexity order of some of these algorithms. The ℓ 1 minimization algorithms are solvable in polynomial time, however, their computational complexity orders are dissimilar. The authors in [START_REF] Yang | Fast L1-Minimization Algorithms and An Application in Robust Face Recognition: A Review[END_REF] have discussed the performance of some algorithms including: the primal-dual interior point (PDIP) method and the Homothopy method. The PDIP method requires an average running time that increases linearly with the projection dimensions. The number of required iterations is O( (N )), and each iteration can be executed in O(N 3 ) operations. Besides, the ℓ 1 minimization problem requires less computational operations using the Homothopy method, O(In 2 + InN ) where I is the number of iterations. However, it entails an accuracy loss .

SIMULATION RESULTS

In this section we evaluate the Bit Error Rate (BER) and the computational complexity of the proposed decoding scheme based on ℓ 1 -minimization. We consider N × n underdetermined MIMO systems (n < N ), where N and n are the number of transmit and receive antennas, respectively. The channel coefficients are i.i.d. circular symmetric complex Gaussian distributed with zero mean and unit variance, and the data symbols belong to a finite constellation. The number of transmitted symbols is equal to N at one channel use. For our proposed decoding scheme, we use the cvx toolbox which is a Matlab-based modeling system for convex optimization. Cvx employs the SeDuMi solver to solve the ℓ 1 minimization problem under convex constraints [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF][START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.0 beta[END_REF]. We simulate this system using Matlab 2009b on a CPU Intel Xeon E5620 at 2.40GHz and memory 6GB RAM. Fig. 1 compares the time-run of the sphere decoder (SD), described in [START_REF] Cui | An Efficient Generalized Sphere Decoder for Rank-Deficient MIMO Systems[END_REF], to the ℓ 1 -based decoder. The time-run represents the average duration that needs a processor to decode the received signal. We assume a 4-QAM constellation map- Fig. 3: Time-run comparison of the ℓ 1 -minimization versus the Viterbi-ML for SNR = 14dB, assuming BPSK modulation ping known at both the transmitter and the receiver. One can notice that using the ℓ 1 -based decoder, the computational complexity keeps almost invariant with the system dimensions and the SNR level, whereas the SD time-run increases exponentially with these two factors. For the SD, we do not go beyond the 24 × 21 due to a too high computational complexity, which is upper-bounded by O(M γN ), where γ ∈ (0, 1] [START_REF] Jalden | On the Complexity of Sphere Decoding in Digital Communications[END_REF]. On the other hand, Fig. 2 illustrates a slight performance gain of our scheme in the low SNR region. Otherwise, i.e. beyond 8dB, the SD outperforms the proposed scheme. For example at BER 10 -2 , we observe a gain of about 5dB with a 16 × 14 and of 4dB with a 24 × 21.

Next, Fig. 3 compares the time-run of our proposed decoder to the Viterbi decoder one. The Viterbi algorithm exploits the channel multi-paths, and achieves optimal performance over a frequency selective channel. The frame length is equal to T = 20, and the constellation mapping is BPSK. The computational complexity of the Viterbi decoder is known to grow exponentially with the number of transmit antennas and the number of channel multi-paths τ as O(2 N.τ ). This is consistent with the obtained results in Fig. 3, where the Viterbi time-run increases from 0.73 seconds for τ = 3 to 6.77 seconds for τ = 4, whereas the time-run of our proposed scheme remains constant and equal to around 0.25 seconds. However, the Viterbi decoder leads to a BER improvement as illustrated in Fig. 4. For example, at BER 10 -2 , the gain fluctuates between 1dB and 2.5dB, and at BER 10 -3 the gain fluctuates between 3dB and 4dB, for different multi-path number.

Remarks: 1) It is important to mention that despite the non-optimality of the current Matlab solver, it can always show the increase of the computational complexity order of the above decoding schemes.

2) The gain obtained over the proposed scheme can be reduced using an error-correcting code e.g. turbocode.

CONCLUSION

In this paper we have addressed the problem of decoding in high dimension MIMO systems with finite constellation. We have modeled the transmission as a higher-dimension MIMO channel with sparse input vector. We have then defined an ℓ 1minimization problem to detect the sparse vector. An iterative algorithm of polynomial moderate complexity has been used to solve the problem. Simulations carried out in the cases of large MIMO systems on flat fading channel and MIMO systems on frequency selective channels, where the efficiency of the proposed decoding scheme has been proved.

APPENDIX

From a general point of view, let Y, Θ, X be three d-dimensional real random vectors where X ∼ N(0, σ 2 I d ) when Θ and X are independent and Y = Θ + X. Given tolerance τ 0, Random Distortion Testing (RDT) [START_REF] Pastor | Random distortion testing and applications[END_REF] is the problem of testing whether Θ(ω) -θ 0 τ or not, when we are given Y and the probability distribution of Θ is unknown. By analogy with standard terminology in statistical inference, we say that this problem is the testing of the null event Θ -θ 0 τ against the alternative event Θ -θ 0 > τ on the basis of observation Y . The RDT problem [START_REF] Pastor | Random distortion testing and applications[END_REF] is summarized as follows:

RDT:

      
Observation: Y = Θ + X Θ and X independent, X ∼ N(0, σ 2 I d ), Null event: Θ -θ 0 τ , Alternative event: Θ -θ 0 > τ .

(12) Given any η 0, let T η be any thresholding test with threshold height η defined for any y ∈ R d by

T η (y) = 1 if y -θ 0 > η 0 if y -θ 0 η. (13)
Given γ ∈ (0, 1] and ρ 0, there exists a unique solution λ γ (ρ) 0 in η to 1 -F χ 2 d (ρ 2 ) (η 2 ) = γ, where F χ 2 d (ρ 2 ) is the cumulative distribution function of the non-central χ 2 distribution χ 2 d (ρ 2 ) with d degrees of freedom and non-central parameter ρ 2 . In [START_REF] Pastor | Testing the mahalanobis distance between a random signal with unknown distribution and a known deterministic model in additive and independent standard gaussian noise: the random distortion testing problem[END_REF], it is then proved that the thresholding test T λγ (τ ) with threshold height λ γ (τ ) is such that the conditional probability values P T λγ (τ ) (Θ + X) = 1 Θθ 0 τ have supremum equal to γ, whatever Θ such that P Θ -θ 0 τ = 0. We thus say that T λγ (τ ) has size γ for RDT. Moreover, it turns out that T λγ (τ ) is optimal for RDT among all tests with same size in the following sense: 1) Save for values of ρ in some subset D ⊂ (τ, ∞) such that P Θ -θ 0 ∈ D = 0, the conditional probability P T λγ (τ ) (Θ + X) = 1 Θ -θ 0 = ρ does not depend on the distribution of Θ for every ρ ∈ (τ, ∞) \ D and 2) P T λγ (τ ) (Θ + X) = 1 Θ -θ 0 = ρ P T(Θ + X) = 1 Θ -θ 0 = ρ for all test T with level γ and such that P T(Θ + X) = 1 Θ -θ 0 = ρ does not depend on the distribution of Θ either. In other words, with respect to some criterion suitable for the natural invariance exhibited by RDT on the spheres centered at θ 0 in R d , thresholding tests T λγ (τ ) are optimal.

Fig. 1 :

 1 Fig. 1: Time-run comparison of the ℓ 1 -minimization versus the Sphere Decoder for different SNR values.

Fig. 2 :

 2 Fig. 2: Performance of the ℓ 1 -minimization versus the Sphere decoder for different antenna dimensions in large MIMO systems

Fig. 4 :

 4 Fig. 4: Performance of the ℓ 1 -minimization versus the ML-Viterbi decoder for different number of multipaths assuming BPSK modulation. τ represents the number of multipaths.