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.

La insaciable búsqueda de El Dorado: procesos hegemónicos y dispositivos de dominación en un pueblo sikuani de la orinoquía colombiana

Esta tesis examina desde una perspectiva histórica de larga duración cómo se han configurado diversos escenarios de disputa política en la Orinoquía colombiana, a través del colonialismo interno y la configuración de la región como margen del Estado, teniendo en cuenta la multiplicidad de actores dominantes que han tenido presencia en la región, y las relaciones de dominación y poder que han entablado con un el pueblo sikuani como sujeto subalterno. Se presenta así, una línea de tiempo que permite visualizar temporalmente tanto las cosas que permanecen como aquellas que se transforman o que emergen en momentos concretos. En cada escenario se hacen visibles dispositivos de poder disciplinario utilizados por los actores dominantes, y de las acciones que el pueblo sikuani, como actor subalterno, ha utilizado para negociar y resistir su opresión. Nos encontramos entonces con una antropología de los contactos y los encuentros coloniales; entre los agentes dominantes –misiones católicas, misiones, evangélicas fundamentalistas, funcionarios del Estado, terratenientes, grupos paramilitares, entre otros- y subalternos – el pueblo sikuani- para entender los momentos de crisis, ruptura y su contraparte, la formación de alianzas. Se examina así la configuración de la hegemonía entendida no como “consenso” sino como un proceso hegemónico que genera un espacio de controversia, confrontación y colusión entre grupos dominantes y grupos subordinados. Asimismo hay una descentralización de la historia focalizada en el Estado central, girando la mirada hacia las márgenes donde se dan complejas relaciones de poder, en las que se insertan los sectores subalternos, en este caso el del pueblo sikuani. Además se exploran las disputas en el interior de las comunidades indígenas, es decir, de la hegemonía comunal para examinar los cambios de autoridad y disputas políticas a nivel comunitario. Desde una visión etnográfica e histórica, hay una aproximación a las prácticas cotidianas y políticas de una comunidad sikuani, a su manera de relacionarse con los grupos dominantes, pero también a sus dinámicas políticas internas.

Déficit comercial: a la búsqueda de nuevos mercados

Probablemente en todos los países, pero desde luego en España, el resultado de la cuenta corriente de la balanza de pagos está fundamentalmente gobernado por la cuenta comercial de bienes. Ahora bien, si hubiera que destacar una característica de la citada cuenta en España, ninguna más adecuada que el déficit permanente que registra. Por eso puede afirmarse que la necesidad de endeudamiento externo de la economía española viene regida por sus malos resultados comerciales.

Aceleración de algoritmos para imágenes hiperespectrales con OpenCL

En el presente trabajo se propone dar solución a uno de los problemas principales surgido en el campo del análisis de imágenes hiperespectrales. En las últimas décadas este campo está siendo muy activo, por lo que es de vital importancia tratar su problema principal: mezcla espectral. Muchos algoritmos han tratado de solucionar este problema, pero que a través de este trabajo se propone una cadena nueva de desmezclado en paralelo, para ser acelerados bajo el paradigma de programación paralela de OpenCl. Este paradigma nos aporta el modelo de programación unificada para acelerar algoritmos en sistemas heterogéneos. Podemos dividir el proceso de desmezclado espectral en tres etapas. La primera tiene la tarea de encontrar el número de píxeles puros, llamaremos endmembers a los píxeles formados por una única firma espectral, utilizaremos el algoritmo conocido como Geometry-based Estimation of number of endmembers, GENE. La segunda etapa se encarga de identificar los píxel endmembers y extraerlos junto con todas sus bandas espectrales, para esta etapa se utilizará el algoritmo conocido por Simplex Growing Algorithm, SGA. En la última etapa se crean los mapas de abundancia para cada uno de los endmembers encontrados, de esta etapa será encargado el algoritmo conocido por, Sum-to-one Constrained Linear Spectral Unmixing, SCLSU. Las plataformas utilizadas en este proyecto han sido tres: CPU, Intel Xeon E5-2695 v3, GPU, NVidia GeForce GTX 980, Acelerador, Intel Xeon Phi 31S1P. La idea de este proyecto se basa en realizar un análisis exhaustivo de los resultados obtenidos en las diferentes plataformas, con el fin de evaluar cuál se ajusta mejor a nuestras necesidades.

Diseño y desarrollo de un servicio big data en la nube para búsqueda, compartición de ficheros y data mining

En esta memoria se presenta el diseño y desarrollo de una aplicación en la nube destinada a la compartición de objetos y servicios. El desarrollo de esta aplicación surge dentro del proyecto de I+D+i, SITAC: Social Internet of Things – Apps by and for the Crowd ITEA 2 11020, que trata de crear una arquitectura integradora y un “ecosistema” que incluya plataformas, herramientas y metodologías para facilitar la conexión y cooperación de entidades de distinto tipo conectadas a la red bien sean sistemas, máquinas, dispositivos o personas con dispositivos móviles personales como tabletas o teléfonos móviles. El proyecto innovará mediante la utilización de un modelo inspirado en las redes sociales para facilitar y unificar las interacciones tanto entre personas como entre personas y dispositivos. En este contexto surge la necesidad de desarrollar una aplicación destinada a la compartición de recursos en la nube que pueden ser tanto lógicos como físicos, y que esté orientada al big data. Ésta será la aplicación presentada en este trabajo, el “Resource Sharing Center”, que ofrece un servicio web para el intercambio y compartición de contenido, y un motor de recomendaciones basado en las preferencias de los usuarios. Con este objetivo, se han usado tecnologías de despliegue en la nube, como Elastic Beanstalk (el PaaS de Amazon Web Services), S3 (el sistema de almacenamiento de Amazon Web Services), SimpleDB (base de datos NoSQL) y HTML5 con JavaScript y Twitter Bootstrap para el desarrollo del front-end, siendo Python y Node.js las tecnologías usadas en el back end, y habiendo contribuido a la mejora de herramientas de clustering sobre big data. Por último, y de cara a realizar el estudio sobre las pruebas de carga de la aplicación se ha usado la herramienta ApacheJMeter.

Herramienta para búsqueda de casos médicos semejantes

Una de las tareas más comunes a las que se enfrentan los médicos es buscar historiales médicos, una tarea lenta y laboriosa que les arrebata tiempo útil. Este proyecto intenta reducir el tiempo dedicado a esa búsqueda permitiendo que, a partir del historial médico de un paciente, se encuentren otros casos similares dentro de la base de datos. Por eso, la base de datos con los documentos clínicos, en lenguaje natural en castellano, ha de ser procesada con las herramientas producidas por este proyecto. La aplicación está dividida en tres partes: la primera y la segunda se encargan de procesar los informes, dividiendo en campos y hallando los conceptos médicos respectivamente; la tercera parte es la que realiza las búsquedas de informes médicos similares.

Verificación de algoritmos y estructuras de datos en Dafny

La verificación formal de un programa es la demostración de que este funciona de acuerdo a una descripción del comportamiento esperado en toda posible ejecución. La especificación de lo deseado puede utilizar técnicas diversas y entrar en mayor o menor detalle, pero para ganarse el título de formal esta ha de ser matemáticamente rigurosa. El estudio y ejercicio manual de alguna de esas técnicas forma parte del currículo común a los estudios de grado de la Facultad de Informática y del itinerario de Ciencias de la Computación de la Facultad de Ciencias Matemáticas de la Universidad Complutense de Madrid, como es el caso de la verificación con pre- y postcondiciones o lógica de Hoare. En el presente trabajo se explora la automatización de estos métodos mediante el lenguaje y verificador Dafny, con el que se especifican y verifican algoritmos y estructuras de datos de diversa complejidad. Dafny es un lenguaje de programación diseñado para integrar la especificación y permitir la verificación automática de sus programas, con la ayuda del programador y de un demostrador de teoremas en la sombra. Dafny es un proyecto en desarrollo activo aunque suficientemente maduro, que genera programas ejecutables.

Aceleración de algoritmos de estimación de movimiento mediante OpenCL

El flujo óptico y la estimación de movimiento es área de conocimiento muy importante usado en otros campos del conocimiento como el de la seguridad o el de la bioinformática. En estos sectores, se demandan aplicaciones de flujo óptico que realicen actividades muy importantes con tiempos de ejecución lo más bajos posibles, llegando a tiempo real si es posible. Debido a la gran complejidad de cálculos que siguen a este tipo de algoritmos como se observará en la sección de resultados, la aceleración de estos es una parte vital para dar soporte y conseguir ese tiempo real tan buscado. Por lo que planteamos como objetivo para este TFG la aceleración de este tipo de algoritmos mediante diversos tipos de aceleradores usando OpenCL y de paso demostrar que OpenCL es una buena herramienta que permite códigos paralelizados con un gran Speedup a la par que funcionar en toda una diversa gama de dispositivos tan distintos como un GPU y una FPGA. Para lo anteriormente mencionado trataremos de desarrollar un código para cada algoritmo y optimizarlo de forma no especifica a una plataforma para posteriormente ejecutarlo sobre las diversas plataformas y medir tiempos y error para cada algoritmo. Para el desarrollo de este proyecto partimos de la teoría de dos algoritmos ya existentes: Lucas&Kanade monoescala y el Horn&Schunck. Además, usaremos estímulos para estos algoritmos muy aceptados por la comunidad como pueden ser el RubberWhale o los Grove, los cuales nos ayudarán a establecer la corrección de estos algoritmos y analizar su precisión, dando así un estudio referencia para saber cual escoger.

Las prácticas externas. Su organización para una mayor eficacia en la formación y búsqueda de empleo.

Se pretende implementar un procedimiento para la gestión de las prácticas externas que incluya la documentación necesaria para la clasificación y evaluación de las empresas e instituciones que intervienen, atendiendo a criterios como la formación recibida en ellas y la oportunidad de empleo.

La geografía de la búsqueda externa de conocimiento: la amplitud internacional de la cooperación en I+D

Es ampliamente aceptado que la habilidad de la empresa para innovar está sujeta a la base de conocimientos disponibles dentro de la organización. Tradicionalmente, la generación de nuevo conocimiento ha sido vinculada a las actividades de investigación y desarrollo (I+D) que la empresa realiza internamente. La internalización de la I+D era la forma dominante de búsqueda tecnológica corporativa (Mowery, 1983; Rosenberg et al., 1985; Nelson y Levin, 1986). La tendencia de internalizar los esfuerzos de innovación de las organizaciones se puede explicar, a partir del análisis realizado por Williamson (1975, 1985) sobre los costes de transacción que involucra las asimetrías de información, el monitoreo de problemas, y la posibilidad de comportamientos oportunistas. Sin embargo, Williamson (1984) deja abierta la pregunta de "hacer" o "comprar", y sugiere que la respuesta a ella es contingente a las especificidades de los procesos de transacción en cuestión. La decisión de la organización entre hacer o comprar, puede llevar a los directivos a la exploración de nuevas fuentes de conocimiento fuera de las fronteras de la empresa. Lo anterior fue sugerido por investigadores de la Economía Evolutiva, cuando propusieron que la organización debería de dedicarse a explorar el ambiente externo para mejorar su habilidad de innovar (Cyert y March, 1963), y que su proceso de búsqueda era crítico para su habilidad de adaptarse y evolucionar (Nelson y Winter, 1982; March, 1991; Levinthal, 1997). Estas actividades de búsqueda ayudarán a la organización a encontrar diferentes caminos tecnológicos (Metcalfe, 1995), permitiéndole crear nuevas combinaciones de tecnologías y conocimiento (Nelson y Winter, 1982)...