【文章內容簡介】 雜交（或稱交叉）(crossover)和變異(mutation)，從而產(chǎn)生出代表新的解集的下一代種群。這樣一代一代的不斷進化，最后收斂到一個最適應環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算法所涉及的六大要素：參數(shù)編碼、初始群體的產(chǎn)生、適應 度函數(shù)的設計、遺傳操作的設計、控制參數(shù)的設定以及算法終止條件。九、遺傳算法基本流程圖傳統(tǒng)遺傳算法（TGA）模擬自然界生物的雙親繁殖方式，主要利用交叉算子繁殖后代。傳統(tǒng)遺傳算法在采用非序號編碼（包括二進制編碼、實數(shù)編碼等）且所求解問題屬無約束優(yōu) 化問題時是有效的。對于組合優(yōu)化問題，如巡回旅行商（TSP）問題，使用序號編碼比非序號編碼更簡單、更直接，但序號編碼的染色體不能使用常規(guī)交叉算子，必須使用部分匹配交差PMX、順序交叉OX和循環(huán)交叉CX等特殊的交叉算子，而這些特殊的交叉算子遺傳操作復雜，計算效率不高，且缺乏理論基礎，這在很 大程度上限制了序號編碼遺傳算法的推廣應用。針對于傳統(tǒng)遺傳算法在求解組合優(yōu)化問題時的上述不足，提出了一種單親遺傳算法。單親遺傳算法主要采用序號編碼，不使用傳統(tǒng)遺傳算法的交叉算子，而代之以僅在一條染色體上操作的基因重組等遺傳算子，即單親遺傳算法只通過單個個體繁殖后代。單親遺傳算法也因此而得名。后來，在用遺傳算法求解火電廠機組優(yōu)化組合問題時，發(fā)現(xiàn)盡管這一問題可采取非序號編碼，但由于其約束條件很多，傳統(tǒng)遺傳算法的交叉算子的作用效率大為下降。因為當交叉算子作用于代表可行解的兩個個體時，產(chǎn)生的兩個新個體很可能不再代表可行解。因此，針對火電廠機組優(yōu)化組合問題提出了一種使用實數(shù)編碼的單親遺傳算法，取得了比傳統(tǒng)遺傳算法更好的效果。、單親遺傳算法的特點與傳統(tǒng)遺傳算法一樣，單親遺傳算法群體規(guī)模N的選擇對計算效率有著很大的影響。如果N太小,每遺傳迭代一次處理的圖式數(shù)量太少,容易導致算法收斂于局部最優(yōu)解；反之，如果N太大，每遺傳迭代一次的適應度計算時間大幅度增加,計算效率低下。本文通過分析 單單親遺傳算法在每一次遺傳操作時處理的有效圖式的數(shù)量，對單親遺傳算法的最優(yōu)群體規(guī)模進行研究單親遺傳算法取消了傳統(tǒng)遺傳算法的交叉算子,采取單親繁殖方式。跟傳統(tǒng)遺傳算法相比，單親遺傳算法遺傳操作簡單，容易在遺傳操作過程中處理約束條件，不要求初始群體具有多樣性，不存在“早熟”收斂問題，計算效率高，全局收斂性好。單親遺傳算法的研究對完善遺傳算法的理論基礎，有效地解決組合優(yōu)化問題和有約束優(yōu)化問題具有重要意義。單親遺傳算法與傳統(tǒng)遺傳算法的區(qū)別主要在產(chǎn)生新個體的方法上，傳統(tǒng)遺傳算法模擬自然界絕大多數(shù)生物的雙親繁殖方式，遺傳操作主要在兩個個體上進行；而單親遺傳算法模擬自然界少數(shù)生物的單親繁殖方式，遺傳操作只在一個個體上進行。眾所周知，傳統(tǒng)遺傳算法的交叉算子在群體中的個體都相同時是無效的，這就要求初始群體中的個體具有廣泛的多樣性，并且這種多樣性必須維持到遺傳迭代的完成。如果在進化過程中群體中的個體失去多樣性，則交叉算子不能產(chǎn)生新的個體，會發(fā)生所謂“早熟收斂”現(xiàn)象。單親遺傳算法的全部遺傳操作都在一個個體上進行，遺傳迭代的進行與群體的多樣性無關，不要求初始群體中的個體具有的多樣性，也不會發(fā)生“早熟收斂”現(xiàn)象。導致早熟的原因可以有以下幾種類型：A、群體規(guī)模 當群體規(guī)模太小時，造成有效等位基因先天缺失，不能保證有 效模式的正確傳播，使得群體進化不能按模式定理產(chǎn)生所預測的期望數(shù)量。B、 群體初始化 初始群體分布在編碼空間的局部區(qū)域，模式采樣誤差較大， 導致遺傳算法的搜索范圍受到限制。c)、選擇壓力 選擇壓力（最佳個體與最差個體被選擇的概率之比）太大，將 會導致當前種群中的最優(yōu)個體具有較高的復制數(shù)目，較差個體消亡速度過快，導 致群體多樣性迅速降低。D、變異概率 當變異概率較小時，群體多樣性下降速度較快，容易導致有效 基因的迅速丟失且難以恢復；當變異概率較大時，雖然群體多樣性可保持在較高 水平，但高階模式被破壞的概率隨之增大。E、 適應函數(shù)自身的性質 當適應函數(shù)高度非線性，染色體基因位之間高度相 關時，有效模式被破壞的可能性加大。針對上述原因，防止早熟一般有以下方法：A、 選擇合適的群體規(guī)模：在計算量允許的情況下，盡量選擇較大的群體規(guī)模，以保證群體的多樣性。B、保持合適的選擇壓力：當變異概率較小時，可采用中等壓力的選擇參數(shù)；當變異概率較大時，可采用較大壓力的選擇參數(shù)。C、適應度定標法：為使遺傳算法有效地工作，必須保持種群內染色體的多樣性和位串之間的競爭機制。在算法進行的早期，個體差別很大，為了防止超級個體的出現(xiàn)，保持種群的多樣性，此時必須降低個體之間適應度的差異，可對適應度采取收縮的操作；而到了后期，此時經(jīng)過進化，種群中的個體在適應度上都已經(jīng)很接近，從而導致了算法在后期搜索效率低下，就必須放大個體間適應度上的差異，可對個體適應度采取拉伸的操作，使得種群朝著良好的方向進化。D、參數(shù)適應性：遺傳算法的性能由在搜索空間進行的深度搜索和廣度搜索的 平衡決定。這種平衡受遺傳算法中的參數(shù)（包括種群規(guī)模、遺傳代數(shù)、交叉概率 和變異概率等）的影響。自適應是針對遺傳算法中參數(shù)配置能力不足提出來的。 Srinivaszai 提出了對交叉概率和變異概率進行算法動態(tài)自適應的思想，通過交叉概 率和變異概率動態(tài)自適應，能夠協(xié)調種群的多樣性和算法的收斂性之間的矛盾， 從而達到一個很良好的算法求解效果。Whiley 則考慮針對個體之間的海明距離 (Hamming Distance)來配置變異概率。E、多種群進化： 單純多群體：單純多群體遺傳算法的基本思想是多群體同時 進化，其中多群體之間不存在染色體位串的遷移和基因的交換，這一點與并行遺 傳算法不同。它要求每個子群體的進化獨立進行，群體之間互不干擾。協(xié)同多群體：實際優(yōu)化問題中的多峰搜索或多模態(tài)函數(shù)優(yōu)化問題，不僅要求在可行區(qū)域內尋找全局最優(yōu)解，而且需要找到多個全局最優(yōu)解和局部最優(yōu)解，這類問題一般用協(xié)同多群體遺傳算法求解較好。它要求多個群體相互協(xié)調，同時進化。如 Goldberg 和 Richardson于1987年提出的基于適應度值共享機制的小生境技術(niching technology)。、單親遺傳算法理論研究現(xiàn)狀早期的單親遺傳算法一般都采取序號編碼方式，通過多機多階段 Flowshop問題兩種不同編碼方式的比較，說明編碼方式的選擇對單親遺傳算法的計算效率 影響是很大的。對于同序基因數(shù)gc1 的組合優(yōu)化問題，應該盡量找到一種能使gc=1 的編碼方式，以降低串空間的維數(shù)，提高搜索效率。實數(shù)編碼單親遺傳算法的研究工作起步較晚，針對火電廠機組優(yōu)化組合問題提出了一種實數(shù)編碼方式，每條染色體中的每個基因代表一臺機組某一個時段內的出力，使染色體串長大大縮短，提高了搜索效率。單親遺傳算法遺傳算子的構造與編碼方式有關。序號編碼單親遺傳算法常用的遺傳算子可分為兩大類：基因重組算子和基因突變算子。基因重組算子包括基因換位、基因移位、 基因倒位等調整序號基因在染色體中相對位置的遺傳算子?；蛑亟M算子和基因突變算子 分別搜索Λe 和Λm 子空間，它們的遺傳操作功能明顯不同。如果單親遺傳算法采取 gc=1 的編碼方式，則不存在基因突變算子。序號編碼單親遺傳算法的每一種遺傳算子都可分為單點算子和多點算子。相應地有單點基因換位和多點基因換位、單點基因移位和多點基因移位、單點基因倒位和多點基因倒位、單點基因突變和多點基因突變等。多點遺傳算子對圖式的破壞作用太大，搜索效率不高，使用不多。但在遺傳迭代的后期，使用多點遺傳算子對防止算法收斂于局部最優(yōu)解是有好處的。實數(shù)編碼單親遺傳算法主要用于有約束的復雜工程優(yōu)化問題。因為需要在遺傳操作過程 中處理約束條件，遺傳算子的構造比較困難。針對火電廠機組優(yōu)化組合問題構造了幾種實數(shù)編碼遺傳算子，這些遺傳算子對其它問題不具有通用性。有的論文給出了單親遺傳算法的幾種常用選擇方式，并指出單親遺傳算法的全局收斂性和收斂速度與選擇方式有關。錦標賽選擇方式和父子競爭選擇方式不能保證算法的全局收斂 性，但有較快的收斂速度；按適應度比例選擇方式在引入了最優(yōu)保持操作后能保證算法的全 局收斂性，但收斂速度較慢。圖式定理是遺傳算法的重要理論基礎之一。對單親遺傳算法的圖式定理進行了分析研究，單親遺傳算法的遺傳算子處理圖式的能力與傳統(tǒng)遺傳算法的基本相當，單親遺傳算法具有與傳統(tǒng)遺傳算法類似的隱含并行性。單親遺傳算法的運行過程可以與傳統(tǒng)遺傳算法的完全相同，但先繁殖后選擇的運行方式，比先選擇后繁殖的運行的方式更適合于單親遺傳算法 。有的論文在假定上一代群體中的所有個體被選擇到下一代的概率都大于0時，對單親遺傳算法的全局收斂性進行了分析研究，指出單親遺傳算法的基因換位算子、基因移位算子、基因倒位算子和基因突變算子對串空間的搜索都具有遍歷性，單親遺傳算法在引入了最優(yōu)保持操作后是全局收斂的。因此單親遺傳算法是否全局收斂主要取決于選擇方式。有的論文分別基于圖式定理和 Markov 鏈對單親遺傳算法的計算效率進行了定性分析，從提高計算效率的角度，對單親遺傳算法遺傳算子的作用概率等遺傳控制參數(shù)的選取進行了 研究。單親遺傳算法計算效率的定量分析有待進一步研究。有的論文提出了一種多模態(tài)單親遺傳算法，對其收斂性進行了分析，并通過兩個典型函 數(shù)優(yōu)化問題驗證了這種算法的有效性。有的論文提出了一種基于單親遺傳算法和模糊 C均值算法的混合聚類算法。這種算法克 服了模糊 C均值算法的局部最優(yōu)問題以及采用普通遺傳算法聚類時搜索速度和聚類精度的矛盾。針對旅行商問題，對單親遺傳算法作了進一步改進。通過改進個體編碼方式， 壓縮了個體空間；通過對初始群體進行預處理，提高了初始群體中個體的平均適應度；通過 改進個體適應度函數(shù)的計算方法，減少了個體適應度的計算時間；通過對群體中個體的相似 性檢查而淘汰部分相同的個體，能保持群體中個體的多樣性。這些改進措施對提高算法的收 斂速度和算法的全局搜索能力具有重要意義。有的論文分別就單親遺傳算法和傳統(tǒng)遺傳算法的編碼方式、遺傳算子、運行過程、適值 計算等方面進行了比較研究，指出除了遺傳操作不同外，單親遺傳算法在編碼方式、運行過程、適值計算等方面都非常類似于傳統(tǒng)遺傳算法。單親遺傳算法的遺傳操作雖然全部在一個個體上進行，但單親遺傳算法的基因重組算子隱含了傳統(tǒng)序號編碼遺傳算法的交叉算子的功能，單親遺傳算法的子代個體也保留了父代個體的大部分遺傳特征，即單親遺傳算 法具有與傳統(tǒng)遺傳算法類似的進化機制。、單親遺傳算法的應用研究現(xiàn)狀討論了單親遺傳算法在列車占線問題中的應用，給出了仿真實驗結果，并將 實驗結果與傳統(tǒng)遺傳算法的進行了比較。仿真結果顯示單親遺傳算法具有明顯的優(yōu)越性。研究了單親遺傳算法在模式聚類問題中的應用，用單親遺傳算法求解模式聚類問題可 以使聚類結果完全不依賴于初始聚類中心。研究了單親遺傳算法在Flowshop 問題中的應用，給出了仿真實驗結果，從仿真結果可以看出單親遺傳算法能夠適應于較大規(guī) 模的生產(chǎn)調度問題的優(yōu)化。肖鵬等將單親遺傳算法應用于物流配送和車輛路徑問題中，也取得了良好的效果。將單親遺傳算法應用于火電廠機組優(yōu)化組合問題，并使用實數(shù)編碼，給出了一 個10臺機組的仿真實例。仿真結果顯示了算法的有效性。研究求解復雜工程優(yōu)化問題的實 數(shù)編碼單親遺傳算法對降低工業(yè)生產(chǎn)和管理成本，提高社會經(jīng)濟效益具有重要的意義。針對電力系統(tǒng)機組優(yōu)化組合問題，提出了一種基于單親遺傳算法基本思想的基因協(xié)同 變異遺傳算法。這種算法能同時解決機組的啟、停狀態(tài)組合和經(jīng)濟負荷分配問題。與常規(guī)遺 傳算法比較，實數(shù)編碼單親遺傳算法通過采用一個基因對應一個參數(shù)的實數(shù)編碼方式，壓縮了染色體串長，且無需解碼；通過采用單親繁殖方式，提高了遺傳算子的搜索效率，并能較方便地在遺傳操作過程中處理約束條件；通過在遺傳操作過程中實現(xiàn)基因協(xié)同變異，進一步提高了遺傳算子的搜索效率。 配電網(wǎng)絡規(guī)劃屬于非線性混合整數(shù)規(guī)劃問題，應用傳統(tǒng)數(shù)學優(yōu)化算法往往難以直接求解。針對目前應用廣泛的常規(guī)遺傳算法在求解該問題時存在的難以保證方案連通性 和輻射性的缺陷，提出了基于單親遺傳算法的配電網(wǎng)絡優(yōu)化規(guī)劃算法。基于整數(shù)編碼策略， 給出了配電網(wǎng)絡規(guī)劃中變量編碼的具體方法和迭代求解程序。該算法具有進化操作成功率高，求解配電網(wǎng)絡優(yōu)化規(guī)劃問題的效率高等優(yōu)點，同時可將簡化網(wǎng)架結構和選取導線截面結 合在一起，既可確保解的最優(yōu)性，又可減少工作量。仿真算例驗證了該方法的快速性和有效 性。該算法還適用于輻射型配電網(wǎng)絡的擴展規(guī)劃。針對油藏地質中復雜地層巖性劃分存在的模糊性和多解性，提出了一種基于 單親遺傳算法的模式聚類劃分復雜地層巖性的方法。該方法通過隱含傳統(tǒng)遺傳算法交叉算子 功能的基因換位等遺傳算子來實現(xiàn)進化操作，簡化了遺傳操作過程，同時避免了“早熟收斂” 問題。采用該方法對大慶油田 10 8 個地層樣本進行處理，總符合率達 %，表明該方法 可提高復雜巖性識別的精度。、單親遺傳算法的展望單親遺傳算法自誕生以來，其理論研究和應用研究取得了一定的進展?；旧闲纬蓡?親遺傳算法的理論基礎，應用研究也取得了很好的成績。但單親遺傳算法的理論體系尚不是 很完善，在工程實際中的應用也有待進一步推廣。單親遺傳算法的進一步研究工作可以在以 下幾個方面進行：單親遺傳算法新的遺傳算子的構造及新遺傳算子遍歷性的研究。 單親遺傳算法選擇方式的研究及選擇方式對算法全局收斂性和收斂速度的影響。 單親遺傳算法全局收斂性和收斂速度的深入研究，特別是收斂速度的定量分析。 單親遺傳算法運行機理的進一步研究。 單親遺傳算法在復雜工程優(yōu)化中的應用研究。 單親遺傳算法與其它優(yōu)化方法的綜合二、 混合單親遺傳算法 、算法模型簡介指派問題的標準形式（以人和事為例）：有n個人和n件事，已知第i個人做第j件事的費用為cij(i,j=1,2……n)，要確定人和事之間一一對應的指派方案，使完成這n件事的總費用最少。其數(shù)學模型為：指派問題的標準形式是01整數(shù)線性規(guī)劃問題，其中cij表示第i個人作第j件事的費用(i,j=1……n)，式（1）表示該指派方案消耗的總費用，式（2）表示每件事必有且只有一個人去做，式（3）表示每個人必做且只做一件事。因而指派問題有n!個可行解。 、新的遺傳算法、新的編碼