François Cluzel
email: francois.cluzel@ecp.fr

Bernard Yannou

Markus Dihlmann

User tests for the convergence of a car silhouettes design model using an Interactive Genetic Algorithm

Keywords: Interactive Genetic Algorithm, Evolutionary Design, car profile, user test, subjective evaluation

We propose in this paper a car silhouettes design model based on an Interactive Genetic Algorithm. The design solutions are indirectly encoded by a Fourier analysis approach. Thus after creating an initial population, the designer is able to evaluate himself generations of car profiles, in order to converge towards an individual which meets its requirements. An automatic test has already been conducted, but it is not sufficient to validate the model; we propose here 6 new tests. The two first ones are based on the user satisfaction towards the created design solution. The data were collected during a short subjective evaluation workshop. The 4 other tests use a similarity index (that quantify the perceived distance between 2 individuals) to process the same data and validate the model. These results reveal a really satisfactory behaviour and open perspectives on the understanding of the user perception.

1-Introduction

A recurrent observation in Design is the lack of CAD (Computer Aided-Design) tools for the first phase of the design process [C1] [START_REF] Dagher | Study of the correlations between user preferences and design factors: application to cars front-end design[END_REF]. At this step, most of the work actually consists in drawing 2D sketches to create new and innovative products. The existing CAD tools often offer wide possibilities, but later in the design process. These tools are indeed based on geometric constraints and clearly defined form, which is not really compatible with the human and sometimes artistic refinement process that leads to 2D sketches. Thus the ideal aiding tool should be able to take into account the user perception to permit an easy convergence towards a design solution that really meets the designer own requirements.

In this study field, the theory of Evolutionary Design (ED) seems very promising. Genetic Algorithms (GA) [START_REF] Bentley | An introduction to creative evolutionary systems[END_REF] [RE1] are an application of ED. Originally used for complex optimisation problems, GAs work on the basis of an initial population. Each individual of this population is a design solution and its structure and apparent qualities are called phenotype. Each phenotype is encoded by a genome. Through recombination of these genomes during an operation called crossing over, the individuals can reproduce themselves and produce new individuals. So with successive generations, the GA displays better and better design solutions. The principle is the same for an Interactive Genetic Algorithm (IGA, see [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF]) but here the user plays an active role in the process. He/she performed himself the choice of the individuals which will be used to create the next generation. So IGAs are then particularly adapted to our situation, where an aesthetic evaluation of the individuals is required and the user perception is essential. Two conference papers have already been written to describe the principle of the encoding and the working of the IGA [START_REF] Yannou | Indirect encoding of the genes of a closed curve for interactively create innovative car silhouettes[END_REF] [START_REF] Yannou | Evolutive design of car silhouettes[END_REF]. So in this paper we first present a summary of these publications to clearly describe the model.

Several methods are commonly used to encode the genome of an individual, but they often have the disadvantage to be conceived for a given design domain. The proposed encoding is based on the Fourier decomposition of a 2D-closed-curve and can be applied to all possible objects represented by their 2D silhouettes. Our IGA is based on this encoding. After creating an initial population, the IGA starts. The interactive part takes place at each generation, where the style designer qualitatively assesses individuals. After the evaluation, the crossing over operation is automatically performed to create new design solutions.

In this way, innovative and new concepts are expected from the collaboration between an automatic process of design space exploration and the interaction of a designer. But validations are necessary. A first automatic test has been proposed in the previous papers [START_REF] Yannou | Indirect encoding of the genes of a closed curve for interactively create innovative car silhouettes[END_REF] [YD2], using a similarity index. The aim of this indicator is to quantify the perceived distance between 2 individuals. However our model is supposed to be interactive, and an automatic test cannot answer all the following questions:

 Are the users satisfied by our model?  Are the results better with our model than without?  Does our model really create novelty?  Are the results different from a user to another? So user tests seem to be essential to prove that innovation and surprise may emerge from this process. Thus we performed a subjective evaluation workshop to collect user data. Then the results of 2 main tests and 4 post-processing tests using the similarity index have been established. They show a very satisfactory behaviour of the model in terms of convergence, diversity, dependence to the initial population, but they also show interesting results about the user perception.

The paper presents in section 2 the process of the Interactive Genetic Algorithm with the different operations required for encoding a car profile, generating an initial population and combining the genomes. In section 3, a similarity index is proposed to measure the perceived distance between two individuals. Section 4 deals with the subjective evaluation workshop that was carried out to validate the model, whereas other tests based on the similarity index are explained in section 5 to study the model's behaviour. Finally, section 6 concludes on some forthcoming perspectives.

2-Model description

This part has been developed in more details in 2 previous papers (see [START_REF] Yannou | Indirect encoding of the genes of a closed curve for interactively create innovative car silhouettes[END_REF] and [START_REF] Yannou | Evolutive design of car silhouettes[END_REF]). However, the model description is necessary to understand the next parts of this paper.

-Encoding of the car profiles

A major difficulty when using GAs in automatic design systems is the encoding of the genome (see [START_REF] Nicaise | Indirect encoding of structures for evolutionary design[END_REF]). Most systems use a direct encoding where geometrical dimensions and structures of the design object are directly represented in the genome [AC1] [START_REF] Yanagisawa | Interactive Reduct Evolutional Computation for Aesthetic Design[END_REF]. Other works use tree structures [START_REF] Liu | Supporting evolution in a multi-agent cooperative design environment[END_REF] or shape grammars [START_REF] Osborn | Creating cross-over vehicles: Defining and combining classes using shape grammars[END_REF], or even a set of predefined components of the studied product [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF].

But the main disadvantage of all these systems is that they are conceived for a given design domain. Implementing these methods in new fields of design is a difficult and time consuming process.

We propose here a new encoding method for a 2D-closed-curve based on the works of McGarva [START_REF] Mcgarva | Harmonic representation of closed curves[END_REF]. He has proposed its development into a Fourier series as a method for coding its phenotype. We have personally already used this theory in [START_REF] Vasiliu | Dimensional Synthesis of Planar Mechanisms Using Neural Networks: Application to Path Generator Linkages[END_REF] for encoding a 2D-closed-curve into the five first Fourier harmonics of this decomposition. The main advantages of such a method are numerous. Indeed almost all possible 2D-closed-curves may be generated, every detail may be represented (which is really important to stimulate emotions), the genomes have a constant length (which is simpler for the crossing over operation), and last but not least, the genes (the Fourier harmonics) are narrowly associated to apparent characteristics of the phenotype.

McGarva's theory of Fourier decomposition of a closed curve considers that the position of each point belonging to this curve can be expressed by a complex function in the complex plane:

(1) As z(t) is a closed curve, its function is periodic. The period is normalised with: z(t+1) = z(t). This function z(t) can be developed into a Fourier series, according to formula (2):

∑ (2)
where the complex Fourier coefficients can be calculated by formula (3):

∫ (3)
Coefficient a 0 is called fundamental, a 1 and a -1 represent the first harmonic, a 2 and a -2 the second harmonic, etc.

As we will see later, the function z(t) is not known as an explicit function from the beginning. Instead, we assume that the curve has been initially defined by a set of successive points z k (k=0,..,N) which belong to the curve. So, in order to calculate the a m coefficients (3) we need a numeric approximation. We obtain this approximation by dividing the curve into N segments connecting each point with its successor. We call t k the length of the curve between the first point z 0 and the point z k . Under these conditions the integral can be calculated by the trapezium formula:

∑ (4)
while z is a periodic function, (z N+1 = z 0 ). t k is defined by:

(5)

where the total length L is the sum of the lengths of all segments, L k is the length from the origin to the current point, with x N+1 = x 0 and y N+1 = y 0 .

To construct the genome of an object, we develop its silhouette into Fourier series and define the fundamental (the coefficient a 0 ) as gene number zero. The first harmonic (a 1 , a -1 ) will be called the first gene, the second harmonic the second gene, etc.

On the basis of the genome, the original shape of the individual can be reconstructed. Every point P k with the coordinates (x k , y k ) on the curve z * which approximates the silhouette of the car, can be calculated by formula (6).

∑ (6)

where t k (0≤t k ≤1) is the position on the curve and p fixes the number of harmonics used for the decoding. When p equals 1 for example, we use one harmonic to reconstruct the silhouette of the car. The more harmonics used for the decoding the more precise will be the approximation to the original curve (as seen in figure 1). We call p the "precision" of decoding.

-Creation of a population

The first step of the IGA process is the creation of an initial population (phase 1 on figure 1). Then the population evolves in phase 2 (see figure 1), explained in section 2.3.

The initial population consists of silhouettes of several (20 for the user tests in sections 4 and 5) already existing car bodies. In order to easily sketch these silhouettes we programmed an interface in Java which allows to border a silhouette from a photograph by clicking on the screen and to encode it (see figure 2). During bordering, a sufficient amount of points should be used to represent as many details as possible. When using a number M of 60 to 80 points per silhouette the result is satisfactory.

However it is not sufficient to calculate a genome which is precise enough to allow a highly detailed decoding into the phenotype. Consequently we need to augment the number of points on the curve by smooth interpolations. Bicubic splines linking three successive points have been choose, because this method provides a curve which is very close to the original curve without producing oscillations. Within each spline, a given number of points are interpolated, leading to a total number of N points with N>M. N has an influence on the precision of the Fourier coefficients. The number p of harmonics used to decode the genome has a strong influence on the final result too. So it is necessary to determine a satisfactory balance between N and p.

After qualitative experiments, we found out that a satisfactory choice was achieved with a genome size p of 71 and a number N of approximately 1500 points for the interpolation since both initial and resulting silhouettes were visually identical.

A last operation of normalization is necessary in order to obtain car silhouettes that are independent of a particular location or size. The coefficient a 0 is simply set to 0 to fix the centre of gravity of all individuals at the origin of the representation plane. To normalize the size of the curve we chose to simply have a surface area invariance.

-Evolution of a population

The population of a Genetic Algorithm evolves during the crossing over operation. In our case the individuals of the populations are car silhouettes. They reproduce themselves to create new individuals. A fitness value f between 0 and 6 (where 0 is the worst and 6 the best evaluation) is assigned to each individual, according to the grade given by the user via an interface. It is important to notice that the meaning of the scale is chosen by the user himself. No visual connection is given. It permits a high liberty in the design process, but it may sometimes have bad effects, because the user can change his/her own scale during the evaluations.

The interface developed in Java (see figure 3) displays six individuals at a time and the user can browse through all the individuals of a population. The user is supposed to evaluate all the individuals of a population. Four operators have been implemented:

 Selection: decides which individuals will reproduce and create children according to the fitness values.  Crossover: builds a child's genome from two selected genomes (called parents).  Mutation: changes in a random way a genome after the crossover (not detailed here).  Killing: decides which individuals from the parents' population will survive and live on in the new generation (not detailed here).

We decided to adopt some conventional choices in terms of selection and killing operators and to propose an original crossover operator. We chose a turnover rate of 0.7, meaning that, for a coming generation, 30% of the individuals are kept from the previous one and 70% of children are generated.

In this way we do not lose potential good design solutions. The probability for an individual to be selected to be a parent is proportional to its fitness value (between 0 and 6). After choosing two individuals from the parents' population, their genomes are combined into the genome of a child by applying the crossover and the mutation operators. Afterwards the two individuals are re-put into the parents' population. Indeed, an individual can be selected more than once by the selection operator.

We envisaged several possibilities to crossover the two genomes of parents into the one of the child, but the best tried idea is to operate a weighted mean between the gene values of the two parents to build the genome of the child. A crossover weight W is chosen randomly between 0 and 100. A new gene g* is formed by calculating the weighted mean of the genes g m,1 and g m,2 of the parents after formula (7).

(7)

In function of the weight W we obtain different new design solutions which continuously interpolate a silhouette between the two parents' silhouettes. Thus children have visual characteristics of the two parents and no useless car is produced, but only a small space of possible solutions is explored. To enlarge the space of possible solutions we must apply a mutation operator (not detailed here).

3-Similarity Index

-Requirement

Is our system really capable to produce innovation and novelty? Is it possible for a user to design with the help of our system a new car body silhouette which was not part of the initial population?

A simple test permits to have a first idea of the answer, before performing a user tests workshop. A designer draws on a sheet of paper a car body silhouette which comes spontaneously to his/her mind and which is not part of the initial population. This car body silhouette is taken as "reference individual". By working with our system he should try to obtain in the end the silhouette he had drawn before on the paper. To cope with this, he is supposed to evaluate the car solutions which look close to the reference individual with higher grades and those who look different with lower grades. By counting the number of generations he needs to reach the reference individual, we can estimate the quality of our design system.

But this method is highly linked to the designer subjectivity, which would probably influence the results. Our objective is just to estimate the convergence ability of the model. If no automatic convergence is observed, there will probably not be a convergence with any user test. So we have preferred to perform an automatic test. The target individual is a car silhouette that has been removed from the initial population. The role of the designer is played by an algorithm, which automatically evaluates the individuals of a generation in terms of their similarity to the target individual. For that purpose, we defined a similarity index between two individuals.

The idea is to work with an indicator of the perceived distance between two individuals. Initially, this index has been built for the test described in this section, but we will see in section 5 that it is a useful tool to work on the user data too.

-Description

The difference between two genomes G k and G l is given by D(k,l) in formulas (8):

∑ with (8) ( ) ( ) ( ) ( )
with a m = u m + i v m , and α(m) a weight factor which should give more importance to the first genes than to the last genes because it is more easy to perceive. Formula (9) gives an approximation of α(m) from user evaluations:

(9)

Finally we define the similarity index between two genomes k and l as:

(10

)
where N is a normalisation factor.

To understand the link between the reality and this tool, table 1 proposes a range of values and their visual meaning on car silhouettes.

-Automatic convergence test

For the test we used the car in figure 4a as reference individual. The parameters for the Genetic Algorithm were the following: population of 100 individuals, turnover rate of 0.7 and mutation probability of 0.3. The mutation could change a gene in a range of ±(50%-200%). After 10 generations our system reached the car body silhouette in figure 4b which has a similarity index of 92%, which can be considered as a much satisfactory result. The average fitness of the population converges over the generations to a high value (more than 95%), whereas the value of the best similarity index in the population (the fitness of the fittest individual) raises rapidly from relative low 44% to 92%.

So our system is able to automatically and quickly (less than 10 generations) converge towards a given car silhouette that is not in the initial population. It means that the space of possible solutions which can be reached by our system is large enough. This is necessary to be able to produce innovation and novelty, but not sufficient. The problem is now to validate the model with regard to the user perception, and to answer the following questions:

 Are the users satisfied by our model?  Are the results better with our model than without?  Does our model really create novelty?  Are the results different from a user to another?

That is why we propose in section 4 two new tests based on the users' subjective evaluation and on the works of Kim [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF]; 4 new post-processing analyses will also be performed in section 5, using the similarity index.

4-Validation tests 4.1 -Tests construction

Kim worked in 2000 on fashion design with an Interactive Genetic Algorithm [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF]. He proposed a model to create innovative dresses from a catalogue of components (predefined necklines, sleeves, skirts… See figure 5). The main difference between our model and Kim's one is the space of possible solutions. As Kim worked with a set of predefined parts, which is a finite and discrete set, this space is limited, whereas our possible solution space if infinite and continuous. To validate his model, Kim performed two different tests.

The first test is called convergence test. It permits to ensure that the average fitness value according to each generation of the Genetic Algorithm increases with the generations. He made the test along 10 generations composed of 8 dresses. He used a panel of 10 users, working on two semantic attributes (splendid and cool-looking), that means that he asked the users to evaluate 10 generations of dresses according to the first attribute, and then to do the same process with the second attribute. The results showed a significant increase of the fitness.

The second test is called subjective test. Its goal is to show that the results obtained with the model are better than without. Kim asked 3 users to find the 10 best dresses according to the two semantic attributes (splendid and cool-looking) among 500 individuals randomly created from the catalogue of permitted combinations (i.e. without his IGA). Then he asked the 10 previous users to find the best dress of the 10 th generation of the previous convergence test, according to the two attributes. The last stage was to compare for each attribute and for each user their own best dress obtained with the model with the 10 best dresses obtained without. The comparisons were made by pairwise comparisons, on a 7 degrees scale (from -3 to 3). Finally, the results showed that the individuals obtained with the algorithm reached on average a degree of about 2, compared to the individuals obtained without algorithm. So the model was really satisfactory.

But two main criticisms can be formulated on these two tests:

 Are the evaluations hedonistic or not? A hedonistic evaluation includes the preference of the user (for example "Please rate these individuals according to your preferences in terms of sportiveness"; the user maybe likes sportive individuals, but not too much), whereas a nonhedonistic evaluation does not (for example "Please rate these individuals according to their apparent degree of sportiveness").  What is the meaning given by Kim on the pairwise comparisons? He asked the users to compare their own best dress (from the algorithm) with the 10 best dresses found by 3 other people. So it seems logical that the first one (found by the user himself) is better than the others (found by other people).

We built our test according to these criticisms.

-Workshop realization

We have chosen to work for the two tests with a non-hedonistic evaluation ("Please rate these individuals according to their apparent degree of sportiveness").

We have also chosen two semantic attributes: friendly and sportive (half of the users work with the first one, the others with the second one).

The first test that we have defined is the same that the convergence test defined by Kim. We called it test of "designer satisfaction". We have worked with 10 generations composed of 20 individuals, and with a mutation probability of 0.05 and a selection rate of 0.7.

We have defined the second test (that we called test of "satisfaction superiority of the IGA model") with regard to the problem of the pairwise comparisons (expressed in Section 4.1). The process is the following:

 400 car silhouettes are created randomly from an initial population of 20 real individuals. To clarify the notations in the next parts of the paper, these 400 individuals are called paper individuals. Each user has to find the 3 bests individuals according to his/her semantic attribute. Practically, these individuals are printed on paper and numbered, and the users record their evaluation in an Excel according to the following process: o Each user evaluates the 400 paper individuals on the same scale as in the IGA (from 0 to 6). The best car silhouettes in his/her mind have to receive a 6.

o Only the individuals which receive a 6 are selected for the next evaluation. An Excel macro sorts out these individuals and a new evaluation table is presented to each user. o The two first stages are repeated until each user finds the 3 best individuals. That means that the users must be more and more selective (to always have scores between 0 and 6 in order to progress).  Then each user has to find the 3 best individuals of the 10 th generation of the test of "designer satisfaction".  Then a pairwise comparison [YE1] matrix permits to each user to compare pair to pair his/her own 3 best individuals of the algorithm with his/her own 3 best individuals obtained without the algorithm. The scale used has 7 degrees (from -3 to 3).  Pairwise comparisons are explained in more details in [YE1]. They permit to evaluate simply a set of individuals without any absolute scale.  An example of such a matrix is given on figure 6. The comparisons have a direction to follow: here the individuals in lines are compared to the individuals in columns. The evaluation scale for these comparisons is given in table 2. The users work with the mathematic symbols (>, >>, =…), which are then replaced by numbers to analyze the data (see section 4.3.2). The tests were realized during a short workshop. The panel of users was composed of 7 students (6 men and a woman) and a professor. 4 users received the semantic attribute friendly and the 4 others the attribute sportive.

-Test of "designer satisfaction"

Figure 7: examples of best "sportive" car silhouettes (one from each user).

Figure 8: examples of best "friendly" car silhouettes (one from each user).

The analysis of the car silhouettes obtained by the users during the first test shows interesting results.

For the two semantic attributes, the users reach in their own last generation the same type of car silhouettes. Moreover, those profiles are nearly the same for the semantic attribute sportive, whereas they are really different from a user to another with the attribute friendly. Figures 7 and8 illustrate this phenomenon. The displayed silhouettes are chosen from the 3 best ones of each user. It is also interesting to notice that the car silhouettes from the 6 th generation are almost the same for each user, which means that the diversity of the populations is weak from the 6 th generation. In other words, the IGA seems to converge very quickly. It could be interesting to know if this quick convergence is wanted or not. This observation is not tackled is this paper. However, a way to change this speed is the mutation operator. For the tests, a really low mutation rate has been chosen. With a high mutation rate, the convergence speed would probably be lower, because a lot of novelty would appear at each generation. Finally, the curves presented on figure 9 can be drawn. In spite of local minima, the average fitness increases for the two semantic attributes, that shows a good global behaviour of the model: the user satisfaction increases on average from 3.0 to 5.0 for the attribute friendly, and from 2.3 to 3.9 for the attribute sportive. So it is an increase of about 70%.

-Test of "satisfaction superiority of the IGA model"

Table 3 shows the results of the test for each user and for each semantic attribute. The results show a good behaviour for the semantic attribute sportive: the average score is +1.50, so the best IGA individuals are between "slightly superior" and "superior" to the best paper individuals.

For the attribute friendly, the results show a good behaviour too, even if the difference is slightly less perceptible. All the users prefer the individuals from the IGA except user 5, who prefers the individuals without the model. Globally, the results for this attribute are not really homogenous, which can be explained by a more subjective comprehension (and so characteristic to each user) of the word friendly than the word sportive (this observation will be highlighted in other tests presented after).

-Synthesis

Those first two tests show a satisfactory behaviour of our model. The user satisfaction increases with the generations, and the results are globally better with the IGA than without.

However, some major differences can be noticed between the two semantic attributes. Indeed the user perception is really different from a user to another: sportive seems to be perceived in the same way by everyone, whereas each user has a different perception of friendly. But to confirm these observations we have proceeded to more sophisticated post-processing analysis, using the similarity index described in section 3.

5-Behaviour's model analysis

For the following tests, the index similarity described in section 3 is used. Those tests are postprocessing analysis performed on the data of the subjective evaluation workshop (see section 4).

-Test of "diversity lowering"

-Description

The aim of this test, called test of "diversity lowering" is to study:

 The evolution of the similarity index for each user along the ten generations.  The similarities that could exist between the individuals of the last generation of each designer.

The idea consists simply to calculate the similarity index between all the individuals of all the users and for all the generations of the previous workshop (see section 4), and to group together the data to observe potential correlations.

A high value of similarity for the last generation would mean that the IGA converges towards a single individuals family, and so that there is a diversity lowering.

-Results

Figure 10: evolution of the similarity index along the generations for the two semantic attributes.

The first results concern the evolution of similarity index of each user. The curves are shown on figure 10 .The initial population has an average of 6.5% of similarity. In all the cases and for the two semantic attributes, the values increase quickly. At the 6 th generation (Generation #5 on the graph), the averages of all the users are above 40% similarity, and at about 75% for the last generation. The averages of each user (in italic in tables 4 and 5) are all included between 60 and 90% of similarity, which correspond to the ranges "very strong similarities" and "imperceptible differences". It shows that for each user, the model converges towards a single family of car silhouettes, which are very close in terms of visual aspect. But it means too that there is a real diversity lowering.

-Test of "inter-designer convergence"

-Description

The goal of this test, called test of "inter-designer convergence" is to study the similarities that could exist between the last generations of all the users.

As in the previous test, the idea consists simply to calculate the similarity index between all the individuals of all the users and for all the generations of the previous workshop (see section 4), and to group together the data to observe potential correlations.

-Results

The results are displayed on tables 4 and 5. These matrices represent the averages of the similarity index for the two semantic attributes:

 Between all the users (in bold).  For each user (in italic). These values are treated in the previous test.

The values are really consistent with the visual aspect of the individuals. For the semantic attribute friendly, the values inter-designer (in bold) are not high, and the total average is only 9.21% similarity, whereas this total average is 50.83% for the attribute sportive. According to table 1 (in section 3), it means that the similarities between the last population of the users with the attribute sportive is very strong, and that there is no connection between those with the attribute friendly.

These results confirm rigorously the observations of section 4: the perception of the word sportive is the same for all users (they all came to the same type of profiles), whereas each user has its own perception of the word friendly (they all have a different kind of car silhouettes at the end of the workshop).

-Test of "superiority of the IGA model"

-Description

This test is called test of "superiority of the IGA model". Its goal is to show that our model obtains better results than without, in particular in terms of time and number of individuals.

It consists in comparing for each user the 3 best individuals of the IGA with the 3 best paper individuals (see section 4) with the similarity index. So it is the same test as the test of "satisfaction superiority of the IGA model" described in section 4.3.2, but instead of treating the fitness data, the similarity index values are used.

-Results

The maxima of similarity are shown in table 6. For 5 users out of 8, the maximum is above 70% of similarity. For 2 users, the maximum is included between 20 and 30%. For the last one, it is only 2.67% of similarity.

These values mean that it is possible to obtain the same results with and without our model. 5 users have found with the IGA at least one individual that is common or very close to one of the paper individuals.

400 individuals were proposed on paper. It took about 45 minutes for the user to evaluate them. Less than 200 individuals were used with the IGA (10 generations of 20 individuals, minus those who survive from one generation to the next one), during about 20 minutes. So we can say that our system seems to be able to bring the same results as without the model, more quickly and with fewer individuals.

-Test of "attraction in the surroundings of initial individuals"

-Description

The last test proposed in this paper is called test of "attraction in the surroundings of initial individuals".

It tries to answer the following question: is the user really able to design his/her own car silhouette, or are the final individuals influenced by the initial individuals and close to their genotypes?

Our solution to this problem is to compare the best individuals of the IGA with the 20 car silhouettes of the initial population.

-Results

The results of this test are very interesting, but too sizeable to be displayed here. That is why only the case of user 2 is presented on table 7.

This table shows that the best individuals of user 2 are very close to Individual #13 of the initial population (more than 50% of similarity). Individual #13 represents the silhouette of a Porsche 911 (see figure 11). Two other minor influences can be noticed (with Individuals #2 and #8), but the values are below 20%, which is not significant. User 2 worked with the semantic attribute sportive, and it is important to notice that the same results are obtained with the 3 other users who worked with this attribute.

Table 7: example of similarity values for the comparison between the best individuals of the IGA and the initial population (in %).

That means that they all came to the same type of profile (see section 5.1.2) which is very close to a Porsche 911. In other words, all the users perceived a sportive car as a Porsche 911.

For the semantic attribute friendly, the results are totally different. No car that influences all the users can be identified. In 2 cases out of 4, no significant influence of an initial individual is noticed. In the two other cases, such a car can be identified, with the scores of 40% of similarity, but this car is different for the two users (Porsche 911 for the one, Chevrolet Corvette C4 for the other). It shows again that this attribute is differently perceived.

-Synthesis

Those 3 tests based on the similarity index permit to prove rigorously some results of the subjective evaluation workshop (see section 4). They also permit to observe the behaviour of the model and the perception of the users.

Initial Population

In all cases the system turns out to converge towards a uniformized population. For the semantic attribute sportive, this profile is the same for any of the four users and is close to a Porsche 911. For the semantic attribute friendly, no similar influence from the initial population is identified, and the results really depend on the user. The perception of the attributes is really different from a user to another. Moreover, our model converges quickly and with less individuals than without the model, which is really satisfactory. However, some remarks can be formulated:  The model always converges towards one profile family. Is it not possible to converge towards at least two different families?  What happens if the Porsche 911 or the other influencing cars are not in the initial population? Do the users even find them?  Why are there so many differences in the perception of the semantic attributes? Some concept of Emotional Design could be introduced to develop a more powerful model.

6-Conclusions and perspectives

We have presented in this paper an innovative car silhouettes design model. Based on an encoding method of the genomes by Fourier decomposition, it offers to the car designers the possibility to create new car silhouettes from an initial population according to their preferences.

Several user tests have been carried out to study the convergence of the model in terms of user satisfaction, but also in terms of perceived distance, using a similarity index. The results show very satisfactory results. They permit to answer the four questions defined in the introduction:

 Are the users satisfied by our model? Yes, the satisfaction increases along the generations of the IGA, and the users prefer to work with our model rather than without.  Are the results better with our model than without? Yes, in terms of user satisfaction, but also in terms of time and numbers of processed individuals.  Does our model really create novelty? Potentially. It highly depends on the chosen semantic attribute. But individuals than are far from the initial population in terms of similarity can be created.  Are the results different from a user to another? Potentially. It depends on the chosen semantic attribute too.

In consequence, our system should allow style designers to converge towards intuitive ideas and to make emerging surprise in exploring large spaces of potential silhouettes.

Further tests with a larger panel of user could be done to validate the statements described in this paper and dealing with Emotional Design. The large difference of results between the simple semantic attributes sportive and friendly open a very interesting field of study for the future with the objective of creating CAD tools that really meet the user perception.

The real role of the mutation operator has to be studied too. So the identification of the optimal parameters would permit to develop a more reliable model.

Finally these first results are very promising and numerous research perspectives appear now:

 Allowing a step of "direct modification by the designer" within an intermediary generation, i.e. modifying some details of a silhouette curve or even adding new individuals to the population. We must acknowledge here that all our 20 initial silhouettes are silhouettes of existing commercial cars. Then, the experiment in this paper has just consisted in morphing between known solutions. For really creating surprise and innovating, we must also test our system in a more creative way.  Combining several series of closed curves to better define the important lines of a car (see [C1]).  Making more complex the interactive assessment of individuals by the style designer through multicriteria assessments under several perceptual attributes.  Exploring a new product field: the encoding method that we use is very flexible and applicable to many design objects. We think that excellent results could be obtained with simple shapes.

The ideal form would be a simple 2D-closed-curve from a solid of revolution (which permits to describe the whole product with a single closed curve), like stemmed glasses or vases.  Finally, a way to improve the model could be to develop a function for introducing car silhouettes drawn by the designer himself. For instance, a new form appears in his/her mind during the IGA process, so he/she can draw this form on the screen (or with some graphic tool) and introduce the new individual in the current population.

Figure 1 :

 1 Figure 1: diagrammatic plan of the IGA process.

Figure 2 :

 2 Figure 2: After bordering we obtain a closed curve representing the car silhouette of an existing car.

Figure 3 :

 3 Figure 3: User Interface for the designer evaluation showing 6 individuals of a larger population. The designer can browse through the population by clicking on the arrow buttons.

Figure 4 :

 4 Figure 4: Comparison between the reference silhouette (a) and the final resulting silhouette (b).

Figure 5 :

 5 Figure 5: examples of possible choices for arms and sleeves in Kim's fashion design model (taken from [KC1]).

Figure 6 :

 6 Figure 6: example of pairwise comparison matrix used for the tests.

About 2

 2 hours were necessary to complete the three stages (time for presentation of the tests included):  Evaluation of the 400 random printed individuals: 1 hour.  Use of the Interactive Genetic Algorithm: 30 minutes.  Pairwise comparisons: 15 minutes.

Figure 9 :

 9 Figure 9: fitness evolution for the convergence test.

Figure 11 :

 11 Figure 11: Porsche 911 and its car silhouette.

Table 1 : visual meaning of the similarity index.

 1

	< 10%	No connection
	20% to 30%	Very poor similarities
	30% to 50%	Similarities
	50% to 80%	Very strong similarities
	80% to 100%	Imperceptible differences

Table 2 : pairwise comparison scale.

 2

	-3	<<< highly inferior
	-2	<< inferior
	-1	<	slightly inferior
	0	=	equal
	1	>	slightly superior
	2	>> superior
	3	>>> highly superior

Table 3 : average values of the results of the subjectivity test (for the evaluation scale, see table 2).

 3

		User 1	+1,78
		User 2	+1,67
	Sportive	User 3	+1,56
		User 4	+1,00
		Average	+1,50
		User 5	-0,33
		User 6	+0,67
	Friendly	User 7	+0,78
		User 8	+1,22
		Average	+0,58
	Total Average	+1,04

Some details have to be explained to understand the meaning of table 3. The pairwise comparisons are made according to the following scheme: the best individuals from the IGA are compared to the best paper individuals. User 4 has for example an average evaluation of +1.00. According to table 2, it means that user 4 found the best individuals from the IGA slightly superior to the best paper individuals. Thus positive numbers prove that the results obtained with our model are better than without.

Table 4 : similarity values between users for the semantic attribute friendly (in %).

 4

	100
		80
	Index	60
	Similarity	40								Friendly
		20								Sportive
		0
		0	1	2	3	4	5	6	7	8	9
					Generation
			User 5			User 6		User 7	User 8
	User 5		79,07			6,91			4,02		2,89
	User 6					89,65		20,65		8,81
	User 7							61,02		11,97
	User 8										74,16
		Total average						9,21

Table 5 : similarity values between users for the semantic attribute sportive (in %).

 5

		User 1	User 2	User 3	User 4
	User 1	79,95	47,87	63,09	36,20
	User 2		72,34	74,14	42,62
	User 3			89,61	41,04
	User 4				74,74
		Total average		50,83

Table 6 : maxima of similarity values between the best individuals of the IGA and the paper individuals (in %).

 6

		User 1	84,49
		User 2	21,26
	Sportive	User 3	80,92
		User 4	97,93
		Average	71,15
		User 5	2,67
		User 6	98,09
	Friendly	User 7	71,32
		User 8	26,94
		Average	49,75
	Total Average	60,45


Bernard Yannou

Markus Dihlmann

François Cluzel
email: francois.cluzel@ecp.fr

Indirect Encoding of the Genes of a Closed Curve for interactively create innovative car Silhouettes

Keywords: Interactive Genetic Algorithms, shape design, car profile, Fourier decomposition, evolutionary design

An Interactive Genetic Algorithm system is proposed for designing a car silhouette while involving the style designer in the evaluation process of a population of individuals. This IGA is based on the principle of an indirect encoding of a closed curve genome using a primary Fourier decomposition. A crossing over operator is proposed for mixing the parents' genes by a random weighted average into a new child's genome. A perceived similarity index between two genomes is built. It allows to check that our IGA is able to converge toward a targeted individual which was not present within the initial population and, consequently, that any silhouette in a style designer's mind could be revealed by our system.

Introduction

Design is an engineering activity for creating new and innovative structures and shapes. Finding a new shape and style for an object can be seen as a profound human and sometimes artistic refinement process. Indeed, starting from an initial idea, the style designers continuously refine it through multiple sketches and drawings using their intuition and perception of their own production in a reflexive manner. Is it possible to help such style designers in their refinement process? Such an aiding tool should help him or her to explore more easily and systematically a large space of possible styles or shapes, and also to converge towards an ideal shape the designers could have more or less represented in their mind.

In the field of implementing this creative design process, Evolutionary Computation (EC) has become one of the primary approaches. A method in EC uses basically genetic algorithms (GA) [START_REF] Bentley | An introduction to creative evolutionary systems[END_REF][START_REF] Renner | Genetic Algorithms in Computer Aided Design[END_REF], which were originally used to find solutions for complex optimisation problems.

Taking the evolution in nature as paradigm, the GAs work on the basis of a population of individuals, where each individual represents a possible solution for the initial problem. The structure and the qualities of each individual are encoded in their genomes. Through recombination of these genomes the individuals can reproduce themselves and produce new individuals (solutions), while by a sort of natural selection the individuals who are not adapted to the environment (what is expected of their properties) are not selected for procreation. In this way, the individuals display better and better qualities over the generations. Interactive Genetic Algorithms (IGA, see [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF][START_REF] Yanagisawa | Interactive Reduct Evolutional Computation for Aesthetic Design[END_REF]) represent a special class of GAs where a human (here, the style designer) is a key player embedded within the task of selection of individuals of a generation. IGAs are then particularly adapted to situations where it is impossible to explicitely express a preference function (the fitness function) on individuals or even when it is hard to qualify expected properties. This is typically the case with style designers.

A major difficulty when using GAs in automatic design systems is the encoding of the genome (see [START_REF] Nicaise | Indirect encoding of structures for evolutionary design[END_REF]), which means the way of coding the phenotype (physical structure) of the individual into the genotype (genome). Most systems use a direct encoding where geometrical dimensions and structures of the design object are directly represented in the genome. When designing a bottle for example [START_REF] Ang | Combining evolutionary algorithms and shape grammars to generate branded product design[END_REF] or finding a design for cylinder shapes [START_REF] Yanagisawa | Interactive Reduct Evolutional Computation for Aesthetic Design[END_REF] the phenotype is represented in the genome by a sequence of geometrical parameters like radii, lengths and part locations. Consequently, the encoding is context dependent. Other works use tree structures [START_REF] Liu | Supporting evolution in a multi-agent cooperative design environment[END_REF] or shape grammars [START_REF] Osborn | Creating cross-over vehicles: Defining and combining classes using shape grammars[END_REF] to encode the genome. Kim and Cho [START_REF] Kim | Application of interactive genetic algorithm to fashion design[END_REF] have used a set of predefined parts of clothes to find new designs in fashion by recombining these parts. As the combinatorial dimension of the space of possible solutions is limited, the utility of such an automated exploration is questionable.

In addition, all these systems are conceived for a given design domain. Implementing these methods in new fields of design is a difficult and time consuming process. However, a good design method should be applicable, as much as possible, on a large spectrum of situations.

In this paper, we first propose a method of encoding a 2D-closed-curve which is supposed to meet a desired style. This method can be applied to all possible objects represented by their 2D-silhouettes. For instance a car silhouette or profile is a primordial style feature of a car since it has been proved that the aesthetic aspects of a car amounts for 70% of purchase intents for customers [START_REF] Cheutet | 2D semantic sketcher for a car aesthetic design[END_REF]] and the car silhouette in itself has been proved to have a strong determining influence on the car perception while embedding perceptual attributes such as: sportiveness, aggressivity or peacefulness, etc [START_REF] Cheutet | 2D semantic sketcher for a car aesthetic design[END_REF]]. Next, an Interactive GA (IGA) has been developed in defining a crossing-over operation between genes. The interactivity consists in letting a style designer qualitatively assessing individuals at each generation. In this manner, new innovative designs are expected to emerge by a balanced collaboration between an automatic process of design space exploration and the interaction of a designer. Finally, we provide measures for proving that innovation and surprise may emerge from this process. Indeed, we show that the initial population of individuals contains a sufficient richness of genes so as to be able to quickly converge towards a desired silhouette which is not an individual of this initial population.

The paper explains the principles of the Fourier decomposition of a closed curve and the encoding principle in section 2. Section 3 presents the process of the interactive genetic algorithm with the different operations required for generating an initial population and the principle of the crossover operator for combining the genomes. In section 3, a test of convergence toward a reference silhouette is carried out to show that it is possible to quickly converge toward a silhouette which was not present within the initial population. This test is based on a similarity index which is also presented before concluding on some forthcoming perspectives.

The genome

Usual methods for coding the phenotype of an object (i.e., its structure) are to parameterise the major dimensions of several parts of it [START_REF] Ang | Combining evolutionary algorithms and shape grammars to generate branded product design[END_REF][START_REF] Yanagisawa | Interactive Reduct Evolutional Computation for Aesthetic Design[END_REF], like its total length, the position of the tires and their radii for a car, for example. Another method is to use shape grammars [START_REF] Osborn | Creating cross-over vehicles: Defining and combining classes using shape grammars[END_REF].

Concerning the encoding of a 2D-closed-curve, [START_REF] Mcgarva | Harmonic representation of closed curves[END_REF] has proposed its development into a Fourier series as a method for coding its phenotype. We have personally already used this theory in [START_REF] Vasiliu | Dimensional Synthesis of Planar Mechanisms Using Neural Networks: Application to Path Generator Linkages[END_REF] for encoding a 2D-closed-curves into the five first Fourier harmonics of this decomposition. In that way, we have been able to build an Artificial Neural Network for synthesizing four-bar linkage mechanisms following targeted trajectories. This approach is not as rigid as the approach of parameterisation for multiple reasons:

 this encoding is supposed to embrace a much vaster space of possible 2D-closed-curvesor 2D-silhouettesthan by a parameterisation approach;  all kind of shapes may be represented even with small details, that can be of the highest importance for provoking feelings and emotions;  the encoding may be performed through a constant length of genome, which simplifies a lot crucial GA stages such as the cross-over operation between parent individuals;  finally, the genes in our solution have proved to be narrowly associated to apparent characteristics which is primordial to converge after several generations to the ideal 2D shapes.

The Mac Garva's theory of Fourier decomposition of a closed curve considers that the position of each point belonging to this curve can be expressed by a complex function in the complex plane:

( ) ( ) ( ) (1)
As z(t) is a closed curve, its function is periodic. The period is normalised with: z(t+1) = z(t). This function z(t) can be developed into a Fourier series:

( ) ∑ ( ) (2)
where the complex Fourier coefficients can be calculated by this formula:

∫ ( ) ( ) (3)
Coefficient a 0 is called fundamental, a 1 and a -1 represent the first harmonic, a 2 and a -2 the second harmonic, etc.

As we will see later, the function z(t) is not known as an explicit function from the beginning. Instead, we assume that the curve has been initially defined by a set of successive points z k (k=0,..,N) which belong to the curve. So, in order to calculate the a m coefficients (3) we need a numeric approximation. We obtain this approximation by dividing the curve into N segments connecting each point with its successor. We call t k the length of the curve between the first point z 0 and the point z k . Under these conditions the integral can be calculated by the trapezium formula:

∑ ( ( ( ) ( )) (4)
while z is a periodic function, (z N+1 = z 0 ).

The value of t k is the ratio of the length of the curve to the point k and the total length of the curve.

,

∑ √( ) ( ) and ∑ √( ) ( ) (5)
where the total length L is the sum of the lengths of all segments, L k is length from the origin to the current point, x N+1 = x 0 and y N+1 = y 0 .

To construct the genome of an object, we develop its silhouette into a Fourier series and define the fundamental (the coefficient a 0 ) as gene number zero . The first harmonic (a 1 , a -1 ) will be called the first gene, the second harmonic the second gene, etc.

On the basis of the genome, the original shape of the individual can be reconstructed. Every point P k with the coordinates (x k , y k ) on the curve z * which approximates the silhouette of the car, can be calculated by formula (6).

( ) ∑ ( )

(6)
where t k (0≤t k ≤1) is the position on the curve and p fixes the number of harmonics used for the decoding. When p equals 1 for example, we use one harmonic to reconstruct the silhouette of the car.

The more harmonics used for the decoding the more precise will be the approximation to the original curve (as seen in figure 1). We call p the "precision" of decoding.

Figure 1. Decoding of a genome of a Smart car with different precisions

It can be easily proved that the first harmonic (the sole complex coefficient a 0 ) represents the coordinates of the centre of gravity of the curve in a complex plane. The second gene (a 1 and a -1 ) contains the information defining an ellipse. The influence of the other genes cannot be illustrated easily. But we can say that the first genes influence the very basic structure and shape of the silhouette while the higher genes bring in the details of the shape.

The process of the interactive genetic algorithm

The process of finding new design solutions can be divided into two phases (see Figure 2). During Phase 1 an initial population of individuals is created. Phase 2 consists of a loop where the user evaluates the current population and a genetic algorithm evolves the population respecting the evaluation of the user.

Phase 1: Creating an initial population

The genetic algorithm needs an initial population of individuals and their genetic code to start working. This initial population consists of silhouettes of 30 already existing car bodies. In order to easily sketch these silhouettes we programmed an interface in Java which allows to draw curves on a plain and code them into a genome. To border a silhouette we display the image of an existing car in the background of the screen and draw a contour-chart around the car on the image by clicking on the screen. The result is a closed curve representing the silhouette of an existing car-body (see figure 3).

During bordering, a sufficient amount of points should be used to represent as many details as possible. When using a number M of 60 to 80 points per silhouette the result is satisfactory.

Figure 3. After bordering we obtain a closed curve representing the car silhouette of an existing car

However this amount M of 60 to 80 points is not sufficient to calculate a genome which is precise enough to allow a highly detailed decoding into the phenotype. Consequently we need to augment the number of points on the curve by smooth interpolations. The curve produced by interpolation should be very close to the original curve and should be continuously derivable in each point. If the curve is not continuously derivable, the decoding from the genotype into the phenotype produces high-frequency oscillations and is therefore useless. We chose to solve this problem with bicubic splines linking three successive points (see figure 4), because this method provides a curve which is very close to the original curve without producing oscillations (as it is the case when using polynomial interpolations like Lagrange's interpolation formula). Within each spline, a given number of points are interpolated, leading to a total number of N points with N>M.

SO O G G G G G G G 30 SO O G G G G G G G 40 SO SO O O GG GG GG GG

Figure 6. The design of experiments carried out for finding an ideal (p, N). Initial and reconstructed silhouettes are visually compared to result in subjective assessments: Iinaccurate, Ooscillations, SO strong oscillations, G -Good result, GGvery good result

Taking care of the quality of the encoding amounts to find a satisfactory balance between the number N of points on the curve used for coding and the number p of harmonics used when decoding the genome into a curve. The number p of harmonics used for decoding has an influence on the production of details. The more harmonics used for the decoding the more precise will be the approximation to the original curve. The number N of points on the curve used for coding the genome has an influence on the precision of the Fourier coefficients. This is due to the fact that we use the trapezium formula in (4) to approximate the integral during the calculation of the coefficients. We achieved numerous trials of (1) bordering a silhouette, (2) interpolating with N Points, (3) encoding with p harmonics, (4) decoding, for finally comparing the initial and the resulting silhouettes (see Figure 5). A qualitative design of experiments has been carried out (see Figure 6) with p varying from 80 to 2000 and N varying from 5 to 200. We clearly noticed that the if p is too low, the codingdeconding sequencevisually -fails to accurately represent the initial silhouette. In addition, for a given number p, there is a minimal number of points N beyond which the reconstructed curve displays strong oscillations (see such oscillations in Figure 5). In definitive, we found out that a satisfactory choice was achieved with a genome size of 71 and a number N of approximately 1500 points for the interpolation since both initial and resulting silhouettes were visually identical.

A last operation of normalization is necessary to the genomes so that the phenotypessilhouettesbe independent of a particular location, size or rotation but be compared uniquely in terms of their shape. The coefficient a 0 is simply set to 0 to fix the centre of gravity of all individuals at the origin of the representation plane. The invariance by rotation is useless because car silhouettes of the initial population are sketched horizontally and the next generations turn out to stay horizontal. Mc Garva [START_REF] Mcgarva | Harmonic representation of closed curves[END_REF] proposes to normalize the size of the curve in setting to 1 the small axis of the ellipse defined by harmonics 2. It would amount in our case to fix to a constant height the car silhouettes which is not fair for short cars. We prefer to have a surface area invariance instead. The calculus is then a bit more sophisticated but simply consists in dividing all coefficients am by a value function of | a 1 | and | a -1 | (formula not detailed here).

Phase 2: Evolution of the population

We use an interactive genetic algorithm to evolve the population and create innovation. The individuals can reproduce among themselves and produce in this way new solutions. In our case the genetic algorithm handles a population of individuals where each individual represents a possible design for a car body silhouette. A fitness value is assigned to each individual by the user.

Consequently the fitness value is a number between 0 and 6 according to the grade given by the user via an interface. The interface developed (see figure 7) displays six individuals at a time and the user can browse through all the individuals of a population. The user is supposed to evaluate all the individuals of a population on a scale from 0 to 6, where 0 is the worst and six the best evaluation. This fitness decides if an individual has a good chance to reproduce and create children. Furthermore it influences the chance of an individual to survive and to live on in the next generation. This development is reached by applying the following genetic operators to the population:

 Selection: decides which individuals will reproduce and create children.

 Crossover: builds a child's genome from two parent genomes.  Mutation: changes in a random way a genome after the crossover.  Killing: decides which individuals from the parents' population will survive and live on in the new generation.

We decided to adopt some conventional choices in term of selection and killing operators and to propose an original crossover operator. First, apart the initial population of 30 individuals, we have fixed the number of individuals to 100 at each generation. We chose a turnover rate of 0.7, meaning that, for a coming generation, 30 individuals are kept from the previous one and 70 children are generated. In this way we do not lose potential good design solutions. The probability for an individual to be selected to be a parent is proportional to its fitness value (between 0 and 6). After choosing two individuals from the parents' population, their genomes are combined into the genome of a child by applying the crossover and the mutation operators. Afterwards the two individuals are re-put into the parents' population. Indeed, an individual can be selected more than once by the selection operator.

We envisaged several possibilities to crossover the two genomes of parents into the one of the child.

For instance, we envisaged a "Two-Part-Crossover"-method which seemed promising at the beginning. It consisted in choosing randomly a crossover point X, where X is a number between 2 and 69. The child's genome was built by the first X genes from the genome of parent A and the last (70-X) genes from the genome of parent B. This method produced innovative designs for car silhouettes and few useless forms. However the method didn't produce stable results over the generations. This means that after some generations the car silhouettes were useless because they lost the tires or began to oscillate. The good idea is to operate a weighted mean between the gene values of the two parents to build the genome of the child. A crossover weight W is chosen randomly between 0 and 100. A new gene g* is formed by calculating the weighted mean of the genes g m,1 and g m,2 of the parents after formula (7).

( )

In function of the weight W we obtain different new design solutions which continuously interpolate a silhouette between the two parents' silhouettes (see figure 8). The advantage of this method is the fact that a child resembles a lot to its parents and that it produces almost no useless car solutions (the tires keep their rounded shapes). The disadvantage is the relatively small explored space of possible solutions. In consequence, the population of design solutions has a tendency to converge rapidly. To enlarge the space of possible solutions we must apply a mutation operator (not detailed here).

The killing operator is applied to the original population and kills at first all the individuals who have a fitness of 0. These individuals are considered totally useless or totally non-satisfactory and shall no more contribute to the evolution of the population. All the other individuals have a chance to survive. The individuals to be killed are chosen by an inverse roulette wheel method. That means that the probability for an individual to be killed can be expressed by formula (8).

( ) ∑ ( ) (8)
where is the fitness of individual i and is the number of individuals in the population who have not been evaluated with a fitness of 0.

Test of convergence

Is our system really capable to produce innovation and novelty? Is it possible for a human being to design with the help of our system a new car body silhouette which was not part of the initial population? This question also implicates the question if the space of possible solutions which can be reached by our system is large enough to result in a car body which is really new and innovative?

To answer this question we can execute a simple test. A designer draws on a sheet of paper a car body silhouette which comes spontaneously to his mind and which is not part of the initial population. This car body silhouette is taken as "reference individual". By working with our system he should try to obtain in the end the silhouette he had drawn before on the paper. To cope with this, he is supposed to evaluate the car solutions which look close to the reference individual with higher grades and those who look different with lower grades. By counting the number of generations he needs to reach the reference individual, we can estimate the quality of our design system.

Alternatively the target car silhouette may be an individual of the initial population that is removed from this initial population.

We have preferred to make abstraction of the designer subjectivity in automating the ability of the system to converge towards an ideal car silhouette, so as to measure the sole quality of the method. The role of the designer is played by an algorithm, which automatically evaluates the individuals of a generation in terms of their similarity to the target individual. For that purpose, we defined a similarity index between two individuals.

The similarity index

The difference between two genomes G k and G l is given by D(k,l) in formulas ( 9).

( ) ∑ ( ) with (9) ( ) ( ) ( ) ( )
with a m = u m + i v m , and α(m) a weight factor which should give more importance to the first genes than to the last genes because it is more easy to perceive. A series of user tests have been carried out to identify α(m) for several values of m. We found out that α(m) is exponential and we approximated it with:

( )

Finally we define the similarity index between two genomes k and l as:

( ) ( ) (11)
where N is a normalisation factor.

The results

For the test we used the car in figure 9.a as reference individual. The parameters for the genetic algorithm were the following: population of 100 individuals, turnover rate of 0.7 and mutation probability of 0.3. The mutation could change a gene in a range of ±(50%-200%). After 10 generations our system reached the car body silhouette in figure 9.b which has a similarity index of 92%, which can be considered as a much satisfactory result. The average fitness of the population converges over the generations to a high value (see figure 10), whereas the value of the best similarity index in the population (the fitness of the fittest individual) raises rapidly from relative low 44% to 92%.

Concluding remarks

We have presented an encoding method which works on the basis of development of the design object's silhouette into Fourier series. This method is very flexible and applicable to many design objects. The quality of coding and decoding has been subjectively assessed and tuned to be satisfactory. Furthermore we have used this encoding method to conceive an automatic design system working with an interactive genetic algorithm to evolve the design and create novelty. A crossover method for this new concept of genomes has been defined and evaluated. Finally, a formula has been identified to express a similarity index between two genomes in terms of the perceived difference of the phenotypes. In less than 10 generations, it has been showed that our system is able to automatically converge with a good quality toward a reference silhouette individual which is not present within the initial population. In consequence, our system should allow style designers to converge towards intuitive ideas and to make emerging surprise in exploring large spaces of potential silhouettes.

This concept seems to be a promising way to create future automatic design systems. Several perspectives of extensions are:

 Allowing a step of "direct modification by the designer" within an intermediairy generation, i.e. modifying some details of a silhouette curve or even adding new individuals to the population. We must acknowledge here that all our 30 initial silhouettes are silhouettes of existing commercial cars. Then, the experiment in this paper has just consisted in morphing between known solutions. For really creating surprise and innovating, we must also test our system in a more creative way.  Combining several series of closed curves to better define the important lines of a car (see [START_REF] Cheutet | 2D semantic sketcher for a car aesthetic design[END_REF]).  Making more complex the interactive assessment of individuals by the style designer through multicriteria assessments under several perceptual attributes like "Dynamic" or "Comfortable" (see [START_REF] Dagher | Study of the correlations between user preferences and design factors: application to cars front-end design[END_REF]).

Figure 2 .

 2 Figure 2. Diagrammatic plan of the IGA process

Figure 4 .Figure 5 .

 45 Figure 4. The tangent of the spline at point i is parallel to the line passing by points i-1 and i+1

Figure 7 .

 7 Figure 7. The User Interface for the designer evaluation showing 6 individuals of a larger population of 100. The designer can browse the individuals by clicking on the arrow buttons

Figure 8 .

 8 Figure 8. Results of a weighted mean crossover using different weights W

Figure 9 .

 9 Figure 9. Comparison between the reference silhouette (a) and the final resulting silhouette (b)

Figure 10 .

 10 Figure 10. The average fitness of all individuals in the population over the generations


Benjamin Vincent
email: benjamin.vincent@g2elab.inpg.fr

O Chadebec
email: olivier.chadebec@g2elab.inpg.fr

J L Schanen

C A F Sartori
email: sartori@pea.usp.br

Laurent Krahenbühl
email: laurent.krahenbuhl@ec-lyon.fr.

New robust coil sensors for near field caracterization

Keywords: Coils electromagnetic sensors, near field measurements, multipolar expansion, radiated EMC, radiated electromagnetic sources characterization I

This paper introduces a new generation of magnetic field sensors, based on the spherical harmonics decomposition concept. The measurement principle is similar to a spatial filtering: according to the coil shape, the sensors are just sensitive to a specific component of the multipolar expansion. Five coil shapes are determined, in order to account for the first two orders of the harmonic decomposition. The way of determining the coil shape is first explained, and a validation is proposed using a finite element software.

INTRODUCTION

With the increase of power density in modern power systems, interactions between various elements become often a key point to be addressed. This problem can be treated at various scales: interactions between two variable speed drives or power transformers in the same room ("indoor EMC"), interactions between power and control board, or different devices on the same board. On this latter example, magnetic coupling between magnetic components (inductor, transformer) and/or wires are encountered in complex systems, which can lead to dysfunctions or a bad filtering.

Addressing these magnetic coupling implies the ability of magnetic field characterization, close to the sources. The complete knowledge of this near field can be based on simulation or experimentation, but is unavoidable to handle interaction problems.

The first idea starts from a simple mapping of the near magnetic field, using some magnetic sensor and sampling the space by moving the sensors around the system, or by moving the system itself, or by multiplying the sensors, or using any appropriate combination of all previous solutions. After this step, the magnetic field is characterized by a set of thousands of measurement points (obtained from experimental or simulation data), what is very heavy for interaction studies. These data must therefore be summarized into a simpler equivalent source [START_REF] Keradec | Nano-teslameter for characterization of the fields emitted and received by wound electronic components[END_REF][START_REF] Rouve | Optimal magnetic sensor location for spherical harmonic identification applied to radiated electrical devices[END_REF][START_REF] Kildishev | Measurement of the Spacecraft Main Magnetic Parameters[END_REF].

One possible method is to use multipolar expansion [START_REF] Keradec | Nano-teslameter for characterization of the fields emitted and received by wound electronic components[END_REF][START_REF] Rouve | Optimal magnetic sensor location for spherical harmonic identification applied to radiated electrical devices[END_REF][START_REF] Kildishev | Measurement of the Spacecraft Main Magnetic Parameters[END_REF][START_REF] Bergervoet | A large-loop antenna for magnetic field measurements[END_REF][START_REF] Savi | Developing a Van Veen & Bergervoet Antenna[END_REF][6][START_REF] Pasmooij | A 'Helmholtz' large loop antenna system for improved magnetic field measurements[END_REF], which has shown previously its ability of synthesizing any magnetic sources into known standardized sources (dipole, quadrupole, etc.). For instance, it has been shown that a set of several thousands of data points can be summarized into 15 terms, with a large validity region [START_REF] Keradec | Nano-teslameter for characterization of the fields emitted and received by wound electronic components[END_REF].

The determination of each term of the multipolar expansion consists in solving an "inverse problem", and may be very sensitive to measurement/simulation inaccuracy. Several solutions can be used to reduce the effect of this inaccuracy [START_REF] Rouve | Optimal magnetic sensor location for spherical harmonic identification applied to radiated electrical devices[END_REF]. The idea presented in this paper is to imagine specific sensors, to measure directly the component of the multipolar expansion. The shape of the sensors will be designed in order to be sensitive to one term only, what should increase the accuracy of the parameter determination [START_REF] Kildishev | Measurement of the Spacecraft Main Magnetic Parameters[END_REF][START_REF] Bergervoet | A large-loop antenna for magnetic field measurements[END_REF][START_REF] Savi | Developing a Van Veen & Bergervoet Antenna[END_REF][6][START_REF] Pasmooij | A 'Helmholtz' large loop antenna system for improved magnetic field measurements[END_REF].

The paper will be organized as follows:

• Presentation of the mathematic model : spherical harmonics decomposition • Design of the sensor geometry • Validation with a finite elements software [11] II. SPHERICAL HARMONICS The multipolar expansion is a classical tool used for the electromagnetic field representation [START_REF] Jackson | Classical Electrodynamics[END_REF][START_REF] Stratton | Electromagnetic Theory[END_REF][START_REF] Wikswo | Scalar multipole expansions and their dipole equivalents[END_REF]. It allows decomposing any field into an infinite sum of simple terms. The first order of the decomposition is the well known dipole. Several mathematical functions (basis) can be used for the decomposition. For near field studies, the quasi-static approximation is suitable, therefore, displacement currents can be neglected. This decomposition is thus simpler than using the complete one, including propagation terms [START_REF] Jackson | Classical Electrodynamics[END_REF].

A. Harmonic decomposition

Outside a sphere including all radiation sources, the magnetic field can be completely described with its magnetic scalar potential ψ(t). This potential is a solution of Laplace equation:

0 ) ( = ∆Ψ t (1)
Considering harmonic decomposition of the temporal sources leads to complex variables. Then, the solution of ( 1) can be expressed as follows:

( )

         = = Ψ Ψ - = ∑ ∑ ∑ ∑ ∞ + = + - = ∞ + = + - = + 1 1 1 ) , , ( ) , ( . 1 . , , ) ( ) , , ( n n n m nm n n n m nm n nm B r B Y r A r grad r B r ϕ θ ϕ θ ϕ θ ϕ θ (2)
Where:

nm Y are specific functions called spherical harmonics, -r, the distance between the centre of the decomposition and the point where the field is expressed, -

)) , ( . . ( ) 1 ( ϕ θ nm n nm nm Y r A grad B + - - = r
, the elementary magnetic field of the decomposition, -A nm , the coefficients of the decomposition, the unknowns.

B. Relevance

The choice of this basis is motivated by two reasons. First, the orthogonality: coefficients A nm are unique for a given source. Secondly, the r -(n+1) decrease of the different terms insures a hierarchy between all parts of the decomposition: The larger the distance to the source is, the less terms are necessary to reconstruct the field. Far from the source, only the dipole is useful to fully characterize the radiated field.

For interaction studies, we have decided to limit the expansion to the two first orders of the decomposition. This also corresponds to the physical behaviour of most sources in electrical systems, where disturbances often originate from current loops. Therefore, the number of unknowns is limited to only 8 (from (2), there are 2n+1 coefficients for each order n. Thus, 3 unknowns for order 1 and 5 for order 2).

The aim of the identification is thus to deduce these 8 unknowns from measurements achieved around the radiation source. For this purpose, one possible solution is to take advantage from the fast decrease of the high order terms with the distance: far from the source, the sensors are only sensitive to the dipole. This property has been used in [START_REF] Bergervoet | A large-loop antenna for magnetic field measurements[END_REF][START_REF] Savi | Developing a Van Veen & Bergervoet Antenna[END_REF][6][START_REF] Pasmooij | A 'Helmholtz' large loop antenna system for improved magnetic field measurements[END_REF]. This lead to large measurement systems, and furthermore, the accuracy is poor: far from the Device Under Test, the field is low, and the signal is small. Thus, in the following section, the design of specific sensors will be proposed. Instead of employing the r -(n+1) behaviour, the aim is to use the geometrical properties of the spherical harmonics functions Y nm . This will be explained in the following section.

III. SENSOR DESIGN

To determine the 8 unknowns, a first idea may be to start from a set of several measurement points, using either a single measurement loop, or several ones. Then, a linear system can be solved to compute the 8 values from these multiple measurements, using inverse problem methods (error minimization or any other method). The advantage of this solution is the simplicity of the sensors, however, the convergence and final accuracy is not guaranteed, especially if the spatial sampling is not suitable (number and special position): the matrix condition number can often be very poor [START_REF] Rouve | Optimal magnetic sensor location for spherical harmonic identification applied to radiated electrical devices[END_REF].

We have chosen to use less sensors (8 to determine the 8 unknowns), but designed in order to give more robust information. The difficulty is to find a shape which is not sensitive to any other component than the one which has to be determined. To clarify our approach, we propose to detail the process of creating a B 10 sensor. Starting from the observation of the magnetic field created by a simple B 10 source (all A nm = 0 except A 10 , e.g. a dipole oriented along z axis), we look for the basic shape which maximizes the B 10 flux (Fig. 1). The result is obviously a simple loop, as presented in previous works [START_REF] Bergervoet | A large-loop antenna for magnetic field measurements[END_REF][START_REF] Savi | Developing a Van Veen & Bergervoet Antenna[END_REF][6]. Then, substituting to the B 10 source a more complex one, we try to define a new shape, more robust against the other terms of the field. This new source is obtained by imposing all A nm to 1, until n=4 (24 coefficients). This order has been considered sufficient for most of practical radiating systems, at reasonable distances (not too close). We try to define the position of a loop (or a combination of loops), which cancel all the other contributions of magnetic field. For various z position of a simple loop, it is clear from Fig. 2 that only 4 elementary magnetic fields among 24 bring a contribution to the flux. To cancel the odd components (B 20 and B 40 ), the idea is to use a second loop, symmetrical from the first one, as illustrated on Appendix. After composition of the two fluxes, only B 10 and B 30 remain. Choosing a proper distance between the two loops finally allows cancelling the contribution of B 30 (Fig. 2). This is obtained for a distance

5 2 ⋅ = = r R z
, where R is the radius of the loops and z the inter-loops distance. This geometry is exactly a Helmholtz coil [START_REF] Pasmooij | A 'Helmholtz' large loop antenna system for improved magnetic field measurements[END_REF].

In comparison with previous works [START_REF] Bergervoet | A large-loop antenna for magnetic field measurements[END_REF][START_REF] Savi | Developing a Van Veen & Bergervoet Antenna[END_REF][6] it is clear from Fig. 2 that this new sensor is far more robust versus parasitic components: a single loop in z=0 measures both B 30 and B 10 … Using the same method allows determining the shape of all other sensors (see Appendix):

• 1 st finding a generic shape to maximize the flux of the tracked component • 2 nd Modifying the geometry and combining several shapes to reject the other components

IV. FEM VALIDATION

To validate the method, a toroidal inductor has been used (5 cm diameter -Fig. 3). It corresponds to the common mode filter at the input of a variable speed drive. The aim is to determine the coefficient of the spherical harmonic decomposition. We have included the identification of the first and second order of the decomposition (all 8 sensors). Since we are looking for the field outside the variable speed drive, we identified the coefficients A 1m and A 2m outside a validity sphere of 30 cm radius, corresponding to the double of the size of the apparatus. The inductor is disposed at the center of the sphere. All tests have been carried out in a Finite Elements Software FLUX3D© [11].

a. A 1m identification and validation

The validation of the dipole identification is shown on Fig. 4. After identification including 1 or 2 orders, we compared the reconstructed magnetic field with the FEM results, from 1 m to 2 m. First, in all cases, the good concordance validates the 8 A 1m and A 2m values. Far from the source the difference is smallest since the dipole is preponderant. Second, the results confirm the interest to make identification until the second order: on Fig. 4, the convergence is better with the source including dipole and quadrupole.

b. Identification and robustness

First, we checked the robustness of the sensor to a change of radius r: three different sensors for three different measurement distances have been tested, the identification has been found very stable (less then 1% error). It confirms that it is not necessary to be far from the source to identify the dipole and quadrupole, contrary to the standard solution [START_REF] Bergervoet | A large-loop antenna for magnetic field measurements[END_REF][START_REF] Savi | Developing a Van Veen & Bergervoet Antenna[END_REF][6].

The second verification concerns the shifting of the inductor versus the center of the decomposition. This implies a more complex field (i.e. higher orders in the decomposition) [START_REF] Wikswo | Scalar multipole expansions and their dipole equivalents[END_REF]. Only dipole identification is concern by this phase. The results of FEM simulation show that an error on the dipole determination occurs. It is attributed to the contribution of B 5m (and B 7m …) terms in our sensor. However, the error is reasonable, and lower than using the standard antenna, since this latter is sensitive to B 3m and B 5m .

All these results are illustrated in Fig. 5. It shows the interest of using dedicated sensors, which are more robust than previous ones and than punctual measurements.

V. CONCLUSION

The spherical harmonic decomposition is an interesting method to synthesize a magnetic field, for EMC interaction studies for instance: the very compact representation is extremely attractive. To identify the components of the decomposition, it seems not convenient to use several punctual measurements. Therefore, we choose to develop dedicated sensors, In Future work, propagation effects in the decomposition may be added, and its influence on sensor design studied.

VI. APPENDIX

Figure 1 .

 1 Figure 1. Radial component of induction (T) for a B10 source.

Figure 2 .Figure 3 .Figure 4 .

 234 Figure 2. Flux induced in the loop sensor (radius 1 meter) as a function of z, for each component of B

Figure 5 .

 5 Figure 5. Comparison between Van Veen antenna and our sensor: relative error compared to the actual dipole. The dipole computation is achieved by summing the three components of the dipole:

*Work partially supported by Capes-Cofecub (Project 0568/07).