//This is NOT a genetic algorithm - just a demonstration of the ability of good mutations to prevail even when rare. It is a demonstration of 'fixation'. //It does not demonstrate transposition. It does not demonstrate creation of new functionality. It does not demonstrate anything except for the spread of beneficial adaptations. //Another way this could be viewed, instead of being the mutation of individual genes, as being the mutation of traits. I.e., we could treat trait 23 as being "eyesight", or trait 7 as being "walking speed". In a real organism, these are comprised of many genes; here, this would be the net effect of all mutations to all of those genes. //To keep it simple, we're not going to do "pairs" of genes, selecting dominant/recessive genes, etc for now. We'll just have it pick the gene from one mate or the other. //Again, for simplicity, we're going to have all organisms be bisexual. //Each gene has a "functionality" value assigned to it. The organism's total competitive edge is the product of all of its genes. When actually competing, since having better genes doesn't necessarily mean you're going to do better, the algorithm selects a random number of a range from zero to the fitness of the organism for competition. Note that this is just a way to represent the net effect of all genes (or functional elements) of the organism. //Competition is done in a "free for all" mode. A random child organism is selected. A random competitor is selected. They duke it out, using the randomness/fitness method described above. The loser dies. //I chose the fixed types of mutations instead of a bell curve for simplicity and for transparency (I want it to be obvious what is going on with the numbers). //I took very inefficient algorithms also in the interest of transparency (such as the method for picking competitors) //Again, let me repeat: This demonstration is not a GA, and it is done for simplicity only, just to prove a single point about beneficial, rare mutations being able to fixate into a population. //Criticisms are *welcome*. If requested, I may make it more complex, or even make it all of the way to being a true GA. //If you're going to be nonproductively critical (i.e., not mentioning *which parts* you think may be causing it to produce the result you don't expect, my reply is: then code your own algorithm so we can compare :) ). //If you don't understand any part, please ask! I'll try and comment better, or use a simpler algorithm. //My email address is daystar_setting@myself.com #define POP_SIZE 100000 //total organisms #define GENES 100 //genes per organism #define OFFSPRING 20 //offspring per organism #define MUT_PERCENT 2.0 //rate of mutation per gene. #define MUT_PERCENT_MINUS_90 14.27 //percent of mutations that hurt the organism by 90% of its competitive advantage. #define MUT_PERCENT_MINUS_50 14.27 //percent of mutations that hurt the organism by 50% of its competitive advantage. #define MUT_PERCENT_MINUS_20 14.27 //percent of mutations that hurt the organism by 20% of its competitive advantage. #define MUT_PERCENT_MINUS_10 14.27 //percent of mutations that hurt the organism by 10% of its competitive advantage. #define MUT_PERCENT_MINUS_5 14.27 //percent of mutations that hurt the organism by 5% of its competitive advantage. #define MUT_PERCENT_MINUS_2 14.27 //percent of mutations that hurt the organism by 2% of its competitive advantage. #define MUT_PERCENT_MINUS_1 14.28 //percent of mutations that hurt the organism by 1% of its competitive advantage. #define MUT_PERCENT_NOCHANGE 0.0 //percent of mutations that don't hurt or help the organism #define MUT_PERCENT_PLUS_1 0.08 //percent of mutations that help the organism by 1% #define MUT_PERCENT_PLUS_2 0.015 //percent of mutations that help the organism by 2% #define MUT_PERCENT_PLUS_5 0.004 //percent of mutations that help the organism by 5% #define MUT_PERCENT_PLUS_10 0.001 //percent of mutations that help the organism by 10% #define TRUE 1 #define FALSE 0 #include #include float frand() //Returns a random number from 0 to 1. { return (((float)random())/(float)RAND_MAX); } int main(int argv, char** argc) { //General arrays. We're not going to free them since the code is an infinite loop - we'll let the OS do it. :) float* fitness[GENES]; //Gets allocate to the number of genes; is basically [POP_SIZE][GENES]. We couldn't just allocate on the heap, because it's too big. float* offspring_fitness[GENES][OFFSPRING]; //Same as above; is basically [POP_SIZE][OFFSPRING][GENES]. char* dead[OFFSPRING]; //Loop counters int i,j,k,l,count; //Reproduction variables int mate, parent1, offspring1, parent2, offspring2; //Mutation variables float mut_type; float mut_type_sum; //Competition variables float rating1, rating2, random_rating1, random_rating2; //Statistics variables int generation = 0; int best, worst; float this_avg, this_std, this_fit, avg_gene, avg_std, best_avg, best_std, worst_avg, worst_std, std_avg, avg_fit, best_fit, worst_fit, diff; //Check to make sure that the mutation rates effectively add up to 100%. We can't test *exactly*, because of rounding errors in floating point arithmetic. if (fabs(MUT_PERCENT_MINUS_90 + MUT_PERCENT_MINUS_50 + MUT_PERCENT_MINUS_20 + MUT_PERCENT_MINUS_10 + MUT_PERCENT_MINUS_5 + MUT_PERCENT_MINUS_1 + MUT_PERCENT_NOCHANGE + MUT_PERCENT_PLUS_1 + MUT_PERCENT_PLUS_2 + MUT_PERCENT_PLUS_5 + MUT_PERCENT_PLUS_10 - 100.0) < 0.0001) { printf("Error: Mutation rates aren't sufficiently close to 100%.\n"); return 1; } //Allocate the arrays printf("Allocating memory...\n"); for (i=0; i random_rating2) dead[offspring2][parent2]=TRUE; else dead[offspring1][parent1]=TRUE; } //Replace the parents with the remaining offspring printf("Replacing.\n"); count=0; for (i=0; i best_fit) { best=i; best_fit=this_fit; } else if (this_fit < worst_fit) { worst=i; worst_fit=this_fit; } } avg_fit/=POP_SIZE; avg_gene=0.0; for (i=0; i