Otimização de controle de tráfego em grupo de elevadores com algoritmos bioinspirados

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Mecânica, 2015.

Modelo origen destino para estimar el flujo de tráfico usando algoritmos genéticos

En este trabajo se ha desarrollado un nuevo método basado en Inteligencia Artificial para resolver un problema del matriz origen-destino (O-D) aplicado al caso de una red de tráfico vehicular en la ciudad de Ambato. El método implementado, basado en algoritmos genéticos (AG), resuelve el problema de minimización asociado al problema de matriz O-D. Para validar la técnica, se ha utilizado una red vial correspondiente a la zona del Mercado Modelo en la ciudad de Ambato, que es una zona de alta congestión vehicular.

Algoritmos de otimização e o problema inverso aplicados à identificação de danos estruturais com o uso do MEF

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Civil e Ambiental, 2015.

Las matemáticas universitarias y las tecnologías computacionales

Cuando se habla de “modernización en la enseñanza de las matemáticas” se alude, muy frecuentemente, a la incorporación de tecnologías computacionales y de comunicaciones al proceso de enseñanza-aprendizaje. Esto no significa desconocer elementos de modernidad en los enfoques que privilegian mayor autonomía y mayor participación del aprendiz en el proceso de construcción de su conocimiento, o en los enfoques que buscan trascender el estrecho marco de la aplicación ilustrativa de conceptos para enfatizar su aplicación a situaciones prácticas; significa aceptar que el rápido crecimiento de la importancia de las calculadoras, los computadores y la multimedia es el factor de más trascendencia para crear cambios en los diferentes aspectos de la educación matemática (Comu y Ralston, 1992). Significa, también, reconocer que aun la viabilidad y efectos de los enfoques anteriormente mencionados se favorecen e intensifican mediante el uso de estas tecnologías.

Ordenação por translocação de genomas sem sinal utilizando algoritmos genéticos

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016.

Problema del agente viajero selectivo con restricciones adicionales

En esta tesis se introduce una variante del Problema del Agente Viajero Selectivo, también conocido en la literatura como Orienteering Problem (OP). En el OP se tiene un conjunto de clientes potenciales, a cada uno de los cuales se le asocia una puntuación o beneficio que recibe el agente al visitarlo, el objetivo es el de diseñar una ruta que comience y termine en el depósito y que maximice el puntaje colectado, tomando en cuenta que existe un límite máximo en la duración de la ruta. En este trabajo se consideran restricciones de conflictos entre clientes, es decir, si dos de ellos tienen conflicto, no pueden ser incluidos ambos en la ruta; por otra parte, existe un subconjunto de clientes que deben ser visitados de manera obligatoria. Se proponen dos modelos matemáticos del problema, cuya diferencia principal es la manera en que aborda la eliminación de ciclos. El primer modelo usa restricciones de tipo secuencial inspiradas en las propuestas por Miller et al. (1960) y el segundo utiliza restricciones basadas en flujo de múltiples productos y se basan en las restricciones propuestas por Wong (1980) y Claus (1984). Asimismo, se proponen dos algoritmos para la solución del problema planteado, el primero es de tipo heurístico y está basado en un esquema GRASP (Greedy Randomized Adaptive Search Procedure) reactivo, cuya fase de mejora es un método tipo VNS (Variable Neighborhood Search) general, el segundo es una estrategia de descomposición basada en generación de columnas. El desempeño de los algoritmos propuestos es evaluado a través de experimentos computacionales sobre un gran conjunto de instancias y los resultados obtenidos son comparados contra las soluciones ´optimas obtenidas al resolver los modelos matemáticos haciendo uso del solver Cplex 12.6.

Generación Automática de Contenido para Juegos de Estrategia en Tiempo Real

El destacado volumen de negocio a nivel mundial ha convertido a los videojuegos en el principal protagonista dentro de la industria del entretenimiento. Este hecho no ha pasado desapercibido para la comunidad científica, que se ha visto surtida de nuevos retos y desafíos que abordar. La generación automática de contenido son un conjunto de técnicas que permiten generar de forma algorítmica contenido específico para videojuegos. Estas técnicas reducen costes de producción y diseño, sirven como fuente de creatividad e inspiración para el diseñador, ahorran recursos computacionales a la hora de ejecutar el juego y permiten adaptar el juego al jugador para que la experiencia de juego sea única y personalizada. Generalmente el criterio usado para la generación es el de la jugabilidad, es decir, que el contenido cumpla con las reglas del juego. Esta tesis define una metodología para la generación automática de contenido para juegos de estrategia en tiempo real en base a unos criterios que van más allá de que el contenido sea válido. Esta metodología propone el uso de algoritmos evolutivos para la generación del contenido siguiendo un esquema de generación y prueba. La primera característica exigible al contenido generado que se ha estudiado ha sido el equilibrio entre jugadores. También se ha descrito un método de generación enfocado en esta característica que es capaz de crear mapas que no proporcionan ventaja alguna a los jugadores, independientemente de su habilidad o estrategia elegida. Otra característica deseable que evita que las partidas se conviertan en algo aburrido y monótono y que también ha sido estudiada es el dinamismo. A la hora de buscar el dinamismo se ha optado por dos enfoques distintos, uno basado en los recursos que mantienen los jugadores a lo largo de la partida y otro basado en las confrontaciones entre ellos, que se centra en las batallas y el nivel de naves perdidas. Se han analizado ambas características en conjunto, detectándose que la definición de dinamismo que se ha usado como objetivo de la optimización incluye implícitamente una componente de equilibrio, concluyéndose por tanto que el equilibrio es compatible con un nivel medio de dinamismo. Además, se ha estudiado un enfoque multi-objetivo del problema que ha sacado a la luz otras relaciones entre equilibrio y dinamismo y mediante el cual se ha establecido que conforme aumenta el equilibrio se produce un leve descenso en el dinamismo, acabando con un descenso brusco en la frontera superior del equilibrio. Al igual que con el equilibrio y el dinamismo, se ha abordado el problema de mejorar la estética de los mapas siguiendo dos enfoques, uno geométrico que se basan en la geométrica espacial del mapa (coordinadas y distancias), y otro topológico que se basan en propiedades cualitativas de los mapas que no se ven afectadas por transformaciones geométricas simples y que han sido obtenidas a partir del grafo de esferas de influencia. Los resultados indican que existe una relación lineal entre la diferencia con los mapas estéticos y con los que no lo son, lo que da una idea de la densidad del espacio de búsqueda. Con respecto a las medidas utilizadas, se observa que hay algunas de ellas que tienen una mayor influencia sobre el valor de aptitud que el resto de variables. Por último, tras realizar un análisis cruzado de las soluciones obtenidas con ambos enfoques se observa que ambos enfoques son capaces de generar mapas adecuados, aunque hay que destacar que existe una mayor diversidad en las soluciones del enfoque geométrico que en las del topológico, además de que las soluciones geométricas obtenidas quedan más cerca del conjunto de mapas estéticos que las propias soluciones topológicas según la medida de aptitud de éstas últimas.

Desarrollo de un agente 3D con uso de algoritmos evolutivos y minería de datos

En este Trabajo Fin de Grado se lleva a cabo la implementación de un mundo 3D a través del uso del entorno Unity en el se cual realizará el desarrollo de un agente 3D el cual interactúe con el entorno que le rodea. Para ello haremos uso de algoritmos relacionado con la inteligencia artificial así como aplicación de algoritmos relacionados con la minería de datos tales como redes neuronales basando su aprendizaje en algoritmos evolutivos o arboles de decisión, respectivamente. Así pues, el objetivo de este proyecto es la creación de un agente 3D el cual sea capaz de adaptarse al entorno que le rodea, siendo hostiles algunos de estos entornos. Habrá principalmente 2 entornos los cuales serán una ciudad donde el agente deberá recoger clientes en su rol de taxista y soltarlas reconociendo a través de una serie de variables que personas son de fiar y cuales no. El segundo entorno es una cancha de baloncesto donde el agente deberá aprender a lanzar a canasta y reconocer con qué estados meteorológicos es viable jugar.

Problemas de corte : métodos exactos y aproximados para formulaciones mono y multi-objetivo

Los problemas de corte y empaquetado son una familia de problemas de optimización combinatoria que han sido ampliamente estudiados en numerosas áreas de la industria y la investigación, debido a su relevancia en una enorme variedad de aplicaciones reales. Son problemas que surgen en muchas industrias de producción donde se debe realizar la subdivisión de un material o espacio disponible en partes más pequeñas. Existe una gran variedad de métodos para resolver este tipo de problemas de optimización. A la hora de proponer un método de resolución para un problema de optimización, es recomendable tener en cuenta el enfoque y las necesidades que se tienen en relación al problema y su solución. Las aproximaciones exactas encuentran la solución óptima, pero sólo es viable aplicarlas a instancias del problema muy pequeñas. Las heurísticas manejan conocimiento específico del problema para obtener soluciones de alta calidad sin necesitar un excesivo esfuerzo computacional. Por otra parte, las metaheurísticas van un paso más allá, ya que son capaces de resolver una clase muy general de problemas computacionales. Finalmente, las hiperheurísticas tratan de automatizar, normalmente incorporando técnicas de aprendizaje, el proceso de selección, combinación, generación o adaptación de heurísticas más simples para resolver eficientemente problemas de optimización. Para obtener lo mejor de estos métodos se requiere conocer, además del tipo de optimización (mono o multi-objetivo) y el tamaño del problema, los medios computacionales de los que se dispone, puesto que el uso de máquinas e implementaciones paralelas puede reducir considerablemente los tiempos para obtener una solución. En las aplicaciones reales de los problemas de corte y empaquetado en la industria, la diferencia entre usar una solución obtenida rápidamente y usar propuestas más sofisticadas para encontrar la solución óptima puede determinar la supervivencia de la empresa. Sin embargo, el desarrollo de propuestas más sofisticadas y efectivas normalmente involucra un gran esfuerzo computacional, que en las aplicaciones reales puede provocar una reducción de la velocidad del proceso de producción. Por lo tanto, el diseño de propuestas efectivas y, al mismo tiempo, eficientes es fundamental. Por esta razón, el principal objetivo de este trabajo consiste en el diseño e implementación de métodos efectivos y eficientes para resolver distintos problemas de corte y empaquetado. Además, si estos métodos se definen como esquemas lo más generales posible, se podrán aplicar a diferentes problemas de corte y empaquetado sin realizar demasiados cambios para adaptarlos a cada uno. Así, teniendo en cuenta el amplio rango de metodologías de resolución de problemas de optimización y las técnicas disponibles para incrementar su eficiencia, se han diseñado e implementado diversos métodos para resolver varios problemas de corte y empaquetado, tratando de mejorar las propuestas existentes en la literatura. Los problemas que se han abordado han sido: el Two-Dimensional Cutting Stock Problem, el Two-Dimensional Strip Packing Problem, y el Container Loading Problem. Para cada uno de estos problemas se ha realizado una amplia y minuciosa revisión bibliográfica, y se ha obtenido la solución de las distintas variantes escogidas aplicando diferentes métodos de resolución: métodos exactos mono-objetivo y paralelizaciones de los mismos, y métodos aproximados multi-objetivo y paralelizaciones de los mismos. Los métodos exactos mono-objetivo aplicados se han basado en técnicas de búsqueda en árbol. Por otra parte, como métodos aproximados multi-objetivo se han seleccionado unas metaheurísticas multi-objetivo, los MOEAs. Además, para la representación de los individuos utilizados por estos métodos se han empleado codificaciones directas mediante una notación postfija, y codificaciones que usan heurísticas de colocación e hiperheurísticas. Algunas de estas metodologías se han mejorado utilizando esquemas paralelos haciendo uso de las herramientas de programación OpenMP y MPI.

Estudio y aplicación de metaheurísticas y comparación con métodos exhaustivos

Cuando nos enfrentamos a problemas reales haciendo uso de recursos computacionales, hemos de tener en cuenta que el número de posibles soluciones candidatas a tener en cuenta puede llegar a ser tan inmenso que abordarlas mediante técnicas algorítmicas clásicas, en la mayoría de los casos, pueden llegar a convertirse en un problema en sí mismo debido al gran coste en recursos que pueden llegar a generar. En este contexto, aspectos como el tiempo utilizado en la búsqueda de una solución mediante algoritmos de búsqueda exhaustiva tales como fuerza bruta, vuelta atrás, ramificación y poda, etc., puede llegar a ser prohibitivo en la práctica. Ante este problema que se nos plantea, podemos hacer un estudio sobre otros métodos, tales como los metaheurísticos, que, aunque no siempre aseguran la optimalidad de las soluciones producidas; tienen un tiempo de ejecución mucho menor que los métodos exhaustivos. En el presente trabajo hemos seleccionado dos problemas NP-completos de entre los más famosos de la literatura y hemos realizado un estudio de ambos. Concretamente, los problemas seleccionados han sido el TSP (Traveling Salesman Problem) y el problema de la Mochila 0-1. Por otro lado, hemos llevado a cabo un estudio sobre distintas metaheurísticas para poder resolver los problemas mencionados. Entre estas metaheurísticas, hemos seleccionado cuatro: metaheurísticas evolutivas, metaheurísticas inspiradas en colonias de hormigas, metaheurísticas simulated annealing (enfriamiento simulado) y metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure). Después de esto, cada problema ha sido resuelto aplicando tanto algoritmos de búsqueda exhaustiva como metaheurísticas. Una vez adaptados los algoritmos a la resolución de los problemas concretos, hemos realizado un estudio experimental, donde se realizaron comparativas de rendimiento. Finalmente, todo este trabajo ha sido plasmado en el desarrollo de una aplicación software, la cual consta de dos partes: una que contiene la implementación los algoritmos adaptados para la resolución de los problemas y que son ofrecidos a modo de servicios web y otra parte donde se ha implementado un cliente web que puede consumir estos servicios y realizar una presentación más vistosa de la ejecución de los algoritmos y los resultados obtenidos. Esta arquitectura podrá servir como base para futuras ampliaciones de este estudio.

O problema da supressão na protecção de informação confidencial: formalizações e algoritmos.

Doutoramento em Matemática Aplicada à Economia e à Gestão.