Algoritmos genéticos aplicados a la distribución de planta

En este capitulo mencionare algunos de los trabajos ya realizados con respecto a la distribución de planta bajo el uso de algoritmos genéticos sin profundizar mucho en los mecanismos empleados para implementarlo y posteriormente en el siguiente capitulo se mostrara a detalle como se implemento el algoritmo LAYAGEN-G[Diego-Mas 06] en el lenguaje de programación GAMBAS explicando el funcionamiento de cada parte.

La primer propuesta de TAM

Este procedimiento comienza por la determinación del árbol de cortes adecuado al problema. Este árbol sera fijo y empleado a lo largo del resto del proceso.

La creación de la estructura del árbol de cortes se realiza aplicando técnicas numéricas de clustering. Dichas técnicas analizan la afinidad de las actividades evaluando la distancia existente entre ellas y agrupándolas en función de la mencionada distancia.

En este caso la distancia sera una función inversa de la intensidad relacional, es decir la distancia sera menor cuanto mayor sea la intensidad relacional. Tam propone como medida de la distancia entre 2 actividades i , j:

donde wij y wji es el flujo de materiales entre las actividades, con estas distancias es posible formar una matriz de distancias D que representa la distancia entre cada par de actividades

Una vez establecidas las distancias se procede al agrupamiento. Se agrupan inicialmente 2 actividades mas cercanas entre si, tras ello el grupo formado pasa a ser considerado una actividad, recalculándose su distancia a cada una de las actividades restantes y modificando en consecuencia la matriz de distancias. El procedimiento continua agrupando de nuevo aquellas actividades/grupos mas cercanos entre si.

Para un problema de n actividades, deberán realizarse n-1 agrupamientos. El recalculo de las distancias debe hacerse cada vez que se crea un grupo.

La segunda propuesta de TAM

La variación fundamental de esta segunda propuesta con respecto a la primera es la introducción de una codificación de los individuos que permite la búsqueda en todo el espacio de soluciones. Para ello el árbol de cortes y la distribución que genera se codifican mediante una representación pre-orden en 3 partes. La primera parte de la codificación representa la estructura del árbol, la segunda el tipo de corte realizado en los nodos internos y la tercera las actividades que ocupan las hojas del árbol. Es esta codificación de carácter binario, la que sera sometida a los operadores binarios correspondientes. Así la optimización podrá llevarse a cabo mediante el cambio de la estructura del árbol, el cambio de corte en cada nodo y el cambio en las actividades que ocupan cada nodo.

La codificación de la estructura árbol emplea una cadena binaria en la que un 0 representa un nodo interno y un 1 representa una hoja del árbol. La representación, que se realiza recorriendo el árbol de manera pre-orden poseerá siempre las siguientes características:

• el primer elemento de la codificación debe ser un 0 (el correspondiente al nodo raíz) y los 2 últimos 1's;

• el numero total de 0's debe ser igual al numero de actividades menos 1, y el de 1's igual al numero de actividades;

• el numero de 0's existente delante de cualquier posición de la cadena debe ser mayor igual que el de 1's

Así pues, no es necesario representar completamente la cadena puesto que determinados elementos de la misma pueden deducirse de los restantes.

La codificación de los nodos internos se lleva a cabo definiendo el tipo de corte que se llevara a cabo en cada nodo. Un 0 indica un corte vertical y un 1 indica un corte horizontal. Si el corte es horizontal, las actividades que penden de la rama izquierda del nodo, serán colocadas en la parte izquierda del corte. Si el corte es vertical las actividades que penden de la rama izquierda del nodo serán colocadas en la parte superior del corte y en la inferior las restantes.

Por ultimo la codificación de las actividades que ocupan cada hoja del árbol se lleva a cabo realizando permutaciones de la posición de las actividades en las hojas y almacenando en la estructura la secuencia de dichas permutaciones de forma binaria.

El método LAYAGEN de Santamarina

Este método es el que se uso en la implementación informática objetivo de este reporte así que sera explicado con detalle en el siguiente capitulo.

Otras propuestas destacables

La cantidad de bibliografía referente a la aplicación de algoritmos genéticos al problema de la distribución de planta es abundante. Pueden encontrarse variantes en las que se modifica la formulación del problema, la codificación de los individuos, los modelos empleados o los operadores genéticos. A continuación se expone un listado muy breve:

En [Nissen, 94] se aplican los algoritmos genéticos sobre una formulación cuadrática de asignación del problema; en [Corway et al, 94] se usan en la resolución dinámica del problema; en [Tate et al, 95] Se utiliza el modelo de bahías flexibles. Una recopilación de los métodos mas completa puede encontrarse en [Marvidou et al, 97] o en [Islier, 98].