Embed Size (px)
Citation preview
INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY
CAMPUS ESTADO DE MÉXICO
DISEÑO DE DEPARTAMENTOS DE ÁREA DESIGUAL DADA
UNA FACILIDAD, MEDIANTE ALGORITMOS GENÉTICOS
TESIS QUE PRESENTA
EVA SELENE HERNÁNDEZ GRESS
MAESTRÍA EN INGENIERÍA INDUSTRIAL MII95
SEPTIEMBRE, 2005
INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY CAMPUS ESTADO DE MÉXICO
DISEÑO DE DEPARTAMENTOS DE ÁREA DESIGUAL DADA UNA FACILIDAD, MEDIANTE ALGORITMOS GENÉTICOS
TESIS QUE PARA OBTENER EL GRADO DE MAESTRA EN CIENCIAS EN INGENIERÍA INDUSTRIAL
PRESENTA
EVA SELENE HERNÁNDEZ GRESS
Asesor: Dr. Eduardo Díaz Santillán Dr. Jaime Mora Vargas
Comité de tesis: Dr. César Martínez Olvera
Dr. Manuel Álvarez Madrigal Dr. Humberto Vaquera Huerta
Jurado: Dr. César Martínez Olvera Presidente
Dr. Manuel Álvarez Madrigal Secretario Dr. Humberto Vaquera Huerta Vocal
Atizapán de Zaragoza, Edo. de Mex., Septiembre de 2005.
Índice 1. Introducción……………………………...………………………………………
01
2. Marco Teórico 03
2.1 Distribución de Departamentos................................................................. 03
2.1.1 Manejo de Materiales...................................................................... 04
2.1.2 Tipos de configuraciones en una empresa productiva……………. 04
2.2 Investigación Bibliográfica....................................................................... 07
2.2.1 Tipos de Modelos............................................................................ 07
2.2.1.1 Modelo de Asignación Cuadrático....................................... 07
2.2.1.2 Modelo de Cobertura Cuadrática......................................... 10
2.2.1.3 Programación Lineal Entera................................................. 11
2.2.1.4 Programación Entera Mixta................................................. 13
2.2.1.5 Formulaciones de Teoría de Grafos..................................... 15
2.3 Complejidad Computacional.................................................................... 16
2.3.1 Algoritmos Óptimos......................................................................... 16
2.3.1.1 Algoritmos de Ramificación y Acotamiento........................ 17
2.3.1.2 Algoritmos de Plano de Corte.............................................. 18
2.3.2 Algoritmos Subóptimos................................................................... 18
2.3.2.1 Algoritmos de Construcción................................................. 21
2.3.2.2 Algoritmos de Mejora........................................................... 23
2.3.2.3 Algoritmos Híbridos............................................................. 26
2.3.2.4 Algoritmos de Teoría de Grafos............................................ 27
2.4 Métodos Heurísticos................................................................................ 28
2.4.1 Problemas NP-Completos................................................................ 28
2.4.1.1 Definición Formal.................................................................. 32
2.4.2 Tipos de Heurísticos......................................................................... 33
2.4.3 Algoritmos Genéticos....................................................................... 34
2.4.3.1 Funcionamiento..................................................................... 35
2.4.5 Recocido Simulado......................................................................... 38
2.5 Distribución de Departamentos por Métodos Heurísticos...................... 41
2.5.1 Recocido Simulado......................................................................... 42
2.5.1.1 Células de Manufactura mediante Recocido Simulado........ 42
2.5.1.2 CLASS: Soluciones computarizadas.................................... 43
2.5.1.3 Recocido Simulado para departamentos con maquinaria..... 44
2.5.2 Algoritmos Genéticos 47
2.5.2.1 Distribución de departamentos de área desigual.................. 47
2.5.2..2 Diseño integrado de departamentos usando un enfoque ... 48
2.6 Objetivos.................................................................................................. 53
3. Planteamiento del Problema.............................................................. 54
3.1 Modelo Genérico..................................................................................... 56
3.2 Búsqueda de las variables binarias mediante Algoritmos Genéticos...... 62
4. Análisis y Discusión de Resultados............................................................. 66
4.1 Experimentos para colocar parámetros de Algoritmos Genéticos……... 66
4.1.1 Torneo………………………………………………………... 67
4.1.2 Cruza…………………………………………………………. 74
4.1.3 Mutación……………………………………………………... 78
4.2 Búsqueda Local con Recocido Simulado………………………………. 84
4.3 Resultados……………………………………………………………… 96
5. Conclusiones y Trabajo Futuro............................................................................... 98
6. Bibliografía............................................................................................................. 100
2
el sabio en su sabiduría, ni en su valentía se alabe el valiente, ni el
rico se alabe en sus riquezas.
Más alábese en esto el que se hubiere de alabar: en entenderme
y conocerme, que soy Jehová, que hago misericordia, juicio y
justicia en la tierra; porque estas cosas quiero, dice Jehová.
Jeremías 9:23-24
3
1
1.Introducción Los problemas de optimización combinatoria, los cuales están caracterizados por un número finito, aunque muy extenso de soluciones factibles se presentan en la vida diaria, particularmente en la ingeniería. Una importante área de aplicaciones de los problemas de optimización combinatoria, se refiere al uso eficiente de los recursos para incrementar la productividad. A pesar de que en principio, la solución óptima puede ser encontrada por enumeración de todas las posibles soluciones; en la práctica esto es frecuentemente imposible, especialmente para problemas prácticos de tamaño real, donde el número de soluciones factibles es extremadamente grande (explosión combinatoria). Entre los retos más importantes de este tipo de problemas se encuentra el tratar efectivamente con la explosión combinatoria. Una forma de resolver este tipo de problemas, es el uso de los Algoritmos Genéticos, una técnica metaheurística inspirada en la evolución natural. Desde 1960 ha habido un interés en imitar la evolución y desarrollo de los seres vivos al desarrollar algoritmos poderosos para resolver problemas difíciles de optimización. El término para referirse a este tipo de técnicas es computación evolutiva, las mejores técnicas en esta clase incluyen a los algoritmos genéticos desarrollados por Holland, las estrategias de evolución por Recehenberg y Schwefel, programación evolutiva creada por Fogel y programación genética desarollada por Koza [43]. Los algoritmos genéticos como una técnica poderosa y aplicable en varios campos, es la más conocida. En los últimos años los algoritmos genéticos han sido un tema de atención para resolver problemas de optimización en ingeniería industrial que pueden ser aplicados en situaciones reales en las empresas. Un problema de ingeniería industrial es la distribución de departamentos dentro de un área definida, generalmente de forma rectangular. Una planta puede ser vista como un número finito de áreas geométricas acomodadas en el edificio, lo importante es distribuir estos departamentos para minimizar el flujo de personas, información, materiales, productos, etc. Particularmente este proyecto de tesis se centra en la distribución de departamentos rectangulares de área desigual, y se refiere a encontrar el arreglo más eficiente dentro de un espacio determinado. El objetivo de este diseño es minimizar los costos asociados de las interacciones entre los departamentos, en este caso los costos de manejo de materiales; aunque podría referirse a cualquier puntaje de adyacencia entre ellos. En los últimos años se ha estado trabajando para resolver el problema distribución de departamentos de forma directa, muchos de estos modelos utilizan optimización lineal, por la facilidad que implica su solución en paquetes computacionales. Castillo [12] logró un modelo de programación entera que encuentra soluciones óptimas con un grado de error entre el .1 y el 10% para problemas de menos de 10 departamentos; esto debido a que la cantidad de variables binarias aumenta de forma exponencial con respecto al número de departamentos; por lo que no es posible encontrar el óptimo global en un tiempo razonable de computo. El objetivo del presente trabajo es manejar estas variables binarias mediante Algoritmos Genéticos, ya que si éstas variables tienen valores fijos, se reduce la complejidad del problema; pudiendo ser esta la puerta de entrada a resolver problemas reales de más departamentos. El capítulo 2 comprende el marco teórico, la justificación del problema; además del estado del arte, una revisión de los tipos de modelos, también se hace una breve descripción de los algoritmos que surgieron debido a la complejidad computacional; por último se revisan algunas
2
técnicas actuales, todo para observar los alcances de los distintos métodos que se han utilizado en este problema. El capítulo 3 esta dedicado al planteamiento del problema y la aportación del trabajo de tesis, aquí se presenta el modelo utilizado para su solución; además de detallar el tipo de Algoritmo Genético utilizado para encontrar las variables binarias. La experimentación y análisis de resultados se muestran en el capítulo 4, para esto se utiliza un problema específico que será detallado más adelante. Por último en el apartado 5 se muestran las conclusiones y el trabajo futuro.
3
2.Marco Teórico 2.1 Distribución de Departamentos Una planta de manufactura típica tiene diversas actividades interactuando unas con otras. Las materias primas llegan a recepción, para ser desempacadas y revisadas en el área de control de calidad, después son procesadas en distintas áreas, para finalmente llevar el producto final al área de embarque. Adicionalmente, se cuenta con otras áreas como vestidores, comedor, oficinas de administración, diseño de productos y control de la producción, espacio para inventarios y pasillos, etc. De hecho, una planta puede ser vista como un número finito de áreas geométricas acomodadas en el edificio. El problema radica en distribuir estos departamentos de tal manera que el flujo de materiales, personas, información, etc. puedan llegar al lugar correcto en el momento apropiado, esto se conoce como problema de distribución de departamentos.
Figura 2.1 Flujo entre departamentos, Paul A. Jensen, Departamento de Ingeniería
Industrial, Universidad de Texas, 2004 Claramente, este problema tiene relevancia en muchas áreas del diseño arquitectónico, no sólo en departamentos de empresas, sino también en el acomodo de habitaciones en una casa o la configuración de circuitos electrónicos (Jensen, 2004), asimismo, se ha usado en algunas otras instalaciones como aeropuertos, oficinas, centros deportivos, estaciones de policía. En los hospitales se ha implementado esta técnica para reducir el esfuerzo de las enfermeras al trasladarse de un lugar a otro. A pesar de las diferentes aplicaciones del problema, esta investigación se enfoca a la distribución de los departamentos en las industrias. Desde este punto de vista, el ingeniero de diseño analiza, conceptualiza, diseña e implementa sistemas para la producción de bienes o servicios. Este diseño es usualmente representado como distribución de planta, o arreglo de departamentos. Lo que se pretende en la mayoría de las empresas es optimizar la interrelación entre el personal operativo, flujo de información y los métodos requeridos para alcanzar los objetivos de la misma de forma eficiente, económica y segura. Cuando se habla de recursos necesarios es obligado hablar de costos; no sirve de mucho tener estos recursos cuando los costos se incrementan de tal forma que no te permiten situar el producto a un precio competitivo en el mercado. Una vez que se contempla la distribución de departamentos, es necesario identificar los costos más relevantes de acuerdo al Principio de Pareto, el cual nos dice que la mayor parte de los costos son generados por una misma causa,
4
pudiendo ser mano de obra, materiales, etc. Los costos más representativos son los que primero se deben minimizar, en este caso hablando del acomodo de departamentos son los de manejo de materiales ya que comprenden entre el 30 y 75% de los costos totales de producción [10]. 2.1.1 Manejo de Materiales
Existe una fuerte relación entre el diseño de los departamentos en la planta y la función de manejo de materiales. Siempre que se considera la planeación de los departamentos debe considerarse el manejo de materiales [48]. El manejo de materiales ocupa el 25% de los empleados, 55% del espacio de la fábrica, 87% del tiempo de producción y 15-70% de los costos totales el producto manufacturado, es por ello que hacerlo de la forma correcta puede traer reducciones en costo y mejoramiento de la calidad. El manejo de materiales es el arte y ciencia de mover, almacenar, proteger y controlar el material. Material son unidades en forma sólida líquida o gas, también pueden ser información. Manejar los materiales significa proveer la cantidad correcta de material en la condición apropiada, en el tiempo y la posición adecuada para tener el mejor costo usando los mejores métodos. Existen varios equipos para transportar el material, algunos de ellos son bandas, vehículos industriales tanto los de mano como los dirigidos por computadora, monorrieles, etc., sin embargo, aunque el costo que éstos implican será diferente siempre tendrá que ver con la distancia recorrida. Es decir el costo de manejo de materiales será entendido como el costo de mover una unidad de carga de un lugar a otro multiplicado por la distancia. La importancia del diseño de departamentos para hacer más eficiente la operación de una empresa no puede ser subestimada. Debe reconocerse que el flujo de materiales usualmente representa la estructura de una entidad productiva y no se debe permitir que las distintas áreas ocasionen confusión y tráfico. La importancia del diseño de departamentos puede ser resumido como sigue:
1. Una planta eficiente en el flujo de material es un requisito indispensable para la producción económica.
2. El flujo de material en forma eficiente nos habla de un arreglo efectivo de departamentos físicos.
3. El manejo de materiales convierte el flujo estático en una realidad dinámica, dando significado a qué material le es permitido o no moverse.
4. El arreglo efectivo de departamentos alrededor del flujo de materiales resulta en operaciones eficientes de varios procesos relacionados.
5. Una operación eficiente de los procesos resulta en costos de producción mínimos.
2.1.2 Tipos de configuraciones en una empresa productiva Existen cuatro tipos de configuraciones para departamentos:
1) Departamentos con la localización del material fijo. 2) Departamentos con producción en línea 3) Departamentos según familias de productos 4) Departamentos según proceso
5
La siguiente figura ilustra el flujo de material en cada caso:
(a)
(b)
(c)
(c)
A L M A C É N
D E
M. P.
torno taladro cubierta
torno torno
torno
pintura
torno ensamble
torno
pintura
cubierta
molino
molino molino
molino
ensamble
A L M A C É N
D E
P. T.
taladro
A L M A C É N
D E
M. P.
torno taladro moldeo torno
prensa molde torno
molino
torno torno taladro
EN S A M BLE
A L M A C É N
D E
P. T.
taladro
A L M A C É N
D E
M. P.
torno taladro moldeo
cubierta pintura ensamble
A L M A C É N
D E
P. T.
6
(d) Figura 2.2 Tipos de configuraciones de departamentos a) línea de producción, b) localización fija de material, c) por familia de productos y d) por proceso. La configuración con localización fija de material difiere en concepto de las otras tres. Con las otras, el material es traído a la estación de trabajo; en el caso de localización fija las estaciones son traídas al material. Ésta es usada en ensamble de aviones, construcción de barcos, etc. Los departamentos de producción en línea están basados en la secuencia de operaciones que debe tener el producto. Los materiales fluyen de una estación a al otra que está adyacente, y estas configuraciones se conocen como “por producto”. La configuración para familias de productos como su nombre lo indica está basada en agrupar artículos en clases. Partes no necesariamente idénticas se agrupan en un mismo espacio de trabajo basado en secuencias de proceso idénticas, formas, composición de material, etc. En este caso, cada familia es tratada como un seudo producto y una distribución menor es desarrollada. Todas las herramientas necesarias para realizar este producto son puestas en una celda de manufactura, es por esto que existen grandes flujos intradepartamentales y menores interdepartamentales. Los departamentos acomodados por proceso se sitúan en la configuración dependiendo de flujo entre los distintos procesos. En este caso existe gran flujo interdepartamental y poco intradepartamental. Este tipo de configuración se justifica cuando la actividad de partes individuales o por grupo no es lo suficientemente grande para hacer una distribución por producto o por familia. De no ser por la configuración de localización fija, cualquiera de las otras tiene áreas rectangulares de áreas iguales o similares; es por ello que el problema de situarlos para optimizar costos sigue siento relevante, incluso cuando son de pocos departamentos, pues las configuraciones totales se dividen a su vez en seudo configuraciones como almacenes, área de proceso, proceso por artículo, etc. Sí consideramos los almacenes podemos establecer que esta área juega un rol muy importante y asegura que la cadena de suministro esté funcionando de forma exitosa [48]. La misión del almacén es preservar el producto y de llevarlo a las áreas siguientes, independientemente de cuál
A L M A C É N
D E
M. P.
torno moldeo torno
molino ensamble
cubierta
prensa
cubierta taladro ensamble
pintura
torno taladro
torno cubierta
prensa ensamble
taladro
A L M A C É N
D E
P. T.
7
sea la configuración, sin cambiar la forma básica del material. Son necesarios varios pasos, esto justifica el ocupar métodos que aseguren cumplir con la misión de forma óptima. El almacén puede ser considerado como una seudo configuración, entre las áreas mas importantes se encuentran:
• Recepción: es aquí donde ser recibe orden de materiales asegurándose que la cantidad y calidad de éstos sea la correcta.
• Inspección y control de calidad: Se revisan las materias primas para asegurar que cumplan con los requerimientos necesarios.
• Reempaque: Cuando los materiales vienen en bultos grandes, se separan y/o combinan para ser repartidos a el área de producción.
• Almacén: Aquí se guardan las mercancías que no serán utilizadas de forma inmediata, también aquí se liberan estas mercancías cuando se demandan.
Cada una de ellas demandan un conjunto de actividades que deben ser elaboradas en alguna área física del almacén; entre ellas existe flujo de materiales o de información (órdenes) lo cual tiene un costo; por lo que hacer una distribución óptima de áreas es valioso tanto en costos como para hacer más eficiente la operación. 2. 2 INVESTIGACIÓN BIBLIOGRÁFICA 2.2.1 Tipos de Modelos Diferentes métodos para distribuir departamentos han sido ampliamente abordados desde 1950 en diferentes artículos. Tal y como lo describen Kusiak y Heragu[28], la distribución de departamentos en una planta ha sido estudiado como un problema de asignación cuadrático y de cobertura, un problema de programación lineal, entera mixta y de grafos. Los algoritmos que a continuación se describen han sido probados para 8 tipos de configuraciones con 5, 6, 7, 8, 12, 15, 20, 30 departamentos, sin embargo estos departamentos han sido de áreas iguales, excepto el CRAFT de Armour y Buffa [2] en donde se logró resolver un problema con 20 de área desigual. 2.2.1.1 Modelo de Asignación Cuadrático Koopmasn y Beckman [27] fueron los primeros en modelar la localización de departamentos con flujo de material entre ellas. Ellos lo formularon como un problema de asignación cuadrático, éste nombre le fue dado porque la función objetivo era de segundo grado con respecto a las variables pero las restricciones eran lineales. Se usó por primera vez la siguiente notación: n - número total de departamentos/ localizaciones. aij – ganancia neta del departamento i a la localización j. fik – flujo de material de del departamento i al k. cjl - costo de transportar una unidad de material del departamento j al l. xij = 1, sí el departamento i está en la localización j, 0 de otra manera. Koopmans y Beckman asumieron que aij no incluía el costo de transportación entre departamentos, fik es independiente de las localizaciones de los departamentos y cjl es independiente de los departamentos, es más barato transportar material directamente del departamento i al k, que desde una tercera localización.
8
El problema QAP queda entonces:
{ } )4(,....,2,1,,1,0
)3(,....,2,1,1
)2(,....,2,1,1..
)1(
1
1
1 1 1 1
1 1
njix
njx
nixas
xxcf
xaMax
ij
n
iij
n
jij
klijjl
n
i
n
j
n
k
n
lik
ij
n
i
n
jij
=∈
==
==
−
�
�
����
��
=
=
= = = =
= =
Sin embargo, sí aij es el costo de localizar y operar el departamento i en la localización j, en lugar de la ganancia neta, el problema es transformado en:
)5(1 1 1 1
1 1
klijjl
n
i
n
j
n
k
n
lik
ij
n
i
n
jij
xxcf
xaMin
����
��
= = = =
= =
+
Las variables son redefinidas como: aij – costo fijo de localizar el departamento i en la localización j. fik – flujo de material entre el departamento i y el k. cjl - costo de transportar una unidad de material de la localización j a la l. Lawler [30] introdujo el cambio bikjl, donde bikjl es el resultado de multiplicar el flujo de material entre el departamento i y el k por el costo de transportar una unidad de material de la localización j a l. Se le suma el costo fijo de la localizar el departamento i en la localización j cuando el departamento i y el k es el mismo. La función objetivo también fue redefinida como:
)6(1 1 1 1����
= = = =
n
i
n
j
n
k
n
lklijijkl xxbMin
En la formulación pasada i�k implica que j�l , j�l implica i�k, i=k implica que j=l y j=l implica que i=k , en las restricciones (2) y (3). En este problema se asume que el número de departamentos a colocar es igual al número de localizaciones. Sin embargo, para algunos problemas como el propuesto por Steinberg [28] el número de departamentos es menor que el de
� � �
� � �
�
� �
= = + =
, 1
, 1
jy k i si c f
j y k i si a c f b
jl ik
ij jl ik ijkl
9
localizaciones, este problema pudo ser formulado como uno de asignación cuadrático, introduciendo departamentos ficticios 1, 2, 3,….n-m y considerando los flujos entre éstas y las existentes igual a cero. Sí las aij’s son iguales a cero o idénticas, la función objetivo (1a) se reduce a:
)7(1 1 1 1����
= = = =
n
i
n
j
n
k
n
lklijjlik xxcfMin
Dos casos especiales del problema de asignación cuadrática con la función objetivo (7) y las restricciones (2)- (4) son considerados:
• Problema de asignación lineal: Sucede sí las fik ‘s son iguales a cero o son idénticas, de esta forma la función objetivo se reduce a:
)8(1 1
ij
n
i
n
jij xaMin ��
= =
las restricciones (2)- (4) son lineales. • Problema de Agente Viajero: Las ecuaciones (2)-(4) implican que las xij‘s se representan
en forma matricial, la matriz resultante X=[xij] pueden ser una matriz de permutación, en donde cada columna y cada fila tendrá un sola entrada, llamada 1. El problema del agente viajero puede ser formulado con la función objetivo (8) y las restricciones (2)-(4), además de la matriz de permutación cíclica.
El problema de Asignación Cuadrática (5) , (2)-(4) ha sido usado frecuentemente para modelar la distribución de departamentos, pero esto no significa que todos los problemas puedan ser abordados desde este punto de vista, por ejemplo, en problema de asignación de máquinas dentro de una planta, en donde las localizaciones no son conocidas de forma inicial. Este problema no puede ser resuelto con esta formulación, debido a que las distancias entre las localizaciones no pueden ser determinadas. La distancia djl entre las localizaciones j y l depende del acomodo de las otras máquinas. Esto no pasa en problemas donde los departamentos son de tamaño igual, de esta forma las localizaciones son de la misma área, por lo tanto, la distancia entre ellas es independiente de los departamentos asignados a ellas; djl no cambia entre un arreglo y otro. No obstante, este problema es difícil de encontrar en la realidad, los departamentos son de áreas diferentes y la distancia entre las localizaciones depende de los departamentos asignados a ellas, este es conocido como problema general. Existen dos formulaciones para el problema general. La primera es:
{ } )4(,....,2,1,,1,0
)3(,....,2,1,1
)2(,....,2,1,1..
)9(
1
1
1 1 1 1
njix
njx
nixas
xxcfMin
ij
n
iij
n
jij
klijk
jl
n
i
n
j
n
k
n
lik
=∈
==
==
�
�
����
=
=
= = = =
10
Donde cjlk es el costo de transportar una unidad de material desde la localización j a la l bajo el
arreglo de departamentos k. El rango de k son todos los arreglos de departamentos potenciales, así como lo establecen Armour y Buffa [2], este número depende de las áreas de los departamentos y no necesariamente es n!, esto es por 2 o más arreglos son simétricos. 2.2.1.2 Modelo de Cobertura Cuadrática (Set Covering) La segunda formulación para el problema general de distribución de departamentos es el de cobertura cuadrática propuesto por Bazaara [3]. En esta formulación, el área total ocupada por los departamentos es dividida en un número de bloques. La siguiente notación es utilizada: q - es el número de bloques en los que el área total ocupada por los departamentos es
dividida. I(j) - número potencial de localizaciones para el departamento i. Ji(j) - conjunto de bloques ocupados por el departamento i, sí es asignado a la localización j. d(ji, lk) - distancia entre los centroides de las localizaciones j y l, sí el departamento i es asignado a localización j y el k es asignado a la localización l. xij = 1 sí el departamento i es asignado a la localización j, 0 de otra manera. Pijt = 1 sí el bloque t � Ji(j), 0 de otra manera. La formulación es:
{ }
)(,....,2,1
)13(,....,2,1,1,0
)12(,....,2,1,1
)11(,....,2,1,1..
)10(),(
)(
11
)(
1
1
)(
1 1
)(
1
1
)(
1
iIj
nix
qtxp
nixas
xxljdf
xaMin
ij
iI
jijijt
n
i
iI
jij
klijki
n
i
iI
j
n
k
kI
lik
ij
n
i
iI
jij
=
=∈
=≤
==
+
��
�
����
��
==
=
= = = =
= =
La restricción (11) asegura que cada departamento es asignado a una sola localización y la (12) asegura que cada bloque es ocupado en la mayoría por un solo departamento. Puesto que la distancia es tomada desde los centroides (el punto justo a la mitad del ancho y el largo) de las localizaciones, Bazaara propone una medida alternativa para el flujo entre departamentos:
kiikik ssff /'= Donde si es el número de bloques ocupado por la departamento i y d’jl es la distancia entre los bloques j y l. Usando la medida anterior, se obtiene:
11
{ }
qj
nix
qjx
nisxas
ssxxdf
xaMin
ij
n
iij
q
jij
kiklijjl
n
i
q
j
n
k
q
lik
ij
n
i
q
jij
,....,2,1
)17(,....,2,1,1,0
)16(,....,2,1,1
)15(,....,2,1,..
)14(/'
1
11
1 1 1 1
1 1
=
=∈
=≤
==
+
�
�
����
��
=
=
= = = =
= =
Esta formulación puede ser utilizada para resolver el problema de departamentos de área desigual, pero tiene la desventaja, de que el tamaño del problema aumenta exponencialmente, cuando el área total ocupada es dividida en bloques cada vez más pequeños. Hillier y Connors [28], sugirieron resolver este tipo de problemas partiendo el área de cada departamento en subdepartamentos de área similar, pero resulta complicado. 2.2.1.3 Programación Lineal Entera Lawler [30] fue el primero en formular el problema de distribución de departamentos como de programación lineal entera, definiendo: xij = 1 sí el departamento i es asignado a la localización j, 0 de otra manera. xil = 1 sí el departamento i es asignado a la localización l, 0 de otra manera.
)18(ilijijkl xxy ⋅=
El problema de asignación cuadrático (6), (2)-(4) puede ser representado como uno lineal:
12
{ }
{ } )22(,....,2,1,,,,1,0
)4(,....,2,1,,1,0
)21(,,...,2,1,,,
,02
)20(
)3(,....,2,1,1
)2(,....,2,1,1..
)19(
2
1 1 1 1
1
1
1 1 1 1
nlkjiy
njix
nlkji
yxx
ny
njx
nixas
ybMin
ijkl
ij
ijklklij
n
i
n
j
n
k
n
lijkl
n
iij
n
jij
ijkl
n
i
n
j
n
k
n
lijkl
=∈
=∈
=
≥−+
=
==
==
����
�
�
����
= = = =
=
=
= = = =
Lawler demostró que la formulación anterior y el problema cuadrático de asignación son equivalentes. Este último tiene n2 del tipo de variables xij y 2n restricciones, mientras que el programa de programación entera tiene n2 variables xij, n4 variables yijkl y n4+2n +1 restricciones. Love and Wong [28] propusieron una formulación lineal entera simple en donde:
i) las localizaciones son dadas como puntos en un plano bidimensional. ii) los costos de transportación son proporcionales a las distancias rectangulares.
Sí
=ikrh
=iklh
=ikav
),( ii yx−−
localización del departamento i
Distancia horizontal entre los departamentos i y k cuando el i está a la derecha de k, 0 de otra manera,
Distancia horizontal entre los departamentos i y k cuando el i está a la izquierda de k, 0 de otra manera,
Distancia vertical entre los departamentos i y k cuando el departamento i está arriba de k, 0 de otra manera,
Distancia vertical entre los departamentos i y k cuando el departamento i está abajo de k, 0 de otra manera,
=ikbv
13
=ijx
La formulación es:
)27(;,....,2,1,)(
)26(;,....,2,1,)(
)25(1;,....,2,1
)24(1;,....,2,1..
)23()(
__
1
__
__
1
__
__
__
1
1
1
1
1 1
nixyxyx
nixyxyx
ikniyyvv
iknixxhhas
vvhhf
xaMin
ijjj
n
jii
ijjj
n
jii
kiblik
aik
kil
ikr
ik
bik
aik
lik
rik
n
i
n
ikik
n
i
n
jijij
=−=−
=+=+
+==−=−
+==−=−
+++
+
�
�
��
��
=
=
−
=
−
+=
= =
{ }
)29(;,....,2,1,0,
,1;,....,2,1
)28(0,,,
)4(,...,2,1,,1,0
)3(;,....,2,1,1
)2(;,....,2,1,1
1
1
niyx
ikni
vvhh
njix
njx
nix
ii
bik
aik
lik
rik
ij
n
jij
n
jij
=≥
+==
≥
=∈
==
==
−−
=
=
�
�
De lo anterior se deduce que las localizaciones de los departamentos están especificadas por las coordenadas rectangulares. Las restricciones (26) y (27) especifican la localización del departamento, todo en conjunto tienen n2 variables enteras y n2+3n restricciones. Esta formulación sólo puedo resolver problemas de ocho o menos departamentos de área desigual. 2.2.1.4 Programación Entera Mixta Kaufman y Broeckx [25] desarrollaron un programa de programación entera mixta, que tenía el menor número de variables y restricciones. Ellos definieron:
1 si el departamento i es asignado a la localización j 0 de otra manera
14
)31(
)30(
1 1
1 1
��
��
= =
= =
=
=
n
k
n
lijklij
kl
n
k
n
lijklijij
be
xbxw
{ } )4(,....,2,1,,1,0
)34(,....,2,1,0
)33(
)3(,....,2,1,1
)2(,....,2,1,1..
)32(
)(
)19(
1 1
1
1
1 1
1 1 1 1
1 1 1 1
njix
njiw
ewxbxe
njx
nixas
w
xbx
xxbMin
ij
ij
ijijkl
n
k
n
lijklijij
n
iij
n
jij
n
k
n
lij
n
i
n
jkl
n
k
n
lijklij
klij
n
i
n
j
n
k
n
lijkl
=∈
=≥
≤−+
==
==
=
=
��
�
�
��
�� ��
����
= =
=
=
= =
= = = =
= = = =
La equivalencia de la formulación anterior y el problema de asignación cuadrática fue probada por ellos mismos con la ayuda de Burkard [7]. Este modelo contiene n2 variables binarias, n2
variables continuas y n2+2n restricciones. Otros modelos equivalentes de programación entera fueron desarrollados por Balas y Mazzola, Bazaara y Sherali, Burkard y Bonninger [8] y Frieze y Yadegar, también en la misma fecha. Bazaara y Sherali definieron [5]:
[ ]
.,,...,2,1,
,...,1
1,...,2,1'
,)1/(
jlnjl
nik
niparaxxy
dfdfmaag
klijijkl
ljkijlikklijijkl
≠=
+=
−==
++−+=
ijkly' siempre tomará valores de 0 ó 1 , en este caso hay dos departamentos contemplados el i y el k que deben ser asignados a dos localizaciones diferentes j y l que deben ser diferentes; el departamento k es el sucesivo de i , es decir si i=1, k=2.
ijklg representa los costos, el flujo de material entre el departamento i y el k se multiplica por la distancia entre la localización j y l y esta se hace en ambos sentidos de i a k y de k a i, la primera parte es la suma de los costos fijos de localizar el departamento en la localización j y la k en la l.
15
El problema de programación mixta equivalente fue:
{ }
)39(,1;,....2,1,;,....1
,1,...,2,1
0'
)38(,1;,....2,1,;,....1
,1,...,2,1
1'
)4(,....,2,1,,1,0
)3(,....,2,1,1
)2(,....,2,1,1
,,...,2,1,....,2
)37(,0)1('
,,...,2,11,....,2,1
)36(,0)1('..
)35('
1
1
1 1
1 1
1
1 1 1 1
≠=+=
−=
≥
≠=+=
−=
≤
=∈
==
==
==
=−−
=−=
=−−
�
�
��
��
����
=
=
=≠=
+=≠=
−
= = += =
jnljnik
ni
y
jnljnik
ni
y
njix
njx
nix
nl
nk
xky
nj
ni
xnyas
ygMin
ijkl
ijkl
ij
n
iij
n
jij
n
i
n
ljj
klijkl
n
ik
n
jll
ijijkl
ijkl
n
i
n
j
n
ik
n
lijkl
Como se puede observar las restricciones (2)-(4) y (35)-(39) tienen n2 variables enteras, n2(n-1)2/2 variables continuas y 2n2 restricciones, la equivalencia entre este modelo y el programa de asignación cuadrática, también fue demostrada por Bazaara y Sherali. 2.2.1.5 Formulaciones con Teoría de Grafos Según Foulds y Robinson [17], en las formulaciones gráfico teóricas se debe conocer que tan deseable es que cada par de departamentos se encuentren juntos. Sí, G=(V,E) - es una grafo con V como un conjunto de vértices (departamentos), E es un
conjunto de bordes obtenidos desde V. wij - los rangos de cercanía que indican que tan deseable es que el departamento i este
adyacente al j. V -el conjunto de departamentos.
16
N -el conjunto de pares de departamentos que deben ser adyacentes en cualquier solución factible.
F - el conjunto de pares que no deben ser adyacentes en cualquier solución factible. E’ = {{i,j}: xij =1, {i,j} � E}, xij =1 si la departamento i es adyacente al departamento j, 0 de otra manera.
Entonces la formulación grafo teórica es:
{ }
{ }
)43.(...).',(..
)42(,,0.
)41(,,1..
)40(,
planagraficaunaesNEV
Fjix
Njixas
xwMax
ij
ij
ijEi Ej
ij
∪
∈=
∈=
��∈ ∈
La función objetivo maximiza los rangos de cercanía, se trata de que los rangos más altos se cumplan, es por esto que se multiplican por 1 si el departamento i es adyacente al j. La restricción (41) se cumple si los departamentos considerados estan en le conjunto de pares que deben ser adayacentes en cualquier solución factible, la (42) sé esta en el que no deben ser adyacentes. La (43) se refiere a sacar de todo el juneto de departamentos y formar con los que deben ser adyacentes un grafo plano. Un grafo plano se define así porque puede ser elaborada en un plano sin que dos de sus orillas o límites se intercepten. Otros que trabajaron en tipo de modelos son Harare, Bondy y Morty [28]. Rosenblatt [28] desarrolló un modelo que minimiza el costo de transportación de material y maximiza el rango de cercanía, siendo estos objetivos conflictivos entre sí. Rosenblatt [28], Dutta y Sahu [28] desarrollaron algoritmos heurísticos para desarrollar el modelo. 2.3 Complejidad Computacional Sahni y Gonzalez [28] demostraron que el problema de asignación cuadrática es NP Completo, es decir que el tiempo de solución del problema no crece de forma proporcional con el tamaño del mismo. Burkard [7], reportó resultados computacionales, por ejemplo, para encontrar una solución óptima al problema de 15 departamentos de Nugent había ocupado más de una hora de tiempo CPU en una unidad CDC CYBER 76. También Bukard analizó los resultados del código de ramificaciones para este mismo problema hecho en FORTRAN, requiriéndose n3+5.5 n2+17.5n unidades (1 unidad equivale a 8 bytes) de memoria. Desde 1950, se han desarrollado algoritmos para desarrollar el problema de distribución de departamentos. Estos algoritmos son clasificados como óptimos o subóptimos. 2.3.1 Algoritmos Óptimos Durante los 60’s fue desarrollado una gran cantidad de investigación para desarrollar algoritmos óptimos para el problema de asignación cuadrática. Estos algoritmos pueden ser divididos en dos clases: algoritmos de ramificación y acotamiento, y de plano de corte.
17
2.3.1.3 Algoritmos de Ramificación y Acotamiento Los primeros dos algoritmos fueron desarrollados por Gilmore y Lawler [19,30]. La diferencia principal entre estos trabajos fue la manera en como se calculan los límites inferiores, los dos evalúan implícitamente todas las posibles soluciones, pero sí no existen límites, el procedimiento se vuelve ineficiente. Adicionalmente a estos métodos, Land,Gavett y Plyter [28] desarrollaron otros algoritmos. Éstos asignan un par de departamentos a un par de localizaciones, mientras que los algoritmos de Gilmore y Lawler asignan un solo departamento a una sola localización. Los algoritmos anteriores trabajan etapa por etapa asignando departamentos a localizaciones, en cada una de ellas, ciertas asignaciones son excluidas y el proceso de búsqueda es más sencillo. Pierce y Crowston [39], discutieron un algoritmo en donde se usa la exclusión de pares de asignaciones etapa por etapa para la solución de un problema. Todos estos algoritmos, ya que buscan una solución óptima, ocupan una gran memoria y exigen requerimientos computacionales (Burkard [7]). Lavalle y Rocairol [28] sugirieron el uso del método paralelo de ramificaciones y límites para resolver el problema de asignación cuadrática de forma óptima. Estos algoritmos trabajan de forma paralela en varias partes del árbol de decisión, sin embargo, reportaron que se requería una gran cantidad de tiempo computacional para problemas de doce o más departamentos. Graves y Whinston [28] desarrollaron un heurístico que está basado en el hecho de que se pueden determinar los límites usando propiedades estadísticas de la función objetivo. Estos límites son usados en un procedimiento enumerativo que desarrolla soluciones subóptimas. Burkard [7] propuso un algoritmo subóptimo para resolver el problema de asignación cuadrática basado en la reducción de la matriz cuadrada. La reducción de esta matriz se refiere a la transformación de la matriz A en otra matriz A’ de elementos no negativos en donde por lo menos hay un cero en cada fila y en cada columna. Estas reducciones habían sido aplicadas al problema del agente viajero por Little y en el caso del problema de asignación cuadrática se usa para mejorar la calidad de los límites, reduciendo la magnitud del término cuadrático en la función objetivo y aumentando la influencia de los términos lineales. Bazaara [3], desarrolló un algoritmo de ramificación y acotamiento para departamentos de áreas desiguales, en donde una configuración parcial P esta disponible en cada etapa. Un límite inferior LB en el costo de todas las opciones de la configuración parcial esta determinado. Sí LB es menor que el costo de la distribución disponible Cº, el algoritmo asigna un nuevo departamento e incrementa el tamaño P del la distribución parcial, de otra forma está ruta se elimina y se busca asignar un nuevo departamento. La búsqueda continúa utilizando este procedimiento hasta que se completa la asignación de todos los departamentos. Bazaraa y Elshafei [6], propusieron otro algoritmo de este tipo, que este basado también en la asignación etapa por etapa de un solo departamento en localizaciones desocupadas. Kaku y Thompson [28] previeron otro algoritmo de ramificación que trabaja mejor que el de Lawler [40] para problemas de tamaño más grande.
18
2.3.1.2 Algoritmos de Plano de Corte Bazaraa y Sherali [5] desarrollaron un algoritmo de plano de corte basado en el esquema de partición de Bender. Burkard y Bonninger [8], también desarrollaron un método de este tipo para resolver el problema de asignación cuadrático. Los algoritmos de ramificación y acotamiento y el de plano de corte, tienen complejidad en el tiempo de solución y almacenamiento. Por ejemplo, el problema más grande que se ha resuelto de forma óptima con el algoritmo de plano de corte es la distribución de ocho departamentos. Una experiencia común de Burkard y Stratman [9], Bazaraa y Kirka [4] con los algoritmos óptimos es que la solución óptima es encontrada tempranamente en el proceso de ramificación, pero no es verificada hasta que un gran número de soluciones han sido encontradas. Esto obligó a los investigadores a terminar el proceso de ramificación prematuramente sin verificar su optimalidad. Esto resultó en métodos heurísticos de ramificación. Burkard [7] sugirió dos criterios para terminación del proceso de ramificación:
(i) terminación prematura basada en límites de tiempo. (ii) terminación prematura basado en la calidad de los límites superiores; después de
cierto tiempo si no hay mejora en la solución, el límite superior se disminuye en cierto porcentaje.
2.3.2 Algoritmos Subóptimos Los algoritmos óptimos tienen las siguientes desventajas:
i) los requerimientos de memoria y tiempo computacional son altos. ii) el problema más grande resuelto de manera óptima es el problema con quince
departamentos. Estas consideraciones originaron que los investigadores se concentraran en algoritmos subóptimos para resolver el problema de distribución de departamentos. Algunos de los primeros métodos usaron cuadros de flujo, diagramas de proceso; además de la experiencia y conocimiento del analista. Otros métodos usados fueron el cuadro de relaciones, que muestra la cercanía deseada entre pares de departamentos, este concepto fue introducido por Muther [48] en 1955. La cercanía deseada es representada en el cuadro de relaciones por valores A, E, I, O, U y X. Para cualquier par de departamentos (i,j), los valores A, E, I, O, U y X indican sí la cercanía entre los departamentos es absolutamente necesaria, especialmente importante, importante, ordinaria, no importante o indeseable. Los pasos son los siguientes:
i) Construir el diagrama de relación de los distintos departamentos, es necesario contar con el área total y por departamento.
19
Figura 2.3 Diagrama de Relaciones
ii) Seleccionar el primer departamento a ser asignado, éste debe ser el que tenga la mayo cantidad de A´s. Se pone en el centro de la distribución.
iii) Seleccionar el segundo departamento. Éste debe tener una relación A con el primer departamento seleccionado, se pone adyacente al primer escogido
iv) Seleccionar el tercer departamento que entra a la distribución, debe tener la mayor relación de combinación con los seleccionados anteriormente.
v) El departamento n es seleccionado con las reglas de iii) y iv). vi) Se construye una distribución relativa con las unidades que ocupa cada
departamento.
Figura 2.4 Distribución Relativa.
4 4 1 1
4 4 3 1
4 2 1 3
4 2 2 2
5 6 6 6
1 1 1
5 6 6 6
5 7 7 7
5 7 7 7
20
Este método sentó las bases para el desarrollo del método popular conocido como planeación sistemática de distribución de departamentos en 1973, cuyo algoritmo se muestra a continuación:
Figura 2.5 Planeación sistemática de distribución de departamentos Wimmert [48] presentó un método matemático para el problema de distribución de departamentos que usaba el criterio de minimización de flujo de productos y distancias entre todas las combinaciones de departamentos. Conway y Maxwell probaron que el teorema en el cual se sustenta este método, es incorrecto. Buffa propuso otro método llamado análisis secuencial, su nombre proviene del análisis de operaciones dentro de la planta. Existen otros métodos desarrollados a finales de los 50’s y principios de los 60’s pero que no arrojaron soluciones de calidad. Posteriormente, los investigadores empezaron a desarrollar nuevos algoritmos que pueden ser clasificados como:
Datos de entrada y Activida des
Flujo de Material Relación ente Actividades
Diagrama de Relación
Requerimientos de Espacio Espacio Disponible
Diagrama de Relación de Espacio
Modificar por consideraciones Limitaciones Prácticas
Alternativas de Layout
Evaluación Selección
B úsqueda
Análisis
21
• algoritmos de construcción • algoritmos de mejoramiento • algoritmos híbridos • algoritmos de teoría de grafos
2.3.2.1 Algoritmos de Construcción En los algoritmos de construcción los departamentos son asignados a un sitio, uno a uno hasta que la distribución final es obtenida. Moore encontró que existía una gran cantidad de algoritmos de construcción y de mejoramiento, ellos se mencionan en le trabajo de Kusiak y Heragu[28]. Algunos de los algoritmos de construcción más populares son mencionados.
• HC66 Hillier y Connors surgieron un algoritmo de construcción y mejoramiento basado en uno que Hillier ya había construido en 1963. HC66 es una modificación del algoritmo de Gilmore, en cualquier etapa k, k departamentos son asignados a k localizaciones. Dadas estas k asignaciones, se calcula un límite inferior asociado con la asignación de los (n-k) departamentos no asignados. Cada uno de estos límites entra como elementos de la matriz H, cuyas filas representan departamentos no asignados y las columnas localizaciones que no están ocupadas. La diferencia con el algoritmo de Gilmore es la forma de seleccionar el elemento (i,j) de la matriz H, HC66 usa el criterio de aproximación de Vogel para resolver problemas de transportación.
• ALDEP ALDEP fue creado por Seehor y Evans. Este método selecciona al azar un departamento y lo asigna en la esquina superior izquierda de la distribución. El siguiente departamento seleccionado es el que tiene la relación más o tan grande que la especificada con el primer departamento seleccionado; sí ya hay dos departamentos asignados se selecciona uno al azar para hacer la comparación. Esto se hace hasta que todos los departamentos han sido asignados.
• CORELAP Fue creado por Lee y Moore y usa el rango de cercanía total de cada departamento para determinar una configuración. El rango de cercanía total del departamento i es igual a la suma de del valor numérico de sus relaciones con los demás departamentos. En lugar de seleccionar el primer departamento al azar, se selecciona el que tenga el rango de cercanía más grande y se coloca en el centro. Las facilidades subsecuentes son adheridas a la configuración dependiendo de sus relaciones con las facilidades que ya han sido asignadas.
• RMA Comp I Fue desarrollado por Muther y McPherson, éste selecciona el departamento que tenga el rango de cercanía más alto y lo ubica al centro de la configuración. Los departamentos subsecuentes son incluidos dependiendo de los departamentos asignados y no asignados. Por ejemplo, cuando se ubica el departamento i, se cuida que haya suficiente espacio a la izquierda para el departamento no asignado j, el cual tiene el rango de cercanía más alto con respecto a i. En cada etapa, se revisa el cuadro de relaciones para estar seguros de que tan deseable es localizar o no pares de departamentos adyacentes.
22
• MAT Su creador fue Edwards, a él se le ocurrió que había que acomodar pares de departamentos, de acuerdo con sus flujos y distancias y usar esta información para determinar una configuración. Los autores de MAT encontraron que al combinar la salida de MAT con la de CRAFT (creada por Armour y Buffa) resultaba en soluciones de buena calidad con tiempo computacional menor para problemas de ocho departamentos.
• PLANET La asignación de departamentos creado por Deisenroth y Apple maneja un proceso en tres etapas. En la primera, el costo de cada par de departamentos es determinado. Cada facilidad tiene un número asignado que oscila ente 1 a 9 y determina el orden en que un departamento puede entrar a la configuración. Este número de prioridad y el costo de flujo entre cada para de facilidades forman la base para la selección del orden en que se asignarán los departamentos a la configuración. La selección del orden constituye la siguiente etapa, para seleccionar este orden existen tres algoritmos diferentes que el usuario tiene opción a escoger. La etapa 3 es para colocar los departamentos en la configuración en el orden que fue seleccionado en la etapa 2.
• LSP Zoller y Adendorff éste genera la secuencia en que los departamentos serán colocados en la distribución, además de un modo de construcción que determina una representación en dos dimensiones de la secuencia generada. Este simulador es un generador de números seudo aleatorios y su salida es convertida en secuencia aleatoria sesgada de departamentos. Esta configuración es evaluada y estas revisiones son las que deciden cuando parar el programa. Se requiere un gran esfuerzo computacional.
• Algoritmo de colocación lineal Neghabat y consistía en colocar los dos departamentos que tuvieran el flujo más alto entre ellos en localizaciones arbitrarias de tal manera en que la distancia entre las dos fuera minimizada. Los departamentos subsecuentes eran seleccionados uno a uno tomando como base sus flujos generales con los que ya han sido asignados, obviamente estos eran asignados de tal manera que existiera una minimización de costos. Al mismo tiempo se cuida que las restricciones de espacio no sean violadas. Este algoritmo solo puede resolver problemas con departamentos de área similar.
• INLAYT Es uno de los algoritmos usados en un heurístico propuesto por O’Brien y Abdel Barr. Este heurístico usa INLAYT, nombre dado por sus autores, para generar una configuración inicial que después es mejorada por otro algoritmo llamado S-Zaky. El usuario puede aceptar, rechazar o modificar lo arrojado por ambos algoritmos mediante un lápiz óptico conectado a una terminal gráfica. INLAYT agrupa departamentos dependiendo del costo de transporte y los despliega como un arreglo de localizaciones posibles. El usuario responde asignando los departamentos del primer grupo a cualquier localización deseada. El mismo procedimiento es repetido para el segundo, tercero y hasta que todos los departamentos sean asignados.
• FLAT Fue creado por Heragu y Kusiak para departamentos de áreas desiguales. FLAT usa:
23
i) la matriz de flujo [fij], donde fij es el flujo entre los departamentos i y j.
ii) La matriz de adyacencia [dij], donde dij es la distancia mínima entre los departamentos i y j cuando están lo más cerca posible uno del otro.
Se calcula una nueva matriz [tij], donde tij= fij. dij. El algoritmo consiste de dos fases, en la fase uno un número de tríadas con sus pesos máximos es seleccionado. Cada trío esta compuesto de vértices en donde cada cima representa un departamento. El peso de un trío se refiere a la suma de los flujos entre cada par de vértices del mismo. El número de tríos seleccionado depende del número total de departamentos que estén representados en los vértices. Los tríos son arreglados en orden decreciente según sus pesos en una lista L. En la fase 2, la asignación de departamentos a sus respectivas localizaciones es hecha usando:
i) los tríos ordenadas en la lista L, y ii) un vector de asignación que corresponda a cada departamento.
El vector de asignación, indica en que localización será asignado un departamento específico, a cuáles otros será adyacente y cómo su forma puede ser alterada por la configuración final. Esto se hace de la siguiente manera: los tríos ordenados en la lista L, son seleccionados uno por uno empezando por el primero y luego clasificados según:
i) el flujo entre los vértices del trío ii) sí uno de los vértices en el trío ha sido asignado con anterioridad.
La clasificación de los vértices es lo que determina la secuencia de departamentos a entrar en la configuración. 2.3.2.2 Algoritmos de Mejora En los algoritmos de mejora existe siempre una solución inicial la cual es generada de forma aleatoria. Basados en esta solución inicial, se hacen intercambios sistemáticos entre los departamentos y luego los resultados son evaluados. El intercambio que produce la mejor solución es retenido y el procedimiento continúa hasta que esa solución no puede mejorarse más. De esta forma, la solución final depende considerablemente de inicial. A continuación se presentan los más importantes recabados en el trabajo de Kusiak y Heragu[28]:
• CRAFT Fue propuesto originalmente por Armour y Buffa [2]. Los principios que se manejan son tan populares que han sido modificados frecuentemente. Ejemplos de esto son COFAD diseñado por Tompkins y Reed, la técnica de muestreo sesgada de Nugent, CRAFT M, SPACECRAFT, entre otros. Armour y Buffa consideraron el problema de distribución de departamentos como un problema de asignación cuadrática, además de utilizar un heurístico debido a la dificultad combinatoria, es decir, existe una gran cantidad de diferentes acomodos de departamentos; evaluar cada una de estas posibilidades es lo que encierra la dificultad del problema. La formulación es como sigue: n - número de departamentos vij - número de unidades que se mueven entre los departamentos i y j uij -costo de mover una unidad de carga, una unidad de distancia entre el departamento i y j. Iij - distancia entre los departamentos i y j.
24
Los elementos de la matriz U y la matriz V no varían con cambios en las localizaciones, así que es permisible combinarlas para obtener yij. Esta matriz representa los costos de mover el producto total del departamento i al j una unidad de distancia. La distancia la forma la matriz L, y varía conforme las localizaciones cambian., lij - la distancia entre centros del departamento i al j. La función objetivo es:
)44(11
ij
n
jij
n
i
lyTC ��==
=
Se considera al siguiente heurístico: 2) Calcular la matriz L de distancia entre departamentos para la solución inicial
propuesta, la que utilizaron fue para 20 departamentos. 3) Calcular la matriz yij para ello, se deben tener dos matrices V y U. 4) Evaluar los cambios en el costo total que ocurrirán si cada departamento se cambiara
con todos los demás en localización. Encontrar el mayor ahorro �TC. Se requieren (n2-n)/2 evaluaciones. Al evaluar el intercambio entre dos departamentos sólo es necesario considerar los vectores encabezados por los departamentos que están siendo analizados en dicho intercambio, simplemente es un proceso de multiplicar dos vectores por producto punto, buscar los nuevos vectores, recalcular el producto punto y calcular la diferencia. Si se consideran dos departamentos E y F. Los costos contribuidos por E y F antes del intercambio son:
)45(11
fj
n
jfjej
n
jejfe llylCC ��
==
+=+
Los costos contribuidos por e y j después del intercambio:
)46(''11
efefej
n
jfjfj
n
jejfe ylllylCC ++=+ ��
==
El cambio en el costo resultante por intercambiar el departamento E y F es:
)47(21111
efefej
n
jfjfj
n
jejej
n
jfjfj
n
jejef ylllylllylTC −−−+=∆ ����
====
Se compara el nuevo �TC con el último encontrado, se retiene al mayor y se continúa hasta que todos los intercambios sean evaluados.
5) Si no hay algún �TC positivo se va al paso 6, en caso contrario se recalcula L para la configuración con el mayor ahorro obtenido, se imprime este nueva configuración.
6) Ir al paso 3. 7) Parar un subóptimo ha sido alcanzado
Este algoritmo no funciona bien cuando los departamentos son de áreas desiguales.
• H63 Hillier desarrolló un algoritmo heurístico nombrado así por el nombre de su autor y el año en que lo publicó 1963, el cual está basado en una tabla, que consiste en los cambios de costo (dado una configuración inicial) que resultarían de mover un departamento de su localización actual a una adyacente. Esta tabla es revisada y el valor máximo es seleccionado. El departamento i que corresponde a su valor máximo es considerado para un movimiento en su localización. Sí después de la revisión
25
existe una reducción positiva en el costo, se hace el cambio; de otra manera otros movimientos adyacentes son considerados y el movimiento que resulte en una reducción positiva del costo es hecho. Sí no existe algún cambio de reducción en costo cuando la facilidad i es movida, se toma el segundo valor más grande y se continúa con el proceso. Este algoritmo sólo sirve para departamentos con áreas similares.
• COL Este algoritmo fue hecho por Vollman, determina para cada facilidad i, el costo pi de flujo del departamento i a todos los otros departamentos los cuales están localizados � o más unidades del departamento i. Estos costos pi son la base para seleccionar dos departamentos m, n que son los mejores candidatos para el intercambio. Después el departamento m es considerado para intercambio con todas las demás departamentos, para evaluar el menor costo posible. Los pi’s son recalculados y el ciclo es repetido hasta que no sea posible realizar mejoras. COL produce buenas soluciones, siendo lo doble de rápido que HC66 y requiere menos almacenamiento de memoria.
• Algoritmos con Muestreo Dos algoritmos con muestreo son propuestos, el primero fue creado por Nugent y genera soluciones aleatorias. A cada solución que es mejor que la anterior, se le asigna una probabilidad diferente de cero. El algoritmo permite la selección de cualquier intercambio entre pares, lo que resulta en una reducción de costo. En esencia lo que hace es introducir un elemento probabilístico al algoritmo CRAFT y busca los vecinos para una mejor solución. El segundo algoritmo fue desarrollado por Hitchings y Cottam llamado proceso de muestreo temporal. Usa los principios de otros algoritmos como COL y CRAFT, etc., ejecuta una selección de pares selectiva y reduce el tiempo de cómputo. Al final de estos cambios selectivos, la iteración es terminada por un ciclo CRAFT.
• COFAD COFAD fue creado por Tompkins y Reed éste es una modificación de CRAFT que incluye mover los costos de todos los sistemas de manejo de materiales alternativo, es decir, no sólo se puede decidir la ubicación óptima de departamentos sino también el sistema a utilizar. Se mejora la configuración inicial con el procedimiento CRAFT, el algoritmo después determina el costo de mover material entre cada par de departamentos usando un sistema factible de manejo de materiales. Estos costos de movimiento son utilizados para seleccionar el sistema de manejo de materiales que minimice los costos. Un supervisor dirige el modelo y determina cuando el diseño ha alcanzado el estado estacionario. Se alcanza este estado cuando el costo de sistema de manejo de materiales y el número de cambios varían menos que un cierto porcentaje del costo total de sistema y el número de asignaciones. Sí el estado estacionario es alcanzado, el supervisor termina el programa, en caso contrario el procedimiento se repite.
• Algoritmo Hillier Revisado El algoritmo desarrollado por Picone y Willhelm usa H63 para mejorar una solución inicial dada y después mejorar esta solución considerando perturbaciones–4 (perturbaciones-k considera el intercambio de la localización de k departamentos al mismo tiempo). Sí la aplicación de perturbaciones-4 mejora la solución, se aplica un método llamado PERTURB, en caso contrario se mejora la solución usando H63. PERTURB considera perturbaciones-4 y perturbaciones-3, después de realizarlas, H63 se aplica a la solución actual. Sí la solución resultante cumple con el
26
criterio especificado C, una perturbación-4 es aplicada una vez más, si no hay una reducción en costo, una vez más, si esto se realiza después de varias sin haber reducción el programa termina. Si no se cumple con el criterio especificado C, se hace un esfuerzo final por mejorar la solución, el programa termina sí no se obtiene. Este algoritmo produce soluciones tan buenas como H63, pero requiere mayor tiempo computacional (aproximadamente el doble, debido a que usa H63 y el Hillier Revisado). 2.3.2.3 Algoritmos Híbridos Bazaara y Kirca clasificaron los algoritmos que tienen característica de óptimo y subóptimos como híbridos. Ejemplos de éstos son los hechos por Burkard y Stratman [9], Bazaara y Sherali [5], y Bazaara y Kirca [4]. Burkard y Sratman propusieron un heurístico que usa los conceptos de ramificación y un algoritmo de mejoramiento. Una solución inicial se obtiene usando el algoritmo de ramificación y termina después de haber alcanzado un tiempo límite. La solución inicial, mejorada después usando un algoritmo de mejoramiento llamado VERBES. VERBES usa intercambios de pares y de tríos alternadamente hasta que ningún mejoramiento pueda ser hecho. De esta manera, el nivel más pequeño k0 en el proceso de ramificación, es en donde VERBES obtiene una mejor solución. Este proceso se repite desde el nivel k0 hasta que la solución actual no pueda ser mejorada. Burkard y Stratman propusieron otro algoritmo similar, pero usa el elaborado por Gaschutz y Ahrens en lugar del de ramificación. Bazaara y Kirca propusieron algoritmos que son modificaciones del algoritmo óptimo presentado en el mismo artículo. Estos heurísticos están basados en un algoritmo de ramificación y reducen el tiempo computacional en cualquier rama similar a la que ya ha sido explorada. Estos heurísticos produjeron resultados de buena calidad.
• DISCON Drezner modeló el problema de distribución de departamentos como un problema de programación no convexo. Este problema es resuelto usando un algoritmo de dos fases llamado de dispersión-concentración. En la primera fase, la dispersión, se usa el método de gradiente de Lagrange, esta provee de un mínimo local satisfactorio. La solución final en la etapa de dispersión provee buenos puntos de inicio para la segunda fase (concentración). En la primera fase, los departamentos no están lo suficientemente cerca. La segunda fase consisten en acercar los departamentos pero sin que encimen.
• FLAC FLAC fue propuesto por Scriabin y Vergin, es un algoritmo que consiste de tres etapas. En la primera los departamentos son colocados de tal manera que su flujo sea inversamente proporcional a la distancia. En la segunda etapa, los departamentos son asignados usando el principio de la etapa 1, pero ahora las restricciones de espacio son tomadas en cuenta. La tercera etapa consiste de un ajuste usando un algoritmo de intercambio similar a FRAT.
27
2.3.2.4 Algoritmos de Teoría de Grafos. Este tipo de algoritmos identifica subgrafos planos de un total que muestra las relaciones entre departamentos. El dual de un subgrafo plano determina la configuración de los departamentos. Seppanen y Moore propusieron un algoritmo de este tipo [44], además de otro heurístico que también usaba esta estrategia. El algoritmo determina el máximo árbol basado en el grafo total; con la ayuda de un proceso, el árbol máximo es usado para obtener un subgrafo máximo plano cuyo dual determina la configuración final.
• Algoritmo de ramificación Foulds y Robinson lo presentaron [17]. Este algoritmo empieza colocando pares de departamentos {i,j} en orden descendente según sus flujos fij, son colocados en una lista P. Todos los pares de departamentos son ubicados en localizaciones adyacentes para obtener un grafo parcial. Una vez hecho esto, el algoritmo de ramificación comienza. En cualquier etapa k, k pares departamentos son elegidos e incluidos en el grafo T. Para obtener una solución óptima, un grafo máximo es requerido. Este grafo plano tiene 3n-6 lados, donde n el número de vértices de los departamentos, 3n-6-k lados tienen que ser adheridos para tener un grafo máximo plano. Un lado {i,j} representa la relación entre los departamentos i y j. También en cada etapa del proceso de ramificación y acotamiento, existe una penalización por adherir o no el siguiente par de departamentos en la lista P. La ramificación entonces comienza desde el nodo que tiene la menor penalización y menor de 3n-6 lados. Al mismo tiempo, se determina si un lado debe ser adherido a la gráfica actual T sin que deje de ser plana. Los nodos que deben ser considerados son aquellos que permitan los grafos planos máximos con la menor penalización, el proceso continúa hasta que todos los nodos con menor penalización han sido considerados. El último nodo da la solución final.
• Algoritmo de Deltahedro Foulds y Robinson [17] presentaron dos algoritmos heurísticos que evitan la evaluación de sí es plano o no (esto es difícil especialmente para cuando el tamaño del problema se incrementa). Los algoritmos inicialmente determinan un tetraedro, particularmente en el tipo de grafo en donde cada uno de los cuatro vértices se conecta con otros 3 vértices. Este tetraedro tiene cuatro caras incluyendo la externa f1, f2, f3, f4. Los vértices sobrantes son insertados uno a uno en las caras del gráfico. En cualquier etapa del algoritmo una lista de vértices V, lados E y caras F mantenida. Por ejemplo, sí el vértice a es insertado en la cara f1 que consiste de los lados pq, pr y qr, los lados correspondientes ap, aq y ar son aumentados a la grafica. Las listas V, E y F son actualizadas como: V consiste de los vértices a, p, q, r , s; E está formado por los lados ap, aq, ar, pq, pr, qr, ps, rs, qs; F tiene las caras f1, f2, f3, f4 , f5, f6; Los dos algoritmos que emplean esta estrategia difieren en la forma en que el tetraedro inicial es seleccionado. Carrie [13], también desarrolló cuatro algoritmos heurísticos que seguían el proceso de solución general propuesto por Seppannen y Moore, pero considerando un paso adicional, redibujar la
28
grafica plana máxima basados en las relaciones entre los departamentos. Estos algoritmos difieren en la forma son adheridos a la grafica en cada paso.
• Algoritmo de Expansión de la Rueda. Eades [15], desarrolló un algoritmo heurístico muy parecido al de Foulds y Robinson. El algoritmo empieza determinando un tetraedro, después se realiza un procedimiento conocido como expansión de rueda. Una rueda con n vértices es graficada, ésta consiste de un ciclo con n-1 vértices, de tal manera que cada uno de los n-1 vértices está adyacente a un vértice adicional p. En el proceso de expansión de la rueda, otro vértice q es adherido a la gráfica de tal manera que:
i) p y q son los centros de las dos ruedas. ii) Existen dos vértices k, l que están en los ciclos de las dos ruedas. iii) Cada vértice previamente adyacente a p, a q o a ambos está en la
nueva rueda. Se obtienen las gráficas planas para determinar una configuración de departamentos. Foulds comparó el algoritmo deltaedro, el algoritmo de expansión de la rueda y otro glotón, sus lados son ordenados con respecto a sus pesos y adheridos a la gráfica siempre y cuando no deje de ser plana. Encontró que el método deltaedro en combinación con la técnica de mejoramiento era la más exitosa en calidad de la solución y tiempo. 2.4 Métodos Heurísticos Los problemas de optimización combinatoria son aquellos caracterizados por un número finito de soluciones, estos se presentan en la vida diaria, particularmente en el diseño ingenieril, pudiendo ser estos balanceo de líneas, horario de máquinas, rutas de vehículos, localización de departamentos en una distribución, etc. A pesar de que en principio, estos problemas pueden resolverse por simple enumeración, en la práctica esto es frecuentemente imposible cuando el número de soluciones factibles es extremadamente alto. Este tipo de problemas se conocen como NP Completos. 2.4.1 Problemas NP-Completos NP-completo implica que sí existe un algoritmo que resuelve un problema de CUALQUIER TAMAÑO, su tiempo de ejecución es una función que crece con respecto al tamaño del problema a un ritmo mayor que la de cualquier función polinómica, por ejemplo, en proporción exponencial.
En este sentido juega un papel importante el tiempo, éste es necesario como una medida de rendimiento para comparar diferentes algoritmos, y el más ampliamente aceptado es el que el algoritmo en cuestión consume antes de producir la solución final [42]. Este tiempo muchas veces es expresado en términos del número de pasos elementales como operaciones aritméticas, comparaciones, lecturas, escrituras, etc. que se efectúan para obtener el resultado final. De esta forma la complejidad de un algoritmo está en función del tamaño de la entrada n, pudiendo ser n el número de trabajos para secuenciación, número de departamentos a distribuir, números para ordenar, actividades para encontrar la ruta más corta, etc., (por ejemplo 10n3, 2n, n log n). La notación de la razón de crecimiento de la complejidad de un algoritmo puede ser acotada mediante frases como "toma un tiempo O(n3)".
29
Para entender la frase O(n3), se puede considerar un problema simple de intercambio de un conjunto de n números para acomodarlos del más pequeño al más grande a través de un algoritmo de orden [51]. En este algoritmo se comparan dos objetos cercanos y se cambian sí están en el orden equivocado. En este caso, si los números están dados en orden descendente, el algoritmo hará n2 comparaciones antes de acomodar los números. Sí los números en su fase inicial están en el orden correcto sólo se harán n comparaciones. Basados en el peor escenario, este algoritmo de ordenamiento puede ser clasificado como O(n2). La O significa tiempo y denota la expresión dominante, la complejidad computacional. Así que si el algoritmo es O(n2), existe c y n0 tal que n � n0 y el número de cálculos requeridos es a lo mucho c n2. Los algoritmos más eficientes de orden son O(n*log(n). Observando problemas de programación conocidos, el Algoritmo del Glotón (Greedy Algorithm) y el de Dijkstra para encontrar la ruta más corta son O(n2).
Algunos algoritmos de complejidad computacional polinomial son O(n) o O(n3), existen otros para los cuales la complejidad asintótica no es un polinomio en sí pero puede ser acotada por un polinomio como n2 y n log n. Los algoritmos que tienen tiempos de solución polinomial se consideran eficientes porque pueden resolver problemas de tamaños grandes en un tiempo razonable, además utilizando procesadores que trabajan en paralelo es posible encontrar la solución óptima. Se le da el nombre de algoritmo exponencial a todo aquel que viola todo acotamiento polinomial para instancias suficientemente grandes, ejemplos de esto son kn (para cualquier constante k > 1), n!, nn y nlog n. Como se puede ver en la siguiente en la tabla 2.1 [42], cuando el tamaño de la entrada crece, cualquier algoritmo polinomial eventualmente llegará a ser más eficiente que cualquier algoritmo exponencial.
Tabla 2.1: Crecimiento de funciones polinomiales y exponenciales.
Función Valores Aproximados
Polinomiales
N 10 100 1,000
N log n 33 664 9,966
N3 1,000 1,000,000 109
106 n8 1,014 1022 1030
No Polinomiales
2n 1,024 1.27 x 1030 1.05 x 10301
nlog n 2,099 1.93 x 1013 7.89 x 1029
N! 3,628,800 10158 4 x 102,567
Otra característica positiva de los algoritmos polinomiales es que toman ventaja de los avances de la tecnología como se puede ver en la tabla 2.2. Por ejemplo, cada vez que una mejora tecnológica incrementa la velocidad de las computadoras 10 veces, el tamaño de la instancia más
30
grande que puede ser solucionada por un algoritmo polinomial en una hora, por ejemplo, será multiplicado por una constante entre 1 y 10. En contraste, un algoritmo exponencial experimentará únicamente un incremento pequeño que se sumará al tamaño de la instancia que este puede resolver.
Tabla 2.2: Avances de la tecnología.
Función Tamaño de la Instancia Solucionada en un Día
Tamaño de la Instancia Solucionada en un Día en una Computadora 10 Veces Más Rápida
Polinomiales
N 1012 1013
n log n 0.948 x 1011 0.87 x 1012
n2 106 3.16 x 106
n3 104 2.15 x 104
108 n4 10 18
Exponenciales
2n 40 43
10n 12 13
nlog n 79 95
n! 14 15
Finalmente se puede decir que los algoritmos polinomiales tienen la propiedad de cerradura: pueden ser combinados para resolver casos especiales del mismo problema; un algoritmo polinomial puede llamar otro algoritmo polinomial como una subrutina y el algoritmo resultante continuará siendo polinomial. La teoría de la NP-Completo fue presentada inicialmente por Cook desde 1971 [42]. Cook probó un problema particular que se estudia en Lógica "El Problema de Satisfactibilidad", este problema pertenece a la clase NP y puede ser reducido a una transformación de tipo polinomial. Esto significaba que sí el problema de satisfactibilidad podía ser resuelto en tiempo polinomial, todos los problemas No Polinomiales también podrían resolverse en tiempo polinomial. Cook también sugirió que el problema de satisfactibilidad y otros problemas NP tenían la característica de ser los problemas más difíciles, teniendo dos tipos de versiones: de decisión y de optimización. Los problemas de optimización se denominan NP Completos, entendiéndose como de optimización donde se busca el máximo o mínimo de una función y existen un conjunto de restricciones. Se sabe que dado un problema de optimización, se puede definir un problema de decisión asociado a él, esto es, una pregunta que puede ser contestada por si o no. La definición de problema de decisión a partir del problema de optimización permite estudiar ambos tipos de problemas de una manera uniforme. Además, como se ha puntualizado que un problema de
31
decisión no es más difícil que el problema de optimización original, cualquier resultado negativo probado sobre la complejidad del problema de decisión será aplicable al problema de optimización también. Si se está interesado en clasificar los problemas de decisión de acuerdo a su complejidad. Se denota por P a la clase de problemas de decisión que son polinomialmente acotados, esto es, la clase de problemas de decisión que pueden ser solucionados en tiempo polinomial. Se puede decir que P es la clase de problemas para los cuales existe un algoritmo que los soluciona eficientemente. Para una entrada dada, una "solución" es un objeto que satisface el criterio en el problema y justifica una respuesta afirmativa de si. Una "solución propuesta" es simplemente un objeto del tipo apropiado, este puede o no satisfacer el criterio. Informalmente se puede decir que NP es la clase de problemas de decisión para los cuales una solución propuesta dada para una entrada dada, puede ser revisada rápidamente (en tiempo polinomial) para ver si ésta es realmente una solución, es decir, si ésta satisface todos los requerimientos del problema. Para entender que es un problema NP es necesario definir las fases de un algoritmo no determinístico:
1. Alguna cadena de caracteres, s, completamente arbitraria es escrita a partir de algún lugar de memoria designado. Cada vez que el algoritmo corre, la cadena escrita puede diferir. Esta cadena puede ser vista como una adivinación de la solución para el problema, por lo que a esta fase se le da el nombre de adivinación.
2. Un algoritmo determinístico, es decir ordinario, siendo ejecutado. Además de la entrada del problema de decisión, el algoritmo puede leer s, o puede ignorarla. Esta etapa verifica s para ver si ésta es una solución para la entrada del problema de decisión.
El número de pasos llevados a cabo durante la ejecución de un algoritmo no determinístico es definido como la suma de los pasos en ambas fases; esto es, el número de pasos tomados para escribir s (simplemente el número de caracteres en s) más el número de pasos ejecutados por la segunda fase determinística. Normalmente cada vez que se corre un algoritmo con la misma entrada se obtiene la misma salida. Esto no ocurre con algoritmos no determinísticos; para una entrada particular x, la salida a partir de una corrida puede diferir de la salida de otra debido a que ésta depende de s. Aunque los algoritmos no determinísticos no son realistas (algoritmos útiles en la práctica), ellos son útiles para clasificar problemas. Se dice que un algoritmo no determinístico es polinomialmente acotado si hay un polinomio p tal que para cada entrada de tamaño n para la cual la respuesta es si, hay alguna ejecución del algoritmo que produce una salida si en cuando mucho p(n) pasos. De esta forma se puede decir que: NP es la clase de problemas de decisión para los cuales hay un algoritmo no determinístico acotado polinomialmente (el nombre de NP viene de no determinístico polinomialmente acotado). Un algoritmo ordinario (determinístico) para un problema de decisión es un caso especial de un algoritmo no determinístico. En otras palabras, si A es un algoritmo determinístico para un problema de decisión, entonces A es la segunda fase de un algoritmo no determinístico. A simplemente ignora lo que fue escrito por la primera fase y procede con su cálculo usual. Un
32
algoritmo no determinístico puede hacer cero pasos en la primera fase (escribiendo la cadena nula). Así si A corre en tiempo polinomial, el algoritmo no determinístico con A como su segunda fase corre también en tiempo polinomial. De lo mencionado se deduce que P es un subconjunto propio de NP. Se cree que NP es un conjunto mucho mayor que P [42], pero no hay un solo problema en NP para el cual éste haya sido probado que el problema no está en P. No hay un algoritmo polinomialmente acotado conocido para muchos problemas en NP, pero ningún límite inferior mayor que un polinomio ha sido probado para estos problemas. NP-completo es el término usado para describir los problemas de decisión que son los más difíciles en NP en el sentido que, si hubiera un algoritmo polinomialmente acotado para un problema NP-completo, entonces habría un algoritmo polinomialmente acotado para cada problema en NP. 2.4.1.1 Definición Formal de la Clase NP La definición formal de NP-completo usa reducciones, o transformaciones, de un problema a otro. Sí se quiere resolver un problema P1, se tiene un algoritmo para otro problema P2. La función T toma la entrada x para P1 y produce T(x), existe también una entrada para P2 tal que la solución correcta de P1 en x es afirmativa (si) sí y solo sí la respuesta correcta para P2 en T(x) es un si. Entonces, haciendo una composición de T y el algoritmo para P2, se obtiene un algoritmo para P 1. Sea T una función que va del conjunto de entradas para el problema de decisión P1 al conjunto de entradas para el problema de decisión P2. T es una reducción polinomial (también llamada transformación polinomial) de P1 a P2 si T puede ser calculada en un tiempo acotada polinomialmente. Para cada entrada x de P1, la respuesta correcta para P2 en T(x) es la misma que la respuesta correcta para P1 en x. P1 es polinomialmente reducible (también llamada polinomialmente transformable) a P2 si existe una transformación polinomial de P1 a P2. La notación P1 µ P2 es usada para indicar que P1 es reducible a P2. El punto fundamental de la reducibilidad es que P2 es al menos tan duro o difícil de resolver como P1. Esto puede precisarse a través del siguiente teorema. Sí P1 µ P 2 y P2 está en P, entonces P1 está en P. Ahora se puede dar una definición formal de NP-completo: Un problema P es NP-completo si éste está en NP y para cada otro problema P’ en NP, P’µ P Del teorema anterior y la definición de NP-completo se deduce el siguiente teorema:
Si cualquier problema NP-completo esta en P, entonces P=NP Este teorema indica, por un lado, que tan valioso sería encontrar un algoritmo polinomialmente acotado para cualquier problema NP-completo y, por otro, que tan improbable es que tal algoritmo exista pues hay muchos problemas en NP para los cuales han sido buscados algoritmos polinomialmente acotados sin ningún éxito.
33
Como se señaló antes, el primer problema de decisión que se propuso como un problema NP -completo es el satisfacibilidad de la lógica proposicional. Todos los problemas NP para los cuales se puede comprobar que pueden ser reducibles al problema de satisfactibilidad, son NP-completos. Así tenemos que los siguientes problemas son NP-completos: rutas y circuitos de Hamilton, asignación de trabajos con penalizaciones, el agente viajero, el problema de la mochila. Actualmente para probar que un problema es NP-completo, es suficiente con probar que algún otro problema NP-completo es polinomialmente reducible a éste debido a que la relación de reducibilidad es transitiva. La lógica de lo dicho es la siguiente:
• Si P ’ es NP-completo, entonces todos los problemas en NP µ P ’ • Si se demuestra que P ’ µ P, entonces todos los problemas en NP µ P
Por lo tanto, P es NP-completo. De todos los problemas en NP, Los problemas NP-completo son aquellos con complementos de estar en NP. Cuando todos los problemas en NP se transforman polinomialmente al problema P, pero no es posible demostrar P µ NP, se dice que P es tan difícil como cualquier problema en NP y por lo tanto NP-hard. NP-hard es usado también a los problemas de optimización de los cuales su problema de decisión asociado es NP-completo [42]. 2.4.2 Tipos de Heurísticos Los investigadores usan técnicas de aproximación para llegar a una buena solución cuando se enfrentan con problemas difíciles de resolver conocidos como NP. Estas técnicas de aproximación para alcanzar el óptimo son clasificadas como heurísticas en la investigación de operaciones. Un heurístico es un algoritmo que utiliza pruebas o aproximaciones para llegar a una solución, de esta forma, sin conocer unos datos base exactos se puede llegar a un resultado final. Por lo regular, estas técnicas están caracterizadas por buscar el mejor de cada opción, con el fin de obtener una buena solución en un tiempo eficiente y hacer algún mejoramiento cambiando esta solución por una cercana o haciendo búsqueda local. Una posibilidad es quedar atrapados en una solución óptima local y fallan al encontrar un óptimo global. No se ha demostrado con principios matemáticos o evaluación implícita del espacio de solución como es que los heurísticos producen soluciones óptimas, sin embargo, muchos de estos heurísticos tienden a converger a una buena solución en un tiempo polinomial, los mejores proveen rangos de calidad de la solución (cercanos al óptimo en cierto porcentaje). Después de estas heurísticos surgieron los metaheurísticos, entendiéndose como estrategias generales de diseño de procedimientos heurísticos para la solución de problemas con un alto rendimiento. Estas técnicas han sido exitosas en ciencia e ingeniería para resolver problemas que son inherentemente difíciles. Simon en 1987 [51] trató de integrar la investigación de operaciones con inteligencia artificial, en este estudio se abrieron muchos campos de investigación y se obtuvieron resultados significativos. Glover y Greenber en 1989 examinaron cuatro enfoques heurísticos: algoritmos genéticos, redes neuronales, recocido simulado, y la búsqueda tabú. Durante las últimas décadas, estos metaheurísticos basados en las técnicas de inteligencia artificial han sido adoptados para resolver problemas en la industria.
34
Un metaheurístico es una estrategia general para resolver problemas y están basados en técnicas de búsqueda inteligente. Búsqueda inteligente es el nivel más específico de búsqueda, especialmente diseñado para llegar a la información en forma exacta. Las técnicas de inteligencia artificial están basadas en sistemas naturales de adaptación, como selección natural, sistemas físicos y aprendizaje humano. Los algoritmos genéticos son una técnica de solución que imita a los genes humanos y su proceso se selección natural. El recocido simulado, simula el proceso de calentar un sólido hasta que la que temperatura este a punto de cambiarlo de estado y después bajarla lentamente para encontrar un estado de energía baja. Las redes neuronales simulan el comportamiento del cerebro para inferir con experiencias previas el proceso de toma de decisiones. La búsqueda tabú usa memoria a largo y corto plazo para buscar soluciones cercanas de calidad y evitar errores recientes. Estas técnicas tratan de prescribir una estrategia que puede ser usada para resolver diferentes problemas difíciles para alcanzar una buena solución de forma eficiente. Estos tratan de evitar un óptimo local, aceptando soluciones que no pueden ser mejoradas o considerando varias soluciones al mismo tiempo, también hay mecanismos para terminar los algoritmos sin que se ciclen. 2.4.3 Algoritmos Genéticos Los algoritmos genéticos pertenecen a la computación evolutiva, son considerados también una técnica de inteligencia artificial. A través de millones de años, los organismos han evolucionado biológicamente para sobrevivir y crecer en un mundo cambiante. Los materiales genéticos de todos los organismos vivos consisten de cromosomas que están divididos en genes; su codificación y desarrollo son considerados un proceso clave en la continuación de las especies. El proceso de selección natural y el sobrevivir de los más aptos son considerados elementos importantes en la evolución, que ha sido estudiada desde el siglo XVII. El primer evolucionista fue Lamarck que en 1809 se inclinó por un cambio gradual, según el cual unas especies se transformaron en otras sin necesidad de recurrir a nuevas creaciones. El mecanismo que propuso fue que los organismos desarrollan a lo largo de su vida estructuras que se adaptan mejor al medio ambiente, y que estas modificaciones estructurales son hereditarias. En 1859 Charles Darwin publica “Sobre el Origen de la Especies por medio de la Selección Natural”. Según Darwin en las especies hay una tendencia enorme a la variación sobre las que actúa la selección natural y la selección sexual. Aquellos organismos que poseyeran caracteres que los ajustaran mejor a su ambiente, tendrían una tendencia a reproducirse de una forma más prolífica que los otros, y sus caracteres se transmitirán a las generaciones futuras en mayor proporción. Así, las poblaciones estarían continuamente mejorando, y sus adaptaciones a los ambientes a los que están sometidas, y las poblaciones con adaptaciones no adecuadas acabarían extinguiéndose. Los Algoritmos Genéticos están basados en estos aspectos de evolución. Holland en 1975 propuso heurísticos basados en principios genéticos como una metodología para resolver problemas de toma de decisiones. Los algoritmos genéticos utilizan ideas de biología como población de cromosomas, selección natural para selección de pareja, cruza para producción de descendencia y mutación para diversidad. El punto importante de los algoritmos genéticos es la representación de un problema-solución que use un cromosoma de longitud constante o cambiante. La variable representada por la posición es un gen, y su valor se conoce como alelo. Una vez que obtenida la representación (codificado), es decir la manera en que el espacio de soluciones potenciales se transforma en el dominio de trabajo, la metodología de Algoritmos Genéticos puede ser aplicada para alcanzar una buena solución del problema. El codificado más popular por su simplicidad es el binario, donde los alelos son los valores de 0 ó 1.
35
De ser necesario, el codificado basado en valor o de caracteres puede ser usado también. A pesar de que el codificado fijo es popular, los investigadores han usado uno que puede adaptarse para algunos problemas para mejorar los resultados. 2.4.3.1 Funcionamiento Los algoritmos genéticos son métodos de optimización problemas que consistan en hallar (xi,...,xn) tales que F(xi,...,xn) sea máximo o mínimo. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todos los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno. Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies. La diversidad genética se introduce mediante mutaciones y reproducción sexual. Para comenzar la competencia, se generan aleatoriamente una serie de cromosomas (población inicial). Se evalúa la aptitud (fitness) de cada uno de los genes y se permite a cada uno de los individuos reproducirse, de acuerdo con aptitud. Se equilibran los individuos de la nueva población, haciendo que intercambien material genético, y que alguno de los bits de un gen se vea alterado debido a una mutación espontánea. Cada uno de los pasos consiste en una actuación sobre las cadenas de bits, es decir, la aplicación de un operador a una cadena binaria. Se les denominan, por razones obvias, operadores genéticos, y hay tres principales: selección, entrecruzamiento o recombinación y mutación, las cuales se detallan más adelante. Las ventajas de este heurístico son considerables. Primero, la evaluación de la función que determina la aptitud no necesita ser lineal, diferenciable o continua. Los parámetros como el tamaño de la población inicial, tasas de cruza y mutación, están bajo control del usuario; de esta manera, pueden ser manipuladas para alcanzar convergencia rápida o lenta. El método de solución es paralelo, es decir que se puede incrementar la rapidez al trabajar en varias máquinas. Otra ventaja es que pueden ser usados donde no se conozca alguna forma de resolver, pero se tenga una posibilidad de evaluar la solución, además de poder combinarse con otros algoritmos para formar métodos híbridos. Los algoritmos genéticos trabajan con varias soluciones de forma simultánea, siendo esta característica la más importante a considerar para la realización de este trabajo. Entre las desventajas se pueden mencionar son lentos, aunque en algoritmos híbridos han llegado a acelerar algunos métodos [31, 32]; pero esto se aminora sí la importancia de resolver el problema supera a la complejidad computacional.
36
Los Algoritmos Genéticos se mueven hacia encontrar óptimos, puede ser que el proceso de reproducción no destruya los patrones o esquemas que hacen que la población sobreviva, pero que si pueda combinarse con otros patrones que aseguren un óptimo (condiciones Teorema Fundamental propuesto por Goldberg en 1989), o cómo se ha investigado más recientemente [50] que se pueda romper con estos patrones pero seguir encontrando óptimos; Waelbroeck propone que los individuos ganadores no son aquellos con mejores propiedades de adaptación sino los sujetos a mutaciones. Un algoritmo genético convencional consta de los siguientes pasos:
• Generación de una población inicial de soluciones. Típicamente, el tamaño de la población es colocada aun un tamaño predeterminado de n, y los valores de los alelos son generados aleatoriamente. A esto se le conoce población inicial de la generación 1.
• Evaluación. Aquí se califica cada solución (individuo) por una función de aptitud. La función objetivo asociado con un carácter es, en general, la aptitud asociada con cada uno de ellos. Las soluciones no factibles, son típicamente penalizadas.
• Selección: Probabilistícamente, elegir de las soluciones actuales, los padres de la siguiente generación. El que tenga la aptitud más alta o menor (depende si es de maximizar o minimizar) tiene una probabilidad más alta de selección. Este operador es una versión artificial de la selección natural, una estrategia Darwiniana del individuo más apto. En las poblaciones naturales, la aptitud es determinada por la habilidad del individuo de sobrevivir a depredadores, clima, y otros obstáculos que les impiden crecer o reproducirse. El operador de reproducción puede ser implementado computacionalmente en muchas formas. Uno de los procedimientos más utilizados, es el denominado ruleta, en donde cada individuo tiene una sección circular de una ruleta que es directamente proporcional a su calidad. De esta forma, las cadenas con mayor aptitud tienen un mayor número de descendencia en las generaciones sucesivas. Otra forma es el torneo, en donde se elige un individuo de la población y se compara con otro elegido al azar, se seleccionar el individuo con el mayor o menor valor de aptitud y se pasa a las siguiente generación, con este método se asegura que los pobladores con mejores aptitudes estén en la generación siguiente.
• Entrecruzamiento: Para aplicar el entrecruzamiento, crossover o recombinación, se escogen aleatoriamente dos miembros de la población. No pasa nada si se cruzan dos descendientes de los mismos padres; ello garantiza la perpetuación de un individuo con buena puntuación, sin embargo, si esto sucede demasiado a menudo, puede crear problemas: toda la población puede aparecer dominada por los descendientes de algún gen, que, además, puede tener caracteres no deseados. Esos dos miembros de la población conocidos como “padres” se intercambian en un punto seleccionado al azar de un gen, de tal manera que el descendencia tenga una porción de cada padre. Los operadores de cruzamiento más utilizados son: a) de un punto: se elige aleatoriamente un punto de ruptura de los padres y se intercambian sus bits, b) de dos puntos: se eligen dos puntos de ruptura para intercambiar, c) uniforme: se genera un patrón aleatorio de 1s y 0s, y se intercambian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrón, o bien se genera un número aleatorio para cada bit, y si supera una determinada probabilidad se intercambia ese bit entre los dos cromosomas. d) PMX y SEX: son operadores más sofisticados que consisten en mezclar y aleatorizar los anteriores.
• Mutación: En la Evolución, una mutación es un suceso poco común (sucede aproximadamente una de cada mil replicaciones). En la mayoría de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es
37
decir, muy baja). Una vez establecida la frecuencia de mutación, por ejemplo, uno por mil, se examina cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus padres (normalmente se hace de forma simultánea al crossover). Si un número generado aleatoriamente está por debajo de esa probabilidad, se cambiará el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejará como está. Dependiendo del número de individuos que haya y del número de bits por individuo, puede resultar que las mutaciones sean extremadamente raras en una sola generación. No conviene abusar de la mutación. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la solución cuando un algoritmo genético está estancado, pero también es cierto que reduce el algoritmo genético a una búsqueda aleatoria.
Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes:
• Tamaño de la población: debe de ser suficiente para garantizar la diversidad de las soluciones, y, además, tiene que crecer más o menos con el número de bits del cromosoma, aunque nadie ha aclarado cómo tiene que hacerlo. Por supuesto, depende también del ordenador en el que se esté ejecutando.
• Condición de terminación: lo más habitual es que la condición de terminación sea la convergencia del algoritmo genético o un número prefijado de generaciones, sin embargo existen otros como la aptitud promedio generacional.
• Cruza: La cruza es otro paso importante para mejorar el funcionamiento de un Algoritmo Genético, la que es basada en el azar es usada ampliamente, pero métodos especializados eligen posiciones candidatas para la cruza para mejorar la convergencia del Algoritmo Genético.
• Probabilidad de mutación: El factor de mutación juega un rol importante para moverse de los óptimos locales y diversificar el espacio de búsqueda. Típicamente, una tasa pequeña (menor a .2) es usada para mutación, sin embargo, la selección de ésta depende del problema.
38
El funcionamiento general de un Algoritmo Genético puede ser representado como:
Figura 2.6. Funcionamiento de Algoritmos Genéticos. Los algoritmos genéticos han sido aplicados a muchos problemas de optimización combinatorios, Goldberg trabajo sobre el flujo de gas y petróleo; Davis y Storer, lo hicieron en programación de la producción; Whitley en el problema del agente viajero; David y Coombs [43] los aplicaron para decidir el tamaño de redes de comunicación, Chiang Fang Liaw [31] los utilizó para calendarizar trabajos que no tienen relaciones de precedencia entre las operaciones de cada uno, Casillas y Martínez [11] los utilizaron para hacer grupos (clusters) de documentos en línea, Daniel Huerta [29] los ocupó para penalizar problemas de calendarización de actividades, Joaquín Elorza[16] en el diseño de iluminación, Salvador Izquierdo Estallo [22] en la reducción de costos para chimeneas de diseño inverso. 2.4.4 Recocido Simulado Recocido Simulado es un procedimiento general de optimización para resolver problemas combinatorios, el cual está basado en técnicas aleatorias. Sin embargo, incorpora aspectos relacionados con algoritmos de mejoramiento iterativos. La aplicación de este tipo de algoritmos presupone la definición de una función de costo y un mecanismo de generación que marque la
no
no
si
no
si
fin
no
si
si
no
si
comienzo
Crear una población
inicial
¿La generación se puede mejorar?
fin
Seleccionar padres y
comparar los para elegir los de mayor (menor)
aptitud.
¿Son todos los individuos elegidos del tamaño de n?
Escoger aleatoriamente 2 miembros de la
población y utilizarlos para crear hijos
ubicando el lugar de cambio según la
probabilidad de cruza.
¿Son todos los individuos elegidos del tamaño de n?
¿Es la mutación de tasa x?
Mutar el hijo cambiando los alelos cuyos valores sean
ceros por uno y viceversa y colocarlo en la nueva población
¿Se ha alcanzado el criterio de paro?
39
transición de una solución dada a otra a través de un pequeño cambio. Este mecanismo de generación define las cercanas para cada solución, que consisten de todas aquellas que pueden ser alcanzadas con un cambio. Para mejorar estos algoritmos iterativos Kirkpatrick [26] introdujo la aceptación de transiciones que generaban un incremento en la función costo en forma limitada. Se le nombra recocido simulado por hacer una analogía con el proceso de calentar un sólido hasta que la que temperatura este a punto de cambiarlo de estado y después bajarla lentamente para encontrar un estado de energía baja, también se le da otros nombres como recocido Monte Carlo, enfriamiento estadístico o algoritmo de intercambio probabilístico. Las soluciones obtenidas por este método no dependen de la configuración inicial y tienen un costo usualmente cercano al mínimo [20], además es posible establecer límites superiores polinomiales para el tiempo de cálculo en algunas implementaciones del algoritmo. Metrópolis desarrollo un modelo basado en Monte Carlo simple para simular el comportamiento de átomos para alcanzar su equilibrio dado una temperatura inicial. El objetivo es encontrar la configuración del nivel mínimo de energía. Se comienza con un estado de energía inicial E0 y se aplica una perturbación al azar a la estructura. Sí esta perturbación resulta en un estado de energía más bajo, el proceso se repite con este nuevo estado de energía, si el resultado es más alto el nuevo estado es aceptado con una cierta probabilidad. El Recocido Simulado fue introducido como una técnica para resolver problemas complejos no lineales, es una emulación del proceso físico de agregar partículas en un sistema que se enfría. Bajando lentamente la temperatura, el intercambio de energía permite el equilibrio en cada etapa hasta que el nivel de energía mínimo es alcanzado. El cambio en el estado está basado en evaluar el nuevo estado con respecto a la función de Boltzman de la cual se habla más adelante. Cualquier mejoramiento factible es aceptado. Este aspecto del método permite al proceso moverse hacia una solución óptima local. Este método también es visto como un proceso probabilístico en donde un parámetro de control evalúa la probabilidad de aceptación PR(A) es denotada por exp( ∆ C/T) donde,
∆ C = valor mejor función objetivo a la fecha- valor de la función objetivo actual Para un problema de minimización ∆ C es negativo, así como T decrece, la probabilidad de aceptar una solución inferior decae exponencialmente. Johnson [24] presenta una clara analogía entre el sistema físico y ambiente simulado: Tabla 2.3 Analogía sistema físico y problema de optimización Sistema Físico Problema de Optimización Estado Solución factible Energía Costo Estado de la tierra Solución óptima Decremento rápido Buscado local Recocido simulado Recocido real
40
La técnica tiene poca memoria porque optimiza sin conocimiento anterior de la estructura del problema. Recocido Simulado utiliza las cadenas de Markov para proveer las condiciones suficientes y necesarias para una convergencia asintótica del algoritmo y el óptimo global. Este método [24] sirve para tratar con problemas de optimización combinatorio y estos son descritos como problemas NP, lo que significa que el tiempo para correr el algoritmo que garantice una solución óptima es una función exponencial del tamaño del problema. Recocido Simulado (SA) es una de las herramientas heurísticas diseñadas para dar una buena solución que no necesariamente sea la óptima con un tiempo de cálculo razonable. Supone que el espacio de solución S es la colocación finita de todas las soluciones y la función de costo f, es una función valuada real definida en los miembros de S. El problema es encontrar una solución o estado i ∈ S que minimice f sobre S. Sí una reducción en el costo es encontrada, la solución actual es reemplazada por el vecino generado, de otra forma la solución actual es retenida. Una forma de mejorar la solución es correr el algoritmo de forma descendente varias veces empezando desde diferentes soluciones iniciales y tomar el mejor con el mínimo local encontrado, en lugar de esto, el algoritmo te permite evitar estar atrapado en un óptimo local aceptando algunas veces un movimiento vecino que incrementa el valor de f. La aceptación o rechazo de este movimiento es determinado por una secuencia de números seleccionados al azar con una probabilidad controlada. La probabilidad de aceptar un movimiento causa un incrementoδ en f es llamada función de aceptación y es normalmente se denota por exp(-δ /T) donde T es un parámetro de control que corresponde a la temperatura en el anillado físico. . Metrópolis introdujo un algoritmo simple para simular una colección de átomos en una temperatura dada. En cada iteración, un átomo tiene un pequeño desplazamiento al azar y el cambio resultante δ en la energía del sistema es calculado. Si δ <0 el cambio resultante es aceptado, pero si δ >0 el cambio es aceptado con probabilidad de exp(-δ /kBt) donde T es la temperatura y kB es una constante física llamada la constante Boltzmann. Muchos parámetros en este algoritmo deben ser especificados: temperatura inicial (T), constante de Boltzmann kB y un criterio de paro. Una configuración inicial es necesaria para empezar el procedimiento de cambio que busca una mejor configuración. El criterio de paro afecta la calidad de la solución, tiempos de ejecución más largos dan con resultado una solución más favorable [20], sin embargo el rango de mejora tiende a disminuir después de un cierto punto y sólo una mejora pequeña adicional se gana. El número de iteraciones N (Época) a ser considerada en cada temperatura, es proporcional al tamaño del problema. El algoritmo se ejecuta hasta que se alcanza la temperatura final que corresponde en analogía a la temperatura de solidificación o enfriamiento. Para obtener una buena solución de calidad en un periodo corto de tiempo usando este algoritmo los parámetros deben ser seleccionados cuidadosamente [1], es decir que para un problema existen ciertos parámetros que son más apropiados que otros. En la siguiente figura se muestra el funcionamiento del algoritmo:
41
2.5 Distribución de Departamentos por Métodos Heurísticos En apartados anteriores se hablo sobre cómo resolver configuraciones de departamentos de área similar con algoritmos que han sido ampliamente demostrados a través de la literatura; sin embargo, como se pudo también notar, estos métodos comienzan a fallar al considerar áreas diferentes. Aquí es donde surge la importancia de los metaheurísticos, que son los que permiten dar una solución factible y muchas veces óptima, los algoritmos óptimos para resolver el
si
Hacer la SI=NS
no
si
no
si
no
Generar una solución
cercana (NS)
Evaluar la NS por medio de
la F.O.
¿Es la NS <SI?
Generar un aleatorio (X) y
compararlo con la probabilidad de aceptación (PA)
¿Es X < PA?
Conservar la SI
¿Se ha hecho por N?
si
Inicio
Definir temperatura inicial T y número de
iteraciones N
Definir la Función Objetivo
(F.O.)
Generar la solución
inicial=SI
Evaluar la SI por medio de
la F.O.
¿Se ha alcanzado el criterio de
paro?
Decremento de la
Temperatura
Fin no
Figura 2.7 Funcionamiento de Recocido Simulado.
42
problema de configuración son NP, así que la solución exacta solo es factible para pequeños problemas, es por esto que se usan los heurísticos [38]. Para constatar los alcances de éstos, se presentan a continuación algunos de los trabajos más relevantes. 2.5.1 Recocido Simulado 2.5.1.1 Células de Manufactura mediante Recocido Simulado Kar Yan Tam [46] presentó un procedimiento para colocar células de manufactura (de forma rectangular) utilizando recocido simulado. Este procedimiento toma en cuenta el tráfico entre células, la forma y tamaño de éstas, y las áreas ocupadas en piso. El objetivo es encontrar una distribución que minimice el flujo de partes, mientras que satisface las restricciones geométricas. Para el autor la distribución toma la forma de una estructura en donde recursivamente se parte un bloque rectangular. Cada partición corresponde al espacio destinado para una célula. También utilizan representaciones de árboles, siendo éstos binarios, cada nodo interno en esta estructura representa la dirección del corte en el área rectangular. Se genera un espacio de solución S, formado por todos los árboles posibles, dando estos los mismos departamentos diferentes distribuciones para las células. Aunado a esta representación, se manejan restricciones de área, para que el punto de corte no intervenga con el área requerida por cada célula y estas juntas justifiquen un área total, en este punto dan la facilidad de colocar una celda en un espacio fijo (fijado con anticipación) o hacerlo de forma libre; además de que asignan espacios a áreas ya ocupadas como elevadores columnas, etc., únicamente substrayéndolas del área total. La función objetivo del este procedimiento consiste en asignar espacio a las células de manufactura en donde las que tengan mayor tráfico se encuentren lo más cerca posible, de tal forma que cumplan con las restricciones de área y forma, ya teniendo una estructura, el problema es formulado como:
nji
oo
aaa
as
dvF
ii
ii
i
n
i
n
jijij
,...,2,1,
)50(max0
)49(maxmin
.
)48(min1 1
=≤≤
≤≤
=��= =
donde vij -tráfico de volumen entre la célula i y la j dij -distancia rectilínea entre los centroides de las particiones de la célula i y la j ai -radio de la partición que coloca a la célula i oi -radio de espacio muerto de la partición que coloca a la célula i ai
min -limite inferior de ai
aimax -limite superior de ai
oimax -limite superior de oi
n -número de células Las restricciones anteriores son convertidas a una función de penalización, cuyo objetivo es asignar pesos para permitir o no la distorsión de las células:
43
El espacio de soluciones S tiene 4n-1 posibles, una búsqueda exhaustiva no es permitida cuando n (número de células) es grande, para esto es usado el Recocido Simulado. Para implementar este heurístico utilizan como espacio de solución S y F como función de costo; por último se considera un programa de enfriamiento con los siguientes parámetros:
i) c0, un valor inicial de control. ii) L, longitud de la cadena de Markov iii) un factor para disminuir el valor de c iv) un criterio de paro v) una función de generación G
Aunque este método da buenos resultados para 20 células utilizando recocido simulado, su dificultad consiste en construir la estructura de corte, puesto que es necesario conocer técnicas numéricas para la construcción de árboles además de poder interpretarlas computacionalmente, otro factor difícil de establecer son los pesos βα
kk ww , . 2.5.1.2 CLASS: Soluciones computarizadas de distribución de departamentos usando Recocido Simulado. S. Jajodia y Joannis Minis propusieron un método [23] utilizando recocido simulado, para ellos el problema de configuración de departamentos consiste en determinar las posiciones relativas de las k entidades en el conjunto m1, m2, ...mk , que representan el conjunto de máquinas pertenecientes a una célula o a un conjunto de ellas, lo que se pretende en la función objetivo es minimizar la distancia total viajada por las partes entre departamentos, esta función es definida como:
)55(:min1
1 1ij
k
i
k
ijij dTE ��
−
= +=
=
Tij -es el número de transferencias (viajes requeridos) entre las entidades mi y mj. dij - es la distancia entre las entidades mi y mj, pudiendo ser calculada con la distancia
cartesiana o con la de Manhattan.
Cartesiana: [ ] )56()()(2/122
jijiij yyxxd −+−=
Manhattan: )57(jijiij yyxxd −+−=
xi -representa la coordenada x del centro geométrico de la entidad i.
yi -representa la coordenada y del centro geométrico de la entidad i.
{ }
nkji
ww
oo
aa
aa
aa
donde
wwdvF
kk
kkk
kkk
kk
kk
n
kkkkk
n
i
n
jijij
,...,2,1,,
0,
,0max
)1
,(min),1
,max(max,0max
)(min
max
maxmin
minmax
11 1
=≥
−=���
���
���
��� −
���
���
���
���−=
++= ���== =
βα
βα
β
α
βα(51)
(52)
(53)
(54)
44
Entre los parámetros que se utilizaron del problema se encuentran:
i) Espacio de solución: Consiste de una rejilla de k x k en donde a cada punto se le asigna un número de identificación.
ii) Cambios de configuración: son de dos tipos, un movimiento de una entidad de su posición actual a otra que esta desocupada o un cambio de posiciones entre dos de ellas.
iii) Recocido: sólo se menciona que se utiliza una temperatura inicial grande y un factor para disminuirla menor a 1.
iv) Criterios de aceptación para cambios de configuración: Se utiliza el criterio de Metrópolis, sí el cambio de configuración genera una minimización de la función objetivo se acepta; en caso contrario se acepta con una probabilidad de exp(-�E/t) donde �E representa un cambio en el valor de la función objetivo y t es la temperatura del sistema, para comparar esta probabilidad se genera un aleatorio entre 0 y 1.
Este algoritmo consiste en saber con seguridad el número de entidades envueltas en el problema y el tráfico que existen entre ellas. Se genera la rejilla k x k y se mide la distancia entre ellas usando cualquiera de las fórmulas de distancia, posteriormente las entidades son colocadas en esta rejilla al azar. Se calcula la función objetivo, y esta configuración inicial se guarda como el mejor. Se introduce el proceso de recocido simulado, se seleccionan dos posiciones del espacio de solución, por lo menos una de ellas debe contener una entidad, intercambiando los contenidos entre estas dos posiciones. Una vez que se tiene la nueva configuración se calcula el cambio en la función objetivo y se acepta la nueva con los criterios de aceptación antes mencionados; esto se hace hasta que no existan cambios significativos en la función objetivo. Un problema es que no se tiene contemplado de manera formal el traslape entre departamentos, es necesario que un área determinado puede ser dividida en bloques cuadrados del mismo tamaño, es decir no se es posible trabajar con áreas justas, incluso con lo que se prueba este algoritmo de forma sólida es con problemas de área similar; sin embargo este heurístico iguala las soluciones encontrados por métodos exactos. 2.5.1.3 Recocido simulado para la configuración de departamentos con maquinaria La formulación entera mixta desarrollada por Das en 1993 es adaptada para el problema de configuración de ciclo cerrado mediante recocido simulado, el funcionamiento de éste es comparada con el heurístico de cuatro pasos de Das y el de algoritmos genéticos propuesto por Rajasekharan en 1998. Corry y Kozan [14] proponen un nuevo método, en este caso se supone que las celdas son bloques rectangulares y los puntos de embarque están localizados en el eje horizontal o vertical. Un bloque celular consiste de un grupo de máquinas que son asignadas considerando el espacio para pasillos y de manejo de materiales. Oi es la distancia de los puntos de embarque al centro de la célula, hi y vi representan la longitud vertical y horizontal, respectivamente. La configuración debe ser diseñada de tal manera que el pasillo rodee a las máquinas y que dos celdas no se traslapen. Zi es una variable binaria que indica la orientación de la célula i(1, vertical 0, horizontal) y Iij es una variable que muestra la relación de interferencia entre dos células. Sí la variable binaria Iij =1, la interferencia entre la células I y J se considera alrededor del eje X, mientras que si Iij=0, se considera alrededor del eje Y; si no existe interferencia X o Y, las células están separadas. La distancia entre los puntos adyacentes de
45
embarque es estimando con la distancia rectilínea entre células adyacentes. La notación que define la formulación entera mixta es: N -número total de células. i,j: -índices para las células; i,j=1,...,N uij -volumen de tráfico esperado de la célula i a la j en unidades de carga Cij -costo por unidad de distancia para transportar una unidad de carga de las células i a la j. W -ancho de la célula. L -largo de la célula. (xi,yi) -coordenadas espaciales del centroide de la célula. (pxi,pyi) -coordenadas espaciales del centroide de la célula. Lni -variables binarias que indican las posición del punto de embarque, n=1,2,3,4. L1i=1 a la derecha del centro de la célula. L2i=1 abajo del centro de la célula. L3i=1 izquierda del centro de la célula. L4i=1 abajo del centro de la célula. �ij -variable binaria que indica la secuencia espacial horizontal �ij=1 si xi� xj (el centroide de la célula i está a la derecha del centroide de la célula j) 0, de otra manera. ßij -variable binaria que indica la secuencia espacial vertical ßij=1 si yi � yj (el centroide de la célula i está abajo del centroide de la célula j) 0, de otra manera. Eij(Fij) -el positivo (negativo) del componente xi-xj. Gij(Hij) -el positivo (negativo) del componente xi-xj. Pij(Qij) -el positivo (negativo) del componente pxi-pxj. Rij(Sij) -el positivo (negativo) del componente pyi-pyj. La formulación es:
{ }
)60(),(
)59(),(
.
)58()(
,...1;,...1),(
1 1
Φ∈−=−
Φ∈−=−
+++
+===Φ
��= +=
jiHGyy
jiFExx
as
SRQPuCMin
NijNiji
ijijji
ijijji
ijijijij
N
i
N
ijijij
46
)66(),()1(22
122
1
)65(),(22
122
1
)64(),()1(
)63(),(
)62(),()1(
)61(),(
Φ∈−−≥−−−−−
−+
Φ∈−≥−−−−−
−+
Φ∈−≤
Φ∈≤
Φ∈−≤
Φ∈≤
jiIMvZ
hZj
vZ
hZ
HG
jiMIvZ
hZj
vZ
hZ
FE
jiMH
jiMG
jiMF
jiME
ijjj
jii
ii
ijij
ijjj
jii
ii
ijij
ijij
ijij
ijij
ijij
β
β
α
α
{ }
)76(,0,,0
)75(1,0,2,1,,,,
)74(),(
)73(),(
)72(242
)71(2131
)70(1142
)69(131
)68(,...1)2()4(
)67(,...1)3()1(
LpyyWpxx
LLIZ
jiSRpypy
jiQPpxpx
TipoiZLL
TipoiZLL
TipoiZLL
TipoiZLL
NiOLOLypyi
NiOLOLxpx
iiii
ijijiji
ijijji
ijijji
iii
iii
iii
iii
iiiii
iiiiii
≤≤≤≤
∈
Φ∈−=−
Φ∈−=−
∈=+
∈−=+
∈−=+
∈=+
∈−+=
∈−+=
βα
El proceso de ciclo cerrado para acomodar las células consiste en determinar el tamaño del ciclo inicial. La suma de la longitud lateral de cada célula puede ser el tamaño más grande de ciclo, 25% de este valor puede ser un lado de ciclo; y este tamaño se reduce con ciertos procedimientos hasta el límite inferior de ciclo, que es la longitud lateral de su célula más pequeña. La colocación empieza en la esquina superior izquierda y se sigue llenado el espacio en sentido de las manecillas del reloj; sí al querer colocar la última célula ésta excede a la longitud del ciclo se deja fuera. La principal prioridad de orientación son los puntos de embarque y sirven para orientar la línea formada por el ciclo. Las células que quedaron fuera del ciclo son orientadas de acuerdo con sus puntos de embarque cerca de la línea de ciclo para reducir los costos por manejo de materiales.
47
El recocido simulado empieza con una solución inicial S (construida al azar) y el valor correspondiente de la función objetivo z. Dos celdas son seleccionadas al azar y se intercambian, se calcula el nuevo valor de la función objetivo y se compara con al anterior, si existe un decremento se acepta la nueva configuración, pero si existe un aumento se acepta con cierta probabilidad, se guarda el mejor hasta que se alcance el límite de temperatura y/o de iteraciones. Se obtuvieron buenos resultados comparados con los heurísticos hechos por Das y el método de algoritmos genéticos propuesto por Rajasekhran, a pesar de que se contaba con una máquina menos potente el tiempo en el cual se obtuvieron resultados fue menor con el de recocido simulado, sin embargo la función objetivo fue mejorada por el de algoritmos genéticos. La desventaja de éste método es que es necesario tener puntos de embarque necesariamente localizados en un punto, de modo que se puedan colocar para tener una ruta cíclica. 2.5.2 Algoritmos Genéticos 2.5.2.1 Distribución de departamentos de área desigual mediante algoritmos genéticos Este enfoque para crear configuraciones de áreas desiguales fue propuesto por Alice Smith y David M. Tate [36]. Ellos usaron la estructura por bahías desarrollada por Tong, en donde el área rectangular es dividida en una sola dirección en bahías de ancho variante, cada una de ellas es dividida en departamentos rectangulares de ancho igual, pero de diferente longitud. Se utilizaron dos cromosomas distintos para codificar las soluciones, el primer cromosoma tiene una permutación de los enteros 1 al n donde n es el número de los departamentos, consiste en leer la secuencia bahía por bahía de abajo hacia arriba, de izquierda a derecha. El segundo cromosoma contiene la codificación de un número de bahías y un registro de donde la secuencia entre ellas se rompe. Para crianza se ocupa una variante de cruce uniforme, cada localización en la descendencia es ocupada por un departamento de uno u otro padre con igual probabilidad, de tal manera que las localizaciones comunes del padre se transmiten a los hijos. El numero y localización de puntos de ruptura en la solución es tomada sin cambio de un padre o el otro con probabilidad igual. Los padres se seleccionan con un número al azar ente 1 y n donde n es el tamaño de la población, esto se hace para dar a la población la misma capacidad de reproducirse. Para mutación se definen tres operadores, uno que fractura la bahía existente en dos bahías adyacentes, o que fusiona dos bahías adyacentes en una y otra que revierte la secuencia de departamentos. Los parámetros se seleccionaron de forma experimental corriendo varias pruebas. Se usó una función de penalización, para obtener configuraciones reales, se estableció longitud y anchura máxima por departamento:
{ } { }
anchuraWi
longitudLi
WiLiWiLi
=== )77(,min/,maxα
cuando el radio � se vuelve más pequeño las soluciones factibles son más difíciles de encontrar, para determinar el mejor se realizaron pruebas con varios. También se utilizó una función de penalización para el algoritmo genético, para mutar todas la soluciones infactibles a factibles.
48
( ) ( ) )78()( allfeask
ii VVnnp −= ni - es el número de departamentos no factibles. Vfeas -es el valor de la mejor función factible Vall - es mejor de todos los encontrados K -es un parámetro que ajusta la severidad de la función de penalización , en este
caso k=3. Se obtuvieron soluciones factibles (cercanas al óptimo) con 10, 12, 20 departamentos, sin embargo fue necesario un estación de trabajo DEC-400 AXP para generarlos. 2.5.2.2. Diseño integrado de departamentos usando un enfoque evolutivo con un algoritmo de redes subordinado Este procedimiento fue propuesto por Bryan Norman y Alice E. Smith [37]. El razonamiento básico del que parte es que los departamentos deben ser rectangulares de un área específica y que los límites del área total son iguales o mayores a la suma de las de los departamentos. Su formulación es similar al de bahías flexibles en el trabajo propuesto por Tate y Smith, pero es más restrictiva con respecto a las estructuras de corte. Se forman las bahías de área desigual cortando en una sola dirección, las bahías luego se subdividen en departamentos. Al codificar estas bahías se puede forzar a cumplir formas y áreas de departamentos. Para encontrar una configuración de departamentos óptima o cercana al óptimo, se utiliza un algoritmo genético. Éste trabaja con una longitud variable donde existe correspondencia entre la codificación y la distribución; excepto para aquellas que son simétricas. Esta codificación consiste en una permutación de departamentos que especifica su orden en la configuración, con un carácter concatenado que indica dónde se rompe la bahía para que la configuración sea posible. Mientras que la codificación de los departamentos necesarios es fija, dónde se rompen no lo es y se puede considerar cualquier valor desde cero hasta n (número de departamentos). La cruza que utilizan es una variación de la uniforme, de esta manera dos padres crean un solo hijo. La secuencia de los departamentos está sujeta a la uniforme para asegurar que solo existan soluciones factibles. La estructura de bahía es tomada directamente de un padre a otro con igual probabilidad. La mutación puede consistir en permutar 50%, aumentar o borrar 25% el rompimiento de una bahía; la mutación de permutación es invertir dos departamentos seleccionados al azar. La cruza y la mutación son independientes uno de la otra. Para interpretar la función objetivo se consideran puntos de entrada y/o salida, siendo los potenciales donde se puede interceptar la esquina de un departamento adyacente. Sí cada departamento tiene un número no restringido de estas estaciones, la distancia de pasillos interdepartamental puede ser encontrada formulándolo como un problema de ruta más corta. La función objetivo del algoritmo genético es:
)79()()(1 1
3allfeas
n
jkj
kjkjk ZZmdFZ −+=∏ ��
=≠=
m -número de departamentos en el layout � que violan restricciones de largo o ancho mínimos.
Zfeas -valor de la función objetivo para la mejor solución factible
49
Zfeas -valor de la función objetivo para la mejor solución factible sin penalizar. djk -es la distancia rectilínea más corta a través de los perímetros departamentales entre las
estaciones de los departamentos j y k encontrado por el algoritmo de ruta más corta. m - el número de departamentos no factibles en la configuración, que no cumplan con
restricciones de área La función de penalización es una variante de la propuesta por Smith. Tiene la propiedad de reconfigurarse usando una búsqueda hacia atrás, obteniendo la diferencia relativa entre la mejor factible y las infactibles e incluye una distancia métrica (en este caso el número de departamentos no factibles en la configuración, que no cumplan con restricciones de área). Una vez creada la población inicial y hacerles cruza uniforme, se evalúa la configuración actual, se calcula el número de departamentos infactibles; con esto se construye una red de nodos correspondiente a cada departamento en el diseño, se encuentra la ruta más corta con el algoritmo de Floyd Warshall y se usan las distancias para calcular la función objetivo. Una vez hecho esto se continúa con el algoritmo genético reemplazando el peor cromosoma en la población actual con su descendiente, se selecciona un individuo al azar usando su respectiva tasa, se evalúan de nuevo los mutantes, se reemplazan los peores cromosomas con los mutantes. Los parámetros utilizados en este algoritmo fueron similares a los de Tate y Smith, tamaño de población 10, tasa de mutación del 50% y número de soluciones (descendencia y mutantes) igual a 600,000 para el problema de Armour y Buffa de tamaño 20. Se lograron buenas configuraciones, sin embargo, las soluciones que encuentra se limitan a cuando los pasillos están de forma externa en los departamentos. Aunque con las mismas limitaciones respecto a los pasillos externos, Smith y Norman hicieron una variación de este proyecto [49]; sin embargo, sin tener problemas en cuanto a la construcción de las bahías o estructuras de corte. El problema esta relacionado con uno de asignación cuadrática y se manejan las siguientes variables: Xi,k -Variable binaria, sí el departamento i usa la localización candidata k, zero de otra manera. Xi,k,j,l -Variable binaria que es igual a 1 sí el departamento i usa la localización k, el
departamento j la l, cero de otra manera. Indica la ruta que es usada para mover material del departamento i al j.
di,k,j,l -la distancia de la localización k en el departamento i a la localización l en el departamento j.
d_costij-distancia del departamento i al j usando el procedimiento de puntos. Loci -conjunto de localizaciones candidatas para el departamento i. fij -el flujo entre los departamentos i y el j n -Número de departamentos a asignar El objetivo del problema de optimización es minimizar el producto de los flujos por la distancia, donde los flujos están fijos, pero las distancias dependen de los puntos (localizaciones) situadas en cada departamento. De esta forma el problema puede ser representado como:
50
)84(,...1,,...1cos_
)83(,,...1,,...1
)82(,...1,,...11
)81(,...11..
)80(cos_
,,,,,,,
,,,,,
,,,
1 1
NjNitddx
LoclLockNjNixx
NjNix
Nixas
tdfMin
jik l
ljkiljki
jikiljki
k lljki
Lockik
N
i
N
jijij
i
==∀=
==∀≤
==∀=
=∀=
��
��
�
��
∈
= =
Las tres últimas restricciones pueden ser reemplazadas con la siguiente, sin embargo es no lineal y entera lo que la hace difícil de resolver:
)85(,...1,,...1cos_ ,,,,,, NjNitddxxk l
jiljkiljki ==∀=��
Se utiliza el algoritmo de Floyd-Warshall para encontrar la distancia más corta. La complejidad de este problema radica en que cada departamento tiene sus puntos de entrada y salida independiente de los otros, el número total de posibles combinaciones crece de forma exponencial. Para lidiar con la complejidad de este problema, se compararon dos metaheurísticos Recocido Simulado con factor de enfriamiento de 0.9, temperaturas de 100 a 10 y con 1400 movimientos entre ellas; un algoritmo genético cuya codificación son el punto de entrada o salida en que se ubica cada departamento, siendo su aptitud el costo del flujo de material; se utiliza un tipo especial de selección, cruza y mutación. Se resolvieron problemas de 10, 14, 20, 30 departamentos. Lo resuelto mediante algoritmos genéticos supero notablemente al recocido simulado.
Tabla 2.4 Comparación de Enfoques para el Problema de Distribución de Departamentos.
NOMBRE AUTOR PROBLEMA SUPOSICIONES METODOLOGÍA USADA
Células de Manufactura mediante Recocido Simulado
Kar Yan Tam (1992)
Colocar células de manufactura de forma rectangular El objetivo es encontrar una distribución que minimice el flujo de partes, mientras que satisface las restricciones geométricas. Problemas de hasta 20 células.
• La distribución toma la forma de una estructura en donde recursivamente se parte un bloque rectangular.
• Se utilizan representaciones de árboles, siendo éstos binarios, cada nodo interno en esta es-tructura representa la dirección del corte en el área rectangular.
Recocido simulado
51
• Se manejan restric-ciones de área y forma.
• Factores difíciles de establecer: estructuras de corte y pesos
βαkk ww , .
CLASS: Soluciones computarizadas de distribución de departamentos usando Recocido Simulado.
S. Jajodia y Joannis Minis (1991)
Consiste en determinar las posiciones relativas de las k entidades en el conjunto m1, m2, ...mk , que representan el conjunto de máquinas pertenecientes a una célula o a un conjunto de ellas, lo que se pretende en la función objetivo es minimizar la distancia total viajada por las partes entre departamentos.
• Se considera un espacio de solución que puede dividirse en rejillas del mismo tamaño k x k..
• Sólo se puede mover una entidad de una localización a otra que esta desocupada, o hacer e intercambio entre 2, lo que nos habla de que los departamentos son de la misma área.
• Sí los departamentos son de áreas diferentes se traslapan.
Recocido simulado
Recocido simulado para la configuración de departamentos con maquinaria
Corry y Kozan (2000)
Las celdas son bloques rectangulares y los puntos de embarque están localizados en el eje horizontal o vertical. Un bloque celular consiste de un grupo de máquinas que son asignadas considerando el espacio para pasillos y de manejo de materiales.
• La configuración debe ser diseñada de tal manera que el pasillo rodee a las máquinas y que dos celdas no se traslapen. Puntos de embarque son nece-sarios.
• Se considera el espacio como un ciclo cerrado para acomodar las células
• La principal prioridad de orientación son los puntos de embarque
Se obtuvieron resul-tados menores con el de recocido simulado, sin embargo la función objetivo fue mejorada por el de algoritmos genéticos.
Distribución de departamentos de área desigual mediante
Alice Smith y David M. Tate (1992)
Distribución de departamentos de áreas desiguales, utilizando codificación por bahías.
• el área rectangular es dividida en una sola dirección en bahías de ancho variante,
Algoritmos Genéticos
52
algoritmos genéticos
Se obtuvieron soluciones factibles (cercanas al óptimo) con 10, 12, 20 departamentos, sin embargo fue necesario un estación de trabajo DEC-400 AXP para generarlos.
cada una de ellas es dividida en departamentos rectangulares de ancho igual, pero de diferente longitud
• Se usó una función de penalización, para obtener configuraciones reales, se estableció longitud y anchura máxima por departamento.
• También se utilizó una función de penalización para el algoritmo genético, para mutar todas la soluciones infactibles a factibles
Diseño integrado de departamentos usando un enfoque evolutivo con un algoritmo de redes subordinado
Bryan Norman y Alice E. Smith (1998)
Distribución de departamentos que deben ser rectangulares de un área específica, los límites del área total son iguales o mayores a la suma de las de los departamentos Configuraciones cercanas al óptimo para problemas de menos de 20 departamentos, tamaño de población de 600,000.
• Su formulación es similar al de bahías flexibles en el trabajo propuesto por Tate y Smith, pero es más restrictiva con res-pecto a las estructuras de corte
• La codificación consiste en una per-mutación de depar-tamentos que especi-fica su orden en la configuración.
• Para interpretar la función objetivo se consideran puntos de entrada y/o salida, siendo los potenciales donde se puede interceptar la esquina de un departamento adyacente, siendo éste un problema de ruta más corta.
• Los pasillos están de forma externa
Algoritmos Genéticos
53
en los departamentos.
Diseño integrado de departamentos usando un enfoque evolutivo con un algoritmo de redes subordinado (variación)
Bryan Norman y Alice E. Smith (1999)
Distribución de departamentos que deben ser rectangulares de un área específica, los límites del área total son iguales o mayores a la suma de las de los departamentos Problemas de 10, 14, 20, 30 departamentos
• Los pasillos están de forma externa en los departamentos.
• El problema esta relacionado con uno de asignación cuadrá-tica.
• Se utiliza el algoritmo de Floyd-Warshall para encontrar la distancia más corta. La complejidad de este problema radica en que cada departamento tiene sus puntos de entrada y salida independiente de los otros, el número total de posibles combinaciones crece de forma exponencial.
Se comparó Recocido Simulado con Algoritmos Genéticos, la función objetivo fue mejorada por este último.
2.6 Objetivos Antes de empezar a trabajar fue necesario determinar los objetivos principales:
• Entender las implicaciones del problema de acomodo de departamentos, es decir, como afecta el minimizar los costos al funcionamiento general de la empresa.
• Analizar el modelo de Castillo [12] para comprender porque sólo puede resolver problemas pequeños (menos de 9 departamentos).
• Generar una metodología que nos permita resolver problemas de mayor tamaño utilizando Algoritmos Genéticos.
• Experimentar con los parámetros de torneo, mutación, cruza para ver en que casos se llega más rápido (menores generaciones) al resultado.
• Dejar bases que puedan ayudar a investigaciones posteriores.
54
3 Planteamiento del Problema. La distribución de departamentos pertenece a la familia de problemas de optimización que involucran la partición de una región plana de dimensiones conocidas (usualmente rectangulares) en departamentos de área conocida [38], para minimizar los costos asociados con la interacción entre ellos. Estos costos pueden representar costos de transporte (incluyendo aquellos por el sistema de manejo de materiales) o cualquier puntaje de preferencia de acuerdo con la adyacencia entre departamentos. Como ya se ha mencionado, todos estos problemas se consideran como NP Completos [38]. Un problema de distribución de departamentos puede ser clasificado [14] como 1) general en donde sólo se considera el área de los departamentos o 2) un problema de configuración con máquinas, en donde se considera la forma específica que tienen éstas. En este trabajo se abordará el caso 1. Como se pudo observar se ha trabajado el problema de áreas desiguales basados en enfoques de teoría de grafos (Foulds [16], Seppanen y Moore[44]) y representaciones discretas que dividen el área en rejillas de cuadrados iguales (Bazaara[3] y Hassan [18]). Recientemente la atención está puesta para encontrar la solución directa, Meller [33], Lacksonen [29], Anjos y Vanelli [12], Tam y Li [45] , van Camp [49] y Castillo [12]. En este sentido, se ha estado trabajando de forma extensa para resolver el modelo de departamentos múltiples con optimización lineal. La motivación surge de la aparición de paquetes computacionales para resolver programación entera mixta o lineal como CPLEX [12]. Montreuil trató de linealizar el problema [35] al poner límites al perímetro de cada departamento, desafortunadamente se acarreaban grandes errores en el área final de cada departamento. Meller [33] hizó lo mismo pero aumentó una variable real para cada departamento. Tompkins observó en general que una restricción que limitara el perímetro incrementaba el número de soluciones factibles, el número de restricciones también era aumentado y al final no se cumplía con el área final. Para limitar la violación del área Lacksonen [29] propone una linealización del área actual aumentando dos variables binarias para cada departamento, sin embargo su aplicación es limitada. En contraste con las investigaciones anteriores Anjos y Vanelli [12], Tam y Li [45] y van Camp [49] proponen métodos de solución que usan la restricción no convexa y hiperbólica de área wih
i =ai . Tam y Li, y van Camp proponen procedimientos de optimización que transforman el problema no lineal de restricto a no restricto utilizando métodos de penalización de funciones. Anjos y Vanelli propusieron un modelo de optimización con restricciones complementarias usando un heurístico de programación no lineal para obtener una solución. Todo estos utilizan restricciones de área no convexas e hiperbólicas, sin embargo sólo se encuentra un mínimo local que las satisface [12]. Castillo en 2003 [12], logró un modelo de programación mixta entera que encuentra soluciones óptimas con un grado de error E. El aspecto básico de este modelo consiste de una representación de las restricciones no convexas y hiperbólicas que aseguren la solución óptima bajo un error muy pequeño. Esta representación está basada en la generación de ciertos planos de corte para cada departamento y garantiza que en el óptimo se cumplirá con la restricción de área
55
bajo un cierto grado de error. Esta representación es puramente lineal. Los resultados que logró fueron muy buenos logrando soluciones óptimas para problemas de menos de 10 departamentos debido a la complejidad de las variables binarias que se detallarán más adelante. La cantidad de variables binarias y de restricciones aumentan a la vez que el número de departamentos, tanto que se hace complicado que paquetes computacionales como CPLEX resuelvan el problema de forma óptima. Sin embargo una vez que estas variables tienen valores dados, se reduce la complejidad del problema. Por otra parte, tener un conjunto de soluciones no óptimas pero si muy buenas puede ayudar a la empresa a ser mucho más flexible en el acomodo de sus departamentos. La contribución de este trabajo será buscar estas variables binarias mediante algoritmos genéticos para que al tener un valor dado puedan introducirse en el modelo y así obtener un conjunto de soluciones que se acerquen al óptimo no sólo para problemas pequeños (menores a 10 departamentos). Esto les será útil a las empresas para considerar distintas opciones de acomodo y elegir las que mejor se adapten a sus necesidades. Adicionalmente, se tratará de evaluar que tipo de algoritmo genético servirá dado el problema, es decir, determinar los valores de los parámetros y cómo puede ayudar hacerlo híbrido con otro método como recocido simulado. Dada la complejidad computacional de tomar el modelo-E se trabaja únicamente con el modelo genérico de Castillo [12]. Anteriormente ya se han ligado técnicas de Inteligencia Artificial (IA) con Programación Matemática [23]. En este sentido las técnicas de IA pueden ser usadas para formular e interpretar los problemas de programación matemática, o ésta última para asegurarse que los sistemas IA están generando soluciones óptimas. Pero el enfoque más reciente es resolver problemas más complejos utilizando IA para resolver parte de ellos y después ligarlos con enfoques de programación matemática que puedan generar soluciones óptimas mejorando la calidad computacional. Winston en 1984 observó que el objetivo de la IA es hacer más útiles a los computadores y es lo que pretende en este proyecto mediante el uso de Algoritmos Genéticos, ocuparlos para resolver una parte de la formulación del problema de programación lineal. El objetivo de este trabajo, como se detalla en el apartado 3.5 es minimizar el costo de flujo de material entre los departamentos; hasta ahora sólo se ha hecho en problemas menores a 10 departamentos, pero se pretende que mediante el uso de algoritmos genéticos una mayor cantidad de departamentos puedan ser distribuidos. El costo ocupado será el de manejo de materiales. Se utilizará la distancia rectilínea, porque para espacios en los que se requieran divisiones y corredores es más realista. Sin embargo para casos en donde se requiera la euclidiana, Cheng y Ku y Weis [49] han demostrado basados en experimentos computacionales que las dos medidas convergen especialmente cuando las dimensiones del problema crecen, para este caso se considera la distancia rectilínea entre centros.
Figura 3.1 Distancia Rectilínea
xi xj
yi
yj
56
3.5 Modelo Genérico
Suponga que es necesario encontrar las posiciones y las dimensiones de ancho y longitud por departamento, cuyas áreas son desiguales. El área total de la planta es un rectángulo de área wF x hF, para cada departamento su posición está dada por las coordenadas de su centro (xi , yi ) y sus dimensiones de ancho y alto como wi y hi respectivamente. De esta forma hay cuatro variables de decisión. Cada departamento i tiene área ai y radio de �i �1 donde por razones prácticas, se delinea el máximo radio permisible entre las dimensiones más cortas y más largas,
{ } { } Nihwhw iiii ,....1,,min/,max =≥α . Adicionalmente, se denotan los límites superiores e inferiores wi y hi como (wi
bajo, wi alto) y (hi
bajo, hi alto) respectivamente. Dada la relación de flujo
de materiales o adyacencia entre departamentos denotada como cij entre los departamentos i y j, donde cij �0 y cij = cji y cii =0, se formula el problema como:
)(,...,1021
)(,...,121
)(,...,1021
)(,...,121
)(,...,1,..
)()(min1
1 1
fNihy
eNihhy
dNiwx
cNiwwx
bNiahwas
ayyxxc
ii
Fii
ii
Fii
iii
ji
N
i
N
iijiij
=≥−
=≤+
=≥−
=≤+
==
−+−��−
= +=
{ }
{ } )(,11,0
)(,11,0
)(,...,1
)(,...,1
)(,1)2()()(21
)(,1)1()()(21
)(,1)1()()(21
)(,1)()()(21
lNjiY
kNjiX
jNihhh
iNiwww
hNjiYXhyyhh
gNjiYXhyyhh
hNjiYXwxxww
gNjiYXwxxww
ij
ij
altoii
bajoi
altoii
bajoi
ijijFijii
ijijFjiji
ijijFijii
ijijFjiji
≤≤≤∀∈
≤≤≤∀∈
=≤≤
=≤≤
≤≤≤∀−−≤−−+
≤≤≤∀+−≤−−+
≤≤≤∀−+≤−−+
≤≤≤∀+≤−−+
La figura 3.2 ilustra las combinaciones de wi y hi que son factibles a las restricciones (b), (i) y (j). Estas combinaciones entre altura y ancho se encuentran en la curva no convexa e
57
hiperbólica entre los puntos representados como P1=(wi bajo, hi
alto) y P2=( wi alto, hi
bajo), donde wi bajo =hi
bajo = iia α/ y wi alto =hi
alto = iia α .
Figura 3.2. Combinaciones de wi y hi
El problema esta sujeto a dos tipos de restricciones: (1) requerimientos de área por departamento y total y (2) restricciones de localización de departamentos, éstos no se pueden traslapar y deben ser puestos dentro de la configuración. Las del tipo (1) son de la (c)-(f) y aseguran que el lado derecho de un departamento este a la izquierda del lado derecho de la planta y el lado izquierdo esta a la derecha de la pared izquierda de la planta. De forma similar aseguran que la pared superior de cada departamento este debajo de la superior de la planta, la pared inferior debe estar arriba de la inferior de la planta. Las del tipo (2) son de la (g)-(h) y aseguran que no exista traslape entre departamentos, para entenderlas mejor es necesario referirse a Camp [49] debido a que maneja el mismo tipo de restricciones:
0)(21
0)(21
0)(21
0)(21
<+−−≥+−−
<+−−≥+−−
jijijiji
jijijiji
wwxxsihhyy
hhyysiwwxx
Estas restricciones aseguran que sí la distancia entre los centros de dos departamentos en la dirección y es menor que el promedio de sus alturas, no se pueden traslapar en la dirección x, y viceversa. De esta forma para hacer la relación Castillo introduce un conjunto de variables binarias, tomando las cuatro restricciones:
58
)(,1)2()()(21
)(,1)1()()(21
)(,1)1()()(21
)(,1)()()(21
hNjiYXhyyhh
gNjiYXhyyhh
hNjiYXwxxww
gNjiYXwxxww
ijijFijii
ijijFjiji
ijijFijii
ijijFjiji
≤≤≤∀−−≤−−+
≤≤≤∀+−≤−−+
≤≤≤∀−+≤−−+
≤≤≤∀+≤−−+
Esto se hace para asegurar que 3 de las 4 cumplan en cada caso, las de Camp también pueden ser expresadas como:
0)()(21
0)()(21
0)()(21
0)()(21
>−−+≤−−+
>−−+≤−−+
jijijiji
jijijiji
xxwwsiyyhh
yyhhsixxww
Existen cuatro combinaciones posibles: Xij Yij Caso 1 0 0 Caso 2 1 0 Caso 3 0 1 Caso 4 1 1 Sí tomamos las restricciones (g) y (h) quedaría: Caso 1
)(,1)()(21
)(,10)()(21
hNjihyyhh
gNjixxww
Fjiji
jiji
≤≤≤∀≤−−+
≤≤≤∀≤−−+
El promedio de los anchos menos la distancia entre los centros es menor o igual que cero, por lo tanto la restricción (h) según las restricciones de Camp debe ser mayor a cero, lo cual es posible dado que hF mayor que cero. Caso 2
)(,10)()(21
)(,1)()(21
hNjiyyhh
gNjiwxxww
jiji
Fjiji
≤≤≤∀≤−−+
≤≤≤∀≤−−+
El promedio de las alturas menos la distancia entre los centros en y es menor o igual que cero, por lo tanto la restricción (g) según las de Camp debe ser mayor a cero, lo cual es posible dado que wF mayor que cero.
59
Caso 3
)(,12)()(21
)(,1)()(21
hNjihyyhh
gNjiwxxww
Fjiji
Fjiji
≤≤≤∀≤−−+
≤≤≤∀≤−−+
El promedio de los anchos menos la distancia entre los centros en x es menor o igual que wF, por lo tanto la restricción (h) debe ser mayor a esta cantidad, lo cual es posible dado que 2hF será mayor que wF. Caso 4
)(,1)()(21
)(,12)()(21
hNjihyyhh
gNjiwxxww
Fjiji
Fjiji
≤≤≤∀≤−−+
≤≤≤∀≤−−+
El promedio de las alturas menos la distancia entre los centros en y es menor o igual que hF, por lo tanto la restricción (g) debe ser mayor a esta cantidad, lo cual es posible dado que 2wF seguramente será mayor que hF. Otra connotación de las variables binarias se refiere a la ubicación especial de un departamento con respecto a otro. En la figura 3.3 se muestran las ubicaciones que dan éstas a otro departamento con respecto al que está en el centro.
Figura 3.3 Connotación gráfica de las variables binarias Para relacionar cada par de departamentos existe una variable binaria X y Y, y juntas al cumplir todas las restricciones del problema dan soluciones factibles o la óptima para una configuración determinada. Para clarificar cómo se abordará mediante Algoritmos Genéticos este problema, se presenta a continuación una configuración específica para 7 departamentos presentada por Castillo [12]: Tabla 3.1 Requerimientos de área total y por departamento. Ancho Total Máximo wF 12
Largo Total Máximo hF 5Dept. 1 2 3 4 5 6 7Ancho min w i
bajo 2.8000 2.0000 1.8000 1.2247 2.0000 5.0000 5.0000
Ancho max w imax 7.4833 6.3246 6.0000 4.8990 6.3246 10.0000 10.0000
Altura min hibajo 1.8708 1.5811 1.5000 1.2247 1.5811 2.5000 2.5000
Altura max hialto 5.0000 5.0000 5.0000 4.8990 5.0000 5.0000 5.0000
(1,1) (1,1)(0,0) (1,1) (0,1)
(0,0) (0,1)(1,0) (0,1)(0,0) (1,0) (1,0)
60
Tabla 3.2 Costo de manejo de material: problema de 7 departamentos
Dept. 1 2 3 4 5 6 71 ------- 2.40 0.00 0.00 0.00 0.00 0.002 ------- 0.00 0.00 0.00 0.00 7.003 ------- 12.00 0.00 0.00 0.004 ------- 12.00 0.005 ------- 6.00 0.006 ------- 0.007 -------
Nota: cuesta mover lo mismo en la dirección x, que en la y.
Esta formulación se corrió en CPLEX a través AMPL. La solución óptima que arrojó se muestra a continuación: Minimización Z = 83.5397 Tabla 3.3 Variables de decisión- 7 departamentos. Tabla 3.4 Variables binarias- 7 departamentos.
x1 4.9000 y1 0.9354 w1 2.8000 h1 1.8708x2 2.5000 y2 1.0803 w2 2.0000 h2 1.5811x3 7.9877 y3 1.7500 w3 1.8000 h2 1.5000x4 9.5000 y4 1.8877 w4 1.2247 h4 1.2247x5 6.0000 y5 3.7500 w5 2.0000 h5 1.5811x6 9.5000 y6 3.7500 w6 5.0000 h6 2.5000x7 2.5000 y7 3.1208 w7 5.0000 h7 2.5000
11 X12 02 Y12 0 23 X13 0 13 X23 04 Y13 1 14 Y23 1 35 X14 0 15 X24 0 23 X34 06 Y14 1 16 Y24 1 24 Y34 1 47 X15 1 17 X25 1 25 X35 1 31 X45 08 Y15 1 18 Y25 1 26 Y35 1 32 Y45 0 59 X16 1 19 X26 0 27 X36 1 33 X46 1 37 X56 0
10 Y16 1 20 Y26 1 28 Y36 1 34 Y46 1 38 Y56 1 611 X17 1 21 X27 1 29 X37 0 35 X47 0 39 X57 0 41 X67 012 Y17 1 22 Y27 1 30 Y37 0 36 Y47 0 40 Y57 0 42 Y67 0
61
Figura 3.4 Configuración óptima- 7 departamentos. Tal como se había mencionado, una combinación exacta de variables binarias arroja una configuración determinada. Para efectos de la búsqueda con Algoritmos Genéticos, el espacio de soluciones tiene 242 = 4.398046511X1012 posibles (42 variables binarias para 7 departamentos), una búsqueda exhaustiva es compleja en este caso. A mayor número de departamentos el problema sigue creciendo, lo cual hace aún más difícil la búsqueda exhaustiva, por ejemplo para calcular la cantidad de variables binarias:
• Para 7 departamentos [ ] 42)2(123456 =+++++ • Para 8 departamentos [ ] 56)2(1234567 =++++++ • Para 12 departamentos [ ] 132)2(1234567891011 =++++++++++
De lo anterior se puede deducir la fórmula general para calcular el número de variables binarias según los departamentos: [ ] )2())1(...()3()2()1( −−+−+−+− nnnnn En la siguiente gráfica se muestra como crece el número de combinaciones según la cantidad de departamentos: Tabla 3.5 Combinaciones variables binarias Departamentos Variables Combinaciones Binarias
7 42 4.39805E+128 56 7.20576E+169 72 4.72237E+21
10 90 1.23794E+2711 110 1.29807E+3312 132 5.44452E+3913 156 9.13439E+4614 182 6.12998E+5415 210 1.6455E+6320 380 2.4626E+11425 600 4.1495E+18030 870 7.8722E+261
62
11E+221E+441E+661E+88
1E+1101E+1321E+1541E+1761E+1981E+2201E+2421E+264
0 5 10 15 20 25 30 35
Departamentos
Com
bina
cion
es (e
scal
a lo
garí
tmic
a)
3.2 Búsqueda de las variables binarias mediante Algoritmos Genéticos De forma general, este proceso se describe como sigue:
c
no
si
si
si
si
no si
no
si
Elegir Y Elegir X
Decidir el lugar de
cruza
inicio
Generar la población inicial (N)
Evaluar cada
individuo
¿La generación se puede mejorar?
¿Es la aptitud del X<Y?
¿Son los individuos del tamaño de N?
Generar aleatorio
p/ind
¿Es este número< probabilidad de cruza?
Ponerlo en la lista de
padres
Seleccionar dos padres
Elegir de las lista 2 individuos
Intercambia los
cromosomas para forma 2
nuevos individuos
Generar aleatorio
p/ind
¿Es este número< probabilidad de mutación?
Cambiar ceros por
unos y viceversa
Actualizar la nueva
población
¿Se ha alcanzado el número de generaciones?
fin
a a
a
b
b
c
fin
Gráfica 3.1. Combinaciones variables binarias
63
Generación de la población Esta población se genera al azar, el único requerimiento es que los genes sean la misma cantidad de variables binarias, por ejemplo sí son 42 variables: Figura 3.6. Representación de un individuo. Lo anterior representa un individuo, cada alelo es el valor de una variable binaria dentro del modelo genérico antes descrito, en este caso: Tabla 3.5 Valor de las variables binarias según representación Evaluación de cada individuo Todos los individuos de la generación inicial son evaluados mediante CPLEX, el valor de las variables binarias es introducido como parámetro, una vez obtenida la solución se asigna la aptitud a cada integrante de la población. Selección El tipo de selección utilizada es por torneo, a continuación se describe de forma general este proceso cuando el tamaño de torneo es igual a 2.
1 X12 02 Y12 13 X13 0 13 X23 04 Y13 1 14 Y23 15 X14 1 15 X24 1 23 X34 06 Y14 1 16 Y24 1 24 Y34 17 X15 0 17 X25 0 25 X35 1 31 X45 18 Y15 1 18 Y25 0 26 Y35 1 32 Y45 09 X16 1 19 X26 1 27 X36 1 33 X46 0 37 X56 1
10 Y16 1 20 Y26 0 28 Y36 1 34 Y46 1 38 Y56 011 X17 0 21 X27 1 29 X37 0 35 X47 0 39 X57 1 41 X67 112 Y17 1 22 Y27 0 30 Y37 0 36 Y47 1 40 Y57 0 42 Y67 0
0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0
Generar n números aleatorios
Multiplicar por num de variales
binarias
Seleccionar posición
Intercambiar 0 por 1 y viceversa
Evaluar al individuo
Aptitud nueva < anterior
Actualizar población *
Seleccionar nuevo individuo
Generar aleatorio
Posición = n
Prob. Aceptac. > aleatorio
si no
c
si
no
no si
Figura 3.5 Funcionamiento del algoritmo genético, recocido simulado en la búsqueda local
64
• Se comparan las aptitudes del el poblador 1 con otro elegido al azar, en este caso para elegir al menor se utiliza )1/(1 +f , donde f es la aptitud del individuo.
Caso 1: Las dos aptitudes son iguales a cero, en este caso se puede elegir cualquiera, la aptitud normalizada es igual a 1, se mantiene la población y se desecha el individuo de la población de torneo. Caso 2: La aptitud de la población es igual a cero, la de torneo es diferente. Se elige la de torneo. Caso 3: La aptitud de la población es diferente de cero, la de torneo es cero. Se elige la de población. Caso 4: Las dos aptitudes son diferentes de cero, al normalizarlas queda mayor la que minimiza la función objetivo, se escoge esa ya sea la de la población o la guardada en la posición de torneo. • Terminado esto sólo se tiene la mitad de la población, se repite el proceso una vez
más. Cruza Se escogen de forma aleatoria varios individuos que forman una lista de padres. Esto se hace asignando a cada individuo un número aleatorio y comparándolo con la probabilidad de cruza. Sí aleatorio <probabilidad de cruza se une a esta lista, en caso contrario no. Con esta lista, se escogen 2 padres seleccionando una posición aleatoria, desde allí se intercambian genes para formar nuevos individuos. Figura 3.7 Cruza. Mutación En este caso también se eligen varios individuos generando un aleatorio y relacionando con la probabilidad de mutación. Sí aleatorio < probabilidad de mutación se elige el individuo, en caso contrario no. De los individuos seleccionados se intercambian los alelos 1 por 0 y viceversa. Una vez que se tanga la nueva generación se repite el proceso. Los parámetros a elegir son probabilidad de mutación, de cruza, número de individuos en cada población, número de generaciones, tamaño de torneo. Recocido Simulado A pesar de que los Algoritmos Genéticos por sí solos, han probado ser una técnica de búsqueda versátil y efectiva para resolver problemas de optimización, una manera de mejorar su desempeño varias estrategias de hibridación son utilizadas, éstas regularmente incorporan heurísticas convencionales como Recocido Simulado o Búsqueda Tabú como un procedimiento de mejora en la búsqueda local del Algoritmo Genético Básico [20]. En investigaciones anteriores, las comparaciones han demostrado que la combinación con estas heurísticas genera mejores resultados [41], también que encuentra soluciones óptimas es una fracción de tiempo más pequeña [34].
0 1 1 1 0 0 1 0 Padre 1 1 0 0 1 0 0 1 0 Nuevo individuo 1
1 0 0 1 1 0 0 0 Padre 2 0 1 1 1 1 0 0 0 Nuevo individuo 2
65
Para ayudar a resolver el problema de acomodo de departamentos, una variación de Recocido Simulado es usada para evaluar su funcionamiento. Este proceso empieza cuando el operador de mutación acaba, se describe a continuación: Paso 1: De cada individuo se seleccionen las posiciones en el cromosoma, esto se hace generando aleatorios y multiplicándolo por el número de variables binarias (genes). Paso 2: En cada posición se intercambia un 0 por 1 y viceversa, se evalúa con CPLEX el nuevo individuo. Sí este es menor y diferente de cero, se cambia el cromosoma y la aptitud almacenada en la población original. Sí la aptitud encontrada es mayor, se genera un aleatorio que se compara con una cierta probabilidad; en caso de que el aleatorio< probabilidad se cambia al individuo en la población. Paso 3. Se continúa con el siguiente individuo.
66
4. Análisis y Discusión de Resultados 4.1 Experimentos para colocar Parámetros de Algoritmos Genéticos Cuando se trabaja con Algoritmos Genéticos generalmente se compara una población generada al azar con una inicial de “mejores encontrados” [37], funcionando mejor la población de mejores [47] en este caso entendiéndose como mejores aquellos que cumplen las restricciones del modelo de programación entera, es decir, aquellos cuya función objetivo (fitness) era diferente de cero. La fase inicial de la experimentación se hizo considerando de forma aleatoria la población inicial, al experimentar de esta forma el algoritmo genético, se observó que aunque encontraba individuos que cumplían con las restricciones, no siempre la tendencia era a minimizar; es por esto que después de realizar experimentos durante 3 ocasiones se tuvo la población inicial de 970 individuos que fue necesaria para emprender los experimentos para probar los demás parámetros como cruza, mutación, torneo, etc. Para fijar todos los parámetros de estos tres experimentos iniciales se observó que: la cruza que funcionó en diferentes trabajos que fueron ocupados para la distribución de departamentos ocupando algoritmos genéticos fue escogida cercana a 1 y mayor a 0.5 [36, 37, 38] y la mutación menor a 0.1, en algunos casos mutaciones más grandes pero siempre menores a 0.5 también funcionaron [36,37], es por ello que para estos experimentos una cruza de 0.9 y una mutación de 0.01 fueron fijadas. La población utilizada en el trabajo de Norman y Smith [36] para solucionar el problema de 20 departamentos de Armour y Buffa fue con una población total de 600,000, para estos experimentos se hizo con un poco más de la mitad porque era un problema de 7 departamentos, 900 individuos con 400 generaciones; aunque en muchos casos como se observará más adelante se obtuvieron resultados mucho antes de terminar las 400 generaciones. El torneo de tamaño 2 [37, 38] por ser también el que se ocupo para generar resultados es ocupado para esta fase inicial. En la segunda fase se seleccionaron varios experimentos que a continuación se detallan para determinar como afectaban los parámetros al problema específico. Trabajo posterior incluye hacerlo ocupando el Diseño de Experimentos con el fin de evaluar cuál de estos parámetros tiene más impacto en el tiempo (número de generaciones) para encontrar la solución. Todos estos se hicieron con una población inicial de los mejores encontrados (970 individuos) y ocupando 400 generaciones para su comparación, aunque en muchos casos, se encontró el mejor en generaciones anteriores. Los experimentos fueron: Tabla 4.1. Experimentos con Algoritmos Genéticos. Torneo 2 Mutación Cruza .01 .5 .01 .7 .01 .9 .005 .5 .015 .5 Torneo 4 Mutación Cruza .01 .5 .01 .7
67
.01 .9
.005 .5
.015 .5 Torneo 8 Mutación Cruza .01 .5 .01 .7 .01 .9 .005 .5 .015 .5 Torneo 16 Mutación Cruza .01 .5 .01 .7 .01 .9 .005 .5 .015 .5 A continuación se presentan gráficas con la finalidad de realizar una comparación de los resultados. Algunas gráficas presentan el mejor alcanzado (mínimo poblacional-offline performance) y otras la aptitud promedio generacional (online performance). El mínimo poblacional se obtiene actualizando este dato cuando un menor es encontrado, no importa que individuo sea; para ello se revisa la población total en cada generación buscando el de menor aptitud. Una vez encontrado se hace lo mismo para la siguiente generación pero comparándolo con la aptitud de la generación anterior. La aptitud promedio generacional, como su nombre lo indica, se obtiene generación a generación revisando cada uno de los individuos, la aptitud de cada individuo se divide entre la población total y se suma a aptitud promedio generacional:
)/)((PrPr
1
otalPoblaciónTiividuoaptitudindracionalomedioGeneAptitud
racionalomedioGeneAptitud
otalPoblacionThastadesdeiindividuopara
+=
4.1.1 Torneo En este apartado se presentan graficas comparativas de la Aptitud Promedio Generacional (online) y el Mejor Encontrado (offline) para los distintos torneos evaluados.
68
a) Mutación= .005, Cruza=.5
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
140
145
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneos-Mutacion=.005, Cruza=.5
torneo 2torneo 4torneo 8torneo 16
0 50 100 150 200 250 300 350 400110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneos-Mutacion=.005, Cruza=.5
torneo 2torneo 4torneo 8torneo 16
Gráfica 4.1 Torneos Variantes, Mutación=.005, Cruza=.5. Aptitud Promedio Generacional/Mejor Generacional
Como se puede observan en este caso, se minimiza en una generación previa la aptitud promedio generacional, utilizando torneo 16, también con éste se encuentra más rápido el mejor generacional.
69
b)Mutación=.015 Cruza=.5
0 50 100 150 200 250 300 350 4000
50
100
150Torneos-Mutacion=.015, Cruza=.5
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
torneo 2torneo 4torneo 8torneo16
0 50 100 150 200 250 300 350 40095
100
105
110
115
120
125
130
135Torneos-Mutacion=.015, Cruza=.5
Generaciones
Mej
or G
ener
acio
nal
torneo 2torneo 4torneo 8torneo 16
Gráfica 4.2 Torneos Variantes, Mutación=.015, Cruza=.5. Aptitud Promedio
Generacional/Mejor Generacional Utilizando torneo 16, se minimiza en una generación previa la aptitud promedio generacional, sin embargo el mejor es alcanzado utilizando torneo 8.
70
c)Mutación=.01 Cruza=.5
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneos-Mutacion=.01, Cruza=.5
torneo 2torneo 4torneo 8torneo 16
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneos-Mutacion=.01, Cruza=.5
torneo 2torneo 4torneo 8torneo 16
Gráfica 4.3 Torneos Variantes, Mutación=.01, Cruza=.5. Aptitud Promedio
Generacional/Mejor Generacional Tanto el mejor generacional como la minimización de la aptitud promedio generacional se alcanzan utilizando torneo 16.
71
d)Mutación=.01 Cruza=.7
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneos-Mutacion=.01, Cruza=.7
torneo 2torneo 4torneo 8torneo 16
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneos-Mutacion=.01, Cruza=.7
torneo 2torneo 4torneo 8torneo 16
Gráfica 4.4 Torneos Variantes, Mutación=.01, Cruza=.7. Aptitud Promedio
Generacional/Mejor Generacional En este experimento, el que minimizo la aptitud promedio generacional fue el torneo 8, pero se alcanza el mejor generacional con el torneo 4.
72
e)Mutación_.01, Cruza=.9
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneos-Mutacion=.01, Cruza=.9
torneo 2torneo 4torneo 8torneo 16
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneos-Mutacion=.01, Cruza=.9
torneo 2torneo 4torneo 8torneo16
Gráfica 4.5 Torneos Variantes, Mutación=.01, Cruza=.9. Aptitud Promedio
Generacional/Mejor Generacional Se minimiza la aptitud promedio generacional con el torneo 16, con este mismo se encuentra el mejor generacional. Para hacer una comparación entre los mejores encontrados se presentan las configuraciones para cada torneo:
73
Figura 4.1 Mejores configuraciones obtenidas. Torneos Variantes Los departamentos que deben estar juntos debido a que ocasionan costos son 1 y 2 ($2.40), 2 y 7 ($7.00), 3 y 4 ($12.00), 4 y 6 ($12.00), 5 y 6 ($6.00). Cuando se obtiene un valor de 110 .58, el 1 y el 2 están separados y existe un espacio que podía recorrerse entre el 4 y el 6. Como es de esperarse con el valor de 109.8 no existen muchos cambios, el 1 con el 2 siguen separados y existe también la posibilidad de juntar el 4 con el 6. En el valor de 97.342 todos los
Torneo: 2 Valor Mínimo de la Función Objetivo: 110.585 Experimentos donde fue encontrado: • Cruza 0.5, Mutación .01. • Cruza 0.7, Mutación .01 Siguiente valor encontrado: 111.95
Torneo: 4 Valor Mínimo de la Función Objetivo: 109.8 Experimentos donde fue encontrado: • Cruza 0.7, Mutación .01 Siguiente valor encontrado: 111.65
Torneo: 8 Valor Mínimo de la Función Objetivo: 97.342 Experimentos donde fue encontrado: • Cruza 0.5, Mutación .015. Siguiente valor encontrado: 104.23
Torneo: 16 Valor Mínimo de la Función Objetivo: 104.23 Experimentos donde fue encontrado: • Cruza 0.5, Mutación .01. Siguiente valor encontrado: 110.58
74
departamentos que deben estar juntos lo están y por eso se minimiza, en el de 104.23 el departamento 4 y 6 ya están juntos, pero el 1 y el 2 se encuentran separados. 4.1.2 Cruza Se presentan graficas comparativas de la Aptitud Promedio Generacional (online performance) y el Mejor Encontrado (offline performance) para cruzas diferentes 0.5, 0.7, 0.9 en distintos torneos. Cabe señalar que la tasa de mutación se mantiene constante en 0.01. a)Torneo 2
0 50 100 150 200 250 300 350 40090
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo2-Cruza Variable
cruza=.5cruza=.7cruza=.9
0 50 100 150 200 250 300 350 400110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneo2-Cruza Variable
cruza=.5cruza=.7cruza=.9
Gráfica 4.6 Torneo 2, Cruza Variante 0.5, 0.7 y 0.9. Aptitud Promedio Generacional/Mejor
Generacional.
75
La cruza que minimiza la aptitud promedio generacional es la de 0.5, si se compara el mejor generacional F.O.=111.95 se obtiene en una generación anterior con la cruza 0.5, 0.7 y 0.9 respectivamente pero el mejor encontrado 110.58 se obtiene con 0.5 y 0.7 pero en las generaciones 249 y 299 respectivamente. b) Torneo 4
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo4-Cruza Variable
cruza=.5cruza=.7cruza=.9
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneo4-Cruza Variable
cruza=.5cruza=.7cruza=.9
Gráfica 4.7 Torneo 4, Cruza Variante 0.5, 0.7 y 0.9. Aptitud Promedio Generacional/Mejor
Generacional.
76
En cuanto a la aptitud generacional promedio no se ve diferencia significativa entre las cruzas, si comparamos el mejor generacional de F.O.=110.58 se obtiene con mayor rapidez con la cruza 0.5, 0.7 y 0.9 respectivamente; sin embargo, el mejor generacional F.O.=109.8 se encuentra con la cruza 0.7. c) Torneo 8
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo8-Cruza Variable
cruza=.5cruza=.7cruza=.9
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneo8-Cruza Variable
cruza=.5cruza=.7cruza=.9
Gráfica 4.8 Torneo 8, Cruza Variante 0.5, 0.7 y 0.9. Aptitud Promedio Generacional/Mejor
Generacional.
77
La aptitud promedio generacional se minimiza con la cruza 0.5, aunque no se ven diferencias significativas; para el mejor generacional F.O=111.95 tanto el parámetro 0.5 y 0.7 tienen el mismo comportamiento; pero el mejor F.O=104.23 se obtiene con la cruza 0.9. d) Torneo 16
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Pro
med
io G
ener
acio
nal
Torneo16-Cruza Variable
cruza=0.5cruza=0.7cruza=0.9
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneo16-Cruza Variable
cruza=.5cruza=.7cruza=.9
Gráfica 4.9 Torneo 16, Cruza Variante 0.5, 0.7 y 0.9. Aptitud Promedio Generacional/Mejor
Generacional.
78
La aptitud generacional promedio se minimiza con la cruza en 0.5, también con este mismo valor se obtiene el mejor generacional F.O.=104.23 en la generación 257. A continuación se muestran las configuraciones para los mejores encontrados en cada cruza para torneo 16:
Figura 4.2 Mejores configuraciones. Cruza Variante.
En el valor de 104.23 los departamentos 1 y 2 ($2.40) se encuentran separados. Cuando se obtiene un valor de 109.8, el 1 y el 2 también están separados y existe un espacio que podía recorrerse entre el 4 y el 6 ($12.00) 4.1.3 Mutación Se presentan graficas comparativas de la Aptitud Promedio Generacional (online performance) y el Mejor Encontrado (offline performance) para cruzas diferentes 0.005, 0.01, 0.015 en distintos torneos. Se escogen estos valores porque a mayor mutación los valore de la aptitud promedio generacional tienden a cero y no se minimiza al mejor generacional, la tasa de cruza se mantiene constante en 0.05.
Cruza: 0.5 Valor Mínimo de la Función Objetivo: 104.23 Experimentos donde fue encontrado:
• Torneo 16, Mutación .01. Siguiente valor encontrado: 110.58
Cruza: 0.7 Valor Mínimo de la Función Objetivo: 109.8 Experimentos donde fue encontrado:
• Torneo 4, Mutación .01. Siguiente valor encontrado: 110.58
Cruza: 0.9 Valor Mínimo de la Función Objetivo: 104.23 Experimentos donde fue encontrado:
• Torneo 8, Mutación .01. Siguiente valor encontrado: 110.58
79
a) Torneo 2
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo2-Mutacion Variable
mut=.005mut=.01mut=.005
0 50 100 150 200 250 300 350 400110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneo2-Mutacion Variable
mut=.005mut=.01mut=-015
Gráfica 4.10 Torneo 2, Mutación Variable 0.005, 0.01 y 0.015. Aptitud Promedio
Generacional/Mejor Generacional.
Se minimiza la aptitud generacional promedio con la mutación de 0.01 y 0.015, el mejor poblacional F.O.=111.95 lo encuentra en una generación menor con la mutación de .015, pero el mínimo F.O.=110.58 únicamente se encuentra con el valor de 0.01.
80
b) Torneo 4
0 50 100 150 200 250 300 350 40040
60
80
100
120
140
160
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo4-Mutacion Variable
Mut=.005Mut=.01Mut=.015
0 50 100 150 200 250 300 350 400110
115
120
125
130
135
Generaciones
Mej
or G
ener
acio
nal
Torneo4-Mutacion Variable
Mut=.005Mut=.01Mut=.015
Gráfica 4.11. Torneo 4, Mutación Variable 0.005, 0.01 y 0.015. Aptitud Promedio
Generacional/Mejor Generacional. Aquí se minimiza la aptitud promedio generacional con la mutación de 0.015, con los tres valores se encuentra el mismo mejor generacional mínimo F.O.=111.95, pero se obtienen en una menor generación con la mutación .01, .015 y .005 respectivamamente.
81
c.) Torneo 8
0 50 100 150 200 250 300 350 40020
40
60
80
100
120
140
160
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo8-Mutacion Variable
mut=.005mut=.01mut=.015
0 50 100 150 200 250 300 350 40095
100
105
110
115
120
125
130
135Torne8-Mutacion Variable
Generaciones
Mej
or G
ener
acio
nal
mut=.005mut=.01mut=.015
Gráfica 4.12 Torneo 8, Mutación Variable 0.005, 0.01 y 0.015. Aptitud Promedio
Generacional/Mejor Generacional.
El mejor generacional F.O.=97.3420 se obtiene con mutación de 0.015, con este mismo valor se minimiza también la aptitud generacional promedio.
82
d) Torneo 16
0 50 100 150 200 250 300 350 4000
50
100
150
Generaciones
Apt
itud
Gen
erac
iona
l Pro
med
io
Torneo16-Mutacion Variable
mut=.005mut=.01mut=.015
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135Torneo16-Mutacion Variable
Generaciones
Mej
or G
ener
acio
nal
mut=.005mut=.01mut=.015
Gráfica 4.13 Torneo 16, Mutación Variable 0.005, 0.01 y 0.015. Aptitud Promedio
Generacional/Mejor Generacional.
La aptitud generacional promedio se minimiza con al incrementar la mutación, el mejor generacional F. O.=111.65 se obtiene en una generación anterior con la mutación 0.015 y después con .01; pero el mínimo F.O.=104.23 se obtiene con la mutación 0.01.
83
Para evaluar los resultados se presentan las configuraciones para los tres tipos de mutación utilizando torneo 8.
Figura 4.3. Mejores Configuraciones, Mutación Variable. En el valor de 104.23 los departamentos 1 y 2 ($2.40) se encuentran separados. En el valor de 97.342 todos los departamentos que deben estar juntos lo están y por eso se minimiza. El valor de 111.95 es parecido al de 110.58, el 1 y el 2 están separados y existe un espacio que podía recorrerse entre el 4 y el 6 ($12.00). A continuación se muestra una tabla, dónde se muestra el mínimo de la función objetivo alcanzado en cada experimento:
Mutación: 0.015 Valor mínimo de la Función Objetivo: 97.342 Experimentos en dónde se encontró:
• Torneo 8, cruza 0.5 Siguiente valor encontrado: 111.65
Mutación: 0.01 Valor mínimo de la Función Objetivo: 104.23 Experimentos en dónde se encontró:
• Torneo 16, cruza 0.5 Siguiente valor encontrado: 111.95
Mutación: 0.005 Valor mínimo de la Función Objetivo: 111.95 Experimentos en dónde se encontró:
• Torneo 4, cruza 0.5 • Torneo 16, cruza 0.5
Siguiente valor encontrado: 124.9
84
Tabla 4.2. Mínimos de la función objetivo encontrados
Óptimo obtenido en CPLEX 83.53969Torneo Mutación Cruza Mínimo
(mejor solución)2 0.005 0.5 111.95
0.01 0.5 110.580.015 0.5 111.950.01 0.7 110.580.01 0.9 110.58 Mínimo 97.342
4 0.005 0.5 111.95 Promedio 111.20960.01 0.5 104.23 Máximo 124.91
0.015 0.5 111.650.01 0.7 109.80.01 0.9 110.58
8 0.005 0.5 124.90.01 0.5 111.95
0.015 0.5 97.3420.01 0.7 111.950.01 0.9 110.58
16 0.005 0.5 111.950.01 0.5 104.23
0.015 0.5 111.950.01 0.7 124.910.01 0.9 110.58
4.2 Búsqueda Local con Recocido Simulado Como se ha mencionado, se utilizó Recocido Simulado como parte del Algoritmo Genético con la finalidad de disminuir el tiempo en que se encuentra el valor mínimo (offline performance) y minimizar el promedio generacional (online performance). A los parámetros habituales de Algoritmos Genéticos; dos más se agregaron; por una parte el número de veces que se hace el cambio dentro del cromosoma (j) y (p) que es la probabilidad de aceptación dentro del Recocido. Para entender estos dos parámetros es necesario recordar el proceso: Paso 1: De cada individuo se seleccionen las posiciones en el cromosoma (j), esto se hace generando aleatorios y multiplicándolo por el número de variables binarias (genes). Paso 2: En cada posición se intercambia un 0 por 1 y viceversa, se evalúa con CPLEX el nuevo individuo. Sí este es menor y diferente de cero, se cambia el cromosoma y la aptitud almacenada en la población original. Sí la aptitud encontrada es mayor, se genera un aleatorio que se compara con una cierta probabilidad (p); en caso de que el aleatorio< probabilidad se cambia al individuo en la población. Paso 3. Se continúa con el siguiente individuo. Los experimentos realizados estuvieron enfocados a: a) Comparar los resultados obtenidos con Recocido Simulado en la Búsqueda Local y el
Algoritmo Genético Simple. b) Evaluar que tan sensible es el recocido a la probabilidad (p) de aceptación utilizada. c) Ver sí el número de posiciones seleccionadas para realizar el cambio afecta el
comportamiento.
85
A continuación se presentan las gráficas de experimentos realizados en cada apartado: a) Comparación Algoritmo Genético con Recocido Simulado en la Búsqueda Local. Torneo 16-Cruza=.9, Mutación=.01, j=6 p=.005
0 50 100 150 200 250 300 350 40020
40
60
80
100
120
140
160
Generaciones
Apt
itud
Torneo16-Cruza=0.9, Mutacion=.01, j=6, p=.005
AGAG-RS
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo16-Cruza=0.9, Mutacion=.01, j=6, p=.005
AGAG-RS
Gráfica 4.14. Torneo 16, Cruza 0.9, Mutación 0.01, j=6, p=.005. Comparación Aptitud
Promedio Generacional/Mejor Generacional. Como se puede observar existe un mejor comportamiento al utilizar Recocido Simulado tanto en la aptitud promedio generacional (online performance) como en el mejor generacional (offline performance). Con el Algoritmo Genético Simple se obtiene un valor de la función objetivo
86
mínimo de 110.58 después de la generación 290, mientras que cuando se utiliza Recocido Simulado en la búsqueda local se obtiene un mejor generacional de 106.8 en la generación 145. Torneo 8-Cruza=0.5, Mutación=.015, j=2, p=.005
0 50 100 150 200 250 300 350 40020
40
60
80
100
120
140
160Torneo8-Cruza=0.5, Mutacion=.015, j=2, p=.005
Generaciones
Apt
itud
AGAG-RS
0 50 100 150 200 250 300 350 40095
100
105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.015, j=2, p=.005
AGAG-RS
Gráfica 4.15. Torneo 8, Cruza 0.5, Mutación 0.015, j=2, p=.005. Comparación Aptitud
Promedio Generacional/Mejor Generacional En este experimento en la aptitud promedio generacional (online performance) la diferencia, no es muy significativa y sí observamos con respecto al mejor generacional, éste se obtiene cuando se utiliza el Algoritmo Genético sólo, pero sí se corriese los dos nuevamente sólo 200 generaciones se nota un mejor comportamiento con el Recocido Simulado en la búsqueda local.
87
Torneo4- Cruza=.5, Mutación=0.01, j=2
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Torneo4-Cruza=0.5, Mutacion=.01, j=2, p=.005
AGAG-RS
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo4-Cruza=0.5, Mutacion=.01, j=2, p=.005
AGAG-RS
Gráfica 4.16. Torneo 4, Cruza 0.5, Mutación 0.01, j=2, p=.005. Comparación Aptitud
Promedio Generacional/Mejor Generacional La aptitud promedio generacional no difiere significativamente, sin embargo se alcanza un mejor generacional cuando se utiliza Recocido Simulado en la búsqueda local.
88
Torneo8-Cruza=.5, Mutación=.01, j=2
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, j=2, p=.005
AGAG-RS
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, j=2, p=.005
AGAG-RS
Gráfica 4.17 Torneo 8, Cruza 0.5, Mutación 0.01, j=2, p=.005. Comparación Aptitud
Promedio Generacional/Mejor Generacional La aptitud promedio generacional (online performance) se minimiza al utilizar Recocido Simulado en la búsqueda local. El menor generacional mínimo (offline performance) se encuentra cuando se utiliza la búsqueda local, sí el experimento se realiza hasta la generación 200 se puede observar que cuando se utiliza recocido simulado se encuentra el menor más rápido.
89
Torneo8-Cruza=.5, Mutación=.01, j=4
0 50 100 150 200 250 300 350 40060
70
80
90
100
110
120
130
140
150
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, p=.005, j=4
AGAG-RS
0 50 100 150 200 250 300 350 40090
95
100
105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, p=.005, j=4
AGAG-RS
Gráfica 4.18 Torneo 8, Cruza 0.5, Mutación 0.01, j=4, p=.005. Comparación Aptitud
Promedio Generacional/Mejor Generacional En este experimento se puede observar cómo la aptitud promedio generacional se minimiza con al utilizar Recocido Simulado en la búsqueda local. Por otra parte el mejor generacional encontrado sólo con Algoritmos Genéticos F.O.=111.95 encontrado después de la generación
90
200, se obtiene antes de la 50 con Recocido Simulado en la búsqueda local, en este caso se encuentra al mejor generacional de todos los experimentos F.O=91.2793.
b) Probabilidad de aceptación Torneo8- Cruza=0.5, Mutación=.015, j=2
0 50 100 150 200 250 300 350 40020
40
60
80
100
120
140
160
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.015, j=2
p=.05p=.005
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135Torneo8-Cruza=0.5, Mutacion=.015, j=2
Generaciones
Apt
itud
p=.05p=.005
Gráfica 4.19 Torneo8, Cruza 0.5, Mutación 0.015, j=2. Comparación Aptitud Promedio
Generacional/Mejor Generacional entre p=.05 y p=.005. Aunque en el promedio generacional no se notan diferencias significativas, en el mejor encontrado sí, con una probabilidad menor de aceptación se obtiene el mejor generacional más rápido (en una generación menor) y también el mínimo.
91
Torneo4- Cruza=0.5, Mutación=01, j=2
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Torneo4-Cruza=0.5, Mutacion=.01, j=2
p=.05p=.005
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo4-Cruza=0.5, Mutacion=.01, j=2
p=.05p=.005
Gráfica 4.20 Torneo4, Cruza 0.5, Mutación 0.01, j=2. Comparación Aptitud Promedio
Generacional/Mejor Generacional entre p=.05 y p=.005.
Cuando se utiliza una probabilidad menor, se alcanza un mejor generacional (offline), la aptitud promedio generacional (online) también se minimiza.
92
Torneo8-Cruza=0.5, Mutación=0.01, j=2
0 50 100 150 200 250 300 350 40090
100
110
120
130
140
150Torneo8-Cruza=0.5, Mutacion=.01, j=2
Generaciones
Apt
itud
p=.05p=.005
0 50 100 150 200 250 300 350 400100
105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, j=2
p=.05p=.005
Gráfica 4.21 Torneo8, Cruza 0.5, Mutación 0.01, j=2. Comparación Aptitud Promedio
Generacional/Mejor Generacional entre p=.05 y p=.005.
Con respecto a la aptitud promedio generacional, ésta se ve minimizada con la probabilidad más pequeña, el mejor generacional se alcanza también. Sí comparamos el mejor generacional hasta la generación 200, se puede observar que el que encontraría el mejor generacional sería el de la p=0.005.
93
c) Posiciones seleccionadas Torneo16- Cruza=0.5, Mutación=0.01, p=0.005
0 50 100 150 200 250 300 350 40020
40
60
80
100
120
140
160
Generaciones
Apt
itud
Torneo16-Cruza=0.5, Mutacion=.01, p=.005
j=2j=6
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo16-Cruza=0.5, Mutacion=.01, p=.005
j=2j=6
Gráfica 4.22 Torneo 16, Cruza 0.5, Mutación 0.01, p=.005. Comparación Aptitud Promedio
Generacional/Mejor Generacional entre j.2 y j=6.
La aptitud generacional promedio se minimiza utilizando j=6, también de esta forma se encuentra el mejor generacional promedio. Si sólo se hiciese el experimento hasta la generación 100 se
94
obtendrían mejores resultados (función objetivo mínimo) con una seleccionando una revisión de posiciones mayor. Torneo4- Cruza=0.5, Mutación=0.01, p=0.005
0 50 100 150 200 250 300 350 40080
90
100
110
120
130
140
150
Generaciones
Apt
itud
Torneo4-Cruza=0.5, Mutacion=.01, p=.005
j=2j=4
0 50 100 150 200 250 300 350 400105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo4-Cruza=0.5, Mutacion=.01, p=.005
j=2j=4
Gráfica 4.23 Torneo 4, Cruza 0.5, Mutación 0.01, p=.005. Comparación Aptitud Promedio
Generacional/Mejor Generacional entre j=2 y j=4.
La aptitud promedio generacional se ve ligeramente disminuida con j=4, aunque el mejor generacional es obtenido con j=2 ante de éste siempre se obtienen en menores generaciones con j=4.
95
Torneo8- Cruza=0.5, Mutación=0.01, p=0.005
0 50 100 150 200 250 300 350 40060
70
80
90
100
110
120
130
140
150
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, p=.005
j=2j=4
0 50 100 150 200 250 300 350 40090
95
100
105
110
115
120
125
130
135
Generaciones
Apt
itud
Torneo8-Cruza=0.5, Mutacion=.01, p=.005
j=2j=4
Gráfica 4.24 Torneo 8, Cruza 0.5, Mutación 0.01, p=.005. Comparación Aptitud Promedio
Generacional/Mejor Generacional entre j=2 y j=4. En este experimento se puede observar cómo la aptitud promedio generacional (online performance), se minimiza con una j mayor. Haciendo una comparación de los mejores generacionales encontrados (offline performance), con j= 2 se encuentran los mismos valores de
96
la función objetivo en generaciones posteriores. El mejor generacional se encuentra con j=4, F.O.=91.2723. Por último se incluye una gráfica para mostrar cómo en la mitad de generaciones es posible minimizar la Aptitud Promedio Generacional y encontrar el mínimo utilizando Recocido Simulado en la búsqueda local.
0 20 40 60 80 100 120 140 160 180 20020
40
60
80
100
120
140
160
Generaciones
Apt
itud
Torneo8-Cruza=0.5,Mutacion=.015, j=2, p=.05
onlineoffline
Gráfica 4.25 Torneo8-Cruza=0.5, Mutación=.015, j=2, p=.05. Aptitud promedio generacional y
mejor generacional. 4.3 Resultados Con respecto al torneo, se alcanzan mejores resultados en cuanto a mejor poblacional y mejor aptitud generacional sí se utiliza torneo 16, esto es lógico sí se hace una búsqueda 16 veces para selección de los de menor función objetivo. Sin embargo esto no sucede todas las veces, puesto que el Algoritmo Genético trabaja de forma aleatoria los mejores resultados encontrados no difieren de manera significativa. Debido a esto aunque pudiera pensarse que al aumentar el tamaño de torneo mejoran los resultados, se debe pensar que esto puede alentar el proceso y cómo se observó durante el experimento los resultados incluso con el menor torneo (tamaño 2) son buenos (que cumplen con las restricciones y tienden a minimizar la función objetivo). Al parecer una cruza menor 0.5 funciona mejor tanto en aptitud generacional promedio como en encontrar el mejor; con este valor se encuentra el valor mínimo de la función objetivo en el menor tiempo; sin embargo no se debe olvidar que debido a que existe mayor probabilidad de cruza en 0.7 y 0.9 y debido a que este es un proceso aleatorio muchas veces se encuentra el mejor con estos valores. Es posible generalizar ya que los mejores encontrados no difieren significativamente. Con la tasa de mutación se tiene que tener mas cuidado, porque este factor hace que se minimice la aptitud promedio generacional o que se encuentre el mejor generacional mínimo más rápido; pero también se corre el riesgo de que este factor haga que la aptitud promedio generacional
97
tienda a cero y que el mejor generacional se mantenga. Es por ello que lo mejor es buscar un punto de equilibrio; en este caso 0.01. Las configuraciones no difieren significativamente, cumplen con las restricciones de área por departamento y total. Lo único que cambia es que tan cerca o lejos están los departamentos que importan los costos más elevados en este caso el 4 y 6 y el 3 con el 4. Por otro lado, es fácil observar que aunque el 1 y 2 tienen costos asociados, no se les da prioridad puesto que son los más bajos $2.40. Al observar el optimo podemos distinguir algo importante los departamentos que deben estar juntos se encuentran lo mas próximos posible tanto en dirección “x” como en la “y”.
Figura 4.4 Óptimo, función objetivo 83.53969
En todos los experimentos realizados con Recocido Simulado en la búsqueda local, se obtuvieron mejores resultados (mínimos en menor tiempo), no importando el valor de j(número de posiciones elegidas) o p(probabilidad de aceptación). Cuando se realizo la comparación con respecto a p hay mejor comportamiento al elegir una probabilidad más pequeña; esto es, porque a mayor probabilidad crece el riesgo de elegir entre dos la de mayor función objetivo, cabe recordar que ésta probabilidad es fijada para evitar mínimos locales. Por último la j que minimiza es la más grande, puesto que se hacen más revisiones en mismo individuo. Con esto se puede decir que cuando se combinan heurísticas se generan mejores resultados; también que encuentran soluciones óptimas es una fracción de tiempo más pequeña, en este caso en menores generaciones.
98
5. Conclusiones y Trabajo Futuro El problema de configuración de departamentos es un problema de optimización, encontrado en muchas organizaciones tanto de manufactura como de servicios. La distribución de departamentos rectangulares sigue siendo vigente en la actualidad, incluso en subconfiguraciones. Este problema ha sido estudiado desde los años 50’s, pero formulado originalmente por Armour y Buffa en los 60’s como uno de minimización de costos de manejo de materiales; y consiste en encontrar el arreglo más eficiente de departamentos de área desigual dentro de una configuración. Sobre los distintos métodos considerados en la investigación bibliográfica se puede observar que:
1) Los métodos de asignación cuadrática y de cobertura, programación lineal entera y entera mixta, fueron métodos exactos que funcionaron bien pero sólo para problemas de menos de ocho departamentos con áreas similares.
2) Debido a la complejidad computacional, surgieron los algoritmos óptimos y subóptimos; éstos pudieron resolver problemas de hasta 30 departamentos, pero de áreas similares. Los algoritmos híbridos necesitan más requerimientos computacionales (memoria y tiempo), que los de mejoramiento; pero los de construcción son los que requieren menos. Con los algoritmos de construcción sólo se obtiene una sola solución, mientras que en los de mejoramiento varias.
3) Sólo con las técnicas metaheurísticas se han resuelto problemas de 10 departamentos de área desigual; no se han encontrado soluciones óptimas pero si algunas muy cercanas.
4) Actualmente la atención se enfoca a obtener la solución directa de este problema de optimización, el modelo más actual ha alcanzado representaciones óptimas bajo un grado de error en problemas de menos de 10 departamentos.
En esta investigación se conjunta un modelo que obtiene la solución directa para menos de 10 departamentos con Algoritmos Genéticos, para realizar la búsqueda de las variables binarias. Después de hacer varios experimentos en un problema de siete departamentos se concluye que: Los Algoritmos Genéticos son una técnica robusta, debido a que los parámetros como torneo, mutación y cruza no modifican su funcionamiento de forma significativa, es decir en el mínimo encontrado o en la aptitud promedio generacional. Las mejores soluciones encontradas (mínimos con respecto a la función objetivo) son muy cercanas, de acuerdo con esto se puede concluir que para el problema de distribución de departamentos abordado como uno de programación entera los algoritmos genéticos son un método eficiente de búsqueda, en este caso también se demuestra que pueden también ser considerados para un número mayor de variables binarias (mayor cantidad de departamentos) no importando que parámetros se utilicen. En todos los casos, la mejor solución fue alcanzada en el 75% de generaciones o menos. Una ventaja importante para las empresas, es que mediante este método es posible tener al final un conjunto de mejores soluciones cercanas al óptimo, que pueden ayudarle a la empresa a ser flexible, entendiéndose como la capacidad que tendría (de ser necesario) de hacer un cambio en la distribución con una configuración no óptima pero muy buena. En todos los experimentos realizados con Recocido Simulado en la búsqueda local, se obtuvieron mejores resultados (mínimos en menos generaciones), no importando los parámetros elegidos. Cuando se combinan heurísticas este caso Algoritmos Genéticos con Recocido Simulado se generan mejores resultados, el mejor generacional (mínimo de la función objetivo) fue de 97.342
99
en la generación 263 con Algoritmos Genéticos y de 91.237 en la generación 290; también se encuentran soluciones óptimas en una fracción de tiempo más pequeña, en este caso en menores generaciones; por ejemplo en experimentos generados en el caso de F.O=111.95, con Algoritmos Genéticos se obtiene este resultado en la generación 200, mientras que con Recocido Simulado antes de la 50; la F.O.=110.58 se obtiene con Algoritmos Genéticos en la generación 263, mientras que con Recocido en la Búsqueda Local en la 55. Esto nos habla de una reducción de las generaciones del 75%. Con respecto al trabajo futuro se puede considerar lo siguiente, de forma general:
1) Desarrollar modelos exactos, formulaciones cuadráticas o lineales en donde no sea necesario manejar una cantidad enorme de variables; de tal forma que se aseguren soluciones óptimas para problemas de más de 10 departamentos
2) Explorar todas las posibles mejoras, por ejemplo haciendo la codificación del individuo más sencilla para soluciones donde se utilizan algoritmos genéticos [27, 28, 29], considerando ambos casos donde se encuentran pasillos externos y no, etc., en los métodos que usan técnicas metaheurísticas con el propósito de obtener configuraciones de áreas desiguales con mayor precisión.
3) Hacer más real el problema, tomando en consideración otros parámetros como tiempos de flujo del material, congestión de tráfico a través de los canales, accesibilidad, diagramas de relación, etc. Otra situación a considerar es cómo hacer la configuración flexible, pues una eficiente no debe cumplir sólo con los requerimientos actuales de producción; sino también con los futuros.
De forma específica:
1) Considerar funciones objetivo múltiples, es decir, que minimicen costo y también espacio. 2) Considerar varios tipos de métodos heurísticos en la búsqueda local para tratar de
encontrar los mínimos (con respecto a la función objetivo) en menores generaciones, sin embargo, es importante considerar que el tiempo no es relevante si la necesidad de resolver el problema sobrepasa la complejidad computacional.
3) Resolver problemas más grandes incluyendo el modelo completo de Castillo (�-accurate) [12] comparando éstos con otras soluciones encontradas en la literatura para más de 10 departamentos.
Se pudo observar a lo largo de esta investigación, que existe un campo abundante todavía por considerar en el problema de acomodo por departamentos; aún cuando son diferentes las técnicas utilizadas todas persiguen lo mismo: realizar este arreglo formalmente para minimizar costos. Este problema todavía no se ha aplicado, la mayoría de las empresas; especialmente en nuestro país siguen haciendo sus acomodos por experiencia; ocasionando grandes costos a la larga, es por ello que este trabajo pretende dejar abiertos nuevos campos, pero que involucren la utilización práctica de de esas estrategias en las empresas para hacerlas más competitivas.
100
6. Bibliografía [1]Aarts E.H.L y Laarhoven P.J.M. Statistical cooling: A general approach to combinatorial optimization problems. Philips Journal of Research 1985: 40:193-226. [2]Armour GC, Buffa ES. A heuristic algorithm and simulation approach to relative allocation of facilities. Management Science 1963:9:294-309. [3]Bazaraa MS. Computerized layout design: a branch and bound approach. AIIE Transactions 1975:7:432-8. [4]Bazaraa MS, Kirca O. A branch and bound-based heuristic for solving the QAP. Naval Research Logistics Quarterly 1983:30:287-304. [5]Bazaara MS, Sherali MD. Benders partinioning scheme applied to a new formulation of the quadratic assignment problem. Naval Research Logistics Quarterly 1980:27:29-41. �6�Bazaraa M.S. and Elshafei A.N. An exact branch and bound procedure for quadratic assignment problems. Naval Researh Logistics Quarterly 1979:26:109-121 [7]Burkard R.E. Die störugnsmethode zur lösung quadratisches zourdnungsprblem. in R.L. Francis anda P.B. Mirchandani discrete Location Theory Academic Press, New York 1973. [8] Burkard R:E and Bonninger A heuristic for quadratic Boolean program with applications to quadratic assignment problem, Europena Jorunal of Opertional Research 1983:13: 374-386. [9]Burkard RE, Stratman KH. Numerical investigations on quadratic assignment problem. Naval Research Logistics Quarterly 1978:25:129-144. [10]Cacceta L, Kusumah Y. Graph Theoretic Based Heuristics For the Facility Layout Designs Problems. http://www.esc.auckland.ac.nz/Organisations/ORSNZ/conf34/PDFs/Kusumah.pdf. [11]Casillas A, Martínez R. Algoritmo de Clustering On-Line Utilizando Metaheurísticas y Técnicas de Muestreo. http://nlp.uned.es/docs/CasillasGonzalezMartinezSEPLN.pdf [12]Castillo I, Westerlund T. An �-accurate model for optimal unequal-area blocks layout design. Computers & Operations Research 2003:1-19. [13]Carrie A. S. Moore. J.M. Roezniak M. And Seppanen, J.J. Numerical investigations on quadratic assignments problems. Graph theory and computer aided facilities design. OMEGA 1978:6:353-361 [14]Corry P, Kozan E. An ant algorithm for the Robust Machine Layout Problem. International Journal of Production Research, 1997. [15]Eades P. Foulds L.R and Giffin. An efficient heuristic for identyfing a maximum weigh planar subgraph in: Lecture Notes in Mathematics No. 952 (Combinatorial Mathematics No. 952 Springer Berlin. [16]Elorza J. Algoritmos Genéticos en el Diseño de Iluminación. Tesis, Tecnológico de Monterrey, 1996 [17]Foulds LR. Techniques for facility layout: deciding which pairs of activities should be adjacent. Management Science1983:29:1414-26. [18]Hasaan MMD, Hogg G.L Smith DR. SHAPE: un algoritmo de construcción para la evaluación de localización de área. International Journal of Production Research 1986:24:1283-95. [19]Gilmore P.C. Optimal and suboptimal algorithms for the quadratic assignment problem. Journal of the Society for Industrial and Applied Mathematics 1962:10:305-313 [28]Hopper E, Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research 2001:128:34-57 [29]Huerta DA. Mecanismos Adaptables sobre Castigos en Problemas de Calendarización de Actividades utilizando Algoritmos Genéticos. Tesis, Tecnológico de Monterrey, 2003.
101
[22] Izquierdo E. Diseño inverso de chimeneas industriales, Minimización del impacto ambiental y reducción de costes mediante el uso de algoritmos genéticos. Departamento de Ciencia y Tecnología de Materiales y Fluidos, Centro Politécnico Superior, Universidad de Zaragoza. http://www.um.es/estructura/equipo/vicestudiantes/arquimedes2003/pdf/PRESENTACION.pdf [23]Jajodia S. CLASS: A computerized layout solution. International Journal of Production Research 1995:30:95-108. [24]Johnson, D. S., Aragon, C.R., McGeogh, L. A. y Schevon C. Optimization by simulated annealing: An experimental evaluation. AT&T Bell Laboratories. [25]Kaufman L., Broeckx F., An algorithm for the quadratic assignment problem using Benders' decomposition. European Journal of Operational Research 1978:2: 204-211 [26]Kirkpatrick S. Gelatt, Jr. C.D. y Vecchi M.P. Optimization by simulated annealing. Science 1983:220:671-680 [27] Koopmans, T. C., and Beckmann, M. J., Assignment Problems and the Location of Economic Activities Econometrica 1957:25:53-76. [28]Kusiak A. Heragu SS. The facility layout problem. European Journal of Operational Research 1987:29:229-51. [29]Lacksonen T. A. Static and Dynamic Layout Problems with varying area. Journal of Operational Research Society 1994:43:59-69 [30] Lawler E. L. The Quadratic Assignment Problem, Management Science1963: 9:586-599. [31]Liaw CF. A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operacional Research 2000:124:28-42 híbridos [32]Mc Bride R., O´Leary Daniel. The use of mathematical programming with artificial intelligence and expert systems. Elsevier Science Publishers.1993-Invited Review. [33]Meller RD, Narayaaan V. Vance PH. Optimal facility layout design and flow network design. In: Proceedings of the Material Handling Research Colloquium, Hebron Kentucky 1990. [34]Montano BR, et al. A genetic algorithm approach to policy design for consequence minimization. European Journal of Operational Research 2000:124:43-54 [35]Montreuil B. A modeling framework for integrating layout design and flow network design. In: Proceedings of the Material Handling Research Colloquium, Hebron, Kentucky, 1990. [36]Norman B, Smith A. Integrated Facility Design using an Evolutionary Approach with a Subordinate Network Algorithm. Revised by IEEE Transactions on Evolutionary Computation 1997. [37]Norman B, Smith A. Locating input and output points in Facilities Design: A Comparison of Constructive,Evolutionary and Exact Methods. Revised by IEEE Transactions on Evolutionary Computation 1999. [38]Norman B, Smith A. A Genetic Algorithm Approach to Input/Output Station Location in Facilities Design. Revised by IEEE Transaction on Evolutionary Computation. [39]Pierce, J.F., Crowston, W.B. Tree-search algorithms for quadratic assignment problems. Naval Research Logistics Quarterly, 1971:18: 136 [40]Rivera JF. Fast hard linear problem resolution using simulated annealing and Datzing’s rule. Proc. of IASTED Int.Conf. in Artificial Intelligence and Soft Computing (ASC 2001), 2001. [41]Rivera JF. A simplex genetic method for solving the Klee Minty Cube. Systems Transactions 2002:1:232-237. [42]Rivera JF. Complejidad computacional. Tecnológico de Monterrey. http://w3.mor.itesm.mx/~optimiza/opti9901/capa2/complejidad.html [43]Runwei C, Gen M. Genetic Algorithms and engineering optimization. New York, NY:Wiley: 2000. pp. 1:1-80
102
[44]Seppanen JJ, Moore JM. Facilities planning with graph theory. Management Science 1970:17:243-53. [45]Tam K.Y , Li S.G. A hierarchical approach to the facilities layout problem. International Journal of Productions Research. 1991:29:165-184. [46]Tam K.Y. A simulated annealing algorithm space to manufacturing cells. International Journal of Productions Research 1992: 30:63-87. [47] Tate D, Smith A. Unequal-area facility layout by genetic search. IEE Transactions 1995:27:465-472 [48]Tompkins J. Facilities Planning. New York, NY : Wiley & Sons Inc. :2003, pp. 3-25, 79-119, 163-384 [49]van Camp DJ, Carter MW, Vanelli A. A nonlinear optimization approach for solving facility layout problems. European Journal of Operational Research. 1992:57:174-89 [50]Waebroeck H. CODON BIAS AND MUTABILITY IN HIV SEQUENCES. Instituto de Ciencias Nucleares, UNAM, 1997. http://citebase.eprints.org/cgi-bin/fulltext?format=application/pdf&identifier=oai%3AarXiv.org%3Aadap-org%2F9708003 [51]Winston W, Venkataramanan M. Introduction to Mathematical Programming. New York, NY:Thomson: 2003. pp. 1:800-821
