I'm developing a genetic algorithm to solve a two-dimensional knapsack problem. Currently, I'm testing with 50 itens, each one having a weight, volume, and value. Each cycle, 10(of my population of 500) of the best individuals survive to the next cycle, and in my tests at the end, these 10 are always the best possible solution, and a very small portion of the other 490 share that solution. Analysing the fitness graph, it seems to me that it is converging too fast to the optimal solution. However, how do I determine whether my algorithm is good and the problem I'm testing is just easy to solve, or if I'm forcing convergence too much, which could result in a premature convergence to a sub-optimal solution in more complex cases? Fitness graph below.
How to know whether i'm forcing convergence too much, if my GA converges to the RIGHT solution quickly?
203 views Asked by Eduard At
1
For this question there are lot of books. You can't tell if something is "overconvergenciated". You can use injection to be sure. That means that for example, if you have 5000 loops(in ideal world) every 1000th loop you inject some new material to population. This worked for me and this is also written everywhere(I guess)