Seems that your options are limited:
1. Punish infeasible individuals through fitness.
2. Prevent infeasible individuals from occurring by constraining
3. Prevent infeasible individuals from occurring by repeatedly applying
variation operators until a valid individual is generated.
4. Repair infeasible individuals after variation to change them into a
5. Define a representation such that every individual in your search
space is a feasible solution.
(2) or (5) are the most desirable to me, as the rest result in a
potential waste of compute power... although sometimes infeasible
solutions can be useful in constructing feasible ones.
On 09/03/11 17:56, J. Alejandro Zepeda Cortés wrote:
> Because a hard time constraint we choose to walk into the space of valid
> solutions specializing the classes for the crossover, mutation and
> initialization methods. In our problem, the individuals were complex and
> time consuming to build so we avoid to spend time building unfitted
> On Wed, Mar 9, 2011 at 2:30 PM, doranchak <[log in to unmask]
> <mailto:[log in to unmask]>> wrote:
> A while back, i was using a GA to evolve logic puzzles, and it
> created many invalid puzzles. But I didn't exclude invalid puzzles
> from the search, because I was afraid that they would include good
> building blocks for valid puzzles. So, my algorithm pulled error
> counts into the fitness function as a way to guide the invalid
> puzzles towards valid ones.
> I wonder if there is a good way to determine if a search is better
> or worse off by doing this.
> On Mar 9, 2011, at 11:56 AM, Robert Baruch wrote:
> > 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
> > 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.
> > --Rob
> > 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
> J. Alejandro Zepeda Cortés
> Ing. Civil Informático
> [log in to unmask] <mailto:[log in to unmask]>
Dr David R. White
Dept. of Computer Science
University of York,
Deramore Lane, YO10 5GH.