{"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\/en\/combinatorial-optimization-2\/heuristic-evaluation\/","title":{"rendered":"Heuristics evaluation"},"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\/en\/combinatorial-optimization-2\/\">\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\">Combinatorial optimization<\/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\/en\/\">\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\">Home page<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/combinatorial-optimization-2\/heuristic-evaluation\/#Methodes-devaluation-des-heuristiques\" >Methods for evaluating heuristics<\/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\/en\/combinatorial-optimization-2\/heuristic-evaluation\/#Performance-relative\" >Relative performance<\/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\/en\/combinatorial-optimization-2\/heuristic-evaluation\/#Evaluation-a-priori\" >A priori assessment<\/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\/en\/combinatorial-optimization-2\/heuristic-evaluation\/#Evaluation-a-posteriori-bornes-inferieures\" >A posteriori evaluation: lower bounds<\/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\/en\/combinatorial-optimization-2\/heuristic-evaluation\/#Evaluation-statistique\" >Statistical evaluation<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Methodes-devaluation-des-heuristiques\"><\/span>Methods for evaluating heuristics<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The problem of evaluating heuristics is crucial. Indeed, heuristics offer no guarantee of optimality: they can find the optimum for certain data, or be very far from it.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Performance-relative\"><\/span>Relative performance<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;\">Suppose that we are studying a combinatorial problem for which we already have an exact (optimal) reference method. For a <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">heuristic<\/a> H and a datum d, we note H(d) the cost of the heuristic solution and OPT(d) the optimal cost. We call relative performance of H on d the quotient: R<sub>H<\/sub> (d) = H (d) \/ OPT (d).<\/div>\n<p><\/p>\n<p>For a problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/minimization-dun-afd\/\">minimization<\/a>, R<sub>h<\/sub> (d) \u2265 1. We can also speak of distance to the optimum as a percentage with the formula: 100 * (R<sub>H<\/sub> (d) - 1). Relative performance is an evaluation of heuristics which can be bounded a priori (with the tests) or unpredictable a posteriori (after the tests).<\/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=\"heuristic evaluation\" 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>A priori assessment<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;\">We call the worst case performance ratio P<sub>H<\/sub> of a heuristic H its worst relative performance on the set of possible data: P<sub>H<\/sub> = max {R<sub>H<\/sub> (d), for any valid d}.<\/div>\n<p><\/p>\n<p>This is a performance guarantee obtained by theoretical analysis of H. For this we limit R<sub>H<\/sub> (d) for any data d, then we construct a data showing that this worst case can actually be reached. This result is very difficult to obtain, and is often not possible to calculate, in particular for all heuristics which do not include mathematical choice characters.<\/p>\n<p><\/p>\n<p>Take an example of a minimization heuristic with P<sub>H<\/sub> = 1.5. This means that whatever the input data, the heuristic will never give a result more than 50% above the overall optimum. &quot;Never&quot; since this has been proven mathematically.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Evaluation-a-posteriori-bornes-inferieures\"><\/span>A posteriori evaluation: lower bounds<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>When the evaluation of heuristics before execution is impossible, it is still possible to evaluate the results after execution of the heuristic H. We have seen the relative performance, but this method only applies if it is possible to know the global optimum.<\/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;\">We can however obtain an evaluation if we have a default evaluation B (d) for the optimum OPT (d) with: R<sub>H<\/sub> (d) = H (d) \/ OPT (d) \u2264 H (d) \/ B (d). In particular, if H (d) = B (d), then we have reached the global optimum. It is always possible to find a bound to the global optimum by a naive or greedy method.<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Evaluation-statistique\"><\/span>Statistical evaluation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>A priori and a posteriori evaluations of heuristics still pose a problem: when are there very large problems? The simplest heuristic evaluation consists in comparing solutions with those given in benchmarks or widely used methods. The value of the solution, over a large set of tests, compared to known methods, gives a good approximation of the efficiency of the heuristic.<\/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>Combinatorial optimization Wiki home page Heuristic evaluation methods The problem of heuristic evaluation is crucial. Indeed, heuristics do not offer any guarantee of optimality\u2026 <\/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\/en\/wp-json\/wp\/v2\/pages\/3427","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=3427"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3427\/revisions"}],"predecessor-version":[{"id":16653,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3427\/revisions\/16653"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1770"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=3427"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}