Implementing a genetic algorithm to solve the Diophantine Equation

I am trying to implement a genetic algorithm to solve (Diophantine Equation).

For instance, a + 2b + 3c + 4d = 90 where a, b, c, d are positive integers.

After reading some books and following tutorials, I finally wrote this code, but as I am new to programming and GA, I don't know if this is a good implementation.

#include
#include 
#include 
#include 
#include 
using namespace std;

#define variable 4
#define chromoSize 100000
float total = 0;
struct Equation
{
int eq[variable];
float ev;
float fit;
float p;
};

void init_chrom(vector &Original, vector &Temp)
{
  for(int i=0; i &orginalCh)
{
    for(int i=0; i &orginalCh)
{
     for(int i=0; i &p1, vector &p2, int s)
{
   for(int i=0; i &parent2, int i)
{
     int size = variable;
     int index1 = rand() % size;
     int index2 = rand() % size;
     int j = rand() % chromoSize;

    parent2[i].eq[index1] = parent2[j].eq[index2];

}
void mate(vector &parent1, vector &parent2)
{

     int sub, p1, p2, tSsize = variable;

    _copy(parent1, parent2, chromoSize);

    for(int i=0; i 0.1f)
            mutate(parent2, i);
     }

 }

bool sort_fitness(Equation x, Equation y)
{
   return(x.fit > y.fit);
}
void _sort(vector &orginalCh)
{
    sort(orginalCh.begin(),orginalCh.end(),sort_fitness);
}
void swap(vector *&parent1, vector *&parent2)
{
     vector *temp = parent1;
     parent1 = parent2;
     parent2 = temp;
}
void print(vector &originalCh)
{
    for(int i=0; i chromO, chromT;
     vector *originalCh, *bufferCh;
     init_chrom(chromO, chromT);

    originalCh = &chromO;
    bufferCh = &chromT;

    for(int i=0; i<2000; i++)
       {
        calc_fit(*originalCh);
        select_fit(*originalCh);
        _sort(*originalCh);
        print(*originalCh);

        if((*originalCh)[0].fit == 1) break;

        mate(*originalCh,*bufferCh);
        swap(*originalCh, *bufferCh);

      }

    system("pause");

    return 0;
 }

The code will output something like this:

21, 22, 7, 1,  0 1

The first fo

OK, so first of all, your code is far from being C++. It is more like C using some C++ features, such as std::vector. I'm not going to refactor all of your code into a class, instead, this is an exercise for you: Take all those loose functions and data and put them in a C++ class. This is one possible interface you can start with:

class GeneticAlgorithm 
{
public:

    void initChromosomes(vector &Original, vector &Temp);
    void calcFitness(vector &orginalCh);
    void selectFit(vector &orginalCh);
    void mutate(vector &parent2, int i);
    void mate(vector &parent1, vector &parent2);
    void print(const vector &originalCh)

private:

    // Internal helper methods and data.
    // ...
};

Other style and code quality issues:

Names should not start with _!

Names starting with an underscore _ are reserved for the C++ implementation, so they are a no-no. This is wrong:

void _sort(vector &orginalCh)
{
    sort(orginalCh.begin(), orginalCh.end(), sort_fitness);
}

I see that you've defined _sort as a shorthand for the std::sort algorithm. This is OK, but give the function another name. E.g.: sortByFitness() which is also a lot more meaningful.

#define for constants, not recommended:

Macros (AKA defines) are an inherited C feature that has quite a few drawbacks and problems. One of the most problematic ones is that they don't respect scope. Once you declare a macro, it is visible everywhere. This makes them a very poor choice for declaring constants. C++ offers much better ways. The constants you've defined with macros should be instead defined with const int or even better constexpr int if your compiler has C++11 support. But also, the names you gave to the variables are not optimal. Constants are by convention named differently. One common naming convention for constants it using ALL_CAPS. So I suggest you redeclare:

constexpr int VARIABLE = 4;
constexpr int CHROMO_SIZE = 100000;

Also note that now the constants are strongly typed (int), which is a nice thing since the compiler can now warn you about unwanted conversions.

Using namespace std?

You have a using namespace std; at the beginning of the file. This is generally not a good idea, since it defeats the purpose of a namespace, which is allowing identical names to coexist without clashes. I recommend that you remove any using namespace std; occurrences and call the library functions an types by their fully qualified names, E.g.: std::vector, std::sort, std::copy, etc.

rand():

C++11 has a brand new (and awesome!) random number library. If your compiler supports C++11, you should definitely check it out and replace the old and unreliable rand() that you currently use.

Use of system("pause"):

This was noted by @Edward in a comment below, I forgot to mention it in my first iteration, so thanks for the reminder:


system("pause") is a non-portable security nightmare that will run any local program named "pause". It might just pause, or it might format your hard drive. Please use something like std::cin.get() instead.

Poor spacing and indentation:

Your code is poorly indented and spaced on some places, also, you are not consistent with your spacing. Take these lines for example:

orginalCh[i].ev = abs((orginalCh[i].eq[j] + 2*orginalCh[i].eq[j+1] +
3*orginalCh[i].eq[j+2] + 4*orginalCh[i].eq[j+3]) - 10);

The above are tightly packed (which I find pretty hard to read, BTW). While this is more spaced:

orginalCh[i].fit = 1 /( 1 + orginalCh[i].ev);

All the code you've posted suffers from indenting problems, I don't know if this problem occurred when you posted it here or if it is like that in your project, but the guideline stays: Be very consistent with spacing and indenting. A well formatted code will be way easier for the reader to "parse".

What is the expected behavior here?

void _copy(vector &p1, vector &p2, int s)
{
   for(int i=0; i<s; i++)
   {
        for(int j=0; j<variable; j++)
           p2[i].eq[j] = p1[i].eq[j];

           p2[i].fit = p1[i].fit;
    }
}

This function is an example of an issue I frequently see in code. The last statement line, p2[i].fit = p1[i].fit;, is it meant to belong to last for()? The way it is indented, it leads the reader to believe so. A more careful look will reveal that it belongs to the first loop, being executed only s times (which is likely to be the correct). Is that the intended behavior, or did you actually mean this?

for(int i=0; i<s; i++)
{
    for(int j=0; j<variable; j++)
    {
        p2[i].eq[j] = p1[i].eq[j];
        p2[i].fit = p1[i].fit;
    }
}

Or this?

for(int i=0; i<s; i++)
{
    for(int j=0; j<variable; j++)
    {
        p2[i].eq[j] = p1[i].eq[j];
    }
    p2[i].fit = p1[i].fit;
}

This guideline is worth more than what most people think: Always enclose if, while, for and other control flow statements with {} braces, even if they are single line statements.

StackExchange Code Review Q#62162, answer score: 4