一種新的改進遺傳算法及其性能分析摘要：雖然遺傳算法以其全局搜索、并行計算、更好的健壯性以及在進化過程中不需要求導而著稱，但是它仍然有一定的缺陷，比如收斂速度慢。本文根據幾個基本定理，提出了一種使用變異染色體長度和交叉變異概率的改進遺傳算法，它的主要思想是：在進化的開始階段，我們使用短一些的變異染色體長度和高一些的交叉變異概率來解決，在全局最優解附近，使用長一些的變異染色體長度和低一些的交叉變異概率。最后，一些關鍵功能的測試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優于只保留最佳個體的遺傳算法。關鍵字：編譯染色體長度；變異概率；遺傳算法；在線離線性能遺傳算法是一種以自然界進化中的選擇和繁殖機制為基礎的自適應的搜索技術，它是由Holland1975年首先提出的。它以其全局搜索、并行計算、更好的健壯性以及在進化過程中不需要求導而著稱。然而它也有一些缺點，如本地搜索不佳，過早收斂，以及收斂速度慢。近些年，這個問題被廣泛地進行了研究。本文提出了一種使用變異染色體長度和交叉變異概率的改進遺傳算法。一些關鍵功能的測試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優于只保留最佳個體的遺傳算法。在第一部分，提出了我們的新算法。第二部分，通過幾個優化例子，將該算法和只保留最佳個體的遺傳算法進行了效率的比較。第三部分，就是所得出的結論。最后，相關定理的證明過程可見附錄。1.算法的描述1.1一些定理在提出我們的算法之前，先給出一個一般性的定理（見附件），如下：我們假設有一個變量（多變量可以拆分成多個部分，每一部分是一個變量）xa,b,xR，二進制的染色體編碼是1.定理1染色體的最小分辨率是s=定理2染色體的第i位的權重值是wi=(i=1,2,l)定理3單點交叉的染色體搜索步驟的數學期望Ec(x)是Ec(x)=Pc其中Pc是交叉概率定理4位變異的染色體搜索步驟的數學期望Em(x)是Em(x)=(b-a)Pm其中Pm是變異概率1.2算法機制在進化過程中，我們假設變量的值域是固定的，交叉的概率是一個常數，所以從定理1和定理3我們知道，較長的染色體長度有著較少的染色體搜索步驟和較高的分辨率；反之亦然。同時，交叉概率與搜索步驟成正比。由定理4，改變染色體的長度不影響變異的搜索步驟，而變異概率與搜索步驟也是成正比的。進化的開始階段，較短染色體（可以是過短，否則它不利于種群多樣性）和較高的交叉和變異概率會增加搜索步驟，這樣可進行更大的域名搜索，避免陷入局部最優。而全局最優的附近，較長染色體和較低的交叉和變異概率會減少搜索的步驟，較長的染色體也提高了變異分辨率，避免在全局最優解附近徘徊，提高了算法收斂速度。最后，應當指出，染色體長度的改變不會使個體適應性改變，因此它不影響選擇（輪盤賭選擇）。1.3算法描述由于基本遺傳算法沒有在全局優化時收斂，而遺傳算法保留了當前一代的最佳個體，我們的方法采用這項策略。在進化過程中，我們跟蹤到當代個體平均適應度的累計值。它被寫成：X(t)=(t)其中G是當前進化的一代，favg是個體的平均適應度。當累計平均適用性增加到最初個體平均適應度的k(k1,kR)倍，我們將染色體長度變為其自身的m(m是一個正整數)倍，然后減小交叉和變異的概率，可以提高個體分辨率、減少搜索步驟以及提高算法收斂速度。算法的執行步驟如下：第一步：初始化群體，并計算個體平均適應度favg0，然后設置改變參數的標志flag。flag設為1.第二步：在所保留的當代的最佳個體，進行選擇、再生、交叉和變異，并計算當代個體的累積平均適應度favg第三步：如果且flag=1，把染色體的長度增加至自身的m倍，減少交叉和變異概率，并設置flag等于0；否則繼續進化。第四步：如果滿足結束條件，停止；否則轉自第二步。2.測試和分析我們采用以下兩種方法來測試我們的方法，和只保留最佳個體的遺傳算法進行比較：2.1收斂的分析在功能測試中，我們進行了以下政策：輪盤賭選擇，單點交叉，位變異。種群的規模是60。L是染色體長度，Pc和Pm分別是交叉概率和變異概率。我們隨機選擇4個遺傳算法所保留的最佳個體來與我們的方法進行比較，它們具有不同的固定染色體長度和交叉和變異的概率。表1給出了在100次測試的平均收斂代。在我們的方法中，我們采取的初始參數是l0=10，Pc0=0.3，Pm0=0.1和k=1.2，當滿足改變參數的條件時，我們調整參數l=30，Pc=0.1，Pm=0.01。從表1中得知，我們的方法顯著提高了遺傳算法的收斂速度，正符合上述分析。表1功能測試結果方法我們的算法l=10Pc=0.1,Pm=0.1l=10Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1l=30Pc=0.1,Pm=0.1f1257152363579116264363f2198269734237445054332.2在線和離線性能的分析Dejong提出了遺傳算法的定量評價方法，包括在線和離線性能評價。前者測試動態性能，而后者評估收斂性能。為了更好地分析測試功能的在線和離線性能，我們把個體的適應性乘以10，并f1和f2分別給出了4000和1000代的曲線：(a)在線(b)離線圖1f1的在線與離線性能(a)在線(b)離線圖2f2的在線與離線性能從圖1和圖2可以看出，我們方法的在線性能只比第四種情況差一點點，但比第二種、第三種、第五種好很多，這幾種情況下的在線性能幾乎完全相同。同時，我們方法的離線性能也比其他四種好很多。3.結論本文提出了一種使用變異染色體長度和交叉變異概率的改進遺傳算法。一些關鍵功能的測試表明，我們的解決方案可以顯著提高遺傳算法的收斂速度，其綜合性能優于只保留最佳個體的遺傳算法。附件有了第一部分中假定的條件，定理1和定理2的驗證是顯而易見的。下面給出定理3和定理4的證明過程：定理3單點交叉的染色體搜索步驟的數學期望Ec(x)是Ec(x)=Pc其中Pc是交叉概率證明：如圖A1所示，我們假設交叉發生在第k個基因位點，從k到l的父基因位點沒有變化，基因位點1到k