March 2011


Options: Use Proportional 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
adil raja <[log in to unmask]>
Reply To:
ECJ Evolutionary Computation Toolkit <[log in to unmask]>
Wed, 9 Mar 2011 09:38:06 -0800
text/plain (76 lines)
This is a very good idea, but it may make the whole algorithm hefty.

Best Regards,
Adil Raja

----- Original Message ----
From: doranchak <[log in to unmask]>
To: [log in to unmask]
Sent: Wed, March 9, 2011 6:30:27 PM
Subject: Re: Help on a general GA issue

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