From: ted.dunning@gmail.com   
      
   On Nov 2, 1:38 am, jackie  wrote:   
   > On Oct 31, 4:09 pm, Tim Frink  wrote:   
   > > algorithm that finds the best combination for the values of a, b, c   
   > > with the constraint that the sum of all values is not larger than 200.   
   >   
   > > A normal GA would try to find a good solution, like a=b=c=100. But   
   > > this would violate the constraint of sum <= 200.   
   >   
   >   
   > Do you have to use GA? you problem sound more like linear programming   
   > problem. GA can also solve the problem, for example, you can add a   
   > penalty in your fitness function.   
   >   
      
   If combination means sum, then this is, indeed, just linear   
   programming.   
      
   If combination means arbitrary smooth function, then GA's are still   
   probably not the best way to solve the problem since you are dealing   
   with presumably continuous values.  There are better function   
   optimization methods.   
      
   The standard hack to solve constrained problems with function   
   optimization is to adjust your fitness function to include the   
   barrier.  There are many ways to do this.  One is to have a function   
   that is 0 where-ever the constraint is satisfied and increases as the   
   violation of the constraints becomes more severe.  It is nice to have   
   a parameter that governs how sharply and how suddenly the increase   
   is.  You can anneal on this parameter to get a limiting program where   
   the fitness function increases to a very large value right at the   
   constraint.  For your program, you can   
      
       f(a,b,c) = 0                           if a + b + c <= 200   
       f(a, b, c) = k*(a+b+c-200)    if a+b+c > 200   
      
   As k -> infinity, you get the desired barrier function.  You could   
   also use an exponential here to get nice derivatives but that tends to   
   leave you with an unpleasant incursion of the barrier into the   
   feasible region.   
      
   Without more knowledge other than an answer to the question about   
   linear programming, I would just use Nelder-Mead simplex descent on   
   your original fitness function plus a barrier.  If your fitness   
   function is very multi-modal, then I might opt for a meta-evolutionary   
   algorithm, but I would avoid classical GA's without meta-mutation.  I   
   don't see much value for a cross-over operator here.   
      
   [ comp.ai is moderated ... your article may take a while to appear. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)