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].

Algoritmos Genéticos

Algoritmos Evolutivos.

Los algoritmos evolutivos son una técnica de resolución de problemas de búsqueda y optimización inspirada en la teoría de la evolución de las especies y de la selección natural[Araujo, 09]. Estos algoritmos reúnen características de búsqueda aleatoria con características de búsqueda dirigida que provienen del mecanismo de selección de los individuos mas adaptados. La unión de ambas características les permite abordar problemas de una manera muy particular, ya que tienen la capacidad para acceder a cualquier regióndel espacio de búsqueda, capacidad de la que carecen otros métodos de búsqueda exhaustiva, a la vez que exploran el espacio de soluciones de una manera mucho mas eficiente que los métodos puramente aleatorios. Indudablemente un algoritmo diseñado de forma especifica para la resolución de un problema concreto será más eficiente que un algoritmo evolutivo, que es una técnica general de resolución. Pero existen muchas situaciones en las que no es posible contar con tales algoritmos, como por ejemplo la complejidad computacional o el tamaño de los problemas que los hace inaccesibles para su solución.

Algoritmos Genéticos

Uno de los tipos de algoritmos evolutivos mas populares son los algoritmos genéticos propuestos por Holland [Holland,75]. Se caracterizar por representar las soluciones al problema que abordan en forma de cadena de bits. Entre las diversas razones que hacen que este tipo de algoritmo suela ser uno de los mas estudiados con mas detalle son su eficiencia y sencillez de implementación. Podemos estudiar a detalle la forma de implementar un algoritmo genético para resolver un problema especifico a partir de su esquema general que a continuación mostraremos.

La ejecución de un algoritmo genético requiere de una serie de parámetros de funcionamiento como por ejemplo el tamaño de la población con la que va a trabajar, que definen su comportamiento en promedio. Una vez que el algoritmo dispone de los valores para estos parámetros comienza generando una población de individuos donde cada uno de ellos es una posible solución del problema tratado.

Posteriormente esa población entra en un ciclo de evolución donde cada ciclo de evolución al que llamaremos generación constara de los siguientes operadores básicos:

• Selección que modifica la composición de la población, eliminando a ciertos individuos y reforzando la presencia de otros

• Reproducción que introduce nuevos individuos y una nueva evaluación que actualiza los datos de la evolución, tales como la adaptación media o la posición del mejor individuo de la población

Representación de los individuos

En un AG los individuos son cadenas binarias que denotaremos por b que representan a puntos x del espacio de búsqueda del problema. Tomando la nomenclatura de la biología a b se le denomina genotipo del individuo y a x se le denomina fenotipo. La nomenclatura biológica a veces se adopta también para otros datos del individuo .

Así se usa gen para referirse a la codificación de una determinada característica del individuo. En los AGs se suele identificar un gen con cada posición de la cadena binaria,aunque esto no tiene por que ser siempre así. Se usa alelo para los distintos valores que puede tomar un gen y locus para referirse a una determinada posición de la cadena binaria.

La sencillez de la representación binaria que utilizan los AGs les aporta características muy importantes de eficiencia. Pero su contrapartida es que requieren cierta lógica para poder codificar-decodificar a cada individuo y su complejidad va a variar dependiendo de l problema a tratar, este paso es necesario para poder evaluar la aptitud de cada individuo.

Es importante que cada posición de la cadena tenga un significado para el problema ya que de esta forma se favorece que los genes den alta calidad a un individuo sigan dando características de calidad en un nuevo individuo obtenido a partir de la la aplicación de un operador genético.

Generación de la población inicial

Los individuos de la población inicial de un AGs suelen ser cadenas de 1's y 0's generadas completamente en forma aleatoria, es decir se va generando un gen con cada función que devuelve un 0 o un 1 con igual probabilidad. En algunos problemas en los que se disponga de información adicional que nos permita saber de antemano que determinadas cadenas tienen mas probabilidades de de llegar a ser solución, podemos favorecer a su generación al crear la población inicial. Sin embargo es imprescindible para el buen funcionamiento del AG dotar a la población de suficiente variedad para poder explorar todas las zonas del espacio de búsqueda.

Grado de adaptación de los individuos

La evolución de la población depende de la calidad relativa de los individuos que compiten por aumentar su presencia en la población y por participar en las operaciones de reproducción. En un problema de búsqueda u optimización dicha calidad se mide por la adecuación o adaptación de cada individuo a se solución del problema. Es frecuente que los problemas se presenten como una función matemática explicita. En dichos casos la función adaptación coincide con la función a optimizar Sin embargo a veces se realizan algunas transformaciones a la función a optimizar o función de evaluación g(x) para transformarla en una función de adaptación adecuada f(x).

Condiciones de Paro

Es necesario especificar las condiciones en las que el algoritmo deja de evolucionar y se presenta la mejor solución encontrada. La condición de terminación mas sencilla es alcanzar determinado numero de generaciones de evolución. Otras condiciones que a veces se utilizan en forma combinada, son alcanzar una determinada calidad o detectar que mayor parte de la población a convergido a una forma similar careciendo de la suficiente diversidad para que tenga sentido continuar con la evolución.

La Selección: Procesos de Muestreo

La población del algoritmo genético se somete a un proceso de selección que debe tender a favorecer la calidad de copias de los individuos mas adaptados. Este proceso se puede realizar de formas muy diferentes en este caso mostraremos solamente 2 de ellas incluyendo la que se utilizara en la implementación informática de LAYAGEN-G

Selección por Ruleta

La probabilidad de selección pi de un individuo i con este método es proporcional a su adaptación relativa

siendo f la adaptación media de la población.

Necesitamos generar un numero aleatorio de acuerdo a la distribución de probabilidad dada por los pi. Si contamos con un generador de números aleatorios que genera números de forma uniformemente distribuida a lo largo de un intervalo como [0,1] podemos seguir el siguiente procedimiento [Perez 96]

Selección por torneo

En la selección por torneo se elige aleatoriamente una pequeña muestra de la población y de ella se selecciona el individuo de mejor valor de adaptación. Normalmente se utiliza un tamaño pequeño para la muestra, de 2 o 3 individuos. El proceso se repite hasta tener el numero de individuos que se desee seleccionar. Esta puede realizarse en forma probabilística o determinista

• En la selección por torneo determinista se selecciona aleatoriamente un numero p de individuos. Habitualmente p toma el valor de 2. Después de entre los individuos seleccionados se elije el mejor, es decir es decir el de mayor valor de adaptación.

• El caso probabilístico es similar, excepto porque una vez seleccionados los p individuos en lugar de escoger siempre el mejor, la selección se realiza con una cierta probabilidad. Si un numero, que se genera aleatoriamente entre 0 y 1, es mayor que un cierto umbral especificado como parámetro del algoritmo, entonces se elige al mejor, en otro caso al peor.

Como se había mencionado anteriormente uno de estos métodos sera implementado en el algoritmo LAYAGEN-G[Diego-Mas 06], El autor nos propone usar el método de ruleta sencillo aunque también da alternativas de mejoramiento del procedimiento pero en nuestro caso solo implementaremos la ruleta sencilla.

Operadores genéticos: Reproducción y Mutación

En cada nueva generación se crean algunos individuos que no estaban presentes en la población anterior. De esta forma el algoritmo genético va accediendo a nuevas regiones del espacio de búsqueda. Los nuevos individuos se crean aplicando ciertos operadores genéticos a individuos de la población anterior. Los operadores suelen estar presentes en todo el algoritmo genético son los operadores de cruce y mutación. El operador cruce combina las propiedades de 2 individuos de la población anterior para crear nuevos individuos. El operador de mutación crea un nuevo individuo realizando algún tipo de alteración usualmente pequeña en algún individuo de la población anterior veamos a continuación la forma mas simple de implementarlos que sera un tanto similar a la que usaremos.

Cruce Monopunto

La forma mas simple del operador de cruce en los algoritmos genéticos es el cruce monopunto. Este consiste en seleccionar al azar una única posición en la cadena de ambos padres e intercambiar las partes de los padres divididas por dicha posición, como muestra la siguiente figura.

Este operador produce 2 hijos que combinan propiedades de ambos padres lo que puede llevar a una mejora de adaptación de los hijos con respecto a los padres.

La forma mas sencilla de mutación que se puede aplicar a un individuo de un algoritmo genético consiste en cambiar el valor de una de las posiciones de la cadena: si es 0 pasa a 1 y si es 1 pasa a 0 como en la siguiente figura.

En muchos casos la mutación produce individuos con peor adaptación que los originales, ya que la mutación puede romper las posibles correlaciones entre genes que se hayan formado con la evolución de la población. Sin embargo contribuyen a mantener la diversidad de la población que es fundamental para el buen funcionamiento de un algoritmo genético..