遺傳算法的并行實(shí)現(xiàn)

遺傳算法的并行實(shí)現(xiàn)章衡2007310437一、 問題描述遺傳算法是通過模擬自然界生物進(jìn)化過程來求解優(yōu)化問題的一類自組織、自適應(yīng)的人工智能技術(shù)。它主要基于達(dá)爾文的自然進(jìn)化論和孟德爾的遺傳變異理論。多數(shù)遺傳算法的應(yīng)用是處理一個(gè)由許多個(gè)體組成的群體，其中每個(gè)個(gè)體表示問題的一個(gè)潛在解。對(duì)個(gè)體存在一個(gè)評(píng)估函數(shù)來評(píng)判其對(duì)環(huán)境的適應(yīng)度。為反映適者生存的思想，算法中設(shè)計(jì)一個(gè)選擇機(jī)制，使得：適應(yīng)度好的個(gè)體有更多的機(jī)會(huì)生存。在種群的進(jìn)化過程中，主要存在兩種類型的遺傳算子：雜交和變異。這些算子作用于個(gè)體對(duì)應(yīng)的染色體，產(chǎn)生新的染色體，從而構(gòu)成下一代種群中的個(gè)體。該過程不斷進(jìn)行，直到找到滿足精度要求的解，或者達(dá)到設(shè)定的進(jìn)化代數(shù)。顯然，這樣的思想適合于現(xiàn)實(shí)世界中的一大類問題，因而具有廣泛的應(yīng)用價(jià)值。遺傳算法的每一次進(jìn)化過程中的，各個(gè)體之間的操作大多可以并列進(jìn)行，因此，一個(gè)非常自然的想法就是將遺傳算法并行化，以提高計(jì)算速度。本報(bào)告中試圖得到一個(gè)并行遺傳算法的框架，并考察并行化之后的一些特性。為簡單起見(本來應(yīng)該考慮更復(fù)雜的問題，如TSP。因時(shí)間有些緊張，請(qǐng)老師原諒)，考慮的具有問題是：對(duì)給定的正整數(shù)n、n元函數(shù)f，以及定義域D，求函數(shù)f在D內(nèi)的最大值。二、 串行遺傳算法染色體與適應(yīng)度函數(shù)對(duì)函數(shù)優(yōu)化問題，一個(gè)潛在的解就是定義域D中的一個(gè)點(diǎn)(x0,x1,...,氣_1)，因此，我們只需用一個(gè)長度為n的實(shí)數(shù)數(shù)組來表示一個(gè)個(gè)體的染色體。由于問題中要求求函數(shù)f的最大值，我們可以以個(gè)體所代表點(diǎn)(x0,x1,...,xn_1)在f函數(shù)下的值來判斷該個(gè)體的好壞。因此，我們直接用函數(shù)f作為個(gè)體的適應(yīng)度函數(shù)。選擇機(jī)制選擇是遺傳算法中最主要的機(jī)制，也是影響遺傳算法性能最主要的因素。若選擇過程中適應(yīng)度好的個(gè)體生存的概率過大，會(huì)造成幾個(gè)較好的可行解迅速占據(jù)種群，從而收斂于局部最優(yōu)解；反之，若適應(yīng)度對(duì)生存概率的影響過小，則會(huì)使算法呈現(xiàn)出純粹的隨機(jī)徘徊行為，算法無法收斂。下面我們介紹在實(shí)驗(yàn)中所使用的選擇機(jī)制。我們定義P為當(dāng)前種群內(nèi)所有個(gè)體的集合，。(。),。⑴，…，。3-1)為P中所有個(gè)體的一個(gè)

固定排列。若xeP為某一個(gè)體，f(x)表示該個(gè)體的適應(yīng)度，則種群P的適應(yīng)度定義為：

庶)=云f(x())i=0對(duì)任意個(gè)體xeP，x的相對(duì)適應(yīng)度定義為r(x)=f(x)/s(P)。累積適應(yīng)度定義為(x(k))=￡r(x(i))

i=0進(jìn)行選擇之前，先產(chǎn)生一個(gè)0到1之間的隨機(jī)實(shí)數(shù)t，若滿足r(xk)<t<r(xk+i)，則第k+1個(gè)個(gè)體被選中。循環(huán)以上過程，即得到生成下一代種群的母體。具體實(shí)現(xiàn)見如下函數(shù)：voidpop_select(void){intmem,i,j,k;doublesum=0;doublep;/*計(jì)算種群適應(yīng)度之和*/for(mem=0;mem<POPSIZE;mem++){sum+=(population[mem].fitness-lower_fitness);} —/*計(jì)算相應(yīng)適應(yīng)度*/for(mem=0;mem<POPSIZE;mem++){population[mem].rfitness=(population[mem].fitness-lower_fitness)/sum;}population[0].cfitness=population[0].rfitness;/*計(jì)算累積適應(yīng)度*/for(mem=1;mem<POPSIZE;mem++){population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;}/*按照累積適應(yīng)度概率選取母體種群*/for(i=0;i<POPSIZE;i++){p=rand()%1000/1000.0;if(p<population[0].cfitness)newpopulation[i]=population]。];else{for(j=0;j<POPSIZE;j++)if(p>=population[j].cfitness&&p<population[j+1].cfitness)newpopulation[i]=population[j+1];}}for(i=0;i<POPSIZE;i++)population[i]=newpopulation[i];}雜交算子雜交算子的流程一般如下：按雜交概率選擇一對(duì)參與進(jìn)化的個(gè)體;隨機(jī)確定一個(gè)截?cái)帱c(diǎn)；將兩個(gè)個(gè)體的染色體從截?cái)帱c(diǎn)處截?cái)?，并交換，從而得到新的染色體。具體算法見如下函數(shù)：voidcrossover(void){inti,j,k,m,point;intfirst=0;doublex;for(k=0;k<POPSIZE;k++){x=rand()%1000/1000.0;if(x<PXOVER){first++;if(first%2==0){if(NVARS==2)point=1;elsepoint=(rand()%(NVARS-1))+1;for(j=0;j<point;j++)swap(&population[m].gene[j],&population[k].gene[j]);}elsem=k;}}}變異變異操作的實(shí)現(xiàn)相當(dāng)簡單，只需遍歷各染色體的各個(gè)單元，按某一變異概率將該單元變成一個(gè)隨機(jī)的合法值。具體操作如下函數(shù)所示：voidmutate(void){inti,j;doublelbound,hbound;doublex;for(i=0;i<POPSIZE;i++)for(j=0;j<NVARS;j++){x=rand()%1000/1000.0;if(x<PMUTATION){population[i].gene[j]=randval(lower[j],upper[j]);}}}串行遺傳算法的主要流程如圖1所示。在每一次進(jìn)化過程中，總是找出種群中的最優(yōu)解與最差解，并將最優(yōu)解保存，將本次最差解用上次保存的最優(yōu)解替換，這樣保證了各次進(jìn)化的最優(yōu)解的適應(yīng)度不會(huì)降低，從而增快收斂的速度。

圖1串行遺傳算法基本流程三、算法設(shè)計(jì)分析圖1中的串行算法，容易看出，在選擇函數(shù)中，計(jì)算相對(duì)適應(yīng)度需要用到全局種群的適應(yīng)度之和，計(jì)算個(gè)體xk+1的累積適應(yīng)度依賴于孔的累積適應(yīng)度，如果在并行算法中要原封不動(dòng)地模擬串行算法的運(yùn)算，這些數(shù)據(jù)依賴關(guān)系都將產(chǎn)生通訊。更為不幸的是，選擇后的個(gè)體需在各進(jìn)程中作大量數(shù)據(jù)遷移。雜交算子中，一次雜交需要用到母體中的兩個(gè)個(gè)體，若在這兩個(gè)個(gè)體分配在不同進(jìn)程，則需要進(jìn)行一次通訊。此后的變異和評(píng)估都可以非常容易的實(shí)現(xiàn)并行，并且完全不需要任何通訊。但最后一步求最優(yōu)個(gè)體和最差個(gè)體需要對(duì)各進(jìn)程進(jìn)行歸約。由這些分析可以看出，完全地模擬串行情形將使算法變得相當(dāng)?shù)托?。幸運(yùn)地是，遺傳算法本身是一個(gè)概率算法，我們完全可以對(duì)串行算法作些必要的改變。如圖2所示，我們將整個(gè)種群分成p個(gè)子種群，每一子種群由一個(gè)單一的進(jìn)程負(fù)責(zé)。各進(jìn)程獨(dú)立地完成串行遺傳算法的整個(gè)過程，唯一不同的是選擇函數(shù)。各進(jìn)程作選擇操作時(shí)，首先計(jì)算各子種群內(nèi)的局部累積適應(yīng)度，然后根據(jù)局部累積適應(yīng)度選擇若干（本算法實(shí)現(xiàn)中使用的時(shí)常數(shù)3,也可以設(shè)為子種群大小的一個(gè)函數(shù)）個(gè)體按一固定規(guī)則輪流發(fā)送到其他進(jìn)程；同時(shí)，按照該規(guī)則相應(yīng)地從其他進(jìn)程獲取若干用來進(jìn)行交流的個(gè)體。獲取到個(gè)體后，先將其

暫存；然后按串行算法中的選擇機(jī)制從原子種群中選擇進(jìn)行進(jìn)化的母體；最后再用之前暫存的個(gè)體完成進(jìn)程間的種群交流。對(duì)每一個(gè)待交流的個(gè)體，具體策略如下：（1） 隨機(jī)地從本地的待進(jìn)化母體種群內(nèi)抽取與之進(jìn)行交流的母體；（2） 比較本地個(gè)體與傳送過來的待交流個(gè)體，選取適應(yīng)度高者作為最終母體。各進(jìn)程在每一次進(jìn)化過程中，均分別保留各自的局部最優(yōu)解，用來在下一次進(jìn)化中替換局部最差的個(gè)體。各進(jìn)程均完成所預(yù)定的進(jìn)化迭代后，最后對(duì)各進(jìn)程的局部最優(yōu)解進(jìn)行歸約，從而得到整個(gè)算法的全局最優(yōu)解。算法的主要流程詳見圖2。4已完成規(guī)定進(jìn)

化代數(shù)??,已完成規(guī)定進(jìn)

化代數(shù)??已完成規(guī)定進(jìn)

化代數(shù)，丕按適應(yīng)度隨機(jī)選擇參與進(jìn)化的個(gè)體與其他進(jìn)行交

換個(gè)體雜交變異評(píng)估選出最優(yōu)個(gè)體和最差

個(gè)體,保存最優(yōu)個(gè)體，并

將最差個(gè)體用上一代

最優(yōu)個(gè)體替代4已完成規(guī)定進(jìn)

化代數(shù)??,已完成規(guī)定進(jìn)

化代數(shù)??已完成規(guī)定進(jìn)

化代數(shù)，丕按適應(yīng)度隨機(jī)選擇參與進(jìn)化的個(gè)體與其他進(jìn)行交

換個(gè)體雜交變異評(píng)估選出最優(yōu)個(gè)體和最差

個(gè)體,保存最優(yōu)個(gè)體，并

將最差個(gè)體用上一代

最優(yōu)個(gè)體替代按適應(yīng)度隨機(jī)選擇參與進(jìn)化的個(gè)體與其他進(jìn)行交換個(gè)體F雜交1r變異1評(píng)估1F選出最優(yōu)個(gè)體和最差個(gè)體,保存最優(yōu)個(gè)體，并將最差個(gè)體用上一代最優(yōu)個(gè)體替代是丕按適應(yīng)度隨機(jī)選擇參與進(jìn)化的個(gè)體與其他進(jìn)行交

換個(gè)體雜交變異評(píng)估選出最優(yōu)個(gè)體和最差

個(gè)體,保存最優(yōu)個(gè)體，并

將最差個(gè)體用上一代

最優(yōu)個(gè)體替代開始1FF■V初始化種群1初始化種群2???初始化種群p歸約最優(yōu)解輸出最優(yōu)解f \終止圖2并行遺傳算法基本流程四、算法實(shí)現(xiàn)該算法實(shí)現(xiàn)的最關(guān)鍵部分為選擇中的種群交流，該功能有如下函數(shù)實(shí)現(xiàn)voidpop_select(void){ —MPI_Statusstatus;MPI_Requesthandle;intmem,i,j,k;doublesum=0;doublep;staticstructgenotypeex_member[EX_NUM];/*計(jì)算子種群的總適應(yīng)度*/for(mem=0;mem<TASK_NUM(pid);mem++){sum+=(population[mem].fitness-lower_fitness);} —/*計(jì)算各個(gè)體相應(yīng)適應(yīng)度*/for(mem=0;mem<TASK_NUM(pid);mem++){population[mem].rfitness=(population[mem].fitness-lower_fitness)/sum;}population[0].cfitness=population[0].rfitness;/*計(jì)算各個(gè)體累積適應(yīng)度*/for(mem=1;mem<TASK_NUM(pid);mem++){population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;}/*按照累積適應(yīng)度概率選取種群交流個(gè)體，并發(fā)送和接收*/for(i=1;i<=EX_NUM;i++){p=rand()%1000/1000.0;if(p<population[0].cfitness){MPI_Isend(&population[0],sizeof(structgenotype)/sizeof(char),MPI_ChAr,(pid+i*generation)%pnum,0,MPI_COMM_WORLD,&handle);}else{for(j=0;j<TASK_NUM(pid);j++)if(p>=population[j].cfitness&&p<population[j+1].cfitness){MPI_Isend(&population[j+1],sizeof(structgenotype)/sizeof(char),MPI_CHAR,(pid+i*generation)%pnum,0,MPI_COMM_WORLD,&handle);break;}}MPI_Recv(&ex_member[i-1],sizeof(structgenotype)/sizeof(char),MPI_CHAR,(pid+(pnum-i)*generation)%pnum,0,MPI_CoMM_WORLD,&status);}/*按照累積適應(yīng)度概率選取母體種群*/for(i=0;i<TASK_NUM(pid);i++){p=rand()%1000/1000.0;if(p<population[0].cfitness)newpopulation[i]=population]。];else{for(j=0;j<TASK_NUM(pid);j++)if(p>=population[j].cfitness&&p<population[j+1].cfitness)newpopulation[i]=population[j+1];}}for(i=0;i<TASK_NUM(pid);i++)population[i]=newpopulation[i];/*按優(yōu)勝劣汰的原則完成種群交流*/for(i=0;i<EX_NUM;i++){j=rand()%TASK_NUM(pid);if(population[j].fitness<ex_member[i].fitness){for(k=0;k<NVARS;k++){population[j].gene[k]=ex_member[i].gene[k];}population[j].rfitness=0;population[j].cfitness=0;population[j].fitness=ex_member[i].fitness;} —}}另外，全局最優(yōu)解的歸約由如下代碼實(shí)現(xiàn)：MPI_Op_create((MPI_User_function*)gene_max,1,&my_op);MPI_Reduce(local_best_individual,best_individual,NVARS+1,MPI_DOUBLE,my_op,pnum-1,MPI_COMM_WORLD);其中，具體的歸約操作由如下函數(shù)實(shí)現(xiàn)：voidgene_max(double*in,double*inout,int*len,MPI_Datatype*dptr){ — —inti;if(inout[0]<in[0]){ /*比較適應(yīng)度*/for(i=0;i<*len;++i){inout[i]=in[i];/*復(fù)制適應(yīng)度較高的個(gè)體*/}}}五、算法分析與實(shí)驗(yàn)結(jié)果下面的實(shí)驗(yàn)結(jié)果是在166.111.143.24上利用結(jié)點(diǎn)cn115和cn116獲得的。用來計(jì)算最大值的函數(shù)為f(x,x,x,x,x,x)=x6一xxxx2X+X5XX1 2 3 4 5 6 1 1234 6 3 56xxx2x x2x2x2+x2xxx+xxx3x245 6 1 3 5 2 356 124 5其定義域如文件ga_data.txt中所示，總種群大小為500，最大進(jìn)化次數(shù)為2000。進(jìn)程個(gè)數(shù)1234567運(yùn)算時(shí)間32.3085949.1328124.3359382.7773443.6992192.9492192.621094加速比13.5376397.45135111.6329108.73389610.95496612.326377運(yùn)行結(jié)果x122.45505022.45505022.45505022.45505022.45505022.45505022.455050X27.2055007.2790007.2895007.2370007.2895007.2895007.289500X319.26950019.23900019.26950019.26950019.26950019.26950019.269500X44.9440004.9920004.0720004.9840004.8880004.9840004.968000X5-1.193000-1.196500-1.200000-1.200000-1.200000-1.196500-1.200000X6-9.120000-9.113180-9.072260-9.120000-9.120000-9.120000-9.120000f157521400,960884157373629.694664157325373.684378157701606.886265157673921.515628157623544.425141157702393.783168進(jìn)程個(gè)數(shù)891011121314運(yùn)算時(shí)間2.2265622.5742192.4492192.6171882.2890622.6640622.597656

加速比14.51053012.55083313.19138612.34477414.11433812.12756812.437595運(yùn)行結(jié)果x122.45505022.45505022.45505022.45505022.45505022.45505022.455050X27.2895007.2895007.2790007.2895007.2895007.2895007.279000X319.26950019.26950019.26950019.26950019.26950019.26950019.269500X44.9200004.9760004.9920004.9840004.9920004.9680004.992000X5-1.200000-1.200000-1.200000-1.200000-1.200000-1.196500-1.200000X6-9.120000-9.120000-9.120000-9.120000-9.120000-9.120000-9.120000f157689427,608764157704566.391334157624693.663186157706742.306205157708921.527178157619195.230127157707891.211178表1實(shí)驗(yàn)結(jié)果表1中最為有趣的現(xiàn)象是，當(dāng)進(jìn)程數(shù)小于5時(shí)，該算法的加速比似乎與進(jìn)程數(shù)p存在一個(gè)平方關(guān)系，也就是說，存在一個(gè)超線性加速的關(guān)系。進(jìn)程數(shù)大于等于5時(shí)，這種超線性加速實(shí)際也應(yīng)該存在，只是由于節(jié)點(diǎn)數(shù)的限制，被進(jìn)程管理的開銷所限制。下面我們通過估計(jì)時(shí)間復(fù)雜性來分析造成這種超線性加速的原因。如果將對(duì)染色體中每一變元上的一個(gè)計(jì)算看作一個(gè)基本計(jì)算，并設(shè)變元數(shù)為奴總種群中個(gè)體數(shù)為n，進(jìn)程數(shù)則對(duì)每一進(jìn)程，分析容易得到：pop_select函數(shù)最壞情形的時(shí)間復(fù)雜性為O((kn/p)2)，crossover函數(shù)最壞情形的時(shí)間復(fù)雜性為O(kn/p)，mutate函數(shù)最壞情形的時(shí)間復(fù)雜性為O(kn/p)，評(píng)估函數(shù)最壞情形的時(shí)間復(fù)雜性為O(kn/p)，elitist函數(shù)最壞情形的時(shí)間復(fù)雜性為O(n/p+k)。此外，按照算法的設(shè)計(jì)，在選擇過程中的通訊所耗費(fèi)的時(shí)間為O(kn/p)。綜合可知，一次進(jìn)化的時(shí)間復(fù)雜性為O((kn/p)2)。因此，所有進(jìn)程總的計(jì)算時(shí)間醉最壞情形的漸近上界為O((kn)2/p).而串行遺傳算法一次進(jìn)化的時(shí)間復(fù)雜性為O((kn)2)，這就解釋了為什么p小于5的情形會(huì)具有超線性加速。當(dāng)然，這并不能說明并行計(jì)算真能產(chǎn)生超線性加速比，因?yàn)槲覀兛梢苑浅Ｓ行У赜靡粋€(gè)進(jìn)程來模擬p個(gè)進(jìn)程的計(jì)算，也就是說在串行的情形下也能達(dá)到這樣的加速。真正值得研究的問題是分析上述建立并行遺傳算法的收斂速度與串行遺傳算法的收斂速度之間的關(guān)系。不過從表1可以看出，進(jìn)程增加時(shí)，解得質(zhì)量并沒有任何降低。因?yàn)闀r(shí)間的限制，不能在這里進(jìn)行進(jìn)一步的理論分析，請(qǐng)老師諒解。六、源程序清單#definePOPSIZE500#define#definePOPSIZE500#defineNVARS6#defineMAXGENS2000#definePXOVER0.8#include"mpi.h”#include<stdio.h>#include<stdlib.h>#include<math.h>/*雜交概率*/#definePMUTATION0.15 /*變異概率*/#defineTASK_NUM(i) ((POPSIZE+pnum-1)/pnum)#defineEX_NUM 3structgenotype{doublegene[NVARS];/*適應(yīng)度*//*適應(yīng)度*//*相對(duì)適應(yīng)度*//*累積適應(yīng)度*/doublerfitness;doublecfitness;}*population,*newpopulation;doubleupperbound[NVARS];doublelocal_best_individual[NVARS+1];/*局部最優(yōu)解*/doublebest_individual[NVARS+1];/*全局最優(yōu)解*/intgeneration;doublelower_fitness;FILE*galog;intpid,pnum;doublerandval(doublelow,doublehigh){doubleval;val=((double)(rand()%1000)/1000.0)*(high-low)+low;returnval;}voidinitialize(void){FILE*infile;inti,j,r;doublelbound,ubound;MPI_Statusstatus;population=malloc(sizeof(structgenotype)*(TASK_NUM(pid)+1));newpopulation=malloc(sizeof(structgenotype)*(TASK_NUM(pid)+1));if(pid==pnum-1){if((infile=fopen("ga_data.txt”,''r''))==NULL){fprintf(galog,"\nCannotopeninputfile!\n");exit(1);}srand(time(0));for(i=0;i<pnum;i++){r=rand();MPI_Send(&r,1,MPI_INT,i,1,MPI_COMM_WORLD);}for(i=0;i<NVARS;i++){fscanf(infile,"%lf”,&lowerbound[i]);fscanf(infile,"%lf”,&upperbound[i]);}}else{MPI_Recv(&r,1,MPI_INT,pnum-1,1,MPI_COMM_WORLD,&status);srand(r);}MPI_Bcast(lowerbound,NVARS,MPI_DOUBLE,pnum-1,MPI_COMM_WORLD);MPI_Bcast(upperbound,NVARS,MPI_DOUBLE,pnum-1,MPI_COMM_WORLD);for(j=0;j<TASK_NUM(pid);j++){population[j].fitness=0;population[j].rfitness=0;population[j].cfitness=0;//printf("\nGeneofmember%din%dis:\n",j,pid);for(i=0;i<NVARS;i++){population[j].gene[i]=randval(lowerbound[i],upperbound[i]);//printf("%lf”,population[j].gene[i]);}}if(pid==pnum-1)fclose(infile);}voidevaluate(void){intmem;inti;doublex[NVARS+1];lower_fitness=0.0;for(mem=0;mem<TASK_NUM(pid);mem++){for(i=0;i<NVARS;i++)x[i+1]=population[mem].gene[i];population[mem].fitness=(x[1]*x[1]*x[1]*x[1]*x[1]*x[1])-(x[1]*x[2]*x[3]*x[4]*x[4]*x[6])+(x[3]*x[3]*x[3]*x[3]*x[3]*x[5]*x[6])-(x[2]*x[4]*x[5]*x[5]*x[6])-(x[1]*x[1]*x[3]*x[3]*x[5]*x[5])+(x[2]*x[2]*x[3]*x[5]*x[6])+(x[1]*x[2]*x[4]*x[4]*x[4]*x[5]);if(population[mem].fitness<lower_fitness)lower_fitness=population[mem].fitness;}}voidkeep_the_best(){intmem,i,cur_best=0;for(mem=0;mem<TASK_NUM(pid);mem++){if(population[mem].fitness>population[TASK_NUM(pid)].fitness){cur_best=mem;population[TASK_NUM(pid)].fitness=population[mem].fitness;}}for(i=0;i<NVARS;i++){population[TASK_NUM(pid)].gene[i]=population[cur_best].gene[i];local_best_individual[i+1]=population[cur_best].gene[i];}local_best_individual[0]=population[cur_best].fitness;}voidpop_select(void){MPI_Statusstatus;MPI_Requesthandle;intmem,i,j,k;doublesum=0;doublep;staticstructgenotypeex_member[EX_NUM];for(mem=0;mem<TASK_NUM(pid);mem++){sum+=(population[mem].fitness-lower_fitness);}for(mem=0;mem<TASK_NUM(pid);mem++){population[mem].rfitness=(population[mem].fitness-lower_fitness)/sum;}population[0].cfitness=population[0].rfitness;for(mem=1;mem<TASK_NUM(pid);mem++){population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;for(i=1;i<=EX_NUM;i++){p=rand()%1000/1000.0;if(p<population[0].cfitness){MPI_Isend(&population[0],sizeof(structgenotype)/sizeof(char),MPI_CHAR,(pid+i*generation)%pnum,0,MPI_COMM_WORLD,&handle);}else{for(j=0;j<TASK_NUM(pid);j++)if(p>=population[j].cfitness&&p<population[j+1].cfitness){MPI_Isend(&population[j+1],sizeof(structgenotype)/sizeof(char),MPI_CHAR,(pid+i*generation)%pnum,0,MPI_COMM_WORLD,&handle);break;}}MPI_Recv(&ex_member[i-1],sizeof(structgenotype)/sizeof(char),MPI_CHAR,(pid+(pnum-i)*generation)%pnum,0,MPI_COMM_WORLD,&status);}for(i=0;i<TASK_NUM(pid);i++){p=rand()%1000/1000.0;if(p<population[0].cfitness)newpopulation[i]=population]。];else{for(j=0;j<TASK_NUM(pid);j++)if(p>=population[j].cfitness&&p<population[j+1].cfitness)newpopulation[i]=population[j+1];}}for(i=0;i<TASK_NUM(pid);i++)population[i]=newpopulation[i];for(i=0;i<EX_NUM;i++){j=rand()%TASK_NUM(pid);if(population[j].fitness<ex_member[i].fitness){for(k=0;k<NVARS;k++){population[j].gene[k]=ex_member[i].gene[k];}population[j].rfitness=0;population[j].cfitness=0;population[j].fitness=ex_member[i].fitness;}}}voidswap(double*x,double*y){doubletemp;temp=*x;*x=*y;*y=temp;}voidXover(intone,inttwo){inti;intpoint;if(NVARS>1){if(NVARS==2)point=1;elsepoint=(rand()%(NVARS-1))+1;point=for(i=0;i<point;i++)swap(&population[one].gene[i],&population[two].gene[i]);}}voidcrossover(void){inti,mem,one;intfirst=0;doublex;for(mem=0;mem<TASK_NUM(pid);mem++){x=rand()%1000/1000.0;if(x<PXOVER){first++;if(first%2==0)Xover(one,mem);elseone=mem;}}}voidmutate(void){inti,j;for(i=0;i<TASK_NUM(pid);i++)for(j=0;j<NVARS;j++){if(rand()%1000/1000.0<PMUTATION){population[i].gene[j]=randval(lowerbound[j],upperbound[j]);}}}voidelitist(void){inti;doublebest,worst;intbest_mem,worst_mem;best=population[0].fitness;worst=population[0].fitness;for(i=0;i<TASK_NUM(pid)-1;++i){if(population[i].fitness>population[i+1].fitness){if(population[i].fitness>=best){best=population[i].fitness;best_mem=i;}if(population[i+1].fitness<=worst){worst=population[i+1].fitness;worst_mem=i+1;}}else{if(population[i].fitness<=worst){worst=population[i].fitness;worst_mem=i;}if(population[i+1].fitness>=best){best=population[i+1].fitness;best_mem=i+1;}}if(best>=population[TASK_NUM(pid)].fitness){for(i=0;i<NVARS;i++){population[TASK_NUM(pid)].gene[i]=population[best_mem].gene[i];local_best_individual[i+1]=population[best_mem].gene[i];}population[TASK_NUM(pid)].fitness=population[best_mem].fitness;local_best_individual[0]=population[best_mem].fitness;}else{for(i=0;i<NVARS;i++)population[worst_mem].gene[i]=population[TASK_NUM(pid)].gene[i];population[worst_mem].fitness=population[TASK_NUM(pid)].fitness;}}voidreport(void){inti,j;fprintf(galog,"\nGenedatain%dforgeneration%dis:\n",pid,generation);for(j=0;j<TASK_NUM(pid);j++){fprintf(galog,"%4d:",j);for(i=0;i<NVARS;i++){fprintf(galog,"\t%10.6lf