Roulette Wheel

[M.A.H]

Hi,
I generated 10 random numbers ranging from 0 to maxrange to find out the running total to work out the fitness of each chromosome. Then I generated 10 more random numbers which range from 0 to the maximum of running total. The second set of 10 random numbers are to compare them to the running total (all of the running total numbers are the fittest ones of each chromosome) to find out the parent population.

What I have done in addition to this is make the last number the total value (max range), so that a random number can only be generated from 0-to maximum of running total.

Im trying to figure out how to display a number (parent population) from an array where it has been chosen by a random number (ranging 0 to maximum of running total).

For example
(Random numbers always different when program is ran)

First set of 10 random numbers for running total ranging from 0 to maxrange
11, 31, 45, 65, 36, 25, 150, 187, 70, 200

Second set of 10 random numbers ranging from 0 to maximum of running total. Each one is added with the previous number.
0 = 10
1 = 30 (+20)
2 = 32 (+2)
3 = 40 (+8)
4 = 71 (+31)
5 = 76 (+5)
6 = 100 (+24)
7 = 152 (+52)
8 = 163 (+11)
9 = 200 (+37)

So the last index number 9 equals to 200 which is the maxmum number generated for the running total.

Now
If the random number is 150, the program should display the value from index number 7 which is 152.

If the random number is 70, the program should display the value from index number 4 which is 71.

(I am looping this 10 times, so 10 random numbers are generated.)

This is where the problem comes in I can't seem to display the value from index 7.

Basically I have worked out the fitness of each chromosome but need to select the parent population from the roulette wheel. It is the roulette wheel part of my code which i cant seem to get my head around.

Can someone point me in the right direction please. Would appreciate it a lot.

Here is my code fo my roulette wheel.

//------------------------------------------------------------------------------
//Roulette_Wheel
void roulette_wheel(int fitness [population], char chromosome[population][chromelength], char parent[population][chromelength])
{
int i;
int j;
int k;
int max_fitness;
int random;
int running_total[population];
int current_total;
//int chromosome[population];
//int parent[population];
current_total = 0;


	for (i=0; i<population; i++)
                 	{
                    current_total =   fitness[i] + current_total;
                    running_total[i] = current_total;

                    cout<<"Running Total ["<<i<<"]  "<<running_total[i]<<endl;
        //            cout<<"Current Total "<<current_total<<endl;
                  }
                   cout<<endl;
                   max_fitness = current_total;
                   cout<<"Max Fitness = "<<max_fitness;
                   cout<<endl;
               
   	for (i=0; i<population; i++)
      			{
                 cout<<endl;
                 random = My_rand_no(max_fitness);
            	  cout<<"Random Number = "<<random<<endl;
            	  cout<<endl;

             	  	for (j=0; j<population; j++)
                    {
                     if (random > running_total[j])
                         for (k=0; k < chromelength; k++)
                        {
                         parent[i][k] = chromosome[j][k];
                         j = population + 1;
                         cout<<"Parent ["<<i<<"] = "<current_total[j] <<endl;
                        }
                    }
               }
}

If the post is unclear, please say so and I will try elaborate abit more.

Thank you

[iamthwee]

I would just go through the loop of arrays and print out the one which is closest to the number generated. If I understand you correctly.

Perhaps?

/*
  0 = 10
  1 = 30 (+20)
  2 = 32 (+2)
  3 = 40 (+8)
  4 = 71 (+31)
  5 = 76 (+5)
  6 = 100 (+24)
  7 = 152 (+52)
  8 = 163 (+11)
  9 = 200 (+37)
*/

#include <iostream>

using namespace std;

int main ()
{

int array[] = {10,30,32,40,71,76,100,152,163,200};

int val = 150; /*test value*/

int p;
int old = 10000000; //some arbitrary large number
int diff = 0;
for ( int i = 0; i < 10; i++ )
 {
    diff = array[i] - val;
    
    /*negative*/
    if ( diff < 0 )
    {
     diff = diff * -1;
    }
    
 if ( diff < old )
 {
   old = diff;
   p = array[i];
  } 
}
cout << p<<endl;
cin.get();
return 0;
}

[iamthwee]

Is that what you're trying to do?

[M.A.H]

in a previous program, fitness is declared which contains 10 different numbers.

now by using fitness and adding it to current_total and placing it in a new array running_total

current_total = fitness[i] + current_total;
running_total[i] = current_total;

I will get something like this:

0 = 10 (+10)
1 = 30 (+20)
2 = 32 (+2)
3 = 40 (+8)
4 = 71 (+31)
5 = 76 (+5)
6 = 100 (+24)
7 = 152 (+52)
8 = 163 (+11)
9 = 200 (+37)

(these numbers are just examples)
(the numbers in brackets are the fitness values)

I then make the

max_fitness = current_total;

so when generating a random it is easier to pick a number from 0 - max_fitness.

This is where the loop starts and where I generate the random numbers (NB Population is #define population 10):

for (i=0; i<population; i++)
{
cout<<endl;
random = My_rand_no(max_fitness);
cout<<"Random Number = "<<random<<endl;
cout<<endl;

Once the random number is selected another loop is ran, if the random number is less than the number in the array, that index will become the new parent: (this is probably where problem is starting but I am really unsure)

for (j=0; j<population; j++)
{
if (random < running_total[i])

for (k=0; k < chromelength; k++)
{
parent[i][k] = chromosome[j][k];
j = population + 1;
cout<<"Parent ["<<i<<"] = "<current_total[j] <<endl;
}

so if the 10 random numbers are:
11, 31, 45, 65, 36, 25, 150, 187, 70, 199

11 < 30 [1]
31 < 32 [2]
45 < 71 [4]
65 < 71 [4]
36 < 40 [3]
25 < 30 [1]
150 < 152 [7]
187 < 200 [9]
70 < 71 [4]
199 < 200 [9]

the values in the array for the index of 1, 2, 4, 4, 3, 1, 7, 9, 4, 9, will become the new parent array.

Now I am having trouble working this out.

[iamthwee]

Oh so it has to be less than the number as opposed to the closest.

[M.A.H]

Yes

Also when I run my program it displays squares and wierd signs. Is there any reason for this or am I really doing something wrong.

[iamthwee]

Maybe (untested)

#include <iostream>

using namespace std;

int main ()
{

int array[] = {10,30,32,40,71,76,100,152,163,200};

int val = 31 ; /*test value*/

int p;
int old = 10000000; //some arbitary large number
int diff = 0;
int index_pos = 0;
for ( int i = 0; i < 10; i++ )
 {
 if (  array [i] < val)
  {
    diff =  val - array[i];
    
    /*negative*/
    if ( diff < 0 )
    {
     diff = diff * -1;
    }
    
 if ( diff < old )
 {
   
  
     old = diff;
     p = array[i];
     index_pos = i;
   
  } 
 }
}
cout << p<< " index position ["<<index_pos<<"]"<<endl;
cin.get();
return 0;
}

[iamthwee]

Any luck?

#include <iostream>

using namespace std;

int main ()
{

int array[] = {10,30,32,40,71,76,100,152,163,200};

int test[] = {11, 31, 45, 65, 36, 25, 150, 187, 70, 199};

for ( int j =0; j <10; j++ )
 {

int val = test[j] ; /*test value*/

int p;
int old = 10000000; //some arbitary large number
int diff = 0;
int index_pos = 0;
for ( int i = 0; i < 10; i++ )
 {
  if (  val < array[i])
  {
    diff =  val - array[i];
    
    /*negative*/
    if ( diff < 0 )
    {
     diff = diff * -1;
    }
    //cout << "diff" <<array[i]<<" "<<diff<<endl;
    //cin.get();
    
 if ( diff < old )
 {
     old = diff;
     p = array[i];
     index_pos = i;
  } 
 }
}
cout <<test[j]<<" < "<< p<< " index position ["<<index_pos<<"]"<<endl;
}
cin.get();
return 0;
}

i changed bit in red...

my output

11 < 30 index position [1]
31 < 32 index position [2]
45 < 71 index position [4]
65 < 71 index position [4]
36 < 40 index position [3]
25 < 30 index position [1]
150 < 152 index position [7]
187 < 200 index position [9]
70 < 71 index position [4]
199 < 200 index position [9]

[M.A.H]

Maybe (untested)

[B]int array[] = {10,30,32,40,71,76,100,152,163,200};[/B]

These random numbers arent always the same. Every time I load my program they are different.

[iamthwee]

I know, in order to create random numbers you could do:-

#include <iostream.h>
#include <time.h>
#include <stdlib.h> 


int GetRand(int min, int max);

int main ()
{

  int array[] = {10,30,32,40,71,76,100,152,163,200};


  int i, r;
  int test[10];
  for (i = 0; i < 10; i++)
  {
    r = GetRand(0, 200);
    test[i] = r;
  }


for ( int j =0; j <10; j++ )
 {

int val = test[j] ;

int p;
int old = 10000000; //some arbitary large number
int diff = 0;
int index_pos = 0;
for ( int i = 0; i < 10; i++ )
 {
  if (  val < array[i])
  {
    diff =  val - array[i];
    
    /*negative*/
    if ( diff < 0 )
    {
     diff = diff * -1;
    }
    //cout << "diff" <<array[i]<<" "<<diff<<endl;
    //cin.get();
    
 if ( diff < old )
 {
     old = diff;
     p = array[i];
     index_pos = i;
  } 
 }
}
cout <<test[j]<<" < "<< p<< " index position ["<<index_pos<<"]"<<endl;
}
cin.get();
return 0;
}


int GetRand(int min, int max)
{
  static int Init = 0;
  int rc;
  
  if (Init == 0)
  {
    /*
     *  As Init is static, it will remember it's value between
     *  function calls.  We only want srand() run once, so this
     *  is a simple way to ensure that happens.
     */
    srand(time(NULL));
    Init = 1;
  }

  /*
   * Formula:  
   *    rand() % N   <- To get a number between 0 - N-1
   *    Then add the result to min, giving you 
   *    a random number between min - max.
   */  
  rc = (rand() % (max - min + 1) + min);
  
  return (rc);
}

[M.A.H]

The random numbers are always meant to be different every time the program is ran

[M.A.H]

The program im trying to make involves genetic algorithm.
Here is a idea what genetic algorithm are and what type of coding is required.
http://www.bridgeport.edu/sed/projects/449/Fall_2000/fangmin/chapter4.htm

[iamthwee]

The random numbers are always meant to be different every time the program is ran

I have shown you how to make the test array random every time you run the program. Just do a similar thing for the other array.

[M.A.H]

I have got it to find the correct number from the running_total array but it also displays all the other numbers after it, I just need it to display the first correct number and not all the other after it

for (j=0; j < population; j++)
if (random < running_total[j])
cout<<"Testing             = "<<j<<endl;

How would I make the number in that position get placed into a new array?

[M.A.H]

I have fixed the selection problem out but now I have another.
How would you do a crossover if you got binarys of example:

Chromosome A: 0010011
Chromosome B: 0110101

And I want to crossover from ][

Chromosome A: 0010][011
Chromosome B: 0110][101

So that I get:

New Chromosome A: 0010101
New Chromosome B: 0110011

I havent started coding it yet. How would I start coding it?

Thanks

[iamthwee]

Can you use std::strings?

Really what I'm getting at is, does your compiler support this?

/*
  Chromosome A: 0010][011
  Chromosome B: 0110][101
*/

#include <iostream>
#include <string>

using namespace std;

int main()
{

  string A = "0010011";
  string B = "0110101";

  string Anew;
  string Bnew;

  cout << A.substr(4,3) << endl;
  return 0;
}

If this is not possible (as I suspect) you would have to create your own substring function using char[] style arrays, which is not that difficult if you play safe.