title: Genetic algorithm - Subset sum problem
body: <p>I have to do a project which using a genetic algorithm solves the subset sum problem. Unfortunately, when coding the algorithm I found a big problem ...</p>
  
  <p>My algorithm:</p>
  
  <ul>
  <li>as long as no solution was found and the number of steps is smaller than steps do:</li>
  <li>calculate the probability and then distribution function for each chromosome</li>
  <li>perform selection (roulette)</li>
  <li>select n chromosomes to be crossed</li>
  <li>perform the crossing (the crossing point is selected randomly)</li>
  <li>select m chromosomes to mutation</li>
  <li>perform mutations</li>
  <li>if you found a solution then stop</li>
  </ul>
  
  <p>(Algorithm was taken from the book "Genetic Algorithms + Data Structures = Evolution Programs, Chapter 2 ")
  Variables such as population size, amount of data, scope of data collection, number of steps, the number of mutations (in step), the number of crossings (in a step) is set rigidly in the program options.</p>
  
  <p>The problem is that after a certain (relatively small) number of steps in the population all the chromosomes are identical. The problem illustrates this graph:
  <a href="http://imageshack.us/m/96/7693/wykresb.png" rel="nofollow">http://imageshack.us/m/96/7693/wykresb.png</a></p>
  
  <p>What I'm doing wrong? How to fix it?
  Thanks in advance.</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>Here You can find logs from my app:
  <a href="http://paste.pocoo.org/show/391318/" rel="nofollow">http://paste.pocoo.org/show/391318/</a></p>
  
  <p>I think that roulette is not the best solution (as deong said). Mutations also need to improve.</p>