遺傳算法基礎及應用實例湖南師范大學數學與計算機科學學院劉剛湖南師范大學計算機專業研究生課程一、遺傳算法的基本知識遺傳算法（GeneticAlgorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。1975年遺傳算法美國J.Holland教授具有內在的隱并行性和更好的全局尋優能力；直接對結構對象進行操作，不存在求導和函數連續性的限定采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳算法的組成遺傳算法可定義為一個8員組：SGA=(C,E,P0,M,Φ,Γ,Ψ,T)

C——

個體的編碼方法；

E

——

個體適應度評價函數；

P0

——

初始群體；

M

——

群體大小；

Φ

——

選擇算子；

Γ——

交叉算子；

Ψ——

變異算子；

T——

遺傳運算終止條件。遺傳算法的優點（1）遺傳對所解的優化問題沒有太多的數學要求，遺傳算法可以處理任意形式的目標函數和約束，無論是線性的還是非線性的，離散的還是連續，甚至混合的搜索空間。（2）進化算子的各態歷經性使得遺傳算法能夠非常有效的進行概率意義下的全局搜索，而傳統的優化方法是通過鄰近點比較而轉移到較好的點，從而達到收斂的局部搜索過程。（3）遺傳算法對于各種特殊問題可以提供極大的靈活性來混合構造領域獨立的啟發式，從而保證算法的有效性。遺傳算法性能分析指標（1）在線性性能評估 在線性能表示為：其中：T是進化代數；是第t代的平均適應度函數；表示到T代為止所有適應度函數值的平均性能。在線指標用于說明算法的在線性能。（2）離線性性能評估 離線性能表示為：其中是第t代最好的個體的適應度函數值；表示至第T代每次最好的適應度函數值的平均。離線指標用于說明算法的收斂性。二、實例講解目標分配問題描述為：m個地空導彈火力單元對n批空襲目標進行目標分配。每批空襲用一個火力單元實施射擊。假設進行目標分配之前，各批目標的威脅程度與各火力單元對各批目標的射擊有利程度已經經過評估和排序。注： 空襲批次可能因機型的不同，襲擊方向的不同，襲擊方式的不同，而不同。 火力單元可能因導彈類型的不同，分布方位的不同，預警時間的不同，而不同。 這些不同，導致了各批目標的威脅程度與各火力單元對各批目標的射擊有利程度的不同。第

j批目標的威脅程度評估值為wj，第

i個火力單元對第

j批目標射擊有利程度估計值為pij，令各火力單元對各批目標進行攔擊的效益值為cij=wj×pij，其中cij表示對某批目標進行攔擊我方獲益大小程度。目標分配的目的是滿足目標分配的基本原則，追求總體效益最佳，即求：

染色體采用十進制編碼，每個基因表示為火力點的編號。染色體的長度由按目標批次編號順序排列的火力單元分配編號組成，表示一種可能的分配方案。射擊有利程度估計值（對每個定點測量后確定的）

p=[.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45; .87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.62.87.70.22.80.42.43.90.13.95.18.19.12.61.35;.48.20.42.16.43.58.69.03.34.72.15.24.29.30.75];威脅程度評估值

w=[.47.97.76.62.48.77.33.74.54.65.43.35.63.66.57];計算過程BaseV=crtbase(15,8); %創建初始矩陣 Chrom=crtbp(NIND,BaseV)+ones(NIND,15);%初始種群 ObjV=targetalloc(Chrom); %計算初始種群函數值 while

FitnV=ranking(-ObjV);

%分配適應度值SelCh=select('sus',Chrom,FitnV,GGAP);

%選擇

SelCh=recombin(‘xovsp’,SelCh,0.7);%重組，交叉

f=rep([1;8],[1,15]); %復制矩陣 SelCh=mutbga(SelCh,f); %變異

SelCh=fix(SelCh);%fix(2.8)=2.0 ObjVSel=targetalloc(SelCh);%計算子代目標函數值

[ChromObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);%重插入 end經過遺傳迭代后，目標分配方案如下：（可能的一種方案） 目標編號123456789101112131415

分配結果177171172713818與此方案對應的總收益為6.4719注： 最大遺傳代數為MAXGEN=400，方能比較穩定地得到總收益值為6.4719。 對于設計者而言，應該有一個估計的總收益值，如＞6.4。當計算結果大于估計值時就基本達到了目的，但并不一定是最優解。三、函數講解crtbase：創建長度為Lind的向量

BaseV=crtbase(Lind,Base) 如果Lind是向量，BaseV的長度為Lind的總長；如果Base也是一個長為Lind的向量，則BaseV是一組由Lind和基本字符Base的元素決定長度的基本字符組組成。當描述染色體結果的基因為基本字符時，最后一選項是有用的。舉例：創建2個基數為6的基本字符{0，1，2，3，4，5}和3個基數為9的基本字符{0，1，2，3，4，5，6，7，8}的基本字符向量。

BaseV=crtbase([23],[69])

BaseV=[66999]crtbp：創建一元素為隨機數的種群矩陣

[Chrom,Lind,BaseV]=crtbp(Nind,Lind)

[Chrom,Lind,BaseV]=crtbp(Nind,BaseV)

[Chrom,Lind,BaseV]=crtbp(Nind,Lind,Base) Chrom：染色體矩陣；Lind：長度；BaseV：基本字符。舉例：創建一個長度為4有3個個體的種群

[Chrom,Lind,BaseV]=crtbp(3,4,BaseV)

得到：

Chrom=[0010;1011;0101]

Lind=4;

BaseV=[2222];crtrp：創建一大小為Nind*Nvar的隨機實值矩陣。Nind指定了種群中個體的數量，Nvar指定每個個體的變量個數。Nvar來自FieldDR，Nvar=size(FieldDR,2)。 FieldDR(FieldDescriptionRealvalue)是一大小為2*Nvar的矩陣，并包含每個個體變量的邊界，第一行包含下界，第二行包含上界。舉例：使用crtrp創建一具有6個個體，每個個體有4個變量的隨機種群 FieldDR=[-100-50-30-20;100503020]; Chrom=crtrp(6,FieldDR) Chrom=[40.23-17.1728.9515.38; 82.0613.2613.35-9.09; 52.4325.6415.20-2.54; -47.5049.109.0910.65; -90.50-13.46-25.63-0.89; 47.21-25.297.80-10.48]targetalloc：計算子代目標函數值并返回。ObjV=targetalloc(Chrom);

首先生成初始種群：

chrom=crtbp(NIND,BaseV)+ones(NIND,15);

然后按火力點編號分配pij值：

fori=1:m forj=1:15 chrom(i,j)=p(chrom(i,j),j);

end end 再計算目標值：

eval=chrom*w';ranking：基于排序的適應度分配。按照個體的目標值ObjV由小到大的順序對它們進行排序，并返回一包含對應個體適應度值FitnV的列向量 FitnV=ranking(ObjV) FitnV=ranking(ObjV,RFun) FitnV=ranking(ObjV,RFun,SUBPOP)舉例：考慮具有10個體的種群，其當前目標值如下： ObjV=[12345109876]‘。使用線性排序和壓差為2，估算適應度值 FitnV=ranking(ObjV)

FitnV=[2.001.77781.55561.33331.111100.22220.44440.66670.8889]’舉例：使用RFun中的值估算適應度值 RFun=[35710141825304050]’ FitnV=ranking(ObjV,RFun)

FitnV=[504030253571014]’FitnV表明了每個個體被選擇的預期概率。

select：（高級函數）從種群Chrom中選擇個體返回到SelCh中。 SelCh=select(SEL_F,Chrom,FitnV) SelCh=select(SEL_F,Chrom,FitnV,GGAP) SelCh=select(SEL_F,Chrom,FitnV,GGAP,SUBPOP)舉例：chrom=[11121;21222;31323;41424] FitnV=[1.2,0.3,0.9,0.7]‘ SelCh=select('sus',chrom,FitnV) SelCh=[11121;31323;31323;41424]概率最小的被淘汰了——[21222]0.3sus：隨機遍歷抽樣。按FitnV的值選擇個體。recombin：完成種群Chrom中個體的重組，在新種群NewChrom中返回重組后的個體。Chrom和NewChrom中的一行對應一個個體。 NewChrom=recombin(REC_F,Chrom) NewChrom=recombin(REC_F,Chrom,RecOpt) NewChrom=recombin(REC_F,Chrom,RecOpt,SUBPOP)低級重組函數：xovsp——單點交叉。Recdis——離散重組。算法說明：recombin檢測輸入參數的一致性并調用低級重組函數。如果recombin調用時具有多個種群，則對每個子種群分別調用低級重組函數。舉例：P81rep：矩陣復制。

Syntax:MatOut=rep(MatIn,REPN);Example:MatIn=[123]REPN=[12]:MatOut=[123123]REPN=[21]:MatOut=[123;123]REPN=[32]:MatOut=[123123;123123;123123]mutbga：對實值種群OldChrom，使用給定的概率，變異每一個變量，返回變異后的種群NewChrom。 NewChrom=mutbga(OldChrom,FieldDR) NewChrom=mutbga(OldChrom,FieldDR,MutOpt) FieldDR是一個矩陣，包含每個變量的邊界。 MutOpt是一個可選向量，具有兩個參數的最大值。舉例：OldChrom=[40.2381-17.176628.953015.3883; 82.064213.263913.3596-9.0916; 52.439625.641015.2014-2.5435] FieldDR=[-100-50-30-20;100503020] mutbag產生一中間任務表MutMx，決定變異的變量，并為加入的delta所標識。如： MutMx=[0001;00-10;00-1-1] delta=[0.25000.25000.25000.2500;0.00010.00010.00010.0001;0.25050.25050.25050.2505]

NewChrom=mutbga(OldChrom,FieldDR,[1/41.0])

NewChrom=[40.2381-17.176628.953015.3849 94.56577.013113.3596-9.0916 52.403025.641015.2014-2.5435]fix：Roundtowardszero.FIX(X)roundstheelementsofXtothenearestintegerstowardszero.Examp：

fix(1.1)=1,fix(3.8)=8

fix([1.32.64.9;24.46.9])

ans=124246reins：完成插入子代到當前種群，用子代代替父代并返回結果種群，子代包含在矩陣SelCh中，父代在矩陣Chrom中，Chrom和SelCh中每一行對應一個個體。 Chrom=reins(Chrom,SelCh) Chrom=reins(Chrom,SelCh,SUBPOP) Chrom=reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh) Chrom=reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh,ObjVSel)舉例： ObjVCh=[21;22;23;24;25;26]; ObjVSel=[31;32];

Chrom=reins(Chrom,SelCh,1,1,ObjVCh);父代種群Chrom的目標值向量為ObjVCh，子代SelCh目標值向量為ObjVSel，基于適應度插入所有子代代替最不適應的父代個體。即：用31和32的個體代替25和26的個體。四、改進的遺傳算法問題：

⑴適應度值標定方式多種多樣，不簡潔、通用；

⑵早熟現象——最難處理的關鍵問題；

⑶收斂較慢。七種改進的遺傳算法

分層遺傳算法；自適應遺傳算法；基于小生境技術的遺傳算法；并行遺傳算法；混合遺傳算法：遺傳算法與最速下降法相結合的混合遺傳算法；

遺傳算法與模擬退火法相結合的混合遺傳算法。改進的遺傳算法一在初始群體中，對所有個體按其適應度大小進行排序，然后計算個體的支持度和置信度；按一定的比例復制（將當前種群中適應度最高的兩個個體結構完整地復制到待配種群中）；按個體所處的位置確定其變異概率并變異：按優良個體復制4份，劣質個體不復制的原則復制個體；從復制組中隨機選擇兩個個體，對這兩個個體進行多次交叉，從所得的結果中選擇一個最優個體存入新群種；若滿足結束條件，則停止；不然，跳轉第1步，直至找到所有符合條件的規則。該算法的優點：進化過程中，子代總是保留了父代中最好的個體，保證了全局最優解。改進的遺傳算法二劃分尋優空間設計空間退化尋優空間的移動改進的遺傳算法三交叉和變異算子的改進和協調采用：

進化過程分為漸進和突變；動態變異；正交設計或均勻設計方法設計新的交叉和變異算子。采用與局部搜索算法相結合的混合遺傳算法，解決局部搜索能力差的問題。采用有條件的替代父代的方法，解決單一的群體更新方式難以兼顧多樣性和收斂性的問題。收斂速度慢的解決方法：

產生好的初始群體；小生境技術；移民技術；自適應算子；與局部搜索結合的混合遺傳算法；參數編碼的動態模糊控制；進行未成熟收斂判斷。改進的遺傳算法四適應度值的標定群體多樣化五、多目標優化中的遺傳算法多目標優化的概念

解決含有多目標和多約束的優化問題稱為多目標優化問題。在實際應用中，工程優化問題大多數是多目標優化問題，有時需要使多個目標在給定區域上都可能地達到最優的問題，目標之間一般都是相互沖突的。

例如投資問題，一般我們都是希望所投入的資金量最少，風險最小，并且所獲得的收益最大。這種多于一個的數值目標的最優問題就是多目標優化問題。最優解和Pareto最優解。多目標優化問題的遺傳算法權重系數變換法并列選擇法排列選擇法共享函數法混合法權重系數變換法對于一個多目標優化問題，若給其每個子目標函數f(xi)(i=1,2,…,n)賦予權重wi，其中wi為相應的f(xi)在多目標優化問題中的重要程度，則各個子目標函數f(xi)的線性加權和表示為

若將u作為多目標優化問題的評價函數，則多目標優化問題就可以轉化為單目標優化問題，即可以利用單目標優化的遺傳函數求解多目標優化問題。并列選擇法并列選擇法的基本思想是，先將群體中的全部個體按子目標函數的數目均等地劃分為一些子群體，對每個子群體分配一個子目標函數，各個子目標函數在相應的子群體中獨立地進行選擇運算，各自選擇出一些適應度高的個體組成一個新的子群體，然后再將所有這些新生成的子群體合并成一個完整的群體，在這個群體中進行交叉和變異運算，從而生成下一代的完整群體，如此不斷地進行“分割-并列選擇-合并”操作，最終可求出多目標優化問題的Pareto最優解。排列選擇法排列選擇法的基本思想是，基于Pareto最優個體，對群體中的各個個體進行排序，依據這個排列次序來進行進化過程中的選擇運算，從而使得排在前面的Pareto最優個體將有更多的機會遺傳到下一代群體中。如此這樣經過一定代數的循環之后，最終就可求出多目標最優化問題的Pareto最優解。共享函數法求解多目標最優化問題時，一般希望所得到的解能夠盡可能地分散在整個Pareto最優解集合內，