Evolución, sistemas evolutivos, enfoque lingüístico, lingüística matemática, reconocimiento sintáctico de patrones, inferencia gramatical, gramáticas evolutivas, computación evolutiva, programación genética, matrices evolutivas, redes neuronales evolutivas, reconocimiento de patrones, autómatas celulares evolutivos, sistemas complejos, sistemas expertos, aprendizaje de maquinas, procesos de Markov, recursividad, complejidad, informática, sistemas adaptativos, hardware evolutivo.

 

Crecimiento, aprendizaje, pensamiento, transformación de nuestra imagen de la realidad, inteligencia artificial, vida artificial, procesos de descomposición, el desarrollo y transformación de las empresas, sociedades, organizaciones, países, galaxias y universos, vida, cambio.

 

Evolución y Educación, Invención por evolución, Sistemas Evolutivos y música, Robótica evolutiva, sistemas evolutivos de la naturaleza, generación de paisajes, árboles, nubes, ríos, etc..

 

 

www.fgalindosoria.com/eac/

Evolution and Evolutionary Systems

LINKS  to Approaches, Methods and Tools

 

Evolución y Sistemas Evolutivos

LIGAS a Enfoques, Métodos y Herramientas

http://www.fgalindosoria.com/eac/evolucion/links/Approach.htm

 

Fernando Galindo Soria

www.fgalindosoria.com             fgalindo@ipn.mx

Red de Desarrollo Informatico REDI   www.LaRedi.com

 

 

Creación de la página  www    Cd. De México a  2 de Junio del 2001

Ultimas actualizaciones  27 de Mayo del 2007, 9 de Diciembre del 2008, 9 de Julio del 2009, 11 de Julio del 2010

 

 

Ir a

Evolución y Sistemas Evolutivos, Sistemas Afectivos y Sistemas Concientes

 

Evolución y Sistemas Evolutivos           Sistemas Afectivos             Sistemas Concientes

Matrices Evolutivas y Dinámica Dimensional

 

 

 

Go to   Evolution and Evolutionary Systems      /      Ir a   Evolución y Sistemas Evolutivos

Go to   Principal Page       /       Ir a   Página Principal

 

Go to   Links Pages         /        Ir a   Páginas de Ligas

 

FGS Papers     /     Artículos de FGS

Papers     /     Artículos

Thesis over Evolutionary Systems     /     Trabajos de titulación sobre sistemas evolutivos

Pages of peoples and organizations over Evolutionary Systems     /     Páginas de personas y organizaciones sobre sistemas evolutivos

Complementary Bibliography over Evolutionary Systems     /     Bibliografía complementaria sobre sistemas evolutivos

 

Evolution     /     Evolución

History of evolutionary thought     /     Historia del Pensamiento Evolutivo

Approaches, Methods and Tools     /     Enfoques, Métodos y Herramientas

Applications     /     Aplicaciones

Book´s     /     Libros

Events     /     Eventos

Others link over Evolutionary Systems     /     Otras ligas sobre sistemas evolutivos

 

 

 

LINKS  /  LIGAS

 

Approaches, Methods and Tools

Enfoques, Métodos y Herramientas

 

 

 

***********************************************************

Evolutionary Informatics  /  Informática evolutiva

 

Evolutionary Informatics

“Evolutionary informatics merges theories of evolution and information, thereby wedding the natural, engineering, and mathematical sciences. Evolutionary informatics studies how evolving systems incorporate, transform, and export information. The Evolutionary Informatics Laboratory explores the conceptual foundations, mathematical development, and empirical application of evolutionary informatics. The principal theme of the lab’s research is teasing apart the respective roles of internally generated and externally applied information in the performance of evolutionary systems.” (Link June 2, 2010)

http://www.evolutionaryinformatics.org/

 

Informática evolutiva

“Informática evolutiva es un subcampo de informática tratando la práctica de la tratamiento de la información adentro, y la ingeniería de los sistemas de información para, el estudio de evolución biológica, así como el estudio de la información en sistemas evolutivos, natural y artificial.”

http://www.worldlingo.com/ma/enwiki/es/Evolutionary_informatics

 

 

Future IT: A Look at How It Will Evolve

By Michael Fitzgerald, CIO, December 15, 2003

 “Evolution is a hot topic in IT circles. There is, appropriately enough, evolutionary computation, which bases aspects of computing on biological systems that gradually change into "a different and usually more complex or better form." The process of evolution provides models for dealing with the complexity of advanced IT systems.”

http://www.cio.com/article/32037/Future_IT_A_Look_at_How_It_Will_Evolve

 

Evolutionary Software Systems

Applications and testing systems were self generating.

http://www.evolswsys.com/

 

 

***********************************************************

Evolutionary Systems and Artificial Life

 

Evolutionary Systems and Artificial Life  by Luis Rocha

http://informatics.indiana.edu/rocha/alife.html#dds

 

Luis Rocha's CyberCorner

http://informatics.indiana.edu/rocha/index.html

 

Indiana University School of Informatics

http://informatics.indiana.edu/

 

Indiana University-Purdue University Indianapolis School of Informatics

http://www.informatics.iupui.edu/

 

Evolutionary Systems Biology Group

http://www.ai.sri.com/people_list/esb/

 

 

Polyworld: Using Evolution to Design Artificial Intelligence

http://www.youtube.com/watch?v=_m97_kL4ox0&feature=related

 

 

Evolving artificial creatures

http://www.youtube.com/watch?v=d4BGLp0wcdE&feature=related

 

 

Evolving Virtual Creatures: The Definitive Guide

http://aigamedev.com/open/article/evolving-virtual-creatures/

 

 

*************************************************************************

*************************************************************************

Evolutionary Linguistic Approach  /  Enfoque Lingüístico Evolutivo

Linguistic Evolution  /  Evolución Lingüística

Grammatical Evolution  /  Evolución Gramatical  /  Gramaticas Evolutivas

 

 

*************************************************************************

Grammatical Evolution: Evolving Programs for an Arbitrary Language

Conor Ryan, J. J. Collins, Michael O'Neill

April 1998

Lecture Notes In Computer Science; Vol. 1391

EuroGP '98: Proceedings of the First European Workshop on Genetic Programming

Publisher: Springer-Verlag, UK

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=646806.706289&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Crossover in Grammatical Evolution: A Smooth Operator?

Michael O'Neill, Conor Ryan

April 2000

Lecture Notes In Computer Science; Vol. 1802

Proceedings of the European Conference on Genetic Programming

Publisher: Springer-Verlag, London, UK

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=646808.703948&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Crossover in Grammatical Evolution

Michael O'neill, Department of Computer Science & Information Systems, University of Limerick, Ireland

Conor Ryan, Department of Computer Science & Information Systems, University of Limerick, Ireland

Maarten Keijzer, Free University, Amsterdam

Mike Cattolico, Tiger Mountain Scientific, Inc.

March 2003

Genetic Programming and Evolvable Machines , Volume 4 Issue 1, March 2003

Publisher: Kluwer Academic Publishers  Hingham, MA, USA

ABSTRACT

“We present an investigation into crossover in Grammatical Evolution that begins by examining a biologically-inspired homologous crossover operator that is compared to standard one and two-point operators. Results demonstrate that this homologous operator is no better than the simpler one-point operator traditionally adopted.

An analysis of the effectiveness of one-point crossover is then conducted by determining the effects of this operator, by adopting a headless chicken-type crossover that swaps randomly generated fragments in place of the evolved strings. Experiments show detrimental effects with the utility of the headless chicken operator.

Finally, the mechanism of crossover in GE is analysed and termed ripple crossover, due to its defining characteristics. An experiment is described where ripple crossover is applied to tree-based genetic programming, and the results show that ripple crossover is more effective in exploring the search space of possible programs than sub-tree crossover by examining the rate of premature convergence during the run. Ripple crossover produces populations whose fitness increases gradually over time, slower than, but to an eventual higher level than that of sub-tree crossover.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=608284.608289&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language (Genetic Programming)

Michael O'Neill , Conor Ryan

http://portal.acm.org/citation.cfm?id=862025&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Book

Publisher: Springer; Hardcover, 1 edition (May 1, 2003), 160 pages

Review

From the reviews: "This is the first book written on grammatical evolution, a new technique that is receiving increasing attention and use. Therefore, the book fulfills an important role … . The book contains a good description of grammatical evolution … . ‘Grammatical Evolution’ should be useful for specialists and Ph.D. students in the field of grammatical evolution and genetic programming, and people working in artificial intelligence and genetic algorithms in general. We would advise it as a good resource for university libraries." (Manuel Alfonseca and Alfonso Ortega, Genetic programming and Evolvable Machines, Vol. 5, 2004)

Product Description

“Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language provides the first comprehensive introduction to Grammatical Evolution, a novel approach to Genetic Programming that adopts principles from molecular biology in a simple and useful manner, coupled with the use of grammars to specify legal structures in a search. Grammatical Evolution's rich modularity gives a unique flexibility, making it possible to use alternative search strategies - whether evolutionary, deterministic or some other approach - and to even radically change its behavior by merely changing the grammar supplied. This approach to Genetic Programming represents a powerful new weapon in the Machine Learning toolkit that can be applied to a diverse set of problem domains.

Beginning with an overview of the necessary background material in Genetic Programming and Molecular Biology, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language outlines the current state of the art in grammatical and genotype-phenotype-based approaches. Following a description of Grammatical Evolution and its application to a number of example problems, an in-depth analysis of the approach is conducted, focusing on areas such as the degenerate genetic code, wrapping, and crossover. The book continues with a description of hot topics in Grammatical Evolution and presents possible directions for future research.”

(FGS Link, July, 2010)

 

Purchase this Book  

http://www.amazon.com/Grammatical-Evolution-Evolutionary-Automatic-Programming/dp/1402074441

 

 

Book Review: Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language

Manuel Alfonseca, Alfonso Ortega

Source

Genetic Programming and Evolvable Machines

Volume 5 ,  Issue 4  (December 2004), Pages: 393 – 393, December 2004

Publisher: Kluwer Academic Publishers  Hingham, MA, USA

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1011987.1011991&coll=ACM&dl=ACM&CFID=45851609&CFTOKEN=24619111

 

 

***********************************

Meta-grammar constant creation with grammatical evolution by grammatical evolution

Ian Dempsey, University of Limerick, Limerick, Ireland

Michael O'Neill, University of Limerick, Limerick, Ireland

Anthony Brabazon, University College Dublin, Dublin, Ireland

June 2005

GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary computation, Washington DC, USA

SESSION: Genetic programming

Publisher: ACM

ABSTRACT

“This study examines the utility of meta-grammar constant generation on a series of benchmark problems. The performance of the meta-grammar approach is compared to a grammar which incorporates grammatical ephemeral random constants, digit concatenation, and an expression based approach. It is found that the meta-grammar approach to constant creation is particularly beneficial on the dynamic problem instances in terms of the best fitness values achieved.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1068009.1068289&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

Full text available for ACM Digital Library Members:

PdfPdf (205.51 KB)

http://portal.acm.org/ft_gateway.cfm?id=1068289&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Constant creation in grammatical evolution

Ian Dempsey, Michael O'Neill, Anthony Brabazon

Natural Computing Research and Applications Group, University College Belfield, Dublin, Dublin, Ireland, April 2007

International Journal of Innovative Computing and Applications , Volume 1 Issue 1, April 2007

Publisher: Inderscience Publishers, Geneva, SWITZERLAND

ABSTRACT

“We present an investigation into constant creation in Grammatical Evolution (GE), a form of grammar-based Genetic Programming (GP). The methods for constant creation evaluated include digit Concatenation (Cat) and a grammatical version of ephemeral random constants called persistent random constants. Experiments conducted on a diverse range of benchmark problems uncover clear advantages for a digit Cat approach.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1359342.1359345&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Towards models of user preferences in interactive musical evolution

Dan Costelloe, Conor Ryan

University of Limerick, Limerick, Ireland

July 2007

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, London, England

Publisher: ACM

ABSTRACT

“We describe the "bottom-up" construction of a system which aims to build models of human musical preferences with strong predictive power. We use Grammatical Evolution to construct models from toy datasets which mimic real-world user-generated data. These models will ultimately substitute for the subjective fitness functions that human users employ during Interactive Evolution of melodies.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1276958.1277389&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (68.82 KB)

http://portal.acm.org/ft_gateway.cfm?id=1277389&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Gecco 2007 Grammatical Evolution Tutorial

Grammatical evolution

Conor M. Ryan, University of Limerick, Limerick, Ireland

July 2007

GECCO '07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, London, United Kingdom

Publisher: ACM

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1274000.1274126&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (636.53 KB)

http://portal.acm.org/ft_gateway.cfm?id=1274126&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Gecco 2008 grammatical evolution tutorial

R. Muhammad Atif Azad, Conor Ryan

University of Limerick, Limerick, Ireland

July 2008

GECCO '08: Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, Atlanta, GA, USA

Publisher: ACM

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1388969.1389058&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (868.80 KB)

http://portal.acm.org/ft_gateway.cfm?id=1389058&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

GEVA: grammatical evolution in Java

Michael O'Neill, Erik Hemberg, Conor Gilligan, Eliott Bartley, James McDermott, Anthony Brabazon

University College Dublin, Ireland, July 2008

SIGEVOlution , Volume 3 Issue 2, Summer 2008

Publisher: ACM

ABSTRACT

 “We are delighted to announce the release of GEVA [1], an open source software implementation of Grammatical Evolution (GE) in Java. Grammatical Evolution in Java (GEVA) was developed at UCD's Natural Computing Research & Applications group (http://ncra.ucd.ie).”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1527063.1527066&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (227.64 KB)

http://portal.acm.org/ft_gateway.cfm?id=1527066&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

***********************************

Elevated Pitch: Automated Grammatical Evolution of Short Compositions

John Reddin, Trinity College Dublin,

James Mcdermott, University College Dublin,

Michael O'Neill, University College Dublin,

April 2009

Lecture Notes In Computer Science; Vol. 5484

EvoWorkshops '09: Proceedings of the EvoWorkshops 2009 on Applications of Evolutionary Computing: EvoCOMNET, EvoENVIRONMENT, EvoFIN, EvoGAMES, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, EvoNUM, EvoSTOC, EvoTRANSLOG, Tübingen, Germany

Section: EvoMUSA

Publisher: Springer-Verlag  Berlin, Heidelberg

ABSTRACT

“A system for automatic composition using grammatical evolution is presented. Music is created under the constraints of a generative grammar, and under the bias of an automatic fitness function and evolutionary selection. This combination of two methods is seen to be powerful and flexible. Human evaluation of automatically-evolved pieces shows that a more sophisticated grammar in combination with a naive fitness function gives better results than the reverse.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1533570.1533643&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

*************************************************************************

Automatic verilog code generation through grammatical evolution

Ulya R. Karpuzcu, Istanbul Technical University, Maslak, Istanbul, Turkey, June 2005

GECCO '05: Proceedings of the 2005 workshops on Genetic and evolutionary computation, SESSION: UGWS

Washington, D.C.

Publisher: ACM

ABSTRACT

“This work aims to investigate the automatic generation of Verilog code, representing digital circuits through Grammatical Evolution (GE). Preliminary tests using a simple full adder generation problem have been performed.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1102256.1102346&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (80.32 KB)

http://portal.acm.org/ft_gateway.cfm?id=1102346&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

*************************************************************************

Using APL2 to compute the dimension of a fractal represented as a grammar

Manuel Alfonseca, Alfonso Ortega

Universidad Autónoma de Madrid, July 2000

APL '00: Proceedings of the international conference on APL-Berlin-2000 conference

Berlin, Germany

Publisher: ACM

ABSTRACT

“In this paper we describe the use of APL2 to implement and depict the equivalence between the mathematical field of fractal curves and the linguistic field of parallel derivation grammars, by tackling the problem of determining the dimension of a fractal from its representation as a grammar. APL2 makes the required computation quite easy.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=570475.570477&coll=ACM&dl=ACM&CFID=47353934&CFTOKEN=22785683

 

Full text available for ACM Digital Library Members:

PdfPdf (540.78 KB)

http://portal.acm.org/ft_gateway.cfm?id=570477&type=pdf&coll=ACM&dl=ACM&CFID=47353934&CFTOKEN=22785683

 

 

Also published in:

June 2000

SIGAPL APL Quote Quad

Volume 30 Issue 4

 

 

***********************************

Automatic composition of music by means of grammatical evolution

Alfonso Ortega de la Puente, Universidad Autónoma de Madrid

Rafael Sánchez Alfonso, Universidad Autónoma de Madrid & IBM

Manuel Alfonseca Moreno, Universidad Autónoma de Madrid

July 2002

APL '02: Proceedings of the 2002 conference on APL: array processing languages: lore, problems, and applications, Madrid, Spain

Publisher: ACM

ABSTRACT

“This work describes how grammatical evolution may be applied to the domain of automatic composition. Our goal is to test this technique as an alternate tool for automatic composition. The AP440 auxiliary processor will be used to play music, thus we shall use a grammar that generates AP440 melodies. Grammar evolution will use fitness functions defined from several well-known single melodies to automatically generate AP440 compositions that are expected to sound like those composed by human musicians.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=602231.602249&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (191.13 KB)

http://portal.acm.org/ft_gateway.cfm?id=602249&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

Also published in:

June 2002

SIGAPL APL Quote Quad

Volume 32 Issue 4

 

PDF

http://arantxa.ii.uam.es/~alfonsec/artint/apl2002b.pdf

 

 

************************************

Grammatical evolution to design fractal curves with a given dimension

A. Ortega, A. Dalhoum, M. Alfonseca

Universidad Autónoma de Madrid, Campus de Cantoblanco, 28049 Madrid, Spain

July 2003

IBM Journal of Research and Development , Volume 47 Issue 4, July 2003

Publisher: IBM Corp.

ABSTRACT

Lindenmayer grammars have frequently been applied to represent fractal curves. In this work, the ideas behind grammar evolution are used to automatically generate and evolve Lindenmayer grammars which represent fractal curves with a fractal dimension that approximates a predefined required value. For many dimensions, this is a nontrivial task to be performed manually. The procedure we propose closely parallels biological evolution because it acts through three different levels: a genotype (a vector of integers), a protein-like intermediate level (the Lindenmayer grammar), and a phenotype (the fractal curve). Variation acts at the genotype level, while selection is performed at the phenotype level (by comparing the dimensions of the fractal curves to the desired value).”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1014587.1014594&coll=ACM&dl=ACM&CFID=47353934&CFTOKEN=22785683

 

 

************************************

Automatic generation of benchmarks for plagiarism detection tools using grammatical evolution

Manuel Cebrián, Manuel Alfonseca, Alfonso Ortega

Universidad Autónoma de Madrid, Madrid, Spain, July 2007

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Publisher: ACM

ABSTRACT

“Student plagiarism is a mayor problem in universities worldwide. In this paper,we focus on plagiarism in answers to computer programming assignments,where student mix and/or modify one or more original solutions to obtain counterfeits. Although several software tools have been implemented to help the tedious and time consuming task of detecting plagiarism, little has been done to assess their quality, because, in fact, determining the original subset of the whole solution set is practically impossible for graders. In this article we present a Grammatical Evolution technique which generates benchmarks. Given a programming language, our technique generates a set of original solutions to an assignment, together with a set of plagiarisms of the former set which mimic the way in which students act. The phylogeny of the coded solutions is predefined, providing a base for the evaluation of the performance of copy-catching tools. We give empirical evidence of the suitability of our approach by studying the behavior of one state-of-the-art detection tool (AC) on four benchmarks coded in APL2, generated with this technique.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1276958.1277388&coll=ACM&dl=ACM&CFID=45851609&CFTOKEN=24619111

 

Full text available for ACM Digital Library Members:

PdfPdf (324.18 KB)

http://portal.acm.org/ft_gateway.cfm?id=1277388&type=pdf&coll=ACM&dl=ACM&CFID=45851609&CFTOKEN=24619111

 

 

*************************************************************************

Grammex: defining grammars by example

Henry Lieberman, Media Laboratory Massachusetts Institute of Technology Cambridge, MA

Bonnie A. Nardi, Apple Computer, Advanced Technology Group, 1 Infinite Loop, Cupertino, CA

David Wright, Apple Computer, Advanced Technology Group, 1 Infinite Loop, Cupertino, CA

April 1998

Conference on Human Factors in Computing Systems

CHI 98 conference summary on Human factors in computing systems

Los Angeles, California, United States, Pages: 11 – 12, Year of Publication: 1998

Publisher: ACM

ABSTRACT

“Parsers are powerful tools for computer understanding of text, whether the language is a natural language or a formal language. To make the computational power of these tools fully available to an end user, a parser should be user-extensible. Until now, a user who wished to control a parser was forced to write or edit a grammar, a text file containing rules. Editing grammars is often difficult and error-prone for end users since the effect of writing specific rules, and interaction between rules, can often be unclear.

Grammex [“Grammars by Example”] is the first direct manipulation interface designed to allow ordinary users to define grammars interactively. Instead of writing a grammar in an abstract rule language, the user presents concrete examples of text that he or she would like the parser to recognize. The user describes the text by selecting substrings, and choosing possible interpretations of the text from popup menus of suggestions heuristically computed by Grammex. Grammex compiles grammar rules that can be used as the input to a traditional parser.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=286498.286504&coll=ACM&dl=ACM&CFID=46776952&CFTOKEN=58818603

 

 

Full text available for ACM Digital Library Members:

PdfPdf (257 KB)

http://portal.acm.org/ft_gateway.cfm?id=286504&type=pdf&coll=ACM&dl=ACM&CFID=46776952&CFTOKEN=58818603

 

 

Grammex: Defining Grammars by Example

Henry Lieberman

Media Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA

(FGS Link, July, 2010)

http://web.media.mit.edu/~lieber/Lieberary/Grammex/Grammex-Intro.html

 

 

********************************

Training agents to recognize text by example

Henry Lieberman, Massachusetts Institute of Technology, Cambridge

Bonnie A. Nardi, AT&T Labs West, Menlo Park, CA

David Wright, Apple Computer, Cupertino, CA

April 1999

International Conference on Autonomous Agents

AGENTS '99: Proceedings of the third annual conference on Autonomous Agents

Seattle, Washington, United States, Pages: 116 – 122, Year of Publication: 1999

Publisher: ACM

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=301136.301176&coll=ACM&dl=ACM&CFID=46776952&CFTOKEN=58818603

 

Full text available for ACM Digital Library Members:

PdfPdf (756 KB)

http://portal.acm.org/ft_gateway.cfm?id=301176&type=pdf&coll=ACM&dl=ACM&CFID=46776952&CFTOKEN=58818603

 

 

Training Agents to Recognize Text by Example

Henry Lieberman

Media Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139 USA
Bonnie A. Nardi, AT&T Labs West, 75 Willow Road, Menlo Park, CA 94025

David Wright, Apple Computer, 1 Infinite Loop, Cupertino, CA 95014 USA
ABSTRACT

“An important function of an agent is to be "on the lookout" for bits of information that are interesting to its user, even if these items appear in the midst of a larger body of unstructured information. But how to tell these agents which patterns are meaningful and what to do with the result?

Especially when agents are used to recognize text, they are usually driven by parsers which require input in the form of textual grammar rules. Editing grammars is difficult and error-prone for end users. Grammex ["Grammars by Example"] is the first direct manipulation interface designed to allow non-expert users to define grammars interactively. The user presents concrete examples of text that he or she would like the agent to recognize. Rules are constructed by an iterative process, where Grammex heuristically parses the example, displays a set of hypotheses, and the user critiques the system’s suggestions. Actions to take upon recognition are also demonstrated by example.”

(FGS Link, July, 2010)

http://web.media.mit.edu/~lieber/Lieberary/Grammex/Grammex.html

 

 

*************************************************************************

Can a parser be generated from examples?

Marjan Mernik, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia

Goran Gerlič, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia

Viljem Žumer, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia

Barrett R. Bryant, The University of Alabama at Birmingham, Birmingham, AL

March 2003

Symposium on Applied Computing

SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

Melbourne, Florida

SESSION: Programming languages and object technologies, Pages: 1063 - 1067  

Publisher: ACM

ABSTRACT

“One of the open problems in the area of domain-specific languages is how to make domain-specific language development easier for domain experts not versed in a programming language design. Possible approaches are to build a domain-specific language from parameterized building blocks or by language (grammar) induction. This paper uses an evolutionary approach to grammar induction. Grammar-specific genetic operators for crossover and mutation are proposed to achieve this task. Suitability of the approach is shown by small experiments where underlying grammars are successfully genetically obtained and parsers are than automatically generated.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=952532.952740&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (435.01 KB)

http://portal.acm.org/ft_gateway.cfm?id=952740&type=pdf&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

***********************************

Context-free grammar induction using genetic programming

F. Javed, University of Alabama at Birmingham, Birmingham, AL

B. R. Bryant, University of Alabama at Birmingham, Birmingham, AL

M. Črepinšek, University of Maribor, Maribor, Slovenia

M. Mernik, University of Maribor, Maribor, Slovenia

A. Sprague, University of Alabama at Birmingham, Birmingham, AL

April 2004

ACM-SE 42: Proceedings of the 42nd annual Southeast regional conference

Huntsville, Alabama

Publisher: ACM

ABSTRACT

“While grammar inference is used in areas like natural language acquisition, syntactic pattern recognition, etc., its application to the programming language problem domain has been limited. We propose a new application area for grammar induction which intends to make domain-specific language development easier and finds a second application in renovation tools for legacy systems. The genetic programming approach is used for grammatical inference. Our earlier work used grammar-specific heuristic operators in tandem with non-random construction of the initial grammar population and succeeded in inducing small grammars.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=986537.986635&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (195.18 KB)

http://portal.acm.org/ft_gateway.cfm?id=986635&type=pdf&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

***********************************

Extracting grammar from programs: brute force approach

Matej Črepinšek, Marjan Mernik, Viljem Žumer

University of Maribor, Maribor, Slovenia,

SIGPLAN Notices , Volume 40 Issue 4, April 2005

Publisher: ACM

ABSTRACT

Extracting grammar from programs attracts researchers from several fields such as software engineering, pattern recognition, computational linguistic and natural language acquisition. So far, only regular grammar induction has been successful, while purposeful context-free grammar induction is still elusive. We discuss the search space of context-free grammar induction and propose the Brute Force approach to the problem which, along with its various enhancements, can be further used in collaboration with the Evolutionary approach, as described in the accompanying paper.

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1064165.1064171&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (2.79 MB)

http://portal.acm.org/ft_gateway.cfm?id=1064171&type=pdf&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

***********************************

Extracting grammar from programs: evolutionary approach

Matej Črepinšek, University of Maribor, Maribor, Slovenia

Marjan Mernik, University of Maribor, Maribor, Slovenia

Faizan Javed, The University of Alabama at Birmingham, Birmingham, AL

Barrett R. Bryant, The University of Alabama at Birmingham, Birmingham, AL

Alan Sprague, The University of Alabama at Birmingham, Birmingham, AL

SIGPLAN Notices , Volume 40 Issue 4, April 2005

Publisher: ACM

ABSTRACT

“The paper discusses context-free grammar (CFG) inference using genetic-programming with application to inducing grammars from programs written in simple domain-specific languages. Grammar-specific heuristic operators and non-random construction of the initial population are proposed to achieve this task. Suitability of the approach is shown by small examples where the underlying CFG's are successfully inferred.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1064165.1064172&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

Full text available for ACM Digital Library Members:

PdfPdf (1.93 MB)

http://portal.acm.org/ft_gateway.cfm?id=1064172&type=pdf&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

***********************************

An unsupervised incremental learning algorithm for domain-specific language development

Faizan Javed, Department of Computer & Information Sciences, University of Alabama at Birmingham, Birmingham, Alabama, USA

Marjan Mernik, Faculty of Electrical Engineering and Computer Science, University of Maribor, Maribor, Slovenia

Barrett R. Bryant, Department of Computer & Information Sciences, University of Alabama at Birmingham, Birmingham, Alabama, USA

Alan Sprague, Department of Computer & Information Sciences, University of Alabama at Birmingham, Birmingham, Alabama, USA

August 2008

Applied Artificial Intelligence , Volume 22 Issue 7-8, August 2008

Publisher: Taylor & Francis, Inc.  Bristol, PA, USA

ABSTRACT

“While grammar inference (or grammar induction) has found extensive application in the areas of robotics, computational biology, and speech recognition, its application to problems in programming language and software engineering domains has been limited. We have found a new application area for grammar inference which intends to make domain-specific language development easier for domain experts not well versed in programming language design, and finds a second application in construction of renovation tools for legacy software systems. As a continuation of our previous efforts to infer context-free grammars (CFGs) for domain-specific languages which previously involved a genetic-programming based CFG inference system, we discuss extensions to the inference capabilities of GenInc, an incremental learning algorithm for inferring CFGs. We show that these extensions enable GenInc to infer more comprehensive grammars, discuss the results of applying GenInc to various domain-specific languages and evaluate the results using a comprehensive suite of grammar metrics.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1451363.1451367&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

*************************************************************************

Evolutionary music composer integrating formal grammar

Yaser M. A. Khalifa, Badar K. Khan, Jasmin Begovic, Airrion Wisdom, Andrew Maxymillian Wheeler

State University of New York, New Paltz, NY July 2007

GECCO '07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, London, United Kingdom

Publisher: ACM

ABSTRACT

“In this paper, an autonomous music composition tool is developed using Genetic Algorithms. The production is enhanced by integrating formal grammar rules. A formal grammar is a collection of either or both descriptive or prescriptive rules for analyzing or generating sequences of symbols. In music, these symbols are musical parameters such as notes and their attributes. The composition is conducted in two Stages. The first Stage generates and identifies musically sound patterns (motifs). In the second Stage, methods to combine different generated motifs and their transpositions are applied. These combinations are evaluated and as a result, musically fit phrases are generated. Four musical phrases are generated at the end of each program run. The generated music pieces will be translated into Guido Music Notation (GMN) and have alternate representation in Musical Instrument Digital Interface (MIDI). The Autonomous Evolutionary Music Composer (AEMC) was able to create interesting pieces of music that were both innovative and musically sound.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1274000.1274020&coll=ACM&dl=ACM&CFID=47166338&CFTOKEN=60514033

 

Full text available for ACM Digital Library Members:

PdfPdf (313.96 KB)

http://portal.acm.org/ft_gateway.cfm?id=1274020&type=pdf&coll=ACM&dl=ACM&CFID=47166338&CFTOKEN=60514033

 

 

*************************************************************************

Learning to extract information from semi-structured text using a discriminative context free grammar

Paul Viola,  Microsoft Research, Redmond, WA

Mukund Narasimhan,  University of Washington, Seattle, WA

August 2005

SIGIR '05: Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval

Publisher: ACM

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1076034.1076091&coll=ACM&dl=ACM&CFID=46542654&CFTOKEN=84397846

 

Full text available for ACM Digital Library Members:

PdfPdf (178.95 KB)

http://portal.acm.org/ft_gateway.cfm?id=1076091&type=pdf&coll=ACM&dl=ACM&CFID=46542654&CFTOKEN=84397846

 

 

Learning to Extract Information from Semistructured Text using a Discriminative Context Free Grammar

Draft submitted to the conference SIGIR 2005

Paul Viola, Mukund Narasimhand

ABSTRACT

“In recent work, conditional Markov chain models (CMM) have been used to extract information from semi-structured text (one example is the Conditional Random Field [10]).

Applications range from finding the author and title in research papers to finding the phone number and street address in a web page. The CMM framework combines a priori knowledge encoded as features with a set of labeled training data to learn an efficient extraction process. We will show that similar problems can be solved more e_ectively by learning a discriminative context free grammar from training data. The grammar has several distinct advantages: long range, even global, constraints can be used to disambiguate entity labels; training data is used more efficiently; and a set of new more powerful features can be introduced. The specific problem we consider is of extracting personal contact, or address, information from unstructured sources such as documents and emails. While linear-chain CMMs perform reasonably well on this task, we show that a statistical parsing approach results in a 50% reduction in error rate. This system also has the advantage of being interactive, similar to the system described in [9]. In cases where there are multiple errors, a single user correction can be propagated to correct multiple errors automatically. Using a discriminatively trained grammar, 93.71% of all tokens are labeled correctly (compared to 88.43% for a CMM) and 72.87% of records have all tokens labeled correctly (compared to 45.29% for the CMM).”

(FGS Link, July, 2009)

http://research.microsoft.com/en-us/um/people/viola/pubs/docextract/contact_sigir05.pdf

 

 

*************************************************************************

Symbolic regression using abstract expression grammars

Michael F. Korns

Freeman Investment Management, Henderson, NV, USA, June 2009

GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, Shanghai, China

Publisher: ACM

ABSTRACT

“Abstract Expression Grammars have the potential to integrate Genetic Algorithms, Genetic Programming, Swarm Intelligence, and Differential Evolution into a seamlessly unified array of tools for use in symbolic regression. The features of abstract expression grammars are explored, examples of implementations are provided, and the beneficial effects of abstract expression grammars are tested with several published nonlinear regression problems.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1543834.1543960&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (400.77 KB)

http://portal.acm.org/ft_gateway.cfm?id=1543960&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

*************************************************************************

Grammatical Swarm: The generation of programs by social programming

Michael O'Neill, Anthony Brabazon

Natural Computing Research & Applications Group, University College Dublin, Dublin, Ireland, November 2006

Natural Computing: an international journal , Volume 5 Issue 4, November 2006

Publisher: Kluwer Academic Publishers

ABSTRACT

“This study examines Social Programming, that is, the construction of programs using a Social Swarm algorithm based on Particle Swarm Optimization. Each individual particle represents choices of program construction rules, where these rules are specified using a Backus---Naur Form grammar. This study represents the first instance of a Particle Swarm Algorithm being used to generate programs. A selection of benchmark problems from the field of Genetic Programming are tackled and performance is compared to Grammatical Evolution. The results demonstrate that it is possible to successfully generate programs using the Grammatical Swarm technique. An analysis of the Grammatical Swarm approach is presented on the dynamics of the search. It is found that restricting the search to the generation of complete programs, or with the use of a ratchet constraint forcing individuals to move only if a fitness improvement has been found, can have detrimental consequences for the swarms performance and dynamics.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1180219.1180223&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

*************************************************************************

Evolutionary swarm design of architectural idea models

Sebastian von Mammen, Christian Jacob

University of Calgary, Calgary, AB, Canada, July 2008

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, Atlanta, GA, USA

Publisher: ACM

ABSTRACT

“In this paper we present a swarm grammar system that makes use of bio-inspired mechanisms of reproduction, communication and construction in order to build three-dimensional structures. Ultimately, the created structures serve as idea models that lend themselves to inspirations for architectural designs.

Appealing design requires structural complexity. In order to computationally evolve swarm grammar configurations that yield interesting architectural models, we observe their productivity, coordination, efficiency, and their unfolding diversity during the simulations. In particular, we measure the numbers of collaborators in each swarm individual's neighborhood, and we count the types of expressed swarm agents and built construction elements. At the end of the simulation the computation time is saved and the created structures are rated with respect to their approximation of pre-defined shapes. These ratings are incorporated into the fitness function of a genetic algorithm. We show that the conducted measurements are useful to direct an evolutionary search towards interesting yet well-constrained architectural idea models.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1389095.1389115&coll=ACM&dl=ACM&CFID=47460721&CFTOKEN=36888833

 

Full text available for ACM Digital Library Members:

PdfPdf (1.05 MB)

http://portal.acm.org/ft_gateway.cfm?id=1389115&type=pdf&coll=ACM&dl=ACM&CFID=47460721&CFTOKEN=36888833

 

 

*************************************************************************

Generative and developmental systems

Kenneth O. Stanleym University of Central Florida, Orlando, FL, USA, July 2008

GECCO '08: Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation

Publisher: ACM

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1388969.1389081&coll=GUIDE&dl=GUIDE&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (4.10 MB)

http://portal.acm.org/ft_gateway.cfm?id=1389081&type=pdf&coll=GUIDE&dl=GUIDE&CFID=46014229&CFTOKEN=26545706

 

 

*************************************************************************

From Watson-Crick L systems to Darwinian P systems

Erzsébet Csuhaj-Varjú, Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, 1111 Budapest, Hungary

Carlos Martín-Vide, Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tárraco 1, 43005 Tarragona, Spain

Gheorgh Păaun, Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tárraco 1, 43005 Tarragona, Spain; Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 70700 Bucureşti, Romania

Arto Salomaa, Turku Centre for Computer Science, Lemminkäisenkatu 14A, 20520 Turku, Finland

August 2003

Natural Computing: an international journal , Volume 2 Issue 3, 2003

Publisher: Kluwer Academic Publishers  Hingham, MA, USA

ABSTRACT

“Watson-Crick L systems are language generating devices making use of Watson-Crick complementarity, a fundamental concept of DNA computing. These devices are Lindenmayer systems enriched with a trigger for complementarity transition: if a ``bad'' string is obtained, then the derivation continues with its complement which is always a ``good'' string. Membrane systems or P systems are distributed parallel computing models which were abstracted from the structure and the way of functioning of living cells. In this paper, we first interpret the results known about the computational completeness of Watson-Crick E0L systems in terms of membrane systems, then we introduce a related way of controlling the evolution in P systems, by using the triggers not in the operational manner (i.e., turning to the complement in a ``bad'' configuration), but in a ``Darwinian'' sense: if a ``bad'' configuration is reached, then the system ``dies'', that is, no result is obtained. The triggers (actually, the checkers) are given as finite state multiset automata. We investigate the computational power of these P systems. Their computational completeness is proved, even for systems with non-cooperative rules, working in the non-synchronized way, and controlled by only two finite state checkers; if the systems work in the synchronized mode, then one checker for each system suffices to obtain the computational completeness.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=903811.903820&coll=GUIDE&dl=GUIDE&CFID=46014229&CFTOKEN=26545706

 

 

***********************************

A remark on evolutionary systems

Erzsébet Csuhaj-Varjú, Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende utca 13-17, H-1111 Budapest, Hungary

Jürgen Dassow, Fakultät für Informatik Otto-von-Guericke-Universität Magdeburg, PSF 4120, D-39016 Magdeburg, Germany

Discrete Applied Mathematics , Volume 146 Issue 1, February 2005

Publisher: Elsevier Science Publishers B. V.,  Amsterdam, The Netherlands

ABSTRACT

Evolutionary systems have been introduced by Csuhaj-Varjú and Mitrana (Acta Inform. 36 (2000) 913) who proved that two context-sensitive or three context-free components are sufficient to obtain all recursively enumerable languages. We improve these results by showing that two context-free components are sufficient to generate all recursively enumerable languages. Furthermore, we study the power of systems with one component.

 (FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1080499.1080511&coll=GUIDE&dl=GUIDE&CFID=46014229&CFTOKEN=26545706

 

 

*************************************************************************

Regular expression generation through grammatical evolution

Ahmet Cetinkaya, Istanbul Technical University

July 2007

GECCO '07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, London, United Kingdom

Publisher: ACM

ABSTRACT

“This study investigates automatic regular expression generation using Grammatical Evolution. The software implementation is based on a subset of POSIX regular expression rules. For fitness calculation, a multiline text file is supplied. Lines which are required to match with generated regular expressions are specified beforehand. Fitness is evaluated according to the successful match results. Using this fitness evaluation strategy, preliminary tests have been performed on different files. Results indicate that the Grammatical Evolution approach to automatic generation of regular expressions is promising.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1274000.1274089&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

Full text available for ACM Digital Library Members:

PdfPdf (83.88 KB)

http://portal.acm.org/ft_gateway.cfm?id=1274089&type=pdf&coll=ACM&dl=ACM&CFID=47333874&CFTOKEN=32485152

 

 

*************************************************************************

Active Coevolutionary Learning of Deterministic Finite Automata

Josh Bongard, Hod Lipson

December 2005

The Journal of Machine Learning Research , Volume 6

Publisher: MIT Press

ABSTRACT

“This paper describes an active learning approach to the problem of grammatical inference, specifically the inference of deterministic finite automata (DFAs). We refer to the algorithm as the estimation-exploration algorithm (EEA). This approach differs from previous passive and active learning approaches to grammatical inference in that training data is actively proposed by the algorithm, rather than passively receiving training data from some external teacher. Here we show that this algorithm outperforms one version of the most powerful set of algorithms for grammatical inference, evidence driven state merging (EDSM), on randomly-generated DFAs. The performance increase is due to the fact that the EDSM algorithm only works well for DFAs with specific balances (percentage of positive labelings), while the EEA is more consistent over a wider range of balances. Based on this finding we propose a more general method for generating DFAs to be used in the development of future grammatical inference algorithms.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1046920.1194900&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (288.07 KB)

http://portal.acm.org/ft_gateway.cfm?id=1194900&type=pdf&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

*************************************************************************

A more bio-plausible approach to the evolutionary inference of finite state machines

Hooman Shayani, Peter J. Bentley

July 2007

GECCO '07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, University College London

Publisher: ACM

ABSTRACT

“With resemblance of finite-state machines to some biological mechanisms in cells and numerous applications of finite automata in different fields, this paper uses analogies and metaphors to introduce an element of bio-plausibility to evolutionary grammatical inference. Inference of a finite-state machine that generalizes well over unseen input-output examples is an NP-complete problem. Heuristic algorithms exist to minimize the size of an FSM keeping it consistent with all the input-output sequences. However, their performance dramatically degrades in presence of noise in the training set. Evolutionary algorithms perform better for noisy data sets but they do not scale well and their performance drops as size or complexity of the target machine grows. Here, inspired by a biological perspective, an evolutionary algorithm with a novel representation and a new fitness function for inference of Moore finite-state machines of limited size is proposed and compared with one of the latest evolutionary techniques.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1274000.1274039&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (269.46 KB)

http://portal.acm.org/ft_gateway.cfm?id=1274039&type=pdf&coll=ACM&dl=ACM&CFID=46014229&CFTOKEN=26545706

 

 

*************************************************************************

Evolved finite state controller for hybrid system

Jean-François Dupuis, Technical University of Denmark, Kgs. Lyngby, Denmark

Zhun Fan, Technical University of Denmark, Kgs. Lyngby, Denmark

Erik Goodman, Michigan State University, East Lansing, MI, USA

June 2009

GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation

Publisher: ACM

ABSTRACT

“This paper presents an evolutionary methodology to automatically generate finite state automata (FSA) controllers to control hybrid systems. FSA controllers for a case study of two-tank system have been successfully obtained using the proposed evolutionary approach. Experimental results show that these controllers have good performance on the set of training targets as well as on a randomly generated set of validation targets.”

(FGS Link, July, 2009)

http://portal.acm.org/citation.cfm?id=1543834.1543850&coll=GUIDE&dl=GUIDE&CFID=46014229&CFTOKEN=26545706

 

Full text available for ACM Digital Library Members:

PdfPdf (6.04 MB)

http://portal.acm.org/ft_gateway.cfm?id=1543850&type=pdf&coll=GUIDE&dl=GUIDE&CFID=46014229&CFTOKEN=26545706

 

 

***********************************************************

Computación Evolutiva (CE)

 

*********************************************

Dr. Carlos A. Coello Coello

 

Introducción a la Computación Evolutiva (Presentación)

Dr. Carlos A. Coello Coello

http://delta.cs.cinvestav.mx/~ccoello/compevol/clase2-2006.pdf

 

Introducción a la Computación Evolutiva (Notas de Curso)

Dr. Carlos A. Coello Coello

http://weblidi.info.unlp.edu.ar/catedras/neuronales/Apunte%20Coello%20Coello.pdf

 

Introducción a la Computación Evolutiva Carlos A. Coello Coello

http://www.cs.cinvestav.mx/~EVOCINV/tutorials/computacionevolutiva..htm

 

The Evolutionary Computation Group at CINVESTAV-IPN (EVOCINV)

http://www.cs.cinvestav.mx/~EVOCINV/

http://www.cs.cinvestav.mx/~EVOCINV/publications.html

 

 

GECCO Genetic and Evolutionary Computation Conference

http://gal4.ge.uiuc.edu:8080/GECCO-2003/

 

 

********************************************

Genetic programming / Programación genética

Algoritmos genéticos

 

The Genetic Algorithms Archive is a repository for information related to research in genetic algorithms and other forms of evolutionary computation

http://www.aic.nrl.navy.mil/galist/

 

 

Home Page of John R. Koza

http://www.genetic-programming.com/johnkoza.html

 

John Koza’s Publications on Genetic Programming

http://www.genetic-programming.com/#_John_Koza’s_Publications

 

 

Welcome to

www.genetic-programming.com

(the home page of Genetic Programming Inc., a privately funded research group that does research in applying genetic programming)

http://www.genetic-programming.com/

 

**************************

 

Algoritmos genéticos (general)

http://www.rennard.org/alife/english/gavintrgb.html

 

http://cs.felk.cvut.cz/~xobitko/ga/

 

(aplicados a juegos)

 http://www.gignews.com/gregjames1.htm

 

Evolutionary algorithms

scholarpedia

http://www.scholarpedia.org/article/Evolutionary_algorithms

 

Informática evolutiva Juan Julián Merelo Guervós

http://geneura.ugr.es/~jmerelo/ie/intro.htm

 

Informática evolutiva: Algoritmos genéticos Juan Julián Merelo Guervós

http://geneura.ugr.es/~jmerelo/ie/ags.htm

 

 

********************************************

Algoritmos Culturales

Alberto Ochoa O. Zezzatti, Gaceta Ide@s CONCYTEG Año 3. Núm. 31, 21 de enero de 2008

http://energia.guanajuato.gob.mx/gaceta/Gacetaideas/Archivos/31052008_ALGORITMOS_CULTURALES.pdf

 

 

*********************************************

Ángel García Baños

 

Curso de Computación Evolutiva (CE)

Angel García Baños

Profesor titular de la Escuela de Ingeniería de Sistemas y Computación  de la Universidad del Valle (Cali - Colombia)

Las transparencias que componen el curso

Tema 1: Introducción a la asignatura. Introducción a la evolución.

Tema 2 : Algoritmos genéticos. Paralelismo. Teorema fundamental. Multiobjetivo. Ejemplos con problemas combinatorios.
Tema 1: Introducción a la asignatura. Introducción a la evolución.

Tema 2 : Algoritmos genéticos. Paralelismo. Teorema fundamental. Multiobjetivo. Ejemplos con problemas combinatorios.

Tema 3: Programación genética. Evolución gramatical. Programación por expresión genética.

Tema 4 : Programación evolutiva. Estrategias evolutivas.

Tema 5 : Sistemas clasificadores.

Tema 6: Simulated annealing.

Tema 7: Límites computacionales fundamentales.

Tema 8: Autoduplicación. Complejidad. Autómatas celulares. Constructor universal de von Neumann.

Tema 9: Teoría de juegos. Dilema del prisionero. Emergencia. Señalización.

Tema 10: Mundos artificiales. Hormigas Artificiales. Arte evolutivo por computador.

Tema 11: Caos. Fractales.

Tema 12: Teorema de "no-free-lunch".

Tema 13: Conclusiones y resumen.

http://eisc.univalle.edu.co/~angarcia/ce/ce_material.html

 

 

Mundos Artificiales

Angel García Baños

Grupo EVA (Evolución y Vida Artificiales), Escuela de Ingeniería de Sistemas y Computación, Facultad de Ingenierías, Universidad del Valle

COLOQUIO EPISTEME, marzo de 2008 v2

http://eisc.univalle.edu.co/~eva/mundosArtificiales.pdf

 

Computación Evolutiva (CE)

Teorema de No-Free-Lunch

Angel García Baños

Escuela de Ingeniería de Sistemas y Computación, Universidad del Valle, 04 de febrero de 2008

http://eisc.univalle.edu.co/~angarcia/ce/ce_clases/ce-12_%20NFL.pdf

 

 

***********************************************************

Evolving Matrices  / Matrices Evolutivas

 

Adquisición de conocimientos utilizando matriz evolutiva

Jorge Martínez Muñoz

Carreras : Ing. Industrial [Maestria], Tesis

Plantel : Instituto Tecnológico de Toluca

http://www.triangulum.org.mx/CO_FichaLibro.asp?IDI=9993&DSD=LT

 

Learning Matrices and Their Applications
Steinbuch, K.   Piske, U.A.W.

Institute for Information Processing and Communication, Technische Hochschule Karlsruhe;

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4038031

 

“Fast Diagonalization of Evolving Matrices: Application to Spin-Fermion

Models

E. F. D’Azevedo*, P. K. Nukala, G. Alvarez

Oak Ridge National Laboratory

Advanced Scientific Computing Research Applied Mathematics

http://www.sc.doe.gov/ascr/Research/AM/07AccompPDFs/ORNL-DAzevedo.pdf

 

EPSRC Consortium: Multi-Scale Diffusion Phenomena for Advanced Materials Manufacture

Draft Proposal 24/09/07

“evolving matrices are ones in which the matrix

microstructure changes with time. Interacting matrices are ones in which there is strong”

http://www.umi.surrey.ac.uk/UserFiles/file/MSDP%20Draft%20070924.pdf

 

The Markov Process as a Compositional Model: A Survey and Tutorial

Charles Ames

Leonardo, Vol. 22, No. 2 (1989), pp. 175-187

Published by: The MIT Press

 “If standard first- order matrices will not suffice, one might consider Nth-order matrices, evolving matrices or chains of chains. ...”

http://www.jstor.org/pss/1575226

 

Interior Penalty Finite Element Approximation of Navier-Stokes Equations and Application to Free Surface Flows

Christoph Winkelmann

Public Defense CMCSEPFL, December 5th 2007

http://iacs.epfl.ch/~winkelma/docs/public_defense.pdf

 

 

***********************************************************

Evolvable hardware  /  Hardware evolutivo

 

Evolvable hardware

Evolvable hardware (EH) is a new field about the use of evolutionary algorithms (EA) to create specialized electronics without manual engineering. It brings together reconfigurable hardware, artificial intelligence, fault tolerance and autonomous systems. Evolvable hardware refers to hardware that can change its architecture and behavior dynamically and autonomously by interacting with its environment.” (Wikipedia, 8/vii/2010)

http://en.wikipedia.org/wiki/Evolvable_hardware

 

 

On evolvable hardware

Timothy GW Gordon and Peter J. Bentley University College London

http://www.cs.ucl.ac.uk/staff/t.gordon/scie.pdf

 

 

Crean el primer prototipo de hardware evolutivo

Abre nuevas vías para el desarrollo de una Inteligencia Artificial más avanzada

Raúl Morales, TENDENCIAS21, TENDENCIAS INFORMÁTICAS, Martes 3 Abril 2007

 

“Un equipo de investigadores noruegos ha creado la primera pieza de un hardware que usa la evolución para cambiar su diseño y adaptarse a la función que tiene que desempeñar. Este hardware evoluciona como lo harían las especies animales o vegetales y se adapta al medio sin que sufra su funcionalidad y en apenas unos segundos. En vez de actualizar software, el hardware es capaz de evolucionar, probar soluciones ante los problemas y adoptar la decisión más adecuada. Esta investigación abre la puerta a desarrollos de Inteligencia Artificial más avanzados.

Los profesores Kyrre Glette y Jim Torresen de la Facultad de Informática de la Universidad de Oslo han publicado un artículo en el que presentan un prototipo de hardware evolutivo capaz de adaptarse en unos segundos a la función que desarrolla en cada momento. La Universidad de Oslo ha explicado este proyecto en su revista Apollon, del que se ha hecho eco Bitsofnews.”

http://www.tendencias21.net/Crean-el-primer-prototipo-de-hardware-evolutivo_a1484.html

 

 

A semejanza de las neuronas

Producen el primer circuito de procesamiento evolutivo

MADRID, 26 Abr. (EUROPA PRESS) -, 20100426

“   Los circuitos de procesamiento de información en los ordenadores de la era digital son estáticos. Como ventaja comparativa, en nuestro cerebro, estos mismos circuitos de procesamiento de información --las neuronas-- evolucionan continuamente para resolver problemas complejos.

   Ahora, un equipo internacional de investigadores del National Institute of Information and Comunication Technology, de Japón, y la Universidad Tecnológica de Michigan ha creado un proceso similar de evolución en el circuito de una base orgánica molecular que puede resolver problemas complejos. Esta es la primera vez que se produce un circuito evolutivo a semejanza de los que forman el cerebro.”

http://www.europapress.es/sociedad/ciencia/noticia-producen-primer-circuito-procesamiento-evolutivo-20100426121006.html

 

 

***********************************************************

Evolving Cellular Automata

 

Evolving Cellular Automata: Papers

Last updated: 17 Feb 00

http://cse.ucdavis.edu/~evca/evabstracts.html

 

 

***********************************************************

Evolution and the Theory of Games 

 

Cover

Cover of Evolution and the Theory of Games, with an exemplary ternary plot of frequency changes of three different strategies.

Evolution and the Theory of Games

Author John Maynard Smith

Publication date 1982

“Evolution and the Theory of Games is a 1982 book by the British evolutionary biologist John Maynard Smith on evolutionary game theory. In it, Maynard Smith summarises work on evolutionary game theory that had developed in the 1970s, to which he made several important contributions. The book is also noted for being well written and not overly mathematically challenging.

The main contribution to be had from this book is the introduction of the Evolutionarily Stable Strategy, or ESS, concept, which states that for a set of behaviours to be conserved over evolutionary time, they must be the most profitable avenue of action when common, so that no alternative behaviour can invade.” (Wikipedia 25/vii/2010)

http://en.wikipedia.org/wiki/Evolution_and_the_Theory_of_Games

 

Evolution and the Theory of Games

John Maynard Smith

University of Sussex

Cambridge University Press, 1982

“Professor John Maynard Smith has written an account of a new way of thinking about evolution which has been developed in the last ten years. The theory of games, first developed to analyse economic behaviour, is modified so that it can be applied to evolving populations. John Maynard Smith's concept of an evolutionarily stable strategy is relevant whenever the best thing for an animal or plant to do depends on what others are doing. The theory leads to testable predictions about the evolution of behaviour, of sex and genetic systems, and of growth and life history patterns. This book contains the first full account of the theory, and of the data relevant to it. The account is aimed at senior undergraduate and graduate students, teachers and research workers in animal behaviour, population genetics and evolutionary biology. The book will also be of interest to mathematicians and game theorists; the mathematics has been largely confined to appendixes so that the main text may be easily followed by biologists.” (FGS Link, 26/vii/2010)

http://www.cambridge.org/catalogue/catalogue.asp?isbn=0521288843

 

 

John Maynard Smith

John Maynard Smith,[1] F.R.S. (6 January 1920 – 19 April 2004) was a British theoretical evolutionary biologist and geneticist. Originally an aeronautical engineer during the Second World War, he then took a second degree in genetics under the well-known biologist J.B.S. Haldane. Maynard Smith was instrumental in the application of game theory to evolution and theorized on other problems such as the evolution of sex and signalling theory.

… In 1973 Maynard Smith formalised a central concept in game theory called the evolutionarily stable strategy (ESS), based on a verbal argument by George R. Price. This area of research culminated in his 1982 book Evolution and the Theory of Games” (Wikipedia 26/vii/2010)

http://en.wikipedia.org/wiki/John_Maynard_Smith#Evolution_and_the_Theory_of_Games

 

John Maynard Smith

John Maynard Smith (6 de enero de 192019 de abril de 2004). Genetista e investigador en biología evolutiva.

...Maynard Smith es una de las figuras clave de la escuela neodarwinista. Originalmente ingeniero aeronáutico durante la segunda guerra mundial, cambiando sorpresivamente su visión al campo de la genética y la ecología bajo el mando del famoso biólogo J. B. S. Haldane cuando cambio por completo su formación académica y se vinculó al University College London. los primeros aportes de Maynard Smith a la biología evolutiva fue simplemente reconocer de forma inmediata la idea de otro biólogo evolutivo W. D. Hamilton el cual planteaba que en humanos y en insectos eusociales opera sobre los genes y no sobre la población como otros proponían, por primera vez se utilizo el termino " Kin selection "

Por ejemplo, fue a partir de sus ideas como Richard Dawkins desarrolló la teoría del gen egoísta. Maynard Smith Fue el primero en aplicar la teoría de juegos al estudio de la biología evolutiva.” (Wikipedia 26/vii/2010)

http://es.wikipedia.org/wiki/John_Maynard_Smith

 

 

Evolutionary game theory

Evolutionary game theory (EGT) is the application of game theory to interaction dependent strategy evolution in populations. EGT is useful in a biological context by defining a framework of strategies in which adaptive features can be modeled. It originated in 1973 with John Maynard Smith and George R. Price's formalization of evolutionarily stable strategies as an application of the mathematical theory of games to biological contexts[1], arising from the realization that frequency dependent fitness introduces a strategic aspect to evolution. EGT differs from classical game theory by focusing on the dynamics of strategy change more than the properties of strategy equilibria. Despite its name, evolutionary game theory has become of increasing interest to economists, sociologists, anthropologists, and philosophers.” (Wikipedia 25/vii/2010)

http://en.wikipedia.org/wiki/Evolutionary_game_theory

 

Teoría evolutiva de juegos

“La teoría evolutiva de juegos (EGT) es la aplicación de modelos inspirados en genética de la población de cambios de la frecuencia genética en poblaciones a la teoría de juegos. Difiere de la teoría de juegos clásica en que se concentra en las dinámicas de la estrategia en lugar de sus equilibrios. A pesar de su nombre, la teoría evolutiva de juegos se aplica más en economía que en biología.

La metodología habitual para estudiar las dinámicas evolutivas en un juego es a través de las ecuaciones de replicador. Las ecuaciones de replicador asumen población infinita, tiempo continuo y mezcla completa. Los atractores de las ecuaciones son equivalentes con los estados evolutivamente estables.” (Wikipedia 25/vii/2010)

http://es.wikipedia.org/wiki/Teor%C3%ADa_evolutiva_de_juegos

 

 

Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics

Carlos P. Roca, José A. Cuesta, Angel Sánchez

Available online 7 August 2009

“Abstract

Evolutionary game dynamics is one of the most fruitful frameworks for studying evolution in different disciplines, from Biology

to Economics. Within this context, the approach of choice for many researchers is the so-called replicator equation, that describes

mathematically the idea that those individuals performing better have more offspring and thus their frequency in the population

grows. While very many interesting results have been obtained with this equation in the three decades elapsed since it was first

proposed, it is important to realize the limits of its applicability. One particularly relevant issue in this respect is that of non-meanfield

effects, that may arise from temporal fluctuations or from spatial correlations, both neglected in the replicator equation. This

review discusses these temporal and spatial effects focusing on the non-trivial modifications they induce when compared to the

outcome of replicator dynamics. Alongside this question, the hypothesis of linearity and its relation to the choice of the rule for

strategy update is also analyzed. The discussion is presented in terms of the emergence of cooperation, as one of the current key

problems in Biology and in other disciplines.”

http://gisc.uc3m.es/~cuesta/PDFs/PLR06208.pdf

 

 

***********************************************************

Robotic minds think alike?

ICT Results, 27 March 2008

“Most schoolchildren struggle to learn geometry, but they are still able to catch a ball without first calculating its parabola. Why should robots be any different? A team of European researchers have developed an artificial cognitive system that learns from experience and observation rather than relying on predefined rules and models.”

http://cordis.europa.eu/ictresults/index.cfm?section=news&tpl=article&ID=89632

 

 

***********************************************************

 

 

Ir a

Evolución y Sistemas Evolutivos, Sistemas Afectivos y Sistemas Concientes

 

Evolución y Sistemas Evolutivos           Sistemas Afectivos             Sistemas Concientes

Matrices Evolutivas y Dinámica Dimensional

 

 

 

Go to   Evolution and Evolutionary Systems      /      Ir a   Evolución y Sistemas Evolutivos

Go to   Principal Page       /       Ir a   Página Principal

 

Go to   Links Pages         /        Ir a   Páginas de Ligas

 

FGS Papers     /     Artículos de FGS

Papers     /     Artículos

Thesis over Evolutionary Systems     /     Trabajos de titulación sobre sistemas evolutivos

Pages of peoples and organizations over Evolutionary Systems     /     Páginas de personas y organizaciones sobre sistemas evolutivos

Complementary Bibliography over Evolutionary Systems     /     Bibliografía complementaria sobre sistemas evolutivos

 

Evolution     /     Evolución

History of evolutionary thought     /     Historia del Pensamiento Evolutivo

Approaches, Methods and Tools     /     Enfoques, Métodos y Herramientas

Applications     /     Aplicaciones

Book´s     /     Libros

Events     /     Eventos

Others link over Evolutionary Systems     /     Otras ligas sobre sistemas evolutivos