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