The fitting of curves in computer aided geometric design is generally regarded as an optimisation problem. According to the application, conditions to be satisfied can make the problem difficult to solve with classical methods. Stochastic ones, such as gen
Sliikk
Figure 2 : Curve deviation di calculation
By knowing these arc lengths and by applying the property of cubic typical curves concerning their arc lengthderivative, which we do not detail here (see [7]), it comes, at last, the curve point C(ui) location.
3.4. Generation of the initial population
A difficulty with genetic algorithm in a continuous optimization problem, we face with, is the large number ofpossible solutions, which can be generated within the search domain. In case of a too wide one, a risk thereforeexists by random sampling, unless to generate a great number of individuals, to not cover homogeneously thewhole solution space and consequently to converge to a local optimum. To avoid this, before generating theinitial population, we search to fit the search domain of each variable, according to some approximations and/orempirical rules. Thus, the initial tangent direction W0 and curvature 0 are estimated by means of a discrete shapeanalysis. The domain estimation for the other variables is, on the other hand and until now, empirically made.
3.5. Crossover and mutation operators
We have developed two crossover operators, respectively dedicated to the initial curve variables (W0, 0) and tothe shape segment variables ( k , k).The crossing consists here just in exchanging their initial variables values between two individuals. The shape segment variables values in the initial population , contrarily to the previous ones, are not necessarilyclose to good solutions. This is particularly the case for the k variables which determine the curve nodes locationand for which meaningful estimation is difficult. Therefore, we used a crossover operator which combines ( k , k) variables values and generates new ones. It proceeds according to a one point crossover method. A crossoverpoint s, 1 s m, is selected at random, as well as a weight w, 1/3 w 2/3. Given two individuals A and B :
(W0,A, 0,A), ( 1,A, 1,A) ... ( m,A , m,A) (W0,B, 0,B), ( 1,B, 1,B) ... ( m,B , m,B)
we generate two new individuals A’ and B’ with new segment variables ( k,A’ , k,A’) and ( k,B’ , k,B’) as :
if k s( k,A’ , k,A’) = w ( k,A , k,A) +(1- w) ( k,B, k,B) ,
( k,B’ , k,B’) = (1-w) ( k,B , k,B) + w ( k,A, k,A)
if k s( k,A’ , k,A’) = (1-w) ( k,A , k,A) + w ( k,B, k,B) ,
( k,B’ , k, B’) = w ( k,B , k,B) + (1-w) ( k,A, k,A)
The mutation operator, we use, proceeds in a classic way. After selecting at random an index within 0,m , weobtain a new individual by generating randomly a new value for either the (W0, 0) or a ( k , k) variables subset.
4. General algorithm and first results
We give here a global view on our algorithm, knowing that its development is still in progress.
Program Curve_Fitting_by_GA
Generate the initial population;Identify the best and the worst individuals;
While ( mean_fitness – best_fitness) > given threshold_value
Select randomly two individuals;Generate two new individuals by crossover and keep the best offspring;
If offspring_fitness < worst_fitnessThenMutate it according a given probability_rule;
Abstract Adaptive T-spline Surface Fitting to Z... Computational Geometry and Object Modeling—curve,...styling, NC machining, GIS, and computer vision....
Abstract Conceptual design in the automotive ...for a design application where creativity should ...The resulting 2D curve is projected back into 3D...
deforming 3d shapes in biomedical and styling ...Abstract In contrast to machined mechanical parts,... Computational Geometry and Object Modeling—Curve,...
deforming 3d shapes in biomedical and styling ...Abstract In contrast to machined mechanical parts,... Computational Geometry and Object Modeling—Curve,...
热门文档