進(jìn)化算法復(fù)習(xí)11版

1、14題中p（x）進(jìn)行了修改，于妍版本為參考書版本，新版本為老師筆記版本12題就行了優(yōu)化1) 和傳統(tǒng)優(yōu)化算法相比，進(jìn)化算法有什么優(yōu)勢？A. 不直接作用在問題空間，而是作用在編碼后的空間(解空間)B. 不是單點(diǎn)出發(fā)，而是群體搜索，是一種全局隨機(jī)搜索算法C. 除需知適應(yīng)度函數(shù)外，無需導(dǎo)數(shù)或者其他輔助信息D. 利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則（具有全局搜索性，并行性，簡單，應(yīng)用廣泛，隨機(jī)迭代）2) 編碼應(yīng)該遵循的規(guī)則是什么？A. 完備性（completeness）：原問題空間所有點(diǎn)都能成為編碼后空間的點(diǎn)，亦任意的解都對應(yīng)一個編碼B. 健全性（soundness）：編碼后的空間的點(diǎn)都對應(yīng)原問題空間的點(diǎn)C

2、. 非冗余性（non-redundancy）：問題空間-（一一對應(yīng)）-編碼后空間點(diǎn)注意：這三條只是要求編碼時不要漏解，也不要多表示解。以上三點(diǎn)是獨(dú)立于問題，對提高遺傳算法效率無關(guān)。相比之下，DeJong提出的如下編碼規(guī)則可操作性強(qiáng)，對遺傳算法效率具有一定的指導(dǎo)意義：1. 有意義積木塊編碼規(guī)則：所有編碼規(guī)則應(yīng)在遺傳算子作用下易于生成與所求問題相關(guān)的積木塊。（把握起來十分困難）2. 最小字符集編碼規(guī)則：所用編碼應(yīng)使問題能得到自然描述，而用最小的字符集。（實(shí)用）3) 對最大化問題，設(shè)計一種適合輪盤賭選擇的適應(yīng)度函數(shù)，并寫出輪盤賭選擇方法的步驟Ø 適應(yīng)度函數(shù)：直接選取目標(biāo)函數(shù)作為適應(yīng)度函數(shù)值

3、（當(dāng)目標(biāo)函數(shù)恒為正），或者選擇Ø 輪盤賭選擇步驟：1. 計算群體中每個個體被選擇的概率值，即注意到，0，且所有的和為12. 計算累加概率，即3. 在0,1中產(chǎn)生隨機(jī)數(shù)，若，則選擇；否則，若，選擇4. 重復(fù)N次，產(chǎn)生N個個體輪盤賭選擇的特點(diǎn)是：適應(yīng)度越大（即所占適應(yīng)度概率越大）被選擇的概率就越大4) 適應(yīng)度函數(shù)尺度化的作用是什么？試給出在進(jìn)化初期和末期尺度化函數(shù)的例子Ø 適應(yīng)度函數(shù)為正值，適應(yīng)度越大，個體越好Ø 最小化問題：Ø 最大化問題：適應(yīng)度的尺度變化：在不同階段，對個體適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大與縮小，來重新定義適應(yīng)度函數(shù)以便避免未成熟收斂或者加快收斂。令

4、U：正實(shí)數(shù)到正實(shí)數(shù)上的映射，U為嚴(yán)格單調(diào)增加的非負(fù)函數(shù).F=U(F)F:尺度變換后新的適應(yīng)度函數(shù) F:原適應(yīng)度函數(shù)² 進(jìn)化初期：種群中可能有超級個體，通過選擇，它的占有比例很大，導(dǎo)致算法早熟收斂。 對策：縮小個體間差距。例子：由于個體間差異很大，出現(xiàn)了超級個體X1，則采用指數(shù)尺度變化將系數(shù)取小，取為0.005，得到尺度變化后的結(jié)果為：，縮小了個體間差異² 進(jìn)化后期：個體之間適應(yīng)度差異不大，最佳個體和其他個體選擇機(jī)會均等（使得算法無目的的隨即選擇） ,應(yīng)當(dāng)加快收斂，增大個體間差異。 對策：放大個體間差異，區(qū)分個體優(yōu)劣例子：由于差異不大，應(yīng)當(dāng)放大個體間差異，采用指數(shù)尺度變換，變

5、化系數(shù)取值大一點(diǎn)，取為0.5，最后得到結(jié)果為：， 可見個體間差異得到擴(kuò)大。常用的三種尺度變化：1. 線性尺度變化 其中，a,b為常數(shù)（或系數(shù)）2. 乘冪尺度變化 3. 指數(shù)尺度變化 5) 對TSP問題，試給出一種編碼方法，并給出一種與之相適應(yīng)的一種雜交算子和變異算子Ø 編碼方法1：路徑表示法路徑由1n的一個排列表示，例如：1,3,2,4,6,5,7,8，表示的路徑為1->3->2->4->6->5->7->8大多數(shù)算法采用所遍歷城市的順序排列來表示個體.交叉方法：順序交叉順序交叉的步驟：1. 設(shè)p1和p2為參加交叉的兩個個體，隨即選擇匹配區(qū)2

6、. 將p1在匹配區(qū)外與p2匹配區(qū)內(nèi)相同的數(shù)字去掉，再將p1匹配區(qū)內(nèi)的數(shù)移動到最左端得到O1，同理得到O2.3. 將O2的匹配區(qū)添加到O1匹配區(qū)的后面，將O1匹配區(qū)的數(shù)字添加到O2匹配區(qū)后面，最終得到O1和O2例子：匹配區(qū)：隨機(jī)選擇匹配區(qū)，此例子為576和239P1=（9,8,4 |5,7,6| 1,3,2）-> O1=(5,7,6, 8,4,1)->O1=(5,7,6, 2,3,9,8,4,1)P2=（8,7,1 |2,3,9| 5,4,6）-> O2=(2,3,9, 8,1,4)-> O2=(2,3,9, 5,7,68,1,4)Ø 變異算子：倒位變異

7、0;  對個體編碼串中隨機(jī)選取的子串以逆轉(zhuǎn)概率Pm逆向排序如下：A(1)，A(8)，A(5)，A(7)，A(6)，A(4)，A(2)，A(3)對46位進(jìn)行倒位變異：A(1)，A(8)，A(5)，A(4)，A(6)，A(7)，A(2)，A(3)變異結(jié)束。Ø 編碼方法2：順序表示法假設(shè)所有城市所組成一個列表(集合)，記為w，給每個城市分配一個1n之間的序號，將序號排列亦記為w. w=(1,2,3，,n) 或者w=（A,B,N）對于城市列表w，取w作為參考路徑，假定有一個一個訪問路徑為，規(guī)定每訪問完一個城市，即從城市列表W中刪除該城市，則用第i個所訪問的城市在所未訪問城

8、市列表中，對應(yīng)的位置序號,就可以表示具體訪問哪個城市，如此這樣，直到處理完w為止，將全部順序排列，得到個體基因型表示一個循環(huán)路線。例如：10-TSP編碼：城市列表w=（A,B,C,D,E,F,G,H,I,J） 現(xiàn)有一個訪問序列t=(ADBHFIJGEC) , 按照t的順序依次劃去w中的相應(yīng)字母，即將劃去的字母在w中所排列的序號即為其編碼數(shù)字。 最終對應(yīng)于訪問序列t編碼為G1=（1315344321）解碼：仍舊依次劃去列表w中的字母，并寫出G1中序號所對應(yīng)位置的字母序列。交叉方法：使用傳統(tǒng)的單點(diǎn)不會破壞路徑的可行性 6) 寫出多維背包問題的數(shù)學(xué)形式，并給出一種求解算法（組合優(yōu)化的NP完全問題）問

9、題描述：有一個背包，能提供m種資源（空間、容積、載重），各種資源的容量是，現(xiàn)在要把n種物資放入背包中，第i種物資占用第j項(xiàng)資源的數(shù)量是，而裝入第i中物資的收益是，問背包中應(yīng)放入哪些物資，在沒有超出資源容量的情況下，獲益最大？ M=1： 單背包問題 M2：多維背包問題數(shù)學(xué)形式： 求解辦法：Ø 編碼采用二進(jìn)制編碼，染色體編碼為向量，物資i放入背包，表示物資i不放入背包。Ø 適應(yīng)度函數(shù)選取目標(biāo)函數(shù)，采用修補(bǔ)算子產(chǎn)生可行解由于存在約束條件，則雜交、變異產(chǎn)生的解有的可能不可行，對不可行的染色體，采用貪心算法的修補(bǔ)算子，將其修正為可行解步驟如下：1. 計算背包中的每一個物資（）的利潤密

10、度，2. 計算背包中每一物資（）的最小利潤密度，3. 對背包中的各個物資（）按的值的升序排列4. 從背包中移出值最小的物資（將對應(yīng)位基因由1變0）5. 重復(fù)4，直到背包中剩下的物資滿足約束條件為止（得到可行染色體）7) 給出Pareto最優(yōu)解的定義，多目標(biāo)優(yōu)化算法的評價原則是什么（pareto最優(yōu)解是多目標(biāo)優(yōu)化問題通常采用的最優(yōu)解的定義，是平衡多個相互沖突目標(biāo)的主要方法）Pareto最優(yōu)解定義：一個自變量向量X D, 若不存在a D，使得a優(yōu)于X（），則稱X為pareto最優(yōu)解通常多目標(biāo)優(yōu)化問題(MOP)有多個Pareto最優(yōu)解，這些解的集合成為Pareto最優(yōu)解集，對應(yīng)的，目標(biāo)向量構(gòu)成了pa

11、reto front（pareto前沿）多目標(biāo)優(yōu)化算法的評價原則通常有以下幾項(xiàng)：1. 逼近性：所求出的Pareto最優(yōu)解集在目標(biāo)函數(shù)空間接近Pareto前沿的程度，越接近說明這個算法求出的最優(yōu)解集質(zhì)量越高。2. 均勻性：所求出的Pareto最優(yōu)解集在目標(biāo)函數(shù)空間分布的均勻程度，越均勻說明這個算法求出的最優(yōu)解集分布性好3. 寬廣性：所求出的Pareto最優(yōu)解集在目標(biāo)函數(shù)空間分布的寬廣程度，越寬廣說明這個算法算出的最優(yōu)解集占據(jù)的范圍越廣，搜索區(qū)域越大。4. 最優(yōu)解數(shù)目：用來描述在Pareto最優(yōu)解集中不屬于Pareto前端的解所占的比例5. 收斂性度量值：衡量一組已知的Pareto最優(yōu)解集的收斂范

12、圍。收斂性度量的評價方法為在多目標(biāo)優(yōu)化問題的pareto前沿均勻地取若干個點(diǎn)構(gòu)成pareto前端基點(diǎn)系，計算由算法獲得的Pareto最優(yōu)解與基點(diǎn)系之間的距離的最小值，所有這些最小值的平均值就是收斂性度量值8) 敘述NSGA-II的非劣分類方法（多目標(biāo)優(yōu)化進(jìn)化算法）基于精英策略的非劣分類遺傳算法首先，用種群規(guī)模為N的父代種群記為產(chǎn)生子代種群（種群規(guī)模N），將兩個種群合在一起形成種群規(guī)模為2N的種群,然后使用非劣分類排序?qū)⒎值燃?。新種群由N個不同非劣分類等級的個體填充，填充過程從最低的非劣等級開始，接著是第二非劣等級，以此類推。隨機(jī)產(chǎn)生種群規(guī)模為N的初始種群，進(jìn)化代數(shù)t為0對進(jìn)行選擇、交叉、變異操

13、作，產(chǎn)生 對進(jìn)行非劣分類按非劣等級從低到高對的N個個體進(jìn)行填充t=t+1 結(jié)束 Y t>MaxGen N 種群規(guī)模 ：2N， 種群規(guī)模：N9) 寫出經(jīng)典遺傳算法（CGA）的算法步驟方法一A. 初始化：設(shè)置進(jìn)化代數(shù)計數(shù)器t=0，設(shè)置參數(shù)：（種群規(guī)模N，最大進(jìn)化代數(shù)M，交叉概率，變異概率，計算串長，）隨機(jī)生成N個染色體作為初始種群P(0)B. 計算各個染色體的適應(yīng)度值，對染色體進(jìn)行評價C. 終止條件判斷，若，算法停止，輸出結(jié)果；D. 選擇，輪盤賭選擇E. 雜交：單點(diǎn)交叉 F. 變異：基本位變異 G. 下一代種群 令， 轉(zhuǎn)B方法二：A. 初始化：設(shè)置進(jìn)化代數(shù)計數(shù)器t=0，設(shè)置參數(shù)：（種群規(guī)模N

14、，最大進(jìn)化代數(shù)M，交叉概率，變異概率，計算串長，）隨機(jī)生成N個染色體作為初始種群P(0)B. 計算各個染色體的適應(yīng)度值，對染色體進(jìn)行評價C. 選擇，輪盤賭選擇D. 重復(fù)一下過程，知道終止條件成立，算法結(jié)束1. 雜交，單點(diǎn)交叉2. 變異，基本位變異3. 計算各個染色體的適應(yīng)度值4. 選擇10) 敘述并證明經(jīng)典遺傳算法的模式定理 模式定理：遺傳算法中，在選擇、交叉、變異算子的作用下具有低階、短定義長度，并且平均適應(yīng)度高于群體適應(yīng)度的模式將按指數(shù)級增大。階：在模式中具有確定基因值的位值數(shù)目。定義長度：模式中第一個確定基因的位置與最后一個確定基因值的位置之間的距離.模式定理證明過程詳見筆記！11) 對

15、于二進(jìn)制編碼，試設(shè)計一種變異算子，使對任意兩個染色體a和b，將a變異為b的概率大于零，并估計出概率值解：海明距離：兩個個體基因b與b的差異數(shù)，記為H(b,b). 經(jīng)過變異操作后，由個體b變?yōu)閭€體b的概率為： （其中表示染色體串長）12) 對經(jīng)典遺傳算法（CGA）若變異概率為,則由變異引起的狀態(tài)轉(zhuǎn)移矩陣是什么？13) ，給定精度要求=0.00001,采用二進(jìn)制編碼解該問題時，至少要用多少位二進(jìn)制表示x，才能使求出的解的誤差不超過？假設(shè)串長為的二進(jìn)制數(shù)表示為，寫出對應(yīng)的解碼公式.解： 即為所求串長解碼公式：14) 試給出一種約束處理方法、雜交算子和變異算子解：目前處理約束優(yōu)化問題的方法主要有基于罰

16、函數(shù)的約束處理技術(shù)。罰函數(shù)法是處理約束條件最常見、最基本的方法，它將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，再將無約束優(yōu)化問題的方法進(jìn)行求解，具有簡單、易行的特點(diǎn)。如何選擇合適的罰因子一直是罰函數(shù)應(yīng)用的瓶頸問題。方法：用罰函數(shù)將原問題轉(zhuǎn)化為無約束優(yōu)化問題再用遺傳算法求解。令，式中，隨代數(shù)t而變化?？啥x為（據(jù)罰函數(shù)原理）:k為給定的一個自然數(shù); B(i)為第i代中最好的個體; D為可行域； P(x)的定義如下：，函數(shù)p(x)表示個體x違反約束的程度，其中表示個體x在第i個不等式約束的違反程度，表示個體x在第j個等式約束的違反程度。顯然，p(x)越大說明例子x距離可行域D越遠(yuǎn)，即給的約束違反程度越高；p(x)越小，說明里子x距離可行域D越近，即給的約束違反程度越?。划?dāng)粒子x，則有p(x)=0，即任意的粒子x到可行域D的距離為0.注意：1. 若在最近的K代中，所有代最好的個體都是可行的，則減少2. 若在最近的K代中，所有代最好的個體都是不可行的，則增大3. 若在最近的K代中，有些代的最好個體為可行解，而有些代的最好個體不為可行解，則保持不變4. 也可以使用其他類型的罰函數(shù)15) 用進(jìn)化算法求解多目標(biāo)優(yōu)化問題的優(yōu)勢是什么？給出Pareto最優(yōu)解的定義優(yōu)勢：對于多目標(biāo)優(yōu)化，傳統(tǒng)方法一次只能求出一個或少數(shù)