Implementación de LAYAGEN-G
En este capitulo se explicara a detalle como se implemento el algoritmo modificado LAYAGEN-G propuesto primero por Santamarina en [Santamarina 95] y modificado posteriormente para su mayor adaptación a los algoritmos genéticos por José Antonio Diego Mas en [Diego-Mas 06] El análisis se hará parte por parte del software mostrando capturas de pantalla y los mecanismos que se emplearon detrás de la implementación así como su código fuente del componente a tratar(para ver el código fuente completo ver anexo 1)
Captura de los datos
Esta primer pantalla se refiere a la captura de los datos de definición del problema de distribución de planta incluyendo los parámetros del primer paso del algoritmo genético.
En esta segunda pantalla contiene La tabla conocida como de flujo de materiales, con la simetría desactivada ya que muchos autores consideran que no es lo mismo lo que se transporta del departamento i al j que lo del departamento j al i ademas de los coeficientes Relacional y Geométrico.
En esta tercer pantalla se meten los datos referentes a proximidad así como el valor numérico equivalente y el botón que ejecuta el primer paso del algoritmo genético.
Esta pantalla se activara cuando finalice la ejecución del primer paso del algoritmo genético en ella se colocaran todos los parámetros del segundo paso del algoritmo genético. Introducir los datos ya no es necesario ya que serán los mismos que en el primer paso. El fragmento de codigo fuente mostrado a continuación a pesar de ser relativamente largo no posee mucha dificultad su entendimiento ya que solo es tomar lo que tenemos en los controles de formulario antes mencionados y posteriormente cargarlos a variables facilmente manejables y posteriormente a nuestra estructura de árbol que en nuestro caso se llamara codificador pero hablaremos de ella mas adelante.
Podemos corroborar que el código es bastante sencillo de interpretar ya que en esta sección no se implemento nada del código que corresponde al algoritmo LAYAGEN-G
• En la primera parte solo se da una serie de declaraciones de variables publicas, ya que serán utilizadas por otros módulos durante la ejecución del algoritmo posteriormente viene una serie de valores a cargarse desde la apertura del formulario. Estos son conocidos como valores por default pero ya en ejecución del código pueden ser cambiados, solo sirven como una referencia
• En la primer pantalla donde definimos los datos del problema de distribución de planta a resolver cuenta con validaciones con respecto a las áreas de los departamentos que no pueden se mayor que el are del terreno que tenemos además de que debe estar completamente abarcado todo el terreno así que si la suma de nuestras áreas es
menor bastara con dar un doble click en la gradilla para que aparezca un dialogo donde nos pregunta cuantos departamentos son necesarios para redistribuir el área restante, al dar aceptar nuestro valor en el campo actividades abra cambiado bastara con oprimir el botón definir nuevamente ya que es el encargado de cargar los valores de los campos y parámetros del algoritmo en las variables
• Posteriormente en la segunda pantalla se cargan los datos de los flujos al presionar el botón siguiente. La tabla contiene sus respectivas rutinas para poder mostrar y almacenar los datos.
• En la tercer pantalla se hace una lectura de las letras pero antes de pasarlas a la matriz se hace el cambio de las letras por su respectivo valor numérico en este caso si cuenta con simetría la matriz así que solo se llena la diagonal superior y la diagonal inferior se llenara automáticamente.
• Al dar click en ejecutar paso 1 se ejecutara el modulo paso1 que a continuación se mostrara. Debemos verificar que todos los datos fueron colocados en su totalidad ya que no se ha resuelto que avise cuando falten datos y que no comience la ejecución.
La clase Codificador
La clase codificador contiene todas las especificaciones necesarias para la estructura de datos necesaria para poder evaluar el potencial de una codificación especifica al mismo tiempo contiene todos los datos que esta estructura puede proporcionar como son la capacidad del árbol en el primer paso y en el segundo y cambien cuales son sus 2 codificaciones ya que el algoritmo posee dos codificaciones una para el primer paso del algoritmo y una para ejecutar su segundo paso. El mecanismo empleado para generar las dos codificaciones se mostrara así como la estructura del algoritmo en general se mostrara a continuación:
A continuación se muestra el mecanismo de generación de los arboles de cortes y como se codifica al mismo tiempo. En nuestro código en particular el se opto por generar una lista donde cada nodo de la lista es un árbol y se van armando como muestra el siguiente diagrama
Aquí podemos ver de forma general como es que se crearon los arboles a partir de sus respectivos nodos, como lo mencione antes en nuestro caso la caja de donde se extraen los nodos es una lista ligada de arboles Los arboles están descritos en la clase ArbolB y la lista ligada es la clase ListaA
Ahora en cada nodo del árbol contiene información importante tanto con respecto al árbol como de su geometría en el estado actual es decir los cortes que tenga en ese momento aunque cabe destacar que solo se tomara este aspecto hasta el segundo paso ya que en este primer paso encontraremos el árbol cuyo potencial de adyacencia sea el mas pequeño posible lo que quiere decir que dentro del árbol(no en la distribución) cada par de actividades este lo mas cerca posible es por eso que se implementa algo conocido como potencial de adyacencia que es la distancias entre los nodos pasando por la raíz y se define de la siguiente forma.
Donde
• P(i,j) es el potencial de adyacencia entre el nodo i y el nodo j co i={1,2...n};j{1,2,...n}
• s es la distancia de el nodo i a la raíz
• s' es la distancia del nodo j a la raíz
Lo siguiente a tomar en cuenta es de suma importancia para el algoritmo genético y se trata de la función evaluadora que es casi la misma que en [Diego-Mas, 06] pero adaptada solo para el caso particular de nuestra implementación. Dicha función esta compuesta por 2 potenciales el relacional y el geométrico en nuestro caso se implemento el geométrico además del relacional pero el primero no tiene mucho sentido ya que solo se utiliza cuando nuestro terreno inicial es variable, la función evaluadora sera la siguiente para el primer paso :
Donde
• Cg, Cr Son Coeficientes de ponderación
• Pgac y Prac Potencial geométrico y relacional respectivamente
Como se menciono anteriormente el potencial geométrico en el primer paso es irrelevante pero se calcula mediante el mínimo incumplimiento geométrico de las actividades que esta definido de la siguiente forma.
Donde
• li es el incumplimiento geométrico de la actividad i
• αi es el ratio actual de la actividad i
• αimin es el ratio minimo de la actividad i
• a es αimax en caso de que αimax <>
Como mencionamos antes el potencial geométrico es el mínimo incumplimiento de una actividad dependiendo del corte que tenga pero como se menciono anteriormente el autor dice que este valor sera significativo o tendrá coherencia solo cuando el terreno sea variable o no se conozca la forma y se busque que tenga una forma óptima, no obstante el valor del incumplimiento si sera utilizado en el segundo paso ya que en ese caso su significado es para la forma de cada uno de los departamentos y se va tratar de disminuir en lo posible su costo geométrico para que sea factible en relación a los requerimientos de la planta pero departamento a departamento ya con el terreno fijo.
En lo que respecta al potencial relacional este sera definido a continuación
• P(i , j) Es el potencial de adyacencia entre los nodos i , j
• fi, j ,ri,j Flujo de materiales y relaciones de proximidad para las actividades i,j
• α es un coeficiente de ponderación para la importancia entre f (i,j) y r(i,j)
• n numero de actividades
Para poder encontrar los centros geométricos, se requiere que sea una generalización ya que como no siempre da la misma forma (figura) no se puede hacer una forma específica del cálculo, y para esto se trabajó de la siguiente manera: Se utilizó el mismo procedimiento que del autor para interpretar los cortes y hacer la imagen correspondiente. Y de este mismo procedimiento se utilizó para hacer el cálculo de los centros de cada departamento.
En este problema en particular son a lo más rectángulos las figuras que se forman, tomando en cuenta este detalle muy importante y considerando el origen como la parte inferior izquierda de la figura, se requiere de 4 datos muy importantes:
- TA Tope Superior del área disponible
- TD Tope Derecha del área disponible
- A Ancho del rectángulo
- L Largo del rectángulo
Considerando que el algoritmo es recursivo es probable que puede llegar a ser confuso, asi que se utilizará un ejemplo para su más fácil comprensión, consideremos el siguiente árbol y datos:
Considerando que el Largo total y el Ancho total sean de 10 (ya sean metros, centímetros, etc.). Se procede de la siguiente manera:
Procedimiento de manera generalizada:
Se envía la información inicial de TA, TD, A, L, junto con el nodo raíz del árbol. Se revisa el nodo, en el caso de ser corte, se revisa que tipo de corte es, se realizan los reajustes adecuados dependiendo del corte, y se calculan los centros del subárbol izquierdo y del subárbol derecho. Pero si el nodo actual ya es un departamento se hacen los cálculos pertinentes con los datos actuales y se calculan los centros. Para ejemplificar el procedimiento exacto se utilizara el ejemplo anteriormente especificado.
Datos de entrada inicial:
TA = 10 Se considera como 10 dado a que es el ancho disponible es igual al ancho total
TD = 10 Se considera como 10 dado a que es el largo disponible es igual al largo total
A =10 Se considera 10 dado a que es el área total por lo tanto tiene el ancho total
L = 10 Se considera 10 dado a que es el área total por lo tanto tiene el largo total
En la tabla anterior se ve como hace el cálculo del nodo 9 que es particularmente el nodo raíz, pero eso no es relevante, como no es departamento se hace checa que tipo de corte es, en este caso es un corte 3 (Vertical derecha) es decir, toda el área que le corresponde al 8 se va a la derecha del corte, entonces se toma el área que le corresponde a 8 que es 90. Ahora se divide entre el lado que no se va a mover, en este caso el Ancho (A=10) por qué el que va a recibir el corte es a lo largo por ser un corte vertical, y al resultante se tiene que enviar a los siguientes. Por ser el algoritmo recursivo el siguiente a evaluar es el 8.
Ahora en este siguiente paso se debe notar que recibe es el mismo que envía el cálculo del nodo 9, en este paso se repite revisar si es departamento, si no es , se repiten los cálculos, es un corte tipo 2, se revisa el área del hijo izquierdo (en este caso es 40), y se divide entre el lado que no se va a mover que en este caso es el Largo (L=9 en este momento). Nótese que los valores han cambiado ahora se llega a apreciar mejor por que las 4 variables aunque al comienzo se veían similares, los topes superior y a la derecha indican hasta que valor pueden llegar, y así es mas simple calcular los centros, pero volviendo a los cálculos, el resultado da 4.44, y ese calor se debe pasar a los dos nuevos valores a ser calculados, considere que todos los valores que cambian son dados a la resta o al cambio de manera directa del valor obtenido, y por el algoritmo el siguiente a ser evaluado es el nodo 1.
Ahora en este caso el nodo 1 ya no es un corte si no ya es un departamento, en este caso ya solo es calcular el centro geométrico, aquí es donde se mostrará exactamente por qué la necesidad de las 4 variables. El cálculo es relativamente sencillo, al tener el largo y el ancho simplemente se dividen entre 2 para obtener la mitad y por ende el centro geométrico y se le restan estos valores a los topes superior y el tope de la derecha, y así obtenemos los valores X y Y correspondientes. El uso real del tope superior y el tope de la derecha es ubicar el departamento en el área de trabajo, sin tener que hacer cálculos adicionales para encontrarlo. Así ya no tenemos la incertidumbre si está en la esquina o por en medio. Pero regresando a los cálculos, ya hemos llegado al tope izquierdo del árbol, entonces ahora se regresa al nodo 8, pero ahora se calcula su hijo derecho, en este caso el Nodo 7
Ahora con los nuevos valores se vuelven a hacer los cálculos, y se continua hasta terminar todo el árbol, ya con todos los cálculos hechos, así es como quedan los puntos y un aproximado de la forma geométrica de cómo queda la imagen.
Datos obtenidos a partir del algoritmo
Distribución de planta con los datos de la tabla anterior
