遺傳算法是一種具有全局搜索能力的進化算法，已經(jīng)在許多領(lǐng)域得到成功應(yīng)用，但它存在局部搜索能力較差的缺點^[1]。針對遺傳算法的全局搜索和局部搜索之間的矛盾， Ge Hong等^[2]提出了GA與模擬退火算法結(jié)合的方案，F(xiàn)ogel D B^[3]給出了GA與進化規(guī)劃(EP)融合算法。上述混合遺傳算法均是利用遺傳算法的全局性，從同時結(jié)合特定問題的局部搜索技術(shù)的角度，有效地彌補了GA的局部搜索不足的缺點，但是均未能很好地改善遺傳算法本身的局部搜索性能。
　　本文模擬生物染色體中基因排列有序性，啟發(fā)于轉(zhuǎn)基因科學(xué)技術(shù)，從逆序算子的角度改善遺傳算法的局部搜索能力，借鑒遺傳算子的優(yōu)化組合方案^[4]，構(gòu)造了一種基于逆序算子的優(yōu)化組合遺傳算法，既基于傳統(tǒng)的遺傳算法，又有別于傳統(tǒng)的遺傳算法和混合算法。實驗結(jié)果表明，該算法比傳統(tǒng)的遺傳算法具有較強的局部搜索性能和更好的尋優(yōu)能力。
1 基因逆序算子
1.1 逆序算子的提出
　　遺傳算法是基于進化思想的一種優(yōu)化算法，很多的改進都來源于生物進化的啟示，并且遵循進化規(guī)則。在遺傳學(xué)中，染色體所攜帶的遺傳基因決定個體發(fā)育的方向和全過程，個體發(fā)育過程就是特定基因有序地活化和表達的過程。染色體的每個基因都含有大量的信息，并且有顯性基因和隱性基因之分，隱性基因是在特定的情況下表現(xiàn)其特性，改變生物體性能。在科技發(fā)達的今天，轉(zhuǎn)基因技術(shù)給人類帶來了無限美好的憧憬，在嘗試改變癌變細(xì)胞的基因組排序方面不斷取得新突破。此外，在現(xiàn)實世界中物質(zhì)的排列結(jié)構(gòu)對物質(zhì)的性能影響較大，例如由于碳原子排列不同，從而形成性能截然不同的金剛石和石墨。
　　在位串編碼遺傳算法中，染色體的表示是一個有序位串基因組，含有的信息量比較少。模擬生物染色體中基因排列有序性和轉(zhuǎn)基因技術(shù)應(yīng)用，對于染色體的基因組存在一個基因反序排列的基因組，構(gòu)成不同的染色體。由此提出了對染色體按基因組排列不同，分為顯性基因組和隱性基因組。在位串編碼中，染色體的順序基因組稱為顯性基因組，該染色體的一種隱性基因組由基因組的反序列構(gòu)成，由顯性基因組到隱性基因組稱為一次基因轉(zhuǎn)換，逆序算子模仿了轉(zhuǎn)基因技術(shù)，完成了基因轉(zhuǎn)換，增強了染色體的適應(yīng)度。
　　定義1：若染色體的反序列基因組有意義，設(shè)染色體X=x₁x₂……x_n-1x_n，則X′=x_nx_n-1……x₂x₁是X的逆序隱性基因組。
　　定義2：逆序算子(GR)是實現(xiàn)由X到X′轉(zhuǎn)換的遺傳算子，若X′的適應(yīng)度優(yōu)于X的適應(yīng)度,則X被X′替代，反之，X′被淘汰。
1.2 局部搜索能力的提高
　　模式定理使遺傳算法在位串基因的染色體對其性能分析有了基本定理描述手段^[5]。應(yīng)用模式定理分析，經(jīng)過逆序算子運算后的種群，每個染色體均保留了較高適應(yīng)度的基因組，形成了規(guī)模不變的新種群，通常情況下，對于總體平均適應(yīng)度和最優(yōu)個體適應(yīng)度，運算后的種群優(yōu)于或者一定不亞于運算前的種群。新種群的形成，符合遺傳算法搜索方向，向搜索目標(biāo)更加逼近和集中。逆序算子對當(dāng)前種群表達的樣本空間進行盡可能的搜索，快速找到染色體代表子空間的當(dāng)前狀態(tài)最優(yōu)解，增加遺傳算法的局部搜索能力，因此逆序算子是一種具有良好局部搜索性能的遺傳算子。大量實驗分析證明，在一定的程度上也破壞了種群的多樣性，在實際操作中,不宜每代都進行逆序算子運算。
　　對Shubert函數(shù)^[6]測試逆序算子的局部搜索能力,此函數(shù)有760個局部極小點，其中(-1.42513，-0.80032)為全局最小點，最小值為-186.7309。此函數(shù)容易陷入局部極小值-186.34027。實驗采用二進制串編碼，錦標(biāo)賽選擇策略" title="選擇策略">選擇策略，均勻雜交概率Pc=0.45，變異率Pm=0.01，種群規(guī)模m=80，遺傳代數(shù)N=1500代。對無逆序算子運行(SGA)，每隔10代、30代、50代進行逆序算子運算，分別實驗200次，結(jié)果平均值為隨機取5次的平均，如表1。

　　實驗結(jié)果表明，沒有進行逆序算子運算的結(jié)果容易發(fā)散，一旦臨近最優(yōu)值點，很難再逼近。進行逆序運算的結(jié)果不容易發(fā)散，局部搜索性強，但一旦臨近極小值，就很難跳出，全局搜索能力有所降低。綜合評價局部搜索能力和全局搜索能力，每隔30代進行一次逆序算子運算的效果較好。
2 優(yōu)化組合遺傳算法
2.1 算法構(gòu)造
　　利用逆序算子增強局部搜索性能的特點，并且最大限度地減少對全局搜索的影響，把全局搜索算子和局部搜索算子優(yōu)化組合，構(gòu)造一種基于逆序算子的優(yōu)化組合遺傳算法。全局搜索算子為高變異和低雜交率的均勻雜交法，局部搜索算子為逆序算子與低變異率和高雜交率單點交叉法。該算法把搜索過程分為全局搜索和局部搜索兩個階段，操作過程為：首先在繁殖代數(shù)的前四分之三代啟動全局搜索算子，為全局搜索階段；后四分之一代數(shù)啟動基于逆序算子的局部搜索算子，為局部搜索過程；對于最終最優(yōu)解采用每代迭代法來確定最終全局最優(yōu)解。實驗結(jié)果表明該優(yōu)化組合遺傳算法具有良好的全局搜索性能和局部搜索性能。
　　該組合優(yōu)化遺傳算法的編碼采用位、串結(jié)構(gòu)型編碼，有二進制編碼、實數(shù)編碼、浮點數(shù)編碼、格雷編碼等。常用的選擇算子如轉(zhuǎn)盤式選擇、錦標(biāo)賽選擇等，轉(zhuǎn)盤式選擇法不能使傳統(tǒng)遺傳算法收斂至全局最優(yōu)解，錦標(biāo)賽選擇策略能避免超級個體的影響，但對局部搜索不利，關(guān)于本文的選擇算子的遺傳算法的收斂性將在后面做出證明。本算法中采用排序選擇的方法作為選擇算子。在求解過程中，根據(jù)個體的適應(yīng)度大小，然后把一定的概率分配給個體，作為個體的選擇概率。
　　在全局搜索和局部搜索階段，分別考慮雜交和變異方式的優(yōu)化選擇的同時，要和其參數(shù)相適應(yīng)。在全局搜索階段，采用對全局搜索有效的均勻雜交方式，均勻雜交方式破壞模式的概率大，在搜索過程中能以較大的概率搜索到點式雜交無法搜索到的模式，但此雜交方式對局部搜索不利，因此其雜交概率一般不要過高，在0.30～0.60之間為好。為了兼顧局部搜索概率，變異率設(shè)置稍大一些，在0.03～0.1之間。在局部搜索階段，每隔30代啟動逆序算子運算。采用破壞模式概率小的點式雜交，其雜交率一般不宜過低，在0.6～0.85之間，為了兼顧全局搜索概率，變異率設(shè)置應(yīng)偏小，在0.005～0.02之間。
2.2 優(yōu)化組合遺傳算法實現(xiàn)過程
　　具體分析上述構(gòu)造基于GR的優(yōu)化組合遺傳算法各個環(huán)節(jié)，其過程描述如下：
　　(1)根據(jù)約束條件，生成二進制編碼的初始化種群，初始全局最優(yōu)解為P；
　　(2)計算種群各個染色體的適應(yīng)度；
　　(3)根據(jù)排序選擇算法對群體進行排序選擇，如果本代的最優(yōu)解優(yōu)于P，則P被本代最優(yōu)解替代；
　　(4)如果屬于全局搜索階段，按全局搜索階段的交叉和變異算子生成滿足條件的新種群；
　　(5)如果屬于局部搜索階段，按局部搜索階段的交叉和變異算子生成滿足條件的新種群，并且每隔30代啟動一次逆序局部搜索算子；
　　(6)判斷是否滿足優(yōu)化組合遺傳算法的結(jié)束條件，如果滿足結(jié)束條件，輸出最終解P，否則轉(zhuǎn)向(2)；
　　(7)輸出結(jié)果。
2.3 算法收斂性分析
　　定理 如果變異概率Pm∈(0，1)，交叉概率Pc∈(0，1)，同時采用排序選擇算法和局部搜索策略，遺傳算法最終收斂到全局最優(yōu)解。
　　證明：令F_k是時刻k，狀態(tài)為λi時群體中的最大適應(yīng)度，F(xiàn)^*是遺傳算法所求問題的全局最優(yōu)解的適應(yīng)度。若S₀是含有最優(yōu)個體X^*群體的集合，那么X^*的適應(yīng)度F₀=F^*。因此，如果狀態(tài)λi進入S₀，λ_k(k=i+1，……)將以概率1處于S₀中，即S₀為閉集。由于采用排序選擇算法，并按給定的概率表來進行選擇，在選擇之后，排在最前面的個體被選擇，也就是最佳的個體被選擇后保留。
　　由于陳國良等^[7]已證明了對于變異概率Pm∈(0，1)，交叉概率Pc∈(0，1)，并采用選擇后保留當(dāng)前最優(yōu)值的遺傳算法能收斂到全局最優(yōu)解。
　　應(yīng)用馬爾克夫鏈理論可證明局部搜索策略可在某一時刻j，進入搜索狀態(tài)S_j，并且S_j是含有最優(yōu)個體X*的小群體(狀態(tài))的集合S_j∈S₀^[8]，X*的適應(yīng)度F₀=F*，那么S_j收斂到全局最優(yōu)解。
　　由此可證基于逆序算子的本文優(yōu)化組合遺傳算法具有良好的全局收斂性。
2.4 試驗結(jié)果對比及分析
　　為了驗證本文的優(yōu)化組合遺傳算法具有良好的局部搜索性能和更好尋優(yōu)能力，對Shubert函數(shù)^[6]測試和傳統(tǒng)遺傳算法進行試驗比較。二者均采用二進制串編碼，排序選擇算法選擇策略，種群規(guī)模m=80。傳統(tǒng)遺傳算法的均勻雜交率為0.60，變異率為0.1。組合優(yōu)化遺傳算法全局搜索階段均勻雜交率Pc=0.45，變異率Pm=0.05，局部搜索階段每30代進行逆序算子運算，點式雜交率Pc′=0.7，變異率Pm′=0.01,對比試驗分別繁殖800代、1200代、1600代、2000代隨機測試200次，結(jié)果平均值為隨機取實驗10次的平均，如表2和表3。