<p><span lang="EN-US" style="FONT-SIZE: 10.5pt; FONT-FAMILY: "Times New Roman"; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;">Denis Cormier(North Carolina State University)</span><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-ascii-font-family: "Times New Roman"; mso-hansi-font-family: "Times New Roman"; mso-bidi-font-family: "Times New Roman";">开发的，</span><span lang="EN-US" style="FONT-SIZE: 10.5pt; FONT-FAMILY: "Times New Roman"; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;">Sita Raghavan(University of North Carolina at Charlotte)</span><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-ascii-font-family: "Times New Roman"; mso-hansi-font-family: "Times New Roman"; mso-bidi-font-family: "Times New Roman";">修正的遗传算法</span><span lang="EN-US" style="FONT-SIZE: 10.5pt; FONT-FAMILY: "Times New Roman"; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;">C</span><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-ascii-font-family: "Times New Roman"; mso-hansi-font-family: "Times New Roman"; mso-bidi-font-family: "Times New Roman";">代码。</span></p><p></p><p>/***************************************************************/<br/>/* This is a simple genetic algorithm implementation where the */<br/>/* evaluation function takes positive values only and the */<br/>/* fitness of an individual is the same as the value of the */<br/>/* objective function */<br/>/***************************************************************/</p><p>#include <stdio.h><br/>#include <stdlib.h><br/>#include <math.h></p><p>/* Change any of these parameters to match your needs */</p><p>#define POPSIZE 50 /* population size */<br/>#define MAXGENS 1000 /* max. number of generations */<br/>#define NVARS 3 /* no. of problem variables */<br/>#define PXOVER 0.8 /* probability of crossover */<br/>#define PMUTATION 0.15 /* probability of mutation */<br/>#define TRUE 1<br/>#define FALSE 0</p><p>int generation; /* current generation no. */<br/>int cur_best; /* best individual */<br/>FILE *galog; /* an output file */</p><p>struct genotype /* genotype (GT), a member of the population */<br/>{<br/> double gene[NVARS]; /* a string of variables */<br/> double fitness; /* GT's fitness */<br/> double upper[NVARS]; /* GT's variables upper bound */<br/> double lower[NVARS]; /* GT's variables lower bound */<br/> double rfitness; /* relative fitness */<br/> double cfitness; /* cumulative fitness */<br/>};</p><p>struct genotype population[POPSIZE+1]; /* population */<br/>struct genotype newpopulation[POPSIZE+1]; /* new population; */<br/> /* replaces the */<br/> /* old generation */</p><p>/* Declaration of procedures used by this genetic algorithm */</p><p>void initialize(void);<br/>double randval(double, double);<br/>void evaluate(void);<br/>void keep_the_best(void);<br/>void elitist(void);<br/>void select(void);<br/>void crossover(void);<br/>void Xover(int,int);<br/>void swap(double *, double *);<br/>void mutate(void);<br/>void report(void);</p><p>/***************************************************************/<br/>/* Initialization function: Initializes the values of genes */<br/>/* within the variables bounds. It also initializes (to zero) */<br/>/* all fitness values for each member of the population. It */<br/>/* reads upper and lower bounds of each variable from the */<br/>/* input file `gadata.txt'. It randomly generates values */<br/>/* between these bounds for each gene of each genotype in the */<br/>/* population. The format of the input file `gadata.txt' is */<br/>/* var1_lower_bound var1_upper bound */<br/>/* var2_lower_bound var2_upper bound ... */<br/>/***************************************************************/</p><p>void initialize(void)<br/>{<br/>FILE *infile;<br/>int i, j;<br/>double lbound, ubound;</p><p>if ((infile = fopen("gadata.txt","r"))==NULL)<br/> {<br/> fprintf(galog,"\nCannot open input file!\n");<br/> exit(1);<br/> }</p><p>/* initialize variables within the bounds */</p><p>for (i = 0; i < NVARS; i++)<br/> {<br/> fscanf(infile, "%lf",&lbound);<br/> fscanf(infile, "%lf",&ubound);</p><p> for (j = 0; j < POPSIZE; j++)<br/> {<br/> population[j].fitness = 0;<br/> population[j].rfitness = 0;<br/> population[j].cfitness = 0;<br/> population[j].lower = lbound;<br/> population[j].upper= ubound;<br/> population[j].gene = randval(population[j].lower,<br/> population[j].upper);<br/> }<br/> }</p><p>fclose(infile);<br/>}</p><p>/***********************************************************/<br/>/* Random value generator: Generates a value within bounds */<br/>/***********************************************************/</p><p>double randval(double low, double high)<br/>{<br/>double val;<br/>val = ((double)(rand()%1000)/1000.0)*(high - low) + low;<br/>return(val);<br/>}</p><p>/*************************************************************/<br/>/* Evaluation function: This takes a user defined function. */<br/>/* Each time this is changed, the code has to be recompiled. */<br/>/* The current function is: x[1]^2-x[1]*x[2]+x[3] */<br/>/*************************************************************/</p><p>void evaluate(void)<br/>{<br/>int mem;<br/>int i;<br/>double x[NVARS+1];</p><p>for (mem = 0; mem < POPSIZE; mem++)<br/> {<br/> for (i = 0; i < NVARS; i++)<br/> x[i+1] = population[mem].gene;<br/> <br/> population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3];<br/> }<br/>}</p><p>/***************************************************************/<br/>/* Keep_the_best function: This function keeps track of the */<br/>/* best member of the population. Note that the last entry in */<br/>/* the array Population holds a copy of the best individual */<br/>/***************************************************************/</p><p>void keep_the_best()<br/>{<br/>int mem;<br/>int i;<br/>cur_best = 0; /* stores the index of the best individual */</p><p>for (mem = 0; mem < POPSIZE; mem++)<br/> {<br/> if (population[mem].fitness > population[POPSIZE].fitness)<br/> {<br/> cur_best = mem;<br/> population[POPSIZE].fitness = population[mem].fitness;<br/> }<br/> }<br/>/* once the best member in the population is found, copy the genes */<br/>for (i = 0; i < NVARS; i++)<br/> population[POPSIZE].gene = population[cur_best].gene;<br/>}</p><p>/****************************************************************/<br/>/* Elitist function: The best member of the previous generation */<br/>/* is stored as the last in the array. If the best member of */<br/>/* the current generation is worse then the best member of the */<br/>/* previous generation, the latter one would replace the worst */<br/>/* member of the current population */<br/>/****************************************************************/</p><p>void elitist()<br/>{<br/>int i;<br/>double best, worst; /* best and worst fitness values */<br/>int best_mem, worst_mem; /* indexes of the best and worst member */</p><p>best = population[0].fitness;<br/>worst = population[0].fitness;<br/>for (i = 0; i < POPSIZE - 1; ++i)<br/> {<br/> if(population.fitness > population[i+1].fitness)<br/> { <br/> if (population.fitness >= best)<br/> {<br/> best = population.fitness;<br/> best_mem = i;<br/> }<br/> if (population[i+1].fitness <= worst)<br/> {<br/> worst = population[i+1].fitness;<br/> worst_mem = i + 1;<br/> }<br/> }<br/> else<br/> {<br/> if (population.fitness <= worst)<br/> {<br/> worst = population.fitness;<br/> worst_mem = i;<br/> }<br/> if (population[i+1].fitness >= best)<br/> {<br/> best = population[i+1].fitness;<br/> best_mem = i + 1;<br/> }<br/> }<br/> }<br/>/* if best individual from the new population is better than */<br/>/* the best individual from the previous population, then */<br/>/* copy the best from the new population; else replace the */<br/>/* worst individual from the current population with the */<br/>/* best one from the previous generation */</p><p>if (best >= population[POPSIZE].fitness)<br/> {<br/> for (i = 0; i < NVARS; i++)<br/> population[POPSIZE].gene = population[best_mem].gene;<br/> population[POPSIZE].fitness = population[best_mem].fitness;<br/> }<br/>else<br/> {<br/> for (i = 0; i < NVARS; i++)<br/> population[worst_mem].gene = population[POPSIZE].gene;<br/> population[worst_mem].fitness = population[POPSIZE].fitness;<br/> } <br/>}<br/>/**************************************************************/<br/>/* Selection function: Standard proportional selection for */<br/>/* maximization problems incorporating elitist model - makes */<br/>/* sure that the best member survives */<br/>/**************************************************************/</p><p>void select(void)<br/>{<br/>int mem, i, j, k;<br/>double sum = 0;<br/>double p;</p><p>/* find total fitness of the population */<br/>for (mem = 0; mem < POPSIZE; mem++)<br/> {<br/> sum += population[mem].fitness;<br/> }</p><p>/* calculate relative fitness */<br/>for (mem = 0; mem < POPSIZE; mem++)<br/> {<br/> population[mem].rfitness = population[mem].fitness/sum;<br/> }<br/>population[0].cfitness = population[0].rfitness;</p><p>/* calculate cumulative fitness */<br/>for (mem = 1; mem < POPSIZE; mem++)<br/> {<br/> population[mem].cfitness = population[mem-1].cfitness + <br/> population[mem].rfitness;<br/> }</p><p>/* finally select survivors using cumulative fitness. */</p><p>for (i = 0; i < POPSIZE; i++)<br/> { <br/> p = rand()%1000/1000.0;<br/> if (p < population[0].cfitness)<br/> newpopulation = population[0]; <br/> else<br/> {<br/> for (j = 0; j < POPSIZE;j++) <br/> if (p >= population[j].cfitness && <br/> p<population[j+1].cfitness)<br/> newpopulation = population[j+1];<br/> }<br/> }<br/>/* once a new population is created, copy it back */</p><p>for (i = 0; i < POPSIZE; i++)<br/> population = newpopulation; <br/>}</p><p>/***************************************************************/<br/>/* Crossover selection: selects two parents that take part in */<br/>/* the crossover. Implements a single point crossover */<br/>/***************************************************************/</p><p>void crossover(void)<br/>{<br/>int i, mem, one;<br/>int first = 0; /* count of the number of members chosen */<br/>double x;</p><p>for (mem = 0; mem < POPSIZE; ++mem)<br/> {<br/> x = rand()%1000/1000.0;<br/> if (x < PXOVER)<br/> {<br/> ++first;<br/> if (first % 2 == 0)<br/> Xover(one, mem);<br/> else<br/> one = mem;<br/> }<br/> }<br/>}<br/>/**************************************************************/<br/>/* Crossover: performs crossover of the two selected parents. */<br/>/**************************************************************/</p><p>void Xover(int one, int two)<br/>{<br/>int i;<br/>int point; /* crossover point */</p><p>/* select crossover point */<br/>if(NVARS > 1)<br/> {<br/> if(NVARS == 2)<br/> point = 1;<br/> else<br/> point = (rand() % (NVARS - 1)) + 1;</p><p> for (i = 0; i < point; i++)<br/> swap(&population[one].gene, &population[two].gene);</p><p> }<br/>}</p><p>/*************************************************************/<br/>/* Swap: A swap procedure that helps in swapping 2 variables */<br/>/*************************************************************/</p><p>void swap(double *x, double *y)<br/>{<br/>double temp;</p><p>temp = *x;<br/>*x = *y;<br/>*y = temp;</p><p>}</p><p>/**************************************************************/<br/>/* Mutation: Random uniform mutation. A variable selected for */<br/>/* mutation is replaced by a random value between lower and */<br/>/* upper bounds of this variable */<br/>/**************************************************************/</p><p>void mutate(void)<br/>{<br/>int i, j;<br/>double lbound, hbound;<br/>double x;</p><p>for (i = 0; i < POPSIZE; i++)<br/> for (j = 0; j < NVARS; j++)<br/> {<br/> x = rand()%1000/1000.0;<br/> if (x < PMUTATION)<br/> {<br/> /* find the bounds on the variable to be mutated */<br/> lbound = population.lower[j];<br/> hbound = population.upper[j]; <br/> population.gene[j] = randval(lbound, hbound);<br/> }<br/> }<br/>}</p><p>/***************************************************************/<br/>/* Report function: Reports progress of the simulation. Data */<br/>/* dumped into the output file are separated by commas */<br/>/***************************************************************/</p><p>void report(void)<br/>{<br/>int i;<br/>double best_val; /* best population fitness */<br/>double avg; /* avg population fitness */<br/>double stddev; /* std. deviation of population fitness */<br/>double sum_square; /* sum of square for std. calc */<br/>double square_sum; /* square of sum for std. calc */<br/>double sum; /* total population fitness */</p><p>sum = 0.0;<br/>sum_square = 0.0;</p><p>for (i = 0; i < POPSIZE; i++)<br/> {<br/> sum += population.fitness;<br/> sum_square += population.fitness * population.fitness;<br/> }</p><p>avg = sum/(double)POPSIZE;<br/>square_sum = avg * avg * POPSIZE;<br/>stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1));<br/>best_val = population[POPSIZE].fitness;</p><p>fprintf(galog, "\n%5d, %6.3f, %6.3f, %6.3f \n\n", generation, <br/> best_val, avg, stddev);<br/>}</p><p>/**************************************************************/<br/>/* Main function: Each generation involves selecting the best */<br/>/* members, performing crossover & mutation and then */<br/>/* evaluating the resulting population, until the terminating */<br/>/* condition is satisfied */<br/>/**************************************************************/</p><p>void main(void)<br/>{<br/>int i;</p><p>if ((galog = fopen("galog.txt","w"))==NULL)<br/> {<br/> exit(1);<br/> }<br/>generation = 0;</p><p>fprintf(galog, "\n generation best average standard \n");<br/>fprintf(galog, " number value fitness deviation \n");</p><p>initialize();<br/>evaluate();<br/>keep_the_best();<br/>while(generation<MAXGENS)<br/> {<br/> generation++;<br/> select();<br/> crossover();<br/> mutate();<br/> report();<br/> evaluate();<br/> elitist();<br/> }<br/>fprintf(galog,"\n\n Simulation completed\n");<br/>fprintf(galog,"\n Best member: \n");</p><p>for (i = 0; i < NVARS; i++)<br/> {<br/> fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene);<br/> }<br/>fprintf(galog,"\n\n Best fitness = %3.3f",population[POPSIZE].fitness);<br/>fclose(galog);<br/>printf("Success\n");<br/>}<br/>/***************************************************************/</p><p><br/></p>
IP卡
狗仔卡
发表于 2007-5-10 01:56
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
