遺傳算法論文范文

導(dǎo)語(yǔ)：如何才能寫(xiě)好一篇遺傳算法論文，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。

篇1

論文摘要：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)能力。

論文關(guān)鍵詞：旅行商問(wèn)題遺傳算法基因庫(kù)多重搜索策略

TSP(travelingsalesmanproblem)可以簡(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]。遺傳算法主要包括選擇、交叉和變異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-FaTsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來(lái)求解TSP問(wèn)題。該文根據(jù)文[7]中最小生成樹(shù)MST(minimumcostspanningtree)的應(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.1TSP編碼表示

設(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)了初始群體的全局性。具體算法如下:

VoidMiniSpanTree—PRIM(MGraphG,VertexTypeu){

Struct{

VertexTypeadjvex;

VRTypelowcost;

}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)。基因換位操作是將親代的染色體基因進(jìn)行對(duì)換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式。基因段錯(cuò)位操作是隨機(jī)確定基因段,也隨機(jī)選定錯(cuò)位位置,整段錯(cuò)移。基因段倒轉(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(ordercrossover)法類似的交叉方法[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-FaTsai提出的多重搜索策略[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(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都進(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í)兼顧了算法的效率。

4結(jié)束語(yǔ)

篇2

【關(guān)鍵詞】自動(dòng)導(dǎo)航小車；路徑規(guī)劃；免疫遺傳算法；疫苗

1、引言

目前，為使移動(dòng)機(jī)器人規(guī)劃出良好的去去路徑，所用的方法很多，如柵格法[1]、勢(shì)場(chǎng)法[2]、可視圖法[3]等。但各種方法有其使用局限。人工智能的發(fā)展為AGV的路徑規(guī)劃提供了新思路，產(chǎn)生了諸如神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)法、遺傳算法等方法。這些算法在一定程度上解決了AGV的路徑規(guī)劃問(wèn)題，但也有其缺陷。如神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)法對(duì)于復(fù)雜環(huán)境難以數(shù)學(xué)建模，范化能力差；模糊法靈活性差。遺傳算法在迭代過(guò)程中，個(gè)體在進(jìn)化過(guò)程中不可避免地會(huì)產(chǎn)生退化。受生物免疫系統(tǒng)的啟發(fā)，論文將免疫引入到遺傳算法中，在保留遺傳算法優(yōu)點(diǎn)的情況下，利用待求問(wèn)題的一些特征信息，采用免疫方法所具有的識(shí)別、記憶等功能來(lái)抑制遺傳算法在進(jìn)化中所出現(xiàn)的退化現(xiàn)象。本文所設(shè)計(jì)的基于免疫遺傳算法的AGV路徑規(guī)劃方法利用AGV在移動(dòng)過(guò)程中的特殊信息對(duì)所選路徑進(jìn)行優(yōu)化，可較快地使AGV根據(jù)環(huán)境信息搜索一種滿意的路徑，提高了AGV路徑規(guī)劃的智能性。

2、環(huán)境信息建模

對(duì)AGV進(jìn)行路徑規(guī)劃前，應(yīng)解決對(duì)其環(huán)境信息的描述即環(huán)境建模問(wèn)題。為此，作以下假設(shè)[3]：

（1）AGV在二維平面中運(yùn)動(dòng)，不考慮其高度方向的信息；（2）規(guī)劃環(huán)境的邊界及其內(nèi)所有障礙物（妨礙AGV運(yùn)動(dòng)的所有物體）用凸多邊形表示。（3）考慮到AGV的大小等，對(duì)環(huán)境邊界進(jìn)行縮小和對(duì)障礙物進(jìn)行擴(kuò)大時(shí)，其縮放量為AGV外形最大尺寸的一半。即AGV為“點(diǎn)機(jī)器人”。

至此，AGV的工作空間可描述為：工作平面和障礙物群{Oi|i=1，2…N}。具體到其個(gè)障礙物Oi，可描述為Oi={頂點(diǎn)1坐標(biāo)（xi1， yi1），….. 頂點(diǎn)n坐標(biāo)（xni， yni）}。為方便數(shù)據(jù)處理，對(duì)多邊形頂點(diǎn)沿順時(shí)針?lè)较蚓幪?hào)。起點(diǎn)為S，終點(diǎn)為E。工作平面可表示為矩形{（Xmin，Ymin），（Xmax，Ymax）}。

設(shè)在AGV的工作環(huán)境中有n個(gè)已知的障礙物Oi（i=1，2，...，n），對(duì)應(yīng)的頂點(diǎn)數(shù)為Si，頂點(diǎn)坐標(biāo)為（x（i，j），y（i，j））（j=1，2，…Si）。為描述AGV工作環(huán)境中的障礙物，采用Dm×m矩陣對(duì)環(huán)境信息進(jìn)行描述，其中，m為障礙物頂點(diǎn)總數(shù)。定義d（i，j）為：

3、免疫遺傳算法設(shè)計(jì)

3.1路徑編碼方式

采用免疫遺傳算法求解最優(yōu)問(wèn)題的關(guān)鍵是對(duì)所求問(wèn)題的解進(jìn)行編碼。編碼的長(zhǎng)度與搜索空間的大小及求解精度有直接關(guān)系，也影響算法的效率。對(duì)AGV進(jìn)行路徑規(guī)劃時(shí)，傳統(tǒng)的二進(jìn)制或?qū)崝?shù)編碼方式都不適用。本文設(shè)計(jì)了一種自適應(yīng)變長(zhǎng)度實(shí)數(shù)數(shù)組編碼方式，即第p代Xp的第k條染色體Xkp的第j位基因Xkp（j）表示為Xkp（j）=|io，xk，yk|T，其中io為障礙物序號(hào)，（xk，yk|）為第io號(hào)障礙物的某頂點(diǎn)坐標(biāo)。由于路徑的起點(diǎn)為AGV的起始點(diǎn)，終點(diǎn)為其目標(biāo)點(diǎn)，在路徑規(guī)劃時(shí)可省去以縮短染色體的長(zhǎng)度。定義，AGV的可能運(yùn)動(dòng)路徑由數(shù)條直線段組成，相鄰兩直線段的交點(diǎn)稱為AGV的路徑拐點(diǎn)。為使AGV不穿越障礙物運(yùn)動(dòng)，基于對(duì)工作規(guī)劃空間建模時(shí)所作的假設(shè)，AGV可沿多邊形障礙物的邊界線移動(dòng)，也可以障礙物的頂點(diǎn)為拐點(diǎn)在自由空間中移動(dòng)。染色體即AGV的某行路徑Xkp為Xkp={Xkp（1）， Xkp（2），…， Xkp（nkp）}，其中nkp為第p代中第k條染色體的長(zhǎng)度，每代中各條染色體長(zhǎng)度不同。

3.2適應(yīng)度函數(shù)

在對(duì)AGV進(jìn)行路徑規(guī)劃時(shí)，其優(yōu)化目標(biāo)為在所有可能的運(yùn)動(dòng)路徑Xp={Xkp|k=1， 2，…，N}中找出一條最優(yōu)或次優(yōu)路徑。設(shè)某個(gè)體Xkp的路徑長(zhǎng)度Dk為：

其中dj為Xk中各直線段軌跡長(zhǎng)。因?yàn)锳GV由一直線軌跡向另一直線軌跡過(guò)渡時(shí)運(yùn)動(dòng)速度的變化會(huì)影響其運(yùn)行時(shí)間，因此，在對(duì)所選路徑進(jìn)行評(píng)價(jià)時(shí)，除考慮其總長(zhǎng)度外，可要求路徑中的拐點(diǎn)數(shù)盡可能的少或AGV的姿態(tài)角變化量盡要能的小。本論文的路徑規(guī)劃目標(biāo)是路徑短且拐點(diǎn)較少。定義適應(yīng)度函數(shù)為：

式中，和為調(diào)整系數(shù)。這里取=0.8，=0.2。N為種群大小，Dj為種群中第j個(gè)體的路徑長(zhǎng)度，nj為第j個(gè)體路徑拐點(diǎn)數(shù)。

3.3算法的實(shí)現(xiàn)

在進(jìn)行路徑規(guī)劃時(shí)，首先判斷AGV從起點(diǎn)向終點(diǎn)沿直線軌跡運(yùn)動(dòng)時(shí)是否穿越障礙物。若無(wú)障礙物，兩點(diǎn)間的連線為AGV的最佳運(yùn)動(dòng)路徑，無(wú)須進(jìn)行路徑規(guī)劃。否則進(jìn)行路徑規(guī)劃。

免疫遺傳算法中，疫苗是根據(jù)待求問(wèn)題的先驗(yàn)知識(shí)構(gòu)造的最佳個(gè)體基因的估計(jì)，抗體是根據(jù)疫苗將某個(gè)體基因進(jìn)行修正后所得到的新個(gè)體。論文所設(shè)計(jì)的基于免疫遺傳算法的路徑規(guī)劃過(guò)程如下：

（1）根據(jù)問(wèn)題從記憶抗體庫(kù)中提取問(wèn)題的抗體P得到初始種群 ，不足N個(gè)時(shí)在AGV起始點(diǎn)和目標(biāo)點(diǎn)之間隨機(jī)產(chǎn)生N-P條路徑。個(gè)體的產(chǎn)生方法是：以包圍AGV的起點(diǎn)、終點(diǎn)和所有在線障礙物的最小矩形為規(guī)劃區(qū)域，在規(guī)劃區(qū)域內(nèi)的障礙物頂點(diǎn)個(gè)數(shù)為M，在線障礙物為m，則染色體的最大長(zhǎng)度為M-m。以規(guī)劃區(qū)域內(nèi)的障礙物頂點(diǎn)為被選對(duì)象，沿一定的條件隨機(jī)選取基因位上的基因組成一條染色體，同用樣的方法產(chǎn)生其它染色體以組成群體。

（2）根據(jù)先驗(yàn)知識(shí)抽取疫苗H={h1， h2， …， hm}；

（3）計(jì)算第p代種群Ak所有個(gè)體的適應(yīng)度，并進(jìn)行終止進(jìn)化判斷。

（4）對(duì)當(dāng)前群體Xp進(jìn)行遺傳算子操作得到子代群體Bp。進(jìn)行交叉操作時(shí)，采用單點(diǎn)交叉。交叉操作時(shí)，兩個(gè)個(gè)體若有相同的基因（而非等位基因）進(jìn)行交叉操作。當(dāng)相同基因位不止一個(gè)，隨機(jī)選擇其一進(jìn)行交叉；當(dāng)無(wú)相同基因位則不進(jìn)行交叉。進(jìn)行變異操作時(shí)，從個(gè)體中隨機(jī)刪除一基因位或隨機(jī)選取一基因位插入一新基因位，或在個(gè)體中隨機(jī)選取一基因位用另一隨機(jī)產(chǎn)生的基因位交換。

（5）對(duì)子代Bp進(jìn)行免疫操作，得到新代Xp+1；接種疫苗和免疫選擇是免疫算法的主要操作，接種疫苗是為了提高個(gè)體的適應(yīng)度，免疫選擇是為了防止個(gè)體的退化。接種疫苗即從Bp中按比例K隨機(jī)抽取Nk=KN個(gè)個(gè)體Bip（i=1，2，…，Nk），并按先驗(yàn)知識(shí)修改Bip（這時(shí)就變?yōu)榭贵w），使其以較大的概率具有更高的適應(yīng)度。接種疫苗時(shí)，若Bip已經(jīng)是最佳個(gè)體，則其以概率1轉(zhuǎn)移為Bip。對(duì)路徑規(guī)劃，接種疫苗就是對(duì)所選個(gè)體進(jìn)行判斷：首先，相鄰兩點(diǎn)間能否使AGV無(wú)障礙的沿直線運(yùn)動(dòng)；其次，任意兩點(diǎn)間能否使AGV無(wú)障礙的沿直線運(yùn)動(dòng)？條件滿足，則刪除中間點(diǎn)。免疫選擇分兩步完成：免疫檢測(cè)和退火選擇。免疫檢測(cè)即對(duì)抗體進(jìn)行檢測(cè)，若出現(xiàn)適應(yīng)度下降，此時(shí)由父代個(gè)體代替其參加競(jìng)選，退火選擇即以概率P（Bip）在當(dāng)前子代中進(jìn)行選擇：

其中，為適應(yīng)度函數(shù)；Tk是單調(diào)遞減趨于0的退火溫度控制序列，Tk=ln（T0/k+1），T0=100，p是進(jìn)化代數(shù)[3]。

（6）選擇個(gè)體進(jìn)入新的群體。更新抗體庫(kù)，并轉(zhuǎn)到第（3）步。

4、仿真實(shí)驗(yàn)

仿真是在Matlab6.1上進(jìn)行的。AGV的工作環(huán)境大小為8×6m2，其內(nèi)有6個(gè)形狀各異、排列任意的障礙物（如圖2所示），現(xiàn)欲使AGV從S點(diǎn)無(wú)碰撞地運(yùn)動(dòng)到E點(diǎn)且使其運(yùn)動(dòng)路徑最短，建立如圖4所示的可視圖。其可視矩陣如左圖：

論文采用所設(shè)計(jì)的路徑規(guī)劃方法和現(xiàn)有的遺傳和免疫算法對(duì)AGV進(jìn)行路徑規(guī)劃以尋找最佳路徑。取遺傳操作中的交叉概率Pc=0.8，變異概率Pm=0.2，免疫操作中的接種疫苗概率Pv=0.6，初始種群大小為N=20，抗體庫(kù)M=5，遺傳代數(shù)不超過(guò)K=200。圖3為路徑規(guī)劃的最佳路徑。進(jìn)化過(guò)程中適應(yīng)度變化和路徑長(zhǎng)度變化如圖4所示。

由仿真結(jié)果知，采用免疫遺傳算法進(jìn)行路徑規(guī)劃時(shí)，退化現(xiàn)象基本不會(huì)發(fā)生，再能很快得到問(wèn)題的最優(yōu)解。其原因是，利用免疫遺傳算法對(duì)AGV進(jìn)行路徑規(guī)劃，一方面利用了遺傳算法的優(yōu)點(diǎn)，由于是對(duì)編碼進(jìn)行操作，對(duì)問(wèn)題的依賴性小，且操作是并行進(jìn)行，優(yōu)化速度快；同時(shí)針對(duì)遺傳算在進(jìn)行交叉和變異操作時(shí)是以以概率方式隨機(jī)地、缺泛指導(dǎo)性地進(jìn)行導(dǎo)致問(wèn)題進(jìn)化時(shí)產(chǎn)生退化的現(xiàn)象，采用適當(dāng)?shù)闹笇?dǎo)，彌補(bǔ)了遺傳算法的缺點(diǎn)。利用遺傳免疫算法進(jìn)行優(yōu)化，在保證算法收斂的前提下，有效地提高計(jì)算速度。利用此法對(duì)AGV的路徑進(jìn)行規(guī)劃，比其它的方法更有效。

5、結(jié)論

論文主要針對(duì)環(huán)境建模和路徑搜索兩大問(wèn)題進(jìn)行了研究。基于可視圖環(huán)境建模方法優(yōu)點(diǎn)，完成了對(duì)環(huán)境信息的建模。并結(jié)合遺傳和免疫算法的優(yōu)點(diǎn)設(shè)計(jì)了具有精英保留策略的基于免疫遺傳算法的AGV路徑規(guī)劃方法。通過(guò)比較采用遺傳算法、免疫算法和本論文所設(shè)計(jì)的免疫遺傳算法對(duì)AGV進(jìn)行路徑規(guī)劃結(jié)果和效率的比較，分析了所提出的基于免疫遺傳算法的AGV路徑規(guī)劃方法的優(yōu)點(diǎn)。仿真結(jié)果表明：

A.本論文采用改進(jìn)的可視圖法對(duì)環(huán)境信息進(jìn)行建模，在改變障礙物位置、形狀、大小和AGV的起點(diǎn)及終點(diǎn)的情況下，均可快速構(gòu)建AGV的環(huán)境信息模型。

B.采用本論文所設(shè)計(jì)的基于免疫遺傳算法的AGV路徑規(guī)劃方法對(duì)AGV進(jìn)行路徑規(guī)劃，在速度方面優(yōu)于傳統(tǒng)的免疫算法和遺傳算法，且系統(tǒng)退化現(xiàn)象基本得到消除。

參考文獻(xiàn)

[1]吳鋒，楊宜民.一種基于柵格模型的機(jī)器人路徑規(guī)劃算法[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2012，4（3），7-9，13.

[2]沈鳳梅，吳隆.基于改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人自主導(dǎo)航和避障研究[J].制造業(yè)自動(dòng)化，2013，35 （12），28-30，39.

[3]李善壽，方潛生，肖本賢.全局路徑規(guī)劃中基于改進(jìn)可視圖法的環(huán)境建模[J].華東交通大學(xué)學(xué)報(bào)，2008，25（6），73-77.

作者簡(jiǎn)介

篇3

關(guān)鍵詞：遺傳算法；肝臟CT圖像；圖像分割；閾值

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)04-0864-02

Research on Liver CT Image Segmentation Based on Genetic Algorithm

KONG Xiao-rong1, SHI Yan-xin2, LIU Peng1

(1.Department of Computer Technology，Inner Mongolia Medical College, Huhhot 010059; 2.Department of Mathematics and Physics, Xi'an Technology University, Xi'an 710032, China)

Abstract: Genetic Algorithm (GA) is a global optimization and random search algorithm based on natural selection and genetic mechanism. It is suited to dealing with the tradition searching algorithms which cannot solve difficult and complicated problem. And it have great potentialities. First, this paper discusses fundamental principle and primary features of Genetic Algorithm. And it emphases on image segmentation based on GA. Then applying genetic algorithm to select theproper threshold, and it uses maximum entropy method to process liver CT images by segmentation methods. It obtains the results by segmentation experimentation and analyses the results.

Key words: genetic algorithm; liver CT images; image segmentation; threshold value

遺傳算法(Genetic Algorithm, GA)的基本思想來(lái)源于Darwin的生物進(jìn)化論和Mendel的群體遺傳學(xué)，該算法最早是由美國(guó)Michigan大學(xué)的John Holland教授于20世紀(jì)70年代創(chuàng)建，之后，遺傳算法的研究引起了國(guó)際組織及學(xué)者的關(guān)注。遺傳算法通過(guò)模擬生物的遺傳進(jìn)化過(guò)程形成一種全局優(yōu)化概率搜索算法，提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，可以不依賴于問(wèn)題的具體領(lǐng)域[1]。近年來(lái)，遺傳算法已被廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、自動(dòng)控制、人工智能、人工生命、機(jī)器學(xué)習(xí)、圖像處理和模式識(shí)別等多個(gè)領(lǐng)域，具有巨大的發(fā)展?jié)摿Α１疚闹饕榻B遺傳算法在醫(yī)學(xué)圖像處理方面的應(yīng)用。

1 遺傳算法的基本原理

遺傳算法是模擬生物進(jìn)化和遺傳機(jī)制發(fā)展起來(lái)的一種全局優(yōu)化、隨機(jī)、自適應(yīng)搜索算法。它模擬了自然界遺傳過(guò)程中的繁殖、和變異現(xiàn)象，依據(jù)適者生存、優(yōu)勝劣汰的進(jìn)化原則，利用遺傳算子（即選擇、交叉和變異）逐代產(chǎn)生優(yōu)選個(gè)體（候選解），最終搜索到適合的個(gè)體。

遺傳算法的運(yùn)算對(duì)象是由N個(gè)個(gè)體所組成的集合，稱為群體。遺傳算法的運(yùn)算過(guò)程是一個(gè)群體反復(fù)迭代的過(guò)程，這個(gè)群體不斷地經(jīng)過(guò)遺傳和進(jìn)化操作，每次按照優(yōu)勝劣汰的進(jìn)化原則將適應(yīng)度較高的個(gè)體以更高的概率遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體，它將達(dá)到或接近于問(wèn)題的最優(yōu)解[2]。

遺傳算法的求解步驟如下：

1）編碼：定義搜索空間解的表示到遺傳空間解的表示的映射，兩個(gè)空間的解需一一對(duì)應(yīng)且編碼盡量簡(jiǎn)明。遺傳算法把問(wèn)題的解也稱為個(gè)體或染色體，個(gè)體通常由字符串表示，字符串的每一位稱為遺傳因子，多個(gè)個(gè)體形成一個(gè)種群。

2）初始化種群 隨機(jī)產(chǎn)生N個(gè)個(gè)體組成一個(gè)種群，此種群代表一些可能解的集合。GA 的任務(wù)是從這些群體出發(fā)，模擬進(jìn)化過(guò)程進(jìn)行優(yōu)勝劣汰，最后得出優(yōu)秀的種群和個(gè)體，滿足優(yōu)化的要求。

3）設(shè)計(jì)適應(yīng)度函數(shù)：將種群中的每個(gè)個(gè)體解碼成適合于計(jì)算機(jī)適應(yīng)度函數(shù)的形式，并計(jì)算其適應(yīng)度。

4）選擇：按一定概率從當(dāng)前群體中選出優(yōu)良個(gè)體，作為雙親用于繁殖后代，一些優(yōu)良的個(gè)體遺傳到下一代群體中，適應(yīng)度越高，則選擇概率越大。進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的優(yōu)良個(gè)體將有更多繁殖后代的機(jī)會(huì)，從而使優(yōu)良特性得以遺傳。選擇是遺傳算法的關(guān)鍵，它體現(xiàn)了適者生存原則。

5）交叉：交叉操作是遺傳算法中最主要的遺傳操作。對(duì)于選中的用于繁殖的每一對(duì)個(gè)體，隨機(jī)選擇兩個(gè)用于繁殖下一代的個(gè)體的相同位置，在選中的位置實(shí)行交換。交叉體現(xiàn)了信息交換的思想。

6）變異：從群體中選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體按一定的概率隨機(jī)選擇改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值，即對(duì)某個(gè)串中的基因按突變概率進(jìn)行翻轉(zhuǎn)。變異模擬了生物進(jìn)化過(guò)程中的偶然基因突變現(xiàn)象，遺傳算法中變異發(fā)生的概率很低。對(duì)產(chǎn)生的新一代群體進(jìn)行重新評(píng)價(jià)、選擇、雜交和變異。

7）終止準(zhǔn)則：如此循環(huán)往復(fù)，使群體中最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個(gè)體的適應(yīng)度滿足某一性能指標(biāo)或規(guī)定的遺傳代數(shù)，迭代過(guò)程收斂，算法結(jié)束。

2 遺傳算法在圖像分割處理中的應(yīng)用

在圖像處理中，圖像分割是圖像三維重建的基礎(chǔ)，常用的分割方法包括閾值法、邊緣檢測(cè)法和區(qū)域跟蹤法，其中閾值法是最常用的方法[3]。圖像閾值分割算法是利用圖像中目標(biāo)物體與背景灰度上的差異，根據(jù)圖像灰度值的分布特性把圖像分為不同灰度級(jí)的目標(biāo)區(qū)域和背景區(qū)域，目前已有模糊集法、共生矩陣法、四元樹(shù)法、最大類間方差法、最佳直方圖熵法、最小誤差閾值法等多種閾值分割方法。

遺傳算法在圖像分割中的作用是：幫助現(xiàn)存的圖像分割算法在參數(shù)空間內(nèi)搜索參數(shù)，或者在候選的分隔空間內(nèi)搜索最優(yōu)的分隔方案[3]。在參數(shù)空間內(nèi)搜索參數(shù)主要是指利用遺傳算法的全局搜索特性優(yōu)化現(xiàn)有的閾值分割算法，用于幫助確定最佳分割閾值。

3 基于遺傳算法的肝臟CT圖像分割

本文基于遺傳算法選取閾值，采用最大熵原則對(duì)肝臟CT圖像進(jìn)行分割。目的是將圖像的灰度直方圖分成兩個(gè)或多個(gè)獨(dú)立的類，使得各類熵的總量最大，根據(jù)信息論，這樣選擇的閾值能獲得的信息量最大[4]。在圖像的灰度直方圖中設(shè)定一個(gè)灰度閾值，可以把圖像分成背景和物體兩類區(qū)域，這是一般的單閾值選擇的情況，而設(shè)定N個(gè)閾值，可以把圖像分成N+1類區(qū)域[4]。

最大熵分割方法步驟為：

用p0,p1,…,pn表示灰度級(jí)的概率分布，如果把閾值設(shè)置在灰度級(jí)s，將獲得兩個(gè)概率分布，一個(gè)包含1到s間的灰度級(jí)，另一個(gè)包含s+1到n間的灰度級(jí)，這兩個(gè)分布如下：

其中，與每一個(gè)分布相關(guān)的熵為：

令: (4)

當(dāng)該函數(shù)取最大值時(shí)即為圖像的最佳分割，用此函數(shù)作為遺傳算法中的適應(yīng)度函數(shù)。通過(guò)遺傳算法的設(shè)計(jì)步驟，取得最佳閾值，既而對(duì)人體肝臟中有病灶組織的CT圖像進(jìn)行分割，得到下面分割處理實(shí)驗(yàn)結(jié)果。

(a) 原圖 (b) 分割結(jié)果(c)原圖 (d) 分割結(jié)果

圖1 對(duì)有病灶肝臟圖像進(jìn)行分割

通過(guò)實(shí)驗(yàn)結(jié)果可以看到，基于遺傳算法采用最大熵原則，對(duì)人體肝臟CT圖像進(jìn)行分割，能夠使選取的閾值獲得的信息量比較大，從而原始圖像和分割圖像之間的信息量差異最小。因此分割后的圖像效果明顯，具有一定的優(yōu)勢(shì)[5]。

但由于醫(yī)學(xué)圖像的復(fù)雜性和人體的差異性，對(duì)人體同一器官不同狀況的圖像，無(wú)法找出一種最為適合的分割方法處理，必須根據(jù)具體情況具體分析，針對(duì)圖像的特點(diǎn)來(lái)選取相應(yīng)的分割算法，才能較好地解決問(wèn)題。

參考文獻(xiàn)：

[1] 田瑩,苑瑋琦.遺傳算法在圖像處理中的應(yīng)用[J].中國(guó)圖象圖形學(xué)報(bào),2007,12(3):389-396.

[2] Hsieh puted Tomography Principle, Design, Artifacts and Recent Advances（中文翻譯版）[M].北京:科學(xué)出版社,2006.

[3] 徐丹霞,郭圣文,吳效明,等. 肝臟CT圖像分割技術(shù)研究進(jìn)展[J].醫(yī)療衛(wèi)生裝備,2009,30(3):34-36.

篇4

【關(guān)鍵詞】多目標(biāo)優(yōu)化 進(jìn)化算法 遺傳算法 組合算法

中圖分類號(hào)：TP18

1引言

大多數(shù)多目標(biāo)優(yōu)化問(wèn)題，每個(gè)目標(biāo)函數(shù)之間可能是競(jìng)爭(zhēng)的關(guān)系，優(yōu)化某一個(gè)函數(shù)的同時(shí)，往往以犧牲另一個(gè)優(yōu)化目標(biāo)為代價(jià)，如果將多目標(biāo)轉(zhuǎn)化為單目標(biāo)函數(shù)優(yōu)化時(shí)，各優(yōu)化目標(biāo)加權(quán)值的分配帶有很大的主觀性，必然造成優(yōu)化結(jié)果的單一性，沒(méi)有考慮全局優(yōu)化。而如果將多目標(biāo)函數(shù)利用評(píng)價(jià)函數(shù)法轉(zhuǎn)化為單目標(biāo)函數(shù)求解，得到的僅僅是一個(gè)有效解，所以我們可以考慮直接采用多目標(biāo)函數(shù)的優(yōu)化方法對(duì)多目標(biāo)進(jìn)行優(yōu)化[1-2]。

2多目標(biāo)優(yōu)化的發(fā)展現(xiàn)狀

在多目標(biāo)優(yōu)化問(wèn)題中，各分目標(biāo)函數(shù)的最優(yōu)解往往是互相獨(dú)立的，很難同時(shí)實(shí)現(xiàn)最優(yōu)。在分目標(biāo)函數(shù)之間甚至還會(huì)出現(xiàn)完全對(duì)立的情況，即某一個(gè)分目標(biāo)函數(shù)的最優(yōu)解卻是另一個(gè)分目標(biāo)函數(shù)的劣解。求解多目標(biāo)優(yōu)化問(wèn)題的關(guān)鍵，是要在決策空間中尋求一個(gè)最優(yōu)解的集合，需要在各分目標(biāo)函數(shù)的最優(yōu)解之間進(jìn)行協(xié)調(diào)和權(quán)衡，以使各分目標(biāo)函數(shù)盡可能達(dá)到近似最優(yōu)。多目標(biāo)優(yōu)化問(wèn)題不存在唯一的全局最優(yōu)解，而是要尋找一個(gè)最終解。得到最終解需要通過(guò)各種算法來(lái)實(shí)現(xiàn)，如進(jìn)化算法、模擬退火算法、蟻群算法、粒子群算法和遺傳算法等[3-4]。由于各種算法存在應(yīng)用領(lǐng)域的差異和自身缺陷，人們也提出了一些改進(jìn)算法和組合算法。

2.1進(jìn)化算法

進(jìn)化算法 （Evolutionary Algorithms，EA）是一種仿生優(yōu)化算法，主要包括遺傳算法、進(jìn)化規(guī)劃、遺傳規(guī)劃和進(jìn)化策略等。根據(jù)達(dá)爾文的“優(yōu)勝劣汰、適者生存”的進(jìn)化原理及盂德?tīng)柕热说倪z傳變異理論，在優(yōu)化過(guò)程中模擬自然界的生物進(jìn)化過(guò)程與機(jī)制，求解優(yōu)化與搜索問(wèn)題。進(jìn)化算法具有自組織、自適應(yīng)、人工智能、高度的非線性、可并行性等優(yōu)點(diǎn)[5]。

進(jìn)化算法在求解多目標(biāo)優(yōu)化問(wèn)題上優(yōu)勢(shì)在于：一是搜索的多向性和全局性，通過(guò)重組操作充分利用解之間的相似性，能夠在一次運(yùn)行中獲取多個(gè)Pareto最優(yōu)解，構(gòu)成近似問(wèn)題的Pareto最優(yōu)解集；二是可以處理所有類型的目標(biāo)函數(shù)和約束。三是采用基于種群的方式組織搜索、遺傳操作和優(yōu)勝劣汰的選擇機(jī)制，不受其搜索空間條件的限制。

雖然基于Pareto最優(yōu)解的多目標(biāo)進(jìn)化算法可以得到較好分布的最優(yōu)解集，但如何保證算法具有良好的收斂性仍是一個(gè)熱點(diǎn)問(wèn)題。

2.2模擬退火算法

模擬退火（Simulated Annealing，SA）算法是根據(jù)物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性，基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法。SA在初始溫度下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。SA具有以下優(yōu)點(diǎn)：通用性強(qiáng)，對(duì)問(wèn)題信息依賴較少，可有效避免陷入局部極小并最終趨于全局最優(yōu)。因此在諸多工程和學(xué)術(shù)領(lǐng)域得到了研究與應(yīng)用[6-7]。遺憾的是它在多目標(biāo)優(yōu)化領(lǐng)域的研究與應(yīng)用尚少。

2.3蟻群算法

蟻群算法（Ant Colony Optimization， ACO）是一種用來(lái)在圖中尋找優(yōu)化路徑的正反口的新型模擬進(jìn)化算法。。蟻群算法具有并行性、分布性、正反饋性、自組織性、較強(qiáng)的魯棒性和全局搜索能力等特點(diǎn)。目前運(yùn)用這種方法已成功地解決了旅行商（TSP）問(wèn)題、Job-shop調(diào)度問(wèn)題、二次指派問(wèn)題等組合優(yōu)化問(wèn)題。

由于蟻群算法需要的參數(shù)數(shù)目少，設(shè)置簡(jiǎn)單，在求解多目標(biāo)優(yōu)化問(wèn)題時(shí)存在一些困難。首先，多目標(biāo)函數(shù)優(yōu)化問(wèn)題是在連續(xù)空間中進(jìn)行尋優(yōu)，解空間以區(qū)域表示，螞蟻在每一階段可選的路徑不再是有限的，螞蟻在信息索的駐留和基于信息素的尋優(yōu)上存在困難。文獻(xiàn)[8]提出先使用遺傳算法對(duì)解空間進(jìn)行全局搜索，再運(yùn)用蟻群算法對(duì)得到的結(jié)果進(jìn)行局部?jī)?yōu)化；文獻(xiàn)[9]修改了螞蟻信息素的留存方式和行走規(guī)則，運(yùn)用信息素交流和直接通訊兩種方式來(lái)指導(dǎo)螞蟻尋優(yōu)；文獻(xiàn)[10]將搜索空間劃分為若干子域，根據(jù)信息量確定解所在的子域，在該子域內(nèi)尋找解，也取得了滿意的結(jié)果。

其次，螞蟻算法需要較長(zhǎng)的搜索時(shí)間、容易出現(xiàn)早熟停滯現(xiàn)象。文獻(xiàn)[11]提出了具有免疫能力的螞蟻算法和蟻群遺傳算法，提高算法的尋優(yōu)能力和尋優(yōu)效率。

最后，多目標(biāo)優(yōu)化問(wèn)題由于解的多樣性，不僅要求所得的解能夠收斂到Pareto前沿，而且要有效地保持群體的多樣性。螞蟻之間的這種信息素交流方式，會(huì)使所求得的解集中在解空間的某一區(qū)域內(nèi)，不利于群體多樣性的保持。

2.4粒子群算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是在1995年由美國(guó)社會(huì)心理學(xué)家Kennedy和電氣工程師Eberhart共同提出的，源于對(duì)鳥(niǎo)群覓食過(guò)程中的遷徙和聚集的模擬。它收斂速度快、易于實(shí)現(xiàn)且僅有少量參數(shù)需要調(diào)整，目前已經(jīng)被廣泛應(yīng)用于目標(biāo)函數(shù)優(yōu)化、動(dòng)態(tài)環(huán)境優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練等許多領(lǐng)域。

由于直接用粒子群算法處理多目標(biāo)優(yōu)化問(wèn)題，很容易收斂于非劣最優(yōu)域的局部區(qū)域，以及如何保證算法的分布性等問(wèn)題，Coello等人提出了基于Pareto的多目標(biāo)粒子群算法（MOPS0），強(qiáng)調(diào)了粒子和種群之間作用的重要性[12]。

多目標(biāo)粒子群優(yōu)化算法作為一種新興的多目標(biāo)優(yōu)化算法具有以下優(yōu)點(diǎn)：（1）在編碼方式上PSO算法比較簡(jiǎn)單，可以直接根據(jù)被優(yōu)化問(wèn)題進(jìn)行實(shí)數(shù)編碼；（2）對(duì)種群的初始化不敏感，可達(dá)到較快的收斂速度；（3）算法適用于絕大多數(shù)的多目標(biāo)優(yōu)化問(wèn)題；（4）優(yōu)化過(guò)程中，每個(gè)粒子通過(guò)自身經(jīng)驗(yàn)與群體經(jīng)驗(yàn)進(jìn)行更新，具有學(xué)習(xí)和記憶的功能；（5）該算法在收斂性、解的分布性以及計(jì)算效率方面具有很大改善。

2.5遺傳算法

遺傳算法（Genetic Algorithm，GA）是進(jìn)化算法的一種，是美國(guó)密執(zhí)安大學(xué)的John Holland教授于七十年代中期首先提出來(lái)的，從生物進(jìn)化的過(guò)程中得到靈感與啟迪，模擬人自然“物竟天擇，適者生存”的自然選擇的法則創(chuàng)立的。

與其他優(yōu)化算法相比，遺傳算法求解多目標(biāo)優(yōu)化問(wèn)題的主要優(yōu)點(diǎn)：一是保證算法的收斂性，即在目標(biāo)空間內(nèi)，所求得的Pareto最優(yōu)解集與實(shí)際Pareto盡可能的接近。二是多樣性的維護(hù)，即希望找到的Pareto最優(yōu)解集具有較好的分布特性（如均勻分布），且分布范圍盡可能的寬闊。三是具有很好的魯棒性，是一種高度并行、隨機(jī)、自適應(yīng)能力很強(qiáng)的智能搜索算法，因此特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜非線性問(wèn)題。四是新的遺傳算法引入精英概念，使進(jìn)化的每一代的Pareto最優(yōu)解總是直接保留到下一代的群體中，提高了Pareto最優(yōu)解的搜索效率。五是引入用戶的偏好信息，以交互的方式表達(dá)偏好，使用決策者的偏好信息來(lái)指導(dǎo)算法的搜索過(guò)程和范圍[13-14]。

3多目標(biāo)優(yōu)化研究的熱點(diǎn)問(wèn)題

多目標(biāo)優(yōu)化問(wèn)題中，各個(gè)目標(biāo)之間通過(guò)決策變量相互制約，對(duì)其中一個(gè)目標(biāo)優(yōu)化必須以其他目標(biāo)作為代價(jià)，而且各目標(biāo)的單位又往往不一致，因此很難客觀地評(píng)價(jià)多目標(biāo)問(wèn)題解的優(yōu)劣性。傳統(tǒng)優(yōu)化方法往往強(qiáng)調(diào)最優(yōu)化，在解決因多種復(fù)雜因素難以建模，或根本不存在傳統(tǒng)意義上的最優(yōu)解或獲得最優(yōu)解的代價(jià)太大的優(yōu)化問(wèn)題時(shí)。由此，采用滿意優(yōu)化方法解決這類問(wèn)題是較好的策略。滿意優(yōu)化本質(zhì)上是一個(gè)多目標(biāo)優(yōu)化方法，它摒棄了傳統(tǒng)的最優(yōu)概念，它將優(yōu)化問(wèn)題的約束和目標(biāo)融為一體，將性能指標(biāo)要求的滿意設(shè)計(jì)與參數(shù)優(yōu)化融為一體，強(qiáng)調(diào)的是“滿意”而不“最優(yōu)”。所以，近年來(lái)，滿意優(yōu)化也逐漸成為各領(lǐng)域關(guān)心的問(wèn)題。

4結(jié)束語(yǔ)

多目標(biāo)優(yōu)化問(wèn)題是近年來(lái)人們?cè)絹?lái)越需要面對(duì)和解決的問(wèn)題。除了以上單一優(yōu)化算法外，很多學(xué)者已經(jīng)在單一優(yōu)化算法的基礎(chǔ)上，結(jié)合多種優(yōu)化算法解決了一些多目標(biāo)優(yōu)化問(wèn)題，如NSGA-Ⅱ與MOPSP的結(jié)合算法[15]，模擬退火算法與遺傳算法的結(jié)合算法[16]。然而，由于各種多目標(biāo)優(yōu)化算法的不同特點(diǎn)和缺陷，如何使這些優(yōu)化算法能夠更好地?zé)o縫對(duì)接，對(duì)解決多目標(biāo)滿意優(yōu)化問(wèn)題具有非常重要的意義。

參考文獻(xiàn)

[1]玄光男，程潤(rùn)偉著.周根貴譯.遺傳算法與工程優(yōu)化，清華大學(xué)出版社，2004.

[2] Liu Zhen Yu .Multi-objective optimization design analysis of primary surface recuperator for microturbines[J].Applied Thermal Engineering 28（2008）：601～610.

[3]肖曉偉等.多目標(biāo)優(yōu)化問(wèn)題的研究概述.計(jì)算機(jī)應(yīng)用研究，2011（03）

[4] Kalyanmoy Deb，Amrit Pratap，T Meyarivan.A fast and elitist multi-objective genetic 2002.6（2）：182～197.algorithm： NSGA-II [J].IEEE Transactions on Evolutionary Computation.

[5]楊海清.進(jìn)化算法的改進(jìn)及其應(yīng)用研究.浙江工業(yè)大學(xué)碩士論文，2004.

[6]鄧俊等.基于神經(jīng)網(wǎng)絡(luò)和模擬退火算法的配煤智能優(yōu)化方法[J].冶金自動(dòng)化，2007（3）.

[7]韓強(qiáng).多目標(biāo)應(yīng)急設(shè)施選址問(wèn)題的模擬退火算法[J].計(jì)算機(jī)工程與應(yīng)用 ，2007（30）.

[8]陳峻等.蟻群算法求解連續(xù)空間優(yōu)化問(wèn)題的一種方法[J].軟件學(xué)報(bào) 2002，13（12）.

[9]Dorigo M，Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Trans. Evolutionary Computation，1997，1（1）：53-56.

[10]張德勇，黃莎白.多目標(biāo)優(yōu)化問(wèn)題的蟻群算法研究[J].控制與決策 2005，20（2）

[11]毛寧.具有免疫能力的螞蟻算法研究（碩士學(xué)位論文） 河北工業(yè)大學(xué).2006

[12]張慧敏.改進(jìn)的粒子群計(jì)算智能算法及其多目標(biāo)優(yōu)化的應(yīng)用研究（碩士學(xué)位論文）.

杭州大學(xué).2005.

[13]李金娟.遺傳算法及應(yīng)用的研究[J].電腦與信息技術(shù)，2013（02）.

[14]洪朝飛等.面向機(jī)械設(shè)計(jì)的一種改進(jìn)的遺傳算法.太原科技大學(xué)學(xué)報(bào)，2013（02）.

[15]王金華等.基于NSGA-Ⅱ與MOPSP融合的一種多目標(biāo)優(yōu)化算法[J].

篇5

作者簡(jiǎn)介：陳 軒（1990―），男，湖北漢川人，碩士研究生，研究方向：智能控制與智能應(yīng)用。

文章編號(hào)：1003-6199(2014)02-0089-04

摘 要：區(qū)域防空雷達(dá)網(wǎng)是防空作戰(zhàn)空情預(yù)警的發(fā)展趨勢(shì)，為了提高區(qū)域雷達(dá)網(wǎng)探測(cè)能力和抗綜合電子干擾、抗隱身技術(shù)與隱身飛機(jī)的威脅，抗低空、超低空突防及抗反輻射導(dǎo)彈(ARM)的能力，研究雷達(dá)組網(wǎng)的問(wèn)題，介紹免疫遺傳算法的基本原理和特點(diǎn)，提出基于免疫遺傳算法的雷達(dá)組網(wǎng)方法，通過(guò)計(jì)算機(jī)仿真實(shí)驗(yàn)證明方法的可行性。

關(guān)鍵詞：免疫遺傳算法；雷達(dá)組網(wǎng)；覆蓋系數(shù)

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

お

Approach to Radar Netting Based on Immune Genetic Algorithm

お

CHEN Xuank, HUANG Xinhan

(School of Automation, Huazhong University of Science and Technology, Wuhan,Hubei 430074,China)

Abstract:Regional airdefense radar netting is the tendency of air defense warfare in future, in order to improve the detective performance and the performance of anti synthesized electronic interference, anti stealth technique and stealth aircraft, anti low, ultra low altitude penetration and anti anti-radiation missiles(ARM), radar netting is studied. The principle and characteristics of immune genetic algorithm is introduced, and immune genetic algorithm is put forward in radar netting. The simulation experiment by computers indicates valid of this method.

Key words:immune genetic algorithm; radar network; coverage coefficient

1 引 言

隨著新型空襲兵器和航天技術(shù)的不斷發(fā)展，單臺(tái)雷達(dá)無(wú)論在探測(cè)能力上，還是電子防御功能上都有較大的局限性，因此雷達(dá)組網(wǎng)技術(shù)在現(xiàn)代戰(zhàn)爭(zhēng)和人類對(duì)宇宙的探測(cè)中起著舉足輕重的作用，該技術(shù)是通過(guò)將多功能、多類型、多頻段的雷達(dá)進(jìn)行組網(wǎng)，實(shí)現(xiàn)實(shí)時(shí)數(shù)據(jù)傳輸，資源共享，并在此基礎(chǔ)上對(duì)數(shù)據(jù)實(shí)時(shí)處理，這已被證明是一種有效的方法［1］。雷達(dá)組網(wǎng)系統(tǒng)的關(guān)鍵問(wèn)題是如何對(duì)多臺(tái)雷達(dá)進(jìn)行最佳組網(wǎng)以獲得最優(yōu)的防御能力。目前進(jìn)行雷達(dá)組網(wǎng)的方法很多，常用的有效用函數(shù)法或?qū)＜曳ǎ鼈兪歉鶕?jù)雷達(dá)覆蓋防守區(qū)域面積、雷達(dá)部署任務(wù)、單臺(tái)雷達(dá)探測(cè)距離、地形、銜接角、遮蔽角、起伏角等因素進(jìn)行加權(quán)求和得到陣地的效用值，但是這些都不能很好地解決執(zhí)行速度的問(wèn)題。將免疫遺傳算法應(yīng)用于雷達(dá)組網(wǎng)，能較快地使布陣接近最優(yōu)解，從而避免了采用窮舉的方法帶來(lái)執(zhí)行速度慢的問(wèn)題，并且克服了遺傳算法未成熟收斂和局部搜索能力差的缺陷。

2 免疫遺傳算法原理和設(shè)計(jì)

2.1 免疫遺傳算法原理

生物免疫系統(tǒng)對(duì)抗原會(huì)自動(dòng)產(chǎn)生相應(yīng)的抗體來(lái)防御，這一過(guò)程被稱為免疫應(yīng)答。在此過(guò)程中，部分抗體作為記憶細(xì)胞保存下來(lái)，當(dāng)同類抗原再次侵入時(shí)，記憶細(xì)胞被激活并產(chǎn)生大量抗體，使再次應(yīng)答比初次應(yīng)答更迅速，體現(xiàn)了免疫系統(tǒng)的記憶功能。同時(shí)，抗體與抗體之間也相互促進(jìn)和抑制，以維持抗體的多樣性及免疫平衡，這種平衡是依濃度機(jī)制完成的，即抗體的濃度越高，則越受抑制，反之亦然，體現(xiàn)了免疫系統(tǒng)的自我調(diào)節(jié)功能。抗體的濃度計(jì)算是系統(tǒng)保持種群多樣性的基本手段之一［2］。

傳統(tǒng)的遺傳算法是一種具有“生成+檢測(cè)”的迭代過(guò)程的搜索算法，而免疫遺傳算法IGA (Immune Genetic Algorithm，IGA)則是一種借鑒生物免疫系統(tǒng)的自適應(yīng)識(shí)別和排除侵入機(jī)體的抗原性異物的功能，將生物免疫系統(tǒng)的學(xué)習(xí)、記憶、多樣性和識(shí)別特點(diǎn)引入的遺傳算法。在解決實(shí)際問(wèn)題時(shí)，目標(biāo)函數(shù)和約束條件作為抗原輸入，隨后產(chǎn)生初始抗體群，計(jì)算抗原和抗體的親和力用來(lái)描述可行解與最優(yōu)解的逼近程度，并通過(guò)一系列遺傳操作的計(jì)算，在保持抗體多樣性的情況下，找出針對(duì)該抗原的抗體，即問(wèn)題的解［3］。免疫遺傳算法與傳統(tǒng)的遺傳算法相比，具有如下顯著特點(diǎn)：

1）具有免疫記憶功能：可加快搜索速度，提高總體搜索能力，確保快速收斂于全局最優(yōu)解；

2）具有抗體的多樣性保持功能：可提高全局搜索能力，避免未成熟收斂；

3）具有自我調(diào)節(jié)功能：可提高局部搜索能力。

2.2 免疫遺傳算法設(shè)計(jì)

免疫遺傳算法在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上增加了抗體濃度概率計(jì)算、抗體的促進(jìn)與抑制等模塊來(lái)提高解的多樣性。該算法因?yàn)閷⒚庖呦到y(tǒng)中抗體多樣性維持機(jī)制引入了遺傳算法，使得其性能比標(biāo)準(zhǔn)遺傳算法更進(jìn)了一步。在解決實(shí)際問(wèn)題時(shí)，目標(biāo)函數(shù)和約束條件作為抗原輸入，隨后產(chǎn)生初始抗體群，并通過(guò)一系列遺傳操作及抗體親和度的計(jì)算，在保持抗體多樣性的情況下，找出針對(duì)該抗原的抗體，也就是問(wèn)題的解［3］。免疫遺傳算法的流程圖如圖1所示，其基本的步驟如下：

計(jì)算技術(shù)與自動(dòng)化2014年6月

第33第2期陳 軒等:基于免疫遺傳算法的雷達(dá)組網(wǎng)方法

1）算法初始化。輸入抗原及設(shè)定參數(shù)：輸入目標(biāo)函數(shù)以及約束條件，作為抗原的輸入；設(shè)定種群規(guī)模、選擇概率、交叉概率、變異概率等參數(shù)。

2）初始抗體產(chǎn)生。在第一次迭代時(shí)，抗體通常在解空間中用隨機(jī)的方法產(chǎn)生。

3）親和度及濃度的計(jì)算。計(jì)算各抗體和抗原的親和度以及各抗體的濃度。

4）終止條件判斷。判斷是否滿足終止條件，如果滿足終止條件，將與抗原親和度最高的抗體加入細(xì)胞記憶數(shù)據(jù)庫(kù)，然后終止；否則繼續(xù)。

5）選擇、交叉、變異操作。根據(jù)設(shè)置的選擇概率、交叉概率和變異概率選擇抗體，對(duì)抗體進(jìn)行交叉和變異操作。

6）根據(jù)以上的操作更新群體以后轉(zhuǎn)入步3)。

ネ1 免疫遺傳算法流程圖オ

3 采用免疫遺傳算法的雷達(dá)組網(wǎng)

3.1 雷達(dá)組網(wǎng)問(wèn)題描述

在采用免疫遺傳算法進(jìn)行雷達(dá)組網(wǎng)的方案中，雷達(dá)的覆蓋系數(shù)為：

Е=［(∪Ni=1Si)∩Sarea］/Sarea(1)

式中Si為第i臺(tái)雷達(dá)的探測(cè)范圍，N為雷達(dá)總數(shù)，Sarea給定的責(zé)任區(qū)域。ρ∈［0，1］ 表示N臺(tái)雷達(dá)所覆蓋的有效責(zé)任區(qū)域占總責(zé)任區(qū)域的比重。maxρ為本次雷達(dá)組網(wǎng)的目標(biāo)函數(shù)，也就是免疫遺傳算法中的抗原，即

maxρ=max ［(∪Ni=1Si)∩Sarea］/Sarea (2)

3.2 抗體編碼

雷達(dá)坐標(biāo)是所求問(wèn)題解的信息，為了縮小抗體空間，提高搜索效率，采用了對(duì)雷達(dá)組網(wǎng)比較直觀的抗體編碼方式，假設(shè)一共有5臺(tái)雷達(dá)進(jìn)行組網(wǎng)，則N種雷達(dá)布陣的方案可以表示為如下的結(jié)構(gòu)：

X11Y11X12Y12X13Y13X14Y14X15Y15第1種雷達(dá)組網(wǎng)方案

X21Y21X22Y22X23Y23X24Y24X25Y25

第2種雷達(dá)組網(wǎng)方案

……

Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5

第n種雷達(dá)組網(wǎng)方案

其中，Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5（n表示雷達(dá)組網(wǎng)的任意一種方案）分別是第1臺(tái)、第2臺(tái)、第3臺(tái)、第4臺(tái)和第5臺(tái)雷達(dá)的橫坐標(biāo)和縱坐標(biāo)。雷達(dá)布陣的每一種方案對(duì)應(yīng)為免疫遺傳算法中抗體種群中的每一個(gè)個(gè)體。

3.3 親和力計(jì)算

親和力是指發(fā)生免疫系統(tǒng)識(shí)別的抗體和抗原的結(jié)構(gòu)越互補(bǔ)，結(jié)合越可能發(fā)生，而把彼此結(jié)合的強(qiáng)度稱之為親和力。抗原需要盡可能好的與入侵的抗體相結(jié)合。二者匹配程度越好，結(jié)合就越好，抗原和抗體親和力就越大。對(duì)于雷達(dá)組網(wǎng)問(wèn)題，抗原對(duì)應(yīng)的是雷達(dá)組網(wǎng)的最大覆蓋系數(shù)，由于雷達(dá)組網(wǎng)的總責(zé)任區(qū)域的面積是一定的，可以定義抗體Ab與抗原Ag的之間的親和力為：

(Ab,Ag)=1Tb－Tg(3)

式中：Tb，Ta分別為抗體Ab，Ag對(duì)應(yīng)的雷達(dá)網(wǎng)的覆蓋系數(shù)，其中Tg也是所求的最大的雷達(dá)網(wǎng)覆蓋系數(shù)。

定義抗體Ab1與抗體Ab2之間的親和力為：

App(Ab1,Ab2)=1|Tb1－Tb2|(4)

式中：Tb1、Tb2分別為抗體Ab1與抗體Ab2對(duì)應(yīng)的雷達(dá)網(wǎng)覆蓋系數(shù)［4］。

3.4 算法選擇、交叉、變異算子

免疫遺傳算法能使抗體保持多樣性并且最終能夠收斂到最優(yōu)解的主要操作，就是因?yàn)樵谒惴ㄖ杏羞x擇、交叉和變異算子的存在，從而使整個(gè)抗體群沿著適應(yīng)度較好的方向搜索。

1)選擇算子

選擇是根據(jù)適者生存原則選擇下一代抗體，在基于免疫遺傳算法的雷達(dá)組網(wǎng)中選擇的是下一代的組網(wǎng)方案。采用如下的選擇算子：

PS(xi)=αρ(xi)∑ni=1ρ(xi)+(1－α)1Ne－ciβ(5)

式中：ρ(xi)是以式(1)為適應(yīng)度函數(shù)的雷達(dá)組網(wǎng)覆蓋系數(shù)；ci是抗體xi的濃度，即群體中相似抗體所占的比重［5］，即

ci=和抗體i親和度大于λ的抗體數(shù)N(6)

其中λ為相似常數(shù)，一般取為0.9~1；

α和β是常數(shù)調(diào)節(jié)因子； N是該種群內(nèi)抗體的總數(shù)。

2)交叉

交叉是在選中的抗體中，對(duì)兩個(gè)不同的個(gè)體按交叉概率Pc隨機(jī)選中相同的位置進(jìn)行基因交換(一般交叉概率取值為0.15~0.75)，從而產(chǎn)生新的抗體，也就是新的雷達(dá)組網(wǎng)方案。如果對(duì)于5臺(tái)組網(wǎng)雷達(dá)，隨機(jī)選擇的是抗體1和抗體2進(jìn)行交叉，抗體1和抗體2的編碼如下：

抗體1：X11Y11X12Y12X13Y13X14Y14X15Y15

抗體2：X21Y21X22Y22X23Y23X24Y24X25Y25

按照交叉概率產(chǎn)生的交叉點(diǎn)為4，則交叉以后的抗體1和抗體2的編碼分別是：

抗體1：X11Y11X12Y12X23Y23X24Y24X25Y25

抗體2：X21Y21X22Y22X13Y13X14Y14X15Y15

3)變異

變異是在選中的抗體中，對(duì)個(gè)體中的某些基因以一定的變異概率對(duì)某些抗體的某些位執(zhí)行異向轉(zhuǎn)化(一般變異概率的取值為0.01~0.2)。在變異的時(shí)候，對(duì)于交叉過(guò)程中產(chǎn)生的抗體方案，隨機(jī)產(chǎn)生一個(gè)介于［-MAX/2, +MAX/2］的數(shù)字rand，其中MAX為橫坐標(biāo)和縱坐標(biāo)可取的最大值。變異以后坐標(biāo)值x’與原來(lái)值x之間的關(guān)系如下：

x，=x+rand(7)

變異以后如果x′＞MAX，則取x′=MAX；如果x，

單靠變異不能在求解中得到好處，但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣的時(shí)候，選擇和交叉無(wú)法產(chǎn)生新的基因，這時(shí)只能靠變異產(chǎn)生新的基因，即變異增加了全局優(yōu)化的特質(zhì)。

3.5 基于濃度的種群更新

由式(5)可見(jiàn)，本文中的選擇算子是采用基于抗體的雷達(dá)組網(wǎng)覆蓋系數(shù)以及抗體濃度的選擇概率Ps(xi)，從而有效地保證了抗體的多樣性，避免了算法的早熟問(wèn)題，能夠獲得更好的覆蓋系數(shù)。

4 仿真實(shí)驗(yàn)

根據(jù)前面的算法流程，選取目標(biāo)函數(shù)為N臺(tái)雷達(dá)所覆蓋的有效責(zé)任區(qū)域占總責(zé)任區(qū)域的比重。雷達(dá)的臺(tái)數(shù)分別為3臺(tái)，4臺(tái)，5臺(tái)，初始抗體的數(shù)量為N=50，即一共有50種方案。利用Иmatlab仿真的結(jié)果如圖2所示。ネ賈芯匭慰蟣硎鏡氖親橥雷達(dá)陣地的有效范圍(長(zhǎng)為200公里，寬為100公里)，雷達(dá)的類型一共有兩種，即探測(cè)范圍為50公里的雷達(dá)和探測(cè)范圍為30公里的雷達(dá)。參照雷達(dá)組網(wǎng)的實(shí)際要求，在仿真的過(guò)程中，最多只提供2臺(tái)性能優(yōu)越的雷達(dá)，效能較差的雷達(dá)數(shù)量不限。

ィa）3臺(tái)雷達(dá)的面積覆蓋率

ィb）4臺(tái)雷達(dá)的面積覆蓋率

ィc）5臺(tái)雷達(dá)的面積覆蓋率

圖2 matlab仿真結(jié)果

在圖2中當(dāng)雷達(dá)數(shù)量為3臺(tái)時(shí)，組網(wǎng)雷達(dá)的面積覆蓋率為87.84%（圖2（a））；當(dāng)為4臺(tái)時(shí)，組網(wǎng)雷達(dá)的面積覆蓋率為91.53%（圖2（b））；當(dāng)為5臺(tái)時(shí)，組網(wǎng)雷達(dá)的覆蓋率為94.27%（圖2（c））。將仿真的結(jié)果與傳統(tǒng)遺傳算法的組網(wǎng)覆蓋率對(duì)比［6］，如表1所示。

表1 雷達(dá)組網(wǎng)覆蓋率對(duì)比

3臺(tái)雷達(dá)

4臺(tái)雷達(dá)

5臺(tái)雷達(dá)

傳統(tǒng)遺傳算法覆蓋率

81.5%

86.1%

88.2%

免疫遺傳算法覆蓋率

87.84%

91.53%

94.27%

由表1可以看出，基于免疫遺傳算法雷達(dá)組網(wǎng)的覆蓋率要高很多，將免疫遺傳算法應(yīng)用于雷達(dá)組網(wǎng)是一種有效的方法。

5 結(jié) 論

雷達(dá)組網(wǎng)能夠有效地提高雷達(dá)系統(tǒng)的整體性能，更好的適應(yīng)高科技電子戰(zhàn)、信息戰(zhàn)。將免疫遺傳算法應(yīng)用于雷達(dá)組網(wǎng)系統(tǒng)，能夠有效地提高雷達(dá)網(wǎng)的面積覆蓋率。免疫遺傳算法與傳統(tǒng)的遺傳算法相比，能夠克服傳統(tǒng)遺傳算法的未成熟收斂，提高全局搜索能力。

參考文獻(xiàn)

［1］ 彭獲由. 區(qū)域性雷達(dá)組網(wǎng)［J］. 電子科學(xué)技術(shù)評(píng)論, 1992(3) :1- 6

［2］ LUO WENJIAN, CAO XIANBIN,WANG XUFA. An Immune Genetic Algorithm Based on Immune Regulation［A］. Proceedings of the 2002 Congress on Evolutionary ComputationCEC2002. May 12-17, 2002. Honolulu, USA. Vol.2: 801-806.

［3］ 段玉波, 任偉建, 霍鳳財(cái), 等. 一種新的免疫遺傳算法及其應(yīng)用［J］, 2005, 20(10):1185-1188.

［4］ 謝剛, 武斌, 謝克明. 基于免疫遺傳算法的TSP優(yōu)化問(wèn)題求解［J］. 太原理工大學(xué)學(xué)報(bào), 2007, 38(3): 199-201.

篇6

關(guān)鍵詞全局最優(yōu)；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數(shù)優(yōu)化問(wèn)題具有廣泛的工程和應(yīng)用背景，如結(jié)構(gòu)設(shè)計(jì)中使得結(jié)構(gòu)內(nèi)最大應(yīng)力最小而歸結(jié)為極大極小優(yōu)化（minmax）問(wèn)題、數(shù)據(jù)魯棒性擬合中采取最小絕對(duì)值準(zhǔn)則建立失擬函數(shù)等。其求解方法的研究越來(lái)越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部?jī)?yōu)化方法，優(yōu)化結(jié)果與初值有關(guān)。

近年來(lái)，由Holland研究自然現(xiàn)象與人工系統(tǒng)的自適應(yīng)行為時(shí)，借鑒“優(yōu)勝劣汰”的生物進(jìn)化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數(shù)全局最優(yōu)解的方法。以遺傳算法為代表的進(jìn)化算法發(fā)展很快，在各種問(wèn)題的求解與應(yīng)用中展現(xiàn)了其特點(diǎn)和魅力，但是其理論基礎(chǔ)還不完善，在理論和應(yīng)用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問(wèn)題[1,2]。為克服這一問(wèn)題，早在1989年Goldberg就提出混合方法的框架[2]，把GA與傳統(tǒng)的、基于知識(shí)的啟發(fā)式搜索技術(shù)相結(jié)合，來(lái)改善基本遺傳算法的局部搜索能力，使遺傳算法離開(kāi)早熟收斂狀態(tài)而繼續(xù)接近全局最優(yōu)解。近來(lái)，文獻(xiàn)[3]和[4]在總結(jié)分析已有發(fā)展成果的基礎(chǔ)上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部?jī)?yōu)化方法結(jié)合構(gòu)成新的全局優(yōu)化方法，是目前有待集中研究的問(wèn)題之一，這種混合策略可以從根本上提高遺傳算法計(jì)算性能。文獻(xiàn)[5]采用牛頓－萊佛森法和遺傳算法進(jìn)行雜交求解旅行商問(wèn)題，文獻(xiàn)[6]把最速下降法與遺傳算法相結(jié)合來(lái)求解連續(xù)可微函數(shù)優(yōu)化問(wèn)題，均取得良好的計(jì)算效果，但是不適于不可微函數(shù)優(yōu)化問(wèn)題。

本文提出把Powell方法融入浮點(diǎn)編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個(gè)算子，構(gòu)成適于求解不可微函數(shù)優(yōu)化問(wèn)題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問(wèn)題。數(shù)值算例對(duì)混合方法的有效性進(jìn)行了驗(yàn)證。

2混合遺傳算法

編碼是遺傳算法應(yīng)用中的首要問(wèn)題，與二進(jìn)制編碼比較，由于浮點(diǎn)編碼遺傳算法有精度高，便于大空間搜索的優(yōu)點(diǎn)，浮點(diǎn)編碼越來(lái)越受到重視[7]。考慮非線性不可微函數(shù)優(yōu)化問(wèn)題(1)，式中為變量個(gè)數(shù)，、分別是第個(gè)變量的下界和上界。把Powell方法嵌入到浮點(diǎn)編碼遺傳算法中，得到求解問(wèn)題(1)如下混合遺傳算法：

min(1)

step1給遺傳算法參數(shù)賦值。這些參數(shù)包括種群規(guī)模m，變量個(gè)數(shù)n，交叉概率pc、變異概率pm，進(jìn)行Powell搜索的概率pPowell和遺傳計(jì)算所允許的最大代數(shù)T。

Step2隨機(jī)產(chǎn)生初始群體，并計(jì)算其適應(yīng)值。首先第i個(gè)個(gè)體適應(yīng)值取為fi’=fmax-fi，fi是第i個(gè)個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值，fmax為當(dāng)前種群成員的最大目標(biāo)函數(shù)值，i=1,2,…,m。然后按Goldberg線性比例變換模型[2]式(2)進(jìn)行拉伸。

fi’=a×fi’+b（fi³0）(2)

step3執(zhí)行比例選擇算子進(jìn)行選擇操作。

step4按概率執(zhí)行算術(shù)交叉算子進(jìn)行交叉操作。即對(duì)于選擇的兩個(gè)母體和，算術(shù)交叉產(chǎn)生的兩個(gè)子代為和，是[0，1]上的隨機(jī)數(shù)，1,。

step5按照概率執(zhí)行非均勻變異算子[8]。若個(gè)體的元素被選擇變異，，則變異結(jié)果為，其中，

(3)

(4)

返回區(qū)間[,]里的一個(gè)值，使靠近0的概率隨代數(shù)的增加而增加。這一性質(zhì)使算子在初始階段均勻地搜索空間，而在后面階段非常局部化。是[,]之間的隨機(jī)數(shù)，為最大代數(shù)，為決定非均勻度的系統(tǒng)參數(shù)。

step6對(duì)每個(gè)個(gè)體按照概率pPowell進(jìn)行Powell搜索。若個(gè)體被選擇進(jìn)行Powell搜索操作，則以作為初始點(diǎn)執(zhí)行Powell方法得，若則把所得計(jì)算結(jié)果作為子代，否則，若取=；若取=，1。

step7計(jì)算個(gè)體適應(yīng)值，并執(zhí)行最優(yōu)個(gè)體保存策略。

step8判斷是否終止計(jì)算條件，不滿足則轉(zhuǎn)向step3，滿足則輸出計(jì)算結(jié)果。

作為求解無(wú)約束最優(yōu)化問(wèn)題的一種直接方法，Powell法的整個(gè)計(jì)算過(guò)程由若干輪迭代組成，在每一輪迭代中，先依次沿著已知的n個(gè)方向搜索，得一個(gè)最好點(diǎn)，然后沿本輪迭代的初始點(diǎn)與該最好點(diǎn)連線方向進(jìn)行搜索，求得這一階段的最好點(diǎn)。再用最后的搜索方向取代前n個(gè)方向之一，開(kāi)始下一階段的迭代。為了保持算法中n個(gè)搜索方向是線性無(wú)關(guān)的，保證算法的收斂性，對(duì)替換方向的規(guī)則進(jìn)行改進(jìn)，在混合法的計(jì)算步驟step6中采用文[9]中的改進(jìn)Powell方法，其求解過(guò)程如下：

(1)變量賦初值，n個(gè)線性無(wú)關(guān)的n個(gè)方向,,…,，和允許誤差ε>0，令k=1。

(2)令，從出發(fā)，依次沿方向,,…,作一維搜索，得到點(diǎn),,…,求指標(biāo)m，使得-=max{-}，令。若ε，則Powell方法計(jì)算結(jié)束，否則，執(zhí)行(3)。

(3)求使得=min，令==，若，則Powell方法計(jì)算結(jié)束，得點(diǎn)；否則，執(zhí)行(4)。

(4)若，令，否則令()，然后置，轉(zhuǎn)(2)。

3算例

T[-500,500]

函數(shù)f(x)有相當(dāng)多的極小點(diǎn),全局極小點(diǎn)是=-420.97，=1,2,…,，最優(yōu)值為-837.97；次最優(yōu)點(diǎn)為={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次優(yōu)值-719.53。變量個(gè)數(shù)n=2時(shí)函數(shù)f(x)特性如圖1示。程序編制和運(yùn)行環(huán)境采用FortranPowerStation4.0，隨機(jī)數(shù)由內(nèi)部隨機(jī)函數(shù)產(chǎn)生，在奔騰133微機(jī)上運(yùn)行。

采用改進(jìn)的Powell方法計(jì)算100次，初值在區(qū)間[-500,500]內(nèi)隨機(jī)產(chǎn)生，只有6次（即以概率0.06）搜索到全局最優(yōu)，計(jì)算成功的概率極低。

Holland建立的標(biāo)準(zhǔn)（或簡(jiǎn)單）遺傳算法，其特點(diǎn)是二進(jìn)制編碼、賭輪選擇方法、隨機(jī)配對(duì)、一點(diǎn)交叉、群體內(nèi)允許有相同的個(gè)體存在。取種群規(guī)模m=30，交叉概率pc=0.95、變異概率pm=0.05，最大進(jìn)化代數(shù)T=1000，每個(gè)變量用串長(zhǎng)為L(zhǎng)=16的二進(jìn)制子串表示。二進(jìn)制編碼比浮點(diǎn)編碼遺傳算法計(jì)算精度低，對(duì)于標(biāo)準(zhǔn)遺傳算法以目標(biāo)函數(shù)小于-800為搜索成功，標(biāo)準(zhǔn)遺傳算法運(yùn)行100次。當(dāng)取最大進(jìn)化代數(shù)為T=200時(shí)，40次（以概率0.40）搜索到全局最優(yōu)，平均計(jì)算時(shí)間為0.51秒；當(dāng)取T=500時(shí)，51次（以概率0.51）搜索到全局最優(yōu)，平均計(jì)算時(shí)間為1.13秒。

采用本文混合法計(jì)算，取m=30，pc=0.85、pm=0.2，T=100，進(jìn)行Powell搜索的概率pPowell取不同值，混合法運(yùn)行100次，計(jì)算結(jié)果見(jiàn)如表1。對(duì)于這個(gè)具有多極值的算例，多次計(jì)算表明pPowell=0.3時(shí)，混合法能以完全概率搜索到全局最優(yōu)的準(zhǔn)確值，但是此時(shí)混合法計(jì)算時(shí)間約為標(biāo)準(zhǔn)遺傳算法取T=500時(shí)計(jì)算時(shí)間的4/5。對(duì)應(yīng)的浮點(diǎn)編碼遺傳算法，取m=30，pc=0.85、pm=0.2，T=100，運(yùn)行100次，82次（以概率0.82）搜索到全局最優(yōu)（如表1中PPowell=0所示），計(jì)算時(shí)間約為標(biāo)準(zhǔn)遺傳算法取T=500時(shí)計(jì)算時(shí)間的1/8，但是搜索到全局最優(yōu)的概率卻遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)遺傳算法。

表1pPowell取不同值時(shí)混合法的計(jì)算結(jié)果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最優(yōu)解的次數(shù)

82

85

89

94

98

100

求得最優(yōu)解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均計(jì)算時(shí)間/秒

0.14

0.20

0.31

0.47

0.68

0.87

4結(jié)束語(yǔ)

針對(duì)不可微函數(shù)的全局優(yōu)化問(wèn)題，本文提出一種把Powell方法與浮點(diǎn)編碼遺傳算法相結(jié)合的混合遺傳算法，該算法兼顧了遺傳算法全局優(yōu)化方面的優(yōu)勢(shì)和Powell方法局部搜索能力較強(qiáng)的特點(diǎn)，提高求得全局解的概率。計(jì)算結(jié)果表明混合法優(yōu)于遺傳算法和Powell法，可以可靠地搜索到具有多個(gè)局部極值的函數(shù)優(yōu)化問(wèn)題的全局解。由于計(jì)算中只用到函數(shù)值信息，本文混合法不僅適用于不可微函數(shù)優(yōu)化問(wèn)題，也適合可微函數(shù)全局優(yōu)化問(wèn)題。

參考文獻(xiàn)

[1]周明，孫樹(shù)林．遺傳算法原理及應(yīng)用[M]．北京：國(guó)防工業(yè)出版社，1999．

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．

[3]孟慶春，賈培發(fā)．關(guān)于Genetic算法的研究及應(yīng)用現(xiàn)狀[J]．清華大學(xué)出版社，1995，35(5)：44－48．

[4]戴曉暉，李敏強(qiáng)，寇紀(jì)松．遺傳算法理論研究綜述[J]．控制與決策，2000，15(3)：263－268．

[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．

[6]趙明旺．連續(xù)可微函數(shù)全局優(yōu)化的混合遺傳算法[J]．控制與決策，1997，12(5)：589－592．

[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．

[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．

篇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*)=min C（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ā)式算法（Heufistic Algorithms）等。這些方法的和核心是分割問(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 –depth search）、BC等算法的性能。文獻(xiàn)[7]利用GECP理論對(duì)存在禁用頻率的異頻雙工設(shè)備的頻率分配給出工程上的實(shí)用算法；文獻(xiàn)[9]則采用了BC方法頻率分配的全排列算法進(jìn)行了優(yōu)化。本文將探討如何遺傳算法解決FAP問(wèn)題。

2.

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

2．1 遺傳算法的原理

遺傳算法(Genetic Algorithms GA)是根據(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

｛

i++;

if(i≥pop-size)

｛

sum=0; i=0

wheelpos=rand()*sumfitness;

｝

j=rand()*pop-size;

sum+=fitness［j］;

｝

return j;

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);

else if(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(all frequentpoint)

{

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] Robert A.Murphey， Panos M. Pardalos etc， Frequency Assignment Problems， Handbook of combinatorial optimization， Kluwer Academic Publishers，1999

[2] Vittorio M.， Antonella C.， An ANTS Heuristic for the Frequency Assignment Problem， csr.unibo.it

[3] Joe Bater， Peter Jeavons， David Cohen， Are there optimal reuse distance constraints for FAPs with random Tx placement?， CSD-TR-98-01， CS Royal Holloway Uni. Of London，1998

[4] K.I Aardal， C.A.J. Hurkens， J.K. etc. Algorithms for Freequency Assignment Problems，CWI Quarterly，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)鍵詞 ] 異常客戶 孤立點(diǎn)檢測(cè) k-medoids算法 遺傳算法

國(guó)內(nèi)大多數(shù)商業(yè)銀行都已擁有自己的數(shù)據(jù)集中業(yè)務(wù)平臺(tái),數(shù)據(jù)集中以后,商業(yè)銀行建立了龐大的數(shù)據(jù)倉(cāng)庫(kù),實(shí)施了對(duì)經(jīng)營(yíng)信息、客戶數(shù)據(jù)的有效存儲(chǔ),緊接著商業(yè)銀行就迫切需要從這些海量的數(shù)據(jù)當(dāng)中挖掘出高價(jià)值的信息資源,從而精確的把握商業(yè)競(jìng)爭(zhēng)、客戶動(dòng)態(tài)等實(shí)時(shí)信息,以便實(shí)施具有針對(duì)性戰(zhàn)略。面對(duì)數(shù)量龐大的銀行客戶,如何應(yīng)對(duì)隨之帶來(lái)的風(fēng)險(xiǎn),成為商業(yè)銀行客戶關(guān)系管理必須面對(duì)的一個(gè)問(wèn)題。因此,本文將異常客戶檢測(cè)(Exceptional Client Distinguish,ECD)作為研究對(duì)象,利用數(shù)據(jù)挖掘的思想和方法,對(duì)異常客戶的風(fēng)險(xiǎn)進(jìn)行預(yù)警。

一、異常客戶檢測(cè)

客戶關(guān)系管理即為吸引并保持有經(jīng)濟(jì)價(jià)值的客戶,驅(qū)逐并消除缺乏經(jīng)濟(jì)價(jià)值的客戶。識(shí)別異常客戶,一方面可有效地驅(qū)逐和消除風(fēng)險(xiǎn),另一方面可以避免將正常客戶誤判為異常客戶,吸引并保持有經(jīng)濟(jì)價(jià)值潛力的客戶。

目前,異常客戶檢測(cè)技術(shù)主要還是基于數(shù)據(jù)特征匹配的方法。目前存在兩個(gè)缺點(diǎn)。首先,總結(jié)異常客戶特征主要靠專家手工完成,耗費(fèi)人力物力;其次,所需時(shí)間較長(zhǎng),錯(cuò)過(guò)最佳挽留時(shí)機(jī),異常客戶造成的危害就無(wú)法減少。

異常客戶反映在數(shù)據(jù)上,就是異常數(shù)據(jù)。Hawkins給出了異常的本質(zhì)性定義:異常是在數(shù)據(jù)集中與眾不同的數(shù)據(jù),使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差,而是產(chǎn)生于完全不同的機(jī)制;Knor和Ng給出了基于距離的異常定義:數(shù)據(jù)集S中的一個(gè)對(duì)象O,如果它滿足下列性質(zhì):數(shù)據(jù)集S中至少有p*100%的對(duì)象與O的距離大于距離D,則對(duì)象O稱為DB(p,D) - 異常 。

二、孤立點(diǎn)檢測(cè)

發(fā)現(xiàn)異常數(shù)據(jù),孤立點(diǎn)檢測(cè)是個(gè)行之有效的方法。孤立點(diǎn)(outlier)是數(shù)據(jù)集中的小部分?jǐn)?shù)據(jù)對(duì)象,這一小部分對(duì)

象和數(shù)據(jù)中的一般行為或數(shù)據(jù)模型有著明顯的不同。孤立點(diǎn)挖掘分為兩個(gè)子問(wèn)題:在給定的數(shù)據(jù)集中定義什么數(shù)據(jù)可以認(rèn)為是不一致的;找到一個(gè)有效的方法來(lái)挖掘孤立點(diǎn)。

孤立點(diǎn)在某種尺度下與其他點(diǎn)不同或不一致。孤立點(diǎn)可能是由于度量或執(zhí)行錯(cuò)誤導(dǎo)致的。許多數(shù)據(jù)挖掘算法試圖使孤立點(diǎn)的影響最小化,或者排除它們。然而,一個(gè)人的噪聲可能是另一個(gè)人的信號(hào)。這樣的點(diǎn)通常包含了一些重要的隱藏信息。例如,在欺詐探測(cè)中,孤立點(diǎn)可能預(yù)示著欺詐行為。

目前孤立點(diǎn)挖掘算法主要有四種:統(tǒng)計(jì)學(xué)方法、基于距離、基于偏離和基于密度的方法。

基于統(tǒng)計(jì)的方法主要應(yīng)用于科研計(jì)算,這主要是因?yàn)檫@種方法必須事先知道數(shù)據(jù)的分布特征,

從Knorr和Ng開(kāi)始開(kāi)始研究采用無(wú)需任何參數(shù)的方法,并提出使用數(shù)據(jù)點(diǎn)到其最近鄰居的距離和的方法作為異常的量度標(biāo)準(zhǔn)。雖然距離是一種發(fā)現(xiàn)孤立點(diǎn)的有效的無(wú)參數(shù)方法,但需要耗費(fèi)時(shí)間來(lái)計(jì)算距離。

A.Arning和P.Raghavan提出了基于偏離的孤立點(diǎn)探測(cè)的線性方法,但基于偏離的方法中的序列異常的概念并沒(méi)有得到普遍的認(rèn)同。這是因?yàn)樾蛄挟惓Ｔ诟拍钌先匀挥幸欢ǖ娜毕?遺漏了不少的異常數(shù)據(jù)。

基于密度的方法只關(guān)注對(duì)象周圍臨近的密度(最近鄰居數(shù))。關(guān)于它周圍的鄰居具有高密度鄰居的數(shù)據(jù)點(diǎn)不是孤立點(diǎn),具有低密度鄰居的數(shù)據(jù)對(duì)象可能是孤立點(diǎn)。

上文中介紹了當(dāng)前各種孤立點(diǎn)檢測(cè)算法面臨的種種缺陷,并對(duì)其進(jìn)行了比較,發(fā)現(xiàn)基于距離的孤立點(diǎn)檢測(cè)方法在許多方面都優(yōu)于其他方法,在思路上也是正確的。基于距離的方法與基于統(tǒng)計(jì)的方法相比,不需要用戶擁有任何領(lǐng)域知識(shí)。與“序列異常”相比,在概念上更加直觀。

三、基于距離的k-medoids聚類算法與遺傳算法

本文將基于距離的k-medoids聚類算法與遺傳算法相結(jié)合,既可以很好地解決局部最優(yōu)的問(wèn)題,也可以很好地解決孤立點(diǎn)的問(wèn)題,還可以加快遺傳算法的收斂速度,節(jié)約時(shí)間成本。

k-medoids算法與k均值算法相似,但與k均值不同的是k-medoids算法不采用均值作為聚類中心,而是采用數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)作為聚類中心,因此,可以很好地解決k均值對(duì)孤立點(diǎn)敏感的問(wèn)題,極大地提高聚類的精度。但該方法同樣受初始值影響很大,通常不能得到全局最優(yōu)解。

遺傳算法是一種建立在自然選擇原理和自然遺傳機(jī)制上的迭代式自適應(yīng)概率性搜索方法,具有魯棒性強(qiáng)、需要的領(lǐng)域知識(shí)少等優(yōu)點(diǎn),用于孤立點(diǎn)檢測(cè)理論上是可行的。

本文提出的基于k-medoids算法和遺傳算法結(jié)合的孤立點(diǎn)檢測(cè)算法,繼承了遺傳算法的優(yōu)點(diǎn),在一定程度上克服了現(xiàn)有算法的弱點(diǎn)和不足。隨機(jī)產(chǎn)生遺傳算法的第一代并開(kāi)始選擇,然后在每代進(jìn)化中,都用k-medoids算法對(duì)每個(gè)被選擇的個(gè)體進(jìn)行進(jìn)一步的優(yōu)化。也就是說(shuō),在每一代都要對(duì)所有被選中的個(gè)體計(jì)算以其為初始值的k-medoids算法的局部最優(yōu)結(jié)果,并以這些局部最優(yōu)結(jié)果替換掉原來(lái)的個(gè)體并繼續(xù)進(jìn)化,直到達(dá)到最大代數(shù)或者結(jié)果符合要求為止。

該算法的步驟將在以下部分詳細(xì)介紹。

1.對(duì)個(gè)體進(jìn)行編碼和初始種群的生成

本文采用實(shí)數(shù)編碼。染色體中實(shí)數(shù)的數(shù)量代表需要聚類的數(shù)量。初始種群采用隨機(jī)函數(shù)生成,形成一個(gè)初始種群矩陣,其中每一行代表一個(gè)個(gè)體,每一行中的每個(gè)元素代表一個(gè)聚類中心。矩陣的行數(shù)代表種群中個(gè)體的數(shù)目,列數(shù)代表需要聚類的數(shù)目。

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

本文采用均方差作為適應(yīng)度函數(shù),定義如下:

其中, E為所有數(shù)據(jù)對(duì)象與相應(yīng)聚類中心的均方差之和,p為代表對(duì)象空間中的一個(gè)點(diǎn),為聚類的中心對(duì)象,n為中點(diǎn)的個(gè)數(shù)。

3.選擇算子的實(shí)現(xiàn)

遺傳算法使用選擇運(yùn)算(或稱復(fù)制運(yùn)算)來(lái)實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作。本文采用錦標(biāo)賽選擇法。

4.用k-medoids算法進(jìn)行優(yōu)化

用k-medoids算法對(duì)選擇出來(lái)的個(gè)體進(jìn)行優(yōu)化,并用優(yōu)化后的個(gè)體代替原來(lái)的個(gè)體。用k-medoids算法進(jìn)行聚類一般只能得到局部最優(yōu)解,但用其優(yōu)化后的個(gè)體來(lái)代替原來(lái)的個(gè)體便可大大加速遺傳算法的收斂速度,節(jié)約時(shí)間成本。

5.交叉算子的實(shí)現(xiàn)

交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法。交叉率一般取值0.4 - 0.9。單點(diǎn)交叉中,交叉點(diǎn)的范圍為[ 1, Nvar-1] ,Nvar為個(gè)體變量數(shù)目,以該交叉點(diǎn)為分界相互交換變量。

6.變異算子的實(shí)現(xiàn)

遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法,它是必不可少的一個(gè)運(yùn)算步驟。變異率一般取值0. 001- 0. 1。

四、實(shí)驗(yàn)分析

本文的數(shù)據(jù)來(lái)自美國(guó)加州大學(xué)Irvine分校的機(jī)器學(xué)習(xí)庫(kù)(the UCI Irvine Machine Learning Repository),選擇德國(guó)信用數(shù)據(jù)集為研究對(duì)象,該數(shù)據(jù)集包含20個(gè)屬性,本研究截取前100條數(shù)據(jù),采用k均值算法、k-medoids算法和本文研究的新算法分別對(duì)數(shù)據(jù)集進(jìn)行了聚類分析,實(shí)驗(yàn)結(jié)果見(jiàn)表1 (本結(jié)果只顯示包含孤立點(diǎn)的類,其中的數(shù)字代表數(shù)據(jù)對(duì)象的序號(hào))。

從表可以看出,在聚類時(shí)k均值算法無(wú)法把孤立點(diǎn)分離出來(lái),而k-medoids算法和本文所研究的算法都可以把孤立點(diǎn)分離出來(lái)。從衡量聚類效果的重要指標(biāo)均方差值的大小來(lái)看,在存在孤立點(diǎn)的時(shí)候, k-medoids算法比k均值算法要好,而新算法顯然優(yōu)于前面兩個(gè)算法。

五、結(jié)論

本文比較了四種孤立點(diǎn)檢測(cè)方法,通過(guò)分析發(fā)現(xiàn)基于距離的孤立點(diǎn)檢測(cè)方法在許多方面都優(yōu)于其他方法,在思路上也是正確的。基于距離的k-medoids算法可有效檢測(cè)孤立點(diǎn),但容易陷入局部最優(yōu)。將k-medoids算法與遺傳算法相結(jié)合,既可以很好地解決局部最優(yōu)的問(wèn)題,也可以很好地解決孤立點(diǎn)的問(wèn)題,還可以加快遺傳算法的收斂速度,節(jié)約時(shí)間成本。應(yīng)用該算法可以有效地檢測(cè)孤立點(diǎn),即商業(yè)銀行的異常客戶,對(duì)風(fēng)險(xiǎn)進(jìn)行有效地預(yù)警。

參考文獻(xiàn):

[1]Hawkins DM.Identification of Out1iers.Chapman and Hal1.London.1980

篇9

關(guān)鍵詞：軟件可靠性；神經(jīng)網(wǎng)絡(luò)；遺傳算法

中圖分類號(hào)：TP183文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)28-0181-03

Prediction of Software Reliability Based on Evolutionary Neural Network

ZHANG Gui-yong, SHEN Yuan-long, DING Xiao-guang, WANG Ling

(College of Optoelectronic Engineering,Nanjing University of Posts & Telecommunications,Nanjing 210003,China)

Abstract: It is more precise using neural network to predict software reliability than the model of NHPP. The structure of neural network designs by experienced experts. The author uses genetic algorithm to optimize the structure of neural network and solves this problem. The evolutionary neural network can effectively improve the ability of prediction in precision and accurate.

Key words: software reliability; neural network; genetic algorithm

1 軟件可靠性

軟件可靠性被定義為：“在一段時(shí)間內(nèi)軟件正常運(yùn)行的概率”。軟件可靠性模型對(duì)于軟件可靠性的估測(cè)起著核心的作用。而對(duì)于軟件質(zhì)量保證有直接意義的模型，是那些它們的參數(shù)能夠以軟件故障發(fā)生的歷史預(yù)測(cè)軟件將來(lái)故障發(fā)生的行為，軟件可靠性模型是這種思想的體現(xiàn)。

到目前為止，世界上大約已公開(kāi)發(fā)表了一百多個(gè)軟件可靠性模型，基本上被分為兩類：參數(shù)型軟件可靠性模型和數(shù)據(jù)驅(qū)動(dòng)型軟件可靠性增長(zhǎng)模型。前者主要有Musa的執(zhí)行時(shí)間模型、Goel-Okumoto模型、J-M模型、貝葉斯模型等等。這種模型的主要缺點(diǎn)是：預(yù)測(cè)的數(shù)據(jù)是在自己模型的假設(shè)前提下實(shí)現(xiàn)的，每個(gè)模型都有自己的假設(shè)前提，導(dǎo)致模型應(yīng)用的局限性。后者主要指用神經(jīng)網(wǎng)絡(luò)去預(yù)測(cè)軟件可靠性模型，這種模型沒(méi)有前提、假設(shè)。輸入的是歷史錯(cuò)誤數(shù)據(jù)，提高了預(yù)測(cè)的精度。Karunanithi.whitley&Malaiya在1992年的論文中已證明數(shù)據(jù)驅(qū)動(dòng)型比參數(shù)型有著更好的預(yù)測(cè)精度。

2 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)是采用BP算法的神經(jīng)網(wǎng)絡(luò)的統(tǒng)稱。目前在人工神經(jīng)網(wǎng)絡(luò)實(shí)際應(yīng)用中，絕大部分采用BP網(wǎng)絡(luò)和它的變化形式，它是前向網(wǎng)絡(luò)的核心部分。

2.1 BP網(wǎng)絡(luò)的結(jié)構(gòu)

BP神經(jīng)網(wǎng)絡(luò)有三層，分別為：輸入層、隱藏層和輸出層（見(jiàn)圖1），其中隱藏層的層數(shù)理論上可以為任意值。

■

圖1 BP網(wǎng)絡(luò)模型結(jié)構(gòu) 圖2 三層BP網(wǎng)絡(luò)模型

2.2 BP算法

BP神經(jīng)網(wǎng)絡(luò)參數(shù)傳遞有兩個(gè)過(guò)程：一個(gè)為輸出參數(shù)的順傳播，另一個(gè)為誤差的逆?zhèn)鞑ァ＜僭O(shè)一個(gè)三層的BP神經(jīng)網(wǎng)絡(luò)（見(jiàn)圖2）網(wǎng)絡(luò)權(quán)值（Wij Tli）閾值為θ。則

1) 輸出的順傳播

隱節(jié)點(diǎn)：■ 其中■

輸出節(jié)點(diǎn)：■其中■

2) 誤差的逆?zhèn)鞑?/p>

誤差：

■

輸出節(jié)點(diǎn)權(quán)值修正值：

■

令δl=-(Tl-Ol)f'(netl) 則■

隱節(jié)點(diǎn)權(quán)值修正值：

■

令■ 則 ■

由于權(quán)值的修正正比于誤差函數(shù)沿梯度下降，所以有：

Tli=ηδlY Wij=ηδi'Xj其中η為修正參數(shù)。

對(duì)閾值的修正過(guò)程同對(duì)權(quán)值的修正過(guò)程，推倒的結(jié)果為：

輸出節(jié)點(diǎn)：θl(k+1)=θl(k)+ηδl

隱節(jié)點(diǎn)： θi(k+1)=θi(k)+η'δi'

2.3 傳遞函數(shù)

在BP神經(jīng)網(wǎng)絡(luò)中經(jīng)常使用對(duì)數(shù)S形函數(shù)、正切函數(shù)和線性函數(shù)作為神經(jīng)元的傳遞函數(shù)。

3 遺傳算法

遺傳算法(GA)是由美國(guó)科學(xué)家Holland提出來(lái)的，它的主要優(yōu)點(diǎn)是簡(jiǎn)單、魯棒性強(qiáng)、需要解決的問(wèn)題越復(fù)雜，目標(biāo)越不明確，優(yōu)越性越大。它模擬自然界適者生存，優(yōu)勝劣汰的進(jìn)化原則，將問(wèn)題的解表示成染色體(chromosome)，在計(jì)算機(jī)編程時(shí)，通常用二進(jìn)制碼串表示，每個(gè)碼稱為一個(gè)基因，每個(gè)染色體代表問(wèn)題的一個(gè)解。一群染色體構(gòu)成一個(gè)群體或種群，他是GA搜索的空間。在搜索過(guò)程中，用適應(yīng)度函數(shù)(fitness function) 來(lái)評(píng)價(jià)每個(gè)染色體的優(yōu)劣，其值越大（適應(yīng)度越大），相應(yīng)染色體代表的解越優(yōu)。選擇適應(yīng)度大的染色體進(jìn)行再生(reproduction)，通過(guò)交換(crossover) 、變異(mutation) 兩種操作產(chǎn)生新的一代更適應(yīng)環(huán)境的染色體群，這樣一代一代地不斷進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境地個(gè)體上，求得問(wèn)題的最優(yōu)解。適應(yīng)度函數(shù)的選擇能有效的指導(dǎo)搜索空間沿著面向優(yōu)化參數(shù)組合方向，逐步逼近最佳參數(shù)組合，而不會(huì)導(dǎo)致不收斂或陷入局部最優(yōu)。

算法流程如下：

1) 編碼所要解決的問(wèn)題。

2) 隨機(jī)生成N個(gè)個(gè)體，形成初始染色體群體。

3) 計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度值。

4) 計(jì)算群體的平均適應(yīng)度，把每個(gè)染色體的適應(yīng)度歸一化。

5) 依據(jù)歸一化后的染色體適應(yīng)度值，賦給每個(gè)染色體一個(gè)生存概率，按這個(gè)概率選擇n（n

6) 用新的染色體代替原來(lái)的2n個(gè)染色體，形成新的種群。

7) 若滿足中止條件，則解碼適應(yīng)度最大的染色體得到問(wèn)題的解，否則返回步驟2)繼續(xù)進(jìn)行。

4 用遺傳算法去優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)

在用神經(jīng)網(wǎng)絡(luò)去預(yù)測(cè)軟件可靠性的過(guò)程中，神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)往往是預(yù)先不能獲得的。本文提出了用遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的方法。論文假設(shè)神經(jīng)網(wǎng)絡(luò)有四個(gè)輸入一個(gè)輸出中間的隱層為待優(yōu)化的部分。

4.1 個(gè)體的編碼

我們用2進(jìn)制編碼方法對(duì)結(jié)構(gòu)進(jìn)行編碼，每個(gè)隱層用4位二進(jìn)制碼來(lái)代表，則隱層的神經(jīng)元的個(gè)數(shù)為0－15個(gè)，當(dāng)個(gè)數(shù)為零時(shí)代表該層不存在，我們可以假設(shè)隱層有二層、三層或任意層，則個(gè)體的編碼為8、12或更多個(gè)二進(jìn)制碼。

4.2 適應(yīng)度函數(shù)

在遺傳算法中使用適應(yīng)度來(lái)度量群體中的個(gè)體在優(yōu)化計(jì)算中能達(dá)到或接近于最優(yōu)解的優(yōu)良程度。本文采用的適應(yīng)度函數(shù)為：

■

其中p為可靠性樣本用于訓(xùn)練的數(shù)目，■i是神經(jīng)網(wǎng)絡(luò)的輸出值，xi為樣本值。

4.3 控制參數(shù)的選取

遺傳算法中控制參數(shù)的選擇非常關(guān)鍵，參數(shù)選取的不同對(duì)遺傳算法的性能產(chǎn)生較大的影響。這些參數(shù)有群體規(guī)模N、交叉概率Pc、變異概率Pm等等。交叉概率太大使搜索走向隨機(jī)化，交叉概率越小，搜索的速度就越慢，太小時(shí)則陷入停滯，一般Pc為0.4－0.99。變異概率越大，容易破壞好的模式，是遺傳算法近似隨機(jī)搜索，變異概率太小，對(duì)產(chǎn)生新個(gè)體和抑制早熟現(xiàn)象的能力就會(huì)較差，一般為0.001－0.1。群體規(guī)模的大小直接影響到遺傳算法的收斂性或計(jì)算效率。規(guī)模過(guò)小容易收斂到局部最優(yōu)解；規(guī)模過(guò)大，會(huì)造成計(jì)算速度降低。群體規(guī)模可以根據(jù)具體情況在10－200之間選擇。

4.4 流程圖(見(jiàn)圖3)

4.5 泛化處理

在BP網(wǎng)絡(luò)的訓(xùn)練中往往會(huì)出現(xiàn)這樣的情況，當(dāng)網(wǎng)絡(luò)的訓(xùn)練誤差很小的時(shí)候，一個(gè)新的輸入會(huì)使網(wǎng)絡(luò)的訓(xùn)練誤差增大，這是因?yàn)榫W(wǎng)絡(luò)記憶了已被訓(xùn)練的樣本，而對(duì)新的輸入沒(méi)有良好的泛化能力。規(guī)則化調(diào)整方法是通過(guò)調(diào)整網(wǎng)絡(luò)的性能函數(shù)，來(lái)增強(qiáng)網(wǎng)絡(luò)的泛化能力。普通的BP神經(jīng)網(wǎng)絡(luò)都采用網(wǎng)絡(luò)誤差的均方根之和作為性能函數(shù)。如下式 ：

■

其中 ei ti ai分別表示第i個(gè)訓(xùn)練樣本的訓(xùn)練誤差、目標(biāo)函數(shù)和網(wǎng)絡(luò)輸出。而調(diào)整后的網(wǎng)絡(luò)函數(shù)如下：

msereg=γmse=(1-γ)msw

γ是性能參數(shù) ■

使用該函數(shù)可以減少網(wǎng)絡(luò)的有效權(quán)值和閾值，并且使網(wǎng)絡(luò)的訓(xùn)練輸出更加平滑，從而增強(qiáng)網(wǎng)絡(luò)的泛化性能。

4.6 數(shù)據(jù)預(yù)處理

在我們開(kāi)始試驗(yàn)之前，還得對(duì)原始數(shù)據(jù)進(jìn)行如下處理：■，x為原始數(shù)據(jù)，=xmax-xmin。這樣數(shù)據(jù)就被調(diào)整到0.1－0.9之間。在預(yù)測(cè)結(jié)束后用■將得到的數(shù)據(jù)調(diào)整到原始數(shù)據(jù)。

5 進(jìn)化神經(jīng)網(wǎng)絡(luò)對(duì)軟件可靠性預(yù)測(cè)實(shí)例

為了證明本文提出的方法優(yōu)于直接用神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)，這里我們找到了一組軟件可靠性的數(shù)據(jù)，這組數(shù)據(jù)來(lái)源于一個(gè)中等項(xiàng)目軟件測(cè)試過(guò)程（見(jiàn)表1）。

在進(jìn)行仿真之前我們還得定義幾個(gè)指標(biāo)來(lái)代表預(yù)測(cè)的精度。

■其中■i為預(yù)測(cè)的數(shù)據(jù)，xi為實(shí)際的數(shù)據(jù)。

■其中■i為預(yù)測(cè)的數(shù)據(jù)，xi為實(shí)際的數(shù)據(jù)，n為待預(yù)測(cè)的數(shù)據(jù)量。

我們用前12組數(shù)據(jù)對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，后四組作為待預(yù)測(cè)的數(shù)據(jù)，普通神經(jīng)網(wǎng)絡(luò)采用3－7－1的結(jié)構(gòu)，優(yōu)化的結(jié)果神經(jīng)網(wǎng)絡(luò)采用2－6－2－1的結(jié)構(gòu)。預(yù)測(cè)結(jié)果的RE和AE比較（見(jiàn)表2）。

對(duì)數(shù)據(jù)的擬合度如圖4所示 。

6 結(jié)論

篇10

關(guān)鍵詞：排課；排課管理；遺傳算法

中圖分類號(hào)：G647 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2016）15-0011-02

一、國(guó)內(nèi)外研究動(dòng)態(tài)

（一）背景與意義

排課管理作為教育教學(xué)中的重要環(huán)節(jié)，其目的是為教師、學(xué)生安排合適的教學(xué)地點(diǎn)與時(shí)間。排課管理是教學(xué)管理中一項(xiàng)復(fù)雜的工作，只有合理安排好了課程時(shí)間與地點(diǎn)，才能保障教學(xué)工作的有序進(jìn)行[1]。關(guān)于教學(xué)排課管理研究已經(jīng)有近四十多年之久，在理論以及實(shí)際應(yīng)用中都取得了豐碩的成果。然而，現(xiàn)有教學(xué)排課管理在面對(duì)復(fù)雜教學(xué)排課環(huán)境及大規(guī)模教學(xué)排課管理時(shí)存在的問(wèn)題至今尚未完全解決，特別是隨著各大高校學(xué)生的大力擴(kuò)招，給教學(xué)排課管理帶來(lái)了巨大的壓力。在國(guó)內(nèi)，目前教學(xué)排課管理采用系統(tǒng)自動(dòng)排課與人工排課的方式[2]，系統(tǒng)首先進(jìn)行自動(dòng)排課，然后找出存在沖突的課程進(jìn)行人工調(diào)整，并根據(jù)經(jīng)驗(yàn)判斷將課程安排到合理的位置。由于人工調(diào)整缺乏理論指導(dǎo)與數(shù)據(jù)模型，使教學(xué)排課管理具有一定的盲目性，因此需要利用計(jì)算機(jī)技術(shù)與合適的排課算法解決人工干預(yù)的問(wèn)題，這對(duì)于推動(dòng)教學(xué)的發(fā)展也起到了非常重要的作用[3]。排課管理通過(guò)將各個(gè)年級(jí)開(kāi)設(shè)的課程匯總，然后根據(jù)學(xué)校全年教學(xué)計(jì)劃任務(wù)和教學(xué)資源定制各個(gè)年級(jí)課程表，從而達(dá)到優(yōu)化教學(xué)資源的目的，通過(guò)設(shè)計(jì)一個(gè)有效的智能排課系統(tǒng)，減輕教學(xué)管理工作者的勞動(dòng)強(qiáng)度，提高教學(xué)工作效率，為規(guī)范教學(xué)管理工作流程提供技術(shù)支持，從而保障學(xué)校的正常教學(xué)秩序。排課管理是非常復(fù)雜而煩瑣的管理過(guò)程，在學(xué)校規(guī)模大、約束（條件）復(fù)雜以及規(guī)律不斷變化的環(huán)境下，目前許多排課軟件與排課算法無(wú)法滿足實(shí)際需求，為滿足學(xué)校排課需求及師生對(duì)教學(xué)資源利用的要求，規(guī)避資源限制等約束條件，本研究對(duì)江蘇信息學(xué)院排課管理進(jìn)行了研究分析以滿足學(xué)院實(shí)際排課需求。

（二）國(guó)內(nèi)外研究現(xiàn)狀和發(fā)展態(tài)勢(shì)

排課問(wèn)題是教育界非常關(guān)心的問(wèn)題，對(duì)于排課問(wèn)題研究主要集中在理論、啟發(fā)式搜索技術(shù)應(yīng)用求解、系統(tǒng)求解設(shè)計(jì)、遺傳算法應(yīng)用求解上。在國(guó)外，排課算法起源于20世紀(jì)50年代，1963年Gotlieb提出“排課算法數(shù)學(xué)模型”這一概念，標(biāo)志著排課算法研究進(jìn)入了科學(xué)的殿堂。自此以后，許多學(xué)者也參與到了排課算法研究中，早期的大多數(shù)求解都存在諸多問(wèn)題，無(wú)法完全應(yīng)用于實(shí)際生活中，如Ferland、吳金榮等人將排課問(wèn)題化成整數(shù)規(guī)劃來(lái)求解，但這種方法計(jì)算量巨大，只能應(yīng)用到小數(shù)據(jù)量環(huán)境中，無(wú)法適用于實(shí)際應(yīng)用中。而何永太和胡順仁等人則采用圖論中的染色問(wèn)題進(jìn)行排課研究，由于圖論的染色問(wèn)題本身也是NP完全問(wèn)題，其計(jì)算比較復(fù)雜，也只能應(yīng)用于特殊條件中，因此至今沒(méi)有一個(gè)切實(shí)可行的算法。到了20世紀(jì)90年代，國(guó)外對(duì)于排課算法研究非常活躍，提出了一種新的課表編排方法，它以“人”為單位，利用格朗日松弛法及分支定界技術(shù)進(jìn)行排課算法研究。而在我國(guó)，對(duì)于排課算法的研究卻要始于20世紀(jì)80年代，從模擬手工排課到運(yùn)用人工智能，逐步發(fā)展，取得了一定的成績(jī)。隨著人工智能的發(fā)展，開(kāi)始在排課算法中引入了生物界進(jìn)化思想和遺傳算法，依靠其超強(qiáng)的并行搜索能力和在解決優(yōu)化問(wèn)題中表現(xiàn)出來(lái)的優(yōu)勢(shì)，已經(jīng)被廣泛使用。特別是生物進(jìn)化思想和遺傳思想的出現(xiàn)，出現(xiàn)了基于遺傳算法來(lái)求解排課問(wèn)題。本課題就是利用了基于遺傳算法進(jìn)行排課算法設(shè)計(jì)，并結(jié)合J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA技術(shù)實(shí)現(xiàn)系統(tǒng)開(kāi)發(fā)設(shè)計(jì)。

二、理論意義及實(shí)用價(jià)值

隨著社會(huì)經(jīng)濟(jì)的發(fā)展，高校規(guī)模的擴(kuò)大增加了教學(xué)管理的難度及造成了教學(xué)資源的相對(duì)緊張，但顯然這些學(xué)校的師資、教學(xué)設(shè)備和其他教學(xué)資源都不能及時(shí)有效地進(jìn)行補(bǔ)充，所以無(wú)法適應(yīng)教學(xué)發(fā)展的需求，這其中排課問(wèn)題就尤為突出。不僅在普通高校出現(xiàn)了以上問(wèn)題，在高職院校也出現(xiàn)同樣的問(wèn)題。江蘇信息職業(yè)技術(shù)學(xué)院經(jīng)過(guò)六十多年的艱苦創(chuàng)業(yè)，現(xiàn)有全日制在籍學(xué)生共一萬(wàn)多人，學(xué)校形成了中高職銜接、職成教一體的辦學(xué)體系。目前采用的是2004年引進(jìn)學(xué)院的教務(wù)排課系統(tǒng)，經(jīng)過(guò)十年的運(yùn)營(yíng)，技術(shù)已經(jīng)落后，不能很好地滿足日常教學(xué)工作的需要。本文也是基于這個(gè)原因，意在編寫(xiě)一套適用于江蘇信息學(xué)院的自動(dòng)排課系統(tǒng)。

三、目標(biāo)、研究?jī)?nèi)容和研究方法

（一）工作目標(biāo)與任務(wù)

結(jié)合江蘇信息學(xué)院的現(xiàn)實(shí)，再造教務(wù)教學(xué)管理的管理流程，使它更加科學(xué)化、規(guī)范化。據(jù)此建立一套教學(xué)制管理制度，不但要適合江蘇信息學(xué)院的現(xiàn)實(shí)，還要完成選課排課的信息化與自動(dòng)化。最后設(shè)計(jì)一個(gè)排課系統(tǒng)，與現(xiàn)有運(yùn)行的排課系統(tǒng)相比，該系統(tǒng)支持全學(xué)分制，這是它最明顯的優(yōu)點(diǎn)。它不僅能夠減少各級(jí)教學(xué)管理人員的工作量，方便檢索查詢與管理，還能夠形成先進(jìn)的教學(xué)理念和管理制度。

（二）研究?jī)?nèi)容和研究方法

本文主要包括以下工作：重點(diǎn)分析、設(shè)計(jì)及研究排課管理系統(tǒng)。（1）對(duì)目前許多高校的教務(wù)管理流程進(jìn)行重點(diǎn)分析，找出手工排課的主要問(wèn)題和編制課表的基本原則，分析排課需求。組織學(xué)生評(píng)價(jià)教師及他們所授的課程，最優(yōu)組合教師和課程，充分做好排課的相關(guān)準(zhǔn)備工作；（2）從多方面分析系統(tǒng)需求，主要包括系統(tǒng)開(kāi)發(fā)背景、可行性論證、主要業(yè)務(wù)流程分析、系統(tǒng)功能需求分析、數(shù)據(jù)模型分析等，確定江蘇信息學(xué)院排課管理系統(tǒng)實(shí)現(xiàn)的必要性及可行性；（3）全面設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)的各個(gè)功能模塊，確定本排課系統(tǒng)的主要內(nèi)容：其中包含系統(tǒng)管理、原始數(shù)據(jù)、教室管理、教學(xué)任務(wù)管理、排課管理、和課表管理等六大模塊。同時(shí)，詳細(xì)設(shè)計(jì)各個(gè)功能模塊；（4）利用J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA等技術(shù)進(jìn)行具體的程序開(kāi)發(fā)。同時(shí)，在后臺(tái)數(shù)據(jù)庫(kù)方面，選擇SQL Server 2008作為管理系統(tǒng)；（5）關(guān)于算法研究方面，本排課系統(tǒng)完整討論了排課問(wèn)題的主要影響要素、約束條件、以及排課系統(tǒng)中遺傳算法的設(shè)計(jì)及核心算法等問(wèn)題。

四、關(guān)鍵技術(shù)問(wèn)題

（一）創(chuàng)新之處

首先，對(duì)于排課問(wèn)題的影響要素、主要約束條件、求解目標(biāo)和難點(diǎn)，本系統(tǒng)進(jìn)行了完整的討論，提出了排課問(wèn)題求解方法的總體框架和技術(shù)路線；其次，根據(jù)江蘇信息學(xué)院的實(shí)際情況，從排課系統(tǒng)的需求分析開(kāi)始，建立排課系統(tǒng)的數(shù)據(jù)模型及其體系結(jié)構(gòu)。給出排課系統(tǒng)中遺傳算法的設(shè)計(jì)，核心算法的實(shí)現(xiàn)方法和步驟；最后，說(shuō)明本排課系統(tǒng)的總體設(shè)計(jì)方案、各模塊的功能結(jié)構(gòu)及相應(yīng)的實(shí)現(xiàn)方法。

（二）擬解決的關(guān)鍵問(wèn)題

影響排課的因素很多，總結(jié)起來(lái)分為以下兩大類：一是參與教學(xué)活動(dòng)的主體。主要是指教師、班級(jí)、課程，教學(xué)等主體對(duì)象因素，這些因素在每個(gè)學(xué)期都是可能變動(dòng)的，是動(dòng)態(tài)的。它們是需要給予分配資源的對(duì)象。而在排課過(guò)程中，這些主體對(duì)象必須在空間和時(shí)間上都保證獨(dú)立，而不是沖突的。在排課過(guò)程中，最主要的問(wèn)題就是解決這些主體對(duì)象因素在空間和時(shí)間上的沖突；二是教學(xué)資源對(duì)象因素。主要指被分配的資源，如教室、教學(xué)時(shí)間等因素，這些資源往往都是有限的。并且教學(xué)資源都是分種類的，如教室有大教室、小教室之分，類型有多媒體教室、普通教室、語(yǔ)音室、實(shí)驗(yàn)室之分。其他因素還包括教學(xué)計(jì)劃的不同、教師個(gè)人的選擇喜好等。

五、可行性論證

（一）目標(biāo)可行性論證

通過(guò)校園網(wǎng)構(gòu)建一個(gè)交流平臺(tái)來(lái)連接教師、學(xué)生和教學(xué)管理部門，利用并結(jié)合J2EE技術(shù)、Struts技術(shù)、MVC結(jié)構(gòu)設(shè)計(jì)、SOA技術(shù)實(shí)現(xiàn)B/S結(jié)構(gòu)的數(shù)據(jù)信息管理目標(biāo)。

（二）技術(shù)可行性論證

軟件方面，本系統(tǒng)結(jié)合了物聯(lián)網(wǎng)技術(shù)，采用目前最常用的J2EE技術(shù)與SQL相結(jié)合的模式進(jìn)行開(kāi)發(fā)，數(shù)據(jù)庫(kù)服務(wù)器選用Microsoft的SQL Server 2008作為數(shù)據(jù)庫(kù)，此數(shù)據(jù)庫(kù)能夠處理大量的數(shù)據(jù)，不僅能夠保持?jǐn)?shù)據(jù)的完整性，而且還能夠提供多項(xiàng)高級(jí)管理功能。由此可見(jiàn)，系統(tǒng)的軟件開(kāi)發(fā)平臺(tái)條件已經(jīng)滿足。在硬件方面，江蘇信息學(xué)院計(jì)算機(jī)容量越來(lái)越大，可靠性越來(lái)越高，硬件平全能夠滿足系統(tǒng)開(kāi)發(fā)和系統(tǒng)運(yùn)行的需要。

（三）成本可行性論證

本系統(tǒng)只需花費(fèi)少量的經(jīng)費(fèi)，廣大教務(wù)管理人員就能從繁重的手工排課工作中解脫出來(lái)，他們可以把更多的精力投入到其他教學(xué)管理工作中，提高工作效率；同時(shí)也可以使廣大師生通過(guò)校園網(wǎng)查詢到相關(guān)的個(gè)人教學(xué)信息，此方式成本低，既方便又經(jīng)濟(jì)。

（四）社會(huì)可行性論證

目前，江蘇信息學(xué)院校園網(wǎng)絡(luò)已經(jīng)覆蓋了整個(gè)教學(xué)區(qū)和學(xué)生區(qū)，學(xué)院各個(gè)教學(xué)部門、行政部門和廣大學(xué)生的上網(wǎng)需求都可以滿足。尤其是本學(xué)院已經(jīng)通過(guò)光纖接入的方式與Internet連接，能夠很好地實(shí)現(xiàn)校內(nèi)用戶之間以及校內(nèi)用戶與校外用戶之間的聯(lián)系。

綜上所述，面對(duì)江蘇信息學(xué)院教務(wù)信息處理需求的日益增長(zhǎng)，開(kāi)發(fā)一個(gè)教務(wù)排課管理系統(tǒng)來(lái)應(yīng)對(duì)這種需求，為學(xué)生和教學(xué)管理人員提供快捷方便的雙向選擇服務(wù)，提高排課管理工作的效率，是非常有必要的。

參考文獻(xiàn)：

[1]劉真.基于URP的地方高校數(shù)字校園建設(shè)應(yīng)用研究[D].山東大學(xué)碩士學(xué)位論文，2008.