[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.

[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.----------------------------------------------------------------------------------------------