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