【文章內容簡介】 程的概念，其基本思想是 :采用樹型結構表示計算機程序，運用遺傳算法的思想，通過自動生成計算機程序來解決問題。雖然遺 傳編程的理論尚未成熱，應用也有一些限制，但它已成功地應用于人工智能、機器學習等領域。目前公開的遺傳編程實驗系統(tǒng)有十多個。 （ 9）機器學習 學習能力是高級自適應系統(tǒng)所具備的能力之一，基于遺傳算法的機器學習，特別是分類器系統(tǒng)，在很多領域中都得到了應用。例如，遺傳算法被用于學習模糊控制規(guī)則，利用遺傳算法來學習隸屬度函數(shù)，從而更好地改進了模糊系統(tǒng)的性能；基于遺傳算法的機器學習可用來調整人工神經網絡的連接權，也可用于人工神經網絡結構優(yōu)化設計；分類器系統(tǒng)也在學習式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。 [9] （ 10）數(shù)據(jù)挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應用價值的知識和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應用遺傳算法在數(shù)據(jù)庫中進行搜索，對隨機產生的一組規(guī)則進行進化 .直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進行了數(shù)據(jù)挖掘實驗，結果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一。 遺傳算法發(fā)展 方向 遺傳算法發(fā)展方向其實就是和其他方法結合優(yōu)化問題，單方面改進遺傳算法的各種算子不能取得明顯進展。遺傳算法以其基本思想簡單、便于實現(xiàn)和并行搜索的優(yōu)點贏得了眾多學者和各種工程人員的青睞，是目前應用最廣的優(yōu)化搜索算法之一。但遺傳算法存在收斂速度慢和易于陷入局部最優(yōu)的問題，在需要優(yōu)化的參數(shù)較多時，更凸現(xiàn)了遺傳算法的不足。遺傳算法如何提高遺傳算法跳出局部最優(yōu)的能力和如何提高遺傳算法的收斂速度成為近年來遺傳算法的研究熱點。許多學者從不同的角度對遺傳算法進行了改進，使遺傳算法的尋優(yōu)能力有了不同程度的提高。和其它方法結 合的遺傳算法才有生命力。目前，對遺傳算法的研究主要集中在數(shù)學基礎、各環(huán)節(jié)的實現(xiàn)方式以及與其他算法的結合方面。其中，尤以遺傳算法與其他算法相結合方面的研究最為引人關注。由于遺傳算法具有開放式的結構，與問題的關聯(lián)性不大，很容易和其他算法進行結合，所以融合了其他的算法思想和遺傳算法思想的混合遺傳算法成了目前改進遺傳算法研究的一個重要方向?，F(xiàn)將比較常見的混合遺傳算法介紹如下。 （ 1）模擬退火遺傳算法 模擬退火算法的基本思想是通過模擬高溫物體退火過程的方法來找到優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解。從統(tǒng)計物理學的觀點看 ，隨著溫度的降低，物質的能量將逐漸趨近于一個較低的狀態(tài)，并最終達到某種平衡。遺傳算法的局部搜索能力較差，但把握搜索過程總體的能力較強；而模擬退火算法具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解，但它卻對整個搜索空間的了解不多，不便于使搜索過程進入最有希望的搜索區(qū)域，從而使得模擬退火算法的運算效率不高。但如果將遺傳算法和模擬退火算法相結合，互相取長補短，則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法。目前，已有許多學者將退火機制引入到遺傳操作中，使遺傳操作產生優(yōu)良個體的概率增加，并使遺傳算法的尋優(yōu)能力有 了明顯的提高。 （ 2）免疫遺傳算法 人工免疫算法受生物免疫系統(tǒng)原理的啟發(fā)，針對求解問題特征進行人工疫苗接種，可充分利用問題本身的信息，和遺傳算法結合時，遺傳算法的全局搜索能力及免疫算法的局部優(yōu)化相配合，可大大提高搜索效率。我們可以通過注射疫苗的方法來減少遺傳操作的盲目性，加強遺傳算法收斂性能，多次的測試結果證明了該改進方法的有效性。 [4] （ 3）小生境遺傳算法 生物學上，小生境指在特定環(huán)境中的一種組織功能，它將每一代個體劃分為若干類，每個類中選出若干適應度較大的個體作為一個類的優(yōu)秀代表，組成一個新種群，再在 同一種群中以及不同種群之間進行雜交、變異，產生新一代個體群，同時采用“預選擇”機制或排擠機制或共享機制完成選擇操作?！敖饪臻g”中峰周圍的子空間中的個體具有相對獨立生長繁衍的特性。常用的小生境遺傳算法大多在對群體進行選擇操作前，計算個體之間的海明距離，如小于事先設定值，則對“適應值”低的個體處以罰函數(shù)，降低其適應值。這樣可以保護解的多樣性，也可以避免大量重復的解充斥整個解空間。用小生境思想來實現(xiàn)遺傳算法的選擇操作，使遺傳算法的全局尋優(yōu)能力得到了明顯提高。 （ 4）模糊遺傳算法 模糊遺傳算法，即融合模糊優(yōu)化設計思 想的遺傳算法，它把模糊優(yōu)化和遺傳算法優(yōu)化結合起來，構成一種混合優(yōu)化的設計方法。其目的是利用模糊優(yōu)化設計的優(yōu)點，克服一般遺傳算法優(yōu)化設計存在的不足，從而使得系統(tǒng)的優(yōu)化設計更靈活、方便，取得好的設計效果。首先，在模糊遺傳算法中引入“論域”的概念。在這里，“論域”即指用隸屬函數(shù)來表示遺傳算法的優(yōu)化過程中所采用的約束條件的區(qū)間范圍。用隸屬函數(shù)來表示遺傳算法的約束條件，以使約束條件能夠更容易得到表達，又能夠保證遺傳子代的選擇中能夠擁有更廣泛的群體組成。其次，在模糊遺傳算法中，采用權變理論中的以變應變的思想。模糊遺傳算 法運用模糊控制的思想來自適應改變遺傳算法的種群規(guī)模、交叉概率、變異概率、適應度函數(shù)以及控制策略等。 （ 5）混沌遺傳算法 混沌是自然界廣泛存在的一種非線性現(xiàn)象，它充分體現(xiàn)了系統(tǒng)的復雜性?；煦邕\動具有類似隨機變量的雜亂表現(xiàn)，具有隨機性；“混沌”能在一定范圍內按其自身特性不重復地歷經所有狀態(tài)，具有遍歷性；初值條件極其微弱的變化會引起混沌系統(tǒng)行為的巨大變化，具有對初始條件的極度敏感性。混沌運動的上述性質作為避免陷入局部極小的優(yōu)化搜索機制，恰好可以彌補遺傳算法易陷入局部最優(yōu)、收斂速度慢的缺陷?？梢岳没煦绲谋闅v性產生 初始種群，也可以運用混沌的遍歷性對優(yōu)良個體進行變異操作，混沌遺傳算法增強了遺傳算法的全局尋優(yōu)能力。 （ 6）量子遺傳算法 量子遺傳算法是量子計算思想與遺傳算法結合的產物。與遺傳算法類似，它也是一個產生―檢驗的過程，但其實現(xiàn)同標準遺傳算法不一樣。在表達方式上，量子遺傳算法將量子的態(tài)矢量表述引入染色體編碼；在演化機制上，它利用量子門實現(xiàn)染色體演化。這些區(qū)別，使得量子遺傳算法表現(xiàn)出比標準遺傳算法更好的種群多樣性、更強的全局搜索能力和更快的收斂速度。還有其他的算法已被引入到遺傳算法中來（如禁忌―并行 ，分層），在此， 就不再過多介紹。遺傳算法與其他算法和理論的結合已經成為改進遺傳算法的一個非常有效的手段。 隨著人們對遺傳算法研究的不斷深入，可以預見，會有更多的理論和方法被引入到遺傳算法中來。相信通過遺傳算法與其他算法的結合以及自身實現(xiàn)方式的不斷改進，在不久的將來，遺傳算法的優(yōu)化能力會有一個質的提高 . 第二章．遺傳算法的基本原理和實現(xiàn)技術 前一章講了遺傳算法的原理，概念，這一章就具體將編碼。 模式定理 （ 1） 模式 模式（ schema）是一個描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。例如二值字符集 0， 1 ，由此可以產生通常的 0,1 字符串?，F(xiàn)在增加一個通配符“ *” ，“ *”既可以被當作“ 0”，又可以被當作“ 1”。這樣二值字符集 0,1 就可擴展成三值字符集 0， 1， * 。 [4] 定義 基于三值字符集 0， 1， * 所產生的能描述具有某些結構相似的 0、 1 字符串稱作模式。 引入模式概念并不是僅僅為了描述上的方便。在引入模式概念前，我們看到的遺傳算法是：在某一代中， N 個互不相同的串在選擇、交叉、變異等遺傳算子的作用下產生下一代的 N 個新的互不相同的串。那么，兩代之間 究竟保留了什么性質，破壞了什么性質，我們無法知到，因為我們所看到的“串”都是相互獨立的，互不聯(lián)系的。在引入模式概念后，我們看到的一個串實際上隱含著多個模式，一個模式可以隱含在多個串中，不同的“串”之間通過模式而相互聯(lián)系。遺傳算法中串的運算實質上是模式的運算。因此通過分析模式在遺傳操作下的變化，就可以了解什么性質被延續(xù)，什么性質被丟棄，從而把握遺傳算法的實質，這正是模式定理所要揭示的內容。 （ 2） 模式定理 首先定義兩個重要的概念：模式階（ schema order）和定義長度（ schema defining length）。 定義 模式 H 中確定位置的個數(shù)稱作該模式的模式階，記作 O H 。[2] 比如模式 110*10*的階為 5，而模式 0*****的階為 1。顯然，一個模式的“階數(shù)”越高，其樣本數(shù)就越少，因而確定性越高。 但是，模式的“階”并不能反映模式的所有性質。既使具有“同階”的模式，在遺傳操作下，也會有著不同的性質。為此，在引入定義長度的概念。 定義 模式 H 中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距離或定義長度，記作 δ H 。比如模式 110*10*的定義長度為 4，而模式 0*****定義長度 0。 【定義】（模式定理） 在遺傳算子選擇，交叉和變異的作用下，具有低階、短的定義長度，并且平均適應度高于群體平均適應度的模式將按“指數(shù)級”增長。[3] 模式定理是遺傳算法的理論基礎。 遺傳算法主要通過遺傳操作對群體中具有某種結構形式的個體施加結構重組處理，從而不斷的搜索出群體中個體間的結構相似性。所以遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。這一操作就是編碼。更一般性的定義為：由問題空間向遺傳算法 空間的映射稱作編碼（ Encoding）。反之，由遺傳算法空間向問題空間的映射稱作譯碼（ Decoding）。 編碼技術 編碼的方式有多種，下面作簡要的介紹： 一維染色體編碼 所謂一維染色體編碼是指搜索空間的參數(shù)轉換到遺傳空間后，其相應的基因呈一維排列構成染色體。一維染色體編碼中最常用的符號集是二值符號集 0,1 ，基于此符號集的個體呈“二值碼串”。 二維染色體編碼 許多應用場合里，問題的解呈二維或多維表示。此時若采用一維染色體編碼就顯得不方便了。例如圖像恢復處理是指把一個被干擾的圖像盡量恢復到它的原始面目。用遺傳算法完成此任務，一個染色體就代表一個圖像。若圖像為二值圖像，則染色體就可表示成二維的二值數(shù)組。 多參數(shù)映射編碼 多參數(shù)映射編碼的基本思想是把每個參數(shù)先進行二值編碼得到子串，再把這些子串連成一個完整的染色體。 樹結構編碼 在實際應用中，許多問題本身可以采用結構描述，比如，人工智能中知識獲取和提煉中采用的語義網絡，神經網絡中神經元連接狀態(tài)圖表示等。雖然此時也可以把“圖結構”編碼為一維染色體來處理，但是“圖結構”特性不能在適應度評估中充分體現(xiàn)出來。作為對策，可以直接把問題的結構表示為染色體來處理，從 而省去編碼和譯碼的操作。 群體設定 群體的設定可以采取下面的策略：根據(jù)問題固有知識，設法把握最優(yōu)解所占空間在整個問題空間的分布范圍，然后，在此分布范圍內設定初始群體。先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)目達到了預先確定的規(guī)模。通過定理證明，在二進制編碼的前提下，為了滿足隱含的并行性，群體“個體數(shù)”只要設定為 2n 即可，其中 n 為個體長度的一半。所以在實際應用中，群體個數(shù)的取值范圍一般在幾十到幾百。另外，群體規(guī)模的確定受遺傳操作中選擇操作的 影響很大。群體規(guī)模越大，群體中個體的多樣性越高，算法陷入局部解的危險就小。但是，群體過大，其適應度評估次數(shù)增加，所以計算量也增加，從而影響算法效率。另一方面，如果群體規(guī)模太小，會使遺傳算法的搜索空間分布范圍有限，因此搜索有可能停止在未成熟階段，導致未成熟收斂。 函數(shù) 遺傳算法在進化搜索中基本上不用外部信息，僅僅使用目標函數(shù)即適應度函數(shù)為依據(jù)。遺傳算法的目標函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合。對目標函數(shù)的唯一要求是，針對輸入可計算出能加以比較的結果為非負。 1 目標函數(shù)到適應度函數(shù)的映射 在許多問 題中，目標是求費用函數(shù) g x 的最小值。即使某一問題可自然地表示求最大值形式，也不能保證對于所有的 x,使 f x 取“非負值”。但是遺傳算法中，適應度函數(shù)要進行比較排序并且在此基礎上計算選擇概率，所以適應度函數(shù)的值要取正值。因此必須將目標函數(shù)映射為求最大值形式且適應度函數(shù)值非負。在通常情況下，為了把一個最小化問題轉化為最大化問題，只需要簡單的把原函數(shù)乘以 1 即可 . 2 適應度尺度變換（適應度函數(shù)定標） 應用遺傳算法時，常常會出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結果。在遺傳進化的初期，通常出現(xiàn)一些超常的個體 ，這些異常個體有可能在群體中占據(jù)很大的比例，因而可能導致未成熟收斂現(xiàn)象。這是因為這些異常個體競爭力太突出，控制了整個選擇過程，從而影響了算法的全局優(yōu)化性能。針對上述情況，可以通過放大或縮小相應的適應度函數(shù)值來進行改進。這種對適應度的縮放調整稱作適應度定標。通常采用的定標方式為： ① 線性定標 af + b ； ②σ 截斷 f cσ ； ③乘冪定標 fk； 遺傳操作 1 選擇算子 從群體中選擇優(yōu)勝的個體，淘汰劣質個體的操作叫做選擇。選擇算子又叫再生算子（ Reproduction Operator）。選擇的目的是把“優(yōu)化的解”直接遺傳到下一代或者通過配對交叉產生新的個體再遺傳到下一代。選擇操