Programacion Genetica

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ FACULTAD DE MATEMÁTICAS E INGENIERÍAS INGENIERÍA DE SISTEMAS PROGRAMACIÓN GENÉTICA Por: Pervys Rengifo Rengifo Leonardo Jiménez

El rápido avance en sistemas de procesamiento de información en las décadas recientes ha dirigido la investigación en ingeniería hacia el desarrollo de sistemas inteligentes que puedan evolucionar modelos de fenómenos naturales automáticamente, “por ellos mismos”. Dentro del desarrollo de estos sistemas inteligentes, se aplican, sobre todo, técnicas del Aprendizaje de Máquina(ML), de Minería de Datos(DM) y de Inteligencia Computacional(IC), las cuales han permeado diferentes campos de la investigación científica y, junto con la inmensa cantidad de datos que se han registrado, han permitido el desarrollo y aplicación, en diferentes disciplinas, de algunos procedimientos clasificados como modelos de cajas negras( o en ocasiones de caja gris), y que por su dependencia casi exclusiva de información histórica registrada, se han denominado modelos conducido por datos(data driven models). Dentro de estos modelos teóricos se pueden citar: Las Redes Neuronales Artificiales(ANN), los Árboles de Decisión(AD), Support Vector Machine(SVM) y la Programación Genética(PG), que junto con diferentes métodos de búsqueda heurística y meta heurística como: Quimiotaxis, Búsqueda Tabú, Simulated Annealing(SA), Algoritmos genéticos( y otros relacionados como los algoritmos culturales y los algoritmos inmunológicos), GRASP, Ant Colony Optimization(ACO), Particle Swarm Optimization(PSO) y con otras técnicas estadísticas y de teoría de sistemas de control tradicionales; han arrojado resultados promisorios, lo que se evidencia por la creciente investigación en estos tópicos[ ver por ejemplo: Abbott, M.B., 1997 ; Babovic V.et al., 2001; Bailer-Jones et al., 2001; Dibique Y. B. Et al. 2001; Babovic, V., et al, 2001a; Lorrai, M. Et al.,1995; Minns, A. W et al., 1996; Muller, K.R., et al., 1997; Quinlan, J. R., 1986; Koza, J. R., 1992] y la reciente aparición de revistas especializadas en temáticas, y la consolidación de “transdisciplinas” que involucran modelación convencional, modelación manejada por datos y modelación soportada en conocimientos, aplicadas a contextos que requieren una visión interdisciplinar, que enriquezca y permita una aproximación más efectiva a muchos problemas complejos, como es el caso de la Hidroinformática, Bioinformática, Ecohidroinformática [Abbott, M.B., 1997]. Esto ha facilitado la aplicación de técnicas combinadas en modelos híbridos y la integración de Sistemas de Soporte de Decisión(DSS) para el manejo de sistemas. En Colombia, la comunidad académica ya se está interesando en estas temáticas como puede apreciarse por algunas aplicaciones de Redes Neuronales Artificiales, de Árboles de Decisión y de Lógica Difusa reportadas, por algunos autores. Sin embargo, a pesar del éxito relativo en aplicaciones prácticas en muchos campos de las ciencias y la ingeniería, estas técnicas han sido fuertemente criticadas, ya que, la mayoría de ellas, sólo proveen resultados operativos y no

obtienen explícitamente la función que transforma las entradas en salidas, es decir la función de transformación que representa al sistema. Sin embargo, es innegable que son un camino efectivo y eficiente para modelar los fenómenos en situaciones en donde el conocimiento explícito de los subprocesos internos no se requieren, como es el caso de muchas situaciones prácticas en ingeniería. No obstante, en la minería de datos para propósitos científicos se debe hallar un equilibrio entre la interpretabilidad y la potencia predictiva de las soluciones propuestas o hipótesis. En este sentido algunas técnicas hacen énfasis en la parte de la interpretabilidad( por ejemplo Árboles de Decisión y Sistemas Basados en Reglas), mientras que otras son capaces de ajustar datos hasta cualquier grado de precisión deseado( por ejemplo las Redes Neuronales Artificiales y la Programación Genética). En descubrimiento científico ambos aspectos deben ser abordados con sobriedad, ya que soluciones con alta precisión, sin interpretación no conducen a nuevas ideas, asimismo que soluciones fácilmente interpretables sin mucha precisión pueden proporcionar ideas que son erróneas o simplemente falsas. Dentro de las técnicas mencionadas tiene un especial interés, la Programación Genética, la cual consiste en la evolución automática de programas usando ideas basadas en la selección natural, permitiendo realizar regresión simbólica, esto es, permite obtener además de un dato numérico predictivo, una expresión matemática en función de las variables de entrada, que pretende identificar al sistema estudiado en lo que respecta al proceso modelado. Esto posibilita la interpretación de los resultados, en cuanto a la dependencia entre las variables y en cuanto a la plausibilidad física de la expresión obtenida. De todas las técnicas de minería de datos, como se sugirió antes, la Programación Genética es la más promisoria en la inducción de expresiones interpretables, mostrando además precisión competitiva. La aplicación de la programación genética para realizar regresión simbólica permitiría aumentar la expresividad de la relación entre variables independientes y dependientes en un problema dado, ya que lo que típicamente se hace es suponer una forma de relación funcional entre las variables( que en la mayoría de los casos corresponde a formas lineales o de alguna forma linealizables) y luego mediante regresión de mínimos cuadrados estimar los coeficientes. Esto a pesar de haber permitido resolver muchos problemas a lo largo de muchos años, también ha limitado la aplicación de formas funcionales no lineales. A la fecha, ya son muchos los investigadores que han desarrollado modelos inspirados en regresión simbólica, aplicados a diversos problemas en ingeniería[ver IHE-Stowa, 2001; ASCE, 2002, Dibique Y. B. Et al, 2001; Obregón N.,1999; Obregón N., 2002; Obregón N., 2002ª, Obregón N., 2003, Tokar, A. S. Et al. , 2000; Cousin, N. Et al., 1997; Keijzer, M. Et al. 1999, Morshed, J. Et al. 1998; Solomatine D. P. Et al. 1996; Tsoukalas, L. H. Et al., 1997; Smith, J., et al. 1995; Abbot, M. B., 1997; Solomatine, D. P. 2002; Koza, 1992], sin embargo en la literatura científica colombiana, hasta donde se ha revisado, a pesar de la existencias de algunos trabajos desarrollados en el departamento de Ingeniería de Sistemas de la Universidad Nacional de Colombia(Velasquez, J. D., 1997) y los presentados en algunos congresos, son pocas las publicaciones que se han reportado sobre programación genética.

La actividad económica moderna, así como muchas otras, descansan en el manejo de grandes volúmenes de información, la cual da lugar a las bases de datos. En la actualidad tanto la cantidad como el tamaño de las bases de datos crece rápidamente. Se desarrollan grandes bases de datos (medidas en giga y terabytes) sobre datos de los consumidores, historia de transacciones, registros de ventas, etc... En 1990 se calculaba que existían más de medio millón de estas grandes bases de datos en el mundo. La cantidad total de datos almacenados en las computadoras se duplica cada cinco años (aunque otros estimados plantean que cada 20 meses) y se espera que el futuro se duplique cada año. Este crecimiento de la cantidad de información almacenada ha sido mayor que el desarrollo de la potencia de procesamiento; las capacidades para coleccionar y almacenar datos ha sobrepasado la habilidad para analizarlos, resumirlos y extraer conocimiento a partir de ellos. Esto ha conducido a un interés creciente en desarrollar con fuerza la potencia de procesamiento para lograr una mejor utilización de los datos almacenados. Aunque uno de los propósitos primarios del almacenamiento de información es su recuperación eficiente posterior, cada vez más esta recuperación no es necesariamente una copia fiel de los datos almacenados, sino de una nueva información que pueda ser inferida a partir de estos. Es decir, desarrollar la capacidad de interpretar los datos y poder actuar basado en estas interpretaciones; de allí la fuerte relación entre la minería de datos y los sistemas de ayuda a la toma de decisiones. Todo esto sugiere el uso de técnicas de minería de datos, con el fin de poder generar conocimiento a partir de la información disponible y mejorar sustancialmente, aunque de forma indirecta, la comprensión de algunos procesos y abordar modelos novedosos que hagan uso intensivo de los datos, y que permitan resolver problemas operativos a partir de la información disponible. Sin embargo, dentro de los investigadores colombianos no es de conocimiento generalizado el uso de estas técnicas de minería de datos, sobre todo de Programación Genética y menos en su forma de regresión simbólica, por lo que es necesario iniciar un proceso de difusión e ilustración de las potencialidades de las mismas, con el fin de estimular la investigación y la aplicación de estas técnicas que, lejos de ser difíciles, son muy sencillas y fáciles de usar. Además, hay una falta de bibliografía general sobre estos temas, y la poca que hay es de difícil consecución o esta muy dispersa para propósitos prácticos; por lo tanto, se hace necesario la consolidación de un marco conceptual amigable y disponible, que integre de forma inteligente la bibliografía existentes y se constituya en una referencia de consulta básica para las investigaciones posteriores sobre estas temáticas. En concordancia con todo lo expuesto anteriormente se propone:  Constituir un marco conceptual comprensible, que permita establecer claramente los procedimientos involucrados en las aplicaciones más comunes, de la PG, en su forma de regresión simbólica, dando elementos y sugerencias para potenciar e incrementar la aplicabilidad de la PG, a otros problemas, que representándolos de manera adecuada pudieran ser tratados exitosamente.  Identificar problemas, que al resolverlos con programación genética, permitan ilustrar los conceptos y procedimientos fundamentales de la regresión simbólica sugeridos en el marco conceptual.



Desarrollar herramientas informáticas que faciliten el uso de la regresión simbólica en nuestro medio, incentivando investigaciones en esta dirección, llevando, a mediano plazo a proporcionar una gran evidencia del éxito de la aplicación de la PG en muchos campos del conocimiento.

Con esta propuesta se busca pues, contribuir de forma efectiva a la comprensión de los aspectos fundamentales de la Programación Genética, como también a la aplicabilidad práctica de este paradigma en la solución de problemas que involucren regresión simbólica. Esta investigación que se propone, que tiene el carácter de investigación básica, podría generar toda una serie de investigaciones sobre aplicaciones y potenciación de la Programación Genética como herramienta operativa y de análisis en ingeniería. Además, si se hace una difusión adecuada dentro del medio académico, en poco tiempo se podría tener investigaciones similares dentro de otras disciplinas, que sin duda, valorarán la gran representatividad y las impensadas posibilidades de la Programación Genética, en sus múltiples aplicaciones. Esta investigación se constituiría en una primera aproximación a la programación genética que daría el soporte conceptual suficiente para iniciar diferentes proyectos aplicados a casos específicos en donde se disponga de datos históricos. En el futuro cercano podría conducir a la exploración integral de las diferentes formas y aplicaciones de la programación genética, que podría soportar el estudio del descubrimiento científico por computador y la evolución de estructuras más complejas, como circuitos, cadenas de proteínas, etc., como ya ha sido ampliamente reportado por Koza[1992]. Por otra parte, en el futuro, también se podría, consolidar una herramienta computacional que involucre las diferentes técnicas de estadística multivariada y de inteligencia computacional( Redes Neuronales, Support Vector Machine, Arboles de Decisión, Programación genética, etc.), para realizar minería de datos de forma efectiva. Es de anotar que la temática que se aborda, además de estar dentro de la tendencia mundial en investigación en ingeniería, y es altamente pertinente, dado el estado actual del conocimiento y las inmensas posibilidades que involucra la evolución automática de programa de computador debidamente representados, en la solución de problemas reales. De esta forma, el problema que se propone abordar mediante esta investigación se puede formular así: ¿Cómo contribuir al entendimiento y aplicabilidad de la programación genética en su forma de regresión simbólica? La cual es motivada por la enorme potencialidad que se ha identificado en la PG como paradigma de modelación, y la preocupación por la actualización permanente que debe caracterizar a un programa de ingeniería de sistemas y corresponde a un convencimiento por parte de los proponentes de que es posible contribuir de manera efectiva al mejoramiento de la comprensión y modelación de la regresión simbólica, por medio del entendimiento y potenciación de la aplicabilidad de la Programación Genética, y que da lugar de forma natural a la hipótesis básica con la cual se inicia esta investigación:

“Mediante herramientas conceptuales y computaciones que ilustren los procedimientos y la potencia aplicativa de la Programación Genética se puede contribuir de manera efectiva a su entendimiento y se puede fomentar su aplicación” La cual se soporta en la convicción de que las expresiones simbólicas que se generan mediante programación genética pueden resultar convenientes para el análisis y la interpretación en modelación. Esta investigación se constituye en una excelente oportunidad científica para contribuir desde la FUKL, inicialmente en el ámbito nacional, constituyéndose en un estudio pionero, puesto que sólo se conocen pocas referencias anteriores de investigaciones en temáticas similares( sobre todo en Redes Neuronales Artificiales y Árboles de Decisión). A nivel internacional, lo que se puede apreciar es un creciente interés de los investigadores en esta nueva forma de ver la modelación y el análisis. Por lo tanto, este proyecto permitiría a la academia colombiana participar en la intensa discusión que se ha generado acerca de la conveniencia y efectividad de estas nuevas técnicas, en particular de la Programación Genética.

1.3.2 MARCO TEÓRICO Y ESTADO DEL ARTE: En los modelos conducidos por datos lo que típicamente se requiere son registros históricos de variables, sin la consideración detallada de la estructura interna de los procesos físicos involucrados en la transformación estímulorespuesta correspondiente. La incertidumbre y la complejidad de muchos sistemas estudiados tanto en las ingenierías como en otras disciplinas, junto con la inmensa cantidad de datos registrados la interior de estos sistemas, las limitaciones prácticas de los modelos convencionales en cuanto a suposiciones y calidad de la información requerida, han obligado a que muchos investigadores se enfoquen a la aplicación de muchas técnicas de Minería de Datos(Data Mining, DM), Inteligencia Computacional(CI) y Aprendizaje de Máquina(Machine Learning), que en el contexto de la modelación se han denominado “Data driven models” o Modelos Conducidos por Datos, debido a su dependencia casi exclusiva de datos registrados para su desarrollo. Estos nuevos modelos incluyen, entre otros: Redes neuronales Artificiales, Máquinas de Soporte Vectorial(Support vector Machine) Árboles de Decisión y de Regresión, Métodos Bayesianos, Sistemas Basados en Reglas Difusas y Computación Evolucionaria, los cuales se han aplicado con éxito relativo en diferentes problemas de ingeniería, según lo reportan diversos autores(ver IHE-Stowa, 2001; ASCE, 2002, Dibique Y. B. Et al, 2001; Obregón N.,1999; Obregón N., 2002; Obregón N., 2002a, Obregón N., 2003, Tokar, A. S. Et al. , 2000; Cousin, N. Et al., 1997; Keijzer, M. Et al. 1999, Morshed, J. Et al. 1998; Solomatine D. P. Et al. 1996; Tsoukalas, L. H. Et al., 1997; Smith, J., et al. 1995; Abbot, M. B., 1997, Solomatine, D. P. 2002). Debido a que el interés de esta propuesta se centra en la computación evolucionaria, entonces, se procederá a hacer una presentación general de los conceptos más importantes.

COMPUTACIÓN EVOLUCIONARIA A lo largo del período de evolución de los seres vivos, se han ido seleccionando conductas que son adecuadas para la supervivencia. las especies y los individuos que sobreviven son aquellos que están mejor adaptados al ambiente que les rodea. en la lucha por sobrevivir, los individuos mejor adaptados sobreviven más fácilmente y por tanto pueden reproducirse y transferir a sus descendientes las cualidades beneficiosas que les permitieron estar mejor adaptados, lo cual constituye el proceso de selección natural explicado por Charles Darwin en su libro "El Origen de las Especies" (1859). todos aquellos rasgos que faciliten la supervivencia del individuo tenderán a mantenerse, mientras que lo que constituya una dificultad o debilidad para la adaptación tenderá a desaparecer, pues su poseedor no tendrá oportunidad de legarlo a su descendencia. este procedimiento utilizado por la naturaleza, ha sido el principal aspecto de interés de la computación evolucionaria y ha sido fuente de inspiración en el campo de las ciencias de la computación e ingeniería para el desarrollo de métodos de optimización y búsqueda alternativos, conformando lo que se ha denominado en el contexto del aprendizaje de máquina, el paradigma evolutivo. la computación evolutiva (evolutionary computation, EC), aplica la teoría de la evolución natural y la genética en la adaptación evolutiva de estructuras computacionales, proporcionando un medio alternativo para atacar problemas complejos en diversas áreas como la ingeniería. Una población de posibles soluciones de un problema dado es análoga a una población de organismos vivos que evoluciona cada generación al recombinar los mejores individuos de la población y transmitir las características de dichos individuos padres, a sus descendientes. En este campo, diferentes esquemas de métodos evolutivos se han desarrollado, los cuales difieren en el tipo de estructuras que conforman la población. El tema central de la computación evolucionaria es la aplicación de conceptos de selección basados en la aptitud de una población de estructuras de datos en la memoria del computador. Estas estructuras se reproducen de una manera tal que el contenido genético de sus descendientes está relacionado de alguna forma con el contenido genético de los padres, aunque ligeramente diferente; de la misma forma la aptitud de los hijos está relacionada, pero es potencialmente diferente a la de los padres. En la mayoría de los casos, la función de aptitud( la que determina que tan bien se comporta un individuo a un ambiente en particular) usada en la computación evolucionaria no está orientada directamente hacia la reproducción sino que la crea el hombre como supervisor del proceso evolucionario. A los individuos de la población se les permite su reproducción en diferentes cantidades basados también en la función de aptitud diseñada por el programador de acuerdo al propósito particular del proceso evolutivo simulado. Entre los diferentes estilos de computación evolucionaria suelen distinguirse: Estrategias evolucionarias, Programación Evolucionaria, Algoritmos Genéticos y Programación Genética. Estos estilos comprenden operadores genéticos que son las funciones que dirigen la selección y la transformación de los individuos a lo largo del proceso simulado. Entre estos operadores se puede mencionar:

Selección(n-ario): Selecciona los cromosomas(representación apropiada del individuo o de la solución tentativa) de la población para posteriormente permitir que se reproduzca. Esta selección está basada en la aptitud del cromosoma: entre más apto mayor probabilidad tiene de ser seleccionado. Reproducción(unario): Este operador lleva soluciones tentativas sin transformarlas, a la siguiente generación. Cruce(binario): Este operador escoge aleatoriamente una posición en el cromosoma e intercambia la subsecuencia antes y después de la posición para crear dos hijos(soluciones tentativas derivadas). Mutación(unario): Este operador cambia aleatoriamente algunos de los bits en un cromosoma( solución tentativa). Este operador permite hacer una exploración completa para evitar una concentración de los genes más aptos en máximos locales. Función de Aptitud(n-aria): Esta función es la encargada de determinar cuán buena es una solución candidata dada. En esta propuesta de investigación se pretende abordar uno de estos estilos de computación evolucionaria, el denominado programación genética, que es una extensión de los algoritmos genéticos, por lo tanto se hará una pequeña introducción a los algoritmos genéticos y luego se hará una exposición sencilla de los aspectos particulares de la programación genética. Algoritmo Genético Simple Propuestos por Holland(1989), se clasifica, también como un algoritmo de búsqueda estocástica. Este tipo de algoritmos combina la supervivencia de los mejores individuos dentro de un conjunto, los más aptos, con un intercambio de información estructurado y aleatorio, que imitan los procesos de evolución biológica. Una vez definido el problema a resolver, el procedimiento de aplicación de los algoritmos genéticos, en su forma simple, exige la representación en una cadena de símbolos( genotipo) de las soluciones candidatas(fenotipos). Esta representación es típicamente binaria. El procedimiento que comprende un algoritmo genético básico es el siguiente: 1. Comience con una población generada aleatoriamente de k cromosomas de h bits(soluciones candidatas para la solución del problema representadas adecuadamente) 2. Repita los siguientes pasos hasta que se satisfaga alguna condición de parada, ya sea por el número de ejecuciones o por el valor de la función de aptitud. 3. Calcule la función de aptitud f(x) de cada cromosoma x en la población. 4. Repita los siguientes pasos hasta que k hijos hallan sido creados. • Seleccione un par de cromosomas de la población actual (estos cromosomas serán los padres). La probabilidad de selección estará dada de acuerdo a la aptitud de cada cromosoma. La selección se hace sin reemplazo, es decir que un cromosoma puede seleccionarse más de una vez para ser padre. • Con probabilidad pc(probabilidad de cruce), se cruzan el par de cromosomas en un punto escogido aleatoriamente para formar dos hijos. Si no se efectúa el cruce los padres son copias exactas de los padres.

•

De acuerdo con una probabilidad pm( probabilidad de mutación), se elige sustituir el símbolo de cada posición de las cadenas de los hijos, por otro cualquiera. De esta forma se obtienen los cromosomas de la nueva población

5. Reemplace la población actual de padres por la población nueva conformada por los hijos. 6. Regrese al paso 3. Cada iteración de este proceso se llama generación. Obsérvese que los algoritmos genéticos descritos no trabajan directamente sobre las soluciones candidatas, sino que las representan adecuadamente, típicamente en forma binaria, y es a estas representaciones a las que se les aplican los operadores genéticos. Programación Genética(PG) La PG, como se mencionó antes puede considerarse como una extensión de los algoritmos genéticos donde los individuos( representados por cromosomas) que se evolucionan son programas en sí mismos . Se usan operadores genéticos especializados que generalizan la recombinación sexual y la mutación. En PG los programas a evolucionar son representados en forma de árboles analíticos que constituyen material genético no lineal, a diferencia de los algoritmos genéticos que trabajan con material genético lineal representado en cadenas de símbolos binarios.

En la gráfica anterior puede observarse claramente cómo se representa una función matemática que puede interpretarse como un programa de computador. En la estructura del árbol, es posible identificar nodos terminales, que son las hojas del árbol y que pueden ser valores constantes o variables, que se obtiene a partir de las entradas del programa(En el caso del árbol: 0.234, Z, X y 0.789). Las funciones primitivas son nodos no terminales (En es caso del árbol mostrado: *, +, -) y pueden ser operaciones aritméticas estándar, operaciones de programación estándar, funciones matemáticas estándar, funciones lógicas o funciones específicas del domino del problema a resolver. Cada programa de computador es una composición de funciones del conjunto de funciones primitivas y terminales definidas. Es de anotar que cuando se crean y se transforman estos árboles debe conservarse la corrección sintáctica. Para la ejecución de un algoritmo de PG es necesario, como ya hemos comentado, definir previamente una serie de aspectos relativos al funcionamiento del propio algoritmo:

•

Conjunto de Terminales, esto es, las entradas del programa y las constantes que debe resolver nuestro problema.

•

Funciones Primitivas: deben ser apropiadamente definidas: operadores aritméticos, lógicos, de programación, etc. El conjunto de terminales más el conjunto de funciones primitivas deben cumplir el criterio de suficiencia, esto es, deben ser capaces de expresar la solución del problema. Por otro lado, cualquier función primitiva debe aceptar como argumento cualquier valor devuelto por cualquier función y cualquier valor que pueda ser usado como terminal. Esto es lo que se denomina requisito de clausura.

•

Medida de Aptitud nos permite evaluar cuán bien funciona cada programa de la población en el entorno del problema. Esta medida debe estar completamente definida, debe ser capaz de evaluar cualquier programa de la población.

•

Parámetros de Control de Ejecución son varios, aunque básicamente establecen el tamaño de la población inicial (4000), el número de generaciones (50), el porcentaje de individuos que pasan directamente a la siguiente generación (10%), etc.

•

Criterio de Finalización debe indicar cuándo finalizar la ejecución del algoritmo de PG, lo cual puede ocurrir cuando transcurra el número de generaciones predeterminadas, o bien hallemos el programa que sea "perfecto" según la medida de aptitud que hemos proporcionado.

•

Designación del Resultado se hace generalmente utilizando el criterio de "mejor hasta el momento", esto es, se elige el mejor programa de todos los obtenidos hasta la finalización de la ejecución.

Los operadores genéticos: mutación cruce y reproducción se definen de manera similar que para los AG. Sin embargo las consideraciones de corrección sintácticas exigen ciertas particularidades 2.1.1.1 Cruzamiento La operación de cruce se usa para crear nuevos programas hijos, a partir de dos programas padres seleccionados por su buena aptitud. Los programas padres, a diferencia de los AG, normalmente son de diferente tamaño y forma. Los programas hijos se componen de subexpresiones, subprogramas, subrutinas, bloques de sus padres. Así, los programas hijos normalmente son de diferente tamaño y forma que sus padres, y posiblemente, y es lo que se espera, sean más idóneos que sus progenitores. Para ilustrar la forma como se realiza esta operación se presenta un ejemplo: Primero considérese a los dos árboles que van a ser los padres en el cruce y numérense sus nodos en preorden( raíz, subárbol izquierdo, subárbol derecho):

A continuación se escogen al azar los nodos interiores que servirán de referencia para el cruce. Supóngase que se obtuvo el nodo 2 para el primer árbol y el noto 5 para el segundo árbol. Por lo tanto los puntos de cruce son: “*” para el primer árbol y el “+” para el segundo padre. Los dos fragmentos del cruce se presentan a continuación:

En la tercera vemos a los padres despojados de dichos subárboles para que sean intercambiados:

La cuarta muestra los hijos generados con el intercambio de los subárboles anteriores:

2.1.1.2 Mutación En el caso de la programación genética, el procedimiento típico es simple: los programas seleccionan una parte del árbol y la reemplazan por otro subárbol creado aleatoriamente. Esto le da al algoritmo la posibilidad de escapar de un mínimo local creando un descendiente con características totalmente nuevas. Sin embargo la mutación puede ser peligrosa. Si ella se aplica muy frecuentemente la población será esparcida por todo el espacio de soluciones

potenciales en vez de converger hacia la mejor solución y el proceso de búsqueda se convertirá en una búsqueda ciega aleatoria, sin ninguna inteligencia. Para ilustrar el operador de mutación se presenta el siguiente ejemplo: Supóngase que se tiene un individuo que va a ser mutado, el cual se muestra a continuación, y corresponde a la función: ZY + ( Y + ( 0.314Z ) ) , el cual para propósitos de programación se podría escribir, en notación prefija, como: (+((* Z Y) (+ Y (* 0.314 Z)))) Sobre este individuo se elige al azar un nodo que será el punto de mutación. Supóngase que ese punto resultó ser el nodo 7.

1

Nodo elegido aleatoriamente para mutación

+ 5

2

Z

+

* 4

6 Y

7 Y

*

8 0.314

Z 9

ZY + ( Y + ( 0.314Z ) )

Supóngase que luego se genera un árbol aleatorio, con una profundidad dada, el cual se muestra en la siguiente gráfica

/

* Z

Y

0.0278

Y

El individuo mutante se construye reemplazando el subárbol debajo del nodo en el individuo original por el subárbol generado aleatoriamente. El individuo mutilado por el nodo de mutación y el individuo mutante resultante, se muestran a continuación

1

1

+

3 Z

4

3

6 Y

7 Y

+

*

+

*

5

2

5 2

+

Z

4

7

6 Y

-

Y 8 9 Z

/

*

11

10 Y

0.0278 12

Individuo mutante:

ZY + ( Y + ( ZY − 0.0278Y ) )

Y

13

Individuo mutilado por el nodo de mutación

Los pasos involucrados para la aplicación de la PG, en su forma más simple, a un problema en particular pueden resumirse así: 1. Genere una población inicial de composiciones aleatorias de las funciones y terminales definidas para el problema(programas de computador). 2. Ejecute cada programa de la población y asígnele un valor de ajuste de acuerdo a qué tan bien resuelve el problema. 3. Cree una nueva población de programas de computador a) Copie el mejor de los programas existentes(elitismo) b) Cree nuevos programas de computador por mutación. c) Cree nuevos programas de computador por cruzamiento( reproducción sexual) 4. Itere a partir de 2. hasta que el problemas se considere resuelto, esto es, hasta que se cumpla con el criterio de finalización. 5. El mejor programa de computador que aparece en cualquier generación, la mejor solución hasta el momento, se designa como el resultado de la programación genética( Koza, 1992) A continuación se muestra el diagrama de flujo para la forma más simple de la PG:

La PG es un intento de resolver una de las cuestiones más excitantes e interesantes de las ciencias de la computación: ¿Cómo pueden aprender las computadoras a solucionar problemas sin que se les programe explícitamente para ello? En otras palabras la cuestión es cómo se puede hacer que los programas hagan lo que tiene que hacer , sin necesidad de decirles exactamente cómo lo deben hacer. El espacio de búsqueda de la PG es el espacio de todos los programas de computadora que se puedan construir con lo elementos básicos definidos: funciones y elementos terminales apropiados. La PG ha sido aplicada con éxito en muchos problemas de ingeniería, de bioinformática, de economía, etc., de acuerdo con lo reportado por muchos autores[Cousin, N. Et al., 1997; Keijzer, M., Babovic., V 1999; Abbott, M.B., Gen =0 Cree la poblacion inicial aleatoriamente El criterio de F inalización es Satisfecho?

Si

Reporte el resultado

No

F in

Evalúe la función de aptitud para cada individuo en la población Individuos =0 Si Gen=Gen+1

Individuos =M ? No

reproducción

Selecione la operación Genética P robabilísticamente

mutación

cruzamiento Seleccione un individuo basado en su aptitud

Seleccione dos individuos basado en la aptitud

Seleccione un individuo basado en su aptitud

Realice la Reproducción

Realice el cruzamiento

Realice la mutación

Copie en la nueva población

Individuos =Individuos +1

Inserte los dos descendientes en la nueva población Individuos =Individuos +2

Inserte individuo mutante en la nueva población

Individuos =Individuos +1

1997; Babovic V. et al.,. Bojkov 2001; Babovic, V., and Abbott, M.B, 1997; Babovic, V., and Keijzer, M,2000; Babovic, V., et al., 2001; Bavovic V. and M. Keijzer, 2002; Drécourt, J., and H. Madsen, 2001; Whigham and P. Crapper, 1999] Entre las aplicaciones de la programación genética pueden citarse: -En la inteligencia artificial y robótica la planificación de acciones requiere encontrar una secuencia de trabajo, a partir de la información obtenida

por sensores que definen el estado de los objetos que forman el sistema. Esta secuencia llevará al sistema hacia un estado determinado, la PG busca hallar el mejor plan de trabajo para alcanzar dicho estado. Un problema típico de planificación se conoce como el problema de la hormiga. El sistema está formado por un territorio dividido en casillas, algunas de ellas tienen comida y una hormiga. El objetivo es que la hormiga encuentre toda la comida recorriendo el menor número de casillas. -Identificación simbólica de funciones, se trata de buscar una función que ajuste una secuencia discreta de puntos, el caso más simple se trata de calcular un elemento arbitrario de una secuencia de números a partir de un subconjunto de ellos. -Regresión simbólica, es un caso particular de la identificación de funciones, debemos encontrar la relación que hay entre la variable independiente y la variable dependiente. A diferencia de otras técnicas de ajuste de funciones como regresión lineal, cuadrática, polinómica, interpolación,.... donde el problema se reduce a la búsqueda de los coeficientes más adecuados para que una función de un tipo determinado ajuste la nube de puntos, en estos problemas la P.G. busca tanto la función como los coeficientes al mismo tiempo. -Descubrimiento empírico, se puede ver como un tipo determinado de regresión, pero el objetivo es buscar leyes o modelos matemáticos que rigen sistemas naturales, por ejemplo se puede ver como la P.G. es capaz de redescubrir la Tercera Ley de Kepler, o usarse para buscar relaciones entre variables que en principio no sabemos si están o no relacionadas. -Problemas de clasificación de objetos, se basan en la búsqueda de árboles de decisión que nos permitan clasificar todos los objetos de un universo en clases, dependiendo de las características fundamentales que presentan. -Reconocimiento de patrones, busca un algoritmo que sea capaz de reconocer un patrón en una imagen digitalizada. -Estrategias de juego, define que jugada deberá hacer un jugador en cada momento, dependiendo de movimientos anteriores, etc. -Creación y entrenamiento de redes neuronales. De todas las aplicaciones mencionadas en esta propuesta se intentará abordar a la regresión simbólica, por lo tanto se harán algunas precisiones al respecto 2.1.1.3 Regresión simbólica Esta parte está basada en el trabajo del Dr. Keijzer.( 2001). La formación de la ciencia moderna ocurrió aproximadamente en el periodo entre el finales del 15 y finales del siglo 18. Las nuevas fundamentaciones eran basadas en la utilización de experimentos físicos y la aplicación de un aparato matemático para describir estos experimentos. Los trabajos de Brahe, Kepler, Newton, Leibniz, Euler y Lagrange personifican este acercamiento. Antes de estos desarrollos, el trabajo científico consistió principalmente en coleccionar datos , o registros de las lecturas que se hacían del libro de la naturaleza directamente. Este acercamiento científico es caracterizado tradicionalmente a través de dos fases: una primera en la que se reúne un juego de observaciones del sistema físico, y una segunda en la que se genera una aserción inductiva sobre el comportamiento del sistema--una hipótesis--. Las observaciones presentan

conocimiento específico, mientras que las hipótesis representan una generalización de estos datos que implica o describe a las observaciones. Este procedimiento conduce a una simplificación del conocimiento, ya que proporciona una forma más compacta de describir a las observaciones. Hoy, a principios del siglo 21, se está experimentando un cambio en el proceso científico, que ha dado lugar a una aproximación científica en la cual las tecnologías de la información asisten al analista humano, en el proceso de generación de hipótesis. Este análisis asistido por computadora de grandes cantidades de datos multidimensionales es a veces denominado Minería de Datos y Descubrimiento Científico, el cual apunta a proporcionar herramientas para facilitar la transformación de los datos en diversas formas que lleven a un mejor entendimiento de los procesos físicos que generaron o produjeron esos datos. Estos nuevos modelos combinados con el conocimiento ya alcanzado de los procesos físicos -la teoría- puede conducir a una mejor comprensión y a una nueva formulación de leyes físicas y, además, a una mayor capacidad del predictiva. Un modo particular de hacer minería de datos es inducir modelos. La inferencia de modelos a partir de datos es una actividad de comprende la deducción de una explicación de forma cerrada basada únicamente en las observaciones, de lo cual surge una pregunta: Como un flujo limitado de información de un sistema físico hacia el observador, puede resultar en la formación de un modelo que es completo en el sentido de que el proporciona respuesta para el rango completo de fenómenos encontrados dentro del sistema físico- e incluso describir los datos que están por fuera del rango de las observaciones previamente halladas? El trabajo presente es un esfuerzo por mostrar la potencia de la PG, en particular de la Regresión Simbólica, para la inducción de expresiones interpretables y de soporte para el descubrimiento científico. Aunque el proceso de crear ecuaciones de los datos se hace usando medios automatizados, el proceso importante de interpretación, de análisis y valoración de las hipótesis propuestas son tareas que están en las manos del científico. Las ecuaciones que se descubren forman una formulación empírica de las relaciones en los datos y una propuesta provisional de los conceptos físicos que son manipulados por la formulación. Se piensa que el científico que usa estas propuestas provisionales puede preparar más eficazmente, la prueba y refutación de modelos para el problema bajo el estudio. Aunque la programación genética puede ser usada para varias tareas automáticas, en este proyecto se enfocará a la inducción de expresiones matemáticas a partir de datos. Esto es llamado regresión simbólica{Koza,1992], para enfatizar el hecho de que el objeto de búsqueda es una descripción simbólica de un modelo, no sólo un conjunto de coeficientes en un modelo preespecificado. Esto está en fuerte contraste con otros métodos de regresión, incluyendo redes neuronales, donde un modelo específico es asumido Las tareas de regresión pueden ser especificadas con un conjunto de entradas, variables independientes, X, y una salida deseada, la variable dependiente, Y. El objeto de la búsqueda es entonces aproximar Y usando X y coeficientes W, tales que:

donde representa un término de ruido. Con las técnicas estándares de regresión la forma funcional f es preespecificada. Usando regresión lineal por ejemplo, f podría ser: Donde los coeficiente W se hallan mediante regresión de mínimos cuadrados. En forma matricial, esto se escribiría: donde el coeficiente de sesgo, bias, w0 ha sido omitido por razones de claridad. La técnica no-lineal de regresión de una red neuronal artificial podría introducir una función de transferencia auxiliar g( usualmente una sigmoidea) y usaría el morfismo:

Aquí los coeficientes son comúnmente llamados pesos; wh son los pesos de los los nodos de entrada a los nodos ocultos y w o son los pesos de los nodos ocultos a la capa de salida. Otra vez los pesos del sesgo son omitidos en la ecuación. Debido a su forma funcional, el cálculo del gradiente del error para los pesos de una red neuronal como tal es directo y tiene complejidad lineal en el número de pesos. En contraste con esas técnicas , la programación genética aplicada a la tarea de regresión simbólica no usa una forma preespecificada. Ella usa funciones primitivas de bajo nivel. Esas funciones pueden ser combinadas para especificar la función completa. Dado un conjunto de funciones primitivas que toman un argumento h1,...,hu, y un conjunto de funciones que toman dos argumentos g1,.., gb, la forma funcional general inducida por programación genética puede tomar una variedad de formas. Las funciones h y g son usualmente funciones aritméticas estándares tales como adición, sustracción, multiplicación y división pero podría incluir también trigonométricas, lógicas, y funciones trascendentales. Un ejemplo de función podría ser: f ( x, w) = h1 ( g 2 ( g1 ( x3 ,w1 ) , h2 ( x1 ) ) ) Esta función particular puede ser descrita en forma de árbol

Sin embargo, también es consistentes.

posible obtener combinaciones de funciones no

Llenado con alguna función primitiva concreta los símbolos abstractos h y g podría conducir al árbol:

o como expresión:

El objeto de búsqueda es entonces una composición de variables de entrada, coeficientes y funciones primitivas tales que el error de la función con respecto a la salida deseada sea mínima. La forma y el tamaño de la solución no es especificada al principio de la optimización(aunque típicamente se da un tamaño máximo) ya que este es otro objeto de la búsqueda. El número de coeficientes a usar y cual es el valor que toma cada uno de ellos es otra cuestión que es determinada en el proceso de búsqueda en sí mismo. El sistema es también libre de excluir ciertas variables de entrada de la ecuación, pudiendo así reducir la dimensionalidad del problema. Mediante el uso de tales primitivas, la programación genética es en principio capaz de expresar cualquier forma funcional que usen esas funciones: en particular un conjunto suficientemente expresivo de funciones, es capaz de expresar una relación lineal o una relación no lineal. La programación genética no es el único sistema capaz de inducir expresiones simbólica de datos. Un trabajo computacional bien conocido sobre la inducción de ecuaciones sobre datos es el programa BACON[Langley et al., 1987]. En contraste con la programación genética, el sistema BACON explora el espacio de búsqueda de posibles expresiones usando varias heurísticas. Estas toman la forma de comparaciones numéricas: si por ejemplo dos términos ( variables o expresiones ya inducidas) parecen crecer conjuntamente, se considerará una expresión que involucre la relación entre los dos términos. Similarmente, cuando un término incrementa cuando otro decrece y hace esto de forma no lineal, el producto de los dos términos es considerado. Los heurísticos en el sistema BACON relacionan de esta forma los valores numéricos entre los términos con las manipulaciones simbólicas que serán consideradas. Así, el sistema producirá una expresión donde todas las funciones que se aplican tiene esta justificación heurística. Esto presupone que cualquier relación matemática entre el conjunto de datos puede ser incrementalmente construida usando estos heurísticos. Además cuando los datos presenta ruido, los conceptos tales como el incremento o decrecimiento conjunto de valores resultaría difícil de medir. La

aplicación de los heurísticos podría necesitar parámetros adicionales que requerirían ser fijados con el propósito de estimar el ruido. Con programación genética, las transformaciones posibles no están limitadas a algún conjunto de heurísticas motivadas numéricamente. Como se describió antes los operadores de variación son aleatorizados, mientras que el comportamiento de una expresión completa se usa como guía para seleccionar a las expresiones. Las expresiones que son inducidas de esta forma no tienen necesariamente una estructura interna que sea incrementalmente justificada. La programación genética es capaz de realizar computación creativa a medida que disminuye el error. Esto tiene la desventaja de que las expresiones inducidas pueden ser demasiado creativas, hasta el punto de ser imposibles de comprender. Un sistema de programación genética que realice regresión simbólica se requiere de esta manera, para encontrar la forma de la ecuación, la composición de funciones primitivas, el uso de variables de entrada, el uso de valores de coeficientes mas la complejidad de esta composición, todo en un solo procedimiento de optimización. Además no emplea ninguna información del gradiente de la composición de funciones ni heurísticas numéricas sobre las funciones. La única retroalimentación que el sistema recibe es el comportamiento general de una expresión dada sobre los datos con respecto a alguna función de error. A continuación se presenta un ejemplo, de regresión simbólica con el fin ilustrar aún más el procedimiento: Se dispone del siguiente conjunto de datos entrada-salidas de un sistema( que corresponde a la ecuación x2+x+1) : Variable independiente X

Variable dependiente Y

-1.00

1.00

-0.80

0.84

-0.60

0.76

-0.40

0.76

-0.20

0.84

0.00

1.00

0.20

1.24

0.40

1.56

0.60

1.96

0.80

2.44

1.00

3.00

A continuación se definen los parámetros básicos para la aplicación de la PG

Objetivo

Hallar un programa de computador con un argumento (variable independiente X) cuya salida sea igual a la variable dependiente Y, proporcionada para cada uno de los datos

1

Conjunto de Terminales

T = {X, Constantes aleatorias}

2

Conjunto funciones

3

Medida de aptitud:

La suma del valor absoluto de las diferencias entre la salida del programa candidato y los datos dados para la variable dependiente

4

Parámetros:

Tamaño de la población M = 4

5

Criterio de Finalización:

Cuando se halle un individuo cuya suma de los errores absolutos sea menor que 0.1

de F = {+,

-,

*, %}

Se genera a continuación la población inicial de individuos:

Se calcula la función de aptitud para cada individuo( El área sombreada es la medida de aptitud):

x+1

x2+1

2

x

Se obtiene la siguiente generación mediante los operadores genéticos.

Primer hijo del cruce de

Copia de a)

Copia de a)

Primer hijo del

(a) y (b)  Mutante de   (c)  Segundo hijo del cruce de  (a) y (b)   cruce de  (a) y (b)  Mutante de   (c) Primer hijo del cruce de  (a) y  Seleecionado como puntos Seleecionado como Seleccionando el nodo  Seleccionando como puntos de cruce  Seleccionando (b)  Seleccionando como puntos  de cruce  “+” del padre puntos de cruce  “+” el nodo 3 como de cruce  “+” del padre (a) y la  3 como punto de  “+” del padre (a) y la x más a la  (a) y la x más a la del padre (a) y la x punto de izquierda del padre  (b) izquierda del  padre  (b) mutación x más a la izquierda del padre  más a la izquierda mutación del padre  (b) (b) 2

Para este ejemplo “de juguete”, ya se halló la solución: x +x+1, en el cuarto individuo de la segunda generación..

BIBLIOGRAFIA • Abbott, M. B, Bathurst, J.C., Cunge, J. A., O’Connel, P. E. and Rasmunsen, J.(1986). An introduction to the European Hydrological System – Systeme Hydrologique European. • Abbott, M.B., Babovic, V.M., and Cunge, J.A. (2001). Towards the hydraulics of the hydroinformatics. Journal of Hydraulic Research, 39(4), 339-349. • Abbott, M.B.,(1997). Engine 2000: Research in to the next generation of computational hydraulic modelling, Proceedings of the 27th Congress of the International Association for Hydraulic Research, 2, 859-864. • Amorocho, J., and A. Brandstetter(1971). Determination of nonlinear functional response functions in rainfall-runoff processes, Water Resour. Res. 7(5), 1987-110 • ASCE Task Committee on Application of Artificial Neural Network in Hydrology(2000a). Artificial Neural Natwork in Hydrology. I , Preliminary Concepts, Journal od Hydrologic Engineering, 2000, 5(2), 116-123, 2000.

• • • •

• • • • • •

• •

• • • •

ASCE Task Committee on Application of Artificial Neural Network in Hydrology(2000b). Artificial Neural Natwork in Hydrology. I , Hydrologic Applications, Journal od Hydrologic Engineering, 2000, 5(2), 124-135, 2000. Avellaneda, P., Rengifo, P. & N. Obregón. 2002a. Aplicación de las Redes Neuronales Artificiales para la Predicción de Caudales Medio Mensuales. XV Seminario Nacional de Hidráulica e Hidrología. Medellín, Agosto 29-31. Babovic V. & Keijzer M.(2000). An evolutionary algorithm approach to the induction of differential equations. In Proceedings of the Fourth International Conference on Hydroinformatics. Babovic V. & Keijzer M.(1999a). Computer supported knowledge discovery -- A case study in flow resistance induced by vegetation. In Proceedings of the XXVIII Congress of the International Association for Hydraulic Research . Babovic V. & Keijzer M.(1999b) Data to knowledge -- the new scientific paradigm. In D. Savic and G. Walters, editors, Water Industry Systems. Babovic V. & Keijzer M.(1999c). Forecasting of river discharges in the presence of chaos and noise. In J. Marsalek, editor, Coping with Floods: Lessons Learned from Recent Experiences, Kluwer. Babovic V. & Keijzer M.(2001a). On the introduction of declarative bias in knowledge discovery computer systems. In P. Goodwin, editor. New paradigms in river and estuarine management. Kluwer. CIIC2003(2003). Congreso Internacional de Inteligencia Computacional. Univerisdad Nacional Sede Medellín. Davidson, J. W., D. A. Savic, and G. A. Walters (2002), “Symbolic and numerical regression: experiments and applications”, Journal of Information Science, accepted for publication Dibike, B. Y.& Velickov, S.& Solomatine, Dimitri &Abbot, M. B.(2001).”Model Induction with Support Vector Machines: Introduction and Applications”.ASCE Journal of Computing in Civil Engineering, July, vol. 15, No. 3, pp. 208-216 Dibike, Y. B. 2000 Machine Learning Paradigms for Rainfall-Runoff Modelling on the Proc. of the 3rd International Conference on Hydroinformatics, Iowa City, USA. Dibique Y. B. Et al.(2001). Model Induction with Support Vector Machines: Introduction and Applications , ASCE Journal of Computing in Civil Engineering, vol. 15, No. 3, pp. 208-216.2 ,July. Hsu K., Gupta H. V., and Sorooshian S.(1995). Artificial Neural Network modeling of the rainfall-runoff process, Water Resour. Res. 31(10), 25172530. Jørgensen K., Berry Elfering, Keijzer M., and Babovic V.(2000). Analysis of long term morphological changes: A data mining approach. In Proceedings of the International Conference on Coastal Engineering, Australia. Katya Rodríguez Vázquez(2002) .Genetic Programming In Time Series Modelling: An Application To Meteorological Data. Proceedings of ERAD 416–421 Keijzer M. and Babovic V.(2002). Declarative and preferential bias in gpbased scientific discovery. Genetic Programming and Evolvable Machines.

• •

• •

Keijzer M.(2002). Scientific Discovery Using Genetic Programming. PhD thesis, Danish Technical University, Lyngby, Denmark, March. Keijzer M., Babovic V. , Conor Ryan, Michael O'Neill, and Mike Cattolico.(2001) Adaptive logic programming. In Lee Spector et.al., eds, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Koza, J. R.(1992). Genetic Programming. On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems), MIT Press Obregón, N. & F. Fragala’. 2003. Poster: “Avances en la simulación estocástica espacial de los niveles piezométricos del acuífero cuaternario de la Sabana de Bogotá (Colombia)”, “Hacia la estimación de la vulnerabilidad de acuíferos por medio de árboles de decisión” & “Aspectos hidrogeológicos de la cuenca alta del Río Tunjuelo (Sabana de Bogotá, Colombia)”. IX Congreso Colombiano de Geología. Julio 30-Agosto 1 2003. Medellín, Colombia.

•

Obregón, N. 1999 Hidroinformática: Nuevas perspectivas en Ingeniería de Recursos Hídricos. XIX Reunión Nacional de Facultades de Ingeniería. Cartagena de Indias, Colombia. Agosto 25-27 de 1999.

•

Obregón, N. 2002. Herramientas Hidroinformáticas en la Gestión de los Recursos Hídricos. Seminario y Muestra Tecnológica del Agua. Ministerio de Desarrollo, DNP, Uniandes, Banco Mundial y Andesco. Cartagena. Mayo 810 Obregón, N. 2002b. Sistemas Inteligentes en Hidroinformática. Foro sobre Recursos Hídricos. Asociación Nacional de Estudiantes de Ingeniería Civil (ANEIC). Bogotá, Octubre 26. Velásquez, J. D, 1997. Predicción de Series de Tiempo usando Programación Genética. Tesis de Maestría en Ingeniería de Sistemas. Universidad Nacional de Colombia. Sede Medellín.

• •

•

Zhang, Byoung-Tak y Mühlenbein, Heinz(1995). Balancing Accuracy and Parsimony in Genetic Programming. Evolutionary Computation, Vol. 3, No. 1, pp 17-38.