0

Hey folks im having some trouble with a roulette wheel selection that im programming for a genetic algorithm. I decided to do it slightly differently to the standard Roulette wheel, primarilty because its highly likley in standard version that the fittest solution will mate with itself. And that just seems weird and wrong. So... in my attempt to make sure that no individual can be seleceted as both parents to an offspring i inversed the fitness and reordered the array to slide the current individual to the bottom (*hence making its fitness below the minimum value and not letting it be selected for reproduction*)

Then the cumulative fitness of each is added to the array in the CreatePie function and the total possible fitness is found. A random number is then generated to see which solution 'i' will reproduce with.

The problem im encountering is that occassionally the array does not list having as having a random number generated. So will not select anything for its reprocuction.

I inserted several fields into the 1 array for debugging purposes, but it should operate much the same as having multiple arrays. It goes like this:
iPopulation:


|0-7|8|9|10|11|
|----|--|--|---|---|
|----|--|--|---|---|
|----|--|--|---|---|
|----|--|--|---|---|
.
.
.
iChromeLength = 8
0-7 is the binary digits of the chromosome
8 is the fitness (iChromeLength)
9 is the cumlative fitness (iChromeLength + 1)
10 is the X value that it will breed with. (iChromeLength + 2)
11 is the random number generated by the roulette wheel while selecting breeding mate. (ChromeLength + 3)

here is the code for the roulette wheel and the createpie function.

void RouletteWheelSelection(int (&iPopulation)[iPopDensity][iChromeLength + 4])
{
	int iRandomNumber, iTotalFitness;
	for(unsigned short int i=0; i<iPopDensity; i++)
	{
		CreatePie(iPopulation, iTotalFitness, i);
		GenerateRandomNumber(iTotalFitness, iRandomNumber);
		iPopulation[iPopDensity - 1][iChromeLength + 3] = iRandomNumber;

		for(short int j=iPopDensity - 1; j >= 0; j)
		{
 			if(iRandomNumber > iPopulation[j][iChromeLength + 1])
				j--;
			else
			{
				if(j >= i) //this small section makes sure that 'i' cant breed with itself and the selection is corrected for array re-arrangement
					iPopulation[iPopDensity - 1][iChromeLength + 2] = j + 1;
				else
					iPopulation[iPopDensity - 1][iChromeLength + 2] = j;
				break;
			}
		}
		iPopulation[iPopDensity - 1][iChromeLength] *= (-1);
		ReorderPopulation(iPopulation);
	}
}

void CreatePie(int (&iPopulation)[iPopDensity][iChromeLength + 4], int &iTotalFitness, int iExcluded)
{
	/*This function calculates the metaphorical Pie that makes up the chance of roulette wheel selection. In order to make sure a number does not mate with itself the current number in the roulette wheel loop is inversed and then the array re-arranged so it is at the bottom. Then simply making it a matter of running the roulette wheel loop to 1 less than the population density means that the current specimin wont reproduce with itself.*/

	iTotalFitness = iPopulation[iExcluded][iChromeLength];
	iPopulation[iExcluded][iChromeLength] *= (-1);
	
	for(unsigned short int i=0; i<iPopDensity; i++)
	{
		iPopulation[i][iChromeLength + 1] = iPopulation[i][iChromeLength];
		iTotalFitness += iPopulation[i][iChromeLength];
	}


	ReorderPopulation(iPopulation);
	for(short int i=(iPopDensity-3); i>=0; i--)
		iPopulation[i][iChromeLength + 1] += iPopulation[i+1][iChromeLength + 1];

	ReorderPopulation(iPopulation, true);
}

The code is lacking the main obv, and some other things that are easy to implement. I just need to know why its giving me this error.

I inserted debugging statemesnt after the insertion of the random number into the array, which yeilded no problems, then after the Re-order population call in the roulette wheel function which did yeild something. I cant think of what mite be happenin inbetween those functions. And the anoying thing is that the error only occurs about 1 in every 10 runs, sometimes more sometimes less.

I will put the ReorderPopulation and RandomNumber functions down aswell although they are reasonably simple and as far as i can see dont contain the error that is causing this problem:

void ReorderPopulation(int (&iPopulation)[iPopDensity][iChromeLength + 4], bool bCumulative)
{
	int temp;
	//sorting the array into highest to lowest
	if(!bCumulative)
	{
		for(unsigned short int i=0; i<iPopDensity; i++)
			for(unsigned short int j=i+1; j<iPopDensity; j++)
				if(iPopulation[i][iChromeLength] < iPopulation[j][iChromeLength])
					for(unsigned short int k=0; k<iChromeLength + 4; k++)
					{
						temp = iPopulation[i][k];
						iPopulation[i][k] = iPopulation[j][k];
						iPopulation[j][k] = temp;
					}
	}
	else
	{
		for(unsigned short int i=0; i<iPopDensity; i++)
			for(unsigned short int j=i+1; j<iPopDensity; j++)
				if(iPopulation[i][iChromeLength + 1] < iPopulation[j][iChromeLength + 1])
					for(unsigned short int k=0; k<iChromeLength + 4; k++)
					{
						temp = iPopulation[i][k];
						iPopulation[i][k] = iPopulation[j][k];
						iPopulation[j][k] = temp;
					}
	}
}

void GenerateRandomNumber(int highest, int &iNumberStore)
{
	srand((unsigned)time(0));
	int lowest = 1;

	iNumberStore = (rand() % highest) + lowest;
}

Sorry for the epic post, but any help is appriciated, iv been at this error for days now.

Thanks!

Edited by Lord_Migit: n/a

2
Contributors
1
Reply
2
Views
7 Years
Discussion Span
Last Post by vijayan121
0
else
    {
        if(j >= i) //this small section makes sure that 'i' cant breed with itself and the selection is corrected for array re-arrangement
            // Don't we need to recalibrate the roulette wheel here? 
            iPopulation[iPopDensity - 1][iChromeLength + 2] = j + 1;
        else
	    // ...
    }
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.