Avances en algoritmos de estimación de distribucionesalternativas en el aprendizaje y representación de problemas

Resumen

La Computación Evolutiva es una disciplina que se caracteriza por crear un conjun- to de posibles soluciones y hacerlas evolucionar generación a generación con el propósi- to 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 tie- nen 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 mode- lo 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 pro- babilistico, 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 solucio- nes. 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 Teresa Miquelez, Tesis Doctoral, 2010 v individuos se clasifian 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. Laburpena 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 (Gene- tic 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 pro- babilistikoetan oinarritutako tekniketan. Nahiz EDAk hainbat optimizazio problemetan emaitza onak lortzen dituztela fro- gatu bada ere, hobekuntzarako hainbat esparru existitzen dira. Adibidez, EDAen ka- suan populazio bakoitzean eboluziorako aukeratzen diren indibiduoen aldagaien ba- lioak kontsideratzen dira, baina indibiduoen arteko ¯tness edo soluzioaren egokitasun maila ez da normalean kontuan hartzen eta indibiduo guztiak berdin bezala tratat- zen 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 adieraz- pen modua oso inportantea da. Ezaugarri hau optimizazio problema bakoitzeko des- berdina bada ere, egokiena da aukeratutako problemaren adierazpideak hoberen era- kustea soluzio posible desberdinen arteko desberdintasun nagusienak. Problemaren vi Teresa Miquelez, Tesis Doctoral, 2010 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 egokit- ze 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 oro- kor bat aurkezten duen ikerketa kasu praktikoei erantzun bat eman ahal izateko, hots, erabakiak hartzeko problemak, zirkuitu integratuen diseinu eta frogaketa, optimiza- zioa 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. Summary 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 opti- mization 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 pro- blem 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 performan- ce. 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 pro- babilistic 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¯abi- lity 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 veri¯cation of integrated circuits, optimization and task planning. Based on published works using evolutionary computation techniques for SAT, di®erent re- presentation ways are presented and analysed in order to investigate which is the best problem representation and ¯tness function to improve the performance of EDAs.