基于實(shí)數(shù)編碼的遺傳算法在飼料配方設(shè)計中的應(yīng)用

1、基于實(shí)數(shù)編碼的遺傳算法在飼料配方設(shè)計中的應(yīng)用報告人：陶琳麗云南省動物營養(yǎng)與飼料重點(diǎn)實(shí)驗(yàn)室云南農(nóng)業(yè)大學(xué)動物科學(xué)技術(shù)學(xué)院一、研究意義1、引入新的優(yōu)化算法遺傳算法，解決現(xiàn)有飼料配方設(shè)計中由純數(shù)學(xué)思維算法本身局限性所產(chǎn)生的不足。如：線性規(guī)劃模型中，當(dāng)約束條件之間或約束條件與目標(biāo)函數(shù)間存在矛盾時，系統(tǒng)無可行解；數(shù)學(xué)上給出的滿足約束條件和目標(biāo)函數(shù)的優(yōu)化配方，從營養(yǎng)學(xué)的角度看有時又是不可行的。Yunnan Animal Nutrition And Feed Science Laboratory一、研究意義2、解決標(biāo)準(zhǔn)遺傳算法在計算飼料配方時易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力差等問題 。如：用標(biāo)準(zhǔn)遺傳算法在計算飼

2、料配方時易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力差等問題，特別是在原料多，約束條件多的情況下，這種缺點(diǎn)表現(xiàn)的更為明顯。 Yunnan Animal Nutrition And Feed Science Laboratory二、遺傳算法（Genetic Algorithm，GA）遺傳算法（Genetic Algorithm）是一類借鑒生物界的進(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)整

3、搜索方向，不需要確定的規(guī)則。Yunnan Animal Nutrition And Feed Science Laboratory1、遺傳算法的組成遺傳算法可定義為一個8員組：SGA=(C, E, P0, M, , , , T) C 個體的編碼方法； E 個體適應(yīng)度評價函數(shù)； P0 初始群體； M 群體大??； 選擇算子； 交叉算子； 變異算子； T 遺傳運(yùn)算終止條件。 Yunnan Animal Nutrition And Feed Science Laboratory2、遺傳算法思想初始化群體；計算群體上每個個體的適應(yīng)度值；按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體；按概率Pc進(jìn)

4、行交叉操作；按概率Pm進(jìn)行突變操作；沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)。輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。Yunnan Animal Nutrition And Feed Science Laboratory3、遺傳算法的優(yōu)點(diǎn)（1）遺傳對所解的優(yōu)化問題沒有太多的數(shù)學(xué)要求，遺傳算法可以處理任意形式的目標(biāo)函數(shù)和約束，無論是線性的還是非線性的，離散的還是連續(xù)，甚至混合的搜索空間。（2）進(jìn)化算子的各態(tài)歷經(jīng)性使得遺傳算法能夠非常有效的進(jìn)行概率意義下的全局搜索，而傳統(tǒng)的優(yōu)化方法是通過鄰近點(diǎn)比較而轉(zhuǎn)移到較好的點(diǎn)，從而達(dá)到收斂的局部搜索過程。（3）遺傳算法對于各種特殊問

5、題可以提供極大的靈活性來混合構(gòu)造領(lǐng)域獨(dú)立的啟發(fā)式，從而保證算法的有效性。Yunnan Animal Nutrition And Feed Science Laboratory4、遺傳算法性能分析指標(biāo)（1）在線性性能評估在線性能表示為：其中：T 是進(jìn)化代數(shù)；是第t代的平均適應(yīng)度函數(shù)；表示到T代為止所有適應(yīng)度函數(shù)值的平均性能。在線指標(biāo)用于說明算法的在線性能。Yunnan Animal Nutrition And Feed Science Laboratory4、遺傳算法性能分析指標(biāo)（2）離線性性能評估離線性能表示為：其中是第t代最好的個體的適應(yīng)度函數(shù)值；表示至第T代每次最好的適應(yīng)度函數(shù)值的平均。

6、離線指標(biāo)用于說明算法的收斂性。 Yunnan Animal Nutrition And Feed Science Laboratory三、遺傳算法在飼料配方設(shè)計中的應(yīng)用 算法設(shè)計流程圖飼料配方問題描述確定決策變量、約束條件建立線性規(guī)劃模型確定適應(yīng)度轉(zhuǎn)換規(guī)則設(shè)計遺傳因子個體表型X編碼方法解碼方法個體基因型X確定運(yùn)行參數(shù)適應(yīng)度函數(shù)F(x)遺傳算法算法調(diào)試運(yùn)行Yunnan Animal Nutrition And Feed Science Laboratory1、標(biāo)準(zhǔn)遺傳算法在飼料配方設(shè)計中的應(yīng)用1.1 編碼策略 在遺傳算法的運(yùn)行過程中，它不對所求解問題的實(shí)際決策變量直接進(jìn)行操作，而是對表示可行解的

7、個體編碼施加選擇、交叉、變異等遺傳算法，通過這種遺傳操作來達(dá)到優(yōu)化的目的，這是遺傳算法的特點(diǎn)之一。遺傳算法通過這種對個體編碼的操作，不斷搜索出適應(yīng)度較高的個體，并在群體中逐漸增加其數(shù)量，最終尋求出問題的最優(yōu)解或近似最優(yōu)解。在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼。Yunnan Animal Nutrition And Feed Science Laboratory1.1 編碼策略二進(jìn)制編碼浮點(diǎn)數(shù)編碼符號編碼存在缺點(diǎn)：1、海明懸崖；2、求解的精度確定后算法缺乏微調(diào)能力；3、算法精度要求高或二進(jìn)制編碼字串長時，算法搜索效率

8、較低。 也稱實(shí)數(shù)編碼，是指個體的每個基因值用某一范圍內(nèi)的一個浮點(diǎn)數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。 根據(jù)飼料配方設(shè)計的要求及實(shí)數(shù)編碼的特點(diǎn)，在本次飼料配方中的標(biāo)準(zhǔn)遺傳算法采用實(shí)數(shù)編碼。 Yunnan Animal Nutrition And Feed Science Laboratory1.2 初始種群的生成根據(jù)飼料原料及其營養(yǎng)成分表中各種原料的用量上限、用量下限、等量使用的要求，在最優(yōu)解所占問題空間中的分布范圍內(nèi)使用隨機(jī)生成初始種群。 具體實(shí)現(xiàn)過程：Yunnan Animal Nutrition And Feed Science Laboratory1.2 初始種群的生成（1）生

9、成隨機(jī)種子；（2）設(shè)定初始種群的數(shù)量；（3）利用約束條件對生成的每一個隨機(jī)數(shù)的上下限進(jìn)行控制，保證生成的隨機(jī)數(shù)在約束條件圍內(nèi)；（4）測試生成的種群中各原料是否能滿足營養(yǎng)需求，若不能滿足則返回（3）；（5）初始種群的數(shù)量是否達(dá)到，若達(dá)到則跳出，否則返回（3）。 Yunnan Animal Nutrition And Feed Science Laboratory1.3 適應(yīng)度函數(shù)度量個體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。飼料配方設(shè)計的要求是在保證滿足飼養(yǎng)標(biāo)準(zhǔn)要求的條件下降低飼料配方的成本。因此，本研究中遺傳算法的個體適應(yīng)度函數(shù)的設(shè)計采用飼料成本極小化方法。適應(yīng)度函數(shù)為： ci代表第i種的飼料原料的市場

10、價格；xi代表第i種飼料原料在配方中的含量；Zmin為飼料配方的成本；n為飼料原料的種類數(shù)。適應(yīng)度較高的個體遺傳到下一代的概率較大，適應(yīng)度較低的個體遺傳到下一代的概率相對較小。 Yunnan Animal Nutrition And Feed Science Laboratory1.4 選擇操作選擇操作也叫復(fù)制操作，從群體中按個體的適應(yīng)度函數(shù)值選擇出較適應(yīng)環(huán)境的個體。 標(biāo)準(zhǔn)遺傳算法中采用輪盤賭模型。選擇操作的主要目的是提高全局的收斂性和計算效率。 飼料配方設(shè)計中的標(biāo)準(zhǔn)遺傳算法的選擇操作的實(shí)現(xiàn)： Yunnan Animal Nutrition And Feed Science Laborator

11、y1.4 選擇操作 以單個個體適應(yīng)度值倒數(shù)占種群中共np個個體的適應(yīng)度值倒數(shù)之和的比率作為選擇概率。即：單個個體適應(yīng)度值倒數(shù)：適應(yīng)度值倒數(shù)之和：選擇概率：(1=j=np)Yunnan Animal Nutrition And Feed Science Laboratory1.5 交叉過程交叉運(yùn)算是產(chǎn)生新個體的主要方法，是決定算法收斂性能的關(guān)鍵。標(biāo)準(zhǔn)遺傳算法中，進(jìn)行交叉操作時， 首先按照預(yù)先設(shè)定的交叉概率選出要進(jìn)行交叉的個體， 形成交叉配對池， 然后對配對池中的個體進(jìn)行完全隨機(jī)的等概率一一配對，最后對每一對父代個體隨機(jī)確定交叉點(diǎn)，交換基因片段，生成新的子代個體。 Yunnan Animal Nu

12、trition And Feed Science Laboratory1.5 交叉過程根據(jù)實(shí)數(shù)編碼的特點(diǎn)，交叉方式選擇算術(shù)交叉。算術(shù)交叉是指由兩個個體的線性組合而產(chǎn)生出兩個新的個體。當(dāng)滿足概率Pc，則 ：rnd是0,1上的隨機(jī)數(shù)。Yunnan Animal Nutrition And Feed Science Laboratory1.5 交叉過程否種群中的每個個體Xi是否選擇完成？針對Xi生成隨機(jī)數(shù)R隨機(jī)數(shù)R小于交叉概率Pc？種群中的個體Xi進(jìn)入交叉配對池種群配對池中的每個個體是否配對完成？隨機(jī)配對隨機(jī)選擇交叉點(diǎn)交換基因片段進(jìn)入下一階段操作是否是是否標(biāo)準(zhǔn)交叉操作具體流程圖Yunnan Anim

13、al Nutrition And Feed Science Laboratory1.6 變異過程變異運(yùn)算是產(chǎn)生新個體的輔助方法。但也是必不可少的一步運(yùn)算步驟。 主要目的：（1）提高了遺傳算法的局部搜索能力。 （2）維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。在本研究中，基本遺傳算法變異過程的實(shí)現(xiàn)采用均勻變異，即在變異過程中，個體中的一個隨機(jī)基因，在約束條件的上下范圍內(nèi)實(shí)現(xiàn)隨機(jī)生成，并替換原有基因值。 Yunnan Animal Nutrition And Feed Science Laboratory1.7 算法操作的基本步驟（1）根據(jù)配方設(shè)計要求進(jìn)行實(shí)數(shù)編碼；（2）隨機(jī)初始化群體P(0)=(p1,

14、p2, pn)； （3）計算群體上每個個體的適應(yīng)度值(Fitness)；（4）評估適應(yīng)度，對當(dāng)前群體P(t)中每個個體Pi計算其適應(yīng)度F(Pi)；（5）按由個體適應(yīng)度值所決定的某個規(guī)則應(yīng)用選擇算子產(chǎn)生中間代Pr(t)；（6）依照交叉概率Pc選擇個體進(jìn)行交叉操作；（7）根據(jù)變異概率Pm對繁殖個體進(jìn)行變異操作；（8）沒有滿足某種停止條件，則轉(zhuǎn)第（3）步，否則進(jìn)入（9）步；（9）輸出種群中適應(yīng)度值最優(yōu)的個體。算法的停止條件：完成了預(yù)先給定的進(jìn)化代數(shù)則停止。 Yunnan Animal Nutrition And Feed Science Laboratory運(yùn)行參數(shù)確定通過100次試驗(yàn)，分別確定：終

15、止代數(shù)G=300；群體大小M=128；交叉概率Pc=0.7；變異概率Pm=0.1。Yunnan Animal Nutrition And Feed Science Laboratory標(biāo)準(zhǔn)遺傳算法的不足1、算法的運(yùn)算時間長；2、計算后的結(jié)果不理想，與單純型法的結(jié)果相比還有一定的差距。造成不足的原因： 標(biāo)準(zhǔn)遺傳算法在進(jìn)化過程中易產(chǎn)生早熟現(xiàn)象和局部尋優(yōu)能力差等問題。Yunnan Animal Nutrition And Feed Science Laboratory2、改進(jìn)的遺傳算法2.1 編碼策略同標(biāo)準(zhǔn)遺傳算法。2.2 初始種群生成同標(biāo)準(zhǔn)遺傳算法。2.3 適應(yīng)度函數(shù)同標(biāo)準(zhǔn)遺傳算法。Yunnan

16、Animal Nutrition And Feed Science Laboratory2.4 選擇策略標(biāo)準(zhǔn)遺傳算法選擇策略輪盤賭模型存在以下缺陷：（1）適應(yīng)度函數(shù)中有較多指標(biāo)需要計算，特別在多次的迭代過程中，一定程度上影響了程序運(yùn)行效率；（2）不能保證最優(yōu)個體進(jìn)入下一輪競爭。 Yunnan Animal Nutrition And Feed Science Laboratory2.4 選擇策略針對以上缺陷，對選擇策略進(jìn)行優(yōu)化：（1）采用隨機(jī)聯(lián)賽選擇模型替代輪盤賭模型，降低計算機(jī)處理時間。操作：每次從群體中隨機(jī)選取4個個體進(jìn)行適應(yīng)度大小比較，將其中適應(yīng)度最高的2個個體遺傳到下一代群體；重復(fù)上述

17、過程直到下一代群體完全生成。（2）構(gòu)造新的種群時，采用精英主義方法。操作：在交叉和變異的過程中允許父代和子代進(jìn)行競爭，讓優(yōu)良個體進(jìn)入下一輪的競爭環(huán)境，這樣既保證了算法的迭代穩(wěn)定性，又保證了算法具有實(shí)現(xiàn)局部最優(yōu)化的能力。Yunnan Animal Nutrition And Feed Science Laboratory2.5 交叉操作標(biāo)準(zhǔn)遺傳算法交叉操作存在的缺陷：子代個體的搜索空間將不斷收縮，從而導(dǎo)致早熟。 針對以上缺陷，對交叉操作進(jìn)行改進(jìn)。對父代矢量的各個分量進(jìn)行交叉時，采用不同的隨機(jī)數(shù)：child1j= parent1j+ rndj (parent2j- parent1j)child2j

18、= parent2j+ rndj (parent1j- parent2j) parent1j、parent2j分別為父代parent1、parent2的分量；child1j、child2j分別為子代個體矢量child1、child2的分量；rndj為-2,2區(qū)間的隨機(jī)數(shù)。 Yunnan Animal Nutrition And Feed Science Laboratory2.6 變異操作標(biāo)準(zhǔn)遺傳算法變異操作存在的缺陷： 均勻變異特點(diǎn)適合應(yīng)用于遺傳算法的初期運(yùn)行階段，但在運(yùn)行階段后期對于局部的重點(diǎn)搜索，均勻變異的收斂難于達(dá)到一個很好的效果。針對以上缺陷，對變異操作進(jìn)行改進(jìn)： 采用高斯變異來改進(jìn)均勻變異，高斯變異時符合正態(tài)分布的隨機(jī)數(shù)Q可由一些符合均勻分布的隨機(jī)數(shù)利用公式來近似產(chǎn)生。Yunnan Animal Nutrition And Feed Science Laboratory2.7 交叉概率和變異概率標(biāo)準(zhǔn)遺傳算法中存在問題：交叉概率Pc越大，新個體產(chǎn)生的速度越快，遺傳模式被破壞的可能性也越大；Pc太小，會使搜索過程緩慢，以至停滯不前。變異概率Pm過小，不易產(chǎn)生新個體；變異率Pm過大，遺傳算法就變成了純粹的隨機(jī)搜索法。 改進(jìn)方法：針對Pc和