遺傳算法求解函數(shù)最大值

1、精選優(yōu)質(zhì)文檔-傾情為你奉上人工智能遺傳算法函數(shù)優(yōu)化目錄1引言1.1 摘要函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。本文將用一個(gè)詳細(xì)的例子來說明用遺傳算法解一個(gè)簡(jiǎn)單參數(shù)優(yōu)化問題的過程。這里求解的是一個(gè)函數(shù)的最大值的問題。1.2 背景遺傳算法采納自然進(jìn)化模型。通過保持一個(gè)潛在解的群體執(zhí)行了多方向的搜索并支持這些方向上的信息構(gòu)成和交換。群體經(jīng)過一個(gè)模擬進(jìn)化的過程：在每一代，相對(duì)“好”的解產(chǎn)生，相對(duì)“差”的解死亡。為區(qū)別不同解，我們使用了一個(gè)目標(biāo)（評(píng)價(jià)）函數(shù)，它起著一個(gè)環(huán)境的作用。選擇是用來確定管理費(fèi)用或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)代個(gè)體。雜交組合了兩個(gè)親代染色體的

2、特征，并通過交換父代相應(yīng)的片斷形成了兩個(gè)相似的后代。雜交算子的意圖是在不同潛在解之間進(jìn)行信息交換。變異是通過用一個(gè)等于變異率的概率隨機(jī)地改變被選擇染色體上的一個(gè)或多個(gè)基因。變異算子的意圖是向群體引入一些額外的變化性。運(yùn)用遺傳算法解題必經(jīng)的五個(gè)步驟：1 對(duì)問題潛在解的遺傳表達(dá)。2 產(chǎn)生潛在解初始群體的方法。3 起環(huán)境作用的用“適應(yīng)值”評(píng)價(jià)解的適應(yīng)程度的評(píng)價(jià)函數(shù)。4 改變后代組成的各種遺傳算子。5 遺傳算法所使用的各種參數(shù)：群體規(guī)模、應(yīng)用遺傳算子的概率等。2 實(shí)驗(yàn)過程2.1 程序目標(biāo)在實(shí)驗(yàn)過程中，我們應(yīng)用遺傳算法來模擬一個(gè)函數(shù)優(yōu)化的問題。程序所要解決的問題是求f(x1,x2)=21.5+x1*si

3、n(4pi*x1)+x2*sin(20pi*x2)的最大值，其中-3.0x112.1及4.1x25.8。2.2 實(shí)驗(yàn)原理及步驟1 ） 首先確立變量x1的定義域長(zhǎng)度為15.1；所要求的小數(shù)點(diǎn)以后第四位精度意味著區(qū)間-3.0, 12.1應(yīng)該至少被分成15.1*10000個(gè)等距區(qū)間，即染色體的第一部分需要18位；自變量x2域長(zhǎng)度為1.7，精度要求區(qū)間4.1, 5.8應(yīng)該至少被分成1.7*10000個(gè)等距區(qū)間，即染色體的第二部分需要15位。所以染色體總長(zhǎng)度為33位。用遺傳算法的優(yōu)化函數(shù)f,產(chǎn)生了一個(gè)有pop_size = 20個(gè)染色體的群體。所有染色體的33位都是隨機(jī)初始化。對(duì)每個(gè)染色體進(jìn)行解碼并計(jì)算

4、解碼后的（x1,x2）的適應(yīng)函數(shù)值，eval(vi) (i=1,.,pop_size) = f(x1,x2)。2）為選擇過程建立一個(gè)輪盤。計(jì)算群體的總適應(yīng)值F，并計(jì)算每個(gè)染色體vi (i=1,.,pop_size)的選擇概率pi:pi = eval(vi) / F 和累積概率qi: qi = p1 + . + pi.3）轉(zhuǎn)動(dòng)輪盤20次，每次為新群體選擇一單個(gè)染色體。生成一個(gè)區(qū)間0,1里的20個(gè)數(shù)的一個(gè)隨機(jī)序列。如果一個(gè)隨機(jī)數(shù)位于qi于q(i+1)之間，則q(i+1)被選擇。4）對(duì)新群體中的個(gè)體應(yīng)用雜交算子。雜交概率pc = 0.25，所以預(yù)計(jì)染色體中平均有25%將經(jīng)歷雜交。雜交按照下面的方法進(jìn)

5、行：對(duì)新群體中的每個(gè)染色體，產(chǎn)生在區(qū)間0,1里的隨機(jī)數(shù)r,并從隨機(jī)序列中選出r<0.25的染色體進(jìn)行雜交。5）對(duì)被選擇的染色體隨機(jī)進(jìn)行配對(duì)。并從區(qū)間1,32里產(chǎn)生一個(gè)隨機(jī)整數(shù)pos。數(shù)字pos表示雜交點(diǎn)的位置。6）算子變異。在一位一位基礎(chǔ)上執(zhí)行。變異概率pm = 0.01,所以我們預(yù)計(jì)平均將有1%的位經(jīng)歷變異。整個(gè)群體共有m*pop_size = 660位，可以預(yù)計(jì)平均每代有6.6次變異。因?yàn)槊恳晃欢加芯鹊臋C(jī)會(huì)被變異，所以對(duì)群體中的每一位可以產(chǎn)生區(qū)間0,1里的一個(gè)隨機(jī)數(shù)r,如果r<0.01,則變異此位。7）由上面得到最新的向量群體。對(duì)每個(gè)染色體進(jìn)行解碼，并計(jì)算解碼后的(x1,x2

6、)的適應(yīng)函數(shù)值。選出最好染色體的評(píng)價(jià)值。8）準(zhǔn)備再一次運(yùn)行選擇過程，繼續(xù)進(jìn)行迭代計(jì)算，應(yīng)用遺傳算子及評(píng)價(jià)下一代。2.3程序2.3.1程序理解：初始化函數(shù)：在變量限定的范圍內(nèi)初始化遺傳因子的值。從gadata.txt'這個(gè)文件中讀取每個(gè)變量的上下邊界，并且在這個(gè)范圍內(nèi)隨機(jī)初始化產(chǎn)生染色體中的值。隨機(jī)值生成函數(shù)：多次用到此函數(shù)。評(píng)價(jià)函數(shù)：函數(shù)需要用戶自己定義一個(gè)數(shù)學(xué)函數(shù)式。populationmem.fitness = 21.5+x1*sin(4.0*PI*x1)+x2*sin(20.0*PI*x2);記錄最優(yōu)個(gè)體（取優(yōu)函數(shù)）：前一代的最優(yōu)成員被存儲(chǔ)在數(shù)組的最后。但如果現(xiàn)今這一代的最優(yōu)成員

7、并沒有上一代的好（值小于），則后者（上一代的最優(yōu)值）會(huì)取代本代中最差的成員。如果當(dāng)前代的最優(yōu)值大于上一代的，則將當(dāng)前代的最優(yōu)值拷貝出來，否則則用上一代的最優(yōu)值取代當(dāng)前代的最差值。確保我們始終取到最適合的那個(gè)值。選擇函數(shù)：為的是解決優(yōu)化模型中的最大問題，確保最優(yōu)秀的成員始終存活下來。雜交函數(shù)：void Xover(int one, int two)對(duì)選擇出來的雙親進(jìn)行雜交。變異：void mutate(void)某個(gè)被選擇出來的要進(jìn)行變異的因子，將會(huì)被一個(gè)取值范圍內(nèi)的隨機(jī)量所代替。報(bào)告函數(shù)：void report(void)用來報(bào)告演算程序的進(jìn)展。輸入output文件里的數(shù)據(jù)以逗號(hào)相隔。2.3.

8、3調(diào)試程序：寫好程序之后，就可以進(jìn)行調(diào)試了。當(dāng)在gadat.txt里輸入3 5；6 9；7 8；1 6四組數(shù)據(jù)時(shí)，在”galog.txt”文件中可以看到輸出的結(jié)果?，F(xiàn)附上迭代500次的結(jié)果：1, 32., 23., 5. 2, 32., 25., 4. 3, 32., 25., 4. 4, 32., 26., 4. 5, 34., 27., 4. 6, 34., 27., 4. 7, 34., 28., 4. 8, 34., 28., 4. 9, 34., 28., 3.。 494, 34., 34., 0. 495, 34., 34., 0. 496, 34., 34., 0. 497, 3

9、4., 34., 0. 498, 34., 34., 0. 499, 34., 34., 0. 500, 34., 34., 0.Simulation completed var(0) = 4. var(1) = 8. var(2) = 7. var(3) = 5. Best fitness = 34.附源代碼：#include <stdio.h>#include <stdlib.h>#include <math.h>#define TRUE 1#define FALSE 0#define PMUTATION 0.001 #define MAXGENS 50

10、0 #define POPSIZE 100 #define NVARS 4 #define PXOVER 0.8 int generation; int cur_best; FILE *galog; FILE *output; struct genotype double geneNVARS; double fitness; double upperNVARS; double lowerNVARS; double rfitness; double cfitness; ;struct genotype populationPOPSIZE+1; struct genotype newpopulat

11、ionPOPSIZE+1; void initialize(void);double randval(double, double);void evaluate(void);void keep_the_best(void);void elitist(void);void select(void);void crossover(void);void Xover(int,int);void swap(double *, double *);void mutate(void);void report(void);void initialize(void)FILE *infile;int i, j;d

12、ouble lbound, ubound;if (infile = fopen("gadata.txt","r")=NULL) fprintf(galog,"nCannot open input file!n"); exit(1); remove("output.dat");for (i = 0; i < NVARS; i+) fscanf(infile, "%lf",&lbound); fscanf(infile, "%lf",&ubound); fo

13、r (j = 0; j < POPSIZE; j+) populationj.fitness = 0; populationj.rfitness = 0; populationj.cfitness = 0; populationj.loweri = lbound; populationj.upperi = ubound; populationj.genei = randval(populationj.loweri, populationj.upperi); fclose(infile);double randval(double low, double high)double val;v

14、al = (double)(rand()%1000)/1000.0)*(high - low) + low;return(val);void evaluate(void)if (output = fopen("output.dat","a")=NULL) exit(1); int mem;int i;double xNVARS+1;double PI = 3.;for (mem = 0; mem < POPSIZE; mem+) for (i = 0; i < NVARS; i+) xi+1 = populationmem.genei; po

15、pulationmem.fitness = 21.5+x1*sin(4.0*PI*x1)+x2*sin(20.0*PI*x2); if (populationmem.fitness <40 && populationmem.fitness>35) fprintf(output, "n%5d, %6.9f, %6.9f, %6.9f ", generation, x1,x2,populationmem.fitness); fclose(output);void keep_the_best()int mem;int i;cur_best = 0; f

16、or (mem = 0; mem < POPSIZE; mem+) if (populationmem.fitness > populationPOPSIZE.fitness) cur_best = mem; populationPOPSIZE.fitness = populationmem.fitness; for (i = 0; i < NVARS; i+) populationPOPSIZE.genei = populationcur_best.genei;void elitist()int i;double best, worst; int best_mem, wor

17、st_mem; best = population0.fitness;worst = population0.fitness;for (i = 0; i < POPSIZE - 1; +i) if(populationi.fitness > populationi+1.fitness) if (populationi.fitness >= best) best = populationi.fitness; best_mem = i; if (populationi+1.fitness <= worst) worst = populationi+1.fitness; wo

18、rst_mem = i + 1; else if (populationi.fitness <= worst) worst = populationi.fitness; worst_mem = i; if (populationi+1.fitness >= best) best = populationi+1.fitness; best_mem = i + 1; if (best >= populationPOPSIZE.fitness) for (i = 0; i < NVARS; i+) populationPOPSIZE.genei = populationbes

19、t_mem.genei; populationPOPSIZE.fitness = populationbest_mem.fitness; else for (i = 0; i < NVARS; i+) populationworst_mem.genei = populationPOPSIZE.genei; populationworst_mem.fitness = populationPOPSIZE.fitness; void select(void)int mem, i, j, k;double sum = 0;double p;for (mem = 0; mem < POPSI

20、ZE; mem+) sum += populationmem.fitness; for (mem = 0; mem < POPSIZE; mem+) populationmem.rfitness = populationmem.fitness/sum; population0.cfitness = population0.rfitness;for (mem = 1; mem < POPSIZE; mem+) populationmem.cfitness = populationmem-1.cfitness + populationmem.rfitness; for (i = 0;

21、i < POPSIZE; i+) p = rand()%1000/1000.0; if (p < population0.cfitness) newpopulationi = population0; else for (j = 0; j < POPSIZE;j+) if (p >= populationj.cfitness && p<populationj+1.cfitness) newpopulationi = populationj+1; for (i = 0; i < POPSIZE; i+) populationi = newpop

22、ulationi; void crossover(void)int i, mem, one;int first = 0; double x;for (mem = 0; mem < POPSIZE; +mem) x = rand()%1000/1000.0; if (x < PXOVER) +first; if (first % 2 = 0) Xover(one, mem); else one = mem; void Xover(int one, int two)int i;int point; if(NVARS > 1) if(NVARS = 2) point = 1; el

23、se point = (rand() % (NVARS - 1) + 1; for (i = 0; i < point; i+) swap(&populationone.genei, &populationtwo.genei); void swap(double *x, double *y)double temp;temp = *x;*x = *y;*y = temp;void mutate(void)int i, j;double lbound, hbound;double x;for (i = 0; i < POPSIZE; i+) for (j = 0; j

24、< NVARS; j+) x = rand()%1000/1000.0; if (x < PMUTATION) lbound = populationi.lowerj; hbound = populationi.upperj; populationi.genej = randval(lbound, hbound); void report(void)int i;double best_val; double avg; double stddev; double sum_square; double square_sum; double sum; sum = 0.0;sum_squa

25、re = 0.0;for (i = 0; i < POPSIZE; i+) sum += populationi.fitness; sum_square += populationi.fitness * populationi.fitness; avg = sum/(double)POPSIZE;square_sum = avg * avg * POPSIZE;stddev = sqrt(sum_square - square_sum)/(POPSIZE - 1);best_val = populationPOPSIZE.fitness;fprintf(galog, "n%5d

26、, %6.9f, %6.9f, %6.9f ", generation, best_val, avg, stddev);printf( "n%5d, %6.9f, %6.9f, %6.9f ", generation, best_val, avg, stddev);void main(void)int i;if (galog = fopen("galog.txt","w")=NULL) exit(1); generation = 0;fprintf(galog, "n generation best average standard n");printf( "n generation best average standard n");fprintf(galog, " number value fitness deviation n");printf(" n