5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 1/56

Algoritmos Genéticosy

susAplicaciones

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 2/56

Angel Kuri M.Centro de Investigación en Computación

Instituto Politécnico Nacional

oct. 2000

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 3/56

Computación Evolutiva

1 Computación Evolutiva

» Algoritmos Genéticos2 Aplicaciones

2.1 Optimización Numérica

2.2 Asignación de Segmentos en Basesde Datos Distribuidas

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 4/56

Computación Evolutiva

1. Simulación parcial del proceso de

selección natural

2. No requiere de un modelo matemáticopara atacar un problema dado

3. No alcanza resultados óptimos sino

cercanos al óptimo en poco tiempo

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 5/56

 A lgoritmo Evolut ivo.

1. Generar un conjunto de posibles soluciones

2. Evaluar el desempeño del sistema para cada

individuo.3. Verificar si ya se ha alcanzado algún criterio de

convergencia.

Si: Terminar.

No: Proceder con el paso 4.

4. Seleccionar a los mejores individuos de acuerdo consu evaluación.

5. Modificar a cada uno de los individuos en base a sudesempeño para obtener un nuevo conjunto deposibles soluciones.

6. Proceder con el paso 2.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 6/56

Programa de Ilustración

l El programa que va a ilustrarse forma

parte del libro

l “A Comprehensive Approach to GeneticAlgorithms in Optimization and

Learning”

l El software puede bajarse de148.204.45.189/galsk/ 

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 7/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 8/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 9/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 10/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 11/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 12/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 13/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 14/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 15/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 16/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 17/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 18/56

Ejemplo d e Ap licación

lOptimización de una función conrestricciones

» Función no lineal

» Restricciones no lineales

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 19/56

Representación Numérica

Para representar un conjunto de números

puede emplearse un formato de punto

fijo

En él, cada número consta de signo, una

parte entera y una parte decimal

La codificación suele hacerse con códigoGray

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 20/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 21/56

Una Corrida de Ejemplo

Ejemplificamos el proceso maximizando

la función

sujeto a las siguientes restricciones

)11cos()32(),( y xsin x y x f  −+=

0

0

≥>Π

≥>Π

 y

 x

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 22/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 23/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 24/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 25/56

Algoritmo Genético

Los individuos de la población inicial no

necesariamente satisfacen las

restricciones impuestas por elproblema.

Si ninguna restricción fuese satisfecha, el

fitness sería de “-1000,000,000”; si sesatisficiera una de las restricciones

sería “-75,000,000”, etc.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 26/56

Función de Fitness

40 ≤≤ s

×+−

Π≤≤

Π≤≤−+

=

casootroens

 x

 xsi x xsin x

 x f 

)1025(10 0

0)11cos(32(

)(79 2

1

211r

en donde s es el número de restricciones satis-

fechas y

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 27/56

Algoritmo Genético

Nótese que, como estamos maximizando,

lo que el algoritmo nos “dice” es que

estas propuestas de solución son muymalas.

En la tabla que se ilustra a continuación

aparece el número “-25,000,000” quenos indica que 3 de las 4 restricciones

son satisfechas.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 28/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 29/56

Algoritmo Genético

En la generación 8 aparece el primer

individuo que satisface las 4

restricciones.

Esto induce un fitness aún lejano al

óptimo pero claramente mejor que sus

antecesores.Como el algoritmo es elitista, siempre

conserva al mejor individuo.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 30/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 31/56

Algoritmo Genético

Para la generación 15 la mayoría de lassoluciones propuestas (individuos) arrojan

fitnesses que satisface las restricciones.Nótese que el mejor individuo es

considerablemente mejor que en la tablaanterior y que, a medida que el AG procede,

las soluciones son cada vez más grandes ycercanas al óptimo.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 32/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 33/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 34/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 35/56

Algoritmo Genético

En la siguiente figura puede observarse el

fitness del mejor individuo al final de 50

generaciones.

También se muestra el genoma

correspondiente.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 36/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 37/56

Algoritmo Genético

Ahora queremos interpretar los valores da

cada una de las variables contenidas en

el individuo.

Eso se logra como se muestra en la

siguiente figura.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 38/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 39/56

Algoritmo Genético

Al activar el botón “See Variables”,

podemos ver:

a) El máximo fitness reportado

b) Los valores de las variables

Nótese que los valores:

a) Satisfacen las restricciones

b) Maximizan la función

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 40/56

Algoritmo Genético

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 41/56

Aplicaciones

lSegmentación Automática deBases de Datos Distribuidas

» Segmentación horizontal

» Segmentación vertical

» Segmentación mixta

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 42/56

Bases de Datos Distribuidas

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 43/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 44/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 45/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 46/56

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 47/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 48/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 49/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 50/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 51/56

BDDs

l Ejemplificamos los resultados con un

sistema un poco más complejo que el

señalado en las láminas anteriores

l En lo que sigue, el número de “sites” es

3.

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 52/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 53/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 54/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 55/56

BDDs

5/17/2018 Algoritmos Genticos y Sus Aplicaciones - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-genticos-y-sus-aplicaciones 56/56

Conclusiones

l Los algoritmos genéticos son

herramientas de amplia aplicación

l La metodología puede ser generalizada

l Su programación es fácil