Evolució gramatical

La evolució gramatical és una tècnica relativament nova de computació evolutiva iniciada per Conor Ryan, JJ Collins i Michael O'Neill en 1998 en el Grup BD S en l'Universitat de Limerick.

Es relaciona en l'idea de Programació Genètica que l'objectiu és trobar un programa eixecutable o fragment de programa, que conseguixca un bon valor de comportament per a la funció objectiu donada. En la majoria dels treballs publicats sobre la Programació Genètica, una expressió en forma d'arbre és estructurada a l'estil LISP es maneja directament, mentres que l'Evolució gramatical aplica operadors genètics (operador genètic) a una cadena d'número entero, posteriorment assignada a un programa per mig de l'us d'una gramàtica.

Un dels beneficis d'Evolució Gramatical (GE) és que este mapage simplifica l'aplicació de la busca a diferents llenguages de programació i atres estructures.

Problema abordat

En la programació genètica a l'estil convencional de Koza, el conjunt de funcions deu complir el requisit de tancament: totes les funcions deuen ser capaces d'acceptar com a arguments l'eixida de totes les demés funcions en el conjunt de funcions.

Per lo general, açò s'implementa tractant en un únic tipo de senyes, com a punt flotant de doble precisió. Mentres que els marcs de programació genètica moderns recolzen la tipificación, tals sistemes de tipo tenen llimitacions que l'evolució gramatical no sofrix.

La solució d'Evolució Gramatical

Evolució Gramatical oferix una solució a este problema per mig de l'evolució de les solucions d'acort a una gramàtica especificada per l'usuari (per lo general una gramàtica en la forma de Backus-Naur). Per lo tant, l'espai de busca pot ser restringit, i el coneiximent del domini del problema pot ser incorporat. L'inspiració per a este enfocament ve d'un desig de separar el "genotip" de el "fenotip": vist des del punt de vista de la Programació Genètica, els objectes sobre els que opera l'algoritme de busca i lo que la funció d'evaluació de l'aptitut interpreta són una i la mateixa. En contrast, els "genotips" d'Evolució Gramatical són llestes ordenades d'número entero que es codifiquen per a seleccionar regles de la gramàtica lliure de context proporcionada. El fenotip, no obstant, és el mateix que en l'estil Koza: una estructura similar a un arbre que s'evalua recursivamente. Este model està més en llínea en la forma en que la genètica funciona en la naturalea, a on hi ha una separació entre el genotip d'un organisme i l'expressió final del fenotip en les proteïnes, etc.

Observe que els objectes de l'Evolució Gramatical actuen com a buscador de la mateixa manera que són utilisat en els algoritmes genètics. Açò significa, en principi, que qualsevol paquet d'algoritme genètic existent, com el popular GAlib, pot utilisar-se per a portar a terme la busca, i un desenrollador que implemente un sistema d'Evolució Gramatical només deu preocupar-se per portar a terme el mapage des de la llista de sancers fins a l'arbre de programes. També és possible en principi realisar la busca utilisant algun atre método, com l'optimisació de l'eixam de partícules (vore l'observació a continuació); La naturalea modular de l'Evolució Gramatical crea moltes oportunitats per als híbrits a mida que el problema d'interés és va resultar.

Brabazon i O'Neill han aplicat en èxit l'Evolució Gramatical per a predir la fallida corporativa, la previsió d'índexs bossístics, les calificacions creditícies d'abonaments i atres aplicacions financeres. L'Evolució Gramatical també s'ha utilisat en el clàssic model predador-assut per a explorar l'impacte dels paràmetros tals com l'eficàcia dels depredadors, el número de casetes i mutacions aleatòries sobre l'estabilitat ecològica.

És possible estructurar una gramàtica evolutiva que per a un conjunt de funció / terminal dau és equivalent a la programació genètica.

Vore també

• Programació genètica