knapsack problem using genetic algorithm

Question

0.00/5 (No votes)

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:

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.

Posted 2-Jan-11 5:01am

Neha_59

Updated 22-Feb-17 2:42am

v2

Add a Solution

Comments

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

Please first formulate the knapsack problem you're trying to solve precisely. I'm asking because there are different variants of the problem.

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.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

fjdiewornncalwe · Answer 1 · 2011-01-02T05:07:00

Solution 1

Try checking out this. It has been asked before.

Cheers.

Posted 2-Jan-11 5:07am

fjdiewornncalwe

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.

Stefan_Lang · Answer 2 · 2017-02-22T02:42:00

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.

C++

modified_fitness = max_fitness*A - excess_of_limits*B

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