Zaloamati
Permanent URI for this communityhttps://hdl.handle.net/11191/38
Browse
5 results
Search Results
- Algoritmos heurísticos para el ruteo de dispositivos programables(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2016-02-16) GALVAN CARDOZO, FABIAN GUILLERMOEn este documento, se presenta una nueva manera eficiente de obtener un ruteo detallado, para cualquier tipo de FPGA con estructura de islas. A partir de instancias de ruteo global, que proporciona el programa de empaquetamiento versatil, colocación y ruteo, se creó un nuevo algoritmo heurístico llamado búsqueda indexada, que parte de un modelo matemático de satisfacibilidad booleana y que se resuelve mediante una coloración condicional de gráficas, que también se propone aquí. A su vez, se potencializa la heurística de búsqueda indexada, por medio de un árbol R, el cual indexa los datos de tal manera, que la heurística puede conocer rápidamente el número de conflictos, en los que aumenta o disminuye la función objetivo, si se realiza un movimiento. Con cada uno de estos aspectos, se busca un ruteo de calidad perfecta y que además disminuya considerablemente el tiempo necesario para obtener un ruteo detallado. Finalmente, se compara el ruteo detallado de seis instancias obtenidos por el VPR y por la búsqueda indexada.
- Optimal Euclidean Non-Crossing 3-Matchings(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2017-08-29) VAZQUEZ CASAS, GUALBERTOLet P be a set of 3k points in the Euclidean plane. A 3-matching is a partition of P into k subsets of 3 points each, called triplets. The cost of each triplet fa; b; cg is given by minfjabj + jbcj; jbcj + jcaj; jcaj + jabjg, and the cost of the 3-matching is the sum of the costs of its triplets. The Euclidean 3-matching problem consists on finding a minimum cost 3-matching of P under the Euclidean metric. In the usual formulation of the Euclidean 3- matching problem we need to find a minimum cost 3-matching of P. This problem has several applications, especially in the insertion of components on a printed circuit board. Johnsson, Magyar, and Nevalainen introduced two integer programming formulations for this problem, and proved that its decision version is NP-complete if each triplet has an arbitrary positive cost (i.e., not necessarily Euclidean). The problem remains NP-complete even if the points of P correspond to vertices of a unit distance graph (a metric cost function). In this work, we prove that the linear programming relaxations of these two models are equivalent. Then we introduce three new integer programming models that use fewer variables than those from Johnsson, Magyar, and Nevalainen. We also compare the linear programming relaxations of the models. Besides the minimization problem, we are also interested in a similar maximization problem: finding a maximum cost non-crossing Euclidean 3-matching of P, where non-crossing means that no two segments intersect in a common interior point. Both problems, minimum cost and maximum cost non-crossing, are challenging, and we believe that both are NP-hard. Exact solutions to both problems can be attained through integer programming; however, in order to obtain good solutions in feasible times, we fix our attention to heuristics. We present three heuristics specially designed for our problems and compare their solutions and execution times against solving the exact models.
- Número acromático de gráficas gramíneas bipartitas(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2016-03-16) CASTELAN CHAVEZ, ERNESTOEn este trabajo estudiamos diversas propiedades de las gráficas gramíneas bipartitas, enfocándonos en particular en las coloraciones completas y el número acromático de las mismas. En el capítulo 1, presentamos al lector los conceptos preliminares más importantes para el desarrollo de éste trabajo. En el capíutlo 2, introducimos una clasificación de las gramíneas bipartitas en varias familias, y presentamos varias propiedades relacionadas con la estructura de estas familias, en particular, mostramos dos resultados importantes: una caracterización de un grupo de gramíneas bipartitas en términos de acoplamientos y la relación que el mismo grupo guarda con la familia de torneos regulares. También exploramos el problema de reconocer gráficas gramíneas en estas familias y presentamos un programa entero y un algoritmo que resuelven el problema. En cuanto a problemas de coloración, en el capítulo 3, damos una cota superior, que es justa, para el número acromático de una familia de gramíneas bipartitas y clasificamos las coloraciones completas que alcanzan dicha cota. Estudiamos algunas de las coloraciones completas mencionadas y exhibimos condiciones necesarias y condiciones suficientes para la existencia de estas coloraciones. Así mismo, presentamos técnicas para obtener y extender coloraciones completas en las gráficas de interés.
- Metaheurísticas para el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW)(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2017) MONTES OROZCO, EDWINEn este trabajo, se presentan 7 técnicas basadas en cuatro metaheurísticas y dos métodos exactos, las cuales son: Sistema de Hormigas (AS), Búsqueda Armónica (HS), Algoritmo Genético (GA), Búsqueda local iterada (ILS), Algoritmo primaldual (PDA) y Método dual simplex (DSM) para resolver el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW), haciendo énfasis en los algoritmos híbridos entre estas técnicas, los cuales se denominan AS-GA, AS-HS, DSM-ASPDA, AS-ILS, donde a excepción de DSM-AS-PDA, las técnicas involucradas trabajan de manera entrelazada. Con el fin de analizar, comparar y caracterizar el comportamiento de las técnicas desarrolladas, estas se emplearon para resolver 12 instancias del VRP-TW. En AS-GA, se utiliza el GA para encontrar una mejor solución con la población generada por un ciclo de n hormigas dentro de AS, con la cual se actualiza el nivel de la matriz de feromona para el siguiente ciclo de hormigas. Con esto se logra guiar la construcción de una manera más eficaz, y el algoritmo genético ayuda a no converger de manera prematura, sino que debido a la codificación se diversifica el espacio de búsqueda. Dentro de AS-HS, la técnica HS sirve para guiar el comportamiento del AS a través de los cambios en la matriz de feromona, ya que se aprovecha la información de un número n de ejecuciones de la HS guardadas en la memoria armónica (HM). En el procedimiento propuesto se retoman las mejores soluciones para la actualización del nivel de la fermona. Por último, en DSM-AS-PDA se utiliza el optimizador denominado Gurobi ejecutando el método dual simplex para resolver dos relajaciones lineales del problema original. Con las soluciones regresadas por Gurobi se inicializa la matriz de nivel de fermona para AS y una vez que termina la ejecución de AS con base en la mejor solución entregada, se utiliza el algoritmo PDA para revisar si la solución encontrada es la óptima. Los resultados muestran que los algoritmos híbridos desarrollados poseen un comportamiento más robusto respecto a las técnicas reportadas en la literatura y a su vez, son capaces de generar mejores soluciones con un número menor de llamadas a la función objetivo en instancias grandes, utilizando menos recursos computacionales.
- Composición en una Sociedad de Músicos(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2016-12-13) VAZQUEZ CORTES, ALBERTO ALEJANDROEn este trabajo, se presenta una nueva metaheurística denominada “Composición en una Sociedad de Músicos" (CSM); la cual basa sus ideas sociológicas sobre el comportamiento colaborativo en el Método de Composición Musical (MMC); CSM incluye además dos nuevos comportamientos sociales: aislamiento y abuso. Por otro lado se incluye el paradigma de reactividad (resultado del aprendizaje, autoadaptación y toma de decisiones) en las metaheurísticas. Con base en los resultados numéricos obtenidos, se puede decir que la CSM ha demostrado tener una buena capacidad de resolver instancias del problema de optimización global continua sin restricciones en comparación con otras técnicas del estado del arte.