[Cs254f11] length of individual thoughts...
Lee Spector
lspector at hampshire.edu
Fri Dec 2 23:46:39 EST 2011
I'm not sure what those outputs from your runs mean. Are the sizes program sizes or tournament sizes?
Clock times (msecs) may not be particularly meaningful for a variety of reasons ranging from machine architecture to system load.
Generally what one wants to measure is either the "computational effort to produce a solution (error = 0)" or "mean best fitness" over a bunch of runs in one condition (e.g. trivial geography with a particular radius) vs. the same thing over a bunch of runs in another condition (e.g. no trivial geography). In your case, since you're not getting solutions (error = 0), you probably want to look at the mean best fitness in a couple of conditions -- that is, record the best fitness from each run and average this across a bunch of runs (yes, maybe 20 per condition is a good number to shoot for, although we often do 50 or 100). As for the conditions, maybe they'd be "no trivial geography", "trivial geography with radius 10" and "trivial geography with radius 20", or something along those lines.
On the double tournament thing -- I haven't ever worked with that idea myself and I'm not sure what would make the most sense, but I don't think it's crazy to do it within a relatively small neighborhood. For example, if you have a radius of 10 the there are 21 individuals to choose from. If you select, say, 5 based on fitness with tournaments of 5, and then pick the smallest of those, then you'd end up picking someone who is among the fittest and the smallest, but maybe not the very fittest or the very smallest... but maybe this would still be reasonable. Another idea is to pick randomly from among the "Pareto non-dominated", which means from the set of individuals for which nobody else is BOTH fitter AND smaller.
-Lee
On Dec 2, 2011, at 8:17 PM, Wm. Josiah Erikson wrote:
> Hm. It could be rough to get enough variation to make the double tournament meaningful if you're pulling 7 tournaments worth of individuals from the same location and then having a tournament from those tournament winners... I mean, if you're doing crossover between two individuals that have to come from the same neighborhood, I'm not sure how else you'd do it. Maybe I'm missing something (probably!)
>
> Anyway, I've got a function set up that does some benchmarking runs to see if trivial geography helps in my case. When you run it, it looks like this, for instance:
>
> (time (time_test 100 10 3))
> ..........."Elapsed time: 6580.808 msecs"
> Run 0 : error 17 , size 5
> ..........."Elapsed time: 21111.225 msecs"
> Run 1 : error 17 , size 3
> ..........."Elapsed time: 24018.463 msecs"
> Run 2 : error 16 , size 5
> ..........."Elapsed time: 24155.432 msecs"
> Run 3 : error 15 , size 7
> Benchmarking runs complete. Average error: 16 Average size: 4
> This was over 3 runs of 10 generations with a population size of 100
> This is the version that implements trivial geography
> "Elapsed time: 75959.035 msecs"
> nil
>
> Is this the kind of data that is useful? What other data should I gather if not? I was thinking population size 1000, 20 runs, 50 generations. What do you think? Should I keep track of it if it finds a solution in less than the specified number of generations?
>
> -Josiah
>
> On 12/2/11 6:00 PM, Lee Spector wrote:
>> You could do local neighborhood tournaments based on fitness and then a size-based tournament among the ones that won the fitness tournaments. Or the other way around, I guess. So the winners would have been filtered by both criteria, in sequence, but everyone would have to come from the same local area originally. The main idea of geography is that the production of offspring for a particular location can only "see" parents in that location's neighborhood. Implementing various schemes is another issue, however, and there would be various approaches...
>>
>> I'm not sure if anyone has tried probabilistic lexicographic parsimony pressure (!).
>>
>> -Lee
>>
>> On Dec 2, 2011, at 5:47 PM, Wm. Josiah Erikson wrote:
>>
>>> Hehe, yes I *do* see why your research group eats up all of the cluster's cycles :)
>>> Thanks for the tips on running stuff from the command line - I might try it later on if it seems necessary to use more than just my laptop this weekend.
>>> I was thinking about it on the way home some more, and I can't see how double tournament would work in any sensible way with trivial geography. If one (the other one being the other way around) idea of double tournament is that you have a tournament (based on fitness) of individuals that are already winners of other tournaments (based on size), then where would the geography get implemented? I suppose you could implement the geography at the size tournament level, but that doesn't then accomplish what geography is supposed to accomplish, which is that the final tournament winners are picked from a tournament of individuals that are local to each other... right?
>>>
>>> Then I was thinking about modifying my lexicographic parsimony pressure routine so that it would have x chance of putting a smaller individual first if its error was the same. Maybe that has a name. I no longer have the paper in front of me. But it would work with trivial geography.
>>>
>>> Anyway, I'll do some preliminary runs to figure out if trivial geography helps in my use-case. That's easy enough. As you say, I don't know if I'll be able to do enough runs to be statistically significant, but the results might at least be interesting.
>>>
>>> -Josiah
>>>
>>>
>>>
>>> On 12/2/11 4:05 PM, Lee Spector wrote:
>>>> Now you see how my research group eats up all of the cluster's cycles :-).
>>>>
>>>> I do not know how any bloat control methods would interact with trivial geography, and I for one would like to know! In fact I'd be interested in knowing even just how trivial geography works on your problem regardless of bloat control. If tests clearly show an effect then that would be cool, but I wouldn't extrapolate too much from a small number of runs and it may be necessary to do some stats on the results to see what's going on. We can talk about details of that, depending on what kinds of results you get.
>>>>
>>>> You can run your code from a linux command line in a couple of ways. Probably the sanest would be to use leiningen, which should work the same way under any OS, taking care of classpaths etc so that you can have the same directory structures, etc. But out of inertia I currently run my linux stuff by putting all of my files in the same directory and executing something like:
>>>>
>>>> java -Xmx8000m -XX:+UseParallelGC -cp ./*:./src/ clojure.main -i core.clj | tee out
>>>>
>>>> Those initial flags are for big memory allocation and parallel garbage collection, which I found helped when doing lots of concurrent threads on high-core-count machines... The "tee" is to spool output to a file and also the screen. For this to make my code run immediately in my core.clj I have a -main function:
>>>>
>>>> (defn -main
>>>> [& args]
>>>> (evolve) ;; or whatever your top-level call is
>>>> ;(System/exit 0) ;; uncomment if you want it to quit when it's done
>>>> )
>>>>
>>>> The reason that this is called "-main" rather than just "main" is somewhat obscure to me, but here's an explanation I found on stackoverflow: "The default for gen-class is to use - as the prefix for method names of that class. Which is why -main is the default entry point for java -cp clojure.jar yourclass".
>>>>
>>>> I guess you could just call your top-level functions from the repl instead, but that's what I do in my workflow...
>>>>
>>>> -Lee
>>>>
>>>>
>>>>
>>>> On Dec 2, 2011, at 3:35 PM, Wm. Josiah Erikson wrote:
>>>>
>>>>> Absolutely. The article just told me that, too. If I have time this weekend, I will do runs of populations of 1000, 50 generations (I would do larger populations and more generations if I had the horsepower, but I absolutely don't) with the following variations:
>>>>>
>>>>> -with and without trivial geography
>>>>> -with no bloat control, with lexicographic parsimony pressure, and with double tournament
>>>>>
>>>>> Do you have any idea how those bloat control methods interact with trivial geography, if at all? Is that an interesting thing to find out?
>>>>>
>>>>> Can I take clooj code and run it on the command line with clojure under linux?
>>>>>
>>>>> -Josiah
>>>>>
>>>>>
>>>>>
>>>>> On 12/2/11 3:24 PM, Lee Spector wrote:
>>>>>> Cool.
>>>>>>
>>>>>> What you want to avoid, however, and what you might not be able to tell if you're avoiding without doing lots of runs in different conditions, is getting smaller programs but also not finding the really good programs that you could get in other conditions. Sometimes the best programs are big, and sometimes even if they're small evolution can find them more effectively if it's allowed to generate bigger programs along the way. E.g. it might require a big program to be variable in ways that can be varied, by evolution, to produce a good result, even if the same result can be produced by a simpler program.
>>>>>>
>>>>>> -Lee
>>>>>>
>>>>>>
>>>>>> On Dec 2, 2011, at 3:18 PM, Wm. Josiah Erikson wrote:
>>>>>>
>>>>>>> Here's something that clearly shows the effects of lexicographic parsimony pressure (this is with a population size of 2000):
>>>>>>>
>>>>>>> Generation: 29
>>>>>>> Best error: 9
>>>>>>> Best program: (pmod (prem (prem percent_in_mixolydian (min (min average_velocity percent_in_pentatonic) (max percentage_of_pitchbend percent_in_blues))) (min (+ (pmod (prem (prem percent_in_mixolydian (min (min average_velocity percent_in_pentatonic) (max percentage_of_pitchbend percent_in_blues))) (min (+ 40 (pd 47 high_note)) (prem percent_in_pentatonic percent_in_lydian))) std_dev_mostcom) percentage_of_percussion) average_velocity)) std_dev_mostcom)
>>>>>>> Median error: 19
>>>>>>> Average program size: 8.0525
>>>>>>> Generation: 30
>>>>>>> Best error: 9
>>>>>>> Best program: (min (prem percent_in_pentatonic 11) (pd (min (min percent_in_pentatonic high_note) percent_in_lydian) std_dev_mostcom))
>>>>>>> Median error: 19
>>>>>>> Average program size: 8.1925
>>>>>>>
>>>>>>> Without lexicographic parsimony pressure and no bloat control method at all, my programs, by this generation, were getting up into 40-50 in size, which I think (well no, I know) is larger than necessary.
>>>>>>>
>>>>>>> I think I'll try double tournament next, since that article suggests that it's a very good method. That seems intuitive to me.
>>>>>>>
>>>>>>> -Josiah
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On 12/2/11 2:56 PM, Wm. Josiah Erikson wrote:
>>>>>>>> Neat, I didn't know I was programming lexicographic parsimony pressure. That makes me feel very important indeed :)
>>>>>>>>
>>>>>>>> Reading the article... not sure I'll get through the entire thing, but thanks for the light reading!
>>>>>>>>
>>>>>>>> -Josiah
>>>>>>>>
>>>>>>>>
>>>>>>>> On 12/2/11 2:46 PM, Lee Spector wrote:
>>>>>>>>> Ah, you have come to a pretty deep vein of genetic programming research, on bloat control methods (of which this is one, for which you could use a fancy name like "lexicographic parsimony pressure").
>>>>>>>>>
>>>>>>>>> Short answer: Maybe! Depends! On what? Not sure! It'll usually make things smaller but at what cost in terms of problem solving?
>>>>>>>>>
>>>>>>>>> Somewhat longer: Certainly a good idea to try sometimes. Or if you're mainly interested in readability then you might do it only late in a run (on which there's some literature).
>>>>>>>>>
>>>>>>>>> The tip of the iceberg: In my journal we've just published a new and I think very good contribution to the bloat literature, which includes a good overview of related work. I've put a link to it on the class moodle page, with the name "Silva et al. GPEM article on bloat" (it's with the other links under the syllabus info, above the calendar).
>>>>>>>>>
>>>>>>>>> -Lee
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Dec 2, 2011, at 2:33 PM, Wm. Josiah Erikson wrote:
>>>>>>>>>
>>>>>>>>>> Hehe. Yes. Now I pose an interesting question (well, at least *I* think it's interesting):
>>>>>>>>>>
>>>>>>>>>> Does doing this in one's tournament selection (preferring smaller individuals with the same error) prevent program bloat? (Yes, I think, from preliminary experiments) And does it inhibit evoluation?
>>>>>>>>>>
>>>>>>>>>> I'm not sure yet on the second question, but I think the answer is probably yes as well. It certainly does with small population sizes, like 100 - you just hit a local minimum and sit there almost immediately. With a population size of 1000, given what I'm doing, it seems less clear that this is occurring, and the things I'm getting are certainly a lot shorter and more readable! This doesn't necessarily mean they are better, but perhaps it's easier to discern what they are actually doing and if it's at all interesting (probably not).
>>>>>>>>>>
>>>>>>>>>> -Josiah
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On 12/2/11 2:16 PM, Lee Spector wrote:
>>>>>>>>>>> On Dec 2, 2011, at 2:02 PM, Wm. Josiah Erikson wrote:
>>>>>>>>>>>
>>>>>>>>>>>> You interpreted what I was doing correctly, and actually that "mistake" you pointed out was intentional, because to do it "right", the line gets even more insane:
>>>>>>>>>>>>
>>>>>>>>>>>> (first (first (sort #(< (codesize (first %1)) (codesize (first %2))) (filter #(= (second %) (second (first sorted))) sorted))))
>>>>>>>>>>>>
>>>>>>>>>>>> And it doesn't gain you anything.
>>>>>>>>>>>>
>>>>>>>>>>> Yeah, well...... in a sense, but in another it gains you clarity of purpose when you try to read/change your code, which is actually pretty valuable.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>> But I don't quite know how to write the second thing you suggest. Let's take a stab:
>>>>>>>>>>>>
>>>>>>>>>>>> (let
>>>>>>>>>>>> [sorted (sort (fn [[prog1 err1] [prog2 err2]] (or (< err1 err2)(< (codesize prog1) (codesize prog2)))) population)]
>>>>>>>>>>> Close, but not quite.
>>>>>>>>>>>
>>>>>>>>>>> First, let's reformat this -- I can't stress enough how much this can help, at least for me, and I suspect for everyone:
>>>>>>>>>>>
>>>>>>>>>>> (let [sorted (sort (fn [[prog1 err1] [prog2 err2]]
>>>>>>>>>>> (or (< err1 err2)
>>>>>>>>>>> (< (codesize prog1)
>>>>>>>>>>> (codesize prog2))))
>>>>>>>>>>> population)]
>>>>>>>>>>>
>>>>>>>>>>> We're sorting population by a function of two arguments that are destructured into program/error pairs, and the guts of the thing is:
>>>>>>>>>>>
>>>>>>>>>>> (or (< err1 err2)
>>>>>>>>>>> (< (codesize prog1)
>>>>>>>>>>> (codesize prog2)))
>>>>>>>>>>>
>>>>>>>>>>> So you're telling sort that pair number 1 comes before pair number 2 if its error is lower OR its size is smaller. Which means it'll make it come first if it's smaller, even if it's ... AHA -- you discovered this and emailed me mid sentence!
>>>>>>>>>>>
>>>>>>>>>>> Now you propose (reformatted!):
>>>>>>>>>>>
>>>>>>>>>>> (let
>>>>>>>>>>> [sorted (sort (fn [[prog1 err1] [prog2 err2]]
>>>>>>>>>>> (or (< err1 err2)
>>>>>>>>>>> (and (< (codesize prog1) (codesize prog2))
>>>>>>>>>>> (= err1 err2))))
>>>>>>>>>>> population)]
>>>>>>>>>>>
>>>>>>>>>>> And that looks right to me!
>>>>>>>>>>>
>>>>>>>>>>> -Lee
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>> ...
>>>>>>>>>>>>
>>>>>>>>>>>> I think that's what you meant, and is, indeed, a better idea. Thanks :)
>>>>>>>>>>>>
>>>>>>>>>>>> -Josiah
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> On 12/2/11 12:20 PM, Lee Spector wrote:
>>>>>>>>>>>>> Close.... or rather, I think it will work but slightly by accident.
>>>>>>>>>>>>>
>>>>>>>>>>>>> I'm assuming that "sorted" here contains a sequence of [program error] pairs -- note that in some of my example code I had those pairs the other way around, so make sure you're treating them consistently!
>>>>>>>>>>>>>
>>>>>>>>>>>>> In any event, with that assumption (which is the only thing that makes sense given the rest of your code) your call to filter is producing a sequence of only those that have the same error as the first one (which will be the best). Then you're sorting those on the basis of which has the lowest codesize, but you're calling codesize on the whole pairs rather than on just the programs. Which I guess always comes to the same thing, since the error will just add 1 to everything uniformly. So it'll do the right thing but not quite in the right way (which you could do by calling codesize on just the programs).
>>>>>>>>>>>>>
>>>>>>>>>>>>> Alternatively, and this is probably what I'd do, you could change the predicate used in the call to sort that gives a value to "sorted" it say that %1 should come before %2 if either %1 has a lower error OR if they have the same error by the program in %1 has a lower codesize.
>>>>>>>>>>>>>
>>>>>>>>>>>>> -Lee
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> On Dec 2, 2011, at 11:24 AM, Wm. Josiah Erikson wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> So in the way I'm evolving things, I've often got a population full of individuals with similar error. Given Lee's
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> (let [sorted (sort #(< (second %1) (second %2)) population)]
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> would this function get the smallest individual that had the best error? :
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> (first (first (sort #(< (codesize %1) (codesize %2)) (filter #(= (second %) (second (first sorted))) sorted))))
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> (It seems to work)
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Is there an easier way to do that? Is this even a good idea? I'm currently just using it as the final return value so that my final result is as easy to read as possible :)
>>>>>>>>>>>>>> _______________________________________________
>>>>>>>>>>>>>> Cs254f11 mailing list
>>>>>>>>>>>>>> Cs254f11 at lists.hampshire.edu
>>>>>>>>>>>>>> https://lists.hampshire.edu/mailman/listinfo/cs254f11
>>>>>>>>>>>>> --
>>>>>>>>>>>>> Lee Spector, Professor of Computer Science
>>>>>>>>>>>>> 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
>>>>>>>>>>>>>
>>>>>>>>>>>>> _______________________________________________
>>>>>>>>>>>>> Cs254f11 mailing list
>>>>>>>>>>>>> Cs254f11 at lists.hampshire.edu
>>>>>>>>>>>>> https://lists.hampshire.edu/mailman/listinfo/cs254f11
>>>>>>>>>>>> --
>>>>>>>>>>>> Wm. Josiah Erikson
>>>>>>>>>>>> Network Engineer
>>>>>>>>>>>> Hampshire College
>>>>>>>>>>>> Amherst, MA 01002
>>>>>>>>>>>> (413) 559-6091
>>>>>>>>>>>>
>>>>>>>>>>>> _______________________________________________
>>>>>>>>>>>> Cs254f11 mailing list
>>>>>>>>>>>> Cs254f11 at lists.hampshire.edu
>>>>>>>>>>>> https://lists.hampshire.edu/mailman/listinfo/cs254f11
>>>>>>>>>>> --
>>>>>>>>>>> Lee Spector, Professor of Computer Science
>>>>>>>>>>> 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
>>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> Wm. Josiah Erikson
>>>>>>>>>> Network Engineer
>>>>>>>>>> Hampshire College
>>>>>>>>>> Amherst, MA 01002
>>>>>>>>>> (413) 559-6091
>>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> Lee Spector, Professor of Computer Science
>>>>>>>>> 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
>>>>>>>>>
>>>>>>> --
>>>>>>> Wm. Josiah Erikson
>>>>>>> Network Engineer
>>>>>>> Hampshire College
>>>>>>> Amherst, MA 01002
>>>>>>> (413) 559-6091
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Cs254f11 mailing list
>>>>>>> Cs254f11 at lists.hampshire.edu
>>>>>>> https://lists.hampshire.edu/mailman/listinfo/cs254f11
>>>>>> --
>>>>>> Lee Spector, Professor of Computer Science
>>>>>> 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
>>>>>>
>>>>> --
>>>>> Wm. Josiah Erikson
>>>>> Network Engineer
>>>>> Hampshire College
>>>>> Amherst, MA 01002
>>>>> (413) 559-6091
>>>>>
>>>> --
>>>> Lee Spector, Professor of Computer Science
>>>> 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
>>>>
>> --
>> Lee Spector, Professor of Computer Science
>> 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
>>
--
Lee Spector, Professor of Computer Science
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
More information about the Cs254f11
mailing list