【文章內容簡介】 　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)境的基因結構，再通過基因重組和基因突變等遺傳操作，就可能產生更適應環(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)遺傳算法對給定問題，可以產生許多的潛在解，最終選擇可以由使用者確定. 在某些特殊情況下，如多目標優(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)勝劣汰的選擇機制使得適應值大的個體有較大的存活機會，不同的選擇策略對算法性能有較大的影響. 輪盤賭法是使用最多的選擇策略，但這種策略可能會產生較大的抽樣誤差，于是對此提出了很多的改進方法，如繁殖池選擇、Boltzmann選擇、非線性排名選擇、基于局部競爭機制的選擇如(λ+μ)選擇等等.(4)控制參數(shù)　控制參數(shù)一般有群體大小、交換概率、變異概率等，這些參數(shù)對遺傳算法性能影響較大. 在標準的遺傳算法中采用經驗進行估計，這將帶來很大的盲目性而影響算法的全局最優(yōu)性和收斂性，人們意識到這些參數(shù)應該隨著遺傳進化而自適應變化. 基于這一觀，Davis提出自適應算子概率方法，即用自適應機制把算子概率與算子產生的個體適應性結合，高適應性值被分配高算子概率. 這種方法較好地解決了這一問題. 遺傳算法的應用領域遺傳算法提供了一種求解復雜系統(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完全問題非常有效.，例如，遺傳算法已經在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用.(3)生產調度問題. 生產調度問題在許多情況下所建立起來的數(shù)學模型難以精確求解，即使經過一些簡化之后可以進行求解，也會因簡化太多而使得求解結果與實際甚遠. 因此，目前在現(xiàn)實生產中好主要靠一些經驗進行調度. 遺傳算法已成為解決復雜高度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用.(4)自動控制. 在自動控制領域中許多與優(yōu)化相關的問題需要求解，遺傳算法的應用日益顯示了良好的效果. 例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、基于遺傳算法的模糊控制器優(yōu)化設計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進行人工神經網絡的結構優(yōu)化設計和權值學習都顯示出了遺傳算法在這些領域中應用的可能性.(5)機器人智能控制. 機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人智能控制理所當然地成為遺傳算法的一個重要應用領域. 例如遺傳算法已經在移動機器人路徑規(guī)劃、關節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行動協(xié)調等方面得到研究和應用.(6)圖像處理和模式識別. 圖像處理和模式識別是計算機視覺中的一個重要研究領域. 在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會產生一些誤差這些誤差會影響到像處理和識別的效果. 如何使這些誤差最小是使視覺達到實用化的重要要求. 遺傳算法在圖像處理中的優(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)，在許多領域得到了應用. 例基于遺傳算法的機器學習可用于調整人工神經網絡的連接權，也可用于神經網絡結構的優(yōu)化設計.(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ù)挖掘的有效方法之一.4 基于 MATLAB 的遺傳算法實現(xiàn)Matlab是一個高性能的計算軟件，配備有功能強大的數(shù)學函數(shù)支持庫，適用范圍大，編程效率高，語句簡單，功能齊備，是世界上頂級的計算與仿真程序軟件. 利用Matlab來編寫遺傳算法程序簡單而且易于操作.(1)編碼編碼就是把一個問題的可行解從其解空間轉換到遺傳算法能夠處理的搜索空間的轉化方法，編碼形式決定了重組算子的操作. 遺傳算法是對編碼后的個體作選擇與交叉運算，然后通過這些反復運算達到優(yōu)化目標. 遺傳算法首要的問題是通過編碼將決策變量表示成串結構數(shù)據(jù). 我們常用的是二進制編碼，即用二進制數(shù)構成的符號串來表示每個個體. 通常根據(jù)搜索精度(sca_var)、決策變量上界(range(2)) 的和下界(range(1))來確定各個二進制字符串的長度(bit_n)，搜索精度為sca_var=(range(2)range(1))./(2^bit_n—1)，然后再隨機產生一個的初始種群(be_gen),其規(guī)模為popusize. 15下面用encoding函數(shù)來實現(xiàn)編碼和產生初始的種群：function [be_gen,bit_n]=encoding(sca_var,range(1),range(2),popusize)bit_n=ceil(log2 (( range(2) range(1))./sca_var))；be_gen= randint( popusize, sum(bit_n))；(2)譯碼決策變量經過編碼之后，各個個體構成的種群be_gen 要通過解碼才能轉換成原問題空間的決策變量構成的種群vgen，譯碼首先要求出二進制數(shù)對應的十進制數(shù)decimal，然后根據(jù)下面的公式求出實際決策變量X： X=range(1)+decimal*sca_dec. 通常可以用decoding函數(shù) [19]來實現(xiàn)譯碼的過程：function[vgen,fitness]=decoding(f,be_gen,bit_n,range(1),range(2))popusize=size(be_gen,1)；n_var=length(bit_n)；sca_dec=(range(2) range(1))./(2^bit_n 1)；bit_n=cumsun(bit_n)；bit_n=[0 bit_n]；for i=1:n_varbe_var(i)=be_gen(:,bits(i)+1:bit_n(i+1))；var(i)= range(1)(i)+sum(ones(popusize,1)*2.^(size(be_var(i),2) 1: 1:0).*be_var(i),2).*sca_dec(i)；endvgen=[var(1,:)]；for i=1:popusizefitness(i)=eval([f,’(var_gene(i,:))’] )；end(3)選擇選擇就是利用碼后求得的各個個體的適應度的大小，從中選出一些適應度高的個體，并淘汰一些適應度較小的個體以生成交配池的過程. 然后再對優(yōu)良的個體進行交叉和變異操作. 在選擇算子中，先找出當前群體中適應度最高和最低的個體，將最佳個體bes_ind 保留并替換最差個體，直接進入下一代，將剩余個體evol_gen 按適應值16比例選擇法進行操作，即采用輪盤賭(roulettewheel)方式來實現(xiàn). 這種方式首先計算每個個體的適應值，然后計算出該適應值在群體適應值總和中所占的比例，來表示該個體被選中的概率，這樣既能保證最佳個體的適應度值不會減小，最佳個體不會被交叉變異操作所破壞，也能不斷提高該群體的平均適應度值. 比例選擇法體現(xiàn)了生物進化過程中“優(yōu)勝劣汰，適者生存” 的思想，