導語：如何才能寫好一篇遺傳算法論文，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇1

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

論文關鍵詞：旅行商問題遺傳算法基因庫多重搜索策略

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

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

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

1單親演化過程

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

1.1TSP編碼表示

設n個城市編號為1,2,…,n,為一條可行路徑,Pk=Vk1Vk2…Vkn為一條可行路徑,它是1,2,…,n的一個隨機排列,其含意是第k條路徑起點城市是Vk1,最后一個城市是Vkn,則第k條環路的總長度可以表示為:

其中,d(Vki,Vkj)表示城市Vki與城市Vkj之間的距離。在算法中環路Pk的總長d(Pk)用來評價個體的好壞[9]。適應度函數取路徑長度d(Pk)的倒數,f(Pk)=1/d(Pk)。

1.2構建TSP基因庫

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

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單親演化算法

單親演化算法是利用遺傳算法的優勝劣汰的遺傳特性,在單個染色體內以基因重組的方式,使子代在滿足TSP問題的限定條件下進行繁衍,然后保留適應度高的染色體種群,達到優化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯位和基因段倒轉三種操作來實現。基因換位操作是將親代的染色體基因進行對換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式。基因段錯位操作是隨機確定基因段,也隨機選定錯位位置,整段錯移。基因段倒轉操作則是隨機地確定倒轉基因段的起止位置,倒轉操作是對該段內基因按中垂線作鏡面反射,若段內基因數為奇數時,則中位基因不變。單親演化時可以是單個操作用于單個父代,也可以是幾種操作同時采用。為了編程方便,文中采用基因段倒轉操作。

2群體演化過程

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

2.1交叉算子

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

P1=(12|3456|789)P2=(98|7654|321)

將P2的區域加到P1的前面或后面,P1的區域加到P2的前面或后面,得

M1=(7654|123456789)

M2=(3456|987654321)

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

S1=(765412389)S2=(345698721)

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

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

2.2局部啟發式算子

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

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

2.3選擇機制和收斂準則

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

遺傳算法求TSP問題如果不設定終止條件,其演化過程將會無限制地進行下去。終止條件也稱收斂準則,因為多數最優化問題事先并不了解最優的目標函數值,故無法判斷尋優的精度。該文采用如下兩條收斂準則:在連續K1代不再出現更優的染色體;優化解的染色體占種群的個數達K2的比例以上。當兩準則均滿足時,則終止運算,輸出優化結果和對應的目標函數值。由數值實驗表明,添加第2條準則之后,全局最優解的出現頻率將大為提高。

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

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

3實驗結果與分析

該文的GB—MGA算法由C#編程實現,所有的結果都是在P42.0G微機上完成,并進行通用的TSP庫實驗,選用了具有一定代表性的TSP實例,并把該算法和其他算法做了一個對比。為了減少計算量,程序中的數據經過四舍五入整數化處理,與實數解有一定的偏差,下面給出圖Kroa100的示例。

為了證明該文提出的GB—MGA算法的有效性,將該文算法與典型的遺傳算法GA、單親遺傳算法PGA以及文[5]中楊輝提出的Ge—GA(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都進行了一個對比。

實驗結果證明,該文算法的求解質量要優于GA、PGA、MMGA算法,而求解速度方面則優于Ge—GA算法,特別是對于大規模城市的TSP問題求解效果尤其明顯,具有快速收斂的特性。Ge—GA算法對于中等城市規模的TSP實例求解,其運算時間就大幅度增加,如果把該算法用于求解大規模和超大規模TSP問題,那么時間上的代價就讓人無法忍受。而該文的GB—MGA算法在單親遺傳演化中就使用了基因庫中的優質基因,使得單個個體的進化速度大大提高,從而為進一步的演化提供了條件,群體演化過程的選擇機制和收斂準則的恰當選取使得算法在注重了求解質量的同時兼顧了算法的效率。

4結束語

篇2

【關鍵詞】自動導航小車；路徑規劃；免疫遺傳算法；疫苗

1、引言

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

2、環境信息建模

對AGV進行路徑規劃前，應解決對其環境信息的描述即環境建模問題。為此，作以下假設[3]：

（1）AGV在二維平面中運動，不考慮其高度方向的信息；（2）規劃環境的邊界及其內所有障礙物（妨礙AGV運動的所有物體）用凸多邊形表示。（3）考慮到AGV的大小等，對環境邊界進行縮小和對障礙物進行擴大時，其縮放量為AGV外形最大尺寸的一半。即AGV為“點機器人”。

至此，AGV的工作空間可描述為：工作平面和障礙物群{Oi|i=1，2…N}。具體到其個障礙物Oi，可描述為Oi={頂點1坐標（xi1， yi1），….. 頂點n坐標（xni， yni）}。為方便數據處理，對多邊形頂點沿順時針方向編號。起點為S，終點為E。工作平面可表示為矩形{（Xmin，Ymin），（Xmax，Ymax）}。

設在AGV的工作環境中有n個已知的障礙物Oi（i=1，2，...，n），對應的頂點數為Si，頂點坐標為（x（i，j），y（i，j））（j=1，2，…Si）。為描述AGV工作環境中的障礙物，采用Dm×m矩陣對環境信息進行描述，其中，m為障礙物頂點總數。定義d（i，j）為：

3、免疫遺傳算法設計

3.1路徑編碼方式

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

3.2適應度函數

在對AGV進行路徑規劃時，其優化目標為在所有可能的運動路徑Xp={Xkp|k=1， 2，…，N}中找出一條最優或次優路徑。設某個體Xkp的路徑長度Dk為：

其中dj為Xk中各直線段軌跡長。因為AGV由一直線軌跡向另一直線軌跡過渡時運動速度的變化會影響其運行時間，因此，在對所選路徑進行評價時，除考慮其總長度外，可要求路徑中的拐點數盡可能的少或AGV的姿態角變化量盡要能的小。本論文的路徑規劃目標是路徑短且拐點較少。定義適應度函數為：

式中，和為調整系數。這里取=0.8，=0.2。N為種群大小，Dj為種群中第j個體的路徑長度，nj為第j個體路徑拐點數。

3.3算法的實現

在進行路徑規劃時，首先判斷AGV從起點向終點沿直線軌跡運動時是否穿越障礙物。若無障礙物，兩點間的連線為AGV的最佳運動路徑，無須進行路徑規劃。否則進行路徑規劃。

免疫遺傳算法中，疫苗是根據待求問題的先驗知識構造的最佳個體基因的估計，抗體是根據疫苗將某個體基因進行修正后所得到的新個體。論文所設計的基于免疫遺傳算法的路徑規劃過程如下：

（1）根據問題從記憶抗體庫中提取問題的抗體P得到初始種群 ，不足N個時在AGV起始點和目標點之間隨機產生N-P條路徑。個體的產生方法是：以包圍AGV的起點、終點和所有在線障礙物的最小矩形為規劃區域，在規劃區域內的障礙物頂點個數為M，在線障礙物為m，則染色體的最大長度為M-m。以規劃區域內的障礙物頂點為被選對象，沿一定的條件隨機選取基因位上的基因組成一條染色體，同用樣的方法產生其它染色體以組成群體。

（2）根據先驗知識抽取疫苗H={h1， h2， …， hm}；

（3）計算第p代種群Ak所有個體的適應度，并進行終止進化判斷。

（4）對當前群體Xp進行遺傳算子操作得到子代群體Bp。進行交叉操作時，采用單點交叉。交叉操作時，兩個個體若有相同的基因（而非等位基因）進行交叉操作。當相同基因位不止一個，隨機選擇其一進行交叉；當無相同基因位則不進行交叉。進行變異操作時，從個體中隨機刪除一基因位或隨機選取一基因位插入一新基因位，或在個體中隨機選取一基因位用另一隨機產生的基因位交換。

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

其中，為適應度函數；Tk是單調遞減趨于0的退火溫度控制序列，Tk=ln（T0/k+1），T0=100，p是進化代數[3]。

（6）選擇個體進入新的群體。更新抗體庫，并轉到第（3）步。

4、仿真實驗

仿真是在Matlab6.1上進行的。AGV的工作環境大小為8×6m2，其內有6個形狀各異、排列任意的障礙物（如圖2所示），現欲使AGV從S點無碰撞地運動到E點且使其運動路徑最短，建立如圖4所示的可視圖。其可視矩陣如左圖：

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

由仿真結果知，采用免疫遺傳算法進行路徑規劃時，退化現象基本不會發生，再能很快得到問題的最優解。其原因是，利用免疫遺傳算法對AGV進行路徑規劃，一方面利用了遺傳算法的優點，由于是對編碼進行操作，對問題的依賴性小，且操作是并行進行，優化速度快；同時針對遺傳算在進行交叉和變異操作時是以以概率方式隨機地、缺泛指導性地進行導致問題進化時產生退化的現象，采用適當的指導，彌補了遺傳算法的缺點。利用遺傳免疫算法進行優化，在保證算法收斂的前提下，有效地提高計算速度。利用此法對AGV的路徑進行規劃，比其它的方法更有效。

5、結論

論文主要針對環境建模和路徑搜索兩大問題進行了研究。基于可視圖環境建模方法優點，完成了對環境信息的建模。并結合遺傳和免疫算法的優點設計了具有精英保留策略的基于免疫遺傳算法的AGV路徑規劃方法。通過比較采用遺傳算法、免疫算法和本論文所設計的免疫遺傳算法對AGV進行路徑規劃結果和效率的比較，分析了所提出的基于免疫遺傳算法的AGV路徑規劃方法的優點。仿真結果表明：

A.本論文采用改進的可視圖法對環境信息進行建模，在改變障礙物位置、形狀、大小和AGV的起點及終點的情況下，均可快速構建AGV的環境信息模型。

B.采用本論文所設計的基于免疫遺傳算法的AGV路徑規劃方法對AGV進行路徑規劃，在速度方面優于傳統的免疫算法和遺傳算法，且系統退化現象基本得到消除。

參考文獻

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

[2]沈鳳梅，吳隆.基于改進人工勢場法的移動機器人自主導航和避障研究[J].制造業自動化，2013，35 （12），28-30，39.

[3]李善壽，方潛生，肖本賢.全局路徑規劃中基于改進可視圖法的環境建模[J].華東交通大學學報，2008，25（6），73-77.

作者簡介

篇3

關鍵詞：遺傳算法；肝臟CT圖像；圖像分割；閾值

中圖分類號：TP391文獻標識碼：A文章編號：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)的基本思想來源于Darwin的生物進化論和Mendel的群體遺傳學，該算法最早是由美國Michigan大學的John Holland教授于20世紀70年代創建，之后，遺傳算法的研究引起了國際組織及學者的關注。遺傳算法通過模擬生物的遺傳進化過程形成一種全局優化概率搜索算法，提供了一種求解復雜系統優化問題的通用框架，可以不依賴于問題的具體領域[1]。近年來，遺傳算法已被廣泛應用于函數優化、組合優化、生產調度、自動控制、人工智能、人工生命、機器學習、圖像處理和模式識別等多個領域，具有巨大的發展潛力。本文主要介紹遺傳算法在醫學圖像處理方面的應用。

1 遺傳算法的基本原理

遺傳算法是模擬生物進化和遺傳機制發展起來的一種全局優化、隨機、自適應搜索算法。它模擬了自然界遺傳過程中的繁殖、和變異現象，依據適者生存、優勝劣汰的進化原則，利用遺傳算子（即選擇、交叉和變異）逐代產生優選個體（候選解），最終搜索到適合的個體。

遺傳算法的運算對象是由N個個體所組成的集合，稱為群體。遺傳算法的運算過程是一個群體反復迭代的過程，這個群體不斷地經過遺傳和進化操作，每次按照優勝劣汰的進化原則將適應度較高的個體以更高的概率遺傳到下一代，這樣最終在群體中將會得到一個優良的個體，它將達到或接近于問題的最優解[2]。

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

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

2）初始化種群 隨機產生N個個體組成一個種群，此種群代表一些可能解的集合。GA 的任務是從這些群體出發，模擬進化過程進行優勝劣汰，最后得出優秀的種群和個體，滿足優化的要求。

3）設計適應度函數：將種群中的每個個體解碼成適合于計算機適應度函數的形式，并計算其適應度。

4）選擇：按一定概率從當前群體中選出優良個體，作為雙親用于繁殖后代，一些優良的個體遺傳到下一代群體中，適應度越高，則選擇概率越大。進行選擇的原則是適應性強的優良個體將有更多繁殖后代的機會，從而使優良特性得以遺傳。選擇是遺傳算法的關鍵，它體現了適者生存原則。

5）交叉：交叉操作是遺傳算法中最主要的遺傳操作。對于選中的用于繁殖的每一對個體，隨機選擇兩個用于繁殖下一代的個體的相同位置，在選中的位置實行交換。交叉體現了信息交換的思想。

6）變異：從群體中選擇一個個體，對于選中的個體按一定的概率隨機選擇改變串結構數據中某個串的值，即對某個串中的基因按突變概率進行翻轉。變異模擬了生物進化過程中的偶然基因突變現象，遺傳算法中變異發生的概率很低。對產生的新一代群體進行重新評價、選擇、雜交和變異。

7）終止準則：如此循環往復，使群體中最優個體的適應度和平均適應度不斷提高，直至最優個體的適應度滿足某一性能指標或規定的遺傳代數，迭代過程收斂，算法結束。

2 遺傳算法在圖像分割處理中的應用

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

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

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

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

最大熵分割方法步驟為：

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

其中，與每一個分布相關的熵為：

令: (4)

當該函數取最大值時即為圖像的最佳分割，用此函數作為遺傳算法中的適應度函數。通過遺傳算法的設計步驟，取得最佳閾值，既而對人體肝臟中有病灶組織的CT圖像進行分割，得到下面分割處理實驗結果。

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

圖1 對有病灶肝臟圖像進行分割

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

但由于醫學圖像的復雜性和人體的差異性，對人體同一器官不同狀況的圖像，無法找出一種最為適合的分割方法處理，必須根據具體情況具體分析，針對圖像的特點來選取相應的分割算法，才能較好地解決問題。

參考文獻：

[1] 田瑩,苑瑋琦.遺傳算法在圖像處理中的應用[J].中國圖象圖形學報,2007,12(3):389-396.

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

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

篇4

【關鍵詞】多目標優化 進化算法 遺傳算法 組合算法

中圖分類號：TP18

1引言

大多數多目標優化問題，每個目標函數之間可能是競爭的關系，優化某一個函數的同時，往往以犧牲另一個優化目標為代價，如果將多目標轉化為單目標函數優化時，各優化目標加權值的分配帶有很大的主觀性，必然造成優化結果的單一性，沒有考慮全局優化。而如果將多目標函數利用評價函數法轉化為單目標函數求解，得到的僅僅是一個有效解，所以我們可以考慮直接采用多目標函數的優化方法對多目標進行優化[1-2]。

2多目標優化的發展現狀

在多目標優化問題中，各分目標函數的最優解往往是互相獨立的，很難同時實現最優。在分目標函數之間甚至還會出現完全對立的情況，即某一個分目標函數的最優解卻是另一個分目標函數的劣解。求解多目標優化問題的關鍵，是要在決策空間中尋求一個最優解的集合，需要在各分目標函數的最優解之間進行協調和權衡，以使各分目標函數盡可能達到近似最優。多目標優化問題不存在唯一的全局最優解，而是要尋找一個最終解。得到最終解需要通過各種算法來實現，如進化算法、模擬退火算法、蟻群算法、粒子群算法和遺傳算法等[3-4]。由于各種算法存在應用領域的差異和自身缺陷，人們也提出了一些改進算法和組合算法。

2.1進化算法

進化算法 （Evolutionary Algorithms，EA）是一種仿生優化算法，主要包括遺傳算法、進化規劃、遺傳規劃和進化策略等。根據達爾文的“優勝劣汰、適者生存”的進化原理及盂德爾等人的遺傳變異理論，在優化過程中模擬自然界的生物進化過程與機制，求解優化與搜索問題。進化算法具有自組織、自適應、人工智能、高度的非線性、可并行性等優點[5]。

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

雖然基于Pareto最優解的多目標進化算法可以得到較好分布的最優解集，但如何保證算法具有良好的收斂性仍是一個熱點問題。

2.2模擬退火算法

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

2.3蟻群算法

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

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

其次，螞蟻算法需要較長的搜索時間、容易出現早熟停滯現象。文獻[11]提出了具有免疫能力的螞蟻算法和蟻群遺傳算法，提高算法的尋優能力和尋優效率。

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

2.4粒子群算法

粒子群優化算法（Particle Swarm Optimization，PSO）是在1995年由美國社會心理學家Kennedy和電氣工程師Eberhart共同提出的，源于對鳥群覓食過程中的遷徙和聚集的模擬。它收斂速度快、易于實現且僅有少量參數需要調整，目前已經被廣泛應用于目標函數優化、動態環境優化、神經網絡訓練等許多領域。

由于直接用粒子群算法處理多目標優化問題，很容易收斂于非劣最優域的局部區域，以及如何保證算法的分布性等問題，Coello等人提出了基于Pareto的多目標粒子群算法（MOPS0），強調了粒子和種群之間作用的重要性[12]。

多目標粒子群優化算法作為一種新興的多目標優化算法具有以下優點：（1）在編碼方式上PSO算法比較簡單，可以直接根據被優化問題進行實數編碼；（2）對種群的初始化不敏感，可達到較快的收斂速度；（3）算法適用于絕大多數的多目標優化問題；（4）優化過程中，每個粒子通過自身經驗與群體經驗進行更新，具有學習和記憶的功能；（5）該算法在收斂性、解的分布性以及計算效率方面具有很大改善。

2.5遺傳算法

遺傳算法（Genetic Algorithm，GA）是進化算法的一種，是美國密執安大學的John Holland教授于七十年代中期首先提出來的，從生物進化的過程中得到靈感與啟迪，模擬人自然“物竟天擇，適者生存”的自然選擇的法則創立的。

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

3多目標優化研究的熱點問題

多目標優化問題中，各個目標之間通過決策變量相互制約，對其中一個目標優化必須以其他目標作為代價，而且各目標的單位又往往不一致，因此很難客觀地評價多目標問題解的優劣性。傳統優化方法往往強調最優化，在解決因多種復雜因素難以建模，或根本不存在傳統意義上的最優解或獲得最優解的代價太大的優化問題時。由此，采用滿意優化方法解決這類問題是較好的策略。滿意優化本質上是一個多目標優化方法，它摒棄了傳統的最優概念，它將優化問題的約束和目標融為一體，將性能指標要求的滿意設計與參數優化融為一體，強調的是“滿意”而不“最優”。所以，近年來，滿意優化也逐漸成為各領域關心的問題。

4結束語

多目標優化問題是近年來人們越來越需要面對和解決的問題。除了以上單一優化算法外，很多學者已經在單一優化算法的基礎上，結合多種優化算法解決了一些多目標優化問題，如NSGA-Ⅱ與MOPSP的結合算法[15]，模擬退火算法與遺傳算法的結合算法[16]。然而，由于各種多目標優化算法的不同特點和缺陷，如何使這些優化算法能夠更好地無縫對接，對解決多目標滿意優化問題具有非常重要的意義。

參考文獻

[1]玄光男，程潤偉著.周根貴譯.遺傳算法與工程優化，清華大學出版社，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]肖曉偉等.多目標優化問題的研究概述.計算機應用研究，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]楊海清.進化算法的改進及其應用研究.浙江工業大學碩士論文，2004.

[6]鄧俊等.基于神經網絡和模擬退火算法的配煤智能優化方法[J].冶金自動化，2007（3）.

[7]韓強.多目標應急設施選址問題的模擬退火算法[J].計算機工程與應用 ，2007（30）.

[8]陳峻等.蟻群算法求解連續空間優化問題的一種方法[J].軟件學報 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]張德勇，黃莎白.多目標優化問題的蟻群算法研究[J].控制與決策 2005，20（2）

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

[12]張慧敏.改進的粒子群計算智能算法及其多目標優化的應用研究（碩士學位論文）.

杭州大學.2005.

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

[14]洪朝飛等.面向機械設計的一種改進的遺傳算法.太原科技大學學報，2013（02）.

[15]王金華等.基于NSGA-Ⅱ與MOPSP融合的一種多目標優化算法[J].

篇5

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

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

摘 要：區域防空雷達網是防空作戰空情預警的發展趨勢，為了提高區域雷達網探測能力和抗綜合電子干擾、抗隱身技術與隱身飛機的威脅，抗低空、超低空突防及抗反輻射導彈(ARM)的能力，研究雷達組網的問題，介紹免疫遺傳算法的基本原理和特點，提出基于免疫遺傳算法的雷達組網方法，通過計算機仿真實驗證明方法的可行性。

關鍵詞：免疫遺傳算法；雷達組網；覆蓋系數

中圖分類號：TP39文獻標識碼：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 引 言

隨著新型空襲兵器和航天技術的不斷發展，單臺雷達無論在探測能力上，還是電子防御功能上都有較大的局限性，因此雷達組網技術在現代戰爭和人類對宇宙的探測中起著舉足輕重的作用，該技術是通過將多功能、多類型、多頻段的雷達進行組網，實現實時數據傳輸，資源共享，并在此基礎上對數據實時處理，這已被證明是一種有效的方法［1］。雷達組網系統的關鍵問題是如何對多臺雷達進行最佳組網以獲得最優的防御能力。目前進行雷達組網的方法很多，常用的有效用函數法或專家法，它們是根據雷達覆蓋防守區域面積、雷達部署任務、單臺雷達探測距離、地形、銜接角、遮蔽角、起伏角等因素進行加權求和得到陣地的效用值，但是這些都不能很好地解決執行速度的問題。將免疫遺傳算法應用于雷達組網，能較快地使布陣接近最優解，從而避免了采用窮舉的方法帶來執行速度慢的問題，并且克服了遺傳算法未成熟收斂和局部搜索能力差的缺陷。

2 免疫遺傳算法原理和設計

2.1 免疫遺傳算法原理

生物免疫系統對抗原會自動產生相應的抗體來防御，這一過程被稱為免疫應答。在此過程中，部分抗體作為記憶細胞保存下來，當同類抗原再次侵入時，記憶細胞被激活并產生大量抗體，使再次應答比初次應答更迅速，體現了免疫系統的記憶功能。同時，抗體與抗體之間也相互促進和抑制，以維持抗體的多樣性及免疫平衡，這種平衡是依濃度機制完成的，即抗體的濃度越高，則越受抑制，反之亦然，體現了免疫系統的自我調節功能。抗體的濃度計算是系統保持種群多樣性的基本手段之一［2］。

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

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

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

3）具有自我調節功能：可提高局部搜索能力。

2.2 免疫遺傳算法設計

免疫遺傳算法在標準遺傳算法的基礎上增加了抗體濃度概率計算、抗體的促進與抑制等模塊來提高解的多樣性。該算法因為將免疫系統中抗體多樣性維持機制引入了遺傳算法，使得其性能比標準遺傳算法更進了一步。在解決實際問題時，目標函數和約束條件作為抗原輸入，隨后產生初始抗體群，并通過一系列遺傳操作及抗體親和度的計算，在保持抗體多樣性的情況下，找出針對該抗原的抗體，也就是問題的解［3］。免疫遺傳算法的流程圖如圖1所示，其基本的步驟如下：

計算技術與自動化2014年6月

第33第2期陳 軒等:基于免疫遺傳算法的雷達組網方法

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

2）初始抗體產生。在第一次迭代時，抗體通常在解空間中用隨機的方法產生。

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

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

5）選擇、交叉、變異操作。根據設置的選擇概率、交叉概率和變異概率選擇抗體，對抗體進行交叉和變異操作。

6）根據以上的操作更新群體以后轉入步3)。

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

3 采用免疫遺傳算法的雷達組網

3.1 雷達組網問題描述

在采用免疫遺傳算法進行雷達組網的方案中，雷達的覆蓋系數為：

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

式中Si為第i臺雷達的探測范圍，N為雷達總數，Sarea給定的責任區域。ρ∈［0，1］ 表示N臺雷達所覆蓋的有效責任區域占總責任區域的比重。maxρ為本次雷達組網的目標函數，也就是免疫遺傳算法中的抗原，即

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

3.2 抗體編碼

雷達坐標是所求問題解的信息，為了縮小抗體空間，提高搜索效率，采用了對雷達組網比較直觀的抗體編碼方式，假設一共有5臺雷達進行組網，則N種雷達布陣的方案可以表示為如下的結構：

X11Y11X12Y12X13Y13X14Y14X15Y15第1種雷達組網方案

X21Y21X22Y22X23Y23X24Y24X25Y25

第2種雷達組網方案

……

Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5

第n種雷達組網方案

其中，Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5（n表示雷達組網的任意一種方案）分別是第1臺、第2臺、第3臺、第4臺和第5臺雷達的橫坐標和縱坐標。雷達布陣的每一種方案對應為免疫遺傳算法中抗體種群中的每一個個體。

3.3 親和力計算

親和力是指發生免疫系統識別的抗體和抗原的結構越互補，結合越可能發生，而把彼此結合的強度稱之為親和力。抗原需要盡可能好的與入侵的抗體相結合。二者匹配程度越好，結合就越好，抗原和抗體親和力就越大。對于雷達組網問題，抗原對應的是雷達組網的最大覆蓋系數，由于雷達組網的總責任區域的面積是一定的，可以定義抗體Ab與抗原Ag的之間的親和力為：

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

式中：Tb，Ta分別為抗體Ab，Ag對應的雷達網的覆蓋系數，其中Tg也是所求的最大的雷達網覆蓋系數。

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

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

式中：Tb1、Tb2分別為抗體Ab1與抗體Ab2對應的雷達網覆蓋系數［4］。

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

免疫遺傳算法能使抗體保持多樣性并且最終能夠收斂到最優解的主要操作，就是因為在算法中有選擇、交叉和變異算子的存在，從而使整個抗體群沿著適應度較好的方向搜索。

1)選擇算子

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

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

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

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

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

α和β是常數調節因子； N是該種群內抗體的總數。

2)交叉

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

抗體1：X11Y11X12Y12X13Y13X14Y14X15Y15

抗體2：X21Y21X22Y22X23Y23X24Y24X25Y25

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

抗體1：X11Y11X12Y12X23Y23X24Y24X25Y25

抗體2：X21Y21X22Y22X13Y13X14Y14X15Y15

3)變異

變異是在選中的抗體中，對個體中的某些基因以一定的變異概率對某些抗體的某些位執行異向轉化(一般變異概率的取值為0.01~0.2)。在變異的時候，對于交叉過程中產生的抗體方案，隨機產生一個介于［-MAX/2, +MAX/2］的數字rand，其中MAX為橫坐標和縱坐標可取的最大值。變異以后坐標值x’與原來值x之間的關系如下：

x，=x+rand(7)

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

單靠變異不能在求解中得到好處，但是，它能保證算法過程不會產生無法進化的單一群體。因為在所有的個體一樣的時候，選擇和交叉無法產生新的基因，這時只能靠變異產生新的基因，即變異增加了全局優化的特質。

3.5 基于濃度的種群更新

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

4 仿真實驗

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

ィa）3臺雷達的面積覆蓋率

ィb）4臺雷達的面積覆蓋率

ィc）5臺雷達的面積覆蓋率

圖2 matlab仿真結果

在圖2中當雷達數量為3臺時，組網雷達的面積覆蓋率為87.84%（圖2（a））；當為4臺時，組網雷達的面積覆蓋率為91.53%（圖2（b））；當為5臺時，組網雷達的覆蓋率為94.27%（圖2（c））。將仿真的結果與傳統遺傳算法的組網覆蓋率對比［6］，如表1所示。

表1 雷達組網覆蓋率對比

3臺雷達

4臺雷達

5臺雷達

傳統遺傳算法覆蓋率

81.5%

86.1%

88.2%

免疫遺傳算法覆蓋率

87.84%

91.53%

94.27%

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

5 結 論

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

參考文獻

［1］ 彭獲由. 區域性雷達組網［J］. 電子科學技術評論, 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］ 段玉波, 任偉建, 霍鳳財, 等. 一種新的免疫遺傳算法及其應用［J］, 2005, 20(10):1185-1188.

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

篇6

關鍵詞全局最優；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數優化問題具有廣泛的工程和應用背景，如結構設計中使得結構內最大應力最小而歸結為極大極小優化（minmax）問題、數據魯棒性擬合中采取最小絕對值準則建立失擬函數等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部優化方法，優化結果與初值有關。

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

本文提出把Powell方法融入浮點編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構成適于求解不可微函數優化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數值算例對混合方法的有效性進行了驗證。

2混合遺傳算法

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

min(1)

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

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

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

step3執行比例選擇算子進行選擇操作。

step4按概率執行算術交叉算子進行交叉操作。即對于選擇的兩個母體和，算術交叉產生的兩個子代為和，是[0，1]上的隨機數，1,。

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

(3)

(4)

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

step6對每個個體按照概率pPowell進行Powell搜索。若個體被選擇進行Powell搜索操作，則以作為初始點執行Powell方法得，若則把所得計算結果作為子代，否則，若取=；若取=，1。

step7計算個體適應值，并執行最優個體保存策略。

step8判斷是否終止計算條件，不滿足則轉向step3，滿足則輸出計算結果。

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

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

(2)令，從出發，依次沿方向,,…,作一維搜索，得到點,,…,求指標m，使得-=max{-}，令。若ε，則Powell方法計算結束，否則，執行(3)。

(3)求使得=min，令==，若，則Powell方法計算結束，得點；否則，執行(4)。

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

3算例

T[-500,500]

函數f(x)有相當多的極小點,全局極小點是=-420.97，=1,2,…,，最優值為-837.97；次最優點為={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次優值-719.53。變量個數n=2時函數f(x)特性如圖1示。程序編制和運行環境采用FortranPowerStation4.0，隨機數由內部隨機函數產生，在奔騰133微機上運行。

采用改進的Powell方法計算100次，初值在區間[-500,500]內隨機產生，只有6次（即以概率0.06）搜索到全局最優，計算成功的概率極低。

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

采用本文混合法計算，取m=30，pc=0.85、pm=0.2，T=100，進行Powell搜索的概率pPowell取不同值，混合法運行100次，計算結果見如表1。對于這個具有多極值的算例，多次計算表明pPowell=0.3時，混合法能以完全概率搜索到全局最優的準確值，但是此時混合法計算時間約為標準遺傳算法取T=500時計算時間的4/5。對應的浮點編碼遺傳算法，取m=30，pc=0.85、pm=0.2，T=100，運行100次，82次（以概率0.82）搜索到全局最優（如表1中PPowell=0所示），計算時間約為標準遺傳算法取T=500時計算時間的1/8，但是搜索到全局最優的概率卻遠遠高于標準遺傳算法。

表1pPowell取不同值時混合法的計算結果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最優解的次數

82

85

89

94

98

100

求得最優解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均計算時間/秒

0.14

0.20

0.31

0.47

0.68

0.87

4結束語

針對不可微函數的全局優化問題，本文提出一種把Powell方法與浮點編碼遺傳算法相結合的混合遺傳算法，該算法兼顧了遺傳算法全局優化方面的優勢和Powell方法局部搜索能力較強的特點，提高求得全局解的概率。計算結果表明混合法優于遺傳算法和Powell法，可以可靠地搜索到具有多個局部極值的函數優化問題的全局解。由于計算中只用到函數值信息，本文混合法不僅適用于不可微函數優化問題，也適合可微函數全局優化問題。

參考文獻

[1]周明，孫樹林．遺傳算法原理及應用[M]．北京：國防工業出版社，1999．

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

[3]孟慶春，賈培發．關于Genetic算法的研究及應用現狀[J]．清華大學出版社，1995，35(5)：44－48．

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

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

[6]趙明旺．連續可微函數全局優化的混合遺傳算法[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

關鍵字：頻率分配 遺傳算法 GECP 組合優化

1.

通信網頻率分配問題的背景

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

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

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

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

2.

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

2．1 遺傳算法的原理

遺傳算法(Genetic Algorithms GA)是根據生物學上的染色體基因因子構成機制而產生的。1975年Holland教授首次提出了GA的思想，從而吸引了大批的研究者，迅速推廣到優化、搜索、機器學習等方面。遺傳算法是一種全局優化算法，其僅以目標函數值為搜索依據，通過群體優化搜索和隨機執行基本遺傳運算，實現遺傳群體的不斷進化，適合解決組合優化問題和復雜非線性問題[6]。

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

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

2．2 遺傳算法的基本結構

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

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

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

2. 計算群體中各個候選解的適應值；

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

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

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

6. 使用選擇機制形成新一代候選解；轉2。

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

遺傳算法通過編碼和遺傳操作，達到了處理的并行性，可以同時處理群體中的多個個體，即同時對搜索空間內的多個解進行評估，具有較好的全局搜索性能，減少了限于局部最優解的風險。

3.

遺傳算法用于頻率分配

3．1 算法的基本流程

采用遺傳算法的FAP基本流程

3．2 遺傳算子的選擇

3．2．1 選擇算子

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

輪賭算法流程如下：

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 交叉算子

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

其基本流程如下：

//flip函數中，產生一個0到1的隨機數，若小于pc，則返回1，否則返回0

if(flip(pc))

crossover1(mother，father);

else if(flip(pc))

crossover2(mother，father);

else

copy(mother);

copy(father);

3．2．3 變異算子

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

其基本流程如下：

while(all frequentpoint)

{

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

4.

工程上需要注意的問題

4．1 初始候選種群

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

4．2 編碼方案

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

4．3 適配值函數

適配值函數對個體（頻率分配方案）進行評價，也是優化過程發展的依據。可以采用如下方式來計算適應度：

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

其中：

pri 是節點的加權值；

函數seperate(Freq)是節點中各條鏈路發頻率同其它鏈路的收頻率間隔的和；

參考文獻

[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] 王凌： 《智能優化算法及其應用》清華大學出版社 2001

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

[7] 孫俊柏：禁用頻點、頻段下野戰通信網的頻率分配 中國科學技術大學碩士學位論文 1998

篇8

[ 關鍵詞 ] 異常客戶 孤立點檢測 k-medoids算法 遺傳算法

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

一、異常客戶檢測

客戶關系管理即為吸引并保持有經濟價值的客戶,驅逐并消除缺乏經濟價值的客戶。識別異常客戶,一方面可有效地驅逐和消除風險,另一方面可以避免將正常客戶誤判為異常客戶,吸引并保持有經濟價值潛力的客戶。

目前,異常客戶檢測技術主要還是基于數據特征匹配的方法。目前存在兩個缺點。首先,總結異常客戶特征主要靠專家手工完成,耗費人力物力;其次,所需時間較長,錯過最佳挽留時機,異常客戶造成的危害就無法減少。

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

二、孤立點檢測

發現異常數據,孤立點檢測是個行之有效的方法。孤立點(outlier)是數據集中的小部分數據對象,這一小部分對

象和數據中的一般行為或數據模型有著明顯的不同。孤立點挖掘分為兩個子問題:在給定的數據集中定義什么數據可以認為是不一致的;找到一個有效的方法來挖掘孤立點。

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

目前孤立點挖掘算法主要有四種:統計學方法、基于距離、基于偏離和基于密度的方法。

基于統計的方法主要應用于科研計算,這主要是因為這種方法必須事先知道數據的分布特征,

從Knorr和Ng開始開始研究采用無需任何參數的方法,并提出使用數據點到其最近鄰居的距離和的方法作為異常的量度標準。雖然距離是一種發現孤立點的有效的無參數方法,但需要耗費時間來計算距離。

A.Arning和P.Raghavan提出了基于偏離的孤立點探測的線性方法,但基于偏離的方法中的序列異常的概念并沒有得到普遍的認同。這是因為序列異常在概念上仍然有一定的缺陷,遺漏了不少的異常數據。

基于密度的方法只關注對象周圍臨近的密度(最近鄰居數)。關于它周圍的鄰居具有高密度鄰居的數據點不是孤立點,具有低密度鄰居的數據對象可能是孤立點。

上文中介紹了當前各種孤立點檢測算法面臨的種種缺陷,并對其進行了比較,發現基于距離的孤立點檢測方法在許多方面都優于其他方法,在思路上也是正確的。基于距離的方法與基于統計的方法相比,不需要用戶擁有任何領域知識。與“序列異常”相比,在概念上更加直觀。

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

本文將基于距離的k-medoids聚類算法與遺傳算法相結合,既可以很好地解決局部最優的問題,也可以很好地解決孤立點的問題,還可以加快遺傳算法的收斂速度,節約時間成本。

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

遺傳算法是一種建立在自然選擇原理和自然遺傳機制上的迭代式自適應概率性搜索方法,具有魯棒性強、需要的領域知識少等優點,用于孤立點檢測理論上是可行的。

本文提出的基于k-medoids算法和遺傳算法結合的孤立點檢測算法,繼承了遺傳算法的優點,在一定程度上克服了現有算法的弱點和不足。隨機產生遺傳算法的第一代并開始選擇,然后在每代進化中,都用k-medoids算法對每個被選擇的個體進行進一步的優化。也就是說,在每一代都要對所有被選中的個體計算以其為初始值的k-medoids算法的局部最優結果,并以這些局部最優結果替換掉原來的個體并繼續進化,直到達到最大代數或者結果符合要求為止。

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

1.對個體進行編碼和初始種群的生成

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

2.適應度函數的確定

本文采用均方差作為適應度函數,定義如下:

其中, E為所有數據對象與相應聚類中心的均方差之和,p為代表對象空間中的一個點,為聚類的中心對象,n為中點的個數。

3.選擇算子的實現

遺傳算法使用選擇運算(或稱復制運算)來實現對群體中的個體進行優勝劣汰操作。本文采用錦標賽選擇法。

4.用k-medoids算法進行優化

用k-medoids算法對選擇出來的個體進行優化,并用優化后的個體代替原來的個體。用k-medoids算法進行聚類一般只能得到局部最優解,但用其優化后的個體來代替原來的個體便可大大加速遺傳算法的收斂速度,節約時間成本。

5.交叉算子的實現

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

6.變異算子的實現

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

四、實驗分析

本文的數據來自美國加州大學Irvine分校的機器學習庫(the UCI Irvine Machine Learning Repository),選擇德國信用數據集為研究對象,該數據集包含20個屬性,本研究截取前100條數據,采用k均值算法、k-medoids算法和本文研究的新算法分別對數據集進行了聚類分析,實驗結果見表1 (本結果只顯示包含孤立點的類,其中的數字代表數據對象的序號)。

從表可以看出,在聚類時k均值算法無法把孤立點分離出來,而k-medoids算法和本文所研究的算法都可以把孤立點分離出來。從衡量聚類效果的重要指標均方差值的大小來看,在存在孤立點的時候, k-medoids算法比k均值算法要好,而新算法顯然優于前面兩個算法。

五、結論

本文比較了四種孤立點檢測方法,通過分析發現基于距離的孤立點檢測方法在許多方面都優于其他方法,在思路上也是正確的。基于距離的k-medoids算法可有效檢測孤立點,但容易陷入局部最優。將k-medoids算法與遺傳算法相結合,既可以很好地解決局部最優的問題,也可以很好地解決孤立點的問題,還可以加快遺傳算法的收斂速度,節約時間成本。應用該算法可以有效地檢測孤立點,即商業銀行的異常客戶,對風險進行有效地預警。

參考文獻:

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

篇9

關鍵詞：軟件可靠性；神經網絡；遺傳算法

中圖分類號：TP183文獻標識碼：A文章編號：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 軟件可靠性

軟件可靠性被定義為：“在一段時間內軟件正常運行的概率”。軟件可靠性模型對于軟件可靠性的估測起著核心的作用。而對于軟件質量保證有直接意義的模型，是那些它們的參數能夠以軟件故障發生的歷史預測軟件將來故障發生的行為，軟件可靠性模型是這種思想的體現。

到目前為止，世界上大約已公開發表了一百多個軟件可靠性模型，基本上被分為兩類：參數型軟件可靠性模型和數據驅動型軟件可靠性增長模型。前者主要有Musa的執行時間模型、Goel-Okumoto模型、J-M模型、貝葉斯模型等等。這種模型的主要缺點是：預測的數據是在自己模型的假設前提下實現的，每個模型都有自己的假設前提，導致模型應用的局限性。后者主要指用神經網絡去預測軟件可靠性模型，這種模型沒有前提、假設。輸入的是歷史錯誤數據，提高了預測的精度。Karunanithi.whitley&Malaiya在1992年的論文中已證明數據驅動型比參數型有著更好的預測精度。

2 BP神經網絡

BP神經網絡是采用BP算法的神經網絡的統稱。目前在人工神經網絡實際應用中，絕大部分采用BP網絡和它的變化形式，它是前向網絡的核心部分。

2.1 BP網絡的結構

BP神經網絡有三層，分別為：輸入層、隱藏層和輸出層（見圖1），其中隱藏層的層數理論上可以為任意值。

■

圖1 BP網絡模型結構 圖2 三層BP網絡模型

2.2 BP算法

BP神經網絡參數傳遞有兩個過程：一個為輸出參數的順傳播，另一個為誤差的逆傳播。假設一個三層的BP神經網絡（見圖2）網絡權值（Wij Tli）閾值為θ。則

1) 輸出的順傳播

隱節點：■ 其中■

輸出節點：■其中■

2) 誤差的逆傳播

誤差：

■

輸出節點權值修正值：

■

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

隱節點權值修正值：

■

令■ 則 ■

由于權值的修正正比于誤差函數沿梯度下降，所以有：

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

對閾值的修正過程同對權值的修正過程，推倒的結果為：

輸出節點：θl(k+1)=θl(k)+ηδl

隱節點： θi(k+1)=θi(k)+η'δi'

2.3 傳遞函數

在BP神經網絡中經常使用對數S形函數、正切函數和線性函數作為神經元的傳遞函數。

3 遺傳算法

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

算法流程如下：

1) 編碼所要解決的問題。

2) 隨機生成N個個體，形成初始染色體群體。

3) 計算群體中每個個體的適應度值。

4) 計算群體的平均適應度，把每個染色體的適應度歸一化。

5) 依據歸一化后的染色體適應度值，賦給每個染色體一個生存概率，按這個概率選擇n（n

6) 用新的染色體代替原來的2n個染色體，形成新的種群。

7) 若滿足中止條件，則解碼適應度最大的染色體得到問題的解，否則返回步驟2)繼續進行。

4 用遺傳算法去優化BP神經網絡的結構

在用神經網絡去預測軟件可靠性的過程中，神經網絡的結構往往是預先不能獲得的。本文提出了用遺傳算法優化神經網絡結構的方法。論文假設神經網絡有四個輸入一個輸出中間的隱層為待優化的部分。

4.1 個體的編碼

我們用2進制編碼方法對結構進行編碼，每個隱層用4位二進制碼來代表，則隱層的神經元的個數為0－15個，當個數為零時代表該層不存在，我們可以假設隱層有二層、三層或任意層，則個體的編碼為8、12或更多個二進制碼。

4.2 適應度函數

在遺傳算法中使用適應度來度量群體中的個體在優化計算中能達到或接近于最優解的優良程度。本文采用的適應度函數為：

■

其中p為可靠性樣本用于訓練的數目，■i是神經網絡的輸出值，xi為樣本值。

4.3 控制參數的選取

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

4.4 流程圖(見圖3)

4.5 泛化處理

在BP網絡的訓練中往往會出現這樣的情況，當網絡的訓練誤差很小的時候，一個新的輸入會使網絡的訓練誤差增大，這是因為網絡記憶了已被訓練的樣本，而對新的輸入沒有良好的泛化能力。規則化調整方法是通過調整網絡的性能函數，來增強網絡的泛化能力。普通的BP神經網絡都采用網絡誤差的均方根之和作為性能函數。如下式 ：

■

其中 ei ti ai分別表示第i個訓練樣本的訓練誤差、目標函數和網絡輸出。而調整后的網絡函數如下：

msereg=γmse=(1-γ)msw

γ是性能參數 ■

使用該函數可以減少網絡的有效權值和閾值，并且使網絡的訓練輸出更加平滑，從而增強網絡的泛化性能。

4.6 數據預處理

在我們開始試驗之前，還得對原始數據進行如下處理：■，x為原始數據，=xmax-xmin。這樣數據就被調整到0.1－0.9之間。在預測結束后用■將得到的數據調整到原始數據。

5 進化神經網絡對軟件可靠性預測實例

為了證明本文提出的方法優于直接用神經網絡進行預測，這里我們找到了一組軟件可靠性的數據，這組數據來源于一個中等項目軟件測試過程（見表1）。

在進行仿真之前我們還得定義幾個指標來代表預測的精度。

■其中■i為預測的數據，xi為實際的數據。

■其中■i為預測的數據，xi為實際的數據，n為待預測的數據量。

我們用前12組數據對神經網絡進行訓練，后四組作為待預測的數據，普通神經網絡采用3－7－1的結構，優化的結果神經網絡采用2－6－2－1的結構。預測結果的RE和AE比較（見表2）。

對數據的擬合度如圖4所示 。

6 結論

篇10

關鍵詞：排課；排課管理；遺傳算法

中圖分類號：G647 文獻標志碼：A 文章編號：1674-9324（2016）15-0011-02

一、國內外研究動態

（一）背景與意義

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

（二）國內外研究現狀和發展態勢

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

二、理論意義及實用價值

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

三、目標、研究內容和研究方法

（一）工作目標與任務

結合江蘇信息學院的現實，再造教務教學管理的管理流程，使它更加科學化、規范化。據此建立一套教學制管理制度，不但要適合江蘇信息學院的現實，還要完成選課排課的信息化與自動化。最后設計一個排課系統，與現有運行的排課系統相比，該系統支持全學分制，這是它最明顯的優點。它不僅能夠減少各級教學管理人員的工作量，方便檢索查詢與管理，還能夠形成先進的教學理念和管理制度。

（二）研究內容和研究方法

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

四、關鍵技術問題

（一）創新之處

首先，對于排課問題的影響要素、主要約束條件、求解目標和難點，本系統進行了完整的討論，提出了排課問題求解方法的總體框架和技術路線；其次，根據江蘇信息學院的實際情況，從排課系統的需求分析開始，建立排課系統的數據模型及其體系結構。給出排課系統中遺傳算法的設計，核心算法的實現方法和步驟；最后，說明本排課系統的總體設計方案、各模塊的功能結構及相應的實現方法。

（二）擬解決的關鍵問題

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

五、可行性論證

（一）目標可行性論證

通過校園網構建一個交流平臺來連接教師、學生和教學管理部門，利用并結合J2EE技術、Struts技術、MVC結構設計、SOA技術實現B/S結構的數據信息管理目標。

（二）技術可行性論證

軟件方面，本系統結合了物聯網技術，采用目前最常用的J2EE技術與SQL相結合的模式進行開發，數據庫服務器選用Microsoft的SQL Server 2008作為數據庫，此數據庫能夠處理大量的數據，不僅能夠保持數據的完整性，而且還能夠提供多項高級管理功能。由此可見，系統的軟件開發平臺條件已經滿足。在硬件方面，江蘇信息學院計算機容量越來越大，可靠性越來越高，硬件平全能夠滿足系統開發和系統運行的需要。

（三）成本可行性論證

本系統只需花費少量的經費，廣大教務管理人員就能從繁重的手工排課工作中解脫出來，他們可以把更多的精力投入到其他教學管理工作中，提高工作效率；同時也可以使廣大師生通過校園網查詢到相關的個人教學信息，此方式成本低，既方便又經濟。

（四）社會可行性論證

目前，江蘇信息學院校園網絡已經覆蓋了整個教學區和學生區，學院各個教學部門、行政部門和廣大學生的上網需求都可以滿足。尤其是本學院已經通過光纖接入的方式與Internet連接，能夠很好地實現校內用戶之間以及校內用戶與校外用戶之間的聯系。

綜上所述，面對江蘇信息學院教務信息處理需求的日益增長，開發一個教務排課管理系統來應對這種需求，為學生和教學管理人員提供快捷方便的雙向選擇服務，提高排課管理工作的效率，是非常有必要的。

參考文獻：

[1]劉真.基于URP的地方高校數字校園建設應用研究[D].山東大學碩士學位論文，2008.