遺傳算法在非線性規(guī)劃中的應(yīng)用

李欣蔚

摘 要 非線性規(guī)劃問(wèn)題是如今被應(yīng)用在各領(lǐng)域中的重要解題方法。遺傳算法作為近年來(lái)一種從生物遺傳學(xué)身上學(xué)習(xí)到的智能算法，與傳統(tǒng)方法相比雖然具有一定的模擬限制，但在解決全局優(yōu)化問(wèn)題上已經(jīng)取得了重大進(jìn)步。本文主要通過(guò)簡(jiǎn)要介紹遺傳算法的優(yōu)化過(guò)程，以及分析非線性規(guī)劃中主要存在的問(wèn)題，通過(guò)提出一種新的學(xué)習(xí)因子來(lái)進(jìn)行改進(jìn)遺算法在非線性規(guī)劃中的應(yīng)用。

【關(guān)鍵詞】遺傳算法 改進(jìn) 適配性 非線性規(guī)劃

非線性規(guī)劃？作為發(fā)展歷史不久的新型學(xué)科，目前其有效算法已經(jīng)存在多種解法，隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，非線性規(guī)劃的方法在其中的編譯取得了重要的成果。而對(duì)于應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究不僅僅局限于生物學(xué)，已經(jīng)被引用到人工智能等方面，為一定領(lǐng)域上的開(kāi)發(fā)瓶頸帶來(lái)了新的希望。遺傳算法的優(yōu)化過(guò)程值得在更好的方向上應(yīng)用，在這其中，如何改進(jìn)遺傳算法在非線性規(guī)劃中的應(yīng)用成為了難題之一。

1 遺傳算法的優(yōu)化過(guò)程

遺傳算法是模擬了生物學(xué)在基因遺傳方面的操作的算法。因而不難理解，在遺傳算法的操作過(guò)程中的主要任務(wù)就是在群體對(duì)象中實(shí)現(xiàn)對(duì)個(gè)體的改進(jìn)，通過(guò)一層一層的遺傳算法改進(jìn)操作，達(dá)到對(duì)整體的改進(jìn)目的。其中最基礎(chǔ)的三種遺傳優(yōu)化過(guò)程為選擇、交叉和變異。

1.1 選擇

遺傳算法的選擇過(guò)程首先要進(jìn)行編譯，利用編碼來(lái)對(duì)遺傳算法中的每一個(gè)個(gè)體進(jìn)行分析，并計(jì)算其累計(jì)的概率。具體的算法步驟如下：

（1）將遺傳算法中的數(shù)據(jù)轉(zhuǎn)換成編碼值。

（2）編碼過(guò)程中對(duì)個(gè)體進(jìn)行匹配而后計(jì)算其適配值。

（3）將群體個(gè)數(shù)的總數(shù)設(shè)定為n，個(gè)體為ki，其中i為1到n之間的任意數(shù)。因此每個(gè)個(gè)體的適配值的函數(shù)為f（ki）。

（4）將每個(gè)個(gè)體的適配值疊加得到群體總數(shù)的適配值為

（5）分別計(jì)算每個(gè)遺傳算法中的個(gè)體 ki（i=1，…，n）的選擇概率pi=f（ki）/F。

（6）分別計(jì)算每個(gè)遺傳算法中的個(gè)體 ki（i=1，…，n）的選擇概率疊加為

（7）尋找一個(gè)隨機(jī)概率數(shù)，即大于0小于1的數(shù)值，記作c。

（8）用程序進(jìn)行判斷，若c≤qi，則這個(gè)選擇概率符合我們的要求，進(jìn)而記錄這個(gè)個(gè)體，否則進(jìn)行下一個(gè)個(gè)體的判斷，使得pi-1

（9）重復(fù)（7）-（8）之間的步驟n次，直到結(jié)束。

1.2 交叉

在遺傳算法中，交叉算子是遺傳操作最重要的部分。交叉遺傳指的是把個(gè)體部分的結(jié)構(gòu)替換成改進(jìn)后的部分生成新的個(gè)體的操作。交叉算法的具體重組方式有很多種，其中使用最為廣泛的為單點(diǎn)交叉。即在個(gè)體編碼中找到一個(gè)交叉點(diǎn)，在進(jìn)行交叉過(guò)程中，以交叉點(diǎn)作為分界的兩部分進(jìn)行互換，使得生成兩個(gè)新的個(gè)體編碼。編譯過(guò)程如下：

（1）尋找一個(gè)隨機(jī)概率數(shù)，即大于0小于1的數(shù)值，記作c。

（2）將c與個(gè)體的交叉概率相比較，即個(gè)體的交叉概率較大，則個(gè)體通過(guò)篩選。

（3）將全部篩選通過(guò)的個(gè)體編碼隨機(jī)進(jìn)行匹配，而后尋找一個(gè)隨機(jī)數(shù)，隨機(jī)數(shù)要小于個(gè)體編碼的長(zhǎng)度且大于1。隨機(jī)數(shù)即為交叉點(diǎn)的位置，而后匹配好的個(gè)體編碼在交叉點(diǎn)的位置進(jìn)行互換操作。

1.3 變異

遺傳算法中的變異操作有不同的幾種，一般來(lái)說(shuō)，會(huì)按照個(gè)體編碼的表示方法而進(jìn)行不同的變異。基本操作過(guò)程為，先對(duì)群體中的個(gè)體變異概率進(jìn)行比較，判斷其是否會(huì)發(fā)生變異，而后對(duì)能夠產(chǎn)生變異的個(gè)體進(jìn)行隨機(jī)選擇變異。

（1）隨機(jī)產(chǎn)生一個(gè)變異概率數(shù)，變異概率數(shù)小于1大于0，記作c。

（2）將c與個(gè)體的變異概率進(jìn)行比較，如果個(gè)體的變異概率大于c，那么該個(gè)體將發(fā)生變異。

1.4 停止

在程序設(shè)定過(guò)程中規(guī)定一個(gè)進(jìn)化的次數(shù)。以上的選擇、交叉、變異過(guò)程為一次完整的進(jìn)化。進(jìn)化次數(shù)為多少以上步驟就重復(fù)多少次。

2 非線性規(guī)劃的主要問(wèn)題

遺傳算法在非線性規(guī)劃中應(yīng)用的最困難的問(wèn)題在于進(jìn)化的目標(biāo)函數(shù)在執(zhí)行過(guò)程中存在側(cè)重，在部分進(jìn)化的過(guò)程中實(shí)現(xiàn)整體進(jìn)化才是主要目的，然而很難做到。傳統(tǒng)的求解非線性規(guī)劃的方法存在一定的局限性，很容易使得進(jìn)化的方向陷入一個(gè)具體的點(diǎn)。具體存在以下的問(wèn)題：

（1）目標(biāo)函數(shù)的限制要求過(guò)于苛刻。

（2）整體的優(yōu)化方向是根據(jù)目標(biāo)函數(shù)的具體限制來(lái)進(jìn)行的，然而在執(zhí)行的過(guò)程中容易陷入局部化，整體性不夠。

（3）要實(shí)現(xiàn)具體的算法需要大量的數(shù)學(xué)前提準(zhǔn)備，在目標(biāo)函數(shù)復(fù)雜的情況下，想要準(zhǔn)確的進(jìn)行十分困難。

（4）在初始值的設(shè)定上存在局限性，不一定是目前算法的最優(yōu)初始值，使得得到的計(jì)算結(jié)果存在偏差。

（5）算法不夠適用，僅僅針對(duì)一個(gè)局部問(wèn)題而設(shè)計(jì)的算法并不能真正解決整體的進(jìn)化問(wèn)題，而整體進(jìn)化的大方向的把控也是難題。

3 改進(jìn)遺傳算法在非線性規(guī)劃中的應(yīng)用

3.1 非線性規(guī)劃的數(shù)學(xué)模型

如果要對(duì)遺傳算法進(jìn)行非線性規(guī)劃，首先要針對(duì)實(shí)際規(guī)劃的問(wèn)題分析，而后建立數(shù)學(xué)模型。數(shù)學(xué)模型的建立需要確定目標(biāo)變量和決策變量，建立兩個(gè)變量之間的函數(shù)關(guān)系，而后通過(guò)相應(yīng)的約束條件，達(dá)到非線性規(guī)劃的目的。

（1）設(shè)定目標(biāo)函數(shù)為x1，x2，......，x3。

（2）設(shè)定約束條件。

（3）目標(biāo)函數(shù)下的約束條件都是在定義域中的實(shí)際函數(shù)，且只要有一個(gè)為非線性。

3.2 改進(jìn)遺傳算法的設(shè)計(jì)

為了改進(jìn)遺傳算法的優(yōu)化速度以及進(jìn)化方向，這里引入學(xué)習(xí)因子。

所謂的學(xué)習(xí)因子即在遺傳算法過(guò)程中，一些本身適配性很小的個(gè)體，使用一種類似學(xué)習(xí)的算法，向適配性較大的優(yōu)秀的個(gè)體進(jìn)行學(xué)習(xí)，使其在學(xué)習(xí)后具有更好的適配性。通過(guò)增加學(xué)習(xí)因子的計(jì)算步驟，可以使得整個(gè)遺傳算法進(jìn)行改進(jìn)。具體步驟為：

（1）尋找一個(gè)較大的選擇概率數(shù)作為進(jìn)化學(xué)習(xí)目標(biāo)個(gè)體，而后篩選出適配性較差的個(gè)體，讓適配性較差的個(gè)體向?qū)W習(xí)目標(biāo)進(jìn)行概率學(xué)習(xí)。

（2）尋找學(xué)習(xí)因子作為學(xué)習(xí)方向，通過(guò)對(duì)學(xué)習(xí)目標(biāo)進(jìn)行定位，而后在一定的個(gè)體編碼中對(duì)目標(biāo)進(jìn)行梯度學(xué)習(xí)。

（3）經(jīng)過(guò)上述學(xué)習(xí)之后，使得適配性較差的個(gè)體適配性增高，在適配概率上，被選擇的概率和改進(jìn)的程度都有所提高。

4 結(jié)論

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，非線性規(guī)劃的方法在其中的編譯取得了重要的成果。非線性規(guī)格化作為發(fā)展歷史不久的新型學(xué)科，目前其有效算法已經(jīng)存在多種解法，而對(duì)著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究不僅僅局限于遺傳學(xué)，甚至已經(jīng)被用于更多的智能科技領(lǐng)域，在未來(lái)的科技發(fā)展上開(kāi)拓了新的道路。通過(guò)研究遺傳算法的優(yōu)化過(guò)程，并在計(jì)算機(jī)算法中進(jìn)行實(shí)現(xiàn)，在分析非線性規(guī)劃中主要存在的問(wèn)題的基礎(chǔ)上，通過(guò)提出一種新的學(xué)習(xí)因子來(lái)進(jìn)行改進(jìn)遺算法在非線性規(guī)劃中的應(yīng)用。學(xué)習(xí)因子在一定程度上可以擴(kuò)大整體進(jìn)化的程度，在一定方向上實(shí)現(xiàn)了改進(jìn)遺傳算法在非線性規(guī)劃中的應(yīng)用。

參考文獻(xiàn)

[1]陳丹丹.多準(zhǔn)則多約束水平非線性規(guī)劃理論及應(yīng)用研究[D].西南石油大學(xué)，2014.

[2]劉牧華.約束非線性規(guī)劃的兩種算法[D].河南科技大學(xué)，2012.

[3]周偉平，劉兵兵.解灰色非線性規(guī)劃問(wèn)題的隨機(jī)搜索算法[J].計(jì)算機(jī)應(yīng)用，2013（10）.

作者單位

東北育才學(xué)校超常教育實(shí)驗(yàn)部 遼寧省阜新市 123000