自適應遺傳算法

自適應遺傳算法(Adaptive Genetic Algorithm，AGA)是對基本遺傳算法的一種改進，它通過對遺傳參數的自適應調整，大大提高了遺傳算法的收斂精度，加快了收斂速度。

基本介紹

• 中文名：自適應遺傳算法
• 外文名：Adaptive genetic algorithm
• 所屬學科：IT
• 套用領域：程式設計

遺傳算法

編碼

編碼就是把自然問題描述為編碼的形式，生成編碼的原則是：所定編碼應當易於生成與所求問題相關的最小字元集。目前主要的編碼技術有：

• 一維染色體編碼；
• 多參數映射編碼；
• 可變染色體長度編碼等。

最初的編碼方式為二進制編碼，它是基於二進制串的，類似於生物染色體結構，各種遺傳操作易於實現，現在也經常用到，但是二進制編碼不能直接反映問題的固有結構特徵，個體長度大，占用計算機記憶體多，數值最佳化時精度不高，所以就產生了實數編碼和格雷碼編碼方法。實數編碼更方便、簡潔的描述了實際問題，在具體問題中，直接採用解空間的形式進行編碼，可在解的表現型上進行遺傳操作，精度高，適合於複雜的大空間搜尋。格雷碼是一種絕對編碼方式，典型的格雷碼是一種具有反射特性和循環特性的單步自補碼，它的循環、單步特性消除了遺傳算法在隨機取數時出現重大誤差的可能，使遺傳算法的隨機編碼的錯誤最小化，同時，格雷編碼便於反映所求問題的結構特徵，對於一些連續函式的最佳化問題，也可以改善遺傳運算局部搜尋能力差的缺點。

群體規模

對於種群的規模，一般是在初始階段設定好的，複雜程度不同的問題，相應的初始種群的設定也不同。種群規模設定要適中，太小的種群規模會使收斂速度過慢，過大的規模也會增加搜尋的難度，演化為枚舉搜尋。

適應度函式

適應度函式是評價個體適應環境的能力，在進行選擇操作時經常用到，它的選取是否恰當直接影響到遺傳算法的性能，所以就形成了很多計算適應度的函式，改進這些適應度函式是為了使適應度能更好的反映個體的優劣，使得適應度低的個體被淘汰，適應度高的個體被保留。自適應的適應度函式可以隨著種群代數的增加自適應的調整，在算法的開始階段，適應度差別較大，為了防止一些適應度較差的個體在一開始就丟失，可以通過改變適應度函式使得它們得以保留下來，另外，當種群趨於收斂時，適應度差別很小，這時為了加快收斂的速度，應對適應度進行調整，使得個體適應度差別增大，從而更快的收斂到全局最優解。常用的適應度變換方法有：線性變換、冪函式變換和指數變換。

另外，採用適應度結合了模擬退火的思想。選擇的作用是按某種方法從父代群體中選取一些將要進行交叉的個體，現在常用的選擇方法很多，它們大多有一個共同的特點，就是都是基於適應度的選擇，適應度大的個體被選中的機率就大，適應度小的個體被選中的機率就小。常用的選擇算法有適應度比例法、精英保留策略、聯賽選擇法等。另外，也可以將這些選擇算法混合使用，如今還出現了啟發式的搜尋選擇策略，這種策略是用每個個體所帶有的啟發信息來確定它被選中的機率。

交叉

交叉運算，是指對兩個相互配對的染色體依據交叉機率cp，按某種方式相互交換其部分基因，從而形成兩個新個體。交叉運算是遺傳算法區別於其它進化算法的重要特徵，它在遺傳算法中起關鍵作用，交叉操作應該產生儘可能多樣性的後代[38]。目前常用的交叉方法有：單點交叉（簡單交叉）、兩點交叉、多點交叉、均勻交叉、算術交叉等。

變異

所謂變異運算，是指依據變異機率mp將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新個體。遺傳算法中的變異運算是產生新個體的輔助方法，它增強了遺傳算法的局部搜尋能力，同時保持了種群的多樣性。交叉運算和變異運算相互配合，共同完成對搜尋空間的全局搜尋和局部搜尋。對於用二進制編碼符號串表示的個體，若需要進行變異操作的某一基因座上的基因值為0，則變異操作將其變為1；反之，若原有基因值為1，則變異操作將其變為0。對於用實數編碼串表示的個體，則需要對進行變異操作的某一基因座上的基因值進行改變，比如基因值是1.4，可以通過隨機方法重新生成一個基因值來替換原基因值，也可以採用別的生成方法重新生成一個基因值來替換原基因值。

自適應遺傳算法

自適應遺傳策略

自適應遺傳算法(Adaptive Genetic Algorithm，AGA)是對基本遺傳算法的一種改進，它通過對遺傳參數的自適應調整，大大提高了遺傳算法的收斂精度，加快了收斂速度。自適應遺傳算法在保持群體多樣性的同時，保證了遺傳算法的收斂性。自適應遺傳算法的遺傳參數是自適應的，提高了基本遺傳算法的收斂速度和收斂精度。如今大量改進算法根據生物進化特徵，更加形象的模擬生物進化，使算法能夠以較大機率收斂到最優解。為了提高遺傳算法的收斂速度、搜尋精度以及穩定性，自適應遺傳算法各個階段（編碼、計算流程、種群規模、種群初始化策略、GA運算元、終止條件等）的設計必須合理，這樣，許多改進的自適應遺傳算法就應運而生。自適應遺傳策略研究與設計可以分為微觀遺傳策略研究和巨觀遺傳策略研究兩部分。

1. 微觀遺傳策略：主要討論群體規模、遺傳運算元的形式和參數設計，及其對GA求解能力的影響。
2. 巨觀遺傳策略：主要討論關於通過GA流程的再設計，改變GA的巨觀特徵，或者以GA流程為基礎，引入其他算法構成混合GA，以期提高GA求解全局最優解的能力。下面我們討論改進遺傳算法的一些方法。

自適應群體策略

種群規模要視最佳化問題的具體特徵而定，一般的種群規模為幾十到幾百。現在，也有很多關於自適應種群規模研究的學術論文出現，比如徐曉華、陳俊、陳宏建所給出的可變種群規模的遺傳算法[39]，通過模擬人類進化過程中人口數量的增長規律，證明了他們的算法能得到較優的解，計算代價也較小。

自適應選擇策略

自適應的選擇策略可以不單單依靠個體適應度的由高到低的排序來進行選擇，它會根據遺傳算法的進化特徵自適應的選擇將要進入交叉操作的個體。比如在王寧的碩士論文中所提到的自適應選擇方法[40]，首先挑選出種群中的最小適應度函式值，然後將種群中的所有個體的適應度函式值都減去這個最小值，然後根據新的適應度函式值採用輪盤賭法進行選擇。這種策略在計算的過程中就能動態的改變每個串的適應度值。這樣，個體的生存環境改變，評判標準也應隨之發生變化。

自適應交叉策略

基本遺傳算法的交叉機率是固定的，自適應交叉機率是隨著進化過程的進行自適應調整的，在進化的開始階段，交叉機率要選的大一些，這樣的粗略搜尋過程有利於保持種群的多樣性，而在後期，則需要進行細緻搜尋，防止破化最優解，加快收斂速度。許多改進的算法都立足於恰當的利用廣泛搜尋和細緻搜尋來調整交叉機率，比如自適應算法可以利用分階段法，將種群進化過程分為幾個階段，每個階段的交叉機率上限和下限不同，一般都是採用從小到大的變化方式，還有的將交叉機率的計算公式改為餘弦自適應變化。不同個體交叉機率的選取直接影響到算法的收斂速度和收斂精度，所以交叉機率的選取也很重要。

自適應變異策略

自適應變異是變異機率依照種群的進化特徵而變化的過程。一般的變異機率都在0.01以內選取，變異機率過大，對解的破壞性也比較大，容易使得到的最優解丟失，變異機率太小，容易出現早熟現象。所以，自適應的變異機率一般採取從大到小的變化方式。這樣，在開始階段進行廣泛搜尋可以保持種群的多樣性，在將要結束時進行細緻搜尋可以防止最優解被破壞。另外，在最佳化過程中，多次進行從廣泛搜尋到細緻搜尋的操作，利用這種方法可以使得算法既能保證搜尋的全面性和精確性，也可以很快的跳出局部最優，從而更快更好地收斂到全局最優，經過實驗證明，這種變異方法與以往的自適應算法相比較，在收斂速度、收斂精度上都有很大的提高，尤其對於多峰函式更加有效。