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 h = ? (i) 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].
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.
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 se les especifique la codificación de los individuos y una función de evaluación que mida la aptitud de cada individuo. La función de Aptitud es la guía que emplean estos algoritmos para explorar de forma eficiente su amplio espacio de búsqueda de posibles soluciones.
Figura 2: Estructura de Algoritmo Evolutivo Un algoritmo Evolutivo clásico tiene la estructura mostrada en la figura 2 en la cual se pueden observar 5 componentes característicos de un Algoritmo Evolutivo:
1. Representación genética de soluciones del problema.
2. Una Manera para crear la población inicial.
3. Una función de evaluación que pone en juego las reglas de la evolución, proporcionando soluciones en términos de la aptitud.
4. Operadores genéticos que efectúan la creación de la descendencia durante la reproducción.
5. Valores para los parámetros que el algoritmo requiere: tamaño de la población, probabilidades para aplicar los operadores genéticos, etc.
Un vasto número de problemas pueden ser tratados con estos algoritmos: Edificación de almacenes en localidades distintas, Planificación de Eventos, Distribución de Recursos o de Materiales, etc. Entre estos problemas se encuentran los de Asignación Cuadrática de Facilidades – QAP, que hasta el presente constituye uno de los problemas más difíciles de ser tratados por el hombre.
El AE propuesto tiene características propias para problemas combinatorios, éstas se pueden observar en la representación de la solución y en cada uno de los operadores del algoritmo.
La representación de individuos
Figura 3: Representación de Individuo. . . Cromosoma Una solución es representada por un vector de longitud m cuyo contenido es una permutación ? (vea figura 3) que representa a una secuencia de asignación de facilidades. Para el problema tratado el vector corresponde al orden de relación en que se deben asignar las máquinas, el valor de aptitud de esta permutación identifica el costo de producir en la línea de flujo. Una asignación natural b=(1, 2, … , m) y cualquier permutación de este vector son soluciones factibles al problema; por lo que el espacio de búsqueda corresponde a m!.
El Método de Selección El método de selección más ampliamente usado es la rueda de la ruleta, y por ende también es usado como el método de selección principal en este algoritmo propuesto. Sin embargo, un segundo esquema de selección se introduce con la finalidad de dar aceleración al proceso de escogencia de los individuos parientes; este método de selección es propuesto por Darrell Whitley [6], el cual opera de la manera siguiente: en cada generación se ordenan los individuos en forma decreciente, de acuerdo al valor de aptitud de cada cromosoma; para cada individuo con índice impar se determina el índice del individuo con el cual se cruzará empleando la siguiente expresión:
donde N representa el tamaño de la población, a es un parámetro que introduce un sesgo que determina la preferencia de los individuos mejor adaptados y rand(0,1) es un valor aleatorio entre 0 y 1. La ecuación (2) es una transformación no lineal que da mayor probabilidad a los índices bajos, que corresponden a los individuos de mejor adaptación, sin embargo puede producir cualquier índice sin importar cuan grandes sean las adaptaciones de los individuos, permitiendo disipar el efecto de un súper individuo que domine en generaciones tempranas a toda la población.
Elitismo
El proceso de selección es complementado con una estrategia elitista con la cual se asegura la convergencia hacia el individuo con el valor óptimo en cada generación. Una de sus posibles implementaciones es: en cada generación, después de haber ejecutado los operadores genéticos de cruce y mutación, se selecciona el mejor individuo de la población llamado Elite, el cual reemplaza al peor individuo en la generación siguiente. Si existe un individuo mejor que el elite previo, entonces éste pasará a ser el nuevo elite. La idea fundamental es que el mejor individuo en cada generación prevalezca, para así asegurar la convergencia del Algoritmo Evolutivo Propuesto.
El Operador Cruce
Figura 4: Operador Cruce Principal Cualquier número de máquina que se repita y por ende, aquella que falte dará lugar a un individuo no factible, así que el operador de cruce implementado en este algoritmo es diseñado considerando la no-factibilidad de individuos. Al igual que en el esquema de selección, en donde se implementaron dos mecanismos diferentes; también se implementan dos operadores de cruce distintos. Tal como se muestra en la figura 4, el operador de cruce principal [1], consiste en seleccionar un punto aleatoriamente en ambos padres, dividiendo los cromosomas padres en dos, la primera mitad de un padre se copia intacta sobre un hijo, y la segunda mitad del otro padre se copia idénticamente sobre el otro hijo. Los cromosomas descendientes se completan copiando las máquinas faltantes tomándolas de los cromosomas padres alternando aleatoriamente entre ellos, solamente se copia aquellas máquinas que falten en los descendientes.
Figura 5: Operador Cruce Secundario El otro operador cruce [4], consiste en tomar, alternando entre los cromosomas padres, los genes para ir llenando al cromosoma hijo (con un recorrido secuencial de izquierda a derecha), con la excepción de aquellos genes que coinciden en ambos padres, los cuales ocuparán esa misma posición en la descendencia. Así se podrá apreciar en el ejemplo mostrado en la figura 5, en donde además se observa que existe un gen comodín, el cual se introduce en el cromosoma descendiente en la posición donde sea necesaria su presencia. El único cromosoma hijo reemplaza al cromosoma pariente con peor aptitud.
Figura 6: Mecanismo de Mutación Primario |
Figura 7: Mecanismo de Mutación Secundario |
El primer mecanismo de mutación, consiste en seleccionar dos puntos aleatorios sobre el cromosoma seleccionado (dada una probabilidad de mutación) para luego invertir la secuencia de los genes enmarcados por estos dos puntos, así se muestra en la figura 6, donde se expresa mediante el ejemplo la idea fundamental de este método de mutación [4]. Como operador de mutación secundario, se empleó una variación del primer mecanismo, donde solo se intercambian los genes identificados por los puntos tomados aleatoriamente. Para más detalles véase la figura 7, en donde se esquematiza este proceso de mutación.
Un Computador paralelo es un conjunto de procesadores capaces de cooperar en la solución de un problema simultáneamente. Esta definición incluye supercomputadoras con cientos de procesadores, redes de estaciones de trabajo y máquinas con múltiples procesadores (Computadoras Multiproceso).
La paralelización del AE mejora considerablemente tanto en el desempeño como la calidad de las soluciones encontradas en un espacio de búsqueda grande.
Paralelización del algoritmo evolutivo
Se ha tomado el modelo de paralelismo grano grueso el cual toma una población global repartida entre los EPs migrando el mejor individuo, llamando subpoblación a cada una de las partes. Cada subpoblación evoluciona en un procesador por la ejecución del AE. Luego de un número de generaciones predeterminado, que se llama período de migración, se realiza una difusión o migración del mejor individuo de la población total en cada una de las subpoblaciones.
Figura 8: Centralización de los Individuos mejor adaptados La estrategia para la migración consiste en centralizar los individuos mejor adaptados de cada subpoblación en uno de los procesadores (llamado Proceso Centralizador), ver figura 8; donde son cruzados entre ellos sin reemplazo. Se maneja como criterio de decisión el individuo mejor adaptado de los migrados más los descendientes del cruce, el cual reemplaza al peor individuo de las subpoblaciones tal como se observa en las siguientes figuras.
| |
Figura 9: Proceso de Migración | |
En la figura 9, se muestra que los individuos centralizados no desaparecen de la subpoblación de origen, sino que se hace una copia del mismo el cual es recibido por el proceso centralizador. También se puede observar que el mejor individuo seleccionado en este proceso, retorna a la población de donde proviene creándose una nueva copia del mismo (por reemplazo del peor individuo).
Las pruebas del algoritmo se realizaron en dos etapas, la primera consistió en hacer las corridas sobre una máquina secuencial y la segunda etapa se realizaron corridas sobre una arquitectura paralela.
Resultados Secuenciales La plataforma computacional corresponde a un Pc INTEL Pentium III de 866 MHz con 256 KB de caché de segundo nivel y memoria RAM de 256 Mbyte. El algoritmo fué desarrollado en lenguaje C++ y compilado con c++ del sistema operativo Linux Red Hat 7.2.
Los datos para las corridas de la etapa de prueba han sido basados en:
Tamaño de la población: 100 individuos.
Número de generaciones: 1000 iteraciones.
Probabilidad de Cruce y Mutación: 0.8 y 0.033 respectivamente.
Número de Corridas: 20 corridas por cada conjunto de máquinas.
Tabla 1: Comparación de Desempeño de Algoritmos. Arquitectura Secuencial.
AEQAP OO* | AE Nmaneiro | DIH | ||||||||
Maq.(m). | Valor Obj | T(seg). | Valor Obj | T(seg) | Valor Obj. | T(seg) | ||||
4 | 500 | 0.00 | 500 | 0.00 | 500 | 0.00 | ||||
6 | 1371 | 0.26 | 1371 | 0.42 | 1371 | 0.00 | ||||
8 | 2898 | 1.12 | 2898 | 1.92 | 2898 | 0.28 | ||||
12 | 512963 | 2.28 | 512963 | 3.83 | 515376 | 0.36 | ||||
16 | 89534 | 4.28 | 92022 | 8.83 | 96686 | 0.45 | ||||
24 | 4278567 | 28.15 | 4386817 | 31.15 | 4764502 | 1.48 | ||||
48 | 34319104 | 35.06 | 34925368 | 44.12 | 37361376 | 2.45 | ||||
56 | 117658864 | 42.14 | 120956504 | 57.84 | 125769984 | 3.24 | ||||
* Algoritmo Evolutivo Propuesto Orientado a Objeto | ||||||||||
En la tabla 1 se muestran las corridas del AE propuesto, comparando los resultados con otros algoritmos desarrollados que tratan el mismo problema: el algoritmo evolutivo AE_MANEIRO en [1] y el Método Depth – First Insertion Heuristic (DIH) en [5].
Como se puede observar en la tabla, el AE propuesto reporta mejoras en cuanto a calidad de solución encontradas así como de tiempos de respuestas. Sin embargo estos tiempos aumentan conforme crece la dimensión del problema. Para estudiar espacios de búsqueda tan grandes (16! = 20.922.789.888.000), se requiere de un tamaño de población mayor a 100 individuos o simplemente emplear un modelo computacional que permita evolucionar más de una población independientemente.
La plataforma computacional de prueba corresponde a un Cluster de 48 Nodos conectados por switches de alta velocidad Marynet y fibra óptica. Para mayor detalles ver http://www.labf.usb.ve, el algoritmo fue desarrollado empleando lenguaje C++ y la Interfaz de Paso de Mensajes (MPI) [8].
Para las corridas se consideró a un proceso especial, al cual se le asignó una alta mutación para crear un efecto ruido sobre el total de la población[9]; y los datos para las corridas de la etapa de prueba han sido basados en:
Tamaño de la población global: 100 individuos.
Número de generaciones: 1000 iteraciones para cada proceso.
Probabilidad de Cruce y Mutación: 0.75 y 0.055 respectivamente.
Probabilidad de Cruce y Mutación para Proceso Especial: 0.25 y 0.75.
Cantidad de procesos: 4 procesos.
Período de Migración: 20 generaciones.
Número de Corridas: 20 corridas por cada problema.
Tabla 2: Comparación de Desempeño de Algoritmo Secuencial Vs. Algoritmo Paralelo
AEQAP_OO | AEP_QAP* | ||||||||
Máq. (m) | Valor Obj. | T(seg.) | Valor Obj. | T(seg.) | |||||
16 | 89534 | 4.28 | 89534 | 3.25 | |||||
24 | 4278567 | 28.15 | 4198729 | 15.75 | |||||
48 | 34319104 | 35.06 | 32982182 | 21.73 | |||||
56 | 117658864 | 42.14 | 112647544 | 39.65 | |||||
* Algoritmo Evolutivo Paralelo Propuesto | |||||||||
En la tabla 2 se muestran las corridas del AE Paralelo, comparando los resultados con el AE secuencial, considerando para ello sólo los problemas de más alta dimensionalidad ( a partir de 16 máquinas). Las pruebas experimentales mostraron que el algoritmo evolutivo paralelo (propuesto) logra satisfaces todas las perspectivas en cuanto a las soluciones encontradas y tiempos de respuestas; ya que reporta mejoras significativas que las soluciones encontradas por otros algoritmos además de disminuir los tiempos de respuesta, lográndose demostrar las ventajas de esta técnica, la cuál radica en su generalidad y flexibilidad de adaptación.
[1] Ninoska Maneiro. Algoritmo Genético Aplicado a Problemas de Localización de Facilidades. Tesis de Maestría. Facultad de Ingeniería. Universidad de Carabobo, 2001.
[2] Patrice Roger Calgari. Parallelization of Population – Based Evolutionary logarithms for Combinatorial Optimization Problems. Doctoral thesis. Éole Polytechnique Fédérale de Lausanne. Lausanne – Francia, 1999.
[7] Ahuja Ravindra K. A Greedy Genetic Algorithm for the Quadratic Assignment Problem. Technical report, Indian Institute of technology. Kanpur – India, 1997.
[4] Alice E. Smith & David M. Tate. A Genetic Approach to the Quadratic Assignment Problem. Technical report, University of Pittsburgh, 1992.
[5] B. R. Sarker et al. Backtracking of jobs in one dimensional machine location problems. European Journal of Operational Research, 85:593–609, 1995.
[3] John Holland. Adaptation in Natural and Artificial Systems. Ann Harbord. University of Michigan, 1999.
[6] Germán Larrazábal et al. Un Algoritmo Genético Paralelo Grano Grueso. Reporte Técnico. Facultad de Ciencias y Tecnología. Universidad de Carabobo, 1996.
[8] Willians Gropp et al. Using MPI – 2nd Edith. Edit. MIT Press. ISBN: 0-262-571323.
[9] Brad L. Miller and David E. Goldberg. Genetic Algorithms, Selection Schemes, and the Varying Effects of Noise. Technical report, Department of Computer Science. University of Illinois at Urbana/Champaign. USA, 1996.
Autor:
González Heli, Larrazábal Germán, Loyo Jaqueline.
helijesusg[arroba]cantv.net
| Página siguiente |