遺傳算法(C++)

1、   遺傳算法（Genetic Algorithm，縮寫為GA）是一種有效的解決最優(yōu)化問題的方法。它最先是由John Holland于1975年提出的。從那以后，它逐漸發(fā)展成為一種通過模擬自然進(jìn)化過程解決最優(yōu)化問題的計(jì)算模型。     利用遺傳算法解最優(yōu)化問題，首先應(yīng)對(duì)可行域中的點(diǎn)進(jìn)行編碼（一般采用二進(jìn)制編碼），然后在可行域中隨機(jī)挑選一些編碼組成作為進(jìn)化起點(diǎn)的第一代編碼組，并計(jì)算每個(gè)解的目標(biāo)函數(shù)值，也就是編碼的適應(yīng)度。接著就像自然界中一樣，利用選擇機(jī)制從編碼組中隨機(jī)挑選編碼作為繁殖過程前的編碼樣本。選擇機(jī)制應(yīng)保證適應(yīng)度較高的

2、解能夠保留較多的樣本；而適應(yīng)度較低的解則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算子對(duì)挑選后的樣本進(jìn)行交換。交叉算子交換隨機(jī)挑選的兩個(gè)編碼的某些位，變異算子則直接對(duì)一個(gè)編碼中的隨機(jī)挑選的某一位進(jìn)行反轉(zhuǎn)。這樣通過選擇和繁殖就產(chǎn)生了下一代編碼組。重復(fù)上述選擇和繁殖過程，直到結(jié)束條件得到滿足為止。進(jìn)化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結(jié)果。從以上介紹可以看出，GA算法具有下述特點(diǎn)： 1)GA是對(duì)問題參數(shù)的編碼組進(jìn)行進(jìn)貨，而不是直接對(duì)參數(shù)本身。 21)GA的搜索是從問題解的編碼組開始搜索，而不是從單個(gè)解開始。 31)GA使用目標(biāo)函數(shù)值（適

3、應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息。 4)GA算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定規(guī)則。 實(shí)踐表明，遺傳算法解最優(yōu)化問題的計(jì)算效率比較高、適用范圍相當(dāng)廣。為了解釋這一現(xiàn)象，Holland給出了圖式定理。所謂圖式，就是某些碼位取相同值的編碼的集合。圖式定理說明在進(jìn)化過程的各代中，屬于適應(yīng)度高、階數(shù)低且長(zhǎng)度短的圖式的編碼數(shù)量將隨代數(shù)以指數(shù)形式增長(zhǎng)。另外，Holland還發(fā)現(xiàn)遺傳算法具有隱含的并行計(jì)算特性。最近的研究則表明，上述遺傳算法經(jīng)適當(dāng)改進(jìn)后對(duì)任意優(yōu)化問題以概率1收斂于全局最優(yōu)解。 將遺傳算法用于解決各種實(shí)際問題后，人們發(fā)現(xiàn)遣傳算法也會(huì)由于各種原因過早向目標(biāo)函

4、數(shù)的局部最優(yōu)解收斂，從而很難找到全局最優(yōu)解。其中有些是由于目標(biāo)函數(shù)的特性造成的，例如函數(shù)具有欺騙性，不滿足構(gòu)造模塊假說等等；另外一些則是由于算法設(shè)計(jì)不當(dāng)。為此，不斷有人對(duì)遺傳算法提出各種各樣的改進(jìn)方案。例如：針對(duì)原先的定長(zhǎng)二進(jìn)制編碼方案；提出了動(dòng)態(tài)編碼、實(shí)數(shù)編碼等改進(jìn)方案；針對(duì)按比例的選擇機(jī)制，提出了競(jìng)爭(zhēng)選擇、按續(xù)挑選等改進(jìn)方案；針對(duì)原先的一點(diǎn)交叉算子，提出了兩點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等算子；針對(duì)原先遺傳算法各控制參數(shù)在進(jìn)化過程中不變的情況，提出了退化遺傳算法、自適應(yīng)遺傳算法等。另外，針對(duì)不同問題還出現(xiàn)了分布式遺傳算法、并行遺傳算法等等。 近年來，隨著對(duì)于遺傳算法研究的不斷深入完善，有越來越

5、多的人認(rèn)識(shí)了解了遺傳算法，并把它應(yīng)用到越來越廣泛的領(lǐng)域，例如機(jī)器學(xué)習(xí)、模式識(shí)別、圖像處理、神經(jīng)網(wǎng)絡(luò)、工業(yè)優(yōu)化控制和社會(huì)科學(xué)等方面。特別是在解決旅行商問題、煤氣管道的最優(yōu)控制、通信網(wǎng)絡(luò)鏈接長(zhǎng)度的優(yōu)化問題、鐵路運(yùn)輸計(jì)劃優(yōu)化、噴氣式收音機(jī)渦輪機(jī)的設(shè)計(jì)、VLSI版面設(shè)計(jì)、鍵盤排列優(yōu)化等問題上遺傳算法都取得了很大的成功。 目前國(guó)際國(guó)內(nèi)有關(guān)GA的研究熱潮方興未艾。除從1985年起每?jī)赡昱e辦一屆GA國(guó)際會(huì)議外，還有MIT從1993年開始出版的Evolutionary Computatio和Adaptive Behavior兩種雜志、IEEE從今年起出版的專門關(guān)于進(jìn)化計(jì)算的匯刊。另外，各種AI類的雜志不斷出版

6、有關(guān)進(jìn)化計(jì)算的專輯。其它有關(guān)GA理論和工程應(yīng)用的文章也在各種不同類型雜志上不斷涌現(xiàn)。國(guó)內(nèi)有關(guān)GA的研究也正在不斷深入地展開。· 遺傳算法(Genetic Algorithm, GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。這一點(diǎn)體現(xiàn)了自然界中"物競(jìng)天擇、適者生存"進(jìn)化過程。1962年Holland教授首次提出了GA算法的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機(jī)器學(xué)習(xí)等方面，并奠定了堅(jiān)實(shí)的理論基礎(chǔ)。用遺傳算法解決問題時(shí)，首先要對(duì)待解決問題的模型結(jié)構(gòu)和參數(shù)進(jìn)行編碼

7、，一般用字符串表示，這個(gè)過程就將問題符號(hào)化、離散化了。也有在連續(xù)空間定義的GA(Genetic Algorithm in Continuous Space, GACS)，暫不討論。一個(gè)串行運(yùn)算的遺傳算法(Seguential Genetic Algoritm, SGA)按如下過程進(jìn)行：(1) 對(duì)待解決問題進(jìn)行編碼；(2) 隨機(jī)初始化群體X(0):=(x1, x2, xn)；(3) 對(duì)當(dāng)前群體X(t)中每個(gè)個(gè)體xi計(jì)算其適應(yīng)度F(xi)，適應(yīng)度表示了該個(gè)體的性能好壞；(4) 應(yīng)用選擇算子產(chǎn)生中間代Xr(t)；(5) 對(duì)Xr(t)應(yīng)用其它的算子，產(chǎn)生新一代群體X(t+1)，這些算子的目的在于擴(kuò)展有

8、限個(gè)體的覆蓋面，體現(xiàn)全局搜索的思想；(6) t:=t+1；如果不滿足終止條件繼續(xù)(3)。GA中最常用的算子有如下幾種：(1) 選擇算子(selection/reproduction): 選擇算子從群體中按某一概率成對(duì)選擇個(gè)體，某個(gè)體xi被選擇的概率Pi與其適應(yīng)度值成正比。最通常的實(shí)現(xiàn)方法是輪盤賭(roulette wheel)模型。(2) 交叉算子(Crossover): 交叉算子將被選中的兩個(gè)個(gè)體的基因鏈按概率pc進(jìn)行交叉，生成兩個(gè)新的個(gè)體，交叉位置是隨機(jī)的。其中Pc是一個(gè)系統(tǒng)參數(shù)。(3) 變異算子(Mutation): 變異算子將新個(gè)體的基因鏈的各位按概率pm進(jìn)行變異，對(duì)二值基因鏈(0,1

9、編碼)來說即是取反。上述各種算子的實(shí)現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進(jìn)GA的某些性能。系統(tǒng)參數(shù)(個(gè)體數(shù)n,基因鏈長(zhǎng)度l,交叉概率Pc,變異概率Pm等)對(duì)算法的收斂速度及結(jié)果有很大的影響，應(yīng)視具體問題選取不同的值。GA的程序設(shè)計(jì)應(yīng)考慮到通用性，而且要有較強(qiáng)的適應(yīng)新的算子的能力。OOP中的類的繼承為我們提供了這一可能。定義兩個(gè)基本結(jié)構(gòu)：基因(ALLELE)和個(gè)體(INDIVIDUAL)，以個(gè)體的集合作為群體類TPopulation的數(shù)據(jù)成員，而TSGA類則由群體派生出來，定義GA的基本操作。對(duì)任一個(gè)應(yīng)用實(shí)例，可以在TSGA類上派生，并定義新的操作。TPopulation類包含兩

10、個(gè)重要過程：FillFitness: 評(píng)價(jià)函數(shù)，對(duì)每個(gè)個(gè)體進(jìn)行解碼(decode)并計(jì)算出其適應(yīng)度值，具體操作在用戶類中實(shí)現(xiàn)。Statistic: 對(duì)當(dāng)前群體進(jìn)行統(tǒng)計(jì)，如求總適應(yīng)度sumfitness、平均適應(yīng)度average、最好個(gè)體fmax、最壞個(gè)體fmin等。TSGA類在TPopulation類的基礎(chǔ)上派生，以GA的系統(tǒng)參數(shù)為構(gòu)造函數(shù)的參數(shù)，它有4個(gè)重要的成員函數(shù)：Select: 選擇算子，基本的選擇策略采用輪盤賭模型（如圖2）。輪盤經(jīng)任意旋轉(zhuǎn)停止后指針?biāo)赶騾^(qū)域被選中，所以fi值大的被選中的概率就大。Crossover: 交叉算子，以概率Pc在兩基因鏈上的隨機(jī)位置交換子串。Mutati

11、on: 變異算子，以概率Pm對(duì)基因鏈上每一個(gè)基因進(jìn)行隨機(jī)干擾(取反)。Generate: 產(chǎn)生下代，包括了評(píng)價(jià)、統(tǒng)計(jì)、選擇、交叉、變異等全部過程，每運(yùn)行一次，產(chǎn)生新的一代。SGA的結(jié)構(gòu)及類定義如下(用C+編寫)：code typedef char ALLELE; / 基因類型typedef structALLELE *chrom;float fitness; / fitness of ChromosomeINDIVIDUAL; / 個(gè)體定義class TPopulation / 群體類定義public:int size; / Size of population: nint lchrom; /

12、 Length of chromosome: lfloat sumfitness, average;INDIVIDUAL *fmin, *fmax;INDIVIDUAL *pop;TPopulation(int popsize, int strlength);TPopulation();inline INDIVIDUAL &Individual(int i) return popi;void FillFitness(); / 評(píng)價(jià)函數(shù)virtual void Statistics(); / 統(tǒng)計(jì)函數(shù);class TSGA : public TPopulation / TSGA類派生于群

13、體類public:float pcross; / Probability of Crossoverfloat pmutation; / Probability of Mutationint gen; / Counter of generationTSGA(int size, int strlength, float pm=0.03, float pc=0.6):TPopulation(size, strlength)gen=0; pcross=pc; pmutation=pm; ;virtual INDIVIDUAL& Select();virtual void Crossover(I

14、NDIVIDUAL &parent1, INDIVIDUAL &parent2,INDIVIDUAL &child1, INDIVIDUAL &child2);&child1, INDIVIDUAL &child2);virtual ALLELE Mutation(ALLELE alleleval);virtual void Generate(); / 產(chǎn)生新的一代;用戶GA類定義如下：class TSGAfit : public TSGApublic:TSGAfit(int size,float pm=0.0333,float pc=0.6):

15、TSGA(size,24,pm,pc);void print(); /code由于GA是一個(gè)概率過程，所以每次迭代的情況是不一樣的；系統(tǒng)參數(shù)不同，迭代情況也不同。在實(shí)驗(yàn)中參數(shù)一般選取如下：個(gè)體數(shù)n=50-200，變異概率Pm=0.03, 交叉概率Pc=0.6。變異概率太大，會(huì)導(dǎo)致不穩(wěn)定。核心函數(shù)： (1)function pop=initializega(num,bounds,eevalFN,eevalOps,options)-初始種群的生成函數(shù) 【輸出參數(shù)】  pop-生成的初始種群 【輸入?yún)?shù)】  num-種群中的個(gè)體數(shù)目  bounds-代表變量的上下界的矩

16、陣  eevalFN-適應(yīng)度函數(shù)  eevalOps-傳遞給適應(yīng)度函數(shù)的參數(shù)  options-選擇編碼形式(浮點(diǎn)編碼或是二進(jìn)制編碼)precision F_or_B,如     precision-變量進(jìn)行二進(jìn)制編碼時(shí)指定的精度     F_or_B-為1時(shí)選擇浮點(diǎn)編碼，否則為二進(jìn)制編碼,由precision指定精度) (2)function x,endPop,bPop,traceInfo = ga(bounds,evalFN,evalOps,startPop,opts,.      

17、60;  termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)-遺傳算法函數(shù) 【輸出參數(shù)】     x-求得的最優(yōu)解     endPop-最終得到的種群     bPop-最優(yōu)種群的一個(gè)搜索軌跡 【輸入?yún)?shù)】     bounds-代表變量上下界的矩陣     evalFN-適應(yīng)度函數(shù)     evalOps-傳遞給適應(yīng)度函數(shù)的參數(shù)     startPop-初始種

18、群     optsepsilon prob_ops display-opts(1:2)等同于initializega的options參數(shù)，第三個(gè)參數(shù)控制是否輸出，一般為0。如1e-6 1 0     termFN-終止函數(shù)的名稱,如'maxGenTerm'     termOps-傳遞個(gè)終止函數(shù)的參數(shù),如100     selectFN-選擇函數(shù)的名稱,如'normGeomSelect'     selectOps-傳遞個(gè)選擇函數(shù)的參數(shù),如0.08  

19、   xOverFNs-交叉函數(shù)名稱表，以空格分開，如'arithXover heuristicXover simpleXover'     xOverOps-傳遞給交叉函數(shù)的參數(shù)表，如2 0;2 3;2 0     mutFNs-變異函數(shù)表，如'boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'     mutOps-傳遞給交叉函數(shù)的參數(shù)表,如4 0 0;6 100 3;4 100 3;4 0 0 注意】ma

20、tlab工具箱函數(shù)必須放在工作目錄下 【問題】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0<=x<=9 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為10，二進(jìn)制編碼長(zhǎng)度為20，交叉概率為0.95,變異概率為0.08 【程序清單】    %編寫目標(biāo)函數(shù)      functionsol,eval=fitness(sol,options)        x=sol(1);        eval=x+10*sin(5*x)+7*co

21、s(4*x);    %把上述函數(shù)存儲(chǔ)為fitness.m文件并放在工作目錄下        initPop=initializega(10,0 9,'fitness');%生成初始種群，大小為10    x endPop,bPop,trace=ga(0 9,'fitness',initPop,1e-6 1 1,'maxGenTerm',25,'normGeomSelect',.      0.08,'arithX

22、over',2,'nonUnifMutation',2 25 3) %25次遺傳迭代 運(yùn)算借過為：x =    7.8562 24.8553(當(dāng)x為7.8562時(shí)，f（x）取最大值24.8553) 注：遺傳算法一般用來取得近似最優(yōu)解，而不是最優(yōu)解。 遺傳算法實(shí)例2 【問題】在5<=Xi<=5,i=1,2區(qū)間內(nèi)，求解        f(x1,x2)=-20*exp(-0.2*sqrt(0.5*(x1.2+x2.2)-exp(0.5*(cos(2*pi*x1)+cos(2*pi*x2)+22.71282

23、的最小值。 【分析】種群大小10，最大代數(shù)1000，變異率0.1,交叉率0.3 【程序清單】    源函數(shù)的matlab代碼       function eval=f(sol)         numv=size(sol,2);         x=sol(1:numv);         eval=-20*exp(-0.2*sqrt(sum(x.2)/numv)-exp(sum(cos(2*pi*x)/numv)+22.7

24、1282;   %適應(yīng)度函數(shù)的matlab代碼       function sol,eval=fitness(sol,options)         numv=size(sol,2)-1;         x=sol(1:numv);         eval=f(x);         eval=-eval;   %遺傳算法的matlab代碼      

25、; bounds=ones(2,1)*-5 5;       p,endPop,bestSols,trace=ga(bounds,'fitness') 注：前兩個(gè)文件存儲(chǔ)為m文件并放在工作目錄下，運(yùn)行結(jié)果為    p =    0.0000 -0.0000 0.0055 大家可以直接繪出f(x)的圖形來大概看看f（x）的最值是多少，也可是使用優(yōu)化函數(shù)來驗(yàn)證。matlab命令行執(zhí)行命令：  fplot('x+10*sin(5*x)+7*cos(4*x)',0,9) evalops是傳遞

26、給適應(yīng)度函數(shù)的參數(shù)，opts是二進(jìn)制編碼的精度，termops是選擇maxGenTerm結(jié)束函數(shù)時(shí)傳遞個(gè)maxGenTerm的參數(shù)，即遺傳代數(shù)。xoverops是傳遞給交叉函數(shù)的參數(shù)。mutops是傳遞給變異函數(shù)的參數(shù)。 遺傳算法(Genetic Algorithm, GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。這一點(diǎn)體現(xiàn)了自然界中"物競(jìng)天擇、適者生存"進(jìn)化過程。1962年Holland教授首次提出了GA算法的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機(jī)器學(xué)習(xí)等方面，并奠

27、定了堅(jiān)實(shí)的理論基礎(chǔ)。 用遺傳算法解決問題時(shí)，首先要對(duì)待解決問題的模型結(jié)構(gòu)和參數(shù)進(jìn)行編碼，一般用字符串表示，這個(gè)過程就將問題符號(hào)化、離散化了。也有在連續(xù)空間定義的GA(Genetic Algorithm in Continuous Space, GACS)，暫不討論。 一個(gè)串行運(yùn)算的遺傳算法(Seguential Genetic Algoritm, SGA)按如下過程進(jìn)行： (1) 對(duì)待解決問題進(jìn)行編碼； (2) 隨機(jī)初始化群體X(0):=(x1, x2, xn)； (3) 對(duì)當(dāng)前群體X(t)中每個(gè)個(gè)體xi計(jì)算其適應(yīng)度F(xi)，適應(yīng)度表示了該個(gè)體的性能好壞； (4) 應(yīng)用選擇算子產(chǎn)生中間代Xr

28、(t)； (5) 對(duì)Xr(t)應(yīng)用其它的算子，產(chǎn)生新一代群體X(t+1)，這些算子的目的在于擴(kuò)展有限個(gè)體的覆蓋面，體現(xiàn)全局搜索的思想； (6) t:=t+1；如果不滿足終止條件繼續(xù)(3)。GA中最常用的算子有如下幾種： (1) 選擇算子(selection/reproduction): 選擇算子從群體中按某一概率成對(duì)選擇個(gè)體，某個(gè)體xi被選擇的概率Pi與其適應(yīng)度值成正比。最通常的實(shí)現(xiàn)方法是輪盤賭(roulette wheel)模型。 (2) 交叉算子(Crossover): 交叉算子將被選中的兩個(gè)個(gè)體的基因鏈按概率pc進(jìn)行交叉，生成兩個(gè)新的個(gè)體，交叉位置是隨機(jī)的。其中Pc是一個(gè)系統(tǒng)參數(shù)。 (3

29、) 變異算子(Mutation): 變異算子將新個(gè)體的基因鏈的各位按概率pm進(jìn)行變異，對(duì)二值基因鏈(0,1編碼)來說即是取反。 上述各種算子的實(shí)現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進(jìn)GA的某些性能。系統(tǒng)參數(shù)(個(gè)體數(shù)n,基因鏈長(zhǎng)度l,交叉概率Pc,變異概率Pm等)對(duì)算法的收斂速度及結(jié)果有很大的影響，應(yīng)視具體問題選取不同的值。GA的程序設(shè)計(jì)應(yīng)考慮到通用性，而且要有較強(qiáng)的適應(yīng)新的算子的能力。OOP中的類的繼承為我們提供了這一可能。 定義兩個(gè)基本結(jié)構(gòu)：基因(ALLELE)和個(gè)體(INDIVIDUAL)，以個(gè)體的集合作為群體類TPopulation的數(shù)據(jù)成員，而TSGA類則由群體派生出來

30、，定義GA的基本操作。對(duì)任一個(gè)應(yīng)用實(shí)例，可以在TSGA類上派生，并定義新的操作。 TPopulation類包含兩個(gè)重要過程： FillFitness: 評(píng)價(jià)函數(shù)，對(duì)每個(gè)個(gè)體進(jìn)行解碼(decode)并計(jì)算出其適應(yīng)度值，具體操作在用戶類中實(shí)現(xiàn)。 Statistic: 對(duì)當(dāng)前群體進(jìn)行統(tǒng)計(jì)，如求總適應(yīng)度sumfitness、平均適應(yīng)度average、最好個(gè)體fmax、最壞個(gè)體fmin等。 TSGA類在TPopulation類的基礎(chǔ)上派生，以GA的系統(tǒng)參數(shù)為構(gòu)造函數(shù)的參數(shù)，它有4個(gè)重要的成員函數(shù)： Select: 選擇算子，基本的選擇策略采用輪盤賭模型（如圖2）。輪盤經(jīng)任意旋轉(zhuǎn)停止后指針?biāo)赶騾^(qū)域被選中

31、，所以fi值大的被選中的概率就大。 Crossover: 交叉算子，以概率Pc在兩基因鏈上的隨機(jī)位置交換子串。 Mutation: 變異算子，以概率Pm對(duì)基因鏈上每一個(gè)基因進(jìn)行隨機(jī)干擾(取反)。 Generate: 產(chǎn)生下代，包括了評(píng)價(jià)、統(tǒng)計(jì)、選擇、交叉、變異等全部過程，每運(yùn)行一次，產(chǎn)生新的一代。 SGA的結(jié)構(gòu)及類定義如下(用C+編寫)： codetypedef char ALLELE; / 基因類型 typedef struct ALLELE *chrom; float fitness; / fitness of Chromosome INDIVIDUAL; / 個(gè)體定義 class TPopulation / 群體類定義 public: int size; / Size of population: n int lchrom; / Length of chromosome: l float s