programación genética (pg)
DESCRIPTION
Programación Genética (PG). Mario Hernández. ¿PG?. La PG suministra una metodología para crear automáticamente programas a partir de una definición de los mismos a alto nivel. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/1.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Programación Genética(PG)
Mario Hernández
![Page 2: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/2.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
¿PG?
• La PG suministra una metodología para crear automáticamente programas a partir de una definición de los mismos a alto nivel.
• PG consigue el objetivo de Programación Automática (también denominada Síntesis de Programas o Inducción de Programas) reproduciendo genéticamente una población de programas utilizando los principios darwinianos de la selección natural y de las operaciones inspiradas biológicamente.
![Page 3: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/3.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
PG
• Rama de la Computación Evolutiva (CE)
• Diferencia PG - AG: ¿qué solución se busca?O, de otra manera: cuál es la
representación que se utiliza para la solución
•
![Page 4: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/4.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• Los AG crean cadenas de cromosomas que codifican (representan) la solución buscada
• La PG crea Programas (código)
• Es decir: en PG se transforman Programas que buscan la Solución, en vez de la Representación de la solución
![Page 5: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/5.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Algunos Campos de Aplicación
• Síntesis automática de circuitos eléctricos analógicos• Síntesis automática de controladores • Problemas en biología molecular computacional,
incluyendo rutas metabólicas y redes genéticas. • Autómatas Celulares • Sistemas Multiagente• Investigación Operativa• Areas de Diseño• Uso de PG como una “Máquina Automática de
Invenciones” para crear nuevas invenciones útiles patentables
![Page 6: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/6.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Algoritmo Evolutivo General
• Crear aleatoriamente una población de soluciones
• Hacer iterativamente, hasta alcanzar una solución suficientemente buena:– Evaluar cada solución, dándole una
puntuación– Escoger las mejores y reproducirlas;
mutarlas o cruzarlas, con otras nuevas soluciones para la próxima generación
![Page 7: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/7.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Algoritmo General de PG
1) Generarar una población inicial de programas2) Ejecutar cada programa de la población y asignarle
un valor de aptitud (fitness) de acuerdo a lo bien que resuelve el problema.
3) Crear una nueva población de programas aplicando las siguientes operaciones:
i) Copiar los mejores programas existentes ii) Crear nuevos programas por mutacióniii) Crear nuevos programas por cruce
(crossover)El mejor programa aparecido en cualquier generación, es
decir el que genera la mejor de las soluciones con las restricciones que le son impuestas (pe complejidad, etc…), resulta designado como el resultado del procedimiento de Selección Genética por PG.
![Page 8: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/8.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
La Idea ¿Lunática? de Evolucionar Programas
• Ejemplo del primer paso: Programa generado aleatoriamente:
![Page 9: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/9.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Argumentos contra la evolución de programas
• Los programas creados aleatoriamente tienen una posibilidad infinitesimal de compilar, y menos que hagan lo que se pretende
• La ejecución de un programa creado aleatoriamente darán lugar, si compila, y muy probablemente a errores de salida de espacios reservados para matrices, data-casting, core-dumps, divisiones por cero, etc... lo que conllevará a suspensión de ejecución
• Mutar y mezclar segmentos de programas creados aleatoriamente resulta en un sinsentido equivalente a crearlos aleatoriamente
¿Cómo se resuelve esto en la PG?
![Page 10: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/10.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
La Representación en PG
El truco consiste en escoger una representación subyacente para los programas tal que resulte factible la creación aleatoria, la mutación y el cruce de programas
![Page 11: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/11.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
La Representación en PG
• Representación basada en árboles
+
* 4
5 -2
(+ (* 5 –2) 4)La representación empleada en PG se basa en árboles, que presentan una correspondencia directa con la notación prefija o polaca
![Page 12: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/12.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• Una familia de lenguajes de programación que se adapta a esta representación son la familia Lisp (Lisp-like), como p.e. Lisp o Scheme
La Representación en PG (II)
![Page 13: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/13.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Notación Sufija Notación Prefija f(x,y) (f x y)
3*4 (* 3 4)
Los programas complejos se expresan utilizando funciones compuestas, pe:
(+ 2 (IF (> X 3) 4 7))
La Representación en PG (III)
![Page 14: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/14.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
(+ 2 (IF (> X 3) 4 7))La estructura consta de funciones y terminales
+
2 IF
> 4
X 3
7
![Page 15: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/15.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Utilidad de la representación en árbol
1. La estructura en árbol resulta útil para definir los efectos de los operadores sobre los programas
2. Los operadores presentan una estructura muy “elegante” en este formato
3. También resulta útil a efectos prácticos en dominios de aplicación como:– Determinar las capas (layouts) en un circuito
integrado analógico– Crear redes neuronales– Paralelizar programas– Y muchos otros ...
![Page 16: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/16.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Ventajas de las estructuras “Lispy”
• Cada programa es una lista uniforme• Las listas representan, sin distinción alguna,
datos y código. Ello permite que se puedan definir las operaciones genéticas de forma sencilla
• El formato de las instrucciones es el de una función aplicada a argumentos. Ello representa la información de control en una sintaxis común, que resulta (otra vez) cómoda para su modificación genética
• La estructura de longitud variable de las lista supera la limitación de longitud fija de las cadenas (strings) en los AG
![Page 17: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/17.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Operadores Genéticos para Programas
• Creación: generación aleatoria de árboles utilizando funciones y terminales
• Cruce: fijar puntos de cruce en ambos padres y solapar ambos subárboles
• Mutación: fijar un punto de mutación en un padre y reemplazar subárbol con un árbol generado aleatoriamente
![Page 18: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/18.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Para aplicar operadores genéticos
El Primer Paso:Identificación de los “Puntos de Fractura” : análogos a los “puntos de cruce en las representaciones genéticas en cadenas utilizadas por los AG.
Pueden ser:1. El Inicio de una sublista2. Un Terminal
![Page 19: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/19.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Implementación de Operadores
I. CruceII. InversiónIII. Mutación
![Page 20: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/20.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
I. Operador de Cruce (crossover)
Pasos:1. Escoger dos programas criadores
individuales2. Seleccionar dos sublistas, una por
criador3. Intercambiar las sublistas en la
descendencia
![Page 21: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/21.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 1
*
x +
x y
+
/*
yz y x
(* x (+ x y )) (+ (* z y) (/ y x ))
![Page 22: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/22.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
*
x +
x y
+
/*
yz y x
![Page 23: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/23.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
*
x +
x y
+
/*
yz y x
![Page 24: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/24.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
*
x +
x
+
*
z y
![Page 25: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/25.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 3
y
*
x +
x
+
*
z y/
y x
![Page 26: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/26.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
II. Operador de Inversión
Pasos:1. Escoger un individuo de la
población2. Seleccionar dos puntos de fractura
en el individuo3. Generar un nuevo individuo
conmutando los símbolos delimitados y solapando las sublistas con la lista principal
![Page 27: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/27.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 1
+
/*
yz y x
![Page 28: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/28.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
+
/*
yz y x
![Page 29: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/29.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
+
/*
yz y x
![Page 30: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/30.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
+
/*
yz y x
![Page 31: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/31.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 3
+
/*
yz y x
![Page 32: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/32.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 3
+
/
*
y
z
y
x
![Page 33: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/33.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 3
+
/
*
y
z
y
x
![Page 34: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/34.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
III. Operador de Mutación
Pasos:1. Seleccionar un programa padre 2. Reemplazar aleatoriamente
cualquier símbolo de función por cualquier otro o cualquier símbolo terminal por cualquier otro
![Page 35: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/35.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 1
+
/*
yz y x
![Page 36: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/36.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
+
/*
yz y x
![Page 37: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/37.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
+
/+
yz y x
![Page 38: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/38.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Paso 2
+
/+
yz y x
![Page 39: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/39.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Problema
• Todos los ejemplos anteriores son aritméticos
• En casos más generales puede darse SOLAPAMIENTO DE ARGUMENTOS
Pe: si una función devuelve una lista y se intercambia con otra que devuelve un entero, la estructura resultará sintacticamente inválida
![Page 40: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/40.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Soluciones
1. Todas las funciones deben devolver el mismo tipo de argumentos (pe entero)
2. Usar programación genética fuertemente tipada para asegurar que todas las expresiones son type-safe
3. Implementar algún tipo de chequeo
![Page 41: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/41.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Algoritmo de PG
• La principal diferencia del algoritmo básico de PG con el AG básico surge de la sustitución de las cadenas por programas
• Esta diferencia se muestra en la evaluación de la aptitud, por lo que el programa se prueba con un conjunto de entradas para evaluarlo.
![Page 42: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/42.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Algoritmo de PG
• Escoger una población de tamaño NP
• Escoger el número de generaciones NG
• Inicializar la población• Repetir durante NG generaciones
– Seleccionar probabilísticamente un cierto número de pares de individuos de la población después de asignar a cada estructura una probabilidad proporcional a su aptitud (fitness) o desempeño (performance)
– Copiar las estructuras seleccionadas y aplicarle los operadores para producir nuevas estructuras
– Seleccionar aleatoriamente otros elementos y reemplazarlos con las nuevas estructuras
– Observar y registrar la aptitud de las nuevas estructuras
– Suministrar como salida a los individuos más adecuados
![Page 43: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/43.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Creación de la Población Inicial
• Cuando se crea una población, resulta interesante empezar con muchos árboles de diferentes tamaños/formas
• Se generan árboles utilizando los siguientes métodos:– Full: cada ruta en el árbol es de la longitud
máxima– Grow: las longitudes de rutas varían hasta la
longitud máximaRamp half-and-half: (típico) se crean árboles de profundidades variadas desde un mínimo hasta un máximo, y para cada profundidad, la mitad se crean usando el método full y la otra mitad usando el método grow
![Page 44: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/44.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Pasos preparatorios para PG
Una vez decidido que quieres resolver un problema usando GP, para efectuar la ejecución se necesita:– Determinar el conjunto de terminales: variables, valores
de entrada o comandos de acción– Determinar el conjunto de funciones (no terminales)– Determinar la medida de aptitud (fitness)– Los parámetros para controlar la ejecución:
• Tamaño de población• Número máximo de generaciones• Tasas de Mutación, cruce y reproducción (típicos 1, 90 y
9%)– El método de terminación de una ejecución y de
designación de un resultado
![Page 45: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/45.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Suficiencia y Cierre
El conjunto de funciones y el de terminales deben satisfacer los principios:
• Cierre: cada función f debe ser capaz de aceptar los valores de todos los terminales t del conjunto de terminales y cada función f del conjunto de funciones
• Suficiencia: en el Espacio de Programas creado a partir de los conjuntos de funciones y terminales
• debe existir una solución al problema que se plantea
![Page 46: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/46.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Algunos Ejemplos
![Page 47: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/47.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Ejemplo: Paridad
Objetivo: obtener la función paridad n-par, pe n=3
Entrada Salida
000001010011100101110111
10010110
![Page 48: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/48.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Elementos del Problema
• Conjunto de Terminales: los tres símbolos que representan las tres posibles entradas a ser comprobadas para paridad:
T = {D0, D1, D2}• Conjunto de Funciones: primitivas
booleanas de dos argumentosF = [AND, OR, NAND, NOR}
![Page 49: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/49.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Solución
• Utilizando una población inicial de 4000 programas, se descubrió una solución en la generación 5
• La solución contiene 45 elementos (terminales + no terminales)
![Page 50: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/50.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Solución (II)
(AND (OR (OR D0 (NOR D1 D2)) D2)
(AND (NAND (NOR (NOR (NOR D0 D2)
(AND (AND D1 D1) D1))
(NAND (OR (AND D0 D1) D2) D0))
(OR (NAND (AND (D0 D2)
(OR (NOR D0 (OR D2 D0) D1))
(NAND (NAND D1 (NAND (D0 D1)) D2)))
![Page 51: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/51.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Comentarios sobre la Solución
• La solución no es la función mínima que puede escribirse a mano, sino que contiene muchos usos del conjunto de funciones primitivas
• Ello se debe a que NO EXISTE PRESIÓN SOBRE EL MECANISMO DE SELECCIÓN para escoger la función mínima
![Page 52: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/52.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Parsimonia
• Como se explica en (Koza-92):“Como ocurre con el genoma de los seres vivos, los resultados de la PG raramente son las estructuras mínimas que se definirían a mano para realizar la tarea”
• Los humanos tendemos a seleccionar las explicaciones simples y potentes, incluso a costa de alguna validez empírica
• Principio de Parsimonia: obtener la estructura más pequeña posible que permita resolver el problema
(Koza-92) J. Koza, Genetic Programming, MIT Press , 1992
![Page 53: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/53.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• La naturaleza no tiene porqué favorecer tales estructuras parsimónicas, aunque nosotros las prefiramos como explicaciones de un cierto fenómeno.
• (Koza-92) sugiere un conjunto de factores secundarios que penalizan una solución particular que posea excesivo tamaño o tiempo.
• De esta manera se pueden evolucionar soluciones correctas que sean eficientes y parsimónicas.
![Page 54: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/54.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Ejemplo: Regresión Simbólica
Generar con GP el ajuste de una función a la siguiente tabla de datos
![Page 55: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/55.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Regresión Simbólica (II)
• Conjunto de Funciones: +, -, *, /• Conjunto de Terminales: X• Medida de Aptitud (Fitness): diferencia absoluta del
error. Más apta error 0• Parámetros:
– Tamaño de población: 500– Nº máx. de generaciones: 10– Cruce: 90%– Mutación: 1%– Reproducción: 9%– Selección por Torneo (tamaño 5)– Creación utilizando el método RAMP-HALF-AND-HALF– Condición de terminación: Cuando se encuentra un
programa con aptitud 0.
![Page 56: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/56.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Regresión Simbólica. Resultados
• Individuo Solución con Aptitud 0:(ADD (ADD (MUL X X) (MUL X X))
(MUL (MUL X X) (- X)))(SUB X (SUB (SUB (SUB X X) (MUL X X)) (MUL (ADD X X)
(MUL X X)))))
• Que captura correctamente la función:
f(x) = x4 + x3 + x2 + x
![Page 57: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/57.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Ejemplo: Camino de Santa Fe
Problema: una hormiga artificial debe “comerse” todas las piezas de alimento (89) en un camino. La hormiga solo puede moverse a la izda., a la dcha. o adelante, y sólo puede percibir lo que se encuentra directamente enfrente.
![Page 58: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/58.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Camino de Santa Fe (II)• Conjunto de Funciones: Prog2, Prog3, IfFoodAhead• Conjunto de Terminales: TurnLeft, TurnRight, MoveForward• Medida de Aptitud: recuento del número de items comidos
despues de un número fijo de movimientos, y restarlos de 89. Mala aptitud = 89, Buena Aptitud = 0.
• Parámetros:– Tamaño de población: 500– Nº máx. de generaciones: 50– Cruce: 90%– Mutación: 1%– Reproducción: 9%– Selección por Torneo (tamaño 5)– Creación utilizando el método RAMP-HALF-AND-HALF– Condición de terminación: Cuando se encuentra un
programa con aptitud 0.
![Page 59: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/59.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Camino de Santa Fe. Resultados
• Resultados del agente obtenido
![Page 60: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/60.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Camino de Santa Fe. Resultados
(Prog3 (IfFoodAhead (IfFoodAhead (IfFoodAhead (IfFoodAhead (Prog2 MoveForward MoveForward) TurnLeft) TurnLeft) TurnLeft) (IfFoodAhead MoveForward (IfFoodAhead MoveForward (IfFoodAhead (IfFoodAhead (Prog2 MoveForward MoveForward) TurnLeft) TurnLeft)))) TurnLeft (Prog3 (IfFoodAhead (IfFoodAhead MoveForward TurnLeft) TurnRight) MoveForward TurnRight))
Es posible encontrar agentes más simples
![Page 61: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/61.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Aplicabilidad
• John Koza ha comprobado que la PG resulta efectiva en un rango amplio de problemas, no solamente en regresión simbólica, como se ve en el ejemplo anterior.
• Utilizando conjuntos de funciones que incluyen comandos típicos de programación (como IF o DO-UNTIL), Koza ha evolucionado algoritmos en muchos dominios como:– Control Óptimo– Inducción de Secuencias – Estrategias en Juegos– Inducción de árboles de decisión – Predicción Económica– Etc ....
![Page 62: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/62.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
1000-Pentium Beowulf-Style Cluster Computer (29 Julio 1999)
Computador paralelo con un servidor y 1,000 P-II 350-MHz 64 MB (94 GB total) en 500 placas madre dual-CPU Tyan Tiger 100 con 128 MB en una minitorre c/u con una tarjeta de interface de red de 100 Mb/s. Intel PRO/100+ y una fuente de alimentación de 300 w.
![Page 63: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/63.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• Cada grupo de 40 procesadores (20 carcasas)se conecta a uno de los 25 hubs de 24 puertos y 100 Mb/s
• Cada hub se encuentra conectado a uno de los dos switches de 100 Mb/s y 16 puertos conectados entre si y al servidor.
• El servidor es un Dual Pentium II 350-MHz con 256 MB de RAM, 14 GB de disco, display, teclado, CDROM y unidad de floppy. Corre Red Hat Linux 6.0
• Los 1000 proceadores estan organizados en un grid toroidal de 25x40.
• Cada grupo de 40 procesadores que comparten un hub se organizan en un rectángulo de 8x5.
• El sistema de 1,000-nodos puede acomodar una población de 10.000.000 de programas individuales de 3.000 puntos (funciones o terminales) 30.000.000 de 1.000 puntos.
• Una generación se computa en 0,25 h., y en un día se pueden computar 96 generaciones
![Page 64: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/64.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Eficacia de PG vs. Búsqueda Aleatoria
• Depende del problema• Pero para la mayor parte de los
problemas computacionalmente duros, la evidencia experimental es que el comportamiento de de la PG es mucho mejor.
![Page 65: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/65.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Análisis
• El análisis teórico del desempeño (performance) de la PG es muy difícil
• Se suele caracterizar experimentalmente, observando el comportamiento del algoritmo en ejecuciones sucesivas variando NG y NP, y extrayendo a continuación algunas conclusiones generales
![Page 66: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/66.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• Pk(NP) : probabilidad de generar una solución en una generación particular k utilizando un tamaño de población NP
• P(NG,i) : probabilidad acumulativa de encontrar una solución hasta (incluyéndola) la generación i:
i
kpkG NPiNP
1
)(),(
![Page 67: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/67.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• A priori se cree que Pk se incrementaría monótonamente con k, por lo que con más generaciones se alcanzaría inevitablemente la solución.
• La evidencia experimental muestra otra cosa
• La aptitud de los individuos tiende a la alcanzar una “llanura” (plateau), significando que la búsqueda de la solución ha alcanzado un mínimo local
• Por tanto, para la mayoría de los casos, Pk disminuye con k
![Page 68: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/68.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• La solución es asumir que sucesivos experimentos son independientes entre si, y alcanzar el óptimo repitiendo ejecuciones que partan de diferentes condiciones iniciales
• Una fórmula sencilla determina el número de ejecuciones necesarias basadas en medidas de éxito empírico
![Page 69: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/69.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
Determinación del número de ejecuciones necesarias
• Establece un compromiso entre tamaño de población y múltiples ejecuciones
• Asumiendo ejecuciones independientes, el número necesario se puede obtener conocido P(NP, i) de la siguiente manera
![Page 70: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/70.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• PA : prob. De alcanzar la solución después de G generaciones
• Si r es el número de experimentos, se puede obtener PA como:
PA = 1 – [1 – P(NP, G) ]r
• Como la variable de interés es r, tomando logaritmos:
ln (1 – PA) = r ln [1- P(NP, G) ]
• Ó: r = ln / ln [1- P(NP, G) ]• Siendo : = (1 – PA)
![Page 71: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/71.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
• Esta fórmula permite realizar una estima grosera del algoritmo GP para un problema particular
• Se obtiene un compromiso entre tamaño de población y número de ejecuciones
![Page 72: Programación Genética (PG)](https://reader030.vdocumento.com/reader030/viewer/2022032708/56812b5e550346895d8f81de/html5/thumbnails/72.jpg)
B
ioin
form
áti
ca-P
rog
ram
aci
ón
B
ioin
form
áti
ca-P
rogra
maci
ón
G
en
éti
caG
en
éti
ca
Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería
FIN