lunes, 5 de abril de 2010

LAYAGEN-G Paso 1
Ahora después de haber realizado la codificación y decodificación de cada individuo nos queda aplicar el algoritmo genético en si a las codificaciones(recordemos que es la del árbol y la de los cortes ) El primer paso es generar la población inicial de arboles de corte con el sistema de clustering propuesto en [Diego-Mas, 06]

Es un simple procedimiento que crea los objetos Codificador que como mencionamos anteriormente se trata de los individuos, se crean mediante una variable auxiliar y se depositan en un arreglo dinámico de objetos se crean tantos individuos como se haya especificado en la entrada de los datos después se invocan los siguientes métodos con la secuencia que a continuación se muestra.

El método .Carga captura los datos correspondientes al numero de actividades , las áreas, los ratios mínimos y máximos de cada actividad.

El método .Calcula Realiza la función de crear el árbol a partir de los clusters y por lo tanto su codificación y lo guarda en el objeto aux.datos y a la codificacion la coloca en aux.codificacion

Por ultimo el método .potencial_paso1 carga los datos de flujo y coste relacional así como los coeficientes de ponderación geométrica, relacional y de importancia flujo-relacional y calcula la capacidad de cada individuo que es con lo que mayormente trabaja el algoritmo genético, posteriormente solo se añade al arreglo de objetos.

Comenzaremos a explicar después de la generación de la población inicial primero que nada hay que crear una población auxiliar para meter los individuos que se van creando en esta generación así como los que van a sobrevivir, después viene una función encargada de ordenar a los individuos en base a su capacidad calculada mediante el método anteriormente mencionado- posteriormente se encuentra un procedimiento con el nombre de elite encargado de seleccionar al individuo mas apto de la generación actual compararlo con vector elite de tamaño k(la k la puede dar el usuario o dejarla predefinida) el autor comenta que el problema requiere de un valor k constante no muy grande ya que si no el algoritmo llegaría a lo que se conoce como óptimos locales[Diego-Mas, 06] y no se exploraría toda el área de búsqueda así que lo fijamos en 4 y solo se tomara un individuo de la población para ser elite, así pues ya elegido el mejor de la generación que en nuestro caso seria el que tiene un menor costo ya que se trata de minimizar, seria el ultimo elemento del arreglo ya que esta ordenado de mayor a menor al estar lleno el vector elite primero se compara si el mejor de la generación es mejor que el mejor de la elite y si es así se quita el peor de la elite y se introduce el nuevo individuo a la elite y luego a la población auxiliar.

Las siguientes 7 lineas de código son preliminares y necesarias para la selección tanto de los cruzados, mutados y sobrevivientes esto es debido a que el mecanismo de selección que como se menciono en capítulos anteriores es mediante ruleta elige al que tenga mayor capacidad pero la naturaleza del problema hace que se el mejor sea el de menor capacidad por lo tanto hay que hacer una transformación tomando el máximo valor y restándole todos las demás capacidades y represarlo a su propiedad correspondiente es decir:


Después de hacer la transformación de las capacidades tenemos que calcular la probabilidad de cada una de las capacidades de la siguiente forma


después ordenamos las probabilidades en forma descendente ya estando colocadas previamente en un vector de valores reales y calculamos la probabilidad acumulada para ya poder elegir a los individuos


Una vez calculando el vector de probabilidad acumulada nos quedara algo como esto


Suponiendo que fueran 8 individuos luego generamos un numero aleatorio entre 0 y 1 y el individuo sera el que se encuentre en el intervalo es decir

Siendo k el numero generado de forma aleatoria.

Como los individuos se encuentran ordenados de manera descendente bastara con seleccionar el individuo que tenga el mismo índice que la probabilidad elegida este proceso se debe repetir n⋅Pc donde Pc es la probabilidad de cruce pero asegurándonos que el numero de individuos a reproducirse es par.

Este mismo procedimiento sera empleado para seleccionar los individuos que sobreviven y los individuos que van a mutar solo variando que usando el complemento de la probabilidad de cruce y la probabilidad de mutación para los sobrevivientes y mutados respectivamente.

Ahora el proceso de cruce en el primer paso que es la siguiente linea a tratar contiene un problema que es que no todos cruces son factibles por lo que se debe seleccionar primero u punto de cruce factible para lo que se emplea el siguiente mecanismo.

Primero se verifica que sea viable si la parte izquierda de los 2 padres tiene losmismos elementos sin importar el orden

El anterior gráfico muestra dos individuos que su cruce es viable en donde se muestra pero el autor también pide que de preferencia exista también diversidad que se obtiene si los elementos de la izquierda o derecha se encuentran en diferente orden una vez que se haya seleccionado el punto de cruce como viable si tomamos en cuenta el ejemplo de la figura podemos observar que es tanto viable como diverso ya que los elementos poseen un orden diferente previamente elegido el cruce como viable el mecanismo se puede resumir en el siguiente esquema:

Si al analizar todos los posibles cruces para el par de individuos actual ninguno es viable entonces se mandan los padres directamente y se procede con el siguiente par de individuos

Una observación que me gustaría hacer antes de proseguir. Es que el código fuente contiene la siguiente linea

IF seleccion.convergencia(FMain.poblacion) <> 0.0 THEN

Esta linea no realiza los pasos as ta el endif si algo conocido como la convergencia resulta ser 0.0 este aspecto se relaciona en gran medida con el cruce ya que como mencionamos debe existir diversidad y si todos los elementos de la población fueran el mismo al transformarlo y sumarlo daría 0.0 y generaría una división entre 0 al realizar el calculo de la probabilidad, es por eso que si se carece complemente de diversidad se dice que el algoritmo tuvo una convergencia prematura y solo se llega a la ultima iteración de manera automática y se pone como mejor el único individuo que quedo.

Aclarado el punto anterior ahora solo hay que seleccionar los sobrevivientes y los mutados como ya lo habíamos mencionado, solo hay que recordar que los sobrevivientes deben ser.

el -1 corresponde al individuo elite que ya fue agregado a la población auxiliar desde antes y los mutados tendrán que ser n⋅Probde mutacion . una vez seleccionados los individuos que van a mutar entonces se procede con la mutación que es monopunto pero como en el caso del cruce puede que no sea viable es por eso que en el código del codificador se agrego una propiedad que es la viabilidad que verifica si al crear un árbol este sera viable, en este caso no se pueden alterar los genes es decir pasar de una letra a otra por que carecería de lógica, en este caso se realiza un intercambio entre 2 genes y sus posiciones de manera aleatoria y se verifica si fue viable, si no fuera el caso se deshace la mutación y se intenta otra hasta que de un individuo viable. El procedimiento usa la palabra reservada TRY ya que se generara un error cuando un individuo no es viable. Además hay que guardar de algún modo la posición del individuo para saber a donde represarlo en la población una vez concluida la mutación se recalculan las capacidades para que ninguna este transformada y se reasignan a la población original procediendo a la siguiente generación.

LAYAGEN-G Paso 2

Una vez finalizado el primer paso se elige el mejor individuo que surgió en ese paso y se realiza una segunda población inicial pero con parámetros del algoritmo genetico diferentes así como otros parámetros de la distribución de planta adicionales de los que hablaremos mas adelante

La población inicial se genera de la siguiente forma:

• Se crea un nuevo codificador se le manda la codificación del mejor individuo del primer paso y se calcula la capacidad del primer paso

• Se crea un vector de cortes donde los elementos pueden ser pueden ser [0,1,2,3] de manera aleatoria esta sera la codificación del segundo paso y luego se calcula la capacidad del segundo paso con la siguiente formula


dode:

• dij es la distancia entre cada par de actividades

• fij es la carga de transporte entre cada par de actividad

• rij es la necesidad de proximidad

• gc Es el numero de actividades que cumplen las restricciones geométricas

• μi es la rigidez geométrica de la actividad i toma valores entre [0,1]

• li es el incumplimiento formal de la actividad i

• p Coeficiente de penalización geométrica varia de [1,∞)

Todos estos datos son capturados en la ultima pestaña del programa

• Por ultimo se coloca en el vector de población y se inicia el algoritmo genético

En este segundo es casi identifico al primer paso en casi todo solo que aquí hay que considerar la capacidad2 en lugar de la capacidad1 del primer paso ya que siempre sera la misma ya que es la misma codificación del primer paso, los demás cambios que hay que hacer son los siguientes

1. En el cruce no es necesario verificar la viabilidad ni la diversidad por lo que basta con hacer el cruce de manera directa con un k aleatorio.

2. La mutación tampoco requiere de verificación de viabilidad solo se hace de manera directa y esta vez si se cambia uno de los cortes por otro de los existentes diferente al que esta colocado actualmente.

3. En este caso se implemento que se pudiese obtener mas de una distribución de planta así que hay que agregar un ciclo mas que albergue a todo el algoritmo genético y que haga que se repita n veces para obtener n distribuciones de planta. En este caso no colocaremos el código fuente de esta parte pero para consultarlo en el Anexo se encuentran las direcciones de donde puede ser descargado.

Elaboración del diagrama de bloques

Esta parte podría ser opcional pero resulta de suma importancia poder ver de forma gráfica como es que se vería nuestra(s) distribuciones de planta tentativas.

En este caso se utilizaron las ya antes mencionadas equinas superiores izquierdas que se encuentran dentro de los datos de cada individuos y en nuestro caso de los individuos que se consideran los mejores. Se utiliza un objeto que se llama drawingarea y otro que se llama picture dependiendo de donde queremos que se dibuje nuestra distribución de planta, en pantalla o en una imagen. En el caso del drawing area dibujara solo el mejor de las n ejecuciones y el objeto que guarda las imágenes guardara las n distribuciones.

Además de todo lo anterior se implemento el código para generar un reporte con las medidas de los altos y anchos así como flujos, costos geométricos y costos totales para ambos pasos del algoritmo sin olvidarnos de su codificación y cortes.

No hay comentarios:

Publicar un comentario