{"id":3048,"date":"2016-05-20T15:55:25","date_gmt":"2016-05-20T14:55:25","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3048"},"modified":"2022-12-03T22:59:02","modified_gmt":"2022-12-03T21:59:02","slug":"grasp","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/stochastic-algorithms-2\/grasp\/","title":{"rendered":"GRASP"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3048\" class=\"elementor elementor-3048\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-624d9e5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"624d9e5\" 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-28bbd90\" data-id=\"28bbd90\" 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-7c5bd5c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"7c5bd5c\" 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\/stochastic-algorithms-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\">Stochastic algorithms<\/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-66b35f6\" data-id=\"66b35f6\" 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-05a2a63 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"05a2a63\" 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-ffd98b6\" data-id=\"ffd98b6\" 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-f00d751 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f00d751\" 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\/Greedy_randomized_adaptive_search_procedure\" 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-306e4b57 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"306e4b57\" 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-774b4010\" data-id=\"774b4010\" 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-1cd16116 elementor-widget elementor-widget-text-editor\" data-id=\"1cd16116\" 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\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\/stochastic-algorithms-2\/grasp\/#Greedy-Randomized-Adaptive-Search-Procedure-GRASP\" >Greedy Randomized Adaptive Search Procedure (GRASP)<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Greedy-Randomized-Adaptive-Search-Procedure-GRASP\"><\/span>Greedy Randomized Adaptive Search Procedure (GRASP)<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The Greedy Randomized Adaptive Search Procedure (GRASP) algorithm is a <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">metaheuristic<\/a> introduced by Feo and Resende in 1989.<\/p>\n\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;\">Its operation is based on the repetition of two phases: a gluttonous construction followed by a <a href=\"https:\/\/complex-systems-ai.com\/en\/stochastic-algorithms-2\/descent-methods\/\">local search<\/a>.<\/div>\n\n<p>The characteristic of the GRASP method is its phase of building a solution. To do this, the algorithm maintains an updated list of fragments of possible solutions (RCL, restricted candidate list). The solution is built step by step by going to choose elements (in our case, they are the gains of combining meshes in zones) in the list RCL. This list is sorted, it&#039;s the greedy part of the algorithm.<\/p>\n\n<p>An element is drawn randomly from the best possibilities of the RCL list, it is the random part of the algorithm. Thanks to the random part, the construction phase therefore makes it possible to vary the shape of the solutions generated, but these are of good quality since the random choice is made among a set of good candidates. Local research is applied to the feasible solution resulting from the construction phase in order to see if it is still possible to improve this solution.<\/p>\n\n<div style=\"text-align: justify;\">Two points should be noted:<\/div>\n\n<ul class=\"wp-block-list\">\n<li style=\"text-align: justify;\">the RCL is updated with selected elements according to a specific heuristic adapted to the problem considered.<\/li>\n<li style=\"text-align: justify;\">the choice of an element in the RCL to build the solution is random.<\/li>\n<\/ul>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-3949\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/grasp.png\" alt=\"Greedy Randomized Adaptive Search Procedure GRASP\" width=\"722\" height=\"755\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/grasp.png 722w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/grasp-287x300.png 287w\" sizes=\"(max-width: 722px) 100vw, 722px\" \/><\/figure>\n<\/div>\n\n<p>\u00a0<\/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>Stochastic Algorithms Homepage Wiki Greedy Randomized Adaptive Search Procedure (GRASP) The Greedy Randomized Adaptive Search Procedure (GRASP) algorithm is a metaheuristic introduced by Feo and \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":7101,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3048","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3048","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=3048"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3048\/revisions"}],"predecessor-version":[{"id":18433,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3048\/revisions\/18433"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7101"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=3048"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}