Academic literature on the topic 'Algoritmes genètics'

L'estructura multiresolutiva proposada per Moran [1] té com a objectiu obtenir l'equilibri entre el cost computacional de l'adquisició sèrie i l'eficiència de l'adquisició paral•lela en sistemes d'espectre eixamplat de seqüència directa. L'adquisició i el posterior tracking són dos processos clau en la desmodulació del senyal d'espectre eixamplat, puix que sense una correcta sincronització aquesta és inviable. L'estructura multiresolutiva mostrà en la seva primera proposta un bon comportament en un canal ionosfèric de 800km [2], però el problema al que s'enfronta ara és més complex. Un canal ionosfèric des de l'Antàrtida a Catalunya, d'una longitud de 12700km, amb unes condicions de canal més agreujades per la distància i la variabilitat horària de la ionosfera en el trajecte de les ones. És amb aquest objectiu que aquest treball de tesi presenta millores a aquest algorisme d'adquisició i de seguiment amb els ulls posats en el problema a resoldre. S'han dissenyat seqüències PN adaptades a les necessitats de l'estructura multiresolutiva usant estratègies evolutives [3,4] i algorismes genètics [5], demanant a les seqüències pseudoaleatòries l'acompliment de més requisits que els originals de les seqüències PN. D'altra banda, també s'ha dissenyat un sistema d'estimació de la qualitat de l'adquisició i de control basat en lògica difusa [6], que permeti donar garanties de la robustesa de l'adquisició i alhora, millorar les prestacions de l'estructura reduint-ne el cost computacional. Finalment, s'ha realitzat un refinament del funcionament de l'estructura multiresolutiva, ajustant-ne els paràmetres d'aprenentatge dels filtres adaptatius de la mateixa per al canal ionosfèric i afegint-li la prestació de funcionar com a detector RAKE, que millora la qualitat de les dades desmodulades. Aquests nous dissenys i millores han estat contrastats amb l'estructura multiresolutiva original [1] i amb d'altres algorismes d'adquisició adaptatius basats en filtres LMS [7,8] i s'ha demostrat que les aportacions realitzades en aquest treball permeten obtenir un millor rendiment en les condicions de transmissió abordades. [1] J. A. Morán. Sistema ràpid d’adquisició per transmissió DS-SS sobre canal ionosfèric. Tesi Doctoral, Enginyeria i Arquitectura La Salle. Universitat Ramon Llull, Barcelona (Espanya), 2001. [2] J.A. Morán, J.C. Socoró, X. Jové, J.L. Pijoan i F. Tarrés. Multiresolution Adaptive Structure for acquisition in DS-SS receivers. International Conference on Acoustics, Speech and Signal Processing (ICASSP). Salt Lake City (EUA), 2001. [3] I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipiender biologischen Evolution. Frommann-Holzboog, Alemanya, 1973. [4] H.P. Schwefel. Evoluitonsstrategie und numerische Optimierung. Tesi Doctoral, Technische Universitat Berlin, Berlin (Alemanya), 1975. [5] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. [6] L.A. Zadeh. Fuzzy Sets. IEEE Trans. on Information and Control, 8:338–353, 1965. [7] M.G. El-Tarhuni. Application of Adaptive Filtering to Direct-Sequence Spread-Spectrum Code Synchronization. Tesi Doctoral, Carleton University, 1997. [8] M. Han, T. Yu, C. Kang i D. Hong. A New Adaptive Code-Acquisition Algorithm Using Parallel Subfilter Structure. IEEE Transactions on Vehicular Technology, 55(6):1790–1796, Novembre 2006.<br>La estructura multiresolutiva propuesta por Moran [1] tiene como objetivo obtener el equilibrio entre el coste computacional de la adquisición serie y la eficiencia de la adquisición paralela en sistemas de espectro ensanchado de secuencia directa. La adquisición y el posterior tracking son dos procesos clave en la demodulación de la señal de espectro ensanchado, puesto que sin una correcta sincronización ésta es inviable. La estructura multiresolutiva mostró en su primera propuesta un buen comportamiento en un canal ionosférico de 800km [2], pero el problema al que se enfronta ahora es más complejo. Un canal ionosférico desde la Antártida a Catalunya, con una longitud de 12700km, con unas condiciones de canal más agravadas por la distancia y la variabilidad horaria de la ionosfera en el trayecto de las ondas. Con este objetivo, este trabajo de tesis presenta mejoras a este algoritmo de adquisición y de seguimiento con la mirada puesta en el problema a resolver. Se han diseñado secuencias PN adaptadas a las necesidades de la estructura multiresolutiva usando estrategias evolutivas [3,4] y algoritmos genéticos [5], pidiendo a las secuencias pseudoaleatorias más requisitos que los habituales en las secuencias PN. Por otro lado, también se ha diseñado un sistema de estimación de la calidad en la adquisición y de control basado en lógica difusa [6], que permita dar garantías de la robustez en la adquisición y a su vez, mejorar las prestaciones de la estructura reduciendo el coste computacional. Finalmente, se ha realizado un ajuste del funcionamiento de la estructura multiresolutiva, ajustándose los parámetros de aprendizaje de los filtros adaptativos para el canal ionosférico y añadiendo la prestación de funcionar como detector RAKE, que mejora la calidad de los datos demodulados. Estos nuevos diseños y mejoras se han contrastado con la estructura multiresolutiva original [1] y con otros algoritmos de adquisición adaptativos basados en filtros LMS [7,8] y se ha demostrado que las aportaciones realizadas en este trabajo permiten obtener un mejor rendimiento en las condiciones de transmisión abordadas. [1] J. A. Morán. Sistema ràpid d’adquisició per transmissió DS-SS sobre canal ionosfèric. Tesis Doctoral, Enginyeria i Arquitectura La Salle. Universitat Ramon Llull, Barcelona (España), 2001. [2] J.A. Morán, J.C. Socoró, X. Jové, J.L. Pijoan i F. Tarrés. Multiresolution Adaptive Structure for acquisition in DS-SS receivers. International Conference on Acoustics, Speech and Signal Processing (ICASSP). Salt Lake City (EUA), 2001. [3] I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipiender biologischen Evolution. Frommann-Holzboog, Alemanya, 1973. [4] H.P. Schwefel. Evoluitonsstrategie und numerische Optimierung. Tesis Doctoral, Technische Universitat Berlin, Berlin (Alemanya), 1975. [5] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. [6] L.A. Zadeh. Fuzzy Sets. IEEE Trans. on Information and Control, 8:338–353, 1965. [7] M.G. El-Tarhuni. Application of Adaptive Filtering to Direct-Sequence Spread-Spectrum Code Synchronization. Tesis Doctoral, Carleton University, 1997. [8] M. Han, T. Yu, C. Kang i D. Hong. A New Adaptive Code-Acquisition Algorithm Using Parallel Subfilter Structure. IEEE Transactions on Vehicular Technology, 55(6):1790–1796, Noviembre 2006.<br>The multiresolutive structure proposed by Moran [1] attempts to reach a compromise between the computational cost of serial acquisition schemes and acquisition efficiency of parallel systems in direct-sequence spread spectrum acquisition. Acquisition and subsequent tracking are two key processes in the signal demodulation, since without proper synchronization demodulation is impossible. The multiresolutive structure in Moran’s first proposal showed a good performance on an ionospheric channel of 800km [2], but the problem we face now is more complex. A ionospheric radio channel from the Antarctica to Catalonia, 12700km in length, with worsen channel conditions due to distance and time variability of the ionosphere along the paths of the radio waves. This thesis presents improvements to this algorithm acquisition and tracking system in the aim of facing those hard channel conditions. PN sequences are designed to satisfy the needs of the multiresolutive structure [ABM05, AFSB07] using evolutionary strategies [3, 4] and genetic algorithms [5], through adding more requirements than is usually demanded. On the other hand, a fuzzy logic [6] control block has been implemented to estimate the quality of acquisition and control, evaluate the robustness of the acquisition and improve the performance of the structure by reducing its computational load. Finally, the multiresolutive structure has been adjusted, setting new values for the adaptive filter convergence parameters that refer to the ionospheric radio channel and improving the demodulated data using a RAKE detector. The new multiresolutive structure has been compared to the original multiresolutive structure [1] and to other LMS-based adaptive acquisition algorithms [7,8]. The results show that the new multiresolutive structure is competitive when comparing the original structure and also in relation to other adaptive acquisition algorithms found in state-of-the-art. [1] J. A. Morán. Sistema ràpid d’adquisició per transmissió DS-SS sobre canal ionosfèric. PhD Thesis, Enginyeria i Arquitectura La Salle. Universitat Ramon Llull, Barcelona (Espanya), 2001. [2] J.A. Morán, J.C. Socoró, X. Jové, J.L. Pijoan i F. Tarrés. Multiresolution Adaptive Structure for acquisition in DS-SS receivers. International Conference on Acoustics, Speech and Signal Processing (ICASSP). Salt Lake City (EUA), 2001. [3] I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipiender biologischen Evolution. Frommann-Holzboog, Alemanya, 1973. [4] H.P. Schwefel. Evoluitonsstrategie und numerische Optimierung. Tesi Doctoral, Technische Universitat Berlin, Berlin (Alemanya), 1975. [5] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. [6] L.A. Zadeh. Fuzzy Sets. IEEE Trans. on Information and Control, 8:338–353, 1965. [7] M.G. El-Tarhuni. Application of Adaptive Filtering to Direct-Sequence Spread-Spectrum Code Synchronization. PhD Thesis, Carleton University, 1997. [8] M. Han, T. Yu, C. Kang i D. Hong. A New Adaptive Code-Acquisition Algorithm Using Parallel Subfilter Structure. IEEE Transactions on Vehicular Technology, 55(6):1790–1796, November 2006.

La realización de nuevas infraestructuras para la mejora de la eficiencia global del riego, deben de venir acompañadas de una gestión adecuada, ya que sin ésta no se justifican las grandes inversiones acometidas. Para optimizar el uso de todos los insumos que participan en el riego, agua, energía y fertilizantes, se necesita realizar un seguimiento de todos los procesos en que están implicados, con el fin de detectar los puntos débiles de la gestión y mejorarlos. Dada la gran cantidad de información requerida para ello, resulta recomendable desarrollar un Sistema de Soporte a la toma de Decisiones (DSS). Puesto que la mayoría de la información utilizada es de carácter espacial, los Sistemas de Información Geográfica (SIG) se muestran como la herramienta de trabajo más idónea para ello. En el trabajo desarrollado se describe la metodología seguida para la elaboración de un DSS orientado a la gestión del riego en redes a presión, denominado HuraGIS (Herramientas para el Uso Racional del Agua con el soporte de un GIS). Con este fin se ha diseñado primeramente un modelo de datos relacional, vinculado al propio tiempo con la información espacial. Para su implementación, se han desarrollado una serie de módulos que permiten la captura y edición de los datos, así como su depuración. Otros módulos de la aplicación HuraGIS permiten simular todos los procesos agronómicos del riego. Además, con el fin de reproducir los procesos hidráulicos se ha integrado el módulo de cálculo de EPANET. Finalmente, como herramientas de optimización se han incorporado librerías de programación lineal y de optimización heurística, como son los Algoritmos Genéticos. La metodología desarrollada se ha aplicado a un caso real de estudio, la Comunidad de Regantes de Senyera (Valencia). Para ello se tomaron los datos necesarios en campo y se introdujeron en la aplicación HuraGIS. En una primera fase se realizó un diagnóstico sobre la gestión llevada a cabo durante la campaña de riegos de 2006, media<br>Jiménez Bello, MÁ. (2008). Integración de los procesos agronómicos e hidráulicos del riego a presión en un entorno SIG para la gestión eficiente de comunidades de regantes [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/4101<br>Palancia

Els paradigmes cel·lulars, com les xarxes neuronals cel·lulars (CNN, en anglès) i els autòmats cel·lulars (CA, en anglès), són una eina excel·lent de càlcul, al ser equivalents a una màquina universal de Turing. La introducció de la màquina universal CNN (CNN-UM, en anglès) ha permès desenvolupar hardware, el nucli computacional del qual funciona segons la filosofia cel·lular; aquest hardware ha trobat aplicació en diversos camps al llarg de la darrera dècada. Malgrat això, encara hi ha moltes preguntes a obertes sobre com definir els algoritmes d'una CNN-UM i com estudiar la dinàmica dels autòmats cel·lulars. En aquesta tesis es tracten els dos problemes: primer, es demostra que es possible acotar l'espai dels algoritmes per a la CNN-UM i explorar-lo gràcies a les tècniques genètiques; i segon, s'expliquen els fonaments de l'estudi dels CA per mitjà de la dinàmica no lineal (segons la definició de Chua) i s'il·lustra com aquesta tècnica ha permès trobar resultats innovadors.<br>Los paradigmas celulares, como las redes neuronales celulares (CNN, en<br/>inglés) y los autómatas celulares (CA, en inglés), son una excelente<br/>herramienta de cálculo, al ser equivalentes a una maquina universal de<br/>Turing. La introducción de la maquina universal CNN (CNN-UM, en<br/>inglés) ha permitido desarrollar hardware cuyo núcleo computacional<br/>funciona según la filosofía celular; dicho hardware ha encontrado<br/>aplicación en varios campos a lo largo de la ultima década. Sin<br/>embargo, hay aun muchas preguntas abiertas sobre como definir los<br/>algoritmos de una CNN-UM y como estudiar la dinámica de los autómatas<br/>celular. En esta tesis se tratan ambos problemas: primero se demuestra<br/>que es posible acotar el espacio de los algoritmos para la CNN-UM y<br/>explorarlo gracias a técnicas genéticas; segundo, se explican los<br/>fundamentos del estudio de los CA por medio de la dinámica no lineal<br/>(según la definición de Chua) y se ilustra como esta técnica ha<br/>permitido encontrar resultados novedosos.<br>Cellular paradigms, like Cellular Neural Networks (CNNs) and Cellular Automata (CA) are an excellent tool to perform computation, since they are equivalent to a Universal Turing machine. The introduction of the Cellular Neural Network - Universal Machine (CNN-UM) allowed us to develop hardware whose computational core works according to the principles of cellular paradigms; such a hardware has found application in a number of fields throughout the last decade. Nevertheless, there are still many open questions about how to define algorithms for a CNN-UM, and how to study the dynamics of Cellular Automata. In this dissertation both problems are tackled: first, we prove that it is possible to bound the space of all algorithms of CNN-UM and explore it through genetic techniques; second, we explain the fundamentals of the nonlinear perspective of CA (according to Chua's definition), and we illustrate how this technique has allowed us to find novel results.

New approaches are needed to manage and analyze the enormous quantity of biological data generated by modern technologies. Existing solutions are often fragmented and uncoordinated and, thus, they require considerable bioinformatics skills from users. Three applications have been developed illustrating different strategies to help users without extensive IT knowledge to take maximum profit from their data. SNPator is an easy-to-use suite that integrates all the usual tools for genetic association studies: from initial quality control procedures to final statistical analysis. CHAVA is an interactive visual application for CNV calling from aCGH data. It presents data in a visual way that helps assessing the quality of the calling and assists in the process of optimization. Haplotype Association Pattern Analysis visually presents data from exhaustive genomic haplotype associations, so that users can recognize patterns of possible associations that cannot be detected by single-SNP tests.<br>Calen noves aproximacions per la gestió i anàlisi de les enormes quantitats de dades biològiques generades per les tecnologies modernes. Les solucions existents, sovint fragmentaries i descoordinades, requereixen elevats nivells de formació bioinformàtica. Hem desenvolupat tres aplicacions que il•lustren diferents estratègies per ajudar als usuaris no experts en informàtica a aprofitar al màxim les seves dades. SNPator és un paquet de fàcil us que integra les eines usades habitualment en estudis de associació genètica: des del control de qualitat fins les anàlisi estadístiques. CHAVA és una aplicació visual interactiva per a la determinació de CNVs a partir de dades aCGH. Presenta les dades visualment per ajudar a valorar la qualitat de les CNV predites i ajudar a optimitzar-la. Haplotype Pattern Analysis presenta dades d’anàlisi d’associació haplotípica de forma visual per tal que els usuaris puguin reconèixer patrons de associacions que no es possible detectar amb tests de SNPs individuals.

Within the great interest in the characterization of genomic structural variants (SVs) in the human genome, inversions present unique challenges and have been little studied. This thesis has developed "GRIAL", a new algorithm focused specifically in detect and map accurately inversions from paired-end mapping (PEM) data, which is the most widely used method to detect SVs. GRIAL is based on geometrical rules to cluster, merge and refine both breakpoints of putative inversions. That way, we have been able to predict hundreds of inversions in the human genome. In addition, thanks to the different GRIAL quality scores, we have been able to identify spurious PEM-patterns and their causes, and discard a big fraction of the predicted inversions as false positives. Furthermore, we have created â ˘ AIJInvFESTâ˘A˙I, the first database of human polymorphic inversions, which represents the most reliable catalogue of inversions and integrates all the associated information from multiple sources. Currently, InvFEST combines information from 30 different studies and contains 1092 candidate inversions, which are categorized based on internal scores and manual curation. Finally, the analysis of all the data generated has provided information on the genomic patterns of inversions, contributing decisively to the understanding of the map of human polymorphic inversions.<br>Dentro del estudio de las variantes estructurales en el genoma humano, las inversiones han sido las menos han consolidado sus resultados y constituye uno de los principales retos en la actualidad. Esta tesis aborda el tema a través de la implementación de "GRIAL" un nuevo algoritmo específicamente diseñado para la detección más precisa posible de las inversiones usando el mapeo de secuencias apareadas (del inglés PEM) que es el método más utilizado para estudiar la variación estructural. GRIAL se basa en reglas geométricas para agrupar los patrones de PEM que señalan un posible punto de rotura (del inglés breakpoint) de inversión, además une cada breakpoint correspondientes a inversiones independientes y refina lo más exacto posible su localización. Su uso nos permitió predecir cientos de inversiones. Un gran aporte de nuestro método es la creación de índices (del inglés score) de fiabilidad para las predicciones mediante los cuales identificamos patrones de inversión incorrectos y sus causas. Esto nos permitió filtrar nuestro resultado eliminando un gran número de predicciones posiblemente falsas. Además se creó "InvFEST", la primera base de datos especialmente dedicada a inversiones polimórficas en el genoma humano la cual representa el catálogo más fiable de inversiones, integrando además a cada inversión conocida la información asociada disponible. Actualmente InvFEST contiene (y mantiene la clasificación según el nivel de certeza) un catálogo de 1092 inversiones clasificadas, a partir de datos de 30 estudios diferentes. Finalmente el análisis de toda la información generada nos permitió describir algunos patrones de las inversiones polimórficas en el genoma humano contribuyendo de este modo a la comprensión de esta variante estructural y el estado de su información en los estudios del genoma humano.<br>Inversió genòmica

Durant l'última dècada, els sistemes classificadors (LCS) d'estil Michigan - sistemes d'aprenentatge automàtic que combinen tècniques de repartiment de crèdit i algorismes genètics (AG) per evolucionar una població de classificadors online- han renascut. Juntament amb la formulació dels sistemes de primera generació, s'han produït avenços importants en (1) el disseny sistemàtic de nous LCS competents, (2) la seva aplicació en dominis rellevants i (3) el desenvolupament d'anàlisis teòriques. Malgrat aquests dissenys i aplicacions importants, encara hi ha reptes complexos que cal abordar per comprendre millor el funcionament dels LCS i per solucionar problemes del món real eficientment i escalable.<br/>Aquesta tesi tracta dos reptes importants - compartits amb la comunitat d'aprenentatge automàtic - amb LCS d'estil Michigan: (1) aprenentatge en dominis que contenen classes estranyes i (2) evolució de models comprensibles on s'utilitzin mètodes de raonament similars als humans. L'aprenentatge de models precisos de classes estranyes és crític, doncs el coneixement clau sol quedar amagat en exemples d'aquestes, i la majoria de tècniques d'aprenentatge no són capaces de modelar la raresa amb precisió. La detecció de rareses sol ser complicat en aprenentatge online ja que el sistema d'aprenentatge rep un flux d'exemples i ha de detectar les rareses al vol. D'altra banda, l'evolució de models comprensibles és crucial en certs dominis com el mèdic, on l'expert acostuma a estar més interessat en obtenir una explicació intel·ligible de la predicció que en la predicció en si mateixa.<br/>El treball present considera dos LCS d'estil Michigan com a punt de partida: l'XCS i l 'UCS. Es pren l'XCS com a primera referència ja que és l'LCS que ha tingut més influencia fins al moment. L'UCS hereta els components principals de l'XCS i els especialitza per aprenentatge supervisat. Tenint en compte que aquesta tesi especialment se centra en problemes de classificació, l'UCS també es considera en aquest estudi. La inclusió de l'UCS marca el primer objectiu de la tesi, sota el qual es revisen un conjunt de punts que van restar oberts en el disseny del sistema. A més, per il·lustrar les diferències claus entre l'XCS i l'UCS, es comparen ambdós sistemes sobre una bateria de problemes artificials de complexitat acotada.<br/>L'estudi de com els LCS aprenen en dominis amb classes estranyes comença amb un estudi analític que descompon el problema en cinc elements crítics i deriva models per facetes per cadascun d'ells. Aquesta anàlisi s'usa com a eina per dissenyar guies de configuració que permeten que l'XCS i l'UCS solucionin problemes que prèviament no eren resolubles. A continuació, es comparen els dos LCS amb alguns dels sistemes d'aprenentatge amb més influencia en la comunitat d'aprenentatge automàtic sobre una col·lecció de problemes del món real que contenen classes estranyes. Els resultats indiquen que els dos LCS són els mètodes més robustos de la comparativa. Així mateix, es demostra experimentalment que remostrejar els conjunts d'entrenament amb l'objectiu d'eliminar la presencia de classes estranyes beneficia, en mitjana, el rendiment de les tècniques d'aprenentatge.<br/>El repte de crear models més comprensibles i d'usar mecanismes de raonament que siguin similars als humans s'aborda mitjançant el disseny d'un nou LCS per aprenentatge supervisat que combina les capacitats d'avaluació de regles online, la robustesa mostrada pels AG en problemes complexos i la representació comprensible i mètodes de raonament fonamentats proporcionats per la lògica difusa. El nou LCS, anomenat Fuzzy-UCS, s'estudia en detall i es compara amb una bateria de mètodes d'aprenentatge. Els resultats de la comparativa demostren la competitivitat del Fuzzy-UCS en termes de precisió i intel·ligibilitat dels models evolucionats. Addicionalment, s'usa Fuzzy-UCS per extreure models de classificació acurats de grans volums de dades, exemplificant els avantatges de l'arquitectura d'aprenentatge online del Fuzzy-UCS.<br/>En general, les observacions i avenços assolits en aquesta tesi contribueixen a augmentar la comprensió del funcionament dels LCS i en preparar aquests tipus de sistemes per afrontar problemes del món real de gran complexitat. Finalment, els resultats experimentals ressalten la robustesa i competitivitat dels LCS respecte a altres mètodes d'aprenentatge, encoratjant el seu ús per tractar nous problemes del món real.<br>Durante la última década, los sistemas clasificadores (LCS) de estilo Michigan - sistemas de aprendizaje automático que combinan técnicas de repartición de crédito y algoritmos genéticos (AG) para evolucionar una población de clasificadores online - han renacido. Juntamente con la formulación de los sistemas de primera generación, se han producido avances importantes en (1) el diseño sistemático de nuevos LCS competentes, (2) su aplicación en dominios relevantes y (3) el desarrollo de análisis teóricos. Pese a eso, aún existen retos complejos que deben ser abordados para comprender mejor el funcionamiento de los LCS y para solucionar problemas del mundo real escalable y eficientemente.<br/>Esta tesis trata dos retos importantes - compartidos por la comunidad de aprendizaje automático - con LCS de estilo Michigan: (1) aprendizaje en dominios con clases raras y (2) evolución de modelos comprensibles donde se utilicen métodos de razonamiento similares a los humanos. El aprendizaje de modelos precisos de clases raras es crítico pues el conocimiento clave suele estar escondido en ejemplos de estas clases, y la mayoría de técnicas de aprendizaje no son capaces de modelar la rareza con precisión. El modelado de las rarezas acostumbra a ser más complejo en entornos de aprendizaje online, pues el sistema de aprendizaje recibe un flujo de ejemplos y debe detectar las rarezas al vuelo. La evolución de modelos comprensibles es crucial en ciertos dominios como el médico, donde el experto está más interesado en obtener una explicación inteligible de la predicción que en la predicción en sí misma.<br/>El trabajo presente considera dos LCS de estilo Michigan como punto de partida: el XCS y el UCS. Se toma XCS como primera referencia debido a que es el LCS que ha tenido más influencia hasta el momento. UCS es un diseño reciente de LCS que hereda los componentes principales de XCS y los especializa para aprendizaje supervisado. Dado que esta tesis está especialmente centrada en problemas de clasificación automática, también se considera UCS en el estudio. La inclusión de UCS marca el primer objetivo de la tesis, bajo el cual se revisan un conjunto de aspectos que quedaron abiertos durante el diseño del sistema. Además, para ilustrar las diferencias claves entre XCS y UCS, se comparan ambos sistemas sobre una batería de problemas artificiales de complejidad acotada.<br/>El estudio de cómo los LCS aprenden en dominios con clases raras empieza con un estudio analítico que descompone el problema en cinco elementos críticos y deriva modelos por facetas para cada uno de ellos. Este análisis se usa como herramienta para diseñar guías de configuración que permiten que XCS y UCS solucionen problemas que previamente no eran resolubles. A continuación, se comparan los dos LCS con algunos de los sistemas de aprendizaje de mayor influencia en la comunidad de aprendizaje automático sobre una colección de problemas del mundo real que contienen clases raras.<br/>Los resultados indican que los dos LCS son los métodos más robustos de la comparativa. Además, se demuestra experimentalmente que remuestrear los conjuntos de entrenamiento con el objetivo de eliminar la presencia de clases raras beneficia, en promedio, el rendimiento de los métodos de aprendizaje automático incluidos en la comparativa.<br/>El reto de crear modelos más comprensibles y usar mecanismos de razonamiento que sean similares a los humanos se aborda mediante el diseño de un nuevo LCS para aprendizaje supervisado que combina las capacidades de evaluación de reglas online, la robustez mostrada por los AG en problemas complejos y la representación comprensible y métodos de razonamiento proporcionados por la lógica difusa. El sistema que resulta de la combinación de estas ideas, llamado Fuzzy-UCS, se estudia en detalle y se compara con una batería de métodos de aprendizaje altamente reconocidos en el campo de aprendizaje automático. Los resultados de la comparativa demuestran la competitividad de Fuzzy-UCS en referencia a la precisión e inteligibilidad de los modelos evolucionados. Adicionalmente, se usa Fuzzy-UCS para extraer modelos de clasificación precisos de grandes volúmenes de datos, ejemplificando las ventajas de la arquitectura de aprendizaje online de Fuzzy-UCS.<br/>En general, los avances y observaciones proporcionados en la tesis presente contribuyen a aumentar la comprensión del funcionamiento de los LCS y a preparar estos tipos de sistemas para afrontar problemas del mundo real de gran complejidad. Además, los resultados experimentales resaltan la robustez y competitividad de los LCS respecto a otros métodos de aprendizaje, alentando su uso para tratar nuevos problemas del mundo real.<br>During the last decade, Michigan-style learning classifier systems (LCSs) - genetic-based machine learning (GBML) methods that combine apportionment of credit techniques and genetic algorithms (GAs) to evolve a population of classifiers online - have been enjoying a renaissance. Together with the formulation of first generation systems, there have been crucial advances in (1) systematic design of new competent LCSs, (2) applications in important domains, and (3) theoretical analyses for design. Despite these successful designs and applications, there still remain difficult challenges that need to be addressed to increase our comprehension of how LCSs behave and to scalably and efficiently solve real-world problems.<br/>The purpose of this thesis is to address two important challenges - shared by the machine learning community - with Michigan-style LCSs: (1) learning from domains that contain rare classes and (2) evolving highly legible models in which human-like reasoning mechanisms are employed. Extracting accurate models from rare classes is critical since the key, unperceptive knowledge usually resides in the rarities, and many traditional learning techniques are not able to model rarity accurately. Besides, these difficulties are increased in online learning, where the learner receives a stream of examples and has to detect rare classes on the fly. Evolving highly legible models is crucial in some domains such as medical diagnosis, in which human experts may be more interested in the explanation of the prediction than in the prediction itself.<br/>The contributions of this thesis take two Michigan-style LCSs as starting point: the extended classifier system (XCS) and the supervised classifier system (UCS). XCS is taken as the first reference of this work since it is the most influential LCS. UCS is a recent LCS design that has inherited the main components of XCS and has specialized them for supervised learning. As this thesis is especially concerned with classification problems, UCS is also considered in this study. Since UCS is still a young system, for which there are several open issues that need further investigation, its learning architecture is first revised and updated. Moreover, to illustrate the key differences between XCS and UCS, the behavior of both systems is compared % and show that UCS converges quickly than XCS on a collection of boundedly difficult problems.<br/>The study of learning from rare classes with LCSs starts with an analytical approach in which the problem is decomposed in five critical elements, and facetwise models are derived for each element. The analysis is used as a tool for designing configuration guidelines that enable XCS and UCS to solve problems that previously eluded solution. Thereafter, the two LCSs are compared with several highly-influential learners on a collection of real-world problems with rare classes, appearing as the two best techniques of the comparison. Moreover, re-sampling the training data set to eliminate the presence of rare classes is demonstrated to benefit, on average, the performance of LCSs.<br/>The challenge of building more legible models and using human-like reasoning mechanisms is addressed with the design of a new LCS for supervised learning that combines the online evaluation capabilities of LCSs, the search robustness over complex spaces of GAs, and the legible knowledge representation and principled reasoning mechanisms of fuzzy logic. The system resulting from this crossbreeding of ideas, referred to as Fuzzy-UCS, is studied in detail and compared with several highly competent learning systems, demonstrating the competitiveness of the new architecture in terms of the accuracy and the interpretability of the evolved models. In addition, the benefits provided by the online architecture are exemplified by extracting accurate classification models from large data sets.<br/>Overall, the advances and key insights provided in this thesis help advance our understanding of how LCSs work and prepare these types of systems to face increasingly difficult problems, which abound in current industrial and scientific applications. Furthermore, experimental results highlight the robustness and competitiveness of LCSs with respect to other machine learning techniques, which encourages their use to face new challenging real-world applications.

A mesura que Internet i les xarxes IP s'han anat integrant dins la societat i les corporacions, han anat creixent les expectatives de nous serveis convergents així com les expectatives de qualitat en les comunicacions. Les Next Generation Networks (NGN) donen resposta a les noves necessitats i representen el nou paradigma d'Internet a partir de la convergència IP. Un dels aspectes menys desenvolupats de les NGN és el control de la Qualitat del Servei (QoS), especialment crític en les comunicacions multimèdia a través de xarxes heterogènies i/o de diferents operadors. A més a més, les NGN incorporen nativament el protocol IPv6 que, malgrat les deficiències i esgotament d'adreces IPv4, encara no ha tingut l'impuls definitiu.<br/>Aquesta tesi està enfocada des d'un punt de vista pràctic. Així doncs, per tal de poder fer recerca sobre xarxes de proves (o testbeds) que suportin IPv6 amb garanties de funcionament, es fa un estudi en profunditat del protocol IPv6, del seu grau d'implementació i dels tests de conformància i interoperabilitat existents que avaluen la qualitat d'aquestes implementacions. A continuació s'avalua la qualitat de cinc sistemes operatius que suporten IPv6 mitjançant un test de conformància i s'implementa el testbed IPv6 bàsic, a partir del qual es farà la recerca, amb la implementació que ofereix més garanties.<br/>El QoS Broker és l'aportació principal d'aquesta tesi: un marc integrat que inclou un sistema automatitzat per gestionar el control de la QoS a través de sistemes multi-domini/multi-operador seguint les recomanacions de les NGN. El sistema automatitza els mecanismes associats a la configuració de la QoS dins d'un mateix domini (sistema autònom) mitjançant la gestió basada en polítiques de QoS i automatitza la negociació dinàmica de QoS entre QoS Brokers de diferents dominis, de forma que permet garantir QoS extrem-extrem sense fissures. Aquesta arquitectura es valida sobre un testbed de proves multi-domini que utilitza el mecanisme DiffServ de QoS i suporta IPv6.<br/>L'arquitectura definida en les NGN permet gestionar la QoS tant a nivell 3 (IP) com a nivell 2 (Ethernet, WiFi, etc.) de forma que permet gestionar també xarxes PLC. Aquesta tesi proposa una aproximació teòrica per aplicar aquesta arquitectura de control, mitjançant un QoS Broker, a les noves xarxes PLC que s'estan acabant d'estandarditzar, i discuteix les possibilitats d'aplicació sobre les futures xarxes de comunicació de les Smart Grids.<br/>Finalment, s'integra en el QoS Broker un mòdul per gestionar l'enginyeria del tràfic optimitzant els dominis mitjançant tècniques de intel·ligència artificial. La validació en simulacions i sobre un testbed amb routers Cisco demostra que els algorismes genètics híbrids són una opció eficaç en aquest camp.<br/>En general, les observacions i avenços assolits en aquesta tesi contribueixen a augmentar la comprensió del funcionament de la QoS en les NGN i a preparar aquests sistemes per afrontar problemes del món real de gran complexitat.<br>A medida que Internet y las redes IP se han ido integrando dentro de la sociedad y las corporaciones, han ido creciendo las expectativas de nuevos servicios convergentes así como las expectativas de calidad en las comunicaciones. Las Next Generation Networks (NGN) dan respuesta a las nuevas necesidades y representan el nuevo paradigma de Internet a partir de la convergencia IP. Uno de los aspectos menos desarrollados de las NGN es el control de la Calidad del Servicio (QoS), especialmente crítico en las comunicaciones multimedia a través de redes heterogéneas y/o de diferentes operadores. Además, las NGN incorporan nativamente el protocolo IPv6 que, a pesar de las deficiencias y agotamiento de direcciones IPv4, aún no ha tenido el impulso definitivo.<br/>Esta tesis está enfocada desde un punto de vista práctico. Así pues, con tal de poder hacer investigación sobre redes de prueba (o testbeds) que suporten IPv6 con garantías de funcionamiento, se hace un estudio en profundidad del protocolo IPv6, de su grado de implementación y de los tests de conformancia e interoperabilidad existentes que evalúan la calidad de estas implementaciones. A continuación se evalua la calidad de cinco sistemas operativos que soportan IPv6 mediante un test de conformancia y se implementa el testbed IPv6 básico, a partir del cual se realizará la investigación, con la implementación que ofrece más garantías.<br/>El QoS Broker es la aportación principal de esta tesis: un marco integrado que incluye un sistema automatitzado para gestionar el control de la QoS a través de sistemas multi-dominio/multi-operador siguiendo las recomendaciones de las NGN. El sistema automatiza los mecanismos asociados a la configuración de la QoS dentro de un mismo dominio (sistema autónomo) mediante la gestión basada en políticas de QoS y automatiza la negociación dinámica de QoS entre QoS brokers de diferentes dominios, de forma que permite garantizar QoS extremo-extremo sin fisuras. Esta arquitectura se valida sobre un testbed de pruebas multi-dominio que utiliza el mecanismo DiffServ de QoS y soporta IPv6. <br/>La arquitectura definida en las NGN permite gestionar la QoS tanto a nivel 3 (IP) o como a nivel 2 (Ethernet, WiFi, etc.) de forma que permite gestionar también redes PLC. Esta tesis propone una aproximación teórica para aplicar esta arquitectura de control, mediante un QoS Broker, a las noves redes PLC que se están acabando de estandardizar, y discute las posibilidades de aplicación sobre las futuras redes de comunicación de las Smart Grids.<br/>Finalmente, se integra en el QoS Broker un módulo para gestionar la ingeniería del tráfico optimizando los dominios mediante técnicas de inteligencia artificial. La validación en simulaciones y sobre un testbed con routers Cisco demuestra que los algoritmos genéticos híbridos son una opción eficaz en este campo.<br/>En general, las observaciones y avances i avances alcanzados en esta tesis contribuyen a augmentar la comprensión del funcionamiento de la QoS en las NGN y en preparar estos sistemas para afrontar problemas del mundo real de gran complejidad.<br>The steady growth of Internet along with the IP networks and their integration into society and corporations has brought with it increased expectations of new converged services as well as greater demands on quality in communications. The Next Generation Networks (NGNs) respond to these new needs and represent the new Internet paradigm from the IP convergence. One of the least developed aspects in the NGNs is the Quality of Service (QoS) control, which is especially critical in the multimedia communication through heterogeneous networks and/or different operators. Furthermore, the NGNs natively incorporate the IPv6 protocol which, despite its shortcomings and the depletion of IPv4 addresses has not been boosted yet.<br/>This thesis has been developed with a practical focus. Therefore, with the aim of carrying out research over testbeds supporting the IPv6 with performance guarantees, an in-depth study of the IPv6 protocol development has been conducted and its degree of implementation and the existing conformance and interoperability tests that evaluate these implementations have been studied. Next, the quality of five implementations has been evaluated through a conformance test and the basic IPv6 testbed has been implemented, from which the research will be carried out. <br/>The QoS Broker is the main contribution to this thesis: an integrated framework including an automated system for QoS control management through multi-domain/multi-operator systems according to NGN recommendations. The system automates the mechanisms associated to the QoS configuration inside the same domain (autonomous system) through policy-based management and automates the QoS dynamic negotiation between peer QoS Brokers belonging to different domains, so it allows the guarantee of seamless end-to-end QoS. This architecture is validated over a multi-domain testbed which uses the QoS DiffServ mechanism and supports IPv6.<br/>The architecture defined in the NGN allows QoS management at level 3 (IP) as well as at level 2 (e.g. Ethernet, WiFi) so it also facilitates the management of PLC networks. Through the use of a QoS Broker, this thesis proposes a theoretical approach for applying this control architecture to the newly standardized PLC networks, and discusses the possibilities of applying it over the future communication networks of the Smart Grids.<br/>Finally, a module for managing traffic engineering which optimizes the network domains through artificial intelligence techniques is integrated in the QoS Broker. The validations by simulations and over a Cisco router testbed demonstrate that hybrid genetic algorithms are an effective option in this area.<br/>Overall, the advances and key insights provided in this thesis help advance our understanding of QoS functioning in the NGNs and prepare these systems to face increasingly complex problems, which abound in current industrial and scientific applications.

Real life is full of multi-class decision tasks. In the Pattern Recognition field, several method- ologies have been proposed to deal with binary problems obtaining satisfying results in terms of performance. However, the extension of very powerful binary classifiers to the multi-class case is a complex task. The Error-Correcting Output Codes framework has demonstrated to be a very powerful tool to combine binary classifiers to tackle multi-class problems. However, most of the combinations of binary classifiers in the ECOC framework overlook the underlay- ing structure of the multi-class problem. In addition, is still unclear how the Error-Correction of an ECOC design is distributed among the different classes. In this dissertation, we are interested in tackling critic problems of the ECOC framework, such as the definition of the number of classifiers to tackle a multi-class problem, how to adapt the ECOC coding to multi-class data and how to distribute error-correction among different pairs of categories. In order to deal with this issues, this dissertation describes several proposals. 1) We define a new representation for ECOC coding matrices that expresses the pair-wise codeword separability and allows for a deeper understanding of how error-correction is distributed among classes. 2) We study the effect of using a logarithmic number of binary classifiers to treat the multi-class problem in order to obtain very efficient models. 3) In order to search for very compact ECOC coding matrices that take into account the distribution of multi-class data we use Genetic Algorithms that take into account the constraints of the ECOC framework. 4) We propose a discrete factorization algorithm that finds an ECOC configuration that allocates the error-correcting capabilities to those classes that are more prone to errors. The proposed methodologies are evaluated on different real and synthetic data sets: UCI Machine Learning Repository, handwriting symbols, traffic signs from a Mobile Mapping System, and Human Pose Recovery. The results of this thesis show that significant perfor- mance improvements are obtained on traditional coding ECOC designs when the proposed ECOC coding designs are taken into account.<br>En la vida cotidiana las tareas de decisión multi-clase surgen constantemente. En el campo de Reconocimiento de Patrones muchos métodos de clasificación binaria han sido propuestos obteniendo resultados altamente satisfactorios en términos de rendimiento. Sin embargo, la extensión de estos sofisticados clasificadores binarios al contexto multi-clase es una tarea compleja. En este ámbito, las estrategias de Códigos Correctores de Errores (CCEs) han demostrado ser una herramienta muy potente para tratar la combinación de clasificadores binarios. No obstante, la mayoría de arquitecturas de combinación de clasificadores binarios negligen la estructura del problema multi-clase. Sin embargo, el análisis de la distribución de corrección de errores entre clases es aún un problema abierto. En esta tesis doctoral, nos centramos en tratar problemas críticos de los códigos correctores de errores; la definición del número de clasificadores necesarios para tratar un problema multi-clase arbitrario; la adaptación de los problemas binarios al problema multi-clase y cómo distribuir la corrección de errores entre clases. Para dar respuesta a estas cuestiones, en esta tesis doctoral describimos varias propuestas. 1) Definimos una nueva representación para CCEs que expresa la separabilidad entre pares de códigos y nos permite una mejor comprensión de cómo se distribuye la corrección de errores entre distintas clases. 2) Estudiamos el efecto de usar un número logarítmico de clasificadores binarios para tratar el problema multi-clase con el objetivo de obtener modelos muy eficientes. 3) Con el objetivo de encontrar modelos muy eficientes que tienen en cuenta la estructura del problema multi-clase utilizamos algoritmos genéticos que tienen en cuenta las restricciones de los ECCs. 4) Pro- ponemos un algoritmo de factorización de matrices discreta que encuentra ECCs con una configuración que distribuye corrección de error a aquellas categorías que son más propensas a tener errores. Las metodologías propuestas son evaluadas en distintos problemas reales y sintéticos como por ejemplo: Repositorio UCI de Aprendizaje Automático, reconocimiento de símbolos escritos, clasificación de señales de tráfico y reconocimiento de la pose humana. Los resultados obtenidos en esta tesis muestran mejoras significativas en rendimiento comparados con los diseños tradiciones de ECCs cuando las distintas propuestas se tienen en cuenta.