/* ga.c */ /* Genetic Algorithm Program */ /* By Will Lennon */ /* Started 1-28-95 */ /* Updated 10-4-95 */ /* Note to new users: A GENETIC ALGORITHM is a a parallel search method that manipulates a string of numbers (a chromosome) in a manner similar to the laws of evolution and biology. In this software, that string of numbers represents parameters of a mathematical function, called a "fitness function." In this sense, chromosomes (parameters) which correspond to a large function value are deemed "more fit" than chromosomes which correspond to smaller function values. Some GA Definitions: A GENE is a single-digit number. (Ex: 1,2,3, etc ) (In this program we use the Base-10 number system, so a gene is any number between 0 and 9. A lot of GAs use the binary number system, in which case a gene is either 1 or 0) A CHROMOSOME is a string of genes. (Ex: 12345678901 could be a chromosome of length 11) A TRAIT is a decimal number (Ex: 56.0, 0.002, -600.0 ) An INDIVIDUAL is the object that the GA is attempting to optimize. An individual is described by its chromosome. The chromosome determines an individual's traits. The individual's traits determine its fitness. A POPULATION is a set of individuals. A CHROMOSOME SECTION is a substring of a chromosome that corresponds to a particular trait. If there are N traits on a chromosome, there must be N chromosome sections. In this software, use the constant Trait_Start[] to specify how to separate a chromosome into sections. Example: if a chromosome of length 11 is: 12345678901 and there are 2 traits on that chromosome, then the following are possible chromosome sections: Chrom. Sect. 1 Chrom. Sect. 2 Trait_Start[] values: 12 345678901 {0,2,11} 123 45678901 {0,3,11} 1234 5678901 {0,4,11} 12345 678901 {0,5,11} etc... Basically, you pick points on the chromosome where to end one section and begin the next. If you had 3 traits on the chromosome, you would pick 2 locations on the chromosome to separate the sections. Note: Chromosome sections should be at least 2 genes long. The first gene in each section is used to determine the sign of the trait, and the remaining terms determine the size of the trait. If you have a section of size 1, you will have a trait that has no value, only a positive or negative sign. DECODING A CHROMOSOME SECTION INTO A TRAIT: If the constant "negative" is set to one: The first gene of each chromosome section determines the sign of the trait. If this gene is 0-4, the trait is negative. If this gene is 5-9, the trait is positive. The remaining genes determine the size of the trait. The second gene is the most significant digit, while the last gene is the least significant digit. If the constant "negative" is set to zero: No gene is used for the sign. All genes are used for magnitude. To determine the relative magnitude of a trait, this software uses the Decimal[] constant. This number determines how many digits to the left of the decimal to place the first digit of the trait (=second gene on the chrom. section). Finally, the constant Offset_Trait is added to this trait value to get the final trait value. Ex: For Chromosome section #i = 123456 (negative = 1) Offset_Trait = 0 Offset_Trait = -10.0 If Decimal[i] = Then Trait[i]= Then Trait[i] = -2 -0.0023456 -10.0023456 -1 -0.023456 -10.0234560 0 -0.23456 -10.2345600 1 -2.3456 -12.3456000 2 -23.456 -33.4560000 etc... Offset_Trait is used to shift the traits up or down. This is helpful if you want at trait to lie, e.g., between 800 and 1799. You could set: Offset_Trait = 800, Low_Trait = 0, and High_Trait=999. Likewise you could set: Offset_Trait = 0, Low Trait = 800, and High Trait = 1799. The advantage of the first method is that your chromsome would be 1 gene fewer because you could define it for 3 genes, 000-999, as opposed to 4 genes, 0800-1799. The High_Gene[] and Low_Gene[] are arrays that limit the possibilities that each gene may take. For example, if you have a chromosome with 1 trait that is limited to between 1000 and 2499, you could set: High_Gene{2,4,9,9} Low_Gene{1,0,0,0} This makes the GA more effecient because it doesn't try to mutate the first gene into any number other than 1 or 2, which are the only two 'legal' possibilities. Naturally, if you are allowing negative numbers, the first gene should range 0-9. If you don't know what you're doing, just set all Low_Genes to 0 and all High_Genes to 9. CROSSOVER TYPES: Right now you have two choices for crossover. If cross_type=1, then the GA selects a single crossover site and swaps all the genes before that site. If cross_type=0, then the GA swaps each gene with a probability of 50%. In other words, there is no one site, but rather each gene is crossed-over individually. Ex. If you have two genes xxxxxxxxxx and yyyyyyyyyy that crossover, some possible results are: cross_type = 1 cross_type = 0 xxxxxyyyyy yyxxyyxxyyxy yyyyyxxxxx xxyyxxyyxxyx -or- xxyyyyyyyy xyyyyyxyxyxy yyxxxxxxxx yxxxxxyxyxyx -or- xxxxxxxyyy xxxyyyxxxxyx yyyyyyyxxx yyyxxxyyyyxy etc... RUNNING THIS PROGRAM: Compile this program by typing: gcc ga.c -o ga -lm Then run the program by typing: ga This program creates the following data files: stats.out : A complete list of every generation and the fitness of every member in the population. best.out : A list of the "most fit" member of each generation. generation.data : A list of all the information of every member of the last generation. TO CHANGE THIS GENETIC ALGORITHM to optimize a different fitness function, you only need to change the following areas: 1) The #define definitions 2) The global constants 3) The Get_Fitness() function (This is the first function defined below) You may also like to modify the Fit_params structure to allow for a fitness function that varies with passing generations (this is not necessary for a simple GA, but is useful with a GMRAC). Presently this structure contains only an example that is not being used. Note: The #define ZERO is necessary to compensate for numerical error. It is sufficiently small for most applications. However, if you have a trait that has significant digits smaller than ZERO, you should reduce ZERO until it is smaller than your least significant digit. IMPORTANT: Depending on the computer system you compile this on, you may need to change the MaxRandom constant in the function Rand_Num(). If you run this software in the Control Research Lab (CL343) you will be OK with the present MaxRandom value. For the EE HP's (er4hp site), change this number to 32767. For other machines, check the manual pages for the function rand() in and change MaxRandom to the maximum integer value rand() returns. */ /******************* INCLUDE FILES ***************************************/ #include #include #include #include /***************** DEFINITIONS *******************************************/ #define NUM_TRAITS 2 /* Number of Traits on the Chromosome */ #define CHROM_LENGTH 14 /* Total Length of Chromosome */ #define MAX_POPULATION 20 /* Maximum population size */ #define MIN_POPULATION 10 /* Minimum population size */ #define ZERO 0.00000000001 /* Compensate for roundoff error in Encode_Chrom*/ /****************** GLOBAL CONSTANTS **************************************/ const int max_generation = 100; /* Number of Generations */ const double cross_prob = 0.9; /* Probability of Crossover */ const double mutat_prob = 0.1; /* Probability of Mutation */ const int elitism = 1; /* elitism ON/OFF 1/0 */ const int output = 1; /* Save stats.out to file? 1=yes 0=no*/ const int negative = 0; /* Negative traits possible? 1=yes 0=no */ const int cross_type = 0; /* Method of crossover */ /* High_Trait & Low_Trait indicate the max/min allowable value of each trait on the chromosome. */ const double High_Trait[NUM_TRAITS] = {+7.0, +5.0}; const double Low_Trait[NUM_TRAITS] = {0.0, 0.0}; const double Offset_Trait[NUM_TRAITS] = {-1.0, 1.0}; const int High_Gene[CHROM_LENGTH] = {6,9,9,9,9,9,9,4,9,9,9,9,9,9}; const int Low_Gene[CHROM_LENGTH] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0}; /* Decimal[] describes how to decode a chromosome section into a trait. It tells the function Decode_Chrom() how many genes of the chromosome section to place to the left of the decimal point. For example, if a chromosome section [i] is "45678", and Decimal[i] = 2, the corresponding trait would equal -56.78. If Decimal[i] = -1, the corresponding trait would equal -0.05678. Note that the first gene of each chromosome section indicates + or -, (see Decode_Chrom()). */ const int Decimal[NUM_TRAITS] = {1, 1}; /* Trait_Start[] represents the gene on the chromosome where each trait starts. This array must always begin with '0' and end with CHROM_LENGTH. The number of intermediate terms is dependent on NUM_TRAITS. In effect, this determines the length of each chromosome section and hence determines the precision of the corresponding trait. */ const int Trait_Start[NUM_TRAITS+1] = {0,7,CHROM_LENGTH}; /*********************** TYPES *******************************************/ /* CREATE FITNESS PARAMETERS TO PASS TO FITNESS FUNCTION */ typedef struct { double example; /* Change/add/delete this structure as desired */ } Fit_params; /* CREATE TYPE CHROMOSOME: STRING OF GENES */ typedef struct { int gene[CHROM_LENGTH]; } Chromosome; /* CREATE TYPE TRAITS */ typedef struct { double num[NUM_TRAITS]; } Traits; /* CREATE TYPE INDIVIDUAL */ /* A complete description of every member of the population, including the members of the previous population (parents) who produced it. */ typedef struct { Chromosome chrom; Traits trait; double fitness; int parents[2]; } Individual; /* CREATE TYPE SURVIVORS */ /* "Survivors" are those members of the current population that are selected to reproduce into the next generation */ typedef struct { int bestmember; int size; int number[MAX_POPULATION+1]; Chromosome chrom[MAX_POPULATION+1]; } Survivors; /* CREATE TYPE POPULATION */ /* A complete description of the entire population, including the population size, the generation number (count), and number of mutations, etc */ typedef struct { Individual member[MAX_POPULATION+1]; double sumfitness; int bestmember; int worstmember; int size; int count; int crossovers; int mutations; } Population; /**************************************************************************/ void Get_Fitness(Individual *member, Fit_params *params) { /* Get_Fitness determines the fitness of one individual This is the only function (besides maybe main()) that needs to be modified. I moved it up front so you can find it more easily. */ double fitness; double error; double x,y,z; int i=0; /* Change of variables to something simpler */ x = member->trait.num[0]; y = member->trait.num[1]; z = params->example; /* This could be used in the fitness evaluation */ /* This fitness function will be maximized at x=0, y= 3.14159 */ fitness = pow(cos(x) + sin(y/2.0),6.0); /* fitness = pow(3.0*(1.0-x),2.0) * exp(-x*x - y*y-2.0*y-1.0) - 10.0*(0.5*x-x*x*x-y*y*y*y)*exp(-x*x-y*y) - 0.3333333*exp(-x*x-2.0*x-1.0-y*y); */ /* Make certain fitness is non-negative */ /* REMEMBER: The best individuals have the highest fitness. */ if (fitness<0.0) fitness = 0.00; member->fitness = fitness; } /********************* FUNCTION DEFINITIONS **********************************/ /* GA.C */ void Statistics(Population *pop); void Save_Generation(Population *pop); /* REPRODUCTION.C */ Population First_Generation(int pop_size); void Next_Generation(Population *pop, int pop_size); Survivors Select_Parents(Population *pop, int pop_size); Population Make_Offspring(Survivors parents); void Reproduce(Chromosome parent1, Chromosome parent2, Chromosome *child1, Chromosome *child2, int *crossovers, int *mutations); void Crossover(Chromosome *child1, Chromosome *child2); void Mutate(Chromosome *child, int site); int Check_Chrom(Chromosome chrom); void Create_Chrom(Chromosome *chrom, int flag); double Power(int x, int y); /* FITNESS.C */ void Find_Fitness(Population *pop, Fit_params *params); Traits Decode_Chrom(Chromosome chrom); Chromosome Encode_Traits(Traits trait); void Get_Fitness(Individual *member, Fit_params *params); /* RANDOM.C */ double Rand_Num(void); int Flip(double chance); int Rand_Int(int high, int low); void Randomize(void); double Rand_Double(double high, double low); /**************************************************************************/ void main(void) { Population pop; Fit_params params; FILE *File; int pop_size; /* Initialize Random Number Generator */ Randomize(); /* Remove previous output file */ if (output) { File = fopen("stats.out","w"); fclose(File); } File = fopen("best.out","w"); fclose(File); /**** CREATE FIRST GENERATION ****/ pop_size = MAX_POPULATION; pop = First_Generation(pop_size); params.example = 0.0; /* Initialize fitness function parameters */ Find_Fitness(&pop, ¶ms); Statistics(&pop); /***** CREATE NEW GENERATIONS ****/ while (pop.countcount); fprintf(File,"\nMember Chromosome Traits "); fprintf(File," Fitness Parents"); for(i=0;isize;i++) { fprintf(File,"\n%3d ",i); for (x=0;xmember[i].chrom.gene[x]); } fprintf(File," "); for (x=0;xmember[i].trait.num[x]); fprintf(File," %9.5lf ",pop->member[i].fitness); fprintf(File,"%3d %3d",pop->member[i].parents[0], pop->member[i].parents[1]); } fprintf(File,"\nBest: %5.4lf ", pop->member[pop->bestmember].fitness); fprintf(File,"(#%d)",pop->bestmember); fprintf(File,"\nAverage: %5.4lf", pop->sumfitness/(double)pop->size); fprintf(File,"\nWorst: %5.4lf", pop->member[pop->worstmember].fitness); fprintf(File,"\nCrossovers: %d Mutations: %d",pop->crossovers, pop->mutations); fprintf(File,"\n"); fclose(File); } /* WRITE BEST MEMBER TO FILE BEST.OUT */ File = fopen ("best.out","a"); if (pop->count==1) fprintf(File,"\nGeneration : Fitness : Chromosome : Traits\n"); fprintf(File," %3d ",pop->count); fprintf(File,"%15.10lf ",pop->member[pop->bestmember].fitness); for (x=0;xmember[pop->bestmember] .chrom.gene[x]); } fprintf(File," "); for (x=0;xmember[pop->bestmember] .trait.num[x]); fprintf(File,"\n"); fclose(File); } /****************************************************************************/ void Save_Generation(Population *pop) { /* Save all the data in the pop structure to a file called "generation.data" */ FILE *File; int x,i; File = fopen("generation.data","w"); fprintf(File,"%20.15lf ",pop->sumfitness); fprintf(File,"%d ",pop->bestmember); fprintf(File,"%d ",pop->worstmember); fprintf(File,"%d ",pop->size); fprintf(File,"%d ",pop->count); fprintf(File,"%d ",pop->crossovers); fprintf(File,"%d\n",pop->mutations); for (i=0;isize;i++) { for (x=0;xmember[i].chrom.gene[x]); fprintf(File,"\n"); for (x=0;xmember[i].trait.num[x]); fprintf(File,"\n%15.10lf ",pop->member[i].fitness); fprintf(File,"%d %d\n\n",pop->member[i].parents[0], pop->member[i].parents[1]); } fclose(File); } /***********************************************************************/ /* REPRODUCTION.C */ /***********************************************************************/ Population First_Generation(int pop_size) { /* First_Generation() creates a population of size pop_size. */ /* This is done by randomly creating individual chromosomes with */ /* Create_Chrom() */ Population pop; Chromosome chrom; int k; /* Make Certain pop_size is a nice number */ if (pop_sizeMAX_POPULATION) pop_size = MAX_POPULATION; for(k=0;kMAX_POPULATION) pop_size = MAX_POPULATION; parents = Select_Parents(pop,pop_size); nextpop = Make_Offspring(parents); nextpop.count = pop->count + 1; *pop = nextpop; } /*************************************************************************/ Survivors Select_Parents(Population *pop, int pop_size) { /* Select_Parents() takes members of pop, selects the ones who will survive and reproduce, and places them into parents */ /* This function uses the 'Roulette-Wheel' selection method as described by David E. Goldberg */ Survivors parents; int k; int member_count; int count; double pointer; double sum; /* DETERMINE NUMBER OF PARENTS TO CREATE*/ if (elitism) count = pop_size - 1; else count = ((pop_size+1)/2)*2; for(k=0;ksumfitness*Rand_Num(); /* DETERMINE WHICH MEMBER IS SELECTED BY ROULETTE WHEEL */ member_count = -1; sum = 0.0; while (sumpop->size) { printf("\n\nERROR: Negative Fitness Evaluation! "); member_count=0; } sum += pop->member[member_count].fitness; } /* NOW ASSIGN SELECTED MEMBER TO BECOME A PARENT */ parents.chrom[k]=pop->member[member_count].chrom; parents.number[k]=member_count; } /* AFTER ALL PARENTS HAVE BEEN SELECTED, */ /* ADD BEST INDIVIDUAL IF elitism IS ON */ if (elitism) { parents.chrom[pop_size-1] = pop->member[pop->bestmember].chrom; parents.number[pop_size-1] = pop->bestmember; } parents.size=pop_size; return(parents); } /***********************************************************************/ Population Make_Offspring(Survivors parents) { /* Make_Offspring takes the parents chromosomes and creates a new generation of individuals using Reproduce(). This function assumes parent[n] mates with parent[n+1], n=0,2,4, etc. and there are an even number of parents (parents.size=even) */ int c,j; Chromosome child1, child2; Population next; int crossovers = 0; int mutations = 0; int flag; for(c=0;cgene[count] = child2->gene[count]; child2->gene[count] = temp.gene[count]; } } else { site=Rand_Int(1,CHROM_LENGTH-1); for(count=0;countgene[count] = child2->gene[count]; child2->gene[count] = temp.gene[count]; } } /* MAKE CERTAIN CHILD1 IS VALID */ do { flag=Check_Chrom(*child1); if (flag) Create_Chrom(child1,flag); } while (flag); /* MAKE CERTAIN CHILD2 IS VALID */ do { flag=Check_Chrom(*child2); if (flag) Create_Chrom(child2,flag); } while (flag); } /**************************************************************************/ void Mutate(Chromosome *child, int site) { /* Mutate changes the gene #site. This function *may* create an 'illegal' chromosome, so make certain to check the chromosome after it is mutated. */ Chromosome temp; int newgene; temp = *child; newgene=Rand_Int(Low_Gene[site],High_Gene[site]); temp.gene[site] = newgene; *child = temp; } /************************************************************************/ int Check_Chrom(Chromosome chrom) { /* Check_Chrom checks chrom to see if it is a valid chromosome. Check_Chrom returns 0 if chrom has all legal genes. otherwise this function returns the number of the last bad trait number it finds */ int count; int flag; Traits trait; flag = 0; trait = Decode_Chrom(chrom); for(count=0;count High_Trait[count]) || (trait.num[count] < Low_Trait[count])) flag = count+1; return (flag); } /********************************************************************/ void Create_Chrom(Chromosome *chrom, int flag) { /* Create_Chrom takes chrom and creates a new & valid trait #flag If flag = 0, then Create_Chrom creates an all new chromosome */ Chromosome temp_chrom; Traits trait; int length; if (!flag) do /* CREATE AN ALL NEW CHROMOSOME */ { for(length=0;lengthy;k--) result = result / x ; } if (y>0) { for (k=0;kmember[0].trait = Decode_Chrom(pop->member[0].chrom); Get_Fitness(&(pop->member[0]), params); sumfitness = pop->member[0].fitness; /* ESTABLISH FIRST GUESS AT HIGH & LOW FITNESS */ highfitness = pop->member[0].fitness; lowfitness = pop->member[0].fitness; /* GET FITNESS OF THE REMAINDING CHROMOSOMES */ for(k=1;ksize;k++) { /* DECODE THE CHROMOSOME INTO INDIVIDUAL TRAITS */ pop->member[k].trait = Decode_Chrom(pop->member[k].chrom); Get_Fitness(&(pop->member[k]), params); fitness = pop->member[k].fitness; sumfitness += fitness; /* FIND BEST MEMBER */ if (fitness>highfitness) { highfitness=fitness; high = k; } /* FIND WORST MEMBER */ if (fitnessbestmember = high; pop->worstmember = low; pop->sumfitness = sumfitness; } /**************************************************************************/ /* RANDOM.C */ /**************************************************************************/ void Randomize(void) { /* Randomize() initializes the pseudo-random number generator by seeding the generator with some function of time */ int stime; long int ltime; ltime = time(NULL); stime = (unsigned) ltime/2; srand(stime); } /**************************************************************************/ double Rand_Num(void) { /* Rand_Num() returns a pseudo-random number between 0.0 and 1.0 by calling the function rand() from If the GA is generating unusual numbers (all 0's, or hanging up), you may need to modify the MaxRandom value according to the rand() function on your computer system. */ int MaxRandom =2147483647; /* = 2^31 - 1 */ /* int MaxRandom = 32767;*/ /* = 2^15 -1 */ double number; number = (double)rand() / (double)MaxRandom; return (number); } /**************************************************************************/ int Flip(double chance) { /* This function returns TRUE (1) with probability (chance) */ /* and returns FALSE (0) with probability (1-chance). */ /* 0.0 <= chance <= 1.0 */ return (chance > Rand_Num() ? 1 : 0); } /*************************************************************************/ int Rand_Int(int high, int low) { /* Rand_Int returns an integer between high and low */ /* with equal probability for all numbers (including high & low) */ int temp; /* MAKE CERTAIN LOW <= HIGH */ if (low>high) { temp = low; low = high; high = temp; } return( (int)(Rand_Num()*(high-low+1)) + low ) ; } /*************************************************************************/ double Rand_Double(double high, double low) { /* Rand_Double returns a double between high and low */ /* with equal probability for all numbers */ double temp; /* MAKE CERTAIN LOW <= HIGH */ if (low>high) { temp = low; low = high; high = temp; } return( (double)(Rand_Num()*(high-low)) + low ) ; } /**************************** END ****************************************/