{"id":3427,"date":"2016-02-29T10:27:50","date_gmt":"2016-02-29T09:27:50","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3427"},"modified":"2022-12-03T22:59:03","modified_gmt":"2022-12-03T21:59:03","slug":"evaluation-des-heuristiques","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/evaluacion-heuristica\/","title":{"rendered":"Evaluaci\u00f3n heur\u00edstica"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3427\" class=\"elementor elementor-3427\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-93e2b79 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"93e2b79\" 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-d06b1db\" data-id=\"d06b1db\" 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-63b80b9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"63b80b9\" 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\/optimizacion-combinatoria\/\">\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\">Optimizaci\u00f3n combinatoria<\/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-9e15d60\" data-id=\"9e15d60\" 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-cbc368d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"cbc368d\" 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-138240d\" data-id=\"138240d\" 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-3890245 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"3890245\" 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:\/\/en.wikipedia.org\/wiki\/Heuristic_evaluation\" 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-7c29d914 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7c29d914\" 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-30150a27\" data-id=\"30150a27\" 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-3b9dd33c elementor-widget elementor-widget-text-editor\" data-id=\"3b9dd33c\" 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<p><\/p>\n<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\/evaluacion-heuristica\/#Methodes-devaluation-des-heuristiques\" >M\u00e9todos para evaluar heur\u00edsticas<\/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\/evaluacion-heuristica\/#Performance-relative\" >Desempe\u00f1o relativo<\/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\/evaluacion-heuristica\/#Evaluation-a-priori\" >Evaluaci\u00f3n a priori<\/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\/evaluacion-heuristica\/#Evaluation-a-posteriori-bornes-inferieures\" >Evaluaci\u00f3n a posteriori: l\u00edmites inferiores<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/evaluacion-heuristica\/#Evaluation-statistique\" >Evaluaci\u00f3n estad\u00edstica<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Methodes-devaluation-des-heuristiques\"><\/span>M\u00e9todos para evaluar heur\u00edsticas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>El problema de evaluar la heur\u00edstica es crucial. De hecho, la heur\u00edstica no ofrece ninguna garant\u00eda de optimizaci\u00f3n: pueden encontrar el \u00f3ptimo para ciertos datos o estar muy lejos de \u00e9l.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Performance-relative\"><\/span>Desempe\u00f1o relativo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<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;\">Supongamos que estamos estudiando un problema combinatorio para el que ya tenemos un m\u00e9todo de referencia exacto (\u00f3ptimo). Por una <a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/\">heur\u00edstico<\/a> H y un dato d, notamos H(d) el costo de la soluci\u00f3n heur\u00edstica y OPT(d) el costo \u00f3ptimo. Llamamos desempe\u00f1o relativo de H en d al cociente: R<sub>H<\/sub> (d) = H (d) \/ OPT (d).<\/div>\n<p><\/p>\n<p>por un problema de <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/\">minimizaci\u00f3n<\/a>, R<sub>h<\/sub> (d) \u2265 1. Tambi\u00e9n podemos hablar de distancia al \u00f3ptimo como porcentaje con la f\u00f3rmula: 100 * (R<sub>H<\/sub> (d) - 1). El desempe\u00f1o relativo es una evaluaci\u00f3n de la heur\u00edstica que puede estar acotada a priori (con las pruebas) o impredecible a posteriori (despu\u00e9s de las pruebas).<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-10231 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Optimization-test-results-the-figures-for-relative-processing-performance-show.png\" alt=\"evaluaci\u00f3n heur\u00edstica\" width=\"850\" height=\"261\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Optimization-test-results-the-figures-for-relative-processing-performance-show.png 850w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Optimization-test-results-the-figures-for-relative-processing-performance-show-300x92.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Optimization-test-results-the-figures-for-relative-processing-performance-show-768x236.png 768w\" sizes=\"(max-width: 850px) 100vw, 850px\" \/><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Evaluation-a-priori\"><\/span>Evaluaci\u00f3n a priori<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<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;\">Llamamos a la relaci\u00f3n de rendimiento del peor caso P<sub>H<\/sub> de una heur\u00edstica H su peor desempe\u00f1o relativo en el conjunto de datos posibles: P<sub>H<\/sub> = max {R<sub>H<\/sub> (d), para cualquier d} v\u00e1lido.<\/div>\n<p><\/p>\n<p>Esta es una garant\u00eda de desempe\u00f1o obtenida por an\u00e1lisis te\u00f3rico de H. Para esto limitamos R<sub>H<\/sub> (d) para cualquier dato d, entonces construimos un dato que muestre que este peor de los casos realmente se puede alcanzar. Este resultado es muy dif\u00edcil de obtener y, a menudo, no es posible calcularlo, en particular para todas las heur\u00edsticas que no incluyen caracteres de elecci\u00f3n matem\u00e1tica.<\/p>\n<p><\/p>\n<p>Tome un ejemplo de una heur\u00edstica de minimizaci\u00f3n con P<sub>H<\/sub> = 1,5. Esto significa que sean cuales sean los datos de entrada, la heur\u00edstica nunca dar\u00e1 un resultado m\u00e1s de 50% por encima del \u00f3ptimo general. &quot;Nunca&quot; ya que ha sido probado matem\u00e1ticamente.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Evaluation-a-posteriori-bornes-inferieures\"><\/span>Evaluaci\u00f3n a posteriori: l\u00edmites inferiores<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Cuando la evaluaci\u00f3n de la heur\u00edstica antes de la ejecuci\u00f3n es imposible, todav\u00eda es posible evaluar los resultados despu\u00e9s de la ejecuci\u00f3n de la heur\u00edstica H. Hemos visto el rendimiento relativo, pero este m\u00e9todo solo se aplica si es posible conocer el \u00f3ptimo global.<\/p>\n<p><\/p>\n<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;\">Sin embargo, podemos obtener una evaluaci\u00f3n si tenemos una evaluaci\u00f3n predeterminada B (d) para el OPT \u00f3ptimo (d) con: R<sub>H<\/sub> (d) = H (d) \/ OPT (d) \u2264 H (d) \/ B (d). En particular, si H (d) = B (d), entonces hemos alcanzado el \u00f3ptimo global. Siempre es posible encontrar un l\u00edmite al \u00f3ptimo global mediante un m\u00e9todo ingenuo o codicioso.<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Evaluation-statistique\"><\/span>Evaluaci\u00f3n estad\u00edstica<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Las evaluaciones a priori y a posteriori de la heur\u00edstica siguen planteando un problema: \u00bfcu\u00e1ndo hay problemas muy importantes? La evaluaci\u00f3n heur\u00edstica m\u00e1s simple consiste en comparar las soluciones con las que se dan en los puntos de referencia o los m\u00e9todos de uso generalizado. El valor de la soluci\u00f3n, sobre un gran conjunto de pruebas, en comparaci\u00f3n con m\u00e9todos conocidos, proporciona una buena aproximaci\u00f3n de la eficiencia de la heur\u00edstica.<\/p>\n<p><\/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>Optimizaci\u00f3n combinatoria P\u00e1gina de inicio de Wiki M\u00e9todos de evaluaci\u00f3n heur\u00edstica El problema de la evaluaci\u00f3n heur\u00edstica es crucial. De hecho, las heur\u00edsticas no ofrecen ninguna garant\u00eda de optimizaci\u00f3n... <\/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-3427","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3427","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=3427"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3427\/revisions"}],"predecessor-version":[{"id":16653,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3427\/revisions\/16653"}],"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=3427"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}