Hi Rud,
The fitness function looks reasonable to me.
I would probably not include BOOLEAN.RAND or the other RAND instructions for this problem, since you are presumably looking for a deterministic solution.
Your "purging" step seems potentially problematic to me. Usually in GP parents are selected in a random but fitness-proportionate way, e.g. via tournaments of size 2-7, which will usually mean that poorly-performing individuals have a low but non-zero chance of being parents. Maybe that specific issue (that below-average guys can't be parents) isn't a big deal, but I think the combination of this and the way you're selecting crossover parents -- randomly from the unpurged? -- might have some bad consequences.
There might be an issue if a lot of programs have exactly the average fitness. In that case if you're purging programs with strictly less than the average then you won't be purging very many, and since it this purging is the only way your population can progress, if you don't purge very many then it wouldn't be likely that you'd ever get better programs. On the other hand if you are purging programs with "less than or equal" the average fitness then you may be purging too many.
Another issue may be that among the top half there's no bias toward the better programs. In other words, if the top half includes a bunch -- let's say the top 10% -- that are really good then you'd like them to make more offspring than the others. But I don't think you are doing this.
The introduction of new completely random individuals in each generation is also non-standard... I can imagine that this might slow things down a bit, since your evolved population should soon be better than random and you should be introducing new genetic material via mutation.
I don't see any mention of mutation... That may also be a problem. If you're relying on new material coming in via new random individuals and then via crossover then that may not be happening if all of those new random individuals are purged before the crossover step.
As for maintaining parents in the next generation, normally "straight reproduction" is one of the ways in which "children" (here actually clones) can be made, so some number of good individuals (selected in a fitness proportionate way) will make it into the next generation. But this is normally not connected to whether or not they also served as parents, and it is normally a very small percentage of the population (less than 10%).
A lot may also depend on your population size, particularly since the ODD problem, having only single Boolean outputs for each case, has a fairly coarse fitness landscape -- that is, there aren't a lot of possible fitness values, so there aren't smooth fitness gradients for evolution to follow, and one generally has to compensate for this by sampling a large space of programs. I solve it pretty fast with my Clojush system with the default population size of 1000, but I don't know what you're using.
-Lee
On May 6, 2010, at 8:42 PM, Rud Merriam wrote:
> Hi Lee,
>
> My approach was similar. I modified your approach to do:
>
> -1000 if nothing on boolean stack
> 10 if correct value
> 0 if incorrect value
> sum these over the test values
>
> I'm testing values from 0 to 19 as cited in one of the papers. I plateau at
> values of 100. Those programs are using various techniques for generating a
> constant boolean value. The few times the value is above 100 is with a
> BOOLEAN.RAND instruction and those programs get tossed in the next
> generation.
>
> Let me describe the overall processing to see if that needs changing. I loop
> through:
>
> 1. Purge any program that has less than the average fitness of the
> population
> 2. Bring population up to 80% of maximum using crossover if population is
> larger than the tournament size
> 3. Complete the population with random programs
> 4. Run the program and record the fitness for each program
>
> One question is whether the parents should be retained in the next
> generation, which I am doing.
>
> - 73 -
> Rud Merriam K5RUD
> http://mysticlakesoftware.com/
>
>
>> -----Original Message-----
>> From: Lee Spector [mailto:lspector at hampshire.edu]
>> Sent: Thursday, May 06, 2010 5:24 PM
>> To: Rud Merriam
>> Cc: push at lists.hampshire.edu
>> Subject: Re: [Push] Advice on Fitness
>>
>>
>>
>> What are you using now?
>>
>> In my clojure version of the odd problem I use the code below
>> as the error function, which in English says try inputs 0, 1,
>> 2, 3, 4, 5, 6, 7, 8, 9, and for each push the input on the
>> integer stack and also make it available via an "in"
>> instruction (which pushes it on the integer stack -- I do
>> this via an auxiliary stack but that's just an implementation
>> detail), and then run the program and look at the top item of
>> the boolean stack at the end. If there's no item on top of
>> the boolean stack the error for that case is a penalty of
>> 1000. If there is an item then the error for that case is 0
>> if it's right for the input and 1 if it's wrong. The total
>> error ("fitness," for which lower is better) for the
>> individual is the sum of the errors for the 10 cases. I run
>> this with all of the implemented push instructions available,
>> the "in" instruction, and random positive integers less than 100.
>>
>> -Lee
>>
>>
>> (fn [program]
>> (doall
>> (for [input (range 10)]
>> (let [state (run-push program
>> (push-item input :auxiliary
>> (push-item input :integer
>>
> (make-push-state))))
>> top-bool (top-item :boolean state)]
>> (if (not (= top-bool :no-stack-item))
>> (if (= top-bool (odd? input)) 0 1)
>> 1000)))))
>>
>>
>> On May 6, 2010, at 5:27 PM, Rud Merriam wrote:
>>
>>> I have my PushX running with a crossover operation and
>> trying to solve
>>> the ODD problem, i.e. Boolean result if an integer is odd or even.
>>>
>>> I'm not having any success so I'm guessing my fitness test is not
>>> crafted properly. What would everyone suggest?
>>>
>>> - 73 -
>>> Rud Merriam K5RUD
>>> http://mysticlakesoftware.com/
>>>
>>> _______________________________________________
>>> Push mailing list
>>> Push at lists.hampshire.edu
>>> https://lists.hampshire.edu/mailman/listinfo/push
>>
>> --
>> Lee Spector, Professor of Computer Science
>> School of Cognitive Science, Hampshire College
>> 893 West Street, Amherst, MA 01002-3359
>> lspector at hampshire.edu, http://hampshire.edu/lspector/
>> Phone: 413-559-5352, Fax: 413-559-5438
>>
>> Check out Genetic Programming and Evolvable Machines:
>> http://www.springer.com/10710 - http://gpemjournal.blogspot.com/
>>
>>
>
> _______________________________________________
> Push mailing list
> Push at lists.hampshire.edu
> https://lists.hampshire.edu/mailman/listinfo/push
--
Lee Spector, Professor of Computer Science
School of Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector at hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438
Check out Genetic Programming and Evolvable Machines:
http://www.springer.com/10710 - http://gpemjournal.blogspot.com/