algoritmos genticos y sus aplicaciones
DESCRIPTION
Algoritmos Genéticos y sus AplicacionesAngel Kuri M. Centro de Investigación en Computación Instituto Politécnico Nacional oct. 2000Computación Evolutiva1 Computación Evolutiva » Algoritmos Genéticos 2 Aplicaciones 2.1 Optimización Numérica 2.2 Asignación de Segmentos en Bases de Datos DistribuidasComputación Evolutiva1. Simulación parcial del proceso de selección natural 2. No requiere de un modelo matemático para atacar un problema dado 3. No alcanza resultados óptimos sino cercanosTRANSCRIPT
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