VB.NET - Genetic Algotithm - Knapsack Problem

Question

I have been working on the Knapsack problem using genetic algorithms. But I have run into a few difficulties...

First off the user generates a data set which is stored in a text document. From there I read the data in to the program.

I do fine getting the program to calculate fitness values, select parents, produce children, then mutate the children. But it for some reason only works when I have a low population. My program will consistently evolve when I have a low population, but is very inconsistent when I have a higher population.

For Example: When I have a population of around 10-200 the genetic algorithm runs flawlessly. But when I get to higher populations (around 300+), I will click run and nothing happens. Then I restart the program and use the same exact dataset and the program executes successfully.

I am not sure which part of my code is causing the problem, so If you need a piece of example code please tell me which part of code you would like (Parent Selection, Loading Data Set, etc).

Thanks Alot!

Answer 1

Perhaps the program memory constrained with the higher populations?

Answer 2

I guess there might be three reasons for that.

1) a bug in your code

This should be relatively straightforward to eliminate. Try writing some tests that check if particular parts of your program run correctly (e.g. Parent Selection, etc.). Try testing them against some small examples you can figure out on a piece of paper yourself.

2) out of memory problem - a mentioned by btreat

3) some algorithmic quirk

This will be more difficult to fight. I am just guessing, so I might be wrong, but I've seen algorithms that drastically change their behaviour when problem size exceeds some threshold. Not likely, but not impossible either. Here you could just see if slowly increasing the population size you can see a sudden shift in running times.