Asignacion Cuadratica

Algoritmo Evolutivo Paralelo para problemas de Asignación Cuadrática – QAP

INTRODUCCIÓN

El Problema de Asignación Cuadrática (QAP – Quadratic Assignment Problem) es un problema clásico de optimización combinatorio, en el cual se encuentra un vasto número de problemas de diseño y de distribución de recursos en diferentes campos, donde la decisión a tomar es una asignación de elementos de un conjunto en otro. El QAP es considerado como un problema complejo y dificultoso de resolver y puede establecerse como un conjunto de n elementos distintos que deben ser localizados (asignados) en n localidades distintas de forma óptima [1][2]. Aunque se han propuesto numerosas heurísticas y procedimientos, los Algoritmos Evolutivos (AEs) han emergido como una clase de búsqueda aleatoria de varios puntos concurrentemente sobre un espacio de soluciones factibles; tales algoritmos son inspirados por mecanismos de la evolución natural y mecanismos genéticos introducidos por J. Holland en los años 70 [3]. Experimentos reales sobre algoritmos evolutivos para QAP se iniciaron a principios de los 90’s; David M. Tate y Alice E. Smith (1.992) establecen mecanismos de selección y reproducción (cruce) así como una posible codificación para problemas de Asignación Cuadrática [4]. Para el año 1.995 B. R. Sarker y un grupo de colaboradores implementan un algoritmo secuencial: Depth – First Insertion Heuristic (DIH) [5]; para el problema de retrocesos (backtracking) de trabajos en la localización de una máquina en una línea unidimensional de flujo. Otra manera de tratar a los Algoritmos Genéticos es analizando su paralelismo intrínseco, tal como lo hizo G. Larrazábal en el año 1.996, cuando plantea un Algoritmo Genético Grano Grueso para un problema de alta dimensionalidad [6]. Más tarde, Patrice Roger Calégari (1.999) en su trabajo de tesis doctoral [2], muestra la paralelización eficiente de Algoritmos Evolutivos. Recientemente fue tratado un problema cuadrático de asignación de facilidades por N. Maneiro (2.001) empleando un algoritmo evolutivo simple [1]; el cual consistió en localizar un grupo de m máquinas de tal manera que se minimice el retroceso (backtracking) dentro de una línea de flujo generalizado.

Este trabajo trata la paralelización de un algoritmo evolutivo desarrollado con tecnología de programación orientada a objetos, el cual está enfocado a resolver problemas de asignación cuadrática de facilidades de alta dimensionalidad; el mismo se inicia con una exposición breve de los Problemas de Asignación Cuadrática en donde se detalla el problema de QAP tratado. Luego se explica el funcionamiento de los Algoritmos Evolutivos y enseguida se describe el Algoritmo Evolutivo Propuesto. Más adelante se habla de Paralelismo y de la Paralelización del Algoritmo Evolutivo; para finalizar con la exposición de los resultados en dos partes: Resultados de Corrida Secuencial y Resultados de Corrida Paralela.

ALGORITMO EVOLUTIVO PARA PROBLEMAS QAP

Problemas de Asignación Cuadrática – QAP

Los Problemas de Optimización Combinatorios son frecuentemente tratados en el campo de la Optimización. Cubren una amplia gama, entre ellos la minimización del costo total de interacción entre pares de facilidades. Los mismos están caracterizados por la consideración de una selección o permutación de un conjunto discreto de elementos o por una asignación entre ellos.

El Problema de Asignación Cuadrática (QAP – Quadratic Assignment Problem) es quizás el más complejo y dificultoso de los problemas de asignación, en donde, relacionar dos asignaciones particulares tiene un costo asociado; tal estructura de costo surge, por ejemplo, cuando el costo de localizar la facilidad i en la localidad k y la facilidad j en la localidad l es una función de la distancia entre las dos localidades k y l, y el grado de interacción entre las dos facilidades j e i [7].

Formalmente, el QAP puede ser definido por tres matrices nxn [4]: D = {dij} es la distancia entre la localidad i y la localidad j ; F = {fhk} es el flujo entre las facilidades h y k, es decir la cantidad de interacción (tráfico) existente entre las facilidades; C = {chi} es el costo de asignar la facilidad h en la localidad i. Una permutación  puede ser interpretado como una asignación de la facilidad (i)h = en la localidad i. El problema se centra en encontrar una permutación  para un conjunto dado de facilidades {1, 2, … , n} tal que:

A causa de su diversidad de aplicaciones y a la dificultad intrínseca del problema, el QAP ha sido investigado extensamente por la comunidad científica, clasificándolo como un problema NP – Completo o NP – Hard [4].

El Problema QAP tratado

Dentro de la amplia clase del QAP, se encuentra el problema de flujo en línea generalizado, que es una línea de flujo en la cual las operaciones fluyen hacia adelante y no se procesan –necesariamente– en todas las máquinas de la línea. Un trabajo en tal clase de línea puede comenzar y completar su proceso en cualquier máquina, moviéndose siempre hacia delante (down – stream) por operaciones sucesivas de acuerdo con la secuencia de trabajo del proceso. Cuando la secuencia de operaciones de un trabajo no especifica una máquina delante de su localización actual, el trabajo tiene que viajar en sentido contrario (up – stream) a fin de completar la operación requerida. Este problema ha sido tratado por B. R. Sarker en [5].

Figura 1: Una Línea de flujo generalizada

Este "viaje en reversa" de las operaciones es llamado Backtracking, y se desvía de una línea de flujo ideal para un trabajo específico, resultando en una estructura de trabajo ineficiente, como se muestra en la figura 1.

La minimización del backtracking de trabajos en una línea de producción sirve a varias metas implícitas, tales como la reducción del tiempo de ocio de las máquinas, la simplificación del problema de la programación y carga, el incremento de la salida en la línea de producción, entre otros.

Algoritmos Evolutivos

Los Algoritmos Evolutivos son heurísticas basadas en los principios de evolución natural y genética introducido por J. Holland en los años 70’s [3]. Ellos pueden tratar varios puntos de un espacio de búsqueda concurrentemente permitiendo que no sean atrapados en un óptimo local. Además, se pueden ajustar para resolver problemas de optimización combinatorios eficientemente [2].

Los Algoritmos Evolutivos requieren que

...