摘 要：針對(duì)基本遺傳算法效率低和易早熟的缺陷，提出了一種改進(jìn)操作算子的遺傳算法。該算法在種群初始化、選擇、交叉、變異等基本算子的基礎(chǔ)上加以改進(jìn)，使算法具有更好的適應(yīng)性。對(duì)3組不同函數(shù)的測(cè)試表明，改進(jìn)算法較傳統(tǒng)的遺傳算法具有在種群很小的情況下收斂速度快穩(wěn)定性高的優(yōu)點(diǎn)，同時(shí)能有效地避免早熟現(xiàn)象。
關(guān)鍵詞：遺傳算法；變異；收斂速度；種群數(shù)

0 引 言
    遺傳算法(Genetic Algorithm，GA)是一種宏觀意義下的仿生算法，它模仿的機(jī)制是一切生命與智能的產(chǎn)生與進(jìn)化過(guò)程，從一個(gè)初始種群出發(fā)，不斷重復(fù)執(zhí)行選擇，雜交和變異的過(guò)程，使種群進(jìn)化越來(lái)越接近某一目標(biāo)。它通過(guò)模擬達(dá)爾文“優(yōu)勝劣汰，適者生存”的原理激勵(lì)好的結(jié)構(gòu)；通過(guò)模擬孟德?tīng)栠z傳變異理論在迭代過(guò)程中保持已有的結(jié)構(gòu)，同時(shí)尋找更好的結(jié)構(gòu)。經(jīng)典遺傳算法的求解步驟為：初始化種群；選擇；交叉；變異；判斷終止條件。由于它簡(jiǎn)單有效，具有很強(qiáng)的魯棒性和通用性，所以被廣泛應(yīng)用于模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會(huì)科學(xué)等多種領(lǐng)域。
    早熟和收斂時(shí)間過(guò)長(zhǎng)是影響遺傳算法效率的兩個(gè)主要因素，而選擇壓力過(guò)大是導(dǎo)致早熟收斂的一個(gè)重要原因，為此不少學(xué)者對(duì)遺傳算法做了改進(jìn)，但仍存在一定局限性。在此對(duì)遺傳算法個(gè)操作算子加以改進(jìn)，通過(guò)對(duì)經(jīng)典多極值測(cè)試函數(shù)的仿真研究表明，改進(jìn)后的算法能夠有效避免早熟且在種群規(guī)模較小的情況下具有較快的收斂速度。

l 改進(jìn)操作算子的遺傳算法
    經(jīng)典遺傳算法的把變異作為一種輔助手段，認(rèn)為變異只是一個(gè)背景機(jī)制，這一觀點(diǎn)與生物學(xué)中的實(shí)際觀察是相符的，但作為設(shè)計(jì)人工求解問(wèn)題方法的思想，他正受到理論與實(shí)踐兩方面的挑戰(zhàn)。另外，從微觀角度來(lái)講，變異隨時(shí)都有可能發(fā)生，如果突變向不好的方向進(jìn)行．其“修復(fù)系統(tǒng)”立刻就能對(duì)其進(jìn)行修復(fù)?；谝陨蟽牲c(diǎn)，這里在選擇與交叉算子中滲入不同的變異行為，且動(dòng)態(tài)改進(jìn)變異算子，使算法能快速達(dá)到全局最優(yōu)。
1．1 初始化
    為了改善初始群體的效能，提高模式的優(yōu)良度，采取如下方法：先隨機(jī)產(chǎn)生一個(gè)父染色體，對(duì)其進(jìn)行一定次數(shù)(20次左右)的逐位精英選擇高頻變異，方法如下：例如染色體為01001，先把第一位變異為1，成為11001。若適應(yīng)度提高，則此位以很大的概率p(如O．98)轉(zhuǎn)換為1，否則以很小的概率(如0．01)轉(zhuǎn)換為1，以此類推。接著產(chǎn)生具有一定規(guī)模的染色體種群，隨機(jī)使其中每個(gè)染色體的某段基因與之前父染色體相應(yīng)基因段保持一致。如：假設(shè)父染色體為00110，隨機(jī)產(chǎn)生個(gè)體10101，若以第一和第二位基因與父染色體一致，則該個(gè)體變?yōu)椋?0101。該方法把較優(yōu)秀的模式分散到各個(gè)染色體中，使它一開(kāi)始就具有一定概率的優(yōu)秀短模式，從而有效提高算法的尋優(yōu)效率。
1．2 選擇操作
    經(jīng)典遺傳算法根據(jù)適者生存原則選擇下一代個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。
    然而基于適應(yīng)度的概率選擇機(jī)制如輪盤賭選擇法在種群中出現(xiàn)個(gè)別或極少數(shù)適應(yīng)度相當(dāng)高的個(gè)體時(shí)，就可能導(dǎo)致這些個(gè)體在群體中迅速繁殖，經(jīng)過(guò)少數(shù)迭代后占滿了種群的位置。這樣，遺傳算法的求解過(guò)程就結(jié)束了，也即收斂了。但這樣很有可能使收斂到局部最優(yōu)解，即出現(xiàn)早熟現(xiàn)象。為了從根本上避免早熟現(xiàn)象且加快收斂速度，采用基于高頻精英變異的錦標(biāo)賽選擇法。其操作如下：假設(shè)競(jìng)賽規(guī)模為2，首先選取種群中第1和第2個(gè)個(gè)體X和Y
    如：X=100101，Y=011110
    從第1位開(kāi)始比較適應(yīng)值的大小，即當(dāng)個(gè)體X與Y的第1位分別是1和O時(shí)，假設(shè)fitness(X)>fitness(Y)，于是把Y的第1位由0高頻變異為1，此時(shí)：
    X=110101，Y=101110
此時(shí)，若fithess(X)<fithess(Y)，則把Y的第1位由1高頻變異為O。如此下去，最終得到的為選擇出的個(gè)體，其中較高位(如第1至L／3位，其中L為染色體長(zhǎng)度)變異率為0．8，其他位變異率為0．95，理由是較高位的個(gè)體即使適應(yīng)度低也有可能在附近變異成適應(yīng)度更高的個(gè)體。
    然后選取種群中第2和第3個(gè)個(gè)體應(yīng)用上法選擇出第2個(gè)個(gè)體，這個(gè)過(guò)程重復(fù)進(jìn)行，完成剩余個(gè)體的選擇。這種算子在選擇個(gè)體上就可以有方向性且極大地加快算法的收斂速度。
1．3 交叉操作
    交叉是把兩個(gè)父?jìng)€(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作，從而在下一代產(chǎn)生新的個(gè)體。它的目的是開(kāi)發(fā)問(wèn)題解空間中新的區(qū)域，尋找父?jìng)€(gè)體已有的但未能合理組合的基因，盡量保證具有優(yōu)良模式的個(gè)體不被交叉操作所完全破壞，同時(shí)增大種群的離散程度，產(chǎn)生新的搜索空間。所有交叉操作的一個(gè)共同特征是，不破壞兩個(gè)父?jìng)€(gè)體之間的公共串模式，允許繼續(xù)搜索空間時(shí)保留好的模式。
    對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇2個(gè)個(gè)體的相同位置，按交叉概率P在選中的位置實(shí)行交換。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換，目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。在交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。
    一點(diǎn)交叉是經(jīng)典的交叉方法，它是對(duì)于給定的兩個(gè)父?jìng)€(gè)體，隨機(jī)地選取1個(gè)交叉位置，然后相互交換兩個(gè)個(gè)體交叉位置右邊部分基因，形成2個(gè)子代，一點(diǎn)交叉能夠搜索到的空間十分有限。多點(diǎn)交叉的破壞性可以促進(jìn)解空間的搜索，而不是促進(jìn)過(guò)早地收斂，因此搜索更加健壯。這里在采取多點(diǎn)交叉的同時(shí)考慮父?jìng)€(gè)體間的多樣度。
    當(dāng)兩個(gè)父?jìng)€(gè)體的漢明距離較低，可能導(dǎo)致交叉操作無(wú)效。另外，由于交叉點(diǎn)隨機(jī)產(chǎn)生，可能會(huì)導(dǎo)致交叉后新個(gè)體無(wú)變化，例如，兩父?jìng)€(gè)體分別為01100101和01011010，如果交叉點(diǎn)取值為第2位，則交叉后的兩個(gè)新個(gè)體與父?jìng)€(gè)體相同，交叉操作無(wú)效。在此采取交叉概率與漢明距離成正比的策略：兩父體相似度高時(shí)交叉概率減小以避免無(wú)效操作，一旦在這種情況下進(jìn)行交叉，首先保持具有高適應(yīng)度的父?jìng)€(gè)體不變，然后對(duì)低適應(yīng)度個(gè)體或者交叉點(diǎn)左右具有相同子串的個(gè)體采取變異操作以增大它們之間的漢明距離，從而提高交叉操作的有效性。
1．4 變異操作
    根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)镺，把O變?yōu)?。
    單靠變異不能在求解中得到好處。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)．交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。
    這里提出一種自適應(yīng)快速收斂變異法：對(duì)每一個(gè)體采取從高位到低位逐位變異的策略。在尋優(yōu)的早期主要是全局搜索，此時(shí)各變量二進(jìn)制的高位應(yīng)采用高變異率，低位采用低變異率。在尋優(yōu)過(guò)程中不斷調(diào)整各位的變異率，即高位變異率逐漸降低，低位變異率逐漸增加。到尋優(yōu)后期，主要是局部?jī)?yōu)化，全局優(yōu)化次之，此時(shí)各位變異率與早期相反，即低位變異率要比高位變異率大。在變異過(guò)程中采用概率精英保留策略，也就是每位變異后若適應(yīng)值增加，則以高概率保留，否則放棄此位變異。實(shí)驗(yàn)證明，這種變異策略在種群規(guī)模較小的情況下能獲得較滿意的進(jìn)化能力。

2 算法描述
    算法描述為：
    (1)采用二進(jìn)制編碼，隨機(jī)產(chǎn)生一個(gè)體，通過(guò)逐位高頻精英變異，提高其適應(yīng)度；
    (2)利用上述較優(yōu)父染色體產(chǎn)生產(chǎn)生種群；
    (3)進(jìn)行基于高頻精英變異的錦標(biāo)賽選擇；
    (4)進(jìn)行改進(jìn)的交叉運(yùn)算；
    (5)進(jìn)行自適應(yīng)變異運(yùn)算；
    (6)是否到最大的遺傳代數(shù)，如果達(dá)到，結(jié)束；否則轉(zhuǎn)到步驟(3)。

3 仿真試驗(yàn)及結(jié)果分析
3．1 試驗(yàn)
    為驗(yàn)證改進(jìn)算法的效率，用經(jīng)典遺傳算法SGA和文中的加速收斂改進(jìn)遺傳算法相比較，其中SGA采用的遺傳操作及相應(yīng)參數(shù)為比例選擇、單點(diǎn)交叉(交叉概率0．85)及基本位變異(變異概率0．05)，種群規(guī)模為100，進(jìn)化代數(shù)為100。兩者都采用保留個(gè)體精英的方法。選擇如下3個(gè)算例進(jìn)行仿真計(jì)算。
    (1)Camel函數(shù)

    此函數(shù)有6個(gè)極小點(diǎn)，其中有2個(gè)(一0．089 8，O．712 6)和(0．089 8，一O．712 6)為全局最小點(diǎn)，最小值為一1．031 628，自變量的取值范圍為一100<x，y<100。
    (2)Shubert函數(shù)

   
    該函數(shù)有760個(gè)局部極小點(diǎn)，其中只有1個(gè)(一1．425 13，一O．800 32)為全局最小，最小值為186．730 9。自變量取值范圍一10<x，y<10。此函數(shù)極易陷入局部極小值186．34。
    (3)Schaffer函數(shù)

   
    該函數(shù)有無(wú)限個(gè)局部極大點(diǎn)，其中只有一個(gè)(0，0)為全局最大，最大值為1。自變量的取值范圍為一100<x，y<100。該函數(shù)最大值峰周圍有一個(gè)圈脊，它們的取值均為O．990 283，因此很容易停滯在局部極大值。
    改進(jìn)后算法的種群規(guī)模為20，進(jìn)化代數(shù)為60。對(duì)兩種算法進(jìn)行100次隨機(jī)仿真，試驗(yàn)結(jié)果如表1所示。

3．2 結(jié)果分析
    從以上結(jié)果可以看出，SGA容易早熟收斂，而改進(jìn)后的算法能很好地?cái)[脫早熟，并能以很高的成功概率快速搜索到最優(yōu)值。從各參數(shù)也可以看出，改進(jìn)后的遺傳算法在種群規(guī)模很小的情況下也具有很高的尋優(yōu)效率。因此，這里提出的改進(jìn)算子GA從全局收斂概率和平均進(jìn)化代數(shù)來(lái)看，是成功的，它具有高效的全局以及局部搜索能力。

4 結(jié) 語(yǔ)
    通過(guò)對(duì)算法各算子的改進(jìn)，較好地解決了一般遺傳算法收斂速度慢和全局尋優(yōu)能力弱的缺點(diǎn)。實(shí)踐表明，改進(jìn)GA和標(biāo)準(zhǔn)GA相比，在花費(fèi)更少的情況下具有更快的收斂速度和精度。