March 2011


Options: Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Robert Baruch <[log in to unmask]>
Reply To:
ECJ Evolutionary Computation Toolkit <[log in to unmask]>
Wed, 9 Mar 2011 11:56:25 -0500
text/plain (25 lines)
I, too, am interested in the answer to this question. 

In my own work, I've modified the crossover or mutation algorithm to explicitly generate valid individuals. For example, if a given element in a GA individual must be within a certain range, I could clip the value to the upper or lower limit if the value goes out of range.

GP has retries when it generates individuals that are too big -- it just tries again. If it can't generate a valid individual after a certain number of retries, it gives up and copies the parent.

On the other hand, sometimes you don't know that an individual is valid until you evaluate it. For example, perhaps an individual based on code will throw an exception. Then you just have to score that individual as very poor.


On Mar 9, 2011, at 11:33 AM, Paul Fisher wrote:

> Hello everyone
> This is a plea for help on a general point regarding the genetic algorithm method (rather than a technical ECJ issue).  I hope my question makes sense to someone who can point me in the right direction.
> Simply put, if you have a large solution space (c.9000 element matrix) with a set of constraints that make a large proportion of the possible solutions invalid, how do you treat invalid solutions generated by the reproduction process to ensure the population is composed of only (or mostly) valid solutions?  For example, what happens when you take two good solutions from the initial population, cross them over and mutate them according to some standard method, and the result is two solutions which happen to violate the constraints of the solution space and therefore render the new solutions invalid?  How can you take two good solutions and mate them in such a way to produce only valid solutions according to the problem constraints?
> The only way I have known how to treat invalid solutions so far is to tolerate them in the population but score them out of the selection process.  The problem with this is that 9 times out of 10 the population will be swamped by these duds and never get going.
> Any suggestions please folks?
> Thanks
> Paul