【文章內(nèi)容簡介】 　Initialize P(I)；　Fitness P(I)；10　While (not Terminate2Condition){I++；　GA2Operation P(I)；　Fitness P(I)；　　}END. 遺傳算法的特點遺傳算法不同于傳統(tǒng)的搜索和優(yōu)化方法. 主要區(qū)別在于：(1)自組織、自適應(yīng)和自學(xué)習(xí)性(智能性). 應(yīng)用遺傳算法求解問題時，在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索. 由于基于自然的選擇策略“適者生存、不適者被淘汰”，因而適應(yīng)度大的個體具有較高的生存概率. 通常適應(yīng)度大的個體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，再通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代. 進(jìn)化算法的這種自組織、自適應(yīng)特征，使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力. 自然選擇消除了算法設(shè)計過程中的一個最大障礙，即需要事先描述問題的全部特點，并要說明，利用遺傳算法，我們可以解決那些復(fù)雜的非結(jié)構(gòu)化問題.(2)遺傳算法的本質(zhì)并行性. 遺傳算法按并行方式搜索一個種群數(shù)目的點，而不是單點. 它的并行性表現(xiàn)在兩個方面，一是遺傳算法是內(nèi)在并行的( inherent parallelism)，即遺傳算法本身非常適合大規(guī)模并行. 最簡單的并行方式是讓幾百甚至數(shù)千臺計算機(jī)各自進(jìn)行獨立種群的演化計算，運行過程中甚至不進(jìn)行任何通信(獨立的種群之間若有少量的通信一般會帶來更好的結(jié)果)，等到運算結(jié)束時才通信比較，選取最佳個，可以說，遺傳算法適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行處理，而且對并行效率沒有太大影響. 二是遺傳算法的內(nèi)含并行性. 由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間內(nèi)的多個區(qū)域，并相互交流信息. 使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模N成比例的計算，但實質(zhì)上已進(jìn)行了大約O(N3)次有效搜索，這就使遺傳算法能以較少的計算獲得較大的收益.11(3)遺傳算法不需要求導(dǎo)或其他輔助知識，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù).(4)遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則.(5)遺傳算法可以更加直接的應(yīng)用.(6)遺傳算法對給定問題，可以產(chǎn)生許多的潛在解，最終選擇可以由使用者確定. 在某些特殊情況下，如多目標(biāo)優(yōu)化問題不止一個解存在，有一組pareto最優(yōu)解. 這種遺傳算法對于確認(rèn)可替代解集而言是特別合適的. [1617] 遺傳算法的改進(jìn)(1)編碼表示Holland在運用模式定理分析編碼機(jī)制時，建議使用二進(jìn)制編碼，但二進(jìn)制編碼不能直接反映問題的固有結(jié)構(gòu)精度不高，個體長度大，的措施有：①動態(tài)編碼(dynamic encoding)GA是當(dāng)算法收斂到某局部最優(yōu)時增加搜索的精度從而使得在全局最優(yōu)點附近，可以進(jìn)行更精確的搜索，增加精度的辦法是在保持串長不變的前提下減小搜索區(qū)域.②對于問題的變量是實向量的情形，可以直接采用實數(shù)進(jìn)行編碼，這樣可以直接在解的表現(xiàn)型上進(jìn)行遺傳操作，從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加算法的搜索能力.③復(fù)數(shù)編碼的GA是為了描述和解決二維問題，基因用x+yi表示,其還可以推廣到多維問題的描述中.④多維實數(shù)編碼GA使無效交叉發(fā)生的可能性大大降低，同時其合理的編碼長度也有助于算法在短時間內(nèi)獲得高精度的全局最優(yōu)解.⑤ 在組合優(yōu)化中，可以使用有序串編碼. 當(dāng)問題的表示是樹和圖時，我們還可以使用結(jié)構(gòu)式編碼.(2)適應(yīng)度函數(shù)適應(yīng)度函數(shù)是用來區(qū)分群體中個體好壞的標(biāo)準(zhǔn)，是自然選擇的唯一標(biāo)準(zhǔn)，選擇的好壞直接影響算法的優(yōu)劣. 選擇的不容易引起兩種不利于優(yōu)化的現(xiàn)象：①異常個體引起早熟收斂，影響求得全局最優(yōu)解. 這種現(xiàn)象常出現(xiàn)在小規(guī)模群體中. 在遺傳進(jìn)化的早期，一些超常個體的適應(yīng)度很大，在群體中占有很大的比例，這12些異常個體因競爭力太突出而控制了選擇過程，結(jié)果使得算法過早收斂.②個體差距不大，引起搜索成為隨機(jī)漫游. 當(dāng)群體中個體的適應(yīng)度差別不大，個體間競爭力減弱，特別是平均適應(yīng)度以接近最佳適應(yīng)度時，最佳個體與其他許多個體在選擇過程中就會有大體相等的選擇機(jī)會，從而使有目標(biāo)的優(yōu)化搜索過程變成無目標(biāo)的隨機(jī)漫游，影響求得全面最優(yōu)解. 對于上述問題可以通過引入適應(yīng)度函數(shù)定標(biāo)技術(shù)來加快收斂速度和跳出局部最優(yōu)點. 針對第一種情況，我們可以通過縮小相應(yīng)的適應(yīng)度函數(shù)值降低超常個體的競爭力；對于第二種情況，我們可以放大相應(yīng)的適應(yīng)度函數(shù)值以拉開個體之間的差距，原適應(yīng)值間的比例關(guān)系，常用的比例變換有線性變換、乘冪變換和指數(shù)變換等.(3)選擇策略優(yōu)勝劣汰的選擇機(jī)制使得適應(yīng)值大的個體有較大的存活機(jī)會，不同的選擇策略對算法性能有較大的影響. 輪盤賭法是使用最多的選擇策略，但這種策略可能會產(chǎn)生較大的抽樣誤差，于是對此提出了很多的改進(jìn)方法，如繁殖池選擇、Boltzmann選擇、非線性排名選擇、基于局部競爭機(jī)制的選擇如(λ+μ)選擇等等.(4)控制參數(shù)　控制參數(shù)一般有群體大小、交換概率、變異概率等，這些參數(shù)對遺傳算法性能影響較大. 在標(biāo)準(zhǔn)的遺傳算法中采用經(jīng)驗進(jìn)行估計，這將帶來很大的盲目性而影響算法的全局最優(yōu)性和收斂性，人們意識到這些參數(shù)應(yīng)該隨著遺傳進(jìn)化而自適應(yīng)變化. 基于這一觀，Davis提出自適應(yīng)算子概率方法，即用自適應(yīng)機(jī)制把算子概率與算子產(chǎn)生的個體適應(yīng)性結(jié)合，高適應(yīng)性值被分配高算子概率. 這種方法較好地解決了這一問題. 遺傳算法的應(yīng)用領(lǐng)域遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性即健壯性，法的一些主要應(yīng)用領(lǐng)域：(1)，也是對遺傳算法進(jìn)行性能評價的常用算例. [18] 很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)，有連續(xù)函數(shù)好有離散函數(shù)，有凸函數(shù)也有凹函數(shù)，人們用這些幾何特性各異的函數(shù)來評價遺傳算法的性能. 而對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，遺傳算法卻可以方便地得到較好的結(jié)果.13(2)組合優(yōu)化. 隨著問題規(guī)模的擴(kuò)大，組合優(yōu)化問題的搜索空間急劇擴(kuò)大，有時在目前的計算機(jī)上用枚舉法很難或者甚至不可能得到其精確最優(yōu)解. 對于這類復(fù)雜問題，人們已意識到應(yīng)把精力放在尋求其滿意解上，而遺傳算法則是尋求這種滿意解的最佳工具之一. 實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效.，例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用.(3)生產(chǎn)調(diào)度問題. 生產(chǎn)調(diào)度問題在許多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會因簡化太多而使得求解結(jié)果與實際甚遠(yuǎn). 因此，目前在現(xiàn)實生產(chǎn)中好主要靠一些經(jīng)驗進(jìn)行調(diào)度. 遺傳算法已成為解決復(fù)雜高度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用.(4)自動控制. 在自動控制領(lǐng)域中許多與優(yōu)化相關(guān)的問題需要求解，遺傳算法的應(yīng)用日益顯示了良好的效果. 例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、基于遺傳算法的模糊控制器優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性.(5)機(jī)器人智能控制. 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域. 例如遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運動軌跡規(guī)劃、機(jī)器人逆運動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動協(xié)調(diào)等方面得到研究和應(yīng)用.(6)圖像處理和模式識別. 圖像處理和模式識別是計算機(jī)視覺中的一個重要研究領(lǐng)域. 在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會產(chǎn)生一些誤差這些誤差會影響到像處理和識別的效果. 如何使這些誤差最小是使視覺達(dá)到實用化的重要要求. 遺傳算法在圖像處理中的優(yōu)化計算方面是完全勝任的. 目前已在圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識別等方面得到了應(yīng)用.(7)人工生命. 人工生命是用計算機(jī)等人工媒體模擬或構(gòu)造出具有自然生物系統(tǒng)特有行為的人造系統(tǒng). 自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征. 人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ). 雖然人工生命的研究尚處于啟蒙階段,但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、14行為模型等方面顯示了初步的應(yīng)用能力. 可以預(yù)見，遺傳算法在人工生命及復(fù)雜自適應(yīng)系統(tǒng)的模擬與設(shè)計、復(fù)雜系統(tǒng)突現(xiàn)性理論研究中，將得到更為深入的發(fā)展.(8)遺傳程序設(shè)計. 1989年，美國Standford大學(xué)的Koza教授發(fā)展了遺傳編程的概念，其基本思想是:采用樹型結(jié)構(gòu)表示計算機(jī)程序，運用遺傳算法的思想，通過自動生成計算機(jī)程序來解決問題. 雖然遺傳編程的理論尚未成熟，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域，目前公開的遺傳編程實驗系統(tǒng)有十多個，例如，Koza開發(fā)的ADF系統(tǒng)，White開發(fā)的GPELST系統(tǒng)等.(9)機(jī)器學(xué)習(xí). 學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一. 基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在許多領(lǐng)域得到了應(yīng)用. 例基于遺傳算法的機(jī)器學(xué)習(xí)可用于調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可用于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化設(shè)計.(10)數(shù)據(jù)挖掘. 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則. 許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略. 因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化，直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則. Sunil已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘工具，利用該工具對兩個飛機(jī)失事的真實數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒灒Y(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一.4 基于 MATLAB 的遺傳算法實現(xiàn)Matlab是一個高性能的計算軟件，配備有功能強(qiáng)大的數(shù)學(xué)函數(shù)支持庫，適用范圍大，編程效率高，語句簡單，功能齊備，是世界上頂級的計算與仿真程序軟件. 利用Matlab來編寫遺傳算法程序簡單而且易于操作.(1)編碼編碼就是把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法能夠處理的搜索空間的轉(zhuǎn)化方法，編碼形式?jīng)Q定了重組算子的操作. 遺傳算法是對編碼后的個體作選擇與交叉運算，然后通過這些反復(fù)運算達(dá)到優(yōu)化目標(biāo). 遺傳算法首要的問題是通過編碼將決策變量表示成串結(jié)構(gòu)數(shù)據(jù). 我們常用的是二進(jìn)制編碼，即用二進(jìn)制數(shù)構(gòu)成的符號串來表示每個個體. 通常根據(jù)搜索精度(sca_var)、決策變量上界(range(2)) 的和下界(range(1))來確定各個二進(jìn)制字符串的長度(bit_n)，搜索精度為sca_var=(range(2)range(1))./(2^bit_n—1)，然后再隨機(jī)產(chǎn)生一個的初始種群(be_gen),其規(guī)模為popusize. 15下面用encoding函數(shù)來實現(xiàn)編碼和產(chǎ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)譯碼決策變量經(jīng)過編碼之后，各個個體構(gòu)成的種群be_gen 要通過解碼才能轉(zhuǎn)換成原問題空間的決策變量構(gòu)成的種群vgen，譯碼首先要求出二進(jìn)制數(shù)對應(yīng)的十進(jìn)制數(shù)decimal，然后根據(jù)下面的公式求出實際決策變量X： X=range(1)+decimal*sca_dec. 通?？梢杂胐ecoding函數(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īng)度的大小，從中選出一些適應(yīng)度高的個體，并淘汰一些適應(yīng)度較小的個體以生成交配池的過程. 然后再對優(yōu)良的個體進(jìn)行交叉和變異操作. 在選擇算子中，先找出當(dāng)前群體中適應(yīng)度最高和最低的個體，將最佳個體bes_ind 保留并替換最差個體，直接進(jìn)入下一代，將剩余個體evol_gen 按適應(yīng)值16比例選擇法進(jìn)行操作，即采用輪盤賭(roulettewheel)方式來實現(xiàn). 這種方式首先計算每個個體的適應(yīng)值，然后計算出該適應(yīng)值在群體適應(yīng)值總和中所占的比例，來表示該個體被選中的概率，這樣既能保證最佳個體的適應(yīng)度值不會減小，最佳個體不會被交叉變異操作所破壞，也能不斷提高該群體的平均適應(yīng)度值. 比例選擇法體現(xiàn)了生物進(jìn)化過程中“優(yōu)勝劣汰，適者生存” 的思想，