presentacion algortimos geneticos

Algoritmos Genéticos

Integrantes:

•Ericka Moreira•Ma. Gracia León•Mario Plaza•Fabricio Morales

“Impulsando la Sociedaddel Conocimiento”

Junio, 2009

Seminario de Optimizacion

Algoritmos Geneticos 2

Teoría de la evolución

• Charles Darwin, padre de la teoría de la evolución por selección natural.

• Charles Darwin y Alfred Russell Wallace propusieron la selección natural como principal mecanismo de la evolución.

http://www.portalplanetasedna.com.ar/darwin.htm



Teoría de la evolución

• Un investigador de la Universidad de Michigan llamado John Holland estaba consciente de la importancia de la selección natural, y a fines de los 60 desarrollo una técnica que permitió incorporarla en un programa de computadora.

• Los Algoritmos Genéticos (AG) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización.

• Por imitación del proceso natural, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real.

Algoritmos Genéticos

• Cada ejecución del algoritmo puede dar soluciones distintas.

• Son algoritmos de búsquedas múltiples.

• La convergencia del algoritmo es poco sensible a la población inicial si esta se escoge de forma aleatoria y si el tamaño es grande.

Características

Iniciar población

EvaluaciónInicial

Selección

Cross-over

Mutación EvaluaciónSolución final

Condición salida

Algoritmos Genéticos Simples

SI

NO

• Se supone que los individuos son posibles soluciones del problema los cuales agrupados forman una ristra de valores.

• Habitualmente la población inicial se escoge generando ristras al azar, pudiendo contener cada gen uno de los posibles valores del alfabeto con probabilidad uniforme.

Codificación

• La función de adaptación debe ser diseñada para cada problema de manera especifica.

• La regla general para construir una buena función objetivo es que esta debe reflejar el valor del individuo de una manera “real“.

• Existe algunos métodos para establecer primera será la que podríamos denominar absolutista, Función Reparador, penalización de la función objetivo.

Función Objetivo

• Fase de selección reproductiva: Seleccionan los individuos de la población para cruzarse

• La función de selección de padres mas utilizada es la denominada función de selección proporcional a la función objetivo

• Muestreo estocástico con reemplazamiento del resto

• Muestreo universal estocástico

• Métodos de selección dinámicos

• Selección elitista

Selección

• El operador de cruce, coge dos padres seleccionados y corta sus ristras de cromosomas en una posición escogida al azar, para producir dos subristras iníciales y dos subristras finales

Cruzamiento

• El Algoritmo Genético descrito anteriormente, utiliza el cruce basado en un punto.

• También existen cruces basado en múltiples puntos.

Se aplica a cada hijo de manera individual, y consiste en una alteración aleatoria llamada evolución primitiva generalmente constante pero resultados exitosos experimentando al modificar la probabilidad de mutación a medida que aumenta el numero de iteraciones.

Mutación



Ejemplos de Aplicación

Max(f(x)=x^2)x>=0 y x<=31; x es entero

• Codificación:

x

ValorCodificado

0 00000

1 00001

2 00010

3 00011

4 00100

….. …..

28 11100

29 11101

30 11110

31 11111

• Población Inicial:

Individuo Valor x f(x)

1 1 1 1 1 0 30 900

2 1 1 0 1 1 27 729

3 1 0 1 0 1 21 441

4 1 0 1 1 0 22 484

5 1 0 0 0 0 16 256

6 1 0 0 1 1 19 361

Total 3171

• Selección (Método de la Ruleta):

Individuo Probabilidad Salirf(xi)/∑f(xi)

1 28%

2 23%

3 14%

4 15%

5 9%

6 11%

Individuos Escogidos

6

2

1

4

4

5

1 1 0 0 1 1

2 1 1 0 1 1

3 1 1 1 1 0

4 1 0 1 1 0

5 1 0 1 1 0

6 1 0 0 0 0

Población Resultante

• Cruzar (Método 1X):

ParejasPunto de

Cruce

2 1 1 0 1 13

5 1 0 1 1 0

3 1 1 1 1 04

4 1 0 1 1 0

1 1 0 0 1 13

6 1 0 0 0 0

Descendientes

1 1 1 0 1 0

2 1 0 1 1 1

3 1 1 1 1 0

4 1 0 1 1 0

5 1 0 0 0 0

6 1 0 0 1 1

• Mutar:

1 2 3 4 5 Gen a mutar

1 1 0 1 0 2

1 0 1 1 1 4

1 1 1 1 0 3

1 0 1 1 0 2

1 0 0 0 0 5

1 0 0 1 1 1

Población Resultante Valor x f(x)

1 0 0 1 0 18 324

1 0 1 0 1 21 441

1 1 0 1 0 26 676

1 1 1 1 0 30 900

1 0 0 0 1 17 289

0 0 0 1 1 3 9

Óptimo

Travelling Salesman Problem

• Datos:

Distancias entre ciudades

CIUDAD DESTINO

1 2 3 4 5 6

CIUDAD

ORIGEN

1 0 6 2 1 4 10

2 6 0 3 4 3 1

3 2 3 0 2 8 3

4 1 4 2 0 5 6

5 4 3 8 5 0 9

6 10 1 3 6 9 0

Min(Distancia Recorrida)

• Población Inicial:Distancia

Recorrida

Individuo 1 2 3 6 4 1 5 17

Individuo 2 3 1 5 4 6 2 18

Individuo 3 6 5 2 1 4 3 21

Individuo 4 6 1 4 3 2 5 19

Individuo 5 1 4 3 2 5 6 18

Individuo 6 5 4 6 3 2 1 23

• Selección (Método Torneo):

Individuo Pareja

1 3

2 4

5 6

1 2 3 6 4 1 5

2 2 3 6 4 1 5

3 3 1 5 4 6 2

4 3 1 5 4 6 2

5 5 4 6 3 2 1

6 5 4 6 3 2 1

• Cruzar (Operador basado en la alternancia de posiciones):

Individuo Pareja

3 5

4 1

2 6

3 3 1 5 4 6 2

5 1 4 3 2 5 6

4 3 1 5 4 6 2

1 2 3 6 4 1 5

2 2 3 6 4 1 5

6 1 4 3 2 5 6

Descendiente 1 3 1 4 5 6






• Mutar (Operador basado en cambios):

C1 C2

Descendiente 1 3 5

Descendiente 2 2 4

Descendiente 3 5 2

Descendiente 4 3 1

Descendiente 5 4 5

Descendiente 6 2 3

Óptimo

3 1 4 5 2 6

1 3 4 5 2 6

3 2 1 5 6 4

2 3 1 6 5 4

2 1 3 4 6 5

1 2 4 3 6 5

Distancia Recorrida

Descendiente 1 5 1 4 3 2 6 11






Aplicaciones de los Algoritmos Genéticos

Seminario de Optimización

24Algoritmos Genéticos

• Solución de modelos de Inventarios Estocásticos.

• Solución de Problemas de Corte Unidimensional.

• Diseño de redes viales urbanas.

• Optimización de carga de contenedores.

• Planeación y Administración de Recursos en Entidades Académicas.

• Los algoritmos genéticos no necesitan conocimientos específicos sobre el problema que intentan resolver.

• Operan de forma simultánea con varias soluciones.

• Usan operadores probabilístico, en lugar de determinísticos.

Seminario de Optimización

Algoritmos Genéticos 25

Conclusiones

presentacion algortimos geneticos

Education