Estudio del equilibrado de líneas de montaje por medio de

Estudio del equilibrado de líneas de

montaje por medio de un algoritmo

de colonia de hormigas

Susana García López

Director: Dr. Eng. Jordi Fortuny Santos

Enero de 2021

TRABAJO DE FINAL DE GRADO

GRADO EN INGENIERÍA DE ORGANIZACIÓN INDUSTRIAL

Est. de SALB por medio de ACO Susana García López

1

AGRADECIMIENTOS

A mi familia, por el apoyo incondicional en todo momento.

A Jordi, mi director del trabajo, que ha estado presente en todo momento y circunstancias

durante toda ésta elaboración.


2

RESUMEN

En el presente trabajo se diseña un algoritmo basado en la metaheurística de optimización de

colonia de hormigas (Ant Colony Optimization, ACO) para la resolución de problemas de

equilibrados de líneas de montaje simples tipo 1 (Simple Assembly Line Balancing Problem,

SALBP-1), que tiene el objetivo de minimizar el número de estaciones en función de un tiempo

de ciclo dado. Para ello, se realiza un estudio de, por una parte, las líneas de montaje y sus

problemas de equilibrado, y, por otra parte, la metaheurística ACO y métodos heurísticos para la

resolución de los problemas de equilibrado de líneas. En el estudio, se lleva a cabo una búsqueda

referente a la aplicación de métodos de colonia de hormigas en otros problemas de la industria,

como lo son a parte de los equilibrados de líneas de montaje, el problema de disposición de

máquina y el problema de optimización de procesos logísticos. Los tres problemas fueron

aplicados a casos reales y resueltos con éxito, demostrando así la versatilidad de empleo de los

métodos de colonia de hormigas.

Finalmente, se crea un algoritmo a través del lenguaje de programación Python aplicando un

método de colonia de hormigas, en el que se ejecutaron cuatro problemas SALB. El método

aplicado está adaptado de la heurística ACS (Ant Colony System). Las hormigas construyen

soluciones mediante un método heurístico basado en prioridades, donde tienen prioridad aquellas

tareas de mayor tiempo de procesado. Entre los problemas SALB ejecutados en el algoritmo se

encuentra: un problema de seis tareas, en base al cual se ha diseñado y puesto en funcionamiento

el algoritmo; un problema de Otto et al. (2013), con un total de cincuenta tareas; Gunther,

compuesto por treinta y cinco tareas (Gunther, et al., 1983) y Wee and Magazine, formado por

setenta y cinco tareas (Wee and Magazine, 1981), ambos últimos pertenecen a problemas de la

literatura. En el sexto apartado se describen los problemas y se presentan sus resultados. En los

tres primeros problemas ha sido posible encontrar una secuencia de tareas que alcanza el número

mínimo de estaciones para el tiempo de ciclo indicado, resultando la solución óptima del

problema.

Tras las ejecuciones del algoritmo, se demuestra que los problemas de equilibrados de líneas de

montaje simples tipo 1 pueden ser resueltos mediante métodos de colonia de hormigas

presentando buenos resultados.


3

ABSTRACT

In the present work, an algorithm based on the ant colony optimization metaheuristic (ACO) is

designed for solving simple assembly line balancing problems - type 1 (SALBP-1), which has the

objective of minimizing the number of stations based on a given cycle time. For this, a study is

carried out of, on the one hand, the assembly lines and their balancing problems, and, on the other

hand, the ACO metaheuristics and heuristic methods for solving the line balancing problems. In

the study, a search is carried out regarding the application of ant colony methods in other industry

problems, such as assembly line balancing, the machine layout problem the optimization of

logistics processes problem. The three problems were applied to real cases and solved

successfully, thus demonstrating the versatility of employ of ant colony methods.

Finally, an algorithm is created through the Python programming language applying an ant colony

method, in which four SALB problems were executed. The applied method is adapted from the

ACS (Ant Colony System) heuristic. The ants build solutions using a heuristic method based on

priorities, where they have priority to those tasks with the longest processing time. Among the

SALB problems executed in the algorithm is found: a six-task problem, based on which the

algorithm has been designed and put into operation; a problem of Otto et al. (2013), with a total

of fifty tasks; Gunther, composed of thirty-five tasks (Gunther, et al., 1983) and Wee and

Magazine, formed of seventy-five tasks (Wee and Magazine, 1981), both last pertain to problems

of literature. In the sixth section, the problems are described and their results are presented. In the

first three problems it has been possible to find a sequence of tasks that reaches the minimum

number of stations for the indicated cycle time, resulting in the optimal solution to the problem.

After the runs of the algorithm, it is shown that simple assembly line balancing problems - type 1

can be solved by ant colony methods presenting good results.


4

ÍNDICE

1 OBJETO Y ALCANCE .................................................................................................................... 1

2 EQUILIBRADO DE LÍNEAS DE MONTAJE ............................................................................... 2

2.1 HISTORIA DE LAS LÍNEAS DE MONTAJE ........................................................................................ 2

2.2 TIPOS DE LÍNEAS DE MONTAJE ..................................................................................................... 2

2.2.1 Número de modelos de producto ............................................................................................ 2

2.2.2 Ambiente industrial general ................................................................................................... 3

2.2.3 Metodologías del proceso productivo ..................................................................................... 3

2.2.4 Diseño de línea (Line Layout) ................................................................................................ 4

2.2.5 Duración de tareas ................................................................................................................. 5

2.2.6 Flujo de piezas ........................................................................................................................ 6

2.3 PROBLEMAS DE EQUILIBRADO DE LÍNEAS .................................................................................... 8

2.3.1 Funcionamiento SALBP ......................................................................................................... 9

2.3.2 Funcionamiento GALBP ....................................................................................................... 10

2.3.3 Versiones de SALBP y GALBP ............................................................................................. 11

2.4 SOLUCIONES A PROBLEMAS DE EQUILIBRADO DE LÍNEAS ........................................................... 13

3 HEURÍSTICAS Y METAHEURÍSTICAS .................................................................................... 16

3.1 CLASIFICACIÓN DE LOS MÉTODOS HEURÍSTICOS ........................................................................ 16

3.1.1 Tipos de metaheurísticas ...................................................................................................... 18

3.1.2 Metaheurísticas de búsqueda ............................................................................................... 19

4 ALGORITMOS DE OPTIMIZACIÓN DE COLONIA DE HORMIGAS ................................ 24

4.1 ORÍGENES DE LA OPTIMIZACIÓN DE COLONIAS DE HORMIGAS .................................................... 24

4.1.1 Inspiración Biológica ........................................................................................................... 24

4.2 INTRODUCCIÓN A LA OPTIMIZACIÓN DE COLONIA DE HORMIGAS.............................................. 26

4.2.1 Técnicas de optimización ...................................................................................................... 27

4.3 METAHEURÍSTICA DE OPTIMIZACIÓN DE COLONIA DE HORMIGAS .............................................. 29

4.3.1 Algoritmo de la metaheurística de optimización de colonia de hormigas ............................ 30

4.4 MODELOS DE OPTIMIZACIÓN BASADOS EN COLONIAS DE HORMIGAS ........................................ 32

4.4.1 Sistema de Hormigas ............................................................................................................ 32

4.4.2 Estrategia elitista .................................................................................................................. 36

4.4.3 Sistema de hormigas basado en el rango ............................................................................. 37

4.4.4 Sistema de Hormigas Max-Min ............................................................................................ 38

4.4.5 Sistema de Colonia de Hormigas ......................................................................................... 42

4.4.6 Hormiga Q ............................................................................................................................ 44

4.4.7 Sistema ant............................................................................................................................ 45

4.4.8 Hyper Cube ........................................................................................................................... 47

4.5 APLICACIÓN DE ALGORITMOS DE COLONIAS DE HORMIGAS...................................................... 47

4.5.1 ACO para equilibrados de líneas de montaje ....................................................................... 47

4.5.2 ACO para problemas de disposición de máquina ................................................................ 49

4.5.3 Colonia de hormigas como optimizador de procesos logísticos ........................................... 54

5 METAHEURÍSTICA ACO PARA EL SALBP-1 ......................................................................... 57


5

5.1 INTRODUCCIÓN .......................................................................................................................... 57

5.1.1 La función objetivo para SALBP-1 ....................................................................................... 57

5.2 FUNCIONAMIENTO GENERAL ..................................................................................................... 58

5.2.1 Esquema básico .................................................................................................................... 58

5.2.2 Matriz de feromona .............................................................................................................. 59

5.2.3 Actualización del rastro ........................................................................................................ 59

5.2.4 Backtracking de la matriz de feromonas .............................................................................. 61

5.3 FUNCIONAMIENTO INTERNO: LA SUBCOLONIA ........................................................................... 61

5.3.1 Esquema básico .................................................................................................................... 61

5.3.2 Índices de decisión................................................................................................................ 63

5.3.3 Construcción de secuencia de tareas .................................................................................... 63

5.3.4 Evaluación de la secuencia .................................................................................................. 64

5.4 CRITERIO DE FINALIZACIÓN ....................................................................................................... 66

5.5 CONFIGURACIÓN DE LOS PARÁMETROS BÁSICOS ....................................................................... 66

6 DESCRIPCIÓN DE LAS PRUEBAS............................................................................................. 67

6.1 INTRODUCCIÓN .......................................................................................................................... 67

6.2 ENTORNO COMPUTACIONAL ...................................................................................................... 67

6.2.1 El lenguaje Python................................................................................................................ 67

6.2.2 Máquina y sistema utilizado ................................................................................................. 68

6.2.3 Juego de datos ...................................................................................................................... 68

6.3 PROBLEMA 1 (N=6) .................................................................................................................... 69

6.3.1 Descripción del problema..................................................................................................... 69

6.3.2 Análisis de resultados ........................................................................................................... 70

6.4 OTTO-1 (N=50) .......................................................................................................................... 71



6.5 GUNTHER (N=35) ....................................................................................................................... 74



6.6 WEE AND MAGAZINE (N=75) ..................................................................................................... 75



7 CONCLUSIONES ........................................................................................................................... 78

8 REFERENCIAS ............................................................................................................................... 79

9 ANEXOS........................................................................................................................................... 83

9.1 PROBLEMA 1 (N=6) .................................................................................................................... 83

9.1.1 Tabla de precedencias y tiempos .......................................................................................... 83

9.1.2 Algoritmo problema 1 (n=6) ................................................................................................ 83

9.2 OTTO-1 (N=50) .......................................................................................................................... 93

9.2.1 Tabla de precedencias y tiempos .......................................................................................... 93

9.2.2 Algoritmo Otto-1 (n=50) ...................................................................................................... 94

9.3 GUNTHER (N=35) ..................................................................................................................... 107

9.3.1 Tabla de precedencias y tiempos ........................................................................................ 107

9.3.2 Algoritmo Gunther (n=35) ................................................................................................. 108


6

9.4 WEE AND MAGAZINE (N=75) ................................................................................................... 119

9.4.1 Tabla de precedencias y tiempos ........................................................................................ 119

9.4.2 Algoritmo Wee and Magazine (n=75) ................................................................................ 121


1

1 OBJETO Y ALCANCE

Actualmente se han realizado diferentes investigaciones acerca del funcionamiento y aplicación

de métodos de colonia de hormigas en distintos tipos de problemas presentes en diferentes

ámbitos. Los resultados obtenidos han sido muy positivos en su mayoría, en algunos casos hasta

han llegado a sustituir otros métodos de optimización.

El equilibrado de líneas de montaje es un problema muy presente en las industrias de producción

que recibe especial atención para su resolución óptima. Gracias a ello, es posible disponer de gran

parte de investigaciones orientadas a su resolución, entre ellas se encuentra el algoritmo de

optimización de colonia de hormigas.

El presente trabajo tiene como objetivo la creación de un algoritmo de colonia de hormigas capaz

de resolver con éxito problemas de equilibrado de líneas tipo uno (SALBP-1) para líneas de

montaje pequeñas y medianas, compuestas hasta un máximo de cincuenta tareas. Para su

resolución será necesario tener el conocimiento de las siguientes variables del problema: el

número de tareas y sus respectivas precedencias, el tiempo de procesado de cada tarea y el tiempo

de ciclo a aplicar.

La memoria del trabajo consta de cinco apartados. El primero de ellos es una introducción a las

líneas de montaje, donde se describe su funcionamiento y se definen los diferentes tipos de líneas

en función de sus características. El siguiente apartado hace referencia a las diferentes heurísticas

y metaheurísticas. Seguidamente, el tercer apartado está enfocado en el funcionamiento de los

algoritmos de colonia de hormigas.

Las hormigas son capaces de recorrer caminos más cortos desde su colonia hasta el alimento

mediante una comunicación a través de los rastros de feromonas. En el tercer capítulo también se

incluyen las ideas principales del experimento que favoreció a la aplicación del método de

comunicación utilizado en las colonias de hormigas para la resolución de problemas de

optimización.

Los últimos dos capítulos están relacionados con la construcción del algoritmo. En el primero de

ellos se definen los criterios heurísticos aplicados en el algoritmo y finalmente se describen cuatro

problemas ejecutados en el algoritmo, con los que se ha demostrado su funcionamiento, y un

análisis de los resultados conseguidos.


2

2 EQUILIBRADO DE LÍNEAS DE MONTAJE

Una línea o cadena de montaje (Thomopoulos, 2014), es un proceso de fabricación en el cual las

piezas y componentes de los materiales son unidos de manera secuencial, manualmente por

operadores o automáticamente por robots, con el objetivo de crear un buen producto final de

forma eficiente.

2.1 HISTORIA DE LAS LÍNEAS DE MONTAJE

Las investigaciones llevadas a cabo hasta la fecha indican que la primera cadena de montaje tuvo

lugar en 200 AC en China, en el que se construyeron las esculturas del ejército de Terracota. Las

más de 8.000 figuras se crearon siguiendo un proceso de línea de producción, fabricando piezas

individuales que seguidamente se unieron.

A lo largo de la historia se han identificado varios procesos de cadenas de producción: fabricación

de galeras (en Venetian Arsenal, s. XVI), automatización del proceso de producción de harina

(Oliver Evans, 1785), producción en masa de mosquetes (Eli Whitney, 1797), primera cadena de

montaje automovilística (Ransom Olds, 1901) y producción en masa de automóviles (Henry Ford,

1909) (Thomopoulos, 2014).

2.2 TIPOS DE LÍNEAS DE MONTAJE

Se pueden distinguir tipos de líneas de montaje en función de las características de distribución

de línea, modelos de producto y tiempos asociados al proceso, en los cuáles influyen en el

ambiente industrial, la metodología del proceso productivo, el diseño de la línea de producción,

el número de modelo de productos, la duración de las tareas y la modalidad de flujo de piezas.

A continuación, en la figura 1 se muestran las tipologías de líneas de montaje esquematizadas.

2.2.1 Número de modelos de producto

Según el número de modelos de producto que son fabricados (Battaïa y Dolgui, 2013), las líneas

de producción pueden distinguirse en tres tipos de modelo de líneas: simples, mixtos y

multimodelo.

Líneas de modelos simples o monomodelo

Un solo producto es fabricado en la línea de producción. Se conocen las tareas a realizar y son

agrupadas en subconjuntos que forman una estación. Se repite la misma acción en cada ciclo.

Líneas de modelos mixtos

Diversos modelos de una familia de producto son fabricados simultáneamente. Los procesos de

producción son bastante similares, con la única excepción de los atributos y características

opcionales. Por lo tanto, se debe asociar un subconjunto de tareas que se distinguen entre cada

modelo y dividirse entre las estaciones. El número de subconjuntos diferentes asociados a cada

estación corresponderá al número de modelos producidos.


3

Líneas multimodelo

En este caso, varios productos son fabricados en lotes separados. La línea puede reequilibrarse en

cada lote y deben tenerse en cuenta los tiempos de preparación entre la producción de cada lote.

2.2.2 Ambiente industrial general

Los ambientes industriales considerados en los problemas de balanceo de líneas (Battaïa y Dolgui,

2013) se distinguen en tres tipos de entornos: mecanizado, de ensamblado y desensamblado.

Entorno mecanizado

Las piezas del producto se completan mediante operaciones mecanizadas. Generalmente, pueden

encontrarse muchas menos relaciones de precedencia entre las operaciones que en los entornos

de ensamblado y desensamblado. Sin embargo, puede haber muchas restricciones de

incompatibilidad que dificultan y/o prohíben la asignación de operaciones a la misma estación.

Entorno de ensamblado

El producto se obtiene mediante el montaje de una serie de componentes. Generalmente, su

diagrama de precedencia suele tener varios nodos en su inicio y dan como resultado un único

nodo final. Las líneas de ensamblado pueden estar formadas por distintas configuraciones, desde

trabajadores asignados a cada puesto realizando tareas manuales hasta completamente

automatizadas.

Entorno desensamblado

De un producto inicial se obtienen una serie de piezas o subconjuntos. Las líneas de

desensamblado suelen ser manuales y su diagrama de precedencias no es generalmente la

inversión del diagrama de precedencia de ensamblado del producto inicial.

2.2.3 Metodologías del proceso productivo

Dentro de los ambientes industriales comentados, Thomopoulos (2014) indica diferentes

tipologías en función de su proceso productivo. La finalidad de producción puede ser para

almacenar el producto fabricado, producir tras un pedido previo o una combinación de ambos.

Producir para almacenar (Make-to-Stock, MTS)

Se produce un producto específico en función de la demanda que se prevé tener. Una vez

finalizado, es almacenado hasta su venta. Este método reduce costes de producción y mejora el

servicio al cliente, ya que hace posible disponer del producto demandado en un menor tiempo.

Producir por pedido (Make-to Order, MTO)

La producción inicia cuando un cliente realiza un pedido. Este método tiene un coste más elevado,

pero permite la personalización del producto que demanda el cliente.


4

Ensamblar por pedido (Assemble-to-Order, ATO)

El método ATO es una combinación de los dos métodos anteriores. La producción se divide en

dos partes. En la primera parte se produce para almacenar los componentes o piezas del producto

que son comunes para cualquier producto final, y en la segunda parte se produce por pedido. Al

recibir el pedido del consumidor, se realiza el proceso productivo restante en función de las

especificaciones del cliente.

Estas metodologías de producción pueden aplicarse en distintos modelos. En el caso de ser mixtos

se encontrarían, por un lado, los problemas principales comunes: el problema conseguir la

uniformidad de carga de trabajo para cada trabajador, la minimización del tiempo de inactividad

y la congestión durante el turno en todas las estaciones. La producción destinada a almacenaje

mantiene el número de unidades a producir. Sin embargo, en el modelo de producción mixta para

la fabricación por pedido, a diferencia del modelo anterior, las unidades finales producidas y los

tiempos de estaciones son diferentes en cada pedido. De esta manera, se debe determinar la

secuencia de los pedidos para cada turno teniendo en cuenta los problemas comunes principales.

A parte de los métodos comentados, Thomopoulos (2014) añade una metodología llamada

ensamblado por estación. En este modelo de montaje simple, las estaciones están formadas por

un operario que inicia y finaliza el montaje del producto. Puede clasificarse como un modelo de

ambiente industrial.

2.2.4 Diseño de línea (Line Layout)

El diseño de la línea (Battaïa y Dolgui, 2013) define las reglas para el procesamiento de tareas en

las estaciones de trabajo. Entre los diseños pueden encontrarse líneas rectas básicas, líneas rectas

con múltiples lugares de trabajo, líneas en forma de U, líneas con transferencia circular y líneas

asimétricas.

Líneas rectas básicas

Cada pieza del producto pasa por una serie de estaciones de trabajo en una instalación continua.

En cada estación se realizan un conjunto tareas que se ejecutan una tras otra.

Líneas rectas con múltiples lugares de trabajo

Las estaciones de trabajo se encuentran alineadas. En las estaciones de trabajo se instalan zonas

de trabajo en paralelo, serie o activados mixtos. De esta forma, los trabajadores o equipos del

puesto de trabajo pueden desempeñar la tarea sobre cada pieza de forma simultánea, secuencial o

en serie-paralelo, respectivamente.

En el caso de las líneas de paralelo, en una estación de trabajo se realizarían una serie de tareas

simultáneamente que desencadenarían en un producto.

En una estación de trabajo con lugares de trabajos en serie, el producto es transportado de una

tarea hacia la siguiente.


5

Las estaciones con lugares de trabajo activados mixtos realizan las tareas paralelamente que se

transportan hacia las siguientes tareas relacionadas. Toda la línea acaba completando un producto

final.

Líneas de forma en U

Como su nombre indica, la línea se diseña en forma de U, ofreciendo la posibilidad de que los

trabajadores situados entre dos partes de la línea desarrollen tareas simultáneamente en dos o más

piezas de trabajo durante el mismo ciclo. En este caso, el mismo trabajador realiza varios

subconjuntos de tareas asociadas a diferentes estaciones de trabajo.

Líneas con transferencia circular

Las estaciones de trabajo son instaladas alrededor de una mesa giratoria en la cual se cargan,

descargan y transportan las piezas de una estación a otra. Si sólo se realiza una única vuelta para

completar el producto en una parte de la línea, equivale a una línea recta básica. En caso de

trabajar a ambos lados de la línea se considera una línea con múltiples lugares de trabajo en

paralelo. En el caso de transferencia multi-turno, el conjunto de tareas asignadas a un puesto de

trabajo debe estar dividido en los diferentes ciclos correspondientes al número de turnos de la

mesa. Es decir, en cada puesto de trabajo el operador tendrá tareas a realizar en el primer ciclo o

vuelta y tareas que correspondan a los siguientes ciclos hasta la finalización del producto.

Líneas asimétricas

El objetivo del diseño de las líneas de producción asimétricas es mantener una configuración de

línea común para todos los productos fabricados durante el mayor tiempo posible. Por un lado,

esta estrategia reduce el riesgo asociado al aumento de variedad de los productos fabricados. Por

otro lado, el problema de balanceo de línea y de optimización del diseño deben resolverse

conjuntamente para elaborar la línea final.

2.2.5 Duración de tareas

Según la variabilidad de los tiempos de las tareas, C. Becker y A. Scholl (2003) clasifican tres

tipologías a partir de los estudios de Johnson (1983), Buzacott (1990), Robindon (1990), Boucher

(1987), entre otros.

Líneas de producción de tiempo determinista

Los tiempos entre tareas son mínimos. Normalmente esta tipología se aplica a estaciones

automatizadas o en líneas que realizan tareas simples.

Líneas de producción de tiempos estocásticos

Las variaciones de tiempo entre tareas son considerables. Normalmente es debido a la

inestabilidad de los humanos respecto a la tasa de trabajo, la habilidad y la motivación, como

también la sensibilidad al fracaso de los procesos complejos.

Líneas de producción con tiempos dinámicos o dependientes

En este caso los tiempos de producción varían, por ejemplo, debido al aprendizaje o la mejora de

un proceso de producción.


6

2.2.6 Flujo de piezas

Otra característica que influye en el equilibrado de líneas es el flujo de piezas, que depende de la

conexión de los movimientos entre las tareas de producción. Buzacott y Shanthikumar (1993)

distinguieron dos casos principales. Los siguientes tipos de flujos de piezas son valorados cuando

las líneas de producción son espaciadas, es decir, existen tiempos entre la finalización de una

tarea y el inicio de la siguiente (Boysen, et al., 2006).

Flujo síncrono

En el flujo síncrono, las piezas que finalizan una estación se mueven hacia la siguiente. En este

caso, las estaciones que tienen periodos de tiempo más cortos quedan a la espera de la estación

con mayor periodo de tiempo o carga de trabajo. En esta metodología, como el tiempo de ciclo

es idéntico en todas las estaciones, será el que represente la estación de mayor periodo de tiempo.

Flujo asíncrono

Contrariamente al caso anterior, cuando una pieza finaliza una estación queda a la espera de

iniciar la siguiente, mientras la estación precedente continúa realizando las tareas que la

componen. Por lo tanto, será necesaria la instalación de buffers. Cuando la siguiente estación

requiere de un tiempo inferior a su precedente, se produce lo denominado bloqueo o estación

hambrienta, la cual se mantiene a la espera de recibir el producto en proceso de su estación

precedente.

Definición 1. Buffer

Un buffer es un lugar de almacenamiento de productos procesados de la estación precedente

en la cual su tiempo es inferior al tiempo de la siguiente estación.


7

Figura 1. Tipos de líneas de montaje.

Fuente: Elaboración propia.

Tipos de líneas de montaje

Número de modelos

Simples (monomodelo)

Mixtos

Multimodelo

Ambiente industrial

Mecanizado

Ensamblado

Desensamblado

Ensamblado por estación

Metodología de producción

Producción para almacenar

Producción por pedido

Ensamblado por pedido

Diseño de la línea

Líneas rectasLíneas rectas

multiples

Paralelo

Serie

Activos Mixtos

Líneas de forma en U

Líneas con transparencia

circular

Líneas asimetricas

Duración de tareas

Determinista

Estocástica

Dependiente

Flujo de piezas

Síncrona

Asíncrona


8

2.3 PROBLEMAS DE EQUILIBRADO DE LÍNEAS

El problema de equilibrado de líneas de montaje simple (Simple Assembly Line Balancing

Problem, SALBP, en inglés) surge en la producción en masa de un solo producto en una línea de

montaje constante. SALBP fue introducido por Baybars (1986) junto al problema de equilibrado

de línea general (General type of the Simple Assembly Line Balancing Problem, GALBP, en

inglés). Ghosh y Gagnon (1989) ampliaron las características que distinguían el tipo de

equilibrado de cadenas simple del tipo general. También se han reconocido los problemas de

balanceo de línea de desmontaje (Disassembly Line Balancing Problem, DLBP, en inglés) y de

transferencia (Transfer Line Balancing Problem, TLBP, en inglés), ambos comparten similitudes

con los GALBP. TLBP se aplica en líneas de montaje en serie con máquinas de uso múltiple

ordenadas linealmente (Battaïa y Dolgui, 2008).

Los SALBP se caracterizan por tener una estructura lineal simple. Las tareas disponen de

restricciones de precedencia, son indivisibles y de duración determinística. Además, los tiempos

y orden del proceso son independientes en cada estación.

Los GALBP no se clasifican dentro de los SALBP. En su diferencia, integran todos los modelos

mixtos y con estaciones en paralelo.

Variables del equilibrado de líneas

𝑛 Número de tareas

𝑡𝑗, (𝑗 = 1, … , 𝑛) Tiempo de operación. Normalmente expresado en minutos.

𝑚 Número de estaciones. Subconjunto de tareas-

𝑇 Tiempo de producción. Tiempo total de trabajo durante un turno

dedicado a la producción. Normalmente se expresa en minutos.

𝑁 Unidades de producción. Número total de unidades completadas por

turno.

𝑜 Operadores. Número mínimo de operadores (1) necesarios para poder

producir las N unidades en T.

𝑐 Tiempo de ciclo (2). Tiempo entre dos unidades de producto

completadas.

𝑐𝑜 Tiempo promedio del operador determinado por (3).

𝑡(𝑆𝑘) Tiempo de estación (7). Tiempo de desde que entra un producto en

proceso a una estación hasta que finaliza las tareas de esta.

Variables para determinar la eficiencia de la línea

𝑑 Eficiencia de la línea o retraso del equilibrio determinado por (4).

𝐸 Ratio de eficiencia (5). Mide la porción de tiempo en que los

trabajadores están ocupados trabajando en las unidades.


9

Fórmulas para el cálculo de variables del equilibrado de líneas

Número mínimo de operadores

𝑜 = ∑ 𝑡𝑗 · 𝑁/𝑇

(1)

Tiempo de ciclo

𝑐 = 𝑇/𝑁

(2)

Tiempo promedio del operador

𝑐𝑜 = ∑ 𝑡𝑗/𝑜

(3)

Eficiencia de la línea

𝑑 = (𝑐 − 𝑐𝑜)/𝑐

(4)

Ratio de eficiencia

𝐸 = 𝑐𝑜/𝑐

(5)

2.3.1 Funcionamiento SALBP

El proceso de producción (Scholl, 1995) se subdivide en 𝑛 tareas cuyos tiempos de operación

𝑡𝑗, (𝑗 = 1, … , 𝑛) se asumen como constantes integrales. Debido a restricciones tecnológicas, se

consideran restricciones de precedencia, las cuales pueden representarse mediante diagramas de

precedencia o tablas que indiquen un listado de las tareas del proceso junto con su tiempo de

operación y sus respectivas precedencias.

En el diagrama expuesto (Figura 2), cada tarea se representa con un nodo y cada conexión entre

nodos indica la precedencia entre las tareas, es decir, el arco o borde (𝑖, 𝑗) que indica que una

tarea 𝑖 deba completarse antes de iniciarse la tarea 𝑗. El número indicado en los nodos se refiere

a la distinción entre las tareas.


10

Figura 2. Diagrama de precedencia

Fuente: Elaboración propia

El número de estaciones 𝑚 por el que está formada la línea de montaje están conectadas por una

cinta transportadora. En cada estación se realizan un subconjunto de tareas en unidades de

producto consecutivas que se mueven a lo largo de la línea a velocidad constante. El tiempo de

ciclo 𝑐 también puede definirse como el intervalo de tiempo fijo disponible para operar una

unidad en cada estación. La tasa de producción (6) hace referencia al número de unidades

producidas (normalmente expresadas por minutos u horas), y se representa como el valor inverso

al tiempo de ciclo.

𝑇𝑎𝑠𝑎 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖ó𝑛 =1

𝑐

(6)

2.3.2 Funcionamiento GALBP

Las tareas son asignadas a cada estación de la línea de montaje, cumpliendo con el orden de

precedencia. En cada estación, en función de las tareas que la formen, tiene una determinada carga

de estación 𝑆𝐾, siendo 𝐾 el número de estación 𝑘 = 1, … , 𝑚). Para cada borde (𝑖, 𝑗) del grafo de

precedencia, la relación ℎ ≤ 𝑘 debe cumplirse si 𝑖 ∈ 𝑆ℎ y 𝑗 ∈ 𝑆𝑘 (Scholl, 1995).

El tiempo de estación 𝑡(𝑆𝑘) es igual a la suma de los tiempos de operación de todas las tareas

incluidas en el conjunto 𝑆𝑘.

𝑡(𝑆𝑘) = ∑ 𝑡𝑗𝑗 ∈ 𝑆𝑘

(7)


11

El tiempo máximo de la estación determina el tiempo de ciclo 𝑐. Pata todas las estaciones 𝑘 con

un tiempo de estación inferior a 𝑐, resulta un tiempo inactivo en valor de 𝑐 – 𝑡(𝑆𝑘).

El objetivo es encontrar un tiempo de ciclo 𝑐 y número de estaciones 𝑚 que minimice el tiempo

total de inactividad.

La función objetivo (8) sería la siguiente:

min(𝑚 ∗ 𝑐 − 𝑡𝑠𝑢𝑚)

(8)

Donde,

𝑡𝑠𝑢𝑚 = ∑ 𝑡𝑗

𝑗=𝑛

𝑗=1

(9)

2.3.3 Versiones de SALBP y GALBP

Pueden considerarse diferentes problemas de equilibrado de líneas que dan lugar a diversas

versiones para SALBP y GALBP, mostradas esquemáticamente a continuación en la figura 3.

Scholl (1995) considera las siguientes versiones de SALBP:

- SALBP – 1. Su función es minimizar el número de 𝑚 estaciones para un tiempo de ciclo

𝑐 dado. Este problema se presenta siempre que se debe instalar un nuevo sistema de línea

de montaje y es posible estimar bien la demanda externa.

- SALBP – 2. Su función es minimizar el tiempo de ciclo 𝑐 asignado para un número 𝑚

de estaciones. Este caso se produce cuando hay cambios en el proceso de producción

debido, por ejemplo, a reducciones de los tiempos de operación y otras variaciones del

plan de montaje.

También pueden denotarse las siguientes versiones (Kamal y Martínez, 2011):

- SALBP – F. Es un problema de factibilidad en el cual se dan el número 𝑚 de estaciones

y el tiempo de ciclo 𝑐. Se decide si existe una asignación de las tareas a las estaciones que

no exceda el tiempo máximo de estación al tiempo de ciclo.

- SALBP – E. Este tipo de problema es considerado como la versión más general de ALBP.

Está asociado con maximizar la eficiencia de la línea mediante la minimización del

tiempo de ciclo y el número de estaciones.

- Otras versiones: SALBP – 3, SALBP – 4 y SALBP – 5. Todas se emplean con el objetivo

de maximizar la fluidez de carga de trabajo; en SALBP – 3 mediante maximizar el

parentesco laboral y en SALBP – 4 maximizando múltiples objetivos.


12

En la siguiente tabla se pueden observar las diferentes versiones indicando el tiempo de ciclo

y número de estaciones.

Versión Tiempo de Ciclo Número de

Estaciones

SALBP - F Fijo Fijo

SALBP - 1 Fijo Mínimo

SALBP - 2 Mínimo Fijo

SALBP - E Mínimo Mínimo

Tabla 1. Versiones del SALBP

Fuente: Escobar, DF, Garcés, JA y Restrepo, JH, 2012. Aplicación de la programación entera

binaria para resolver el problema simple de balanceo de línea de ensamble: un caso de estudio.

[Tabla] reproducida en Scientia et Technica. Pereira: Universidad Tecnológica de Pereira.

(Modificado)

En el caso de los GALBP destacan cuatro tipos de problemas (Hernán, J., et al., 2008):

- Problema de equilibrado de líneas-U (U-line Assembly Line Balancing Problem,

UALBP, en inglés). Se trabaja en una línea de forma U, que posibilita una mayor

asignación de tareas a las estaciones y aumento de la eficiencia de resolución del

problema. Dentro de esta tipología se distinguen los siguientes en función de la

finalidad de resolución:

- UALBP – 1, para minimizar el número de estaciones.

- UALBP – 2, para minimizar el tiempo de ciclo.

- UALBP – E, para maximizar la eficiencia de la línea.

- Problema de equilibrado de líneas de montaje mixto (Mixed-Model Assembly Line

Balancing Problem, MALBP, en inglés). Las tipologías son las mismas que indicadas

anteriormente, para problemas MALBP – 1, MALBP – 2 y MALBP – E.

- Problema de equilibrado de líneas robotizadas (Robotic Assembly Line Balancing

Problem, RALBP, en inglés). Permite optimizar la ejecución de tareas.

- Problema de equilibrado de líneas con objetivos múltiples (Multi-Objective Assembly

Line Balancing Problema, MOALBP, en inglés). Este tipo de problema se caracteriza

por tratar de resolver el problema con más de un objetivo.


13

Figura 3. Principales problemas de equilibrado de líneas.


2.4 SOLUCIONES A PROBLEMAS DE EQUILIBRADO DE LÍNEAS

La aparición continua de problemas de optimización combinatoria complejos ha dado lugar a

diversas propuestas de algoritmos para tratar de solucionarlos. Las técnicas pueden clasificarse

básicamente en algoritmos exactos y aproximados (Alonso, et al, 2003). Las tipologías más

reconocidas de ambas técnicas se muestran en la figura 4.

Los algoritmos exactos se basan en la búsqueda de una solución óptima. Las técnicas utilizadas

son, por ejemplo, procesos de Vuelta Atrás (backtracking), Ramificación y poda (Branch and

Bound), programación dinámica, programación linear y entera, etc. Los algoritmos exactos

muestran un rendimiento pobre para muchos problemas, de modo que se han desarrollado

múltiples tipos de algoritmos aproximados que proporcionan soluciones de alta calidad.

Los algoritmos aproximados se clasifican principalmente en algoritmos constructivos y

algoritmos de búsqueda local. Los algoritmos constructivos se basan en generar soluciones desde

cero añadiendo componentes a cada solución, lo son por ejemplo las heurísticas de construcción

voraz o heurísticas greedy. La ventaja principal de este tipo de heurísticas es la rapidez y la calidad

de la solución, sin embargo, no puede garantizarse que la solución sea óptima.

Principales tipos de problemas de

equilibrado de líneas

Simple (SALBP)

SALBP - 1

SALBP - 2

SALBP - E

SALBP - F

General (GALBP)

UALBP

MALBP

RALBP

MOALBP


14

Para refinar la búsqueda obtenida se utiliza una búsqueda local, aunque, por otro lado, puede

producir que la solución óptima local se encuentre lejana a la solución óptima global. Para mejorar

la calidad de las soluciones se han diseñado las técnicas metaheurísticas, una de las mejores

aproximaciones para atacar los problemas de optimización combinatoria.

Entre las metaheurísticas más reconocidas se encuentran las siguientes, explicadas más

detalladamente a continuación.

- Enfriamiento simulado (Kirkpatrick, S., Gelatt Jr., CD y Vecchi MP, 1983).

- Búsqueda tabú (Glover, F., 1989 y Laguna, M., 1997).

- Búsqueda local iterativa (Iterative Local Search) (Lourenco, HR, et al, 1995).

- Algoritmos de búsqueda local con vecindario variable (Variable Neighborhood Search)

(Hansen, P., y Mladenovic, N., 1997).

- Procedimiento de búsqueda codiciosa adaptativa aleatoria (Greedy Randomized

Adaptative Search Procedures, GRASP) (Feo, TA, C. Resendeen, CM, 1989).

- Algoritmos evolutivos (Back, T., 1996, Fogel, D., Michalewicz, Z., et al, 2005).

- Optimización basada en Colonia de Hormigas (Ant Colony Optimization, ACO) (M.

Dorigno, M., 1992, Maniezzo y Colorni, 1997).


15

Figura 4. Tipologías de algoritmos para la solución de problemas de optimización

combinatoria.


Algoritmos para problemas de optimización combinatoria

Algoritmos Exactos

Vuelta Atrás

Ramificación y poda

Programación dinámica

Programación linear y entera

Algoritmos Aproximados

Algoritmos constructivos

Heurísticas de construcción voraz

Heurísticas greedy

Algoritmos de búsqueda local

Enfriamiento simulado

Búsqueda tabú

Búsqueda local con vecindario

variable

GRASP

Algoritmos evolutivos

Ant Colony Optimization


16

3 HEURÍSTICAS Y METAHEURÍSTICAS

Etimológicamente, la heurística se encuentra orientada al estudio del descubrimiento y a la

invención. El término proviene de la palabra griega heuriskein cuyo significado es “encontrar” o

“descubrir”.

“El calificativo heurístico se refiere a la técnica, método o procedimiento inteligente de realizar

una tarea que no es producto de un análisis formal, sino de conocimiento experto sobre la tarea.

De esta manera, el procedimiento heurístico trata de aportar soluciones a un problema con un

buen rendimiento, en referencia a la calidad de las soluciones y a los recursos empleados.

(Melian, B., Pérez, JA., et al., 2003)”

Las metaheurísticas (Alonso, S., Cordón, O., et al, 2003) son reconocidas como una de las mejores

aproximaciones para atacar los problemas de optimización combinatoria.

Las soluciones obtenidas de un procedimiento heurístico no pueden comprobarse que sean

óptimas. Los problemas por resolver mediante métodos heurísticos, ya se clasifiquen como

problemas de optimización, sean o no determinísticos, cumplen algunas de las siguientes

características:

- Se desconoce método exacto para la resolución del problema.

- El método exacto para la resolver el problema es costoso o inviable.

- El método heurístico proporciona una solución más fiable que un método exacto.

- El modelo matemático es demasiado grande, no lineal o complejo.

- Las soluciones obtenidas no son viables al asumir suposiciones o aproximaciones para

simplificar el problema.

- Se requiere el uso del método heurístico en alguna parte del procedimiento global para

llegar a la solución, ya sea para encontrar una buena solución de partida o su uso en un

paso intermedio del procedimiento.

3.1 CLASIFICACIÓN DE LOS MÉTODOS HEURÍSTICOS

Los métodos heurísticos son diseñados mayoritariamente para resolver problemas específicos, lo

que complica su clasificación debido a su gran variedad de distinta naturaleza. Los métodos

heurísticos más conocidos son los siguientes:

- Método de Descomposición. El problema se descompone en subproblemas más sencillos

de resolver.

- Métodos Inductivos. Consiste en identificar las propiedades o técnicas más fáciles de

analizar y aplicarlas al problema completo.


17

- Métodos de Reducción. Tiene como objetivo simplificar el problema a partir de la

restricción del espacio de soluciones mediante la introducción de propiedades que en su

mayoría dan lugar a buenas soluciones.

- Métodos Constructivos. Consisten en construir paso a paso la solución del problema.

Inicialmente, la estructura que presenta la solución se encuentra vacía y se basa en

incorporar elementos iterativamente. Con frecuencia, son métodos deterministas y buscan

la mejor elección en cada iteración.

- Métodos de Búsqueda Local. El procedimiento inicia con una solución del problema con

la finalidad de mejorar la misma mediante modificaciones locales. El algoritmo repite la

acción utilizando la mejor solución actual hasta conseguir su óptima.

Los siguientes tres métodos heurísticos se basan en tomar decisiones simples, aplicados en líneas

simples o monomodelo.

- Método de Tongue (1960).

- Método de Moodie y Young (1965). El método se utiliza para resolver problemas de

balanceo de líneas. Se divide en dos fases, la primera de ellas determina las estaciones

y actividades que la forman y la segunda fase, vuelve a distribuir las actividades con

la finalidad de equiparar el tiempo de ocio entre estaciones (Anon.).

- Método de Helgeson y Birnie (1961). El método, también conocido como método de

los pesos posicionales, consiste en evaluar un peso para cada tarea y asignar la

siguiente tarea a las estaciones en función del su peso, siempre y cuando respecte las

precedencias y tiempo de ciclo. El peso representa la suma del tiempo de la tarea y

de aquellas que la siguen (Tinoco, et al., 2018).

Entre los métodos heurísticos, también se encuentra el método basado en prioridades, en los

que se aplican reglas de prioridad para clasificar las tareas en función de su peso específico

(prioridad). Entre las tareas disponibles, se asigna la tarea prioritaria a una estación (Scholl y

Voß, 1996). En la literatura pueden encontrarse una gran variedad de reglas de prioridad,

algunas de ellas se muestran en el apartado 4.5.1, donde fueron aplicadas por Bautista y Pereira

(2002) en un caso real para la resolución del problema de equilibrados de líneas de montaje

mediante un algoritmo de colonia de hormigas.

Dentro de las heurísticas, se encuentran procedimientos específicos y otros más generales. Los

procedimientos específicos suelen obtener un rendimiento más significativo, debido a que cada

problema tiene un diseño propio. Sin embargo, los procedimientos generales son más fáciles de

comprender, son poco sensibles y pueden adaptarse a distintos contextos de aplicación o

modificaciones del modelo. Dicho de otro modo, estos procedimientos se basan en un principio

sencillo, adaptable y robusto. Las heurísticas generales pueden mejorar su rendimiento a partir de

estrategias inteligentes, denominadas metaheurísticas.


18

Las metaheurísticas son estrategias generales para construir algoritmos que quedan por encima

de las heurísticas, por ello se antepone el sufijo meta, de significado “mas alla”, “a un nivel

superior”, al término heurística.

3.1.1 Tipos de metaheurísticas

Los tipos de metaheurísticas se establecen en función del tipo de procedimiento heurístico. Los

tipos fundamentales son las metaheurísticas de relajación, constructivas, evolutivas, de

descomposición y de memoria a largo plazo.

Metaheurísticas de relajación

Las metaheurísticas de relajación son estrategias para aplicar relajaciones del problema en el

diseño de heurísticas, con el objetivo de resolver el problema original más fácilmente.

La relajación de un problema es una modificación del modelo, de manera que este sea más simple

tras eliminar, debilitar o modificar restricciones (u objetivos) del problema real. El objetivo del

uso de relajaciones es simplificar el problema, mejorar la eficiencia de los procedimientos y

proporcionar muy buenas soluciones al problema original.

El ajuste a la realidad de los procedimientos de resolución y las soluciones propuestas del

problema viene determinado por el grado de simplificación. La resolución de un modelo y la

implementación de sus soluciones suelen ser más complejas a mayor ajuste a la realidad.

Metaheurísticas constructivas

Las metaheurísticas constructivas implantan estrategias para seleccionar las componentes con las

que se construye una buena solución del problema. Una estrategia popular que se ha nombrado

anteriormente es la heurística voraz o greedy y su aportación en la primera fase de la

metaheurística GRASP (Greedy Randomized Adaptive Search Procedure). La estrategia greedy

consiste en construir soluciones iniciales factibles de forma aleatoria o semi-aleatoria. La

metaheurística GRASP está formada por dos fases que se repiten en cada iteración: fase

constructiva y fase de explotación. En la primera de ellas se aplicaría la estrategia comentada, de

manera que se crearía una solución factible, y en la segunda fase se mejoraría la solución obtenida

mediante una búsqueda local.

Metaheurísticas evolutivas

Las heurísticas evolutivas consisten en la interacción entre los miembros de la población

(conjunto de soluciones) frente a las búsquedas guiadas por la información de soluciones

individuales.

Las metaheurísticas evolutivas establecen estrategias para conducir la evolución de conjuntos de

soluciones. Existen diferentes metaheurísticas evolutivas en función de la forma en que combinan

la información, si sus procedimientos son aleatorios o sistemáticos.


19

Otros tipos de metaheurísticas

Metaheurísticas de descomposición

Las metaheurísticas de descomposición establecen pautas para determinar los subproblemas,

(más fáciles de resolver que los originales) y así construir una solución del problema original.

Se consideran metaheurísticas intermedias entre las de relajación y constructivas.

Metaheurísticas de memoria a largo plazo

Las metaheurísticas de memoria a largo plazo utilizan la información sobre las características y

propiedades comunes de las soluciones de alta calidad o decisiones de mejora durante el proceso

de solución. Este tipo de metaheurísticas, constituyen el caso más destacado de las

metaheurísticas de aprendizaje, situadas entre las de arranque y búsqueda tabú.

3.1.2 Metaheurísticas de búsqueda

Las metaheurísticas de búsqueda establecen estrategias para recorrer el espacio de soluciones de

un problema transformando de forma iterativa soluciones de partida. En un problema de

optimización, su procedimiento se basa en realizar recorridos sobre el espacio de soluciones

alternativas y seleccionar la mejor solución encontrada en el recorrido. Es necesario tener en

cuenta un indicador de la calidad de las soluciones para determinar los movimientos y el criterio

de parada, siendo este último el que determina cuándo se considera resuelto un problema sin

disponer de información de lo cerca que se encuentra de solucionarlo.

Por su generalidad, las metaheurísticas de búsqueda se realizan sobre problemas de optimización.

Estos problemas consisten en determinar la solución óptima (𝑆, 𝑓) , siendo 𝑆 el espacio de

soluciones y 𝑓 la función objetivo. La solución óptima es una solución factible 𝑥∗ 𝑆 tal que

𝑓(𝑥∗) 𝑓(𝑥) para cualquier 𝑥 𝑆.

El problema consiste en seleccionar el valor 𝑥𝑖 asignado a cada variable 𝑋𝑖 del dominio 𝑈𝑖, que,

sometido a ciertas restricciones, optimiza una función objetivo 𝑓. Siendo 𝑋 un conjunto finito de

variables que representa las soluciones alternativas 𝑋 = {𝑋𝑖: 𝑖 = 1, 2, … 𝑛} y 𝑈 el conjunto de

valores posibles de cada 𝑛 variables (dominio o universo).

Las metaheurísticas de búsqueda utilizan usualmente procedimientos de búsqueda por

entornos. Dichos procedimientos recorren el espacio de soluciones U mediante un conjunto de

transformaciones o movimientos, generando una solución inicial y seleccionando un movimiento

para modificar la solución hasta cumplir el criterio de parada. Existe la denominación “vecinas”

a las soluciones obtenidas de otras mediante un movimiento posible. El conjunto de movimientos

da lugar a una estructura de entornos. Existen dos características en el procedimiento de búsqueda

Definición 2. Problema de optimización.

Un problema de optimización es aquel cuya solución implica encontrar en un conjunto de

soluciones candidatas alternativas aquella que mejor satisface unos objetivos.


20

por entorno; por un lado, la exploración referente a la capacidad del método para explorar

diferentes regiones del espacio de búsqueda y, por otro lado, la explotación debido al esfuerzo y

capacidad de mejorar soluciones.

Búsquedas Locales

Una búsqueda local es un proceso que, dada una situación actual en la que se encuentra el

recorrido de búsqueda, selecciona iterativamente una solución de su entorno.

Las metaheurísticas de búsqueda local son estrategias o pautas generales para diseñar métodos de

búsqueda local, los cuales se basan en estrategias de estudio de soluciones del vecindario o

entorno de la solución que realiza el recorrido.

Dentro de las búsquedas locales, existen dos tipos: las búsquedas no informadas y las búsquedas

monótonas.

Búsquedas no informadas

Las estrategias de búsquedas por entornos no informadas sólo prestan atención a la estructura de

entornos en el espacio de búsqueda. Las metaheurísticas basadas en la búsqueda no informada

aportan estrategias para una exploración eficiente del espacio de búsqueda. Se pueden distinguir

tres tipos más usuales de metaheurísticas de búsqueda por entornos: exhaustiva, parcial y

aleatoria.

La búsqueda exhaustiva realiza un recorrido de un espacio de búsqueda en el que incluye todos y

cada uno de los elementos del espacio. En el caso de problemas de optimización, se realiza un

recorrido exhaustivo del espacio de soluciones del problema y se toma la mejor de ellas. Este tipo

de recorrido de búsqueda emplea primeramente una ordenación de todas las soluciones del

espacio y utiliza una transformación para obtener la siguiente solución en cada iteración.

En el caso de la búsqueda parcial, se examina una parte del espacio de búsqueda. Para los

problemas de optimización, la búsqueda parcial aporta la mejor solución examinada como

propuesta de solución. En caso de que la selección de soluciones a examinar sea al azar, se trata

de búsqueda parcial aleatoria (método de Monte Carlo).

Por último, la búsqueda aleatoria se trata de un recorrido aleatorio puro o uniforme en caso de

que la distribución de probabilidad en el entorno de la solución actual sea uniforme o equiprobable

(misma probabilidad de ser elegido). Las metaheurísticas de búsqueda por entornos aleatoria se

basan en seleccionar iterativamente al azar una solución del entorno de la solución actual.

Búsquedas Locales Monótonas

Las búsquedas locales monótonas utilizan la evaluación de la función objetivo para admitir sólo

cambios en la solución actual que supongan una mejora. Al utilizarse únicamente la información

en el entorno de la solución actual, a veces las búsquedas quedan atrapadas.


21

Como anteriormente en las búsquedas locales no informadas, es posible aplicar la aleatoriedad.

Las metaheurísticas de búsqueda monótona aleatoria seleccionan iterativamente una solución al

azar del entorno de la solución actual que es substituida por la solución actual en caso de

producirse una mejora.

Dentro de las búsquedas locales monótonas es posible encontrar las metaheurísticas de

intensificación oscilante, metaheurísticas de búsqueda local exhaustiva, metaheurísticas voraz,

metaheurística ansiosa y metaheurística golosa.

Las metaheurísticas de intensificación oscilante consisten en hacer oscilar sistemáticamente entre

dos valores extremos la intensidad de búsqueda. En caso de regular dinámicamente la intensidad

de búsqueda se trataría de una metaheurística de intensificación oscilante dinámica.

Las metaheurísticas de búsqueda local exhaustica maximizan el poder de explotación ya que

examinan todo el entorno de la solución actual.

La metaheurística voraz (Greedy) selecciona el mejor primero, siempre la mejor solución del

entorno. La metaheurística ansiosa (Anxious), en cambio, utiliza la regla de seleccionar el primero

mejor, la primera solución del entorno que mejore la solución actual, continuando el recorrido si

no se encuentra tal mejora. Para elegir el punto en el que comenzar el recorrido del entorno cuando

se utiliza una estrategia ansiosa, es posible utilizar las metaheurísticas golosas que procuran que

las soluciones vecinas a la primera solución escogida sean prometedoras, con la finalidad de

mejorar el poder de explotación de búsqueda.

Búsquedas Globales

Las búsquedas globales solucionan el principal inconveniente de las búsquedas locales, cuando

al acercarse a una solución óptima local, la solución queda atrapada en su entorno. Las búsquedas

globales utilizan herramientas para salir de esta situación y dan lugar a tres tipologías de

metaheurísticas de búsqueda global principales.

La metaheurística con arranque múltiple que utiliza procedimientos de búsqueda con arranque

múltiple (Multi-Start) basados en generar una muestra de soluciones iniciales o de arranque. De

esta manera, cada vez que la búsqueda quede estancada, vuelve a comenzar la búsqueda desde

otra solución inicial.

La metaheurística de entorno variable (Variable Neighborhood Search, VNS) consiste en

cambiar de forma sistemática la estructura de entorno en caso de no encontrar una solución mejor

a remplazar por la actual cuando ejecuta la búsqueda monótona local. También se encuentra la

búsqueda descendente por entornos variables (VND), que aplica una búsqueda monótona por

entornos y modifica la estructura de entornos al alcanzar mínimos locales.

Las metaheurísticas de búsqueda no monótona permiten movimientos que no producen una

mejora de la solución actual con la finalidad de, al menos a la larga, mejorar las soluciones

encontradas y utilizar la información histórica del proceso. Gracias a dicha información histórica,

es posible controlar cuando el recorrido se estanca en un mínimo local y evitar así los ciclos. Entre


22

las metaheurísticas de búsqueda no monótona destacan las metaheurísticas de búsqueda

probabilística, las cuales seleccionan aleatoriamente un vecino de la solución actual que la

remplaza con cierta probabilidad. El Recocido Simulado (Simulated Annealing, SA) representa

el caso más importante de las metaheurísticas de búsqueda global con criterio de aceptación

probabilístico. Al principio utiliza una probabilidad de aceptación de nuevas soluciones peores

(que es función exponencial de la modificación de la función objetivo) y a medida que el

algoritmo avanza, la probabilidad disminuye mejorando la solución. Otras metaheurística

fundamental de búsqueda no monótona es la metaheurística de búsqueda con memoria o

Búsqueda Tabú (Tabu Search, TS), que comprende las estrategias que tratan de utilizar la

memoria del proceso de búsqueda para mejorar su rendimiento. Su propósito principal es evitar

la repetición prematura de las mismas soluciones en el recorrido evitando ciertos movimientos o

soluciones ya visitadas marcadas en una lista como tabús. Inicialmente, se utilizaba el registro de

las últimas soluciones, pero posteriormente se introdujo la memoria a medio o largo plazo, el uso

de este último se conoce como Búsqueda Reactiva (Reactive Search, RS).

Búsquedas basadas en poblaciones

Las búsquedas basadas en poblaciones o en grupo reemplazan la solución actual por un conjunto

de soluciones que recorren conjuntamente el espacio actual de soluciones interaccionando entre

ellas.

Por un lado, una de las estrategias de búsqueda en grupo es el Algoritmo Genético que en los

problemas de optimización realiza lo siguiente. Primeramente, se establece una forma de

evaluación de la función objetivo, se identifican soluciones que pertenecen a los individuos que

puedan formar parte de la población de búsqueda y se les asigna un código (cromosoma del

individuo) en función del número de genes y sus formas alternativas (alelos). Seguidamente, la

población evoluciona de acuerdo la estrategia de selección asignada. Las operaciones de los

individuos pueden realizarse por mutación modificando al azar el alelo del gen y diversificar así

el espacio de búsqueda, o por cruce produciendo un individuo (hijo) en base al cruce entre los dos

individuos (padres). En este caso, los individuos que representan soluciones del problema son

manipulados en busca de la solución óptima.

Los Algoritmos de Estimación de Distribuciones (EDA) son algoritmos evolutivos que utilizan

una colección de soluciones para realizar trayectorias de búsqueda evitando mínimos locales. La

población evoluciona en base a una estimación y simulación de la distribución de probabilidad

conjunta.

La metaheurística de Búsqueda Dispersa (Scatter Search, SS) utiliza un conjunto de buenas

soluciones para conducir la búsqueda y mejora las herramientas con las que combina las

soluciones, manteniendo así el grado de diversidad y llegando a la solución óptima del problema.

El reencadenamiento de camino (Path Relinking, PR) es una metaheurística que trata de generar

soluciones explorando las trayectorias que conectan soluciones de alta calidad.


23

Otras metaheurísticas de búsqueda

Existen otras metaheurísticas de cierta relevancia inspiradas en distintos fenómenos de la

naturaleza, en las cuales se destacan las siguientes.

Las redes neuronales artificiales surgieron de modelos de sistemas nerviosos naturales formados

por unidades de cómputo (neuronas) interconectadas. Se aproximan a la solución óptima a partir

de una red de soluciones del problema y la función objetivo.

La metaheurística de optimización extrema o extremal (Extreme Optimization, EO) se encuentra

inspirada en procesos autoorganizativos frecuentes en la naturaleza utilizando modelos de

evolución de ecosistemas que llevan a la extinción a las componentes mal adaptadas del sistema.

La metaheurística evolutiva de optimización de partículas inteligentes (Particle Swarm

Optimization, PSO) inspirada en el comportamiento social de las bandadas de pájaros o bancos

de peces, en la cual la mejor solución encontrada se hace líder de la bandada.

Las metaheurísticas de sistemas de hormigas (Ant Systems, AS) inspirada en el comportamiento

de las colonias de hormigas, de las que se hablará en profundidad en el siguiente apartado.


24

4 ALGORITMOS DE OPTIMIZACIÓN DE COLONIA DE

HORMIGAS

4.1 ORÍGENES DE LA OPTIMIZACIÓN DE COLONIAS DE HORMIGAS

4.1.1 Inspiración Biológica

En la década de 1940, el entomólogo francés Pierre-Paul Grassé observó que algunas especies de

termitas reaccionan a “estímulos significativos”. Estas reacciones pueden actuar como nuevo

estímulo significativo tanto para el insecto que las produjo como para el resto de los insectos de

la colonia. Este tipo de comunicación se conoce como estigmergia y se caracteriza por ser

indirecta, no simbólica, estar mediada por el medio ambiente y de disponer de información local.

La estigmergia también es el método de comunicación de muchas especies de hormigas, en su

caso mediante senderos de feromonas. Se ha demostrado que este sistema de comunicación les

permite encontrar caminos más cortos entre su nido y fuentes de alimento (Dorigo, et al., 2006).

Experimento del doble puente

Las hormigas son insectos sociales que viven en colonias y su objetivo es la supervivencia de la

colonia en lugar de la supervivencia del individuo.

Con la finalidad de estudiar el comportamiento de seguimiento entre hormigas y la puesta de

feromonas, Deneubourg, et al. (1990) realizaron un experimento conocido como “Experimento

del doble puente”.

El experimento se basa en introducir una colonia de hormigas conectadas con una fuente de

alimento mediante dos puentes. Se realizaron dos pruebas de estudio (Fig.1), en la primera de

ellas se introdujeron dos puentes con la misma longitud (Fig.1.a) y en una segunda parte se

intercambió uno de los puentes por otro considerablemente más largo (Fig.1.b) (Dorigo, et al.,

2006).

Figura 5. Dorigo, et al. citado en Deneubourg, 1990, y Gross, 1989, 2006. Configuración

experimental para el experimento del doble puente. [Ilustración] reproducida en IEEE

Computational Intelligence Magazine. Bélgica: Université Libre de Bruxelles.


25

La primera prueba concluyó que las hormigas realizaban un muestreo aleatorio y a lo largo del

tiempo, las colonias se decantaban por escoger uno de los dos caminos de misma longitud.

En el segundo caso, inicialmente tampoco se observa distinción en las hormigas a la hora de

escoger el camino hacia el alimento. Sin embargo, las hormigas que escogen el puente más corto

por casualidad son las primeras en llegar al nido. De este modo, el puente más corto recibe más

cantidad de feromona, lo que aumenta la probabilidad de ser el camino escogido por las siguientes

hormigas.

La probabilidad de escoger un puente se calcula partiendo la siguiente fórmula (10):

𝑝1 =(𝑚1 + 𝑘)ℎ

(𝑚1 + 𝑘)ℎ + (𝑚2 + 𝑘)ℎ

(10)

Teniendo en cuenta que, el número subíndice representa la distinción entre los dos puentes, 𝑚 la

cantidad de hormigas que escogen uno de los puentes en un momento preciso, 𝑘 corresponde al

grado de atracción atribuido a un puente no marcado y ℎ es el grado de no-linealidad de la

elección. Ambos parámetros deben ajustarse a los datos experimentales (Deneubourg, et al.,

1989).

En base al experimento, se puede concluir lo siguiente:

- Las hormigas exploran el área que rodea su nido de manera aleatoria en busca de

alimento. En su paso, dejan un rastro de feromonas químicas que pueden oler el resto

de las hormigas.

- Cuando una hormiga encuentra alimento, evalúa la cantidad y calidad de la comida

y lleva parte de ella al nido. La cantidad de feromona que deposita la hormiga en su

paso puede depender de la cantidad y calidad de la comida.

- Las hormigas tienden a elegir los caminos marcados por fuertes concentraciones de

feromona, de tal forma que sirve de guía a otras hormigas hacia la fuente de alimento.

Grado de atracción: intensidad de feromona que permite que la elección de la hormiga no sea

aleatoria.

Grado de no-linealidad: grado de decisión o probabilidad de la hormiga de escoger el camino con

más intensidad de feromona.


26

4.2 INTRODUCCIÓN A LA OPTIMIZACIÓN DE COLONIA DE HORMIGAS

Los primeros algoritmos de optimización de colonia de hormigas (Ant Colony Optimization,

ACO, en inglés) fueron introducidos por Dorigo, et al. (1990) inspirados en el comportamiento

de búsqueda de alimento de las hormigas y la capacidad de encontrar caminos más cortos hasta

su fuente de alimento (Blum, 2005).

Los algoritmos ACO son principalmente algoritmos constructivos puesto que las hormigas

construyen una solución en cada iteración del algoritmo en un grafo de construcción. En cada

borde del grafo se encuentran dos tipos información que conducen a la hormiga a la elección del

siguiente borde, estas son:

- Información heurística, que mide la preferencia heurística desde el nodo r hasta el nodo

s, indicado como rs.

- Información de los rastros de feromona artificiales, que mide la deseabilidad aprendida

de ir del nodo r a el nodo s, representado como 𝜏𝑖𝑗.

Dichos algoritmos se caracterizan por crear las soluciones a problemas de optimización a partir

de hormigas artificiales que intercambian información sobre la calidad de solución mediante la

comunicación que adoptan las hormigas reales.

Las colonias de hormigas reales y artificiales comparten una serie de características:

- Ambas interactúan y colaboran para solucionar una tarea común: búsqueda del camino

más corto desde su origen (hormiguero) hasta un estado final (alimento).

- A su vez, las hormigas reales y artificiales modifican su entorno a través de la

comunicación estimérgica basada en la feromona y,

- Aplican una estrategia de transición local estocástica para moverse entre estados

adyacentes y minimizar el recorrido.

Definición 4. Transición local estocástica en ACO.

La transición local estocástica es una estrategia utilizada en los algoritmos ACO. Las

hormigas se desplazan de un nodo 𝑟 a un nodo 𝑠 aplicando una política local de decisión

estocastica en función del rastro de feromona (τrs) y la información estocastica(ηrs) situada

en el borde (r, s). Se denomina estocástico ya que su comportamiento intrínseco no es

determinista, es decir, la hormiga escoge el siguiente nodo en función de información

generada a través de acciones predecibles y aleatorias.

Definición 3. Hormigas artificiales.

Las hormigas artificiales son agentes computacionales simples que trabajan de manera

cooperativa y se comunican mediante rastros de feromonas artificiales. Intentan construir

soluciones posibles al problema explorando los rastros de feromona disponible y la

información heurística (Alonso, et al., 2003).


27

Sin embargo, las hormigas artificiales disponen de algunas características adicionales con la

finalidad de poder desarrollar algoritmos eficientes para problemas combinatorios difíciles. Estas

características son:

- Pueden hacer uso de información heurística (no solo de los rastros de feromona) en la

política estocástica de transición que apliquen.

- Tienen una memoria, 𝐿, que almacena el camino seguido por la hormiga.

- Normalmente sólo depositan feromonas después de generar una solución completa.

- Tienen la capacidad de olvidar lentamente su historia pasada mediante la evaporación de

feromona, esto les permite redireccionar su búsqueda hacia nuevas regiones del espacio

y de esta manera poder evitar que el algoritmo se quede estancado en óptimos locales.

Además, los algoritmos de colonia de hormigas pueden incorporar habilidades adicionales como,

por ejemplo, el mecanismo de anticipación (lookahead) (Michel y Middendorf, 1998), la

optimización local (Dorigo y Gambardella (1999), Stützle y Hoos (1997)), procesos de vuelta

atrás (backtracking) (Dorigo, et al. (1999)), o también es posible integrar la lista de candidatos

que contienen un conjunto de los estados vecinos más prometedores para mejorar la eficacia del

algoritmo.

4.2.1 Técnicas de optimización

Las técnicas de optimización que se muestran a continuación hacen referencia a, por un lado, el

problema de viajante de comercio, con que se inició la investigación de los algoritmos de

hormigas y que más adelante se aplicó a diversos estudios; y, por otro lado, la metaheurística de

optimización de colonia de hormigas, donde se muestra el algoritmo genérico ACO.

Problema del viajante de comercio

El problema del viajante de comercio (Traveling Salesman Problem, TSP, en inglés) parte de un

conjunto de 𝑛 ciudades que deben ser visitadas sin repetición y finalizando el viaje en el mismo

punto de partida (Masià, et al.).

La conexión entre las ciudades se puede contemplar en un grafo y el viaje representa un circuito

cerrado, también conocido como recorrido hamiltoniano.

Definición 5. Lookahead.

Lookahead: permite incorporar información sobre las decisiones anticipadas que están más

allá del horizonte de elección inmediata (Gagné, et al., 2001).

Definición 6. Backtracking.

Backtracking: realiza una búsqueda estructurada, descartando grandes bloques de soluciones

para reducir el espacio de búsqueda (Valero y Pita, 2012).


28

El viaje entre cada par de ciudades tiene un coste en función de la distancia del recorrido. El

problema trata de encontrar un recorrido hamiltoniano de duración mínima en un grafo

completamente conectado, es decir, encontrar el camino más corto que permita visitar todas las

ciudades una sola vez.

En ACO, el problema se plantea simulando una serie de hormigas artificiales que se mueven en

un grafo ponderado (𝑁, 𝐴) que codifica el problema. 𝑁 es el conjunto de ciudades y son

representadas como vértices del grafo; 𝐴 es el conjunto de bordes y figura la conexión entre

ciudades.

El algoritmo del TSP en ACO se caracteriza por los siguientes puntos:

- En cada borde se encuentra asociada una variable que indica el grado de feromona, la

cual es leída y puede ser modificada por las hormigas artificiales.

- Las soluciones son construidas por las hormigas artificiales a medida que el algoritmo

itera, de manera que ACO es un algoritmo iterativo. Estas soluciones representan el

recorrido completo de las hormigas, formado por los caminos de vértice a vértice o bordes

del grafo.

- La restricción que se emplea es la de no visitar ningún vértice que ya se haya visitado en

su camino.

- Las hormigas construyen la solución a medida que seleccionan los vértices para ser

visitados. La toma de su decisión se basa en un mecanismo estocástico en función de la

feromona.

- Al final de cada iteración, en función de la calidad de las soluciones construidas, se

modifican los valores de feromonas. Esto posibilita la construcción de soluciones

similares a las mejores construidas en siguientes iteraciones.

TSP y ATSP

Se pueden diferenciar dos tipologías de problemas TSP aplicados a algoritmos de optimización

colonia de hormigas, estos son: TSP simétrico y TSP asimétrico o ATSP (Asymmetric Traveling

Salesman Problem).

TSP se caracteriza por cumplir las siguientes condiciones.

Sea 𝑁 = {𝑎, … , 𝑧} el conjunto de ciudades, 𝐴 = {(𝑟, 𝑠): 𝑟, 𝑠 ∈ 𝑁} el conjunto de bordes y

𝛿(𝑟, 𝑠) = 𝛿(𝑠, 𝑟) la medida de coste asociada con el borde (𝑟, 𝑠) ∈ 𝐴. Las ciudades 𝑟 ∈ 𝑁 son

dadas por sus coordenadas (𝑥𝑟, 𝑦𝑟) y 𝛿(𝑟, 𝑠) es la distancia Euclidiana entre 𝑟 y 𝑠, dando lugar

así a un TSP Euclidiano.

Sin embargo, se considera ATSP cuando se cumple que 𝛿(𝑟, 𝑠) ≠ 𝛿(𝑠, 𝑟) en algunos bordes

(𝑟, 𝑠).


29

Además de utilizar la medida de coste asociada a los bordes (𝛿(𝑟, 𝑠)), en ACO se añade la medida

de deseabilidad representada como 𝜏(𝑟, 𝑠) , llamada feromona, donde en TSP se cumplirá

𝜏(𝑟, 𝑠) = 𝜏(𝑠, 𝑟) y en ATSP 𝜏(𝑟, 𝑠) ≠ 𝜏(𝑠, 𝑟) (Dorigo y Gambardella, 1997).

4.3 METAHEURÍSTICA DE OPTIMIZACIÓN DE COLONIA DE HORMIGAS

La metaheurística es un conjunto de conceptos algorítmicos que pueden utilizarse para definir

métodos heurísticos aplicables a diferentes problemas de optimización con relativamente pocas

modificaciones (Dorigo, et al., 2006).

La optimización de colonia de hormigas ha sido formalizada en una metaheurística para

problemas de optimización combinatoria.

El modelo de un problema de optimización combinatoria se utiliza para definir el modelo de

feromonas en ACO. Un problema de optimización combinatoria parte de un modelo P = (S, , f)

de un problema de optimización combinatoria se compone de:

- Un espacio de búsqueda S definido sobre un conjunto finito de variables de decisión

discretas Xi, i=1,.., n;

- Un conjunto de restricciones entre las variables; y

- Una función objetivo f: S → ℝ0+, a ser minimizada.

La variable genérica Xi toma valores en 𝐷𝑖 = {𝑣𝑖1, … , 𝑣𝑖

|𝐷𝑖| }. Una solución factible 𝑠 𝜖 𝑆 es una

asignación completa de valores de variables que satisface todas las restricciones en . Una

solución 𝑠∗ 𝜖 𝑆 se denomina óptimo global si y solo si: 𝑓(𝑠∗) ≤ 𝑓(𝑠)∀𝑠 𝜖 𝑆.

En ACO, el valor de feromonas 𝜏𝑖𝑗 está asociado con el componente de solución 𝑐𝑖𝑗, que consiste

en la asignación 𝑋𝑖 = 𝑣𝑖𝑗. De esta manera, cada componente de solución tiene asociado un valor

de feromona y el conjunto de todos los posibles componentes de solución se indican con C.

Las hormigas construyen la solución recorriendo un gráfico de construcción 𝐺𝐶 (𝑉, 𝐴), donde V

representa el conjunto de vértices y 𝐴 el conjunto de aristas. El conjunto de componentes 𝐶 se

puede representar mediante vértices o aristas.

Definición 7. Optimización combinatoria.

La optimización combinatoria (Cook, et al., 1997) es un campo dinámico de matemáticas

aplicadas que combina técnicas de programación lineal combinatoria y la teoría de

algoritmos para resolver problemas de optimización sobre estructuras discretas.


30

A medida que las hormigas construyen la solución circulando de vértice a vértice pueden

depositar una cantidad de feromona en los componentes. Esta cantidad puede variar en función

de la calidad de la solución y será determinante para la elección del camino de hormigas

posteriores.

4.3.1 Algoritmo de la metaheurística de optimización de colonia de hormigas

El procedimiento genérico y conceptos básicos que sigue el algoritmo ACO es el siguiente

(Alonso, et al., 2003):

- Las 𝑚 hormigas se mueven concurrentemente y de manera asíncrona a través de los

estados adyacentes del problema mediante una regla de transición basada en la

información local situada en cada nodo.

- La información local influye en la información heurística y memorística representadas

como el valor de los rastros de feromona.

- Una vez creadas las soluciones, se evalúa cada una y se añade una cantidad de feromona

en función de su calidad.

- Seguidamente, se realiza la evaporación de los rastros de feromona para evitar el

estancamiento de la búsqueda.

- Opcionalmente, es posible implementar tareas desde una perspectiva global mediante las

acciones del demonio.

La estructura genérica del algoritmo ACO es la siguiente:

Algoritmo 1. Optimización de colonia de hormigas.

Procedimiento Metaheurística_ACO()

Inicialización_de_parámetros

mientras (criterio_de_terminación_no_satisfecho)

Programación_de_actividades

Generación_de_hormigas_y_actividad()

Evaporación_de_Feromona()

Acciones_del_demonio()

fin Programación_de_actividades

fin mientras

fin Procedimiento


31

Inicialización de parámetros

En este primer paso se fijan los valores siguientes:

- El rastro inicial de feromona 𝜏0. Normalmente se utiliza el mismo valor para todas las

conexiones o componentes.

- El número 𝑚 de hormigas en la colonia.

- La proporción en la que afecta la información heurística y memorística en la regla de

transición probabilística.

Programación de actividades

Este paso permite controlar la planificación de las componentes:

Generación_de_hormigas_y_actividad(), Evaporación_de_Feromona() y

Acciones_del_demonio(). A su vez, se podrá determinar la sincronía entre cada una de las tres

componentes.

Algoritmo 2. Generación hormiga y actividad de algoritmo 1.

Procedimiento Generación_de_Hormigas_y_actividad

repetir en paralelo desde k=1 hasta m (número_hormigas)

Nueva_hormiga(k)

fin repetir en paralelo

fin Procedimiento

Algoritmo 3. Procedimiento Nueva_Hormiga(id_hormiga) de algoritmo 2.

inicializa_hormiga(id_Hormiga)

L = actualiza_memoria_hormiga()

mientras (estado_actual = estado_objetivo)

P = calcular_probabilidades_de_transición(A, L, Ω)

siguiente_estado = aplicar_política_decisión(P, Ω)

mover_al_siguiente_estado(siguiente_estado)

si (actualizacion_feromona_en_linea_paso_a_paso)

depositar_feromona_en_el_arco_vistado()

fin si

L = actualizar_estado_interno()

fin mientras


32

si (actualizacion_feromona_en_linea_a_posteriori)

para cada arco visitado

depositar_feromona_en_el_arco_visitado()

fin para

fin si

liberar_recursos_hormiga(id_Hormiga)

fin Procedimiento

En el Algoritmo 3 se encuentra el procedimiento actualiza_memoria_hormiga(), el cual tiene

como función:

- Especificar el estado inicial desde el inicio de la iteración.

- Registrar los bordes recorridos en la memoria de la hormiga L.

4.4 MODELOS DE OPTIMIZACIÓN BASADOS EN COLONIAS DE HORMIGAS

A continuación, se presentan los algoritmos más reconocidos de optimización de hormigas: las

tres extensiones del Sistema de hormigas, Sistema de hormigas con estrategia elitista, Sistema de

Hormigas MAX-MIN, Sistema de Colonia de Hormigas, Sistema de Hormiga Q, ANTS y Hyper-

Cube.

4.4.1 Sistema de Hormigas

El Sistema de Hormigas (Ant System, AS, en inglés) es el primer algoritmo ACO propuesto por

la literatura (Colorni, Dorigo, et al., 1991). Se caracteriza principalmente por actualizar en cada

iteración del valor de feromona por todas las 𝑚 hormigas que han construido una solución.

En el Sistema de Hormigas, cada hormiga genera un recorrido completo eligiendo las ciudades

en función de una regla de transición estatal probabilística1. La elección favorable corresponde

a los bordes cortos con gran cantidad de feromona. Al finalizar el recorrido, el algoritmo actualiza

los niveles de feromona en cada borde (llamada regla de actualización global de feromona),

donde evapora una cantidad de feromona de todos los bordes y añade otra cantidad de feromona

1 La regla de transición estatal probabilística y la regla de transición local estocástica tienen el mismo

significado. Ambas hacen referencia a la probabilidad de elección del siguiente nodo mediante la

información heurística y los rastros de feromona.


33

en los bordes correspondientes a los recorridos que obtienen un mejor resultado. La cantidad

depositada se aplica en proporción a la solución (Dorigo y Colorni, 1991).

Como se comentó anteriormente, el planteamiento inicial de los algoritmos de sistemas de

hormigas se presentó como solución al problema del viajante de comercio. En este caso, la

distancia entre ciudades 𝑑𝑖𝑗 se mide en distancia euclidiana entre 𝑖 y 𝑗 (11):

(𝑑𝑖𝑗 = √(𝑥𝑖 − 𝑥𝑗)2

+ (𝑦𝑖 − 𝑦𝑗)2

)

(11)

El número total de hormigas viene determinado por la siguiente fórmula (12), donde 𝑏𝑖(𝑡) (𝑖 =

1, … , 𝑛) es el número de hormigas en la ciudad 𝑖 en el tiempo 𝑡.

𝑚 = ∑ 𝑏𝑖(𝑡)

(12)

La intensidad de feromona asociada a cada borde situado desde el nodo 𝑖 hasta el nodo 𝑗 se

muestra como 𝑖𝑗 y su actualización es la siguiente (13):

𝜏𝑖𝑗(𝑡, 𝑡 + 1) = · 𝜏𝑖𝑗(𝑡) + ∆𝜏𝑖𝑗(𝑡, 𝑡 + 1)

(13)

La evaporación del rastro se mide como (1 - ), siendo la tasa de evaporación. El incremento

del valor de feromona en el borde (𝑖, 𝑗) se determina mediante la siguiente fórmula (14):

∆𝜏𝑖𝑗(𝑡, 𝑡 + 1) = ∑ ∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 1)

𝑚

𝑘=1

(14)

∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 1) es la cantidad de feromona depositada en el borde (𝑖, 𝑗) por la hormiga 𝑘.

Cada hormiga tiene asociada una estructura de datos almacenada en una lista tabú. La lista

memoriza las ciudades visitadas en un momento 𝑡, lo que permitirá que la hormiga visite todas

las ciudades sin repetir ninguna.2

2 La lista tabú no mantiene relación con los algoritmos de búsqueda tabú ya que los algoritmos de

hormigas son heurísticas constructivas y no de búsqueda local. La lista tabú no incorpora ninguna función

de aspiración y está formada por elementos registrados (nodos), no permutaciones.


34

El criterio de aspiración (Glover y Laguna, 1997) es un elemento esencial en los algoritmos de

búsqueda tabú. Este criterio se introduce en la Búsqueda Tabú para determinar cuándo pueden

ser remplazadas o eliminadas las restricciones tabúes sobre ciertos elementos dentro de la lista

tabú.

Una vez finalizado el recorrido de la hormiga, se vacía su lista tabú y la hormiga puede elegir

nuevamente su camino. En el algoritmo, la lista tabú se almacena en un vector definido como

tabuk, y tabuk (s) es conocido como el 𝑠 elemento de la lista tabú de la 𝑘 hormiga.

Probabilidad de transición de la ciudad i a la ciudad j para k hormiga (15).

𝑝𝑖𝑗𝑘 = {

[𝜏𝑖𝑗(𝑡)]𝛼

· [𝜂𝑖𝑗]𝛽

∑ [𝜏𝑖𝑗(𝑡)]𝛼

· [𝜂𝑖𝑗]𝛽

𝑗 ∈𝑝𝑒𝑟𝑚𝑖𝑡𝑖𝑑𝑜

𝑠𝑖 𝑗 ∈ permitido,

0 𝑝𝑎𝑟𝑎 𝑙𝑜 𝑑𝑒𝑚á𝑠,

(15)

Donde 𝑝𝑒𝑟𝑚𝑖𝑡𝑖𝑑𝑜 = {𝑗: 𝑗 𝑡𝑎𝑏𝑢𝑘} y y son parámetros que permiten controlar la

importancia relativa del camino frente a la visibilidad entre la ciudad 𝑖 y 𝑗, 𝑖𝑗

. La visibilidad (16)

es representada como la inversa de la distancia entre la ciudad 𝑖 y 𝑗.

𝜂𝑖𝑗 =1

𝑑𝑖𝑗

(16)

Así pues, en la fórmula expuesta (15), la probabilidad de transición, como se ha comentado

anteriormente para la transición local estocástica en ACO, se encuentra determinada por:

- La distancia entre la siguiente ciudad: las ciudades más cercanas tienen más posibilidad

de ser escogidas, implementando así una heurística constructiva codiciosa.

- La intensidad de la feromona: los caminos con más intensidad de feromona tienen más

posibilidad de ser escogidos. Indica que es el camino con más tráfico de hormigas y, por

lo tanto, es más deseable.

En el caso de establecer = 0, se obtiene un algoritmo codicioso estocástico con múltiples puntos

de partida. Si, además, se establece = ∞ se obtiene el clásico determinista, ya que su salida seria

predecible.

Por otro lado, en el algoritmo se incorpora un número máximo de ciclos definido por el usuario,

𝑁𝐶𝑀𝐴𝑋. El algoritmo repetirá las iteraciones y almacenará el valor óptimo encontrado en la lista

tabú en cada una de ellas hasta no superar el número máximo de ciclos o encontrarse en la

situación en la que todas las hormigas realizan el mismo recorrido. Este último caso se reconocerá

como uni-camino (uni-path en inglés), que denota una situación en la que el algoritmo deja de

buscar soluciones alternativas.


35

Inicialmente, se plantearon tres modelos de AS en función del cálculo de ∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 1) y el

momento en el que actualizar la intensidad de la feromona 𝜏𝑖𝑗(𝑡). Estos modelos son: Densidad

de hormigas (Ant-density), Cantidad de hormigas (Ant-quantity) y Ciclo de hormigas (Ant-cycle).

Todos ellos fueron diseñador originalmente para la solución del TSP. Actualmente se considera

AS el modelo de ciclo de hormigas.

Densidad de hormigas

En el modelo de densidad de hormigas, cuando una hormiga va de 𝑖 a 𝑗, deja 𝑄1 unidades de

feromona por cada unidad de longitud. De esta manera, el incremento de feromona del modelo

de densidad (17) se mide a partir de la fórmula siguiente:

∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 1) = {

𝑄1

0 𝑠𝑖 𝑘 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑣𝑎 𝑑𝑒 𝑖 𝑎 𝑗 𝑑𝑒𝑙 𝑡𝑖𝑒𝑚𝑝𝑜 𝑡 𝑎 𝑡 + 1

𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜

(17)

Por lo tanto, el aumento de intensidad de feromona en el borde (𝑖, 𝑗) cuando una hormiga va de

del punto 𝑖 al punto 𝑗 es independiente de la distancia entre los puntos 𝑑𝑖𝑗.

Cantidad de hormiga

En el modelo de cantidad del SH, la hormiga deposita una cantidad constante de feromona 𝑄2 que

deja la hormiga cuando pasa del punto 𝑖 a el punto 𝑗.

∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 1) = {

𝑄2

𝑑𝑖𝑗

0

𝑠𝑖 𝑙𝑎 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑘 𝑣𝑎 𝑑𝑒 𝑖 𝑎 𝑗 𝑑𝑒𝑙 𝑡𝑖𝑒𝑚𝑝𝑜 𝑡 𝑎 𝑡 + 1


(18)

En este caso, la intensidad de feromona depositada (18) es inversamente proporcional a la

distancia entre el borde (𝑖, 𝑗). En consecuencia, los bordes más cortos serán más deseables para

las hormigas, reforzando así el factor de visibilidad en la ecuación.

Ciclo de hormigas

En el sistema de ciclo de hormigas, el incremento de la intensidad de feromona de 𝑘 hormiga

entre dos puntos (19) no se calcula en cada paso, sino una vez terminado el recorrido. Su valor se

calcula de la siguiente forma:

∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 𝑛) = {

𝑄3

𝐿𝑘

0 𝑠𝑖 𝑘 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑢𝑡𝑖𝑙𝑖𝑧𝑎 𝑒𝑙 𝑏𝑜𝑟𝑑𝑒 (𝑖, 𝑗) 𝑒𝑛 𝑠𝑢 𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜


(19)


36

Donde 𝑄3 es una constante que indica la cantidad de feromona que deposita una hormiga por

recorrido, y 𝐿𝑘 es la longitud del recorrido de la 𝑘 hormiga. En este caso, los rastros se actualizan

al final del ciclo completo en lugar de después cada movimiento. De esta manera, se utiliza

información global sobre la duración del recorrido.

El valor de la feromona (20) se actualiza una vez recorridos los 𝑛 pasos.

𝜏𝑖𝑗( 𝑡 + 𝑛) = 1

· 𝜏𝑖𝑗(𝑡) + ∆𝜏𝑖𝑗(𝑡, 𝑡 + 𝑛)

(20)

Donde la cantidad depositada de feromona en el borde (𝑖, 𝑗) (21) es,

∆𝜏𝑖𝑗(𝑡, 𝑡 + 𝑛) = ∑ ∆𝜏𝑖𝑗𝑘 (𝑡, 𝑡 + 𝑛)

𝑚

𝑘=1

(21)

El valor de la tasa de evaporación 1 es diferente al utilizado en los anteriores sistemas Ant-

density y Ant-quantity, debido a que la ecuación se actualiza una vez recorridos los 𝑛 pasos.

4.4.2 Estrategia elitista

La primera mejora del AS fue la llamada estrategia elitista (elitist strategy en inglés) introducida

por Dorigo en el 1992. Consiste en añadir una cantidad adicional de feromona al mejor recorrido

del momento (𝑇𝑔𝑏, donde 𝑔𝑏 representa la mejor solución global) desde el inicio del algoritmo.

La cantidad añadida es depositada en los bordes cada vez que se actualizan los rastros de

feromona. Las hormigas que realizan el mejor recorrido son reconocidas como hormigas elitistas.

De esta manera, la intensidad extra de feromona recibida en los bordes del mejor recorrido (22)

se determinará a partir de la siguiente ecuación (Dorigo, et al., 1996):

∆𝜏𝑖𝑗𝑔𝑏(𝑡) = {𝑒/𝐿𝑔𝑏(𝑡)

0 𝑠𝑖 𝑒𝑙 𝑏𝑜𝑟𝑑𝑒 (𝑖, 𝑗)𝑝𝑒𝑟𝑡𝑒𝑛𝑒𝑐𝑒 𝑎 𝑇𝑔𝑏


(22)

Los bordes de 𝑇𝑔𝑏 se refuerzan con una cantidad dada por 𝑒/𝐿𝑔𝑏, donde 𝐿𝑔𝑏es la longitud de

𝑇𝑔𝑏 y 𝑒 es un número entero positivo también representado como 𝑄 · , siendo 𝑄 la constante

que muestra la cantidad de feromona que deposita una hormiga por recorrido y el número de

hormigas elitistas.


37

Actualización de feromona

Finalmente, la actualización de feromonas (23) se calcula de la siguiente manera:

𝜏𝑖𝑗 (𝑡 + 1) = 𝜌 · 𝜏𝑖𝑗 (𝑡) + ∆𝜏𝑖𝑗 + ∆𝜏𝑖𝑗𝑔𝑏

(23)

Donde el incremento de feromona del borde (𝑖, 𝑗) (24) es,

∆𝜏𝑖𝑗 = ∑ ∆𝜏𝑖𝑗𝑘

𝑚

𝑘=1

(24)

Y el travesado por la hormiga 𝑘 (25),

∆𝜏𝑖𝑗𝑘 = {

𝑄

𝐿𝑘

0

𝑠𝑖 𝑙𝑎 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑘 𝑢𝑡𝑖𝑙𝑖𝑧𝑎 𝑒𝑙 𝑏𝑜𝑟𝑑𝑒 (𝑖, 𝑗) 𝑒𝑛 𝑠𝑢 𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜

(25)

4.4.3 Sistema de hormigas basado en el rango

El sistema de hormigas basado en el rango (Rank-based Ant System, 𝐴𝑆𝑟𝑎𝑛𝑘 , en inglés) fue

aplicado por primera vez para solucionar problemas del TSP (Dorigo y Gambardella, 1997).

Aplicar AS con estrategia elitista tuvo dos consecuencias:

- Los aspectos de búsqueda local (explotación) toman más importancia que los aspectos de

búsqueda global (exploración).

- El efecto de enfatizar caminos cortos disminuye cuando la duración del recorrido se

acerca. Sucede especialmente cuando muchas hormigas viajan por caminos buenos pero

subóptimos.

Estos problemas también se encuentran en los algoritmos genéticos, en ellos son posibles de evitar

aplicando un esquema de selección basado en una clasificación, entre otros. Este concepto se

introdujo en AS con estrategia elitista para conseguir resolver estos problemas, creando así otra

tipología de algoritmo: 𝐴𝑆𝑟𝑎𝑛𝑘. Su aplicación ordena las hormigas por duración de recorrido una

vez haya sido generado (𝐿1 ≤ 𝐿2 ≤ ⋯ ≤ 𝐿𝑚), y pondera la actualización de feromona con el

índice de clasificación de la hormiga. Además, en 𝐴𝑆𝑟𝑎𝑛𝑘 solo se consideran las mejores

hormigas.

El mejor recorrido encontrado por el momento tendrá una aportación de feromona de hormigas

elitistas. Utilizando “uno” como valor mínimo de , para la − é𝑠𝑖𝑚𝑎 mejor hormiga su

aportación sería de ( − ) y se establece = − 1.


38

Actualización de feromona

La combinación de SH con estrategia elitista y de clasificación o ranking resulta la siguiente

actualización de feromona (26):

𝜏𝑖𝑗 (𝑡 + 1) = 𝜌 · 𝜏𝑖𝑗 (𝑡) + ∆𝜏𝑖𝑗 + ∆𝜏𝑖𝑗𝑔𝑏

(26)

Donde la intensidad de feromona depositada en el borde (i, j) es (27),

∆𝜏𝑖𝑗 = ∑ ∆𝜏𝑖𝑗𝜇

𝜎−1

𝜇=1

(27)

Y la deposición de feromona de la − é𝑠𝑖𝑚𝑎 mejor hormiga en el borde (i, j) es (28),

∆𝜏𝑖𝑗𝜇

= {(𝜎 − 𝜇) ·

𝑄

𝐿𝜇

0

𝑠𝑖 𝑙𝑎 𝜇 𝑚𝑒𝑗𝑜𝑟 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑣𝑖𝑎𝑗𝑎 𝑑𝑒𝑙 𝑏𝑜𝑟𝑑𝑒 (𝑖, 𝑗)𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜

(28)

Siendo 𝜇 el índice de clasificación, ∆𝜏𝑖𝑗𝜇

el incremento del nivel de feromona en el borde (i, j), 𝐿𝜇

el recorrido de la − é𝑠𝑖𝑚𝑎 mejor hormiga y el número de hormigas elitistas.

∆𝜏𝑖𝑗𝑔𝑏

(𝑡) pertenece a la estrategia elitista que mantiene la misma formulación que la anterior

mostrada (22).

4.4.4 Sistema de Hormigas Max-Min

El Sistema de Hormigas Max-Min (Max-Min Ant System, MMAS, en inglés) es un algoritmo

ACO que combina una exploración mejorada de las mejores soluciones encontradas durante la

búsqueda y un mecanismo que evita el estancamiento prematuro en el proceso (Stützle y Hoos,

1999).

𝑀𝑀𝐴𝑆 se diferencia del AS en tres aspectos esenciales:

- Las mejores soluciones encontradas en cada iteración (por la mejor hormiga de la

iteración) o durante la ejecución del algoritmo (por la mejor hormiga global) serán las

únicas en las que se añadirá feromona después de cada iteración.

- El rango de posibles rastros de feromona en cada componente de la situación viene

limitado en un intervalo [𝜏𝑚𝑖𝑛 , 𝜏𝑚𝑎𝑥], con el fin de evitar estancamientos locales de

búsqueda.

- Los rastros de feromona iniciales tienen como valor 𝜏𝑚𝑎𝑥 , para obtener una mayor

exploración de soluciones al inicio del algoritmo.


39

Actualización del rastro de feromona

Como se ha comentado anteriormente, el rastro de feromona solamente es actualizado por una

hormiga. La regla se define a partir de la formula siguiente (29):

𝜏𝑖𝑗 (𝑡 + 1) = 𝜌 · 𝜏𝑖𝑗(𝑡) + ∆𝜏𝑖𝑗𝑏𝑒𝑠𝑡

(29)

Donde ∆𝜏𝑖𝑗𝑏𝑒𝑠𝑡 es (30),

∆𝜏𝑖𝑗𝑏𝑒𝑠𝑡 = {

1

𝑓(𝑠𝑏𝑒𝑠𝑡)

0

𝑠𝑖 (𝑖, 𝑗) 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛 𝑎𝑙 𝑚𝑒𝑗𝑜𝑟 𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜,

𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜,

(30)

∆𝜏𝑖𝑗𝑏𝑒𝑠𝑡 y 𝑓(𝑠𝑏𝑒𝑠𝑡) representan el coste o longitud (en algunos casos expresado como 𝐿𝑏𝑒𝑠𝑡) de la

mejor solución. En caso de ser la mejor iteración es indicado como 𝑠𝑖𝑏 y en el caso de la mejor

solución global como 𝑠𝑔𝑏.

Utilizar únicamente 𝑠𝑔𝑏 puede centrar demasiado rápido en la solución obtenida en la búsqueda

y limitar la exploración de posibles mejoras. En ese caso, aumenta la probabilidad de que la

búsqueda quede atrapada en una solución de mala calidad. Esta probabilidad es reducida cuando

se utiliza 𝑠𝑖𝑏 debido al considerable cambio que pueden representar las mejores soluciones

obtenidas en cada iteración y a un mayor número de componentes de la solución que pueden

recibir feromona ocasionalmente.

Es posible utilizar estrategias mixtas, como por ejemplo incorporar 𝑠𝑖𝑏 en cada iteración y 𝑠𝑔𝑏

cada un número determinado de iteraciones.

Límites del rastro de feromonas

La probabilidad de la elección de las hormigas viene determinada por los rastros de feromona y

la información heurística. Esta última suele depender del problema y es estática durante la

ejecución del algoritmo. Por lo tanto, cuando se obtienen rastros de feromona extremos se

produce una situación de estancamiento.

Como medida para evitar esta situación, 𝑀𝑀𝐴𝑆 limita la influencia de los rastros de feromona

mediante 𝜏𝑚𝑖𝑛 y 𝜏𝑚𝑎𝑥 en los rastros de feromona mínimo y máximo.

De este modo que para todos los rastros de feromona 𝜏𝑖𝑗(𝑡), se cumple lo siguiente:

𝜏𝑚𝑖𝑛 ≤ 𝜏𝑖𝑗(𝑡) ≤ 𝜏𝑚𝑎𝑥


40

En el caso de superar al final de la iteración el máximo rastro de feromona establecido, este se

igualará al máximo, y del mismo modo sucederá con el mínimo. De este modo, la actualización

de feromona (31) podría mostrarse como:

𝜏𝑖𝑗 ← [(1 − 𝜌) · 𝜏𝑖𝑗 + ∆𝜏𝑖𝑗𝑏𝑒𝑠𝑡]

𝜏𝑚𝑎𝑥

𝜏𝑚𝑖𝑛

(31)

Donde 𝜏𝑚𝑎𝑥 y 𝜏𝑚𝑖𝑛 se definen en el operador [𝑥]𝑎𝑏

de la siguiente forma (32):

[𝑥]𝑎𝑏

= {𝑎𝑏𝑥

𝑠𝑖 𝑥 > 𝑎𝑠𝑖 𝑥 < 𝑏


(32)

El algoritmo 𝑀𝑀𝐴𝑆 converge cuando para cada punto de elección, uno de los componentes tiene

𝜏𝑚𝑎𝑥como rastro de feromona asociado y 𝜏𝑚𝑖𝑛 como rastro en el resto de los componentes de

solución alternativa.

El concepto de convergencia hace referencia al hallazgo de la mejor solución construida

compuesta por los elementos que contengan 𝜏𝑚𝑎𝑥.

Stützle y Hoos (1999) elaboraron una propuesta (33) para perfeccionar este concepto, acotando

𝜏𝑚𝑎𝑥 asintóticamente.

La propuesta indica que para cualquier 𝜏𝑖𝑗 se mantiene:

lim𝑡→∞

𝜏𝑖𝑗(𝑡) = 𝜏𝑖𝑗 ≤ 𝜏𝑚𝑎𝑥′ =

1

1 − 𝜌·

1

𝑓(𝑠𝑜𝑝𝑡)

(33)

Donde 1

𝑓(𝑠𝑜𝑝𝑡) es la cantidad máxima posible de feromona agregada y 𝑓(𝑠𝑜𝑝𝑡) es el valor de

solución óptima para un problema específico.

Por lo tanto, el rastro de feromonas descontadas hasta la iteración 𝑡 corresponde a (34):

𝜏𝑖𝑗𝑚𝑎𝑥(𝑡) = ∑ 𝜌𝑡−𝑖

𝑡

𝑖=1

·1

𝑓(𝑠𝑜𝑝𝑡)+ 𝜌𝑡 · 𝜏𝑖𝑗(0)

(34)

Es asintótica porque 𝜌 < 1, esta suma converge a:

1

1 − 𝜌·

1

𝑓(𝑠𝑜𝑝𝑡)


41

El valor de 𝜏𝑚𝑖𝑛 se determina eliminando la influencia de la información heurística y suponiendo

que las mejores soluciones pueden encontrarse cerca de la mejor solución del momento, poco

antes de que se produzca un estancamiento de búsqueda, tal y como sucede en problemas TSP.

El rastro mínimo de feromona 𝜏𝑚𝑖𝑛 se encuentra a partir de la siguiente fórmula (35), que se

encuentra al despejar 𝜏𝑚𝑖𝑛 de la fórmula (36).

𝜏𝑚𝑖𝑛 =𝜏𝑚𝑎𝑥 · (1 − √𝑃𝑏𝑒𝑠𝑡

𝑛

(𝑎𝑣𝑔 − 1) · √𝑃𝑏𝑒𝑠𝑡𝑛

(35)

𝑃𝑑𝑒𝑐 =𝜏𝑚𝑎𝑥

𝜏𝑚𝑎𝑥 + (𝑎𝑣𝑔 − 1) · 𝜏𝑚𝑖𝑛

(36)

Siendo 𝑃𝑑𝑒𝑐 constante en todos los puntos de decisión, 𝑛 el número de veces que una hormiga

toma la decisión correcta (37), 𝑃𝑏𝑒𝑠𝑡 la probabilidad con la que se encuentra la mejor solución

(38), y 𝑎𝑣𝑔 = 𝑛/2 el número de componentes de la solución que cada hormiga escoge en cada

punto de elección en promedio.

𝑃𝑑𝑒𝑐𝑛 = 𝑃𝑏𝑒𝑠𝑡; 𝑃𝑑𝑒𝑐 = √𝑃𝑏𝑒𝑠𝑡

𝑛

(37)

Iniciación del rastro de feromonas

Para incrementar la exploración de soluciones durante las primeras iteraciones del algoritmo,

𝑀𝑀𝐴𝑆 inicia con un valor de rastro de feromona 𝜏max (0) alto, lo que produce que al final de la

primera iteración todos los puntos de decisión tengan un valor de rastro de feromona 𝜏max (1).

En las siguientes iteraciones los rastros toman valores dentro de los límites establecidos.

Suavizado de los rastros de feromona

El Suavizado de los rastros de feromona (Pheromone Trail Smoothing, PTS, en inglés) es un

mecanismo adicional que facilita la exploración del espacio de búsqueda aumentando la

probabilidad de seleccionar componentes de solución con 𝜏ij bajo.

Este mecanismo puede ser útil para aumentar el rendimiento del algoritmo y puede aplicarse en

cualquier versión elitista de AS. En 𝑀𝑀𝐴𝑆 se utiliza cuando el algoritmo ha convergido o esta

muy cerca de ello, aumentando los rastros de feromona proporcionalmente a su diferencia con el

límite máximo de rastros de feromona, representado en la formula (38):

𝜏𝑖𝑗∗ (𝑡) = 𝜏𝑖𝑗(𝑡) + 𝛿 · (𝜏𝑚𝑎𝑥(𝑡) − 𝜏min(𝑡)) 𝑐𝑜𝑛 0 < 𝛿 < 1

(38)

Donde 𝜏𝑖𝑗(𝑡) y 𝜏𝑖𝑗∗ (𝑡) son el rastro de feromona antes y después del suavizado.

De esta forma, se consigue que 𝑀𝑀𝐴𝑆 sea menos sensible a la elección particular de 𝜏min.


42

4.4.5 Sistema de Colonia de Hormigas

El sistema de colonia de hormigas (Ant Colony System, ACS, en inglés) se diseñó en base a el

sistema de hormigas para mejorar la eficiencia de problemas del TSP simétricos y asimétricos.

ACS se caracteriza principalmente por el uso sinérgico de la cooperación entre hormigas

artificiales mediante feromona (memoria distribuida) depositada en los bordes del grafo.

ACS se diferencian del SH en los siguientes aspectos:

- La regla de transición de estado es una regla estocástica codiciosa que proporciona una

forma directa de equilibrio entre la exploración de nuevos bordes y explotación previa y

acumulada sobre el problema.

- La regla de actualización global se aplica solo a los bordes del mejor recorrido.

- Se aplica una regla de actualización de feromona local a medida que las hormigas

recorren los bordes.

Su funcionalidad inicia colocando las hormigas en las 𝑛 ciudades elegidas en función de la regla

de inicialización. Cada hormiga construye un recorrido aplicando la regla de transición de estado.

Mientras se construye el recorrido, la hormiga actualiza los rastros de feromona por los bordes

donde circula, aplicando así la regla de actualización local. Una vez finalizado el recorrido, se

actualiza la feromona mediante la regla de actualización global.

Regla de transición de estado

La regla de transmisión de estado favorece las transiciones a los nodos conectados por bordes

cortos y con una gran cantidad de feromonas.

Una hormiga posicionada en el nodo 𝑟 escoge dirigirse hacia la ciudad 𝑠 aplicando la regla dada

por:

𝑠 = {arg max{[𝜏(𝑟, 𝑢)] · [𝜂(𝑟, 𝑢)]𝛽}

𝑢∈𝐽𝑘(𝑟)

𝑆

𝑠𝑖 𝑞 ≤ 𝑞0 𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜

(39)

Donde 𝑞 es un numero aleatorio uniformemente distribuido en [0…1], 𝑞0 es un parámetro (0 𝑞0

1), 𝜏 es la feromona, 𝜂 es la inversa de la distancia entre los nodos, 𝐽𝑘(𝑟) es el conjunto de

ciudades pendientes de visitar por la hormiga 𝑘 situada en el nodo 𝑟, 𝛽 es el parámetro que

determina la importancia relativa de la feromona frente a la distancia (𝛽 > 0) y S es una variable

aleatoria seleccionada en función de la distribución de probabilidad siguiente:

𝑝𝑘(𝑟, 𝑠) = {

[𝜏(𝑟, 𝑠)] · [𝜂(𝑟, 𝑠)]𝛽

∑ [𝜏(𝑟, 𝑠)] · [𝜂(𝑟, 𝑢)]𝛽𝑢∈𝐽𝑘(𝑟)

0

𝑠𝑖 𝑠𝜖𝐽𝑘(𝑟)


(40)


43

Cuando una hormiga situada en la ciudad 𝑟 tiene que elegir la ciudad 𝑠, muestra un número

aleatorio 0 ≤ 𝑞 ≤ 1 . Si 𝑞 ≤ 𝑞0 se elige el mejor borde de acuerdo con (39) realizando una

exploración, en caso contrario se elige de acuerdo con (40) realizando una exploración parcial.

Regla de actualización global de ACS

La actualización global se realiza después de que todas las hormigas hayan completado sus

recorridos y únicamente deposita feromona la hormiga con recorrido mínimo hasta el momento,

esto es desde el inicio del algoritmo. El nivel de feromonas se actualiza mediante la regla de

actualización global (41):

𝜏(𝑟, 𝑠) ← (1 − 𝛼) · 𝜏(𝑟, 𝑠) + 𝛼 · ∆𝜏(𝑟, 𝑠)

(41)

Donde el incremento de feromona en los bordes (𝑟, 𝑠) (42) es,

∆𝜏(𝑟, 𝑠) = {(𝐿𝑔𝑏)−1

0

𝑠𝑖 (𝑟, 𝑠) ∈ 𝑚𝑒𝑗𝑜𝑟 𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜 𝑔𝑙𝑜𝑏𝑎𝑙𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜

(42)

0 < 𝛼 < 1 es la feromona, y 𝐿𝑔𝑏 la duración del mejor recorrido global hasta el momento.

También es posible utilizar en ACS la mejor iteración (iteration-best), que en lugar de la mejora

global (global-best) se utiliza la longitud 𝐿𝑖𝑏 que corresponde al mejor recorrido de la iteración

actual y únicamente se añade feromona a los bordes correspondientes al mejor recorrido de la

iteración actual. La regla de actualización de feromona en ACS demostró que la mejora global

obtenía unos resultados ligeramente mejores.

Regla de actualización local de ACS

La regla de actualización local se aplica para modificar el nivel de feromonas en los bordes a

medida que las hormigas van construyendo una solución. La regla comentada se encuentra

determinada por (43).

𝜏(𝑟, 𝑠) ← (1 − 𝜌) · 𝜏(𝑟, 𝑠) + 𝜌 · ∆𝜏(𝑟, 𝑠)

(43)

Donde 0 < 𝑟 < 1 es un parámetro.

Inicialmente se plantearon tres opciones para establecer ∆𝜏(𝑟, 𝑠):

- Utilizar la misma fórmula que en Q-lerning debido a la similitud con el problema de

aprendizaje por refuerzo. Como se ha comentado, la primera aplicación de ACS fue para

la resolución de problemas TSP y ATSP. De esta forma ∆𝜏(𝑟, 𝑠) vendría determinado por

(44).


44

Fórmula Q-lerning

∆𝜏(𝑟, 𝑠) = 𝛾 · maxz∈𝐽𝑘(𝑠)

𝜏(𝑠, 𝑧)

(44)

Donde 0 ≤ 𝛾 < 1 es un parámetro

- ∆𝜏(𝑟, 𝑠) = 𝜏0

- ∆𝜏(𝑟, 𝑠) = 0

Los algoritmos con mejor rendimiento aplicaban una de las dos primeras opciones comentadas,

la primera de ellas se denominó Ant-Q y ∆𝜏(𝑟, 𝑠) = 𝜏0 fue la seleccionada por representar menos

cálculo respecto a Ant-Q.

4.4.6 Hormiga Q

Hormiga Q (Ant-Q en inglés) se creó bajo la idea de interpretar AS como un tipo particular de

aprendizaje por refuerzo (Reinforcement Learning, RL) distribuido. Su primera aplicación fue

para la resolución de problemas TSP y ATSP (Gambardella y Dorigo, 1995).

Regla de transición de estado

Ant-Q incorpora 𝐴𝑄(𝑟, 𝑠) que representa el valor real positivo Ant-Q asociado al borde (𝑟, 𝑠) y

𝐻𝐸(𝑟, 𝑢) como el valor de la heurística asociada al borde (𝑟, 𝑠).

Una hormiga 𝑘 situada en la ciudad 𝑟 se mueve a la ciudad 𝑠 utilizando la regla (45):

𝑠 = {arg max

𝑢∈𝐽𝑘(𝑟){[𝐴𝑄(𝑟, 𝑢)]𝛿 · [𝐻𝐸(𝑟, 𝑢)]𝛽}

𝑆

𝑠𝑖 𝑞 ≤ 𝑞0


(45)

Donde y son parámetros que pesan la importancia relativa de los valores AQ aprendidos y los

valores heurísticos, 𝑞 es un valor elegido al azar con probabilidad uniforme en [0,1], q0 (0 ≤

𝑞0 ≤ 1) es un parámetro que regula la probabilidad del uso aleatorio y 𝑆 es una variable aleatoria

seleccionada acorde a una distribución de probabilidad dada por la función de 𝐴𝑄(𝑟, 𝑢) y

𝐻𝐸(𝑟, 𝑢), con 𝑢𝜖𝐽𝑘 (𝑟), siendo 𝐽𝑘 (𝑟) la lista de ciudades aún por visitar.

Regla de actualización de valores AQ

La regla de actualización (46) es idéntica a la fórmula utilizada en Q-learning a excepción del

conjunto 𝐽𝑘 (𝑟), siendo este una función del historial anterior de la k hormiga.

𝐴𝑄(𝑟, 𝑠) ← (1 − 𝛼) · 𝐴𝑄(𝑟, 𝑠) + 𝛼 · (∆𝐴𝑄(𝑟, 𝑠) + 𝛾 · 𝑀𝑎𝑥𝑧∈𝐽𝑘(𝑠) 𝐴𝑄(𝑠, 𝑧))

(46)


45

Regla de elección de acciones

La regla de elección de acciones indica la probabilidad con la que una hormiga 𝑘 situada en la

ciudad 𝑟 elige la siguiente ciudad 𝑠.

Inicialmente se plantearon tres reglas posibles: regla pseudoaleatoria, proporcional

pseudoaleatoria y proporcional aleatoria. Para Ant-Q, la regla que obtenía mejores resultados fue

la regla proporcional pseudoaleatoria la cual viene dada por (47):

𝑝𝑘(𝑟, 𝑠) = {

[𝐴𝑄(𝑟, 𝑠)]𝛿 · [𝐻𝐸(𝑟, 𝑠)]𝛽

∑ [𝐴𝑄(𝑟, 𝑢)]𝛿 · [𝐻𝐸(𝑟, 𝑢)]𝛽𝑢∈𝐽𝑘(𝑟)

0

𝑠𝑖 𝑠 ∈ 𝐽𝑘(𝑟)


(47)

Refuerzo retardado

En Ant-Q pueden aplicarse dos tipos de refuerzo retardado: utilizando la mejor solución global y

la mejor solución de la iteración. Los dos tipos obtienen buenos resultados en Ant-Q, sin embargo,

en la creación del algoritmo se escogió el uso del refuerzo retardado de mejor iteración por ser

menos sensibles a los cambios de valor del parámetro y encontrar la solución más rápido que

aplicando el tipo de mejor solución global. La elección del tipo de refuerzo retardado se tomó

para solucionar problemas de TSP y ATSP, lo cual puede diferir en otros casos o tipos de

problemas o sufrir modificaciones en futuras investigaciones. El refuerzo retardado de mejor

iteración viene dado por la fórmula (48):

∆𝐴𝑄(𝑟, 𝑠) = {

𝑊

𝐿𝑘𝑖𝑏

0

𝑠𝑖 (𝑟, 𝑠) ∈ 𝑏𝑜𝑟𝑑𝑒𝑠 𝑣𝑖𝑠𝑖𝑡𝑎𝑑𝑜𝑠 𝑝𝑜𝑟 𝑙𝑎 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑘𝑖𝑏


(48)

Donde 𝑘𝑖𝑏 es la hormiga que obtuvo la mejor solución en la iteración actual, 𝐿𝑘𝑖𝑏 es la longitud

de su recorrido y W es un parámetro.

4.4.7 Sistema ant

El Sistema Ant (ANTS) (Maniezzo, 1999) es un sistema mejorado del AS original. Inicialmente

se diseñó con la finalidad de ser implantado para la resolución de problemas de asignación

cuadrática (QAP). Sin embargo, a continuación, se presenta la metaheurística ANTS aplicable a

problemas de optimización combinatoria.

Las mejoras ANTS que se incorporan en el algoritmo son el uso de límites y la eficiencia

computacional mejorada. También se elimina el parámetro para evitar el estancamiento.


46

Uso de límites

El algoritmo utiliza límites inferiores en el caso de problemas minimización y límites superiores

en caso de problemas de maximización para estimar el atractivo de un movimiento. Tomando por

ejemplo un problema de minimización, para cada movimiento factible (i,j), se determina el límite

inferior del coste de una solución completa que contenga j, cuanto menor sea su límite, mejor será

el movimiento.

El uso de esta mejora tiene varias ventajas, como por ejemplo el tener la posibilidad de descartar

movimientos que conducen a soluciones parciales que no mejoran la solución actual. Esto sucede

cuando el límite se vuelve mayor que el límite superior actual. Otra ventaja es la de poder reducir

movimientos posibles cuando el límite se deriva de la programación lineal, mediante el cálculo

de costes y la eliminación de variables, reduciendo así el espacio de búsqueda.

Además, en los límites inferiores basados en la programación lineal, es posible eliminar el

parámetro 𝜏𝑖𝑗(0) que define el usuario utilizando una estimación de la probabilidad mediante los

valores primarios de las variables de decisión.

Eficiencia computacional mejorada

En lugar de calcular la probabilidad de una hormiga k de ir del nodo 𝑖 al nodo 𝑗 mediante la

fórmula anterior en el AS (15) es posible utilizar componentes más eficientes

computacionalmente y eliminar el parámetro 𝛽 convirtiendo la fórmula (15) en la siguiente (49):

𝑝𝑖𝑗𝑘 = {

𝛼 · [𝜏𝑖𝑗(𝑡)] · (1 − 𝛼) · [𝜂𝑖𝑗]

∑ 𝛼 · [𝜏𝑖𝑗(𝑡)] · (1 − 𝜂) · [𝜂𝑖𝑗]𝑗 ∈𝑝𝑒𝑟𝑚𝑖𝑡𝑖𝑑𝑜

𝑠𝑖 𝑗 ∈ permitido,

0 𝑝𝑎𝑟𝑎 𝑙𝑜 𝑑𝑒𝑚á𝑠,

(49)

Se recuerda que, 𝑝𝑒𝑟𝑚𝑖𝑡𝑖𝑑𝑜 = {𝑗: 𝑗 𝑡𝑎𝑏𝑢𝑘}, y son parámetros que permiten controlar la

importancia relativa del camino frente a la visibilidad entre la ciudad 𝑖 y 𝑗, 𝑖𝑗

(esta última es

representada como la inversa de la distancia entre la ciudad 𝑖 y 𝑗 ), y 𝜏𝑖𝑗(𝑡) es el rastro de

feromona en el borde de 𝑖 a 𝑗 en el tiempo 𝑡.

Definición 8. Problema de asignación cuadrática.

El problema de asignación cuadrática (Quadratic Assigment Problem, QAP, en inglés) fue

introducido por Koopmans y Beckmann en 1957 como un modelo matemático para la

ubicación de un conjunto de actividades económicas indivisibles. El problema representa

asignar un conjunto de servicios a un conjunto de ubicaciones, siendo el coste una función

de la distancia y el flujo entre los servicios, más los costes asociados con un servicio a una

ubicación, de manera que el coste total se minimice (Burkard, Çela et al., 1998).


47

Evitar estancamiento

Para evitar el estancamiento se decide actualizar el rastro mediante la evaluación de las soluciones

y el cálculo y comparación de su media. Cuando se dispone de las últimas soluciones construidas

globalmente por el algoritmo, se calcula su media móvil, z, y se compara con cada nueva solución,

z_curr. La fórmula (13) que determina la actualización de la feromona en los bordes se representa

en este caso de la forma siguiente (50):

Δ𝜏𝑖𝑗 = 𝜏0 · (1 −𝑧𝑐𝑢𝑟𝑟 − 𝐿𝐵

𝑧 − 𝐿𝐵)

(50)

Donde 𝑧 es el valor promedio de las últimas soluciones y LB es un límite inferior del coste óptimo

de la solución del problema.

4.4.8 Hyper Cube

El marco de hipercubo para la optimización de colonias de hormigas (Blum y Dorigo, 2004)

permite aumentar la calidad promedio de las soluciones en función del tiempo para problemas no

restringidos. Este tipo de problemas se refieren a aquellos en los que en una solución una variable

de decisión puede tomar cualquier valor de su dominio, independientemente de los valores de las

otras variables de decisión.

El marco de hipercubo limita los valores de feromona al intervalo [0,1] mediante modificaciones

en la regla de actualización del valor de feromonas (51), la cual se representa como:

𝜏𝑖𝑗 ← (1 − 𝜌) · 𝜏𝑖𝑗 + 𝜌 · ∑𝐹(𝑠)

∑ 𝐹(𝑠′){𝑠′∈𝑆𝑢𝑝𝑑}{𝑠∈𝑆𝑢𝑝𝑑|𝑐𝑖𝑗∈𝑠}

(51)

Donde, 𝜏𝑖𝑗 es el valor del rastro de feromona en el borde (i,j), 𝜌 ∈ (0,1] es el ratio de evaporación,

𝑆 es el conjunto soluciones candidatas, 𝑠 es le solución tal que 𝑠 ∈ 𝑆, 𝑐𝑖𝑗 es el componente de

solución, 𝑆𝑢𝑝𝑑 es el conjunto de soluciones generadas en la iteración actual y 𝐹: 𝑆 → ℝ+ de tal

manera que 𝑓(𝑠) < 𝑓(𝑠′) ⇒ 𝐹(𝑠) ≥ 𝐹(𝑠′), ∀𝑠, 𝑠′ ∈ 𝑆, 𝑠 ≠ 𝑠′.

4.5 APLICACIÓN DE ALGORITMOS DE COLONIAS DE HORMIGAS

4.5.1 ACO para equilibrados de líneas de montaje

Bautista y Pereira (2002) presentaron un trabajo basado en la resolución de problemas de

equilibrados de líneas de montaje mediante una metaheurística ACO cuyo objetivo es minimizar

el número de estaciones dada una tasa de trabajo o tiempo de ciclo fijo (SALBP-1).


48

El algoritmo se encuentra enfocado a la heurística del sistema de hormigas. Cada iteración

representa una subcolonia formada por veintiséis hormigas con trece reglas de prioridad, es decir,

dos hormigas por cada regla. Las hormigas escogen las tareas utilizando una regla probabilística

basada en la regla de prioridad asignada y la información del rastro depositada por las hormigas

anteriores. Algunas hormigas resuelven la instancia de forma directa y otras de forma inversa.

La nomenclatura utilizada y las trece reglas de prioridad son las siguientes (Bautista, et al., 2000):

Nomenclatura

i, j Índice de tarea

N Número de tareas

C Tiempo de ciclo

Ti Duración de la tarea i

ISi Conjunto de tareas siguientes inmediatas a la tarea i

Si Conjunto de tareas siguientes a la tarea i

TPi Conjunto de tareas precedentes a la tarea i

Li Nivel de la tarea i en el grafo de precedencias

Reglas de prioridad

Nombre Peso

1. Mayor Tiempo de Procesamiento v(i)= ti

2. Mayor número de Sucesores Inmediatos v(i)= |ISi|

3. Mayor número de Sucesores v(i)= |Si|

4. Mayor Peso Posicional Clasificado v v(i)= ti ± Σtj (j∈Si)

5. Mayor Peso Posicional Promedio Clasificado v(i)= (ti ± Σ tj (j∈Si))/(|Si|+1)

6. Límite Superior más Pequeño v(i)= -UBi = -n - 1 + [(ti ± Σ tj

(j∈Si))/C]+

7. Límite Superior más Pequeño / Número de

Sucesores

v(i)= -UBi/(|Si|+1)

8. Mayor Tiempo de Procesamiento/ Límite Superior v(i)= ti/ UBi

9. Límite Inferior más Pequeño v(i)= -LBi = -[(ti ± Σ tj (j∈TPi))/C]+

10. Holgura Mínima v(i)= -(UBi - LBi)

11. Número Máximo de Sucesores / Holgura v(i)= |Si|/(UBi - LBi)

12. Bhattcharjee y Sahu v(i)= ti ± |Si|

13. Etiquetas Kilbridge & Webster v(i)= t - Li

El algoritmo se prueba con dos técnicas de lectura de información y tres políticas de uso de

información de ruta directa e indirecta. También se incorporó un procedimiento de búsqueda

local.

Utilizando búsqueda local, se obtuvieron mejores resultados aplicando la lectura de información

de ruta directa (evaluación directa) y la política en la cual la información del camino se deja entre

tarea y su estación asignada.


49

Sin embargo, los mejores resultados para una lectura de información de seguimiento directa se

construyeron utilizando la política de gestión de información de seguimiento de tarea a tarea

correlativa, que tiene en cuenta la información de seguimiento entre las tareas ya asignadas y la

nueva tarea asignada.

El algoritmo fue aplicado a un caso real, en una industria de montaje de bicicletas de Barcelona.

El problema consistía en asignar ciento tres tareas con un tiempo de ciclo de trescientos veintisiete

segundos, una bicicleta producida cada cinco minutos y medio, tratando de minimizar el número

de puestos de trabajo necesarios con el tiempo de ciclo dado. Para ello, el modelo de algoritmo

se adaptó a la situación del caso, con las características adicionales correspondientes.

4.5.2 ACO para problemas de disposición de máquina

Corry y Kozan (2010) adaptaron un algoritmo de optimización de colonia de hormigas para

solucionar el problema de disposición de máquina, remplazando así la mejor técnica utilizada por

el momento para la solución del problema.

El problema tiene como objetivo minimizar la manipulación de materiales requerida para la

fabricación de un producto disponiendo las máquinas de forma adecuada. El problema se

denomina problema de disposición de la máquina (Machine Layout Problem, MLP, en inglés).

Corry y Kozan (2003) propusieron un algoritmo de optimización de colonia de hormigas (ACO)

para el problema de distribución de máquina (MLP-ACO). En 2010, fue escogido para un caso

real debido a su flexibilidad y capacidad demostrada para encontrar soluciones de buena calidad.

Modelo JSL-ACO

Para hacer frente a las características adicionales del modelo MLP-ACO, Corry y Koznan lo

modificaron creando así el diseño de taller de trabajo (Job Shop Layout, JSL, en inglés) –

optimización de colonia de hormigas (JSL-ACO).

El modelo que se aplicó al caso representaba las máquinas como objetos rectangulares situadas

en una cuadrícula rectangular. El modelo se conforma en base a las siguientes suposiciones,

además de las restricciones aplicadas para cada problema:

- Todas las máquinas son de geometría rectangular fija.

- Todas las máquinas deben estar contenidas dentro de un área rectangular fija llamada

piso.

- Cada máquina puede asumir una de cuatro orientaciones (0, 90, 180 y 270) de manera

que los límites de la máquina sean paralelos a los límites del suelo.

- Las dimensiones del piso, las dimensiones de la máquina y las coordenadas de los vértices

de la máquina deben medirse en unidades integrales.

Ambos modelos comparten las decisiones para la construcción de diseños: el orden en el que se

colocan las máquinas y la ubicación de cada máquina. Hay un tipo de nodo para cada decisión.


50

La ubicación de la máquina se define cuando la hormiga selecciona un conjunto de nodos de la

región de la cuadrícula que representarán el área que ocupará la máquina.

A continuación, se muestran los parámetros de entrada, variables de decisión, otras variables

utilizadas y la función objetivo (52).

Parámetros de entrada

𝑛 número de máquinas en diseño

𝑊 ancho de la planta (x - dirección)

𝐻 altura de la planta (dirección y)

𝑤𝑖 ancho de la máquina i (dirección x)

𝑣𝑖 altura de la máquina i (dirección y)

(𝑎𝑖 , 𝑏𝑖) posición del punto de carga con respecto al origen de la máquina cuando

𝑧𝑖0 = 1

𝑠𝑖 = 1 si la máquina i requiere la eliminación de residuos, 0 en caso contrario

(𝑎𝑖𝑆, 𝑏𝑖

𝑆) posición de la papelera de la máquina en relación con el origen de la máquina

cuando 𝑧𝑖0 = 1

𝐹𝑖𝑗 cantidad de flujo de material entre las máquinas i y j

𝑆(𝑥𝑖𝑆, 𝑦𝑖

𝑆) función de penalización de eliminación de residuos para la máquina i

𝑀 número arbitrariamente grande

∧ = {(𝑖, 𝑗)|𝑖 = 1, … , 𝑛 ∧ 𝑗 = 𝑖 + 1, … , 𝑛 ∧ 𝑖 ≠ 𝑗}

Variables de decisión

𝑧𝑖0 = 1 si la máquina i está orientada a 0 ° (lado más corto en la parte inferior), 0

en caso contrario

𝑧𝑖90 = 1 si la máquina i está orientada a 90 ° (lado más largo en la parte inferior),

0 en caso contrario

𝑧𝑖180 = 1 si la máquina i está orientada a 180 ° (lado más corto en la parte inferior),

0 en caso contrario

𝑧𝑖270 = 1 si la máquina i está orientada a 270 ° (lado más largo en la parte inferior),

0 en caso contrario

(𝑥𝑖0, 𝑦𝑖

0) origen de la máquina i (vértice más cercano al origen del piso (0,0))

Otras variables

(𝑥𝑖, 𝑦𝑖) coordenadas del punto de carga de la pieza de la máquina i

(𝑥𝑖𝑆, 𝑦𝑖

𝑆) coordenadas de la papelera de la máquina i

𝛿𝑖𝑗𝑙𝑓𝑡(𝑟ℎ𝑡)

= 1 si la máquina i está a la izquierda (derecha) de la máquina j, 0 en caso

contrario

𝛿𝑖𝑗𝑏𝑙𝑤(𝑎𝑏𝑣)

= 1 si la máquina i está debajo (arriba) de la máquina j, 0 en caso contrario


51

Modelo/Función objetivo

𝑚𝑖𝑛 ∑ 𝐹𝑖𝑗[|𝑥𝑖 − 𝑥𝑗| + |𝑦𝑖 − 𝑦𝑗|] + ∑ 𝑠𝑖𝑆(𝑥𝑖𝑆, 𝑦𝑖

𝑆)

𝑛

𝑖=1(𝑖,𝑗)∈∧

(52)

Reglas de elección de acciones

En MLP-ACO hay dos reglas de elección de acciones debido a las dos decisiones a tomar. A su

vez, se utilizan dos funciones heurísticas, 𝐻𝑜𝑟𝑑(·) y 𝐻𝑝𝑜𝑠(·) para el orden y posición de la

máquina, respectivamente.

Las hormigas deciden el orden en el que colocan las máquinas a partir de la ecuación (53)

expresada a continuación, la cual hace referencia a una hormiga 𝑞 situada en el nodo 𝑖 después

que la máquina 𝑖 haya sido asignada a una posición, a punto de decidir qué nodo de máquina 𝑗

visitar a continuación.

𝑗 = {arg max

m∈Freiq{[𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑚)]𝛿[𝐻𝑜𝑟𝑑(𝑖, 𝑚)]𝛽}

𝐽

𝑠𝑖 𝑅 ≤ 𝑅0𝑜𝑟𝑑


(53)

Donde 𝐹𝑟𝑒𝑖𝑞 es el conjunto de nodos de máquina que aún no ha visitado la hormiga 𝑞, R es una

variable aleatoria distribuida uniformemente sobre [0,1], 𝛽 es un parámetro que determina las

funciones heurísticas, 𝛿 es un parámetro que define la importancia relativa de las feromonas,

𝑅0𝑜𝑟𝑑 es un parámetro que controla el grado de exploración de las hormigas y 𝐽 es un nodo de la

máquina de 𝐹𝑟𝑒𝑖𝑞

de seleccionado de acuerdo con la probabilidad (54):

𝑝𝑞(𝑖, 𝐽) = {

[𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗)]𝛿[𝐻𝑜𝑟𝑑(𝑖, 𝑗)]𝛽

∑ [𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑚)]𝛿[𝐻𝑜𝑟𝑑(𝑖, 𝑚)]𝛽𝑚∈𝐹𝑟𝑒𝑖

𝑞

0

𝑠𝑖 𝑗 ∈ 𝐹𝑟𝑒𝑖𝑖𝑞


(54)

Por otro lado, en JSL-ACO se consideran cuatro posibles orientaciones de máquina, mientras que

en MCL-ACO hay dos. Para abordar los problemas que se originaban, en JSL-ACO se identifican

dos posibles orientaciones en la misma área, por ejemplo 0° y 180° o 90° y 270°.

Para determinar la ubicación de la máquina i por la hormiga q se utiliza la regla de elección de

acción expresada por la siguiente ecuación (55).

𝐿𝑐𝑛𝑖 = {arg max

Lcni′∈𝐴𝑖

𝑞{[𝑟𝑎𝑠𝑡𝑟𝑜𝑎𝑣𝑔(𝑖, 𝐿𝑐𝑛𝑖

′)]𝛿

[𝐻𝑝𝑜𝑠(𝑖, 𝐿𝑐𝑛𝑖′)]

𝛽}

𝐿𝐶𝑁𝑖

𝑠𝑖 𝑅 ≤ 𝑅0𝑝𝑜𝑠


(55)

Donde 𝑟𝑎𝑠𝑡𝑟𝑜𝑎𝑣𝑔(𝑖, 𝐿𝑐𝑛𝑖) (56) y 𝐿𝐶𝑁𝑖 es una posición tal que 𝑀(𝐿𝐶𝑁𝑖) ⊆ 𝑉𝑐𝑡𝑖𝑞

seleccionado

por una probabilidad 𝑝𝑝 (57).


52

𝑟𝑎𝑠𝑡𝑟𝑜𝑎𝑣𝑔(𝑖, 𝐿𝑐𝑛𝑖) =1

𝑣𝑖𝑤𝑖 ∑ 𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, [𝑥, 𝑦])

[𝑥,𝑦]∈𝑀(𝐿𝑐𝑛𝑖)

(56)

𝑝𝑝(𝑖, 𝐿𝐶𝑁𝑖) = {

[𝑟𝑎𝑠𝑡𝑟𝑜𝑎𝑣𝑔(𝑖, 𝐿𝐶𝑁𝑖)]𝛿

[𝐻𝑝𝑜𝑠(𝑖, 𝐿𝐶𝑁𝑖)]𝛽

∑ [𝑟𝑎𝑠𝑡𝑟𝑜𝑎𝑣𝑔(𝑖, 𝐿𝑐𝑛𝑖′)]

𝛿[𝐻𝑝𝑜𝑠(𝑖, 𝐿𝑐𝑛𝑖

′)]𝛽

𝐿𝑐𝑛𝑖′∈𝐴𝑖

𝑞

0

𝑠𝑖 𝐿𝐶𝑁𝑖 ∪ 𝐴𝑖

𝑞


(57)

𝐿𝑐𝑛𝑖 = (𝑥𝑖 , 𝑧𝑖) es una posible posición para la máquina i definida por su origen y orientación, 𝐴𝑖𝑞

es el conjunto de posiciones consideradas por una hormiga, 𝑀(𝐿𝑐𝑛𝑖) es el conjunto de regiones

de la cuadricula ocupadas por la máquina i en la posición 𝐿𝑐𝑛𝑖 , 𝑉𝑐𝑡𝑖𝑞

indica el conjunto de

regiones de la cuadricula vacías en el diseño parcial de la hormiga 𝑞 y la expresión (𝑖, [𝑥, 𝑦])

representa la feromona acumulada entre el nodo de la máquina 𝑖 y el nodo de la región de

cuadrícula [𝑥, 𝑦].

Reglas de actualización de feromona

Las reglas de actualización de feromona en MLP-ACO no se actualizaron en JSL-ACO. Estas son

una combinación el sistema de hormigas con estrategia elitista y el sistema de hormigas máximo-

mínimo.

El nivel de feromona inicia con un valor máximo, 𝜏𝑚𝑎𝑥, que representará un límite de rastro que

no puede superarse durante la ejecución del algoritmo. Se realiza la evaporación de feromonas en

cada borde (i, j) una vez las hormigas hayan construido la solución. Todos los bordes presentes

en la trayectoria de las hormigas adquieren una cantidad añadida de feromona. A su vez, se utiliza

la estrategia elitista donde se añade una cantidad adicional a la solución más conocida de todas

las iteraciones anteriores.

El depósito de feromonas para cada borde se calcula a través de la ecuación (58).

∆𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗) = ∑𝑈

𝐶𝑝+ 𝑒𝑖𝑗

𝑖𝑛

𝑞∈𝐾

𝑈

𝐶𝑏𝑒𝑠𝑡

(58)

Donde,

𝐾 = {𝑞|(𝑖, 𝑗) 𝑒𝑠𝑡𝑎 𝑒𝑛 𝑒𝑙 𝑐𝑎𝑚𝑖𝑛𝑜 𝑑𝑒 𝑙𝑎 ℎ𝑜𝑟𝑚𝑖𝑔𝑎 𝑞 𝑒𝑛 𝐺(𝑉, 𝐸), 𝑞 = 1, … , 𝑁𝑎𝑛𝑡}

𝑒𝑖𝑗𝑖𝑛 = {

𝑒0

(𝑖, 𝑗) 𝑝𝑎𝑟𝑡𝑒 𝑑𝑒 𝑙𝑎 𝑟𝑢𝑡𝑎 𝑒𝑛 𝑙𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑚á𝑠 𝑐𝑜𝑛𝑜𝑐𝑖𝑑𝑎



53

𝐶𝑝es el coste objetivo de la ruta de diseño de la 𝑞 hormiga, 𝐶𝑏𝑒𝑠𝑡 es el coste objetivo del mejor

diseño encontrado hasta el momento, 𝑈 es un parámetro que controla la intensidad de los

depósitos de feromonas y 𝑒 es el número de hormigas elitistas.

La ecuación (59) aplica la evaporación de feromonas mediante el parámetro 𝛼 y el depósito de

feromonas calculado en la fórmula anterior (58).

𝑟𝑎𝑠𝑡𝑟𝑜′(𝑖, 𝑗) = min(𝜏𝑚𝑎𝑥, (1 − 𝛼)𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗) + 𝛼∆𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗)), (𝑖, 𝑗) ∈ 𝐴

(59)

El algoritmo es el siguiente:

Algoritmo 5. JSL-ACO

Inicialización

𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗) = 𝜏𝑚𝑎𝑥 , ∀(𝑖, 𝑗) ∈ 𝐸

repetir

Generar soluciones

Iniciar cada hormiga en una máquina diferente (si es posible)

para s=1 a N hacer:

para q=1 a Nant hacer:

asignar la posición Lcni a la maquina actual i por la ec. 55 y 57.

si s<n entonces escoger la siguiente máquina j por la ec. 53 y 54.

actualizar 𝐵𝑙𝑘𝑠𝑞

fin para

fin para

Actualizar niveles rastro

Calcular ∆𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗), ∀(𝑖, 𝑗) ∈ 𝐸 por la ec. 58

Evaporar y reforzar 𝑟𝑎𝑠𝑡𝑟𝑜(𝑖, 𝑗), ∀(𝑖, 𝑗) ∈ 𝐸 por la ec. 59

Hasta que se cumpla el requisito de terminación

El algoritmo se aplicó para solucionar un problema impulsado por la modernización de una gran

fundición de hierro en Toowoomba, Australia. La fundición estableció una celda con quince

máquinas, una de ellas con posición fija, para producir cinco productos distintos, con diferentes

tamaños, pesos y volúmenes de producción. El diseño se adaptó a obstáculos, localización de

pasillos y puntos de llegada y salida, restricciones de máquinas móviles y el posible acceso a los

contenedores de basura en puntos indicados, entre otras restricciones.


54

La aplicación de la optimización de colonia de hormigas a un problema real de distribución de

máquina añadió una mejora en los modelos de disposición de máquina anteriores: permitir cuatro

posibles orientaciones. Además, demostró la adaptación con éxito de un ACO para problemas de

diseño de máquinas realistas.

4.5.3 Colonia de hormigas como optimizador de procesos logísticos

Silva, et al. (2002) propusieron un algoritmo fue basado en la colonia de hormigas para presentar

la metodología de programación de procesos logísticos, que se aplicó a un proceso logístico real

en Fujitsu-Siemens Computers.

La finalidad de los procesos logísticos es entregar el pedido a tiempo minimizando las existencias,

teniendo en cuenta que su entrega debe realizarse en la fecha marcada, ni antes ni después.

El proceso logístico puede dividirse en cinco pasos secuenciales. Inicialmente llega un pedido

realizado por el cliente que contiene la fecha de entrega deseada. Los componentes indicados en

el pedido deben solicitarse a los proveedores externos. Una vez llegan los componentes se

entregan a lugares de cross-docking donde se crea una lista de existencias. El proceso de decisión

determina que pedidos van a entregarse, teniendo en cuenta la disponibilidad de componentes, y

estos son asignados. Finalmente, el pedido se entrega al cliente.

En el algoritmo de colonia de hormigas se distinguen dos conjuntos de entidades: las órdenes y

los componentes. Cada componente se representa como una fuente de alimento y cada pedido

como un nido de la colonia. Se asigna una hormiga por cada fuente de alimento, la cual se encarga

de distribuir la cantidad de alimento a los 𝑛 nidos. En cada iteración 𝑡, las hormigas eligen el

primer nido con una probabilidad 𝑝 y depositan una feromona 𝜏 en el camino desde la fuente de

alimento hasta el nido. Cuando todas las 𝑚 hormigas han visitado todos los 𝑛 nidos, completando

así el recorrido.

La hormiga 𝑘 elige el camino a un nido con una probabilidad (60), entregando una cantidad 𝑞𝑗𝑖

de la total 𝑞𝑖 del componente 𝑖 ∈ {1, … , 𝑚} a una orden 𝑗 ∈ {1, … , 𝑛}.

𝑝𝑖𝑗𝑘 (𝑡) = {

𝜏𝑖𝑗𝛼 · 𝜂𝑖𝑗

𝛽

∑ 𝜏𝑖𝑟𝛼 · 𝜂𝑖𝑟

𝛽𝑛𝑟∉Γ𝑘

0

𝑠𝑖 𝑗 ∉ Γ𝑘


(60)

Definición 9. Cross-docking.

El cross-docking es una técnica de preparación de pedidos que transfiere la mercancía recibida

directamente, o mediante un búfer intermedio, al muelle de envío. El cross-docking ahorra

pasos de manipulación, ya que no es necesario almacenar ni recoger las mercancías (Van den

Berg, 2007).


55

Donde 𝜏𝑖𝑗 es la cantidad de feromona que conecta el componente 𝑖 a la orden 𝑗, 𝜂𝑖𝑗 es una función

de visibilidad y Γ𝑘 es la lista tabú de la k-ésima hormiga. La lista tabú contiene los pedidos

visitados por la hormiga 𝑘 y los pedidos que no necesitan el componente 𝑖 . La función de

visibilidad (61) se determina con la siguiente fórmula.

𝜂𝑖𝑗 = 𝑒𝑑𝑗

(61)

Donde 𝑑𝑗 es el retraso del pedido 𝑗. El retraso 𝑑 hace referencia a la diferencia entre el día real y

la fecha deseada, guiando así a las hormigas a recorrer caminos de los pedidos que se encuentran

retrasados. Los parámetros 𝛼 y 𝛽 indican la importancia relativa de la feromona del rastro con la

visibilidad, respectivamente.

La actualización local de feromonas (62) viene determinada por la fórmula siguiente.

𝛿𝑖𝑗𝑘 (𝑡) = {

𝜏𝑐

0

𝑠𝑖 𝑞𝑗𝑖 ≤ 𝑞ì


(62)

Donde 𝜏𝑐 es una pequeña constante.

Una vez completado el recorrido, la modificación de feromona en todos los bordes viene dada

por (63).

∆𝜏𝑖𝑗 = ∑ 𝛿𝑖𝑗𝑘

𝑚

𝑘=1

(63)

La evaluación de las soluciones puede evaluarse a través de la fórmula (64), también denominado

índice de rendimiento.

𝑧 = ∑ 𝑎𝑗

𝑛

𝑗=1

(64)

𝑑𝑜𝑛𝑑𝑒, {𝑎𝑗 = 1 𝑠𝑖 𝑑𝑗 = 0

𝑎𝑗 = 0 𝑑𝑒 𝑜𝑡𝑟𝑜 𝑚𝑜𝑑𝑜

Y 𝑛 es el número de pedidos.

La actualización global de feromona (65) después de completar cada recorrido se expresa como:

𝜏𝑖𝑗(𝑁 × 𝑛 × 𝑚) = {𝜏𝑖𝑗(𝑛 × 𝑚) × 𝜌 + ∆𝜏𝑖𝑗

𝜏𝑖𝑗(𝑛 × 𝑚) × 𝜌 𝑠𝑖 𝑧(𝑁) ≥ max 𝑍


(65)


56

En cada recorrido 𝑁 del algoritmo, formado por 𝑛 × 𝑚 iteraciones 𝑡, se calcula 𝑧 y se almacena

en el conjunto 𝑍 = {𝑧(1), … , 𝑧(𝑁)}. El coeficiente de evaporación (1 − 𝜌) evita el

estancamiento de la solución.

Algoritmo 5. Optimización de colonia de hormigas para procesos logísticos

Inicialización:

Establecer para cada par (𝑖, 𝑗): 𝜏𝑖𝑗 = 𝜏0

Establecer 𝑁 = 1 y definir un 𝑁𝑚𝑎𝑥

Colocar las 𝑚 hormigas

Mientras 𝑁 ≤ 𝑁𝑚𝑎𝑥:

Construir un recorrido completo

Para 𝑖 = 1 a 𝑚:

Para 𝑘 = 1 a 𝑛:

Elegir el siguiente nodo utilizando 𝑝𝑖𝑗𝑘 (𝑡) de ec. 60

Actualizar localmente utilizando 𝛿𝑖𝑗𝑘 (𝑡) de ec. 62

Actualizar la lista tabú Γ𝑘

Analizar soluciones

Calcular el índice de rendimiento 𝑧 (𝑁) utilizado la ec. 64

Actualizar globalmente 𝜏𝑖𝑗(𝑁 × 𝑛 × 𝑚) utilizando la ec. 65

El algoritmo se aplicó a un conjunto de datos reales demostrando ser un método de programación

mejor que la asignación previa.


57

5 METAHEURÍSTICA ACO PARA EL SALBP-1

5.1 INTRODUCCIÓN

La metaheurística utilizada para la resolución del SALBP-1 se basa principalmente en el sistema

de colonia de hormigas, ACS. Como se comenta en el apartado 4.4.5, el diseño original del ACS

se encuentra orientado a la resolución del TSP.

Las diferencias principales entre ambos problemas son:

- En el TSP no existen restricciones de precedencia entre ciudades. Cada hormiga es libre

de escoger la siguiente ciudad a visitar, siempre y cuando se construya el camino a partir

de la información heurística y la cantidad de feromona. Sin embargo, en SALBP-1 existen

restricciones de precedencia entre tareas.

- La función objetivo de SALBP-1 es reducir el número de estaciones. El TSP no utiliza

ninguna variable que se asemeje a las estaciones en SALBP-1.

- En el TSP existe la posibilidad de iniciar el recorrido de la hormiga en una ciudad

concreta introducida por el usuario o de forma aleatoria, mientras que en SALBP-1

siempre se inicia en las primeras tareas disponibles (forma directa) o en las finales (forma

indirecta) debido a las restricciones de precedencia.

Sin embargo, se encuentran varias similitudes entre los problemas que se aplicarán para

construcción del algoritmo para SALBP-1.

- Cada ciudad en el TSP representará una ciudad en el SABLP-1.

- No es posible pasar por una ciudad dos veces en TSP, ni repetir una tarea en el SALBP-

1.

- Se considera el sentido de los bordes del grafo.

- Tanto las ciudades en TSP, como las tareas en SALBP, siguen una precedencia.

- La solución se construye en medida que una hormiga posicionada en un nodo 𝑖 se dirige

a un nodo 𝑗, formando una secuencia de ciudades en TSP, tareas en SALBP.

- Las feromonas son depositaras en los bordes que conforman la unión entre dos ciudades

o pareja de tareas.

5.1.1 La función objetivo para SALBP-1

La función objetivo de SALBP-1 es minimizar el número de estaciones para un tiempo de ciclo

dado. Primeramente, se calcula el número mínimo de estaciones posible. El algoritmo inicia con

un valor de número de estaciones máximo y a medida que itera el algoritmo substituye el número

de estaciones actual por su solución óptima, construyendo en el proceso una secuencia de tareas

que ejecutadas en ese orden generen un número de estaciones. En el momento que el algoritmo

construya una secuencia que represente el número de estaciones mínimo, el algoritmo finaliza e

imprime el resultado.


58

5.2 FUNCIONAMIENTO GENERAL

5.2.1 Esquema básico

El esquema básico del algoritmo elaborado para la resolución del SALBP-1 mediante la

metaheurística ACO es mostrado en la Figura 6.

Figura 6. Esquema básico del funcionamiento del algoritmo para resolver problemas SALB-1.



59

5.2.2 Matriz de feromona

La matriz de feromonas contiene la información del rastro entre tareas. Para la solución de

problemas directos, se elabora una matriz de (𝑛 + 1) × (𝑛 + 1), donde 𝑛 es el número de tareas.

Las tareas que no disponen de tarea precedente, o las tareas que no disponen de tarea sucesora,

son asignada a tareas ficticias creadas: 𝛼 y 𝜛. Esto hace posible la aplicación de la regla de

transición entre la primera tarea de la secuencia, que tendrá bordes hacia las tareas que no tengan

precedente en el grafo.

La matriz inicializa con un valor de feromona dado, el cual se hace presente en todos los bordes.

Es recomendable aplicar un valor alto de feromona inicial para evitar que las primeras hormigas

influencien en gran medida a las siguientes, así se reduciría la probabilidad de estancamiento y

aumentaría la exploración inicial (Bretón y Fernández, 2000).

5.2.3 Actualización del rastro

La actualización del rastro de feromonas se realiza una vez se hayan construido todas las

soluciones de la subcolonia. Primeramente, se procederá a la evaporación en todos los bordes del

grafo, y seguidamente se aplicará una cantidad adicional (66) únicamente en aquellas

subsecuencias de tareas más próximas al número mínimo de estaciones. Las fórmulas del apartado

actual fueron empleadas para la construcción de un algoritmo ACO para la resolución de SALBP-

E con resultados positivos (Bretón y Fernández, 2000).

𝜏𝑖𝑗 ← (1 − 𝜌) · 𝜏𝑖𝑗 +1

(𝑑(%)𝑚𝑒𝑗𝑜𝑟)2

(66)

Donde d(%) es la discrepancia de la función objetivo respecto a la mejor cota hallada (67), y 𝜏𝑖𝑗 es

la cantidad de rastro de feromona del borde (i, j).

𝑑𝑚𝑒𝑗𝑜𝑟(%) =𝑂𝐵𝐽𝑚𝑒𝑗𝑜𝑟 − 𝐶𝑂𝑇𝐴𝑆𝐴𝐿𝐵𝑃−1

𝐶𝑂𝑇𝐴𝑆𝐴𝐿𝐵𝑃−1· 100

(67)

Donde 𝑂𝐵𝐽𝑚𝑒𝑗𝑜𝑟 es el valor mínimo de estaciones de la mejor secuencia encontrada por el

momento.

Una vez encontrada una solución mejor a la obtenida por el momento, se aplicará una deposición

de feromonas adicional sobre la subsecuencia de tareas que la produce (68). La cantidad de

feromona en cada borde de la subsecuencia se determinará a partir del mayor rastro de esta 𝑘

veces superior. Además, la matriz de feromonas actualizada será almacenada para, en caso de ser

aplicado el criterio de desviación, sustituir a otra matriz de feromonas generada posteriormente.


60

𝜏𝑖𝑗 ← 𝑘 · max∀𝑘

{𝜏𝑖𝑘} , ∀(𝑖, 𝑗) ∈ 𝑠𝑢𝑏𝑠𝑒𝑐𝑢𝑒𝑛𝑐𝑖𝑎 𝑑𝑒 𝑙𝑎 𝑚𝑒𝑗𝑜𝑟 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛

(68)

La matriz de feromonas actualizada se aplicará para la siguiente subcolonia de hormigas, que

servirá de guía para encontrar mejores soluciones. De esta manera, la matriz de feromonas

representa la “memoria” de las hormigas hacia caminos de los recorridos con mejor función

objetivo encontrados. El proceso de actualización de feromonas completo se muestra a

continuación en la Figura 7.

Figura 7. Proceso de actualización del rastro de feromonas en el algoritmo.



61

5.2.4 Backtracking de la matriz de feromonas

Como se ha comentado en el apartado anterior, cada vez que se encuentra una solución mejor a

la obtenida hasta el momento se deposita una cantidad de feromona y se guarda la matriz. Este

último proceso se realiza para poder sustituir la matriz de feromonas actual por la matriz

anteriormente guardada en caso de cumplirse el criterio de desviación.

La aplicación del backtracking permite la exploración del espacio de soluciones a lo largo de la

ejecución del algoritmo. El criterio de desviación se mostrará como un valor porcentual límite

que representa el número de ristras que obtienen la mejor solución actual sobre el total de ristras

de una subcolonia.

El criterio de desviación se ha fijado en un 35% (Bretón y Fernández, 2000).

5.3 FUNCIONAMIENTO INTERNO: LA SUBCOLONIA

5.3.1 Esquema básico

Las subcolonias las componen un número de hormigas fijado. Cada hormiga construye su

recorrido independientemente del resto de hormigas de su subcolonia. La decisión que determina

la elección de las tareas se calcula mediante el rastro de feromonas de cada borde disponible y un

criterio heurístico. En la Figura 8 puede observarse el proceso de creación de ristras en cada

subcolonia.

En este trabajo, se aplicarán un criterio heurístico que da preferencia a las tareas que requieren de

un mayor tiempo de procesado.

Criterio heurístico tiempo de procesado más largo.

Seleccionar 𝑖∗ tal que 𝑣(𝑖∗) = 𝑚𝑎𝑥𝑖 {𝑣(𝑖)}.

𝑣(𝑖) = 𝑡𝑖

Donde 𝑡𝑖 es la duración de la tarea 𝑖.


62

Figura 8. Proceso de creación de ristras.



63

5.3.2 Índices de decisión

En el caso del TSP, la elección que toma la hormiga viene determinada por una probabilidad

calculada en función del rastro de feromona en los bordes y un criterio heurístico. En su caso, su

criterio solo puede fijarse en priorizar la selección de los caminos más cortos. Para ello, se calcula

la visibilidad mediante la inversa de la distancia.

Las hormigas se guiarán por un índice que combina el rastro obtenido por la matriz de feromonas

y el criterio heurístico. La fórmula que resultará el peso de cada borde(𝑖, 𝑗) es (69).

𝑢𝑖𝑗 = [𝜏𝑖𝑗]𝛼

· [𝜂𝑗]𝛽

(69)

Donde 𝜏𝑖𝑗 es el rastro histórico de feromona sobre el borde (i, j) y 𝜂𝑗 es el peso de la tarea j (70).

𝜂𝑗 = 𝑡𝑖

(70)

La importancia del rastro de feromona y el peso se controla mediante los parámetros 𝛼 y 𝛽.

La probabilidad de elección de cada nodo 𝑗 se obtiene mediante la ponderación del índice de las

tareas disponibles (71).

𝑝𝑖𝑗 =𝑢𝑖𝑗

∑ 𝑢𝑖𝑘𝑘 ∈𝐽 ∀𝑗 ∈ 𝐷

(71)

Donde D es el conjunto de tareas disponibles.

5.3.3 Construcción de secuencia de tareas

Cada secuencia de tareas es construida por una hormiga, la cual inicia en la primera tarea 𝛼 y

añade nodos a medida que recorre el grafo hasta llegar a la última tarea 𝜛. En el algoritmo, las

secuencias son creadas mediante una función iterativa que localiza los nodos donde la hormiga

puede dirigirse en función del nodo actual y los nodos visitados. Una vez determinados los nodos

disponibles, se calcula el índice de decisión para cada uno, su probabilidad y la probabilidad

acumulada es asignada a una lista. Seguidamente, el siguiente nodo se escoge a partir de un valor

aleatorio situando en la lista de probabilidad acumulada, donde su posición indicará el nodo

asignado. Finalmente, el nodo escogido se añade a la secuencia de tareas y se actualiza la lista de

tareas disponibles.


64

5.3.4 Evaluación de la secuencia

Para cada secuencia de tareas se forma una lista que incluye los tiempos de cada tarea en el mismo

orden de secuencia. A partir de dicha lista y un tiempo de ciclo dado, se calcula el número de

estaciones de la secuencia de tareas.

El número de estaciones de cada secuencia se almacena en una lista. El proceso de creación de la

lista de estaciones se muestra en la Figura 9. La posición en la que se encuentra el mínimo valor

de estaciones corresponde a la lista de secuencias con menor número de estaciones. Puede haber

más de una secuencia de tareas con un número de estaciones menor encontrado o mejor que el

encontrado hasta el momento. Estas son seleccionadas para más tarde evaluar si su solución es

igual o mejor que la solución encontrada hasta el momento, y aplicar la feromona correspondiente

en cada borde de la secuencia.

El tiempo de ciclo se puede determinar por medio de una cota mínima y una máxima. La cota

mínima (72) corresponde al valor máximo entre el tiempo de procesado máximo entre las tareas

del problema y el sumatorio de sus tiempos entre un número de estaciones máximo.

𝑇𝐶𝑚𝑖𝑛 = 𝑚𝑎𝑥 {max{𝑡(𝑖)} ;∑ 𝑡(𝑖)𝑖

𝑛𝑚𝑎𝑥 }

(72)

Donde 𝑛𝑚𝑎𝑥 es el número de estaciones máximo. Este número tendría el mismo valor que número

de tareas, ya que el mayor número de estaciones en una secuencia se consigue al asignar una tarea

por estación.

El tiempo de ciclo máximo puede iniciarse como la suma de todos los tiempos de procesamiento

de las tareas (73).

𝑇𝐶𝑚𝑎𝑥 = ∑ 𝑡(𝑖)

𝑖

(73)


65

Figura 9. Proceso de creación de lista de estaciones.



66

5.4 CRITERIO DE FINALIZACIÓN

El algoritmo finaliza cuando encuentra el número de estaciones mínimo o todas las hormigas de

todas las subcolonias han construido sus recorridos. De este modo, el número de iteraciones del

algoritmo corresponde al número de subcolonias introducido.

El número de estaciones mínimo se calcula mediante los tiempos de procesado de tareas y el

tiempo de ciclo dado (74).

𝐸𝑚𝑖𝑛 =∑ 𝑡(𝑖)𝑖

𝑇𝐶

(74)

En cada caso, el algoritmo indica el resultado junto con la subcolonia que ha encontrado el valor.

Si no se encuentra el óptimo, todas las subcolonias habrán construido las soluciones, es decir, el

algoritmo habrá ejecutado todas las iteraciones que hayan sido indicadas.

5.5 CONFIGURACIÓN DE LOS PARÁMETROS BÁSICOS

En el algoritmo, se han utilizado parámetros para el funcionamiento de la metaheurística de

distintos valores, para así poder adaptarse al problema a solucionar.

Los parámetros son los siguientes:

- 𝛼: importancia del rastro de feromona.

- 𝛽: importancia sobre el peso del criterio heurístico.

- 𝜌: porcentaje de evaporación del rastro de feromona.

- 𝑘: valor por el que es multiplicado el nivel máximo de feromona de los bordes que

componen un recorrido mejor al encontrado en iteraciones anteriores.

- 𝑑: desviación porcentual aplicada en el criterio de desviación.

- 𝜏0: feromona inicial sobre los bordes del grafo.


67

6 DESCRIPCIÓN DE LAS PRUEBAS

6.1 INTRODUCCIÓN

El algoritmo ha sido ejecutado en diferentes pruebas con el fin de verificar su correcto

funcionamiento y su capacidad para gestionar problemas de distinto tamaño.

Los problemas utilizados en las pruebas, formados por 𝑛 estaciones, son los siguientes:

- Problema 1(n=6)

- Otto-1 (n=50)

- Gunther (n=35)

- Wee and Magazine (n=75)

Los resultados más favorables han sido obtenidos por los dos primeros problemas. El algoritmo

localiza el óptimo del problema Gunther, sin embargo, es difícil de encontrar. En el caso del

problema Wee and Magazine no se ha encontrado su resultado óptimo.

La siguiente tabla presenta los resultados obtenidos tras cincuenta ejecuciones por problema.

Problema Número de óptimos Tiempo medio

Problema (n=6) 96% 4ms

Otto 1 (n=50) 100% 280ms

Gunther (n = 35) 2% 980ms

Wee and Magazine

(n=75) 0% 13,86s

Tabla 2. Resultados de los problemas ejecutados en el algoritmo.


6.2 ENTORNO COMPUTACIONAL

6.2.1 El lenguaje Python

El algoritmo ha sido programado mediante el lenguaje Python. Las características principales del

lenguaje, descritas en su página web, son las siguientes:

- Python permite dividir el programa en módulos que pueden utilizarse en otros programas.

- Python admite la programación orientada a objetos con clases y múltiples herencias.

- El lenguaje Python es interpretado, es posible ahorrar tiempo porque no es necesario

compilar ni enlazar. El intérprete puede utilizarse iterativamente.

- Python permite escribir programas compactos y legibles. Los programas en Python

suelen ser más breves que otros programas equivalentes en C, C++ o Java. Las razones

se deben a la posibilidad en Python de expresar operaciones complejas en una sola

instrucción, la agrupación de instrucciones mediante la indentación y el no ser necesario

declarar variables y argumentos.


68

- Python contiene funciones de programación avanzadas como generadores y listas por

compresión.

- Python es extensible. Es posible enlazar su intérprete en una aplicación hecha en C y

utilizarlo como lenguaje de extensión o comando para esa aplicación.

La versión utilizada ha sido Python 3.8. debido a ser la última versión Python que permite trabajar

con el paquete Numpy.

Los paquetes que se han utilizado han sido los siguientes:

- Numpy. En el algoritmo se ha utilizado para definir objetos de matriz multidimensional

y ejecutar funciones matemáticas asociadas a la matriz. El paquete también permite la

generación de números aleatorios y proporciona rutinas sencillas para algebra lineal. Las

funciones utilizadas son: numpy.array(), para crear matrices; numpy.full(), para crear

matrices con un valor y tamaño dado, en este caso para crear la matriz de feromona inicial;

numpy.float(), para especificar el tipo de valores que pueden tomarse en una matriz;

np.amin() para localizar el valor mínimo en una lista o matriz, en este caso, en la lista que

informa sobre las estaciones de cada secuencia de tareas construida y también se utiliza

numpy.amax() para encontrar el valor máximo de feromonas en la matriz de feromonas.

- Math. Este paquete incluye diversas funciones matemáticas. En el algoritmo se ha

utilizado la función math.pow() para calcular valores elevados a una potencia (fórmula

68) y math.ceil() para redondear un valor a su próximo mayor, aplicado para el cálculo

del mínimo de estaciones.

- Random. Se utiliza para generar un número aleatorio entre 0 y 1 con la función

random.random(). El valor generado se buscará entre los parámetros de la probabilidad

acumulada para determinar el siguiente nodo visitado.

- Time. Para saber el tiempo de ejecución del algoritmo mediante la función time.time().

6.2.2 Máquina y sistema utilizado

El trabajo se ha realizado en un ordenador MacBook Pro, con procesador Intel Core i5 con

velocidad de 2,7 GHz, memoria de 8GB y sistema operativo macOS Mojave.

Para trabajar con el paquete Numpy, se ha instalado el sistema de gestión de paquetes Anaconda

que permite trabajar con el IDE Spyder, entre otros, con el que se ha llevado a cabo la construcción

del algoritmo.

6.2.3 Juego de datos

Como se ha comentado anteriormente, se han realizado pruebas con cuatro problemas de distinto

tamaño.

La primera prueba mostrada a continuación corresponde a un problema muy sencillo con un total

de seis tareas, con el que fue diseñado el algoritmo.


69

La segunda prueba soluciona un problema compuesto por cincuenta tareas. Los datos del

problema se encuentran presentes en la siguiente página de Internet:

https://assembly-line-balancing.de/salbp/benchmark-data-sets-2013/

Las últimas dos pruebas se efectuaron con problemas presentes en la literatura. La descripción de

los problemas, grafos y bases de datos con los mejores registros se encuentran en otro apartado

de la dirección mostrada anterior, concretamente:

https://assembly-line-balancing.de/salbp/benchmark-data-sets-1993/

Los resultados han sido comparados con la base de datos.

En los siguientes apartados se proporcionan los datos del estudio de cada prueba.

6.3 PROBLEMA 1 (N=6)

6.3.1 Descripción del problema

El problema es ficticio, se utilizó para la construcción y comprobación del funcionamiento del

algoritmo. Está compuesto por seis tareas de tiempos no superior a seis.

El tiempo de ciclo fijado para la resolución del SALBP-1 es de ocho. Durante la ejecución del

algoritmo, ha sido posible encontrar secuencias de tareas con un valor de tiempo de ciclo máximo

de siete, algo inferior al tempo de ciclo introducido. La tabla de precedencias de tareas y tiempos

y el algoritmo se encuentran en anexos 9.1.

Diagrama de precedencias

El diagrama de precedencias incluye las tareas ficticias que indican el inicio y final de la secuencia

de tareas, 𝛼 y 𝜛 respectivamente. En el diagrama que se muestra en la Figura 10, 𝛼 tomará valor

0 y 𝜛 valor 7, el siguiente valor de la última tarea. Ambas no tienen tiempo de procesado.

Figura 10. Diagrama de precedencias del Problema 1.



70

Parámetros utilizados

Este problema se ha ejecutado con veinte subcolonias de diez hormigas en cada una. De esta

manera, el total de hormigas que recorren el grado es de doscientas. Esta cantidad es elevada para

un problema de tan baja complejidad. Normalmente el problema encuentra la solución óptima en

la primera subcolonia. La razón por la que se han aplicado más subcolonias es debido al tipo de

actualización de feromonas. En el caso de no encontrar su óptimo tras el paso de la primera

subcolonia, el algoritmo actualiza la feromona depositando gran cantidad en ciertos bordes que

complica la exploración de otros recorridos en el espacio de búsqueda. Introduciendo más

subcolonias es posible redirigir el resultado gracias al criterio de desviación. Además, como

usualmente la segunda subcolonia no inicia su paso, su tiempo de ejecución tampoco se ve

afectado en gran medida.

El valor de los parámetros es el siguiente: 𝜌 = 0,2, 𝛼 = 0,75, 𝛽 = 0,6, 𝑘 = 2, 𝑑 = 0,35 y

𝜏0 = 1.

6.3.2 Análisis de resultados

El presente problema alcanza el valor óptimo alrededor de un 96% de las ejecuciones. El valor

óptimo es de tres estaciones. En algunos casos el problema se resuelve en un tiempo de ciclo

máximo inferior al fijado, alrededor de un 4,25% de las ejecuciones.

Una de las secuencias de tareas que alcanzan el óptimo tal y como imprime el algoritmo.

Como se puede observar, el óptimo se ha alcanzado en la primera subcolonia.

Tras los resultados obtenidos, para la resolución del problema actual no se recomienda utilizar

valores de feromona altos y preferiblemente, regular el valor de deposición adicional de

feromona para mejorar el espacio de búsqueda. El método heurístico aplicado favorece la

obtención del óptimo al situar las tareas de menor tiempo de procesado en la estación final.

Ejecución Problema 1.

Estación: 1 Tarea(s): [0, 2, 1] Tiempo total: 7

Estación: 2 Tarea(s): [5] Tiempo total: 6

Estación: 3 Tarea(s): [4, 3, 6, 7] Tiempo total: 7

Solución óptima encontrada en la subcolonia: 0

Número de estaciones: 3

Secuencia de tareas: [0, 2, 1, 5, 4, 3, 6, 7]


71

6.4 OTTO-1 (N=50)


El problema forma parte de un conjunto de datos para SALBP-1 (Otto et al., 2013),

concretamente, representa el primer problema del listado de problemas con cincuenta tareas.

El tiempo de ciclo fijado para su resolución es de mil. Sin embargo, se ha ejecutado con otros

valores de tiempo de ciclo inferiores, como por ejemplo de novecientos cincuenta, y se han

obtenido buenos resultados.

La tabla de precedencias de tareas y tiempos y el algoritmo se encuentran en anexos 9.2.


A cada extremo del diagrama de precedencias se sitúan las tareas ficticias, en este caso se visualiza

un gran número de tareas sin sucesora a las que se le acabará asignando la última tarea número

cincuenta y uno. Pueden observarse unos tiempos de procesado dispares que permitirán la

formación de una gran variedad de secuencia de tareas posibles.

Figura 11. Diagrama de precedencia para la resolución de SALBP-1 con cincuenta tareas.

Fuente: Elaboración propia a partir de los datos de Otto et al. (2013).


El problema se ha ejecutado con una cantidad máxima de mil hormigas, sin embargo, las primeras

veinte suelen encontrar el óptimo en la primera subcolonia. En el caso de no ser encontrado en la

primera subcolonia, se deposita una gran cantidad de feromona en los bordes.


𝜏0 = 10.


72


Los resultados obtenidos han sido muy satisfactorios. Las hormigas encuentran el óptimo en el

100% de las ejecuciones. Como mayoritariamente se conforma la secuencia óptima en la primera

subcolonia, el valor de los parámetros utilizados para la deposición de feromona normalmente no

juega un papel importante/carecen de importancia.

A continuación, se muestran los resultados tras una ejecución. La primera lista representa el

número de estaciones encontrado por cada hormiga de la primera subcolonia. Esta información

ha sido añadida para lograr analizar el grado en que las hormigas de la primera subcolonia

encuentran una secuencia óptima. En este caso, un 60%.

De esta manera, una de las formas de reducir el tiempo de ejecución del programa podría ser

ejecutar el algoritmo con menor cantidad de hormigas. Con dos hormigas por subcolonia se

obtuvo lo siguiente:

Ejecución 1 Otto - 1.

[8, 8, 9, 9, 9, 9, 8, 8, 8, 8, 9, 8, 8, 9, 8, 8, 9, 9, 8, 8]

Estación: 1 Tarea(s): [0, 1, 6, 3, 5, 7, 4, 10, 2] Tiempo total: 940

Estación: 2 Tarea(s): [9, 8, 11, 14, 12, 17] Tiempo total: 874


Estación: 4 Tarea(s): [18, 22, 27, 28, 23] Tiempo total: 994

Estación: 5 Tarea(s): [16, 20, 31, 29, 24, 38, 26] Tiempo total: 998




Solución óptima encontrada en la subcolonia: 0 Número de estaciones: 8 Secuencia de

tareas: [[0, 1, 6, 3, 5, 7, 4, 10, 2, 9, 8, 11, 14, 12, 17, 21, 19, 15, 30, 32, 13, 18, 22, 27, 28,

23, 16, 20, 31, 29, 24, 38, 26, 48, 25, 35, 37, 45, 33, 39, 40, 47, 46, 41, 34, 36, 43, 44, 42,

49, 50, 51]]

--- 0.26807212829589844 seconds ---


73

Como se puede observar, el resultado tiempo de ejecución se ha reducido considerablemente.

La cantidad de hormigas y valores de feromona, son idóneos para encontrar óptimos con un

tiempo de ciclo inferior. En una segunda ejecución del problema, ya se encontró la solución

óptima con un tiempo de ciclo marcado de novecientos cincuenta.


Estación: 1 Tarea(s): [0, 3, 5, 2, 8, 9, 14, 6] Tiempo total: 908









tareas: [[0, 3, 5, 2, 8, 9, 14, 6, 13, 21, 15, 17, 30, 32, 29, 18, 20, 1, 26, 27, 36, 23, 22, 25, 19,

31, 28, 10, 43, 35, 7, 34, 44, 49, 37, 46, 4, 38, 50, 11, 12, 16, 45, 24, 33, 48, 39, 42, 40, 47,

41, 51]] Información estaciones: None

--- 0.2704761028289795 seconds ---


[8, 8]










tareas: [[0, 4, 2, 6, 9, 7, 15, 11, 17, 14, 5, 20, 19, 28, 26, 35, 3, 22, 23, 8, 34, 16, 30, 10, 44,

12, 13, 38, 18, 27, 31, 48, 21, 32, 25, 24, 37, 1, 29, 46, 36, 33, 47, 43, 39, 42, 45, 49, 40, 41,

50, 51]] Información estaciones: None

--- 0.04288506507873535 seconds ---


74

6.5 GUNTHER (N=35)


Gunther es un problema estudiado en la literatura creado por Gunther et al. (1983) y representa el

montaje de la base del motor de un automóvil.

El problema contiene un total de treinta y cinco tareas y su tiempo fijado es de ochenta y cuatro.

De esta forma, el número de estaciones óptimo es de seis.


En este caso, el diagrama no muestra las tareas ficticias, 𝛼 y 𝜛. La precedencia de dichas tareas

se encuentra reflejada en la tabla de precedencias y tiempos situada en el apartado 9.3 de anexos,

junto con el algoritmo para la resolución de Gunther. Como puede observarse, durante la línea de

montaje se encuentran tareas sucesoras y precedentes con variabilidad de tiempos. Esta

distribución puede facilitar la obtención del resultado óptimo.

Figura 12. Diagrama de precedencias de Gunther et al. (1983).

Fuente: Scholl A., 1997. Data of Assembly Line Balancing Problems, pág 20.


Para la ejecución del algoritmo se han definido un total de doscientas cuarenta hormigas, ocho

hormigas en cada una de las treinta subcolonias. El hecho de introducir una pequeña cantidad de

hormigas en cada subcolonia en un mayor número de subcolonias permite actualizar la feromona

más veces durante la ejecución y obtener un mismo resultado a un tiempo de ejecución menor.


𝜏0 = 5.


75


El algoritmo encuentra el óptimo en un 2% de las ejecuciones. Sería posible disminuir el valor de

los parámetros de feromona y poder así aumentar el número de iteraciones (subcolonias) que

permitan la ejecución, sin obtener valores de feromona que alcance el valor límite estipulado por

Python. A continuación, se muestra una de las secuencias de tareas encontradas que obtienen un

valor óptimo de estaciones.

En este caso, el resultado óptimo fue descubierto por la cuarta subcolonia de hormigas.

Las tareas de mayor tiempo de procesado de sitúan entre las primeras cuatro estaciones y la última.

La estación cinco la forman tareas con un tiempo máximo de veintitrés y mínimo de uno. La

mayoría de sus tareas no supera el tiempo de seis.

6.6 WEE AND MAGAZINE (N=75)


El problema Wee and Magazine, o también conocido como Wee-Mag, pertenece también al grupo

de problema estudiado en la literatura diseñado por Wee and Magazine (1981) y representa una

línea de montaje con tareas generadas aleatoriamente.

El problema está formado por de setenta y cinco tareas y su tiempo fijado para la resolución es

de cincuenta y seis. De esta manera, el número de estaciones óptimo es de veintisiete, aunque en

la literatura el mínimo número de estaciones encontrado es de treinta.

En el presente algoritmo, se ha llegado a obtener un número de estaciones mínimo de treinta y

uno. El algoritmo se muestra en el apartado 9.4 de anexos, junto con la tabla de precedencias y

tiempos de tares.

Gunther.





Estación: 5 Tarea(s): [21, 22, 30, 31, 23, 24, 25, 32, 26, 27, 34] Tiempo total: 83

6 10 16 23 5 5 5 5 5 1 3



tareas: [0, 17, 1, 5, 10, 6, 8, 2, 9, 13, 3, 4, 11, 12, 7, 14, 15, 16, 18, 19, 20, 21, 22, 30, 31, 23,

24, 25, 32, 26, 27, 34, 33, 35, 28, 29, 36]


76


El diagrama de precedencias de Wee and Magazine está formado por tareas que poseen tiempos

similares de procesado. Además, muchas de las tareas no tienen tareas sucesoras. En este caso, el

diagrama tampoco muestra las tareas de inicio y final del proceso de producción.

Figura 13. Diagrama de precedencias de Wee and Magazine. (1981).

Fuente: Scholl A., 1997. Data of Assembly Line Balancing Problems, pág 28.


Para la resolución del problema se introdujeron un total de doscientas hormigas, ocho hormigas

en cada una de las veinticinco subcolonias. La razón por la que no se utilizó un gran número se

debe a no haber encontrado mejoría en los resultados tras introducir un número mayor de

hormigas, de manera que se decidió reducir el número y así disminuir a su vez el tiempo de

ejecución. Al haber muchos bordes posibles, los valores de feromona en algunos de ellos donde

no han circulado hormigas alcanzan unos valores mínimos establecidos por Python e imprime un

error. De esta manera, el coeficiente de evaporación es inferior al aplicado en el resto de los

problemas y el parámetro 𝑘 tiene un valor superior al resto.


𝜏0 = 10.


Los resultados obtenidos no son favorables. No se ha llegado a obtener el óptimo ni el mínimo

número de estaciones encontrado en la literatura para un tiempo de ciclo de cincuenta y seis.


77

No obstante, en este caso, la actualización del rastro de feromona en los bordes mediante el

cálculo de su discrepancia y la deposición adicional 𝑘, supuso una reducción del número de

estaciones. Los resultados pasaron de tener un número de estaciones de treinta y tres a alcanzar

un treinta y uno, como se muestra a continuación.

En este problema en particular, se observó que los mejores resultados se construían en las

primeras iteraciones, pero en algunas ocasiones se acababan perdiendo. De esta manera, se

decidió guardar el mejor resultado junto con su secuencia de tareas, para poder ser recuperada en

caso de que los resultados empeoraran tras varias iteraciones.

Wee and Magazine.


Estación: 2 Tarea(s): [2, 5] Tiempo total: 47






























Mejor solución encontrada en la subcolonia: 100 Número de estaciones: 31 Secuencia de

tareas: [0, 1, 3, 2, 5, 4, 14, 6, 11, 9, 8, 24, 25, 34, 10, 7, 28, 18, 16, 13, 12, 26, 19, 22, 32, 21,

45, 33, 41, 15, 31, 17, 30, 23, 39, 37, 44, 20, 27, 35, 42, 38, 29, 47, 52, 49, 61, 56, 36, 59,

64, 40, 43, 62, 46, 57, 51, 48, 67, 53, 66, 58, 68, 70, 73, 50, 72, 55, 74, 65, 54, 69, 60, 63,

71, 75, 76]


78

7 CONCLUSIONES

A lo largo del estudio ha sido posible conocer la variedad de problemas de equilibrados de

líneas de montaje, metaheurísticas y modelos de optimización basados en colonia de hormigas.

Las distintas aplicaciones mostradas en el trabajo demuestran que mediante los métodos de

colonia de hormigas pueden encontrarse resultados óptimos o muy buenos para problemas de

optimización completamente distintos.

Tras el diseño de un algoritmo de colonia de hormigas para resolución de problemas de

equilibrados de líneas tipo 1 (SALBP-1) ha sido posible conocer en profundidad y comprobar su

funcionamiento. En algunos casos se han obtenido resultados muy buenos en pocas iteraciones,

demostrando así que los algoritmos de colonia de hormigas son idóneos para la resolución de

equilibrados de líneas de montaje tipo-1.


79

8 Referencias

Alonso, S., Cordón O., Fernández de Viana, I., Herrera, F, 2003.. La Metaheurística de

Optimización Basada en Colonias de Hormigas: Modelos y Nuevos Enfoques. Granada:

Universidad de Granada.

Anon. Capítulo 5: Método de Moodie & Young, Tesis. pág. 31. Disponible a través de:

<http://tesis.uson.mx/digital/tesis/docs/5253/Capitulo5.pdf>[15/01/21].

Battaïa, O., Dolgui, A., 2008. A Transfer Line Balancing Problem by Heuristic Methods:

Industrial Case Studies. Decisions Making in Manufacturing and Services, pág. 34.

Battaïa, O., Dolgui, A.,2013. A taxonomy of line balancing problems and their solution

approaches. International Journal of Production Economics, págs 5-7.

Bautista, J., Bretón, J., Fernández, JA y De la Rosa, M., 2000. Meta-heurística ACO (Ant Colony

Optimization) para la resolución de problemas en líneas de producción. Congreso sobre Técnicas

de Ayuda a la Decisión en la Defensa (Madrid), págs. 267-287. Cataluña: Universidad Politécnica

de Cataluña.

Bautista, J. y Pereira, J., 2002. Ant Algorithms for Assembly Line Balancing. Ant Algorithms,

Springer, págs. 65-75. Barcelona: Universitat Politécnica de Catalunya.

Becker, C. y Scholl, A., 2003. A survey on problems and methods in generalized assembly line

balancing. European Journal of Operational Research, pág. 3.

Blum, C., Dorigo, M., 2004. The Hyper-Cube Framework for Ant Colony Optimization. IEEE

Transactions on Systems, Man, and Cybernetics—Part B, vol. 34, pàgs. 1161.

Blum, C., 2005. Ant colony optimization: Introduction and recent trends. Physics of Life Reviews

2, págs. 354-373.

Boysen, N., Fliedner, M. y Scholl, A., 2006. A classification of assembly line balancing problems.

European Journal of Operational Research, págs. 7-8.

Burkard, RE, Çela, E., Pardalos, PM y Pitsoulis LS, 1998. The Quadratic Assigment Problem.

Kluwer Academic Publishers, Handbook of Combinatorial Optimization, vol. 3, pág. 243.

Steyrergasse: Technical University Graz, y Gainesville: University of Florida.

Colorni, A., Dorigo, M., 1991. Distributed Optimization by Ant Colonies. Milano: Politecnico di

Milano.

Cook, WJ, Cunningham, WH, Pulleyblank, WR y Schrijver, A., 1997. Combinational

Optimization.

Corry, PG y Kozan, E., 2003. Ant colony optimisation for machine layout problems.

Computational optimization and applications 28, págs.287-310.


80

Corry, PG y Kozan, E., 2010. Adapting Ant Colony Optimization to a Real Machine Layout

Problem. ASOR Bulletin, vol. 29, págs. 2-20.

Deneubourg, JL, Aron, S., Goss, S. y Pasteels, JM, 1989. The Self-Organizing Exploratory

Pattern of the Argentine Ant. Naturwissenschaften 76. Bruselas: Springer-Verlag, págs 579-581.

Dorigo, M., Maniezzo, V. y Colorni, A., 1991. Positive feedback as a search strategy. Milano:

Politecnico di Milano.

Dorigo, M., 1992. Optimization, Learning and Natural Algorithms (in Italian). Milano:

Politecnico di Milano.

Dorigo, M., Maniezzo, V. y Colorni, A., 1996. Ant System: Optimization by a colony of

cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B, vol. 26, págs.

29–41.

Dorigo, M. y Gambardella, LM, 1997. Ant Colony System: A Cooperative Learning Approach

to the Traveling Salesman Problem. IEEE Transactions on evolutionary computationm vol.1.

Dorigo, M. y Gambardella, LM, 1997. Ant colonies for the traveling salesman problem. Bruselas:

Université Libre de Bruxelles.

Dorigo, M., Stützle, T., 2006. The Ant Colony Optimization Metaheuristic: Algorithms,

Applications, and Advances. Bruselas: Université Libre de Bruxelles y Darmstadt: TU Darmstadt.

Págs. 251-285.

Dorigo, M., Stützle, T. y Birattari, M., 2006. Ant Colony Optimization: Artificial Ants as a

Computational Intelligence Technique. IEEE Computational Intelligence Magazine, págs. 28-39.

Escobar, DF, Garcés, JA y Restrepo, JH, 2012. Aplicación de la programación entera binaria para

resolver el problema simple de balanceo de línea de ensamble: un caso de estudio. Scientia et

Technica. Pereira: Universidad Tecnológica de Pereira. Pág. 87.

Gagné, C., Gravel, M., Price WL, 2001. A look-ahead addition to the ant colony optimization

metaheuristic and its application to an industrial scheduling problem. 4th Metaheuristics

International Conference (MIC). Porto.

Gambardella, LM, Dorigo, M., 1995. Ant Q- A Reinforcement Learning approach to the traveling

salesman problem. Proceedings of ML-95, Twelfth Intern. Conf. on Machine Learning, Morgan

Kaufmann, págs. 252-260.

Glover, F. y Laguna, M., 1997. Tabu Search. Kluwer Academic Publishers, Boston MA.

Koopmans, TC y Beckmann, MJ, 1957. Assigment problems and the location of economic

activities. Econometrica 25.


81

Maniezzo, V., 1999. Exact and Approximate Nondeterministic Tree-Search Procedures for the

Quadratic Assignment Problem. Institute for Operations Research and the Management

Sciences (INFORMS), INFORMS Journal on Computing, vol 11, págs. 358- 369. Cesena:

Università di Bologna.

Martínez, JL. y Kamal, U., 2011. Assembly Line Balancing and Sequencing. Assembly Line –

Theory and Practice. Tampere: Tampere University of Technology, pág. 17.

Masià R., Pujol, J., Rifà, J. y Villanueva, M., Grafos eulerianos y grafos hamiltonianos. Cataluña:

Universitat Oberta de Catalunya (UOC).

Melian, B., Pérez, JA, Moreno JM, 2003. Metaheurísticas: una visión global. Inteligencia

Artificial. Revista Iberoamericana de Inteligencia Artificial. Santa Cruz de Tenerife: Universidad

de La Laguna.

Michel, R. y Middendorf, M., 1998. An Island model based Ant system with lookahead for the

shortest supersequence problem. Parallel Problem Solving from Nature – PPSN V.

Otto, A. Otto, C. Scholl, A. (2013). Systematic data generation and test design for solution

algorithms on the example of SALBPGen for assembly line balancing. European Journal of

Operational Research 228/1, págs. 33-45.

Restrepo, JH, Medina, PD y Cruz, EA, 2008. Problemas de balanceo de línea salbp-1 y salbp-2:

un caso de estudio. Scientia et Technica. Pereira: Universidad Tecnológica de Pereira. Página:

106.

Scholl, A., 1995. Data of Assembly Line Balancing Problems. Technische Universität Darmstadt.

Págs. 1-2.

Scholl, A., y Voß, S., 1996. Simple Assembly Line Balancing--Heuristic Approaches. Journal

of Heuristics, 2, pág. 220.

Scholl A., 1997. Data of Assembly Line Balancing Problems, págs 20 y 28.

Silva, CA, Runkler, TA, Sousa, JM y Palm, R., 2002. Ant Colony as Logistic Processes

Optimizers.

Stützle, T. y Hoos, HH, 1999. MAX – MIN Ant System. Elsevier Science. Bruselas: Université

Libre de Bruxelles, y Vancouver: University of British Columbia.

Thomopoulos, NT, 2014. Assembly Line Planning and Control. Editorial: Springer, págs. 8-10.

Tinoco, LA, Rodríguez, LA, Alvarado, A. y Rodríguez, MI, 2018. Comparación de métodos de

balanceo de línea de ensamble para una caja de cambios. Academia Journals, vol.10, pág. 2369.

Tongue, FM, 1960. Summary of a Heuristic Line Balancing Procedure. Management Science,

vol.7.


82

Valero, M., Pita, I., 2012. Capítulo 6: Vuelta Atrás. Madrid: Universidad Complutense de Madrid.

Facultad de Informática.

Van den Berg, JP, 2007. Integral Wharehouse Management, pág. 80.


83

9 ANEXOS

El apartado se compone por los algoritmos y tablas de precedencias y tiempos de cada problema

ejecutado en el algoritmo.

9.1 PROBLEMA 1 (N=6)

9.1.1 Tabla de precedencias y tiempos

Tarea Tiempo Precedencia

0 0 -

1 3 0

2 4 0

3 2 1

4 3 1

5 6 2

6 2 4, 5

7 0 3, 6

Tabla 3. Precedencias y tiempo entre tareas del Problema 1.


9.1.2 Algoritmo problema 1 (n=6)

import numpy as np, math, random, time

#Entrada de datos

n_hormigas = 10

n_subcolonias = 20

m_feromonas = []

m_pesos = []

ro = 0.2

alfa = 0.75

beta = 0.5

feromona_inicial = 1

ntareas = 6

tiempo = [0,3,4,2,3,6,2,0]

TC = 8

precedenciasDI = np.array([["-", None],

[0, None],

[0, None],


84

[1, None],

[1, None],

[2, None],

[4,5],

[3,6]])

k = 2

n_max_precedencias = len(precedenciasDI[1])

por_criterio = 0.35

#Crear matriz feromona inicio

m_feromonas = np.full(

shape=(ntareas+1,ntareas+1),

fill_value=feromona_inicial,

dtype=np.float)

#Calculo de cotas del problema

sumatorio_tiempo = sum(tiempo)

Emin = sumatorio_tiempo/TC

Emin = math.ceil(Emin)

Emax = ntareas

Emejor = Emax

#Asignacion tareas a hormigas

def crearRistra(nodoactual):

i = nodoactual + 1

ult_tarea = ntareas+1

tareas_camino = 0

disponibles = []

visitados=[]

if nodoactual ==0:

visitados.append(0)

while tareas_camino < ntareas:

#Crear lista disponibles


85

for i in range(0,len(precedenciasDI)):

for j in range(0, len(precedenciasDI[n_max_precedencias-1])):

if nodoactual == precedenciasDI[i][j]:

if i not in visitados:

num=0

j=0

while j < n_max_precedencias:

if precedenciasDI[i][j] != None:

num = num + 1

j=j+1

if num == 1:

disponibles.append(i)

elif num < n_max_precedencias+1:

c = 0

j=0


if precedenciasDI[i][j] in visitados:

c = c+1

j=j+1

if c == num:


#Calcular u mediante criterio heuristico

sumatorio_u = 0

lista_u = []

for i in disponibles:

fer= m_feromonas[(nodoactual,i-1)]

u = math.pow(tiempo[i], beta) * math.pow(fer,alfa)

lista_u.append(u)

sumatorio_u = sumatorio_u + u

#Calcular probabilidad

prob_acum = 0

prob_list = []

for i in lista_u:


86

prob = i/sumatorio_u

prob_acum = prob_acum + prob

prob_list.append(prob_acum)

#selecionar siguiente nodo

#Por criterio heuristico

p = random.random()

for i in range(0,len(prob_list)-1):

if prob_list[i] <= p and prob_list[i+1] >= p:

visitados.append(disponibles[i+1])

break

if prob_list[i] >= p:

visitados.append(disponibles[i])

break

#Cuando no hay mas de una tarea disponible

if len(disponibles) == 1:

visitados.append(disponibles[0])

nodoactual=visitados[-1]

if len(disponibles) >= 1:

disponibles.remove(nodoactual)

tareas_camino= tareas_camino + 1

visitados.append(ult_tarea)

return visitados

#Crear lista tareas

def listatareas(ntareas):

hormiga = 1

m_tareas = []

while hormiga < n_hormigas+1:

nodoactual = 0


m_tareas.append(crearRistra(nodoactual))

hormiga = hormiga + 1


87


return m_tareas

#Crear matriz tiempos

def tiemposristras(m_tareas, ntareas, tiempo):

listatiempos = []

m_tiempos=[]

for ii in range(len(m_tareas)):

for jj in range(ntareas + 2):

listatiempos.append(tiempo[m_tareas[ii][jj]])

m_tiempos.append(listatiempos)

listatiempos = []

return m_tiempos

#Calcular lista de estaciones para cada ristra

def listaestaciones(m_tiempos, TC, ntareas):

lista_resultados = []

i=0

while i < len(m_tiempos):

j=0

nestaciones= 0

contadortiempo=0

while j < ntareas + 1:

if m_tiempos[i][j] < TC:

if contadortiempo + m_tiempos[i][j] >= TC:

nestaciones = nestaciones + 1

contadortiempo=0

else:

contadortiempo = contadortiempo + m_tiempos[i][j]

j=j+1

else:


j= j+1


88

nestaciones= nestaciones + 1

lista_resultados.append(nestaciones)

i= i + 1

return lista_resultados

#Encuentra la ristra o ristras generada(s) con menor número de estaciones

def mejorRistra(m_tiempos, lista_resultados, m_tareas, Eactual):

mejor_ristra = []

Eactual = np.amin(lista_resultados)

if Eactual in lista_resultados:

h = lista_resultados.index(Eactual)

if m_tareas[h] not in mejor_ristra:

mejor_ristra.append(m_tareas[h])

return mejor_ristra

#Actualizar feromona

def actualizaferomonas(mejor_ristra, m_feromonas, ro,ntareas, lista_resultados, k, por_criterio,

Emejor, Eactual):

#evaporacion

for i in range(0, ntareas+1):

for j in range(0,ntareas+1):

m_feromonas[i][j] = m_feromonas[i][j]*(1-ro)

#deposito de feromona en mejores ristras

for i in range(len(mejor_ristra)):

for j in range(ntareas+1):

r = mejor_ristra[i][j]

s = mejor_ristra[i][j+1]

d = math.pow((Emin-Eactual)/Eactual, 2)

m_feromonas[r][s-1] = m_feromonas[r][s-1]*(1/d)

#deposito de feromona adicional si el numero de estaciones encontradas es menor que el

encontrado hasta el momento

m_fer = np.amax(m_feromonas)


89

bordes = []

if Eactual < Emejor:



sublista = [i,j]

for r in range(len(mejor_ristra)):

for s in range(len(mejor_ristra[0])):

if sublista[0]== mejor_ristra[r][s]:

if sublista[1] ==mejor_ristra[r][s+1]:

if sublista not in bordes:

bordes.append(sublista)

for i in range(len(bordes)):

r = bordes[i][0]

s = bordes[i][1]

m_feromonas[r][s-1] = m_fer*k

#guarda la feromona y ristra

global saved_m_feromonas, saved_mejor_ristra

saved_m_feromonas = m_feromonas

saved_mejor_ristra = mejor_ristra

Emejor = Eactual

#criterio de desviacion

l = lista_resultados.count(Emejor)

t = len(lista_resultados)

if l/t < por_criterio:

m_feromonas = saved_m_feromonas

return (m_feromonas, saved_m_feromonas, Emejor, saved_mejor_ristra)

#Informa sobre las tareas en cada estacion y su tiempo de procesado

def informacionEstaciones(mejor_ristra, TC, tiempo):


90

estacion= 1

c=0

m=0

lista = []

mejor_ristra = mejor_ristra[0]

while m < len(mejor_ristra):

t = mejor_ristra[m]

if tiempo[t] <= TC:

if c + tiempo[t] > TC:

print("Estación:", estacion, "Tarea(s):", lista, "Tiempo total:", c)

estacion = estacion +1

lista = [t]

c= tiempo[t]

m = m+1

elif c + tiempo[t]< TC:

if tiempo[mejor_ristra[m+1]] ==0:

c = c+tiempo[t]

lista.append(t)

lista.append(mejor_ristra[m+1])


break

else:

c = c + tiempo[t]

lista.append(t)

m= m + 1

else:


c = c+tiempo[t]

lista.append(t)



break

else:


91

lista.append(t)

print("Estación:", estacion, "Tarea(s):", lista, "Tiempo total:", c+tiempo[t])


lista = []

c=0

m = m+1

else:

print("Estación", estacion, "Tarea(s)", t, "Tiempo total:", TC)

lista = []

estacion= estacion + 1

m= m+1

def solucion(ntareas, tiempo, TC, Emax, Emin, m_feromonas, ro, k, por_criterio, Emejor,

n_subcolonias):

subcolonia = 0

while subcolonia < n_subcolonias:

m_tareas = listatareas(ntareas)

m_tiempos = tiemposristras(m_tareas, ntareas, tiempo)

lista_resultados = listaestaciones(m_tiempos, TC, ntareas)


mejor_ristra= mejorRistra(m_tiempos, lista_resultados, m_tareas, Eactual)

if Eactual == Emin:

break

m_feromonas, saved_m_feromonas, Emejor, saved_mejor_ristra =

actualizaferomonas(mejor_ristra, m_feromonas, ro, ntareas, lista_resultados, k, por_criterio,

Emejor, Eactual)

subcolonia = subcolonia + 1

if Emejor < Eactual:

mejor_ristra = saved_mejor_ristra

elif Eactual < Emejor:

Emejor = Eactual


92

if Emejor < Emin:

while Eactual < Emin:




dtype=np.float)

solucion(ntareas, tiempo, TC, Emax, Emin, m_feromonas, ro, k, por_criterio, Emejor,

n_subcolonias)

if subcolonia < n_subcolonias:

print("Solución óptima encontrada en la subcolonia:", subcolonia,

"Número de estaciones:", Emejor,

"Secuencia de tareas:", mejor_ristra,

"Información estaciones:", informacionEstaciones(mejor_ristra, TC, tiempo))

else:

print("Mejor solución encontrada en la subcolonia:", subcolonia,




start_time = time.time()


n_subcolonias)

print("--- %s seconds ---" % (time.time() - start_time))


93

9.2 OTTO-1 (N=50)


Tareas Tiempo Precedencia

0 0 -

1 73 0

2 125 0

3 172 0

4 58 0

5 139 0

6 91 0

7 166 6

8 76 2

9 210 2

10 116 5

11 72 4

12 203 9,11

13 141 8

14 95 9

15 256 9

16 105 11

17 218 9

18 292 13

19 145 14

20 93 17

21 133 14

22 191 17

23 62 15

24 104 16

25 76 22

26 169 20

27 251 18

28 198 19

29 259 21

30 148 5,15

31 182 20,23

32 52 15,21

33 176 1, 7, 12, 25, 35

34 157 26

35 103 28

36 222 29


94

37 73 27

38 86 4, 30

39 198 33

40 191 33

41 39 33

42 159 33

43 184 36

44 219 22, 34

45 49 35, 37

46 148 37

47 183 33, 37

48 228 23, 38

49 163 31,43

50 27 46

51 0 3, 10, 24, 32, 39, 40, 41, 42, 44, 45, 47, 48, 49, 50

Tabla 4. Precedencias y tiempo entre tareas de Otto-1.


9.2.2 Algoritmo Otto-1 (n=50)


#Entrada de datos

n_hormigas = 20

n_subcolonias = 50

m_feromonas = []

m_pesos = []

ro = 0.1

alfa = 0.75

beta = 0.7


ntareas = 50

tiempo = [0, 73, 125, 172, 58, 139,

91, 166, 76, 210, 116,

72, 203, 141, 95, 256,

105, 218, 292, 145, 93,

133, 191, 62, 104, 76,


95

169, 251, 198, 259, 148,

182, 52, 176, 157, 103,

222, 73, 86, 198, 191,

39, 159, 184, 219, 49,

148, 183, 228, 163, 27, 0]

TC = 950

precedenciasDI = np.array([["-", None, None, None, None, None, None, None, None, None,

None, None, None, None],

[0, None, None, None, None, None, None, None, None, None, None, None,

None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],

[9, 11, None, None, None, None, None, None, None, None, None, None,

None, None],


None, None],


None, None],


None, None],


None, None],


96


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],

[1, 7, 12, 25, 35, None, None, None, None, None, None, None, None, None],


None, None],


None, None],


None, None],


None, None],


97


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],


None, None],

[3,10, 24, 32, 39, 40, 41, 42, 44, 45, 47, 48, 49, 50]])

k = 10


por_criterio = 0.35





dtype=np.float)


98





Emax = ntareas

Emejor = Emax



i = nodoactual + 1


tareas_camino = 0

disponibles = []

visitados=[]

if nodoactual ==0:

visitados.append(0)







num=0

j=0



num = num + 1

j=j+1

if num == 1:



c = 0


99

j=0



c = c+1

j=j+1

if c == num:



sumatorio_u = 0

lista_u = []




lista_u.append(u)



prob_acum = 0

prob_list = []

for i in lista_u:






p = random.random()




break



break


100









return visitados

#Crear lista tareas


hormiga = 1

m_tareas = []


nodoactual = 0





return m_tareas



listatiempos = []

m_tiempos=[]





101


listatiempos = []

return m_tiempos




i=0


j=0

nestaciones= 0

contadortiempo=0





contadortiempo=0

else:


j=j+1

else:


j= j+1



i= i + 1




mejor_ristra = []



102




return mejor_ristra



Emejor, Eactual):

#evaporacion














bordes = []




sublista = [i,j]






103




r = bordes[i][0]

s = bordes[i][1]






Emejor = Eactual









estacion= 1

c=0

m=0

lista = []



t = mejor_ristra[m]


104

if tiempo[t] <= TC:




lista = [t]

c= tiempo[t]

m = m+1



c = c+tiempo[t]

lista.append(t)



break

else:

c = c + tiempo[t]

lista.append(t)

m= m + 1

else:


c = c+tiempo[t]

lista.append(t)



break

else:

lista.append(t)



lista = []

c=0

m = m+1

else:



105

lista = []


m= m+1


n_subcolonias):

subcolonia = 0







if Eactual == Emin:

break



Emejor, Eactual)





Emejor = Eactual

if Emejor < Emin:





dtype=np.float)


106


n_subcolonias)






else:







n_subcolonias)



107

9.3 GUNTHER (N=35)



0 0 -

1 29 0

2 3 1

3 5 2

4 22 3

5 6 1

6 14 5

7 2 1, 6

8 5 6

9 22 8

10 30 1

11 23 4

12 30 1

13 23 9

14 2 7, 10

15 19 14

16 29 15

17 2 0

18 2 7, 12

19 19 18

20 29 17, 19

21 6 16, 20

22 10 21

23 16 22

24 23 23

25 5 21

26 5 25

27 5 24, 26

28 40 11, 13, 27

29 2 28

30 5 21

31 5 30

32 1 21, 31

33 40 11, 13, 27, 32

34 2 27

35 2 33

36 0 29, 34, 35


108

Tabla 5. Precedencias y tiempo entre tareas de Gunther.


9.3.2 Algoritmo Gunther (n=35)


#Entrada de datos

n_hormigas = 8

n_subcolonias = 30

m_feromonas = []

m_pesos = []

ro = 0.1

alfa = 0.75

beta = 0.7


ntareas = 35

tiempo = [0, 29, 3, 5, 22, 6, 14, 2, 5, 22, 30, 23,

30, 23, 2, 19, 29, 2, 2, 19, 29, 6, 10, 16,

23, 5, 5, 5, 40, 2, 5, 5, 1, 40, 2, 2, 0]

TC = 84

precedenciasDI = np.array([["-", None, None, None],

[0, None, None, None],






[1, 6, None, None],







109


[7,10, None, None],




[7,12, None, None],


[17,19, None, None],








[11,13,27, None],





[11,13,27,32],



[29,34,35, None]])

k = 10


por_criterio = 0.35





dtype=np.float)


110





Emax = ntareas

Emejor = Emax



i = nodoactual + 1


tareas_camino = 0

disponibles = []

visitados=[]

if nodoactual ==0:

visitados.append(0)







num=0

j=0



num = num + 1

j=j+1

if num == 1:




111

c = 0

j=0



c = c+1

j=j+1

if c == num:



sumatorio_u = 0

lista_u = []




lista_u.append(u)



prob_acum = 0

prob_list = []

for i in lista_u:






p = random.random()




break




112

break









return visitados

#Crear lista tareas


hormiga = 1

m_tareas = []


nodoactual = 0





return m_tareas



listatiempos = []

m_tiempos=[]




113



listatiempos = []

return m_tiempos




i=0


j=0

nestaciones= 0

contadortiempo=0





contadortiempo=0

else:


j=j+1

else:


j= j+1



i= i + 1




mejor_ristra = []


114





return mejor_ristra



Emejor, Eactual):

#evaporacion














bordes = []




sublista = [i,j]






115




r = bordes[i][0]

s = bordes[i][1]






Emejor = Eactual









estacion= 1

c=0

m=0

lista = []



t = mejor_ristra[m]


116

if tiempo[t] <= TC:




lista = [t]

c= tiempo[t]

m = m+1



c = c+tiempo[t]

lista.append(t)



break

else:

c = c + tiempo[t]

lista.append(t)

m= m + 1

else:


c = c+tiempo[t]

lista.append(t)



break

else:

lista.append(t)



lista = []

c=0

m = m+1

else:



117

lista = []


m= m+1


n_subcolonias):

subcolonia = 0







if Eactual == Emin:

break



Emejor, Eactual)





Emejor = Eactual

if Emejor < Emin:





dtype=np.float)


118


n_subcolonias)






else:







n_subcolonias)



119

9.4 WEE AND MAGAZINE (N=75)



0 0 -

1 23 0

2 24 1

3 25 1

4 26 1

5 23 1

6 22 1

7 6 1

8 22 4

9 23 6

10 21 6

11 22 6

12 15 5

13 5 3, 6

14 23 4

15 4 2, 5

16 26 4

17 21 15

18 5 10

19 24 12

20 25 9, 15

21 26 16

22 26 13

23 24 15

24 27 3, 9

25 20 24

26 23 16, 18

27 25 20

28 13 25

29 3 27

30 11 17, 18, 25

31 21 26

32 22 26

33 21 21, 25

34 22 25

35 25 27

36 8 27


120

37 22 31

38 24 35

39 22 31

40 21 36

41 6 26, 33

42 26 35

43 22 36

44 6 32

45 21 32

46 25 40

47 11 42

48 22 43, 46

49 21 47

50 25 43, 47

51 22 39, 46

52 22 47

53 23 47

54 22 50

55 22 50

56 25 52

57 23 52

58 21 53

59 22 49

60 22 50

61 22 49

62 22 43, 49

63 21 55

64 27 59

65 23 58

66 2 59

67 26 62

68 25 66

69 24 68

70 22 68

71 24 68

72 4 68

73 22 68

74 10 68

75 25 68

76 0 7, 8, 11, 14, 19, 23, 28, 29, 30, 34, 37, 38, 41, 44, 45, 48, 51,

54, 56, 57, 60, 61, 63, 64, 65, 67, 69, 70, 71, 72, 73, 74, 75


121

Tabla 6. Precedencias y tiempo entre tareas de Wee and Magazine.


9.4.2 Algoritmo Wee and Magazine (n=75)


#Entrada de datos

n_hormigas = 8

n_subcolonias =25

m_feromonas = []

m_pesos = []

ro = 0.05

alfa = 0.75

beta = 0.5


ntareas = 75

tiempo = [0, 23, 24, 25, 26, 23, 22, 6, 22, 23, 21, 22,

15, 5, 23, 4, 26, 21, 5, 24, 25, 26, 26, 24,

27, 20, 23, 25, 13, 3, 11, 21, 22, 21, 22, 25,

8, 22, 24, 22, 21, 6, 26, 22, 6, 21, 25, 11,

22, 21, 25, 22, 22, 23, 22, 22, 25, 23, 21, 22,

22, 22, 22, 21, 27, 23, 2, 26, 25, 24, 22, 24,

4, 22, 10, 25, 0]

TC = 56

precedenciasDI = np.array([["-", None, None, None, None, None, None, None, None, None,

None, None, None, None, None, None, None, None, None, None, None, None, None, None,

None, None, None, None, None, None, None, None, None],



None, None, None, None, None, None, None],








122




























[3, 6, None, None, None, None, None, None, None, None, None, None, None,


None, None, None, None, None, None],

















123


































[17, 18, 25, None, None, None, None, None, None, None, None, None, None,













124















































125















































126





































[7, 8, 11, 14, 19, 23, 28, 29, 30, 34, 37, 38, 41, 44, 45, 48, 51, 54, 56, 57, 60,

61, 63, 64, 65, 67, 69, 70, 71, 72, 73, 74, 75]])

k = 15


por_criterio = 0.35


127





dtype=np.float)





Emax = ntareas

Emejor = Emax



i = nodoactual + 1


tareas_camino = 0

disponibles = []

visitados=[]

if nodoactual ==0:

visitados.append(0)







num=0

j=0



num = num + 1


128

j=j+1

if num == 1:



c = 0

j=0



c = c+1

j=j+1

if c == num:



sumatorio_u = 0

lista_u = []




lista_u.append(u)



prob_acum = 0

prob_list = []

for i in lista_u:






p = random.random()




129


break



break









return visitados

#Crear lista tareas


hormiga = 1

m_tareas = []


nodoactual = 0





return m_tareas



listatiempos = []


130

m_tiempos=[]





listatiempos = []

return m_tiempos




i=0


j=0

nestaciones= 0

contadortiempo=0





contadortiempo=0

else:


j=j+1

else:


j= j+1



i= i + 1



131



mejor_ristra = []





return mejor_ristra



Emejor, Eactual):

#evaporacion














bordes = []




sublista = [i,j]


132








r = bordes[i][0]

s = bordes[i][1]






Emejor = Eactual









estacion= 1

c=0

m=0

lista = []


133



t = mejor_ristra[m]

if tiempo[t] <= TC:




lista = [t]

c= tiempo[t]

m = m+1



c = c+tiempo[t]

lista.append(t)



break

else:

c = c + tiempo[t]

lista.append(t)

m= m + 1

else:


c = c+tiempo[t]

lista.append(t)



break

else:

lista.append(t)



lista = []


134

c=0

m = m+1

else:


lista = []


m= m+1


n_subcolonias):

subcolonia = 0







if Eactual == Emin:

break



Emejor, Eactual)





Emejor = Eactual

if Emejor < Emin:





135


dtype=np.float)


n_subcolonias)






else:







n_subcolonias)


Documents

Estudio del equilibrado de líneas de montaje por medio de