Advanced search


Knowledge area




6 results, page 1 of 1

Diseño de un algoritmo para aproximar el coloreo de una gráfica mediante conjuntos maximales independientes

ANGELICA GUZMAN PONCE (2017)

El problema del coloreo de gráficas por su importancia se ha tratado de solucionar por diferentes algoritmos, entre los más usados se encuentran los heurísticos, los cuales aproximan la solución, además existen diferentes metodologías de solución. En particular, el presente trabajo de Tesis se ha centrado en tres algoritmos heurísticos, el algoritmo greedy de JGraphT, el algoritmo determinista propuesto por Guzmán et al. y las propuestas híbridas de combinar un algoritmo determinista con un algoritmo genético. Derivado de los resultados obtenidos se puede concluir que en términos de n umero de colores las propuestas de Guzmán et al.(Apéndice A) y la que se presenta como trabajo final de tesis son competitivas, debido a que, el promedio de colores obtenidos en 20 ejecuciones, los resultados obtenidos por la propuesta híbrida de esta tesis, son mejores en gran medida que los obtenidos por Guzmán et al. debido a que el número de colores no está disperso con respecto al promedio obtenido, esto se observa en la desviación estándar obtenida para cada prueba. Adicionalmente, de los resultados de coloreo obtenidos por JGraphT el 62.5% excede el coloreo de una a diez unidades de color, mientras que la propuesta de esta Tesis en s olo 45.83% de las instancias el coloreo excede de una a cinco unidades de color, mientras que para Guzmán et al. en un 58.33% el coloreo obtenido excede de una a seis unidades de color. Los resultados obtenidos en esta investigación y concluidos como los que mantienen una mejor aproximación al coloreo, se deben a la implementación de la Fase de regeneración, la cual favoreció en la mayoría de las instancias, que de la gráfica conocida como residual, a que la aproximación al coloreo se cumpliera con el número de colores restantes, es decir el número k conocido como el mejor coloreo obtenido hasta el momento, se le resta el número de MISes extraídos de la primera fase, debido a que los MISes de la fase de extracción son considerados de la completa, dejando una gráfica residual densa, la cual complica que el coloreo sea propio con k-MISes. Por otro lado, de los análisis realizados en la Sección 4 se encuentra el de tiempo de ejecución, donde se muestra el tiempo en segundos que tardó cada algoritmo en obtener una aproximación, de esto se puede concluir que en términos de tiempo de ejecución el algoritmo híbrido propuesto, toma un mayor tiempo de ejecución en comparación con el resto de los algoritmos comparados, debido a que en la fase de regeneración se considera un número de iteraciones para reconstruir un MIS, así como también el volver a implementar la fase completa de coloreo, dentro de la cual el tiempo que se toma en ejecutar la búsqueda Tabú incrementa el tiempo de ejecución. Sin embargo, ya que el objetivo general fue mejorar la aproximación al coloreo, se considera que se cumplió el objetivo y se verificó la hipótesis propuesta.

Dada una gráfíca no dirigida G = (V;E) con un conjunto de vértices V y un conjunto de aristas E, el problema del coloreo de gráfícacas consiste en particionar todos los vértices de V en el mínimo número K de conjuntos (colores), con la característica de que cada par de vértices en un conjunto no compartan arista. El problema de coloreo se ha estudiado desde 3 perspectivas, la primera es el problema original, encontrar el mínimo número de colores con los cuales una gráfíca puede ser coloreado, la segunda trata de decidir si una gráfíca es k colorable, mientras que la última, aproxima el coloreo con respecto al mejor valor reportado en la literatura (ya que puede no conocerse el mínimo). Diversas propuestas de algoritmos se han desarrollado de manera exacta o heurísticas. En esta Tesis se propone un algoritmo de tipo heurístico resultado de la combinación de un algoritmo determinista y un algoritmo evolutivo para aproximar el coloreo de gráficas con respecto al mejor valor reportado en la literatura. El algoritmo propuesto se evalúa con un conjunto de gráficas propuestas en la literatura. Los resultados obtenidos validan la viabilidad de la propuesta con respecto a otros algoritmos reportados en la literatura.

Conacyt: 702275/584432

Master thesis

coloreo de graficas conjuntos maximales independientes teoría de graficas busqueda tabú algoritmos genéticos heuristicas INGENIERÍA Y TECNOLOGÍA

Revisión de Algoritmos Genéticos Aplicados al Problema de la Programación de Cursos Universitarios

MIREYA FLORES PICHARDO (2011)

La programación de horarios académicos es un problema particular que se encuentra dentro del problema general de asignación de recursos. Este problema de horarios, se conoce en la comunidad científica como Problema de Programación de Horarios Universitarios. Los problemas de programación de horarios consisten en generar horarios para tareas definidas, buscando cumplir de la mejor manera con condiciones o requerimientos específicos.

Este problema ha sido tratado con diferentes métodos, por ejemplo Colonia de Hormigas, Búsqueda Tabú, Coloreo de grafos y Algoritmos Genéticos. En éste trabajo se hace una revisión de algunos algoritmos evolutivos que han abordado el problema de horarios académicos aplicando diferentes modelos.

The academic scheduling is a particular problem within the general problem of resource allocation. This scheduling problem is known as the University Timetabling Problem in the scientific community. The scheduling problems consist on generating schedules for defined tasks by pursuing the best way to specific conditions or requirements.

This problem has been addressed with different methods such as Ant Colony, Tabu Search, Graph Coloring and Genetic Algorithms. In this paper we review some evolutionary algorithms that have addressed the problem of academic schedules applying different models.

Article

INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS Programación de Horarios, Optimización Combinatoria, Heurísticas, Algoritmos Genéticos Timetabling, Combinatorial Optimization, Heuristics, Genetic Algorithms

Metaheurísticas

JESUS DEL CARMEN PERALTA ABARCA PEDRO MORENO BERNAL Sergio Nesmachnow ALFONSO D GRANDA TREJO (2018)

Se presenta una breve revisión bibliográfica del nacimiento de las metaheurísticas como parte de la inteligencia artificial para la solución de problemas de optimización combinatoria. Las metaheurísticas son técnicas computacionales de alto nivel para la resolución aproximada de problemas complejos. Se describen los fundamentos

históricos de las metaheurísticas, los principales conceptos sobre su funcionamiento y sus líneas de aplicación en problemas del mundo real. Uno de los criterios más utilizados por la comunidad científica toma en cuenta el número de soluciones exploradas en cada paso de iteración, que además se dividen en dos tipos de metaheurísticas: las basadas en trayectoria y las basadas en población. Las primeras manejan una única solución en cada paso de iteración, mientras que las segundas manejan un conjunto de soluciones candidatas en cada paso.

Article

INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS heurísticas, inteligencia artificial, sistemas expertos, optimización combinatoria

Modeling and simulation of uncondictional maximum likelihood approach for direction of arrival of near field sources

Modelado y simulación de la aproximación de máxima verosimilitud (ML) incondicional en la determinación del DoA en campo cercano.

Darío Bonilla Hernández (2005)

La detección de la Dirección de Arribo (DoA) de múltiples terminales móviles de banda estrecha, es uno de los temas de mayor investigación en la actualidad dentro de la tecnología de Antenas Inteligentes. Para este propósito se han estudiado distintos métodos, empleando técnicas sub-óptimas y óptimas. Los más utilizados han sido los métodos de subespacio, dadas sus ventajas de rapidez y bajo costo computacional. Pensando en algoritmos que proporcionen una mejor distinción de fuentes cercanas, menor error de estimación y buena eficiencia en ambientes ruidosos, es necesario utilizar nuevos métodos que resuelvan el problema de la localización de fuentes de manera eficiente. Dadas las cualidades de los métodos de inferencia estadística, tales como la consistencia, sesgo y de varianza mínima, es interesante considerar los métodos de Máxima Verosimilitud (ML) para aplicarse al problema de localización de fuentes en sistemas de comunicaciones celulares, ya que pueden ser aplicables a sistemas con señales de banda ancha, con mayor número de usuarios, e incluso bajo ambientes muy agresivos donde se tenga una baja Relación Señal a Ruido (SNR). En este trabajo se realiza el estudio de las propiedades de modelado y simulación de la estimación  de la posición de las fuentes de interés bajo la condición de campo cercano por medio de algoritmos de Máxima Verosimilitud Incondicional basados en el método de Maximización de la Esperanza. Así como, también, la evaluación de las bondades del estimador de Máxima Verosimilitud, su modelado y simulación bajo la variación de los parámetros de: Nivel de ruido,  número de muestras tomadas, número de fuentes a localizar y la separabilidad entre fuentes cercanas.  A partir de los resultados obtenidos se definirán las ventajas y desventajas del estimador ML, comparado con el algoritmo MUSIC (Multiple Signal Classification) basado en subespacios. Se establecerán las limitaciones principales de ambos métodos y los escenarios bajo los que responden adecuadamente, encontrándose que el estimador de máxima verosimilitud es más robusto, y resuelve el problema de la localización de fuentes de manera más eficiente bajo las consideraciones establecidas.  

The Direction of Arrival (DoA) is applied to detection of multiple sources, and  is one of the most studied problem in smart antennas technology. For this purpose, there had been studied many methods, based on optimal and sub-optimal techniques. Sub-space based methods had been most popular given their advantages such as speed and easy implementation. Thinking in improve performance algorithms which had better resolution on localization of near field sources, less estimation error, and a good efficiency under high noise scenarios is necessary the use of methods that solves the  source localization problem in a more efficient way. Due to many attractive characteristics of the statistical inference methods such as consistence, minimum variance and asymptotic unbiasedness, is interesting to considerate the Maximum Likelihood Estimation methods for the application on the source localization problem on mobile communications systems. Also, they could be applied to wideband signals systems, for multiple sources and for aggressive scenarios with a low Signal to Noise Ratio (SNR). This thesis studies the main features, model and simulation of the source location estimation under near field condition by Unconditional Maximum Likelihood method, based on Expectation Maximization algorithm. Also, this thesis evaluates the performance, modeling and simulation of this estimator for the variance of the parameters: Noise level, number of snapshots, number of  sources, and closely spaced sources.   According to the results obtained we found the advantages and disadvantages of the ML Estimator compared with the MUSIC (Multiple Signal Classification) algorithm, which is a based in sub-space method. For both methods were established the principal limitations and the scenarios for which they work properly. Also we found that the ML estimator is more robust and solves the source localization problem in a more efficient way for the considerations above established.   

Master thesis

Planificación celular,optimización del radio celular,técnicas heurísticas,WCDMA,comunicaciones móviles celulares INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LAS TELECOMUNICACIONES

Estudio del problema de programación de la producción en un ambiente multi-propósito flexible con división de lotes

MIGUEL ANGEL FERNANDEZ ROMERO (2018)

127 páginas. Maestría en Optimización.

Consejo Nacional de Ciencia y Tecnología (México).

El problema de programación de tareas conocido como programación de la producción en un ambiente multi-propósito flexible con división de lotes es una variante del problema de tipo programación de la producción, en la cual los lotes pueden dividirse en sublotes de diferentes tamaños y asignarse a diferentes máquinas, de tal forma que se disminuyen los tiempos muertos y el tiempo total de procesamiento. El objetivo consiste en minimizar la amplitud de proceso, es decir, la fecha de terminación de la última operación en la última máquina. Debido a la complejidad computacional de este problema, normalmente se recurre a técnicas heurísticas para poder resolverlo. En este trabajo, se propone un algoritmo que combina estrategias de Búsqueda Tabú, con vecindades y técnicas de división de lotes basados en la ruta crítica de cada solución generada. Para determinar la eficiencia del algoritmo propuesto, se adaptaron las instancias edata, rdata y vdata de Hurink. Debido a que este problema casi no se ha reportado en la literatura, no fue posible encontrar soluciones, que sirvieran como punto de comparación, para las instancias antes mencionadas. Por lo tanto, se emplearon dos estrategias para poder evaluar el desempeño del algoritmo propuesto. Primero, se resolvieron las instancias propuestas hasta donde fue posible, con el solver Gurobi. Segundo, se emplearon los mejores resultados reportados, sin división de lotes, para este mismo conjunto de instancias. Los experimentos realizados muestran que el algoritmo propuesto es capaz de generar buenas soluciones en tiempos de cómputo aceptables. Por otro lado, se evidencian los beneficios de la estrategia combinando flexibilidad y división de lotes, introducida en este trabajo.

The exible job shop scheduling problem with lot streaming or lot splitting is a variant of the job shop scheduling problem, in which a job can be divided into sublots of diferent sizes and assigned to diferent machines, in such a way that processing times can be reduced. In this version the objective is to minimize the makespan. Due to the computational complexity, heuristic techniques are usually used to solve this type of problem. In this thesis, we propose an algorithm that combines tabu search strategies, with specific neighborhoods and lot splitting techniques based on the critical path of each generated schedule. To determine the eficiency of the proposed algorithm, the Hurink's instances edata, rdata, vdata were adapted to the lot splitting policy. Since this problem has hardly been reported in the literature, it was not possible to find solutions to compare with, for the aforementioned instances. Therefore, two strategies were used to evaluate the performance of the proposed algorithm. First, the instances were solved as far as possible, with the Gurobi solver. Second, the best reported solutions, without lot streaming, were used as a reference for this set of instances. The experiments showed that the proposed algorithm is able to generate good solutions in an reasonable computing time. Besides, these results provide clear evidence regarding the benefits of strategy proposed in this work, combining exibilty and lot streaming.

Master thesis

Programación de tareas; División de lotes; Heurísticas; Búsqueda Tabú; Gurobi.Flexible job shop; lot streaming; Job shop scheduling problem; Tabu Search, Gurobi). Flexible manufacturing systems--Mathematical models. Administración de la producción -- Modelos matemáticos. Control de la producción. Procesos de manufactura. TS155.6 CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA MATEMÁTICAS INVESTIGACIÓN OPERATIVA PROGRAMACIÓN LINEAL