{"id":1991,"date":"2016-02-10T10:57:26","date_gmt":"2016-02-10T09:57:26","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1991"},"modified":"2022-12-03T22:58:54","modified_gmt":"2022-12-03T21:58:54","slug":"recherche-tabou","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/tabu-investigacion\/","title":{"rendered":"B\u00fasqueda tab\u00fa"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1991\" class=\"elementor elementor-1991\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-dd53370 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"dd53370\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1caf23f\" data-id=\"1caf23f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-02fe3ef elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"02fe3ef\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-estocasticos\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algoritmos estoc\u00e1sticos<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-2f0328c\" data-id=\"2f0328c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9086f37 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9086f37\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-545a052\" data-id=\"545a052\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5215238 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5215238\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Recherche_tabou\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7a20ef03 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7a20ef03\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4ef9a028\" data-id=\"4ef9a028\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2f3faaa0 elementor-widget elementor-widget-text-editor\" data-id=\"2f3faaa0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/tabu-investigacion\/#Recherche-tabou\" >Investigaci\u00f3n tab\u00fa<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/tabu-investigacion\/#Liste-tabou\" >Lista de tab\u00fa<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/tabu-investigacion\/#Deroulement-de-lalgorithme\" >Secuencia del algoritmo<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/tabu-investigacion\/#Exemple-dapplication\" >Ejemplo de aplicacion<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Recherche-tabou\"><\/span>Investigaci\u00f3n tab\u00fa<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">La investigaci\u00f3n tab\u00fa fue propuesta por Fred Glover en 1986 (cuyos diagramas encontrar\u00e1 en el flujo del algoritmo). El m\u00e9todo utiliza una memoria (o varias memorias) que se actualiza y explota durante la b\u00fasqueda.<\/p><div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">La idea b\u00e1sica de la lista tab\u00fa es memorizar las configuraciones o regiones visitadas e introducir mecanismos para evitar que la investigaci\u00f3n regrese demasiado r\u00e1pido a estas configuraciones. Estos mecanismos son prohibiciones temporales de determinados movimientos (movimientos tab\u00fa).<br \/><span id=\"spans0e0\">PARA<\/span> En cada iteraci\u00f3n, el algoritmo tab\u00fa elige al mejor vecino no tab\u00fa, incluso si esto degrada la funci\u00f3n de costo. Por esta raz\u00f3n, se dice que la investigaci\u00f3n tab\u00fa es un m\u00e9todo agresivo.<\/div><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Liste-tabou\"><\/span>Lista de tab\u00fa<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">La lista tab\u00fa contiene atributos o movimientos prohibidos. Estos \u00faltimos son tab\u00fa durante un determinado n\u00famero de iteraciones del algoritmo (infinitas o finitas). Una vez que finaliza el per\u00edodo tab\u00fa, el atributo o movimiento vuelve a estar disponible en el <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-estocasticos\/metodos-de-descenso\/\">busqueda local<\/a>. Esta lista es una estrategia de diversificaci\u00f3n.<\/div><p style=\"text-align: justify;\">Para ciertos tipos de problemas, la prohibici\u00f3n de un atributo puede eliminar configuraciones \u00fatiles para escapar de un \u00f3ptimo local. Un mecanismo, llamado criterio de aspiraci\u00f3n, permite relajar la prohibici\u00f3n en determinadas condiciones. Es importante se\u00f1alar que un mal criterio de aspiraci\u00f3n es hacer un bucle del algoritmo en un ciclo de soluciones.<\/p><p style=\"text-align: justify;\">Ya sea la elecci\u00f3n de la prohibici\u00f3n o el criterio de aspiraci\u00f3n, estos dos mecanismos deben adaptarse caso por caso en relaci\u00f3n con los problemas encontrados.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Deroulement-de-lalgorithme\"><\/span>Secuencia del algoritmo<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-2009 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tabusearch.png\" alt=\"investigaci\u00f3n tab\u00fa\" width=\"690\" height=\"762\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tabusearch.png 690w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tabusearch-272x300.png 272w\" sizes=\"(max-width: 690px) 100vw, 690px\" \/><\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"aligncenter wp-image-2011 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tabu.png\" alt=\"investigaci\u00f3n tab\u00fa\" width=\"687\" height=\"705\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tabu.png 687w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tabu-292x300.png 292w\" sizes=\"(max-width: 687px) 100vw, 687px\" \/><\/p><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><pre><span class=\"n\"> s<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">s0<\/span>\nsBest <span class=\"err\">\u2190<\/span> <span class=\"n\">s<\/span>\n<span class=\"n\">tabuList<\/span> <span class=\"err\">\u2190<\/span> <span class=\"p\">[]<\/span>\n<strong><span class=\"k\">tiempo<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"k\">no<\/span> <span class=\"n\">condici\u00f3n de parada<\/span><span class=\"p\">())<\/span>\n   <span class=\"n\">Lista de candidatos<\/span> <span class=\"err\">\u2190<\/span> <span class=\"p\">[]<\/span>\n   <span class=\"n\">bestCandidate<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">nulo<\/span>\n   <strong><span class=\"k\">por<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"n\">sCandidato<\/span> <span class=\"k\">en<\/span> <span class=\"n\">sVecindario<\/span><span class=\"p\">)<\/span>\n      <strong><span class=\"k\">tejo<\/span><\/strong> <span class=\"p\">(<\/span> <span class=\"p\">(<\/span><span class=\"k\">no<\/span> <span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">contiene<\/span><span class=\"p\">(<\/span><span class=\"n\">sCandidato<\/span><span class=\"p\">))<\/span> \n      <span class=\"k\">y<\/span> <span class=\"p\">(<\/span><span class=\"n\">aptitud f\u00edsica<\/span><span class=\"p\">(<\/span><span class=\"n\">sCandidato<\/span><span class=\"p\">)<\/span> <span class=\"o\">&gt;<\/span> <span class=\"n\">aptitud f\u00edsica<\/span><span class=\"p\">(<\/span><span class=\"n\">bestCandidate<\/span><span class=\"p\">))<\/span> <span class=\"p\">)<\/span>\n         <span class=\"n\">bestCandidate<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">sCandidato<\/span>\n      <strong><span class=\"k\">terminara si<\/span><\/strong>\n   <strong><span class=\"k\">final para<\/span><\/strong>\n   <span class=\"n\">s<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">bestCandidate<\/span>\n   <strong><span class=\"k\">tejo<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"n\">aptitud f\u00edsica<\/span><span class=\"p\">(<\/span><span class=\"n\">bestCandidate<\/span><span class=\"p\">)<\/span> <span class=\"o\">&gt;<\/span> <span class=\"n\">aptitud f\u00edsica<\/span><span class=\"p\">(<\/span><span class=\"n\">sBest<\/span><span class=\"p\">))<\/span>\n      <span class=\"n\">sBest<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">bestCandidate<\/span>\n   <strong><span class=\"k\">terminara si<\/span><\/strong>\n   <span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">empujar<\/span><span class=\"p\">(<\/span><span class=\"n\">bestCandidate<\/span><span class=\"p\">)<\/span><span class=\"o\">;<\/span>\n   <strong><span class=\"k\">tejo<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">Talla<\/span> <span class=\"o\">&gt;<\/span> <span class=\"n\">maxTabuSize<\/span><span class=\"p\">)<\/span>\n      <span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">removeFirst<\/span><span class=\"p\">()<\/span>\n   <strong><span class=\"k\">terminara si<\/span>\n<span class=\"lineno\">mi<\/span><span class=\"k\">nd mientras<\/span><\/strong>\n<span class=\"n\">regreso<\/span> <span class=\"n\">sBes<\/span><\/pre><\/div><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Exemple-dapplication\"><\/span>Ejemplo de aplicacion<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">Tomaremos el ejemplo del viajero comercial (TSP). Considere un conjunto de ciudades, conocemos la distancia entre todos los pares de ciudades. El objetivo es visitar cada ciudad, una tras otra hasta volver a la primera ciudad, minimizando la distancia total recorrida.<\/p><p style=\"text-align: justify;\">El recorrido est\u00e1 representado por un conjunto de arcos, siendo los v\u00e9rtices los pueblos. Una configuraci\u00f3n inicial consiste en elegir un ciclo <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/hamiltoniano-y-euleriano\/\">hamiltoniano<\/a> (un ciclo que pasa una y solo una vez por cada v\u00e9rtice) arbitrarias, como tomar la siguiente ciudad de la lista.<\/p><p style=\"text-align: justify;\">El barrio se construye con movimiento. Un movimiento consiste en quitar dos arcos para &quot;cruzarlos&quot;. Por ejemplo, el par de arcos <strong>&lt;(a, c), (e, b)&gt;<\/strong> se convierte en <strong>&lt;(a, e), (c, b)&gt;<\/strong>. As\u00ed se conserva el ciclo hamiltoniano. Luego hemos &quot;eliminado&quot; arcos y &quot;agregado&quot; arcos.<\/p><p style=\"text-align: justify;\">Para no repetir el mismo movimiento, presentamos dos listas tab\u00fa: <strong>EN<\/strong> que contiene arcos eliminados <strong>(a, c)<\/strong> y <strong>(e, b)<\/strong>; <strong>FUERA<\/strong> que contiene los arcos a\u00f1adidos <strong>(a, e)<\/strong> y <strong>(c, b)<\/strong>. <span id=\"spans2e0\">PARA<\/span> cada iteraci\u00f3n los movimientos prohibidos son: introducir un arco de <strong>EN<\/strong> y quita un arco de <strong>FUERA<\/strong>. Aqu\u00ed la prohibici\u00f3n es interminable.<\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"aligncenter wp-image-2025 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/tsp1.gif\" alt=\"Investigaci\u00f3n tab\u00fa de TSP\" width=\"639\" height=\"233\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>P\u00e1gina de inicio de Wiki de algoritmos estoc\u00e1sticos B\u00fasqueda tab\u00fa La b\u00fasqueda tab\u00fa fue propuesta por Fred Glover en 1986 (cuyos diagramas encontrar\u00e1 en el ... <\/p>","protected":false},"author":1,"featured_media":0,"parent":1770,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1991","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1991","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=1991"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1991\/revisions"}],"predecessor-version":[{"id":18382,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1991\/revisions\/18382"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1770"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=1991"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}