View
223
Download
0
Category
Preview:
Citation preview
Algoritmos Genéticosy
susAplicaciones
Angel Kuri M.Centro de Investigación en Computación
Instituto Politécnico Nacional
oct. 2000
Computación Evolutiva
1 Computación Evolutiva» Algoritmos Genéticos
2 Aplicaciones2.1 Optimización Numérica
2.2 Asignación de Segmentos en Basesde Datos Distribuidas
Computación Evolutiva
1. Simulación parcial del proceso deselección natural
2. No requiere de un modelo matemáticopara atacar un problema dado
3. No alcanza resultados óptimos sinocercanos al óptimo en poco tiempo
Algoritmo Evolutivo.
1. Generar un conjunto de posibles soluciones2. 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.
Programa de Ilustración
l El programa que va a ilustrarse formaparte del libro
l “A Comprehensive Approach to GeneticAlgorithms in Optimization andLearning”
l El software puede bajarse de148.204.45.189/galsk/
Ejemplo de Aplicación
l Optimización de una función conrestricciones
» Función no lineal» Restricciones no lineales
Representación Numérica
Para representar un conjunto de númerospuede emplearse un formato de puntofijo
En él, cada número consta de signo, unaparte entera y una parte decimal
La codificación suele hacerse con códigoGray
Una Corrida de Ejemplo
Ejemplificamos el proceso maximizandola función
sujeto a las siguientes restricciones
)11cos()32(),( yxsinxyxf −+=
0
0
≥>Π≥>Π
y
x
Algoritmo Genético
Los individuos de la población inicial nonecesariamente satisfacen lasrestricciones impuestas por elproblema.
Si ninguna restricción fuese satisfecha, elfitness sería de “-1000,000,000”; si sesatisficiera una de las restriccionessería “-75,000,000”, etc.
Función de Fitness
40 ≤≤ s
×+−Π≤≤Π≤≤
−+=
casootroensx
xsixxsinx
xf
)1025(100
0)11cos(32(
)(79
2
1211r
en donde s es el número de restricciones satis-fechas y
Algoritmo Genético
Nótese que, como estamos maximizando,lo que el algoritmo nos “dice” es queestas propuestas de solución son muymalas.
En la tabla que se ilustra a continuaciónaparece el número “-25,000,000” quenos indica que 3 de las 4 restriccionesson satisfechas.
Algoritmo Genético
En la generación 8 aparece el primerindividuo que satisface las 4restricciones.
Esto induce un fitness aún lejano alóptimo pero claramente mejor que susantecesores.
Como el algoritmo es elitista, siempreconserva al mejor individuo.
Algoritmo Genético
Para la generación 15 la mayoría de lassoluciones propuestas (individuos) arrojanfitnesses que satisface las restricciones.
Nótese que el mejor individuo esconsiderablemente mejor que en la tablaanterior y que, a medida que el AG procede,las soluciones son cada vez más grandes ycercanas al óptimo.
Algoritmo Genético
En la siguiente figura puede observarse elfitness del mejor individuo al final de 50generaciones.
También se muestra el genomacorrespondiente.
Algoritmo Genético
Ahora queremos interpretar los valores dacada una de las variables contenidas enel individuo.
Eso se logra como se muestra en lasiguiente figura.
Algoritmo Genético
Al activar el botón “See Variables”,podemos ver:a) El máximo fitness reportadob) Los valores de las variables
Nótese que los valores:a) Satisfacen las restriccionesb) Maximizan la función
Algoritmo Genético
Aplicaciones
l Segmentación Automática deBases de Datos Distribuidas
» Segmentación horizontal» Segmentación vertical» Segmentación mixta
Bases de Datos Distribuidas
BDDs
BDDs
BDDs
BDDs
BDDs
BDDs
BDDs
BDDs
l Ejemplificamos los resultados con unsistema un poco más complejo que elseñalado en las láminas anteriores
l En lo que sigue, el número de “sites” es3.
BDDs
BDDs
BDDs
BDDs
Conclusiones
l Los algoritmos genéticos sonherramientas de amplia aplicación
l La metodología puede ser generalizadal Su programación es fácil
Recommended