PDF de programación - Algoritmos Evolutivos - Computación Evolutiva

Algoritmos Evolutivos - Computación Evolutivagráfica de visualizaciones

Publicado el 3 de Abril del 2017
1.212 visualizaciones desde el 3 de Abril del 2017
446,4 KB
39 paginas
Creado hace 11a (12/11/2012)
••

Algoritmos Evolutivos

Computación Evolutiva

M. E. Mazzei

UNA

Evolución

En la naturaleza, los procesos
evolutivos ocurren cuando
coexisten poblaciones de
individuos que son capaces de
reproducirse.

En la población existen individuos
que poseen alguna diferencia con
respecto al resto de ésta, que los
hacen más aptos.

••

2/39

UNA

Evolución y Genética

Es posible transmitir esa
diferencia a nuevas generaciones a
través del cruce entre los individuos
más aptos, resultando poblaciones
de individuos mejor adaptados.

Eventualmente ocurren mutaciones,
ó alteraciones en los cromosomas
de los individuos, que se pueden
transmitir a los descendientes.

••

3/39

UNA

Evolución y Genética

La evolución es un proceso que opera sobre los
cromosomas, los cuales representan los códigos de las
estructuras de la vida.

••

4/39

UNA

Evolución según Darwin

La población consiste de un conjunto diverso de
individuos.

Las combinaciones de características que producen
mejor adaptación tienden a aumentar su
representación en la población.

Ocurren variaciones a través de cambios al azar, que
producen una fuente constante de diversidad.

••

5/39

UNA

De la Genética y la Evolución a los Sistemas Artificiales

••

Las ideas de la Selección Natural y de la Genética han
sido tomadas para desarrollar técnicas basadas en
meta-heurísticas, en el ámbito de la Computación. Se
entiende por meta-heurística, una estrategia de alto
nivel que guía a otras heurísticas en la búsqueda de
soluciones factibles en dominios en los cuales la
búsqueda puede ser compleja.

Como resultado se han desarrollado métodos muy
exitosos en la resolución de diversos tipos de
problemas.

6/39

UNA

Evolución Artificial

Metáfora

••

7/39

UNA

Evolución Artificial

Las soluciones forman una población de individuos,
que se cruzarán mediante procesos aleatorios y a su
grado de adaptación.

La evaluación (o fitness) del individuo permite
cuantificar su adaptación.

La calidad de la solución podrá propagarse a nuevas
generaciones.

••

8/39

UNA

Paradigmas a tratar

••

9/39

UNA

Algoritmos Genéticos: Generalidades

••

Los Algoritmos Genéticos (GA) son métodos de
búsqueda basados en una simulación parcial de los
mecanismos de la evolución natural. Originalmente
fueron creados para optimizar funciones en valores
binarios.

Fueron creados en la década de los 60 por John
Holland, como un modelo de estudio de los procesos
adaptativos de los sistemas biológicos y para el
desarrollo de sistemas artificiales en el computador
que permitieran incorporar las fortalezas presentes en
los sistemas biológicos.

10/39

UNA

Algoritmos Genéticos: Elementos

••

Cada individuo se representa por un cromosoma.

Cada cromosoma consta de cierto número de
posiciones o genes. Cada gen contiene un alelo.

Sobre los individuos o cromosomas actúan ciertos
operadores: selección de individuos a reproducir,
recombinación y mutación.

Se realizan ajustes de parámetros.

11/39

UNA

Algoritmo Genético: otros conceptos tomados de la Genética

••

La información genética que posee un organismo se
llama genotipo y la apariencia física se llama
fenotipo.

El fenotipo se determina a partir del genotipo y
comprende la morfología, fisiología y conducta del
organismo.

12/39

UNA

Algoritmo Genético en seudolenguaje

••

Iniciar población

Evaluar población

Mientras no se satisfaga ( criterio de terminación) hacer

Seleccionar padres para reproducción

Aplicar operadores de recombinación y mutación

Evaluar población

Fin Mientras

13/39

UNA

Algoritmo Genético: Cromosomas

••

Los cromosomas pueden ser:

Números reales: ej.(0, 0.5, 45,6, -0.2)

Cadenas de caracteres: ej:‘ ⋆ L ♥ ∗ J ♦’
Cadenas de bits: ej. ‘00111101010’

Permutaciones de un conjunto de elementos: ej.
BAGF HLEJ → BLGF HAEJ

Reglas: ej. R2R9R11R23R19

Cualquier estructura de datos

14/39

UNA

Evaluación o fitness

••

El evaluador decodifica los cromosomas y le asigna
una medida de acondicionamiento.

La medición de evaluación representa la relación entre
el GA y su resolución. Normalmente en los problemas
típicos de optimización, la evaluación corresponde a la
función objetivo.

Ejemplo: f (x) = ex1x2x3x4x5

15/39

UNA

Cruce

••

El cruce acelera la búsqueda temprana hacia la
evolución de la población

Ejemplo: P1 y P2 son los padres ; h1 y h2 los hijos

P1: (1 1 1 0 1 0 1 0) h1: (1 1 1 1 1 1 0 1)

P2: (0 1 0 1 1 1 0 1) h2: (0 1 0 0 1 0 1 0)

16/39

UNA

Mutación

Eventualmente el material genético cambia
ligeramente. Esto significa que un hijo puede
tener información genética no heredada de los
padres.

Ejemplo:

antes:
después:

(1.05,3.45,5.09,7.32)
(1.05,3.45,5.01,7.32)

••

17/39

UNA

GA: Resumen de términos

••

18/39

UNA

Tipos de Operadores

••

Operadores de Selección: Son los mecanismos que se
emplean para seleccionar los padres en cada generación.
Los métodos más comunes son: Método de la Ruleta o
Método Proporcional, el Método del Torneo y el Método de
Escalamiento por Rango( Ranking).

Operadores de Variación: Son los mecanismos que se
aplican para recombinar( o cruzar) y para generar
mutaciones en los individuos. El operador de
recombinación o cruce actúa sobre dos o más individuos
seleccionados, para dar origen a uno o más individuos.

19/39

UNA

Método de la Ruleta

••

Se seleccionan ambos padres al azar, de acuerdo a

alguna distribución de probabilidad, obtenida sobre la base
de la mejor adaptación de los individuos. A cada individuo
le corresponde un sector de la ruleta. Funciona sobre la

base del principio: “Los mejor adaptados tienen más

posibilidad de ser seleccionados, pero no todos participan

en la selección”.

20/39

UNA

Método de Selección por Torneo

••

Consiste en la selección de un grupo de q individuos de la

población al azar, con o sin reemplazo. Este grupo de
individuos seleccionados formará parte del torneo. El

mejor individuo seleccionado es el que tiene mejor fitness

21/39

UNA

Estrategias Evolutivas: Generalidades

••

Son técnicas de optimización muy rápidas.

Fueron creadas por Rechenberg y Schwefel en la
década de los 70, para resolver un problema de
mecánica de fluidos.

Originalmente se emplearon en la optimización de
funciones en valores reales.

22/39

UNA

Estrategias Evolutivas

Tipos a tratar

••

23/39

UNA

Estrategias Evolutivas (1 + 1):

••

En t = 0 se genera un individuo al azar.

Se aplica el operador mutación al individuo obtenido.

De los dos individuos ( el original y el mutado) se
selecciona el que tenga mejor evaluación.

El proceso continúa hasta que se satisfaga la condición
de terminación.

El último individuo obtenido es el que tiene mejor
adaptaci ón y es la solución del problema

24/39

UNA

Estrategias Evolutivas (µ + 1)

••

En t = 0 se genera una población de µ individuos al
azar(µ > 1).

Se seleccionan al azar 2 individuos de la población.

Se aplica el operador recombinación entre los 2
individuos.

Se aplica el operador selección para eliminar entre los
µ + 1 individuos el que tenga peor evaluación.

El proceso continúa hasta que se satisfaga la condición
de terminación.

El mejor individuo representa la solución.

25/39

UNA

Estrategias Evolutivas (µ + λ)

••

En t = 0 se genera una población de µ individuos al
azar(µ > λ).

Se generan λ individuos a partir de los µ iniciales,
empleando recombinación.

Se aplica el operador selección para eliminar los λ
peores individuos según su evaluación.

El proceso continúa hasta que se satisfaga la condición
de terminación.

El mejor individuo representa la solución.

26/39

UNA

Estrategias Evolutivas (µ, λ)

••

Es una modificación de la estrategia (µ + λ)

Se parte de una población de µ > λ individuos al azar.

Se generan λ individuos a partir de los µ iniciales,
empleando recombinación.

Los λ individuos nuevos son mutados.

Se aplica un operador de selección para eliminar los λ
peores individuos.

El proceso continúa hasta que se satisfaga la condición
de terminación.

El mejor individuo representa la solución.

27/39

UNA

Resumen: Tipos de Estrategias Evolutivas

••

µ: Número de individuos de la población. λ
individuos adicionales.

(1 + 1) − ES es una estrategia evolutiva de dos
miembros.
(µ + 1), (µ + λ) y (µ, λ) son estrategias evolutivas
de múltiples miembros.

28/39

UNA

Programación Genética

••

La Programación Genética(GP,Genetic Programming) es
una técnica desarrollada por John Koza, a finales de la
década de los ochenta.

El objetivo era crear una generación automática de
programas.

Se crea inicialmente una población de individuos.

Los individuos son programas que evolucionan

Se emplean operadores de variación y selección para
obtener nuevos individuos.

Los programas se expresan mediante árboles.

29/39

UNA

Ejemplo de Programación Genética

••

Un Robot en un mundo cuadriculado ( N. Nilsson, ver
bibliografía)
Sea un robot ubicado en un recinto como el que se
muestra en la figura. Se señalan las posibles acciones.

30/39

UNA

Ejemplo de Programación Genética

••

El objetivo es desarrollar un programa que haga que el
robot se mueva,desde alguna posición inicial hasta una
celda contigua a la pared, para continuar paralelo a la
pared a lo largo del recinto. Las funciones primitivas son
las siguientes:

and(x,y) = 0 si x = 0; si no, y

or (x,y) = 1 si x = 1; si no, y

not (x) = 0 si x = 1; si no, 1

if(x,y,z)= y si x = 1; si no 2

31/39

UNA

Ejemplo de Programación Genética

••

Las entradas sensoriales asociadas al robot son: n,
ne, e, se, s, so, o y no. Estas toman un valor 0 siempre
que la celda correspondiente pueda ser ocupada por
el robot, en caso contrario toman el valor 1.

Se debe asegurar que todas las expresiones y
sub-expresiones usadas sean correctas, y por lo tanto
se puedan evaluar.

En la siguiente figura se observa un programa, el cual
ejecutado ocasiona que el robot se mueva hacia el
norte hasta que encuentre la pared. El movimiento
siempre será en el sentido de las agujas del reloj.

32/39

UNA

Ejemplo de Programación Genética

••

33/39
  • Links de descarga
http://lwp-l.com/pdf2651

Comentarios de: Algoritmos Evolutivos - Computación Evolutiva (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad