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
Paul Fisher <[log in to unmask]>
Reply To:
ECJ Evolutionary Computation Toolkit <[log in to unmask]>
Thu, 10 Mar 2011 18:14:57 +0000
text/plain (116 lines)
Thank you all for your replies, which are of great help and interest to 
me. My particular project is still in an early research stage, but now
a small step closer to realisation.


On 10/03/2011 10:33, David R White wrote:
> 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.
>> 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.
>> -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
>> [log in to unmask] <mailto:[log in to unmask]>
>> --------------------------------------------------