Page 1 of 1

Evolutionary Algorithms / Genetic Algorithms Rate Topic: ****- 1 Votes

#1 (KHC)Shadow  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 23
  • Joined: 14-April 11

Posted 30 April 2011 - 10:29 AM

Hello all, just wanted to do a quick introduction. I am new here so hello! I have only posted one thread so far and I received a lot of helpful info about the genetic algorithm program I was having some technical issues with. Thanks again for all the help I got with that. I promised that in return for the generous help on the project I would be posting a tutorial, so here it is.

If you clicked on this thread wondering what a genetic algorithm is, here is a quick explanation (a visit to your friend wikipedia may be more helpful if you want a more in-depth explanation): A genetic algorithm is a way of optimizing some sort of computational problem using a biological approach. You can pretty much guess it by the name — it is based on genetics and evolution. If you need a refresher on high-school biology, you start of with a population of organisms. Each organism has a set of DNA, which is a type of code for building the organism. All the organisms in the environment compete for resources, and the most fit of the organisms (determined by their DNA) will die the least often and, therefore, produce more offspring. Since the more fit organisms will produce more offspring, the population as a whole will have more “fit” genes (note that “fit” means how suited they are for surviving in the organism’s environment). A parent organism can pass down its genes through either sexual or asexual reproduction, but lets assume asexual here because it’s slightly less complicated. To reproduce, the parent will create a copy of its genes for the offspring. However, there will also be mutations during this process. Some of the DNA information maybe be slightly “scrambled” in this copying process. In nature, these mutations are usually a disadvantage to the organism, BUT they can sometimes be beneficial. Its these beneficial mutations that really are the driving force behind this process. Over a (usually long) period of time, the population as a whole will become more and more fit to their environment through the beneficial mutations.

Now, the job of genetic algorithms is to turn this biological process into a computational process. A computer program that could accomplish this would consist of three main components: An array of organisms and their respective DNA or code, a function that will compare their DNA (I call this a fitness test), and a reproduction process. Hopefully you understand the basic process now. I am now going to go through the code that I wrote step by step, to show how you would actually implement a genetic algorithm program.

Here is the entire code:

#ifndef GeneticAlgorithm_H
#define GeneticAlgorithm_H

#include <stdlib.h>
#include <stddef.h>
#include <math.h>
#include <string.h>
#include <time.h>

#include <stdio.h>

#define MATE_VARIANCE_CONSTANT 0.3
#define MUTATATIONS_PER_BASE_PAIR_CONSTANT 0.1

//Binary data used for storing dna
typedef struct {
	
	void *dataPointer;
	int length;
} binary_data;

//This is for sorting the organisms from most fit, to least
struct sorting_element {
	
	unsigned int fitness;
	int state;
	struct sorting_element *nextElement;
};

typedef struct {
	
	binary_data dna;
} organism;

typedef struct {
	
	//Initial Organisms
	//This must be malloc'ed
	organism *organisms;
	//This value should stay constant throughout multiple generations
	int organismsCount;
	//Tests organism's fitness
	int (*fitnessTest)(organism org);
	//Organism's dna length
	int orgDnaLength;
	//Desired Fitness
	unsigned int desiredFitness;
	//Progress Function
	//This function is called every iteration to give the current max fitness level
	void (*progress)(unsigned int fitness);
} evolutionary_algorithm;

//This evolves the group of organisms until they reach a satisfactory fitness level
organism evolve(evolutionary_algorithm ea);
//Reproduction using 2 organisms - crossing, then mutation
organism reproduce(organism org1, organism org2, evolutionary_algorithm alg);

#endif

//GeneticAlgorithm.c

#include "GeneticAlgorithm.h"

organism evolve(evolutionary_algorithm ea)
{
	if (ea.organismsCount % 2) {
		
		printf("Error in evolve: Cannot have odd number of organisms!");
		organism nullOrg;
		nullOrg.dna.dataPointer = NULL;
		nullOrg.dna.length = 0;
		return nullOrg;
	}
	//Seed random number generator
	srand(time(NULL));
	//The organism with a satisfactory fitness
	organism orgToReturn;
	orgToReturn.dna.length = 0;
	orgToReturn.dna.dataPointer = NULL;
	
	unsigned long long totalFitness = 0;
	//Current generation organisms buffer
	organism *currentGeneration = malloc(ea.organismsCount * sizeof(organism));
	memcpy(currentGeneration, ea.organisms, ea.organismsCount * sizeof(organism));
	free(ea.organisms);
	//Next generation organisms buffer
	organism *newGeneration = malloc(ea.organismsCount * sizeof(organism));
	
	int totalChildren = ea.organismsCount;
	
	//Counters
	int i,j;
	
	//This is used to sort the organisms from most fit to least
	//The first element is just for placeholding
	struct sorting_element *elements = (struct sorting_element *)malloc(sizeof(struct sorting_element) * (ea.organismsCount + 1));
	elements[0].fitness = 0.0;
	elements[0].nextElement = NULL;
	elements[0].state = 0;
	
	//Main loop — will exit once organisms found with satisfactory fitness
	while (1) {
		
		/***************************
		 **********TESTING**********
		 ***************************/
		
		//GP var
		unsigned int orgFitness = 0;
		
		//Loops through organisms and tests fitness
		//Also sorts them
		
		ea.organisms = currentGeneration;
		
		for (i = 0; i < totalChildren; i++)
		{
			orgFitness = ea.fitnessTest(ea.organisms[i]);
			
			//If org found with satisfactory fitness
			if (orgFitness >= ea.desiredFitness) {
				
				orgToReturn = ea.organisms[i];
				orgToReturn.dna.dataPointer = (void *)malloc(sizeof(ea.orgDnaLength));
				memcpy(orgToReturn.dna.dataPointer, ea.organisms[i].dna.dataPointer, sizeof(ea.orgDnaLength));
			}
			
			elements[i + 1].fitness = orgFitness;
			elements[i + 1].nextElement = NULL;
			elements[i + 1].state = 1;
			totalFitness += orgFitness;
			
			//Sorts orgs using relative values
			if (!i) {
				
				elements[0].nextElement = &elements[1];
				continue;
			}
			
			//Used to iterate through array of organism fitnesses
			struct sorting_element *next = &elements[0];
			
			for (j = 0; j < i + 1; j++) {
				
				if (next->nextElement == NULL) {
					
					next->nextElement = &elements[i + 1];
					break;
				}
				if (next->nextElement->fitness <= orgFitness) {
					
					elements[i + 1].nextElement = next->nextElement;
					next->nextElement = &elements[i + 1];
					break;
				}
				next = next->nextElement;
			}
		}
		
		ea.progress(elements[0].nextElement->fitness);
		
		if (orgToReturn.dna.dataPointer != NULL) {
			
			break;
		}
		
		 /***************************
		 ********REPRODUCING********
		 ***************************/
		
		//Mate finder pointers
		struct sorting_element *nextMate;
		struct sorting_element *previousMate;
		//Mate pointer
		organism *mate;
		//Org buffer in reproduction
		struct sorting_element *elementToReplicate;
		//Next generation array last index
		int newGenerationIndex = 0;
		//Decides number of children to have
		int children = 0;
		int randomNumber = 0;
		totalChildren = 0;
		
		elementToReplicate = elements[0].nextElement;
		
		//Loops through orgs and finds mate, then reproduce function
		while (elementToReplicate != NULL)
		{
			organism *orgToReplicate = &ea.organisms[(int)(elementToReplicate - elements) - 1];
			previousMate = NULL;
			if (!elementToReplicate->state) {
				
				elementToReplicate = elementToReplicate->nextElement;
				continue;
			}
			
			//State makes sure an organism doesn't reproduce more than once
			elementToReplicate->state = 0;
			randomNumber = rand() % (int)((double)ea.organismsCount * MATE_VARIANCE_CONSTANT);
			nextMate = elementToReplicate->nextElement;
			//Moves down the hierarchy a maximum of MATE_VARIANCE_CONSTANT percent
			for (j = 0; j < randomNumber; j++) {
				
				if (nextMate->state) {
					
					previousMate = nextMate;
				}
				
				nextMate = nextMate->nextElement;
				if (nextMate == NULL) {
					
					nextMate = previousMate;
					break;
				}
			}
			
			if (!nextMate->state) {
				
				if (previousMate == NULL) {
					
					while (!nextMate->state) {
						
						nextMate = nextMate->nextElement;
					}
				}
				else {
					
					nextMate = previousMate;
				}
			}
			
			mate = &ea.organisms[(int)(nextMate - elements) - 1];
			nextMate->state = 0;
			//Calculates number of children based on both parents' fitness
			children = (int)(ea.organismsCount * (double)(elementToReplicate->fitness +
														  nextMate->fitness) / totalFitness);
			totalChildren += children;
			for (j = 0; j < children; j++) {
				
				newGeneration[newGenerationIndex] = reproduce(*orgToReplicate, *mate, ea);
				newGenerationIndex++;
			}
			free(orgToReplicate->dna.dataPointer);
			free(mate->dna.dataPointer);
			elementToReplicate = elementToReplicate->nextElement;
		}
		
		if ((totalChildren % 2)) {
			
			organism dummyOrg;
			dummyOrg.dna.length = ea.orgDnaLength;
			dummyOrg.dna.dataPointer = malloc(ea.orgDnaLength);
			memset(dummyOrg.dna.dataPointer, 0, sizeof(ea.orgDnaLength));
			newGeneration[newGenerationIndex] = dummyOrg;
			totalChildren++;
		}
		organism *buffer = newGeneration;
		newGeneration = memset(currentGeneration, 0, sizeof(currentGeneration));
		currentGeneration = buffer;
		memset(elements, 0, sizeof(currentGeneration));
		totalFitness = 0;
	}
	
	struct sorting_element *elementFreeingPointer = elements[0].nextElement;
	struct sorting_element *elementFreeingBuffer;
	
	while (elementFreeingPointer != NULL) {
		
		elementFreeingBuffer = elementFreeingPointer;
		free(ea.organisms[(int)(elementFreeingPointer - elements) - 1].dna.dataPointer);
		elementFreeingPointer = elementFreeingBuffer->nextElement;
	}
	
	free(currentGeneration);
	free(newGeneration);
	free(elements);
	
	return orgToReturn;
}

organism reproduce(organism org1, organism org2, evolutionary_algorithm alg)
{
	organism child;
	//Decides at which index to start crossing with other parent
	int crossingIndex;
	//Number of mutations (in base pairs) in child
	int mutationCount;
	//Base pair to mutate
	int mutatedBasePair;
	//Mutation base pair buffer
	unsigned char basePairBuffer;
	//Counter
	int i;
	
	//Child starts with first parent's dna then crosses with the other
	child.dna.length = org1.dna.length;
	child.dna.dataPointer = (void *)malloc(org1.dna.length);
	memcpy(child.dna.dataPointer, org1.dna.dataPointer, org1.dna.length);
	
	//Crossing over
	
	//Last index ≥ a random index ≥ 0
	crossingIndex = rand() % (alg.orgDnaLength + 1);
	
	//Copying from somewhere in middle of dna to end, or half of the dna length
	memcpy(child.dna.dataPointer + crossingIndex, org2.dna.dataPointer + crossingIndex, 
					alg.orgDnaLength - crossingIndex >= (int)round((double)alg.orgDnaLength / 2.0) ? 
					(int)round((double)alg.orgDnaLength / 2.0) : alg.orgDnaLength - crossingIndex);
	//If half of the dna length isn't copied already, the remaining amount is copied from the beginning (wraps around)
	memcpy(child.dna.dataPointer, org2.dna.dataPointer, 
		   alg.orgDnaLength - crossingIndex >= (int)round((double)alg.orgDnaLength / 2.0) ? 0 :
		   (int)round((double)alg.orgDnaLength / 2.0) - (alg.orgDnaLength - crossingIndex));
	//Mutating
	
	mutationCount = rand() % (2 * (int)round(MUTATATIONS_PER_BASE_PAIR_CONSTANT * (double)alg.orgDnaLength * 8.0));
	
	for (i = 0; i < mutationCount; i++) {
		
		//Chooses a random byte and copies contents into basePairBuffer
		//Only the first bit will be used
		mutatedBasePair = (rand() % (8 * alg.orgDnaLength));
		memcpy(&basePairBuffer, child.dna.dataPointer + ((int)(mutatedBasePair / 8)), 1);
		//If the bit is 0, make it 1, and vice versa
		if ((basePairBuffer & (unsigned char)pow(2.0, (double)(mutatedBasePair % 8)))) {
			
			memset(child.dna.dataPointer + (int)(mutatedBasePair / 8), 
				   basePairBuffer ^ (unsigned char)pow(2.0, (double)(mutatedBasePair % 8)), 1);
		}
		else {
			
			memset(child.dna.dataPointer + (int)(mutatedBasePair / 8), 
				   basePairBuffer | (unsigned char)pow(2.0, (double)(mutatedBasePair % 8)), 1);
		}
	}
	
	return child;
}




Ok, now we will go through a few lines at a time:


#define MATE_VARIANCE_CONSTANT 0.3
#define MUTATATIONS_PER_BASE_PAIR_CONSTANT 0.1

//Binary data used for storing dna
typedef struct {
	
	void *dataPointer;
	int length;
} binary_data;

//This is for sorting the organisms from most fit, to least
struct sorting_element {
	
	unsigned int fitness;
	int state;
	struct sorting_element *nextElement;
};

typedef struct {
	
	binary_data dna;
} organism;




MATE_VARIANCE_CONSTANT is used to determine the difference in fitness of two organisms that will produce offspring. This will be more clear later when we get to that section.

MUTATIONS_PER_BASE_PAIR_CONSTANT is the % chance that each bit of DNA in a child will mutate. For example, if the DNA information was represented by the binary number 10011001, for each base pair, there is a
MUTATIONS_PER_BASE_PAIR_CONSTANT % chance that it will change from a 0 to a 1 or a 1 to a 0 (a mutation is implemented as flipping the bit’s value).

Binary_data a simple structure to store an n-sized block of data.

Sorting_element is used right after the fitness test to sort the organisms from most fit, to least fit.

organism is simply a container for the DNA. I was thinking about implementing some other things, but decided not to in the first version, which explains why it only contains binary_data.

typedef struct {
	
	//Initial Organisms
	//This must be malloc'ed
	organism *organisms;
	//This value should stay constant throughout multiple generations
	int organismsCount;
	//Tests organism's fitness
	unsigned int (*fitnessTest)(organism org);
	//Organism's dna length
	int orgDnaLength;
	//Desired Fitness
	unsigned int desiredFitness;
	//Progress Function
	//This function is called every iteration to give the current max fitness level
	void (*progress)(unsigned int fitness);
} evolutionary_algorithm;

//This evolves the group of organisms until they reach a satisfactory fitness level
organism evolve(evolutionary_algorithm ea);
//Reproduction using 2 organisms - crossing, then mutation
organism reproduce(organism org1, organism org2, evolutionary_algorithm alg);



evolutionary_algorithm is the main struct that contains most of our data. Not sure if I said this before, but evolutionary algorithm and genetic algorithm are, as far as I know, interchangeable.
organisms – an array of the organisms to evolve
organismCount – number of organisms in organisms array
fitnessTest – this is the function that takes an organism as an input and tests its DNA to see how fit it is to solve the problem. The fitnessTest should be the only piece of this code that needs to be edited when solving different problems. For example, if you wanted one EA (evolutionary algorithm) to calculate the x-value of a 1.56 y-value on a graph with equation y = x^2 + 3x, you would might use the following code as a fitnessTest:

unsigned int testOrg(organism orgToTest)
{
	float dnaValue = *(float *)orgToTest.dna.dataPointer;
	return (unsigned int)(1.0 / fabs(pow((double)dnaValue, 2.0) + 3.0 * dnaValue - 1.56) * 1000);
}



This code squares the value of the dna, adds 3 times the value, then subtracts 1.56. You now have the difference, and since you want to minimize this difference, you take the reciprocal and multiply by a scalar to give you a good-sized scale (you wouldn’t want the scalar to be too small, since the float is truncated to an int). Now, for a different problem. Lets say you just wanted to make the organisms evolve to have the highest value possible (for its data type). The beauty of an EA is that the only thing you need to change now is the fitness function. A function to solve this problem would be the following:

unsigned int testOrg(organism orgToTest)
{
	return *(unsigned int *)orgToTest.dna.dataPointer;
}


This one is even simpler; it just returns the DNA value.

Even though both of these examples are extremely simple, the concept should hold true for any problem. This shows how versatile and easy-to-use EA’s are, and why they are much more efficient for solving complex problems that usually require a more algorithmic-based problem than one that can be simply solved with mathematical equations. Ok, moving on!

orgDnaLength – simply the size of the binary_data in bytes for an organisms dna. This is currently static but the reproduction section may be reworked later to use dynamic DNA lengths.

desiredFitness – This is essentially how close you want to get to the perfect solution to your problem — theoretically, the EA should converge on this value.

Progress – This is just a function to give the rest of the application a heads-up on how close you are to solving the problem.

evolve – This is the function that will do nearly all the work

reproduce – This takes two organisms as an input and creates a child based on their DNA using the crossing process. It also mutates the DNA. Earlier, I explained asexual reproduction, but my program uses sexual because it allows for a greater diversity of genes.

Alright, now on to the implementation file!

organism evolve(evolutionary_algorithm ea)
{
	if (ea.organismsCount % 2) {
		
		printf("Error in evolve: Cannot have odd number of organisms!");
		organism nullOrg;
		nullOrg.dna.dataPointer = NULL;
		nullOrg.dna.length = 0;
		return nullOrg;
	}
	//Seed random number generator
	srand(time(NULL));
	//The organism with a satisfactory fitness
	organism orgToReturn;
	orgToReturn.dna.length = 0;
	orgToReturn.dna.dataPointer = NULL;
	
	unsigned long long totalFitness = 0;
	//Current generation organisms buffer
	organism *currentGeneration = malloc(ea.organismsCount * sizeof(organism));
	memcpy(currentGeneration, ea.organisms, ea.organismsCount * sizeof(organism));
	free(ea.organisms);
	//Next generation organisms buffer
	organism *newGeneration = malloc(ea.organismsCount * sizeof(organism));
	
	int totalChildren = ea.organismsCount;
	
	//Counters
	int i,j;
	
	//This is used to sort the organisms from most fit to least
	//The first element is just for placeholding
	struct sorting_element *elements = (struct sorting_element *)malloc(sizeof(struct sorting_element) * (ea.organismsCount + 1));
	elements[0].fitness = 0.0;
	elements[0].nextElement = NULL;
	elements[0].state = 0;
	



The uses for all these variables will hopefully become clear once I explain the code that uses them, so I will just skip over this section for now — its just initializing a lot of buffer and general-purpose variables.

//Main loop — will exit once organisms found with satisfactory fitness
	while (1) {
		
		/***************************
		 **********TESTING**********
		 ***************************/
		
		//GP var
		unsigned int orgFitness = 0;
		
		//Loops through organisms and tests fitness
		//Also sorts them
		
		ea.organisms = currentGeneration;
		
		for (i = 0; i < totalChildren; i++)
		{
			orgFitness = ea.fitnessTest(ea.organisms[i]);
			
			//If org found with satisfactory fitness
			if (orgFitness >= ea.desiredFitness) {
				
				orgToReturn = ea.organisms[i];
				orgToReturn.dna.dataPointer = (void *)malloc(sizeof(ea.orgDnaLength));
				memcpy(orgToReturn.dna.dataPointer, ea.organisms[i].dna.dataPointer, sizeof(ea.orgDnaLength));
			}
			
			elements[i + 1].fitness = orgFitness;
			elements[i + 1].nextElement = NULL;
			elements[i + 1].state = 1;
			totalFitness += orgFitness;




This section first sets up the main loop, and then uses the fitnessTest function on each organism (if an organism is found with the desired fitness, it does some clean-up and will exit right after the end of the inner for loop). After calculating the organism’s fitness, it places it in the elements array and adds its fitness to the totalFitness. The elements array is used to sort the organisms from most fit to least. The inner workings of the sorting mechanism are not particularly important, but if you wish to know I will give a general idea.


			//Sorts orgs using relative values
			if (!i) {
				
				elements[0].nextElement = &elements[1];
				continue;
			}
			
			//Used to iterate through array of organism fitnesses
			struct sorting_element *next = &elements[0];
			
			for (j = 0; j < i + 1; j++) {
				
				if (next->nextElement == NULL) {
					
					next->nextElement = &elements[i + 1];
					break;
				}
				if (next->nextElement->fitness <= orgFitness) {
					
					elements[i + 1].nextElement = next->nextElement;
					next->nextElement = &elements[i + 1];
					break;
				}
				next = next->nextElement;
			}
		}
		
		ea.progress(elements[0].nextElement->fitness);
		
		if (orgToReturn.dna.dataPointer != NULL) {
			
			break;
		}



The sorting algorithm that I used is the following: the elements array contains all of the organisms indexed from 1 to totalChildren (which is how many organisms there are in the current generation). In addition, each element contains a pointer to another element. This pointer is used to point to the next most fit organism, after the current one. As each organism’s fitness is added to the elements array, it tries to “find its place” among the other organisms. It moves through the list of pointers until it finds an element that has a smaller fitness than its own; it then inserts itself in front of that element. The 0th element of the array is used as a placeholder to point to the most fit organism.

Now on to the reproduction step.

		
		 /***************************
		 ********REPRODUCING********
		 ***************************/
		
		//Mate finder pointers
		struct sorting_element *nextMate;
		struct sorting_element *previousMate;
		//Mate pointer
		organism *mate;
		//Org buffer in reproduction
		struct sorting_element *elementToReplicate;
		//Next generation array last index
		int newGenerationIndex = 0;
		//Decides number of children to have
		int children = 0;
		int randomNumber = 0;
		totalChildren = 0;
		
		elementToReplicate = elements[0].nextElement;
		
		//Loops through orgs and finds mate, then reproduce function
		while (elementToReplicate != NULL)
		{
			organism *orgToReplicate = &ea.organisms[(int)(elementToReplicate - elements) - 1];
			previousMate = NULL;
			if (!elementToReplicate->state) {
				
				elementToReplicate = elementToReplicate->nextElement;
				continue;
			}
			
			//State makes sure an organism doesn't reproduce more than once
			elementToReplicate->state = 0;
			randomNumber = rand() % (int)((double)ea.organismsCount * MATE_VARIANCE_CONSTANT);
			nextMate = elementToReplicate->nextElement;
			//Moves down the hierarchy a maximum of MATE_VARIANCE_CONSTANT percent
			for (j = 0; j < randomNumber; j++) {
				
				if (nextMate->state) {
					
					previousMate = nextMate;
				}
				
				nextMate = nextMate->nextElement;
				if (nextMate == NULL) {
					
					nextMate = previousMate;
					break;
				}
			}
			
			if (!nextMate->state) {
				
				if (previousMate == NULL) {
					
					while (!nextMate->state) {
						
						nextMate = nextMate->nextElement;
					}
				}
				else {
					
					nextMate = previousMate;
				}
			}
			
			mate = &ea.organisms[(int)(nextMate - elements) - 1];
			nextMate->state = 0;




This segment goes through the elements array from most fit to least, and finds a mate based on the MATE_VARIANCE_CONSTANT. The maximum amount that an organism will move down the hierarchy to find a mate is MATE_VARIANCE_CONSTANT percent of the population. A random number is generated between 0 and this value, then it moves down the list until it finds an organism to mate with. The organism’s state must be 1, indicating that it has not already mated.

			//Calculates number of children based on both parents' fitness
			children = (int)(ea.organismsCount * (double)(elementToReplicate->fitness +
														  nextMate->fitness) / totalFitness);
			totalChildren += children;
			for (j = 0; j < children; j++) {
				
				newGeneration[newGenerationIndex] = reproduce(*orgToReplicate, *mate, ea);
				newGenerationIndex++;
			}
			free(orgToReplicate->dna.dataPointer);
			free(mate->dna.dataPointer);
			elementToReplicate = elementToReplicate->nextElement;
		}



This simply calculates the number of children to have based on both the organisms’ fitness, then calls the reproduce function.

		if ((totalChildren % 2)) {
			
			organism dummyOrg;
			dummyOrg.dna.length = ea.orgDnaLength;
			dummyOrg.dna.dataPointer = malloc(ea.orgDnaLength);
			memset(dummyOrg.dna.dataPointer, 0, sizeof(ea.orgDnaLength));
			newGeneration[newGenerationIndex] = dummyOrg;
			totalChildren++;
		}
		organism *buffer = newGeneration;
		newGeneration = memset(currentGeneration, 0, sizeof(currentGeneration));
		currentGeneration = buffer;
		memset(elements, 0, sizeof(currentGeneration));
		totalFitness = 0;
	}
	
	struct sorting_element *elementFreeingPointer = elements[0].nextElement;
	struct sorting_element *elementFreeingBuffer;
	
	while (elementFreeingPointer != NULL) {
		
		elementFreeingBuffer = elementFreeingPointer;
		free(ea.organisms[(int)(elementFreeingPointer - elements) - 1].dna.dataPointer);
		elementFreeingPointer = elementFreeingBuffer->nextElement;
	}
	
	free(currentGeneration);
	free(newGeneration);
	free(elements);
	
	return orgToReturn;
}




This is just some clean-up. It makes sure there are an even number of organisms in the population, so each one has a mate. It also frees allocated DNA and buffer memory.


organism reproduce(organism org1, organism org2, evolutionary_algorithm alg)
{
	organism child;
	//Decides at which index to start crossing with other parent
	int crossingIndex;
	//Number of mutations (in base pairs) in child
	int mutationCount;
	//Base pair to mutate
	int mutatedBasePair;
	//Mutation base pair buffer
	unsigned char basePairBuffer;
	//Counter
	int i;
	
	//Child starts with first parent's dna then crosses with the other
	child.dna.length = org1.dna.length;
	child.dna.dataPointer = (void *)malloc(org1.dna.length);
	memcpy(child.dna.dataPointer, org1.dna.dataPointer, org1.dna.length);
	
	//Crossing over
	
	//Last index ≥ a random index ≥ 0
	crossingIndex = rand() % (alg.orgDnaLength + 1);
	
	//Copying from somewhere in middle of dna to end, or half of the dna length
	memcpy(child.dna.dataPointer + crossingIndex, org2.dna.dataPointer + crossingIndex, 
					alg.orgDnaLength - crossingIndex >= (int)round((double)alg.orgDnaLength / 2.0) ? 
					(int)round((double)alg.orgDnaLength / 2.0) : alg.orgDnaLength - crossingIndex);
	//If half of the dna length isn't copied already, the remaining amount is copied from the beginning (wraps around)
	memcpy(child.dna.dataPointer, org2.dna.dataPointer, 
		   alg.orgDnaLength - crossingIndex >= (int)round((double)alg.orgDnaLength / 2.0) ? 0 :
		   (int)round((double)alg.orgDnaLength / 2.0) - (alg.orgDnaLength - crossingIndex));
	//Mutating
	
	mutationCount = rand() % (2 * (int)round(MUTATATIONS_PER_BASE_PAIR_CONSTANT * (double)alg.orgDnaLength * 8.0));
	
	for (i = 0; i < mutationCount; i++) {
		
		//Chooses a random byte and copies contents into basePairBuffer
		//Only the first bit will be used
		mutatedBasePair = (rand() % (8 * alg.orgDnaLength));
		memcpy(&basePairBuffer, child.dna.dataPointer + ((int)(mutatedBasePair / 8)), 1);
		//If the bit is 0, make it 1, and vice versa
		if ((basePairBuffer & (unsigned char)pow(2.0, (double)(mutatedBasePair % 8)))) {
			
			memset(child.dna.dataPointer + (int)(mutatedBasePair / 8), 
				   basePairBuffer ^ (unsigned char)pow(2.0, (double)(mutatedBasePair % 8)), 1);
		}
		else {
			
			memset(child.dna.dataPointer + (int)(mutatedBasePair / 8), 
				   basePairBuffer | (unsigned char)pow(2.0, (double)(mutatedBasePair % 8)), 1);
		}
	}
	
	return child;
}




I will go through this last part in steps:
1. Allocated child’s DNA
2. Copy parent 1’s DNA into child’s DNA
3. Use a crossing-like process to copy some of parent 2’s DNA over parent 1’s.
4. Determine the number of mutations to occur based on the MUTATIONS_PER_BASE_PAIR_CONSTANT
4. Choose a random bit in the DNA to flip for each mutation


Ok, that’s it! I’m sure there are parts in the tutorial that were not very understandable and need more clarity, so PLEASE let me know if you were lost at any point, need me to clarify any sections, or have feedback/comments etc. Also, there are probably programming errors that I haven’t noticed yet, so if you think you found one, let me know. Here is a simple implementation that will evolve its DNA to be greater than or equal to 4290000000 (interpreted as an unsigned int). Note that this is close to UINT_MAX, so if you increase it, you could get some weird effects. Obviously, you need to have the GeneticAlgorithm.h and GeneticAlgorithm.c available with the main.m to compile this.


#include "GeneticAlgorithm.h"

unsigned int testOrg(organism orgToTest)
{
	return *(unsigned int *)orgToTest.dna.dataPointer;
}

void progressDisplayer(unsigned int currentFitness)
{
	printf("fitness: %u\n", currentFitness);
}

int main(int argc, char *argv[])
{
	srand(time(NULL));
	int i;
	evolutionary_algorithm ea;
	ea.fitnessTest = testOrg;
	ea.progress = progressDisplayer;
	ea.organismsCount = 50;
	ea.orgDnaLength = sizeof(unsigned int);
	ea.desiredFitness = 4290000000;
	
	organism *orgs = malloc(sizeof(organism) * ea.organismsCount);
	
	for (i = 0; i < 50; i++)
	{
		organism newOrg;
		binary_data newOrgDna;
		newOrgDna.dataPointer = malloc(sizeof(unsigned int));
		memset(newOrgDna.dataPointer, i, 1);
		newOrgDna.length = sizeof(unsigned int);
		newOrg.dna = newOrgDna;
		orgs[i] = newOrg;
	}
	
	ea.organisms = orgs;
	
	organism finishedOrg = evolve(ea);
	printf("final: %u", ea.fitnessTest(finishedOrg));
	free(finishedOrg.dna.dataPointer);	
}




Is This A Good Question/Topic? 3
  • +

Replies To: Evolutionary Algorithms / Genetic Algorithms

#2 Deca  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 7
  • Joined: 09-July 11

Posted 09 July 2011 - 02:19 PM

looks cool but how can we get GeneticAlgorithm.h and GeneticAlgorithm.c?
Was This Post Helpful? 0
  • +
  • -

#3 (KHC)Shadow  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 23
  • Joined: 14-April 11

Posted 10 July 2011 - 03:15 PM

Right after the introduction paragraphs is the both geneticalgorithm.h and .c; they are just combined into one code block.
Was This Post Helpful? 0
  • +
  • -

#4 TheShakingHand  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-January 14

Posted 23 January 2014 - 04:46 PM

View Post(KHC)Shadow, on 10 July 2011 - 03:15 PM, said:

Right after the introduction paragraphs is the both geneticalgorithm.h and .c; they are just combined into one code block.


Hi KHC Shadow! I'm trying to use your code but it is really unclear to me where geneticalgorithm.h and .c can be found. Your comment above isn't really helpful to me. I cannot find them anywhere after the introduction paragraphs. Can you please link to the files or describe very explicitly where I can find them by naming the line-numbers in the full code.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10644
  • View blog
  • Posts: 39,515
  • Joined: 27-December 08

Posted 23 January 2014 - 04:50 PM

See the first code block. Line 60 indicates GeneticAlgorithm.c. I would imagine the code above line 60 pertains to GeneticAlgorithm.h.
Was This Post Helpful? 0
  • +
  • -

#6 (KHC)Shadow  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 23
  • Joined: 14-April 11

Posted 23 January 2014 - 05:23 PM

View Postmacosxnerd101, on 23 January 2014 - 11:50 PM, said:

See the first code block. Line 60 indicates GeneticAlgorithm.c. I would imagine the code above line 60 pertains to GeneticAlgorithm.h.


Thank you, that's exactly right. The code begins with the header guard for geneticalgorithm.h, which ends on line 58. Then there is a comment indicating the start of geneticalgorithm.c. Sorry for not making that more clear.
Was This Post Helpful? 0
  • +
  • -

#7 TheShakingHand  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-January 14

Posted 07 February 2014 - 09:38 AM

Thanks for the reply. I actually got the whole thing to work. I used the first suggested fitnessTest where you wish to calculate x for a given value of y=1.56. The intermediate and final fitness of this calculation is shown in the console but the answer is not. What do you need to do to print the answer of the calculation? I realize that this may be a stupid question because it isn't mentioned in the article which probably means that the answer is trivial.
Was This Post Helpful? 0
  • +
  • -

#8 TheShakingHand  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-January 14

Posted 09 February 2014 - 07:43 AM

It would seem logical to print dnaValue since this represents the variable x. Numerous attempts to implement this have failed though. If anyone can help me it would be greatly appreciated.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1