RSS 2.0 Feed

» Welcome Guest Log In :: Register

Pages: (12) < ... 6 7 8 9 10 [11] 12 >   
  Topic: Evolutionary Computation, Stuff that drives AEs nuts< Next Oldest | Next Newest >  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Dec. 21 2009,17:37   

Copied for your delectation from the GP-List.
Quote
Sorry if everyone has already seen this, but I had missed it and then Daniel Rodriguez highlighted Eureqa.
It might be interesting for you.

Distilling Free-Form Natural Laws from Experimental Data
Michael Schmidt and Hod Lipson
Science 3 April 2009: 81-85.
An algorithm has been developed to search for natural laws of physics in large data sets.
http://dx.doi.org/doi:10.1126/science.1165893
4 Minute Video http://www.sciencemag.org/content....3s1.mpg
Bill
Dr. W. B. Langdon,Department of Computer Science,King's College London,Strand, London, WC2R 2LS, UK http://www.dcs.kcl.ac.uk/staff/W.Langdon/
FOGA 2011 http://www.sigevo.org/foga-2011/CIGPU
2010 http://www.cs.ucl.ac.uk/external/W.Langdon/cigpuA
Field Guide to Genetic Programming http://www.gp-field-guide.org.uk/RNAnet http://bioinformatics.essex.ac.uk/users/wlangdon/rnanet
GP

EM http://www.springer.com/10710GP
Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/
------------------------------------


--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
Wesley R. Elsberry



Posts: 4468
Joined: May 2002

(Permalink) Posted: May 18 2010,07:05   

Latest comment linking back here from Iam's weasel thread on PT.

--------------
"You can't teach an old dogma new tricks." - Dorothy Parker

    
Richardthughes



Posts: 10094
Joined: Jan. 2006

(Permalink) Posted: May 18 2010,10:40   

Quote (dvunkannon @ Dec. 21 2009,17:37)
Copied for your delectation from the GP-List.
 
Quote
Sorry if everyone has already seen this, but I had missed it and then Daniel Rodriguez highlighted Eureqa.
It might be interesting for you.

Distilling Free-Form Natural Laws from Experimental Data
Michael Schmidt and Hod Lipson
Science 3 April 2009: 81-85.
An algorithm has been developed to search for natural laws of physics in large data sets.
http://dx.doi.org/doi:10.1126/science.1165893
4 Minute Video http://www.sciencemag.org/content....3s1.mpg
Bill
Dr. W. B. Langdon,Department of Computer Science,King's College London,Strand, London, WC2R 2LS, UK http://www.dcs.kcl.ac.uk/staff/W.Langdon/
FOGA 2011 http://www.sigevo.org/foga-2011/CIGPU
2010 http://www.cs.ucl.ac.uk/external/W.Langdon/cigpuA
Field Guide to Genetic Programming http://www.gp-field-guide.org.uk/RNAnet http://bioinformatics.essex.ac.uk/users/wlangdon/rnanet
GP

EM http://www.springer.com/10710GP
Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/
------------------------------------

Now that's amazing. AI ramifications, surely?

--------------
"Richardthughes, you magnificent bastard, I stand in awe of you..." : Arden Chatfield
"You magnificent bastard! " : Louis
"ATBC poster child", "I have to agree with Rich.." : DaveTard
"I bow to your superior skills" : deadman_932
"...it was Richardthughes making me lie in bed.." : Kristine

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: May 18 2010,11:09   

Quote (Richardthughes @ May 18 2010,11:40)
Quote (dvunkannon @ Dec. 21 2009,17:37)
Copied for your delectation from the GP-List.
Quote
Sorry if everyone has already seen this, but I had missed it and then Daniel Rodriguez highlighted Eureqa.
It might be interesting for you.

Distilling Free-Form Natural Laws from Experimental Data
Michael Schmidt and Hod Lipson
Science 3 April 2009: 81-85.
An algorithm has been developed to search for natural laws of physics in large data sets.
http://dx.doi.org/doi:10.1126/science.1165893
4 Minute Video http://www.sciencemag.org/content....3s1.mpg
Bill
Dr. W. B. Langdon,Department of Computer Science,King's College London,Strand, London, WC2R 2LS, UK http://www.dcs.kcl.ac.uk/staff/W.Langdon/
FOGA 2011 http://www.sigevo.org/foga-2011/CIGPU
2010 http://www.cs.ucl.ac.uk/external/W.Langdon/cigpuA
Field Guide to Genetic Programming http://www.gp-field-guide.org.uk/RNAnet http://bioinformatics.essex.ac.uk/users/wlangdon/rnanet
GP

EM http://www.springer.com/10710GP
Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/
------------------------------------

Now that's amazing. AI ramifications, surely?

I would sic it on the large (ahem) datasets that are going to come out of the LHC.

I see that Fermilab's Tevatron has found something interesting.

http://www.nytimes.com/2010....science

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: July 03 2010,13:16   

Open access to a cool issue for July only!

Quote
Note that John's article is available for FREE under open access, as is the Langdon and Gustafson article in the same issue.

Even better, the ENTIRE ISSUE is available for FREE during the month of July, 2010. This is because the publisher would like to promote this "Tenth Anniversary Issue: Progress in Genetic Programming and Evolvable Machines," edited by Julian Miller and Riccardo Poli.

I think that this is a really nice special issue, containing some excellent summaries of the state of the field and directions in which it is expected to move in the near future. The link to the online version of the entire issue is: http://www.springerlink.com/content/h46r77k291rn/?p=bfaf36a87f704d5cbcb66429f9c8a808&pi=0
-Lee

On Jul 2, 2010, at 12:31 PM, John Koza wrote:
> Hello:
> > > The Genetic Programming and Evolvable Machines journal has just published my article (which is available in its entirety) on 滴uman-competitive results produced by genetic programming. It lists 76 human-competitive results produced by genetic programming and various features common to work done in different fields by many different researchers.
> > [URL=http://www.springerlink.com/content/92n753376213655k/
>]http://www.springerlink.com/content/92n753376213655k/>[/URL]
--Lee Spector,
Professor of Computer Science
School of Cognitive Science,
Hampshire College
893 West Street, Amherst, MA

<a href="mailto:01002-3359lspector@hampshire.edu">01002-3359lspector@hampshire.edu
</a>, http://hampshire.edu/lspector/
Phone:
413-559-5352, Fax: 413-559-5438
Check out Genetic Programming and Evolvable Machines:http://www.springer.com/10710 - [URL=http://gpemjournal.blogspot.com/


Sorry for the crappity reformatting there.

Koza's article on human competitive results is useful ammunition against low grade IDC arguments that evolution can't do nothin'.

The discussion of lack of NFL applicability to GP in the article on the next 10 years in GP theory should be useful against the next level up in IDC critics.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
midwifetoad



Posts: 3553
Joined: Mar. 2008

(Permalink) Posted: July 04 2010,10:24   

Did anyone post this:

http://www.csicop.org/si/show/the_war_of_the_weasels

Quote
Or 滴ow an Intelligent Design Theorist was Bested in a Public Math Competition by a Genetic Algorithm!

This Online Extra is a follow-up to the article 展ar of the Weasels from the May/June 2010 issue of the Skeptical Inquirer (Volume 34.3, May/June 2010). The print article discusses the use of a genetic algorithm (GA) to solve tricky math problems and demonstrates that no specific 鍍arget is required for such algorithms, contra the interminable creationist attacks on the 展easel simulation discussed in Richard Dawkins's book The Blind Watchmaker. The problem I developed the GA for is called Steiner's Problem; it involves finding the shortest straight-line-segment networks connecting an array of given fixed points. This problem provides a miniature digital playground on the very edge of complexity.




A follow-up to this:

http://pandasthumb.org/archives/2010/04/war-of-the-weas.html

--------------
罵et痴 not make a joke of ourselves.

Pat Robertson

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Jan. 21 2011,16:48   

A half year's worth of birfday threads have pushed this worthy thread down and out of sight.

Rather than just bump it, I will take this chance to share with you a design for a GA experiment. Comments please.

I've been thinking recently about the arguments of Polanyi, as filtered by Meyer, and trickling down to the level of Upright Biped and David Abel. Can we show the evolution of a genetic code from nothing (pure noise) to some level of function? I think yes, we can.

Each member of my GA population will have a different genetic code to start. There are 64 codons, and 22 amino acids, so the framework of each genome is a 64*22 array. The content of each array slot will be 10 bits that can be read as an affinity of this codon for this amino acid. (So the total genome size is 64*22*10 bits.)

Let's say we are looking at the row for AUU. It contains 22 10-bit integers. We can look at these as weights that affect the likelihood this codon will code for a particular amino acid. As an illustration, perhaps the value for AA3 (amino acid 3) is 200 and AA12 is 400, and the rest of the row is 0. In this case, the codon AUU will produce amino acid 3 about 1/3 of the time, and amino acid 12 about 2/3 of the time.

If we look at the modern genetic code as this kind of array, each of the 64 rows is full of 0 bits in 21 out of 22 slots. In that 22nd slot, the bits are all 1s. Actually, the code is not quite that strong, and sometimes a codon will produce a different amino acid (leucine or valine instead of isoleucine, for example). So from a randomly filled array, we want to see if an array will come to dominate the population that resembles a mordern array. Importantly, we don't care which codon eventually comes to code for which amino acid.

The fitness function will test 640 values created by taking each codon 10 times, and choosing an amino acid based on the weights in the row in the table. This results in 640 codon-AA pairs. Now we score the fitness of the individual based on these pairs.

The first criteria is coverage, does the table produce all 22 amino acids? Score one for each unique AA in the 640 outputs. Maximum score on this criteria = 22.

The second criteria is reliability, does the table produce the same AA each time? Calculate the score by first looking at each group of 10 trials for a single codon. For the AA produced most often, how many trials produced that AA? The answer will be 10% to 100%. Average these percentages across all 64 codons. Maximum score is 100% reliability.

Third criteria is efficiency, how often does each AA get produced? Do six codons produce one AA, while another AA is produced by only one codon? We could create an order to the list of AAs and say the top AA is needed three times more often than the lowest. Or we could simply measure if they are all produced at about the same rate.

The fourth criteria is resilience, if there is a mutation in a codon, will the same AA still be produced?

Fifth criterion is like a second order resilience, if a mutation creates a different AA, is that AA still in the same polar/nonpolar, hydrophobic/hydrophillic class?

Take a weighted average of each criteria. I would weight the criteria so that the first one is most important.

Since the genome is about 40Kbits, I would use a large population, at least 1,000 individuals, and be prepared for some long run times before seeing convergence on a solution. However, I see no reason to expect that a single code will not eventually emerge the winner. The open question is the structure of that winner.

Yes, this a complex design, maybe overdesigned, but I think it will work. It will aslo support changing the weights of the different criteria and seeing the winning table has any significantly different structure as a result.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
Wesley R. Elsberry



Posts: 4468
Joined: May 2002

(Permalink) Posted: Jan. 21 2011,21:55   

The canonical genetic code can be represented as a degenerate code with 64 input values and 22 output values. Only 20 of the output values, though, specify an amino acid. The other two output values are for "start" and "stop".

I remember back in 1992 when some of my colleagues at Battelle PNL presented on their database for human genome results. They noted that they were scaling to be able to handle the large volume of data, and how the human genome comprised some 3 billion bases on 24 chromosomes.

24? I thought that was odd, since humans have 23 chromosomes. But they treated the sex chromosomes as two separate chromosomes, which makes sense from a programming standpoint.

--------------
"You can't teach an old dogma new tricks." - Dorothy Parker

    
fnxtr



Posts: 2108
Joined: June 2006

(Permalink) Posted: Jan. 21 2011,22:39   

Quote (Wesley R. Elsberry @ Jan. 21 2011,19:55)
The canonical genetic code can be represented as a degenerate code with 64 input values and 22 output values. Only 20 of the output values, though, specify an amino acid. The other two output values are for "start" and "stop".

I remember back in 1992 when some of my colleagues at Battelle PNL presented on their database for human genome results. They noted that they were scaling to be able to handle the large volume of data, and how the human genome comprised some 3 billion bases on 24 chromosomes.

24? I thought that was odd, since humans have 23 chromosomes. But they treated the sex chromosomes as two separate chromosomes, which makes sense from a programming standpoint.

I was about to say "You could somehow model the sex chromosomes as an XOR function", then realized how naive that was. :-)

--------------
"But it's disturbing to think someone actually thinks creationism -- having put it's hand on the hot stove every day for the last 400 years -- will get a different result tomorrow." -- midwifetoad

  
sparc



Posts: 1684
Joined: April 2007

(Permalink) Posted: Jan. 21 2011,23:50   

For real world numbers to start with you may want to have a look in Goodenbour JM and Tao Pan T (2006): Diversity of tRNA genes in eukaryotes. Nucl. Acids Res. 34 (21): 6137-6146.
 
Quote
Only 20 of the output values, though, specify an amino acid. The other two output values are for "start" and "stop"
The initiation codon actually results in two outputs ("start" and Met in the majority of cases where AUG is used). However, the "start" output results from positional information of the initiation codon within the mRNA. Downstream AUGs usually don't function as start sites for translation but only encode Met (BTW, the triplet of the tRNA that pairs with the codon of the mRNA is called the anticodon). The stop opal stop codon (UGA) can also have a diffenrent meaning: A specific tRNASec will incorporate Selenocystein instead of terminating translation. However, to do so additional sequnece information is required: in bacteria selenocystein insertion sequneces (SECIS) are usually within the coding sequence directly downstram of the Sec codon. In eucaryotes and in some bacterial genes SECIS elements are located in the 3'-UTR of the mRNA encoding a seleno-protein.

--------------
"[...] the type of information we find in living systems is beyond the creative means of purely material processes [...] Who or what is such an ultimate source of information? [...] from a theistic perspective, such an information source would presumably have to be God."

- William Dembski -

   
Wesley R. Elsberry



Posts: 4468
Joined: May 2002

(Permalink) Posted: Jan. 22 2011,04:00   

Sparc, thanks for correcting my sloppiness.

However, the canonical genetic code still only specifies 20 amino acids*, which changes some of the design of David's EC experiment. The case with some organisms managing to get additional amino acids specified is a derivation and needn't be included in the basic experimental design, IMO.

* Which is, if I'm reading it right, also confirmed in the link you provided:

Quote

In vivo, each tRNA also carries negative determinants to prevent mis-charging by the 19 other tRNA synthetases (31,32).


--------------
"You can't teach an old dogma new tricks." - Dorothy Parker

    
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Jan. 22 2011,07:32   

Great discussion, and I appreciate the feedback.

My thought on using 22 instead of 20:

It makes the base task harder. I don't think it would be so much harder as to be insurmountable, and I'd prefer to solve the slightly harder problem to avoid carping by IDCists.

I have a vague notion that start and stop are later additions to the functionality of the code. Early translation machinery could have taken linear strings of RNA, started at the beginning and run until there was no more input. The idea of stringing the code for multiple proteins together on one strand of RNA, and then needing to distinguish when one stopped and another began, is a later innovation. This packaging of genes into chromosomoes greatly increases the likelihood that the complete network of proteins can get created in each daughter cell, but for my purposes is not relevant. I think that developing a code happens during the protobiont stage of abiogenesis, when molecular evolution is still the driver, not Darwinian evolution.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
sparc



Posts: 1684
Joined: April 2007

(Permalink) Posted: Jan. 23 2011,01:40   

Quote (Wesley R. Elsberry @ Jan. 22 2011,04:00)
Sparc, thanks for correcting my sloppiness.

However, the canonical genetic code still only specifies 20 amino acids*, which changes some of the design of David's EC experiment. The case with some organisms managing to get additional amino acids specified is a derivation and needn't be included in the basic experimental design, IMO.

* Which is, if I'm reading it right, also confirmed in the link you provided:

 
Quote

In vivo, each tRNA also carries negative determinants to prevent mis-charging by the 19 other tRNA synthetases (31,32).

I would never call you sloppy because
1. I am not sure if I would know much about selenocysteine if a former colleague had not suggested to conditionally remove the SECIS to inactivate a selenoprotein in mice.
2. your contributions here, at the Austringer and elsewhere prove the opposite.
I also agree with dvunkannon that it will be more than enough if he sticks to the canonical code.

Still, allow me a last comment: It is 20 AA because there is no free selenocysteine in the cells. The tRNSSec binds free serine which is then transformed to selenocysteine and this is more or less the point where my knowledge about selenocysteine ends.

--------------
"[...] the type of information we find in living systems is beyond the creative means of purely material processes [...] Who or what is such an ultimate source of information? [...] from a theistic perspective, such an information source would presumably have to be God."

- William Dembski -

   
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Jan. 23 2011,07:34   

Quote (Wesley R. Elsberry @ Jan. 22 2011,05:00)
* Which is, if I'm reading it right, also confirmed in the link you provided:

Quote

In vivo, each tRNA also carries negative determinants to prevent mis-charging by the 19 other tRNA synthetases (31,32).

So what I am proposing to model with 10 exponentially scaled "affinity bits" are in real life negative determinants, dis-affinities. Interesting, but I don't think it will change the design.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Jan. 31 2011,11:59   

If you read Pharyngula, or are just cooler than I am, you might have seen this already:

http://boxcar2d.com/

It is a simple GA that builds wheeled things to run along bumpy tracks. It works as expected (ie the vehicles grow better able to traverse the track over time) even though the parameters are not very helpful.

What is nice about this for sharing with non- or anti-scientific friends is that it is obvious that the vehicles are adapting to the physics of their 2D bumpy universe, not to some fixed target "smuggled in" as part of the fitness function.

The UI is cryptic and not particularly helpful. You watch each individual going over the course, which is an easy way to waste copious time. There is a graph of red and black lines that I'm guessing are best in generation and generation average fitness, but it is unlabled, and gets clipped off as performance improves.

Reloading the page gets you a new course and resets the simulation.

Fun, addicting, and informative.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
midwifetoad



Posts: 3553
Joined: Mar. 2008

(Permalink) Posted: Jan. 31 2011,12:50   

Doesn't really say much about what is mutating.

--------------
罵et痴 not make a joke of ourselves.

Pat Robertson

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Jan. 31 2011,14:21   

Quote (midwifetoad @ Jan. 31 2011,13:50)
Doesn't really say much about what is mutating.

Agree, I think it is just one real number being replaced by another, lots of bits changing at once. One of the reasons real-numbered alleles might be useful for optimization, but don't carry a lot of biological motivation.

My current run is fun because the dominant morph has got a small wheel perched on top that makes it look like a rider on a bicycle, or TRON-esque lightcycle. It is functional, since the bumps make the morph flip over a lot.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
dheddle



Posts: 530
Joined: Sep. 2007

(Permalink) Posted: Mar. 01 2011,17:18   

Are ant colony algorithms examples of genetic algorithms?

--------------
Mysticism is a rational enterprise. Religion is not. The mystic has recognized something about the nature of consciousness prior to thought, and this recognition is susceptible to rational discussion. The mystic has reason for what he believes, and these reasons are empirical. --Sam Harris

   
Wesley R. Elsberry



Posts: 4468
Joined: May 2002

(Permalink) Posted: Mar. 01 2011,21:07   

If something has heritable properties that are passed from parent to child instance, that is likely to be considered included broadly within evolutionary computation. "Genetic algorithm" is a specific form of evolutionary computation due to John Holland. GAs operate on instances that are fixed-length bit strings. Other evolutionary computation differs from that. For instance, the Avida program fits in "genetic programming" specifically and "artificial life" categories in evolutionary computation. It operates on variable-length, fixed cardinality symbol sets (fixed cardinality for any given run; that can be changed by instantiating an instruction set of different size).

I suspect ant colony simulations are not, strictly speaking, in evolutionary computation. I would think that they would fit in both natural computation and emergent computation categories.

--------------
"You can't teach an old dogma new tricks." - Dorothy Parker

    
sledgehammer



Posts: 530
Joined: Sep. 2008

(Permalink) Posted: Mar. 01 2011,22:59   

Quote (dheddle @ Mar. 01 2011,15:18)
Are ant colony algorithms examples of genetic algorithms?

I would think ant behavior is best described by cellular automata.

--------------
The majority of the stupid is invincible and guaranteed for all time. The terror of their tyranny is alleviated by their lack of consistency. -A. Einstein (H/T, JAD)
If evolution is true, you could not know that it's true because your brain is nothing but chemicals. ?Think about that. -K. Hovind

  
dheddle



Posts: 530
Joined: Sep. 2007

(Permalink) Posted: Mar. 02 2011,06:29   

Quote (Wesley R. Elsberry @ Mar. 01 2011,21:07)
If something has heritable properties that are passed from parent to child instance, that is likely to be considered included broadly within evolutionary computation. "Genetic algorithm" is a specific form of evolutionary computation due to John Holland. GAs operate on instances that are fixed-length bit strings. Other evolutionary computation differs from that. For instance, the Avida program fits in "genetic programming" specifically and "artificial life" categories in evolutionary computation. It operates on variable-length, fixed cardinality symbol sets (fixed cardinality for any given run; that can be changed by instantiating an instruction set of different size).

I suspect ant colony simulations are not, strictly speaking, in evolutionary computation. I would think that they would fit in both natural computation and emergent computation categories.

Hmm. I never made a distinction between evolutionary algorithms and GAs. Are you saying the latter is a subset of the former where the solution is necessarily represented by a bit string? None of the implementation I wrote used bits--they all used real numbers (and/or ints) to represent solutions.

The question I asked was along a "theory of algorithms" direction. That's a topic in which I have little expertise. But I recall reading (IIRC) that simulated annealing can be shown to be equivalent to a GA--and having done both (though not with bit representations) that "smelled" right.

For fun I thought I'd try a traveling salesman by an ant colony algorithm, and it struck me that it will just be a GA  where the fitness function is maximal pheromone detection.

--------------
Mysticism is a rational enterprise. Religion is not. The mystic has recognized something about the nature of consciousness prior to thought, and this recognition is susceptible to rational discussion. The mystic has reason for what he believes, and these reasons are empirical. --Sam Harris

   
BillB



Posts: 355
Joined: Aug. 2009

(Permalink) Posted: Mar. 02 2011,07:04   

Quote (dheddle @ Mar. 02 2011,12:29)
Quote (Wesley R. Elsberry @ Mar. 01 2011,21:07)
If something has heritable properties that are passed from parent to child instance, that is likely to be considered included broadly within evolutionary computation. "Genetic algorithm" is a specific form of evolutionary computation due to John Holland. GAs operate on instances that are fixed-length bit strings. Other evolutionary computation differs from that. For instance, the Avida program fits in "genetic programming" specifically and "artificial life" categories in evolutionary computation. It operates on variable-length, fixed cardinality symbol sets (fixed cardinality for any given run; that can be changed by instantiating an instruction set of different size).

I suspect ant colony simulations are not, strictly speaking, in evolutionary computation. I would think that they would fit in both natural computation and emergent computation categories.

Hmm. I never made a distinction between evolutionary algorithms and GAs. Are you saying the latter is a subset of the former where the solution is necessarily represented by a bit string? None of the implementation I wrote used bits--they all used real numbers (and/or ints) to represent solutions.

The question I asked was along a "theory of algorithms" direction. That's a topic in which I have little expertise. But I recall reading (IIRC) that simulated annealing can be shown to be equivalent to a GA--and having done both (though not with bit representations) that "smelled" right.

For fun I thought I'd try a traveling salesman by an ant colony algorithm, and it struck me that it will just be a GA where the fitness function is maximal pheromone detection.

I've not come across that categorical distinction before, from what I was taught through my MSc onwards a GA can be implemented with variable length genomes, and with a variety of encoding formats.

The bulk of the work I was exposed to was in using GA's with animat simulations (using dynamic recurrent NNEts), evolutionary robotics and evolutionary electronics (Husbands, Harvey, Thompson et.al. at Sussex Uni) They never regarded or referred to a GA as requiring a bit encoded fixed length genotype. I guess historically the GA was created in this form but I think the classification has become a little broader (at least in some disciplines like Evo robotics)

  
Wesley R. Elsberry



Posts: 4468
Joined: May 2002

(Permalink) Posted: Mar. 02 2011,08:25   

Quote (dheddle @ Mar. 02 2011,06:29)
Quote (Wesley R. Elsberry @ Mar. 01 2011,21:07)
If something has heritable properties that are passed from parent to child instance, that is likely to be considered included broadly within evolutionary computation. "Genetic algorithm" is a specific form of evolutionary computation due to John Holland. GAs operate on instances that are fixed-length bit strings. Other evolutionary computation differs from that. For instance, the Avida program fits in "genetic programming" specifically and "artificial life" categories in evolutionary computation. It operates on variable-length, fixed cardinality symbol sets (fixed cardinality for any given run; that can be changed by instantiating an instruction set of different size).

I suspect ant colony simulations are not, strictly speaking, in evolutionary computation. I would think that they would fit in both natural computation and emergent computation categories.

Hmm. I never made a distinction between evolutionary algorithms and GAs. Are you saying the latter is a subset of the former where the solution is necessarily represented by a bit string? None of the implementation I wrote used bits--they all used real numbers (and/or ints) to represent solutions.

The question I asked was along a "theory of algorithms" direction. That's a topic in which I have little expertise. But I recall reading (IIRC) that simulated annealing can be shown to be equivalent to a GA--and having done both (though not with bit representations) that "smelled" right.

For fun I thought I'd try a traveling salesman by an ant colony algorithm, and it struck me that it will just be a GA where the fitness function is maximal pheromone detection.

Yes, GAs are a very specific subset of evolutionary computation, at least in the origination of the term and how it is used by people who distinguish between genetic algorithms, evolutionary strategies, genetic programming, etc.

Computational theory does show (I've seen this in a paper by Harold Szu) that many of the models of artificial neural networks are Turing complete, that any computable function can be accomplished using them. I suspect that such is available for simulated annealing and GAs as well. That doesn't mean that the mechanisms by which each work are in any way similar.

I haven't done ant colony simulation, so I don't know what's under the covers, but if it doesn't involve inheritance, it isn't evolutionary computation.

--------------
"You can't teach an old dogma new tricks." - Dorothy Parker

    
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Mar. 02 2011,10:11   

I would agree with BillB and others, above, that GA is still GA even when other encodings and representations of the genome are used. For example, Franz Rothlauf has a whole dissertation on the issue.
http://www.amazon.com/Represe....2064108

David Goldberg of UIUC championed the binary representation early (over high cardinality alphabets), but he certainly understood GA to include higher cardinality alphabets. You could make an argument that the defining characteristic of GA is the linear nature of the chromosome (allowing rings). Even that is stressed by GP representations of what is usually a tree as a variable length linear string. Then you have to shift to a definition of GA that stresses the idea that the genome represents parameters to a program (the fitness function) not the function itself. In GP, when you eval the population member, you are saying in effect that it is the fitness function. In the end, you are better off admitting that these are fuzzy, historical, or personal definitions.

GA for traveling salesman problems uses alleles where each allele is a token for a city. What matters is the order of the tokens, not the token values.

I agree with Heddle that ACO is very like GA for TSP. Both are finding tours through graphs. A connection with ES is that ACO algorithms don't cross tour solutions with each other, they vary existing solutions in the populations. This is similar to the asexual variation and reward we are all familiar with in WEASEL. A connection with EDA is that the population is not represented explicitly, the population is the set of all possible complete paths, and population members are drawn based on pheronome strengths of the edges in the path.

If all the graph edge costs are known in advance (there is no sense of discovery during the run) then ACO can be converted to TSP by just adding one edge of zero cost between the food and the nest. Then use your favorite TSP solver, GA, whatever.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
Wesley R. Elsberry



Posts: 4468
Joined: May 2002

(Permalink) Posted: July 30 2011,19:29   

Googling some terms brought up an antievolutionary rant from 2006 claiming that Dawkins used locking in "weasel". I entered a comment there thttp://ravingconservative.blogspot.com/2006/05/dismembering-evolution-8-avida.htmlhat I will copy here:

Quote

Daniel: "He programmed it to lock in the letters when the right one fell into place."

I just ran across this blog post. There is no discussion of locking characters in Dawkins' "The Blind Watchmaker". But we don't need to quibble about inaccessible programs from 1986. One can easily code the "weasel" program without any "locking" and still have it perform just as well as what Dawkins described. In fact, the performance difference between "locking" non-weasel programs and proper weasel programs is minor at reasonable values of population size and mutation rate.

See http://tinyurl.com/atbc-ec-thread for more information.

Wesley R. Elsberry


--------------
"You can't teach an old dogma new tricks." - Dorothy Parker

    
Dr.GH



Posts: 1954
Joined: May 2002

(Permalink) Posted: July 31 2011,01:17   

Quote (Wesley R. Elsberry @ July 30 2011,17:29)
Googling some terms brought up an antievolutionary rant

Looking for more stupid, I found that "ravingconservative" had shifted to YouTube. And, the next link resulted in the message that "ravingconservative" had gotten the boot from YouTube for "multiple violations of community standards."

--------------
"Science is the horse that pulls the cart of philosophy."

L. Susskind, 2004 "SMOLIN VS. SUSSKIND: THE ANTHROPIC PRINCIPLE"

   
Richardthughes



Posts: 10094
Joined: Jan. 2006

(Permalink) Posted: Aug. 02 2011,14:17   

More Weasel:

http://www.cs.laurentian.ca/badams/evolution/EvolutionApplet102.html

You can see 'non-latching' if you look closely, Gorden E Mullings of Montserrat.

--------------
"Richardthughes, you magnificent bastard, I stand in awe of you..." : Arden Chatfield
"You magnificent bastard! " : Louis
"ATBC poster child", "I have to agree with Rich.." : DaveTard
"I bow to your superior skills" : deadman_932
"...it was Richardthughes making me lie in bed.." : Kristine

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Dec. 01 2011,10:39   

http://www.lulu.com/product....8702814

Genetic Programming applied to playing games of various sorts, including checkers for the frilly shirted among us.

The author's work has won 5 Humie awards, these being given out for evolving something that matches or surpasses human competence in some area.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
midwifetoad



Posts: 3553
Joined: Mar. 2008

(Permalink) Posted: Feb. 02 2012,14:07   

Dumb question:

I've just encountered the term simulated annealing and a discussion of annealing algorithms vs genetic algorithms.

http://www.cs.helsinki.fi/u....sa....sa.html

The difference seems to be that an annealing algorithm selects only one child per generation to produce the next generation.

That would make Weasel and it's relatives an annealing algorithm rather than a genetic algorithm?

This came up in a discussion of Chaitin and his mathematical proof of evolution.

--------------
罵et痴 not make a joke of ourselves.

Pat Robertson

  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Feb. 05 2012,21:04   

Quote (midwifetoad @ Feb. 02 2012,15:07)
Dumb question:

I've just encountered the term simulated annealing and a discussion of annealing algorithms vs genetic algorithms.

http://www.cs.helsinki.fi/u....sa....sa.html

The difference seems to be that an annealing algorithm selects only one child per generation to produce the next generation.

That would make Weasel and it's relatives an annealing algorithm rather than a genetic algorithm?

This came up in a discussion of Chaitin and his mathematical proof of evolution.

There are a large number of Evolutionary Computation (EC) algorithms that use only one candidate solution. Evolution Strategies (ES) is an example. Weasel, IMHO, fits into the ES model the best.

I don't think the reference you provided does a good job of explaining simulated annealing. The main point of SA is to avoid a local optimum by randomly perturbing away from a good solution that isn't getting any better over several iterations, in the hope of finding a better one. The analogy is to cooling down an object (finding the optimization minimum) then partially reheating and cooling down again. So it is mostly hill climbing (or valley following, depending if you are minimizing or maximizing) with a kick every once in a while to avoid the local optimum.

The population size difference is not the most important difference between SA and GA to my way of looking at things. Even if SA had multiple candidate solutions, hill climbing with an occasional kick isn't the same as a mutation only GA. The SA algorithm is using non-local information (lack of solution improvement over some period of time), most GA algorithms avoid non-local information. SA algorithms usually operate on the real valued parameters directly (the phenotype) while GA algorithms usually apply mutation to the genotype (a binary string) which gets translated into the phenotype. The result of this genotype-phenotype distinction is that a mutation that is local in genotype space can move you arbitrarily far in phenotype space.

Here's an example of the difference. The problem has two real valued parameters, X and Y. If the current best candidate solution is { 0.5, 0.5 }, an SA algorithm might test
{ 0.51, 0.51 }
{ 0.51, 0.49 }
{ 0.49, 0.51 }
{ 0.49, 0.49 }
and if none of them is better, kick you off to  { 0.37, 0.19 }.

In contrast, the GA algorithm is working on a 20 bit string. Let's say the population size was 4, and they all were
10000000001000000000, which gets translated into a phenotype of { 0.5, 0.5 } just like the SA solution. If the mutation rate is 0.05, we would expect 1 bit to change in each 20 bit individual. But a 1 bit change to
00000000001000000000
has moved the phenotype to { 0.0, 0.5 }!

That's not hill climbing!  A lot of people, including our friend Kairosfocus at UD, think mutation = hill climbing. It does not. OK, it does, but only for the simplest of genotype-phenotype mappings. Real world mapping of DNA to protein, where one nucleotide change could flip you from a hydrophobic amino acid to a hydrophillic amino acid, with consequent changes to the 3D folded structure of the protein, isn't simple.

Bottom line - SA and GA are pretty different EC algorithms, Weasel is ES, not SA, and mutation isn't hill climbing. Test at the end of next class.

--------------
I知 referring to evolution, not changes in allele frequencies. - Cornelius Hunter
I知 not an evolutionist, I知 a change in allele frequentist! - Nakashima

  
  355 replies since Mar. 17 2009,11:00 < Next Oldest | Next Newest >  

Pages: (12) < ... 6 7 8 9 10 [11] 12 >   


Track this topic Email this topic Print this topic

[ Read the Board Rules ] | [Useful Links] | [Evolving Designs]