【正文】 . 常見的變異算子有基本位變異、均勻變異、高斯變異、二元變異、逆轉變異、自適應變異等.(4) 控制參數(shù)設定. 遺傳算法中需要確定一些參數(shù)取值，主要有串長l，群體大小n，交叉概率pc、變異概率pm等，對遺傳算法性能影響很大. 目前對參數(shù)根據(jù)情況進行調整變化研究比較多，而一般確定的參數(shù)范圍是：n=20～200，pc = 015 ～110，pm =0～0105. 遺傳算法的基本原理在自然界，由于組成生物群體中各個體之間的差異，對所處環(huán)境有不同的適應和生存能力，遵照自然界生物進化的基本原則，適者生存、優(yōu)勝劣汰，將要淘汰那些最差個體，通過交配將父本優(yōu)秀的染色體和基因遺傳給子代，通過染色體核基因的重新組合產(chǎn)生生命力更強的新的個體與由它們組成的新群體. 在特定的條件下，基因會發(fā)生突變,產(chǎn)生新基因和生命力更強的新個體；但突變是非遺傳的，隨著個體不斷更新，群體不斷朝著最優(yōu)方向進化，遺傳算法是真實模擬自然界生物進化機制進行尋優(yōu)的. 在此算法中,被研究的體系的響應曲面看作為一個群體，相應曲面上的每一個點作為群體中的一個個體，個體用多維向量或矩陣來描述，組成矩陣和向量的參數(shù)相應于生物種組成染色體的基因，染色體用固定長度的二進制串表述，通過交換、突變等遺傳操作，在參數(shù)的一定范圍內進行隨機搜索，不斷改善數(shù)據(jù)結構，構造出不同的向量，相當于得到了被研究的不同的解，目標函數(shù)值較優(yōu)的點被保留，目標函數(shù)值較差的點被淘汰. [14] 由于遺傳操作可以越過位壘，能跳出局部較優(yōu)點，到達全局最優(yōu)點.遺傳算法是一種迭代算法，它在每一次迭代時都擁有一組解，這組解最初是隨機生成的，在每次迭代時又有一組新的解由模擬進化和繼承的遺傳操作生成，每個解都有一目標函數(shù)給與評判，一次迭代成為一代. 經(jīng)典的遺傳算法結構圖如下：8編碼、生成初始種群種群中個體適應渡的計算與評價價物種的選擇雜交變異圖1 遺傳算法的結構圖 遺傳算法在實際應用時采取的一般步驟(1)根據(jù)求解精度的要求，確定使用二進制的長度. 設值域的取值范圍為[ ai,b]，若要求精確到小數(shù)點后6位，則由( bia)1062mi1求得 i的最小長度，進而可求出位于區(qū)間的任一數(shù)： xi=a+decimal(10... 2) 1?iab[15] (3)其中，i=1，2， ...， Popsize；Popsize為種群中染色體的個數(shù)；(2)利用隨機數(shù)發(fā)生器產(chǎn)生種群；(3)對種群中每一染色體 vi，計算其對應適應度eval( vi)，i=1，2，… ，Popsize；(4)計算種群適應度之和F：F= ??vealiPopsizi??1 (4)(5)計算每個染色體選擇概率Pi： Flpii (5)i=1，2， ... ，Popsize ；9(6)計算每個染色體的累加概率 qi：i=??jjp1 (6)i=1， 2， ...，Popsize ；(7)產(chǎn)生一個位于[0，1]區(qū)間的隨機數(shù)序列，其長度為N，如果其中任意一數(shù)rq1，則選擇第一個染色體，若 qi1?r i，則選擇第i個染色體，i=1，2， ... Popsize，這樣可以獲得新一代種群；(8)對新一代種群進行交叉運算：設交叉概率為 pc，首先產(chǎn)生一個位于區(qū)間[0,1]內的隨機數(shù)序列，其長度為N，如果其中任意一數(shù)r ，則對應染色體被選中(如果選中奇數(shù)個，則可以去掉一個)，然后在[1，m1]區(qū)間中產(chǎn)生隨機數(shù)，個數(shù)為選中的染色體數(shù)的一半，然后根據(jù)隨機數(shù)在對應位置進行交換操作，從而構成新的染色體；(9)變異操作：設變異概率為 pm，產(chǎn)生mN個位于區(qū)間[0，1]一隨機數(shù)r pm，則選中對應位變異，構成新的種群；(10)第一代計算完畢，返回③繼續(xù)計算，直到達到滿意的結果為止. 遺傳算法的基本流程描述隨機初始化種群p(0)={x1，x2，...，xn}；t=0；計算p(0)中個體的適應值；while(不滿足終止條件){ 根據(jù)個體的適應值及選擇策略從p(t)中選擇下一代生成的父體p(t)；執(zhí)行交叉,變異和再生成新的種群p(t+1) ；計算p(t+1)中個體的適應值；t=t+1；}偽代碼為：BEGIN：　I=0；　Initialize P(I)；　Fitness P(I)；10　While (not Terminate2Condition){I++；　GA2Operation P(I)；　Fitness P(I)；　　}END. 遺傳算法的特點遺傳算法不同于傳統(tǒng)的搜索和優(yōu)化方法. 主要區(qū)別在于：(1)自組織、自適應和自學習性(智能性). 應用遺傳算法求解問題時，在編碼方案、適應度函數(shù)及遺傳算子確定后，算法將利用進化過程中獲得的信息自行組織搜索. 由于基于自然的選擇策略“適者生存、不適者被淘汰”，因而適應度大的個體具有較高的生存概率. 通常適應度大的個體具有更適應環(huán)境的基因結構，再通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應環(huán)境的后代. 進化算法的這種自組織、自適應特征，使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力. 自然選擇消除了算法設計過程中的一個最大障礙，即需要事先描述問題的全部特點，并要說明，利用遺傳算法，我們可以解決那些復雜的非結構化問題.(2)遺傳算法的本質并行性. 遺傳算法按并行方式搜索一個種群數(shù)目的點，而不是單點. 它的并行性表現(xiàn)在兩個方面，一是遺傳算法是內在并行的( inherent parallelism)，即遺傳算法本身非常適合大規(guī)模并行. 最簡單的并行方式是讓幾百甚至數(shù)千臺計算機各自進行獨立種群的演化計算，運行過程中甚至不進行任何通信(獨立的種群之間若有少量的通信一般會帶來更好的結果)，等到運算結束時才通信比較，選取最佳個，可以說，遺傳算法適合在目前所有的并行機或分布式系統(tǒng)上進行并行處理，而且對并行效率沒有太大影響. 二是遺傳算法的內含并行性. 由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間內的多個區(qū)域，并相互交流信息. 使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模N成比例的計算，但實質上已進行了大約O(N3)次有效搜索，這就使遺傳算法能以較少的計算獲得較大的收益.11(3)遺傳算法不需要求導或其他輔助知識，而只需要影響搜索方向的目標函數(shù)和相應的適應度函數(shù).(4)遺傳算法強調概率轉換規(guī)則，而不是確定的轉換規(guī)則.(5)遺傳算法可以更加直接的應用.(6)遺傳算法對給定問題，可以產(chǎn)生許多的潛在解，最終選擇可以由使用者確定. 在某些特殊情況下，如多目標優(yōu)化問題不止一個解存在，有一組pareto最優(yōu)解. 這種遺傳算法對于確認可替代解集而言是特別合適的. [1617] 遺傳算法的改進(1)編碼表示Holland在運用模式定理分析編碼機制時，建議使用二進制編碼，但二進制編碼不能直接反映問題的固有結構精度不高，個體長度大，的措施有：①動態(tài)編碼(dynamic encoding)GA是當算法收斂到某局部最優(yōu)時增加搜索的精度從而使得在全局最優(yōu)點附近，可以進行更精確的搜索，增加精度的辦法是在保持串長不變的前提下減小搜索區(qū)域.②對于問題的變量是實向量的情形，可以直接采用實數(shù)進行編碼，這樣可以直接在解的表現(xiàn)型上進行遺傳操作，從而便于引入與問題領域相關的啟發(fā)式信息以增加算法的搜索能力.③復數(shù)編碼的GA是為了描述和解決二維問題，基因用x+yi表示,其還可以推廣到多維問題的描述中.④多維實數(shù)編碼GA使無效交叉發(fā)生的可能性大大降低，同時其合理的編碼長度也有助于算法在短時間內獲得高精度的全局最優(yōu)解.⑤ 在組合優(yōu)化中，可以使用有序串編碼. 當問題的表示是樹和圖時，我們還可以使用結構式編碼.(2)適應度函數(shù)適應度函數(shù)是用來區(qū)分群體中個體好壞的標準，是自然選擇的唯一標準，選擇的好壞直接影響算法的優(yōu)劣. 選擇的不容易引起兩種不利于優(yōu)化的現(xiàn)象：①異常個體引起早熟收斂，影響求得全局最優(yōu)解. 這種現(xiàn)象常出現(xiàn)在小規(guī)模群體中. 在遺傳進化的早期，一些超常個體的適應度很大，在群體中占有很大的比例，這12些異常個體因競爭力太突出而控制了選擇過程，結果使得算法過早收斂.②個體差距不大，引起搜索成為隨機漫游. 當群體中個體的適應度差別不大，個體間競爭力減弱，特別是平均適應度以接近最佳適應度時，最佳個體與其他許多個體在選擇過程中就會有大體相等的選擇機會，從而使有目標的優(yōu)化搜索過程變成無目標的隨機漫游，影響求得全面最優(yōu)解. 對于上述問題可以通過引入適應度函數(shù)定標技術來加快收斂速度和跳出局部最優(yōu)點. 針對第一種情況，我們可以通過縮小相應的適應度函數(shù)值降低超常個體的競爭力；對于第二種情況，我們可以放大相應的適應度函數(shù)值以拉開個體之間的差距，原適應值間的比例關系，常用的比例變換有線性變換、乘冪變換和指數(shù)變換等.(3)選擇策略優(yōu)勝劣汰的選擇機制使得適應值大的個體有較大的存活機會，不同的選擇策略對算法性能有較大的影響. 輪盤賭法是使用最多的選擇策略，但這種策略可能會產(chǎn)生較大的抽樣誤差，于是對此提出了很多的改進方法，如繁殖池選擇、Boltzmann選擇、非線性排名選擇、基于局部競爭機制的選擇如(λ+μ)選擇等等.(4)控制參數(shù)　控制參數(shù)一般有群體大小、交換概率、變異概率等，這些參數(shù)對遺傳算法性能影響較大. 在標準的遺傳算法中采用經(jīng)驗進行估計，這將帶來很大的盲目性而影響算法的全局最優(yōu)性和收斂性，人們意識到這些參數(shù)應該隨著遺傳進化而自適應變化. 基于這一觀，Davis提出自適應算子概率方法，即用自適應機制把算子概率與算子產(chǎn)生的個體適應性結合，高適應性值被分配高算子概率. 這種方法較好地解決了這一問題. 遺傳算法的應用領域遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性即健壯性，法的一些主要應用領域：(1)，也是對遺傳算法進行性能評價的常用算例. [18] 很多人構造出了各種各樣的復雜形式的測試函數(shù)，有連續(xù)函數(shù)好有離散函數(shù)，有凸函數(shù)也有凹函數(shù)，人們用這些幾何特性各異的函數(shù)來評價遺傳算法的性能. 而對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，遺傳算法卻可以方便地得到較好的結果.13(2)組合優(yōu)化. 隨著問題規(guī)模的擴大，組合優(yōu)化問題的搜索空間急劇擴大，有時在目前的計算機上用枚舉法很難或者甚至不可能得到其精確最優(yōu)解. 對于這類復雜問題，人們已意識到應把精力放在尋求其滿意解上，而遺傳算法則是尋求這種滿意解的最佳工具之一. 實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效.，例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用.(3)生產(chǎn)調度問題. 生產(chǎn)調度問題在許多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化太多而使得求解結果與實際甚遠. 因此，目前在現(xiàn)實生產(chǎn)中好主要靠一些經(jīng)驗進行調度. 遺傳算法已成為解決復雜高度問題的有效工具，在單件生產(chǎn)車間調度、流水線生產(chǎn)車間調度、生產(chǎn)規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用.(4)自動控制. 在自動控制領域中許多與優(yōu)化相關的問題需要求解，遺傳算法的應用日益顯示了良好的效果. 例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、基于遺傳算法的模糊控制器優(yōu)化設計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進行人工神經(jīng)網(wǎng)絡的結構優(yōu)化設計和權值學習都顯示出了遺傳算法在這些領域中應用的可能性.(5)機器人智能控制. 機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人智能控制理所當然地成為遺傳算法的一個重要應用領域. 例如遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行動協(xié)調等方面得到研究和應用.(6)圖像處理和模式識別. 圖像處理和模式識別是計算機視覺中的一個重要研究領域. 在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會產(chǎn)生一些誤差這些誤差會影響到像處理和識別的效果. 如何使這些誤差最小是使視覺達到實用化的重要要求. 遺傳算法在圖像處理中的優(yōu)化計算方面是完全勝任的. 目前已在圖像恢復、圖像邊緣特征提取、幾何形狀識別等方面得到了應用.(7)人工生命. 人工生命是用計算機等人工媒體模擬或構造出具有自然生物系統(tǒng)特有行為的人造系統(tǒng). 自組織能力和自學習能力是人工生命的兩大主要特征. 人工生命與遺傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要理論基礎. 雖然人工生命的研究尚處于啟蒙階段,但遺傳算法已在其進化模型、學習模型、14行為模型等方面顯示了初步的應用能力. 可以預見，遺傳算法在人工生命及復雜自適應系統(tǒng)的模擬與設計、復雜系統(tǒng)突現(xiàn)性理論研究中，將得到更為深入的發(fā)展.(8)遺傳程序設計. 1989年，美國Standford大學的Koza教授發(fā)展了遺傳編程的概念，其基本思想是:采用樹型結構表示計算機程序，運用遺傳算法的思想，通過自動生成計算機程序來解決問題. 雖然遺傳編程的理論尚未成熟，應用也有一些限制，但它已成功地應用于人工智能、機器學習等領域，目前公開的遺傳編程實驗系統(tǒng)有十多個，例如，Koza開發(fā)的ADF系統(tǒng)，White開發(fā)的GPELST系統(tǒng)等.(9)機器學習. 學習能力是高級自適應系統(tǒng)所應具備的能力之一. 基于遺傳算法的機器學習，特別是分類器系統(tǒng)，在許多領域得到了應用. 例基于遺傳算