{"id":109529,"date":"2018-03-11T10:34:59","date_gmt":"2018-03-11T10:34:59","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/metaheura%c2%adsticas-y-computacion-paralela-para-el-problema-de-la-planificacion-de-frecuencias-en-redes-reales-de-telecomunicaciones\/"},"modified":"2018-03-11T10:34:59","modified_gmt":"2018-03-11T10:34:59","slug":"metaheura%c2%adsticas-y-computacion-paralela-para-el-problema-de-la-planificacion-de-frecuencias-en-redes-reales-de-telecomunicaciones","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/extremadura\/metaheura%c2%adsticas-y-computacion-paralela-para-el-problema-de-la-planificacion-de-frecuencias-en-redes-reales-de-telecomunicaciones\/","title":{"rendered":"Metaheur\u00edsticas y computaci\u00f3n paralela para el problema de la planificaci\u00f3n de frecuencias en redes reales de telecomunicaciones"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Jos\u00e9 Manuel Chaves Gonz\u00e1lez <\/strong><\/h2>\n<p>El dise\u00f1o de t\u00e9cnicas y algoritmos eficientes que resuelvan adecuadamente problemas complejos de optimizaci\u00f3n es uno de los campos dentro de la investigaci\u00f3n en inform\u00e1tica con mayor repercusi\u00f3n en la actualidad. De hecho, debido a que la sociedad actual demanda continuamente m\u00e1s y mayores retos en el campo de la ingenier\u00eda, dar una soluci\u00f3n adecuada y eficiente a este tipo de problemas cobra cada vez mayor importancia tanto para la industria como para la comunidad cient\u00edfica. Adem\u00e1s, es bien sabido que tanto los requisitos temporales como computacionales son un factor cr\u00edtico a tener en cuenta cuando se trata de resolver problemas de grandes proporciones cuya soluci\u00f3n debe ser aplicable en un supuesto real. En estos casos, el uso de heur\u00edsticas y metaheur\u00edsticas en combinaci\u00f3n con estrategias paralelas se presenta como la mejor alternativa de resoluci\u00f3n, ya que por una parte, las citadas estrategias no exactas proporcionan una soluci\u00f3n de alta calidad en un tiempo razonable, mientras que por otro, es bien sabido que tanto la eficiencia de dichos algoritmos heur\u00edsticos como los resultados que \u00e9stos obtienen mejoran de manera significativa cuando se aplican estrategias de paralelismo. \u00e9ste es el contexto global en el que se incardina esta tesis doctoral.  \tpor tanto, se han estudiado, dise\u00f1ado y desarrollado un conjunto heterog\u00e9neo de metaheur\u00edsticas para resolver un importante problema de optimizaci\u00f3n dentro del dominio de las telecomunicaciones. Sin embargo, el uso de algoritmos metaheur\u00edsticos conlleva un alto coste computacional, ya que por una parte, dichos m\u00e9todos incluyen una gran cantidad de par\u00e1metros que es necesario ajustar mediante numerosos experimentos, mientras que por otra, ciertas partes de dichos algoritmos requieren mucha capacidad de c\u00f3mputo. Por consiguiente, a la hora de abordar problemas reales de grandes dimensiones, como es el caso del problema manejado en esta tesis, tanto los requisitos t\u00e9cnicos como temporales requeridos por estas t\u00e9cnicas son muy exigentes. As\u00ed pues, se hace imprescindible que el uso de las t\u00e9cnicas metaheur\u00edsticas est\u00e9 combinado con estrategias paralelas. De esta forma, se mejora tanto la productividad como el rendimiento de las metaheur\u00edsticas, ya que de una parte el paralelismo permite que el ajuste param\u00e9trico de las metaheur\u00edsticas se agilice considerablemente, haciendo que este proceso sea m\u00e1s preciso y exhaustivo, mientras que de otra se mejora notablemente la calidad de los resultados en tiempos que ser\u00edan m\u00e1s elevados si los algoritmos se ejecutaran de manera secuencial. Las estrategias paralelas para mejorar productividad y rendimiento son diferentes, ya que en el primer caso se utilizan paradigmas dise\u00f1ados para aplicar computaci\u00f3n de alta productividad y en el otro se utilizan modelos aplicados a computaci\u00f3n de alto rendimiento. En esta tesis se han utilizado ambos modelos, haciendo uso de estrategias paralelas dise\u00f1adas para ser ejecutadas tanto en entornos cl\u00faster como en entornos grid. \ten concreto, el problema de optimizaci\u00f3n con el que se ha trabajado en esta tesis es el de la asignaci\u00f3n autom\u00e1tica de frecuencias (fap, del ingl\u00e9s frequency assigment problem), y fue elegido, entre otras razones, tanto por su complejidad (se trata de un problema np-completo) como por su relevancia para la industria del sector, ya que es bien conocido que el mundo actual en que vivimos est\u00e1 dominado por las comunicaciones, lo cual provoca que los recursos necesarios para llevar a cabo este proceso sean muy limitados. Este hecho hace que las compa\u00f1\u00edas que ofrecen servicios m\u00f3viles deban gestionar los citados recursos de manera eficiente para sacar el m\u00e1ximo rendimiento de ellos manteniendo unos niveles altos en la calidad de los servicios que ofrecen. el problema de optimizaci\u00f3n que surge con el fap se debe al reducido rango de frecuencias disponible para cada red de telefon\u00eda. Debido a este hecho, no es posible asignar a cada comunicaci\u00f3n que se establece en la red una frecuencia \u00fanica, sino que los operadores deben repetir las frecuencias de que disponen m\u00faltiples veces para cubrir todas las comunicaciones que se producen entre los usuarios de la red. Sin embargo, este solapamiento de frecuencias causa interferencias que dificultan, e incluso pueden llegar a anular, dichas comunicaciones, por lo que se hace necesario realizar una planificaci\u00f3n de frecuencias eficiente con la que se consiga maximizar el n\u00famero de comunicaciones que se realizan en la red manteniendo a la vez unos m\u00ednimos aceptables en la calidad de los servicios ofrecidos. tras hacer una amplia revisi\u00f3n de los algoritmos heur\u00edsticos y metaheur\u00edsticos que parec\u00edan ajustarse mejor a los requisitos del problema descrito anteriormente, se termin\u00f3 por desarrollar y ajustar un conjunto de siete metaheur\u00edsticas con el que se trat\u00f3 de resolver el problema de la asignaci\u00f3n de frecuencias desde varios enfoques. El primero que se implement\u00f3 fue pbil (aprendizaje incremental basado en poblaci\u00f3n), el cual se aplic\u00f3 primero a una versi\u00f3n benchmark del fap (las instancias philadelphia), para despu\u00e9s ser adaptado a la versi\u00f3n real del problema que ha centrado la investigaci\u00f3n del autor de esta tesis. Despu\u00e9s se implement\u00f3 el algoritmo ss (b\u00fasqueda dispersa), que ha sido una de las aproximaciones que mejores resultados ha obtenido en la resoluci\u00f3n del problema. No se quiso dejar fuera del estudio al cl\u00e1sico algoritmo gen\u00e9tico (ga), que tras un exhaustivo ajuste demostr\u00f3 proporcionar planificaciones de frecuencia de muy alta calidad. Finalmente, se incluy\u00f3 un algoritmo basado en inteligencia colectiva, el abc (algoritmo basado en colonia de abejas, de reciente aparici\u00f3n), que tambi\u00e9n ofreci\u00f3 muy buenos resultados. Todos los algoritmos mencionados anteriormente son metaheur\u00edsticas basadas en poblaci\u00f3n, ya que utilizan una poblaci\u00f3n de soluciones en su b\u00fasqueda del \u00f3ptimo global, pero no se quisieron dejar fuera del estudio estrategias basadas en trayectoria, ya que presentan caracter\u00edsticas que tambi\u00e9n resultan interesantes. As\u00ed, se desarrollaron los algoritmos ils (b\u00fasqueda local iterativa), vns (b\u00fasqueda de entorno variable) y grasp (procedimiento de b\u00fasqueda adaptativa, avariciosa y aleatoria), con el que adem\u00e1s se desarroll\u00f3 un modelo paralelo maestro-esclavo utilizando una infraestructura grid real. por tanto, se realizaron m\u00faltiples pruebas y experimentos con cada metaheur\u00edstica, aplicando en algunos casos paradigmas basados en paralelismo. Sin embargo, el estudio presentado en esta tesis concluy\u00f3 con el dise\u00f1o e implementaci\u00f3n de una novedosa estrategia paralela que hac\u00eda uso de todas las metaheur\u00edsticas desarrolladas. En concreto, se desarroll\u00f3 una hiperheur\u00edstica paralela basada en el heterog\u00e9neo conjunto de metaheur\u00edsticas que se hab\u00eda desarrollado, y que dio como resultados planificaciones de frecuencia de muy alta calidad que solucionaban el problema de optimizaci\u00f3n abordado. De hecho, entre las principales contribuciones aportadas por esta tesis se encuentran, por un lado, el desarrollo y evaluaci\u00f3n de metaheur\u00edsticas que no hab\u00edan sido aplicadas antes en la resoluci\u00f3n del problema fap, obteni\u00e9ndose adem\u00e1s resultados de muy buena calidad en todas ellas, y por otro, el dise\u00f1o e implementaci\u00f3n de una eficiente estrategia paralela (la hiperheur\u00edstica basada en metaheur\u00edsticas) con la que se ha conseguido mejorar, hasta donde nosotros conocemos, cualquier resultado (tanto en tiempo como en calidad) publicado hasta la fecha en la resoluci\u00f3n del problema de la asignaci\u00f3n autom\u00e1tica de frecuencia en redes reales de telecomunicaciones.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Metaheur\u00edsticas y computaci\u00f3n paralela para el problema de la planificaci\u00f3n de frecuencias en redes reales de telecomunicaciones<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Metaheur\u00edsticas y computaci\u00f3n paralela para el problema de la planificaci\u00f3n de frecuencias en redes reales de telecomunicaciones <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Jos\u00e9 Manuel Chaves Gonz\u00e1lez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Extremadura<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 27\/06\/2011<\/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>Miguel \u00e1ngel Vega Rodr\u00edguez<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Juan  manuel S\u00e1nchez p\u00e9rez <\/li>\n<li>coromoto Le\u00f3n hern\u00e1ndez (vocal)<\/li>\n<li>Juan  Antonio G\u00f3mez pulido (vocal)<\/li>\n<li>ricardo Aler mur (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Jos\u00e9 Manuel Chaves Gonz\u00e1lez El dise\u00f1o de t\u00e9cnicas y algoritmos eficientes que resuelvan adecuadamente problemas complejos de [&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":[949,37303,13880,2528],"tags":[153162,219047,71124,16473,72158,42387],"class_list":["post-109529","post","type-post","status-publish","format-standard","hentry","category-extremadura","category-heuristica","category-informatica","category-inteligencia-artificial","tag-coromoto-leon-hernandez","tag-jose-manuel-chaves-gonzalez","tag-juan-antonio-gomez-pulido","tag-juan-manuel-sanchez-perez","tag-miguel-angel-vega-rodriguez","tag-ricardo-aler-mur"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/109529","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=109529"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/109529\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=109529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=109529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=109529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}