時間：2022-11-21 03:19:50
序論：速發(fā)表網(wǎng)結合其深厚的文秘經(jīng)驗，特別為您篩選了11篇遺傳算法論文范文。如果您需要更多原創(chuàng)資料，歡迎隨時與我們的客服老師聯(lián)系，希望您能從中汲取靈感和知識！
2遺傳算法在計算機網(wǎng)絡可靠度優(yōu)化計算中的應用研究
2.1遺傳運算方法
在計算機網(wǎng)絡中遺傳運算主要是以變異和交叉這兩種方式進行。交叉主要是通過在網(wǎng)絡結點的范圍（[1，N]）之間的隨機數(shù)，以此作為基因交叉位置的設置且一次只可以操作一個結點。這樣能夠最大程度地確保網(wǎng)絡的連通性，但也有可能出現(xiàn)錯的連通結構，所以進行調(diào)整操作；變異則是先確定基因的變異和數(shù)目，然后再根據(jù)范圍來選擇新的基因段替換舊基因段生成后代。一般變異率都在0.001到0.01內(nèi)，如是變異出現(xiàn)了錯誤的網(wǎng)絡連通結構基因，就必須進行相應的調(diào)整。
1．1動力學休止角(γ)［4，10］抄板上的物料表面在初始狀態(tài)時保持穩(wěn)定，直到物料表面與水平面的夾角大于物料的休止角(最大穩(wěn)定角)時才發(fā)生落料情況。隨著轉筒的轉動，抄板上物料的坡度會一直發(fā)生改變。當物料的坡度大于最大穩(wěn)定角時，物料開始掉落。此時，由于物料的下落，物料表面重新達到最大穩(wěn)定角開始停止掉落。然而，抄板一直隨著轉筒轉動，使得抄板內(nèi)物料的坡度一直發(fā)生改變，物料坡度又超過最大休止角。這個過程一直持續(xù)到抄板轉動到一定位置(即抄板位置處于最大落料角δL時)，此時抄板內(nèi)的物料落空。通常，在計算抄板持有量時，會采用動力學休止角來作為物料發(fā)生掉落的依據(jù)，即抄板內(nèi)的物料坡度超過γ時，物料開始掉落。該角主要與抄板在滾筒中的位置δ、動摩擦因數(shù)μ和弗勞德數(shù)Fr等有關。
1．2抄板持有量的計算
隨著抄板的轉動，一般可以將落料過程劃分為3部分(R－1，R－2，R－3)，如圖1(a)所示。在轉動過程中，當抄板轉角δ超過動力學休止角γ時，落料過程從R－1區(qū)域轉變到R－2區(qū)域，在這兩個區(qū)域內(nèi)，物料不僅受到抄板的作用還受到滾筒壁面的作用。當物料表面上的A點與D點重合時，從R－2區(qū)域轉變到R－3區(qū)域，在該區(qū)域內(nèi)，物料僅受抄板作用［4］。然而，抄板情況為圖1(c)、圖1(d)時只會經(jīng)歷R－1、R－3區(qū)域。因為在運轉過程中，抄板上物料的A點與D點重合時抄板的轉角不會超過動力學休止角γ，所以不會經(jīng)歷R－2區(qū)域;但是，當物料的休止角足夠小時，由于物料表面只會與抄板接觸(即A點不會超出D點)，圖1(c)、圖1(d)的抄板落料過程只會經(jīng)歷R－3區(qū)域。以下根據(jù)不同的區(qū)域建立了不同組合下抄板持料量的數(shù)學模型。
2研究結果與分析
2．1最大落料角結果分析
通過MatLab編制以上推導公式的計算程序，模擬計算了120種不同組合(β、θ、a不同)下抄板的最大落料角。其中，物料動摩擦因數(shù)為0．53［8］，轉筒干燥機半徑為300mm，且其抄板安裝角為10°、30°、50°、70°、90°、110°，抄板間夾角為90°、110°、130°、150°，抄板縱向長度a為30、45、60、75、90mm，橫向長度b為60mm。并且，根據(jù)Kelly和O＇Donnell通過驗證得出的公式(1)只適用于Fr小于0．4的情況［4］，此次模擬的轉筒干燥機角速度為0．84rad/s。表1給出了模擬結果中較為典型的數(shù)據(jù)。從模擬結果中可以得出，當a、θ不變時，δL隨著安裝角β的增大而增大;當a、β不變時，δL隨著θ的增大而減小。當抄板情況如圖1(a)、(b)、(c)時，且β、θ不變時，抄板最大落料角隨著長度a的增大而增大;而圖1(d)情況則反之，并且會出現(xiàn)最大落料角小于0°的情況，這是由于抄板無法抄起物料所導致的結果。另外，在圖1(d)情況下，抄板的最大落料角非常小，這會使得干燥器的效率很低。因此，在探討抄板優(yōu)化問題上，不考慮圖1(d)這種情況下的抄板。
2．2優(yōu)化目標與結果分析
水平直徑上均勻撒料雖好，但是物料應與熱氣均勻接觸，如果在路徑長的地方撒料多些，就可以使熱效率高些。又因為圓筒中心熱氣量比邊緣多以及在圓筒下半部分超出干燥圓的區(qū)域存在物料，所以落料均勻度考慮為物料在干燥圓橫截面積上撒料均勻。評判干燥圓橫截面積上落料均勻的具體方法如下:把干燥圓橫截面積劃分20個等分，以水平直徑為X軸，鉛垂直徑為Y軸，圓心O為原點，采用定積分方法求解每個劃分點的x坐標，每個劃分點的鉛垂線與干燥圓壁面(上半部分)有一個交點，連接圓心與每個點，可以得出每條連線與X軸的夾角δi(i=1～21，步長為1，δ1為0°)，如圖2所示。在合理的設計下，不僅希望落料過程中抄板在干燥圓面積上撒料越均勻越好，δL也應越接近180°越好。因此，優(yōu)化函數(shù)為最大落料角和抄板在干燥圓而積上落料的均方差。并且，根據(jù)國內(nèi)外實際情況，抄板的安裝角一般為90°并且抄板間夾角一般不為銳角，由于機構的限制和不考慮圖1(d)的情況，在研究抄板優(yōu)化問題時只探討安裝角在70°～110°、抄板夾角在90°～130°以及抄板縱向長度在30～90mm之間的情況。其余參數(shù)同上。采用了線性加權和法來求解此多目標優(yōu)化結果。其中，f1為1/δL的最優(yōu)化值，f2為q的最優(yōu)化值;均方差q=(1n∑ni=1(qi－qa)2)12，每相鄰角度落料面積差qi=A(δi)－A(δi+1)，qa為面積差的平均值。當δL≤δi+1－δi2，n=i;反之則n=i+1，且δi+1=δL。s1、s2為權重系數(shù)，由于干燥器的效率主要與抄板的撒料均勻有關，但是如果落料角很小、撒料很均勻，干燥器效率也不高，綜合考慮下，取s1、s2分別為0．4、0．6。通過編寫MatLab程序，確定優(yōu)化函數(shù)，然后采用MatLab遺傳算法工具箱進行計算，設置相關參數(shù):最大代數(shù)為51，種群規(guī)模為20，交叉概率為0．2，選擇概率為0．5。運行算法并顯示結果，β、θ、a較優(yōu)結果分別為:1．844rad、1．571rad、51．609mm。
0引言
遺傳算法是一種較新的全局優(yōu)化搜索算法，它使用了群體搜索技術，用種群代表一組問題解，通過對當前種群施加選擇、交叉和變異等一系列遺傳操作，從而產(chǎn)生新的一代種群，并逐漸使種群進化到包含最優(yōu)解或近似最優(yōu)解的狀態(tài)。但由于算法復雜度的限制, 遺傳算法雖然能以概率收斂到全局最優(yōu)解，其局部搜索速度和精度并不能得到很好的保證。近幾年來遺傳算法作為優(yōu)良的全局尋優(yōu)方法日趨成熟,尤其是和其他尋優(yōu)方法的結合,進一步提高了遺傳算法的性能，其中借助于混沌改進遺傳算法的性能,是近年來遺傳算法領域研究的熱點之一，遺傳算法和混沌優(yōu)化的組合,可以使遺傳算法的全局尋優(yōu)能力,搜索精度,搜索速度等幾方面得到較明顯的改進。
1混沌的特征和蟲口方程
混沌是存在于非線形系統(tǒng)中的一種較為普遍的現(xiàn)象?；煦绮⒉皇且黄靵y，而是有著精致內(nèi)在結構的一類現(xiàn)象?；煦邕\動具有遍歷性、隨機性等特點，混沌運動能在一定的范圍內(nèi)按照其自身的規(guī)律不重復地遍歷所有狀態(tài)。因此，如果利用混沌變量進行優(yōu)化搜索，無疑會比隨機搜索更具有優(yōu)越性。
描述生態(tài)學上的蟲口模型Logistic映射自May于1976年開始研究以來，受到了非線形科學家的高度關注，Logistic映射是混沌理論發(fā)展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遺傳算法
GA較傳統(tǒng)數(shù)學優(yōu)化方法更易找到全局最優(yōu)解，但對于一些問題也存在過早收斂、收斂速度較慢、難以找到較精確解的情況。因此，本文通過Logistic映射及相關混沌理論提出了一種運算性能較好的混沌遺傳函數(shù)優(yōu)化算法?；煦邕z傳算法(CGA)的主要步驟如下：
1.初始化:預先確定運行參數(shù)，包括：種群規(guī)模M，交叉概率pc，變異概率pm，最大迭代次數(shù)n。隨機產(chǎn)生一個分布均勻的初始群體(包含n個初始解)，計算各個個體的適應度值；
2.采用比例選擇算子對當前種群進行選擇操作，實現(xiàn)強留劣汰；
3.對當前種群進行交叉運算。將種群內(nèi)個體兩兩隨機組合，對每個配對的組合，首先由系統(tǒng)隨機生成一個(0,1)之間的數(shù)，由交叉概率決定是否交叉。論文參考。論文參考。若交叉，則采用映射生成的序列經(jīng)簡單映射后利用高斯函數(shù)來決定交叉位置，否則，看下一對組合。所有的交叉位置由一個混沌序列即可決定；
5.若終止條件滿足，則算法中止，否則轉向步驟(2)。
本文嘗試在將改進后的遺傳算法與混沌優(yōu)化算法相結合，提出一種基于混沌理論的混合遺傳算法，算法的流程如下頁流程圖所示：
圖1 改進后的混沌遺傳算法（ICGA）流程圖
3仿真分析
本文選用一維和多維多峰值函數(shù)為例，見表1，用遺傳算法（GA）、混沌遺傳算法（CGA）和本文算法（ICGA）進行比較研究。
表1 測試函數(shù)
實驗結果比較如下（以下圖縱坐標表示最大適應值，橫坐標表示演化代數(shù)）
圖2 f2實驗結果比較示意圖圖3 f3實驗結果比較示意圖
從圖2、圖3的比較結果看，本文中算法初始種群較好，進化開始就能找到高的最大值，加快搜索的速度，整個算法的尋優(yōu)結果比遺傳算法好。論文參考?？紤]到算法中使用了隨機操作，僅僅由一次實驗得到的結果是不能夠充分說明問題的，因此，再進行統(tǒng)計比較。本文中進行了20次統(tǒng)計實驗。比較結果如表2
中圖分類號:TP18 文獻標識碼:A 文章編號:1674-7712 (2012) 12-0176-01
一、引言
遺傳算法不同于傳統(tǒng)尋優(yōu)算法的特點在于:遺傳算法在尋優(yōu)過程中,僅需要得到適應度函數(shù)的值作為尋優(yōu)的依據(jù);同時使用概率性的變換規(guī)則,而不是確定性的變換規(guī)則;遺傳算法適應度函數(shù)的計算相對于尋優(yōu)過程是獨立的;算法面對的是參數(shù)的編碼集合,而并非參數(shù)集合本身,通用性強。它尤其適用于處理傳統(tǒng)優(yōu)化算法難于解決的復雜和非線性問題。[1]
目前,GA已經(jīng)在很多領域得到成功應用,但隨著問題規(guī)模的不斷擴大和搜索空間的更加復雜,GA在求解很多具體問題時往往并不能表現(xiàn)出其優(yōu)越性。于是,近年來便出現(xiàn)了遺傳算法與其它理論相結合的實踐,其中遺傳算法與量子理論的結合是一個嶄新的、極富前景和創(chuàng)意的嘗試。
量子遺傳算法QGA是量子計算特性與遺傳算法相結合的產(chǎn)物?；诹孔颖忍氐寞B加性和相干性,在遺傳算法中借鑒量子比特的概念,引入了量子比特染色體。由于量子比特染色體能夠表征疊加態(tài),比傳統(tǒng)GA具有更好的種群多樣性,同時QGA也會具有更好的收斂性,因此在求解優(yōu)化問題時,QGA在收斂速度、尋優(yōu)能力方面比GA都將有較大的提高。QGA的出現(xiàn)結合了量子計算和遺傳算法各自的優(yōu)勢,具有很高的理論價值和發(fā)展?jié)摿Α?/p>
本論文提出用量子遺傳算法處理和解決多目標分配問題,為多目標問題的解決提供一種新的思路。
二、量子遺傳算法
在傳統(tǒng)計算機中,信息存儲是以二進制來表示,不是“0”就是“1”態(tài),但是在量子計算機中,充當信息存儲單元的物質(zhì)是一個雙態(tài)量子系統(tǒng),稱為量子比特(qubit),量子比特與比特不同之就在于它可以同時處在兩個量子態(tài)的疊加態(tài),量子進化算法建立在量子的態(tài)矢量表述基礎上,將量子比幾率幅表示應用于染色體的編碼,使得一條染色體可以表示個態(tài)的疊加,并利用量子旋轉門更新染色體,從而使個體進達到優(yōu)化目標的目的。
一個 位的量子位染色體就是一個量子位串,其表示如下:
其中 。在多目標優(yōu)化中,一個量子染色體代表一個決策向量,在量子態(tài)中一個 位的量子染色體可以表達 個態(tài),采用這種編碼方式使得一個染色體可以同時表達多個態(tài)的疊加,使得量子進化算法比傳統(tǒng)遺傳算法擁有更好的多樣性特征。
為了實現(xiàn)個體的進化,經(jīng)典進化算法中通過染色體的交叉、變異操作推進種群的演化,而對量子進化算法而言,量子染色體的調(diào)整主要是通過量子旋轉門實現(xiàn)的,算法流程如下:
(1)進化代數(shù)初始化: ;
(2)初始化種群 ,生成并評價 ;
(3)保存 中的最優(yōu)解 ;
(4) ;
(5)由 生成 ;
(6)個體交叉、變異等操作,生成新的 (此步可省評價);
(7)評價 ,得到當前代的最優(yōu)解 ;
(8)比較 與 得到量子概率門 ,保存最優(yōu)解于 ;
(9)停機條件 當滿足停機條件時,輸出當前最優(yōu)個體,算法結束,否則繼續(xù);
(10)以 更新 ,轉到4)。
三、基于量子遺傳算法的多目標分配應用
如今為了滿足市場的需要,很多工廠的生產(chǎn)種類多、生產(chǎn)量大,從而設置了不同的生產(chǎn)車間,根據(jù)產(chǎn)品的性質(zhì)分配生產(chǎn)車間合理與否直接影響工廠的經(jīng)濟收益,這同樣可采用遺傳算法的目標分配方法進行分配。
模型構建:設工廠有i個生產(chǎn)車間。 為在第i個車間生產(chǎn)第j種產(chǎn)品的收益, 為第j種產(chǎn)品的需求量;如果第j種產(chǎn)品被選中,則 為在第i個車間生產(chǎn)該產(chǎn)品的總收益。由題意知為求解 最大問題。
仿真實例:設有10個生產(chǎn)車間,要生產(chǎn)15種產(chǎn)品,用Matlab程序編程,設定40個粒子,迭代200次,代溝0.9。運行結果如下:
此圖表明經(jīng)200次迭代后的目標分配方案為:第1種產(chǎn)品由第3個車間生產(chǎn),以此類推,車間5生產(chǎn)第2種產(chǎn)品,車間8生產(chǎn)第3種產(chǎn)品,……。次方案對應的車間總收益值為2.7030e+003,成功進行了多目標分配問題的解決。
四、結論
基于量子遺傳算法的多目標分配,為多目標分配突破傳統(tǒng)尋優(yōu)模式找到了一個可行的解決方法。根據(jù)這種方法實驗,仿真結果可以看出,基本符合要求,并且能夠在一定的時間內(nèi)得到最優(yōu)的分配方案,因此,本文在探索多目標分配問題上找到了一種新的解決思路。
參考文獻:
[1]吉根林.遺傳算法研究綜述[J].計算機應用與軟件,2004,21(2):69-73
[2]肖曉偉,肖迪.多目標優(yōu)化問題的研究概述[J].計算機應用研究,2011,3,28(3):805-808
中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)1110086-01
一、引言
網(wǎng)格計算是在Internet上的一組新興技術,利用共享網(wǎng)絡提供強大的計算能力,任務調(diào)度系統(tǒng)是其重要的組成部分,它根據(jù)任務信息采用適當?shù)牟呗园巡煌娜蝿辗峙涞较鄳馁Y源節(jié)點上運行。由于網(wǎng)格系統(tǒng)的異構性和動態(tài)性,使得任務調(diào)度變得極其復雜。
在過去學者已經(jīng)成功地把各個人工智能算法應用到網(wǎng)格任務調(diào)度系統(tǒng)中,如神經(jīng)網(wǎng)絡、蟻群算法、min-min算法等,并取得了巨大的成果,但由于系統(tǒng)通常不會處于以單一狀態(tài)中以人們所期望的狀態(tài)發(fā)展,從而導致了任務調(diào)度的復雜性,服務器由于工作任務的不確定導致在網(wǎng)格任務的運行過程當中,可能會因為其他原因導致網(wǎng)格任務執(zhí)行的失敗,同時也會導致服務器的運行錯誤。對于這種情況,過去的任務調(diào)度算法并沒有考慮,所以本文結合支持向量機(SVM)與遺傳算法對動態(tài)資源進行預測,從而達到自適應的目的。
支持向量機可以成功地處理回歸問題和模式識別等問題。支持向量機將向量映射到一個更高維的空間里,在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。建立方向合適的分隔超平面使兩個與之平行的超平面間的距離最大化。其中支持向量機的關鍵是核函數(shù)的選取,本論文為了得到精確的數(shù)據(jù),選用徑向基(RBF)核函數(shù)來進行。
在任務的分配方案中,本論文選擇了遺傳算法進行任務調(diào)度,遺傳算法(Genetic Algorithm)是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法是從代表問題可能潛在的解集的一個種群開始的,而一個種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成。初代種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐代演化產(chǎn)生出越來越好的近似解,在每一代,根據(jù)問題域中個體的適應度大小選擇個體,并借助于自然遺傳學的遺傳算子進行組合交叉和變異,產(chǎn)生出代表新的解集的種群。在本論文中就是利用遺傳算法的這一特性來對任務進行調(diào)度分配。
二、基于性能預測機制的遺傳算法任務調(diào)度總體框架
在調(diào)度框架中,為了使調(diào)度算法可以先對重要任務或資源緊急的任務進行快速處理,所以引入了QoS機制,對每個任務進行QoS計算,對QoS進行排序,把QoS最高的任務首先輸入調(diào)度系統(tǒng),優(yōu)先執(zhí)行。
1.對初始任務的QoS進行排序,然后按順序輸入到任務調(diào)度系統(tǒng)的任務群中。
2.在得到排序后的任務群后,利用以往的網(wǎng)格節(jié)點狀態(tài)數(shù)據(jù)進行SVM的分類預測,估計服務器的運行情況,以調(diào)整遺傳算法的系統(tǒng)參數(shù)。
3.利用遺傳算法對任務進行調(diào)度。
4.調(diào)度任務運行,并且記錄實際結果,不斷調(diào)度任務,直至任務隊列為空。
三、基于支持向量機的網(wǎng)格節(jié)點性能預測模型
本文討論的網(wǎng)格框架作為一個純計算網(wǎng)格的框架,顯然網(wǎng)格節(jié)點需要要比其他服務器擁有更快的速度、更大的內(nèi)存,在通常條件下這些服務器都用在商業(yè)或科研環(huán)境下,而并非私人使用,所以服務器負載具有十分明顯的周期性。
經(jīng)過實驗證明,該模型可以對網(wǎng)格節(jié)點負載進行有效預測。
四、基于遺傳算法的任務調(diào)度算法
在網(wǎng)格計算中,任務調(diào)度的實質(zhì)是將n個相互獨立的任務分配到m個異構可用資源上,使得總任務的完成時間最小以及資源得到充分的利用。具體描述如下:
1.J是n個需要調(diào)度的任務集合,表示第個任務。
2.R是m個可用資源集合,表示第i個資源。
3.n個任務m個不同資源上的執(zhí)行時間 是一個 的矩陣。
表示第i個任務在第j個資源上的執(zhí)行時間。
4.把任務i所需要的數(shù)據(jù)從存儲系統(tǒng)傳輸?shù)劫Y源j的傳輸時間為
。
5.所有任務都執(zhí)行完成的時間為時間跨度(),即
由于網(wǎng)格任務調(diào)度的目標是時間跨度盡可能的短,因此適應度函數(shù)可以定義為:
而染色體的編碼則用二進制編碼方式來完成,把一個任務調(diào)度矩陣轉化為一個一維的二進制數(shù)列。
五、網(wǎng)格調(diào)度實驗
在實驗中,任務的CPU時間為0到100的隨機數(shù),內(nèi)存為0到900的隨機數(shù)。在代表程序運行之前,最大等待時間以70步長的時間隨機遞增,以提供一系列的任務。網(wǎng)格節(jié)點CPU最大時間為1000到3000的隨機數(shù),總體內(nèi)存為4000到12000的隨機數(shù)。
從上表可知,在10次的試驗中,遺傳算法整體上任務調(diào)度性能比min-min算法優(yōu)越,其中遺傳算法的運行時間均比min-min算法的運行時間少,而且在任務的丟棄方面,遺傳算法的任務丟棄數(shù)量也比min-min算法的任務丟棄少。從而表明遺傳算法比min-min算法有著更優(yōu)秀的執(zhí)行效率。
六、結論
本論文對基于動態(tài)資源預測的遺傳算法進行研究,實驗驗證了該算法作為調(diào)度函數(shù)的網(wǎng)格任務調(diào)度模型性能更加優(yōu)越,不僅縮短了任務的調(diào)度時間,也增加了任務調(diào)度可靠性,整體上優(yōu)于基于min-min算法網(wǎng)格任務調(diào)度模型。
參考文獻:
[1]張穎峰、李毓麟,基于進化算法的網(wǎng)格計算資源管理調(diào)度系統(tǒng)[J].計算機工程,2003,29(15):110-111.
[2]Carretero J,Xhafa F.Use of Genetic Algorithms for Scheduling Jobs in Large Scale Grid Applications[J].ūKIO TECHNOLOGINIS IR EKONOMINIS VYSTYMAS.2006,12(1):11-17.
[3]Abraham A,Buyya R,Nath B.Nature's heuristics for scheduling jobs on computational grids[C].2000.
1 前言
對于一個粗糙集決策屬性表，人們總是期望能找出所有約簡或最小約簡，然而一個信息表的屬性約簡并不是唯一的，得到信息表的包含最少條件屬性的約簡已被證明是NP 完全問題。由于免疫遺傳算法在NP問題領域取得了比較好的效果，論文提出了一種基于免疫遺傳算法的粗糙集屬性約簡算法，實驗結果證明該算法是有效的，可快速收斂到全局最優(yōu)解。
2 屬性約簡的免疫遺傳算法設計
2.1 染色體編碼
采用傳統(tǒng)的二進制編碼，即若決策表中有N個待約簡的條件屬性，算法產(chǎn)生一個長度為N的0-1二進制串，每一位代表一種對條件屬性的取舍，1表示采用該位上的條件屬性，0則表示不采用。
2.2 初始種群的產(chǎn)生
初始種群設置的好壞直接影響到最后的求解效果。任何一個信息表或決策表的相對核都包含在所有相對約簡當中，即具有唯一性。因此考慮在產(chǎn)生初始種群的時候使每個染色體都含有相對屬性核。
2.3 適應度函數(shù)的構造
適應度函數(shù)用來評價染色體的優(yōu)劣，在對每一個染色體進行適應度評價前，先要對每個染色體進行一定的調(diào)整。調(diào)整是基于屬性重要度相關的某種啟發(fā)式信息，給出染色體的調(diào)整步驟：
（1）計算決策表S中條件屬性集C關于決策屬性集D的重要度γc（D）；
（2）設C'為當前染色體采用的條件屬性集，計算條件屬性集C'關于決策屬性集D的重要度γc'（D）；
（3）比較γc（D）和γc'（D）的大小，若γc'（D）
（4）對任意屬性ai（∈C-C'）（1=1，2，…，|C-C'|），計算每一個μD（ai），令j={j|μD（aj）=max（μD （ai））}，然后將染色體上第j位上的0置為1，并且C'=C'∪{aj}，轉到步驟②；
（5）調(diào)整過程結束。當染色體經(jīng)過如上調(diào)整以后，就可以應用適應度函數(shù)對該染色體進行評價，適應度函數(shù)的計算公式為：
F=|C|-|C'| （5.16）
則染色體中采用的條件屬性個數(shù)越少，該染色體的適應度函數(shù)值就越高，個體就越優(yōu)良。
2.4 抗體產(chǎn)生的促進和抑制
要使適應度高的抗體進行促進，濃度高的抗體進行抑制。
抗體相似性通過抗體編碼的Manhattan距離來度量?？贵wX={a1，a2，…an}與抗體Y={b1，b2，…bn}之間的相似度為：
d值越大，表示兩者的相似程度越低，如果d=0，則表示兩個抗體完全相同。故抗體X的濃度定義為：
其中，函數(shù)D（X）表示抗體X相似度小于λ的抗體數(shù)目，λ為一給定的閾值
2.5 基于收縮精度的逐級進化策略
可以用收縮精度作為算法的停止準則，即當收縮精度小于某個比較小的正數(shù)K時算法停止進化。假設優(yōu)化目標為求目標函數(shù)F的最大值，在不同的進化時期適應度函數(shù)J采用不同的形式如下：
式中α、β、k1 和k1為正數(shù)，根據(jù)優(yōu)化目標的需要取不同的值。其中α 和β是為了在算法的中后期拉大群體內(nèi)個體之間的差距，α
3 實例分析
在某次戰(zhàn)斗任務中，我方使用各種常規(guī)武器對敵方6處戰(zhàn)場目標實施打擊。參與毀傷效果評估計算的我方武器“投入”和“產(chǎn)出”數(shù)據(jù)離散化得出一個毀傷評估決策信息表。應用改進的遺傳算法進行屬性約簡。圖1所示為免疫遺傳算法求解最優(yōu)約簡屬性向量的迭代過程。改進后的基于收縮精度的遺傳算法在進化15代以后即停止搜索，得出了近似最優(yōu)解。
由圖1可以看出在算法的進化過程中，迭代曲線每隔幾代都會變化一次。并且在算法的中后期，曲線依然出現(xiàn)明顯變化。一方面說明算法自始自終都實現(xiàn)了對解空間的有效搜索，另一方面與傳統(tǒng)算法相比，沒有出現(xiàn)過早收斂的現(xiàn)象。說明改進后免疫遺傳算法的科學性和有效性。
參考文獻
[1]曾子林，張宏軍，張睿，邢英.變精度粗糙集的邏輯解釋及其約簡[J].計算機應用研究，2013（05）.
[2]肖大偉，王國胤，胡峰.一種基于粗糙集理論的快速并行屬性約簡算法[J].計算機科學，2009（03）.
隨著經(jīng)濟全球化趨勢的加強，科學技術尤其是信息技術的發(fā)展突飛猛進，產(chǎn)品營銷范圍日趨擴大，社會生產(chǎn)、物資流通、商品交易及其管理方式正在發(fā)生著深刻的變革，與此相適應，被普遍認為企業(yè)在降低物資消耗、提高勞動生產(chǎn)率以外的“第三利潤源”的現(xiàn)代物流在世界范圍內(nèi)廣泛興起，目前正在成為全球經(jīng)濟發(fā)展的一個重要熱點和新的經(jīng)濟增長點。隨著傳統(tǒng)批發(fā)、交通運輸、倉儲業(yè)向現(xiàn)代物流轉化，尤其是配送方式的采用，對運輸成本和時間的有效控制日漸成為城市配送車輛路徑問題的一項重要目標。VRP一直以來都是車輛調(diào)度所重點研究的方向。而在城市內(nèi)采取的配送方式恰恰具備了VRP問題的一般特征和優(yōu)化調(diào)度條件。
一、VRP模型的條件及假設
VRP問題是指按要求用多個車輛從配送中心對顧客進行配給貨物。各顧客點的位置和需求量為己知，各車輛的裝載質(zhì)量己知，力求尋找一個好的配送方案，使得總代價最小(車輛盡量少，行車總距離盡量短，總費用盡量低等)，由VRP的定義不難看出，必須滿足以下條件及假設：
1.僅考慮位置已知的單一配送中心，所有的配送車輛以配送中心為起點，并最終回到配送中心。
2.每條配送路徑上各需求點的需求量之和不超過車輛的裝載質(zhì)量，被配送貨物是可混裝的貨物。
3.每條配送路徑的長度不超過車輛一次允許行駛的最大距離，配送中心有足夠的資源以供配送，并且有足夠的運輸能力。
4.各個客戶需求和所在地均已知，每個需求點的需求由且僅由一輛車一次送貨滿足。
5.滿足總時間約束與時間窗口。必須在時間區(qū)間[ei,lj]訪問點i客戶，并允許在i處等待，車輛服務的總時間不能超過物流中心的時間約束。
6.多個客戶之間存在優(yōu)先關系，必須在訪問客戶j之前訪問客戶i。
二、帶時間窗VRP模型的建立
基于文獻一文中的模型，并考慮配送系統(tǒng)是一個服務系統(tǒng)，所提供的服務必須能夠讓客戶方便、滿意。配送系統(tǒng)的運作成本必須和配送系統(tǒng)其他性能參數(shù)綜合進行考評，單純對成本進行評價是沒有任何實際意義的。需要關注和努力的是：要在保證配送滿足客戶要求、提升客戶滿意度的同時，通過各種技術和管理手段，降低運作成本。因此，本文將建立改進的運輸路徑模型，在傳統(tǒng)的車輛配送成本最小化目標的基礎上，兼顧客戶對配送時間的要求，使車輛等待和延誤時間之和最小化。
（1）
（2）
式中K――車隊規(guī)模，即總的車輛數(shù)目；
k――車輛數(shù)目(k=1,2,……,K)；
N――有待訪問的總的客戶的數(shù)目；
O――配送中心；
Q――每輛車輛的容量，這里假設所有車輛同質(zhì)，容量均為Q;
i,j――顧客數(shù)(i=1,2,……,N；j=1,2,……,N)；
T――個很大的數(shù)字；
C――每輛車單位運距的運費；
t0――車輛從配送中心出發(fā)的時間；
e0――車輛可離開配送中心的最早時間；
ei――到達客戶i處規(guī)定最早到達時間；
l0――車輛返回配送中心的最晚時間；
li――到達客戶i處規(guī)定最晚到達時間；
dij――從客戶i到客戶j的距離；
pj――每個客戶單位卸貨量的卸載費用；
mi――客戶i的貨運需求量；
tki、tkj――第k輛車到達客戶i、j處的時間；
tij――連接客戶i和客戶j的行駛時間；
si――客戶i處的服務時間；
wi――在客戶i的等待時間，wi≥0。
兩個決策變量如下：
這個模型通用性很強，經(jīng)過參數(shù)的不同設定，可以轉換為其它組合優(yōu)化問題的數(shù)學模型。
三、帶時間窗VRP模型的遺傳算法求解
在模型的處理上，根據(jù)本文提出的模型單位標量不統(tǒng)一的特殊性來選擇權重系數(shù)變化法，將變化后的多目標函數(shù)經(jīng)分析和試驗得出各個子目標函數(shù)的數(shù)量級大小并確定權重，最后加權化為單目標函數(shù)用遺傳算法求解。
1.懲罰函數(shù)的引入。在以往的對含有時間窗約束的車輛配送系統(tǒng)的研究中，所研究的成本大多僅包含行駛成本，但事實上，還包括其它成本(如裝卸搬運成本)，將時間窗約束轉化為懲罰函數(shù)而體現(xiàn)在模型中。
式中c1――車輛在任務點處等待單位時間的機會成本。
c2――車輛在要求時間之后到達單位時間所處以的懲罰值(c1和c2的大小，要根據(jù)實際情況來定)。
2.建立適度度函數(shù)。根據(jù)遺傳算法中適應度函數(shù)的特點，需要將原目標函數(shù)式變化為：
(4)
(5)
式中A*，B* ――變化后的目標函數(shù)值，取值范圍為[0，1)；
Amax,Bmax――分別是原始目標函數(shù)。
適應度函數(shù)因此變化為：f(A,B)=α×A*+β×B*(6)
經(jīng)過分析和實驗發(fā)現(xiàn)，A*，B*經(jīng)過處理后，A*的數(shù)量級一般是10-2，B＊的數(shù)量級一般是10-1。
3.用遺傳算法求解帶時間窗VRP模型。本文取α＝0.8,β＝0.2，用遺傳算法進行求解。在運用遺傳算法求解后，驗證了該算法易于理解，對問題的依賴性較小，對其求解的函數(shù)要求簡單，實現(xiàn)起來簡單高效，若參數(shù)選擇的合理，收斂速度很快，但是遺傳參數(shù)的控制對于算法的收斂速度影響很大，在參數(shù)選擇方面有一定難度。雖然文中使用的是根據(jù)以往學者經(jīng)驗選定的參數(shù)，但計算表明最優(yōu)解所在“代”數(shù)的穩(wěn)定性不是很好，這也是以后需要進一步研究的地方。
四、結論
在傳統(tǒng)的車輛配送成本最小化為目標的基礎上，兼顧客戶對配送時間的要求，建立了帶時間窗的車輛路徑優(yōu)化多目標模型。在對模型的處理上，將兩個量綱不統(tǒng)一的子目標函數(shù)除以各子目標函數(shù)的最大值后使其變成無量綱的函數(shù)，并通過權重系數(shù)變化法將各個子目標函數(shù)線性加權和作為多目標優(yōu)化問題的適應度函數(shù)，使得多目標優(yōu)化問題轉化為單目標優(yōu)化問題后再用遺傳算法求解。
參考文獻:
[1]王 惠:引入顧客滿意度求解車輛優(yōu)化調(diào)度問題.大連海事大學碩士論文,2006:1～13
[2]盛麗俊:帶有時間窗的車輛路徑問題的優(yōu)化研究.大連海事大學碩士論文,2002:13～57
中圖分類號:TP273 文獻標識碼:A文章編號:1007-9599 (2010) 10-0000-01
BLDCM Optimization of Speed Control System Based on Hybrid Parallel Genetic Algorithm
Long Ju
(Xihua University,Chengdu610039,China)
Abstract:In this paper,brushless DC motor as a controlled object,the use of the mixed pseudo-parallel genetic algorithm (MPPGA) its speed PI controller design parameters are optimized,the algorithm searches for the conventional genetic algorithm and the premature convergence and low efficiency of the shortcomings,by steepest descent method with the pseudo-parallel genetic algorithm developed a portfolio of global optimization algorithms,and the use of MATLAB 6.5 software to follow the dynamic performance of the simulation experiments,confirmed the use of the algorithm is indeed able to play the purpose of optimizing the speed performance.
Keywords:Brushless DC motor;Mixed pseudo-parallel genetic algorithm;Matlab simulation
一、MPPGA優(yōu)化PI參數(shù)數(shù)學模型的建立
(一)BLDCM轉速控制系統(tǒng)的組成
基于MPPGA優(yōu)化的無刷直流電動機轉速控制系統(tǒng)的組成框圖如上圖1所示。整個系統(tǒng)的運行采用了雙閉環(huán)的控制策略:即電流環(huán)和轉速環(huán),其中電流環(huán)采用了基本的PI控制算法設計電流PI控制器,轉速環(huán)則采用了混合偽并行遺傳算法(MPPGA)設計轉速PI控制器。
(二)MPPGA優(yōu)化數(shù)學模型的建立
無刷直流電動機轉速PI控制器的設計參數(shù)為比例放大系數(shù) 和積分時間常數(shù) ?？紤]到系統(tǒng)有兩個性能指標:超調(diào)量 和調(diào)節(jié)時間 ,所以用MPPGA對轉速控制器的PI參數(shù)進行優(yōu)化的任務便是綜合調(diào)配這兩項性能指標,使之達到用戶能滿意的最優(yōu)結果。我們以常規(guī)工程設計方法達到的指標 作為參考,通過引入設計參數(shù)的隸屬度函數(shù)而合成統(tǒng)一的目標函數(shù)為F:
由于混合偽并行遺傳算法的需要,設計參數(shù)須有一個明確的取值范圍,為充分利用常規(guī)工程設計方法的合理內(nèi)核,我們以常規(guī)工程設計法整定出的 的兩個參數(shù)值 為中心,然后在此兩個數(shù)值附近向兩邊拓展參數(shù)的求解空間,從而可以使遺傳搜索空間大大減小,能較快搜索到最優(yōu)解。綜上所述,將系統(tǒng)優(yōu)化模型歸納成方程如下:
min F(2)
約束條件(3)
; 其中 為[0,1]內(nèi)選定的數(shù)值。
二、MPPGA優(yōu)化PI參數(shù)的算法設計
本文應用MPPGA優(yōu)化PI參數(shù)是按照如下步驟完成的:(一)運行參數(shù)設置:確定混合偽并行遺傳算法的運行參數(shù):總的種群規(guī)模N;每個子種群的規(guī)模M;最大進化代數(shù)MAXGEN;局部線性搜索運算的概率Ps。(二)初始種群的產(chǎn)生:隨機產(chǎn)生初始群體 ,其中 為分組數(shù)。(三)分組計算各子群體 中個體的適應度:對第 代子種群 ,按照公式(1)和(2)計算其對應的適應度值 。(四)對各 分組進行獨立的遺傳運算:對子種群 中的每一個個體 依其適應度值 執(zhí)行下列操作:(1)選擇運算:首先找出當前各子群體中適應度最高和最低的個體,將最佳個體保留并用其替換掉最差個體,允許此時的最佳個體不參與交叉和變異而直接進入下一代,其余的個體按照其適應度值的大小進行排序,然后運用比例選擇法從 中選取兩個個體 和 。(2)交叉運算:按照自適應的交叉概率 的公式(4)對 和 進行自適應的交叉運算生成 和 。
[注:式中 為子種群中最大的適應度值; 為每代子種群中的平均適應度值; 為子種群中要交叉的兩個個體中較大的適應度值; 之間的常數(shù)];(3)變異運算:按照自適應的變異概率 的公式(5)對 和 進行自適應的變異運算生成兩個新個體 和 。
[式中 為子種群中最大的適應度值; 為每代子種群的平均適應度值; 為子種群中要變異的個體的適應度值; 之間的常數(shù)值]由產(chǎn)生的這M個新個體 和 組成子種群 的中間種群 ,并由這 個子中間種群 組成一個整體中間種群 。(五)局部搜索尋優(yōu):對中間種群 利用最速下降法以局部搜索概率Ps[一般取0.4-0.7之間的任一值]對其進行快速局部搜索尋優(yōu),從而得到尋優(yōu)后的中間種群 。(六)再次按照公式(1)和(2)分組計算局部搜索尋優(yōu)運算后的種群 中各個個體的適應度。(七)由信息交換模型進行各子中間種群 之間的信息交換,根據(jù)劃分的群體,本文采用踏腳石模型來進行信息交換,根據(jù)第6步計算出來的適應度,在子中間種群中選擇目前最優(yōu)的個體替代其他子中間種群中最差的個體,替代后加以組合構成 代種群: ,選出第 代中適應性最強的個體 。8、運算終止條件判斷:判斷遺傳運算的代數(shù)是否超過設定代數(shù),沒有就轉到第 3步繼續(xù)進行遺傳運算,有則選取 作為優(yōu)化后的PI參數(shù)輸出。
三、仿真實驗
(一)仿真參數(shù)的設置
本文所用的無刷直流電動機(24V,70W)其轉速環(huán)等效被控對象為二階傳遞函數(shù)
1.使用常規(guī)工程設計法整定轉速PI控制器得到參數(shù)為
2.使用常規(guī)GA(NGA)對轉速控制器的PI參數(shù)進行優(yōu)化,其仿真參數(shù)設置如下表1所示。
3.使用MPPGA對轉速控制器的PI參數(shù)進行優(yōu)化,其仿真參數(shù)設置如下表2所示。
為了便于進行對比分析,將常規(guī)遺傳算法(NGA)和混合偽并行遺傳算法(MPPGA)優(yōu)化后的PI參數(shù)代入轉速控制器,運用MATLAB對其兩種遺傳算法下的動態(tài)跟隨性能進行了多次仿真實驗都得到相似的結果。
參考文獻:
[1]周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,1999
[2]王小平,曹立明.遺傳算法――理論、應用與軟件實現(xiàn)[M],西安:西安交通大學出版社,2002
[3]龍駒.永磁無刷直流電動機轉速控制系統(tǒng)的優(yōu)化設計[M].成都:西南交通大學出版社,2006
[4]牛志華.一類混合遺傳算法的研究[M].西安:西安交通大學碩士學位論文,2002
[5]劉金琨.先進PID控制MATLAB仿真(第2版)[M].北京:電子工業(yè)出版社,2004
中圖分類號：G650 文獻標識碼：A 文章編號：1003-2851（2012）-09-0180-01
遺傳算法[（genetic algorithm，GA）是一種自適應大規(guī)模并行搜索優(yōu)化算法，較以往傳統(tǒng)的搜索算法具有使用方便、魯棒性強、便于并行處理等特點，因而廣泛應用于解決搜索和優(yōu)化的問題。但由于遺傳算法不能很好地維持解種群中個體的多樣性，易趨于“早熟”收斂而陷入局部最優(yōu)解。因此，遺傳算法不能保證一定能找到問題的全局最優(yōu)解，目前公交公司各車隊的排班主要依靠工作人員的經(jīng)驗手工進行，雖然它具有一定的實用性，但它存在著明顯的不足，很難保證排班的結果在運營效率等方面是最優(yōu)或者接近最優(yōu)的。為滿足實際應用需求，采用智能化算法來求解車輛調(diào)度優(yōu)化問題，在有限的算法步驟內(nèi)，找出所有滿足約束條件的排班方案中的最優(yōu)方案或接近最優(yōu)的方案。
一、遺傳算法
1.遺傳算法簡介
遺傳算法（Genetic Algorithms，GA）是一種基于自然選擇和基因遺傳學原理的自適應全局優(yōu)化概率搜索方法。它的創(chuàng)立有兩個研究目的：一是抽象和嚴謹?shù)亟忉屪匀唤绲倪m應過程；二是為了將自然生物系統(tǒng)的重要機理運用到工程系統(tǒng)中。GA從許多點開始并行操作，在解空間進行高效啟發(fā)式搜索，因而可以有效地防止搜索過程收斂于局部最優(yōu)解；遺傳算法在計算機上模擬生物的進化過程和基因的操作，通過目標函數(shù)來計算適配值，并不需要對象的特定知識，它具有全局尋優(yōu)的能力，能解決高度復雜的問題，被廣泛應用于自動控制、圖形處理、電力調(diào)度等方面。
2.建立調(diào)度的數(shù)學模型
調(diào)度系統(tǒng)所采用的數(shù)學模型對運行環(huán)境做了簡化：車的速度恒定，保持勻速行駛，無特殊事件發(fā)生；以分鐘作為最小的時間單位，這對安排時刻表是合理的；假設客流模型能反映該段線路上的日常客流量（我們假設到站乘客服從均勻分布，在不同時段有不同的分布密度）。
首班車發(fā)車時刻為早上6點整，末班車發(fā)車時刻為22點整，所有運營車都在整分鐘時刻發(fā)車，一天之內(nèi)的總班次為m，總時間為16小時，即960分鐘。用xm表示第m輛運營車發(fā)車時刻距首發(fā)時刻的時間，以分鐘為單位。決策變量為X=[x1，x2，…xn]；染色體X是一個完整的發(fā)車時刻表，其中的每個基因為一個車輛的發(fā)車時刻。
免疫算法效仿生物免疫系統(tǒng)，把外來侵犯的抗原和免疫產(chǎn)生的抗體分別與實際求解問題的目標函數(shù)以及問題的解相對應，生成的抗體能有效地排除抗原，也就相當于求得了問題的最優(yōu)解；對與抗原親和力高的抗體進行記憶能促進快速求解。
二、IGA應用于公交動態(tài)調(diào)度
現(xiàn)仍采用上面建立的數(shù)學模型，初始規(guī)模N仍為200且不隨進化代數(shù)而發(fā)生變化，便于IGA和GA比較。現(xiàn)利用IGA來進行優(yōu)化的步驟為：
1.在解空間內(nèi)隨機生成初始群體，并計算其適應度，確定最優(yōu)個體x0best，并給出的取值？滓0，A取為1，？滓0i取為3，？滓？孜取為0。
2.根據(jù)式（4.7）進行進化操作，在解空間內(nèi)生成子代群體，規(guī)模為N。
3.計算子代群體的適應度，確定最優(yōu)個體xt+1best，若f（xt+1best）>f（xtbest），則選定最優(yōu)個體為xt+1best，否則最優(yōu)個體為xtbest。
4.重復執(zhí)行步驟2和3，直至達到終止條件，這里T取為100，選擇最后一代的最優(yōu)個體作為尋優(yōu)的結果。
本文在遺傳算法的基礎上采用了一種較新的混合遺傳算法——免疫遺傳算法對公交靜態(tài)調(diào)度進行了研究，并對二者的應用結果進行了仿真和比較，結果表明IGA有效的克服了簡單GA的不足之處，并提高了尋優(yōu)過程當中目標函數(shù)的收斂速度，并得到了合理的發(fā)車時刻表，可以提高公交企業(yè)的服務水平，對改善城市交通問題和節(jié)約市民出行時間有相當?shù)膶嶋H意義。
參考文獻
中圖分類號：F27 文獻標識碼：A
收錄日期：2011年10月28日
一、遺傳算法簡介
遺傳算法（GAS）是由美國密執(zhí)根大學的Holland等人創(chuàng)立的。與其他啟發(fā)式方法順序搜索解空間的工作方式不同，遺傳算法采用解的種群作為工作單元，使用模仿生物進化的適者生存原則指導搜索并改進目標。種群由代表個體的定長字符串組成，每個個體表示解空間的一個點，每個解的質(zhì)量，通過依賴于問題目標函數(shù)的適應值函數(shù)來進行評估。搜索過程通過進化來進行，每代中的個體以正比于它的適應值的概率遺傳到下一代。它使用3個基本算子：選擇、交叉和變異。選擇是指個體以其適應值比例復制到池中；交叉是池中的兩個個體進行，組合形成一個（或幾個）新個體，復制和交叉將好的特性進行遺傳；變異則是發(fā)生在少數(shù)字符串某基因位上的基因的突變，它使搜索過程能夠有機會從搜索到的局部最優(yōu)解逃出。
解決一個實際問題的遺傳算法通常包括下列兩個決策步驟：（1）將求解問題模型化為符合遺傳算法的框架?？尚薪饪臻g的定義，適應值函數(shù)的表現(xiàn)形式，解的字符串表達式方式；（2）遺傳算法參數(shù)的設計。種群規(guī)模，復制、交叉、變異的概率選擇，進化最大代數(shù)，終止準則設定等。
二、遺傳算法的基本特點
（一）結構特點。遺傳算法是以適應值提供的啟發(fā)式信息進行搜索的，與其他啟發(fā)式（模擬退火、爬山法、神經(jīng)網(wǎng)絡等）方法相比，在結構和工作過程方面的特點見表1。（表1）
（二）實驗性能方面的特點
1、高效性。遺傳算法具有大范圍全局搜索的特點，與問題領域無關，前期工作量比較少。
2、健壯性。遺傳算法的搜索是用種群作為基本單元，采用三個不同作用的基本算子進行搜索的，解的結果隨時間增加而趨于穩(wěn)定，不受初始解的影響，而且不因實例的不同而蛻變。
3、通用性和靈活性。遺傳算法可用于多種優(yōu)化搜索問題，解題程序可以通用，針對不同的實例，適當調(diào)整算子參數(shù)，就可以使算法執(zhí)行獲得最佳的解結果和占用CPU機時的關系。
三、遺傳算法在解決經(jīng)典運籌問題中的應用
（一）旅行商問題（TSP）。旅行商問題自誕生以來，頗受數(shù)學家推崇，今天的旅行商問題已遠遠超過其本身的含義，成為一種衡量算法優(yōu)劣的標準。旅行商問題是采用非標準編碼遺傳算法求解最成功的一例，基因編碼用推銷員順序經(jīng)歷的城市名表示，求最佳路線即是改變編碼次序而求最低適應值的問題。對類似字符串使用標準交叉，產(chǎn)生的后代可能有重復或丟失的元素，因而成為非可行解。為克服這種困難，人們提出許多非標準的交叉和變異方法：交叉主要采用重排序方法――部分匹配重排序，順序交叉和循環(huán)交叉等；變異主要采用位點、反轉、對換、插入等方法，使旅行商問題得以有效地解決。值得一提的是，清華大學張雷博士提出的自適應多點交叉算子，能夠保證多點交叉后路徑的可行性，加快了搜索速度。
（二）作業(yè)調(diào)度問題。作業(yè)調(diào)度問題同樣是自然變更次序的問題，可以用基于變更次序的遺傳算法進行處理。（表2）
（三）背包問題。一維、二維和三維背包問題在商業(yè)和工業(yè)領域有著廣泛的應用，基于遺傳算法的求解方法很多。傳統(tǒng)求解采用啟發(fā)式規(guī)則，決定下一步該裝哪一塊和裝在哪里，此時變更次序的編碼與啟發(fā)式安置策略是利用遺傳算法解決這類問題的最為出色的方法，Lin使用一系列的懲罰項指導其搜索策略，測定單個個體的適應值。
Bortfeldt使用一個層次背包問題，個體用它們的層次代表，當兩個親代被選擇交叉時，它們的層次混在一起，從中選擇最好的作為子代的第一層，再從余下的組件中選擇最好的作為第二層，以此類推，直至產(chǎn)生所有的層次。
陳國良等設計了一種“與/或”交叉方法，使子代繼承雙親的同型基因，對雜型基因采用不同支配方式，這種策略為遺傳算法的硬件實現(xiàn)創(chuàng)造了良好的條件。
（四）時刻表排定問題。Corne對Edinburgh大學7日內(nèi)的28個時間期間安排40門課的考試問題作了處理，尋找一個可行的時間排定表，使每個學生參加的考試在時間上能夠錯開，時刻表用字符串代表，字符串每個位置代表一門課，該位置的值代表考試的時間，用均勻交叉和標準變異操作求解。
這類問題擴展到基于二維的矩陣代表的逼近問題，Colorini使用行代表教師列代表可用的小時數(shù)的矩陣，每個單元的值為教師在此時承擔的任務，包括教室和其他一些資源配置，教師的任務是事先給定的，故行都是可行的，列代表的時間安排可能會發(fā)生沖突，將此沖突用懲罰函數(shù)表示在適應值函數(shù)中，而且采用修復算子在評價之前盡量將結論調(diào)整回可行區(qū)域內(nèi)，該算法用Milan學校的實際數(shù)據(jù)進行了檢驗。
除此之外，遺傳算法在運輸問題、指派問題、分割問題及網(wǎng)絡計劃優(yōu)化問題等方面都獲得了非常成功的應用，這些問題被認為是NP類問題，其規(guī)模隨變量的增加呈指數(shù)增長，遺傳算法在這些問題的求解中，充分體現(xiàn)了其操作性能方面的優(yōu)勢。
四、應用和推廣中存在的問題
在上述問題中，遺傳算法求解展示了優(yōu)良的性能，但遺傳算法并未像其他啟發(fā)式方法那樣容易地被OR學者廣泛接受而用于大量的實際問題中，究其原因，主要有以下幾點：
（一）傳播方式的障礙。遺傳算法最初的工作是以密執(zhí)根大學嚴謹?shù)难芯啃〗M作為研究項目和學術討論中心，當研究成員擴大時，這類討論會演變?yōu)闄C構的學術會議（美國現(xiàn)有5個，歐洲有3個，我國目前還沒有），許多研究者聚于此而遠離問題導向，有關的會議論文公開出版數(shù)量很少，而且，由于歷史原因，研究者常常將他們的研究結果選擇在有關人工智能的雜志上發(fā)表，導致了應用遺傳算法的信息很緩慢地擴散到其他不同技術應用領域的工作者中，這與模擬退火等其他啟發(fā)式方法快速在運籌學會議及雜志上發(fā)表相反。由于缺乏交流導致了兩方面的問題：一是許多關于遺傳算法的論文不能與從其他方法得到的結論進行質(zhì)量的比較，二是削弱了許多遺傳算法多的潛在使用者用遺傳算法與其他方法競爭的信心。
（二）術語的隔膜。初始跨入遺傳算法領域的使用者常常感到起步非常艱難，遺傳算法依賴于遺傳學的術語也像模擬退火的術語來自于統(tǒng)計熱力學一樣。然而，溫度、冷卻等可能很快賦予新的意義，但遺傳算法中的基因位、染色體、遺傳型卻難以很快被人理解和接受；另外，許多發(fā)表的研究偏重于用某些專門函數(shù)檢驗他們的新思路或新設想，這對于全面理解該技術固然是一件好事，但對于一個面對如此豐富復雜材料的初用者會發(fā)現(xiàn)，他將不知從何做起。即使一個非常愿意使用遺傳算法的人，也要有足夠的決心去克服上述障礙。
（三）方法的局限性。對于具有強約束的優(yōu)化問題，采用懲罰函數(shù)逼近常常達不到預想的結果。Radcliffe評論說：“約束通常被認為是遺傳算法面臨的最大問題”因為懲罰因子選擇不當時，會招致錯誤結論。目前，求解帶約束優(yōu)化問題的啟發(fā)式遺傳方法已經(jīng)有了一些，但是，它們多數(shù)與問題領域相關，在這方面還缺少普遍適用的方法的系統(tǒng)研究。
（四）編碼的困難。不是所有問題解空間中的點都能明顯地用編碼表示，作為OR研究者，常常從問題結構取得利益，用矩陣、樹、網(wǎng)絡或其他更適用的方法建立表達式；串表達中的建筑塊假說建議適用較少的字符，導致人們對二進制編碼的偏愛，但二進制編碼具有一定的映射誤差（實際計算時，我們是把問題作為整數(shù)規(guī)劃），特別是它不能直接反映出所求問題本身結構特征，因此很難滿足生成有意義的積木塊編碼原則；再者，二進制字符的長度隨問題發(fā)生明顯變化，當問題復雜時會因為編碼太長而無法進行正常工作。
以上的種種阻力，在一定程度上減緩了遺傳算法在運籌學實際問題中的推廣和應用。
主要參考文獻：
關鍵詞： 鍋爐水位；PID控制；遺傳算法
Key words： boiler water level；PID control；genetic algorithm
中圖分類號：TP273 文獻標識碼：A 文章編號：1006-4311（2014）29-0070-02
0 引言
鍋爐是我國現(xiàn)代工業(yè)中的重要設備，同時也是生活中必不可少的供暖供水設施，在全國各地中小學有著廣泛的應用。學校具有人口密度大等問題，而且學生年齡較小，自我保護意識薄弱，因此，保證鍋爐的安全穩(wěn)定運行具有重要的意義。水位是鍋爐正常運行中必須控制的一個重要參數(shù)，它直接影響到鍋爐系統(tǒng)的安全性與穩(wěn)定性。因此，水位控制是鍋爐控制系統(tǒng)中的一個重要組成部分，但同時這也是一個復雜的控制過程。由于鍋爐負荷波動范圍大、啟停頻繁，人工操作一般很難保證系統(tǒng)長期安全穩(wěn)定的運行，所以，自動控制已成為鍋爐安全高效運行的保證。[1，2，5]
目前傳統(tǒng)PID控制是采用最多的鍋爐水位控制方式，但是因為鍋爐各種參數(shù)的頻繁變化，導致傳統(tǒng)PID控制方式往往難以實現(xiàn)預期的要求。隨著現(xiàn)代控制理論的發(fā)展，各種先進控制算法不斷出現(xiàn)，本文在此基礎上提出了基于遺傳算法的鍋爐水位PID控制方式，該控制方式可以實參系統(tǒng)參數(shù)自整定，克服了傳統(tǒng)PID控制方式的控制精度差以及參數(shù)變化復雜等缺點，基本可以實驗鍋爐水位較高精度的實時控制。[2-4]
1 鍋爐水位控制系統(tǒng)結構及原理
鍋爐水位控制系統(tǒng)主要包括鍋爐水位檢測、進水流量檢測、閥門控制等幾個單元。一般而言，在控制鍋爐水位時控制系統(tǒng)首先檢測給定水位和實際水位、進水控制閥與負載等參數(shù)，然后動作進水控制閥并檢測水位是否達到給定要求，以此判斷進水控制閥的開通和關斷?；谶z傳算法的水位控制器在傳統(tǒng)PID控制中注入了類似人的思想意識，通過基于遺傳算法設計的PID控制器來推算控制系統(tǒng)需要的各個參數(shù)，并應用于控制系統(tǒng)中。[4，7]
系統(tǒng)為雙閉環(huán)控制：外環(huán)由水位變送器、控制器、內(nèi)環(huán)回路及控制對象構成，稱為水位環(huán)，主要作用是控制鍋爐水位高低也主控環(huán)；內(nèi)環(huán)是進水流量測量裝置、控制器、進水控制閥構成的回路，也稱為流量環(huán)，主要作用是控制進水側的擾動，穩(wěn)定流量，內(nèi)環(huán)為輔助環(huán)?；谶z傳算法的鍋爐水位控制系統(tǒng)結構圖如圖1所示。
2 基于遺傳算法的PID控制器設計
本文在設計基于遺傳算法的PID控制器時主要遵循以下思想。
首先，把PID控制器需要的三個關鍵參數(shù)kp，ki，kd按照進行二進制編碼，取值范圍根據(jù)系統(tǒng)實際參數(shù)確定，由此得到三個字串；然后，將三個字串相連來構成一個完整空間個體，隨即便可產(chǎn)生一定數(shù)量的個體；最后，根據(jù)遺傳算法對每個個體進行計算以此得出新的個體，對每個新個體進行適度評估以及遺傳算法操作。[6]
如果新個體不滿足系統(tǒng)要求可按照上述思想重復進行直到滿足優(yōu)化條件。遺傳算法PID控制器系統(tǒng)結構圖如圖2示。
3 控制系統(tǒng)仿真及分析
根據(jù)上文中設計的控制系統(tǒng)及控制器在MATLAB/simulink環(huán)境下搭建仿真模型。設置某校鍋爐蒸發(fā)量為126t/h，鍋爐水位要求穩(wěn)定在設定值的[-4.2，4.2]cm范圍內(nèi)，閥門控制信號為4～20mA電流信號。[4]
根據(jù)鍋爐控制系統(tǒng)結構及參數(shù)可以得到系統(tǒng)各單元的傳遞函數(shù)如下。
進水流量控制器傳遞函數(shù)：G1（s）=0.4
水位控制器傳遞函數(shù)：G2（s）=■
進水流量與水位的傳遞函數(shù)：G3（s）=■=■
控制閥增益設為：kf=2.6，進水流量、水位變送器的轉換系數(shù)分別為：？酌w=0.42，？酌H=1.2，kp=20，ki=0.02仿真時間設為100s，輸入為階躍信號，同時可在系統(tǒng)運行至40s時加入一干擾信號，以此檢測系統(tǒng)的抗干擾性能。
為證明基于遺傳算法的PID控制器在控制系統(tǒng)中的優(yōu)越性，在MATLAB/simulink中分別搭建基于傳統(tǒng)PID的鍋爐控制系統(tǒng)仿真模型以及加入遺傳算法優(yōu)化的鍋爐控制系統(tǒng)仿真模型，然后在相同參數(shù)下進行仿真以可觀地對比仿真結果。
兩種控制系統(tǒng)的仿真輸入波形如圖3、4所示。
通過圖3及圖4分析可知：如果鍋爐控制系統(tǒng)采用加入遺傳算法的PID控制器，輸出具有靜態(tài)穩(wěn)態(tài)誤差小，超調(diào)低等優(yōu)點，輸出波形較傳統(tǒng)PID控制明顯改善，結果較為理想。
4 結論
本文說明了鍋爐系統(tǒng)水位控制的重要性，分析了鍋爐水位基本原理及傳統(tǒng)PID控制方法，在此基礎上提出了基于遺傳算法的新型PID控制器設計方法，然后根據(jù)該控制器設計了具有參數(shù)自動檢測功能的新型智能控制系統(tǒng)，并在MATLAB/simulink中分別搭建基于傳統(tǒng)PID的鍋爐控制系統(tǒng)仿真模型以及加入遺傳算法優(yōu)化的鍋爐控制系統(tǒng)仿真模型。通過兩種模型的仿真結果可以明顯看出，加入遺傳算法優(yōu)化的鍋爐控制系統(tǒng)無論在系統(tǒng)超調(diào)及穩(wěn)態(tài)誤差等方面均有較好的改善，系統(tǒng)收斂速度明顯優(yōu)于傳統(tǒng)PID控制。因此，該控制器無論在學校鍋爐或者工廠企業(yè)的大型鍋爐系統(tǒng)中都具有良好的應用前景。
參考文獻：
[1]李遵基.熱工自動控制系統(tǒng)[M].北京：中國電力出版社，2001.
[2]張曉楠，方浩，戴冠.遺傳算法的編碼機制研究[J].信息與控制，1997，26（2）：134-139.
[3]郭慶鼎，李蒙，郭威.PID控制器參數(shù)的遺傳算法優(yōu)化設計[J].沈陽工業(yè)大學學報，2000，22（1）：31-33.
[4]蔡有社.基于ARM的鍋爐汽包水位控制系統(tǒng)的研究[D]. 安徽理工大學碩士學位論文，2011.
