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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

1.引言

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

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

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

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

2.否定選擇算子

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

3.遺傳選擇算子

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

下面舉例說(shuō)明基本方法。對(duì)于一個(gè)給定的優(yōu)化問(wèn)題，設(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ù)值，也可以是符號(hào)；F為實(shí)數(shù)，是解的優(yōu)劣程度或適應(yīng)度的一種度量；f 為解空間(x,y,z) 到實(shí)數(shù)域FR的一種映射，那么遺傳算法的求解步驟如下:

（1）編碼

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

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

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

（3）評(píng)價(jià)

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

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

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

（5）交叉

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

x=x1x2x3x4x5[00011]

y=y1y2y3y4y5[11100]

x’=x1x2x3x4x5[00000]

y’=y1y2y3y4y5[11100]

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

（6）變異

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

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

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

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

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

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

結(jié)束語(yǔ)

由于遺傳算法的特點(diǎn)，靜態(tài)克隆選擇算法產(chǎn)生的檢測(cè)器有可能是無(wú)效檢測(cè)器，所以本文提出了一種多層動(dòng)態(tài)克隆選擇算法，對(duì)每次動(dòng)態(tài)克隆的新檢測(cè)器再次檢測(cè)，判斷其有效性，從而過(guò)濾掉無(wú)效低檢測(cè)器但是本算法也增加了算法的復(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è)計(jì)

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

0 引言

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

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

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

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

(1.1)

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

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

――第j號(hào)柱的造價(jià)，包括柱的混凝土成本、縱筋成本、箍筋成本、模板成本；

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

1.2 約束條件

1）梁最大配筋率約束

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

(1.2)

(1.3)

(1.4)

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

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

2）梁最小截面約束

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

(1.5)

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

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

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

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

(1.6)

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

(1.7)

3）梁撓度約束

(1.8)

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

[f ] ――梁撓度限制。

4）梁截面高寬比約束

(1.9)

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

5）柱最大配筋率約束

(1.10)

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

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

6）柱最小截面約束

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

(1.11)

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

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

(1.12)

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

(1.13)

7）柱軸壓比約束

(1.14)

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

8）柱截面高寬比約束

以h方向截面高寬為例

(1.15)

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

9）樓層混凝土等級(jí)約束：

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

(1.16)

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

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為離散空間。

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

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

(2.1)

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

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

(2.2)

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

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

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

(2.3)

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

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

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

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

當(dāng)交叉的隨機(jī)判定數(shù)RND小于Pc時(shí)，個(gè)體和需要進(jìn)行染色體交叉計(jì)算生成新的子代染色體，否則兩者直接遺傳到子代中，見(jià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ù)需要變異個(gè)體的適應(yīng)值計(jì)算自適應(yīng)的變異概率。假設(shè)個(gè)體需要進(jìn)行變異計(jì)算，其確定自適應(yīng)變異概率的公式為式2.6：

(2.6)

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

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

當(dāng)交叉的隨機(jī)判定數(shù)RND小于P m時(shí)，根據(jù)式2.7對(duì)基因進(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）個(gè)體，然后選擇其中最佳個(gè)體進(jìn)入下一代種群。重復(fù)操作，直到新的種群規(guī)模達(dá)到原來(lái)的種群規(guī)模。

3算例分析

3.1工程概況

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

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

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

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

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

①識(shí)別模型

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

③生成初始種群

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

⑤評(píng)估新種群

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

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

中圖分類號(hào)：TP311.52

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

1 遺傳算法的基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 組卷管理模塊

（1）自動(dòng)組卷。自動(dòng)組卷生成如圖1所示：

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

中圖分類號(hào):TP18文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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

分類問(wèn)題是集成學(xué)習(xí)的基本研究問(wèn)題,即對(duì)一個(gè)分類器輸入一個(gè)實(shí)例的特征集,然后對(duì)這些特征進(jìn)行判斷,對(duì)這個(gè)樣本進(jìn)行歸類并輸出。在醫(yī)療診斷、語(yǔ)音識(shí)別、數(shù)據(jù)挖掘、人像識(shí)別等領(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)化過(guò)程。遺傳算法通過(guò)有組織的然而是隨機(jī)的信息交換來(lái)重新組合那些適應(yīng)性好的串,在每一代中,利用上一代串結(jié)構(gòu)中適應(yīng)性好的位和串來(lái)生成一個(gè)新的串的群體。這是一類隨機(jī)算法,但不是簡(jiǎn)單地隨機(jī)走動(dòng),而是利用已有的信息來(lái)搜尋那些有希望改善質(zhì)量的串,這個(gè)過(guò)程類似于自然進(jìn)化。[2]

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

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

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

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

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

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

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

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

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

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

1) 編碼表示

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

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

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

3) 選擇策略

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

4) 遺傳算子

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

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

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

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

5) 終止規(guī)則

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

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

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

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

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

在文獻(xiàn)[4]中,使用遺傳算法對(duì)基于C5.0和神經(jīng)網(wǎng)絡(luò)的規(guī)則集進(jìn)行優(yōu)化。優(yōu)化后,得到兩套規(guī)則集,基于C5.0的規(guī)則集邊界值發(fā)生改變,新的規(guī)則在精度上比原來(lái)更高。而基于神經(jīng)網(wǎng)絡(luò)的規(guī)則集在形式上沒(méi)有發(fā)生改變。對(duì)兩種規(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ī)則集,而遺傳算法通過(guò)優(yōu)化規(guī)則條件的部分邊界值提高了分類的精度。這種方法具有較好的魯棒性和可延展性,當(dāng)給定的邊界值與其正確的位置相距很遠(yuǎn),也可通過(guò)遺傳算法對(duì)全局進(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冊(cè).北京:科學(xué)出版社,1995.

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

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

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

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

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

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

1　單親演化過(guò)程

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

1.1　tsp編碼表示

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

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

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

對(duì)n個(gè)編號(hào)為1,2,…,n的城市,根據(jù)它們的坐標(biāo)計(jì)算各城市之間的歐氏距離d(i,j),i,j=1,2,…,n,得到一個(gè)n*n的方陣d={ d(i,j)}。然后利用普里姆算法求得該tsp的一棵mst,并將這棵mst中的每一條邊e(i,j)對(duì)應(yīng)地存儲(chǔ)在一個(gè)n*(n-1)的方陣m={ e(i,j)},即該文的基因庫(kù)。由于一個(gè)tsp可能有多棵mst,操作可以重復(fù)多次,這樣生成的基因庫(kù)中的基因就更多,增強(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)勝劣汰的遺傳特性,在單個(gè)染色體內(nèi)以基因重組的方式,使子代在滿足tsp問(wèn)題的限定條件下進(jìn)行繁衍,然后保留適應(yīng)度高的染色體種群,達(dá)到優(yōu)化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯(cuò)位和基因段倒轉(zhuǎn)三種操作來(lái)實(shí)現(xiàn)?；驌Q位操作是將親代的染色體基因進(jìn)行對(duì)換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式?；蚨五e(cuò)位操作是隨機(jī)確定基因段,也隨機(jī)選定錯(cuò)位位置,整段錯(cuò)移?；蚨蔚罐D(zhuǎn)操作則是隨機(jī)地確定倒轉(zhuǎn)基因段的起止位置,倒轉(zhuǎn)操作是對(duì)該段內(nèi)基因按中垂線作鏡面反射,若段內(nèi)基因數(shù)為奇數(shù)時(shí),則中位基因不變。單親演化時(shí)可以是單個(gè)操作用于單個(gè)父代,也可以是幾種操作同時(shí)采用。為了編程方便,文中采用基因段倒轉(zhuǎn)操作。

2　群體演化過(guò)程

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

2.1　交叉算子

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

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

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

m1=(7654|123456789)

m2=(3456|987654321)

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

s1=(765412389)　s2=(345698721)

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

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

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

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

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

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

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

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

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

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

3　實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

2.遺傳算法在頻率分配問(wèn)題中的適用性

2．1遺傳算法的原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3．1算法的基本流程

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

3．2．1選擇算子

選擇算子在父代群體中選出父體和母體。生物界中，父母親素質(zhì)比較高的其后代素質(zhì)高的概率也大。模擬這種現(xiàn)象，在FAP中選擇算子采用輪賭算法實(shí)現(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)生下一代個(gè)體的雛形，起全局搜索的作用。交叉算子通常有單點(diǎn)交叉、雙點(diǎn)交叉、多點(diǎn)交叉等等。在頻率自動(dòng)分配的算法中，為了不破壞基因段內(nèi)部頻點(diǎn)間的關(guān)系，采用單點(diǎn)交叉和雙點(diǎn)交叉比較合適。此外，在生物界中并不是兩個(gè)個(gè)體相遇了就一定會(huì)結(jié)合，模擬此現(xiàn)象，引入交叉因子pc。

其基本流程如下：

//flip函數(shù)中，產(chǎn)生一個(gè)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變異算子

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

其基本流程如下：

while(allfrequentpoint)

{

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

4.工程上需要注意的問(wèn)題

4．1初始候選種群

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

4．2編碼方案

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

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

適配值函數(shù)對(duì)個(gè)體（頻率分配方案）進(jìn)行評(píng)價(jià)，也是優(yōu)化過(guò)程發(fā)展的依據(jù)?？梢圆捎萌缦路绞絹?lái)計(jì)算適應(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]陳國(guó)良等：《遺傳算法及其應(yīng)用》人民郵電出版社1996

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

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

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

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

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

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

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

1 遺傳算法基本原理

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

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

遺傳算法常用步驟如下：①目標(biāo)函數(shù)確定；②根據(jù)約束條件生成解的初始成員種群；③譯碼染色體使其適合評(píng)價(jià)并給予適應(yīng)值；④以根據(jù)優(yōu)勝劣汰，去掉適應(yīng)值差的染色體，并按概率隨機(jī)選擇幸存的染色體進(jìn)行復(fù)制形成新的群體；⑤根據(jù)概率隨機(jī)選擇染色體進(jìn)行雜交和變異的操作；⑥對(duì)子代群體重復(fù)步驟③-⑤的操作，不斷進(jìn)行遺傳進(jìn)化，讓種群平均適應(yīng)值和最優(yōu)個(gè)體提高，直到適應(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)度等級(jí)、配筋方式、鋼筋等級(jí)、直徑和土層計(jì)算參數(shù)等變量均作為設(shè)計(jì)參量預(yù)先固定下來(lái)，則變量空間為：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指的是兩個(gè)樁之間的中心距；h為基坑的開(kāi)挖深度。將所求解空間X=[hd,D,m1, m2,m3,S]確定每個(gè)變量的精度后，利用二進(jìn)制編碼對(duì)所求變量的解空間進(jìn)行轉(zhuǎn)換，形成初始種群。

2.2約束條件處理

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

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

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

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

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

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

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

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

2.4收斂判別

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

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

3 工程概況

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

3.1 計(jì)算參數(shù)選取

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

2.在該群體中對(duì)每個(gè)個(gè)體估值，計(jì)算各自適應(yīng)度f(wàn)（x）；

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

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

參考文獻(xiàn)

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