examples.html 60 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794
  1. <!DOCTYPE html>
  2. <!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
  3. <!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
  4. <head>
  5. <meta charset="utf-8">
  6. <meta name="viewport" content="width=device-width, initial-scale=1.0">
  7. <title>Some examples &mdash; macop v1.0.5 documentation</title>
  8. <script type="text/javascript" src="_static/js/modernizr.min.js"></script>
  9. <script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
  10. <script type="text/javascript" src="_static/jquery.js"></script>
  11. <script type="text/javascript" src="_static/underscore.js"></script>
  12. <script type="text/javascript" src="_static/doctools.js"></script>
  13. <script type="text/javascript" src="_static/language_data.js"></script>
  14. <script type="text/javascript" src="_static/js/theme.js"></script>
  15. <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  16. <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
  17. <link rel="stylesheet" href="_static/css/custom.css" type="text/css" />
  18. <link rel="index" title="Index" href="genindex.html" />
  19. <link rel="search" title="Search" href="search.html" />
  20. <link rel="next" title="Contributing" href="contributing.html" />
  21. <link rel="prev" title="3. Solutions" href="documentations/solutions.html" />
  22. </head>
  23. <body class="wy-body-for-nav">
  24. <div class="wy-grid-for-nav">
  25. <nav data-toggle="wy-nav-shift" class="wy-nav-side">
  26. <div class="wy-side-scroll">
  27. <div class="wy-side-nav-search" >
  28. <a href="index.html" class="icon icon-home"> macop
  29. </a>
  30. <div class="version">
  31. 1.0.5
  32. </div>
  33. <div role="search">
  34. <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
  35. <input type="text" name="q" placeholder="Search docs" />
  36. <input type="hidden" name="check_keywords" value="yes" />
  37. <input type="hidden" name="area" value="default" />
  38. </form>
  39. </div>
  40. </div>
  41. <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
  42. <p class="caption"><span class="caption-text">Contents:</span></p>
  43. <ul class="current">
  44. <li class="toctree-l1"><a class="reference internal" href="description.html">Description</a></li>
  45. <li class="toctree-l1"><a class="reference internal" href="api.html">API</a></li>
  46. <li class="toctree-l1"><a class="reference internal" href="documentations/index.html">Documentation</a></li>
  47. <li class="toctree-l1 current"><a class="current reference internal" href="#">Some examples</a><ul>
  48. <li class="toctree-l2"><a class="reference internal" href="#some-information">1. Some information</a><ul>
  49. <li class="toctree-l3"><a class="reference internal" href="#implemented-algorithms">1.1 Implemented algorithms</a></li>
  50. <li class="toctree-l3"><a class="reference internal" href="#available-solutions">1.2 Available solutions</a></li>
  51. <li class="toctree-l3"><a class="reference internal" href="#update-solutions">1.3 Update solutions</a></li>
  52. <li class="toctree-l3"><a class="reference internal" href="#backup-feature">1.4 Backup feature</a></li>
  53. </ul>
  54. </li>
  55. <li class="toctree-l2"><a class="reference internal" href="#mono-objective">2. Mono-objective</a><ul>
  56. <li class="toctree-l3"><a class="reference internal" href="#problem-definition">2.1 Problem definition</a></li>
  57. <li class="toctree-l3"><a class="reference internal" href="#operators-and-policy">2.2 Operators and Policy</a></li>
  58. <li class="toctree-l3"><a class="reference internal" href="#before-running-algorithm">2.3 Before running algorithm</a></li>
  59. </ul>
  60. </li>
  61. <li class="toctree-l2"><a class="reference internal" href="#multi-objective">3. Multi-objective</a><ul>
  62. <li class="toctree-l3"><a class="reference internal" href="#id1">3.1 Problem definition</a></li>
  63. <li class="toctree-l3"><a class="reference internal" href="#id2">3.2 Operators and Policy</a></li>
  64. <li class="toctree-l3"><a class="reference internal" href="#how-works-multi-objective-in-macop">3.3 How works multi-objective in macop ?</a></li>
  65. <li class="toctree-l3"><a class="reference internal" href="#checkpoint-multi-objective-solutions">3.4 Checkpoint multi-objective solutions</a></li>
  66. </ul>
  67. </li>
  68. </ul>
  69. </li>
  70. <li class="toctree-l1"><a class="reference internal" href="contributing.html">Contributing</a></li>
  71. </ul>
  72. </div>
  73. </div>
  74. </nav>
  75. <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
  76. <nav class="wy-nav-top" aria-label="top navigation">
  77. <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
  78. <a href="index.html">macop</a>
  79. </nav>
  80. <div class="wy-nav-content">
  81. <div class="rst-content">
  82. <div role="navigation" aria-label="breadcrumbs navigation">
  83. <ul class="wy-breadcrumbs">
  84. <li><a href="index.html">Docs</a> &raquo;</li>
  85. <li>Some examples</li>
  86. <li class="wy-breadcrumbs-aside">
  87. <a href="https://github.com/prise-3d/macop/blob/master/docs/source/examples.rst" class="fa fa-github"> Edit on GitHub</a>
  88. </li>
  89. </ul>
  90. <hr/>
  91. </div>
  92. <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
  93. <div itemprop="articleBody">
  94. <div class="section" id="some-examples">
  95. <h1>Some examples<a class="headerlink" href="#some-examples" title="Permalink to this headline">¶</a></h1>
  96. <div class="section" id="some-information">
  97. <h2>1. Some information<a class="headerlink" href="#some-information" title="Permalink to this headline">¶</a></h2>
  98. <p>The package consists of several modules:</p>
  99. <ul class="simple">
  100. <li><p><strong>algorithms</strong>: generic and implemented OR algorithms.</p></li>
  101. <li><p><strong>evaluator</strong>: contains all the implemented evaluation functions.</p></li>
  102. <li><p><strong>solutions</strong>: all declared solutions classes used to represent problem data.</p></li>
  103. <li><p><strong>operators</strong>: mutators, crossovers update of solution. This module also has policies classes to manage the way of update and use solution.</p></li>
  104. <li><p><strong>callbacks</strong>: contains Callback class implemenration for making callback instructions every number of evaluations.</p></li>
  105. </ul>
  106. <div class="section" id="implemented-algorithms">
  107. <h3>1.1 Implemented algorithms<a class="headerlink" href="#implemented-algorithms" title="Permalink to this headline">¶</a></h3>
  108. <p>Both single and multi-objective algorithms have been implemented for demonstration purposes. The mono-objective Iterated Local Search algorithm which aims to perform local searches and then to explore again (explorations vs. exploitation trade-off). On the multi-objective side, the MOEA/D algorithm has been implemented using the weighted-sum of objectives method (Tchebycheff approach can also be used). This algorithm aims at decomposing the multi-objective problem into <cite>mu</cite> single-objective problems in order to obtain the pareto front.</p>
  109. </div>
  110. <div class="section" id="available-solutions">
  111. <h3>1.2 Available solutions<a class="headerlink" href="#available-solutions" title="Permalink to this headline">¶</a></h3>
  112. <p>Currently, only combinatorial solutions are offered, with the well-known knapsack problem as an example. Of course, it’s easy to add your own representations of solutions.</p>
  113. </div>
  114. <div class="section" id="update-solutions">
  115. <h3>1.3 Update solutions<a class="headerlink" href="#update-solutions" title="Permalink to this headline">¶</a></h3>
  116. <p>A few mutation and crossover operators have been implemented, however it remains quite simple. What is interesting here is that it is possible to develop one’s own strategy for choosing operators for the next evaluation. The available UCBPolicy class proposes this functionality as an example, since it will seek to propose the best operator to apply based on a method known as Adaptive Operator Selection (AOS) via the use of the Upper Confidence Bound (UCB) algorithm.</p>
  117. </div>
  118. <div class="section" id="backup-feature">
  119. <h3>1.4 Backup feature<a class="headerlink" href="#backup-feature" title="Permalink to this headline">¶</a></h3>
  120. <p>The use of callback instance allows both to save every <cite>k</cite> evaluations of the information but also to reload them once the run of the algorithm is cut. Simply inherit the abstract Callback class and implement the <strong>apply</strong> method to backup and <strong>load</strong> to restore. It is possible to add as many callbacks as required.</p>
  121. </div>
  122. </div>
  123. <div class="section" id="mono-objective">
  124. <h2>2. Mono-objective<a class="headerlink" href="#mono-objective" title="Permalink to this headline">¶</a></h2>
  125. <p>In this tutorial, we introduce the way of using <cite>macop</cite> and running your algorithm quickly.
  126. First of all we need to define the kind of solution which best represent the problem. As example, we use the well known knapsack problem using 30 objects (solution size of 30).</p>
  127. <div class="section" id="problem-definition">
  128. <h3>2.1 Problem definition<a class="headerlink" href="#problem-definition" title="Permalink to this headline">¶</a></h3>
  129. <p>Hence, we define our problem :</p>
  130. <ul class="simple">
  131. <li><p>value of each component of knapsack</p></li>
  132. <li><p>weight associated to each of these components (objects)</p></li>
  133. </ul>
  134. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  135. <span class="sd">imports part</span>
  136. <span class="sd">&quot;&quot;&quot;</span>
  137. <span class="kn">import</span> <span class="nn">random</span>
  138. <span class="sd">&quot;&quot;&quot;</span>
  139. <span class="sd">Problem definition</span>
  140. <span class="sd">&quot;&quot;&quot;</span>
  141. <span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">42</span><span class="p">)</span>
  142. <span class="n">elements_score</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">30</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># value of each object</span>
  143. <span class="n">elements_weight</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="mi">25</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">30</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># weight of each object</span>
  144. </pre></div>
  145. </div>
  146. <p>We can now define the solution representation. In knapsack problem we want to fill our knapsack in an optimisation way selecting or not each component (object).
  147. The best way to represent this problem is to use the <cite>BinarySolution</cite> from <cite>macop</cite> which stores solution as a binary array.</p>
  148. <p>Using the solution representation, we need to define multiple elements to fit our algorithm :</p>
  149. <ul class="simple">
  150. <li><p>function which validates or not a solution (based on constraints)</p></li>
  151. <li><p>function which evaluates the solution (in order to obtain fitness)</p></li>
  152. <li><p>initialization solution function</p></li>
  153. </ul>
  154. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  155. <span class="sd">imports part</span>
  156. <span class="sd">&quot;&quot;&quot;</span>
  157. <span class="kn">import</span> <span class="nn">random</span>
  158. <span class="kn">from</span> <span class="nn">macop.solutions.BinarySolution</span> <span class="kn">import</span> <span class="n">BinarySolution</span>
  159. <span class="sd">&quot;&quot;&quot;</span>
  160. <span class="sd">Problem definition</span>
  161. <span class="sd">&quot;&quot;&quot;</span>
  162. <span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">42</span><span class="p">)</span>
  163. <span class="n">elements_score</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">30</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># value of each object</span>
  164. <span class="n">elements_weight</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="mi">25</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">30</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># weight of each object</span>
  165. <span class="c1"># 1. validator function (we accept only bag with maximum weight 80kg)</span>
  166. <span class="k">def</span> <span class="nf">validator</span><span class="p">(</span><span class="n">_solution</span><span class="p">):</span>
  167. <span class="n">weight_sum</span> <span class="o">=</span> <span class="mi">0</span>
  168. <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">elem</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">_solution</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
  169. <span class="n">weight_sum</span> <span class="o">+=</span> <span class="n">elements_weight</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">*</span> <span class="n">elem</span>
  170. <span class="k">if</span> <span class="n">weight_sum</span> <span class="o">&lt;=</span> <span class="mi">80</span><span class="p">:</span>
  171. <span class="k">return</span> <span class="kc">True</span>
  172. <span class="k">else</span><span class="p">:</span>
  173. <span class="kc">False</span>
  174. <span class="c1"># 2. function which computes fitness of solution</span>
  175. <span class="k">def</span> <span class="nf">evaluator</span><span class="p">(</span><span class="n">_solution</span><span class="p">):</span>
  176. <span class="n">fitness</span> <span class="o">=</span> <span class="mi">0</span>
  177. <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">elem</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">_solution</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
  178. <span class="n">fitness</span> <span class="o">+=</span> <span class="p">(</span><span class="n">elements_score</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">*</span> <span class="n">elem</span><span class="p">)</span>
  179. <span class="k">return</span> <span class="n">fitness</span>
  180. <span class="c1"># 3. function which here initializes solution ramdomly and check validity of solution</span>
  181. <span class="k">def</span> <span class="nf">init</span><span class="p">():</span>
  182. <span class="k">return</span> <span class="n">BinarySolution</span><span class="p">([],</span> <span class="mi">30</span><span class="p">)</span><span class="o">.</span><span class="n">random</span><span class="p">(</span><span class="n">validator</span><span class="p">)</span>
  183. </pre></div>
  184. </div>
  185. </div>
  186. <div class="section" id="operators-and-policy">
  187. <h3>2.2 Operators and Policy<a class="headerlink" href="#operators-and-policy" title="Permalink to this headline">¶</a></h3>
  188. <p>In our algorithm we need to use some operators in order to improve current best solution found at current <cite>n</cite> evaluations.</p>
  189. <p>In <cite>macop</cite> you have some available operators. In this example, we use 3 of them.</p>
  190. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  191. <span class="sd">imports part</span>
  192. <span class="sd">&quot;&quot;&quot;</span>
  193. <span class="o">...</span>
  194. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleMutation</span> <span class="kn">import</span> <span class="n">SimpleMutation</span>
  195. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleBinaryMutation</span> <span class="kn">import</span> <span class="n">SimpleBinaryMutation</span>
  196. <span class="kn">from</span> <span class="nn">macop.operators.crossovers.SimpleCrossover</span> <span class="kn">import</span> <span class="n">SimpleCrossover</span>
  197. <span class="sd">&quot;&quot;&quot;</span>
  198. <span class="sd">Problem definition</span>
  199. <span class="sd">&quot;&quot;&quot;</span>
  200. <span class="o">...</span>
  201. <span class="sd">&quot;&quot;&quot;</span>
  202. <span class="sd">Algorithm parameters</span>
  203. <span class="sd">&quot;&quot;&quot;</span>
  204. <span class="c1"># list of operators instance to use</span>
  205. <span class="n">operators</span> <span class="o">=</span> <span class="p">[</span><span class="n">SimpleBinaryMutation</span><span class="p">(),</span> <span class="n">SimpleMutation</span><span class="p">(),</span> <span class="n">SimpleCrossover</span><span class="p">(),</span> <span class="n">RandomSplitCrossover</span><span class="p">()]</span>
  206. </pre></div>
  207. </div>
  208. <p>As we defined multiple operators, we have to tell how we want to select them into the algorithm. This is why <strong>Policy</strong> classes have been implemented.
  209. <cite>Policy</cite> class implementation enables to select the next operator to use and once new solution is generated, computes its score (in <cite>apply</cite> method). This class requires all the operators use to be instanciate.</p>
  210. <p>Why computing score into <strong>Policy</strong> <cite>apply</cite> method ? Because it’s a way to get some important statistics from solution improvment using specific operator.
  211. <strong>UCBPolicy</strong> as example, based on Upper Confidence Bound (<a class="reference external" href="https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/">UCB</a>), computes reward each time a new solution is generated from an operator in order to better select next operator later. We use in this example the <cite>UCBPolicy</cite> implementation.</p>
  212. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  213. <span class="sd">imports part</span>
  214. <span class="sd">&quot;&quot;&quot;</span>
  215. <span class="o">...</span>
  216. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleMutation</span> <span class="kn">import</span> <span class="n">SimpleMutation</span>
  217. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleBinaryMutation</span> <span class="kn">import</span> <span class="n">SimpleBinaryMutation</span>
  218. <span class="kn">from</span> <span class="nn">macop.operators.crossovers.SimpleCrossover</span> <span class="kn">import</span> <span class="n">SimpleCrossover</span>
  219. <span class="kn">from</span> <span class="nn">macop.operators.policies.UCBPolicy</span> <span class="kn">import</span> <span class="n">UCBPolicy</span>
  220. <span class="sd">&quot;&quot;&quot;</span>
  221. <span class="sd">Problem definition</span>
  222. <span class="sd">&quot;&quot;&quot;</span>
  223. <span class="o">...</span>
  224. <span class="sd">&quot;&quot;&quot;</span>
  225. <span class="sd">Algorithm parameters</span>
  226. <span class="sd">&quot;&quot;&quot;</span>
  227. <span class="c1"># list of operators instance to use</span>
  228. <span class="n">operators</span> <span class="o">=</span> <span class="p">[</span><span class="n">SimpleBinaryMutation</span><span class="p">(),</span> <span class="n">SimpleMutation</span><span class="p">(),</span> <span class="n">SimpleCrossover</span><span class="p">(),</span> <span class="n">RandomSplitCrossover</span><span class="p">()]</span>
  229. <span class="c1"># `policy` instance is created using specific value for Upper Confidence Bound</span>
  230. <span class="n">policy</span> <span class="o">=</span> <span class="n">UCBPolicy</span><span class="p">(</span><span class="n">operators</span><span class="p">,</span> <span class="n">C</span><span class="o">=</span><span class="mf">100.</span><span class="p">)</span>
  231. </pre></div>
  232. </div>
  233. </div>
  234. <div class="section" id="before-running-algorithm">
  235. <h3>2.3 Before running algorithm<a class="headerlink" href="#before-running-algorithm" title="Permalink to this headline">¶</a></h3>
  236. <p>Before running algorithm we can define a logger to keep track of the all algorithm run.</p>
  237. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  238. <span class="sd">imports part</span>
  239. <span class="sd">&quot;&quot;&quot;</span>
  240. <span class="o">...</span>
  241. <span class="kn">import</span> <span class="nn">logging</span>
  242. <span class="sd">&quot;&quot;&quot;</span>
  243. <span class="sd">Problem definition</span>
  244. <span class="sd">&quot;&quot;&quot;</span>
  245. <span class="o">...</span>
  246. <span class="sd">&quot;&quot;&quot;</span>
  247. <span class="sd">Algorithm parameters</span>
  248. <span class="sd">&quot;&quot;&quot;</span>
  249. <span class="o">...</span>
  250. <span class="k">if</span> <span class="ow">not</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">exists</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">):</span>
  251. <span class="n">os</span><span class="o">.</span><span class="n">makedirs</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">)</span>
  252. <span class="c1"># logging configuration</span>
  253. <span class="n">logging</span><span class="o">.</span><span class="n">basicConfig</span><span class="p">(</span><span class="nb">format</span><span class="o">=</span><span class="s1">&#39;</span><span class="si">%(asctime)s</span><span class="s1"> </span><span class="si">%(message)s</span><span class="s1">&#39;</span><span class="p">,</span> <span class="n">filename</span><span class="o">=</span><span class="s1">&#39;data/example.log&#39;</span><span class="p">,</span> <span class="n">level</span><span class="o">=</span><span class="n">logging</span><span class="o">.</span><span class="n">DEBUG</span><span class="p">)</span>
  254. </pre></div>
  255. </div>
  256. <p>We can now instanciate our algorithm. We use the Iterated Local Search in this example. It is mainly used to avoid local optima using multiple local search.</p>
  257. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  258. <span class="sd">imports part</span>
  259. <span class="sd">&quot;&quot;&quot;</span>
  260. <span class="o">...</span>
  261. <span class="kn">import</span> <span class="nn">logging</span>
  262. <span class="kn">from</span> <span class="nn">macop.algorithms.mono.IteratedLocalSearch</span> <span class="kn">import</span> <span class="n">IteratedLocalSearch</span> <span class="k">as</span> <span class="n">ILS</span>
  263. <span class="sd">&quot;&quot;&quot;</span>
  264. <span class="sd">Problem definition</span>
  265. <span class="sd">&quot;&quot;&quot;</span>
  266. <span class="o">...</span>
  267. <span class="sd">&quot;&quot;&quot;</span>
  268. <span class="sd">Algorithm parameters</span>
  269. <span class="sd">&quot;&quot;&quot;</span>
  270. <span class="o">...</span>
  271. <span class="k">if</span> <span class="ow">not</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">exists</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">):</span>
  272. <span class="n">os</span><span class="o">.</span><span class="n">makedirs</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">)</span>
  273. <span class="c1"># logging configuration</span>
  274. <span class="n">logging</span><span class="o">.</span><span class="n">basicConfig</span><span class="p">(</span><span class="nb">format</span><span class="o">=</span><span class="s1">&#39;</span><span class="si">%(asctime)s</span><span class="s1"> </span><span class="si">%(message)s</span><span class="s1">&#39;</span><span class="p">,</span> <span class="n">filename</span><span class="o">=</span><span class="s1">&#39;data/example.log&#39;</span><span class="p">,</span> <span class="n">level</span><span class="o">=</span><span class="n">logging</span><span class="o">.</span><span class="n">DEBUG</span><span class="p">)</span>
  275. <span class="n">algo</span> <span class="o">=</span> <span class="n">ILS</span><span class="p">(</span><span class="n">init</span><span class="p">,</span> <span class="n">evaluator</span><span class="p">,</span> <span class="n">operators</span><span class="p">,</span> <span class="n">policy</span><span class="p">,</span> <span class="n">validator</span><span class="p">,</span> <span class="n">_maximise</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
  276. </pre></div>
  277. </div>
  278. <p>The algorithm is now well defined and is ready to run ! But one thing can be done, and it’s very interesting to avoid restart from scratch the algorithm run.
  279. The use of checkpoint is available in <cite>macop</cite>. A <cite>BasicCheckpoint</cite> class let the algorithm save at <cite>every</cite> evaluations the best solution found. This class is based on callback process.
  280. A Callback is runned every number of evaluations but can also implement the <cite>load</cite> method in order to do specific instrusctions when initializing algorithm.</p>
  281. <p>It’s important to note, we can add any number of callbacks we want. For tabu search as example, we need to store many solutions.</p>
  282. <p>In our case, we need to specify the use of checkpoint if we prefer to restart from.</p>
  283. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  284. <span class="sd">imports part</span>
  285. <span class="sd">&quot;&quot;&quot;</span>
  286. <span class="o">...</span>
  287. <span class="kn">import</span> <span class="nn">logging</span>
  288. <span class="kn">from</span> <span class="nn">macop.algorithms.mono.IteratedLocalSearch</span> <span class="kn">import</span> <span class="n">IteratedLocalSearch</span> <span class="k">as</span> <span class="n">ILS</span>
  289. <span class="kn">from</span> <span class="nn">macop.callbacks.BasicCheckpoint</span> <span class="kn">import</span> <span class="n">BasicCheckpoint</span>
  290. <span class="sd">&quot;&quot;&quot;</span>
  291. <span class="sd">Problem definition</span>
  292. <span class="sd">&quot;&quot;&quot;</span>
  293. <span class="o">...</span>
  294. <span class="sd">&quot;&quot;&quot;</span>
  295. <span class="sd">Algorithm parameters</span>
  296. <span class="sd">&quot;&quot;&quot;</span>
  297. <span class="o">...</span>
  298. <span class="k">if</span> <span class="ow">not</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">exists</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">):</span>
  299. <span class="n">os</span><span class="o">.</span><span class="n">makedirs</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">)</span>
  300. <span class="c1"># logging configuration</span>
  301. <span class="n">logging</span><span class="o">.</span><span class="n">basicConfig</span><span class="p">(</span><span class="nb">format</span><span class="o">=</span><span class="s1">&#39;</span><span class="si">%(asctime)s</span><span class="s1"> </span><span class="si">%(message)s</span><span class="s1">&#39;</span><span class="p">,</span> <span class="n">filename</span><span class="o">=</span><span class="s1">&#39;data/example.log&#39;</span><span class="p">,</span> <span class="n">level</span><span class="o">=</span><span class="n">logging</span><span class="o">.</span><span class="n">DEBUG</span><span class="p">)</span>
  302. <span class="n">algo</span> <span class="o">=</span> <span class="n">ILS</span><span class="p">(</span><span class="n">init</span><span class="p">,</span> <span class="n">evaluator</span><span class="p">,</span> <span class="n">operators</span><span class="p">,</span> <span class="n">policy</span><span class="p">,</span> <span class="n">validator</span><span class="p">,</span> <span class="n">_maximise</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
  303. <span class="c1"># create instance of BasicCheckpoint callback</span>
  304. <span class="n">callback</span> <span class="o">=</span> <span class="n">BasicCheckpoint</span><span class="p">(</span><span class="n">_every</span><span class="o">=</span><span class="mi">5</span><span class="p">,</span> <span class="n">_filepath</span><span class="o">=</span><span class="s1">&#39;data/checkpoint.csv&#39;</span><span class="p">)</span>
  305. <span class="c1"># Add this callback instance into list of callback</span>
  306. <span class="c1"># It tells the algorithm to apply this callback every 5 evaluations</span>
  307. <span class="c1"># And also the algorithm to load checkpoint if exists before running by using `load` method of callback</span>
  308. <span class="n">algo</span><span class="o">.</span><span class="n">addCallback</span><span class="p">(</span><span class="n">callback</span><span class="p">)</span>
  309. </pre></div>
  310. </div>
  311. <p>We can also add the <cite>UCBCheckpoint</cite> callback which keeps track of UCB data obtained during previous run:</p>
  312. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  313. <span class="sd">imports part</span>
  314. <span class="sd">&quot;&quot;&quot;</span>
  315. <span class="o">...</span>
  316. <span class="kn">import</span> <span class="nn">logging</span>
  317. <span class="kn">from</span> <span class="nn">macop.callbacks.UCBCheckpoint</span> <span class="kn">import</span> <span class="n">UCBCheckpoint</span>
  318. <span class="sd">&quot;&quot;&quot;</span>
  319. <span class="sd">Problem definition</span>
  320. <span class="sd">&quot;&quot;&quot;</span>
  321. <span class="o">...</span>
  322. <span class="sd">&quot;&quot;&quot;</span>
  323. <span class="sd">Algorithm parameters</span>
  324. <span class="sd">&quot;&quot;&quot;</span>
  325. <span class="o">...</span>
  326. <span class="c1"># add UCB Checkpoint callback to keep track of UCB statistics obtained</span>
  327. <span class="n">algo</span><span class="o">.</span><span class="n">addCallback</span><span class="p">(</span><span class="n">UCBCheckpoint</span><span class="p">(</span><span class="n">_every</span><span class="o">=</span><span class="mi">5</span><span class="p">,</span> <span class="n">_filepath</span><span class="o">=</span><span class="s1">&#39;data/ucbPolicy.csv&#39;</span><span class="p">))</span>
  328. </pre></div>
  329. </div>
  330. <p>In this way, now we can run and obtained the best solution found in <cite>n</cite> evaluations</p>
  331. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">bestSol</span> <span class="o">=</span> <span class="n">algo</span><span class="o">.</span><span class="n">run</span><span class="p">(</span><span class="mi">10000</span><span class="p">)</span>
  332. <span class="nb">print</span><span class="p">(</span><span class="s1">&#39;Solution score is </span><span class="si">{}</span><span class="s1">&#39;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="n">evaluator</span><span class="o">.</span><span class="n">compute</span><span class="p">(</span><span class="n">bestSol</span><span class="p">)))</span>
  333. </pre></div>
  334. </div>
  335. </div>
  336. </div>
  337. <div class="section" id="multi-objective">
  338. <h2>3. Multi-objective<a class="headerlink" href="#multi-objective" title="Permalink to this headline">¶</a></h2>
  339. <div class="section" id="id1">
  340. <h3>3.1 Problem definition<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
  341. <p>In this example we also use the knapsack problem, with here, 2 kinds of value for each object in the knapsack :</p>
  342. <ul class="simple">
  343. <li><p>value 1 of each component of knapsack</p></li>
  344. <li><p>value 2 of each component of knapsack</p></li>
  345. <li><p>weight associated to each of these components (objects)</p></li>
  346. </ul>
  347. <p>In multi-objective algorithm, we do not only found one solution but a set of non-dominated solutions called Pareto front as we have multiple objectives.</p>
  348. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  349. <span class="sd">imports part</span>
  350. <span class="sd">&quot;&quot;&quot;</span>
  351. <span class="kn">import</span> <span class="nn">random</span>
  352. <span class="sd">&quot;&quot;&quot;</span>
  353. <span class="sd">Problem definition</span>
  354. <span class="sd">&quot;&quot;&quot;</span>
  355. <span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">42</span><span class="p">)</span>
  356. <span class="n">elements_score1</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">200</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># value 1 of each object</span>
  357. <span class="n">elements_score2</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">200</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># value 2 of each object</span>
  358. <span class="n">elements_weight</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="mi">25</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">200</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># weight of each object</span>
  359. </pre></div>
  360. </div>
  361. <p>We can now define the solution representation. In knapsack problem we want to fill our knapsack in an optimisation way selecting or not each component (object).
  362. The best way to represent this problem is to use the <cite>BinarySolution</cite> from <cite>macop</cite> which stores solution as a binary array.</p>
  363. <p>Using the solution representation, we need to define multiple elements to fit our algorithm :</p>
  364. <ul class="simple">
  365. <li><p>function which validates or not a solution (based on constraints)</p></li>
  366. <li><p>the first objective function which evaluates the solution (fitness score for objective 1)</p></li>
  367. <li><p>the second objective function which evaluates the solution (fitness score for objective 2)</p></li>
  368. <li><p>initialization solution function</p></li>
  369. </ul>
  370. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  371. <span class="sd">imports part</span>
  372. <span class="sd">&quot;&quot;&quot;</span>
  373. <span class="kn">import</span> <span class="nn">random</span>
  374. <span class="kn">from</span> <span class="nn">macop.solutions.BinarySolution</span> <span class="kn">import</span> <span class="n">BinarySolution</span>
  375. <span class="sd">&quot;&quot;&quot;</span>
  376. <span class="sd">Problem definition</span>
  377. <span class="sd">&quot;&quot;&quot;</span>
  378. <span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">42</span><span class="p">)</span>
  379. <span class="n">elements_score1</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">200</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># value 1 of each object</span>
  380. <span class="n">elements_score2</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">200</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># value 2 of each object</span>
  381. <span class="n">elements_weight</span> <span class="o">=</span> <span class="p">[</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="mi">25</span><span class="p">)</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">200</span><span class="p">)</span> <span class="p">]</span> <span class="c1"># weight of each object</span>
  382. <span class="c1"># 1. validator function (we accept only bag with maximum weight 80kg)</span>
  383. <span class="k">def</span> <span class="nf">validator</span><span class="p">(</span><span class="n">_solution</span><span class="p">):</span>
  384. <span class="n">weight_sum</span> <span class="o">=</span> <span class="mi">0</span>
  385. <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">elem</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">_solution</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
  386. <span class="n">weight_sum</span> <span class="o">+=</span> <span class="n">elements_weight</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">*</span> <span class="n">elem</span>
  387. <span class="k">if</span> <span class="n">weight_sum</span> <span class="o">&lt;=</span> <span class="mi">80</span><span class="p">:</span>
  388. <span class="k">return</span> <span class="kc">True</span>
  389. <span class="k">else</span><span class="p">:</span>
  390. <span class="kc">False</span>
  391. <span class="c1"># 2. functions which computes fitness of solution for the two objectives</span>
  392. <span class="k">def</span> <span class="nf">evaluator1</span><span class="p">(</span><span class="n">_solution</span><span class="p">):</span>
  393. <span class="n">fitness</span> <span class="o">=</span> <span class="mi">0</span>
  394. <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">elem</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">_solution</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
  395. <span class="n">fitness</span> <span class="o">+=</span> <span class="p">(</span><span class="n">elements_score1</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">*</span> <span class="n">elem</span><span class="p">)</span>
  396. <span class="k">return</span> <span class="n">fitness</span>
  397. <span class="k">def</span> <span class="nf">evaluator2</span><span class="p">(</span><span class="n">_solution</span><span class="p">):</span>
  398. <span class="n">fitness</span> <span class="o">=</span> <span class="mi">0</span>
  399. <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">elem</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">_solution</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
  400. <span class="n">fitness</span> <span class="o">+=</span> <span class="p">(</span><span class="n">elements_score2</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">*</span> <span class="n">elem</span><span class="p">)</span>
  401. <span class="k">return</span> <span class="n">fitness</span>
  402. <span class="c1"># 3. function which here initializes solution ramdomly and check validity of solution</span>
  403. <span class="k">def</span> <span class="nf">init</span><span class="p">():</span>
  404. <span class="k">return</span> <span class="n">BinarySolution</span><span class="p">([],</span> <span class="mi">200</span><span class="p">)</span><span class="o">.</span><span class="n">random</span><span class="p">(</span><span class="n">validator</span><span class="p">)</span>
  405. </pre></div>
  406. </div>
  407. </div>
  408. <div class="section" id="id2">
  409. <h3>3.2 Operators and Policy<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h3>
  410. <p>In our algorithm we need to use some operators in order to improve current best solution found at current <cite>n</cite> evaluations.</p>
  411. <p>In <cite>macop</cite> you have some available operators. In this example, we use 3 of them.</p>
  412. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  413. <span class="sd">imports part</span>
  414. <span class="sd">&quot;&quot;&quot;</span>
  415. <span class="o">...</span>
  416. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleMutation</span> <span class="kn">import</span> <span class="n">SimpleMutation</span>
  417. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleBinaryMutation</span> <span class="kn">import</span> <span class="n">SimpleBinaryMutation</span>
  418. <span class="kn">from</span> <span class="nn">macop.operators.crossovers.SimpleCrossover</span> <span class="kn">import</span> <span class="n">SimpleCrossover</span>
  419. <span class="sd">&quot;&quot;&quot;</span>
  420. <span class="sd">Problem definition</span>
  421. <span class="sd">&quot;&quot;&quot;</span>
  422. <span class="o">...</span>
  423. <span class="sd">&quot;&quot;&quot;</span>
  424. <span class="sd">Algorithm parameters</span>
  425. <span class="sd">&quot;&quot;&quot;</span>
  426. <span class="c1"># list of operators instance to use</span>
  427. <span class="n">operators</span> <span class="o">=</span> <span class="p">[</span><span class="n">SimpleBinaryMutation</span><span class="p">(),</span> <span class="n">SimpleMutation</span><span class="p">(),</span> <span class="n">SimpleCrossover</span><span class="p">(),</span> <span class="n">RandomSplitCrossover</span><span class="p">()]</span>
  428. </pre></div>
  429. </div>
  430. <p>As we defined multiple operators, we have to tell how we want to select them into the algorithm. This is why <strong>Policy</strong> classes have been implemented.
  431. <cite>Policy</cite> class implementation enables to select the next operator to use and once new solution is generated, computes its score (in <cite>apply</cite> method). This class requires all the operators use to be instanciate.</p>
  432. <p>Why computing score into <strong>Policy</strong> <cite>apply</cite> method ? Because it’s a way to get some important statistics from solution improvment using specific operator.
  433. <strong>UCBPolicy</strong> as example, based on Upper Confidence Bound (<a class="reference external" href="https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/">UCB</a>), computes reward each time a new solution is generated from an operator in order to better select next operator later. We use in this example the <cite>UCBPolicy</cite> implementation.</p>
  434. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  435. <span class="sd">imports part</span>
  436. <span class="sd">&quot;&quot;&quot;</span>
  437. <span class="o">...</span>
  438. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleMutation</span> <span class="kn">import</span> <span class="n">SimpleMutation</span>
  439. <span class="kn">from</span> <span class="nn">macop.operators.mutators.SimpleBinaryMutation</span> <span class="kn">import</span> <span class="n">SimpleBinaryMutation</span>
  440. <span class="kn">from</span> <span class="nn">macop.operators.crossovers.SimpleCrossover</span> <span class="kn">import</span> <span class="n">SimpleCrossover</span>
  441. <span class="kn">from</span> <span class="nn">macop.operators.policies.UCBPolicy</span> <span class="kn">import</span> <span class="n">UCBPolicy</span>
  442. <span class="sd">&quot;&quot;&quot;</span>
  443. <span class="sd">Problem definition</span>
  444. <span class="sd">&quot;&quot;&quot;</span>
  445. <span class="o">...</span>
  446. <span class="sd">&quot;&quot;&quot;</span>
  447. <span class="sd">Algorithm parameters</span>
  448. <span class="sd">&quot;&quot;&quot;</span>
  449. <span class="c1"># list of operators instance to use</span>
  450. <span class="n">operators</span> <span class="o">=</span> <span class="p">[</span><span class="n">SimpleBinaryMutation</span><span class="p">(),</span> <span class="n">SimpleMutation</span><span class="p">(),</span> <span class="n">SimpleCrossover</span><span class="p">(),</span> <span class="n">RandomSplitCrossover</span><span class="p">()]</span>
  451. <span class="c1"># `policy` instance is created using specific value for Upper Confidence Bound</span>
  452. <span class="n">policy</span> <span class="o">=</span> <span class="n">UCBPolicy</span><span class="p">(</span><span class="n">operators</span><span class="p">,</span> <span class="n">C</span><span class="o">=</span><span class="mf">100.</span><span class="p">)</span>
  453. </pre></div>
  454. </div>
  455. </div>
  456. <div class="section" id="how-works-multi-objective-in-macop">
  457. <h3>3.3 How works multi-objective in macop ?<a class="headerlink" href="#how-works-multi-objective-in-macop" title="Permalink to this headline">¶</a></h3>
  458. <p>As we have now multiple objectives, we define a new algorithm named MOEAD for <cite>MultiObjective Evolutionary Algorithm with Decomposition</cite> inside <cite>macop.algorithms.multi.MOEAD</cite>.
  459. The principle of this algorithm is to decompose the multi-objective problem into several single-objective problems (see <a class="reference external" href="https://sites.google.com/view/moead/home">MOEAD</a> documentation framework).
  460. To implement this algorithm, we now define the attribute <cite>evaluator</cite> as a list of evaluators. The number of objectives is defined by the length of this list and generated weights for each sub problem too.</p>
  461. <p>The <cite>mu</cite> attribute represent the number of sub problems and hence our current population of solutions.</p>
  462. <p>In order to represent the <cite>mu</cite> mono-objective sub problems (obtained from weighted decomposition), we define the <cite>macop.algorithms.multi.MOSubProblem</cite> class.
  463. This class enables to compute and find best solution from weighted decomposition. The <cite>weights</cite> attribute of this class stores the weight for each objective of this sub problem instance.</p>
  464. <p>The <cite>evaluator</cite> of MOSubProblem is defined as below:</p>
  465. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">moEvaluator</span><span class="p">(</span><span class="n">_solution</span><span class="p">,</span> <span class="n">_evaluator</span><span class="p">,</span> <span class="n">_weights</span><span class="p">):</span>
  466. <span class="n">scores</span> <span class="o">=</span> <span class="p">[</span><span class="nb">eval</span><span class="p">(</span><span class="n">_solution</span><span class="p">)</span> <span class="k">for</span> <span class="nb">eval</span> <span class="ow">in</span> <span class="n">_evaluator</span><span class="p">]</span>
  467. <span class="c1"># associate objectives scores to solution</span>
  468. <span class="n">_solution</span><span class="o">.</span><span class="n">scores</span> <span class="o">=</span> <span class="n">scores</span>
  469. <span class="c1"># return the weighted sum</span>
  470. <span class="k">return</span> <span class="nb">sum</span><span class="p">([</span><span class="n">scores</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="k">for</span> <span class="n">i</span><span class="p">,</span> <span class="n">w</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">_weights</span><span class="p">)])</span>
  471. <span class="o">...</span>
  472. <span class="c1"># compute weighted sum from solution using list of evaluators and weights for current sub problem</span>
  473. <span class="n">sub_evaluator</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">_solution</span><span class="p">:</span> <span class="n">moEvaluator</span><span class="p">(</span><span class="n">_solution</span><span class="p">,</span> <span class="n">_evaluator</span><span class="p">,</span> <span class="n">weights</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
  474. </pre></div>
  475. </div>
  476. <p>This function computes the weighted sum of objectives (to transform sub problem into mono-objective) and also stores the objectives scores into solution using the dynamic added <cite>scores</cite> attributes.
  477. This is an example, we based our function using classical weighted sum, we can also implement <a class="reference external" href="https://repository.lib.ncsu.edu/handle/1840.16/272">Tchebychev</a> method.</p>
  478. <p>We can now instance our MOEAD algorithm:</p>
  479. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  480. <span class="sd">imports part</span>
  481. <span class="sd">&quot;&quot;&quot;</span>
  482. <span class="o">...</span>
  483. <span class="kn">import</span> <span class="nn">logging</span>
  484. <span class="kn">from</span> <span class="nn">macop.algorithms.multi.MOEAD</span> <span class="kn">import</span> <span class="n">MOEAD</span>
  485. <span class="sd">&quot;&quot;&quot;</span>
  486. <span class="sd">Problem definition</span>
  487. <span class="sd">&quot;&quot;&quot;</span>
  488. <span class="o">...</span>
  489. <span class="sd">&quot;&quot;&quot;</span>
  490. <span class="sd">Algorithm parameters</span>
  491. <span class="sd">&quot;&quot;&quot;</span>
  492. <span class="o">...</span>
  493. <span class="k">if</span> <span class="ow">not</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">exists</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">):</span>
  494. <span class="n">os</span><span class="o">.</span><span class="n">makedirs</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">)</span>
  495. <span class="c1"># logging configuration</span>
  496. <span class="n">logging</span><span class="o">.</span><span class="n">basicConfig</span><span class="p">(</span><span class="nb">format</span><span class="o">=</span><span class="s1">&#39;</span><span class="si">%(asctime)s</span><span class="s1"> </span><span class="si">%(message)s</span><span class="s1">&#39;</span><span class="p">,</span> <span class="n">filename</span><span class="o">=</span><span class="s1">&#39;data/example.log&#39;</span><span class="p">,</span> <span class="n">level</span><span class="o">=</span><span class="n">logging</span><span class="o">.</span><span class="n">DEBUG</span><span class="p">)</span>
  497. <span class="n">algo</span> <span class="o">=</span> <span class="n">MOEAD</span><span class="p">(</span><span class="n">init</span><span class="p">,</span> <span class="p">[</span><span class="n">evaluator1</span><span class="p">,</span> <span class="n">evaluator2</span><span class="p">],</span> <span class="n">operators</span><span class="p">,</span> <span class="n">policy</span><span class="p">,</span> <span class="n">validator</span><span class="p">,</span> <span class="n">_maximise</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
  498. </pre></div>
  499. </div>
  500. </div>
  501. <div class="section" id="checkpoint-multi-objective-solutions">
  502. <h3>3.4 Checkpoint multi-objective solutions<a class="headerlink" href="#checkpoint-multi-objective-solutions" title="Permalink to this headline">¶</a></h3>
  503. <p>To keep track of our <cite>mu</cite> population and <cite>pfPop</cite> pareto front set, 2 new callbacks have been defined:</p>
  504. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  505. <span class="sd">imports part</span>
  506. <span class="sd">&quot;&quot;&quot;</span>
  507. <span class="o">...</span>
  508. <span class="kn">import</span> <span class="nn">logging</span>
  509. <span class="kn">from</span> <span class="nn">macop.algorithms.multi.MOEAD</span> <span class="kn">import</span> <span class="n">MOEAD</span>
  510. <span class="kn">from</span> <span class="nn">macop.callbacks.MultiCheckpoint</span> <span class="kn">import</span> <span class="n">MultiCheckpoint</span>
  511. <span class="kn">from</span> <span class="nn">macop.callbacks.ParetoCheckpoint</span> <span class="kn">import</span> <span class="n">ParetoCheckpoint</span>
  512. <span class="sd">&quot;&quot;&quot;</span>
  513. <span class="sd">Problem definition</span>
  514. <span class="sd">&quot;&quot;&quot;</span>
  515. <span class="o">...</span>
  516. <span class="sd">&quot;&quot;&quot;</span>
  517. <span class="sd">Algorithm parameters</span>
  518. <span class="sd">&quot;&quot;&quot;</span>
  519. <span class="o">...</span>
  520. <span class="k">if</span> <span class="ow">not</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">exists</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">):</span>
  521. <span class="n">os</span><span class="o">.</span><span class="n">makedirs</span><span class="p">(</span><span class="s1">&#39;data&#39;</span><span class="p">)</span>
  522. <span class="c1"># logging configuration</span>
  523. <span class="n">logging</span><span class="o">.</span><span class="n">basicConfig</span><span class="p">(</span><span class="nb">format</span><span class="o">=</span><span class="s1">&#39;</span><span class="si">%(asctime)s</span><span class="s1"> </span><span class="si">%(message)s</span><span class="s1">&#39;</span><span class="p">,</span> <span class="n">filename</span><span class="o">=</span><span class="s1">&#39;data/example.log&#39;</span><span class="p">,</span> <span class="n">level</span><span class="o">=</span><span class="n">logging</span><span class="o">.</span><span class="n">DEBUG</span><span class="p">)</span>
  524. <span class="n">algo</span> <span class="o">=</span> <span class="n">ILS</span><span class="p">(</span><span class="n">init</span><span class="p">,</span> <span class="n">evaluator</span><span class="p">,</span> <span class="n">operators</span><span class="p">,</span> <span class="n">policy</span><span class="p">,</span> <span class="n">validator</span><span class="p">,</span> <span class="n">_maximise</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
  525. <span class="c1"># Add this callback instance into list of callback</span>
  526. <span class="c1"># It tells the algorithm to apply this callback every 5 evaluations</span>
  527. <span class="c1"># And also the algorithm to load checkpoint if exists before running by using `load` method of callback</span>
  528. <span class="n">algo</span><span class="o">.</span><span class="n">addCallback</span><span class="p">(</span><span class="n">MultiCheckpoint</span><span class="p">(</span><span class="n">_every</span><span class="o">=</span><span class="mi">5</span><span class="p">,</span> <span class="n">_filepath</span><span class="o">=</span><span class="s1">&#39;data/checkpointMOEAD.csv&#39;</span><span class="p">))</span>
  529. <span class="c1"># add Pareto Checkpoint callback instance too</span>
  530. <span class="n">algo</span><span class="o">.</span><span class="n">addCallback</span><span class="p">(</span><span class="n">ParetoCheckpoint</span><span class="p">(</span><span class="n">_every</span><span class="o">=</span><span class="mi">5</span><span class="p">,</span> <span class="n">_filepath</span><span class="o">=</span><span class="s1">&#39;data/paretoMOEAD.csv&#39;</span><span class="p">))</span>
  531. </pre></div>
  532. </div>
  533. <p>These callbacks only stores the last states of <cite>mu</cite> population and <cite>pfPop</cite>.</p>
  534. <p>We can also add the <cite>UCBCheckpoint</cite> callback which keeps track of UCB data obtained during previous run:</p>
  535. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="sd">&quot;&quot;&quot;</span>
  536. <span class="sd">imports part</span>
  537. <span class="sd">&quot;&quot;&quot;</span>
  538. <span class="o">...</span>
  539. <span class="kn">import</span> <span class="nn">logging</span>
  540. <span class="kn">from</span> <span class="nn">macop.callbacks.UCBCheckpoint</span> <span class="kn">import</span> <span class="n">UCBCheckpoint</span>
  541. <span class="sd">&quot;&quot;&quot;</span>
  542. <span class="sd">Problem definition</span>
  543. <span class="sd">&quot;&quot;&quot;</span>
  544. <span class="o">...</span>
  545. <span class="sd">&quot;&quot;&quot;</span>
  546. <span class="sd">Algorithm parameters</span>
  547. <span class="sd">&quot;&quot;&quot;</span>
  548. <span class="o">...</span>
  549. <span class="c1"># add UCB Checkpoint callback to keep track of UCB statistics obtained</span>
  550. <span class="n">algo</span><span class="o">.</span><span class="n">addCallback</span><span class="p">(</span><span class="n">UCBCheckpoint</span><span class="p">(</span><span class="n">_every</span><span class="o">=</span><span class="mi">5</span><span class="p">,</span> <span class="n">_filepath</span><span class="o">=</span><span class="s1">&#39;data/ucbPolicy.csv&#39;</span><span class="p">))</span>
  551. </pre></div>
  552. </div>
  553. <p>We can now run the MOEAD algorithm instance:</p>
  554. <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">paretoFront</span> <span class="o">=</span> <span class="n">algo</span><span class="o">.</span><span class="n">run</span><span class="p">(</span><span class="mi">10000</span><span class="p">)</span>
  555. <span class="nb">print</span><span class="p">(</span><span class="s2">&quot;Pareto front is composed of&quot;</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">paretoFront</span><span class="p">),</span> <span class="s2">&quot;solutions&quot;</span><span class="p">)</span>
  556. </pre></div>
  557. </div>
  558. </div>
  559. </div>
  560. </div>
  561. </div>
  562. </div>
  563. <footer>
  564. <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
  565. <a href="contributing.html" class="btn btn-neutral float-right" title="Contributing" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
  566. <a href="documentations/solutions.html" class="btn btn-neutral float-left" title="3. Solutions" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
  567. </div>
  568. <hr/>
  569. <div role="contentinfo">
  570. <p>
  571. &copy; Copyright 2020, Jérôme BUISINE
  572. </p>
  573. </div>
  574. Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
  575. </footer>
  576. </div>
  577. </div>
  578. </section>
  579. </div>
  580. <script type="text/javascript">
  581. jQuery(function () {
  582. SphinxRtdTheme.Navigation.enable(true);
  583. });
  584. </script>
  585. </body>
  586. </html>