Programacingenticajohnsprockel 131009180802 Phpapp02

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.
2.
3.
4.

Aspectos Históricos
Definición
Lenguajes
Representación de Programas

a. Propiedad de Clausura

5. Pasos

a. Inicialización de los Árboles
b. Selección de la Población Inicial: Fitness

6. Mecanísmos Evolutivos
a. Recombinaciónb. Mutación

7. Implementación
8. Presentación de un Artículo

Programación Genética:
Historia
Interrogante:
¿Cómo generar
programas
automáticos?

Smith (1980)
sistema de
clasificación
para
encontrar
Turing
estrategias en
(1950-1953)
póker
“búsqueda
genética o
evolucionari
a”

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
Winkklohofe
r (1987) en
PROLOG.

Koza (1989,
1992)
importancia
de la
programaci
ón genética
para
inducción
de
programas
en un
amplio
rango de
campos.

Programación Genética

Lenguaje de Generación de
Programas
Características:
Restringidos,
Definidos por el usuario,
Con operadores, variables y constantes
adecuadosdefinidos para el problema

Programación
Funcional

Lenguaje de Generación de
Programas
Creatividad
en crear
nuevas
funciones

Que soporte
representaci
ón en
árboles

Escoger
el
Lenguaj
e
Co-evolución

Autoadaptación

Estructuras de los Programas
Árboles
Grafos
Lineal

Órden Prefix
ó postfix
Memoria
Local

Asas y
recursión
Memoria
local y global

Cadena de
instrucciones
de ejecución
secuencialMemoria nolocal

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
• Propiedadde 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
Formas
Método de
Crecimiento(“Grow”)

Método
Completo
(“full”)

Ramped
Half and
Half

Irregulares
• Se especifica
la
profundidad
máxima
(Dmáx )

• Árboles
Regulares
• Se especifíca
la misma Dmáx

• 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 dela 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.

Operadores de Recombinación
INTRONES:
En GP puede...