Searching the solution space in constructive geometric constraint solving with genetic algorithms

Searching the Solution Space in Constructive Geometric Constraint Solving with Genetic Algorithms R. Joan-Arinyo1, M.V. Luz´on2, A. Soto1 1Departament de Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya, Av. Diagonal 647, 8a, E-08028 Barcelona {robert,tonis}@lsi.upc.es 2Escuela Superior de Ingenier´ıa Inform´atica Universidad de Vigo, Av. As Lagoas s/n, E-32004 Ourense [email protected] May 28, 2002 Abstract Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. Generally, the user is only interested in one instance such that besides fulfilling the geometric constraints, exhibits some additional properties. Selecting a solution instanceamountstoselectingagivenrooteverytime the geometricconstraint solver needs to compute the zeros of a multi valuated function. The problem of selecting a given root is known as the Root Identification Problem. In this paper we present a new technique to solve the root identification problem. The technique is based on an automatic search in the space of solutions performedbya genetic algorithm. The user specifies the solutionof interest by defining a set of additional constraints on the geometric elements which drive the search of the genetic algorithm. The method is extended with a sequential niche technique to compute multiple solutions. A number of case studies illustrate the performance of the method. Keywords Genetic algorithms, Constructive geometric constraint solving, Root identification problem, Solution selection. 1 1 Introduction Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. Generally, the user is only interested in one instance such that besides fulfilling the geometric constraints, exhibits some additional properties. Selecting a solution instance amounts to selecting one among a number of different roots of a nonlinear equation or system of equations. The problem of selecting a given root was named in [7] the Root Identification Problem. Several approaches to solve the root identification problem have been reported in the literature. Examples are: Selectively moving the geometric elements, conducting a dialogue with the constraint solver that identifies interactively the intended solution, and preserving the topology of the sketch input by the user. For a discussion of these approaches see, for example, references [7, 9, 15, 30] and references therein. Adding extra constraints to narrow down the number of possible solutions to constraint geometric problems seems to be a simple approach. However, this approach has been carefully avoided by the field because the resulting over-constrained problem is NP hard. Moreover, the set of constraints may be contradictory, [7]. In this paper we present a new technique to solve the root identification problem by over-constraining the geometric constraint problem. The technique is based on an automatic search in the space of solutions performed by a genetic algorithm. The user specifies the intended solution instance by defining a set of additional constraints or predicates on the geometric elements which drive the search of the genetic algorithm. The approach has been implemented and the results are satisfactory, [30]. The basic technique is then extended with a niching method to locate and maintain multiple solutions. The outline of the paper is as follows. In Sections 2 and 3 we briefly review the basic concepts of constructive geometric constraint solving and genetic algorithms, respectively. Section 4 is devoted to the solution instance selector based on the genetic algorithm. The niche extension is presented in Section 5. As a proof of concept, we present in Section 6 some experimental results. Finally, Section 7 offers a summary and open questions for future work. 2 Constructive Geometric Constraint Solving In two-dimensional constraint-based geometric design, the designer creates a rough sketch of an object made out of simple geometric elements like points, lines, circles and arcs of circle. Then the intended exact shape is specified by annotating the sketch with constraints like distance between two points, distance from a point to a line, angle between two lines, line-circle tangency and so on. A geometric constraint solver then checks whether the set of geometric constraints coherently defines the object and, if so, determines the position of the geometric elements. 2 P3 P 1 P4 P5 d2 d1 P2 r a1 distance(P2, P3) = d2 distance(P1, P2) = d1 angle(segment(P2, P3), segment(P1, P2)) = a1 on(P3, circle(P4, r)) tangent(segment(P2, P3), circle(P4, r) tangent(segment(P1, P5), circle(P4, r)) on(P5, circle(P4, r)) Figure 1: Geometric problem defined by constraints. If geometric elements and constraints are like those above, a constraint-based design can be represented by a set of points along with a set of constraints drawn from distance between two points, distance from a point to a line, and angle between two lines, [33]. Figure 1 shows an example sketch of a constraint-based design. 2.1 A Formalization of the Geometric Constraint Problem It is well known that the relative position of ngiven points {p 1,p 2,... ,p n}in the bidimensional Euclidian space, are determined by 2n−3independent relationships defined between the points, [28, 29]. Based on this fact, the geometric constraint problem in the Euclidean space can be formalized as follows. First we assume that a given set of npoints, on which a set of 2n−3independent constraints has been defined, is split into two nonempty disjoint subsets. One subset,  p={p 1,p  2,... ,p  k}, contains all those given points with fixed position. The other subset, p ={p1,p 2,... ,p l}, contains all those points with unknown position. Notice that this decomposition is always possible because 2n−3 independent relationships between ngiven points define a rigid body with three remaining degrees of freedom, two of them corresponding to a translation and the third one corresponding to a rotation. Hence, the absolute position for at least one given point should be specified. Following Br¨uderlin [10], the set of constraints along with logical conjunction, disjunction and negation allow us to express the geometric constraint problem by a first order logic formula ϕ( p,p 1,... ,p l)such that if the set of constraints is well constrained, [16, 25], the formula ∃p1...∃plϕ( p,p 1,... ,p l) holds. By the axiom of choice, [10, 27], we can say that whenever the above formula holds, the formula ∃f1...∃flϕ( p,f 1( p),... ,f l( p)) also holds. Hence, the goal in solving a geometric constraint problem is to prove the truth of the above formula, and to evaluate the functions f 1,... ,f l. 3 As we show in the next Section, the constructive geometric constraint solving approach is such that given the geometric constraint problem ϕ( p,p 1,... ,p l)defined on the set points {p1,p 2,... ,p n}, searches a constructive first order logic formula, Ψ( p,p 1,... ,p l), such that, if the constraint problem is well constrained, will figure out the relative position of each point. If the predicate pos(p i,(xi,y i)) assigns the position (xi,y i) to point pi, an example of the constructive formula would be, [10], Ψ( p,p 1,... ,p l)=pos(p 1,(x1,y 1)) ∧...∧pos(p k,(xk,y k)) ∧pos(p1,(fx1( p),fy 1( p)) l  i=2 pos(pi,(fxi( p,p 1,... ,p i−1),fy i( p,p 1,... ,p i−1))) 2.2 Solving the Geometric Constraint Problem Many techniques have been reported in the literature that provide powerful and efficient methods for solving systems of geometric constraints. For example, see [11] and references therein for an extensive analysis of work on constraint solving. Among all the geometric constraint solving techniques, our interest focuses on the one known as constructive. Constructive solvers have two major components: the analyzer and the constructor. The analyzer symbolically determines whether a geometric problem defined by constraints is solvable. If the problem is solvable, the output of the analyzer is a sequence of construction steps each of them corresponding to a pair of functions (fx i,fy i)in the above first order logic formula which places each geometric element in such a way that all constraints are satisfied. This sequence is known as the construction plan. After assigning specific values to the parameters, the constructor interprets the construction plan and builds an object instance, provided that no numerical incompatibilities arise. Figure 2 illustrates the main components in a constructive geometric constraint solver. The specific construction plan generated by an analyzer depends on the underlying constructive technique and on how it is implemented. For example, the ruler-and-compass constructive approach is a well-known technique where each constructive step in the plan corresponds to a basic operation solvable with a ruler, a compass and a protractor. In practice, this simple approach solves most useful geometric problems. Figure 3 shows a construction plan for the object of Figure 1, generated by the ruler-and-compass geometric constraint solver reported in [26]. Function names in the plan are self explanatory. For example function adif denotes subtracting the second angle from the first one and asum denotes the addition of two angles while rc and cc stand for the intersection of a straight line and a circle, and the intersection of two circles, respectively. In general, a well constrained geometric constraint problem, [17, 25, 28], has an exponential number of solutions. For example, consider a geometric constraint 4 analyzer constraints sketch and construction plan instance solution constructor values parameters Figure 2: Basic architecture of constructive geometric constraint solvers. P1=point(0,0) P2=point(d1,0) α1=direction(P1,P 2) α2=adif(α1,a 1) P3=rc(line(P2,α 2),circle(P2,d 2),i 1) α3=direction(P2,P 3) α4=asum(α3,π/2) Q1=rc(line(P2,α 4),circle(P2,r),i 2) P4=rc(line(Q1,α 3),circle(P3,r),i 3) Q2=midpoint(P1,P 4) r1=distance(P1,Q 2) P5=cc(circle(P4,r),circle(Q2,r 1),i 4) Figure 3: Construction plan for the object in Figure 1. 5 d1 P1 Q d 2 P2 Q’ Figure 4: Possible placements of a point. problem that properly places npoints with respect to each other. Assume that the points can be placed serially, each time determining the next point by two distances from two already placed points. In general, each point can be placed in two different locations corresponding to the intersection points of two circles. See Figure 4. For npoints, therefore, we could have up to 2n−2solutions. Possible different locations of geometric elements corresponding to different roots of systems of nonlinear algebraic equations can be distinguished by enumerating the roots with an integer index. For a more formal definition see [15, 30]. In what follows, we assume that the set of geometric constraints coherently defines the object under design, that is, the object is generically well constrained and that a ruler-and-compass constructive geometric constraint solver like that reported in [26] is available. In this solver, intersection operations where circles are involved, rc and cc, may lead to up to two different intersection points, depending on whether the second degree equation to be solved has no solution, one or two different solutions in the real domain. With each rc and cc operation, the constructor in the solver associates an integer parameter, ik∈{−1,0,1}, which identifies whether there is no solution, one or two different solutions. For details on how to compute i k, the reader is referred to [24] and [34]. 3 Basic Background on Genetic Algorithms Evolutionary algorithms which model natural evolution processes were already proposed for optimization in the 1960s. The goal was to design powerful optimization methods, both in discrete and continuous domains, based on searching methods on a population of coded problem solutions, [8]. 3.1 Generalities Depending on the constructive search operations on which the algorithm is built, two families of evolutionary algorithms can be distinguished: evolution strategies and genetic algorithms. [8, 36]. An evolution strategy is a random search which uses selection and variation, [3, 37]. The selection operator determines those individuals in the population that survive to participate in the production of the next 6 population. Selection is based on the value of the fitness function, or the fitness of individual members of the population, such that members with greater fitness levels tend to survive. The variation operator, called mutation, introduces some sort of modification in the population members and prevents the search of the space from becoming too narrow. Evolution strategies model natural evolution by asexual reproduction with mutation and selection. Genetic algorithms, invented by Holland, [23], aresearch algorithms that model sexual reproduction which is characterized by recombining two parent strings into an offspring. This recombination is called crossover. Crossover recombines traits of the selected individuals in the hope of producing a child with better fitness levels than its parents. Crossover is accomplished by swapping parts of strings representing two individuals in the population. The use of genetic algorithms has been instrumental in achieving good solutions to discrete problems that have not been satisfactorily addressed by other methods, [18]. Recent surveys can be found in [1] and [18]. 3.2 The Root Identification as a Constraint Optimization Problem In the technique presented in this work, the Root Identification Problem is solved by over constraining the geometric constraint problem: The intended solution instance to a well constrained problem is specified by defining a set of additional constraints or predicates on the geometric elements. An example of extra constraint currently available to the user is defined as PointOnSide(P,line(Pi,P j), side) which means that point Pmust be placed on one of the two open half spaces defined by the straight line through points Pi,P j, oriented from Pito Pj. Parameter side takes values in {right, left}. The resulting over-constrained problem is NP hard and one cannot expect that an effective classical deterministic search algorithm can be devised to solve it, [31]. Moreover, the set of constraints may be contradictory, [7]. Genetic algorithms have proven to be an effective technology for solving general constraint-satisfaction problems, when they are expressed as constraint optimization problems, [2, 14]. In this Section we transform the Root Identification Problem by over-constraining the geometric constraint problem into a constraint optimization problem suitable to be solved by a genetic algorithm. Recall that we consider ruler-and-compass constructive geometric constraint solving. In this context, geometric operations correspond to quadratic equations, thus each constructive step has at most two different roots. Let ijdenote the integer parameter associated by the solver with the j-th intersection operation, either rc or cc, occurring in the construction plan. Since we are interested only in solution instances that actually are feasible, that is, solution instances where no numerical incompatibilities arise in the constructor, we only 7 need to consider integer parameter ijtaking value in Dj={0,1}, where 0stands for the first solution and 1stands for the second different solution. Assume that nis the total number of rc plus cc intersection operations in the construction. We define the index associated with the construction plan as the ordered set I={i1,... ,i j,... ,i n}with ij∈Dj,1≤j≤n. Therefore the cartesian product of sets I=D1×...×Dndefines the space the solution instances to the geometric constraint problem belong to. A construction plan which is solution to a geometric constraint problem can be seen as a function of the index I. Let Ψ(I)denote the construction plan expressed as the corresponding constructive first order logic formula defined in Section 2.1. Clearly, the set of indexes {I∈I|Ψ(I)=true}is the space of feasible indexes, that is the set of indexes each defining an instance which actually is solution to the geometric constraint problem. This set of indexes is the allowable search space, [14]. Let Φdenote first order lolgic formula defined by conjunction of the extra constraints given to specify the intended solution instance. Let fbe a (possibly realvalued) function defined on Ψ(I)∧Φwhich has to be optimized. Then, according to Eiben and Ruttkay, [14], the triple <I,f,Ψ(I)>defines a constraint optimization problem where finding a solution means finding an index Iin the allowable search space with an optimal fvalue. 4 The Genetic Algorithm for the Root Identification Once the Root Identification Problem by over-constraining the constraint problem has been transformed into a constraint optimization problem, the usual machinery in genetic algorithms can be applied to find a solution. In what follows we will use the terms solution instance and intended solution instance.Asolution instance to the geometric constraint problem is an index Iin the allowable search space where the Boolean formula Ψ(I)holds, that is, an index which actually is solution to the geometric constraint problem. An intended solution instance to the geometric constraint problem is a solution instance for which all the extra constraints hold, that is, the Boolean formula Φ holds. 4.1 The Genetic Algorithm The genetic algorithm we have implemented is given in Figure 5. Pis the population of indexes at the current generation. It consists on a fixed, given number of indexes in I. The main components of the genetic learning process are described as follows. 8 Procedure GeneticAlgorithm INPUT F: Functions in the construction plan. C: Values actually assigned to the constraints. R: Set of extra constraints. ng : Maximum number of generations allowed. OUTPUT I: Index selected. InitializeAtRandom (P) Evaluate(P, F, C, R) I = SelectCurrentBestFitting (P) while not TerminationCondition (ng,I,R)do Selection (P) Crossover (P) Mutation (P) ApplyElitism (P, I) Evaluate(P, F, C, R) I = SelectCurrentBestFitting (P) ng =ng −1 endwhile return I EndProcedure Figure 5: Genetic algorithm. 9 Procedure MultiSeleccion INPUT F: Functions in the contruction plan. R: Set of extra constraint. C: Values actually asigned to the constraints. ng : Maximum number of generations allowed. ns : Number of solutions requested. α: Power factor. r: Niche radius. OUTPUT L: List of indexes of the solutions instances. L=∅ do L=L+ MultiGenetic(F, C, R, ng, r, α,L) ns=ns-1 while (ns =0) return L EndProcedure Figure 11: Multi-selection algorithm. We consider the geometric constraint problem shown in Figure 13 consisting of 18 points, 18 straight segments, 18 point-point distance constraints and 15 angle constraints. The potential number of solution instances is bounded by 2 16 = 65,536. The construction plan has 16 operations where a root has to be chosen. Therefore each index included 16 binary units. The intended solution instance was defined by a set including 27 extra constraints like PointOnSide(P1,line(P2,P 3),right) PointOnSide(P2,line(P3,P 4),left) ... PointOnSide(P18,line(P1,P 2),right) To check the algorithm behaviour we have carried out an exhaustive evaluation of the number of extra constraints fulfilled by a number of different solution instances selected by the basic genetic algorithm. The interest was on solution instances with fitness values close to the optimal. The results are shown in Table 1. The first raw shows the number of extra constraints defined to select the intended solution instance and the second raw shows howmany different solution instances fulfill them. Notice that the problem is really sparse. We discuss first the results yielded by the basic genetic algorithm, then those corresponding to the multiselection genetic algorithm. 16 Procedure MultiGenetic INPUT F: Functions in the contruction plan. C: Values actually asigned to the constraints. R: Set of extra constraints. ng : Maximum number of generations allowed. r: Niche radius. α: Power factor. L: List of indexes of the solutions instances. OUTPUT I: Selected index. VARIABLES P: Population. InitializeAtRandon(P) EvaluateP(P, F, C, R, r, α,L) doI = SelectCurrentBestFitting(P) Selection(P) Crossover(P) Mutation(P) ApplyElitism(P,I) EvaluateP(P, F, C, R, r, α,L) ng = ng - 1 while (not TerminationCondition(ng, I, R)) return SelectCurrentBestFitting(P) EndProcedure Figure 12: Modified genetic algorithm. # Extra constraints 27 26 25 24 23 # Solutions 2 0 14 24 102 Table 1: Number of extra constraints and number of different solution instances that fulfill them. 17 d16 d17 d1d5d9d13 d14 d3d7d11 a15 d2 a2a4 a3a5a6 a7 d6 d8 d10 a12 a13 a9 d18 d15 d4 a8 a10 a11 d12 a14 a1 Figure 13: Geometric problem defined by constraints. Case study A. 6.1 Basic Genetic Algorithm According to M¨uhlenbein, [37], five parameters are, at least, required to describe the initial state and the evolution of an artificial population of a genetic algorithm: Population size, length of the string representing individuals, initial configuration of values in the strings, mutation rate and selection law. Investigating the behaviour of the genetic algorithm with all five parameters variable would be hard to accomplish, therefore we have investigated a simpler model. The expected number of offspring to be allocated to the worst index was μmin =0.75. The crossover and mutation probabilities were always 0.6 and 0.2, respectively, [21]. We considered populations with 25, 30, 35 and 40 individuals. To assess the effect of the population size and selection method on the algorithm convergence, for different population sizes, we recorded the number of extra constraints fulfilled by the individual in the population with the best fitness versus the number of generations. The experiment was conducted first applying linear ranking selection and then proportional selection. Figure 14 shows the results yielded by the algorithm for the linear ranking selection. The algorithm convergence shows an exponential answer pattern, as expected for a natural system fed with an step input, defined by the initial population, [38]. After 30 generations, an steady state has been always reached and when the population has 30 individuals or more the individual selected as solution fulfills all the extra constraints. Figure 15 shows the results yielded by the algorithm using proportional selec18 0 5 10 15 20 25 30 010 20 30 40 50 60 Extra Constraints Fulfilled Number of generations 25 individuals ♦ ♦♦ ♦♦♦♦♦♦♦♦♦♦♦♦♦♦ ♦ 30 individuals + +++ ++ ++ + ++++++++ + 35 individuals         40 individuals ×× ×× ×× ×× × ×××××××× × Figure 14: Linear Ranking Selection. tion. Two effects can be noticed. One is that now larger populations, 35 or more individuals, are needed to select an individual which verifies all the extra constraints. The other is that, for the population with 40 individuals, premature convergence due to super individuals selected by the proportional mechanism occurred at early stages, [20, 19]. In this example, the super individual selected fulfills the set of extra constraints. However, premature convergence narrows down the search range and very often makes the algorithm to fail in finding an individual with global optimal fitness. This effect is further illustrated in Figure 16. It shows the results yielded by the algorithm fed with an initial population including 40 individuals different from those used to generate the results in Figure 15. Notice that the linear ranking selection still finds an individual with global optimal fitness. To study the performance of our basic genetic algorithm, we applied it to a number of different geometric constraint problems. Table 2 summarizes the results from six different experiments selected among those reported by Luz´on in [30]. The first column in Table 2 shows the number of multi valuated functions in the n# # Extra # Solution # Indexes % Indexes constraints instances Evaluated 7 12 6 2761 50 10 20 12 210 110 10.7 11 30 13 211 157 7.6 16 40 27 216 561 2 18 40 39 218 534 0.3 20 50 39 220 1663 0.1 Table 2: Performance of the genetic algorithm. 19 0 5 10 15 20 25 30 010 20 30 40 50 60 Extra Constraints Fulfilled Number of generations 25 individuals ♦ ♦♦♦ ♦♦ ♦♦ ♦ ♦♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ 30 individuals + +++ ++ +++++++++++ + 35 individuals       40 individuals × ××× ×× ×× × ×× × × × × × × × Figure 15: Proportional Selection. 0 5 10 15 20 25 30 010 20 30 40 50 60 Extra Constraints Fulfilled Number of generations Linear Ranking ♦♦♦♦ ♦♦ ♦♦ ♦ ♦♦ ♦ ♦♦ ♦♦♦ ♦ Proportional Selection + +++ ++ ++ + ++ + + + + + + + Figure 16: Premature convergence using proportional selection. 20 d1 tg2 r tg1 d2 d3 d4 d5 a2 a1 Figure 17: Geometric problem defined by constraints. Case study B. construction plan. The second column is the number of indexes included in the population. The third column gives the number of extra constraints defined to select the intended solution. The fourth column is the number of indexes in the search space. The fifth column shows the number of indexes actually evaluated by the algorithm. The last column is the ratio between the figures in the fifth and fourth columns. Data in the raw with n=16corresponds to the case study already considered and illustrated in Figure 13. Data in the first raw corresponds to the problem shown in Figure 17 consisting of 6 points, 5 straight segments, and a fixed radius arc of circle. The constraints were 5 point-point distances, 2 angles and 2 tangencies. The construction plan has 7 operations where a root has to be chosen. Thus each index included 7 binary units. The potential number of solution instances is bounded by 2 7= 128. Data in the raw with n=20corresponds to the problem shown in Figure 18. The problem has 22 points and 22 straight segments. The set of constraints includes 22 point-point distances and 19 angles. The construction plan includes 20 operations where a root has to be chosen. Therefore each index included 20 binary units. The potential number of solution instances is bounded by 2 20 and an exhaustive computation shows that only 3 of them verify the 39 extra constraints defined. As illustrated in Table 2, the results yielded by our benchmark, [30], show that in all cases the number of indexes actually evaluated by the basic genetic algorithm is a small fraction of the whole search space. Moreover, the ratio between search space size and the number of individuals actually evaluated decreased for increasing search space size. The number of extra constraints fulfilled after six generations was always higher than 66%. As expected in a behaviour that models a natural process, in all cases the number of extra constraints fulfilled by indexes in the current population increased exponentially until reaching an steady state. In general, about 30 generations were 21 d1 d3 d5 d7 d8 d11 d12 d15 d21 d22 a19 a1d20 a17 d2 d4 a4d6 a5 d9 a8 a7 a6 d10 a9a10 a11a12 d13 d14 a13 a14 a15 d19 d18 d17 d16 a18 a16 a2 a3 Figure 18: Geometric problem defined by constraints. Case study C. 22 # Extra Constraints # Solution instances requested fulfilled 1 2 3 4 5 6 7 8 27 1 2 2 2 2 2 2 2 25 – – 1 1 2 3 4 5 24 – – – – – – – – 23 – – – 1 1 1 1 1 Table 3: Performance of the multi-selection genetic algorithm. needed to find a solution. Therefore, the algorithm showed a great efficiency, [12]. Whenever the number of individuals in the population was equal or greater than the number of multi valuated functions in the construction plan and the selection mechanism was linear ranking, the individual selected at the stationary state was a global optimal, fulfilling all the required extra constraints. This means that the algorithm effectivity is optimal, [12]. 6.2 Multi-selection Genetic Algorithm To illustrate how the multi-selection algorithm works, we consider again the example in Figure 13. According to Table 1, there are only two indexes which fulfill the set of extra constraints. Therefore, one can expect that when the number of solution instances required is greater than two, some of the extra constraints will not hold for some solution instances selected by the multi-selection algorithm. Recall that, in the example at hand, the number of operations where a root should be chosen is 16. The maximum distance between two solution instances occurs when all the corresponding pairs of indexes are different. Thus the maximum distance in the search space is dmax =16. The ratio used to compute the niche radius was rs=0.1, that is, two indexes are considered to belong to the same niche if they differ at most in a 10% of their components. Therefore the niche radius was r=rsdmax =1.6. The power factor used was α=1, that is the linear function. The multiselection genetic algorithm was applied with a requested number of solutions ranging from 1 to 8. Table 3 summarizes the results. When the number of different instance solutions requested was one or two, all the solution instances selected by the algorithm show an optimal fitness and fulfill the 27 extra constraints. As expected, when the number of requested solutions was three or more, some of the selected solutions do not fulfill all the extra constraints. For example, when requesting 4 different solution instances, two of them verify 27 extra constraints, one verifies 25 extra constraints and only 23 extra constraints hold for the last solution instance selected. Notice that the two existing optimal solution instances are always selected. Also notice that instance solutions fulfilling only 23 extra constraints are selected 23 whereas no solution fulfilling 24 is returned by the algorithm. A rational for this behaviour is that no specific search technique to try to escape from local optimal fitness is currently included in our implementation. 7 Summary and Future Work In this paper, we have presented a new technique to efficiently search the solution space in two-dimensional constructive geometric constraint solving problems. The technique is based on a genetic algorithm which searches a solution in a potentially exponential large space of solution instances. The user defines the properties of the intended solution by adding a set of extra constraints which are used to drive the genetic algorithm in the search through the space of solution instances. The approach has been implemented on top of an already developed rule-based constructive geometric constraint solver and has been applied to a number of case studies. The results show that the technique performance is efficient and effective. Extending the basic genetic algorithm with the sequential niche method has proved to be a convenient way to select multiple solutions requested by the user. We have built our prototype on top of an already existing ruler-and-compass geometric constraint solver where multivaluated functions have at most two different values. However, the method applies to any constructive solving technique where the construction plan is explicitly generated, all what is needed is to extend the domain where indexes take values and to properly adapt the genetic operators. Applying genetic algorithms to search the space of solution instances in constructive geometric constraint solving has shown a promising potential. To explore this potential, we plan to further study genetic algorithms following two directions. One is to consider new types of extra constraints and the other one includes to conduct experiments to identify optimum values for number of individuals in the population, and crossover and mutation probabilities in geometric constraint solving. Acknowledgements This research has been partially supported by CICYT under the project TIC20012099-C03-01. References [1] In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, CA, 1993. Morgan Kaufmann. [2] T. B¨ack, D.B. Fogel, and Z. Michalewicz, editors. Handbook of Evolutionary Computation. Institute of Physics Publishing Ltd and Oxford University Press, 1997. 24 [3] T. B¨ack and H.P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1:1–24, 1993. [4] J. E. Baker. Reducing bias and inefficiency in the selection algorithm. Proc. Second International Conference on Genetic Algorithms (ICGA’87), pages 14–21, 1987. [5] D. Beasly, D.R. Bull, and R.R. Martin. A sequential niche technique for multimodal function optimization. Evolutionary Computation, 1(2):101–125, 1993. [6] L.B. Booker, D.B. Fogel, D. Whitley, and P.J. Angeline. Recombination. In T. B¨ack, D.B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, chapter C3.3, pages C3.3:1–C3.3:10. Institute of Physics Publishing Ltd and Oxford University Press, 1997. [7] W. Bouma, I. Fudos, C. Hoffmann, J. Cai, and R. Paige. Geometric constraint solver. Computer Aided Design, 27(6):487–501, June 1995. [8] H.J. Bremermann, J. Roghson, and S. Salaff. Global properties of evolution processes. In H.H. Pattee, E.A. Edelsack, L. Fein, and A.B.Callahan, editors, Natural Automata and Useful Simulations, pages 3–42. Macmillan, 1966. [9] L. Brisoux-Devendeville, C. Essert-Villard, and P. Schreck. Exploration of a solution space structured by finite constraints. In ECAI 14th European Conference on Artificial Intelligence. Workshop on Modelling and Solving Problems with Constraints, pages F:1–18, Berlin, August 2000. [10] B.D. Br¨uderlin. Rule-Based Geometric Modelling. PhD thesis, Institut f¨ur Informatik der ETH Z¨urich, 1988. [11] C. Durand. Symbolic and Numerical Techniques for Constraint Solving. PhD thesis, Computer Science, Purdue University, December 1998. [12] A. Eiben, P.-E. Rau´e, and Zs. Ruttkay. GA-easy and GA-hard constraint satisfaction problems. In M. Meyer, editor, Constraint Processing, LNCS Series 923, pages 267–284. Springer-Verlag, Heidelberg, 1995. [13] A.E. Eiben and Zs. Ruttkay. Self-adaptivity for constraint satisfaction: Learning penalty functions. In Third IEEE World Conference on Evolutionary Computation, pages 258–261, Nagoya, Japan, 1996. IEEE Service Center. [14] A.E. Eiben and Zs. Ruttkay. Constraint-satisfaction problems. In T. B¨ack, D.B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, chapter C5.7, pages C5.7:1–C5.7:5. Institute of Physics Publishing Ltd and Oxford University Press, 1997. 25