遺傳算法的原理及組成淺析

金天坤 高 揚

（大慶師范學院 數學科學學院，黑龍江 大慶 163712）

遺傳算法(GA)是一種宏觀意義下的仿生算法，它模擬的機制是一切生命智能的產生與進化過程。作為一種廣為應用的、高效的隨機搜索與優化方法，它對模型的表達式沒有特定的要求，如目標函數用約束函數的連續性、可微性等函數解析性質的限制，還具有全局優化性、穩健性與可操作的簡單性等優點。

1 遺傳算法的主要步驟及

遺傳算法操作的是一群編碼化的可行解，稱作種群p（t）。它通過種群的更新與迭代來搜索全局最優解。種群的迭代是通過選擇、雜交和變異等具有生物意義的遺傳算子來實現的。在算法中，進化過程是通過一代群體p（t）向下一代群體p（t+1）的演化完成的,每一代群體由若干個個體組成，每個個體稱為一個染色體，而每個染色體是一系基因組成的基因串。每個染色體由于其中所含基因排列方式的不同而表現出不同的性能[1]。

算法在整個優化過程中的遺傳操作是隨機的，但它所呈現出的特性并不是完全隨機的搜索，它能有效的利用歷史信息來推測下一代的期望性能有所提高的尋優點集,這樣反復進行,最后收斂到一個最優解。

2 遺傳算法的組成

遺傳算法主要由幾個部分組成:編碼方式、適應度函數、遺傳操作、算法終止條件。要利用遺傳算法成功的解決優化問題,每個部分的設計都非常關鍵。

2.1 編碼

編碼原理遺傳算法不是對所求問題的實際優化變量直接操作，而是對表示可行解的遺傳編碼（即個體)作遺傳操作。因此遺傳算法中在進行搜索之前需要把解空間的可行解轉換為搜索空間的基因型結構，這些串結構數據的不同組合便構成了不同的點。編碼問題實際上是問題空間到表示空間的映射問題。

一個好的編碼方法，有可能會使得交叉運算、變異運算等遺傳操作可以簡單地實現和執行[2]。

通常的編碼方法包括:①二進制編碼方法；②格雷碼編碼方法；③浮點數編碼方法。

符號編碼方法:①多參數級聯編碼方法；②多參數交叉編碼方法。

2.2 適應度函數的設計

從數學角度看,遺傳算法實質上是一種溉率性捜索算法。但它也具有一定的智能特怔。遺傳算法是在適應度函數的指導下進行搜索。而不是窮舉式的全面搜索。適應度函數評估是選擇操作的依據。各個體適應度函數值的大小決定了它們是繼續繁衍還是消亡。相當于是自然界中各生物對環境的適應能力的大小。通常，適應度大的個體具有更適應環境的基因結構。再通過基因重組和基因突變等遺傳操作，就可能產生更適應環境的后代。改變種群內部結構的操怍皆通過適應度加以控制。適應度函數的選取直接影響到遺傳的收斂性及收斂速度。

2.2 遺傳操作

基本遺傳搡作包括:選擇、交叉、變異。

1）選擇。選擇操作決定如何從當前種群中選取個體作為產生下一代種群的父代個體。不同的選擇策略將導致不同的選擇壓力，即最佳個體選中的概率與平均中概率的比值。但也較容易出現過早收斂現象；較小的選擇壓力能使種群保持足夠的多樣性。從而增大算法收斂到全局最優的概率,但算法收斂速度一般較慢。

常用的選擇方法有:

①基于比例的適應度分配(proportional fitness assignment)方法

在現代社會的新形勢下，森林保護工作的重要性不言而喻。面對森林保護所帶來的巨大利益，我們更應該堅定信心，努力做好森林保護工作，讓森林發揮出巨大的作用。并且我們還要隨時關注森林保護過程中存在的問題，并且要對這些問題提出相應的解決措施，還要注意讓森林保護工作落到實處，真正的為我國的環境保護做出相應的貢獻。

基干適應度比例的選擇方法利用比例于各個體適應的概率決定其子孫的遺留可能性。包括繁殖池選擇（breeding pool selection）、輪盤賭選擇（roulette wheel selection）等方法。

②基于排名的適應度分配(rank-based fitness assignment)方法

基于排名的選擇方法包括線性排名選擇和非線性排名選擇等方法，是將種群中的個體按目標值進行排序。適應度僅僅取決于個體在種群中的序位,而不是實際的目標值。

常用選擇方法還包括局部選擇、截斷選擇、錦標賽選擇、穩態繁殖等。

2）交叉

在生物的自然進化過程中，兩個同源染色體通過交叉而重組形成新的染色體，從而產生出新的個體或物種。交配重組是生物遺傳和進化過程中的一個主要壞節。模仿這個環節,在遺傳算法中也使用交叉算子來產生新的個體。

常用的幾種交叉算子有：

②二進制交叉；單點交叉；多點交叉；均勻交叉；洗牌交叉；縮小代理交叉。

3）變異

變異是遺傳算法中保持生物多樣性的一個重要途徑。它以一定概率選擇某一基因座,通過改變該基因座的基因值來獲取新個體。

算法中的適應值函數要求是非負的，而一般優化問題的目標函數并不滿足這個條件。常用的實現變異的適應度變換有以下三種[3]：

（1）線性尺度變換。假定J是原適應度度量。J′是變換后新的適應度置。 則線性尺度變換的變換公式是 J′（A)=aJ（A）+β，?A∈H

這里α是縮放因子，β是平移參數，H為所有個體構成的個體空間。其變換效果取決于對參數α，β的選取。這兩個參數的選取必須滿足兩個條件:第一、平均適應值等于原平均適應值Jmg；第二,新適應度度置的最大值是頃平均值的指定倍數,即Ji-mg=cJmg,其中C一般取為2。

（2）乘幕尺度變換。 變換公式為：J′=aJ（A）+β，?A∈HL

即新的適應度是原適應度的某個指定乘幕。幕指數K與變換目的及所求解的問題有關。

（3）指數尺度變換換公式為：J′=aJ（A）+β，?A∈HL

指數比例既可以讓非常好的個體保持較多的復制機會，同時又限制了其復制數目以免它很快的控制整個群體。

3遺傳算法的不足及改進

通過分析，可以看出在用遺傳算法進行路徑規劃時，隨機產生初始種群，為了避免陷人局部極值點，種群數量要達到 一定的規模。但種群規模大會導致搜索空間較大，刪除冗余個體的能力較差，大大影響路徑規劃的速度。特別在環境較為復 雜的情形下，這種缺點就更加明顯。

為了更好地發揮遺傳算法的作用，眾多學者從各方面對算法進行深人研究和討論，目前的改進策略大致可以分為以下兩方面[4]：

（1）改進遺傳算法的各組成部分。如:設計新的編碼方式、動態的、自適應的參數操作、新奇的遺傳操作等，來進一步改 善算法的性能(如:收斂速度慢、早熟、易陷入局部最優解等)。

（2）由于遺傳算法的操作簡單，較容易與其他方法結合,實驗研究表明這種改進相對是比較有效的。如:為克服早熟等缺陷，提出與禁搜索（Tabu search)結合，poths提出基于遷移和人工選擇的遺傳算法；為解決局部優的問題，遺傳算法分別與模糊集（Fuzzy set)、與混沌（Chaos)結合、與單純形、與爬出法、神經網絡、正交設計、免疫等結合來不斷優化算法。

在問題越來越復雜化的今天，遺傳算法也應與時倶進，只有通過不同的方式來對算法的結構、參數、操作不斷改進和 提高，才能設計高效的遺傳算法，滿足現代社會的需要。

［1］張文修，梁怡.遺傳算法的數學基礎[M].西安：西安交通大學出版社，2000.

［2］張曉績，方浩，戴冠中.遺傳算法的編碼機制研究[J].信息與控制 ，1997，26（2)：134-139.

［3］周浦城，洪炳鎮，楊敬輝.基于遺傳算法的移動機器人路徑規劃方法[J].哈爾濱工業大學學報，2004，36(7)：880-883.

［4］林銼云，董家禮.多目標優化的方法與理論[M].吉林：吉林教育出版社，1992.