遺傳算法實例參考知識課件

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

C——

個體的編碼方法；

E

——

個體適應(yīng)度評價函數(shù)；

P0

——

初始群體；

M

——

群體大??；

Φ

——

選擇算子；

?！?/p>

交叉算子；

Ψ——

變異算子；

T——

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

j批目標(biāo)的威脅程度評估值為wj，第

i個火力單元對第

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

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

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); %創(chuàng)建初始矩陣 Chrom=crtbp(NIND,BaseV)+ones(NIND,15);%初始種群 ObjV=targetalloc(Chrom); %計算初始種群函數(shù)值 while

FitnV=ranking(-ObjV);

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

%選擇

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

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

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

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

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

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

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

BaseV=[66999]crtbp：創(chuàng)建一元素為隨機(jī)數(shù)的種群矩陣

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

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

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

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

得到：

Chrom=[0010;1011;0101]

Lind=4;

BaseV=[2222];crtrp：創(chuàng)建一大小為Nind*Nvar的隨機(jī)實值矩陣。Nind指定了種群中個體的數(shù)量，Nvar指定每個個體的變量個數(shù)。Nvar來自FieldDR，Nvar=size(FieldDR,2)。 FieldDR(FieldDescriptionRealvalue)是一大小為2*Nvar的矩陣，并包含每個個體變量的邊界，第一行包含下界，第二行包含上界。舉例：使用crtrp創(chuàng)建一具有6個個體，每個個體有4個變量的隨機(jī)種群 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：計算子代目標(biāo)函數(shù)值并返回。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 再計算目標(biāo)值：

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

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

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

select：（高級函數(shù)）從種群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：隨機(jī)遍歷抽樣。按FitnV的值選擇個體。recombin：完成種群Chrom中個體的重組，在新種群NewChrom中返回重組后的個體。Chrom和NewChrom中的一行對應(yīng)一個個體。 NewChrom=recombin(REC_F,Chrom) NewChrom=recombin(REC_F,Chrom,RecOpt) NewChrom=recombin(REC_F,Chrom,RecOpt,SUBPOP)低級重組函數(shù)：xovsp——單點交叉。Recdis——離散重組。算法說明：recombin檢測輸入?yún)?shù)的一致性并調(diào)用低級重組函數(shù)。如果recombin調(diào)用時具有多個種群，則對每個子種群分別調(diào)用低級重組函數(shù)。舉例：P81rep：矩陣復(fù)制。

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是一個可選向量，具有兩個參數(shù)的最大值。舉例：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產(chǎn)生一中間任務(wù)表MutMx，決定變異的變量，并為加入的delta所標(biāo)識。如： 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：完成插入子代到當(dāng)前種群，用子代代替父代并返回結(jié)果種群，子代包含在矩陣SelCh中，父代在矩陣Chrom中，Chrom和SelCh中每一行對應(yīng)一個個體。 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的目標(biāo)值向量為ObjVCh，子代SelCh目標(biāo)值向量為ObjVSel，基于適應(yīng)度插入所有子代代替最不適應(yīng)的父代個體。即：用31和32的個體代替25和26的個體。四、改進(jìn)的遺傳算法問題：

⑴適應(yīng)度值標(biāo)定方式多種多樣，不簡潔、通用；

⑵早熟現(xiàn)象——最難處理的關(guān)鍵問題；

⑶收斂較慢。七種改進(jìn)的遺傳算法

分層遺傳算法；自適應(yīng)遺傳算法；基于小生境技術(shù)的遺傳算法；并行遺傳算法；混合遺傳算法：遺傳算法與最速下降法相結(jié)合的混合遺傳算法；

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

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

產(chǎn)生好的初始群體；小生境技術(shù)；移民技術(shù)；自適應(yīng)算子；與局部搜索結(jié)合的混合遺傳算法；參數(shù)編碼的動態(tài)模糊控制；進(jìn)行未成熟收斂判斷。改進(jìn)的遺傳算法四適應(yīng)度值的標(biāo)定群體多樣化五、多目標(biāo)優(yōu)化中的遺傳算法多目標(biāo)優(yōu)化的概念

解決含有多目標(biāo)和多約束的優(yōu)化問題稱為多目標(biāo)優(yōu)化問題。在實際應(yīng)用中，工程優(yōu)化問題大多數(shù)是多目標(biāo)優(yōu)化問題，有時需要使多個目標(biāo)在給定區(qū)域上都可能地達(dá)到最優(yōu)的問題，目標(biāo)之間一般都是相互沖突的。

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

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