【正文】 體質(zhì)量朝著優(yōu)良的方向發(fā)展 。由于遺傳算法是借鑒生物進化的思想 ， 所以 ， 遺傳算法仍然沿用生物學中的一些術(shù)語 。 2 染色體 ：它是遺傳算法中運行的最基本的單位 ， 是特定問題在算法中的表現(xiàn)形式 ，一般由二進制的數(shù)串所組成 ； 基因 ：它是染色體的最小組成單位 ， 在二進制數(shù)串中它由一個數(shù)位來表示 ； 基因片 ：多個基因構(gòu)成基因片 ； 種群 ：種群是由多個染色體構(gòu)成的集合 ， 它的數(shù)目稱之為種群規(guī)模 ； 適應度 ：適應度反映了染色體所蘊涵的問題解質(zhì)量的優(yōu)劣 ， 一般來說 ， 染色體的適應度是一個非負數(shù) ； 適應度函數(shù) ：染色體到適應度之間的映射關(guān)系 ； 選擇 ：遺傳算子之一 ， 是算法基于適應度對染色體進行優(yōu)勝劣汰的操作過程 ； 交叉 ：遺傳算子之一 ， 是算法產(chǎn)生新個體的途徑之一 ， 又稱之為基因重組 ； 變異 ：遺傳算子之一 ， 是算法產(chǎn)生新個體的途徑之一 ， 是小概率發(fā)生事件 。 遺傳算法所借鑒的生物學基礎就是生物的遺傳、變異和進化 。 遺傳 世間的生物從其父代繼承特性或性狀 ， 這種生命現(xiàn)象就稱為遺傳 。 生物的遺傳方式有以下三個： (1) 復制 生物的主要遺傳方式是復制 。 遺傳過程中 ， 父代的遺傳物質(zhì) DNA 被復制到子代 。 即細胞在分裂時 ， 遺傳物質(zhì) DNA 通過復制而轉(zhuǎn)移到新生的細胞中 ， 新細胞就繼承了舊細胞的基因 。 (2) 交叉 有性生殖生物在繁殖下一代時 ， 兩個同源染色體之間通過交叉而重組 ， 亦即在兩個染色體的某一相同位置處 DNA 被切斷 ， 其前后兩串分別交叉組合而形成兩個新的染色體 。 (3) 變異 在進行細胞復制時 ， 雖然概率很小 ， 僅僅有可能產(chǎn)生某些復制差錯 ， 從而使 DNA 發(fā)生某種變異 ， 產(chǎn)生出新的染色體 。 這些新的染色體表現(xiàn)出新的性狀 。 生物的不同品種都屬于變異 ， 在豐富多彩的生物界中 ， 蘊含著形形色色的變異現(xiàn)象 。 在這些變異現(xiàn)象中 ，有的僅僅是由于環(huán)境因素的影響造成的 ， 并 沒有引起生物體內(nèi)的遺傳物質(zhì)的變化 ， 因而不能夠遺傳下去 ， 屬于不遺傳的變異 。 有的變異現(xiàn)象是由于生殖細胞內(nèi)的遺傳物質(zhì)的改變引起的 ， 因而能夠遺傳給后代 ， 屬于可遺傳的變異 。 敵酋上的生物 ， 都是經(jīng)過長期進化而形成的 。 根據(jù)達爾文的自然選擇學說 ， 地球上的生物具有很強的繁殖能力 。 在繁殖過程中 ， 大多數(shù)生物通過遺傳 ， 使物種保持相似的 3 后代 ； 部分生物由于變異 ， 后代具有明顯差別 ， 甚至形成新物種 。 正是由于生物的不斷繁殖后代 ， 生物數(shù)目大量增加 ， 而自然界中生物賴以生存的資源卻是有限的 。 因此 ， 為了生存 ， 生物就需要競爭 。 生物在生存競爭中 ， 根據(jù)對 環(huán)境的適應能力 ， 適者生存 ， 不適者消亡 。 自然界中的生物 ， 就是根據(jù)這種優(yōu)勝劣汰的原則 ， 不斷地進行進化 。 遺傳算法的基本思想 遺傳算法實質(zhì)上是一種繁衍、監(jiān)測和評價的迭 代算法 。 它 一般要包含以下幾個處理步驟 :(1) 對問題的解進行編碼 ， 即用染色體表示問題的可能潛在解 ， 生成經(jīng)過編碼的初始種群 ， 適應度函數(shù)因優(yōu)化問題的目標函數(shù)而定 ； (2) 根據(jù)適應度大小挑選個體進行遺傳操作 ； (3) 按照適者生存和優(yōu)勝劣汰的原理逐代演化 ， 得到問題的最優(yōu)解或近似最優(yōu)解 。 每個個體在種群演化過程中都被評價優(yōu)劣并得到其適應度值 ， 個體在選擇 、 交叉以及變異算子的作用下向更高的適應度進化以達到尋求問題最優(yōu)解的目標 。 遺傳算法的構(gòu)成要素 遺傳算法中包含五個基本要素 ， 即染色體的編碼方法、適應度函數(shù)、遺傳算子、基本遺傳算法運行參數(shù)及約束條件的處理 。 每個要素對應不同的環(huán)境有各種相應的設計策略和方法 ， 而不同的策略和方法決定了相應的遺傳算法具有不同的特征 。 染色體編碼方法 遺傳算法不能直接處理問題空間的參數(shù) ， 而需要把問題的可行解從其解 空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間中 ， 這一轉(zhuǎn)換方法就稱為編碼 。 一般來說 ， 由于遺傳算法的魯棒性 ， 它對編碼 的要求并不苛刻 。 但由 于編碼的方法對于個體的染色體排列形式 ， 以及個體從搜索空間的基因型到解空間的表現(xiàn)型的轉(zhuǎn)換和遺傳算子的運算都有很大影響 ， 因此編碼方法在很大程度上決定了如何進行群體的遺傳進化運算以及遺傳進化運算的效率 。 針對一個具體應用問題 ， 如何設計一種完美的編碼方案是遺傳算法的應用難點 ， 而目前還沒有一套既嚴密又完整的指導理論及評價準則能幫我們設計編碼方案 。 對于實際應用問題 ， 仍須對編碼方法、選擇運算方法、交叉運算方法、變異運算方法、解碼方法統(tǒng)一考慮 ， 以尋求到一種對問題的描述最為方便、遺傳運算效率最高的編碼方案 。 4 在目前看來 ， 人們已經(jīng)提出了許多種不同的編碼方法 ， 主要有：二進制編碼、格雷碼和浮點數(shù)編碼 等等 [2]。 適應度函數(shù) 適應度函數(shù)指 為了體現(xiàn)染色體的適應能力 ， 引入了對問題中的每一個染色體都能進行度量的函數(shù) 。 遺傳算法在進化搜索中基本不利用外部信息 ， 僅以種群中每個個體的適應度函數(shù)值為依據(jù)進行搜索 ， 因此適應度函數(shù)的選取至關(guān)重要 。 遺傳算法常常將目標函數(shù)直接作為適應度函數(shù) ， 但由于在執(zhí)行選擇操作時 ， 它要按與個體適應度成正比的概率來決定當前群體中每個個體遺傳到下一代群體中的幾率 ， 而要正確計算此概率 ， 要求所有個體 的適應度值必須非負 [3]。 遺傳算子 (1) 選擇算子 選擇操作建立在對個體的適應度進行評價的基礎之上 ， 適應度較高的個體被遺傳到下一代群體中的概率較大 ； 適應度較低的個體被遺傳到下一代群體中的概率較小 ， 因而可以避免有效基因的損失 ， 使高性能的個體得以較大的概率生存 ， 從而提高全局收斂性和計算效率 。 最常用的選擇算子是比例選擇算子 ， 它是以正比于個體適應度值的概率來選擇相應的個體 。 另外還有 比較常用的選擇算子還有：最優(yōu)保存策略選擇、排序選擇和隨機聯(lián)賽選擇 。 (2) 交叉算子 遺傳算法中 ， 在交叉運算之前還必須 先對群體中的個體進行隨機配對 ， 然后在這些配對個體組中兩個個體之間進行交叉操作 。 交叉算子用于組合產(chǎn)生新的個體 ， 它要求對個體編碼串中的優(yōu)良模式不能有太多的破壞并且能有效的產(chǎn)生出一些較好的新個體模式 ， 以便在解空間中能進行有效搜索 ， 且保證對有效模式的破壞概率較小 。 最常用的交叉算子 有 單點交叉算子和算術(shù)交叉算子 。 (3) 變異算子 在生物的遺傳和進化過程中 ， 生物的某些基因偶爾會發(fā)生變異 ， 從而產(chǎn)生出新的個體 ， 雖然其概率比較小 ， 但對新物種的產(chǎn)生也是一個不可忽視的因素 。 模仿生物遺傳和 5 進化過程中的這種變異現(xiàn)象 ， 在遺傳算法中引 入了變異算子來產(chǎn)生新的個體 。 在遺傳運算過程中 ， 當交叉操作產(chǎn)生的后代適應度值不再進化且沒有達到最優(yōu)時 ，意味著算法陷入了早熟 。 早熟的根源在于有效基因的缺損 ， 變異算子在一定程度上克服了這種情況 ， 它可以改善遺傳算法的局部搜索能力 ， 增加種群的多樣性 。 基本遺傳算法運行參數(shù) 遺傳算法中有下面幾個參數(shù)對遺傳算法的運行有很大影響 ， 需認真選取 ， 它們是：個體編碼串長度 l、群體大小 M、 復制概率 Pr、 交叉概率 Pc、 變異概率 Pm、終止代數(shù) T[4]。 (1) 編碼串長度 l 使用二進制編碼表示個體時 ， 編碼串長度 l 的選取與 問題所要求的求解精度有關(guān) ；使用浮點數(shù)編碼來表示個體時 ， 編碼串長度 l 與決策變量的個數(shù) n 相等 ； 另外 ， 也可使用變長度的編碼來表示個體 。 (2) 群體大小 M 當 M 取值較小時 ， 可提高遺傳算法的運算速度 ， 但卻降低了群體的多樣性 ， 有可能會引起遺傳算法的早熟現(xiàn)象 ； 而當 M 取值較大時 ， 又會使得遺傳算法的運行效率降低 。一般建議的取值范圍是 20～ 100。 (3) 復制概率 Pr 復制操作建立在對個體的適應度進行評價的基礎之上 ， 適應度較高的個體被遺傳到下一代群體中的概率較大 ； 適應度較低的個體被遺傳到下一代群體中的概率較小 ， 復制概率不可 取的太大 ， 也不可以取的太小 。 (4) 交叉概率 Pc 交叉概率一般取值較大 。 但如果太大 ， 它會破壞群體中的優(yōu)良模式 ， 對進化運算不利 。 一般建議的取值范圍是 ～ 。 另外 ， 也可使用自適應的思想來確定交叉概率Pc。 (5) 變異概率 Pm 如果變異概率 Pm 取值太大 ， 則容易破壞群體中的優(yōu)良模式 ， 使得遺傳算法的搜索趨于隨機性 ； 如果取值過小 ， 則它產(chǎn)生新個體和抑制早熟的能力會較差 。 一般建議的取值范圍是 ～ 。 另外也可使用自適應的思想來確定變異概率 ， 如取 Pm 與其上一代群體間的海明距離成反比 ， 其結(jié)果會有效地維 持群體的多樣性 。 6 (6) 終止代數(shù) T 終止代數(shù) T 是表示遺傳算法運行結(jié)束條件的一個參數(shù) ， 一般建議的取值范圍是 100～500。 至于遺傳算法的終止條件 ， 還可以利用別的判定準則 。 遺傳算法的特點 遺傳算法利用了生物進化和遺傳的基本思想 ， 所以它與許多傳統(tǒng)優(yōu)化算法的特點不同 ， 可以充分的縮短搜索時間 。 傳統(tǒng)的優(yōu)化方法主要有三種 :枚舉法、啟發(fā)式算法和搜索算法 。 (1) 枚舉法 枚舉法是指枚舉出可行解集合內(nèi)的所有可行解 ， 以求得精確的最優(yōu)解 。 對于連續(xù)的函數(shù) ， 該方法要求先對其進行離散化處理 ， 這樣就有可能產(chǎn)生離散誤差而永遠達 不到最優(yōu)解 。 但是當枚舉空間比較大時 ， 該方法的求解效率比較低 ， 有時甚至在目前最先進的計算工具上都無法求解 。 (2) 啟發(fā)式算法 啟發(fā)式算法是指尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則 ， 以找到一個最優(yōu)解或近似最優(yōu)解 。 該方法的求解效率雖然比較高 ， 但是對于每一個需要求解的問題都必須找出其特有的啟發(fā)式規(guī)則 ， 這個啟發(fā)式規(guī)則沒有通用性 ， 不適合于所有的問題 。 (3) 搜索算法 搜索算法是指尋求一種算法 ， 能在可行解集合的一個子集內(nèi)進行搜索操作 ， 以找到問題的最優(yōu)解或者近似最優(yōu)解 。 該方法雖然保證不了一定能夠得到問題的最優(yōu)解 ， 但是如果適當 的利用一些啟發(fā)知識 ， 就可在近似解的質(zhì)量和求解效率上達到一種較好的平衡 。 而遺傳算法既是一種自然進化系統(tǒng)的計算模型 ， 也是一種通用的求解優(yōu)化問題的適應性搜索方法 。 隨著問題種類的不同以及問題規(guī)模的擴大 ， 要尋求一種能以有限的代價來解決搜索和優(yōu)化的通用方法 ， 遺傳算法正是提供了一種有效的途徑 ， 它不同于傳統(tǒng)的優(yōu)化方法 ， 它具備的特點主要有以下幾個方面 : (1) 遺傳算法采用群體搜索尋找最優(yōu)解 ， 而不是從單個個體搜索尋找最優(yōu)解 。 搜索軌道有多條 ， 而非單條 ， 覆蓋面大 ， 利于全局擇優(yōu) 。 這是遺傳算法與傳統(tǒng)優(yōu)化算法的最大區(qū)別 ， 傳統(tǒng)優(yōu)化算法 是從單個個體搜索尋找最優(yōu)解 ， 效率比較低 。 (2) 遺傳算法求解時利用適應度函數(shù)值信息 ， 并不需要問題導數(shù)等與問題直接相關(guān)的信息 。 所以說在所定義的函數(shù)不連續(xù)、多峰或不可微的情況下 ， 也能以很大的概率收斂 7 到全局最優(yōu)解 。 (3) 遺傳算法是以決策變量的編碼作為運算對象 。 在優(yōu)化過程中借鑒生物學中染色體和基因等概念 ， 模擬自然界中生物的遺傳和進化等機理 ， 應用遺傳操作 ， 可方便求解無數(shù)值概念或很難有數(shù)值概念的優(yōu)化問題 ， 這樣的話 ， 遺傳算法就克服了非數(shù)值變量的操作 。 (4) 遺傳算法有極強的容錯能力 。 遺傳算法的初始解集本身就帶有大 量與最優(yōu)解相差甚遠的信息 ， 通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的解 ， 這是一個強烈的濾波過程 。 并且是一個并行濾波機制 。 因此 ， 遺傳算法有很高的容錯能力 ， 因為它就相當預先就進行了運算 ， 或則說在內(nèi)部就進行了運算 ， 大大增加了運算的效率 。 (5) 遺傳算法使用概率搜索技術(shù) 。 它屬于一種自適應概率搜索技術(shù) ， 其選擇、交叉、變異等運算都是以一定的概率進行的 ， 增加了其搜索過程的靈活性 。 實踐和理論證明了在一定條件下遺傳算法總是以概率 1 收斂于問題的最優(yōu)解 。 (6) 遺傳算法具有隱含的并行性 。 并行性是指兩個或多個事件在同 一時刻發(fā)生 ， 這樣就大大增加了運算的速度 。 遺傳算法的基本模型 (1) 將問題的解表示為編碼串（生物學術(shù)語稱為染色體） ， 每一碼串代表問題的一個可行解 。 (2) 隨機產(chǎn)生一組串長為 m 的初始群體 ， 該群體就是問題的一個可行解的集合 。 (3) 分別將編碼串譯碼成尋優(yōu)參數(shù) ， 計算對應的目標函數(shù)并變換為適應值 。 (4) 根據(jù)碼串個體適應值的高低 ， 執(zhí)行應用復制、交換和變異算子產(chǎn)生下一代群體 。 (5) 返回步驟 3， 直到滿足停止準則為止 。 這樣 ， 反復執(zhí)行步驟 3 到步驟 5， 使碼串群體一代代不斷進化 ， 最后搜索到最適應問題的個體 ， 求得問題的最優(yōu)解 ， 其流程圖如圖 1 所示 。 8 開 始結(jié) 束產(chǎn) 生 初 始 群 體計 算 個 體 適 應 度適 應 值 高 的 個 體執(zhí) 行 復 制選 擇 、 交 叉 、 變 異輸 出 結(jié) 果是 否 滿 足 停 止 準 則是否 圖 1 遺傳算法流程圖 遺傳算法的應用