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.

Algoritmos construtivos para treino de redes neuronais b-spline

Dissertação de mest. em Engenharia de Sistemas e Computação - Área de Sistemas de Controlo, Faculdade de Ciências e Tecnologia, Univ.do Algarve, 2001

Estudo e implementação de algoritmos inteligentes para detecção e classificação de falhas na medição de gás natural

This master dissertation presents the study and implementation of inteligent algorithms to monitor the measurement of sensors involved in natural gas custody transfer processes. To create these algoritmhs Artificial Neural Networks are investigated because they have some particular properties, such as: learning, adaptation, prediction. A neural predictor is developed to reproduce the sensor output dynamic behavior, in such a way that its output is compared to the real sensor output. A recurrent neural network is used for this purpose, because of its ability to deal with dynamic information. The real sensor output and the estimated predictor output work as the basis for the creation of possible sensor fault detection and diagnosis strategies. Two competitive neural network architectures are investigated and their capabilities are used to classify different kinds of faults. The prediction algorithm and the fault detection classification strategies, as well as the obtained results, are presented

Algoritmos de reconstrucción de superficies 3D para modelaje antropométrico

Los protocolos de medición antropométrica se caracterizan por la profusión de medidas discretas o localizadas, en un intento para caracterizar completamente la forma corporal del sujeto -- Dichos protocolos se utilizan intensivamente en campos como medicina deportiva, forense y/o reconstructiva, diseño de prótesis, ergonomía, en la confección de prendas, accesorios, etc -- Con el avance de algoritmos de recuperación de formas a partir de muestreos (digitalizaciones) la caracterización antropométrica se ha alterado significativamente -- El articulo presente muestra el proceso de caracterización digital de forma corpórea, incluyendo los protocolos de medición sobre el sujeto, el ambiente computacional - DigitLAB- (desarrollado en el CII-CAD-CAM-CG de la Universidad EAFIT) para recuperación de superficies, hasta los modelos geométricos finales -- Se presentan comparaciones de los resultados obtenidos con DigitLAB y con paquetes comerciales de recuperación de forma 3D -- Los resultados de DigitLAB resultan superiores, debido principalmente al hecho de que este toma ventaja de los patrones de las digitalizaciones (planares de contacto, por rejilla de pixels - range images -, etc.) y provee módulos de tratamiento geométrico - estadístico de los datos para poder aplicar efectivamente los algoritmos de recuperación de forma -- Se presenta un caso de estudio dirigido a la industria de la confección, y otros efectuados sobre conjuntos de prueba comunes en el ámbito científico para la homologación de algoritmos

Redes neuronales artificiales aplicadas al análisis de datos en ingeniería ambiental e impacto ambiental

Resumen: Se realiza una revisión sobre los antecedentes de las Redes Neuronales Artificiales (RNA) como método de análisis de bases de datos medioambientales, aplicado en las diversas áreas de la Ingeniería Ambiental en general y de Impacto Ambiental en particular. Se describe como ejemplo, la aplicación de RNA en los algoritmos de inversión de datos obtenidos por sensado remoto satelital, para la medición de variables geofísicas

New signal processing algorithms for automated external defibrillators

[ES]La fibrilación ventricular (VF) es el primer ritmo registrado en el 40\,\% de las muertes súbitas por paro cardiorrespiratorio extrahospitalario (PCRE). El único tratamiento eficaz para la FV es la desfibrilación mediante una descarga eléctrica. Fuera del hospital, la descarga se administra mediante un desfibrilador externo automático (DEA), que previamente analiza el electrocardiograma (ECG) del paciente y comprueba si presenta un ritmo desfibrilable. La supervivencia en un caso de PCRE depende fundamentalmente de dos factores: la desfibrilación temprana y la resucitación cardiopulmonar (RCP) temprana, que prolonga la FV y por lo tanto la oportunidad de desfibrilación. Para un correcto análisis del ritmo cardiaco es necesario interrumpir la RCP, ya que, debido a las compresiones torácicas, la RCP introduce artefactos en el ECG. Desafortunadamente, la interrupción de la RCP afecta negativamente al éxito en la desfibrilación. En 2003 se aprobó el uso del DEA en pacientes entre 1 y 8 años. Los DEA, que originalmente se diseñaron para pacientes adultos, deben discriminar de forma precisa las arritmias pediátricas para que su uso en niños sea seguro. Varios DEAs se han adaptado para uso pediátrico, bien demostrando la precisión de los algoritmos para adultos con arritmias pediátricas, o bien mediante algoritmos específicos para arritmias pediátricas. Esta tesis presenta un nuevo algoritmo DEA diseñado conjuntamente para pacientes adultos y pediátricos. El algoritmo se ha probado exhaustivamente en bases de datos acordes a los requisitos de la American Heart Association (AHA), y en registros de resucitación con y sin artefacto RCP. El trabajo comenzó con una larga fase experimental en la que se recopilaron y clasificaron retrospectivamente un total de 1090 ritmos pediátricos. Además, se revisó una base de arritmias de adultos y se añadieron 928 nuevos ritmos de adultos. La base de datos final contiene 2782 registros, 1270 se usaron para diseñar el algoritmo y 1512 para validarlo. A continuación, se diseñó un nuevo algoritmo DEA compuesto de cuatro subalgoritmos. Estos subalgoritmos están basados en un conjunto de nuevos parámetros para la detección de arritmias, calculados en diversos dominios de la señal, como el tiempo, la frecuencia, la pendiente o la función de autocorrelación. El algoritmo cumple las exigencias de la AHA para la detección de ritmos desfibrilables y no-desfibrilables tanto en pacientes adultos como en pediátricos. El trabajo concluyó con el análisis del comportamiento del algoritmo con episodios reales de resucitación. En los ritmos que no contenían artefacto RCP se cumplieron las exigencias de la AHA. Posteriormente, se estudió la precisión del algoritmo durante las compresiones torácicas, antes y después de filtrar el artefacto RCP. Para suprimir el artefacto se utilizó un nuevo método desarrollado a lo largo de la tesis. Los ritmos desfibrilables se detectaron de forma precisa tras el filtrado, los no-desfibrilables sin embargo no.

Un método para el taladro de aluminio que facilita la unión por remaches de los componentes aeronáuticos

189 p. : il. col.