c++ Genetic Algorithm Mutation error

Question

I Have a problem with the mutation function within my genetic Algorithm. I can't quite see what I am doing wrong either. I've looked at this code for a while and I think the logic is correct, it's just not producing the results i want.

The problem When i output the Binary array located in the Child Struct, If mutation has occured on any of the bits, then a random number will be changed, and not the one that should be.

for example

0000000 is the binary string
mutation has occured on the second bit
0001000 would be the result

This section is located within the main.

for (int Child = 0; Child < ParentNumberInit; Child++)
{
    cout << endl;
    mutation(child[Child],Child);
}

This is the mutation function

void mutation(struct Parent Child1,int childnumber)
{
    int mutation; // will be the random number generated

    cout << endl << "Child " << (childnumber+1) << endl;

    //loop through every bit in the binary string
    for (int z = 0; z < Binscale; z++)
    {
        mutation = 0;   // set mutation at 0 at the start of every loop
        mutation = rand()%100;      //create a random number

        cout << "Generated number = " << mutation << endl;

        //if variable mutation is smaller, mutation occurs
        if (mutation < MutationRate)
        {
            if(Child1.binary_code[z] == '0')
                Child1.binary_code[z] = '1';
            else if(Child1.binary_code[z] == '1')
                Child1.binary_code[z] = '0';
        }
    }
}

It's being outputted in the main like this

    for (int childnumber = 0; childnumber < ParentNumberInit; childnumber++)
    {
        cout<<"Child "<<(childnumber+1)<<" Binary code = ";
        for (int z = 0; z < Binscale; z ++)
        {
        cout<<child[childnumber].binary_code[z];
        }
        cout<<endl;
     }

You should really be using an `std::vector` instead of a string. Also, `mutation = 0` does nothing since you're setting it to a different value in the next line. You're also not modifying anything because you're passing a copy of the `struct Parent` to `mutation`. — Fred Foo, Jan 18 '11 at 15:06
The mutation rate is around 25( just to make sure it works) I am expecting to see, when i output the array, a change in the bits that matches perfectly with the ones that have been altered in the function. — William Markey, Jan 18 '11 at 15:06
Where are you outputting the array, within `mutation` or in its caller? — Fred Foo, Jan 18 '11 at 15:08
To repeat Oli Charlesworth's question: which bit do you expect to change? I find it hard to believe that anything changes at all, since you're passing `Child1` by value. — Fred Foo, Jan 18 '11 at 15:13
The bit changed will all depend on the random number generated. As the number is generated for the amount of bits in the chromosome. If the loop is on 3, and the random number generated is less than 25, i want the third bit to change, then when the loop goes to 4, if the random number that is generated is below 25, i want that bit to change too. do you understand? or am i making a hash of this — William Markey, Jan 18 '11 at 15:18
@William, you aren't, the point is that when you pass in the `Parent` structure to the `mutate()` function, you are passing by value - which means you modify a copy of the object rather than what you have in your array (`child`). Hence it could be happily modifying an instance, but not the one you want. Change, `mutate()` to accept by reference and it should do the trick. — Nim, Jan 18 '11 at 15:23

ThomasMcLeod · Accepted Answer · 2011-01-18T15:37:17.397

3

You can't throttle the multation rate this way. You need to separate the mutated bit from the probability of the mutation occuring.

for (int z = 0; z < Binscale; z++)     
{         
    if (rand() % 100 < MutationRate)        
    {
        // flip bit             
        Child1.binary_code[z] += 1; 
        Child1.binary_code[z] %= 2;
    }
}

Even simpler way to flip bit:

Child1.binary_code[z] ^= 1;

edited Jan 18 '11 at 15:37

answered Jan 18 '11 at 15:19

ThomasMcLeod

7,603
4
42
80

Could you explain that a little more to me please. I don't quite understand – William Markey Jan 18 '11 at 15:22
@Will: actually, this is what you have. I misread it initially. – ThomasMcLeod Jan 18 '11 at 15:29
1

@Will: your variable mutation is kind of mislabeled. It's not the mutation per se, it's the probability that a mutation will NOT occur on a particular bit. – ThomasMcLeod Jan 18 '11 at 15:33
Can you see my dilema now, i can't understand whats wrong in the logic. – William Markey Jan 18 '11 at 15:39
indeed. I should of called it random number of something along those lines. – William Markey Jan 18 '11 at 15:40
In your original code, you're modifying all bits (of a copy...) if `rand() % 100 < MutationRate`. – Fred Foo Jan 18 '11 at 15:42
surely not though, as the if statement says, if less than mutation rate. so aslong as the rand number isn't above 25, it wont change – William Markey Jan 18 '11 at 15:46
@Will: are you attempting to modify only one bit per mutation, or any number of bits? – ThomasMcLeod Jan 18 '11 at 15:47
any number of bits. Each bit has a chance of being mutated. – William Markey Jan 18 '11 at 15:48
@Will: Ok, this will do that, but that is extremely fast mutation, by genetic algo standards. – ThomasMcLeod Jan 18 '11 at 15:50
Yeah i know that. The mutation rate will be dropped to 1% as soon as it's working. – William Markey Jan 18 '11 at 15:51
Nope, still fails to work mate using your code. Argh this is driving me nuts. it's changing random bits again. – William Markey Jan 18 '11 at 15:57
@Will: it is designed to change random bits. – ThomasMcLeod Jan 18 '11 at 16:00
I've jsut found my problem. It was the cross over function that had the problem. Arghh god damn it. My cross over function fails to work, not the mutation one. bad day, getting worse. – William Markey Jan 18 '11 at 16:04
and now your code works. Thanks Thomas. If ever i should meet you, i shall buy you a pint. – William Markey Jan 18 '11 at 16:10

score 1 · Answer 2 · answered Jan 18 '11 at 15:32

1

try this:

void mutation(Parent& Child1,int childnumber)

answered Jan 18 '11 at 15:32

Nim

33,299
2
62
101

Changed every random number generated to 1 ha. – William Markey Jan 18 '11 at 15:44

c++ Genetic Algorithm Mutation error

2 Answers2

Linked