1

2 IIC 2632 – Computación Evolutiva 14. Programación Genética IIC 2632 – Computación Evolutiva © Rodrigo Sandoval 2011

3 Contenido Motivación y definiciones Motivación y definiciones Representación y algoritmo Representación y algoritmo Inicialización Inicialización Operadores Genéticos Operadores Genéticos Revisión de la ejecución Revisión de la ejecución GP como máquina de invenciones GP como máquina de invenciones Base: Prof. John R. Koza Stanford University

4 Motivación y Definiciones El Desafío El Desafío ¿Cómo pueden los computadores aprender a resolver problemas sin ser explícitamente programados para ello? En otras palabras, ¿cómo pueden los computadores ser diseñados para hacer exactamente lo que se necesita que hagan sin decirles explícitamente cómo hacerlo? Atribuido a Arthur Samuel (1959)

5 Motivación y Definiciones Criterio de Éxito Criterio de Éxito El objetivo [es] … hacer que las máquinas exhiban comportamiento, que es realizado por humanos, sería como asumir que involucra el uso de inteligencia. Arthur Samuel (1983)

6 Motivación y Definiciones Programación Genética Programación Genética La GP aplica el enfoque del GA al espacio de posibles programas computacionales. La GP aplica el enfoque del GA al espacio de posibles programas computacionales. Los programas son la lingua franca para expresar soluciones a una gran variedad de problemas. Los programas son la lingua franca para expresar soluciones a una gran variedad de problemas. Una gran variedad de problemas aparentemente diferentes de diversos contextos se pueden reformular como una búsqueda de un programa computacional para resolver el problema. Una gran variedad de problemas aparentemente diferentes de diversos contextos se pueden reformular como una búsqueda de un programa computacional para resolver el problema.

7 Motivación y Definición Originado por John R. Koza, Stanford Univ. Originado por John R. Koza, Stanford Univ. 1992, Genetic Programming Treatise - “Genetic Programming. On the Programming of Computers by Means of Natural Selection.” 1992, Genetic Programming Treatise - “Genetic Programming. On the Programming of Computers by Means of Natural Selection.” Combinación entre la idea de “Aprendizaje de Máquinas (Machine Learning)” y las estructuras de árboles evolucionados. Combinación entre la idea de “Aprendizaje de Máquinas (Machine Learning)” y las estructuras de árboles evolucionados.

8 Motivación y Definiciones Puntos principales Puntos principales GP rutinariamente entrega inteligencia de máquina, competitiva a nivel humano y de alto retorno. GP rutinariamente entrega inteligencia de máquina, competitiva a nivel humano y de alto retorno. GP es una máquina de invención automatizada. GP es una máquina de invención automatizada. GP ha entregado una progresión de cualitativamente más resultados sustanciales en sincronía con incrementos de cinco órdenes de magnitud en perjuicio de tiempo computacional. GP ha entregado una progresión de cualitativamente más resultados sustanciales en sincronía con incrementos de cinco órdenes de magnitud en perjuicio de tiempo computacional.

9 Motivación y Definiciones Definición de Alto Retorno. Definición de Alto Retorno. La tasa AI (“artificial-to-intelligence”) de un método de resolución de problemas tiene la tasa de lo que se entrega por la operación automatizada del método artificial, en relación a la cantidad de inteligencia entregada por el humano aplicando el método a un problema particular. La tasa AI (“artificial-to-intelligence”) de un método de resolución de problemas tiene la tasa de lo que se entrega por la operación automatizada del método artificial, en relación a la cantidad de inteligencia entregada por el humano aplicando el método a un problema particular.

10 Motivación y Definiciones Definición de Rutina/Rutinario. Definición de Rutina/Rutinario. Un método de resolución de problemas se considera rutina si es general y se requiere relativamente muy poco esfuerzo humano para lograr que el método exitosamente maneje nuevos problemas dentro de un dominio particular y que exitosamente maneje nuevos problemas de un dominio diferente. Un método de resolución de problemas se considera rutina si es general y se requiere relativamente muy poco esfuerzo humano para lograr que el método exitosamente maneje nuevos problemas dentro de un dominio particular y que exitosamente maneje nuevos problemas de un dominio diferente.

11 Motivación y Definiciones Criterios para Competitividad-Humana Criterios para Competitividad-Humana 1. Previamente patentados, mejora sobre una invención patentada, o patentable hoy. 2. Legítimamente publicable como un nuevo resultado científico – independientemente del hecho de que el resultado fue creado por una máquina. 3. Mantiene su propia competencia regulada contra humanos o programas. 4. 5 otros criterios similares que están al alcance de áreas en AI, ML, GP.

12 Motivación y Definiciones Progresión de cualitativamente mejores resultados producidos por GP. Progresión de cualitativamente mejores resultados producidos por GP. 1. Problemas “juguete” 2. Resultados no-patentados, humano-competitivos. 3. Invenciones patentadas del siglo XX 4. Invenciones patentadas del siglo XXI 5. Nuevas invenciones potencialmente patentables.

13 Individuos en GP Cada individuo es un programa. Cada individuo es un programa. Representación: diferentes formatos lógicos. Representación: diferentes formatos lógicos. Se pueden crear nuevos programas en forma aleatoria. Se pueden crear nuevos programas en forma aleatoria. Se pueden crear nuevos programas a partir de combinaciones de partes de otros programas (crossover). Se pueden crear nuevos programas a partir de combinaciones de partes de otros programas (crossover). Se pueden crear nuevos programas a partir de modificaciones de otros programas (mutación). Se pueden crear nuevos programas a partir de modificaciones de otros programas (mutación).

14 Programa Computacional

15 Programa Computacional en C int foo (int time) { int temp1, temp2; int temp1, temp2; if (time

16 REPRESENTACIÓN Y ALGORITMO Programación Genética

17 Representaciones Decision trees Decision trees If-then production rules If-then production rules Horn clauses Horn clauses Neural nets Neural nets Bayesian networks Bayesian networks Frames Frames Propositional logic Propositional logic Binary decision diagrams Formal grammars Coefficients for polynomials Reinforcement learning tables Conceptual clusters Classifier systems

18 Árbol del Programa (+ 1 2 (IF (> TIME 10) 3 4)) Representación utilizando sintaxis LISP

19 Flujo de GP

20 Creación Aleatoria de Individuos Imagen con animación, fuente genetic-programming.com

21 Creación Aleatoria de Individuos Funciones disponibles Funciones disponibles F = {+, -, *, %, IFLTE} F = {+, -, *, %, IFLTE} Elementos terminales disponibles Elementos terminales disponibles T = {X, Y, Random-Constants} T = {X, Y, Random-Constants} Los programas aleatorios son: Los programas aleatorios son: de diferentes tamaños y formas, de diferentes tamaños y formas, válidos sintácticamente, válidos sintácticamente, y ejecutables. y ejecutables.

22 Operadores Genéticos Reproducción Reproducción Mutación Mutación Crossover Crossover Operadores de alteración de arquitectura Operadores de alteración de arquitectura

23 Operadores Genéticos Mutación Mutación Imagen con animación, fuente genetic-programming.com

24 Operadores Genéticos Mutación Mutación Se selecciona un padre probabilísticamente dependiendo de su fitness. Se selecciona un padre probabilísticamente dependiendo de su fitness. Elegir punto 1 de num_puntos. Elegir punto 1 de num_puntos. Cortar el subárbol desde el punto elegido. Cortar el subárbol desde el punto elegido. Hacer crecer un nuevo subárbol desde el punto de mutación de la misma manera en que se crearon nuevos programas al comienzo (válido y ejecutable). Hacer crecer un nuevo subárbol desde el punto de mutación de la misma manera en que se crearon nuevos programas al comienzo (válido y ejecutable). Agregar el resultante a la próxima generación. Agregar el resultante a la próxima generación.

25 Operadores Genéticos Crossover Crossover Imagen con animación, fuente genetic-programming.com

26 Operadores Genéticos Crossover Crossover Se seleccionan dos padres probabilísticamente dependiendo de su fitness. Se seleccionan dos padres probabilísticamente dependiendo de su fitness. Elegir aleatoriamente un punto entre 1 y num_puntos para el primer padre. Hacer lo mismo para el segundo padre. Elegir aleatoriamente un punto entre 1 y num_puntos para el primer padre. Hacer lo mismo para el segundo padre. Copiar el subárbol de padre 2 desde el punto elegido y reemplazarlo en el punto de padre 1. El resultado es válido y ejecutable. Copiar el subárbol de padre 2 desde el punto elegido y reemplazarlo en el punto de padre 1. El resultado es válido y ejecutable. Agregar el resultante a la próxima generación. Agregar el resultante a la próxima generación.

27 Operadores Genéticos Reproducción Reproducción Se selecciona un padre probabilísticamente dependiendo de su fitness. Se selecciona un padre probabilísticamente dependiendo de su fitness. Se copia directamente (sin cambios) a la próxima generación. Se copia directamente (sin cambios) a la próxima generación.

28 Operadores Genéticos Operadores de alteración de arquitectura Operadores de alteración de arquitectura Programas complejos tienen subrutinas (Automatically Defined Functions: ADFs), iteraciones (ADI), loops (ADL), recursiones (ADR), y memorias (ADS) Programas complejos tienen subrutinas (Automatically Defined Functions: ADFs), iteraciones (ADI), loops (ADL), recursiones (ADR), y memorias (ADS) El usuario pre-define un arreglo de arquitectura fija razonable. El usuario pre-define un arreglo de arquitectura fija razonable. De tal manera, GP realiza decisiones de cambios estructurales. De tal manera, GP realiza decisiones de cambios estructurales. Hay varios posibles operadores para este contexto. Hay varios posibles operadores para este contexto.

29 Operadores Genéticos Duplicación de subrutina: se cambian los llamados a esta rutina y su duplicado con la posi- bilidad de que una de ellas (o ambas) muten. Duplicación de subrutina: se cambian los llamados a esta rutina y su duplicado con la posi- bilidad de que una de ellas (o ambas) muten. Imagen con animación, fuente genetic-programming.com

30 Operadores Genéticos Duplicación de argumento: duplica un argumento de una subrutina ya existente y cambia aleat. las referencias a esta, preservando la semántica. Duplicación de argumento: duplica un argumento de una subrutina ya existente y cambia aleat. las referencias a esta, preservando la semántica. Imagen con animación, fuente genetic-programming.com

31 Operadores Genéticos Creación de subrutina: desde una parte de una rama de resultados rele- vante, de tal forma aumentando la profundidad de la jerarquía de referencias. Creación de subrutina: desde una parte de una rama de resultados rele- vante, de tal forma aumentando la profundidad de la jerarquía de referencias. Imagen con animación, fuente genetic-programming.com

32 Operadores Genéticos Eliminación de subrutina: remueve una subrutina de un programa, provo- cando que la jerarquía de subrutinas sea más angosta o menos profunda. Eliminación de subrutina: remueve una subrutina de un programa, provo- cando que la jerarquía de subrutinas sea más angosta o menos profunda. Imagen con animación, fuente genetic-programming.com

33 Operadores Genéticos Eliminación de argumento: reduce la cantidad de información disponible para la subrutina, lo que puede ser considerado como generalización. Eliminación de argumento: reduce la cantidad de información disponible para la subrutina, lo que puede ser considerado como generalización. Imagen con animación, fuente genetic-programming.com

34 Preparación Determinar: Determinar: Set de terminales. Set de terminales. Set de funciones. Set de funciones. Medida de fitness. Medida de fitness. Parámetros para la ejecución. Parámetros para la ejecución. Método para determinar un resultado y terminar la ejecución. Método para determinar un resultado y terminar la ejecución.

35 EJEMPLO DE EJECUCIÓN DE GP Programación Genética

36 Regresión Simbólica Variable Independiente X Variable Dependiente Y 1.00 -0.800.84 -0.600.76 -0.400.76 -0.200.84 0.001.00 0.201.24 0.401.56 0.601.96 0.802.44 1.003.00 ¿Cuál es la expresión que representa estos resultados?  Se buscará con PG (Hint: x 2 + x + 1) X Y ¿f(x)?

37 Pasos de Preparación Objetivo:Encontrar un programa con una entrada (variable independiente x) cuyo resultado es igual a los datos indicados en la tabla. 1Conjunto Terminal: T = {X, Random-Constants} 2Conjunto de Funciones: F = {+, -, *, %} 3Fitness:La suma del valor absoluto de las diferencias entre el resultado del programa candidato y el dato dado (computado de numerosos valores de la variable independiente x desde -1.0 a +1.0) 4Parámetros:Tamaño población M = 4 5Finalización:Un individuo emerge cuya suma de errores absolutos es menor que 0.1

38 Regresión Simbólica Generación inicial: 4 programas creados aleatoriamente. Generación inicial: 4 programas creados aleatoriamente.

39 Regresión Simbólica x 2 + x + 1 Fitness de los individuos de la generación inicial. Fitness de los individuos de la generación inicial. x + 1x 2 + 12x 0.671.001.702.67

40 Regresión Simbólica x 2 + x + 1 Siguiente generación Siguiente generación Copia de (a) Mutante de (c) utilizando “2” como el punto de mutación. Primer hijo de un crossover entre (a) y (b), tomando “+” del padre (a) y la “x” de más a la izquierda del padre (b). Segundo hijo de crossover entre (a) y (b) tomando “+” de (a) y la “x” de más a la izq. de (b).

41 OTROS EJEMPLOS APLICANDO GP Programación Genética

42 Clasificación en Espirales entrelazadas  Espiral 1  Espiral 2 Debe ser posible determinar si un punto (x,y) cualquiera pertenece a la espiral 1 o la 2.

43 Pasos de Preparación Objetivo:Crear un programa para clasificar un punto dado en el plano x-y ya sea en la espiral 1 o en la espiral 2. 1Conjunto Terminal: T = {X, Y, Random-Constants} 2Conjunto de Funciones: F = {+,-,*,%,IFLTE,SIN,COS} 3Fitness:La cantidad de puntos correctamente clasificados (0 - 194) 4Parámetros:Tamaño población M = 10000, G = 51 5Finalización:Un individuo que logre los 194 puntos correctamente clasificados.

44 Siguiendo las Paredes

45 Siguiendo las Paredes - Fitness

46 Siguiendo las Paredes Mejor Generación 57

47 DESARROLLO DE CIRCUITOS CON GP Programación Genética

48 Desarrollo de Circuitos Síntesis automática de la topología y tamaño de circuitos eléctricos. Síntesis automática de la topología y tamaño de circuitos eléctricos. La topología de un circuito incluye la especificación del número grueso de cada componente, y una netlist que especifica donde se conecta cada componente. La topología de un circuito incluye la especificación del número grueso de cada componente, y una netlist que especifica donde se conecta cada componente. El tamaño involucra especificar valores (numéricos) de los componentes de cada circuito. El tamaño involucra especificar valores (numéricos) de los componentes de cada circuito.

49 Desarrollo de Circuitos Objetivo: Desarrollo de la Topología y Tamaño de un Circuito eléctrico. Objetivo: Desarrollo de la Topología y Tamaño de un Circuito eléctrico. Un circuito completo se puede desarrollar desde un circuito base (embrión) por medio de la ejecución progresiva de funciones de construcción, modificación de topología, y funciones de control de desarrollo. Un circuito completo se puede desarrollar desde un circuito base (embrión) por medio de la ejecución progresiva de funciones de construcción, modificación de topología, y funciones de control de desarrollo. Solución inicial: circuito simple de dos cables modificables Z0 y Z1. Solución inicial: circuito simple de dos cables modificables Z0 y Z1.

50 Desarrollo de Circuitos Para poder ejecutar GP, se requieren funciones que permitan la creación de componentes eléctricos: Para poder ejecutar GP, se requieren funciones que permitan la creación de componentes eléctricos: Función de Resistencia R Función de Resistencia R Función de Condensador C Función de Condensador C Función de Inductor L Función de Inductor L Función de Diodo D Función de Diodo D Función de Transistor Q Función de Transistor Q

51 Desarrollo de Circuitos Creación de Transistor Creación de Transistor

52 Desarrollo de Circuitos También se necesitan funciones de modificación de topología: También se necesitan funciones de modificación de topología: División en SERIE División en SERIE División en PARALELO División en PARALELO VIA VIA FLIP FLIP

53 Desarrollo de Circuitos División PARALELA División PARALELA

54 Desarrollo de Circuitos Función de control de desarrollo: Función de control de desarrollo: Función END Función END Función NOP (No Operation) Función NOP (No Operation) Función SAFE_CUT Función SAFE_CUT

55 Desarrollo de Circuitos Circuito Inicial Circuito Inicial

56 Desarrollo de Circuitos GP GP (LIST (C (– 0.963 (– (– -0.875 -0.113) 0.880)) (series (flip end) (series (flip end) (L - 0.277 end) end) (L (– -0.640 0.749) (L -0.123 end)))) (flip (nop (L -0.657 end)))))

57 Desarrollo de Circuitos Función de creación de un condensador Función de creación de un condensador (LIST (C (– 0.963 (– (– -0.875 -0.113) 0.880)) (series (flip -0.113) 0.880)) (series (flip end) (series (flip end) (L – end) (series (flip end) (L – 0.277 end) end) (L (– -0.640 0.749) (L -0.123 end)))) (flip 0.749) (L -0.123 end)))) (flip (nop (L -0.657 end))))) (nop (L -0.657 end)))))

58 Desarrollo de Circuitos Función de división en SERIE Función de división en SERIE (LIST (C (– 0.963 (– (– -0.875 -0.113) 0.880)) (series (flip -0.113) 0.880)) (series (flip end) (series (flip end) (L – end) (series (flip end) (L – 0.277 end) end) (L (– -0.640 0.749) (L -0.123 end)))) (flip 0.749) (L -0.123 end)))) (flip (nop (L -0.657 end))))) (nop (L -0.657 end)))))

59 Desarrollo de Circuitos Proceso GP Proceso GP

60 Desarrollo de Circuitos Función de fitness Función de fitness

61 Desarrollo de Circuitos Función de fitness Función de fitness Comportamiento esperado (filtro) Comportamiento esperado (filtro)

62 100%-COMPLIANT LOWPASS FILTER GENERATION 25 WITH 5 CAPACITORS AND 11 INDUCTORS  AREA OF 1775.2

63 100%-COMPLIANT LOWPASS FILTER GENERATION 30 WITH 10 INDUCTORS AND 5 CAPACITORS  AREA OF 950.3

64 100%-COMPLIANT LOWPASS FILTER BEST-OF-RUN CIRCUIT OF GENERATION 138 WITH 4 INDUCTORS AND 4 CAPACITORS  AREA OF 359.4

65 GP COMO MÁQUINA DE INVENCIONES Programación Genética

66 Evolución de GP Progresión de cualitativamente mejores resultados producidos por GP. Progresión de cualitativamente mejores resultados producidos por GP. 1. Problemas “juguete” 2. Resultados no-patentados, humano-competitivos. 3. Invenciones patentadas del siglo XX 4. Invenciones patentadas del siglo XXI 5. Nuevas invenciones potencialmente patentables.

67 Invenciones Patentadas Siglo XX Campbell ladder topology for filters Zobel “M-derived half section” and “constant K” filter sections Crossover filter Negative feedback Cauer (elliptic) topology for filters PID and PID-D2 controllers Darlington emitter-follower section and voltage gain stage Sorting network for seven items using only 16 steps 60 and 96 decibel amplifiers Analog computational circuits Real-time analog circuit for time-optimal robot control Electronic thermometer Voltage reference circuit Philbrick circuit NAND circuit Simultaneous synthesis of topology, sizing, placement, and routing

68 EVOLVED CAMPBELL FILTER U. S. patent 1,227,113 George Campbell American Telephone and Telegraph 1917

69 EVOLVED ZOBEL FILTER U. S. patent 1,538,964 Otto Zobel American Telephone and Telegraph Company 1925

70 EVOLVED SALLEN-KEY FILTER

71 EVOLVED DARLINGTON EMITTER- FOLLOWER SECTION U. S. patent 2,663,806 Sidney Darlington Bell Telephone Laboratories 1953

72 NEGATIVE FEEDBACK

73 HAROLD BLACK ’ S RIDE ON THE LACKAWANNA FERRY Courtesy of Lucent Technologies

74 Invenciones Siglo XXI Low-voltage balun circuit Mixed analog-digital variable capacitor circuit High-current load circuit Voltage-current conversion circuit Cubic function generator Tunable integrated active filter

75 LOW-VOLTAGE BALUN CIRCUIT

76 EVOLVED HIGH CURRENT LOAD CIRCUIT

77 REGISTER-CONTROLLED CAPACITOR CIRCUIT

78 LOW-VOLTAGE CUBIC CIRCUIT

79 VOLTAGE-CURRENT-CONVERSION CIRCUIT

80 TUNABLE INTEGRATED ACTIVE FILTER

81 Innovaciones PID tuning rules that outperform the Ziegler-Nichols and Åström-Hägglund tuning rules General-purpose controllers outperforming Ziegler-Nichols and Åström-Hägglund rules

82 EVOLVED EQUATIONS FOR GENERAL- PURPOSE CONTROLLER

83

84 EJEMPLO Aplicación de GP

85 Ejemplo La industria farmacéutica define la fabricación de cada medicamento por medio de una receta, la cual depende de componentes (elementos químicos), en cantidades definidas, y secuencias de pasos en los cuales estos componentes se mezclan y procesan. La industria farmacéutica define la fabricación de cada medicamento por medio de una receta, la cual depende de componentes (elementos químicos), en cantidades definidas, y secuencias de pasos en los cuales estos componentes se mezclan y procesan. Diseñe un sistema evolutivo, utilizando Programación Genética, que busque la receta de fabricación de un medicamento específico, considerando que dicha receta deberá ser capaz de producir unidades idénticas a un conjunto de unidades de muestra, las cuales se describen como una combinación química de elementos Diseñe un sistema evolutivo, utilizando Programación Genética, que busque la receta de fabricación de un medicamento específico, considerando que dicha receta deberá ser capaz de producir unidades idénticas a un conjunto de unidades de muestra, las cuales se describen como una combinación química de elementos (por ej: Aspirina es C 9 H 8 O 4 ). (por ej: Aspirina es C 9 H 8 O 4 ).

86 Ejemplo Defina y comente (incluyendo todas las suposiciones que determine como relevantes): Defina y comente (incluyendo todas las suposiciones que determine como relevantes): 1. La representación, incluyendo conjunto terminal y conjunto de operaciones del proceso. 2. Función de fitness utilizada en este caso. 3. Explique el funcionamiento del operador de mutación y del operador de crossover. 4. Condición de término y posibles parámetros de la ejecución.

87 Ejemplo Consideraciones y supuestos: Consideraciones y supuestos: Las cantidades de componentes se reducen a definir cantidades de átomos de cada elemento químico. Por ej, “2 átomos de Oxígeno” = O 2 Las cantidades de componentes se reducen a definir cantidades de átomos de cada elemento químico. Por ej, “2 átomos de Oxígeno” = O 2 No se conocen los procesos químicos, por lo que se definen algunos que podrían ser razonables. Por ej: “Mezcla de dos o más elementos”, “Precipitación”, “Evaporación”. (No se espera que los alumnos – sin tener una preparación en química – puedan dar una lista de procesos representativos en la industria farmacéutica real, salvo la mezcla y lo que podría denominarse simplemente “procesoN”.) No se conocen los procesos químicos, por lo que se definen algunos que podrían ser razonables. Por ej: “Mezcla de dos o más elementos”, “Precipitación”, “Evaporación”. (No se espera que los alumnos – sin tener una preparación en química – puedan dar una lista de procesos representativos en la industria farmacéutica real, salvo la mezcla y lo que podría denominarse simplemente “procesoN”.) Se supone que la asociación de elementos en la fórmula final no involucra un orden específico. Es decir, H 8 O 4 es lo mismo que O 4 H 8. Se supone que la asociación de elementos en la fórmula final no involucra un orden específico. Es decir, H 8 O 4 es lo mismo que O 4 H 8.

88 Ejemplo Representación: Representación: Conjunto Terminal: Elementos Químicos (E) con su respectiva cantidad de átomos (c) en la forma: E c. Por ej, C 2, H 3, B 4 Conjunto Terminal: Elementos Químicos (E) con su respectiva cantidad de átomos (c) en la forma: E c. Por ej, C 2, H 3, B 4 Conjunto de Funciones: Sin tener mayor información de los posibles procesos utilizados en la fabricación de medicamentos, se pueden resumir en ‘Mezcla’ (operador que recibe dos o más elementos) y ‘ProcesoN’, suponiendo que cada proceso de los N posibles son normalmente utilizados en la industria química. Conjunto de Funciones: Sin tener mayor información de los posibles procesos utilizados en la fabricación de medicamentos, se pueden resumir en ‘Mezcla’ (operador que recibe dos o más elementos) y ‘ProcesoN’, suponiendo que cada proceso de los N posibles son normalmente utilizados en la industria química.

89 Ejemplo Representación Gráfica Representación Gráfica Mezcla Proceso1 C9C9 Mezcla H8H8 O2O2 O2O2 Proceso2

90 Ejemplo Función de fitness. Función de fitness. Asumiendo que existe una forma de evaluar el árbol de la receta descrito en el punto anterior, el cual lleva a un resultado como H 8 O 4, entonces la función de fitness puede simplificarse a comparar la fórmula química resultante con la fórmula química de referencia (la muestra) comparando la combinación de cada elemento y sus átomos respectivos. Asumiendo que existe una forma de evaluar el árbol de la receta descrito en el punto anterior, el cual lleva a un resultado como H 8 O 4, entonces la función de fitness puede simplificarse a comparar la fórmula química resultante con la fórmula química de referencia (la muestra) comparando la combinación de cada elemento y sus átomos respectivos.

91 Ejemplo Función de fitness – cálculo valor fitness. Función de fitness – cálculo valor fitness. Revisar cada uno de los elementos de la fórmula de referencia y comparar las cantidades. Por cada átomo faltante, sumar un punto negativo. Revisar cada uno de los elementos de la fórmula de referencia y comparar las cantidades. Por cada átomo faltante, sumar un punto negativo. Si un elemento de la fórmula de referencia no está en la fórmula candidata, sumar 10 puntos negativos. Si un elemento de la fórmula de referencia no está en la fórmula candidata, sumar 10 puntos negativos. Si en la fórmula candidata hay un elemento que no está en la fórmula de referencia, sumar 10 puntos negativos. Si en la fórmula candidata hay un elemento que no está en la fórmula de referencia, sumar 10 puntos negativos. Finalmente, el proceso de optimización busca aquellas fórmulas minimizando el puntaje negativo. Finalmente, el proceso de optimización busca aquellas fórmulas minimizando el puntaje negativo. Otras posibles formas de cuantificar son válidas. Otras posibles formas de cuantificar son válidas.

92 Ejemplo Operador de Mutación: Operador de Mutación: Se determina un nodo aleatorio dentro del árbol de la receta y se reemplaza por la creación de un nodo nuevo, creado aleatoriamente. Se determina un nodo aleatorio dentro del árbol de la receta y se reemplaza por la creación de un nodo nuevo, creado aleatoriamente. Cada nuevo nodo creado aleatoriamente se compone de funciones y terminales. Cada nuevo nodo creado aleatoriamente se compone de funciones y terminales. Mezcla Proceso1 C9C9 O2O2 Proceso2 Nodo a Mutar O2O2 Proceso3 C9C9 Nodo de reemplazo, creado aleatoriamente

93 Ejemplo Operador de Crossover Operador de Crossover Se seleccionan dos padres, utilizando Elite, Ranking, Ruleta. Se seleccionan dos padres, utilizando Elite, Ranking, Ruleta. En cada uno de ellos se determina un punto aleatorio de crossover, haciendo el intercambio entre ambos padres, generando así dos hijos que contienen información genética de ambos padres. En cada uno de ellos se determina un punto aleatorio de crossover, haciendo el intercambio entre ambos padres, generando así dos hijos que contienen información genética de ambos padres.

94 Crossover Mezcla Proceso1 C9C9 O2O2 Proceso2 Padre 1 Corte para Crossover Padre 2 Mezcla Proceso1 H6H6 O2O2 Proceso2 Corte para Crossover Mezcla Proceso1 C9C9 O2O2 Proceso2 Hijo 1Hijo 2 Mezcla Proceso1 H6H6 O2O2 Proceso2

95 Ejemplo Condición de término y posibles parámetros. Condición de término y posibles parámetros. Se finaliza al encontrar una receta candidata cuya fórmula resultante resulte en una diferencia de 0 (o eventualmente -si es que la industria lo permite-, una diferencia mínima - con grado de tolerancia en puntaje negativo - con respecto a la fórmula referencial). Se finaliza al encontrar una receta candidata cuya fórmula resultante resulte en una diferencia de 0 (o eventualmente -si es que la industria lo permite-, una diferencia mínima - con grado de tolerancia en puntaje negativo - con respecto a la fórmula referencial). Parámetros de ejecución: Parámetros de ejecución: Tamaño de la Población, por ejemplo. Tamaño de la Población, por ejemplo.