Search

188 p., This PhD focuses on the application of machine learning techniques for behaviourmodelling in different types of websites. Using data mining techniques two aspects whichare problematic and difficult to solve have been addressed: getting the system todynamically adapt to possible changes of user preferences, and to try to extract theinformation necessary to ensure the adaptation in a transparent manner for the users,without infringing on their privacy. The work in question combines information of differentnature such as usage information, content information and website structure and usesappropriate web mining techniques to extract as much knowledge as possible from thewebsites. The extracted knowledge is used for different purposes such as adaptingwebsites to the users through proposals of interesting links, so that the users can get therelevant information more easily and comfortably; for discovering interests or needs ofusers accessing the website and to inform the service providers about it; or detectingproblems during navigation.Systems have been successfully generated for two completely different fields: thefield of tourism, working with the website of bidasoa turismo (www.bidasoaturismo.com)and, the field of disabled people, working with discapnet website (www.discapnet.com)from ONCE/Tecnosite foundation.

190 p., El diseño y la verificación de algoritmos y aplicaciones distribuidas tolerantes a fallos son tareas complejas. Para estudiarlas, se han identificado varios problemas estándar. Uno de los más importantes es el Consenso, el problema de varios procesos intentando acordar una decisión común. El problema del Consenso no puede ser resuelto determinísticamente en sistemas asíncronos donde los procesos pueden fallar. Para salvar esta imposibilidad, Chandra y Toueg propusieron los detectores no fiables de fallos. En esta tesis estudiamos, por primera vez, el detector no fiable de fallos Omega en el modelo de sistema de fallo-y-recuperación (Crash-Recovery). Más concretamente nos centramos en el diseño de algoritmos que implementan dicho detector de fallos en modelos de sincronía parcial donde los procesos pueden caer y luego recuperarse, para los que se ha demostrado que el Consenso se puede resolver. En primer lugar redefinimos el detector de fallos Omega para el modelo de fallo-y-recuperación. Definimos los detectores de fallos Omegacr1 y Omegacr2 para sistemas sin y con memoria estable respectivamente. Seguidamente, proponemos un conjunto de ocho algoritmos distribuidos que funcionan en modelos de sistema de fallo-y-recuperación (ligeramente) diferentes. Respecto a la eficiencia, se han implementado dos algoritmos eficientes en cuanto a comunicación (communication-efficient), uno para Omegacr1 y el otro para Omegacr2. Además, proponemos dos algoritmos que implementan detectores de fallos Eventually Perfect, <>P. En el modelo de fallo-y-recuperación no es posible implementar un detector de fallos de la clase <>P. Por ello, se han definido e implementado los detectores de fallos <>Pcr y <>Pk-cr, que satisfacen propiedades más débiles. Los algoritmos están basados en el uso de un servicio de elección de líder, que es proporcionado por el detector de fallos Omegacr2. Finalmente, proponemos tres algoritmos de elección de agregador y agregación de datos para redes de sensores inalámbricas, construidos sobre nuestras implementaciones del detector de fallos Omegacr2.

131 p.: graf. [ES]La Computación Evolutiva es una disciplina que se caracteriza por crear un conjunto de posibles soluciones y hacerlas evolucionar generación a generación con el propósito de resolver problemas de optimización. Ejemplos de paradigmas de computación evolutiva ampliamente reconocidos son los Algoritmos Genéticos (Genetic Algorithms,GAs) y los Algoritmos de Estimación de las Distribuciones (Estimation Distribution Algorithms, EDAs). La principal diferencia entre estos modelos está en la forma de mejorar el conjunto de soluciones en cada generación. En los GAs, la evolución se basa en la utilización de operadores de cruce y mutacion, sin expresar explicitamente las caracteristicas de los individuos seleccionados dentro de una poblacion. Los EDAs tienen en cuenta estas caracteristicas explicitas al considerar las interdependencias entre las diferentes variables que representan a un individuo y aprender el modelo grafico probabilistico que las representa. Aunque en la mayoria de los problemas de optimizacion los EDAs obtienen muy buenos resultados, es posible encontrar aspectos de estos algoritmos susceptibles de mejora con el ¯n de aumentar el rendimiento de este metodo. En este sentido, cabe destacar la utilizacion del valor obtenido por cada individuo al ser evaluado. Mediante la funcion de evaluacion o funcion objetivo, a cada individuo se le calcula un valor que indica como de proximo se encuentra ese individuo del optimo. Los EDAs utilizan este valor para seleccionar a aquellos individuos que se utilizarian para crear el modelo grafico probabilistico. Sin embargo, los EDAs no utilizan toda la informacion que proporciona la funcion objetivo. Es decir, a la hora de obtener el modelo grafico probabilistico, solo tienen en cuenta el valor de las variables predictoras de los individuos seleccionados, considerandolos todos iguales. Esto provoca que individuos con diferente valor de funcion objetivo sean, si han sido seleccionados, considerados iguales por los EDAs a la hora de obtener el modelo que se utilizaria para generar nuevos individuos. Este paso es fundamental para la convergencia del proceso, ya que el modelo grafico probabilistico es la forma que utilizan los EDAs para representar la informacion de los datos analizados. Tambien es importante analizar la manera mas apropiada de representacion de un problema para su resolucion mediante EDAs. Aunque este aspecto esta directamente ligado a cada problema particular, siempre es posible encontrar diferentes formas de representar las caracteristicas que mejor definan las diferencias entre posibles soluciones. Elegir una u otra forma de afrontar el problema puede resultar muy importante a la hora de resolverlo. Ademas, cada representacion necesita su funcion de evaluacion correspondiente, lo cual nos lleva a elegir la funcion objetivo mas adecuada para una mejor y mas rapida convergencia del proceso. En esta tesis se analiza la importancia de estos dos aspectos. Pensando en añadir informacion sobre la funcion objetivo en el proceso de aprendizaje, se ha desarrollado un nuevo metodo de optimizacion que funciona de manera similar a los EDAs, pero que utiliza clasificadores Bayesianos en el proceso de evolucion. De esta forma, los individuos se clasifican segun el valor obtenido en la funcion objetivo y utilizamos esta informacion para, a traves de clasificadores Bayesianos, obtener el modelo grafico probabilistico. A este nuevo metodo se le ha llamado Evolutionary Bayesian Classi¯er- based Optimization Algorithms (EBCOA). Para analizar la importancia que puede tener, en el proceso de evolucion de los EDAs, utilizar una determinada forma de representacion del problema, es necesario trabajar con un ejemplo concreto que resulte realmente completo y que pueda utilizarse para formalizar gran cantidad de casos practicos. Teniendo en cuenta esto, nos hemos centrado en el problema de la satisfactibilidad (SAT). Este problema es uno de los mas importantes en la teoria computacional, ya que representa un modelo generico mediante el cual se pueden formalizar gran cantidad de casos practicos en diferentes campos de investigacion, sobre todo problemas de decision tales como diseño, sintesis y verifiacion de circuitos integrados, optimizacion y planifiacion de tareas. Ademas, este problema es NP-completo. La mayor parte de los trabajos realizados para resolver el SAT estan basados en metodos exactos y completos. Ultimamente tambien se han utilizado algoritmos evolutivos en su resolucion, principalmente algoritmos geneticos. Basandonos en los trabajos realizados en esta linea, se analizan nuevas formas de representacion, buscando en cada caso, la funcion objetivo adecuada y estudiando el comportamiento de los EDAs en los diferentes casos.---------------------------------------------------------------------------------------------- [EU]Konputazio ebolutiboa optimizazio diziplina bat da non optimizazio problemak ebazteko soluzio posibleen azpimultzo baten bidez hurrengo soluzioen generazio bat sortzen den. Ezagunen diren teknikak arlo honen barruan Algoritmo genetikoak (Genetic Algorithms, GAs) eta Estimation Distribution Algorithms (EDA) izenekoak ditugu. Bien arteko desberdintasun nagusiena eboluzionatzeko prozeduran datza, non GAetan gurutzaketa eta mutazio tekniketan oinarritzen den eta EDAetan eredu gra¯ko probabilistikoetan oinarritutako tekniketan. Nahiz EDAk hainbat optimizazio problemetan emaitza onak lortzen dituztela frogatu bada ere, hobekuntzarako hainbat esparru existitzen dira. Adibidez, EDAen kasuan populazio bakoitzean eboluziorako aukeratzen diren indibiduoen aldagaien balioak kontsideratzen dira, baina indibiduoen arteko ¯tness edo soluzioaren egokitasun maila ez da normalean kontuan hartzen eta indibiduo guztiak berdin bezala tratatzen dira eredu probabilistikoa sortzeko orduan. Ezaugarri hau inportantea da eredu hau erabiltzen baita aldagai guztien arteko menpekotasunak irudikatzeko, hau izanik eboluzioa bideratzeko mekanismo nagusiena. Bestalde, EDAen eraginkortasunari dagokionez, optimizazio problemaren adierazpen modua oso inportantea da. Ezaugarri hau optimizazio problema bakoitzeko desberdina bada ere, egokiena da aukeratutako problemaren adierazpideak hoberen erakustea soluzio posible desberdinen arteko desberdintasun nagusienak. Problemaren indibiduoen adierazpenaz gain, egokitasun funtzioaren de¯nizio egokiena ere aukeratu beharra dago eboluzio prozedura erabakigarria izan dadin. Tesi honetan bi ezaugarri hauen garrantzia aztertzen da EDAen eraginkortasun orokorrean duten eragina hobetzeko. Egokitze funtzioaren balioaren esangarritasuna hobetzeko helburuari dagokionez, tesiaren emaitzetako bat izan da EDAen antzeko optimizazio paradigma berri bat de¯nitu izatea, problemaren ikasketa fasea aldatuz. Gure proposamen berri honen arabera, populazio bakoitzeko indibiduoak beren egokitze funtzioaren balioaren arabera sailkatzen dira, eta orden hau jarraituz klasi¯katzaile Bayesiar formako eredu gra¯ko probabilistiko bat eraikitzen da. Teknika berri honi Evolutionary Bayesian Classi¯er-based Optimization Algorithms (EBCOA) deitu dio- gu. Azkenik, indibiduoen adierazpenaren eragina aztertzeko asmoz, EDAen eraginkor- tasun orokorrean dagokionez, optimizazio problema konkretu bat aukeratu dugu, SAT izenekoa (satis¯ability). Hau konputazio teoriaren barnean oso ezaguna den eta NP-osoa den optimizazio problema multzo bat da, zeinak problemen adierazpen eredu orokor bat aurkezten duen ikerketa kasu praktikoei erantzun bat eman ahal izateko, hots, erabakiak hartzeko problemak, zirkuitu integratuen diseinu eta frogaketa, optimizazioa eta atazen plani¯kazioa. Publikatuta dauden SATerako konputazio ebolutiboaren tekniken ikerketa lanetan oinarrituz, SAT optimizazio problemen indibiduo adierazpen desberdinak aztertu ditugu tesi honetan, eta hauekin batera egokien zaizkien ¯tness funtzio optimoenak zein diren aztertuz EDAentzako eraginkortasun hoberena lortzeko asmoz.---------------------------------------------------------------------------------------------- [EN]Evolutionary computation is a discipline characterised by creating a set of possible solutions and to make it evolve generation after generation in order to solve optimization problems. Examples of broadly known evolutionary computation paradigms are Genetic Algorithms (GAs) and Estimation Distribution Algorithms (EDAs). The main di®erence between these models is the evolution process: In GAs this is based on crossover and mutation operators, without explicit expression of the characteristics of selected individuals within the population. EDAs take these explicit characteristics into account by considering the interdependencies between the variables that form an individual and by learning a probabilistic graphical model that represents them. Even if EDAs show good results in many optimization problems, there are many aspects for improvement in order to enhance their performance. One of such aspects is to take into consideration the ¯tness of each individual when it is evaluated using the ¯tness function, which assigns a value to each individual expressing how close it is from the optimum. EDAs use this value to select those individuals that will be considered for creating the probabilistic graphical model. However, EDAs only consider the values of predictor variables of selected values, considering them all as equally valid when Teresa Miquelez, Tesis Doctoral, 2010 vii learning the model to generate the new population. This step is essential since the probabilistic graphical model is used by EDAs to represent all dependencies between values. Secondly, it is important to analyse the most appropriate way to represent a problem for its solving by EDAs. Even if this aspect is fully dependent on each particular optimization problem, the best choice is to try to best show the di®erences between the di®erent solutions. The way in which the problem is represented has an important in°uence on the performance of EDAs. Furthermore, each individual representation of the problem requires a corresponding ¯tness function to be de¯ned, which leads us to the need to choose the most appropriated ¯tness function for a better convergence process. This thesis analyses the importance of these two aspects in the overall performance. With the aim of adding more information to the ¯tness function in the learning process, we have developed a new optimization method that works in a similar way as EDAs but using Bayesian classi¯ers for the learning step. Following this, individuals are classi¯ed according to their ¯tness and this information is used for building a probabilistic graphical model in the form of a Bayesian classi¯er. We call this new method Evolutionary Bayesian Classi¯er-based Optimization Algorithms (EBCOA). Finally, in order to study the importance of a concrete individual representation in EDA's performance, we choose as a concrete optimization problem the satis¯ability one (SAT). This NP-complete problem is broadly known in computational theory since it represents a generic model through which diverse research practical cases can be formalised using a generic representation, mainly decision making problems such as synthesis and verification of integrated circuits, optimization and task planning. Based on published works using evolutionary computation techniques for SAT, di®erent representation ways are presented and analysed in order to investigate which is the best problem representation and ¯tness function to improve the performance of EDAs.