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