Optimización
Permanent URI for this communityhttps://hdl.handle.net/11191/6748
Browse
34 results
Search Results
- Monitoreo con drones en gráficas con viento dinámico(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2024-01) López Elisea, Jovanni ManuelDada una gráfica completa no dirigida, se desea recorrer un subconjunto de sus aristas usando una flotilla de drones. Los drones tienen baterías limitadas que pueden recargarse al regresar a la base y, en principio, el tiempo para recorrer una arista está en función de la distancia entre sus vértices. Sin embargo, ante la presencia de viento el tiempo de recorrer una arista puede depender del sentido en el que se haga. La dificultad del problema aumenta si además la intensidad del viento puede variar de un instante a otro. En esta tesis se aborda el problema anteriormente descrito para el caso particular en el que los vértices son puntos en el plano, el impacto del viento en los tiempos de recorrido de las aristas está relativamente acotado y el subconjunto de las aristas a recorrer inducen un árbol que abarca todos los vértices excepto la base de los drones. Dado que los drones operan simultáneamente y pueden recorrer distintas partes de la gráfica de manera independiente, se desea minimizar el tiempo que emplea el dron con el recorrido más tardado. Esta tesis presenta un modelo matemático para resolver el problema de manera exacta, así como tres heurísticas diferentes para obtener buenas soluciones factibles. La primera de estas heurísticas transforma una solución sin viento y sin batería en una solución con viento y batería. La segunda heurística es un algoritmo glotón sin comunicación entre los drones y la última heurística también es un algoritmo glotón, pero con comunicación entre los drones. Aunque el problema abordado resulta ser lo suficientemente difícil como para que su resolución exacta sea inviable en la práctica, las heurísticas diseñadas son fáciles de implementar y obtuvieron resultados razonables en un tiempo corto de cómputo.
- Diseño de filtros digitales mediante optimización espiral(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2020-08-16) Mancilla Loeza, Juan FranciscoPara diseñar filtros digitales la aproximación que ha permitido lograr mejores resultados, está basada en técnicas de optimización multivariable, en las que se determinan los coeficientes del filtro digital, buscando minimizar la diferencia de una función de error que se comete al aproximar una respuesta calculada, respecto a una respuesta deseada de acuerdo con las especificaciones de diseño previamente establecidas. En este proyecto se utilizó un modelo de función objetivo que minimiza el error combinado en la aproximación de las respuestas requeridas en amplitud y en el grupo de atraso. Mediante optimización multivariable, se determinó llevar a cabo el diseño de filtros RII, dada la ventaja que presentan al ser más reducidos en el número de coeficientes respecto a los filtros RFI y buscando mediante esta aproximación, reducir la complejidad que reviste el diseño de este tipo de filtros y asegurar que funcionan de manera estable. Además, se eligió utilizar una técnica de las denominadas metaheurísticas, las cuales permiten subsanar los problemas que afectan a los algoritmos de optimización clásica. La técnica elegida fue la denominada Optimización Espiral (ESPO), algoritmo de tipo poblacional, que soluciona el problema de minimización del error mediante una búsqueda de soluciones que sigue un patrón en espiral. Las pruebas y experimentos realizados en este trabajo, tuvieron como objetivo el determinar en primera instancia, los parámetros adecuados para la operación de los algoritmos metaheurísticos y una vez lograda esta meta, se procedió a realizar experimentos de diseño de filtros RII mediante estas técnicas. Concluidos los experimentos de diseño de los filtros RII, se procedió con el análisis y documentación de resultados, los cuales permitieron constatar que la técnica ESPM, además de mejorar el algoritmo original ESPO, le confiere un desempeño similar a las metaheurísticas PSO y ED. Aunado a lo previo, el filtro diseñado mediante ESPM reportó mejores resultados en el filtrado de la señal sintética, comparados con aquellos logrados mediante la aplicación del similar construido en MATLAB.
- Programación de trabajos en el área de capitoneado en una empresa de colchones(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2021-05-11) Arzate Flores, DanielEn este trabajo, se presenta una variación de problema de flujo en taller, el cual se presenta en una fábrica de colchones, específicamente en un área conocida como capitoneado. El principal objetivo es programar los diferentes tipos de trabajos a las diferentes máquinas de acuerdo a las características inherentes del producto y su variación en los tiempos de producción, para así satisfacer la demanda diaria que tiene la empresa. Para darle solución a este problema se comienza diseñando un modelo matemático que satisfaga las diferentes restricciones del sistema de producción de la empresa y sus necesidades. Una vez diseñado el modelo matemático, se procede a realizar su implementación mediante el software de gurobi, el cual nos da una solución exacta del problema (BB). Además, se implementan 3 heurísticas, las cuales son el Algoritmo Genético (GA), Algoritmo cultural (CA) y Recocido Simulado (SA). Para medir la eficiencia de las técnicas utilizadas (BB-GA-CA-SA), se comparan con 10 instancias. Cada instancia representa la programación de un día de trabajo en la empresa de colchones que el supervisor asignó de acuerdo a su conocimiento y estrategias internas. De igual manera, una vez obtenidas las soluciones en GA-CA-SA se procedido a comparar con la solución exacta para medir qué tan buenas son y el tiempo utilizado. Este trabajo se divide en 5 capítulos, los cuales son: Introducción, conceptos básicos, descripción del problema, resultados, y conclusiones y trabajo futuro. Por último, se encuentran la bibliografía con la cual este trabajo se apoyó.
- Planeación de evaluaciones de recuperación en la Universidad Autónoma Metropolitana(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2020-06-30) Romero Nájera, Diana KarinaEn la División de Ciencias Básicas e Ingeniería de la Universidad Autónoma Metropolitana, Unidad Azcapotzalco se calendarizan dos tipos de evaluaciones: evaluaciones globales y evaluaciones de recuperación. Esta tesis estará enfocada en el problema de planeación de evaluaciones de recuperación, el cual es un problema que combina aspectos de los problemas de planeación de cursos y de evaluaciones, pues las evaluaciones de recuperación deben planearse antes de la inscripción de los alumnos, pero pueden compartir salón. En la práctica, la planeación de evaluaciones de recuperación debe tomar en cuenta muchos aspectos distintos y es casi un hecho que no puedan encontrarse planeaciones perfectas. Por ejemplo, minimizar el número de salones y el número de horarios por día aumenta la probabilidad de generar empalmes entre evaluaciones que el alumno quiera inscribir al mismo tiempo, mientras que minimizar el número de días de evaluación posiblemente requiera usar más horarios por día. El problema puede verse como un problema multi-objetivo, pero en esta tesis se propone usar métodos de programación matemática para encontrar mejores planeaciones. En este caso, se propone usar la técnica usual de convertir un problema multiobjetivo en un problema mono-objetivo optimizando una suma ponderada de los objetivos múltiples.
- Preservación de la diversidad y manejo de los puntos de referencia en algoritmos evolutivos multiobjetivo(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2022-02-25) Rodríguez Sánchez, AlbertoEl éxito de los algoritmos evolutivos multiobjetivo basados en descomposición (MOEA/D) ha generado un gran interés en los MOEA que utilizan un conjunto de vectores de peso para promover la diversidad dentro de las soluciones no dominadas. Sin embargo, la calidad del conjunto de soluciones obtenido depende en gran medida de la consistencia entre la forma del frente de Pareto del problema y la distribución de peso especificada. El objetivo de este trabajo es doble. En primer lugar, el estudio se centra en seis técnicas clásicas para la generación de vectores de peso, ya sea basadas en el diseño de mezclas o en secuencias de baja discrepancia. El rendimiento de estos métodos, implementados en MOEA/DconPBI, se evaluó y analizo en varias funciones de prueba escalables de la literatura. Además, se introduce un enfoque novedoso para actualizar los vectores de peso durante el proceso evolutivo, que utiliza información de los individuos no dominados de la población actual. Estas soluciones se utilizan para volver a calcular su vector de peso correspondiente y marcarlas como puntos prohibidos o tabú. Luego, se crean nuevos vectores de peso lejos de estos puntos tabú a través de un criterio de repulsión basado en la distancia de Mahalanobis. Algunos experimentos preliminares indican que esta estrategia de adaptación dinámica del vector de peso proporciona beneficios significativos en comparación con el diseño estático Simplex Lattice ampliamente utilizado pero que ha mostrado problemas en altas dimensiones.
- Cálculo de matrices intercaladas óptimas(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2022-09-07) González Yáñez, Rubén AlejandroEl cálculo de matrices intercaladas exige hacer uso de estrategias mucho más eficientes que la búsqueda exhaustiva a ciegas. Para intentar encontrar una matriz intercalada de tamaño r x s con a lo más n colores, una búsqueda ciega requeriría explorar exactamente nrs posibilidades. El primer caso abierto era de tamaño 9 x 17 con 24 colores, por lo que se tendrían 24⁹ˣ¹⁷ = 1;487031 x 10²¹¹ posibilidades y se requerirían aproximadamente 4X10²⁰⁹ años de cálculo en una computadora moderna. Aunque resulta difícil determinar si la complejidad de un algoritmo de búsqueda con retroceso es asintóticamente mejor, sí es posible diseñar algoritmos que examinen una cantidad de matrices varios órdenes de magnitud por debajo del peor caso. Como primera estrategia de solución se diseñaron e implementaron dos modelos de programación entera a resolverse con Gurobi. Durante los experimentos, los modelos se probaron con un caso de tamaño 7 x 9, que es más pequeño que el primer caso abierto, cabe mencionar que en este caso y para el que ya se sabe que conjetura de Yuzvinsky se cumple; se dejaron correr los modelos por más de dos horas cada uno y no pudieron resolverlo, por lo que se concluyó en no continuar con esta estrategia para resolver los casos abiertos. Como una siguiente estrategia se diseñó un algoritmo de búsqueda con retroceso, pero como el espacio de búsqueda es muy grande, fue necesario tratar de hacer las asignaciones de color inteligentemente. Para ello se utilizó un algoritmo eficiente para conocer qué colores se podrían asignar en una celda sin afectar las asignaciones previas. Aunque con este algoritmo se resolvió al menos el primer caso abierto de tamaño 9 x 17, fue necesario utilizar otra estrategia para reducir el tiempo de búsqueda para matrices más grandes. Como una siguiente estrategia para acelerar el tiempo de búsqueda, se diseñó un algoritmo híbrido que combina búsqueda en amplitud y búsqueda en profundidad para poder hacer uso de la concurrencia del hardware. Esta estrategia logró acelerar el algoritmo y se resolvieron siete casos abiertos, que son 9 x 17, 9 x 18, 10 x 17, 9 x 19, 11 x 17, 9 x 20 y 9 x 21. Haciendo la observación de que un color con frecuencia máxima t puede aparecer en diagonal principal y que esto forza una matriz simétrica, se pueden precalcular todas las matrices simétricas de tamaño t x t para reutilizarlas al construir matrices más grandes. Esto reduce el tiempo de búsqueda porque solo se va llenando lo que falta. Añadiendo esta estrategia al algoritmo híbrido se logró reducir el tiempo en los primeros siete casos resueltos con el algoritmo híbrido que no usa esta estrategia y además se lograron resolver los casos 9 x 22, 10 x 19, 11 x 18, 10 x 21, 13 x 18 y 9 x 23, finalizando con trece casos resueltos y quedando seis casos abiertos. Se puede concluir que utilizar concurrencia en el algoritmo de búsqueda es una excelente opción para poder mejorar el rendimiento, pero la reutilización de trabajo previo también puede acelerar considerablemente la búsqueda de las matrices. Con estas ideas se podría diseñar alguna nueva estrategia que sea capaz de revisar los casos faltantes.
- Transformaciones ∆ − Y en redes(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2022) Frausto Tamayo, Diego LeonardoLa Combinatoria se compone de varias ramas que involucran el estudio de procesos finitos y estructuras discretas. Las gráficas son estructuras que constituyen el concepto central del estudio de una rama muy robusta de la Combinatoria. Así que resulta de gran interés investigar sus propiedades, invariantes y clasificaciones en familias que comparten propiedades. Un conjunto de resultados en teoría de graficas muestran que una clase de graficas pueden ser reducidas a una forma canónica mediante la aplicación de ciertas operaciones. Se puede demostrar, que la aplicación inversa de esas mismas operaciones puede generar todas las gráficas en una clase. Uno de los conjuntos más importantes de reducciones usadas en la teoría de graficas son las reducciones serie-paralelo, al aplicar una reducción de este tipo a una gráfica, se disminuye el número de sus aristas. Las operaciones que no alteran el número de aristas de la gráfica se llaman transformaciones, en particular y como centro de análisis en este trabajo, se estudian las transformaciones ∆ − Y.
- Algoritmos metaheurísticos aplicados a una transformada fractal en imágenes(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2022-03-05) Avila Campos, Stephanie PamelaSe describe una investigación sobre el uso de algoritmos metaheurísticos para generar imágenes fractales a partir de la aplicación de una transformada fractal. La codificación fractal de imágenes es una técnica de compresión con pérdidas en donde se representa una imagen digital como un conjunto de códigos fractales, con la ventaja de reducir el espacio que éstas ocupan. Se explican que los algoritmos metaheurísticos son técnicas de optimización que se basan en la exploración sistemática de soluciones y en la evaluación de su calidad, para encontrar la mejor solución posible en un espacio de búsqueda. Se aplican algoritmos metaheurísticos para generar imágenes fractales a partir de una transformada fractal. El uso de algoritmos metaheurísticos en la generación de imágenes fractales puede mejorar la calidad y complejidad de las mismas, en comparación con los métodos tradicionales de transformada fractal. Además, los algoritmos metaheurísticos pueden ser útiles para optimizar la exploración y la convergencia en la búsqueda de soluciones en un espacio de búsqueda complejo.
- Retiro de una bomba mediante la colaboración de robots(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2020-08) Pérez Pérez, CristianEl contexto de nuestro problema es el siguiente: suponga que hay una bomba que se encuentra en una posición conocida y se requiere alejarla de dicha posición lo más posible, sin tomar en cuenta cuándo podría explotar. Para ello se cuenta con una cantidad fija de robots que tienen la capacidad de cargar la bomba, actúan uno a la vez, y disponen de una cantidad limitada de energía para desplazarse. Se considera un espacio de trabajo en dos dimensiones sobre la malla entera, donde cuesta una unidad de energía desplazarse entre vértices adyacentes. A este problema le llamamos "Retiro de la Bomba en la Malla (RBM)". Dadas las características del problema se sospecha que es NP-Duro, aunque hasta donde sabemos esto no se ha demostrado. El problema RBM se atacó con 5 técnicas diferentes: 1) modelo de programación entera y el software solucionador Gurobi; 2) una heurística ad hoc glotona; 3) una heurística ad hoc basada en grupos: 4) metaheurístico ascenso a la colina; y 5) metaheurístico recocido simulado. El desempeño de las técnicas se probó al evaluar un conjunto de instancias de distintos tamaños, las cuales diseñamos acorde a las características de RBM. ya que en la literatura no se encontró ninguna. El modelo de programación entera muestra un aumento excesivamente alto en los tiempos de ejecución conforme crece el tamaño de las instancias. Se resolvieron instancias de manera exacta de a lo más 14 robots (instancias de tamaño pequeño) en un tiempo límite de 8 horas. La heurística de grupos, ascenso a la colina y recocido simulado son técnicas donde se puede aplicar el método multiarranque, por lo que inicialmente se compararon con el mismo número de corridas. Los resultados obtenidos muestran que recocido simulado obtiene las mejores so- luciones (en las instancias pequeñas casi siempre llegó al valor óptimo), seguido por ascenso a la colina y las heurísticas glotona y de grupos, las cuales muestran soluciones similares, sin embargo, los tiempos de ejecución se mantienen el mismo orden, siendo el recocido simulado la técnica con los tiempos más altos (solo superados por los del modelo de programación entera) y la heurística glotona la técnica con los tiempos más bajos. Finalmente, se compara la heurística de grupos con el recocido simulado. Debido a que la heurística de grupos muestra una alta variación en sus respuestas y tiene tiempos de ejecución muy bajos, se realiza un número mayor de corridas para esta técnica. Los resultados muestran que al ejecutar la heurística de grupos cientos de veces, se puede obtener soluciones tan buenas o incluso mejores a las del recocido simulado, en tiempos de ejecución mucho menores.
- Análisis envolvente de datos para evaluar eficiencia en universidades mexicanas(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2020-03) Noguez Moreno, Christian LizbethAl evaluar una entidad u organización, a menudo se requiere saber qué tan bien funciona. Una entidad requiere entradas para producir salidas, por lo tanto, si se contara con una función que asigne a cada salida el mínimo costo necesario para producirla, sería posible determinar la eficiencia de la entidad. A estas entidades se les conoce también como unidades de decisión (DMU, por sus siglas en ingles). Una técnica empleada para medir la eficiencia de unidades de decisión con múltiples entradas y salidas es el Análisis Envolvente de Datos (DEA). DEA genera una frontera de eficiencia que representa el mínimo número de entradas que requiere una DMU para producir cierta cantidad de salidas. Aquellas DMU que se encuentren sobre esta frontera son consideradas eficientes. En este trabajo se utilizó DEA para medir la eficiencia de 60 universidades en México. Debido a las limitaciones inherentes a la cantidad máxima de entradas y salidas, que dependen del número de unidades de decisión utilizadas, es necesario elegir una cantidad específica de rubros como entradas y salidas. Para el manejo de datos y definir entradas y salidas se utilizaron dos enfoques: revisión bibliográfica y análisis estadístico, específicamente utilizando componentes principales.