Implementing a genetic algorithm to solve knapsack

Question

I am trying to develop a genetic algorithm to solve knapsack problem(0-1). I am new to algorithm and programming as well. Here is my code and it works but I would like to know your suggestions of how to improve it.

Knapsack.h

#ifndef KNAPSACK_H
#define KNAPSACK_H
#include <vector>
#include <random>

class knapsack
{

public:
    struct population
    {
        int fitness;
        int weight;
        int pop[5];
    };

public:

    knapsack();

    void initPopulation(std::vector<population> &pop, std::vector<knapsack::population> &initBuffer);
    void calFitness(std::vector<population> &pop, int userInput[][5]);

    void sortByFitness(std::vector<population> &sort);

    void mate(std::vector<population> &mate1, std::vector<population> &mate2);
    void copyNewGeneration(std::vector<population> &copyFrom, std::vector<population> &copyTo);
    void mutate(std::vector<population> &mutate, std::vector<population> &buffer);

    void swap(std::vector<knapsack::population> &pop, std::vector<knapsack::population> &buffer);

    int randGenerate(int start, int end);

    void print(std::vector<knapsack::population> &pop);

    void solve(int userInput[][5]);

private:
    int popSize;
    int maxB;
    int maxW;
    int bagWeight;

public:
    std::default_random_engine dRandom;
};



#endif

implementation.cpp

#include <iostream>
#include <time.h>
#include <algorithm>
#include "Knapsack.h"

typedef std::vector<knapsack::population> chromosomes;

knapsack::knapsack():dRandom(), popSize(10), maxB(0), maxW(0), bagWeight(20){}

void knapsack::initPopulation( chromosomes &initPop,  chromosomes &initBuffer)
{
    knapsack::population p;

    int gene = 0;

    for(int i = 0; i < popSize; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            gene = randGenerate(0, 2);
            p.pop[j] = gene;
        }

        initPop.push_back(p);
    }

    initBuffer.resize(popSize);
}

int knapsack::randGenerate(int start, int end)
{
    std::uniform_int_distribution<int> genenNum(start, end - 1);

    return genenNum(dRandom);
}
void knapsack::calFitness( chromosomes &pop, int userInput[][5])
{
    int fit    = 0;
    int weight = 0;
    for(int i = 0; i < popSize; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            if(pop[i].pop[j] == 1)
            {
                weight         += userInput[0][j];
                fit            += userInput[1][j];
                pop[i].weight  = weight;
                pop[i].fitness = fit;

                if(weight > bagWeight)  pop[i].fitness = 0;
            }
            else
            {
                weight         += 0;
                fit            += 0;
                pop[i].weight  = weight;
                pop[i].fitness = fit;
            }

        }
        weight = 0;
        fit    = 0;
    }

}

void knapsack::copyNewGeneration( chromosomes &copyFrom,  chromosomes &copyTo)
{
    for(int i = 0; i < popSize;i++)
    {
        for(int j = 0; j < 5; j++)
        {
            copyTo[i].pop[j] = copyFrom[i].pop[j];
        }

        copyTo[i].fitness = copyFrom[i].fitness;
    }
}

void knapsack::mutate( chromosomes &mutate,  chromosomes &buffer)
{

    int pIndex1 = randGenerate(0, popSize);
    int  pIndex2= randGenerate(0, popSize);

    int index1 = randGenerate(0, 5);
    int index2 = randGenerate(0, 5);


    buffer[pIndex1].pop[index1] = mutate[pIndex2].pop[index2];



}

void knapsack::mate( chromosomes &mate1,  chromosomes &mate2)
{
   copyNewGeneration(mate1,mate2);

   for(int i= 0; i < 5; i++ )
   {
       int index1 = randGenerate(0, 5);
       int index2 = randGenerate(0, 5);


       if(mate2[i].weight < bagWeight || mate2[i].weight > bagWeight)
         {
             mate2[index1].pop[i] = mate1[index2].pop[i];
         } 

   }

   mutate(mate1,mate2);
}

void knapsack::sortByFitness( chromosomes &sort)
{

    std::sort(sort.begin(),sort.end(),
        []( const population & x, const population & y) -> bool { return( x.fitness > y.fitness);} );
}

void knapsack::swap( chromosomes &pop,  chromosomes &buffer)
{
     chromosomes *temp = &pop;
     pop = buffer;
     buffer = *temp;
}

void knapsack::print( chromosomes &pop)
{

    if(pop[0].fitness > maxB)
       {
           maxB = pop[0].fitness;
       }

    std::cout<< " Max Benefit : "<<maxB<<std::endl;
}

void knapsack::solve(int userInput[][5])
{

     chromosomes initPop, initBuffer, *pop, *buffer;


    initPopulation(initPop, initBuffer);

    pop    = &initPop;
    buffer = &initBuffer;

    for(int i = 0; i < 100; i++)
    {
        calFitness(*pop, userInput);
        sortByFitness(*pop);
        print(*pop);            
        mate(*pop,*buffer);
        swap(*pop,*buffer);

    }
}

int main()
{
    srand(unsigned(time(NULL)));

    int u[2][5] = {{2 , 7 , 1 , 4 , 1},{5 , 3 , 2 , 9 , 6}};

    knapsack ks;

    ks.solve(u);


    std::cin.get();

    return 0;
}

Is the purpose of this code to organize an inventory using GA? I once tried that and it failed miserably :P But that is my fault, I must have done something wrong. Anyway, I gave up once I found that the brute force approach was so much faster. hehehe — glampert, Sep 16 '14 at 3:37
@glampert, I think you are right, brute force or dynamic programming would be much better approach for this problem, but I am trying to learn something different. — Mo Moallim, Sep 16 '14 at 16:46

glampert · Accepted Answer · 2014-09-16 03:27:02Z

Naming of C++ types:

User defined C++ types are usually named using CamelCase, with the first letter upper case. Lowe-case names are commonly used by the standard library. I suggest you rename your types knapsack and population to Knapsack and Population instead.

Make internal stuff private:

I don't see a reason for the random generator dRandom to be public. Actually, the only method being called by main() is knapsack::solve(). If no other method is meant to be called outside the class, put those in the private section (except for the constructor and destructor, of course).

Some mix-up with typedef:

In implementation.cpp you have a chromosomes typedef that you consistently use. However, in Knapsack.h you are using std::vector<population> instead. Why this mix-up? Place the typedef in the class header, right below struct population and use it everywhere.

Re-implementing swap():

Your class implements its own swap() method. Which is redundant with std::swap(), the standard swap function. Use the standard one instead. Chances are that it is much more optimized and efficient than yours.

But wait, there is more! Your swap function is actually incorrect.

void knapsack::swap( chromosomes &pop,  chromosomes &buffer)
{
     chromosomes *temp = &pop; // 1. temp points to pop
     pop = buffer;             // 2. pop is now = buffer
     buffer = *temp;           // 3. buffer is now = whatever temp points at, which is = pop
}

This function is basically a one-way copy. First (1), you save the address, not the value, of pop in the temp pointer. So *temp is the same as pop.

Second (2) you overwrite pop with the contents of buffer. Now pop is equal to buffer.

Third (3) you overwrite buffer with the contents of whatever temp points to. But temp points to pop and pop is already equal to buffer, so you are basically writing buffer over pop and then writing it back to buffer. So buffer is never actually changed.

Const correctness:

knapsack::print() is only reading from its input parameter. When a function/method only reads from a param, that param should be made const. This is even more important when the parameter is passed by reference, as it is the case here. This is called const correctness.

void knapsack::print(const chromosomes &pop) { ... }

srand() is unnecessary in this context:

srand(unsigned(time(NULL)));

Is useless here. std::default_random_engine cannot be seeded that way. If you want to seed it by the current time, see an example of how to do it here.

5s?

You've used the constant 5 in several places. Is this just a coincidence or does 5 actually mean something to your program?

for(int j = 0; j < 5; j++)
...
int index1 = randGenerate(0, 5);
int index2 = randGenerate(0, 5);
...
void knapsack::solve(int userInput[][5])

Give that constant a meaningful name (a class scoped static const int) and replace those raw 5s with it.

Blank lines and some indentation problems:

Your code has a few lines with bad indenting, like these:

if(pop[0].fitness > maxB)
   {
       maxB = pop[0].fitness;
   }

And a few excessive blank lines in some places, like here:

void knapsack::solve(int userInput[][5])
{

     chromosomes initPop, initBuffer, *pop, *buffer;


    initPopulation(initPop, initBuffer);

Fix this to make your code neater and easier to read.

I am using something like this calFitness( chromosomes &pop, int userInput[][5]) in my code but I would like the array's size to not be fixed and based on the user choice, how I can do that can you please help me ? — Mo Moallim, Sep 17 '14 at 17:08
@Code_LOVER, you mean the userInput[][] 2d array? This question is probably a good starting point: stackoverflow.com/a/17569578/1198654 — glampert, Sep 17 '14 at 18:51

asked	2 years ago
viewed	3090 times
active	2 years ago

current community

your communities

more stack exchange communities

Implementing a genetic algorithm to solve knapsack

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ algorithm or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Implementing a genetic algorithm to solve knapsack

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ algorithm or ask your own question.

Related

Hot Network Questions