{"id":105533,"date":"2010-10-12T00:00:00","date_gmt":"2010-10-12T00:00:00","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/mejora-de-algoritmos-evolutivos-en-problemas-de-busqueda-de-arboles-optimos-nuevos-operadores-sobre-la-codificacion-dandelion\/"},"modified":"2010-10-12T00:00:00","modified_gmt":"2010-10-12T00:00:00","slug":"mejora-de-algoritmos-evolutivos-en-problemas-de-busqueda-de-arboles-optimos-nuevos-operadores-sobre-la-codificacion-dandelion","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/inteligencia-artificial\/mejora-de-algoritmos-evolutivos-en-problemas-de-busqueda-de-arboles-optimos-nuevos-operadores-sobre-la-codificacion-dandelion\/","title":{"rendered":"Mejora de algoritmos evolutivos en problemas de b\u00fasqueda de \u00e1rboles \u00f3ptimos: nuevos operadores sobre la codificaci\u00f3n dandelion"},"content":{"rendered":"<h2>Tesis doctoral de <strong> \u00e1ngel Manuel P\u00e9rez Bellido <\/strong><\/h2>\n<p>Esta tesis doctoral aborda la optimizaci\u00f3n de grafos con forma de \u00e1rbol, ampliamente utilizados actualmente para modelar diferentes tipos de estructuras, dada la utilidad que presentan sus caracter\u00edsticas. Concretamente, recurriremos al empleo de m\u00e9todos evolutivos como herramienta clave para afrontar la resoluci\u00f3n de distintos tipos de problemas de optimizaci\u00f3n que en este contexto se plantean. Actualmente existen varios procedimientos que permiten una adecuada representaci\u00f3n de esta clase de grafos, permitiendo a dichos algoritmos manejarlos adecuadamente durante el proceso de optimizaci\u00f3n que desarrollan. Algunos ejemplos de estas codificaciones son pr\u00ed\u00bcfer, blob, neville y en especial dandelion, cuyas valiosas propiedades han convertido dicho m\u00e9todo en el m\u00e1s empleado con este fin. A pesar de la significativa capacidad que estas representaciones poseen para alcanzar buenos resultados ante la mayor\u00eda de escenarios, existen problemas especialmente dif\u00edciles en que su comportamiento no resulta tan satisfactorio como cabr\u00eda esperar. Ante estas situaciones, la mejora de las codificaciones anteriormente mencionadas resulta necesaria a fin de proveer a estos m\u00e9todos evolutivos de representaciones suficientemente vers\u00e1tiles, y consecuentemente, obtener los resultados deseados. Dependiendo del problema concreto que deba abordarse, los mencionados m\u00e9todos deber\u00e1n resultar modificados en un grado diferente.  un primer ejemplo de estos problemas especialmente dif\u00edciles de resolver se puede encontrar en el dise\u00f1o de sistemas de respuesta de voz interactiva, que se han convertido en un componente fundamental de los centros de llamadas. Este tipo de sistemas son ampliamente utilizados por un gran n\u00famero de empresas como medio para gestionar las relaciones con sus clientes. El fin de estos sistemas es proporcionar diferentes servicios y recursos, dependiendo de las preferencias expresadas por los usuarios a trav\u00e9s de una serie de opciones. Teniendo en cuenta el funcionamiento de estos sistemas, se puede demostrar c\u00f3mo la navegaci\u00f3n guiada de cada cliente a trav\u00e9s de los sucesivos men\u00fas puede ser descrita mediante un grafo con forma de \u00e1rbol de servicios, cuyas hojas representan los recursos proporcionados. Dada la amplia variedad de servicios que este tipo de sistemas pueden ofrecer, la cantidad de hojas consideradas puede resultar significativamente alta (y equivalente al tama\u00f1o del \u00e1rbol). Espec\u00edficamente, es posible demostrar que dado un conjunto de l hojas en el sistema es suficiente considerar 2l-1 nodos en el \u00e1rbol para modelar cualquier sistema coherente de este tipo.  entre los diferentes par\u00e1metros a optimizar que pueden abordarse en un sistema interactivo, el tiempo promedio de servicio es probablemente el m\u00e1s significativo. Consecuentemente, esta magnitud es la que se decidi\u00f3 emplear como medida de la calidad que cada sistema considerado exhibe. Efectuando ciertas suposiciones acerca de la duraci\u00f3n de los mensajes que los usuarios de estos sistemas deber\u00e1n escuchar, una primera formulaci\u00f3n del problema a resolver es propuesta. Posteriores desarrollos sobre esta formulaci\u00f3n matem\u00e1tica muestran la estrecha relaci\u00f3n que dicho problema mantiene con la teor\u00eda de codificaci\u00f3n de fuente, resultando equivalentes el dise\u00f1o de un sistemas de respuesta de voz interactiva y el de un c\u00f3digo fuente hasta cierto punto. Esta equiValencia permite aplicar en el dise\u00f1o de centros de llamadas algunas importantes herramientas pertenecientes a la teor\u00eda de la informaci\u00f3n, como son el algoritmo de huffman y el teorema de codificaci\u00f3n de fuente, que respectivamente permitir\u00e1n obtener un buen m\u00e9todo determinista capaz de optimizar estos sistemas y un l\u00edmite inferior para el tiempo de servicio promedio que cualquier centro considero podr\u00e1 proporcionar.  comparando la estructura del problema con el tipo de \u00e1rboles representados mediante cualquiera de las codificaciones anteriormente mencionadas se puede apreciar la existencia de un gran n\u00famero de \u00e1rboles equivalentes: aquellos codificados empleando cromosomas diferentes, pero asociados a una misma soluci\u00f3n. La existencia de semejante cantidad de redundancia responde al hecho de que cualquiera de los m\u00e9todos indicados contiene informaci\u00f3n acerca de qu\u00e9 posici\u00f3n concreta ocupa cada nodo. Sin embargo, desde el punto de vista de este problema, existen ciertos nodos cuya ubicaci\u00f3n no resulta relevante, sino que los mismos se pueden intercambiar sin necesidad de modificar la soluci\u00f3n global. En estas condiciones, ciertas mejoras pueden acometerse con el fin de reducir en la medida de lo posible las dimensiones del espacio de b\u00fasqueda correspondiente. Espec\u00edficamente se han dise\u00f1ado dos procedimientos diferentes de b\u00fasqueda local, capaces de mejorar considerablemente los resultados obtenidos. La utilidad de los procedimientos dise\u00f1ados se comprueba sobre una amplia gama de experimentos dise\u00f1ados artificialmente, consistentes en centros de llamadas provistos de diversas cantidades de servicios a ofrecer, cuyas probabilidades de demanda muestran distribuciones diferentes. Adem\u00e1s, estos ejemplos permiten comparar distintas configuraciones del algoritmo evolutivo propuesto, relacionadas con la codificaci\u00f3n de la soluci\u00f3n, los operadores de cruce y mutaci\u00f3n y el procedimiento de selecci\u00f3n. A continuaci\u00f3n, la mejor de dichas configuraciones se emplea en la optimizaci\u00f3n de sistemas de respuesta de voz interactiva reales, pudi\u00e9ndose adem\u00e1s considerar en nuestro algoritmo ciertas restricciones impuestas sobre dichos sistemas por parte de sus respectivos administradores, con el fin de agrupar algunos de los servicios ofrecidos de acuerdo a ciertos criterios.   respecto el segundo objetivo contemplado, \u00e9ste aborda de modo a\u00fan m\u00e1s evidente el tratamiento de la informaci\u00f3n aportada por la apariencia que los diferentes \u00e1rboles considerados muestran. Espec\u00edficamente aquellos problemas de optimizaci\u00f3n orientados a la obtenci\u00f3n de ciertos \u00e1rboles que exhiban topolog\u00edas concretas ocupar\u00e1n los estudios contenidos en este segundo escenario, cuyo objetivo precisamente consistir\u00e1 en el dise\u00f1o de diferentes alternativas que permitan la correcta representaci\u00f3n de las mencionadas topolog\u00edas en la forma de cromosomas, sin que los mismos contengan informaci\u00f3n alguna acerca de las identidades concretas de aquellos nodos que ocupen ciertas ubicaciones en el \u00e1rbol. Debido a la considerable dificultad que la simple enumeraci\u00f3n de las diferentes topolog\u00edas que a partir de cierto n\u00famero de nodos pueden ser creadas, resultar\u00e1 imprescindible restringir el \u00e1mbito de estudio sobre un conjunto concreto de \u00e1rboles, considerando \u00fanicamente aquellos de apariencia binaria dadas las particulares propiedades que los mismos poseen, las cuales les dota de enorme utilidad en diversas aplicaciones. Tras definir rigurosamente el concepto de topolog\u00eda que durante el mencionado estudio se emplear\u00e1, se procede a evaluar la cantidad de diferentes topolog\u00edas que empleando cierto n\u00famero dado de nodos pueden ser construidas. Primeramente se presenta un m\u00e9todo capaz de representar la totalidad de estas topolog\u00edas de un modo considerablemente sencillo, a costa de introducir cierta redundancia en el espacio de b\u00fasqueda. Con el objetivo de subsanar dicho inconveniente se propone un segundo procedimiento, que si bien no resulta excesivamente laborioso en su utilizaci\u00f3n, requiere un detenido an\u00e1lisis que permita comprobar su validez. La correspondiente demostraci\u00f3n acerca de la capacidad que dicho m\u00e9todo muestra para representar correctamente la totalidad de topolog\u00edas existentes, evitando la inclusi\u00f3n de redundancia en el espacio de b\u00fasqueda, completa dicho estudio.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Mejora de algoritmos evolutivos en problemas de b\u00fasqueda de \u00e1rboles \u00f3ptimos: nuevos operadores sobre la codificaci\u00f3n dandelion<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Mejora de algoritmos evolutivos en problemas de b\u00fasqueda de \u00e1rboles \u00f3ptimos: nuevos operadores sobre la codificaci\u00f3n dandelion <\/li>\n<li><strong>Autor:<\/strong>\u00a0 \u00e1ngel Manuel P\u00e9rez Bellido <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Alcal\u00e1<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 10\/12\/2010<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Sancho Salcedo Sanz<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: saturnino Maldonado basc\u00f3n <\/li>\n<li>Javier Del ser lorente (vocal)<\/li>\n<li>Jos\u00e9 angel Fern\u00e1ndez prieto (vocal)<\/li>\n<li>bernab\u00e9 Dorronsoro d\u00edaz (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de \u00e1ngel Manuel P\u00e9rez Bellido Esta tesis doctoral aborda la optimizaci\u00f3n de grafos con forma de \u00e1rbol, ampliamente [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[17426,37303,2528],"tags":[212802,125648,121791,200226,59569,145379],"class_list":["post-105533","post","type-post","status-publish","format-standard","hentry","category-alcala","category-heuristica","category-inteligencia-artificial","tag-angel-manuel-perez-bellido","tag-bernabe-dorronsoro-diaz","tag-javier-del-ser-lorente","tag-jose-angel-fernandez-prieto","tag-sancho-salcedo-sanz","tag-saturnino-maldonado-bascon"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/105533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=105533"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/105533\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=105533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=105533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=105533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}