Genetic algorithm - Subset sum problem

Question

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 ...

My algorithm:

• as long as no solution was found and the number of steps is smaller than steps do:
• calculate the probability and then distribution function for each chromosome
• perform selection (roulette)
• select n chromosomes to be crossed
• perform the crossing (the crossing point is selected randomly)
• select m chromosomes to mutation
• perform mutations
• if you found a solution then stop

(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.

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: http://imageshack.us/m/96/7693/wykresb.png

What I'm doing wrong? How to fix it? Thanks in advance.

Edit:

Here You can find logs from my app: http://paste.pocoo.org/show/391318/

I think that roulette is not the best solution (as deong said). Mutations also need to improve.

Answer 1

I had a similar problem before, I wish it s the same as your's

First, you need to check (using any measuring metric) if chromosome A is better than chromosome B. This let you have a strict order of the chromosomes of your population and be able to sort your population.

Then, when you produce a new chromosome (either by mutation or crossover) you may be producing a chromosome that already exist in your population. Make sure not to include this in your population list.

In other words, make sure your list always contains different chromosomes and always sorted from best to worst !

Note: The genetic algorithms I work with are usually like this (this is the most general algorithm and most used):

• create P different chromosomes and add them to list Pop;
  1. while (no optimal solution is found && number of iteration < LIM)
  2. create new chromosomes using crossover, mutation or any other methods;
  3. add the created chromosome to list Pop
  4. sort the list Pop (from best-fit to worst-fit)
  5. select the first P different chromosomes and discard all other from Pop.
  6. end while