## ECJ-INTEREST-L@LISTSERV.GMU.EDU

 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 >>]

 Subject: Re: Help on a general GA issue From: David R White <[log in to unmask]> Reply To: ECJ Evolutionary Computation Toolkit <[log in to unmask]> Date: Thu, 10 Mar 2011 10:33:17 +0000 Content-Type: text/plain Parts/Attachments: text/plain (114 lines)
```Seems that your options are limited:

1. Punish infeasible individuals through fitness.
2. Prevent infeasible individuals from occurring by constraining
variation operators.
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
feasible solution.
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.

David

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
> individuals.
>
>
>     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.
>
>     -Dave
>
>     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
>     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.
>      >
>      > --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
> +56-9-98184077