HOME   ::  Conference List   ::   Conference Paper
Lucas, S. (1994) Structuring Chromosomes for Context-free Grammar Evolution. In Proceedings of The IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence.
Bookmark:  

Full-text
   URL: http://www.lania.mx/~ccoello/lucas94.ps.gz
   Cached: PDF-134K    PS-119K    PS.gz-38K   
   SAVE AS an easy-to-recall long filename:
      Filename format: author--year--title   PDF-134K    PS-38K    :: About GZip'd PS
      Filename format: author--year--title--journal|proceedings|...--pages   PDF-134K    PS-38K   

Related links
   CiteSeer: http://citeseer.ist.psu.edu/lucas94structuring.html
  Web search: Google Web Search   ::   Google Scholar
  Within this site: References (9)

Paper at a Glance 

Structuring Chromosomes for Context­Free Grammar Evolution
Simon Lucas
Department of Electronic Systems Engineering
University of Essex
Colchester CO4 3SQ
Abstract This paper investigates the use of genetic algorithms for inferring small regular and context­free grammars. Applied simply, a genetic algorithm is not very ef­ fective at this. To overcome this problem we invest­ igate two methods of structuring the chromosomes. The first is to bias the distribution of `1's in the population of chromosomes according to an algeb­ raic expansion technique previously developed by the author. This `design' of the chromosome distribu­ tion, shows no bias to any particular type of language (i.e. full generality is retained) yet improves conver­ gence. The second method involves performing the evolution (i.e. making the mutations) in a different space, where the grammars are represented in `em­ bedded normal form'. The latter approach structures the chromosome to represent context­free rather than regular grammars, for example. It is shown that bi­ asing the chromosome in this fashion produces ex­ tremely fast convergence, and 3­symbol palindromes grammars are learned in typically less than 10 gener­ ations.
1 Introduction Grammars are an extremely general and useful tool with many applications. These include the higher levels of signal processing, such as pattern recogni­ tion. However, the application of grammars is limited by the algorithms we can apply to infer them from samples of data. As with many domains, there is a tradeoff between the complexity of a model and the cost of estimat­ ing it. An example of this may be seen in speech recognition, where hidden Markov models (equival­ ent to stochastic regular grammars) are applied with great success. These are actually not the most fitting model for speech recognition (for example, context­free would be a theoretically more appropri­ ate choice), but due to the existence of fast robust training algorithms, they have ...
BibTex
@inproceedings{lucas94structuringChromosomes,
  author={Simon Lucas},
  title={Structuring Chromosomes for Context-free Grammar Evolution},
  year={1994},
  booktitle={Proceedings of The IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence},
  url={http://www.isrl.uiuc.edu/~amag/langev/paper/lucas94structuringChromosomes.html}
}

 HOME   ::  Conference List   ::   Conference Paper Comments to: junwang4 you-know-at gmail.com Last update: 2/2/08