遺傳算法綜述摘要：20世紀70年代初，Holland首先提出了遺傳算法。由于遺傳算法是全新的模擬生物演化的仿生優(yōu)化算法以及遺傳算法既適合無表達又適合有表達的任何類函數(shù)，因此己成為許多學科共同關注的熱點研究領域。本文詳細闡述了遺傳算法的起源、發(fā)展過程以及對標準遺傳算法的基本原理、實現(xiàn)步驟、流程和特點。本文還對遺傳算法收斂性進行分析，最后對遺傳算法的應用領域和研究方向進行了概述。關鍵字：遺傳算法；實現(xiàn)；分析Abstract：ThegeneticalgorithmispresentedbyHollandin1970s.Thegeneticalgorithmhasbecomethefocusofmanysubjects,forgeneticalgorithmisanewoptimalalgorithmtosimulatethebiologicalevolution,anditsuitsbothtofunctionswithoutexpressionsandtofunctionswithexpression.Thispaperdescribestheoriginofthegeneticalgorithm,aswellasthedevelopmentofthestandardgeneticalgorithmtothebasictenetsofimplementationsteps,processesandcharacteristics.Thispaperalsoconvergenceofthegeneticalgorithmanalysis,thefinalapplicationofgeneticalgorithmsandresearchareasofthedirectioninwhichoutlined.Keywords：GeneticAlgorithm；implement；analysis遺傳算法的起源遺傳算法是模擬生物在自然環(huán)境力的遺傳和進化過程而形成的一種自適應全局優(yōu)比概率搜索算法［1］。它最早由美國密執(zhí)安大學Holland教授提出，起源于60年代對自然和人工自適應系統(tǒng)的研究。70年代DeJong基于遺傳算法的思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗。在一系列研究工作的基礎上，80年代由Goldberg進行歸納總結，形成了遺傳算法的基本框架［2］。遺傳算法的發(fā)展與現(xiàn)狀遺傳算法創(chuàng)建的目的是在人工適應系統(tǒng)中設計一種基于自然演化原理的搜索機制。Holland不僅設計了遺傳算法的模擬與操作原理，而且對遺傳算法的搜索機理進行了理論分析，為遺傳算法的發(fā)展奠定了初步的理論基礎。在Holland之后，遺傳算法經(jīng)歷了一個相對平穩(wěn)的發(fā)展時期。但到20世紀80年代末到至今，遺傳算法已成為信息科學、計算機科學、運籌學、應用數(shù)學和人工生命等諸多學科所共同關注的熱點研究領域。目前，遺傳算法的研究分為三個方面。一是對遺傳算法本身的改進；二是遺傳算法的數(shù)學理論研究；三是遺傳算法的應用。遺傳算法的理論研究比以前有了一些新的進展，特別是在遺傳算法一般模型的收斂性理論方面已得到了一系列的結論，這因為采用了新的研究方法即迭代方法。遺傳算法的應用己幾乎滲透到從工程到社會科學的諸多領域。對遺傳算法的改進有很多種方法。有與其它優(yōu)化方法如神經(jīng)網(wǎng)絡、模糊系統(tǒng)等相結合而產(chǎn)生的混合遺傳算法。神經(jīng)網(wǎng)絡和遺傳算法現(xiàn)有的結合工作主要是利用遺傳算法輔助設計神經(jīng)網(wǎng)絡。或?qū)⑸窠?jīng)網(wǎng)絡結合到遺傳算法中，以改進遺傳算法的收斂性。一種融和神經(jīng)網(wǎng)絡的改進遺傳算法［4］，是將神經(jīng)網(wǎng)絡和遺傳操作相結合，具體方法是在個體遺傳操作后，將新一代個體與相應父代個體組成訓練模式進行神經(jīng)網(wǎng)絡學習，若訓練成功，則由遺傳算法產(chǎn)生少量個體，從神經(jīng)網(wǎng)絡抽取多個個體，若訓練失敗，則反之。另一方面，將遺傳算法用于神經(jīng)網(wǎng)絡的訓練。神經(jīng)網(wǎng)絡的學習包含了兩個優(yōu)化過程，分別是網(wǎng)絡連接權重的優(yōu)化和網(wǎng)絡拓撲結構的優(yōu)化。優(yōu)化連接權重最著名的方法是反向傳播法。但反向傳播法算法的最大弱點是局部極小問題和無法學習網(wǎng)絡拓撲結構。作為一種通用性和全局性良好的優(yōu)化技術，遺傳算法用于神經(jīng)網(wǎng)絡的訓練就是很自然的事情。遺傳算法用于神經(jīng)網(wǎng)絡的學習可分為三個不同的層次：連接權重的學習、網(wǎng)絡拓撲的學習以及網(wǎng)絡學習規(guī)則的學習。遺傳算法可用于前向網(wǎng)絡、徑向基網(wǎng)絡、Kohonen特征映射及Recurrent網(wǎng)絡等各種人工神經(jīng)網(wǎng)絡的訓練與設計中。采用遺傳算法學習神經(jīng)網(wǎng)絡連接權，不僅發(fā)揮神經(jīng)網(wǎng)絡所具有的廣泛映射能力，而且由于采用遺傳算法，從而使網(wǎng)絡具有快速收斂及增強式學習性能。模糊系統(tǒng)與遺傳算法的結合工作是遺傳算法已成功地用于隸屬函數(shù)形狀與參數(shù)的優(yōu)化，系統(tǒng)相關權重的優(yōu)化以及推理規(guī)則的選取。另外，模糊集技術也被用于遺傳算法，以達到改進遺傳算法的目的。機器學習與遺傳算法相結合，把遺傳算法用于機器學習產(chǎn)生了分類系統(tǒng)，并應用于人工生命、視覺系統(tǒng)的控制等方面。基于小生境技術的遺傳算法［5］，采用神經(jīng)網(wǎng)絡方法將每個個體進行聚類分行，將解空間分為幾個種群，選取平均適應度較大的若干種群建立為小生境，然后運用局部搜索方法產(chǎn)生新個體，最后將新舊個體進行遺傳操作得到新一代群體。壓縮遺傳算法［6］，該算法將群體表示為解集上的概率分布。它獨立處理每個基因并且比簡單遺傳算法要求更少的內(nèi)存。這項研究為遺傳算法引入了新的思想，使人們對標準遺傳算法的復雜動態(tài)特性有了更多的了解，并為設計更高效的遺傳算法打下了基礎。運用自然鮑爾溫效應［7］增強標準遺傳算法的性能，并運用人工神經(jīng)網(wǎng)絡儲存種群進化歷史。標準遺傳算法3.1生物學的基本概念與術語為了便于理解遺傳算法，下面給出幾個生物學的基本概念與術語［3］。適者生存：在算法停止時，最優(yōu)目標值的解被保留的可能性最大。染色體(chromosome)：由多個基因組成，染色體所攜帶的遺傳信息的全體稱為一個基因組，是遺傳物質(zhì)的主要載體。對應目標函數(shù)解的編碼(字符串、向量等)，也稱染色體為染色體個體?；?gene):或稱為遺傳因子。是DNA或RNA長鏈結構中占有一定位置的基本遺傳單位。對應解的字符串編碼中的每一個字符。個體(individual)：指染色體帶有特征的實體，對應目標函數(shù)的解。群體：選定的一組解（群體的大小為群體中解的個數(shù)）。種群：個體的集合稱為種群，也稱作染色體群。是根據(jù)適應函數(shù)值選取的一組解。適應度（fitness）：是度量某個物種對于生存環(huán)境的適應程度，對應適應函數(shù)值。復制（reproduction）：遺傳物質(zhì)DNA通過復制而轉移到新產(chǎn)生的細胞中，新的細胞就繼承了舊細胞的基因。交叉（crossover）:在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體。這個過程又稱基因重組recombination，俗稱“雜交”即通過交叉原則產(chǎn)生一組新解的過程。突變（mutation）:在細胞進行復制時可能以很小的概率產(chǎn)生某些復制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀，對應編碼的某一個分量發(fā)生變化的過程。3.2標準遺傳算法的基本原理Holland的經(jīng)典遺傳算法通常稱為標準遺傳算法［8］。標準遺傳算法是一種由一個種群（或稱染色體群）通過“自然選擇”［9］的機制轉化成為另一個種群的方法。在這里，“自然選擇”是由遺傳學中“選擇”、“交叉”和“突變”幾種作用共同完成的。稱一個解的編碼為一個染色體，組成編碼的元素為基因。例如若解的編碼用一個二進制串表示，則“基因”是指一位二進制代碼（0或1）。編碼的目的是用于優(yōu)化問題解的表現(xiàn)形式和便于在遺傳算法中計算。選擇的作用是從種群中選出可以繁殖后代的個體，一般總是保證當前種群中具有較高適應值的個體以較大的概率產(chǎn)生出更多的后代。交叉作用用于交換兩個編碼之間的組成部分而達到產(chǎn)生下一代的目的。突變作用是指改變個體（染色體）上某一位置基因的值。標準遺傳算法與其它啟發(fā)式方法順序搜索解空間的工作方式不同，標準遺傳算法采用種群作為工作單元，使用模仿生物進化的適者生存原則指導搜索并改進目標，種群由代表個體的定長字符串組成，每個個體的質(zhì)量通過依賴于問題目標函數(shù)的適應值函數(shù)來進行評估，然后，對種群模仿生物進化的規(guī)律，實施三種遺傳操作，對應于使用3個基本算子：選擇、交叉和變異。種群經(jīng)過這3個基本算子的優(yōu)化處理，從種群產(chǎn)生出新的優(yōu)化了一代（即新的種群），增加找到全局最優(yōu)解的可能性。經(jīng)過這樣一代代地不斷進化，擇優(yōu)汰劣，最后得出非常優(yōu)秀的群體和個體，從而得到問題的最優(yōu)解。

3.3標準遺傳算法實現(xiàn)步驟對于一個給定的優(yōu)化問題，目標函數(shù)Maxf(x,y,z), (x,yz) ,FwR其中(x,y,z)為自變量，Q是(x,y,z)的定義域，x,y,z可以是數(shù)值，也可以是符號。函數(shù)值f是實數(shù)。f為解空間(x,y,z)WQ到實數(shù)域FwR的一種映射。下面是用標準遺傳算法求解此問題的步驟［10］。3.3.1選擇編碼方式和編碼遺傳算法在求解之前，要將解以字符串的形式表達，也就是要將待求解問題的所有參數(shù)編碼(為一定長的字符串)，編碼方式［11］有多種，如二進制編碼、Gray編碼、動態(tài)編碼、實數(shù)編碼、有序串編碼、結構式編碼等,根據(jù)優(yōu)化問題選擇合適的編碼方式。常使用的編碼方式主要是二進制碼［12］，這里我們選擇二進制編碼。二進制編碼也就是一個由｛0,1｝組成的二進制串。設需求解的未知參數(shù)xW［a,b］,x對應的二進制編碼的串長取決于x的精度，如果設定求解精確到n位小數(shù)，此時若有2m-1<(b-a)10n<2m則編碼的二進制串長至少需要m位。將一個二進制串(bm1bm2……b0)轉化為區(qū)間［a,b］內(nèi)對應的實數(shù)值x，采取以下兩步：(1)計算二進制串(bm-1bm-2……b0)對應的10進制數(shù)：(b b b)=(曠b2i) =x'm-1m-2 02i10i=0⑵二進制串(bm-1bm-2……b0)對應區(qū)間［a,b］內(nèi)的實數(shù)值x按以下公式計b-a2b-a2m—12m—1其中m是編碼的二進制串長。

3.3.2產(chǎn)生初始種群t=0時，由計算機隨機產(chǎn)生N個初始字符串［13］，每個字符串稱為一個個體，這N個個體就構成了一個群體p(0)(稱為初始群體)。種群p(t)代表優(yōu)化問題的一些可能解的集合。群體中個體的數(shù)目稱為群體的大小。群體的大小可根據(jù)優(yōu)化問題事先設定，如果事先設定群體的大小為N,則由計算機隨機產(chǎn)生N個初始字符串。一般來說，初始群體p(t)的素質(zhì)很差，遺傳算法從初始群體出發(fā)，即從這N個字符串作為初始點開始迭代計算。模擬進化過程，擇優(yōu)汰劣，最后得出非常優(yōu)秀的群體和個體，滿足優(yōu)化的要求。3.3.3選擇適應度函數(shù)以評價種群對種群p(t)中每個個體給出評價，評價規(guī)則也就是根據(jù)優(yōu)化問題選擇適應度函數(shù)。如果某個體的適應度函數(shù)值越高，表示該個體的適應度越高，如果適應度收斂到某一穩(wěn)定值，則此穩(wěn)定值對應所求優(yōu)化問題的解。一般來說，對于不同的問題，適應度函數(shù)的定義方式不同，目的是使適應度越高的個體越接近問題的解。種群進化選擇的依據(jù)是個體的適應度。常用的適應度函數(shù)有以下三種，方法是將目標函數(shù)變換成適應度函數(shù)。將求解的目標函數(shù)直接轉化為適應度函數(shù)Fit(f(x,y,z))。定義若求目標函數(shù)f(x,y,z)的最大值時，則適應度函數(shù)Fit(f(x,y,z))=f(x,y,z)。若求目標函數(shù)f(x,y,z)的最小值時，則適應度函數(shù)Fit(f(x,y,z))=-f(x,y,z)但此方法存在兩個問題，其一是由此計算出的適應度函數(shù)值有可能為負值，導致選擇概率為負，這與概率非負的性質(zhì)矛盾。其二是若求解函數(shù)的函數(shù)值范圍很廣，由種群計算出的平均適應度不能近似反映目標函數(shù)的平均值，因而影響算法的性能。根據(jù)上面定義適應度函數(shù)時存在的問題，對適應度函數(shù)的定義作如下改進定義若目標函數(shù)f(x,y,z)為最小值問題時，則適應度函數(shù)為Fit(f(Fit(f(x,y,z))=c -f(x,y,z)<max0f(x,y,z)<cmaxf(x,y,z)>cmax其中c 是f(x,y,z)的最大估計值，也稱c的界線值。maxmax由上式可知，當f(x)<c 時，F(xiàn)it(f(x,y,z))為c -f(x,y,z)>0,TOC\o"1-5"\h\zmax max:?Fit((x,y,z))^0，V(x,y,z)三Q,所以可保證由適應度定義的選擇概率非負。并且由Fit(f(x,y,z))=c -f(x,y,z)，當f(x,y,z)<c 時，max max可知當適應度函數(shù)值Fitf(x,y,z))越大，則函數(shù)值f(x,y,z)越小。因為適應度越高的個體被選擇的概率越大，此時個體對應的函數(shù)值越小，所以最后搜索到的最佳個體是函數(shù)f(x,y,z)最小值點。同理可對最大值問題給出定義.定義若目標函數(shù)f(x,y,z)為最大值問題，則Fit(fFit(f(x,y,z))=f(x,y,z)-c.min0f(x,y,z)>cminf(x,y,z)<cmin其中c.為f(x,y,z)的最小值估計，也稱c.為界限值這種方法通常稱為“界限構造法”此方法的問題是界限值c，c.maxmin預先難以估計以及估計精確。c.依據(jù)同樣的思路，對適應度函數(shù)給出另一種定義定義若目標函數(shù)f(x,y,z)為最小值問題，則適應度函數(shù)(公式1)Fit(fFit(f(x,y,z))=11+C+f(x,y,z)c>0,c+f(x,y,z)>0若目標函數(shù)f(x,y,z)為最大值問題，則適應度函數(shù)(公式2)Fit(fFit(f()x,y,z)=11+C—f(x,y,z)c>0,c-f(x,y,z)>0其中If(x,y,z)IWc,c是f(x,y,z)的最小上界。c是預先給定的目標函數(shù)f(x,y,z)的界限的估計值。從上公式1可知，若適應度函數(shù)值Fitf(x,y,z))越高，則函數(shù)值f(x,y,z)越小，所以，最后搜索到的最佳個體是目標函數(shù)f(x,y,z)的最小值。從上面公式2可知，若適應度函數(shù)值Fitf(x,y,z))越高，則函數(shù)值f(x,y,z)越大，所以最后搜索到的最佳個體是目標函數(shù)f(x,y,z)的最大值。一般來說，適應度函數(shù)的設計主要滿足以下條件：單值、連續(xù)、非負、最大化。這個條件可通過上面適應度函數(shù)的定義來理解。合理、一致性。適應度值應能反映解的優(yōu)劣程度，這一點往往難以衡量。計算量小。適應度函數(shù)的設計應盡可能簡單，以降低計算成本。通用性強，對某類具體問題，設計的適應度函數(shù)可以通用。3.3.4選擇(或復制)選擇是指從大小為N的種群p(t)中隨機選擇出N=2M個個體，組成M對個體，用于繁殖后代，若以概率1交配，則產(chǎn)生N個新的個體構成新的下一代種群p(t+l)。一個由N個個體組成的種群，這其中哪個個體被保留(即復制)下來用以繁殖后代，哪個被淘汰，是根據(jù)對它們的各自的適應度函數(shù)值來決定。個體的適應度函數(shù)值大，說明其對環(huán)境的適應能力強，它也就有更多的機會被保留下來用以復制后代。反之，則其被淘汰。選擇是遺傳算法的關鍵，它體現(xiàn)了自然界中適者生存的思想。具體選擇時，為了體現(xiàn)這個思想，選擇個體的概率定義為正比于個體的適應值。從N個個體組成的種群中選出適應度高的個體用于繁殖后代，分為兩步來實現(xiàn)。第一步確定個體選擇概率的定義方法。常用的定義方法有兩種［⑶。第二步確定選擇方法。選擇方法有多種方式，常用的有輪盤賭選擇法［⑶。個體選擇概率常用的定義方法有如下兩種：按比例的適應度分配定義設時刻t種群p(t)大小為N,個體i對應的適應度函數(shù)值為f個體i對應的選擇概率為從，則 1fk

P= 匚,i=1,……,Nii=1其中k三1,k是比率參數(shù)，可根據(jù)優(yōu)化問題預先設定i=1,…,N。稱此方法為按比例的適應度分配。基本排序的適應度分配基于排序的適應度分配是對種群中每個個體按適應度函數(shù)值從小到大排序記為1至N,此時個體i的選擇概率P=^—,i=1,……,Ni=1基于排序的適應度分配的好處有兩個：因為VigN,i>0,「.選擇概率p>0。避免了按比例的適應度分配i方法中。若目標函數(shù)值為負值，需對其作變換，以保證適應度函數(shù)值$0。當選擇壓力(即最佳個體選中的概率與平均選中概率的比值)太小時，即最佳個體被選中的可能性太小時，會產(chǎn)生過早收斂。過早收斂是指

遺傳算法在執(zhí)行過程中會出現(xiàn)群體中的個體過早地在一個非最優(yōu)點上達到完全相同或接近完全相同的現(xiàn)象。一旦出現(xiàn)該現(xiàn)象，利用遺傳算法就不能求得問題的全域最優(yōu)解。排序方法避免了這個問題，因為排序方法是以個體的序號作為適應度值，選擇概率定義為正比于個體適應度(即個體序號)，因此排序方法實際上是引入了種群均勻尺度，使搜索不會過早地陷入局部搜索，避免過早收斂的發(fā)生。排序方法比比例方法表現(xiàn)出更好的魯棒性，不失為一種好的選擇方法。下面計算個體i產(chǎn)生下一代的個體數(shù)目D(i)[14]。定理設種群p(t)的大小為N,個體i的適應度為片，個體選擇概率i1=1,n,則個體產(chǎn)生下一代個體數(shù)目i1=1,n,則個體產(chǎn)生下一代個體數(shù)目D(i)=1蘭Ni=1推論1如果個體i的適應度f為平均適應度f，則此個體i產(chǎn)生下一代的個體數(shù)D(i)=1。推論2新生下一代種群p(t+l)的個體總數(shù)N仝f。i=1f3.3.5交叉(基因重組)對通過選擇操作而得到的新一代用于繁殖的種群p(t+l)中的每一對個體，根據(jù)交叉概率pc決定是否交叉產(chǎn)生兩個新的后代，若決定交叉，則c隨機地選定一個位置n(1WnWm),m是基因串即個體的長度。將兩個個體在該位置上交叉互換右端(或左端)的基因串，得到兩個后代。如兩個個體(或稱染色體)分別為100|00100和111|11111，隨機選定的位置是第三位，交換第三位右端的基因串，得到100|11111和111|00100此交叉方法稱為單點交叉。交叉操作粗略地模擬了兩個單倍體生物進行繁殖時染色體(即個體)的配對過程。具體方法是首先把選擇出的N個個體自由排列，這樣可以得到N對2個體組合，對于每一對組合根據(jù)給定的交叉率Pc進行單點交叉，也就是c說，并不是種群中每對個體（字符串）都發(fā)生交叉。若交叉率越大，交叉操作發(fā)生的可能性越大，產(chǎn)生交叉操作的個體就越多，因而得到的新個體也就多些。交叉點的位置隨機選取，交叉的目的是使來自父代的個體組合到一起以產(chǎn)生更優(yōu)良的個體。交叉實質(zhì)上具有破壞性，但正因為此破壞性，才可能產(chǎn)生新品種的優(yōu)良個體，促進搜索全局解空間，而不陷于局部解空間，避免過早收斂的發(fā)生。交叉率的選擇決定了交叉操作的頻率，頻率越高，可以越快地收斂到最有希望的最優(yōu)解區(qū)域。因此一般選取較大的交叉率，但若頻率太高也可能導致過早收斂。交叉率一般取值0.4~0.9。除單點交叉外，交叉算子還有二點交叉、多點交叉、均勻交叉、匹配交叉、順序交叉、循環(huán)交又、洗牌交叉、縮小代理交叉等。3.3.6突變從群體p（t+l）中隨機選取若干個體，對于選中的個體的每一個基因，按一定的突變概率pm決定是否產(chǎn)生變異。若決定變異，則在該位進行取m反運算，即由1?6,或由o?1。遺傳算法的搜索能力主要是由選擇和交叉賦予的，突變?yōu)樾聜€體的產(chǎn)生提供了機會，有利用保持種群的多樣性。因此突變算子能保證算法能搜索到問題解空間的每一點，從而使算法具有全局最優(yōu)，避免過早收斂的發(fā)生。雖然選擇復制和交叉操作可以產(chǎn)生新的基因串（染色體），但是不能產(chǎn)生新的基因。如果所有基因串中某一位置的基因都相同，則這一基因所表征的特性就永遠不會改變。變異算子的引入打破了僵局，但突變率（或步長）不能取得太大，如果突變率大于6.5，遺傳算法就退化為隨機搜索，會引起不穩(wěn)定，突變一般是以較小的概率進行，突變率一般取6.661~6.1。突變操作除了是對基因串的某一位基因作取反運算外，也可采用更復雜的算子，如逆轉算子、自適應變異算子等［15］。標準遺傳算法的過程［16］見圖3.1。位串 適應值排序1101101101121100011100301110101014位串 適應值排序1101101101121100011100301110101014011001001038.3343.7254.5134.64圖3.1標準遺傳算法的過程3.4標準遺傳算法的流程標準遺傳算法的流程分為以下6個步驟：隨機生成N=2M個長度為m的字符串(或個體)，組成初始群體。將種群中的每個字符串代入適應度函數(shù)，計算適應度。判斷是否滿足終止條件，若是，則適應度值最大的字符串對應的候選解就是需要的滿意解。若否，則步驟4重復下列步驟直至產(chǎn)生了N個后代。選擇：根據(jù)個體選擇概率匚，從當前種群中隨機選出兩個個體作為父體。選擇概率P.應該是正比于適應度。交叉：對選中的父體，按交叉概率P決定是否交叉產(chǎn)生兩個新的后代。若決定交叉，則隨機決定交叉位置(也可采用其它交叉方式)；若不交叉，則兩個后代是兩個父體的嚴格復制。突變：對產(chǎn)生的兩個后代，分別在每個位置，按突變概率Pm決定是否發(fā)生突變，得到的兩個后代放入下一代新的種群中。

生成N個新的個體后，用新的種群代替原來的種群。(6)轉向步驟2。終止條件可是指定的迭代代數(shù)，一般為50—500個代數(shù)。也可是指定的誤差條件。標準遺傳算法的流程圖如圖3.2所示。編碼和初始化種群不滿足終止條件計算終止編碼和初始化種群不滿足終止條件圖3.2標準遺傳算法流程解決實際問題時遺傳算法包括兩個決策步驟：將求解問題模型化為符合遺傳算法的框架，可行解空間的定義，適應值函數(shù)的表現(xiàn)形式，解的字符串的表達方式。遺傳算法參數(shù)的設計，如種群的大小，選擇交叉、突變的概率選擇,進化最大代數(shù)，終止準則設定等。3.5標準遺傳算法特點標準遺傳算法有如下特點：遺傳算法是對參數(shù)的編碼進行操作，而不是對參數(shù)本身。對參數(shù)的編碼操作是直接對對象的結構進行操作。具有自組織、自適應、自學習性。遺傳算法利用進化過程獲得的信息，自行組織搜索，適應度大的個體具有較高的生存概率，并獲得更適應環(huán)境的基因結構。遺傳算法具有并行計算的特點。許多傳統(tǒng)搜索方法都是單點搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化。求解所需問題的信息量少，因而應用范圍較廣。這是因為遺傳算法是利用所求問題的適應度函數(shù)值來評估個體，進行搜索求解的。而不像傳統(tǒng)優(yōu)化方法需要一些輔助信息如連續(xù)、導數(shù)等，一旦所需信息不存在，這些方法就會失敗而無法被執(zhí)行。從這個意義上講，遺傳算法幾乎可以處理任何問題，既可以是數(shù)學解析式所表達的顯函數(shù)，也可以是映射矩陣甚至是神經(jīng)網(wǎng)絡等隱函數(shù)，因而應用范圍較廣。所進行的操作簡單、可靠，并利用概率的變遷規(guī)則來指導搜索方向。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導它的搜索方向，并且僅使用復制、交換和突變這三種簡單可靠的操作方法。遺傳算法正是使用這些簡單的隨機操作來指導搜索，向著問題的最優(yōu)解前進。適于求解復雜問題而且效率高。正是由于遺傳算法具有上述特點，所以它最善于搜索求解復雜問題，并可以很快地從這一問題所形成的復雜地域中找出期望值高的區(qū)域，最終快速找出復雜問題的最優(yōu)解。3.6標準遺傳算法存在的問題及改進途徑盡管遺傳算法具有較多的優(yōu)點，并在實際中得到了大量的應用，但它也存在著許多急待解決的問題。3.6.1標準遺傳算法存在的問題重要參數(shù)如N(群體規(guī)模)、pc(交叉概率)、Pm(變異概率)如何選擇。這些重要參數(shù)的選擇將直接影響遺傳算法的性能。交叉算子和變異算子如何協(xié)調(diào)工作。如何改進操作手段或引入新的操作手段來提高遺傳算法的執(zhí)行效果。如何避免算法初期的過早收斂的產(chǎn)生，后期的搜索遲鈍以及局部搜索能力較弱的問題。單一的群體更新方式難以兼顧多樣性和收斂性的要求，收斂速度較慢的問題。如何將遺傳算法與其它傳統(tǒng)優(yōu)化方法有機地結合起來。以便各顯所能，得到解決問題的最佳方案。如何從數(shù)學上更加完善地對遺傳算法進行定量分析，為遺傳算法獲得更好的實際應用奠定基礎。如何更廣泛地開辟遺傳算法的實際應用新領域。3.6.2對標準遺傳算法改進的新算法針對標準遺傳算法所存在的缺陷［17］，許多學者提出了各種改進方法以改善遺傳算法的性能，主要從初始解群的產(chǎn)生、選擇、交叉和變異算子的改進、重要參數(shù)選擇等方面尋求改進。對標準遺傳算法改進的新算法，主要有啟發(fā)式遺傳算法、遞級分布式遺傳算法、連續(xù)繁殖式遺傳算法、基于分裂選擇的遺傳算法、自適應遺傳算法、并行遺傳算法、基于遷移和人工選擇的遺傳算法。3.6.3標準遺傳算法的改進途徑改變遺傳算法的組成成分或使用技術，如選用優(yōu)化控制參數(shù)，適合問題特性的編碼技術等。采用動態(tài)自適應技術，在進化過程中調(diào)整算法控制參數(shù)和編碼粒度。采用非標準的遺傳操作算子。采用混合遺傳算法。這一研究的目的是既發(fā)揮遺傳算法的全局性特點又發(fā)揮某類特定方法對于特定問題的有效收斂性，以便快速、穩(wěn)定地搜索到問題的全局最優(yōu)解。如Poon和Park［i8］。將遺傳算法GA和模擬退火SA進行了比較，結果顯示，在運行初期遺傳算法GA的收斂較快，而模擬退火SA卻往往能發(fā)現(xiàn)更好的解，但計算代價較高，原因是遺傳算法GA能夠產(chǎn)生平均適應值高的種群，但缺少尋找最出色個體的“殺手銅”因此Dejong［i9］建議，應該將遺傳算法GA的全局搜索效能與其它局部搜索方法結合起來。如將遺傳算法與模擬退火綜合，構成混合方法模擬退火—遺傳算法。類似還有神經(jīng)網(wǎng)絡—并行遺傳算法、進化編程—遺傳算法、遺傳編程—遺傳算法、爬山法—遺傳算法、模糊—遺傳算法。采用并行遺傳算法。并行遺傳算法包括以下四類：a、整體并行遺傳算法：這種模型只有一個種群，個體計算和遺傳算子的應用顯示并行化，并行地指派個體的子集到每個有用處理器，每個個體有機會與其它個體匹配，這種方法適用于其享和分布式計算機。b、粗粒度并行遺傳算法：粗粒度并行遺傳算法的主要特征是群體之間的并行性和引入遷移算子的作用。C、細粒度并行遺傳算法：細粒度并行遺傳算法是開發(fā)一個群體中的并行性。種群被劃分成許多小群體，此模型需要巨型并行機。d、混合并行遺傳算法：該方法是組合兩種并行算法，構造出混合并行遺傳算法。一種混合并行遺傳算法是在粗粒度的群體上進行整體并行化，如同粗粒度并行遺傳算法，遷移在群體之間發(fā)生，個體計算是并行處理。4遺傳算法一般模型的收斂性分析4.1基于簡化的遺傳算法模型的收斂性分析近些年，在基于簡化的遺傳算法模型的收斂性分析方面取得了突破，運用的數(shù)學工具是Markov鏈。Coldberg和Segrest[20]首先使用了Markov鏈分析了遺傳算法。Eiben等用Markov鏈證明了最優(yōu)個體的遺傳算法的概率性全局收斂，Rudolph用齊次有限Markov鏈證明了帶有復制、交換、突變操作的標準遺傳算法不收斂到全局最優(yōu)解，不適合于靜態(tài)函數(shù)優(yōu)化問題，建議改變復制策略以達到全局收斂。BaCk和Muhlenbin研究了達到全局最優(yōu)解的遺傳算法的時間復雜性問題。4.2遺傳算法一般模型的收斂性分析上面基于簡化的遺傳算法模型的收斂性結果，都是通過馬爾可夫鏈的極限理論來分析的。近幾年，對于遺傳算法一般模型的收斂性，由張文修[2122]等進行了深入的研究，用鞍方法與迭代方法得到了一系列的結果。給出了遺傳算法一般模型的收斂條件，并應用這些條件證明了杰出者遺傳算法、整體退火遺傳算法、最佳值遺傳算法、廣義模擬退火遺傳算法這四種混合遺傳算法的概率收斂性定理。例如對于標準遺傳算法子，當變異概率1P三P>0時，有r二pln(p<-)，于是，滿足概率收斂定理的條件，因而mn2有結論：若變異不變遺傳算法采用概率收斂定理的算法，則幾乎處處強收斂到全局最優(yōu)解集。對于遺傳算法首次到達最優(yōu)解集的時間，用首達時間的期望值表示，可得到這樣的結論：求目標函數(shù)f(x)= 1x的極大值，ji=1j=1xG［0,1］，首達時間的期望值的上界是l的多項式。目標函數(shù)廠f(x)=<+1,11xII1=1 的首達時間的期望值被指數(shù)下界所控制。l-IIxII,11xIIVl11就遺傳算法的目標來看，是尋求全局最優(yōu)解，而完成的過程是一個隨機搜索過程。因而是一個下鞅序列，利用鞅收斂定理進一步證明遺傳算法的收斂性。為了保證遺傳算法的收斂性，有兩個參數(shù)是非常重要的：一個參數(shù)是過程進入滿意解后下一步脫離滿意解集的可能性。另一個參數(shù)是過程未進入滿意解時下一步仍不能進入滿意解的可能性。這兩個參數(shù)的匹配構成了遺傳算法收斂的一般理論。用這種方法研究收斂性變?yōu)榧兏怕实姆椒ǎ庇^且簡練地證明了多種遺傳算法的收斂性。Markov鏈在分析遺傳算法中的具體形式：設S=￡,12為個體空間，E=SN為種群空間。一般用X，Y，Z或X.，Y.,Z.表示個體，用X,Y,Z,表示種群，顯然種群是個體空間上的一個N..維向量，記為X=(X,X，…,X),個體X.是｛0,1｝上的l維向量，記為X=1 2 N . .(X.1,X.2,...,X.l)。若P是SN上的概率測度，則(SN,P)構成概率空間。設G:(SN,P)T(SN,P)n是隨機遺傳算子，GN可通過選擇、交叉、變異等隨機算子構成。于是得到遺傳算法的種群序列顯然｛x(n)｝為狀態(tài)SN上的Markov鏈。4.3十進制退傳算法的收斂性分析黃友銳㈡］用Markov鏈分析十進制遺傳算法，得到了十進制遺傳算法是一個遍歷的Markov鏈。即不論其初始分布如何，狀態(tài)鏈最終收斂于一個確定的終了狀態(tài)，而各狀態(tài)都是非零概率可達的。并且證明了標準十進制遺傳算法不收斂到全局最優(yōu)值。而每代保留最優(yōu)的改進十進制遺傳算法能收斂于全局最優(yōu)。標準遺傳算法雖不保證全局最優(yōu)收斂，但在一定的約束條件下，遺傳算法可以收斂到全局最優(yōu)值。5應用與展望5.1遺傳算法的應用領域由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計算是不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數(shù)和相應的適應度函數(shù)，所以遺傳算法提供了一種求解復雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于許多科學，下面是遺傳算法的一些主要應用領域。1、函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是遺傳算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結果。2、組合優(yōu)化隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優(yōu)解。對這類復雜的問題，人們已經(jīng)意識到應把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于組合優(yōu)化中的NP問題非常有效。例如遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。80年代以來，遺傳算法的應用領域不斷擴大。目前遺傳算法所涉及的主要領域有自動控制、規(guī)劃設計、組合優(yōu)化、圖象處理、信號處理、人工生命等?？梢?，遺傳算法的應用研究已從初期的組合優(yōu)化求解拓展到了許多更新。更工程化的應用方面。5.2遺傳算法的研究展望遺傳算法雖已取得了一些可喜的成果，但可以說遺傳算法的研究是一個發(fā)展中的領域，目前遺傳算法的研究僅僅是一個開端，對于未來的研究工作，我們可以從以下幾個方面來努力。遺傳算法在人工生命中的應用研究。特別是研究如何采用混合遺傳算法使人工生命外部系統(tǒng)虛擬生物的遺傳進化模型更接近自然生命的多樣性及其賴以生存的復雜環(huán)境和自然法則。目前這方面的研究只限于基本簡單的虛擬生物模型，要深入研究還需要做很多的工作。有必要開拓其它遺傳算法研究方法，為遺傳算法的研究引入新的思想。如利用數(shù)學知識，將群體表示為解集上的概率分布，這樣比簡單遺傳算法要求更少的內(nèi)存，在這方面需作更深入的探討。目前遺傳算法的研究可以說僅僅是一個開端，遺傳算法對生物演化的模擬還只是形式，未能深入到生物演化內(nèi)部規(guī)律的模擬，未能對神經(jīng)元思維的學習過程進行模擬，因此，需要對遺傳算法模型本身作更深入的探討。如果這方面有所突破，將對智能機器人的產(chǎn)生和其它許多科學產(chǎn)生深遠的影響。目前一些學者已對遺傳算法一般模型的收斂性進行了分析，證明了多種遺傳算法的概率收斂性定理，但有的概率收斂性定理還需要進行實例驗證。通過理論指導應用，反過來，由應用推動理論的發(fā)展，必然使遺傳算法的研究