Try checking out this. It has been asked before.

Cheers.

15,569,644 members

See more:

Hello!

I am a new member of code project. I have just started working with genetic algorithm.

I need to solve knapsack problem using genetic algorithm in c++.

For example, I am initializing the population:

I just cant figure out how to evaluate the fitness value if I use genetic process. And should I create benefit and value randomly and then convert decimal no. to binary?

Any help with the basic idea, or any implementation in c++ would be of great help.

I am a new member of code project. I have just started working with genetic algorithm.

I need to solve knapsack problem using genetic algorithm in c++.

For example, I am initializing the population:

void initialize_Q() { double r,num=0.0; for( int i=0;i<POPsize ;i++) { for(int j=0;j<NUM_BIT;j++) { r=rnd0_1(); if(r>=0.5) { population[i].P[j]=1; num++; if(num>CAPACITY) population[i].P[j]=0; } else population[i].P[j]=0; } } }

I just cant figure out how to evaluate the fitness value if I use genetic process. And should I create benefit and value randomly and then convert decimal no. to binary?

Any help with the basic idea, or any implementation in c++ would be of great help.

Comments

Permalink

Share this answer

Comments

Manfred Rudolf Bihy
2-Jan-11 11:51am

This time it's a little different as OP is asking about solving this with a genetic algorithm. I guess the fitness value OP is talking about has to do with genetic algorithms. It sounds as if this value is used to determine if an algrithm is **fit** enough for survival.

Neha_59
2-Jan-11 12:08pm

yes, fitness value is used for that, I need to maximize the profit as well as choose best solutions for the new population.

fjdiewornncalwe
2-Jan-11 13:03pm

@Neha59: Thanks for adding the code block to the question. You have made the question much clearer this time by doing that.

Sergey Alexandrovich Kryukov
2-Jan-11 13:25pm

Marcus thank you for this answer.

Sergey Alexandrovich Kryukov
2-Jan-11 13:34pm

Marcus, unfortunately your answer is inadequate. I'll explain.

You actually reference my answer I gave in the past. But that was an answer to a different person; and the answer formally pointed out that the problem was incorrectly posed.

This question is different and has a different issue: the problem is not formulated at all. For knapsack problems this is important, because there are many variants, so I'm not sure what is exact formulation (and of course don't want to guess).

I suggest you modify the text of your answer to avoid misleading: say the problem was discussed before, but... (I did not vote this time).

Neha, please first formulate the knapsack problem you're trying to solve presicely.

You actually reference my answer I gave in the past. But that was an answer to a different person; and the answer formally pointed out that the problem was incorrectly posed.

This question is different and has a different issue: the problem is not formulated at all. For knapsack problems this is important, because there are many variants, so I'm not sure what is exact formulation (and of course don't want to guess).

I suggest you modify the text of your answer to avoid misleading: say the problem was discussed before, but... (I did not vote this time).

Neha, please first formulate the knapsack problem you're trying to solve presicely.

For the fitness function of any GA you have to define an algorithm that returns the maximum (or minimum, depending on the kind of problem) value for optimal solutions.

For the knapsack problem, the fitness is typically defined as the total value of all items packed, and the optimal solution would be the one with the highest fitness. This should answer your question: simply write a function that calculates the sum of the value of all packed items.

That's the easy part.

It gets more tricky when you consider how you're going to create the next generation, since you have to watch out for the knapsack limitations. One way would be to specify special genetic operators that ensure that the offspring automatically fulfils the restriction. A second would be an additional step that weeds out all offspring that breach the restrictions, and then keep producing offspring until you have a sufficent number of new solutions.

You could also turn the hard limit(s) into a soft limit by allowing 'bad' solutions that exceed the capacity of the knapsack and instead adding a penalty to the fitness function result, e. g.

Finding good values for these constants will probably require some trial (and error). Or you could ask the user to enter these values at runtime, so you don't have to repeatedly change the program.

For the knapsack problem, the fitness is typically defined as the total value of all items packed, and the optimal solution would be the one with the highest fitness. This should answer your question: simply write a function that calculates the sum of the value of all packed items.

That's the easy part.

It gets more tricky when you consider how you're going to create the next generation, since you have to watch out for the knapsack limitations. One way would be to specify special genetic operators that ensure that the offspring automatically fulfils the restriction. A second would be an additional step that weeds out all offspring that breach the restrictions, and then keep producing offspring until you have a sufficent number of new solutions.

You could also turn the hard limit(s) into a soft limit by allowing 'bad' solutions that exceed the capacity of the knapsack and instead adding a penalty to the fitness function result, e. g.

C++

modified_fitness = max_fitness*A - excess_of_limits*Bwhere

`max_fitness`

is an estimate for the maximum achievable fitness value (using the unpenalized fitness function), `A`

is a reducing factor small enough to reduce that estimate well below realistically achievable values (obviously depends on how well you can estimate - some value between 0.5 and 0.9 should work for most cases), `excess_of_limits`

is the amount by which the evaluated solution exceeds the knapsack limits, and `B`

is some scaling factor putting the excess into relation to the approximate size of the fitness value.Finding good values for these constants will probably require some trial (and error). Or you could ask the user to enter these values at runtime, so you don't have to repeatedly change the program.

Permalink

Share this answer

Comments

Patrice T
22-Feb-17 9:11am

a 6 years old question! are you sure ?

Stefan_Lang
23-Feb-17 1:39am

Ouch. Missed the date. But somehow this popped up on the front page. Before I posted this solution. Must have messed with my filters...

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

Please see my comment to Marcus answer (it refers to my past answer); unfortunately this is not an answer which can help you -- just yet.