División de Ciencias Básicas e Ingeniería
Permanent URI for this communityhttps://hdl.handle.net/11191/1
Browse
15 results
Search Results
- Técnicas metaheurísticas de optimización multiobjetivo para resolver el problema del portafolio de inversión(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2017-09) Reyes Hernandez, NaimEl problema del portafolio de inversión consiste en la selección de un conjunto de activos de inversión. Los objetivos en general tienen que ver con la diversificación de la inversión: la minimización del riesgo y la maximización del retorno. El presente documento se organiza como se describe a continuación: el capítulo uno proporciona el marco teórico, relacionando el problema de inversión con el área de optimización multiobjetivo. En un segundo capítulo, se incluye el desarrollo de los métodos para la selección de poblaciones no dominadas, así como la descripción de las características y el modo operativo de las metaheurísticas manejadas. El tercer capítulo presenta la implementación del ajuste de parámetros, se presentan las métricas que se adoptaron. Posterior a ello, la etapa experimental es detallada y la configuración de los parámetros que se determinó. Finalmente, en el cuarto capítulo se presenta la parte experimental del proyecto, es decir, las corridas finales de los algoritmos con los parámetros ajustados, así como su análisis estadístico comparativo. Se incluye también una sección de comparación de los resultados con el estado del arte. Los apéndices están conformados por detalles de la metodología estadística usada, análisis a fondo acerca de algunos conceptos empleados en la investigación, así como información más detallada acerca de la metodología de ajuste de parámetros, así como su análisis estadístico.
- Acoplamientos óptimos de caminos de longitud dos(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2017-08) 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 (a, b, c) is given by min (ab+ bc, bc + ca, ca + ab), 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 noncrossing 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.
- Tres heurísticas basadas en inteligencia de partículas adaptadas al problema de asignación generalizada(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2018) Torres Cockrell, Gilberto SinuheEl presente trabajo desarrolla la adaptación de tres técnicas heurísticas pertenecientes a la rama de las metaheurísticas denominada inteligencia de partículas (IP) para su adaptación al problema de asignación generalizada (PAG). Las heurísticas adaptadas al problema de asignación generalizada son las siguientes: Algoritmo de luciérnagas (AL); Búsqueda Gravitacional (ABG) Método de composición musical (MCM) Se propone una codificación para representar una solución, que permita visualizar de una manera fácil las características de la misma. A diferencia de los algoritmos originales que comienzan con soluciones aleatorias, aquí se plantea una estrategia para generar soluciones de buena calidad aprovechando las características del problema lo cual genera una adaptación en los métodos antes mencionados, ya que se agregan dos parámetros los cuales permitirán generar soluciones por tres estrategias diferentes los cuales serán representados de la siguiente manera: Pg (% soluciones realizadas por un algoritmo glotón) y Pa (% de soluciones realizadas de manera aleatoria ) el restante de la población será generada por una relajación del problema con fijación de variables y generación aleatoria. Para la estrategia AL se realizaron las siguientes adaptaciones: la función objetivo no solo es representada por el valor del individuo, sino que en base a su aptitud a través de las reglas de manejo de restricciones de Coello 2002 [14]. La distancia entre dos individuos no es determinada solamente por la distancia euclidiana, sino que también contempla la distancia de Hamming la cual permite encontrar soluciones de buena calidad; se generaron seis versiones del algoritmo de luciérnagas las cuales se basan en 4 vecindarios diferentes. Para la estrategia ABG se realizaron las siguientes adaptaciones: la masa de inercia es calculada por las reglas de manejo de restricciones de Coello 2002 la cual genera una función de pesos; la función de distancia propuesta contempla al igual que en el AL la distancia euclidiana y la distancia de Hamming, para este algoritmo tanto la mejor como la peor solución el movimiento lo realiza con una búsqueda local; para el resto de las soluciones el movimiento lo realiza con base a las características de la estrategia orinal. Para la estrategia MCM se realizaron las siguientes adaptaciones: la función objetivo utiliza las reglas de manejo de restricciones de Coello 2002 para determinar la aptitud de la solución; la función de distancia propuesta contempla al igual que en las estrategias AL y ABG la distancia euclidiana y la distancia de Hamming. Se tomaron instancias de prueba utilizadas en Chu y Beasley 1997[13], las cuales se encuentran disponibles en Or-Library. Se realizó una calibración de parámetros para las estrategias adaptadas al PAG con la estrategia de búsqueda armónica (BA) para cien mil llamadas a la función objetivo. Se llevó a cabo una serie de experimentos y una comparación con base en algunas de las estrategias del estado del arte del problema. Los resultados obtenidos permiten afirmar que se obtienen soluciones de buena calidad.
- Un nuevo modelo multi-objetivo para el problema de diseño y operación de la cadena de suministro(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2018) Tellez Macias, Angel DavidEn las últimas décadas, el interés de muchas compañías de producción y/o logística se ha enfocado en el estudio de la cadena de suministro, para mejorar su eficiencia operativa y su rentabilidad. En este trabajo, se presenta un nuevo modelo bi-objetivo de programación matemática para un sistema de cadena de suministro multi-producto de 3 escalones (proveedores, fábricas, centros de distribución y clientes). El primer objetivo consiste en minimizar los costos totales, que incluyen costos de inversión (para plantas y centros de distribución) y de operación (producción, almacenamiento y transporte). Por otro lado, se busca simultáneamente minimizar la cantidad total de retrasos en la entrega de los productos a los clientes, con respecto a fechas de entrega establecidas. Para ello, se requiere determinar cuántas fábricas y cuántos centros distribución deben ser abiertos de un conjunto dado; las cantidades de cada producto manufacturadas en cada fábrica abierta; los flujos de los diferentes productos entre capa del sistema global (de proveedores a fábricas, de fábricas a centros de distribución y de centros de distribución a clientes). Las restricciones imponen capacidades limitadas de producción en las fábricas y de almacenamiento en los centros de distribución, mientras que se tiene que cumplir con los pedidos de los clientes. Se adaptaron dos estrategias para resolver diferentes instancias de este modelo, generadas de manera aleatoria y clasificadas por tamaños (chico, mediano y grande). La primera técnica es un algoritmo exacto a través del paquete de programación matemática Gurobi Optimización. Diferentes métodos de escalarización (restricciones-e, funciones de escalarización de Tchebycheff y AASF) fueron probadas para producir mediante varias ejecuciones una aproximación del frente de Pareto. Por otro lado, el algoritmo evolutivo MOEA/D es también adaptado al problema de interés. Los experimentos computacionales sobre instancias chicas demuestran que el paquete Gurobi Optimization determina eficientemente aproximaciones de buena calidad del frente real, mientras que el algoritmo evolutivo funciona bien para identificar ciertas zonas del frente, pero describe mal otras. Sin embargo, para instancias de mayor tamaño, el desempeño de la técnica exacta disminuye mientras que MOEA/D confirma la robustez de su comportamiento.
- Modelo de optimización para subastas de largo plazo de energía eléctrica en México y un modelo con neutralidad tecnológica(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2018-11) Gomez Sanchez, StefaniaEl presente documento muestra inicialmente, en el capítulo 1, una introducción que pretende contextualizar al lector respecto a las Subastas de Largo Plazo implementadas en México a partir de la reforma energética del año 2013, así mismo, se encuentra una sección de antecedentes internacionales respecto a los diferentes diseños de subastas que se han implementado específicamente en América Latina, con el fin de dar a conocer el referente internacional.En el capítulo 2, se encuentra la versión general del modelo matemático de optimización diseñado en México para la subasta de largo plazo empleada por primera vez después de la reforma energética, es decir la subasta SLP-1/2015. Existe una versión del mismo más compleja y la cuál se encuentra descrita en el Manual de Subastas de Largo Plazo [20], pero que fue simplificada en la implementación; en este capítulo, además se demostrará que la complejidad del problema de decisión asociado a la versión general del modelo matemático de optimización descrito, es NP-completo, esto a partir de una simplificación del mismo para llegar al modelo de cobertura de conjuntos de mínimo costo. Más adelante se encontrará la validación de la implementación de los modelos para las Subastas de Largo Plazo SLP-1/2015, SLP-1/2016 y SLP-1/2017, en los capítulos 3, 4 y 5 respectivamente; dicha validación se realizó a partir de los datos disponibles en la sección dedicada a las subastas de largo plazo en la página web del CENACE [3]; en estos capítulos de validación se presentará un análisis detallado del modelo, describiendo los datos de entrada y preprocesamiento tanto de las ofertas de compra como de las ofertas de venta y analizando los resultados obtenidos, se incluyen además algunos hallazgos producto de la validación referentes a la implementación del mismo, así como un análisis de las restricciones en términos de su uso real y finalmente un análisis de sensibilidad sobre los precios ofertados. Posteriormente en el capítulo 6 encontrará una revisión internacional general del manejo de la neutralidad en las subastas de energía eléctrica, específicamente en países de América Latina, así como la propuesta de una extensión hipotética del modelo matemático de optimización, que es intertemporal y que permite mejorar la neutralidad tecnológica de la subasta; por último, se encontrará una simulación en la que a partir de algunos supuestos se pretende evaluar la implementación del modelo propuesto en casos de prueba, tomando como referencia la información disponible para la subastas SLP-1/2016 y SLP-1/2017. Finalmente, en el capítulo 7 encontrará las conclusiones del trabajo realizado, así como algunas prospectivas de trabajo futuro respecto al tema abordado.
- Resolución de problemas de sistemas de producción cíclica aplicando el índice cromático circular(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2016-02) Rodríguez Martínez, José De JesúsEn una gráfica G, el concepto de número cromático circular Xc(G) fue introducido por Vince en 1988. Este invariante es una generalización del número cromático X(G) de una gráfica y provee de una información más refinada de las características de la asignación de colores a los vértices de G. Este trabajo trata sobre la coloración de aristas de una gráfica, mediante el concepto de índice cromático circular X’c(G) como un refinamiento del índice cromático X’(G). Los invariantes Xc(G) y X’c(G) están relacionados, dado que cualquier coloración de las aristas de G es equivalente a colorear los vértices de la gráfica de líneas L(G). En el capítulo 1 se presenta información detallada sobre conceptos fundamentales de este trabajo. El índice cromático circular permite ayudar a resolver un tipo de problemas de asignación que se plantean en sistemas de producción cíclica. Estos problemas se pueden modelar en una gráfica bipartita donde el peso de la arista e = (u; v) corresponde al tiempo de ejecución de la tarea u realizada en la máquina v. En el capítulo 2 se presentan dos conceptos equivalentes: una r-coloración cromática circular y una (k; d)-coloración de las aristas de una gráfica. Ambos conceptos se refieren el índice cromático circular X’c(G). Asimismo, en este capítulo: (i) se comparan las cotas de X’c(G) con respecto a otros parámetros de la gráfica; (ii) se obtiene el X’c(G) para gráficas que tienen una función de peso asociada a sus aristas; y, (iii) finalmente, se enfatiza que es un problema NP-duro el cálculo del valor de X’c(G) para una gráfica dada G. En el capítulo 3 se presenta un resumen de familias de gráficas para las cuales se ha logrado determinar el valor de X’c(G). Este conjunto está constituido por: (i) gráficas de ruedas multieje Wp;q; (ii) gráficas Np; (iii) gráficas snarks, en donde destacan: Petersen, Descartes, Szekeres, Flores, Blanu²a, Blanu²a tipo 1 y Goldberg. Se extienden la últimas dos familias mediante el pegado de ciclos Cs+1 por trayectorias de longitud 1 y 2, dando lugar a nuevas familias, de las cuales se conoce su índice cromático circular. En el capítulo 4 se presenta una aplicación del concepto de coloración circular para modelar un sistema de producción cíclica conocido como open shop scheduling. En este tipo de problemas se tienen n trabajos que deben ser procesados en m máquinas. Cada trabajo consiste de un conjunto de tareas, las cuales tienen un tiempo de procesamiento en cada máquina en la que se puede realizar. El problema se modela mediante una gráfica bipartita (G), donde se tienen dos conjuntos de vértices, el conjunto de trabajos Ji y el conjunto de máquinas Mj . Una arista corresponde a una tarea asociada al trabajo i, que debe ser procesada en la máquina j, la cual se efectúa sin interrupciones. El peso asociado a la arista ij es el tiempo necesario para procesar la tarea ij. El objetivo es encontrar la mínima r-coloración circular por aristas de (G), dado que ésta es equivalente a encontrar la asignación tal que el tiempo necesario para procesar todas las tareas sea el mínimo. Asimismo, en este capítulo se presenta la implementación de tres algoritmos que aproximan el ciclo más pequeño para ejecutar todas las tareas, los cuales de describen a continuación: (i) el primero es una combinación de un problema de programación lineal con la heurística conocida como búsqueda en vecindades variables; y, (ii) los siguientes dos son una combinación de la resolución de un conjunto de problemas de programación lineal con algoritmos genéticos. Estas técnicas son algunas formas de resolver la asignación a sistemas de producción cíclica; las instancias que se utilizan en este trabajo son tomadas de E. Taillard (ver página http://mistic.heig-vd.ch/).
- Problema de ruteo del autobús escolar con recolección mixta(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2015-04) Rojas Silva, EduardoEn este trabajo se presenta una variante del "Problema de ruteo del autobús escolar" (SBRP) clásico, en el cual se trata de minimizar la distancia que se recorre en cada ruta. Concretamente el problema propuesto es una variante del problema de ruteo del autobús escolar para estudiantes con necesidades especiales, en el cual se considera la existencia de dos tipos de de estudiantes, con atributos diferentes al momento de decidir en donde se van a recoger, a diferencia de otras variantes existentes en la literatura, se considera la parte de asignación de los estudiantes como parte del problema ya que se considera que este parámetro influye al momento en que se crean las rutas, aun cuando la complejidad del problema se vea incrementada. La idea principal de este trabajo consiste en explorar tanto los métodos heurísticos como los exactos, para poder obtener una solución a la variante propuesta, ya sea de forma exacta o aproximada. De tal manera que se pueda identificar en qué casos conviene usar uno de estos métodos. El problema se modela como un programa lineal entero mixto, el cual posteriormente se resuelve mediate el software glpk y se encuentran soluciones para instancias pequeñas, que se toman como base para compararlas con las encontradas con el método heurístico utilizado. Para la parte heurística se optó por utilizar una de las técnicas clásicas: Un algoritmo glotón aleatorizado y adaptativo (GRASP, del inglés Greedy Randomized Adaptive Search Procedures), dado que se parte de la formulación matemática previamente obtenida para la parte exacta, fácilmente se puede adaptar para la elaboración del GRASP. La técnica GRASP es una meta-heurística muy rápida que genera soluciones de alta calidad, la cual se divide en dos fases: una de construcción de soluciones, que utiliza para ello un algoritmo glotón aleatorizado una fase de mejora, la cual realiza una búsqueda local. Este proceso se repite varias veces y la mejor solución encontrada se toma como el resultado, lo que al final nos proporciona una solución que, si bien no garantiza que sea la óptima, sí es de buena calidad y se puede obtener en un tiempo mucho menor en comparación con el tiempo que tarda encontrar la solución con un método exacto, cuando éste es capaz de encontrar una. Finalmente nos enfocamos en la versión más simple y general del problema para dar un algoritmo de aproximación, el cual se basa en un algoritmo que originalmente se diseñó para resolver una variante del problema de ruteo vehícular.
- Una técnica metaheurística basada en algoritmos socioculturales para la resolución de problemas de optimización multiobjetivo(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2015-01) Mendez Rosiles, Jose RobertoEste trabajo propone una nueva técnica para el tratamiento de Problemas de Optimización Multiobjetivo, basado en la extensión de un método mono-objetivo basado en conceptos socioculturales, el Método de Composición Musical (MMC). El MMC utiliza una sociedad de agentes, llamados compositores, quienes tienen capacidad creativa propia y mantienen una memoria de su trabajo artístico previo. Además, estos compositores son capaces de intercambiar información dentro de la sociedad. De acuerdo a esta análoga, un enfoque de descomposición es adaptado mediante la implementación de la función de Tchebyche, asignando a cada compositor la resolución de un sub-problema escalar especifico. Los agentes con una parametrización similar del problema multiobjetivo original podrán colaborar en el proceso de búsqueda compartiendo soluciones. Adicionalmente, la técnica de generación de melodías nuevas del MMC original fue modificada, utilizando el operador de mutación presentado en la técnica de Evolución Diferencial. Experimentos computacionales fueron realizados con los bancos de funciones de prueba ZDT y DTLZ. Los resultados obtenidos resaltan el desempeño prometedor del MMC multiobjetivo (MO-MMC), al compararse con técnicas del estado del arte, e.g. dos algoritmos evolutivos (NSGA-II y MOEA/D) y dos técnicas inspiradas en enjambres inteligentes.
- Captura de objetos móviles sobre una recta(Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información., 2014-06) Urban Rivero, Luis EduardoEn este trabajo se comenzó estudiando el problema de captura de objetos sobre una recta de una generalización como una variante del agente viajero con objetivos móviles. A pesar de ser abordado mediante programación lineal, el poder de esta herramienta sólo sirvió en los problemas que implicaban orden, es así como se recurrió a la programación dinámica mediante la discretización del plano, ello bastó para demostrar que dicho mecanismo es suficiente para encontrar una solución óptima en un espacio finito de soluciones. La complejidad del problema no pudo ser disminuida siguiendo este camino. Es aquí donde el problema del reparador juega un papel importarte al ser éste último un caso especial del problema de este trabajo y al estar demostrado que este problema está en el conjunto de problemas NP-Completos. Se tuvo una contribución en lo que respecta a este problema con ventanas de tiempo unitarias, ya que se mejoraron dos algoritmos del estado del avance del conocimiento, en cuanto a su factor de aproximación y se encontró una mejora en cuanto a tiempo de ejecución con respecto a otros 2 algoritmos. En cuanto al trabajo futuro en esta línea de investigación se podrían contemplar las siguientes propuestas: Mejorar el factor de aproximación para Line-TRP con ventanas de tiempo unitarias. Usar el algoritmo de Line-TRP con ventanas unitarias para CTOMSR y sus variantes. Modelar mediante programación entera Line-TRP y CTOMSR. Encontrar la complejidad para Line-TRP con ventanas unitarias.
- 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.