ALGORITMO EVOLUTIVO PARA PROBLEMAS QAP

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

...