遺傳算法論文精選(九篇)

前言：一篇好文章的誕生，需要你不斷地搜集資料、整理思路，本站小編為你收集了豐富的遺傳算法論文主題范文，僅供參考，歡迎閱讀并收藏。

第1篇：遺傳算法論文范文

1．1基因編碼設(shè)計

編碼就是將遺傳算法中處理不了的空間參數(shù)轉(zhuǎn)換成遺傳空間的由基因組成的染色體或個體的過程．其中基因在一定意義上包含了它所代表的問題的解．基因的編碼方式有很多，這也取決于要解決的問題本身．常見的編碼方式有：二進(jìn)制編碼，基因用0或1表示，通常用于解決01背包問題，如基因A：00100011010（代表一個個體的染色體）；互換編碼，主要用于解決排序問題，如調(diào)度問題和旅行商問題，用一串基因編碼來表示遍歷城市順序，如234517986，表示在9個城市中先經(jīng)過城市2，再經(jīng)過城市3，依此類推；樹形編碼，用于遺傳規(guī)劃的演化編程或表示，其編碼的方法就是樹形結(jié)構(gòu)中的一些函數(shù)，本文采用的是樹形編碼．

1．2交叉算子設(shè)計

交叉運(yùn)算的含義是參照某種方式和交叉概率，將兩組相互配對的個體互換部分基因，生成新個體的過程．交叉運(yùn)算在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法．交叉操作流程如圖1所示．交叉操作首先判定要交叉的基因是否相同，如果相同進(jìn)行子基因組的交叉，然后再判定交叉是否完成，沒完成就繼續(xù)，完成就退出；如果交叉的基因不相同，就要選擇是否依據(jù)概率進(jìn)行基因交換，選擇交換就交換其所有的次級基因結(jié)構(gòu)，然后再判定交叉是否完成，選擇不交換就直接判定交叉是否完成．

1．3變異算子設(shè)計

變異操作從第i個子結(jié)構(gòu)開始．依據(jù)變異概率進(jìn)行第i個基因的變異，如果變異完成，就初始化其所有次級基因結(jié)構(gòu)，如果變異沒有完成，就進(jìn)行子基因組的變異操作．重復(fù)操作上面的步驟，直至變異操作結(jié)束．

2遺傳算法在機(jī)械產(chǎn)品設(shè)計中的應(yīng)用

機(jī)械產(chǎn)品設(shè)計是在研究人機(jī)協(xié)同方案設(shè)計的工作機(jī)制上，建立產(chǎn)品的人機(jī)分析、人機(jī)約束模型和協(xié)同方案設(shè)計求解模型，確立人機(jī)協(xié)同系統(tǒng)的同步與異步交互、任務(wù)協(xié)同、數(shù)據(jù)共享、數(shù)據(jù)可視化、易用性等工作機(jī)制．

2．1基于遺傳算法的數(shù)控車床設(shè)計

2．1．1數(shù)控車床總體設(shè)計任務(wù)分解

首先確定數(shù)控車床總體設(shè)計任務(wù)，然后根據(jù)多層次結(jié)構(gòu)知識進(jìn)化算法設(shè)計要求，將數(shù)控車床的總體設(shè)計任務(wù)分解。

2．1．2數(shù)控車床設(shè)計的基因編碼表示

依據(jù)數(shù)控車床設(shè)計任務(wù)分解的結(jié)果，可以得出數(shù)控車床設(shè)計的基因編碼圖．?dāng)?shù)控車床設(shè)計任務(wù)按多層次結(jié)構(gòu)劃分為床身、滑臺、刀架、尾臺、冷卻、控制器、電機(jī)．每個結(jié)構(gòu)都包含多個選擇方案．不同選擇方案的有些結(jié)構(gòu)含有子結(jié)構(gòu)，并且這些子結(jié)構(gòu)還可以進(jìn)一步分解出多種選擇方案．通過數(shù)控車床設(shè)計的基因編碼，可看到數(shù)控車床設(shè)計任務(wù)每一層次的關(guān)系，包括各層次之間的約束關(guān)系．

2．2基于遺傳算法的機(jī)械產(chǎn)品設(shè)計系統(tǒng)應(yīng)用

第2篇：遺傳算法論文范文

關(guān)鍵詞：入侵檢測，否定選擇，克隆選擇

 

1.引言

克隆選擇是基于人工免疫機(jī)制的入侵檢測系統(tǒng)中一個重要組成部分。Forrest小組提出的靜態(tài)克隆選擇算法能夠在一個靜態(tài)數(shù)據(jù)集上建立一個有效的誤用檢測器，但它最大的缺點(diǎn)是不能適應(yīng)網(wǎng)絡(luò)流的變化，即不具有自適應(yīng)性[1]。在Forrest的靜態(tài)克隆選擇算法中，首先產(chǎn)生隨機(jī)檢測器集合D，D中的檢測器都是經(jīng)過隨機(jī)產(chǎn)生器產(chǎn)生，再經(jīng)否定選擇后送到集合D中，D中的檢測器初始適應(yīng)度值為0。否定選擇的目的，是為了排除和“自體”匹配的無效檢測器，使隨機(jī)產(chǎn)生的檢測器，先和“自體”數(shù)據(jù)庫中的所有記錄進(jìn)行比較，若匹配，則丟棄；否則，送入檢測器集合D。由于“自體”數(shù)據(jù)庫非常大，因此進(jìn)行否定選擇的時間很長。

J. Kim此此算法略作改進(jìn)[2]，使否定選擇函數(shù)返回一個特定的值，作為檢測器的初始適應(yīng)度值，檢測器的優(yōu)劣由適應(yīng)度值的大小來衡量。可以把適應(yīng)度值限制在0和1之間，在進(jìn)行否定選擇時，計算產(chǎn)生的每個隨機(jī)檢測器和“自體”數(shù)據(jù)庫中的每個“自體”模式匹配的相異度值，否定選擇函數(shù)返回這些相異度的平均值，并把這個返回值作為這個檢測器的初始適應(yīng)度值。即

其中：fitness(i)為隨機(jī)產(chǎn)生的第i個隨機(jī)檢測器；N為自體數(shù)據(jù)庫中“自體”模式的個數(shù)；dissimilarity(antibody(i),self (j))為產(chǎn)生的第i個隨機(jī)檢測器和“自體”數(shù)據(jù)庫中第j個“自體”模式匹配的相異度值。論文格式，否定選擇。

靜態(tài)克隆選擇算法在一定程度上改進(jìn)了否定選擇算法。但是，傳統(tǒng)的克隆選擇算法是在靜態(tài)的抗原數(shù)據(jù)集基礎(chǔ)上進(jìn)行模式識別的，這種方法對先前已經(jīng)收集到的數(shù)據(jù)具有較好的效果[3]。不過，現(xiàn)實環(huán)境中(比如網(wǎng)絡(luò)中的入侵檢測)，不停的有新的入侵模式, 也就是說AIS每天面對的可能是各種不同的抗原。更重要的是, 現(xiàn)實中某時刻被認(rèn)為Self(正常行為模式)，到了下一時刻可能就成了Nonself(異形模式)。因此，我們要求AIS除了具備先前已經(jīng)描述的具有識別新的未知模式的能力外，當(dāng)識別器的識別能力不再正確的時候，它應(yīng)該隨時被替換[4]。

2.否定選擇算子

檢測系統(tǒng)選擇兩個雙親檢測器，采用交叉、變異的方法去產(chǎn)生后代檢測器，并用后代檢測器中更優(yōu)的子檢測器去代替父檢測器中檢測效果較差的檢測器。由于兩個父檢測器隨機(jī)選取，交叉、變異的過程中可能產(chǎn)生無效的檢測器，所以有必要用否定選擇算法對新生成的子檢測器做一個判定，當(dāng)后代檢測器與任一自體抗原匹配時，這個后代檢測器就被淘汰。當(dāng)一個無效后代檢測器產(chǎn)生時，檢測系統(tǒng)就用同一對雙親檢測器基因算子產(chǎn)生一個新的后代檢測器。當(dāng)產(chǎn)生有效后代檢測器失敗次數(shù)超過T時，檢測系統(tǒng)就選擇一對新的雙親檢測器產(chǎn)生新的后代檢測器。論文格式，否定選擇。

3.遺傳選擇算子

遺傳算法是克隆選擇算法的核心。遺傳算法的基本原理是直接由自然行為類推而來。每個個體根據(jù)問題的好壞被賦予一個適應(yīng)度。適應(yīng)度越高的個體有更高的機(jī)會與其他個體交叉繁殖進(jìn)行再生，新產(chǎn)的個體被稱為后代，它們共享一些來自于它們雙親的特征。那些適應(yīng)度較低的個體因為不太可能被選出來，最后都會滅亡?？寺∵x擇算法用遺傳算法作為遺傳算子，隨機(jī)選擇成熟的檢測器，這樣能產(chǎn)生更新更優(yōu)的子檢測器。用遺傳算法產(chǎn)生的新的子檢測器中，有更優(yōu)的，但也有更不合格的，所以需要用否定選擇算法對他們作一個選擇。遺傳算法是建立在自然選擇和群體遺傳學(xué)機(jī)理基礎(chǔ)上的隨機(jī)、迭代、進(jìn)化，具有廣泛適用性的搜索方法。所有自然種類都是適應(yīng)環(huán)境而得以生存，這一自然適應(yīng)性是遺傳算法的主旋律。論文格式，否定選擇。遺傳算法搜索結(jié)合了達(dá)爾文適者生存和隨機(jī)信息交換，前者消除了解中不適應(yīng)因素，后者利用原有解中己有知識，從而有力地加快了抽索討程。

下面舉例說明基本方法。對于一個給定的優(yōu)化問題，設(shè)目標(biāo)函數(shù)

F=(x,y,z), (x,y,z),FR

要求(x0,y0,z0)使得

F=f(x0,y0,z0)=max(f(x,y,z))

其中 (x,y,z)為自變量，是(x,y,z)的定義域，(x,y,z) 可以是數(shù)值，也可以是符號；F為實數(shù)，是解的優(yōu)劣程度或適應(yīng)度的一種度量；f 為解空間(x,y,z) 到實數(shù)域FR的一種映射，那么遺傳算法的求解步驟如下:

（1）編碼

用一定比特數(shù)的0,1二進(jìn)制碼對自變量x,y,z進(jìn)行編碼形成基因碼鏈，每一碼鏈代表一個個體，表示優(yōu)化問題的一個解。如x有16種可能取值x0,x1，…x15，則可以用4bit的二進(jìn)制碼0000-1111來表示。將x,y,z的基因碼組合在一起則形成碼鏈。

（2）產(chǎn)生群體

t=0，隨機(jī)產(chǎn)生n個個體組成一個群體P(t)，該群體代表優(yōu)化問題的一些可能解的集合。當(dāng)然，一般來說，它們的素質(zhì)都很差，遺傳算法的任務(wù)是要從這些群體出發(fā)，模擬進(jìn)化過程，擇優(yōu)汰劣，最后得出非常優(yōu)秀的群體和個體，滿足優(yōu)化的要求。

（3）評價

按編碼規(guī)則，將群體P(t)中的每一個體的基因碼所對應(yīng)的自變量取值(xi,yi,zi)代入(4-l)式，算出其函數(shù)值Fi ,i=1,2,…,N。Fi越大，表示該個體有較高的適應(yīng)度，更適應(yīng)于f所定義的生存環(huán)境，適應(yīng)度F為群體進(jìn)化時的選擇提供了依據(jù)。

（4）選擇(復(fù)制)

按一定概率從群體P(t)中選取M對個體，作為雙親用于繁殖后代，產(chǎn)生新的個體加入下一代群體P(t+1) 中。一般P,與F,成正比，就是說，適合于生存環(huán)境的優(yōu)良個體將有更多的繁殖后代的機(jī)會，從而使優(yōu)良特性得以遺傳。選擇是遺傳算法的關(guān)鍵，它體現(xiàn)了自然界中適者生存的思想。

（5）交叉

對于選中的用于繁殖的每一對個體，隨機(jī)地選擇同一整數(shù)n，將雙親的基因碼鏈在此位置相互交換，如個體x,y在位置3經(jīng)交叉產(chǎn)生新個體x’,y’，它們組合了父輩個體x,y的特征，即

x=x1x2x3x4x5[00011]

y=y1y2y3y4y5[11100]

x’=x1x2x3x4x5[00000]

y’=y1y2y3y4y5[11100]

交叉體現(xiàn)了自然界中信息交換的思想。論文格式，否定選擇。

（6）變異

以一定概率凡從群體P(t+1)中隨機(jī)選取若干個體，對于選中的個體，隨機(jī)選取某一位進(jìn)行取反運(yùn)算，即由10或由01。同自然界一樣，每一位發(fā)生變異的概率是很小的。變異模擬了生物進(jìn)化過程中的偶然基因突變現(xiàn)象。遺傳算法的搜索能力主要是由選擇和交叉賦予的，變異算子則保證了算法能搜索到問題解空間的每一點(diǎn)，從而使算法具有全局最優(yōu)，它進(jìn)一步增強(qiáng)了遺傳算法的能力。

對產(chǎn)生的新一代群體進(jìn)行重新評價選擇、交叉、變異，如此循環(huán)往復(fù)，使群體中最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個體的適應(yīng)度達(dá)到某一限值或最優(yōu)個體的適應(yīng)度和群體的平均適應(yīng)度值不再提高，則迭代過程收斂，算法結(jié)束。

4.多層動態(tài)克隆選擇算法

為了有效解決上面的問題，對靜態(tài)克隆選擇算法進(jìn)行改進(jìn)。引入幾個重要的參數(shù)和與先前有所不同的新的免疫細(xì)胞，稱為記憶識別器。即成熟識別器集中除了一般的經(jīng)過克隆選擇生成的成熟識別器之外，還包括記憶識別器。一個參數(shù)是生命期限，指的是成熟識別器參與模式識別的期限，當(dāng)一個成熟識別器不能在規(guī)定的期限內(nèi)識別出Nonself，說明該識別器并不是理想的識別器，應(yīng)該被去掉；另一個參數(shù)是記憶計數(shù)器，每當(dāng)成熟識別器識別出一個異形模式，則該計數(shù)器自動增加，當(dāng)超過預(yù)先設(shè)定好的閥值時，說明該成熟識別器具有較高的識別效率，因此將其作為記憶識別器加入到成熟識別器集合中。這樣，識別器集合具有了多層次性。同時，為了適應(yīng)Self和Nonself的動態(tài)變化，用新增的抗原對成熟識別器進(jìn)行再選擇，去掉那些不再有用的識別器，以降低偽肯定率(誤判)。

算法描述：首先初始化識別器種群，計算種群中每個檢測器的適應(yīng)值，在適應(yīng)值高的檢測器中隨便選擇兩個檢測器進(jìn)行克隆繁殖產(chǎn)生子檢測器，讓子檢測器通過一個否定選擇過程去掉那些能夠識別自體的檢測器，這樣就得到了成熟的檢測器集合。下面是另一個再選擇過程，因為我們動態(tài)的增加了自體或非自體，所以有必要對成熟的檢測器進(jìn)行一次再選擇過程，通過再選擇過程的檢測器經(jīng)過監(jiān)測而達(dá)到激活閥值的就激活，而沒達(dá)到激活閥值的就等待或者死亡。論文格式，否定選擇。

算法分析：算法能動態(tài)的適應(yīng)不斷變化的網(wǎng)絡(luò)環(huán)境，能夠根據(jù)環(huán)境的要求動態(tài)的優(yōu)化檢測器。而在檢測器通過初次選擇成為成熟檢測器后又通過一個再選擇過程，這個過程能很好的配合動態(tài)新增自體或非自體，因為每次動態(tài)新增加了自體或者非自體后原來的一些檢測器可能會改變它的屬性，如原來合格的成熟檢測器可能因為新增自體而變?yōu)闊o效檢測器，這個在選擇過程就能夠把它過濾掉，從而能在保持誤報率不變的基礎(chǔ)上提高檢測率。論文格式，否定選擇。

結(jié)束語

由于遺傳算法的特點(diǎn)，靜態(tài)克隆選擇算法產(chǎn)生的檢測器有可能是無效檢測器，所以本文提出了一種多層動態(tài)克隆選擇算法，對每次動態(tài)克隆的新檢測器再次檢測，判斷其有效性，從而過濾掉無效低檢測器但是本算法也增加了算法的復(fù)雜度，這也是日后需要改進(jìn)的地方。

參考文獻(xiàn)

[1]S.Forrest,Hofmeyr,Somayaji.ComputerImmunology.CommunicationsoftheACM,1997,40(10):88~96

[2]J.Kim,P.Bentley.TowardsanArtificialImmuneSystemforNetworkIntrusionDetection:AnInvestigationofDynamicClonalSelection.TheCongressonEvolutionaryComputation，Honolulu,2002:1015~1020.

[3]M.Balazinska,E.Merlo,M.Dagenais,etl.Advancedclone-analysistosupportobject-orientedsystemrefactoring.Proceedings.SeventhWorkingConferenceonReverseEngineering,Brisbane,2000:98~107.

[4]ZejunWu,YiwenLiang.Integratedplatformofartificialimmunesystemforanomalydetection.WSEASTransactionsonInformationScienceandApplications,2005,2(2):144~149

第3篇：遺傳算法論文范文

關(guān)鍵詞：遺傳算法；整數(shù)編碼；離散變量；R.C.框架優(yōu)化設(shè)計

中圖分類號：S611文獻(xiàn)標(biāo)識碼： A

0 引言

遺傳算法(Genetic Algorithm，GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法。與傳統(tǒng)優(yōu)化算法相比，其具有隱行性、全局性和較好的魯棒性的同時，又易于理解，操作簡單的優(yōu)點(diǎn)。采用二進(jìn)制編碼的標(biāo)準(zhǔn)遺傳算法(SGA)在結(jié)構(gòu)優(yōu)化領(lǐng)域已經(jīng)取得了一定的成果，但當(dāng)變量數(shù)量和約束數(shù)量增加時，標(biāo)準(zhǔn)遺傳算法由不一定能搜索到最優(yōu)個體。本文嘗試采用整數(shù)編碼進(jìn)行遺傳算法編寫，減少不同代碼之間的轉(zhuǎn)換工作，同時解決了離散化變量的優(yōu)化問題，與實際工程更為相符。

1 R.C.框架優(yōu)化模型

1.1目標(biāo)函數(shù)和設(shè)計變量

以框架結(jié)構(gòu)主體（主梁和柱）總造價為鋼筋混凝土框架結(jié)構(gòu)的目標(biāo)函數(shù)：

(1.1)

NEB、NEC――分別為梁總數(shù)和柱總數(shù)；

――第i號主梁的造價，包括梁的混凝土成本、縱筋成本、箍筋成本、模板成本；

――第j號柱的造價，包括柱的混凝土成本、縱筋成本、箍筋成本、模板成本；

梁柱以截面編號分組，一組構(gòu)件共享一個截面屬性，每個截面屬性有b、h兩個變量。另外每層柱的砼號相同，每層柱共享一個砼等級變量。對于一個5層框架結(jié)構(gòu)，若有梁柱截面分組各20個，則共有85非設(shè)設(shè)計變量。

1.2 約束條件

1）梁最大配筋率約束

要求支座兩端和跨中的受壓區(qū)高度滿足相對界限受壓區(qū)的高度要求，即

(1.2)

(1.3)

(1.4)

ξl 、ξr、ξm――為左支座、右支座、跨中的相對受壓區(qū)高度；

ξb ――界限受壓區(qū)高度。

2）梁最小截面約束

對于非抗震組合設(shè)計時鋼筋混凝土梁受剪截面應(yīng)滿足如下約束：

(1.5)

V――梁剪力設(shè)計值；

βc――混凝土強(qiáng)度影響系數(shù)。

對于抗震組合設(shè)計時鋼筋混凝土梁受剪截面應(yīng)滿足如下約束：

當(dāng)l0/h > 2.5時，有：

(1.6)

當(dāng)l0/h ≤ 2.5時，有：

(1.7)

3）梁撓度約束

(1.8)

f ―― 準(zhǔn)永久荷載組合下梁的撓度；

[f ] ――梁撓度限制。

4）梁截面高寬比約束

(1.9)

bbh――梁的截面高寬比，一般取4。

5）柱最大配筋率約束

(1.10)

Asb、Ash ――分別為b方向、h方向單偏壓計算配筋面積。

ρmax ―― 柱全截面最大配筋率，取5%。

6）柱最小截面約束

以h方向的抗剪截面要求為例，非抗震組合設(shè)計時鋼筋混凝土梁受剪截面應(yīng)滿足如下約束：

(1.11)

抗震組合設(shè)計時鋼筋混凝土梁受剪截面應(yīng)滿足如下約束：

當(dāng)剪跨比λ大于2.5時，有：

(1.12)

當(dāng)剪跨比λ不大于2.5時，有：

(1.13)

7）柱軸壓比約束

(1.14)

αp ――軸壓比限值?？蚣芙Y(jié)構(gòu)抗震等級為一級、二級、三級、四級時分別取0.65、0.75、0.85、0.90。

8）柱截面高寬比約束

以h方向截面高寬為例

(1.15)

cbh――柱的截面高寬比，一般取3。

9）樓層混凝土等級約束：

第i層的混凝土等級不大于第i-1層的混凝土等級，其約束表達(dá)式為：

(1.16)

2整數(shù)編碼遺傳算法設(shè)計

2.1初始種群生成和適應(yīng)度函數(shù)

已知框架結(jié)構(gòu)中的變量均為符合一定模數(shù)制的離散值。

設(shè)已有目標(biāo)函數(shù)f (x)，有x=(x1，x2，x3……,xn)，x ∈ XD，(i=1,2,3……,n)，其中XD為離散空間。

對第i個變量，有vi ≤ xi ≤ui ，其中vi、ui為第i個變量的上下界，ci為xi在定義域內(nèi)的間隔距離，vi ∈ N*、ui ∈ N*、ci ∈ N*，N*為正整數(shù)集合。

指定遺傳算法中迭代種群規(guī)模為M時，則隨機(jī)生成的個體變量如下：

(2.1)

(i=1,2,3……,n) (j=1,2,3……,M)

其中為在[0,1]內(nèi)的隨機(jī)數(shù)，INT為向下取整的計算。對目標(biāo)函數(shù)為最小化的問題可構(gòu)造如式2.2的適應(yīng)度函數(shù)：

(2.2)

cmax可以是是當(dāng)前所有代或最近K代中f(x)的最大值。

2.2自適應(yīng)交叉算子

為了保障在種群進(jìn)化過程中優(yōu)良的個體不被破壞流失，同時保障有新的個體加入，本文不采用固定的交叉概率，而是根據(jù)需要交叉配對的兩個個體的適應(yīng)值計算自適應(yīng)的交叉概率。假設(shè)和兩個需要進(jìn)行交叉計算的個體，其確定自適應(yīng)交叉概率的公式為式2.3：

(2.3)

――為當(dāng)前種群的平均適應(yīng)值

――為這前種群中的最佳適應(yīng)值

k1、k2――確定交叉變量Pc的相關(guān)常數(shù)，由計算人員確定，一般k2比k1略大

當(dāng)和中適應(yīng)值的較大者大于等于平均適應(yīng)值時，調(diào)整減小交叉概率Pc。當(dāng)和中適應(yīng)值的較大者小于平均適應(yīng)值時，交叉概率Pc等于較大的k2。

當(dāng)交叉的隨機(jī)判定數(shù)RND小于Pc時，個體和需要進(jìn)行染色體交叉計算生成新的子代染色體，否則兩者直接遺傳到子代中，見式2.4，式中為程序自帶產(chǎn)生的隨機(jī)數(shù)。為了保證交叉產(chǎn)生的子代滿足模數(shù)制，還需用式2.5進(jìn)行修正。

(2.4)

以為例進(jìn)行基于模數(shù)制的修正，有：

(2.5)

2.3自適應(yīng)變異算子

本文同樣不采用固定的變異概率，而是根據(jù)需要變異個體的適應(yīng)值計算自適應(yīng)的變異概率。假設(shè)個體需要進(jìn)行變異計算，其確定自適應(yīng)變異概率的公式為式2.6：

(2.6)

k3、k4――確定交叉變量Pm的相關(guān)常數(shù)，由計算人員確定，一般k4比k3略大

當(dāng)個體的適應(yīng)值的大于等于平均適應(yīng)值時，根據(jù)式2.6-(1)調(diào)整減小交叉概率Pm。當(dāng)?shù)倪m應(yīng)值的小于平均適應(yīng)值時，根據(jù)2.6-(2)交叉概率Pm等于k4。

當(dāng)交叉的隨機(jī)判定數(shù)RND小于P m時，根據(jù)式2.7對基因進(jìn)行非均勻變異：

(2.7)

、――系統(tǒng)程序自帶產(chǎn)生的隨機(jī)數(shù)。

2.4錦標(biāo)賽選擇算子

本文根據(jù)選用錦標(biāo)賽選擇作為主要選擇方法。錦標(biāo)賽選擇，又稱隨機(jī)聯(lián)賽選擇，是每次隨機(jī)從進(jìn)化代種群中取出一定數(shù)量（Tour）個體，然后選擇其中最佳個體進(jìn)入下一代種群。重復(fù)操作，直到新的種群規(guī)模達(dá)到原來的種群規(guī)模。

3算例分析

3.1工程概況

算例框架結(jié)構(gòu)，5層；層高3米；設(shè)防烈度7度(0.10g)；地震分組一組；Tg=0.9s；抗震等級為三級；基本風(fēng)壓為0.55kN/m2；地面粗糙程度B類。ETABS模型中每層分為4組梁截面和4組柱截面，平面布置規(guī)則以第5層平面圖為例，每層構(gòu)件分組見圖1。各組梁截面屬性的初始截面為300mm×700mm，柱截面屬性的初始截面為500mm×500mm。最大層間位移角限值為1/550。梁混凝土等級統(tǒng)一采用C30，造價為465元/m3。柱混凝土等級共有1~5個代碼，分別對應(yīng)C30~C50的混凝土等級，各等級單價依此為583元/m3，604元/m3，626元/m3，648元/m3 ，676元/m3。梁模板的單價為82元/kg，梁鋼筋單價為4793元/t，柱模板單價為99元/kg，柱鋼筋單價為4918元/t。主要優(yōu)化參數(shù)設(shè)置見表1。

圖1ETABS模型三維視圖圖2第5層平面布置圖

3.2整體優(yōu)化流程

本文整體優(yōu)化分為兩部執(zhí)行，第一部分凍結(jié)內(nèi)力做結(jié)構(gòu)尺寸的優(yōu)化，第二部分在第一部分得到的新最優(yōu)個體的基礎(chǔ)上，更新模型內(nèi)力，再次執(zhí)行第一部分的操作，反復(fù)這個過程直到造價滿足收斂條件，終止優(yōu)化程序，

輸出最終的優(yōu)化結(jié)果。在第一部分優(yōu)化又分兩個級別。第一級為不考慮結(jié)構(gòu)剛度對內(nèi)力的影響，在梁柱構(gòu)件約束和層間約束下執(zhí)行遺傳算法；第二級為在遺傳算法優(yōu)化得到的最佳個體后，回代入ETABS模型驗算位移約束，如果不滿足位移約束則執(zhí)行行相應(yīng)的調(diào)整策略不斷更新ETABS模型直到滿足位移約束。整體優(yōu)化的步驟為：

①識別模型

②凍結(jié)內(nèi)力，讀取內(nèi)力分析結(jié)果

③生成初始種群

④遺傳算法操作：交叉、變異、選擇

⑤評估新種群

⑥是否達(dá)到遺傳算法收斂精度，是則進(jìn)入下一步，否則返回執(zhí)行④~⑤

⑦驗算位移約束，不通過調(diào)整模型直到通過為止

⑧框架總造價是否整體收斂，是則輸出內(nèi)力，否則解凍內(nèi)力，更新模型，返回執(zhí)行②~⑦

3.3優(yōu)化結(jié)果

部分優(yōu)化參數(shù)取值見表1，優(yōu)化過程中造價的下降曲線見圖3。本案例共進(jìn)行了5次整體優(yōu)化計算，最終優(yōu)化造價比原始設(shè)計造價下降30%，優(yōu)化效果顯著。由于本文引入了遺傳算法的自適應(yīng)參數(shù)調(diào)整，目標(biāo)函數(shù)的下降速度快，整體優(yōu)化的效率高。優(yōu)化后的最大層間位移角出現(xiàn)在第二層為1/552（見表2），說明結(jié)構(gòu)的剛度在滿足規(guī)范要求的前提下，變得更合理。

表1優(yōu)化參數(shù)取值

圖3造價優(yōu)化下降曲線

表2 優(yōu)化后的層間位移角

5 結(jié)論

本文直接采用整數(shù)編碼，能夠良好得描述工程結(jié)構(gòu)問題中離散變量在遺傳算法中的種群生成、交叉、變異、選擇。采用分部優(yōu)化法，反應(yīng)結(jié)構(gòu)尺寸和結(jié)構(gòu)內(nèi)力的非線性關(guān)系。通過算例驗證，本文的方法優(yōu)化效果良好，優(yōu)化效率高，給其他采用遺傳算法優(yōu)化設(shè)計的結(jié)構(gòu)模型提供了有益的參考。

參考文獻(xiàn)

[1] 張琦. 采用遺傳算法對鋼筋混凝土框架結(jié)構(gòu)進(jìn)行優(yōu)化設(shè)計[D]. 山東大學(xué)碩士學(xué)位論文, 2006, 5.

[2]肖國濤. 基于遺傳算法的鋼管混凝土框架結(jié)構(gòu)優(yōu)化研究[D]. 華中科技大學(xué)碩士學(xué)位論文, 2005, 3.

[3] 陸海燕. 基于遺傳算法和準(zhǔn)則法的高層建筑結(jié)構(gòu)優(yōu)化設(shè)計研究[D]. 大連理工大學(xué)博士學(xué)位論文, 2009, 6.

[4] [19] 張思才, 張方曉. 自適應(yīng)遺傳算法在桁架結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J].湘潭大學(xué)自然科學(xué)學(xué)報, 2002, 24(4): 37 - 411.

第4篇：遺傳算法論文范文

關(guān)鍵詞：遺傳算法；智能組卷；應(yīng)用模式

中圖分類號：TP311.52

考試作為教育測量學(xué)和教育統(tǒng)計學(xué)和的基本原理，不僅是對學(xué)生學(xué)習(xí)能力和知識水平的檢驗方式，也是對教師教育教學(xué)水平評價和體現(xiàn)的重要手段之一。如何更加客觀公正地反映學(xué)生的學(xué)習(xí)狀況，全面地掌握和評價教師的教學(xué)工作能力，進(jìn)一步提升教師的教學(xué)水平，實現(xiàn)教學(xué)與考試相分離，使得院校整體工作效率得以提高，因而，開發(fā)出科學(xué)高效的組卷系統(tǒng)尤為重要。

1 遺傳算法的基本原理

遺傳算法（Genetic Algorithm）GA是以達(dá)爾文進(jìn)化論和孟德爾遺傳學(xué)作為基礎(chǔ)，結(jié)合數(shù)學(xué)理論的一種自適應(yīng)隨機(jī)全局優(yōu)化算法。該算法模擬生物的自然選擇和遺傳規(guī)律，對目標(biāo)群體施以選擇、交叉、變異等一系列遺傳操作，使群體內(nèi)個體的適應(yīng)性提高，從而產(chǎn)生出新一代群體，個體不斷進(jìn)化并逐漸接近最優(yōu)解的狀態(tài)，形成一種“生存+檢驗”的搜索尋優(yōu)算法。遺傳算法以編碼群體為進(jìn)化基礎(chǔ)，將問題的參數(shù)空間以編碼空間加以替代，評價標(biāo)準(zhǔn)表示為適應(yīng)度函數(shù)，通過對群體中個串進(jìn)行的遺傳操作實現(xiàn)選擇和遺傳，形成迭代過程。在此過程中，對編碼位串中重要的基因進(jìn)行隨機(jī)重組，使位串集合的新一代總是優(yōu)于上一代，群體中的個體不斷地進(jìn)化而接近最優(yōu)解，達(dá)到求解問題的目的。運(yùn)用遺傳算法提供的通用模型，可以解決涉及到任何方面、何種類型的問題，因此遺傳算法的應(yīng)用正在向多學(xué)科領(lǐng)域滲透。遺傳算法與人工神經(jīng)網(wǎng)絡(luò)、模糊控制理論等正在成為二十一世紀(jì)計算機(jī)智能研究的熱點(diǎn)。

2 改進(jìn)的遺傳算法

遺傳算法的選擇與設(shè)計取決于最初的編碼設(shè)計，而實現(xiàn)問題的解編碼成為染色體是編碼設(shè)計的關(guān)鍵問題。二進(jìn)制編碼、實數(shù)編碼、字母排列編碼等編碼方式是目前較為常見的編碼方式。

遺傳算法適應(yīng)度函數(shù)的確定是采用該算法進(jìn)行智能組卷的關(guān)鍵。適應(yīng)度函數(shù)值為遺傳進(jìn)化過程設(shè)置標(biāo)準(zhǔn)，以此標(biāo)準(zhǔn)有效地區(qū)分個體的優(yōu)劣。如果適應(yīng)度函數(shù)確定的好，在區(qū)分個體優(yōu)劣時，能夠防止好的個體過快擴(kuò)散、壞的個體過快淘汰，從而對群體多樣性的保持起到積極作用，遏制“早熟”現(xiàn)象的出現(xiàn)。

3 與智能組卷系統(tǒng)相關(guān)理論

3.1 智能組卷原則及特點(diǎn)

智能組卷系統(tǒng)研究的重點(diǎn)是如何在短時間內(nèi)生成高質(zhì)量的試卷，并且保證生成的試卷能最大程度地滿足使用者的不同需求。由計算機(jī)考試系統(tǒng)的試題庫中抽取試題組成的試卷，必須能夠作為考察學(xué)生學(xué)習(xí)效果、體現(xiàn)教師教學(xué)水平的重要工具和手段，因而勢必對試卷的組成要求更加提高。

3.2 智能組卷系統(tǒng)指標(biāo)體系

指標(biāo)體系作為組卷問題的重要組成部分在試題庫系統(tǒng)中扮演著重要的角色，某些固有特性參數(shù)就包含在試題本身，描述這些固有特性參數(shù)需要設(shè)定相應(yīng)的指標(biāo)，多個指標(biāo)組織構(gòu)建成指標(biāo)體系，試題指標(biāo)體系的建立對組卷模塊功能加以支持。

4 智能組卷系統(tǒng)實現(xiàn)

4.1 系統(tǒng)設(shè)計

模塊化編程具有使程序結(jié)構(gòu)的設(shè)置更加科學(xué)合理，可讀性進(jìn)一步增強(qiáng)，并且維護(hù)更加簡單易行等優(yōu)點(diǎn)。模塊化編程對輸出數(shù)據(jù)的保護(hù)表現(xiàn)在，模塊之間數(shù)據(jù)傳輸通過中間量，屬性數(shù)據(jù)存儲在各自的模塊中不宜被破壞或丟失，使系統(tǒng)的安全性大幅提高。模塊化編程具備較強(qiáng)的通用性，對于同一類型的控制可以直接或簡單修改就應(yīng)用其中。

4.2 系統(tǒng)基本功能

本系統(tǒng)的開發(fā)是采用PHP與MYSQL相結(jié)合的方式，服務(wù)器采用Apache。組卷管理、試題管理、用戶管理等是試題庫系統(tǒng)必須具備的基本功能。組卷管理包括自動組卷、手動組卷和測驗組卷三部分，是系統(tǒng)的核心。試題管理執(zhí)行試題的錄入、修改、刪除等功能。用戶管理執(zhí)行用戶增加、刪除、權(quán)限管理等功能。根據(jù)實際需要，系統(tǒng)還可以設(shè)置試題科目、題型、專業(yè)信息等等其他功能。系統(tǒng)功能模塊如表1如下：

表1 系統(tǒng)主要功能模塊示意圖

試題庫管理系統(tǒng)

組卷管理 試題管理 綜合管理

自動組卷 手動組卷 測驗組卷 錄入試題 修改試題 刪除試題 科目管理 題型管理 專業(yè)管理 其他管理

下面以組卷管理模塊為例子進(jìn)行組卷系統(tǒng)生成。

4.3 組卷管理模塊

（1）自動組卷。自動組卷生成如圖1所示：

圖1 系統(tǒng)自動組卷界面

（2）手動組卷。手動組卷雖然在步驟上同自動組卷比較要繁瑣得多，但是用戶能夠根據(jù)實際需求組織試卷，因而更具自主性。用戶在進(jìn)入手動組卷模式后，按照先選題型后選知識點(diǎn)的順序，將符合要求的所有試題選出，再逐一選擇試題。對所有題型采用上述操作即可完成手動組卷。

（3）測試組卷。測驗組卷與自動組卷在操作上相類似。由于只突出更便于教師測試的功能，因而無需設(shè)置試題分?jǐn)?shù)以及對分?jǐn)?shù)進(jìn)行校驗。這種方式可以大幅度提高成卷速度，因而對于完成某些特定情況下的工作具有一定意義。比如要測試選擇題出現(xiàn)如圖2所示：

圖2 系統(tǒng)選擇試題界面

總之，通過對組卷問題相關(guān)理論的對比、分析、研究，總結(jié)出常見組卷策略各自的優(yōu)缺點(diǎn)。將項目測量理論IRT作為基礎(chǔ)，綜合考慮教師組卷時的實際需要以及組卷策略必須遵守的基本原則，在對考卷信度與效度、題目難度與區(qū)分度等基本屬性分析研究的情況下，建立了組卷問題的數(shù)學(xué)模型。

參考文獻(xiàn)：

[1]楊棟.組卷的遺傳算法設(shè)計[J].現(xiàn)代計算機(jī)，2010，8（265）：8-9.

[2]林順剛.遺傳算法概述[J].科技信息（學(xué)術(shù)研究），2011，22（057）：90.

[3]魏平，熊偉清，趙杰煌.遺傳算法的早熟現(xiàn)象研究[J].計算機(jī)應(yīng)用研究，2012（09）：12-14.

第5篇：遺傳算法論文范文

關(guān)鍵詞:遺傳算法,分類器,分類優(yōu)化,集成學(xué)習(xí)

中圖分類號:TP18文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)33-9615-02

Discuss the Method of Classification with Genetic Algorithm

WANG Xin-Xin

(Software College, MinJiang University, FuZhou 350011, China)

Abstract: In the classifier system, applied genetic algorithm(GA) to optimized the classifier system which is use a single classify method or multiple classify methods. For the first classifier system, GA make the better precision; and for the other one, GA can make the classifier system to be more precise and apprehensive.

Key words: genetic algorithm(GA); classifier system; classify optimization; ensemble learning

分類問題是集成學(xué)習(xí)的基本研究問題,即對一個分類器輸入一個實例的特征集,然后對這些特征進(jìn)行判斷,對這個樣本進(jìn)行歸類并輸出。在醫(yī)療診斷、語音識別、數(shù)據(jù)挖掘、人像識別等領(lǐng)域都有廣泛的應(yīng)用。

J.H.Holland于1975年出版了《Adaptation in Natural and Artificial Systems》[1],標(biāo)志著遺傳算法的正式產(chǎn)生。遺傳算法是一種概率搜索算法,利用編碼技術(shù)作用于被稱為是染色體的二進(jìn)制數(shù)串,其基本思想是模擬這些串組成的群體的進(jìn)化過程。遺傳算法通過有組織的然而是隨機(jī)的信息交換來重新組合那些適應(yīng)性好的串,在每一代中,利用上一代串結(jié)構(gòu)中適應(yīng)性好的位和串來生成一個新的串的群體。這是一類隨機(jī)算法,但不是簡單地隨機(jī)走動,而是利用已有的信息來搜尋那些有希望改善質(zhì)量的串,這個過程類似于自然進(jìn)化。[2]

1 遺傳算法的特點(diǎn)

與其他傳統(tǒng)的優(yōu)化算法相比,遺傳算法在搜索的過程中采用群體搜索方式,有利于達(dá)到全局最優(yōu)。依據(jù)個體相對優(yōu)劣的適應(yīng)度指標(biāo)進(jìn)行搜索,即使所定義的適應(yīng)函數(shù)存在不連續(xù)、不規(guī)則或有噪聲等情況,也可進(jìn)行處理。通過在遺產(chǎn)算法中使用雜交算子,可將算法的注意力更多地集中到搜索空間中期望值高的那部分;同時,為了避免局部最優(yōu),在遺傳算法中引入變異,這樣既可在當(dāng)前附近找到更好的解得同時保持群體多樣性,有利于群體的繼續(xù)優(yōu)化。[2]

但是,由于進(jìn)化的過程具有隨機(jī)性,遺傳算法搜索的結(jié)果具有一定的不穩(wěn)定性,因此,與傳統(tǒng)的優(yōu)化算法相比,遺傳算法的優(yōu)化效率相對較低。[3]

2 基于遺傳算法的分類優(yōu)化方法

文獻(xiàn)[4]中提出了一種基于遺傳算法的分類優(yōu)化方法。該方法針對兩種分類器進(jìn)行優(yōu)化。一種分類器采用一種分類方法,使用遺傳算法對分類結(jié)果進(jìn)行優(yōu)化。另一種是在分類器中使用幾種不同的分類方法,使用遺傳算法作為綜合方法對分類結(jié)果進(jìn)行綜合優(yōu)化。在一套訓(xùn)練集上使用一種方法,由此產(chǎn)生一個唯一的模型,不同的方法在同一套訓(xùn)練集上產(chǎn)生的模型也不一定相同。有些方法在某一類任務(wù)上的性能很好,但是在另外一類任務(wù)上的性能則較差,它們的預(yù)測結(jié)果有可能是錯的,因此使用遺傳算法可以將多種分類方法結(jié)合起來提高精度。

2.1 數(shù)據(jù)和算法集的定義

數(shù)據(jù)集合L={xn,yn},n=1,…,N},其中,xi是輸入屬性,yi是輸出屬性,N是例子數(shù)目。設(shè)有M個學(xué)習(xí)算法,分別用A1,A2,…,AM表示。A(R,S),其中A是算法,R是算法空間,S是算法搜索的空間。算法對數(shù)據(jù)集合進(jìn)行學(xué)習(xí),得到不同的學(xué)習(xí)結(jié)果,利用遺傳算法對這些結(jié)果進(jìn)行結(jié)合,得到一個綜合結(jié)果。

2.2 基于遺傳算法的組合方法框架

在L0層中,每個算法對輸入的訓(xùn)練集數(shù)據(jù)進(jìn)行訓(xùn)練,各自生成一套對分類問題的表示,利用規(guī)則產(chǎn)生器對將L0層中關(guān)于分類問題的表達(dá)轉(zhuǎn)換為規(guī)則,然后作為L1層的輸入。在L1層中使用遺傳算法對規(guī)則集進(jìn)行綜合,生成最終分類器。這種方法綜合各分類器的優(yōu)點(diǎn),其結(jié)果精度高于各單個分類器,用規(guī)則集表示其結(jié)果。

2.3 如何使用遺傳算法對規(guī)則進(jìn)行優(yōu)化

1) 編碼表示

GlodBerg在上個世紀(jì)80年代對遺傳算法進(jìn)行歸納,在文獻(xiàn)[5]中總結(jié)了遺傳算法的基本框架。根據(jù)該算法,一個個體代表問題的一組解,每一個個體含有表達(dá)全部解的一組規(guī)則集。規(guī)則由條件和結(jié)論組成:“if (x1,y1) and (x2,y2),…,and (xn,yn) then Cj”每一個規(guī)則用一個染色體表示。

2) 適應(yīng)函數(shù)

適應(yīng)函數(shù)由匹配值和不匹配值兩個參數(shù)組成,當(dāng)分類器能對規(guī)則進(jìn)行正確識別并與結(jié)果匹配,則增加匹配值;若不能,則增加不匹配值;如果條件無法識別,則這兩個參數(shù)都不變。

3) 選擇策略

利用遺傳算法來產(chǎn)生新的規(guī)則,采用限制策略,對于同類規(guī)則,可進(jìn)行進(jìn)化,而對于結(jié)論相同的規(guī)則,則只在其條件部分進(jìn)行進(jìn)化。對于結(jié)論相同的規(guī)則只在條件部分進(jìn)行進(jìn)化的目的是為了防止出現(xiàn)不收斂的情況。

4) 遺傳算子

選擇算子:選擇算子從群體中選擇優(yōu)秀的個體,淘汰劣質(zhì)的個體,將適應(yīng)度高的候選解遺傳到下一代。在選擇的過程中以適應(yīng)度為依據(jù)進(jìn)行選擇,獨(dú)立于編碼方式。

雜交算子:雜交是按照一定的概率將兩個父代個體的部分結(jié)構(gòu)加以交換重組,然后產(chǎn)生新的個體。在本文中,個體間同類規(guī)則的相同基因位進(jìn)行交叉。

圖2對遺傳算法的交叉算子進(jìn)行描述。

變異算子:變異算子使個體中某些基因發(fā)生突變,遺傳算法中的變異運(yùn)算通過位的取反操作實現(xiàn)。在本文中,通過對屬性邊界值進(jìn)行突變實現(xiàn)。圖3描述了變異算子。

5) 終止規(guī)則

遺傳算法循環(huán)執(zhí)行計算適應(yīng)值,選擇復(fù)制和應(yīng)用雜交和變異算子幾個步驟,直到找到滿足條件的解。

3 優(yōu)化結(jié)果討論

3.1 對使用一種分類方法的分類器進(jìn)行優(yōu)化

文獻(xiàn)[4]表明,遺傳算法優(yōu)化后的精度優(yōu)于使用單個算法的精度。對于屬性值十分接近的分類目標(biāo),使用單一屬性生成的規(guī)則進(jìn)行區(qū)分是很難實現(xiàn)的,而只有采用屬性值的組合才能實現(xiàn)這類分類目標(biāo)的區(qū)分。

3.2 對使用多種分類方法的分類器進(jìn)行優(yōu)化

在文獻(xiàn)[4]中,使用遺傳算法對基于C5.0和神經(jīng)網(wǎng)絡(luò)的規(guī)則集進(jìn)行優(yōu)化。優(yōu)化后,得到兩套規(guī)則集,基于C5.0的規(guī)則集邊界值發(fā)生改變,新的規(guī)則在精度上比原來更高。而基于神經(jīng)網(wǎng)絡(luò)的規(guī)則集在形式上沒有發(fā)生改變。對兩種規(guī)則集進(jìn)行比較,發(fā)現(xiàn)基于C5.0的規(guī)則集和基于神經(jīng)網(wǎng)絡(luò)的規(guī)則集均具有較高的精度,但是從理解性的方面考慮,基于C5.0的規(guī)則集既有較好的可理解度。

4 小結(jié)

該文討論了一種基于遺傳算法的分類器優(yōu)化方法,在分類技術(shù)中結(jié)合遺傳算法可以得到更好的分類效果,得到的分類結(jié)果更精確、易于理解。用分類技術(shù)處理原始數(shù)據(jù)集從而得到初步的規(guī)則集,而遺傳算法通過優(yōu)化規(guī)則條件的部分邊界值提高了分類的精度。這種方法具有較好的魯棒性和可延展性,當(dāng)給定的邊界值與其正確的位置相距很遠(yuǎn),也可通過遺傳算法對全局進(jìn)行搜索得到解空間的最優(yōu)解;如果在分類器中采用新的分類方法,可將分類的結(jié)果轉(zhuǎn)化為規(guī)則集作為遺傳算法輸入,這些新的規(guī)則集與已有的規(guī)則集一起進(jìn)行演化,從而得到更好的結(jié)果。

參考文獻(xiàn):

[1] Holland J H. Adaptation in Natural and Artificial Systems[M]. MIT Press,1992.

[2] 劉勇,康立山,陳毓屏.非數(shù)值并行算法遺傳算法[M].2冊.北京:科學(xué)出版社,1995.

[3] 孫瑞祥,屈梁生.進(jìn)化計算的過去、現(xiàn)在與未來[C]//進(jìn)化計算研究生論壇論文集.西安:西安交通大學(xué),2001.

第6篇：遺傳算法論文范文

論文摘要：tsp是組合優(yōu)化問題的典型代表,該文在分析了遺傳算法的特點(diǎn)后,提出了一種新的遺傳算法(gb—mga),該算法將基因庫和多重搜索策略結(jié)合起來,利用基因庫指導(dǎo)單親遺傳演化的進(jìn)化方向,在多重搜索策略的基礎(chǔ)上利用改進(jìn)的交叉算子又增強(qiáng)了遺傳算法的全局搜索能力。通過對國際tsp庫中多個實例的測試,結(jié)果表明:算法(gb—mga)加快了遺傳算法的收斂速度,也加強(qiáng)了算法的尋優(yōu)能力。

tsp(traveling salesman problem)可以簡述為:有n個城市1,2,…,n,一旅行商從某一城市出發(fā),環(huán)游所有城市后回到原出發(fā)地,且各城市只能經(jīng)過一次,要求找出一條最短路線。tsp的搜索空間是有限的,如果時間不受限制的話,在理論上這種問題終會找到最優(yōu)解,但對于稍大規(guī)模的tsp,時間上的代價往往是無法接受的。這是一個典型的組合最優(yōu)化問題,已被證明是np難問題,即很可能不存在確定的算法能在多項式時間內(nèi)求到問題的解[1]。由于tsp在工程領(lǐng)域有著廣泛的應(yīng)用,如貨物運(yùn)輸、加工調(diào)度、 網(wǎng)絡(luò) 通訊、電氣布線、管道鋪設(shè)等,因而吸引了眾多領(lǐng)域的學(xué)者對它進(jìn)行研究。tsp的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法[2]、螞蟻算法[3]、模擬退火算法、遺傳算法等。

遺傳算法是一種借鑒生物界 自然 選擇和遺傳機(jī)制的隨機(jī)化搜索算法,其主要特點(diǎn)是群體搜索策略和群體中個體之間的信息交換,搜索不依賴于梯度信息[4]。wWw.133229.COM遺傳算法主要包括選擇、交叉和變異3個操作算子,它是一種全局化搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。遺傳算法雖然不能保證在有限的時間內(nèi)獲得最優(yōu)解,但隨機(jī)地選擇充分多個解驗證后,錯誤的概率會降到可以接受的程度。

用遺傳算法求解tsp能得到令人滿意的結(jié)果,但是其收斂速度較慢,而且種群在交叉算子作用下,會陷入局部解。采用局部啟發(fā)式搜索算法等,雖然能在很短的時間內(nèi) 計算 出小規(guī)模城市的高質(zhì)量解,一旦城市規(guī)模稍大就容易陷入局部最優(yōu)解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優(yōu)解,該文采納了文[5]中楊輝提出的基因庫的想法,并結(jié)合文[6]中cheng-fa tsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來求解tsp問題。該文根據(jù)文[7]中最小生成樹mst(minimum cost spanning tree)的應(yīng)用,由mst建立tsp的基因庫,保存有希望成為最優(yōu)解的邊,利用基因庫提高初始群體的質(zhì)量進(jìn)行單親演化,然后利用改進(jìn)后的交叉算子和的多重搜索策略進(jìn)行群體演化。

1　單親演化過程

現(xiàn)有的大多數(shù)演化算法在整個演化過程中所涉及的基因,大多來源于個體本身,個體質(zhì)量的高低決定了算法的全局性能,如果群體中初始個體的適應(yīng)度都較差,肯定要影響算法的收斂速度,對于規(guī)模稍大的tsp尤其明顯[8]。該文為了克服上述弱點(diǎn),首先利用普里姆算法求出tsp中最小生成樹,并將各個mst中的每一條邊都保存在一個n*(n-1)方陣?yán)锩?就構(gòu)成了一個基因庫,在生成初始群體的時候盡量使用基因庫中的基因片段,來提高整個初始群體的適應(yīng)度,從而提高算法的效率。

1.1　tsp編碼表示

設(shè)n個城市編號為1,2,…,n,為一條可行路徑,pk=vk1vk2…vkn為一條可行路徑,它是1,2,…,n的一個隨機(jī)排列,其含意是第k條路徑起點(diǎn)城市是vk1,最后一個城市是vkn,則第k條環(huán)路的總長度可以表示為:

其中,d(vki,vkj)表示城市vki與城市vkj之間的距離。在算法中環(huán)路pk的總長d(pk)用來評價個體的好壞[9]。適應(yīng)度函數(shù)取路徑長度d(pk)的倒數(shù),f(pk)=1/ d(pk)。

1.2　構(gòu)建tsp基因庫

對n個編號為1,2,…,n的城市,根據(jù)它們的坐標(biāo)計算各城市之間的歐氏距離d(i,j),i,j=1,2,…,n,得到一個n*n的方陣d={ d(i,j)}。然后利用普里姆算法求得該tsp的一棵mst,并將這棵mst中的每一條邊e(i,j)對應(yīng)地存儲在一個n*(n-1)的方陣m={ e(i,j)},即該文的基因庫。由于一個tsp可能有多棵mst,操作可以重復(fù)多次,這樣生成的基因庫中的基因就更多,增強(qiáng)了初始群體的全局性。具體算法如下:

void minispantree—prim(mgraph g,vertextypeu){

struct {

vertextype adjvex;

vrtype lowcost;

}closedge[max—vertex—num];

k=locatevex(g,u);

for(j=0;j<g.vexnum;++j)

if(j!=k)closedge[j]={u,g.arcs[k][j].adj};

closedge[k].lowcost=0;

for(i=0;i<g.vexnum;++i){

k=minimum(closedge);

printf(closedge[k].adjvex,g.vexs[k]);

closedge[k].lowcost=0;

for(j=0;j<g.vexnum;++j)

if(g.arcs [k][j].adj<closedge[j].lowcost)

closedge[j]={g.vexs[k],g.arcs[k][j].adj};

}

}

1.3　單親演化算法

單親演化算法是利用遺傳算法的優(yōu)勝劣汰的遺傳特性,在單個染色體內(nèi)以基因重組的方式,使子代在滿足tsp問題的限定條件下進(jìn)行繁衍,然后保留適應(yīng)度高的染色體種群,達(dá)到優(yōu)化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯位和基因段倒轉(zhuǎn)三種操作來實現(xiàn)?；驌Q位操作是將親代的染色體基因進(jìn)行對換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式?；蚨五e位操作是隨機(jī)確定基因段,也隨機(jī)選定錯位位置,整段錯移?；蚨蔚罐D(zhuǎn)操作則是隨機(jī)地確定倒轉(zhuǎn)基因段的起止位置,倒轉(zhuǎn)操作是對該段內(nèi)基因按中垂線作鏡面反射,若段內(nèi)基因數(shù)為奇數(shù)時,則中位基因不變。單親演化時可以是單個操作用于單個父代,也可以是幾種操作同時采用。為了編程方便,文中采用基因段倒轉(zhuǎn)操作。

2　群體演化過程

在單親演化算法求得的初始群體基礎(chǔ)上,再利用多重搜索策略并行地進(jìn)行群體演化,這樣在保證算法的快速收斂的同時也注重了搜索空間的全局性。

2.1　交叉算子

該文算子采用一種與順序交叉ox(order crossover)法類似的交叉方法[11],即隨機(jī)在串中選擇一個區(qū)域,例如以下兩個父串及區(qū)域選定為:

p1=(12|3456|789)　p2=(98|7654|321)

將p2的區(qū)域加到p1的前面或后面,p1的區(qū)域加到p2的前面或后面,得

m1=(7654|123456789)

m2=(3456|987654321)

在m1中自區(qū)域后依次刪除與區(qū)域相同的城市碼,得到最終的兩個子串:

s1=(765412389)　s2=(345698721)

同時為了能更好地增強(qiáng)算子的全局搜索能力,對該算子作了如下的改進(jìn)。子代個體的新邊來自:隨機(jī)生成和群體中其他個體,其選擇比例由隨機(jī)數(shù)p和閾值p來決定。如果隨機(jī)數(shù)p小于閾值p,則子代個體的新邊來自隨機(jī)生成,否則就來自群體中的其他個體。

這種改進(jìn)后的交叉算子在父串相同的情況下仍能產(chǎn)生一定程度的變異效果,這對維持群體的多樣化特性有一定的作用。實驗結(jié)果也證實了這種改進(jìn)算子對于種群的全局搜索能力有一定的提高,避免搜索陷入局部解。

2.2　局部啟發(fā)式算子

為了增強(qiáng)遺傳算法的局部搜索性能,在算法中引入2-opt局部搜索算子[12]。該算子通過比較兩條邊并交換路徑以提升算法的局部搜索性能,示例見圖2。

比較子路徑ab+cd和ac+bd,如果ab+cd>ac+bd則交換,否則就不交換?？紤]到程序的運(yùn)行效率,不可能對每對邊都做檢查,所以選取染色體中的一定數(shù)量的邊進(jìn)行比較。2-opt搜索算子實際上進(jìn)行的相當(dāng)于變異操作,同時又不僅僅是簡單的變異,而是提高算法的局部搜索性能的變異操作。

2.3　選擇機(jī)制和收斂準(zhǔn)則

為了限制種群的規(guī)模[13],該文采用了聯(lián)賽選擇法的淘汰規(guī)則。聯(lián)賽選擇法就是以各染色體的適應(yīng)度作為評定標(biāo)準(zhǔn),從群體中任意選擇一定數(shù)目的個體,稱為聯(lián)賽規(guī)模,其中適應(yīng)度最高的個體保存到下一代。這個過程反復(fù)執(zhí)行,直到保存到下一代的個體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)目為止。這樣做可能導(dǎo)致種群過早收斂,因此在收斂準(zhǔn)則上要采取苛刻的要求來保證搜索的全局性。

遺傳算法求tsp問題如果不設(shè)定終止條件,其演化過程將會無限制地進(jìn)行下去。終止條件也稱收斂準(zhǔn)則,因為多數(shù)最優(yōu)化問題事先并不了解最優(yōu)的目標(biāo)函數(shù)值,故無法判斷尋優(yōu)的精度。該文采用如下兩條收斂準(zhǔn)則:在連續(xù)k1代不再出現(xiàn)更優(yōu)的染色體;優(yōu)化解的染色體占種群的個數(shù)達(dá)k2的比例以上。當(dāng)兩準(zhǔn)則均滿足時,則終止運(yùn)算,輸出優(yōu)化結(jié)果和對應(yīng)的目標(biāo)函數(shù)值。由數(shù)值實驗表明,添加第2條準(zhǔn)則之后,全局最優(yōu)解的出現(xiàn)頻率將大為提高。

2.4　基于多重搜索策略的群體演化算法

由于基因庫的引入,可能降低初始種群的多樣性,為避免算法陷入局部最優(yōu)解,因此在群體演化中采取多重搜索策略。由cheng-fa tsai提出的多重搜索策略[6],就是把染色體集中的染色體分成保守型和探索型兩種不同類型的集合,然后針對不同類型的染色體集合根據(jù)不同的交叉、變異概率分別進(jìn)行交叉變異操作,對保守型染色體集合就采用比較低的交叉變異概率,而對探索型染色體集合就采用比較高的交叉變異概率。這種策略對保守型染色體集合的操作最大限度地保留了父代的優(yōu)秀基因片段,另一方面對探索型染色體集合的操作又盡可能地提高了算法的全局搜索能力。為了提高算法的收斂速度,初始染色體集合該文采用了前面單親演化的結(jié)果中的染色體集合,交叉算子則利用的是前面介紹的改進(jìn)后的算子,改進(jìn)后的多重搜索策略見下。

3　實驗結(jié)果與分析

該文的gb—mga算法由c#編程實現(xiàn),所有的結(jié)果都是在p42.0g微機(jī)上完成,并進(jìn)行通用的tsp庫實驗,選用了具有一定代表性的tsp實例,并把該算法和其他算法做了一個對比。為了減少 計算 量,程序中的數(shù)據(jù)經(jīng)過四舍五入整數(shù)化處理,與實數(shù)解有一定的偏差,下面給出圖kroa100的示例。

為了證明該文提出的gb—mga算法的有效性,將該文算法與典型的遺傳算法ga、單親遺傳算法pga以及文[5]中楊輝提出的ge—ga(gene pool genetic algorithm)算法和文[12]中提出的mmga(modified multiple-searching genetic algorithm)算法都進(jìn)行了一個對比。

實驗結(jié)果證明,該文算法的求解質(zhì)量要優(yōu)于ga、pga、mmga算法,而求解速度方面則優(yōu)于ge—ga算法,特別是對于大規(guī)模城市的tsp問題求解效果尤其明顯,具有快速收斂的特性。ge—ga算法對于中等城市規(guī)模的tsp實例求解,其運(yùn)算時間就大幅度增加,如果把該算法用于求解大規(guī)模和超大規(guī)模tsp問題,那么時間上的代價就讓人無法忍受。而該文的gb—mga算法在單親遺傳演化中就使用了基因庫中的優(yōu)質(zhì)基因,使得單個個體的進(jìn)化速度大大提高,從而為進(jìn)一步的演化提供了條件,群體演化過程的選擇機(jī)制和收斂準(zhǔn)則的恰當(dāng)選取使得算法在注重了求解質(zhì)量的同時兼顧了算法的效率。

結(jié)束語　該文在對tsp問題進(jìn)行分析的基礎(chǔ)上,通過對全局最優(yōu)解和局部最優(yōu)解中的邊關(guān)系的分析發(fā)現(xiàn),通過最小生成樹的求解保存最有希望成為全局最優(yōu)解的邊,可以提高算法的效率,同時并不降低搜索的性能。在實驗中發(fā)現(xiàn),通過生成基因庫快速提高種群質(zhì)量,雖然可以快速收斂,但是tsp問題的求解質(zhì)量并沒有達(dá)到一個可以接受的程度,因此在群體演化階段中又加入了2-opt局部搜索算子和多重搜索策略,對不同類型的染色體以不同幾率進(jìn)行選擇交叉操作。

用該算法測試tsp庫中的典型實例,結(jié)果顯示,對初始種群運(yùn)用單親遺傳算法,并引入基因庫方法是可行的,有效地提高了算法的效率和收斂速度,在群體演化過程中引入多重搜索策略的方法,提高了算法的并行性和全局尋優(yōu)性能,即使在較少的尋優(yōu)步數(shù)也能得到適應(yīng)度不錯的局部優(yōu)化解。gb-mga算法在提高算法求解質(zhì)量的同時兼顧了算法的效率, 但是其中還有許多有待解決的問題,比如如何構(gòu)建高質(zhì)量的基因庫,如何對現(xiàn)有基因庫進(jìn)行優(yōu)化和擴(kuò)充,以及算法中一些參數(shù)的選取問題等,這些方面,還需要進(jìn)一步的研究。

參考 文獻(xiàn)

1 bck t b,hammel u,schwefel h p.evolutionary computation:comments on the history and current state [j]. leee transactions on evolutionary computation,1997,2(6):3~17

2王磊,潘進(jìn),焦李成.免疫算法[j]. 電子 學(xué)報,2000,28(7):74~78

3 dorigo m,gambardella l m.ant colony system:a cooperativelearning approach to the traveling salesman problem [j]. ieeetransactions on evolutionary computation,1997,2(8):53~66

4 holland j h. adaptation in natural and artificial systems [m].ann arbor:the university of michigan,1975.10~15

5楊輝,康立山,陳毓屏.一種基于構(gòu)建基因庫求解tsp問題的遺傳算法[j].計算機(jī)學(xué)報,2003,26(12):1753~1758

6 tsai cheng-fa, tsai chun-wei, yang tzer. a modified multiple-searching method to genetic algorithms for solving travelingsalesman problem [j].ieee transactions on systems,man andcybernetics,2002,3(10):6~12

7 baraglia r,hidalgo j i, perego r. a hybrid heuristic for thetraveling salesman problem [j]. ieee transactions on evolutionary computation,2001,5(12):613~622

8 tsai cheng-fa, tsai chun-wei. a new approach for solvinglarge traveling salesman problem using evolutionary ant rules[c].in:proc.of the 2002 international joint conf.on neural networks,hawaiian:honolulu,2002

9 jung s,moon b r.toward minimal restriction of genetic encoding and crossovers for the two-dimensional euclidean tsp [j].ieee transactions on evolutionary computation,2002,6(12):557~565

10李茂軍,童調(diào)生,羅隆誦.單親遺傳算法及其應(yīng)用研究[j].湖南大學(xué)學(xué)報,1998,25(6):56~59

11陳國良,王煦法,莊鎮(zhèn)泉,等.遺傳算法及其應(yīng)用[m].徐修存,王曉丹.北京:人民郵電出版社,1996.75~81

第7篇：遺傳算法論文范文

關(guān)鍵字：頻率分配遺傳算法GECP組合優(yōu)化

1.通信網(wǎng)頻率分配問題的背景

無線通信設(shè)備之間通過相互發(fā)射電磁波達(dá)成信息溝通。相互通信的設(shè)備之間使用特定的頻率（信道）構(gòu)成無線通信鏈路。由于電磁波的自然特性，無線通信設(shè)備發(fā)射的電磁波可能對位于附近、滿足一定功率和頻率條件的其它設(shè)備形成干擾。頻率分配（FAP）的目的就是給工作在一定地域內(nèi)的無線通信設(shè)備指定使用的工作頻率(或信道)，使所有設(shè)備都以盡量小的概率擾，從而使整個網(wǎng)絡(luò)的可用性得到優(yōu)化。FAP可以描述為：對N個給定的待分配工作頻率的鏈路，設(shè)G={S1,S2,…Sn}為所有狀態(tài)構(gòu)成的解空間，C(si)為狀態(tài)si對應(yīng)的目標(biāo)函數(shù)值，尋找最優(yōu)解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一種組合優(yōu)化問題。

具體設(shè)備頻率分配方法雖然會隨著設(shè)備的工作方式（單工、雙工）、工作頻段、天線類型、信號的調(diào)制解調(diào)方式的不同而有所區(qū)別，但是大部分頻率分配算法都可以轉(zhuǎn)換為等價的圖的邊著色問題。從圖論算法理論上講，圖的廣義邊著色問題是NPC問題[7]，也就是說無法在多項式時間內(nèi)求得問題的最優(yōu)解。例如對于存在n條邊的無向圖，使用c種顏色對其著色，在沒有其它約束條件下，其解空間是cn。即使在不考慮顏色重復(fù)使用（c>n）的情況下，其解空間也達(dá)到n!。這兩者都是超越數(shù)，在c和n的值較大的情況下想利用窮舉搜索的方法求得問題的最優(yōu)解在時間上是不可行的。

在工程實踐中許多NPC問題使用一些使用的近似算法得到問題的可行解。這些方法包括[]：只對問題的特殊實例求解；動態(tài)規(guī)劃（DP）或者分支界限算法（BC）；概率算法；求近似解；啟發(fā)式算法（HeufisticAlgorithms）等。這些方法的和核心是分割問題的解空間，按照特定規(guī)則搜索典型解作為次最優(yōu)解。

對于FAP問題國內(nèi)外許多學(xué)者進(jìn)行了深入的研究，提出許多解決問題的方法。文獻(xiàn)[4]在對FAP進(jìn)行理論分析的基礎(chǔ)上給出了幾種常用算法的框架，這些算法包括：最小-最后次序查找算法，貪心T著色算法、模擬退火算法（SA）、列表尋優(yōu)算法（TS）、遺傳算法（GA）、神經(jīng)網(wǎng)絡(luò)（NN）多面體算法等，并指出各種算法有各自的適用范圍；文獻(xiàn)[2]提出了利用啟發(fā)式的螞蟻算法，并對解決CELAR、GRAPH、PHILADELPHIA上的幾類問題同TS和SA算法進(jìn)行了比較；文獻(xiàn)[1]比較了SA、TS、GA、VDS（variable–depthsearch）、BC等算法的性能。文獻(xiàn)[7]利用GECP理論對存在禁用頻率的異頻雙工設(shè)備的頻率分配給出工程上的實用算法；文獻(xiàn)[9]則采用了BC方法頻率分配的全排列算法進(jìn)行了優(yōu)化。本文將探討如何遺傳算法解決FAP問題。

2.遺傳算法在頻率分配問題中的適用性

2．1遺傳算法的原理

遺傳算法(GeneticAlgorithmsGA)是根據(jù)生物學(xué)上的染色體基因因子構(gòu)成機(jī)制而產(chǎn)生的。1975年Holland教授首次提出了GA的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機(jī)器學(xué)習(xí)等方面。遺傳算法是一種全局優(yōu)化算法，其僅以目標(biāo)函數(shù)值為搜索依據(jù)，通過群體優(yōu)化搜索和隨機(jī)執(zhí)行基本遺傳運(yùn)算，實現(xiàn)遺傳群體的不斷進(jìn)化，適合解決組合優(yōu)化問題和復(fù)雜非線性問題[6]。

利用遺傳算法解最優(yōu)化問題，首先應(yīng)對可行域中的點(diǎn)進(jìn)行編碼（一般采用二進(jìn)制編碼），然后在可行域中隨機(jī)挑選一些編碼組成作為進(jìn)化起點(diǎn)的第一代編碼組，并計算每個解的目標(biāo)函數(shù)值，也就是編碼的適應(yīng)度。接著就像自然界中一樣，利用選擇機(jī)制從編碼組中隨機(jī)挑選編碼作為繁殖過程前的編碼樣本。選擇機(jī)制應(yīng)保證適應(yīng)度較高的解能夠保留較多的樣本；而適應(yīng)度較低的解則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算子對挑選后的樣本進(jìn)行交換。交叉算子交換隨機(jī)挑選的兩個編碼的某些位，變異算子則直接對一個編碼中的隨機(jī)挑選的某一位進(jìn)行反轉(zhuǎn)。這樣通過選擇和繁殖就產(chǎn)生了下一代編碼組。重復(fù)上述選擇和繁殖過程，直到結(jié)束條件得到滿足為止。進(jìn)化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結(jié)果。

實踐表明，遺傳算法解最優(yōu)化問題的計算效率比較高、適用范圍相當(dāng)廣。為了解釋這一現(xiàn)象，Holland給出了模式定理。所謂模式，就是某些碼位取相同值的編碼的集合。模式定理說明在進(jìn)化過程的各代碼中，屬于適應(yīng)度高、階數(shù)低且長度短的圖式的編碼數(shù)量將隨代數(shù)以指數(shù)形式增長[6]。最近的研究則表明，上述遺傳算法經(jīng)適當(dāng)改進(jìn)后對任意優(yōu)化問題以概率1收斂于全局最優(yōu)解[5]。

2．2遺傳算法的基本結(jié)構(gòu)

在遺傳算法中，將問題的求解的過程，看成一個在候選解空間尋找滿足問題要求的解或近似解的搜索過程。遺傳算法的重點(diǎn)在適應(yīng)規(guī)劃和適應(yīng)度量方面。遺傳算法的適應(yīng)規(guī)劃用于指導(dǎo)算法怎么樣在空間進(jìn)行搜索，一般采用遺傳算子(或稱遺傳操作)諸如(Crossover)和變異(Mutation)等，以及模擬自然過程的選擇機(jī)制，采用計算適應(yīng)值的方法來評估一個候選解的優(yōu)劣。

遺傳算法求解問題的基本步驟可以描述如下：

1.首先生成一組初始的候選解群體(假設(shè)為N個候選解個體)，稱為第0代；

2.計算群體中各個候選解的適應(yīng)值；

3.如果有候選解滿足算法終止條件，算法終止，否則繼續(xù)4；

4.根據(jù)概率，將候選解群體中的個體隨機(jī)兩兩配對，進(jìn)行操作以生成新的候選解；

5.根據(jù)變異概率，對4中生成的候選解群中的每個個體進(jìn)行變異操作；

6.使用選擇機(jī)制形成新一代候選解；轉(zhuǎn)2。

GA算法具有下述特點(diǎn)：GA是對問題參數(shù)的編碼組進(jìn)行，而不是直接對參數(shù)本身；GA的搜索是從問題解的編碼組開始搜索，而不是從單個解開始；GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息；GA算法使用的選擇、交叉、變異這三個算子都是隨機(jī)操作，而不是確定規(guī)則。

遺傳算法通過編碼和遺傳操作，達(dá)到了處理的并行性，可以同時處理群體中的多個個體，即同時對搜索空間內(nèi)的多個解進(jìn)行評估，具有較好的全局搜索性能，減少了限于局部最優(yōu)解的風(fēng)險。

3.遺傳算法用于頻率分配

3．1算法的基本流程

采用遺傳算法的FAP基本流程如下圖：3．2遺傳算子的選擇

3．2．1選擇算子

選擇算子在父代群體中選出父體和母體。生物界中，父母親素質(zhì)比較高的其后代素質(zhì)高的概率也大。模擬這種現(xiàn)象，在FAP中選擇算子采用輪賭算法實現(xiàn)。

輪賭算法流程如下：

sum=0;i=0;

wheelpos=rand()*sumfitness;

for(sum<wheelpos&&i<pop-size)

｛

i++;

if(i≥pop-size)

｛

sum=0;i=0

wheelpos=rand()*sumfitness;

｝

j=rand()*pop-size;

sum+=fitness［j］;

｝

returnj;

3．2．2交叉算子

交叉算子讓父體和母體互相交換某部分基因而產(chǎn)生下一代個體的雛形，起全局搜索的作用。交叉算子通常有單點(diǎn)交叉、雙點(diǎn)交叉、多點(diǎn)交叉等等。在頻率自動分配的算法中，為了不破壞基因段內(nèi)部頻點(diǎn)間的關(guān)系，采用單點(diǎn)交叉和雙點(diǎn)交叉比較合適。此外，在生物界中并不是兩個個體相遇了就一定會結(jié)合，模擬此現(xiàn)象，引入交叉因子pc。

其基本流程如下：

//flip函數(shù)中，產(chǎn)生一個0到1的隨機(jī)數(shù)，若小于pc，則返回1，否則返回0

if(flip(pc))

crossover1(mother,father);

elseif(flip(pc))

crossover2(mother,father);

else

copy(mother);

copy(father);

3．2．3變異算子

變異算子對后代個體的某些基因進(jìn)行變異，起局部搜索的作用.生物界中，父母的染色體交叉后產(chǎn)生后代個體的染色體雛形，這個雛形在成長過程中會發(fā)生基因的變異，正是這種變異使得下一代的群體中會出現(xiàn)各種特征的個體.另外，生物界中并非每個基因都會變異，模擬此現(xiàn)象，引入變異因子pm，使用方法與交叉因子類似。

其基本流程如下：

while(allfrequentpoint)

{

if(flip(pm))mutate(frequentpoint)；}

4.工程上需要注意的問題

4．1初始候選種群

由于遺傳算法和其它啟發(fā)式算法一樣，不對全部解空間進(jìn)行窮舉搜索，因此初始的候選解群體的選擇會對得到最終解的速度和質(zhì)量有影響。初始的候選解群體在解空間內(nèi)分布得越均勻，它們擁有的遺傳基因就越有代表性。實踐中采用文獻(xiàn)[7]的GECP得到以各個頂點(diǎn)為主頂點(diǎn)的可行解作為初始候選種群。

4．2編碼方案

編碼就是用一種數(shù)字排列方案來表示問題的解的方法，利用編碼將問題的解空間映射到GA算法的編碼空間。編碼方案的選擇依賴于問題的性質(zhì)，并影響到算法內(nèi)操作的設(shè)計，是影響算法性能的重要因素。常見的編碼方案有二進(jìn)制編碼、十進(jìn)制編碼、實數(shù)編碼等。頻率分配問題適合采用十進(jìn)制編碼方案，每個碼表示一條通信鏈路，碼值表示分配的信道編號。

4．3適配值函數(shù)

適配值函數(shù)對個體（頻率分配方案）進(jìn)行評價，也是優(yōu)化過程發(fā)展的依據(jù)?？梢圆捎萌缦路绞絹碛嬎氵m應(yīng)度：

fitness=1000/Σ(pri×seperate(Freq))。

其中：

pri是節(jié)點(diǎn)的加權(quán)值；

函數(shù)seperate(Freq)是節(jié)點(diǎn)中各條鏈路發(fā)頻率同其它鏈路的收頻率間隔的和；

參考文獻(xiàn)：

[1]RobertA.Murphey,PanosM.Pardalosetc,FrequencyAssignmentProblems,Handbookofcombinatorialoptimization,KluwerAcademicPublishers,1999

[2]VittorioM.,AntonellaC.,AnANTSHeuristicfortheFrequencyAssignmentProblem,csr.unibo.it

[3]JoeBater,PeterJeavons,DavidCohen,ArethereoptimalreusedistanceconstraintsforFAPswithrandomTxplacement?,CSD-TR-98-01,CSRoyalHollowayUni.OfLondon,1998

[4]K.IAardal,C.A.J.Hurkens,J.K.etc.AlgorithmsforFreequencyAssignmentProblems,CWIQuarterly,Vol9(1&2),1996

[5]王凌：《智能優(yōu)化算法及其應(yīng)用》清華大學(xué)出版社2001

[6]陳國良等：《遺傳算法及其應(yīng)用》人民郵電出版社1996

[7]孫俊柏：禁用頻點(diǎn)、頻段下野戰(zhàn)通信網(wǎng)的頻率分配中國科學(xué)技術(shù)大學(xué)碩士學(xué)位論文1998

第8篇：遺傳算法論文范文

關(guān)鍵詞：鉆孔灌注樁;基坑支護(hù);遺傳算法;優(yōu)化設(shè)計

Abstract: The genetic algorithm is used for excavation of underground continuous retaining wall optimization design, by editing the automatic calculation program of underground continuous wall supporting structure parameters optimization. Algorithm of all constraints is requirements of related codes are given according to the foundation; through the project example and the results prove the validity of the optimization design method.

Key words: bored pile; foundation pit; genetic algorithm; optimization design

中圖分類號：U443.15+4文獻(xiàn)標(biāo)識碼：A文章編號：

深基坑支護(hù)結(jié)構(gòu)隨著城市化建設(shè)大量出現(xiàn)，同時支護(hù)選型和設(shè)計極為保守造成浪費(fèi)，如何選取合理設(shè)計基坑同時保障基坑及周圍環(huán)境安全前提下使工程造價最低是工程設(shè)計最關(guān)心的問題，所以深基坑支護(hù)結(jié)構(gòu)優(yōu)化設(shè)計具有顯著技術(shù)經(jīng)濟(jì)意義。

深基坑支護(hù)優(yōu)化設(shè)計設(shè)計參數(shù)復(fù)雜，目標(biāo)函數(shù)與設(shè)計參數(shù)之間的關(guān)系是復(fù)雜的非線性關(guān)系[1]，神經(jīng)網(wǎng)絡(luò)遺傳算法是具備智能性、全局優(yōu)化性和內(nèi)在學(xué)習(xí)性等特點(diǎn)一種優(yōu)化計算方法，可解決深基坑支護(hù)優(yōu)化設(shè)計的非線性關(guān)系。

1 遺傳算法基本原理

遺傳算法采用編碼的技術(shù)，效仿了生物物種由低級到高級的進(jìn)化過程，從初始種群開始，采取“優(yōu)勝劣汰，適者生存” 的自然法則對個體進(jìn)行選擇、、變異，進(jìn)而產(chǎn)生新一代種群，重復(fù)逐代演變進(jìn)化，直到產(chǎn)生出滿足條件要求的個體為止，它是基于種群的智能優(yōu)化法的一種。

遺傳算法具有智能性、全局優(yōu)化性和隱含并行性三個特點(diǎn)。遺傳算法具有智能算法中的自適應(yīng)、自組織和自學(xué)習(xí)等特點(diǎn)，由于交叉算子的作用，使得搜索方向集中在空間中期望值最高的部分，同時由于變異算子的作用，確保了群體的多樣性，防止了搜索被引導(dǎo)到局部最優(yōu)。遺傳算法具有潛在的并行性，由于搜索過程是同時從多個點(diǎn)出發(fā)，使得這種多智能體的協(xié)作過程是異步并發(fā)進(jìn)行的，同時搜索解空間內(nèi)的多個區(qū)域，相互交流信息，這種分布式并行模式大大提高整個算法的快速反應(yīng)能力和運(yùn)行效率。除此之外，遺傳算法還具有通用性、內(nèi)在學(xué)習(xí)性、多解性、非定向性等特點(diǎn)，這些特點(diǎn)使遺傳算法在實際的工程優(yōu)化中，得到了很大范圍的應(yīng)用。

遺傳算法常用步驟如下：①目標(biāo)函數(shù)確定；②根據(jù)約束條件生成解的初始成員種群；③譯碼染色體使其適合評價并給予適應(yīng)值；④以根據(jù)優(yōu)勝劣汰，去掉適應(yīng)值差的染色體，并按概率隨機(jī)選擇幸存的染色體進(jìn)行復(fù)制形成新的群體；⑤根據(jù)概率隨機(jī)選擇染色體進(jìn)行雜交和變異的操作；⑥對子代群體重復(fù)步驟③-⑤的操作，不斷進(jìn)行遺傳進(jìn)化，讓種群平均適應(yīng)值和最優(yōu)個體提高，直到適應(yīng)值趨于穩(wěn)定，即完成最優(yōu)參數(shù)。

2 數(shù)學(xué)模型的建立

某工程基坑支護(hù)采用鉆孔灌注樁，本文以三層鋼支撐形式為例進(jìn)行數(shù)學(xué)模型。

2.1優(yōu)化參數(shù)的選取

根據(jù)優(yōu)化參數(shù)的選取原則，將鉆孔灌注樁支護(hù)結(jié)構(gòu)[2]中的樁徑D、支撐位置m、嵌固深度hd、樁間距S作為優(yōu)化參數(shù)變量，而將混凝土強(qiáng)度等級、配筋方式、鋼筋等級、直徑和土層計算參數(shù)等變量均作為設(shè)計參量預(yù)先固定下來，則變量空間為：X=[hd,D,m1,m2,m3,S]T

hd ∈[0.5h , 1.5h] D ∈[0.6 ,1.2]S∈[0.5D , 2.5D]

m1∈[0.1h , h-hs′] m2∈[m1+hs, h-hs′ ]m3∈[m2+hs, h-hs′ ]

其中：hs′為最后一道支撐與基坑底的最小間距；hs為鋼支撐豎向的最小間距； S指的是兩個樁之間的中心距；h為基坑的開挖深度。將所求解空間X=[hd,D,m1, m2,m3,S]確定每個變量的精度后，利用二進(jìn)制編碼對所求變量的解空間進(jìn)行轉(zhuǎn)換，形成初始種群。

2.2約束條件處理

用構(gòu)造罰函數(shù)的方法處理約束條件，采用，：

若>0,;若≤0，則；而，定義為違反系數(shù)，則上述約束問題轉(zhuǎn)換成為了無約束問題，即：

式中：為原目標(biāo)函數(shù)，稱為懲罰后的目標(biāo)函數(shù)，參數(shù)為懲罰因子，根據(jù)對所求解可行性的要求嚴(yán)格程度而定。

2.3適應(yīng)度函數(shù)的確定

選取單位寬度的樁材料造價作為目標(biāo)函數(shù)，即：

式中：h為基坑開挖的深度 ，hd為樁的嵌固深度，D為樁徑，S為樁間距。

選取適應(yīng)度函數(shù)為：

式中：c為系數(shù)常量，用以調(diào)整適應(yīng)值的區(qū)間，通常取值為100-1000，顯然的值越大，該母體越優(yōu)。

2.4收斂判別

選擇下式作為收斂判別準(zhǔn)則： （是一個充分小正數(shù)），如果滿足了收斂判別，則輸出結(jié)果，否則重復(fù)計算。

優(yōu)化程序的實現(xiàn)是基于MATLAB語言，首先編寫遺傳算法的運(yùn)算函數(shù)，其中包括了編碼、適應(yīng)度評判、選擇、交叉、變異、解碼等運(yùn)算，函數(shù)調(diào)用了先前編制好的圍護(hù)結(jié)構(gòu)內(nèi)力和變形計算的函數(shù)，為了便于了變量的輸入輸出，利用生成界面的GUI函數(shù)，編寫了參量輸入界面、優(yōu)化運(yùn)行和結(jié)構(gòu)計算界面。

3 工程概況

浙江杭州市區(qū)某車站基坑工程[3]，基坑平均深度為14.6m，按照建筑基坑支護(hù)，本車站基坑支護(hù)工程安全等級為一級。綜合本站周邊環(huán)境、地質(zhì)條件和工程造價等，基坑主體圍護(hù)結(jié)構(gòu)采用鉆孔灌注樁，鉆孔樁選用循環(huán)鉆施工。本區(qū)間地下水埋深為1.3-2.8m，主要為上層滯水，地下水位不連續(xù)，水文地質(zhì)條件較簡單。

3.1 計算參數(shù)選取

鉆孔灌注樁采用為C30，樁徑1300m。圍護(hù)結(jié)構(gòu)的水平受力體系采用鋼管內(nèi)支撐方案，設(shè)三道內(nèi)支撐，采用Φ600，t=16的鋼管支撐，鋼管材料采用Q235鋼，結(jié)構(gòu)設(shè)計時應(yīng)根據(jù)結(jié)構(gòu)類型，按結(jié)構(gòu)整體和單個構(gòu)件可能出現(xiàn)的最不利情況進(jìn)行組合，依相應(yīng)的規(guī)范要求進(jìn)行計算，并考慮施工過程中荷載變化情況分階段計算 。各土、巖層物理力學(xué)指標(biāo)見表1。

表1 土、巖層物理力學(xué)指標(biāo)

3.2 優(yōu)化結(jié)果與分析

通過程序自動計算，優(yōu)化結(jié)果表明，圍護(hù)樁的嵌固深度和樁間距的對改變，對設(shè)計結(jié)果具有較為大的影響，在樁徑不變的情況下，嵌固深度的變小和樁間距的增大，都會使得圍護(hù)結(jié)構(gòu)的上部水平位移和彎矩有所增大，但通過改變支撐的位置和支撐的預(yù)加軸力，可以保證圍護(hù)結(jié)構(gòu)的位移滿足規(guī)范要求的允許值，優(yōu)化結(jié)果顯示：墻體的最大彎矩比原設(shè)計增加了14.4%，墻體的最大剪力增加了19.2%，但都在設(shè)計允許值之內(nèi)。而造價比原設(shè)計降低了17.4%，因此優(yōu)化結(jié)果是比較理想的。根據(jù)優(yōu)化后的支護(hù)結(jié)構(gòu)參數(shù)計算所得圍護(hù)結(jié)構(gòu)變形和受力優(yōu)化結(jié)果對比見表2：

表2 優(yōu)化結(jié)果對比表

4 結(jié)語

通過工程實例證明遺傳算法能夠?qū)又ёo(hù)進(jìn)行優(yōu)化設(shè)計，具有經(jīng)濟(jì)效益，自動化計算程序在工程實踐中更具有應(yīng)用價值。

參考文獻(xiàn)

[1]李云安.深基坑工程變形控制優(yōu)化設(shè)計及其有限元數(shù)值模擬系統(tǒng)研究:博士學(xué)位論文[A].武漢:中國地質(zhì)大學(xué),2000.

[2]劉建航,侯學(xué)淵主編.基坑工程手冊[M].北京:中國建筑工業(yè)出社,1997.75~321.

第9篇：遺傳算法論文范文

【關(guān)鍵詞】適應(yīng)度 反垃圾郵件 數(shù)據(jù)挖掘

【中圖分類號】TP3【文獻(xiàn)標(biāo)識碼】A【文章編號】1672-5158（2013）02-0163-02

該遺傳算法生成的模型建立在解決垃圾郵件的數(shù)據(jù)分析的新方法基礎(chǔ)上。在模型的決策樹上，每個結(jié)點(diǎn)數(shù)據(jù)被設(shè)計成擁有一個隨機(jī)系數(shù)，這樣的話，數(shù)據(jù)與系數(shù)相乘成為判斷該項數(shù)據(jù)記錄是否代表郵件合法的確定性權(quán)重。這里的系數(shù)基于Ephemeral Random Constants（ERC），是特定于數(shù)學(xué)建模的遺傳算法生成的隨機(jī)數(shù)。該系數(shù)的微小變化也會導(dǎo)致進(jìn)化變異產(chǎn)生。

此系統(tǒng)中，之所以要選取特征子集，是考慮到特征子集的選取是在反垃圾郵件中提高機(jī)器學(xué)習(xí)算法性能的可行辦法。特征子集的選取能提高學(xué)習(xí)算法的準(zhǔn)確度，減少計算量，同時可以減少測試數(shù)據(jù)量，降低分類過程中的消耗等。進(jìn)行特征子集選取，最重要的目標(biāo)就是提高郵件檢測的準(zhǔn)確率，減少分類運(yùn)算等過程中的數(shù)據(jù)量。

在系統(tǒng)調(diào)用序列數(shù)據(jù)的挖掘過程中，使用特征向量法，用特征向量的一位標(biāo)識一個短序列，用挖掘算法就能從特征向量集中找出垃圾郵件的規(guī)則來。然而，由于短序列的數(shù)量較大，導(dǎo)致特征向量位數(shù)過大，特征向量集也相應(yīng)過大。為了更高效可行地使用數(shù)據(jù)挖掘算法，采用遺傳算法對特征向量集進(jìn)行優(yōu)化，尋找特征子集，利于后續(xù)的數(shù)據(jù)挖掘。

在使用遺傳算法的過程中，用特征向量的位數(shù)決定其個體的大小，隨機(jī)構(gòu)造50個二進(jìn)制位串的個體，其中“0”、“1”代表該位置的短序列是否入選特征子集，如圖2所示。在此基礎(chǔ)上，進(jìn)行遺傳得到最優(yōu)個體，該最優(yōu)個體必然是“0”、“1”交替的位串，將其所有“1”所在位置進(jìn)行分析，可以得到“1”所在位置代表的短序列集，這就是要尋找的特征子集。后續(xù)挖掘算法根據(jù)該特征子集中的短序列，對訓(xùn)練數(shù)據(jù)進(jìn)行分類等挖掘工作。（如圖2）

采用標(biāo)準(zhǔn)交叉算子和變異算子，交叉概率取0.6，變異概率取0.001。遺傳過程中，個體的選擇比較復(fù)雜。因為這里是針對垃圾郵件檢測進(jìn)行的優(yōu)化，所以在選擇個體時，是將該個體代表的入選子集的短序列應(yīng)用到數(shù)據(jù)分類算法（RIPPER），該算法訓(xùn)練數(shù)據(jù)并應(yīng)用規(guī)則得到測試數(shù)據(jù)，根據(jù)檢測的性能來確定上述要選擇的個體的適應(yīng)度值。根據(jù)個體的適應(yīng)度值就可以對其進(jìn)行選擇，繼續(xù)遺傳優(yōu)化工作。

研究表明，個體的適應(yīng)值可以取決于有垃圾郵件被正確檢測到和有正常郵件被誤判為攻擊，同時考慮個體中置“1”位的數(shù)目。本系統(tǒng)設(shè)計的適應(yīng)度函數(shù)為：F（Xi）=（a/A-b/B）/（δ*m）；Xi表示某個個體，（a/A-b/B）的含意正如前述，m是Xi中“1”的個數(shù)，δ是m對于該適應(yīng)度函數(shù)的相關(guān)系數(shù)。也就是說，a/A是檢出率，b/B是誤報率，高檢出率低誤報率使適應(yīng)度函數(shù)值高，低檢出率高誤報率使適應(yīng)度函數(shù)值低。個體中置“1”的位數(shù)越少，適應(yīng)度值越大，當(dāng)然這是出于尋找最小特征子集的考慮，其影響的強(qiáng)弱，用相關(guān)系數(shù)δ去控制。

本系統(tǒng)采用的遺傳算法的基本步驟如下：

1.設(shè)定進(jìn)化代數(shù)g=0，生成包含n個個體的初始化群體P（g）；

2.在該群體中對每個個體估值，計算各自適應(yīng)度f（x）；

3.通過如下步驟，生成新的群體P（g+1）：

A.根據(jù)個體適應(yīng)度f（x），從P（g）中選擇兩個個體作為父代；（適應(yīng)度值越大，選中的機(jī)會越大）；

參考文獻(xiàn)

[1] Richard Blum，開放源碼郵件系統(tǒng)安全，人民郵電出版社，2002年11月