Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/427| Heurística para el problema MAX-CLIQUE basada en un modelo de cómputo con ADN utilizando GPUs Heuristic for the MAX-CLIQUE problem based on a DNA computing model using GPU's | |
| Nelson Emmanuel Ordóñez Guillén | |
| Israel Marck Martinez Perez | |
| Acceso Abierto | |
| Atribución | |
| Problema Max-Clique,Cómputo con ADN,Heurística,Cómputo biomolecular,Filtrado paralelo,Hilos de CUDA | |
| En sus inicios, los modelos de cómputo biomolecular fueron concebidos como un nuevo paradigma para enfrentar los problemas complejos aprovechando la gran densidad de información de las moléculas biológicas (principalmente ADN) y el paralelismo masivo de sus bio-operaciones. El modelo de etiquetas pertenece a estos modelos y es uno de los más pródigos en cuanto al desarrollo de algoritmos que abordan problemas de la clase NP-Completo. Uno de estos algoritmos es el llamado k-Cliques, que se utiliza para resolver el Problema del Clique Máximo (MCP, por sus siglas en inglés). Sin embargo, a pesar de sus ventajas, es ampliamente conocido que los algoritmos de cómputo biomolecular aplicados a tal clase de problemas, presentan algunos inconvenientes que evidencian su inviabilidad práctica. Estos inconvenientes son principalmente dos: las bio-operaciones son propensas a errores y la entrada (cantidad de ADN) aumenta de manera exponencial respecto al tamaño del problema. Una alternativa poco explorada que permite franquear el primero de estos obstáculos, consiste en la implementación in silico de los algoritmos de cómputo biomolecular en arquitecturas paralelas. El segundo de estos impedimentos se puede atacar combinando estos algoritmos con heurísticas que les proporcionen entradas de tamaño manejable. Tomando esto en consideración, la principal contribución del presente trabajo radica en el desarrollo de una heurística para el MCP, basada en la codificación de la entrada y el filtrado paralelo del algoritmo k-Cliques. En su parte central, esta heurística consiste en la generación y filtrado de tubos de prueba. Cada tubo de prueba contiene un subconjunto del espacio de soluciones completo y se genera tomando subconjuntos de cliques encontrados previamente. El paralelismo masivo de hebras en el filtrado del algoritmo k-Cliques se replica utilizando el paralelismo masivo de hilos de CUDA. Para verificar su desempeño, se realizaron pruebas sobre el conjunto de casos DIMACS. Los resultados obtenidos se comparan con un algoritmo ramifica y acota del estado-del-arte e indican competitividad en casos de prueba de tamaño moderado a grande. Además, una de las principales ventajas del enfoque propuesto, es que permite la obtención de más de una solución en algunos problemas, lo cual es una aracterística no encontrada en ningún otro trabajo previo de su tipo. Biomolecular computing models were initially conceived as a new paradigm to face hard problems by taking advantage from the high-information density existing in biological molecules (mainly in DNA) and massively parallel bio-operations. The sticker model is one of the most popular DNA-based models in the development of algorithms for NP-Complete problems. One of these algorithms, is the so-called k-Cliques sticker algorithm which is used for the Maximum Clique Problem (MCP). However, it has been widely known that the application of DNA computing algorithms for solving such class of problems exhibits two practical limitations: error-prone bio-operations and exponential growth of the input (amount of DNA) with respect to the size of the problem. A scarcely explored alternative which could be used to overcome the inaccuracy of bio-operations, consists of the in silico implementation of DNA-based algorithms using parallel architectures. Aditionally, the scaling-up issue may be tackled combining these algorithms with heuristics in order to provide them with inputs of a manageable size. Thus, the main contribution of this work resides precisely in the development of a heuristic for the MCP, based on the input coding and parallel filtering of the k-Cliques algorithm. In this heuristic, test tubes containing sets of candidate solutions are iteratively generated and filtered out to detect current solutions, where each set is in turn, constructed in an iterative fashion taking subsets from a previously found clique. The parallel filtering strategy of the k-Cliques algorithm is replicated by harnessing the massive threading and parallelism of CUDA. For comparison purposes, computational experiments were performed over DIMACS benchmark set and contrasted with those obtained in a state-of-the-art branch-and-bound algorithm. Experimental results show that the heuristic introduced here is competitive on instances ranging from moderate to large size. Moreover, a key feature of this approach resides in the generation of multiple solutions for some instances, a property not previously found in the literature. | |
| CICESE | |
| 2014 | |
| Tesis de maestría | |
| Español | |
| Ordóñez Guillén,N.E.2014.Heurística para el problema MAX-CLIQUE basada en un modelo de cómputo con ADN utilizando GPUs.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xii, 132 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 234791.pdf | Versión completa de la tesis | 3.91 MB | Adobe PDF | Visualizar/Abrir |