From:Patrick Monsieurs <patrick.monsieurs@luc.ac.be>
To:genetic_programming@yahoogroups.com
Subject:Re: [GP] Homogeneity?
Date:Mon, 05 Jan 2004 11:13:14 +0100
Status:R
Message-ID: <3FF938BA.2010803@luc.ac.be>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)
References: <7127E23C-39AC-11D8-A18F-00039349F194@mrs.umn.edu>
In-Reply-To: <7127E23C-39AC-11D8-A18F-00039349F194@mrs.umn.edu>
MIME-Version: 1.0
Mailing-List: list genetic_programming@yahoogroups.com; contact genetic_programming-owner@yahoogroups.com
Precedence: bulk
Reply-To: genetic_programming@yahoogroups.com
Content-Type: multipart/alternative; boundary="------------050906070105010202010208"

You can also look at my paper which describes a measure of simularity 
between a single tree and
a group of trees.

@InProceedings{monsieurs03,
  author =       "Patrick Monsieurs and Eddy Flerackers",
  title =        "Reducing Population Size While Maintaining Diversity",
  booktitle =    "Genetic Programming, Proceedings of EuroGP'2003 <http://evonet.dcs.napier.ac.uk/eurogp2003/>",
  year =         "2003",
  editor =       "Conor Ryan <http://www.csis.ul.ie/staff/conorryan/> and Terence Soule <http://www.cs.uidaho.edu/%7Etsoule/> and Maarten Keijzer <http://www.cs.vu.nl/%7Emkeijzer/> and 
                 Edward Tsang <http://cswww.essex.ac.uk/CSP/edward/> and Riccardo Poli <http://cswww.essex.ac.uk/staff/poli/> and Ernesto Costa <http://www.dei.uc.pt/%7Eernesto/>",
  volume =       "2610",
  series =       "LNCS",
  pages =        "145--156",
  address =      "Essex",
  publisher_address = "Berlin",
  month =        "14-16 " # apr,
  organisation = "EvoNet",
  publisher =    "Springer-Verlag <http://www.springer.de/index.html>",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "3-540-00971-X",
  abstract =     "This paper presents a technique to drastically reduce
                 the size of a population, while still maintaining
                 sufficient diversity for evolution. An advantage of a
                 reduced population size is the reduced number of
                 fitness evaluations necessary. In domains where
                 calculation of fitness values is expensive, this
                 results in a huge speedup of the search. Additionally,
                 in the experiments performed, smaller populations also
                 resulted in a faster convergence speed towards an
                 optimal solution.",
  notes =        "EuroGP'2003 <http://evonet.dcs.napier.ac.uk/eurogp2003/> held in conjunction with EvoWorkshops
                 2003",
}

Patrick Monsieurs

Nic McPhee wrote:

>My paper with Nicholas Hopper in GECCO 1999 on diversity in GP runs is 
>related but not exactly the same.  We were looking at how much diversity 
>there was [not] in a GP population by counting things like instances of 
>specific nodes and who inherited what from who.
>
>Steve Gustafson has done some nice work in the last few years that's 
>also relevant to these questions.  Another paper that comes to mind off 
>the top of my head are Una-May O'Reilly and David Goldberg's paper 
>"Where does the good stuff go, and why?".
>
>This is really interesting stuff, so I hope that you manage to make some 
>progress on it.
>
>Good luck!
>
>	Nic
>
>	Nicholas Freitag McPhee
>	mcphee@mrs.umn.edu
>	Division of Science and Mathematics
>	University of Minnesota, Morris
>
>On Thursday, December 25, 2003, at 09:22 AM, Ian Badcoe wrote:
>
>  
>
>>Hi,
>>         Thanks, I've found a few web-references on this so I'll get 
>>into
>>them in the new year.
>>
>>         As I type, it occurs to me that I might get better answers if I
>>state my question more exactly.  Tree-to-tree distance is interesting to
>>me, although I can always track it explicitly for the time-being by 
>>keeping
>>a register of who parented who (maybe scaled by % nodes contributed and
>>allowing a % to be attributed to "nobody" for any nodes completely
>>synthesized by mutation operations).
>>
>>         But a direct similarity measure is also interesting.
>>
>>         However, the precise problem I am considering at the moment is 
>>to
>>measure the homogeneity/heterogeneity of the whole population.  I was
>>assuming this had to be based on sum sort of (RMS?) sum of individual
>>pair-wise distances but maybe one could process the entire population 
>>as one?
>>
>>         For example, a tree:
>>
>>A(B(C),B(C),B(C)) can be regarded as 7 nodes, or as 3:
>>
>>1) C,
>>
>>2) B(C), [containing a reference to (1)]
>>
>>and
>>
>>3) A(B(C),B(C),B(C)) [which happens to contain 3 references to (2)]
>>
>>Thus one might say that the heterogeneity of even this one single tree 
>>was
>>only 3/7 -- i.e. 3 out of a total possible 7 nodes are unique.
>>
>>So maybe just extending that over the whole population?
>>
>>Or even regard three measures:
>>
>>A) node count
>>
>>B) nodes unique within each individual
>>
>>C) total unique nodes in population
>>
>>thus:
>>
>>H1 = B/A = heterogeneity of any individual, and,
>>
>>H2 = C / sum_of(A) = heterogeneity of all the nodes in the population (
>>between and within individuals), and,
>>
>>H3 = C / sum_of(B) = heterogeneity only within individuals (= H2 /
>>sim_of(H1) ?)
>>
>>(unless I slipped up on the maths, I only typed this as I thought it...)
>>
>>I'll have to write out a few full examples for small populations and see
>>whether it seems to work...
>>
>>         Ian B
>>
>>At 23:00 24/12/2003 -0600, you wrote:
>>    
>>
>>>Hello,
>>>
>>>There is a concept called "structural distance" for quantifying 
>>>similarity
>>>of trees.  I have no reference at hand now but at least it appeared in
>>>EuroGP 2002, GECCO 2002, and/or GECCO 2003.  I'm not sure whether it 
>>>is a
>>>metric that gives actual values or it's a generic framework.
>>>
>>>Hope this helps, and if you get to gather useful information about 
>>>this,
>>>I'd appreciate if you let me know it since I'm also interested in it.
>>>
>>>Regards,
>>>
>>> -- kazuto
>>>
>>>--
>>>Kazuto Tominaga <tominaga@cc.teu.ac.jp>
>>>School of Computer Science, Tokyo University of Technology
>>>
>>>On Dec 24, 2003, at 15:05, Ian Badcoe wrote:
>>>
>>>      
>>>
>>>>Hi,
>>>>        This must have come up many times before, but as usual I don't
>>>>know what
>>>>to search under.
>>>>
>>>>        If I have trees of nodes, arbitrary number of children per 
>>>>node,
>>>>each node
>>>>has a type, which can be compared with other node's types.  E.g. 
>>>>(using
>>>>function-call notation to avoid ascii art):
>>>>
>>>>A(B(C()),D())
>>>>
>>>>or
>>>>
>>>>A(A(A(A(A(A(C()))))))
>>>>
>>>>or
>>>>
>>>>A(A(B(C()),D()),B(A(B(C()),D())))
>>>>
>>>>        Then how do I calculate a homogeneity (aka similarity, aka
>>>>"relatedness")
>>>>measure between them.  I know all about using dynamic-programming to 
>>>>do
>>>>this for 1D sequences (e.g. "gene alignment" or "sequence 
>>>>comparison") and
>>>>I have a few ideas about trees, but what did people try before?
>>>>
>>>>        Thanks (and Happy Christmas),
>>>>
>>>>                Ian Badcoe
>>>>Free transport into the future, while you wait.
>>>>        
>>>>
>>Free transport into the future, while you wait.
>>
>>
>>
>>
>>Yahoo! Groups Links
>>
>>To visit your group on the web, go to:
>> http://groups.yahoo.com/group/genetic_programming/
>>
>>To unsubscribe from this group, send an email to:
>> genetic_programming-unsubscribe@yahoogroups.com
>>
>>Your use of Yahoo! Groups is subject to:
>> http://docs.yahoo.com/info/terms/
>>
>>
>>    
>>
>
>
> 
>
>Yahoo! Groups Links
>
>To visit your group on the web, go to:
> http://groups.yahoo.com/group/genetic_programming/
>
>To unsubscribe from this group, send an email to:
> genetic_programming-unsubscribe@yahoogroups.com
>
>Your use of Yahoo! Groups is subject to:
> http://docs.yahoo.com/info/terms/ 
>
>
>
>  
>

.