Agenda
Introducción
Cómo funcionan
Ejemplo
Por qué funcionan
Algoritmos genéticos paralelos
Introducción
Provienen de la familia de modelo computacional basado en la evolución
Introducidos por Holland en 1975
Proveen una solución potencial a un problema específico en una estructura tipo cromosoma y aplican operadores de recombinación para preservar la información crítica
Cualquier modelo basado en población que usa selección y recombinación para generar nuevos elementos en el espacio de búsqueda
Introducción
Población
Conjunto de soluciones potenciales, donde la población inicial puede ser elegida randómicamente
Cambia con el tiempo pero su tamaño se mantiene
Individuo
Elemento de la población
Cada individuo es representado por una cadena de caracteres
Introducción
Crossover
Dos nuevos individuos pueden ser obtenidos de dos padres en el mating pool, recombinando a ambos padres
Mutación
Individuos en el mating pool también pueden cambiar a través de mutación randómica
Resultado -> Un nueva generación
El proceso se repite y converge a una población con individuos muy similares entre si
Algoritmo genético Canónico
Los individuos son cadenas binarias de largo fijo codificadas según el problema a resolver
En general las poblaciones iniciales se eligen de forma randómica
Luego de creada la población inicial se le aplica a cada individuo la función de evaluación
En base al resultado de dicha función se calcula el fitness
Fitness = fi/f
Algoritmo genético Canónico
Una vez calculado el fitness de cada individuo, se pasa a la selección para generar la generación intermedia
Los individuos con mayor nivel de fitness son copiados en la generación intermedia
Stochastic Sampling with Replacement
Remainder Stochastic Sampling
Algoritmo genético Canónico
Crossover
Se eligen pares de individuos randómicamente que serán recombinados con una probabilidad p
Se elige un punto aleatorio del individuo y se intercambian sus partes
Mutación
Es aplicada con una probabilidad muy baja a cada bit
Diferentes variantes
Generar un nuevo bit
Invertir un bit
Algoritmo
Repetir
para cada individuo i evaluar y calcular fitness f(i)
Crear mating pool de tamaño N basado en los valores de fitness f(i)
para i=1 hasta (N/2)
quitar pares de individuos {j,k} del mating pool
recombinar usando los individuos j y k
aplicar mutación
Hasta ‘condición de parada’
Página siguiente  |