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