{"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\/en\/combinatorial-optimization-2\/taboo-research\/","title":{"rendered":"Taboo search"},"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\/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-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\/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-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\">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\/taboo-research\/#Recherche-tabou\" >Taboo research<\/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\/taboo-research\/#Liste-tabou\" >Taboo list<\/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\/taboo-research\/#Deroulement-de-lalgorithme\" >Sequence of the algorithm<\/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\/taboo-research\/#Exemple-dapplication\" >Example of application<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Recherche-tabou\"><\/span>Taboo research<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">Taboo research was proposed by Fred Glover in 1986 (the diagrams of which you will find in the flow of the algorithm). The method uses a memory (or several memories) which is updated and exploited during the search.<\/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;\">The basic idea of the taboo list is to memorize the configurations or regions visited and to introduce mechanisms to prevent research from returning too quickly to these configurations. These mechanisms are temporary bans on certain movements (taboo movements).<br \/><span id=\"spans0e0\">TO<\/span> each iteration, the taboo algorithm chooses the best non-taboo neighbor, even if this degrades the cost function. For this reason, taboo research is said to be an aggressive method.<\/div><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Liste-tabou\"><\/span>Taboo list<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;\">The tabu list contains forbidden attributes or movements. The latter are taboo during a determined number of iterations of the algorithm (infinite or finite). Once the taboo period is over, the attribute or movement is again available in the <a href=\"https:\/\/complex-systems-ai.com\/en\/stochastic-algorithms-2\/descent-methods\/\">local search<\/a>. This list is a diversification strategy.<\/div><p style=\"text-align: justify;\">For certain types of problem, the prohibition of an attribute can eliminate useful configurations to escape a local optimum. A mechanism, called the aspiration criterion, allows the ban to be relaxed under certain conditions. It is important to note that a bad criterion of aspiration to make loop the algorithm on a cycle of solutions.<\/p><p style=\"text-align: justify;\">Whether it is the choice of prohibition or the aspiration criterion, these two mechanisms must be adapted on a case-by-case basis in relation to the problems encountered.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Deroulement-de-lalgorithme\"><\/span>Sequence of the algorithm<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=\"taboo research\" 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=\"taboo research\" 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\">while<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"k\">not<\/span> <span class=\"n\">stoppingCondition<\/span><span class=\"p\">())<\/span>\n   <span class=\"n\">candidateList<\/span> <span class=\"err\">\u2190<\/span> <span class=\"p\">[]<\/span>\n   <span class=\"n\">bestCandidate<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">null<\/span>\n   <strong><span class=\"k\">for<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"n\">sCandidate<\/span> <span class=\"k\">in<\/span> <span class=\"n\">sNeighbourhood<\/span><span class=\"p\">)<\/span>\n      <strong><span class=\"k\">yew<\/span><\/strong> <span class=\"p\">(<\/span> <span class=\"p\">(<\/span><span class=\"k\">not<\/span> <span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">contains<\/span><span class=\"p\">(<\/span><span class=\"n\">sCandidate<\/span><span class=\"p\">))<\/span> \n      <span class=\"k\">and<\/span> <span class=\"p\">(<\/span><span class=\"n\">fitness<\/span><span class=\"p\">(<\/span><span class=\"n\">sCandidate<\/span><span class=\"p\">)<\/span> <span class=\"o\">&gt;<\/span> <span class=\"n\">fitness<\/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\">sCandidate<\/span>\n      <strong><span class=\"k\">end if<\/span><\/strong>\n   <strong><span class=\"k\">end for<\/span><\/strong>\n   <span class=\"n\">s<\/span> <span class=\"err\">\u2190<\/span> <span class=\"n\">bestCandidate<\/span>\n   <strong><span class=\"k\">yew<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"n\">fitness<\/span><span class=\"p\">(<\/span><span class=\"n\">bestCandidate<\/span><span class=\"p\">)<\/span> <span class=\"o\">&gt;<\/span> <span class=\"n\">fitness<\/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\">end if<\/span><\/strong>\n   <span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">push<\/span><span class=\"p\">(<\/span><span class=\"n\">bestCandidate<\/span><span class=\"p\">)<\/span><span class=\"o\">;<\/span>\n   <strong><span class=\"k\">yew<\/span><\/strong> <span class=\"p\">(<\/span><span class=\"n\">tabuList<\/span><span class=\"o\">.<\/span><span class=\"n\">size<\/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\">end if<\/span>\n<span class=\"lineno\">e<\/span><span class=\"k\">nd while<\/span><\/strong>\n<span class=\"n\">return<\/span> <span class=\"n\">sBes<\/span><\/pre><\/div><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Exemple-dapplication\"><\/span>Example of application<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">We will take the example of the commercial traveler (TSP). Consider a set of cities, we know the distance between all pairs of cities. The objective is to visit each city, one after the other until returning to the first city, while minimizing the total distance traveled.<\/p><p style=\"text-align: justify;\">The course is represented by a set of arcs, the vertices being the towns. An initial configuration consists of choosing a cycle <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/hamiltonian-and-eulerian\/\">Hamiltonian<\/a> (a cycle that passes once and only once by each vertex) arbitrary, such as taking the next city in the list.<\/p><p style=\"text-align: justify;\">The neighborhood is built by movement. One movement consists of removing two arcs to &quot;cross&quot; them. For example the pair of arcs <strong>&lt;(a, c), (e, b)&gt;<\/strong> bECOMES <strong>&lt;(a, e), (c, b)&gt;<\/strong>. Thus the Hamiltonian cycle is preserved. We then have &quot;removed&quot; arcs and &quot;added&quot; arcs.<\/p><p style=\"text-align: justify;\">In order not to repeat the same movement, we introduce two taboo lists: <strong>IN<\/strong> containing deleted arcs <strong>(a, c)<\/strong> and <strong>(e, b)<\/strong>; <strong>OUT<\/strong> containing the added arcs <strong>(a, e)<\/strong> and <strong>(c, b)<\/strong>. <span id=\"spans2e0\">TO<\/span> each iteration the prohibited movements are: introduce an arc of <strong>IN<\/strong> and remove a bow from <strong>OUT<\/strong>. Here the prohibition is endless.<\/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=\"TSP taboo research\" 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>Stochastic algorithms Wiki homepage Tabu search Tabu search was proposed by Fred Glover in 1986 (the diagrams of which you will find in the \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-1991","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1991","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=1991"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1991\/revisions"}],"predecessor-version":[{"id":18382,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1991\/revisions\/18382"}],"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=1991"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}