Body: <p>I'm working on SLAP (storage location assignment problem) using genetic algorithm implemented manually in the C++ programming language. The problem is fairly simple, we do have <code>N</code> products, which we want to allocate to <code>M</code> warehouse location slots (<code>N</code> might and might not be equal to <code>M</code>).</p>
  <p>Let's begin with the encoding of the chromosomes. The chromosome length is equal to number of products (i.e. each product is one gene). Each product has one integer value (allele value), representing the location its allocated to.</p>
  <p>Let me show you on simple example.</p>
  <pre><code>Products         Average picking rate        Location slots       Location number
  Prod1            0.4                         Location 1, slot 1   (1)   // 3rd best
  Prod2            0.3                         Location 1, slot 2   (2)   // 4th best
  Prod3            0.2                         Location 2, slot 1   (3)   // The best
  Prod4            0.1                         Location 2, slot 2   (4)   // 2nd best
  </code></pre>
  <p>We aim for optimal allocation of products (Prod1-4) to location slots (1-4). The better the allocation is, the faster we can process all the products in customer orders. Now let's say the Location 2 is closer to the warehouse entrance/exit, so its more attractive, and the lower the location slot number is, the faster we can pick product out of the location slot. So the optimal allocation should be:</p>
  <pre><code>Product     Location number
  Prod1       3
  Prod2       4
  Prod3       1
  Prod4       2
  </code></pre>
  <p>And expressed as the chromosome:</p>
  <pre><code>+---+---+---+---+
  | 3 | 4 | 1 | 2 |
  +---+---+---+---+
  </code></pre>
  <p>This allocation will lead to the best warehouse performance. Now let me show you my crossover operator (based on TSP crossover <a href="https://www.permutationcity.co.uk/projects/mutants/tsp.html" rel="nofollow noreferrer">https://www.permutationcity.co.uk/projects/mutants/tsp.html</a>):</p>
  <pre><code>void crossoverOrdered(std::vector&lt;int32_t&gt;&amp; lhsInd, std::vector&lt;int32_t&gt;&amp; rhsInd)
  {
      int32_t a, b;
      int32_t pos =  0;
      int32_t placeholder = -1;
      int32_t placeholderCount = 0;
  
      std::vector&lt;int32_t&gt; o1, o1_missing, o1_replacements;
      std::vector&lt;int32_t&gt; o2, o2_missing, o2_replacements;
  
      while(true)
      {
          do
          {
              a = randomFromInterval(pos, constants::numberDimensions);
              b = randomFromInterval(pos, constants::numberDimensions);
          }
          while(a == b);
  
          if(a &gt; b) std::swap(a, b);
  
          // Insert from first parent
          for(int32_t i = pos; i &lt; a; ++i)
          {
              o1.push_back(lhsInd.at(i));
              o2.push_back(rhsInd.at(i));
          }
  
          // Insert placeholders
          for(int32_t i = a; i &lt; b; ++i)
          {
              ++placeholderCount;
              o1.push_back(placeholder);
              o2.push_back(placeholder);
          }
  
          if(b &gt;= constants::numberDimensions - 1)
          {
              for(int32_t i = b; i &lt; constants::numberDimensions; ++i)
              {
                  o1.push_back(lhsInd.at(i));
                  o2.push_back(rhsInd.at(i));
              }
  
              break;
          }
          else
          {
              pos = b;
          }
      }
  
      // Find missing elements
      for(int32_t i = 0; i &lt; constants::problemMax; ++i)
      {
          if(std::find(o1.begin(), o1.end(), i) == o1.end()) o1_missing.push_back(i);
          if(std::find(o2.begin(), o2.end(), i) == o2.end()) o2_missing.push_back(i);
      }
  
      // Filter missing elements and leave only those which are in the second parent (keep the order)
      for(int32_t i = 0; i &lt; static_cast&lt;int32_t&gt;(rhsInd.size()); i++)
      {
          if(std::find(o1_missing.begin(), o1_missing.end(), rhsInd.at(i)) != o1_missing.end()) o1_replacements.push_back(rhsInd.at(i));
      }
  
      // Filter missing elements and leave only those which are in the second parent (keep the order)
      for(int32_t i = 0; i &lt; static_cast&lt;int32_t&gt;(lhsInd.size()); i++)
      {
          if(std::find(o2_missing.begin(), o2_missing.end(), lhsInd.at(i)) != o2_missing.end()) o2_replacements.push_back(lhsInd.at(i));
      }
  
      // Replace placeholders in offspring 1
      for(int32_t i = 0; i &lt; placeholderCount; ++i)
      {
              auto it = std::find(o1.begin(), o1.end(), placeholder);
              *it     = o1_replacements.at(i);
      }
  
      // Replace placeholders in offspring 2
      for(int32_t i = 0; i &lt; placeholderCount; ++i)
      {
              auto it = std::find(o2.begin(), o2.end(), placeholder);
              *it     = o2_replacements.at(i);
      }
  
      // Assign new offsprings
      lhsInd.assign(o1.begin(), o1.end());
      rhsInd.assign(o2.begin(), o2.end());
  }
  </code></pre>
  <p>My mutation operator(s):</p>
  <pre><code>void mutateOrdered(std::vector&lt;int32_t&gt;&amp; ind)
  {
      int32_t a, b;
  
      do
      {
          a = randomFromInterval(0, constants::numberDimensions);
          b = randomFromInterval(0, constants::numberDimensions);
      }
      while(a == b);
  
      std::rotate(ind.begin() + a, ind.begin() + b, ind.begin() + b + 1);
  }
  
  void mutateInverse(std::vector&lt;int32_t&gt;&amp; ind)
  {
      int32_t a, b;
  
      do
      {
          a = randomFromInterval(0, constants::numberDimensions);
          b = randomFromInterval(0, constants::numberDimensions);
      }
      while(a == b);
  
      if(a &gt; b) std::swap(a, b);
  
      std::reverse(ind.begin() + a, ind.begin() + b);
  }
  </code></pre>
  <p>I tried to use roulette, truncate, tournament and rank selection alorithms, but each with similar results.</p>
  <p>This is my configuration:</p>
  <pre><code>populationSize = 20
  selectionSize = 5
  eliteSize = 1
  probabilityCrossover = 0.6
  probabilityMutateIndividual = 0.4
  probabilityMutateGene = 0.2
  </code></pre>
  <p>My fitness function is fairly simple, since it's real number returned by simulation program which simulates picking of orders on the current allocation we gave it. Unfortunately I cannot provide this program as its confidential. It's just a real number representing how good the current allocation is, the better the allocation is, the lower the number is (i.e. its minimization problem).</p>
  <p><strong>The problem</strong></p>
  <p>This genetic algorithm can find better solutions than just random allocation, the problem is, it gets &quot;stuck&quot; after lets say few thousand generations and it fails to improve furthermore, even though there are better solutions, and it will go even 20k generations with exact same ellite chromosom (don't improve at all). I tried to increase crossover/mutation probability and population size but none of it worked. Thanks for any help.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-29T09:35:12.937Z
Comments.Text: Proper GA implementation should find options close to optimal in dozens, not thousands of iterations in such simple case.
  
  Why don't you look at other implementations, for instance, described here - https://stackoverflow.com/questions/2179823/genetic-algorithms and compare outcomes?
Comments.UserDisplayName: Stepan Novikov
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-29T10:28:16.370Z
Comments.Text: Well the example presented is really a minimal experiment possible, which can be optimized in just a few iterations. The problems of course occurs for hundreds of articles/slots. Sorry if I didn't make it clear. Although my friend already suggested me to remove a few individuals each iteration, and generate completely new ones, which sounds like a good advise to me and I will give it a chance.
Comments.UserDisplayName: kocica
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-29T10:56:23.750Z
Comments.Text: I see. I would recommend even not including chromosomes from a previous iteration into a new one at all - in my experience its speedup it a bit. Also using of Gray code will speed up things - https://en.wikipedia.org/wiki/Gray_code#Genetic_algorithms
Comments.UserDisplayName: Stepan Novikov
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-22T21:02:19.163Z
Comments.Text: In our genetic search stuff, we not only mix chromosomes for best of breed but we always prune duplicates (new and old) and then supplement the generation with random models to allow unexplored portions of the space to potentially influence future generations.
Comments.UserDisplayName: David Hoelzer
Tags: <genetic-algorithms><c++>
Title: Genetic algorithm stuck and cannot find an optimal solution
UserDisplayName: kocica
ThreadText: # Genetic algorithm stuck and cannot find an optimal solution
  
  (Asked by: username_0 on 2020-10-29)
  
  I'm working on SLAP (storage location assignment problem) using genetic algorithm implemented manually in the C++ programming language. The problem is fairly simple, we do have N products, which we want to allocate to M warehouse location slots (N might and might not be equal to M).
  Let's begin with the encoding of the chromosomes. The chromosome length is equal to number of products (i.e. each product is one gene). Each product has one integer value (allele value), representing the location its allocated to.
  Let me show you on simple example.
  Products         Average picking rate        Location slots       Location number
  Prod1            0.4                         Location 1, slot 1   (1)   // 3rd best
  Prod2            0.3                         Location 1, slot 2   (2)   // 4th best
  Prod3            0.2                         Location 2, slot 1   (3)   // The best
  Prod4            0.1                         Location 2, slot 2   (4)   // 2nd best
  
  We aim for optimal allocation of products (Prod1-4) to location slots (1-4). The better the allocation is, the faster we can process all the products in customer orders. Now let's say the Location 2 is closer to the warehouse entrance/exit, so its more attractive, and the lower the location slot number is, the faster we can pick product out of the location slot. So the optimal allocation should be:
  Product     Location number
  Prod1       3
  Prod2       4
  Prod3       1
  Prod4       2
  
  And expressed as the chromosome:
  +---+---+---+---+
  | 3 | 4 | 1 | 2 |
  +---+---+---+---+
  
  This allocation will lead to the best warehouse performance. Now let me show you my crossover operator (based on TSP crossover https://www.permutationcity.co.uk/projects/mutants/tsp.html):
  void crossoverOrdered(std::vector& lhsInd, std::vector& rhsInd)
  {
      int32_t a, b;
      int32_t pos =  0;
      int32_t placeholder = -1;
      int32_t placeholderCount = 0;
  
      std::vector o1, o1_missing, o1_replacements;
      std::vector o2, o2_missing, o2_replacements;
  
      while(true)
      {
          do
          {
              a = randomFromInterval(pos, constants::numberDimensions);
              b = randomFromInterval(pos, constants::numberDimensions);
          }
          while(a == b);
  
          if(a > b) std::swap(a, b);
  
          // Insert from first parent
          for(int32_t i = pos; i < a; ++i)
          {
              o1.push_back(lhsInd.at(i));
              o2.push_back(rhsInd.at(i));
          }
  
          // Insert placeholders
          for(int32_t i = a; i < b; ++i)
          {
              ++placeholderCount;
              o1.push_back(placeholder);
              o2.push_back(placeholder);
          }
  
          if(b >= constants::numberDimensions - 1)
          {
              for(int32_t i = b; i < constants::numberDimensions; ++i)
              {
                  o1.push_back(lhsInd.at(i));
                  o2.push_back(rhsInd.at(i));
              }
  
              break;
          }
          else
          {
              pos = b;
          }
      }
  
      // Find missing elements
      for(int32_t i = 0; i < constants::problemMax; ++i)
      {
          if(std::find(o1.begin(), o1.end(), i) == o1.end()) o1_missing.push_back(i);
          if(std::find(o2.begin(), o2.end(), i) == o2.end()) o2_missing.push_back(i);
      }
  
      // Filter missing elements and leave only those which are in the second parent (keep the order)
      for(int32_t i = 0; i < static_cast(rhsInd.size()); i++)
      {
          if(std::find(o1_missing.begin(), o1_missing.end(), rhsInd.at(i)) != o1_missing.end()) o1_replacements.push_back(rhsInd.at(i));
      }
  
      // Filter missing elements and leave only those which are in the second parent (keep the order)
      for(int32_t i = 0; i < static_cast(lhsInd.size()); i++)
      {
          if(std::find(o2_missing.begin(), o2_missing.end(), lhsInd.at(i)) != o2_missing.end()) o2_replacements.push_back(lhsInd.at(i));
      }
  
      // Replace placeholders in offspring 1
      for(int32_t i = 0; i < placeholderCount; ++i)
      {
              auto it = std::find(o1.begin(), o1.end(), placeholder);
              *it     = o1_replacements.at(i);
      }
  
      // Replace placeholders in offspring 2
      for(int32_t i = 0; i < placeholderCount; ++i)
      {
              auto it = std::find(o2.begin(), o2.end(), placeholder);
              *it     = o2_replacements.at(i);
      }
  
      // Assign new offsprings
      lhsInd.assign(o1.begin(), o1.end());
      rhsInd.assign(o2.begin(), o2.end());
  }
  
  My mutation operator(s):
  void mutateOrdered(std::vector& ind)
  {
      int32_t a, b;
  
      do
      {
          a = randomFromInterval(0, constants::numberDimensions);
          b = randomFromInterval(0, constants::numberDimensions);
      }
      while(a == b);
  
      std::rotate(ind.begin() + a, ind.begin() + b, ind.begin() + b + 1);
  }
  
  void mutateInverse(std::vector& ind)
  {
      int32_t a, b;
  
      do
      {
          a = randomFromInterval(0, constants::numberDimensions);
          b = randomFromInterval(0, constants::numberDimensions);
      }
      while(a == b);
  
      if(a > b) std::swap(a, b);
  
      std::reverse(ind.begin() + a, ind.begin() + b);
  }
  
  I tried to use roulette, truncate, tournament and rank selection alorithms, but each with similar results.
  This is my configuration:
  populationSize = 20
  selectionSize = 5
  eliteSize = 1
  probabilityCrossover = 0.6
  probabilityMutateIndividual = 0.4
  probabilityMutateGene = 0.2
  
  My fitness function is fairly simple, since it's real number returned by simulation program which simulates picking of orders on the current allocation we gave it. Unfortunately I cannot provide this program as its confidential. It's just a real number representing how good the current allocation is, the better the allocation is, the lower the number is (i.e. its minimization problem).
  The problem
  This genetic algorithm can find better solutions than just random allocation, the problem is, it gets "stuck" after lets say few thousand generations and it fails to improve furthermore, even though there are better solutions, and it will go even 20k generations with exact same ellite chromosom (don't improve at all). I tried to increase crossover/mutation probability and population size but none of it worked. Thanks for any help.
  
  **Tags:** genetic-algorithms, c++
  > **Comments:**
  > **username_1**: Proper GA implementation should find options close to optimal in dozens, not thousands of iterations in such simple case.  Why don't you look at other implementations, for instance, described here - https://stackoverflow.com/questions/2179823/genetic-algorithms and compare outcomes?  
  > **username_0**: Well the example presented is really a minimal experiment possible, which can be optimized in just a few iterations. The problems of course occurs for hundreds of articles/slots. Sorry if I didn't make it clear. Although my friend already suggested me to remove a few individuals each iteration, and generate completely new ones, which sounds like a good advise to me and I will give it a chance.  
  > **username_1**: I see. I would recommend even not including chromosomes from a previous iteration into a new one at all - in my experience its speedup it a bit. Also using of Gray code will speed up things - https://en.wikipedia.org/wiki/Gray_code#Genetic_algorithms  
  > **username_2**: In our genetic search stuff, we not only mix chromosomes for best of breed but we always prune duplicates (new and old) and then supplement the generation with random models to allow unexplored portions of the space to potentially influence future generations.  
  
  ---
  
  ## 0 answers
  
  