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