Aspectos Teóricos Metodológicos de la Programación Presupuestaria, Marcos Makón
Programación Genética: Introducción y Aspectos Generales
-
Upload
john-diaz -
Category
Technology
-
view
257 -
download
2
description
Transcript of Programación Genética: Introducción y Aspectos Generales
Programación Genética
John Jaime Sprockel Díaz
MISyC
Departamento de Ingeniería de Sistemas
Facultad de Ingeniería
Pontificia Universidad Javeriana
AGENDA
1. Aspectos Históricos
2. Definición
3. Lenguajes
4. Representación de Programasa. Propiedad de Clausura
5. Pasosa. Inicialización de los Árboles
b. Selección de la Población Inicial: Fitness
6. Mecanísmos Evolutivosa. Recombinación
b. Mutación
7. Implementación
8. Presentación de un Artículo
Programación Genética:
Historia
Turing (1950-1953) “búsqueda genética o evolucionaria”
Smith (1980) sistema de clasificación para encontrar estrategias en póker
Cramer (1985) representación de programas con arboles en un genotipo
Hicklin (1986) y Fujiki y Dickinson(1987) consideraron métodos para evolucionar programas en LIPS. Y Dickmanns, Schmidhuber y Winkklohofer(1987) en PROLOG.
Koza (1989, 1992) importancia de la programación genética para inducción de programas en un amplio rango de campos.
Interrogante:
¿Cómo generar
programas
automáticos?
Programación Genética
Lenguaje de Generación de Programas
Características:
Restringidos,
Definidos por el usuario,
Con operadores, variables y constantes adecuados definidos para el problema
Programación
Funcional
Lenguaje de Generación de Programas
Estructuras de los Programas
Árboles LinealGrafos
Órden Prefix
ó postfix
Memoria
Local
Asas y
recursión
Memoria
local y global
Cadena de
instrucciones
de ejecución
secuencial
Memoria no-
local
Representación de Programas:
Árboles
- Terminales:
Proveen valor al sistema de PG.
- Funciones:
Procesan los valores existentes en el sistema.
Lenguaje de Generación de Programas
• Conjuntos Terminales y de Funciones
– De Terminales: entradas, constantes y funciones sin argumentos.
• Retorna un valor numérico
• Las constantes pueden integrarse en nuevas constantes.
– De Funciones: funciones, operadores y declaraciones.• Pueden ser específicas de la aplicación
• Debe ser suficientemente poderoso para suplir una representación para la solución del problema.
• No debe ser muy largo
Representan los nodos de un árbol. Otras son grafos, estructuras lineales o incluso
autómatas celulares.
Representación de Programas:
Lineal
Lenguaje de Generación de Programas
• Propiedad de Clausura (Cierre)
– Es un requerimiento importante
– “Cada función en el conjunto de funciones debe ser capaz de aceptar como argumento cualquier otra salida de una función y algún terminal en el conjunto terminal”.
– Todo el conjunto de estructuras posibles debe ser formado recursivamente de los conjuntos de función y de terminales.
Inicialización de los Árboles
Método de Crecimiento
(“Grow”)
• Formas Irregulares
• Se especifica la profundidad máxima (Dmáx )
Método Completo
(“full”)
• Árboles Regulares
• Se especifíca la misma Dmáx
RampedHalf and
Half
• Introduce diversidad en la pobl inicial
• Usando ambas tecnicas
Cálculo del Fitness
• Si se logra disponer de una función objetiva para ser optimizada, se puede
obtener una función de fitness por una
trasformación de escala de la función
objetivo.
• No es fácil -> se usa un conjunto de
entrenamiento y se define como una
función basada en error.
Cálculo del Fitness
• A partir de los k ejemplos de
entrenamiento tenemos:
(xi, yi), i = 1,…, k
xi es la entrada
yi es la salida
ei = (yi –oi)^2
f(P) = ∑ei = ∑(yi –oi)^2 Función de error cuadrática
Operadores de Recombinación
Árboles:
Intercambio de sub-árboles entre
padres, pasos:
Escoger los padres
Seleccionar un sub-árbol
Intercambiar los sub-árboles
Operadores de Recombinación
Representación lineal:
Operadores de Recombinación
INTRONES:
Secuencia de ADN que no carga
información genética (no codificada).
Son usados para mejorar el chance de
entrecruzar los bloques a recombinar,
reduce su efecto disruptivo.
X1 Intrón X2 Intrón … Intrón Xs
Operadores de Recombinación
INTRONES:
En GP puede ser un operador que no
produce un cambio en el estado del
sistema.
Emergencias en el proceso de
búsqueda, no afecta el fitness
Espontáneos o insertados
Artificialmente
Mutación
Árboles:
1. Macromutación:
Selecciona aleatoriamente un punto
interno – conj de funciones
externo – símbolo terminal
Mutación
Árboles:
2. Micromutación:
Altera un simple nodo
Mutación
Representación Lineal:
Se selecciona una instrucción
Es perturbada aleatoriamente cambiando
alguna de sus partes
O se selecciona una secuencia de
instrucciones que luego son reemplazadas
X1 X2 X4 X5 X6
X1 X2 X4 X5* X6
X1 X2 X4 X5* X6*
Mutación
IMPLEMENTACIÓN:Se aplica con una probabilidad específica.
Otra, aplicación separada del entrecruzamiento y
mutación
Selección
En la GP no es específica. El problema puede imponer
una elección particular.
_Selección Por Recombinación
Todas las variantes pueden ser usadas, problema:
encontrar el adecuado.
Torneo: en problemas grandes
_Selección Por Reemplazo
Todos los tipos:
Generacional o de Estado Estable
CONJUNTO DE PROCEDIMIENTOS EN GP
Definir el conjunto de Funciones
Definir el conjunto de Terminales
Definir el procedimiento de evaluación
Definir los parámetros de procedimiento
GP
Tamaño de la población,
Profundidad máxima del nodo
Tamaño máximo del individuo
Probabilidades de entre cruzamiento
y mutación
Algoritmo de Programación GenéticaGeneracional
S1. Set t = 0
Initiate población P(t)S2. while (⌐ Condición de terminación) do begin
S2.1. Evaluate individuos en P(t)S2.2. Select individuos en P(t) usando el
algoritmo de selecciónS2.3. Apply operadores de variación para los
individuos seleccionados
S2.4. Insert la descendencia obtenida dentro de la nueva población
S2.5. Set t= t+1
end
Algoritmo de Programación GenéticaEstado Estable
S1. Initiate población
S2. while (⌐ Condición de terminación) do begin
S2.1. Chose un grupo para torneo
S2.2. Play el torneo con los competidores seleccionados
S2.3. Select los ganadores del torneo
S2.4. Modify los ganadores usando operadores de variación
S2.5. Replace algunos de los perdedores del torneo con la descendencia
end
Variaciones
Recombinación de Crías (Tackett, 1994)
-Genera más descendencia (crías)
-Solo se selecciona las dos mejores
crías, el resto se descarta.
-Se considera un parámetro de tamaño
de la cría: K .
Variaciones
Selección punto de entrecruzamiento
Iba y Garis (1996) método para detectar
regularidades en el árbol del programa
Asigna un valor de desempeño a un sub-
árbol
El operador de recombinación aprende
a seleccionar el punto de corte
Presented at the 12th IEEE Symposium on Computer-Based Medical Systems,
1999. Proceedings., IEEE Comput. Soc. (pp. 202–207).
Predicción de Diagnósticos Médicos
Usando Programación Genética
Introducción:-Posicionamiento DSS en Md.
-Posible papel de Árboles de Decisiones
-Limitaciones en su construcción: Selección del mejor
Objetivo:Construir con la ayuda de la programación genética
una herramienta que ayude a predecir un
diagnóstico correcto aplicado al prolapso de la
válvula mitral (MVP). Reducir los pasos en Dx.
Predicción de Diagnósticos Médicos
Usando Programación Genética
Descripción de:
1. MVP
2. Árboles de decisiones
3. Programación genética
Predicción de Diagnósticos Médicos
Usando Programación Genética
Predicción de Diagnósticos Médicos
Usando Programación Genética
Predicción de Diagnósticos Médicos
Usando Programación Genética
x<2
y y
y<1.8 Y<2 y >1.8
x<1.8 x>1.8 Naranja
…y>2 y >2.3 y>2.3
x>1 …
RojoNaranja
Rojo
…
SI NO
Predicción de Diagnósticos Médicos
Usando Programación Genética
F1
F2
F3
<F1
<F2 >F3
Rojo
SI NO
Naranja…
Predicción de Diagnósticos Médicos
Usando Programación Genética
Resultados:
Ptes: 900 ptes <18 años (representativa)
Todos raza Blanca
Área de Maribor (Slovenia)
631 voluntarios para ecocardiograma
103 parámetros que podrían indicar la
presencia de MVP
Entrenamiento 500 ptes, 131 prueba
Predicción de Diagnósticos Médicos
Usando Programación Genética
Falsos
positivosFalsos
negativos
Predicción de Diagnósticos Médicos
Usando Programación Genética
Predicción de Diagnósticos Médicos
Usando Programación Genética
Conclusión:
La introducción de técnicas de
programación automática en la toma
de decisiones médicas ha mostrado
algunos buenos resultados, al menos
en MVP.
Gracias
• John Jaime Sprockel Díaz.
– Pontificia Universidad Javeriana
– Maestría de Ingeniería de Sistemas y
Computación
– email: [email protected]