一個簡單實用的遺傳算法c程序

1、一個簡單實用的遺傳算法 c程序(轉(zhuǎn)載) C+ 2009-07-28 23:09:03 閱讀418評論0 字號： 大中小 這是一個非常簡單的遺傳算法源代碼，是由Denis Cormier (North Caroli na State University)開發(fā)的，Sita S.Raghavan (University of North Carolina at Charlotte)修正。代碼 保證盡可能少，實際上也不必查錯。對一特定的應(yīng)用修正此代碼，用戶只需改變常數(shù)的定義 并且定義 評價函數(shù)”即可。注意代碼的設(shè)計是求最大值，其中的目標(biāo)函數(shù)只能取正值；且函 數(shù)值和個體的適應(yīng)值之間沒有區(qū)別。該系統(tǒng)使用

2、比率選擇、精華模型、單點雜交和均勻變異。 如果用Gaussian變異替換均勻變異，可能得到更好的效果。代碼沒有任何圖形，甚至也沒 有屏幕輸出，主要是保證在平臺之間的高可移植性。讀者可以從，目錄coe/evol 中的文件prog.c中獲得。要求輸入的文件應(yīng)該命名為gadata.txt 系統(tǒng)產(chǎn)生的輸出文件為 galog.txt 輸入的文件由幾行組成：數(shù)目對應(yīng)于變量數(shù)。且每一行提供次序?qū)?yīng)于變 量的上下界。如第一行為第一個變量提供上下界，第二行為第二個變量提供上下界，等等。 /*/ /* This is a simple genetic algorithm implement

3、ation where the */ /* evaluati on fun ctio n takes positive values on ly and the*/ /* fitn ess of an in dividual is the same as the value of the*/ /* objective fun ctio n*/ /*/ #in clude #in clude #in clude /* Change any of these parameters to match your n eeds */ /* populati on size */ /* max. nu m

4、ber of gen erati ons */ /* no. of problem variables */ /* probability of crossover */ /* probability of mutatio n */ #defi ne POPSIZE 50 #defi ne MAXGENS 1000 #defi ne NVARS 3 #defi ne PXOVER 0.8 #defi ne PMUTATION 0.15 #defi ne TRUE 1 #defi ne FALSE 0 int gen erati on; int cur_best; /* curre nt gen

5、 erati on no. */ /* best in dividual */ FILE *galog;/* an output file */ struct geno type /* geno type (GT), a member of the populati on */ double gen eNVARS; /* a stri ng of variables一個變量字符串*/ double fitn ess; /* GTs fitness 適應(yīng)度 */ double upperNVARS; /* GTs variables upper bound變量的上限 */ double lowe

6、rNVARS; /* GTs variables lower bou nd變量的下限 */ double rfitn ess; /* relative fitness相對適應(yīng)度 */ double cfitn ess; /* cumulative fitness累計適應(yīng)度 */ ； /* populati on */ struct ge no type populatio nPOPSIZE+1; struct geno type n ewpopulati on POPSIZE+1; /* new populati on; */ /* replaces the */ /* old gen era

7、ti on */ /* Declarati on of procedures used by this gen etic algorithm */ void in itialize(void); double ran dval(double, double); void evaluate(void); void keep_the_best(void); void elitist(void); void select(void); void crossover(void); void Xover(i nt,i nt); void swap(double *, double *); void mu

8、tate(void); void report(void); /*/ /* In itializatio n fun cti on: In itializes the values of genes*/ /* with in the variables boun ds. It also in itializes (to zero)*/ /* all fitn ess values for each member of the populati on .It*/ /* reads upper and lower bounds of each variable from the*/ /* in p

9、ut file gadata.txt. It ran domly gen erates values*/ */ /* betwee n these bounds for each gene of each geno type in the /* populatio n. The format of the in put file gadata.txt is*/ /* var1_lower_bo und var1_upper bound*/ /* var2_lower_bo und var2_upper bound .*/ /*/ void in itialize(void) FILE *i n

10、file; int i, j; double lbo und, ubo und; if (i nfile = fope n(gadata.txt,r)=NULL) fprin tf(galog,nCannot ope n in put file!n); exit(1); /* in itialize variables with in the bounds */ for (i = 0; i NVARS; i+) fscanf(in file, %lf, fscan f(i nfile, %lf, for (j = 0; j POPSIZE; j+) populati on j.fit ness

11、 = 0; populati on j.rfit ness = 0; populati on j.cfit ness = 0; populati on j.loweri = Ibo und; populati on j.upperi= ubo und; populati on j.ge nei = ran dval(populati on j.loweri, populatio nj.upperi); fclose(i nfile); /*/ /* Ran dom value gen erator: Gen erates a value within bounds */ /*/ double

12、ran dval(double low, double high) double val; val = (double)(ra nd()%1000)/1000.0)*(high - low) + low; return(val); * /* Evaluati on function: This takes a user defi ned function.*/ /* Each time this is cha nged, the code has to be recompiled. */ /* The curre nt fun ctio n is:x1F2-x1*x2+x3*/ /*/ voi

13、d evaluate(void) int mem; int i; double xNVARS+1; for (mem = 0; mem POPSIZE; mem+) for (i = 0; i NVARS; i+) xi+1 = populati on mem.ge nei; populatio nmem.fit ness = (x1*x1) - (x1*x2) + x3; /*/ /* Keep_the_best fun cti on: This fun cti on keeps track of the*/ /* best member of the populati on. Note t

14、hat the last entry in*/ */ /* the array Populati on holds a copy of the best in dividual /*/ void keep_the_best() int mem; int i; cur_best = 0; /* stores the in dex of the best in dividual */ for (mem = 0; mem populatio n POPSIZE.fit ness) cur_best = mem; populati on POPSIZE.fit ness = populatio n m

15、em.fit ness; /* once the best member in the populati on is found, copy the genes */ for (i = 0; i NVARS; i+) populati on POPSIZE.ge nei = populati on cur_best.ge nei; /*/ /* Elitist fun cti on: The best member of the previous gen erati on */ */ /* is stored as the last in the array. If the best memb

16、er of /* the curre nt gen eratio n is worse the n the best member of the*/ /* previous gen erati on, the latter one would replace the worst*/ /* member of the curre nt populati on*/ /*/ void elitist() int i; double best, worst;/* best and worst fitn ess values */ int best_mem, worst_mem; /* i ndexes

17、 of the best and worst member */ best = populati on O.fit ness; worst = populati on O.fit ness; for (i = 0; i populati on i+1.fit ness) if (populatio ni.fit ness = best) best = populati on i.fit ness; best_mem = i; if (populati on i+1.fit ness = worst) worst = populati on i+1.fit ness; worst_mem = i

18、 + 1; else if (populati on i.fit ness = best) best = populati on i+1.fit ness; best_mem = i + 1; /* if best in dividual from the new populati on is better tha n */ */ /* the best i ndividual from the previous populati on, the n /* copy the best from the new populati on; else replace the*/ /* worst i

19、 ndividual from the curre nt populati on with the*/ /* best one from the previous gen erati on*/ if (best = populatio nPOPSIZE.fit ness) for (i = 0; i NVARS; i+) populati on POPSIZE.ge nei = populatio n best_mem.ge nei; populati on POPSIZE.fit ness = populati on best_mem.fit ness; else for (i = 0; i

20、 NVARS; i+) populati on worst_mem.ge nei = populati on POPSIZE.ge nei; populati on worst_mem.fit ness = populati on POPSIZE.fit ness; * /* Selectio n function: Stan dard proporti onal selectio n for*/ */ */ /* maximizati on problems in corporat ing elitist model - makes /* sure that the best member

21、survives * void select(void) int mem, i, j, k; double sum = 0; double p; /* find total fitn ess of the populati on */ for (mem = 0; mem POPSIZE; mem+) sum += populatio n mem.fit ness; /* calculate relative fitn ess */ for (mem = 0; mem POPSIZE; mem+) populati on mem.rfit ness =populati on mem.fit ne

22、ss/sum; populatio n O.cfit ness = populati on O.rfit ness; /* calculate cumulative fitn ess */ for (mem = 1; mem POPSIZE; mem+) populati on mem.cfit ness =populati on mem-1.cfit ness + populati on mem.rfit ness; /* fin ally select survivors using cumulative fitn ess. */ for (i = 0; i POPSIZE; i+) p

23、= ran d()%1000/1000.0; if (p populati on O.cfit ness) n ewpopulati on i = populati on 0; else for (j = 0; j = populati on j.cfit ness /* once a new populati on is created, copy it back */ for (i = 0; i POPSIZE; i+) populati on i = n ewpopulati on i; * */ /* Crossover selecti on: selects two pare nts

24、 that take part in /* the crossover. Impleme nts a sin gle point crossover*/ /*/ void crossover(void) int i, mem, one; int first =0; /* count of the nu mber of members chose n */ double x; for (mem = 0; mem POPSIZE; +mem) x = ran d()%1000/1000.0; if (x 1) if(NVARS = 2) point = 1; else poi nt = (ran

25、d() % (NVARS - 1) + 1; for (i = 0; i poi nt; i+) swap( /*/ /* Swap: A swap procedure that helps in swapp ing 2 variables */ /*/ void swap(double *x, double *y) double temp; temp = *x; *x = *y; *y = temp; /*/ /* Mutati on: Ran dom uniform mutatio n. A variable selected for */ /* mutati on is replaced

26、 by a ran dom value betwee n lower and*/ */ /* upper bounds of this variable void mutate(void) * int i, j; double lbo und, hbo und; double x; for (i = 0; i POPSIZE; i+) for (j = 0; j NVARS; j+) x = ran d()%1000/1000.0; if (x PMUTATION) /* find the bounds on the variable to be mutated */ Ibound = pop

27、ulati on i.lowerj; hbo und = populatio ni.upperj; populati on i.ge nej = ran dval(lbo und, hbo un d); * /* Report fun ctio n: Reports progress of the simulati on. Data*/ /* dumped into the output file are separated by commas*/ /*/ void report(void) int i; double best_val; /* best populati on fitn es

28、s */ double avg; /* avg populati on fitn ess */ double stddev; /* std. deviati on of populati on fitn ess */ double sum_square; /* sum of square for std. calc */ double square_sum; /* square of sum for std. calc */ double sum;/* total populati on fitn ess */ sum = 0.0; sum_square = 0.0; for (i = 0;

29、i POPSIZE; i+) sum += populatio ni.fit ness; sum_square += populati on i.fit ness * populati on i.fit ness; avg = sum/(double)POPSIZE; square_sum = avg * avg * POPSIZE; stddev = sqrt(sum_square - square_sum)/(POPSIZE - 1); best_val = populatio nPOPSIZE.fit ness; fprin tf(galog, n%5d,%6.3f, %6.3f, %6.3f nn, gen eratio n, best_val, avg, stddev); /*/ /* Main fun cti on: Each gen erati on in volves select ing the best */ /* members, perform ing crossover if (galog = fope n( galog.txt,w)=NULL) exit(1); gen erati on = 0; sta ndard n); deviati on n ”)； fprin tf(galog