【文章內(nèi)容簡介】 8 隱含地處理了 )( 3nO 個模式。遺傳算法有效處理的模式總數(shù)正比于群體數(shù) n的立方。 由遺傳算法的并行性可知，在遺傳操作中，盡管具有高階，長定義距的模式在交叉算子和變異算子的作用下遭到破壞，但遺傳算法在處理相對小數(shù)目的串時，仍然隱含地處理了大量的模式。 遺傳算法性能評估 遺傳算法的實現(xiàn)涉及到前述的五個要素，而每個要素又對應(yīng)不同的環(huán)境存在各種相應(yīng)的設(shè)計策略和方法。不同的策略和方法決定了各自的遺傳算法具有不同的性能和特性。因此，評估遺傳算法的性能對于研究和應(yīng)用遺傳算法是十分重要的。 遺傳算法的評估指標(biāo)大多采用 適應(yīng)度值。在沒有具體要求的情況下，一般采用各代中最優(yōu)個體的適應(yīng)度值和群體的平均適應(yīng)度值。 定量分析遺傳算法的測度包括離線性能 (offline performance)測度 n硼和在線性能 (on— line performance)測度。前者測量收斂性，后者測量動態(tài)性能。之所以使用離線和在線測度是為了強調(diào)兩者在應(yīng)用上的差別。一般來說，在離線應(yīng)用中，優(yōu)化問題的求解可以得到模擬，在一定的優(yōu)化進程停止準(zhǔn)則下，當(dāng)前最好的解可以被保存和利用；在在線應(yīng)用中，優(yōu)化問題的求解必須通過真正的實驗在線實現(xiàn)，其好處在于可以迅速地得到 較好的優(yōu)化結(jié)果。 在線性能評估準(zhǔn)則 設(shè)置 )(sXe 為環(huán)境 e策略 s的在線性能， )(tfe 為時刻 t或第 t代中相應(yīng)于環(huán)境 e的目標(biāo)函數(shù)或平均適應(yīng)度函數(shù)，則 )(sXe 可以表示為： ??? Tt ee tfTsX 1 )(1)( （ 2— 1） 上式表明，在線性能可以用從第一代到當(dāng)前代的優(yōu)化進程的平均值來表示。如果在線性能用平均適應(yīng)度來描述，則通過簡單計算第一代到當(dāng) 前代的各代平均適應(yīng)度值對世代數(shù)的平均值即可獲得在線性能。 離線性能評估準(zhǔn)則 設(shè) )(39。 sXe 為環(huán)境 e下策略 s的離線性能，則有： ??? Tt ee tfTsX 1 39。39。 )(1)( （ 2— 2） 華中科技大學(xué)文華學(xué)院畢業(yè)設(shè)計（論文 ） 9 其中 )}() . . .2(),1({)(39。 tfffb e s ttf eeee ? ， 上式表明，離線性能是特定時刻最佳性能的積累平均。具體來說，在進化過程中每進化一代就統(tǒng)計目前為止的各代中的最佳適應(yīng)度或最佳平均適應(yīng)度，并計算對進化代數(shù)的平均值。 遺傳算 法的特點 遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結(jié)構(gòu)對象的優(yōu)化過程中顯示出明顯的優(yōu)勢。它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法是基于一個單一的度量函數(shù) (評估函數(shù) )的梯度或較高次統(tǒng)計以產(chǎn)生一個確定性的試驗解序列； 遺傳算法不依賴于梯度信息， 而是通過模擬自然進化過程來搜索最優(yōu)解 (optimal solution)，它利用某種編碼技術(shù)，作用于染色體的數(shù)字串，模擬由這些串組成的群體的進化過程，遺傳算法通過有組織的，隨機的信息交換來重新組合那些適應(yīng)性好的串，生成新的串的群體。 遺傳算法的優(yōu)點 遺傳算法具有如下優(yōu)點 : 1．對可行解表示的廣泛性。遺傳算法的處理對象不是參數(shù)本身，而是在參數(shù)集進行了編碼的個體。此編碼操作，使得遺傳算法可直接對結(jié)構(gòu)對象 (集合、序列、矩陣、樹、圖、鏈和表 )進行操作。這一特點使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。 2．群體搜索特性。許多傳統(tǒng)的搜索方法都是單點搜索，這種點對點的搜索方法，對于多峰分布的搜索空間常常會陷入局部的某個單峰的極點．相反，遺傳算法采用的是同時處理群體中多個個體的方法，即同時對搜索空間中的多個解進行估。這一特點使 得遺傳算法具有較好的全局搜索性能，也使得遺傳算 法本身易于并行化。 3．不需要輔助信息。遺傳算法僅用適應(yīng)度函數(shù)的數(shù)值來評估基因個體，并在此基礎(chǔ)上進行遺傳操作。更重要的是，遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。由于限制條件的縮小，使得遺傳算法的應(yīng)用范圍大大擴展。 4．內(nèi)在啟發(fā)式隨機搜索的特性。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向。概率僅僅是作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化的解區(qū)域移動的。雖然看起來它是一種盲目的搜索方法，實際上它有明確的搜索 華中科技大學(xué)文華學(xué)院畢業(yè)設(shè)計（論文 ） 10 方向，具有內(nèi)在的并行搜索機制。 5．遺 傳算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)是不連續(xù)的，非規(guī)則的或有噪聲的情況下，也能以很大的概率找到全局最優(yōu)解。 6．遺傳算法采用自然進化機制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠地解決求解非常困難的問題。 7．遺傳算法固有的并行性和并行計算的能力。 8．遺傳算法具有可擴展性，易于同別的技術(shù)混合。 遺傳算法的不足之處 遺傳算法作為一種優(yōu)化方法，它存在自身的局限性： 1．編碼不規(guī)范及編碼存在表示的不準(zhǔn)確定。 2．單一的遺傳算法編碼不能全面地將優(yōu)化問題的約束表示出來?？紤]約束的一個方 法就是對不可行解采用閾值，這樣，計算時間必然增加。 3．遺傳算法容易出現(xiàn)過早收斂。 4．遺傳算法對算法的精度，可靠度計算復(fù)雜性等方面，還沒有有效的定量方法。應(yīng)重點注意的是，遺傳算法對給定的問題給出了大量可能的解答，并挑選最終的解答給用戶，要是一個特定問題沒有單個的解，例如 pareto最優(yōu)解系列中，就像多目標(biāo)優(yōu)化和日程安排案例中，遺傳算法將盡可能地用于識別可同時替換的解。 遺傳算法與傳統(tǒng)算法的比較 日前的最優(yōu)化問題，目標(biāo)函數(shù)和約束條件的種類繁多，有的是線性的，有的是非線性的，有的是連續(xù)的，有的 是離散的，有的是單峰值，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)化解是不可能的，也是不現(xiàn)實的。因而求出其近似最優(yōu)解或滿意解是人們主要研究的問題之一。 對于類似上述最優(yōu)化問題，求最優(yōu)解或近似最優(yōu)解的傳統(tǒng)方法主要有解析法，隨機法和窮舉法。解析法主要包括爬山法和間接法，隨機法主要包括導(dǎo)向隨機方法和盲目隨機方法。而窮舉法主要包括完全窮舉法，回溯法，動態(tài)規(guī)劃法和限界剪枝法。 此類問題可以利用遺傳算法求解。而對于求解此類問題，遺傳算法與一般傳統(tǒng)方法有著本質(zhì)的區(qū)別。 華中科技大學(xué)文華學(xué)院畢業(yè)設(shè)計（論文 ） 11 算法與啟發(fā)式算法的比較 啟發(fā)式算法是指通過尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，找到問題的一個最優(yōu)解或近似最優(yōu)解。該方法求解問題的效率較高，但是它對每一個所求的問題必須找出其特有的啟發(fā)式規(guī)則。這個啟發(fā)式規(guī)則一般無通用性，不適用于其它問題。但遺傳算法采用的不是確定性規(guī)則，而是強調(diào)利用概率轉(zhuǎn)換規(guī)則來引導(dǎo)搜索過程。 爬山法是直接法，梯度法和 Hessian法的通稱。爬山法首先在最優(yōu)解可能存在的地方選擇一個初始點，然后通過分析目標(biāo)函數(shù)的特性，由初始點移到一個新的點，然后再繼續(xù)這個過程。爬山法的 搜索過程是確定的，它通過產(chǎn)生一系列的點收斂到最優(yōu)解 (有時是局部最優(yōu)解 )，而遺傳算法的搜索過程是隨機的，它產(chǎn)生一系列隨機種群序列，二者的主要差別可以歸納如下 ： (1) 爬山法的初始點僅有一個，由決策者給出，遺傳算法的初始點有多個，是隨機產(chǎn)生的。 (2) 通過分析目標(biāo)函數(shù)的特性可知，爬山法上一個點產(chǎn)生一個新的點，遺傳算法通過遺傳操作，在當(dāng)前的種群中經(jīng)過較差，變異和選擇產(chǎn)生下一代種群。對同一優(yōu)化問題，遺傳算法所使用的機時比爬山法所花費的機時要多，但遺傳算法可以處理一些爬山法所不能解決的優(yōu)化問題。 舉法的比較 窮舉法就是對解空間的所有解進行搜索，但是通常的窮舉法并不是完全的窮舉法，即不是對所有解進行嘗試，而是有選擇地嘗試，如動態(tài)規(guī)劃法，限界剪枝法。對于特定的問題，窮舉法有時也表現(xiàn)出很好的特性。但一般情況下，對于完全窮舉法，方法簡單易行，但求解效率太低；對于如動態(tài)規(guī)劃法，限界剪枝法，則魯棒性不強，相比較而言，遺傳算法具有較高的搜索能力和較強的魯棒性。 與上述的搜索方法相比，盲目隨機搜索方法有所改進，但它的搜索效率仍然不高。一般而言，只有解在搜索空間中形成緊致分布 時，它的搜索才有效。而遺傳算法作為導(dǎo)向隨機搜索方法，是對一個被編碼的參數(shù)空間進行高效搜索。 蟻群算法 (Ant Colony Optimization， ACO)模擬螞蟻的群體行為，由 Dorigo等人提出。 hCO本質(zhì)上是一種基于群體的多代理算法。該方法的主要特點是：正反饋、分布式計算、與某種啟發(fā)式算法相結(jié)合，正反饋過程使得該方法能很快發(fā)現(xiàn)較好解；目前有學(xué)者嘗試將其應(yīng)用于電力系統(tǒng)規(guī)劃中但是還沒有很好地將規(guī)劃模型處理成適合于螞蟻算法求解的模型，系統(tǒng)規(guī)模增大時，難以求得高質(zhì)量的解。如何合理地將 規(guī)劃模型轉(zhuǎn)變成適合螞蟻算法的模型，有待人們進一步的研究。而遺傳算法的顯著優(yōu)點是可以同時搜索空間中的許多點，而不是一個點，因而能夠作到全局優(yōu)化；由于其搜索最優(yōu)解的過程是 華中科技大學(xué)文華學(xué)院畢業(yè)設(shè)計（論文 ） 12 有指導(dǎo)性的，避免了某些優(yōu)化算法的維數(shù)災(zāi)難問題。利用遺傳算法進行電力系統(tǒng)調(diào)度優(yōu)化規(guī)劃，可得出若干個最優(yōu)、次優(yōu)方案，供規(guī)劃人員根據(jù)實際情況進行決策選擇。 6．遺傳算法和模擬退火法 模擬退火法的最大特點是搜索中可以擺脫局部解，這是傳統(tǒng)的爬山法所不具備的。遺傳算法中的“選擇一操作是以和個體的適應(yīng)度有關(guān)的概率來進行的。因此，即使是適應(yīng)度低的個體也會有被選 擇的機會。在這一點上它同模擬退火法十分相似。顯然，通過在搜索過程中動態(tài)地控制選擇概率，遺傳算法可以實現(xiàn)模擬退火法中的溫度控制功能。 混沌優(yōu)化算法是近年來隨著混沌學(xué)科的發(fā)展而被提出來的另外一種新算法，它通過將優(yōu)化問題模型向混沌變量的映射，充分利用混沌變量在混沌運動中所具有的遍歷性，隨機性，規(guī)律性來尋找全局的最優(yōu)解。依據(jù)對混沌變量應(yīng)用方式的不同，混沌算法可以分為基于混沌序列的函數(shù)優(yōu)化方法與基于混沌神經(jīng)網(wǎng)絡(luò) (Chaotic Neural Network． CNN)的優(yōu)化算法．但由于混沌變 量的搜索空間狹窄，又需要將優(yōu)化模型歸一化處理，因此還很少有將混沌神經(jīng)網(wǎng)絡(luò)應(yīng)用于實際工程領(lǐng)域的模型。 改進的遺傳算法 遺傳算法的主要問題和解決方案 標(biāo)準(zhǔn)的遺傳算法是具有“生成 +檢測 的迭代過程的搜索算法。遺傳算法采用一種群體搜索策略和群體中個體之間的信息交換，搜索，不依賴于梯度信息。但標(biāo)準(zhǔn)遺傳算法存在一些不足，下面是標(biāo)準(zhǔn)遺傳算法中存在的主要問題和解決方案。 對早熟收斂和后期搜索遲鈍的解決方案：有條件的最佳保留機制；采用遺傳 —— 災(zāi)變算法 D帕：采用適應(yīng)度比例機制和個體濃度選擇機制的加權(quán)和 ：引入主群和屬群的概念；適應(yīng)度函數(shù)動態(tài)定標(biāo)：多種群并行進化及自適應(yīng)調(diào)整控制參數(shù)相結(jié)合的自適應(yīng)并行遺傳算法；對重要參數(shù)選擇采用自適應(yīng)變化而非固定不變。 為了改進簡單遺傳算法的實際計算性能，很多學(xué)者的改進工作也是分別從參數(shù)編碼，初始群體設(shè)定，適應(yīng)度函數(shù)標(biāo)定，遺傳操作算子，控制參數(shù)的選擇以及遺傳算法結(jié)構(gòu)等方面提出的。眾多學(xué)者一直致力于推動遺傳算法的發(fā)展，對編碼方式，控制參數(shù)的確定和交叉機理等進行了深入的研究，提出了各種變形的遺傳算法，其基本途徑概括起來主要有以下幾個方面： (1)改進遺傳算法的組成成分或使用技術(shù)， 如選用優(yōu)化控制參數(shù)，適合問題特性的編碼技術(shù)等。 華中科技大學(xué)文華學(xué)院畢業(yè)設(shè)計（論文 ） 13 (2)采用混合遺傳算法 (Hybrid Geic Algorithm)]8[ 。 (3)采用動態(tài)自適應(yīng)技術(shù)。在進化過程中調(diào)整算法控制參數(shù)和編碼精度。 (4)采用非標(biāo)準(zhǔn)的遺傳操作算子。 (5)采用并行算法。 3. 基于改進遺傳算法的 AGC機組優(yōu)化組合 傳統(tǒng)的機組組合模型 機組優(yōu)化組合問題包含了機組運行約束及常規(guī)的運行約束。在一個調(diào)度周期內(nèi)，根據(jù)負(fù)荷變化的曲線圖，分時段迸行計算。其數(shù)學(xué)模型的目標(biāo)函數(shù)為一個調(diào)度周期 內(nèi)發(fā)電廠煤費用總和最小，其約束包含功率平衡方程、經(jīng)濟運行要求和機組運行約束。假設(shè)系統(tǒng)中有 N臺可運行機組，各時段的總負(fù)荷為 dP ，機組的功率儲備為 rP ，并且假設(shè)電能損耗已經(jīng)被包括在總負(fù)荷以及 機組的功率儲備 中 ]10[ 。 目標(biāo)函數(shù) 要求系統(tǒng)在 T小時 段中各機組的總費用為最小，目標(biāo)函數(shù)可寫為 ? ?? ? ????TtNt itttiititit USUtPFPU 1 1 )1( ])()([),m in ( （ 31） 式中： itP —— 機組 i在時段 t的功率變量。 N—— 發(fā)電機組數(shù) )( itPF —— 第 i臺機組的發(fā)電費用，一般采用二次型，即 iitiitiiti cPbPaPF ??? 2)( 其中iii cba , 為機組 i的運行費用特性參數(shù) 。 T—— 機組的運行總 時間。 t—— 機組的運行時間參數(shù)。 itU —— 機組 i在時段 t時段內(nèi)的狀態(tài)，僅設(shè) 0， 1兩個值， itU =1表示運行態(tài)， itU =0表示停運狀態(tài)。 華中科技大學(xué)文華學(xué)院畢業(yè)設(shè)計（論文 ） 14 tS —— 機組啟動費用，它與機組所建立的數(shù)學(xué)模型有關(guān)分為兩類： a) 冷卻 啟動 機組從冷卻狀態(tài)啟動，啟動費用與停機時間 t的長短有