[Cs254f11] length of individual thoughts...
Wm. Josiah Erikson
wjerikson at hampshire.edu
Sat Dec 3 00:15:25 EST 2011
Well yes, it is certainly odd, but that's kindof what I was thinking -
because you want to give smaller individuals a better CHANCE of ending
up at the front, but not have it guarantee that happening, which is what
double tournament does, and this was just a way of approximating that as
an alternative method of controlling program bloat. I'd have to
experiment with the probability I'm giving the non-deterministic sort
method to see what gave the best results most often, but perhaps the
idea might have some merit, I don't know.
I dunno, just a weird idea :)
On another note...
The runs I'm doing will, in fact, give the mean error over 20 runs, so I
guess I'm good. Yes, the time to execute is probably meaningless, as you
say, especially since my desktop that I'm currently running it on is
also running a couple of copies of maya from time to time when the
animation folks are using it for rendering, which, even if the time to
execute was locally meaningful if you ran all of them on the same
machine, renders it entirely meaningless in this case :)
-Josiah
On 12/3/11 12:02 AM, Lee Spector wrote:
> Instead of (= 4 2) you can just say false, without a quote. The symbol false evaluates to the boolean value false.
>
> Your implementation of weighted_sort_by_error_and_size is a little odd because the sort predicate will be called several times during the sorting, and if you have a non-determinsitic sort predicate, as you do here, then it may return different things at different times in the same sort, even with the same or similar arguments, and I'm not sure how this will all pan out. Here's an experiment to explore it:
>
> (sort #(if (< (rand) 0.5) (< %1 %2) false) [3 5 2 6 1 7])
>
> ; (2 3 5 6 1 7)
>
> (sort #(if (< (rand) 0.5) (< %1 %2) false) [3 5 2 6 1 7])
>
> ; (3 5 2 6 1 7)
>
> (sort #(if (< (rand) 0.5) (< %1 %2) false) [3 5 2 6 1 7])
>
> ; (3 5 2 6 1 7)
>
> (sort #(if (< (rand) 0.5) (< %1 %2) false) [3 5 2 6 1 7])
>
> ; (1 3 5 2 6 7)
>
> (sort #(if (< (rand) 0.5) (< %1 %2) false) [3 5 2 6 1 7])
>
> ; (1 3 2 5 6 7)
>
> I guess that looks sort of reasonable... although it's a little peculiar how 1 got stuck so far to the right in the first 3 tries.... In any event the way you're doing things the lower-error ones should always come first, and the partial sorting will only be on the basis of size... but still, the nature of the "partial sort" may be a little strange.
>
> -Lee
>
> On Dec 2, 2011, at 11:44 PM, Wm. Josiah Erikson wrote:
>
>> So I may have just coded "probabilistic lexicographic parsimony pressure". Let me know if it looks right (why am I up late coding this? I dunno, I was curious to see if it worked.)
>>
>> Here's the function that does it:
>>
>> (defn weighted_sort_by_error_and_size
>> [prog-err-pairs]
>> (sort (fn [[prog1 err1] [prog2 err2]]
>> (or (< err1 err2)
>> (let [a (rand)]
>> (cond (< a 0.75)
>> ;75% chance of
>> (and (< (codesize prog1) (codesize prog2))
>> (= err1 err2))
>> ;25% chance of:
>> :else (= 4 2)))))
>> prog-err-pairs))
>>
>> Then you stick this in your select function like so:
>>
>> (defn select
>> "Returns the program of the best [program error] pair in a tournament
>> set with the specified size, location, and radius."
>> [prog-err-pairs tournament-size location radius]
>> (let [limit (count prog-err-pairs)
>> tournament-set (repeatedly
>> tournament-size
>> #(nth prog-err-pairs
>> (mod (+ location
>> (- (rand-int (inc (* radius 2)))
>> radius))
>> limit)))]
>> (first (first (weighted_sort_by_error_and_size (vec tournament-set))))))
>>
>> ...and maybe, unless I screwed up (which is entirely likely, since it's late), perhaps I have that ungainly phrase implemented.
>>
>> I'm sure there's a better way of returning false than (= 4 2) also. Maybe just 'false ? That appears to work too...
>>
>> Do you think this is worth trying out? It does appear to at least allow evolution to progress, though I haven't tested it extensively yet.
>>
>> Bedtime :)
>>
>> -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