Proceedings home preface contents authors keywords copyright reference ©2012 Civil-Comp Ltd				Paper 59 Handling Linear Constraints in Genetic Algorithms H.L. Pina1 and J.F.A. Madeira1,2 1IDMEC/IST-Instituto Superior Técnico, Lisbon, Portugal 2ISEL-Instituto Superior de Engenharia de Lisboa, Lisbon, Portugal Keywords: genetic algorithms, linear constraints, elimination methods, ill-conditioning. full paper (pdf) - reference Genetic algorithms lack a general methodology to handle constraints and several approaches have been tried. The best method is certainly to generate by proper encoding of legal individuals only, that is, individuals obeying all the constraints. This may be possible for simple constraints on the upper and lower bounds of design variables but becomes increasingly more difficult or 'next to impossible' for more complicated constraints. Two remedies can be attempted: development of repair mechanisms that modify infeasible individuals into feasible ones, an approach that tends to disrupt the normal performance of the genetic operators; or the design of suitable genetic operators (crossover and mutation) that maintain feasibility. The 'next to best' method relies on the transformation of the constrained problem into an unconstrained one by modifying the fitness function to include terms penalizing the violation of constraints; in this case the presence of illegal individuals can "pollute" the population and thereby slow the convergence process. Equality constraints pose additional and specific difficulties. As they effectively reduce the dimensionality of the problem, the penalization approach is inefficient since working in the full search space leads to much more fitness function evaluations then otherwise required. Therefore the best technique is to split the problem variables in two sets; the free or independent variables and the dependent variables. These are then expressed in terms of the free variables which are the ones exclusively "seen" by the genetic algorithm, that is, they are effectively "eliminated" from the genetic algorithm. In the present paper we focus on the problem of proper handling of equality constraints adopting the elimination approach bearing in mind that in many real life applications the linear set of constraints is generated automatically by some user program and one is not sure a priori if this set is linearly independent a fact that has to be checked and dealt with. Additionally, it may happen that the set of constraints is 'almost' linearly dependent thus making the problem ill-conditioned a difficulty that must be addressed in order to obtain meaningful results. We assess three elimination methods: the Gauss-Jordan elimination method, the orthogonal factorization method and the singular value decomposition as tools to identify the independent and dependent variables, examining both the well-conditioned (linear independence) and the ill-conditioned ('almost' linear dependence) cases. Some representative examples are presented and discussed.