Sign up ×

Recently i've been improving traditional genetic algorithm for multiknapsack problem. So My Improved Genetic Algorithm is working better then Traditional Genetic Algorithm. I tested. (i used publically available from OR-Library ( were used to test the GAs.) Does anybody know other improved GA. I wanted to compare with other improved genetic algorithm. Actually i searched in internet. But couldn't find good algorithm to compare.

share|improve this question
I'm not sure what you mean by "traditional genetic algorithm." There are so many different settings you can play with in a simple genetic algorithm (e.g. population size, mutation rate, crossover method, selection method, method of coding the solution in the genotype). It would be quite hard to find an algorithm that would provide you with a definite representative of genetic algorithms. – metaliving Jun 7 '10 at 11:38

3 Answers 3

There should be any number of decent GA methods against which you can compare. However, you should try to first clearly establish exactly which "traditional" GA method you have already tested.

One good method which I can recommend is the NSGA-II algorithm, which was developed for multi-objective optimization.

Take a look at the following for other ideas:

share|improve this answer

You can compare your solution only to problems with the exact same encoding and fitness function (meaning they are equivalent problems). If the problem is different any comparison becomes quickly irrelevant as the problem changes, since the fitness function is almost always ad-hoc for whatever you're trying to solve. In fact the fitness function is the only thing you need to code if you use a Genetic Algorithms toolkit, as everything else usually comes out of the box.

On the other end, if the fitness function is the same, then it makes sense to compare results given different parameters, such as different mutation rate, different implementations of crossover, or even completely different evolutionary paradigms, such as coevolution, gene expression, compared to standard GAs, and so on.

share|improve this answer
Yeah your really rite, I completely accept that. when i canged fitness function under a condition of problem. It was really working . So now i am changing some parameter such crossover rate, mutation rate. But actually these thing is already studied. I mean already constant almost like mutation depend on problem 1/n, something like that. Now what i am doing that i am modifying crossover operators. It was clearly understood to improve GA perforamnce. Currently my algorithm is working better than many algorithms anyway(i just tested on multiknapsack problem). But i am not enough for that. – user347918 Jul 1 '10 at 14:49
The world is too big sometimes when i don't understand something. The world is too small sometimes when i understand something kkk. Still working on . – user347918 Jul 1 '10 at 14:50

Are you trying to improve the state-of-the-art in multiknapsack solvers by the use of genetic algorithms? Or are you trying to advance the genetic algorithm technique by using multiknapsack as a test platform? (Can you clarify?)

Depending on which one is your goal, the answer to your question is entirely different. Since others have addressed the latter question, I'll assume the former.

There has been little major leaps and bounds over the basic genetic algorithm. The best improvement in solving the multiknapsack via the use of genetic algorithms would be to improve your encoding of the mutation and crossover operators which can make orders of magnitude of difference in the resulting performance and blow out of the water any tweaks to the fundamental genetic algorithm. There is a lot you can do to make your mutation and crossover operators tailored to multiknapsack.

I would first survey the literature on multiknapsack to see what are the different kinds of search spaces and solution techniques people have used on multiknapsack. In their optimal or suboptimal methods (independent of genetic algorithms), what kinds of search operators do they use? What do they encode as variables and what do they encode as values? What heuristic evaluation functions are used? What constraints do they check for? Then you would adapt their encodings to your mutation and crossover operators, and see how well they perform in your genetic algorithms.

It is highly likely that an efficient search space encoding or an accurate heuristic evaluation function of the multiknapsack problem can translate into highly effective mutation and crossover operators. Since multiknapsack is a very well studied problem with a large corpus of research literature, it should be a gold mine for you.

share|improve this answer
Sorry wasn't clear answer. i am trying to advance the genetic algorithm technique by using multiknapsack as a test platform. I got it. I will consider all that what you are saying about. – user347918 Jul 1 '10 at 14:38

Your Answer


