HEURISTICA

Autor: CENTENERA CENTENERA PALOMA.
Año: 2004.
Universidad: PONTIFICIA COMILLAS.
Centro de lectura: ESCUELA TECNICA SUPERIOR DE INGENIERÍA ICAI.
Centro de realización: ESCUELA TECNICA SUPERIOR DE INGENIERIA .

Resumen: LOS SISTEMAS INFORMÁTICOS DE DISEÑO ASISTIDO POR ORDENADOR HAN CONSEGUIDO FACILITAR EL TRABAJO DE LOS INGENIEROS Y DISEÑADORES EN LOS MÁS DIVERSOS ÁMBITOS. PERO CADA VEZ DE FORMA MÁS INSISTENTE SE PIDE TAMBIÉN QUE CONTRIBUYAN A FACILITAR LA POSTERIOR FABRICACIÓN DE LOS PRODUCTOS DISEÑADOS PARA LOGRAR CON ELLO UN ABARATAMIENTO DE LOS COSTES DE PRODUCCIÓN. LA CONSTRUCCIÓN DE NUMEROSOS PRODUCTOS A PARTIR DE SUPERFICIES DESARROLLABLES, ES DECIR, SUPERFICIES QUE PUEDEN EXTENDERSE SOBRE UN PLANO Y QUE PUEDEN POR TANTO FABRICARSE A PARTIR DE PIEZAS PLANAS, AYUDA EN GRAN MEDIDA A AUTOMATIZAR SU FABRICACIÓN Y A REDUCIR ASÍ LOS COSTES QUE ESTA LLEVA ASOCIADOS. UN EJEMPLO PARTICULAR ES EL DEL DISEÑO Y CONSTRUCCIÓN DE BUQUES DE ACERO EN EL QUE LA TECNOLOGÍA EMPLEADA PARA LA CONSTRUCCIÓN HACE QUE LA FABRICACIÓN DE SUPERFICIES DESARROLLABLES RESULTE MUY SENCILLA MIENTRAS QUE EL CONFORMADO DE SUPERFICIES NO DESARROLLABLES PRODUCE RESULTADOS CAROS Y DE POCA CALIDAD. EN LA PRESENTE TESIS DOCTORAL SE HA OPTIMIZADO EL MÓDULO DE APROXIMACIÓN DE SUPERFICIES MEDIANTE UNA DESARROLLABLE DE UN SISTEMA CAD PROPONIENDO UN NUEVO MÉTODO CON UN FUERTE FUNDAMENTO MATEMÁTICO, ORIENTADO AL DISEÑO Y CONSTRUCCIÓN DEL BUQUE, QUE APORTA CLARAS MEJORAS RESPECTO DE LOS SISTEMAS EXISTENTES EN LA ACTUALIDAD.

Autor: VERDÚ MONLLOR FERRAN.
Año: 2004.
Universidad: ALICANTE.
Centro de lectura: ESCUELA POLITÉCNICA DE LA UNIVERSIDAD DE ALICANT.
Centro de realización: ESCUELA POLITÉCNICA SUPERIOR.

Resumen: ESTE PROYECTO DESARROLLA UN ALGORITMO PARA OBTENER MÚLTIPLES MODELOS DE REGRESIÓN TANTO LINEALES COMO NO LINEALES EN LOS PARÁMETROS. EL ALGORITMO BASE PARA LA OBTENCIÓN DE LOS VALORES DE LOS PARÁMETROS ES EL DE GAUSS-NEWTON, PERO ADAPTADO A LA POSIBILIDAD DE CONSIDERAR MÚLTIPLES MODELOS. SE ESTABLECE, EN ESTE SENTIDO, UN MÉTODO DE BÚSQUEDA BASADO EN EL ESQUEMA DE PROGRAMACIÓN DEL "BACKTRACKING" DONDE SE INTRODUCEN CRITERIOS DE PODA EN EL ÁRBOL DE BÚSQUEDA BASADOS EN EL ESTUDIO DE LA ESTABILIDAD DE LOS MODELOS POR MEDIO DEL MÉTODO DE MONTE CARLO. EL PROGRAMA ES APLICADO SOBRE 32 EJEMPLOS CLÁSICOS DE REGRESIÓN NO LINEAL MOSTRANDO LOS RESULTADOS OBTENIDOS.

Autor: CANALES CANO SANTIAGO.
Año: 2003.
Universidad: POLITECNICA DE MADRID.
Centro de lectura: FACULTAD DE INFORMATICA .
Centro de realización: FACULTAD DE INFORMATICA.

Resumen: Dentro de la Geometría Computacional, uno de los campos que ha suscitado mayor interés entre la comunidad científica internacional ha sido el de la Visibilidad, es decir, el conjunto de problemas que están relacionados con los conceptos de iluminación y vigilancia de estructuras geométricas, con todas sus posibles variantes. Los resultados obtenidos en este ámbito por los investigadores, se pueden aplicar en algunos casos para solucionar problemas industriales reales relacionados con la iluminación o vigilancia, tales como iluminación de calles o de naves comerciales. Sin embargo, en muchas otras ocasiones, los elementos físicos reales que existen en la actualidad, discrepan en algún sentido de los modelos teóricos utilizados, con lo cual los resultados obtenido no son aplicables. Por ello, es necesario utilizar definiciones de visibilidad o iluminación que se acerquen cada vez más a situaciones reales. Siguiendo este objetivo, presentamos en la primera parte de esta memoria resultados combinatorios y algorítmicos utilizando dos deÞniciones de iluminación que añaden condiciones a los conceptos de vigilancia utilizados tradicionalmente: la primera de estas definiciones fue presentada por Ntafos en 1992, se denomina visibilidad de alcance limitado y añade una restricción a la distancia máxima de iluminación desde un determinado punto; la segunda que hemos denominado t-buena iluminación, se presenta en esta memoria por primera vez y su idea fundamental se basa en que una estructura geométrica sólo está bien iluminada si todos los puntos que la iluminan están bien distribuidos alrededor de ella. Respecto a la visibilidad de alcance limitado presentamos resultados combinatorios para polígonos escalera y polígonos pirámide, mientras para la t-buena iluminación presentamos resultados algoritmos que permiten calcular las regiones iluminadas con esta definición, por luces situadas en diferentes posiciones respecto a un polígono P. Por otra parte existen problemas en el ámbito de la Geometría Computacional que o bien son de naturaleza NP-dura, o bien no se han encontrado hasta el momento algoritmos eficientes que los solucionen. Sin embargo, en ambos casos, puede existir la necesidad real de aportar respuestas a dichos problemas, aunque dichas respuestas sean aproximadas o heurísticas. Así, en la segunda parte de esta memoria, presentamos procedimientos metaheurísticos que abordan problemas con estas características. Esquemáticamente se han abordado dos problemas. El primero de ellos es el problema de minimización del número de luces que iluminan un polígono P, cuya naturaleza NP-dura fue demostrada por Lee y Lin en 1964 y el segundo es el problema de la búsqueda de un nuevo punto en un Diagrama de Voronoi dado, tal que la región asociada a este nuevo punto tenga área máxima en el nuevo Diagrama de Voronoi construido. Para este segundo problema no se han encontrado hasta el momento soluciones algorítmicas eficientes que lo solucionen cuando los puntos se encuentran en posición general, aunque recientemene se han presentado soluciones para puntos situados en posición convexa. Para atacar heurísticamente el primero de estos problemas necesitamos solucionar previamente el problema de la búsqueda del conjunto de k luces, con k mayor que 0, cuyo área conjunta iluminada en el interior de un polígono P sea máxima. Este problema que se analiza por separado para el caso k = 1 y k mayor que 1 constituye el contenido fundamental de la segunda parte de esta memoria.

Autor: VEREDAS NAVARRO FRANCISCO JAVIER.
Año: 2003.
Universidad: MALAGA.
Centro de lectura: INFORMATICA.
Centro de realización: ETSI INFORMÁTICA.

Resumen: El cerebro humano es un evolucionado sistema biológico para el procesamiento de información, compuesto por numerosas, con intrincados patrones de interconexión entre ellas. Para conocer las propiedades computacionales del cerebro es importante comprender bien cómo están conectadas entre si las neuronas. Esto no resulta una tarea fácil. Para el estudio del conexionado neuronal pueden emplearse diferentes estrategias. Los métodos fisiológicos permiten emplear registros intracelulares para registrar la actividad neuronal e inferir conectividad. Sin embargo, este tipo de técnicas adolece de excesiva localidad. Los registros neurofisiológicos extracelulares permiten registrar un número elevado de neuronas a la vez. Sin embargo, también existen importantes limitaciones para identificar conexionado a partir de los datos de este tipo de registros. Por último, es posible hacer un enfoque computacional, basado en el modelado y la simulación de circuitos neuronales que capturen las propiedades básicas de la dinámica neuronal. En esta tesis se llevan a cabo simulaciones de circuitos neuronales, para lo que se ha desarrollado un modelo de neurona de integración y disparo con un alto grado de realismo. El objetivo principal de este trabajo consiste en comprender cuáles son los factores fisiológicos y de concectividad de red que determinan la actividad correlacionada entre pares de neuronas. Para ello, se parte del análisis mediante simulación del circuito más simple posible, una conexión monosináptica excitadora entre dos neuronas, y se prosigue con el estudio y la exploración de circuitos más complejos. Por último, se realizan métodos de optimización para llevar a cabo una búsqueda de redes alternativas al circuito monosináptico excitador que arrojen correlaciones de actividad similares a éste.

Autor: FERNÁNDEZ BLANCO PABLO.
Año: 2003.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FISICA.
Centro de realización: FACULTAD DE CIENCIAS FÍSICAS.

Resumen: En cualquier área de conocimiento aparecen muchos problemas reales de interés en los que se pretende alcanzar una condición óptima. Con los métodos clásicos de optimización, por distintas razones, no siempre resulta posible conseguirlo en un tiempo adecuado para su aplicación. En esta tesis se ha desarrollado el MOEASI, un Algoritmo Evolutivo Multiobjetivo memético, efectivo y flexible, que permite resolver problemas de muy diferente naturaleza. Permite la adopción de inmigrantes y que los tamaños de genes varíen entre generaciones. Es capaz de abordar problemas multiobjetivo, utilizando tanto técnicas clásicas, como incluyendo los principios de optimización del frente óptimo de pareto. La realización del MOEASI ha suspuesto desarrollar un operador de búsqueda local al que se ha denominado Superindividuo, el cual convierte un Algoritmo Evolutivom en hídrido o memético. Este operador consigue mantener la continuidad de la población conservando la diversidad del material genético, evita caer en mínimos locales, permite la inclusión de conocimiento del problema y permite reducir el tamaño de las poblaciones, haciendo disminuir el número de evaluaciones necesarias para lograr la optimización. Se ha estudiado la influencia de los valores de los parámetros del MOEASI y se ha evaluado su eficiencia, comparándolo con otros algoritmos, mediante la resolución de funciones test y con la Programación Dinámica mediante la resolución de distintos problemas, mejorando en todos los casos los resultados disponibles en la literatura. Se ha utilizado el MOEASI para resolver cuatro problemas de optimización: el modelado de los movimientos de un barco de alta velocidad, el diseño del control de dicho barco, la fermentación de la cerveza, y el transporte de fluildos por una red de tuberías. Abordando estos cuatro problemas, se ha demostrado todas las posibilidades que tiene el MOEASI para resolver problemas multiobjetivo. Los cuatro problemas, además de presentar una complejidad creciente (lo que permitirá evaluar la eficacia y la eficiencia del MOEASI), son problemas de muy distinta naturaleza; el modelado y diseño del control de un barco de alta velocidad supone hallar los parámetros de un control fuertemente no lineal trabajando en entornos muy diferentes. El proceso fermentativo de la cerveza resulta ser un proceso multiobjetivo muy complejo con un sistema de trece ecuaciones diferenciales no lineales. La optimización del transporte de diferentes fluidos por una red de tuberías es un problema combinatorio puesto que todas las variables implicadas son enteras. Para la aplicación del MOEASI se ha realizado un modelo para cada uno de los procesos, desarrollado una codificación del individuo que permitira la perfecta representación de la solución del problema tratado y se ha elaborado un conjunto de funciones objetivo con las cuales hemos sido capaces de evaluar la bondad de los individuos. En los cuatro casos se han obtenido soluciones satisfactorias y aplicables por la industria, comparables o aun mejorando las soluciones calculadas por otros métodos. Por último, en el problema combinatorio, se ha hibridado el MOEASI con la Programación Matemática, usando el conjunto de las soluciones obtenidas por esta última como semilla del MOEASI, logrando alcanzar mejores óptimos para todas las funciones objetivo.

Autor: CANO ALSUA SANTIAGO.
Año: 2002.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: MATEMÁTICAS.
Centro de realización: FACULTAD DE CC. MATEMÁTICAS.

Resumen: La monografía consta de ocho capítulos, un apéndice que incluye información del problema en internet y una amplia documentación sobre el problema hasta la actualidad. Los dos primeros capítulos tratan el estado del arte del problema, con atención a las formulaciones, versiones lineales, aplicaciones, problemas relacionados, complejidad y diferentes procedimientos de acotación, algoritmos exactos y heurísticos. En el capítulo tercero se desarrollan los algoritmos heurísticos r-óptimos, y se introducen procedimientos para la selección de permutaciones iniciales que cubran de forma ajustable e inteligente el espacio de soluciones. El capítulo IV presenta tres grupos de algoritmos heurísticos originales que son capaces de modificar el entorno de búsqueda dotando así a los algoritmos de una fuerte componente de memoria adaptiva. En el capítulo V se analizan diferentes variantes originales del algoritmo GRASP, de gran influencia en la literatura. En el capítulo VI se describe la resolución exacta de ejemplos históricos, el comportamiento de metaheurísticas y los resultados obtenidos por los algoritmos que se proponen en la monografía. El capítulo VII analiza las clasificaciones de ejemplos QAP desarrollando dos novedosas clasificaciones en función de las matrices del problema, mostrando el comportamiento estadístico de los algoritmos propuestos en las clases obtenidas. En el capítulo VIII se presentan las conclusiones finales y se plantean, en un estado avanzado, las líneas de investigación futuras.

Autor: RIVAS SANTOS VÍCTOR MANUEL.
Año: 2002.
Universidad: GRANADA.
Centro de lectura: INFORMÁTICA.
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: En esta tesis se describe un nuevo método, EvRBF, basado en un algoritmo evolutivo y diseñado para entrenar redes neuronales de funciones base radiales (RNFBR). El método automatiza el establecimiento de los valores para los parámetros de la RNFBR, incluido el tamaño de la misma, intentnado acercarlos a sus valores óptimos. Adecionalmente, se introduce el concepto de Objeto Evolutivo a partir del cual se ha generado la biblioteca de programación EO, con la que se ha programado el nuevo método. Los Objetivos Evolutivos han permitido la construcción de sistemas que engloban a todos los pradigmas de la computación evolutiva. A continuación, se realiza una revisión de los diferentes enfocados basados en algoritmos evolutivos que tratan de diseñar redes neuronales artificiales. De forma más particular, se revisan los métodos propuestos en la literatura para el diseño automático de RNFBR, incluyendo tanto algoritmos evolutivos como no evolutivos. Posteriormente, se describen los nuevos operadores genéticos diseñados para operar con RNFBR y se realiza un estudio para determinar con qué factores de probabilidad deben ser aplicados. Igualmente, se estudian diversos métodos de inicialización de individuos y asignación de fitness, concluyendo con un conjunto de parámetros óptimo para ejecutar el método. Por último, se comprueba la efectividad del método propuesto aplicándolo a diversos problemas de aproximación funcional, clasificación de patrones y estimación de series temporales. Las tasas de error alcanzadas por el método demuestran su capacidad para determinar la arquitectura de las RNFBR y entrenar los diversos parámetros que las componen.

Autor: DAMAS ARROYO SERGIO.
Año: 2002.
Universidad: GRANADA.
Centro de lectura: INFORMÁTICA.
Centro de realización: E.T.S. INGENIERÍA INFORMÁTICA.

Resumen: El principal objetivo de esta memoria es mostrar el buen comportamiento de las metaheurísticas afrontando el problema de registro de imágenes digitales. En esta línea, nos centraremos en el desarrollo de diferentes enfoques que tratan de reflejar la adecuada resolución del registrado tanto desde la perspectiva de las metaheurísticas que tratan de extender a los algoritmos básicos de búsqueda local, como de aquellas que incluyen un componente de aprendizaje. Para alcanzar este objetivo, la memoria está organizada en cuatro capítulos. La estructura de éstos se introduce brevemente a continuación. El capítulo 1 detalla tres conceptos básicos para el seguimiento de toda la memoria: el procesamiento de este tipo de imágenes, el registrado de imágenes digitales y las metaheurísticas. El capítulo 2 aborada el problema de registrado desde la perspectiva de aquellas metaheurísticas cuyo fundamento es extender las capacidades exploratorias de los algoritmos básicos de búsqueda. Como paradigma de éstas se ha elegido la búsqueda local reiterada. El enfoque de resolución del citado problema es afrontar conjuntamente la puesta en correspondencia y la búsqueda de los parámetros que definen la transformación de registrado. En este sentido, se trata de aprovechar la información que se puede derivar del estudio de la forma del objeto para guiar la búsqueda. De un lado, en el caso 2D, será el análisis del eje medio el que permita extraer importantes atributos que caracterizan la forma. De otro lado, en 3D, se sigue un enfoque complementario a partir de los datos de curvatura del contorno del objeto considerado. En el capítulo 3 se enfrenta el problema de registrado desde la perspectiva de las metaheurísticas que incorporan un componente de aprendizaje en el sentido de que implícita o explícitamente tratan de aprender correlaciones entre variables de decisión para identificar áreas de alta calidad del espacio de búsqueda. Más concretamente, el capítulo se centra en la , que usa modelos computacionales de procesos evolutivos como elementos centrales para el diseño e implementación de sistemas de resolución de problemas. Para ello, se trata de evitar ciertas faltas de precisión y simplificaciones encontradas en otros enfoques de la literatura reciente que tratan de resolver el mismo problema mediante estas mismas técnicas. Alternativamente, se propone el uso de diversos algoritmos evolutivos avanzados. Finalmente, el capítulo 4 de Comentarios Finales se sintetizan los resultados finales, conclusiones y trabajos futuros que se pueden plantear a partir de los expuesto en la memoria. Se incluyen, por tanto, los comportamientos más relevantes deducidos a partir de la experimentación llevada a cabo en cada capítulo, así como líneas abiertas para el desarrollo de nuevos trabajos dentro del ámbito del registrado de imágenes mediante metaheurísticas.

Autor: MARTÍNEZ TALAVAN PEDRO.
Año: 2002.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: MATEMÁTICAS.
Centro de realización: FACULTAD DE CC. MATEMÁTICAS.

Resumen: Esta memoria introduce en los capítulos 1 y 2 el modelo de Hopfield de redes neuronales y su aplicación al Problema del viajante. A pesar de los esfuerzos de muchos especialistas, el problema de determinación de los parámetros del modelo de Hopfield no estaba resuelto satisfactoriamente al no poder garantizar la factibilidad de los torus identificados por los puntos de equilibrio de la ecuación diferencial asociada. En el capítulo 3 se resuelve este problema proponiendo una parametrización para resolver el problema del viajante y se aportan experiencias computacionales que validan los resultados teóricos. En los capítulos 4 y 5 se propone un procedimiento que resuelve el problema de asignación cuadrática con restricciones lineales por medio del modelo de Hopfield. En el capítulo 6 se resuelve el problema de coloración de grafos planteándolo como un problema de asignación lineal con restricciones cuadráticas. En estos tres capítulos citados se garantiza también la validez de las soluciones obtenidas y se detallan experiencias computacionales. En el apéndice A de la memoria se detalla el algoritmo de determinación de puntos estables del modelo de Hopfield, que mejora el método tradicional de Euler de resolución numérica de ecuaciones diferenciales.

Autor: RIERA LEDESMA JORGE.
Año: 2002.
Universidad: LA LAGUNA.
Centro de lectura: INFORMÁTICA.
Centro de realización: CENTRO SUPERIOR DE INFORMÁTICA.

Resumen: La tesis doctoral versa sobre diversos métodos de resolución para el problema del comprador ambulante (The Traveling Porchaser Problem). Dentro de estos métodos se ha diseñado dos algoritmos exactos, basados en una metodología denominada "Brancia-and-cot", para los casos simétricos y asimétricos del problema a estos efectos, se ha diseñado dos modelos basados en programación lineal entera mixta, y posteriormente se ha afectado el estodio poliedríco. Todo lo anterior conduce a dos algorítmos que son evaluados computacionalmente. La versión biobjetivo de este problema es también analizada. Para este problema se ha diseñado un algoritmo que encuentra el conjunto eficiente. Finalmente se propone un algoritmo aeurístico basado en búsqueda local con diferentes tipos de vecindad.

Autor: GONZÁLEZ MARTEL CHRISTIAN.
Año: 2002.
Universidad: LAS PALMAS DE GRAN CANARIA.
Centro de lectura: CIENCIAS ECONÓMICAS Y EMPRESARIALES.
Centro de realización: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES .

Resumen: Diversos trabajos han puesto de manifesto que las conclusiones sobre la falta de poder predictivo de las reglas técnicas eran, cuanto menos, precipitadas. Debido a que la eficiencia e integración pueden variar considerablemente de unos mercados a otros, tiene elevado valor empírico las investigaciones en mercados bursátiles de tamaño mediano como ocurre con el caso de la Bosla de Madrid. Esta Tesis presenta diversas aportaciones sobre la capacidad de generar beneficios de determinadas metodologías para crear reglas técnicas sobre el IGBM, que dan pie al siguiente primer grupo de conclusiones. Por una parte, se ha examinado la capacidad de obtener beneficios de una simple regla técnica de contratación basada en redes neuronales aplicada sobre el IGBM. Asímismo, se ha investigado la capacidad de obtener beneficios de las reglas técnicas de contratatación más comúnmente usadas por los inversores como son las de cruce de medias móviles o la de ruptura de rango, pero realizando una aportación metodológica en el sentido de optimziar los valores de los parámetros que aparecen en tales reglas mediante un algoritmo genético. Se ha estudiado la posibilidad de implementar en el IGBM nuevas reglas técnicas de contratación creadas mediante la programación genética, que permite diseñar reglas técnicas óptimas distitnas a las más comúnmente usadas en el mercado. Por último, se ha diseñado un procedimiento para ajustar, mediante la validación cruzada, los parámetros claves de una regla técnica simple basada en las predicciones por ocurrencias análogas. En este sentido, los parámetros se obtienen mediante optimización con un algoritmo genético de la función de pérdida dada por el exceso rendimientos sobre la estrategia de "comprar y mantener" ajustada por riesgo.

Autor: GARCÍA SÁNCHEZ JOSÉ MANUEL.
Año: 2002.
Universidad: SEVILLA.
Centro de lectura: ESCUELA SUPERIOR DE INGENIEROS.
Centro de realización: ESCUELA SUPERIOR DE INGENIEROS.

Resumen: En esta Tesis se estudia el problema asociado a la planificación conjunta o coordinada de la producción y distribución de productos de carácter no almacenable. Estos productos se caracterizan por una distribución que debe realizarse de manera inmediata a la finalización del proceso productivo, debido a la ausencia de inventarios del producto. La fabriación se realiza en una planta y desde allí se distribuye el pedido hasta una localización determinada, con la ayuda de una flota de vehículos. El problema se centra en la selección de los pedidos que van a ser servidos, de entre un conjunto de pedidos solicitados, debido a dos características fundamentales: * El sistema funciona con una filosofía just-in-time, no permitiendo la entrega de un pedido fuera de su plazo de entrega, ya sea éste fijo o variable. * Se imponen limitaciones de recursos, tanto en la fase de producción como en la de distribución, que normalmente impiden atender a todos los pedidos solicitados. El análisis realizado sobre la actividad de los pedidos en el sistema encamina el problema hacia el campo de la secuenciación de trabajos en máquinas. De allí se extraen diversos modelos que ayudan al planteamiento y resolución del problema. El problema se presenta sobre diferentes escenarios definidos en función del tipo de plazo de entrega (fijo o variable) y del número de plantas de producción. En cada escenario se presenta un modelo de programación entera, así como métodos exactos y aproximados para la resolución del problema. En todos los escenarios estudiados los métodos aproximados permiten resolver el problema con errores mínimos y en tiempos aceptables, conclusión que nos resulta muy satisfactoria para los objetivos perseguidos en la investigación. La presente memoria incluye un CD con todos los datos, programas informáticos y resultados.

Autor: VILLA CARO GABRIEL.
Año: 2002.
Universidad: SEVILLA.
Centro de lectura: ESCUELA SUPERIOR DE INGENIEROS.
Centro de realización: ESCUELA SUPERIOR DE INGENIEROS DE SEVILLA.

Resumen: En esta tesis se pretende abarcar un amplio estudio sobre la metodología del Análisis por Envoltura de Datos (DEA) consistente en dos partes fundamentales: una ampliación teórica de la bibliografía existente de los modelos que resuelven los problemas de medición de la eficiencia mediante DEA, y un estudio práctico de algunos casos novedosos y de interés. Los modelos que aparecen en la metodología DEA tradicional contemplan la resolución de problemas donde a menudo sólo se pretende la medición de la eficiencia de las unidades productivas de forma individual. Sin embargo no suele plantearse dicha medición de la eficiencia sobre el conjunto de las unidades como un todo. Un caso de sumo interés es aquél en el que se quiere analizar el estudio de la eficiencia de unidades productivas dependientes de una organización superior a todas ellas, y capaz de decidir en cada momento los recursos que podrán utilizar. En dicho escenario, esta unidad superior velará por el cumplimiento de dos objetivos fundamentales: por un lado, la búsqueda de la eficiencia de las unidades. Este último objetivo ha sido tratado por diferentes autores por ser de gran utilidad en múltiples casos reales. En la primera parte de la investigación se presentarán una serie de modelos basados en la metodología DEA capaces de abordar este nuevo escenario asumiendo las diferentes tecnologías y orientaciones posibles. La metodología DEA tiene como características fundamental su versatilidad. Debido a ella, muchas son las aplicaciones que se han generado para medir la eficiencia de ciertas unidades mediante los modelos disponibles en la bibliografía. Además, es obvio que el desarrollo de estos ejemplos ayuda en gran medida a la mejor comprensión de la metodología. En la segunda parte del trabajo se desarrollarán un par de aplicaciones que serán justificadas como novedosas. La primera de ellas consiste en un desarrollo de la metodología DEA aplicado a la medición de la eficiencia de las naciones participantes en los últimos cinco Juegos Olímpicos celebrados hasta la fecha. Posteriormente, se realizará un experimentos enfocado en un escenario donde se prtenden no sólo el aumento de la eficiencia individual de las unidades productivas, sino una mejora global de todas ellas en un conjunto. Dicho experimento consistirá en la medición de la eficiencia de los municipios del Principado de Asturias como unidades de reciclado de vidrio.

Autor: MARTÍN GARCÍA ELENA.
Año: 2002.
Universidad: SEVILLA .
Centro de lectura: INFORMÁTICA.
Centro de realización: FACULTAD DE INFORMÁTICA Y ESTADÍSTICA.

Resumen: Los Sistemas Evolutivos buscan soluciones factibles para problemas donde la complejidad de los mismos hacen que no puedan obtenerse soluciones exactas. El problema de la selección de indicadores (PSI) es un problema cuyo carácter no polinomial hace que la utilización de heurísticas sea lo más adecuado para obtener soluciones. El problema que estudiamos en este trabajo es un problema que está íntimamente relacionado con otros tipos de problemas de tipo combinatorio, así como con problemas de decisión, optimización e incluso problemas de localización. El pronóstico de este trabajo es diseñar e implementar un Sistema Evolutivo para resolver el problema de la selección de indicadores y en particular el de la selección de indicadores y en particular el de la selección de indicadores de calidad, problema de gran importancia práctica, económica y social. El objetivo del sistema evolutivo es encontrar un subconjunto de indicadores que posea representatividad y coste adecuado. Representatividad en el sentido que dicho subconjunto debe proporcionar una información que sea más o menos cercana a máximo de la información que se pueda obtener y coste adecuado ya que el coste de dicho subconjunto no debe exceder a una cierta cantidad o bien ha de ser mínimo. Además con este estudio pretendemos comprobar como un sistema evolutivo puede ser de gran utilidad para resolver problemas cuya naturaleza es similar a la de los mencionados anteriormente. Es decir, es un sistema flexible, constituyendo una herramienta muy adecuada para el proceso de toma de decisiones. El algoritmo genético en el que se basa nuestro algoritmo evolutivo utiliza como individuos de la población subconjuntos de indicadores y no las cadenas binarias clásicas, ya que dichos subconjuntos poseen la misma estructura que las posibles soluciones del problema. Nuestro sistema trabaja con un conjunto de operadores que son seleccionados dinámicamente, primando a aquellos con mayor éxito o que el sistema haya primado con mayor calificación. Estas selecciones presenta varias limitaciones, una de ellas es que no se adapta a los mecanismos de la evolución natural. En este trabajo el sistema evolutivo que proponemos emula los procesos de la naturaleza. Se considera un conjunto de operadores básicos que pueden o no poseer un conjunto de características. Éstas pueden o no intercambiarse entre sí permitiendo cruzamientos, mutaciones y selección entre los operadores. Esto permite definir dos poblaciones que van evolucionando paralelamente. Esto supone un gran avance sobre la selección dinámica y un resultado de gran importancia teórica y práctica dentro del campo de los sistemas evolutivos. Queremos de igual forma hacer notar como la modelización de un problema de gran interés de tipo práctico, económico y social, enmarcado en las ciencias sociales y de difícil resolución mediante técnicas clásica, encuentran en el ámbito de las ciencias matemáticas una técnica adecuada para su resolución.

Autor: ZALAMEA LEÓN FRANCISCO JAVIER.
Año: 2002.
Universidad: POLITECNICA DE CATALUÑA.
Centro de realización: DEPARTAMENTO DE ARQUITECTURA DE COMPUTADORES.

Autor: CRESPO ABRIL FORTUNATO.
Año: 2002.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: INFORMÁTICA.
Centro de realización: DPTO. ESTADÍSTICA E INVESTIGACIÓN OPERATIVA APLICADAS Y CALIDAD.

Resumen: Abordamos el Problema de la Programación de Proyectos con Recursos Limitados en su versión estándar, con el objetivo de obtener una programación para las actividades que minimice la duración del proyecto. Este problema es de naturaleza combinatorioa y pertenece a la clase de problemas NP-duros, por ello, el espacio de soluciones posibles crece de forma exponencial conforme aumenta el tamaño del problema. Aunque la aparición en la última década de máquinas cada vez más potentes ha permitido aumentar el tamaño y el número de los problemas resueltos de forma óptima, la resolución de estos problemas siguen demandando mayor velocidad de proceso. La computación en paralelo aparece como un posible camino para abordar estos problemas, ya que explota la idea de dividir el trabajo entre un conjunto de procesadores que colaboran en la solución de un único problema. Los objetivos de este trabajo se centran en el desarrollo, adaptación e implementación de algoritmos paralelos para resolver de forma óptima este problema, estudiando las ventajas e inconvenientes que los mismos presentan. Ha sido necesario reformular e introducir nuevos conceptos para permitir la correcta aplicación de algunas reglas de dominancia que dejan de ser válidas cuando se realiza una búsqueda en paralelo de la solución óptima. La construcción de un cluster de ordenadores personales nos ha permitido diseñar un entorno de programación en paralelo en el que desarrollar nuestro trabajo sin la necesidad de recurrir a costosas máquinas paralelas. Los resultados obtenidos al resolver los proyectos de 30 y 60 actividades de la librería estándar PSPLIB han permitido evaluar el comportamiento de los algoritmos paralelos branch&bound desarrollados. Estos resultados ponen de manifiesto como la computación en paralelo es una técnica adecuada para resolver de forma óptima el problema de la programación de proyectos con recursos limitados. Además la versión truncada de los algortimos diseñados puede competir con algunos de los mejores algoritmos heurísticos publicados.

Autor: SALIDO GREGORIO MIGUEL ÁNGEL.
Año: 2002.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: INFORMÁTICA.
Centro de realización: FACULTAD DE INFORMÁTICA.

Resumen: En esta tesis proponemos un modelo de especificación de restricciones n-arias mediante hiperpoliedros que se resuelve mediante técnicas que manejan las restricciones no binarias en su formulación original de manera que se conserva toda la expresividad de las restricciones no binarias. Debido a la carencia de técnicas para manejar restricciones no binarias sobre dominios continuos, nuestro trabajo se centra en la obtención de técnicas que manejen este tipo de problemas, aunque también abarcamos problemas discretos y problemas disyuntivos, extendiendo algunas de las clases más importantes de restricciones disyuntivas. En vista de la gran cantidad de problemas dinámicos que existen en la vida real, nuestras técnicas mantienen un comportamiento dinámico de manera que las restricciones no binarias se pueden incluir en el sistema de forma incremental. Estas técnicas obtienen información importante del problema tal como la consistencia del problema, las soluciones que el usuario requiera, los dominios mínimos, así como las soluciones que mejor aproximen una función objetivo o multi-objetivo. Estas técnicas están siendo aplicadas en la actualidad en el campo de la diagnosis y más concretamente en la toma de decisiones, donde se utilizan los clasificadores para hacer predicciones. Estos clasificadores son evaluados mediante el cálculo del volumen que generan, siendo imprescindible para ello la obtención de los puntos extremos que componen el hiper-poliedro resultante.

Autor: BARCOS REDÍN LUCIA.
Año: 2002.
Universidad: NAVARRA.
Centro de lectura: INGENIEROS INDUSTRIALES.
Centro de realización: ESCUELA SUPERIOR DE INGENIEROS - TECNUN.

Resumen: El envío de carga de muchos orígenes a muchos destinos es un problema habitual del sector del transporte de paquetería. En estos problemas se intenta consolidar la carga en vehículos para reducir costes, controlando el tiempo de servicio y los retornos en vacío para balancear flujos. La optimización es compleja, pero el análisis del sistema puede descomponerse. (aproximadamente) en el estudio de las relaciones origen-destino. Para cada relación O-D hay varias estrategias para consolidar la carga, pero las más usuales son las paradas múltiples cerca del origen o cerca del destino o la clasificación de cargas en terminales hub que incrementan las expectativas de consolidación. La tesis modeliza el sistema suponiendo un conjunto de terminales hub dadas. Para cada par O-D se minimiza el coste total de transporte cumpliendo un nivel de servicio determinado en plazo de entrega que se expresa como porcentaje mínimo de la carga (o expediciones) que debe servirse en ese plazo. Tras una formulación como programa matemático entero, el problema se resuelve mediante el metaheurístico de las colonias de hormigas. Este bio-heurístico se basa en la elección probabilística de alternativas en función del nivel de feromonas de cada alternativa, rastro éste que depende del número de hormigas que han optado por tal alternativa previamente y que se desvanece al cabo de un tiempo. Se utiliza un parámetro de información heurística para cada uno de los subproblemas de análisis (envíos directos y envíos a través de unos o dos hubs, y paradas múltiples en origen o en destino). El algoritmo implementado se ha contrastado con soluciones exactas en diversos ejemplos de tamaño reducido mostrando una complejidad polinómica de grado bajo con el tamaño del problema. Las aceptables correlaciones obtenidas entre las predicciones del modelo y los datos de base permiten calificar el modelo global de robusto. Cuando se ha aplicado (de forma simplificada) a una empresa de paquetería real, se han conseguido disminuir los costes en un 8%. La aplicación termina con un análisis de sensibilidad respecto a los parámetros y valores más relevantes. Finalmente, se derivan conclusiones y se apuntan futuras líneas de investigación.

Autor: ALONSO BLÁZQUEZ FERNANDO.
Año: 2002.
Universidad: NAVARRA.
Centro de lectura: INGENIEROS INDUSTRIALES.
Centro de realización: ESCUELA SUPERIOR DE INGENIEROS.

Resumen: Es un mercado tan diversificado, competitivo y, sobre todo, tan voluminoso como es el del gran consumo, que abarca las áreas de droguería, perfumería y alimentación, la logística adquiere una relevancia única para lograr una ventaja competitiva en relación con otros marcos estratégicos. Dentro de la logística de las compañías de distribución de productos de gran consumo, la gestión de las actividades de distribución física, y en concreto el transporte, constituyen un punto clave en la toma de decisiones. Este tipo de compañías vende grandes volúmenes de productos con márgenes muy pequeños a través de una red de miles de pequeños, medianos y grandes establecimientos localizados en pueblos y ciudades. Se hace patente la necesidad de estructurar rutas de transporte que permitan explotar eficientemente una flota de vehículos. El modelo de distribución más conocido, que ha sido extensivamente tratado por la comunidad investigadora y que se ajusta a gran cantidad de empresas es el conocido como "Vehicle Routing Problem" (VRP), donde un conjunto de clientes deber ser servido en una base diaria desde un almacén central mediante una flota de vechículos que tiene su base en dicho almacén. Sin embargo, existen otros tipos de compañías cuya planificación no es diaria, sino que se caracterizan por una cierta periodicidad en el servicio de forma que los clientes deben ser servidos entre 1 y t veces dentro de un período de t días. Este modelo se conoce como "Periodic Vechcle Routing Problem" (PVRP) y trata de definir la distribución de los servicios de los clientes en el período y un conjunto de rutas para cada día del período de forma que se asegure el nivel de servicios a cada cliente, respetando las restricciones de la flota de vehículos y minimizando los costes operativos de la flota. En este trabajo se analiza en primer lugar en el modelo de distribución periódico PVRP, mostrando los diferentes planteamientos presentes en la bibliografía así como los métodos de resolución aplicados a lo largo de los años. Se plantea a continuación un modelo de distribución períodico que toma como base el anterior y que incluye, además de las restricciones de capacidad y tiempos máximos de operación diarios para los vehículos otras restricciones y características. Por un lado, se tiene en cuenta el carácter heterogéneo de la flota, en el sentido de que los costes de utilizaicón son dependientes del tipo de vechículo. Por otro lado, se contempla la posibilidad de que un vehículo realice más de una ruta diaria siempre y cuando son supere, en total, su tiempo máximo de operación. Por último, se incluyen algunas restricciones de accesibilidad de los vehículos a los clientes, que deben ser respetadas. Posteriormente se presenta un algoritmo basado en la Búsqueda Tabú que resuelve el problema planteado y que es probado sobre ejemplos del problema generados de forma aleatoria. Se prueba a su vez el método mediante su aplicación a problemas de generación de rutas y planificación de vehículos de la bibliografía y que constituyen casos particulares del problema propuesto ya que relajan una o más características del mismo. Para ellos se dispone de resultados obtenidos por diversos autores. Se logra salvar la barrera entre algoritmos teóricos y resolución de problemas reales mediante la aplicación práctica de la metodología desarrollada a un caso real. En él se verán todos los problmeas que surgen al llevar al campo de la actividad empresarial un modelo teórico y cómo es posible ajustar dicho modelo para que resulte de utilidad a una empresa de distribución. Finalmente se exponen las conclusiones del trabajo, futuras líneas de investigación y las referencias bibliográficas más significativas.

Autor: ALCARAZ SORIA JAVIER.
Año: 2001.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: INFORMATICA.
Centro de realización: FACULTAD DE INFORMATICA.

Resumen: El problema de la Programacion de Proyectos con Recursos Limitados ha sido ampliamente estudiado y para resolverlo se han propuesto tanto tecnicas exactas como heuristcas. Las tecnicas exactas no son capaces, en algunos casos, de encontrar la solucion optima, y en otros, los elevados tiempos de calculo requeridos, debido a que se trata de un problema NP-duro, las hace poco utiles. La alternativa la constituyen las tecnicas heuristicas, de las cuales las basadas en reglas de prioridad fueron las primeras en ser aplicadas. Sin embargo, las tecnicas metaheuristicas estan desbancando a las anteriores, debido a los excelentes resultados que estan obteniendo. Entre las tecnicas metaheuristicas mas utilizadas destacan los algoritmos geneticos, tabu-search y simulated anneling. En esta Tesis doctoral se han desarrollado nuevos algoritmos geneticos para resolver el problema, tanto en su version estandar o "unico-modo" como "multi-modo". Se ha diseñado un nuevo tipo de representacion para las soluciones al problema, que incorpora informacion relativa al esquema empleado para secuenciar las actividades: forward o backward. Ademas, se han desarrollado nuevos operadores de cruce y mutacion, capaces de manejar de forma eficiente la informacion almacenada en este nuevo tipo de representacion. Los algoritmos desarrollados han sido comparados con los mejores heuristicos publicados, utilizando para ello la librería estandar de proyectos PSPLIB. El extenso experimento computacional llevado a cabo pone de manifiesto el superior comportamiento de los algoritmos desarrollados.