時間：2023-04-01 10:06:31
導(dǎo)語：在遺傳算法論文的撰寫旅程中，學(xué)習(xí)并吸收他人佳作的精髓是一條寶貴的路徑，好期刊匯集了九篇優(yōu)秀范文，愿這些內(nèi)容能夠啟發(fā)您的創(chuàng)作靈感，引領(lǐng)您探索更多的創(chuàng)作可能。
關(guān)鍵詞：遺傳算法，混沌，優(yōu)化方法
0引言
遺傳算法是一種較新的全局優(yōu)化搜索算法，它使用了群體搜索技術(shù)，用種群代表一組問題解，通過對當(dāng)前種群施加選擇、交叉和變異等一系列遺傳操作，從而產(chǎn)生新的一代種群，并逐漸使種群進(jìn)化到包含最優(yōu)解或近似最優(yōu)解的狀態(tài)。但由于算法復(fù)雜度的限制, 遺傳算法雖然能以概率收斂到全局最優(yōu)解，其局部搜索速度和精度并不能得到很好的保證。近幾年來遺傳算法作為優(yōu)良的全局尋優(yōu)方法日趨成熟,尤其是和其他尋優(yōu)方法的結(jié)合,進(jìn)一步提高了遺傳算法的性能，其中借助于混沌改進(jìn)遺傳算法的性能,是近年來遺傳算法領(lǐng)域研究的熱點之一，遺傳算法和混沌優(yōu)化的組合,可以使遺傳算法的全局尋優(yōu)能力,搜索精度,搜索速度等幾方面得到較明顯的改進(jìn)。
1混沌的特征和蟲口方程
混沌是存在于非線形系統(tǒng)中的一種較為普遍的現(xiàn)象。混沌并不是一片混亂，而是有著精致內(nèi)在結(jié)構(gòu)的一類現(xiàn)象?；煦邕\動具有遍歷性、隨機(jī)性等特點，混沌運動能在一定的范圍內(nèi)按照其自身的規(guī)律不重復(fù)地遍歷所有狀態(tài)。因此，如果利用混沌變量進(jìn)行優(yōu)化搜索，無疑會比隨機(jī)搜索更具有優(yōu)越性。
描述生態(tài)學(xué)上的蟲口模型Logistic映射自May于1976年開始研究以來，受到了非線形科學(xué)家的高度關(guān)注，Logistic映射是混沌理論發(fā)展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遺傳算法
GA較傳統(tǒng)數(shù)學(xué)優(yōu)化方法更易找到全局最優(yōu)解，但對于一些問題也存在過早收斂、收斂速度較慢、難以找到較精確解的情況。因此，本文通過Logistic映射及相關(guān)混沌理論提出了一種運算性能較好的混沌遺傳函數(shù)優(yōu)化算法?；煦邕z傳算法(CGA)的主要步驟如下：
1.初始化:預(yù)先確定運行參數(shù)，包括：種群規(guī)模M，交叉概率pc，變異概率pm，最大迭代次數(shù)n。隨機(jī)產(chǎn)生一個分布均勻的初始群體(包含n個初始解)，計算各個個體的適應(yīng)度值；
2.采用比例選擇算子對當(dāng)前種群進(jìn)行選擇操作，實現(xiàn)強(qiáng)留劣汰；
3.對當(dāng)前種群進(jìn)行交叉運算。將種群內(nèi)個體兩兩隨機(jī)組合，對每個配對的組合，首先由系統(tǒng)隨機(jī)生成一個(0,1)之間的數(shù)，由交叉概率決定是否交叉。論文參考。論文參考。若交叉，則采用映射生成的序列經(jīng)簡單映射后利用高斯函數(shù)來決定交叉位置，否則，看下一對組合。所有的交叉位置由一個混沌序列即可決定；
5.若終止條件滿足，則算法中止，否則轉(zhuǎn)向步驟(2)。
本文嘗試在將改進(jìn)后的遺傳算法與混沌優(yōu)化算法相結(jié)合，提出一種基于混沌理論的混合遺傳算法，算法的流程如下頁流程圖所示：
圖1 改進(jìn)后的混沌遺傳算法（ICGA）流程圖
3仿真分析
本文選用一維和多維多峰值函數(shù)為例，見表1，用遺傳算法（GA）、混沌遺傳算法（CGA）和本文算法（ICGA）進(jìn)行比較研究。
表1 測試函數(shù)
實驗結(jié)果比較如下（以下圖縱坐標(biāo)表示最大適應(yīng)值，橫坐標(biāo)表示演化代數(shù)）
圖2 f2實驗結(jié)果比較示意圖圖3 f3實驗結(jié)果比較示意圖
從圖2、圖3的比較結(jié)果看，本文中算法初始種群較好，進(jìn)化開始就能找到高的最大值，加快搜索的速度，整個算法的尋優(yōu)結(jié)果比遺傳算法好。論文參考。考慮到算法中使用了隨機(jī)操作，僅僅由一次實驗得到的結(jié)果是不能夠充分說明問題的，因此，再進(jìn)行統(tǒng)計比較。本文中進(jìn)行了20次統(tǒng)計實驗。比較結(jié)果如表2
表2 比較結(jié)果
【關(guān)鍵詞】免疫遺傳算法 粗糙集 屬性約簡
1 前言
對于一個粗糙集決策屬性表，人們總是期望能找出所有約簡或最小約簡，然而一個信息表的屬性約簡并不是唯一的，得到信息表的包含最少條件屬性的約簡已被證明是NP 完全問題。由于免疫遺傳算法在NP問題領(lǐng)域取得了比較好的效果，論文提出了一種基于免疫遺傳算法的粗糙集屬性約簡算法，實驗結(jié)果證明該算法是有效的，可快速收斂到全局最優(yōu)解。
2 屬性約簡的免疫遺傳算法設(shè)計
2.1 染色體編碼
采用傳統(tǒng)的二進(jìn)制編碼，即若決策表中有N個待約簡的條件屬性，算法產(chǎn)生一個長度為N的0-1二進(jìn)制串，每一位代表一種對條件屬性的取舍，1表示采用該位上的條件屬性，0則表示不采用。
2.2 初始種群的產(chǎn)生
初始種群設(shè)置的好壞直接影響到最后的求解效果。任何一個信息表或決策表的相對核都包含在所有相對約簡當(dāng)中，即具有唯一性。因此考慮在產(chǎn)生初始種群的時候使每個染色體都含有相對屬性核。
2.3 適應(yīng)度函數(shù)的構(gòu)造
適應(yīng)度函數(shù)用來評價染色體的優(yōu)劣，在對每一個染色體進(jìn)行適應(yīng)度評價前，先要對每個染色體進(jìn)行一定的調(diào)整。調(diào)整是基于屬性重要度相關(guān)的某種啟發(fā)式信息，給出染色體的調(diào)整步驟：
（1）計算決策表S中條件屬性集C關(guān)于決策屬性集D的重要度γc（D）；
（2）設(shè)C'為當(dāng)前染色體采用的條件屬性集，計算條件屬性集C'關(guān)于決策屬性集D的重要度γc'（D）；
（3）比較γc（D）和γc'（D）的大小，若γc'（D）
（4）對任意屬性ai（∈C-C'）（1=1，2，…，|C-C'|），計算每一個μD（ai），令j={j|μD（aj）=max（μD （ai））}，然后將染色體上第j位上的0置為1，并且C'=C'∪{aj}，轉(zhuǎn)到步驟②；
（5）調(diào)整過程結(jié)束。當(dāng)染色體經(jīng)過如上調(diào)整以后，就可以應(yīng)用適應(yīng)度函數(shù)對該染色體進(jìn)行評價，適應(yīng)度函數(shù)的計算公式為：
F=|C|-|C'| （5.16）
則染色體中采用的條件屬性個數(shù)越少，該染色體的適應(yīng)度函數(shù)值就越高，個體就越優(yōu)良。
2.4 抗體產(chǎn)生的促進(jìn)和抑制
要使適應(yīng)度高的抗體進(jìn)行促進(jìn)，濃度高的抗體進(jìn)行抑制。
抗體相似性通過抗體編碼的Manhattan距離來度量?？贵wX={a1，a2，…an}與抗體Y={b1，b2，…bn}之間的相似度為：
d值越大，表示兩者的相似程度越低，如果d=0，則表示兩個抗體完全相同。故抗體X的濃度定義為：
其中，函數(shù)D（X）表示抗體X相似度小于λ的抗體數(shù)目，λ為一給定的閾值
2.5 基于收縮精度的逐級進(jìn)化策略
可以用收縮精度作為算法的停止準(zhǔn)則，即當(dāng)收縮精度小于某個比較小的正數(shù)K時算法停止進(jìn)化。假設(shè)優(yōu)化目標(biāo)為求目標(biāo)函數(shù)F的最大值，在不同的進(jìn)化時期適應(yīng)度函數(shù)J采用不同的形式如下：
式中α、β、k1 和k1為正數(shù)，根據(jù)優(yōu)化目標(biāo)的需要取不同的值。其中α 和β是為了在算法的中后期拉大群體內(nèi)個體之間的差距，α
3 實例分析
在某次戰(zhàn)斗任務(wù)中，我方使用各種常規(guī)武器對敵方6處戰(zhàn)場目標(biāo)實施打擊。參與毀傷效果評估計算的我方武器“投入”和“產(chǎn)出”數(shù)據(jù)離散化得出一個毀傷評估決策信息表。應(yīng)用改進(jìn)的遺傳算法進(jìn)行屬性約簡。圖1所示為免疫遺傳算法求解最優(yōu)約簡屬性向量的迭代過程。改進(jìn)后的基于收縮精度的遺傳算法在進(jìn)化15代以后即停止搜索，得出了近似最優(yōu)解。
由圖1可以看出在算法的進(jìn)化過程中，迭代曲線每隔幾代都會變化一次。并且在算法的中后期，曲線依然出現(xiàn)明顯變化。一方面說明算法自始自終都實現(xiàn)了對解空間的有效搜索，另一方面與傳統(tǒng)算法相比，沒有出現(xiàn)過早收斂的現(xiàn)象。說明改進(jìn)后免疫遺傳算法的科學(xué)性和有效性。
參考文獻(xiàn)
[1]曾子林，張宏軍，張睿，邢英.變精度粗糙集的邏輯解釋及其約簡[J].計算機(jī)應(yīng)用研究，2013（05）.
[2]肖大偉，王國胤，胡峰.一種基于粗糙集理論的快速并行屬性約簡算法[J].計算機(jī)科學(xué)，2009（03）.
作者單位
關(guān)鍵詞：靜態(tài)調(diào)度；公共交通系統(tǒng)；免疫遺傳算法
中圖分類號：G650 文獻(xiàn)標(biāo)識碼：A 文章編號：1003-2851（2012）-09-0180-01
遺傳算法[（genetic algorithm，GA）是一種自適應(yīng)大規(guī)模并行搜索優(yōu)化算法，較以往傳統(tǒng)的搜索算法具有使用方便、魯棒性強(qiáng)、便于并行處理等特點，因而廣泛應(yīng)用于解決搜索和優(yōu)化的問題。但由于遺傳算法不能很好地維持解種群中個體的多樣性，易趨于“早熟”收斂而陷入局部最優(yōu)解。因此，遺傳算法不能保證一定能找到問題的全局最優(yōu)解，目前公交公司各車隊的排班主要依靠工作人員的經(jīng)驗手工進(jìn)行，雖然它具有一定的實用性，但它存在著明顯的不足，很難保證排班的結(jié)果在運營效率等方面是最優(yōu)或者接近最優(yōu)的。為滿足實際應(yīng)用需求，采用智能化算法來求解車輛調(diào)度優(yōu)化問題，在有限的算法步驟內(nèi)，找出所有滿足約束條件的排班方案中的最優(yōu)方案或接近最優(yōu)的方案。
一、遺傳算法
1.遺傳算法簡介
遺傳算法（Genetic Algorithms，GA）是一種基于自然選擇和基因遺傳學(xué)原理的自適應(yīng)全局優(yōu)化概率搜索方法。它的創(chuàng)立有兩個研究目的：一是抽象和嚴(yán)謹(jǐn)?shù)亟忉屪匀唤绲倪m應(yīng)過程；二是為了將自然生物系統(tǒng)的重要機(jī)理運用到工程系統(tǒng)中。GA從許多點開始并行操作，在解空間進(jìn)行高效啟發(fā)式搜索，因而可以有效地防止搜索過程收斂于局部最優(yōu)解；遺傳算法在計算機(jī)上模擬生物的進(jìn)化過程和基因的操作，通過目標(biāo)函數(shù)來計算適配值，并不需要對象的特定知識，它具有全局尋優(yōu)的能力，能解決高度復(fù)雜的問題，被廣泛應(yīng)用于自動控制、圖形處理、電力調(diào)度等方面。
2.建立調(diào)度的數(shù)學(xué)模型
調(diào)度系統(tǒng)所采用的數(shù)學(xué)模型對運行環(huán)境做了簡化：車的速度恒定，保持勻速行駛，無特殊事件發(fā)生；以分鐘作為最小的時間單位，這對安排時刻表是合理的；假設(shè)客流模型能反映該段線路上的日常客流量（我們假設(shè)到站乘客服從均勻分布，在不同時段有不同的分布密度）。
首班車發(fā)車時刻為早上6點整，末班車發(fā)車時刻為22點整，所有運營車都在整分鐘時刻發(fā)車，一天之內(nèi)的總班次為m，總時間為16小時，即960分鐘。用xm表示第m輛運營車發(fā)車時刻距首發(fā)時刻的時間，以分鐘為單位。決策變量為X=[x1，x2，…xn]；染色體X是一個完整的發(fā)車時刻表，其中的每個基因為一個車輛的發(fā)車時刻。
免疫算法效仿生物免疫系統(tǒng)，把外來侵犯的抗原和免疫產(chǎn)生的抗體分別與實際求解問題的目標(biāo)函數(shù)以及問題的解相對應(yīng)，生成的抗體能有效地排除抗原，也就相當(dāng)于求得了問題的最優(yōu)解；對與抗原親和力高的抗體進(jìn)行記憶能促進(jìn)快速求解。
二、IGA應(yīng)用于公交動態(tài)調(diào)度
現(xiàn)仍采用上面建立的數(shù)學(xué)模型，初始規(guī)模N仍為200且不隨進(jìn)化代數(shù)而發(fā)生變化，便于IGA和GA比較。現(xiàn)利用IGA來進(jìn)行優(yōu)化的步驟為：
1.在解空間內(nèi)隨機(jī)生成初始群體，并計算其適應(yīng)度，確定最優(yōu)個體x0best，并給出的取值？滓0，A取為1，？滓0i取為3，？滓？孜取為0。
2.根據(jù)式（4.7）進(jìn)行進(jìn)化操作，在解空間內(nèi)生成子代群體，規(guī)模為N。
3.計算子代群體的適應(yīng)度，確定最優(yōu)個體xt+1best，若f（xt+1best）>f（xtbest），則選定最優(yōu)個體為xt+1best，否則最優(yōu)個體為xtbest。
4.重復(fù)執(zhí)行步驟2和3，直至達(dá)到終止條件，這里T取為100，選擇最后一代的最優(yōu)個體作為尋優(yōu)的結(jié)果。
本文在遺傳算法的基礎(chǔ)上采用了一種較新的混合遺傳算法——免疫遺傳算法對公交靜態(tài)調(diào)度進(jìn)行了研究，并對二者的應(yīng)用結(jié)果進(jìn)行了仿真和比較，結(jié)果表明IGA有效的克服了簡單GA的不足之處，并提高了尋優(yōu)過程當(dāng)中目標(biāo)函數(shù)的收斂速度，并得到了合理的發(fā)車時刻表，可以提高公交企業(yè)的服務(wù)水平，對改善城市交通問題和節(jié)約市民出行時間有相當(dāng)?shù)膶嶋H意義。
參考文獻(xiàn)
[1]倪長健.免疫進(jìn)化算法研究及其在水問題中的應(yīng)用[D].四川大學(xué)博士論文，2003：50-51.
【關(guān)鍵詞】DNA遺傳算法；型遺傳算子
DNA計算中的DNA是重要的遺傳物質(zhì)攜帶著生物體的所有遺傳信息，而遺傳算法也是采用生物的遺傳信息進(jìn)行操作的算法，其不同是DNA計算是實驗室中進(jìn)行的而遺傳算法是在計算機(jī)上編程進(jìn)行的，將二者混合使用可以使遺傳算法在生物的遺傳調(diào)控機(jī)理中更深層次的進(jìn)行模擬，從而使遺傳算法的計算性能得到進(jìn)一步的提升。由于遺傳算法的優(yōu)越性和良好的性能，將其混合到DNA計算中可以突破其計算的局限性[1]【2】。因此學(xué)者開始對該混合的DNA遺傳算法進(jìn)行深入的研究，并取得了一定的成果。本文是在前人研究的基礎(chǔ)之上，對遺傳算法和DNA計算的混合使用中的算子進(jìn)行了深入的研究。
1.算法中改進(jìn)的新型算子的提出
1.1 改進(jìn)算子中的采用技術(shù)
受到DNA分子結(jié)構(gòu)的啟發(fā)，本文將用DNA的四種堿基對問題的潛在解進(jìn)行編碼，由于DNA的編碼方式不能直接被計算機(jī)處理，本文將使用二進(jìn)制表示的數(shù)0123對堿基進(jìn)行編碼。在這種編碼方式中，令0與鳥嘌呤相對應(yīng)，1與腺嘌呤對應(yīng)，2與胸腺嘧啶對應(yīng)，3與胞嘧啶對應(yīng)，并且0、1、2、3四個整數(shù)將采用二進(jìn)制的形式進(jìn)行表示。為了在在編碼中實現(xiàn)簡易的數(shù)學(xué)和邏輯操作，將二進(jìn)制數(shù)中的第一位作為區(qū)分嘌呤和嘧啶的編碼位即0代表嘌呤而1代表嘧啶。同時與互補(bǔ)堿基對對應(yīng)的代碼也呈現(xiàn)互補(bǔ)關(guān)系，如堿基對C和G互補(bǔ)組合由0（00）與3（11）構(gòu)成，而1（01）與2（10）構(gòu)成的A和T堿基對。這樣的互補(bǔ)配對關(guān)系，有助于新操作算子的設(shè)計。
下面是以上面的編碼方式為依據(jù)的一個n維的最小化問題：
示長度為的四進(jìn)制數(shù)字串，單個個體的編碼長度為，每個變量編碼精度由求得。
DNA-GA與遺傳算法用二進(jìn)制進(jìn)行計算編碼時的解碼方式相似。其均是以n維十進(jìn)制向量的形式對個體進(jìn)行解碼，其中：
上公式中的為整數(shù)串中的第維第列的數(shù)字。因為變量取值范圍的不同，所以按比例將變量進(jìn)行轉(zhuǎn)換，這樣就可以得到對應(yīng)問題的解。
按照這種模式進(jìn)行編碼，就可以引入更多的基因操作到遺傳算法中，這樣就可以設(shè)計算法效率更高更有效的算子。
本文所采用的適應(yīng)度函數(shù)和選擇算子是原遺傳算法中所采用的，這里就不再贅述。
1.2 改進(jìn)的新型算子
1.2.1 交叉算子
交叉操作是遺傳操作中的重要的生物信息遺傳操作，故本文對現(xiàn)有的交叉算子進(jìn)行了改進(jìn)，在其中加入了DNA計算中的生物操作技術(shù)，形成了新的算子。
（1）移位交叉算子
移位交叉的父體為一個，操作過程如圖1所示。移位操作是移換個體中的堿基子序列。設(shè)父代的基因為ATCGGTACAT，在父代中隨機(jī)選取一段子序列，這段子序列所包含的堿基數(shù)目和所選堿基的位置也是隨機(jī)選定的。然后將該段子序列移動到一個新的位置，形成一個新的個體。移位交叉算子的執(zhí)行概率為。如所選子序列是CGGT將其移動到C的后面形成新的個體。
（2）對換交叉算子
對換交叉操作在兩個隨機(jī)配對的個體之間進(jìn)行，操作過程如圖2所示。首先在優(yōu)質(zhì)的群體中隨機(jī)挑選兩個個體作為對換交叉操作的父體。然后在兩個父體中分別隨機(jī)選取一段堿基序列，且命名這個堿基序列為轉(zhuǎn)座子。如圖2，在兩個父體中隨機(jī)選擇兩段個數(shù)相同的堿基序列，交換這兩個父體所選中的堿基序列，形成新的個體。對換交叉操作的執(zhí)行概率為。
（3）抽換交叉算子
抽換交叉操作是需要從種群中選取兩個個體作為父代。而抽換交叉的目的就是改變個體之間的相似性，因此該操作中所選的父代不是隨機(jī)的，而是選擇兩個相似的個體。首先在適應(yīng)度較好的優(yōu)秀種群中隨機(jī)選取一個個體作為父代之一，在隨機(jī)選取兩個個體作為候選父代。然后通過對比候選父體與已知父體的相似度，選擇與已知父體更相似的個體作為抽換交叉操作的另一個父體。操作過程如圖3所示。抽換交叉算子的執(zhí)行概率為。
以上三種算子，都可以對單個的DNA序列進(jìn)行操作，而且各有特點。但是同時執(zhí)行三種算子將大大增加計算復(fù)雜度。本文將對換算子作為基本的交叉算子，移位算子和抽換算子則依據(jù)概率執(zhí)行。
1.2.2 新型變異算子
與以往的同變異算子不同，本文所提出的變異算子是以生物體內(nèi)的DNA轉(zhuǎn)錄成RNA并且通過其配對的反密碼子決定蛋白質(zhì)肽鏈的合成過程，并且計算在反密碼子中各個堿基所出現(xiàn)的概率，然后用低概率替換高概率或者高概率替換低概率的最大最小變異算子，最后形成新的DNA分子。生成一個新的個體。其變異概率為。其過程如圖4所示。
2.新提算子的運算步驟
步驟1：在運行算法之前，先對算法中所涉及到的參數(shù)進(jìn)行設(shè)置，如種群大的大小、終止闕值、最大進(jìn)化代數(shù)和所改進(jìn)新型算子的運行概率，普通變異概率等。
步驟2：隨機(jī)產(chǎn)生size個個體，組成初始種群，并將當(dāng)前的進(jìn)化代數(shù)設(shè)置為1.
步驟3：對個體進(jìn)行編碼串解碼，求出各個個體的適應(yīng)度值。
步驟4：按照適應(yīng)度值的大小將種群中的個體分為高適應(yīng)度個體和低適應(yīng)度個體，令交叉后產(chǎn)生的新個體數(shù)為Ncnew，并且從第一代交叉算起，不交叉時Ncnew為0。
步驟5：對種群中進(jìn)行交叉操作，選擇個體為父代個體，按其隨機(jī)產(chǎn)生的概率數(shù)與交叉。
概率、，進(jìn)行比較，所產(chǎn)生的隨機(jī)數(shù)小于哪個交叉算子的概率就執(zhí)行哪個交叉算子，最后產(chǎn)生新的個體，并且此時產(chǎn)生的新個體數(shù)為+1。
步驟6：對經(jīng)過交叉操作產(chǎn)生的個體以概率進(jìn)行變異操作。產(chǎn)生新個體。
步驟7：對經(jīng)過交叉和變異操作產(chǎn)生的個體用精英保留選擇機(jī)制進(jìn)行選擇保留，選出適應(yīng)度大的個體，此時進(jìn)化代數(shù)加1.
步驟8：判斷是否終止運行，其判斷條件是最大進(jìn)化代數(shù)或者是最大進(jìn)化代數(shù)的闕值。滿足就結(jié)束，輸出結(jié)果；否則返回步驟3繼續(xù)進(jìn)行。
3.實驗測試
為了測試出本文所提出的DNA遺傳算法的有效性和搜索性能，從以往的文獻(xiàn)中選取了兩個具有代表性的無約束的函數(shù)作為測試函數(shù)。本文使用改進(jìn)的DNA遺傳算法求解從文獻(xiàn)中選取的測試函數(shù)，它們的局部最優(yōu)點較多，欺騙性很強(qiáng)，一般的算法不易求解到這兩個函數(shù)的全局最優(yōu)點。其中，的最優(yōu)解為3600，在點（0，0）處取得，而的最優(yōu)解在點（0，0）處取得。
將這兩個函數(shù)分別用未經(jīng)過改進(jìn)的遺傳算法、基于進(jìn)化策略的遺傳算法（EGA）[3]和本文所提出的新的混合DNA遺傳算法（DNA-GA）進(jìn)行求解，并將所得到的結(jié)果進(jìn)行比較，三種算法的種群大小均為60，當(dāng)最大的進(jìn)化代數(shù)時終止運算。
為了對三種算法都進(jìn)行比較，在三種不同的算法下每個函數(shù)都運行了50次，三種算法的對比結(jié)果如表1、表2所示。
綜上所述，可以發(fā)現(xiàn)，本文所設(shè)計的遺傳算子對提高DNA遺傳算法的搜索性能有了很大的作用。對于和兩個函數(shù)而言，新型的變異算子在算法求解問題的收斂速度等方面提高比新型的交叉算子作用更大，因此將兩種新型的算子配合一起來使用，可以進(jìn)一步提高DNA遺傳算法性能。
4.結(jié)束語
本文在前人研究的基礎(chǔ)前提之上，對已有的算法進(jìn)行了改進(jìn)與創(chuàng)新，通過實驗函數(shù)的驗證本文所設(shè)計的遺傳算子對提高DNA遺傳算法的搜索性能有了很大的作用。
但是本文所改進(jìn)提出的新型算子還是只用于實驗研究，需要進(jìn)一步的使用實踐來證明與改進(jìn)。
參考文獻(xiàn)
[1]余文，李人厚.一種有效地雙向進(jìn)化算法[J].小型微型計算機(jī)系統(tǒng)，2003，24（3）：527-530.
[2]陳霄.DNA遺傳算法及其應(yīng)用研究[D].浙江科技大學(xué)博士論文，2010.
[3]王四春.GP算法中適應(yīng)度函數(shù)的光滑擬合與調(diào)整參數(shù)方法研究[J].自動化學(xué)報，2006（3）：23-30.
[4]陶吉利.基于DNA計算的遺傳算法及應(yīng)用研究[D].杭州：浙江大學(xué)博士論文，2007.
關(guān)鍵詞 全局最優(yōu)；混合算法；遺傳算法；powell方法
1 引言
不可微非線性函數(shù)優(yōu)化問題具有廣泛的工程和應(yīng)用背景，如結(jié)構(gòu)設(shè)計中使得結(jié)構(gòu)內(nèi)最大應(yīng)力最小而歸結(jié)為極大極小優(yōu)化（minmax）問題、數(shù)據(jù)魯棒性擬合中采取最小絕對值準(zhǔn)則建立失擬函數(shù)等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、powell方法等，但是這些方法都是局部優(yōu)化方法，優(yōu)化結(jié)果與初值有關(guān)。
近年來，由holland研究自然現(xiàn)象與人工系統(tǒng)的自適應(yīng)行為時，借鑒“優(yōu)勝劣汰”的生物進(jìn)化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數(shù)全局最優(yōu)解的方法。以遺傳算法為代表的進(jìn)化算法發(fā)展很快，在各種問題的求解與應(yīng)用中展現(xiàn)了其特點和魅力，但是其理論基礎(chǔ)還不完善，在理論和應(yīng)用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題，早在1989年goldberg就提出混合方法的框架[2]，把ga與傳統(tǒng)的、基于知識的啟發(fā)式搜索技術(shù)相結(jié)合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態(tài)而繼續(xù)接近全局最優(yōu)解。近來，文獻(xiàn)[3]和[4]在總結(jié)分析已有發(fā)展成果的基礎(chǔ)上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優(yōu)化方法結(jié)合構(gòu)成新的全局優(yōu)化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計算性能。文獻(xiàn)[5]采用牛頓－萊佛森法和遺傳算法進(jìn)行雜交求解旅行商問題，文獻(xiàn)[6]把最速下降法與遺傳算法相結(jié)合來求解連續(xù)可微函數(shù)優(yōu)化問題，均取得良好的計算效果，但是不適于不可微函數(shù)優(yōu)化問題。
本文提出把powell方法融入浮點編碼遺傳算法，把powell方法作為與選擇、交叉、變異平行的一個算子，構(gòu)成適于求解不可微函數(shù)優(yōu)化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數(shù)值算例對混合方法的有效性進(jìn)行了驗證。
2 混合遺傳算法
編碼是遺傳算法應(yīng)用中的首要問題，與二進(jìn)制編碼比較，由于浮點編碼遺傳算法有精度高，便于大空間搜索的優(yōu)點，浮點編碼越來越受到重視[7]。考慮非線性不可微函數(shù)優(yōu)化問題(1)，式中 為變量個數(shù)， 、 分別是第 個變量 的下界和上界。把powell方法嵌入到浮點編碼遺傳算法中，得到求解問題(1)如下混合遺傳算法：
min (1)
step1 給遺傳算法參數(shù)賦值。這些參數(shù)包括種群規(guī)模m，變量個數(shù)n，交叉概率pc、變異概率pm，進(jìn)行powell搜索的概率ppowell和遺傳計算所允許的最大代數(shù)t。
step2 隨機(jī)產(chǎn)生初始群體，并計算其適應(yīng)值。首先第i個個體適應(yīng)值取為fi’=fmax - fi，fi是第i個個體對應(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)行交叉操作。即對于選擇的兩個母體 和 ，算術(shù)交叉產(chǎn)生的兩個子代為 和 ， 是[0，1]上的隨機(jī)數(shù)，1 , 。
step5 按照概率 執(zhí)行非均勻變異算子[8]。若個體 的元素 被選擇變異， ，則變異結(jié)果為 ，其中 ，
(3)
(4)
返回區(qū)間[ , ]里的一個值，使 靠近0的概率隨代數(shù) 的增加而增加。這一性質(zhì)使算子在初始階段均勻地搜索空間，而在后面階段非常局部化。 是[ , ]之間的隨機(jī)數(shù)， 為最大代數(shù)， 為決定非均勻度的系統(tǒng)參數(shù)。
step6 對每個個體按照概率ppowell進(jìn)行powell搜索。若個體 被選擇進(jìn)行powell搜索操作，則以 作為初始點執(zhí)行powell方法得 ，若 則把所得計算結(jié)果 作為子代 ，否則，若 取 = ；若 取 = ，1 。
step7 計算個體適應(yīng)值，并執(zhí)行最優(yōu)個體保存策略。
step8 判斷是否終止計算條件，不滿足則轉(zhuǎn)向step3，滿足則輸出計算結(jié)果。
作為求解無約束最優(yōu)化問題的一種直接方法，powell法的整個計算過程由若干輪迭代組成，在每一輪迭代中，先依次沿著已知的n個方向搜索，得一個最好點，然后沿本輪迭代的初始點與該最好點連線方向進(jìn)行搜索，求得這一階段的最好點。再用最后的搜索方向取代前n個方向之一，開始下一階段的迭代。為了保持算法中n個搜索方向是線性無關(guān)的，保證算法的收斂性，對替換方向的規(guī)則進(jìn)行改進(jìn)，在混合法的計算步驟step6中采用文[9]中的改進(jìn)powell方法，其求解過程如下：
(1) 變量賦初值 ，n個線性無關(guān)的n個方向 , ,…, ，和允許誤差ε>0，令k=1。
(2) 令 ，從 出發(fā)，依次沿方向 , ,…, 作一維搜索，得到點 , ,…, 求指標(biāo)m，使得 - =max { - }，令 。若 ε，則powell方法計算結(jié)束，否則，執(zhí)行(3)。
(3) 求 使得 =min ，令 = = ，若 ，則powell方法計算結(jié)束，得點 ；否則，執(zhí)行(4)。
(4) 若 ，令 ，否則令 ( )，然后置 ，轉(zhuǎn)(2)。
3 算例
t [-500,500]
圖1 函數(shù)f(x)特性示意圖
函數(shù)f(x)有相當(dāng)多的極小點,全局極小點是 =-420.97， =1,2,…, ，最優(yōu)值為-837.97；次最優(yōu)點為 ={( , ,…, )： =-420.97, , =302.52}， =1,2,…, ，次優(yōu)值-719.53。變量個數(shù)n=2時函數(shù)f(x) 特性如圖1示。程序編制和運行環(huán)境采用fortran power station 4.0，隨機(jī)數(shù)由內(nèi)部隨機(jī)函數(shù)產(chǎn)生，在奔騰133微機(jī)上運行。
采用改進(jìn)的powell方法計算100次，初值在區(qū)間[-500,500]內(nèi)隨機(jī)產(chǎn)生，只有6次（即以概率0.06）搜索到全局最優(yōu)，計算成功的概率極低。
holland建立的標(biāo)準(zhǔn)（或簡單）遺傳算法，其特點是二進(jìn)制編碼、賭輪選擇方法、隨機(jī)配對、一點交叉、群體內(nèi)允許有相同的個體存在。取種群規(guī)模m=30，交叉概率pc=0.95、變異概率pm=0.05，最大進(jìn)化代數(shù)t=1000，每個變量用串長為l=16的二進(jìn)制子串表示。二進(jìn)制編碼比浮點編碼遺傳算法計算精度低，對于標(biāo)準(zhǔn)遺傳算法以目標(biāo)函數(shù)小于-800為搜索成功，標(biāo)準(zhǔn)遺傳算法運行100次。當(dāng)取最大進(jìn)化代數(shù)為t=200時，40次（以概率0.40）搜索到全局最優(yōu)，平均計算時間為0.51秒；當(dāng)取t=500時，51次（以概率0.51）搜索到全局最優(yōu)，平均計算時間為1.13秒。
采用本文混合法計算，取m=30， pc=0.85、pm=0.2，t=100，進(jìn)行powell搜索的概率ppowell取不同值，混合法運行100次，計算結(jié)果見如表1。對于這個具有多極值的算例，多次計算表明ppowell=0.3時，混合法能以完全概率搜索到全局最優(yōu)的準(zhǔn)確值，但是此時混合法計算時間約為標(biāo)準(zhǔn)遺傳算法取t=500時計算時間的4/5。對應(yīng)的浮點編碼遺傳算法，取m=30，pc=0.85、pm=0.2，t=100，運行100次，82次（以概率0.82）搜索到全局最優(yōu)（如表1中ppowell =0所示），計算時間約為標(biāo)準(zhǔn)遺傳算法取t=500時計算時間的1/8，但是搜索到全局最優(yōu)的概率卻遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)遺傳算法。
表1 ppowell取不同值時混合法的計算結(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
平均計算時間/ 秒
0.14
0.20
0.31
0.47
0.68
0.87
4 結(jié)束語
針對不可微函數(shù)的全局優(yōu)化問題，本文提出一種把powell方法與浮點編碼遺傳算法相結(jié)合的混合遺傳算法，該算法兼顧了遺傳算法全局優(yōu)化方面的優(yōu)勢和powell方法局部搜索能力較強(qiáng)的特點，提高求得全局解的概率。計算結(jié)果表明混合法優(yōu)于遺傳算法和powell法，可以可靠地搜索到具有多個局部極值的函數(shù)優(yōu)化問題的全局解。由于計算中只用到函數(shù)值信息，本文混合法不僅適用于不可微函數(shù)優(yōu)化問題，也適合可微函數(shù)全局優(yōu)化問題。
參考文獻(xiàn)
[1] 周明，孫樹林．遺傳算法原理及應(yīng)用[m]．北京：國防工業(yè)出版社，1999．
[2] goldberg d e. genetic algorithms in search, optimization and machine learning[m]. reading, ma: addison wesley,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] lin w，delgado-frias j g．hybrid newton-raphson genetic algorithm for traveling salesman problem[j]. cybernetics and systems, 1995，26(5)：387-412．
[6] 趙明旺．連續(xù)可微函數(shù)全局優(yōu)化的混合遺傳算法[j] ．控制與決策，1997，12(5)：589－592．
[7] goldberg d e．real-code genetic algorithm,virtual alphabets and blocking[j]. complex systems，1991，5：139-167．
[8] michalewicz z．a(chǎn) modified genetic algorithm for optimal control problems[j]．computers math. application，1992，23（12）：83-94．
[9] 陳寶林．最優(yōu)化理論與算法[m]．北京：清華大學(xué)出版社，1989．
[10] 俞紅梅．全過程系統(tǒng)能量綜合方法的研究[d]．大連理工大學(xué)博士學(xué)位論文，1998．
hybrid approach for global optima of indifferentiable nonlinear function abstract a hybrid computational intellective algorithm for locating the global optima of indifferentiable nonlinear function was put forward by setting the powell algorithm in real-code genetic algorithm. the hybrid approach improved the local searching ability of the genetic algorithm and promoted the probability for the global optima greatly. because only the objective values are used, the hybrid approach is a generalized genetic algorithm for global optima of differentiable and indifferentiable nonlinear functions.
關(guān)鍵字：遺傳算法；地理信息系統(tǒng)；公交線路網(wǎng)
中圖分類號：TP183 文獻(xiàn)標(biāo)識碼：A文章編號：1007-9599 (2010) 15-0000-02
GIS Bus Line Network Optimization Model Based on Genetic Algorithm
Yuan Hua1,Yu Xinshui2,Tang Weidong3
(1.Southwest Forestry University,Kunming650224,China;2.Forest Resources Management Station of Baoshan,Baoshan678000,China;
3.Forestry Administration Office of Nujiang,Nujiang673100,China)
Abstract: This paper studies the optimization strategy for the city bus lines.Traffic problems in urban public transport the city has been plagued,a difficult problem to solve the problem of urban public transport operation and improve the efficiency of urban transport,vehicle scheduling to improve the efficiency of public transport,this paper presents a genetic algorithm based optimization strategy for GIS bus lines. The strategy for geographic information system (GIS) as a platform,the genetic algorithm optimization model for the spatial layout of the bus transport network optimized layout algorithm.
Keywords:Genetic algorithms;Geographic information system;Bus lines network
隨著社會的快速發(fā)展，公共交通工具已逐漸成為人們?nèi)粘３鲂械闹饕煌üぞ撸覈鞒鞘械墓幌到y(tǒng)也迅速發(fā)展，公眾出行較為通暢、便利。但與此同時，搭乘公交時，乘客也面臨著多條線路的選擇問題。在這種情況下，研制開發(fā)出一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)，已成為一個非常值得研究與探討的問題。公交線路選擇問題的研究，涉及乘客心理、路段流量、公交容量、換乘耗時、及站點分配等諸多因素。這些因素彼此約束，內(nèi)在聯(lián)系較為細(xì)微，各種因素難以精確分析并予以量化，處理起來較為復(fù)雜。而由于大中型城市的公交線路數(shù)、站點數(shù)都已達(dá)到百、千數(shù)量級，數(shù)據(jù)處理的繁瑣性進(jìn)一步增大了問題本身的難度。
地理信息系統(tǒng)（GIS）是以計算機(jī)技術(shù)為基礎(chǔ)的信息管理技術(shù)，它主要是完成空間數(shù)據(jù)的采集、維護(hù)、存儲、分析、輸出和等功能。GIS和空間分析一方面通過記錄地物的坐標(biāo)值定量化了空間位置，另一方面又通過存儲這些地物的屬性表格描述了地物特性。它能夠全面的分析這些地物的空間關(guān)系和相互影響，并能夠直觀和靈活的顯示空間數(shù)據(jù)和空間分析結(jié)果。因此，GIS已經(jīng)成為解決涉及空間相關(guān)問題的唯一方案。目前GIS已經(jīng)被廣泛的應(yīng)用到各個領(lǐng)域。本文針對城市公交交通問題一直困擾城市一大難題，是為了解決城市公共交通運行問題，改善城市交通運行效率，提高公共交通車輛調(diào)度效率，本文提出了基于遺傳算法GIS公交線路網(wǎng)優(yōu)化策略。該策略以地理信息系統(tǒng)（GIS）為平臺，遺傳算法為空間布局優(yōu)化模型的公交車交通網(wǎng)優(yōu)化布局算法。
一、遺傳算法
遺傳算法（GA）提供了一種受生物進(jìn)化啟發(fā)的學(xué)習(xí)方法。它不再是從一般到特殊或從簡單到復(fù)雜地搜索假設(shè)，而是通過變異和重組當(dāng)前已知的最好假設(shè)來生成后續(xù)的假設(shè)。在每一步，被稱為當(dāng)前群體（population）的一組假設(shè)被更新，方法是通過使用目前適應(yīng)度最高的假設(shè)的后代替代群體的某個部分。這個過程形成了對假設(shè)的生成并測試（generate-and-test）柱狀搜索（beam-search），其中若干個最佳當(dāng)前假設(shè)的變體最有可能。采用遺傳算法主要有以下幾個優(yōu)點：
（一）將搜索過程作用在編碼后的字符串上，不直接作用在優(yōu)化問題的具體變量上，在搜索中用到的是隨機(jī)的變換規(guī)則，而不是確定的規(guī)則。它在搜索時采用啟發(fā)式的搜索，而不是盲目的窮舉，因而具有更高所搜索效率。
（二）現(xiàn)行的大多數(shù)優(yōu)化算法都是基于線性、凸性、可微性等要求，而遺傳算法只需要適合度信息，不需要導(dǎo)數(shù)等其他輔助信息，對問題的依賴性較小，因而具有高度的非線性，適用范圍更廣。此外還可以寫出一個通用算法，以求解許多不同的優(yōu)化問題。
（三）遺傳算法從一組初始點開始搜索，而不是從某一個單一的初始點開始搜索。而且給出的是一組優(yōu)化解 ，而不是一個優(yōu)化解，這樣可以給設(shè)計者更大的選擇余地。它能在解空間內(nèi)充分搜索，具有全局優(yōu)化能力。
（四）遺傳算法具有很強(qiáng)的易修改性。即使對原問題進(jìn)行很小的改動 （ 比如目標(biāo)函數(shù)的改進(jìn) ），現(xiàn)行的大多數(shù)算法就有可能完全不能使用 ，而遺傳算法則只需作很小的修改就完全可以適應(yīng)新的問題。
（五）遺傳算法具有很強(qiáng)的可并行性，可通過并行計算來提高計算速度， 因而更適用于大規(guī)模復(fù)雜問題的優(yōu)化。
二、遺傳算法GIS公交線路網(wǎng)優(yōu)化模型
（一）模型的建立
設(shè)城市公交系統(tǒng)共有 個站點，（本問題中 ）， 條公交線路，設(shè)站點和線路通過一個3維的0-1矩陣來表達(dá)。設(shè)
這樣該城市的公交網(wǎng)絡(luò)通過該0-1矩陣能完全表達(dá)。
設(shè)決策變量為 ，意義為：
則當(dāng)站點i和j之間無第k條線路時，i和j之間則不能通過第k條線路到達(dá)，因此有：
（1）
設(shè)起始點為a，目標(biāo)點為b，我們目的是在在a和b之間插入r個站點 ，使得a， ，b構(gòu)成一個可到達(dá)的線路。即：
（2）
目標(biāo)函數(shù)我們考慮費用最小，時間最小和換乘次數(shù)最小三個目標(biāo)。
設(shè) ，表示線路 是否需要通過 換乘。當(dāng) 則線路 不換乘；當(dāng) 則線路 換乘。
則換乘次數(shù)最少的目標(biāo)為
要求時間最小，則有：
其中 為經(jīng)過站點數(shù)， 為坐車時間； 表示換乘時間.二者之和為總時間。設(shè)線路a， ，b計算得到費用為Cost，計算方法根據(jù)一元制和分段計價制度的規(guī)則進(jìn)行計算總費用最小的目標(biāo)函數(shù)為：
最后得到的總模型為：換乘次數(shù)最少
時間最少
費用最小
（3）
對該模型的求解，我們可以根據(jù)換乘次數(shù)最少得到最優(yōu)結(jié)果，也可以根據(jù)時間最少得到最優(yōu)結(jié)果，還也可以根據(jù)費用最少得到最優(yōu)結(jié)果。把三種情況下的最好結(jié)果都可以提供給顧客考慮，由顧客根據(jù)自己的需要選擇。當(dāng)然有的結(jié)果會是兩種或三種目標(biāo)最小情況下的解，這樣就更好。
（二）模型求解
基于本文前面所提到的遺傳算法GIS公交線路網(wǎng)優(yōu)化模型，設(shè)計出公交線路網(wǎng)的求解的流程圖如圖1所示，同時以地理信息系統(tǒng)（GIS）平臺，選取了蘇州市公交網(wǎng)絡(luò)作為實驗數(shù)據(jù)。
三、結(jié)束語
為了解決城市公共交通運行擁擠問題，改善城市交通運行效率，提高公共交通車輛調(diào)度效率，本文提出了基于遺傳算法GIS公交線路網(wǎng)優(yōu)化策略。構(gòu)建了公交系統(tǒng)的數(shù)學(xué)模型，并提出了采用遺傳算法求解該模型，該策略以地理信息系統(tǒng)（GIS）為平臺，遺傳算法為空間布局優(yōu)化模型的公交車交通網(wǎng)優(yōu)化布局算法。
參考文獻(xiàn)：
[1]徐士偉.等.GIS技術(shù)在公共交通規(guī)劃中的應(yīng)用[D].同濟(jì)大學(xué)道路與交通工程系碩士學(xué)位論文,2000
[2]劉光明,蔡先華.一種城市公交查詢的算法及其應(yīng)用[J].交通運輸工程與信息學(xué)報,2005,3(2):87-91
[3]曹桂發(fā),傅俏梅.城市交通信息系統(tǒng)的設(shè)計研制[J].系統(tǒng)工程理論與實踐,1997,(1):105-109
[4]時敬梁,田世峰.遺傳算法在公交車輛智能排班系統(tǒng)中的應(yīng)用研究.人工智能與識別技術(shù),2007(5):1679-1681
資助項目：西南林業(yè)大學(xué)森林經(jīng)理學(xué)國家林業(yè)局重點學(xué)科資助（XKZ200901），云南省省級重點建設(shè)專業(yè)西南林業(yè)大學(xué)林學(xué)專業(yè)資助。
關(guān)鍵詞：入侵檢測器；量子遺傳算法；協(xié)同進(jìn)化
中圖分類號：TP274文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)13-3199-03
Research on Generating Method of Detector in IDS
LI Lu-lu
(College of Computer Science and Engineering Institute, Yulin Normal College, Yulin 537000, China)
Abstract: The generation of intrusion detection device is the core o f the intrusion detection system, In place of com plex problem of optimizaion, quantum genetic algorithm has strong searching capabilities and the most optimal performance. In this paper a quantum genetic algorithm coevolution detector generation method is proposed. The population needing to evolve is divided to some child population by simulating nature cooperative coevolution mechanism, and each population using quantum genetic algorithm to optimize, making whole intrusion detection system has good adaptability and diversity.
Key words: intrusion detection device; quantum genetic algorithm; cooperative coevolution
1概述
隨著網(wǎng)絡(luò)和計算機(jī)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)安全性問題日益突出起來，入侵檢測系統(tǒng)是一種重要的安全防范技術(shù)，已成為網(wǎng)絡(luò)安全的重要保障之一[1-2]。目前各種不同的攻擊方式不斷出現(xiàn)，因此入侵檢測中的有關(guān)智能性研究逐漸成為入侵檢測系統(tǒng)研究領(lǐng)域中的一個重要方向。而入侵檢測系統(tǒng)的主要部件是檢測器，檢測器生成算法是生成有效檢測器的關(guān)鍵，是檢測異常變化的核心所在[3-4]。檢測器的設(shè)計對入侵檢測系統(tǒng)的性能有著重要的影響，其從產(chǎn)生到成熟再到被丟棄，有自身固有的過程和生命周期，可以利用遺傳算法來生成一個成熟檢測器集，采用交叉、變異等遺傳操作對其進(jìn)行進(jìn)化，使成熟檢測器群體向“非我”進(jìn)化。但隨著問題規(guī)模的不斷擴(kuò)大和搜索空間的更加復(fù)雜，遺傳算法在實際應(yīng)用中有一定的局限性，不能表現(xiàn)出算法的優(yōu)越性，出現(xiàn)迭代次數(shù)多、收斂速度慢、易陷入局部最優(yōu)值和過早收斂等問題。
量子遺傳算法結(jié)合了量子計算和遺傳算法的優(yōu)點，它將量子所具有的獨特計算能力和遺傳算法的全局尋優(yōu)能力結(jié)合起來，提升了算法的優(yōu)化性能，比傳統(tǒng)遺傳算法具有更高的搜索效率[5]。該文在現(xiàn)在有研究的基礎(chǔ)上提出一種檢測器生成方法，該算法通過對自然界中的協(xié)同進(jìn)化機(jī)制進(jìn)行模擬，首先將要進(jìn)化的種群劃分為多個子種群，然后各個種群再分別利用量子遺傳算法進(jìn)行優(yōu)化，使整個入侵檢測系統(tǒng)具有良好的自適應(yīng)性和多樣性。
2相關(guān)知識
量子遺傳算法本質(zhì)上是種概率優(yōu)化方法，其基本思想是基于量子計算原理，用量子比特編碼來表示染色體，充分利用量子態(tài)的疊加性和相干性，以當(dāng)前最優(yōu)個體的信息為指導(dǎo)，通過量子門來完成種群的更新操作，以此來促進(jìn)算法的收斂，從而來實現(xiàn)目標(biāo)的最后優(yōu)化求解。
2.1量子比特
通常在計算機(jī)中用二進(jìn)制0和1來表示信息單元，而在量子計算機(jī)中是用一個雙態(tài)量子系統(tǒng)即量子比特來表示信息單元。量子比特作為信息單位，形式上表示為兩種基態(tài)|0>和|1>，一般用|0>表示0，用|1>表示1。與經(jīng)典比特不同，量子比特不僅可以處于兩種基態(tài)|0>和|1>，而且還可以處在中間態(tài)，也就是|0>和|1>的不同疊加態(tài)。因此，量子比特的狀態(tài)可用下式表示：
2.2量子染色體[6]
量子遺傳算法是采用量子比特的編碼方式，用一個復(fù)數(shù)對(α,β)表示一個量子比特。若一個量子染色體包含m個量子比特，則由m個復(fù)數(shù)對組成。這個染色體編碼形式如下：
2.3量子旋轉(zhuǎn)門
在量子遺傳算法中量子染色體一般是糾纏或疊加的，所以可以用量子門來表示染色體的各個糾纏態(tài)或疊加態(tài)；父代群體不能決定子代個體的產(chǎn)生，個體的產(chǎn)生是通過父代的最優(yōu)個體以及它們狀態(tài)的概率幅決定的。用構(gòu)造的量子門表示量子疊加態(tài)或糾纏態(tài)的基態(tài)，它們彼此干涉使相位發(fā)生改變，以此達(dá)到改變各個基態(tài)的概率幅的目的。因此，如何構(gòu)造合適的量子門是量子遺傳操作和量子遺傳算法亟待解決的關(guān)鍵問題，量子門構(gòu)造的是否合適會影響到遺傳算法的性能。目前在量子遺傳算法中通常采用量子旋轉(zhuǎn)門U，U可表示為
，θ為旋轉(zhuǎn)角。
2.4量子變異[7]
通常情況下在遺傳算法中，算法的局部搜索能力以及阻止未成熟染色體收斂這些操作都是通過變異作用實現(xiàn)的，量子變異必須達(dá)到量子遺傳算法對變異操作的要求，這里我們這樣定義量子比特的變異操作：
（1）從種群中以給定的概率pi隨機(jī)地選擇若干個體；
（2）確定變異位，以確定的概率對從（1）中選擇的個體隨機(jī)地確定變異位；（3）對換操作，對換選中位量子比特的概率幅。
2.5協(xié)同進(jìn)化算法[8]
進(jìn)化算法的本質(zhì)是優(yōu)化，是為了使物種在激烈的競爭中能夠具備生存的本領(lǐng)以致在競爭中能夠生存下來。在一般的遺傳算法中要么只涉及到個別群或個體的進(jìn)化，要么只是涉及種群之間的競爭，幾乎沒有顧及到個體與個體，種群與種群之間互惠寄生的協(xié)同關(guān)系?；谝陨显?，提出了協(xié)同進(jìn)化算法。協(xié)同進(jìn)化是生態(tài)系統(tǒng)中眾多進(jìn)化方式中的一種，進(jìn)化中種群要生存下來不僅要受自身因素的影響，同時也受周圍同類或異類的相互影響，在這些因素的影響下能夠生存下來。在進(jìn)化的過程中種群的個體之間及其與其它種群之間都要進(jìn)行相互作用相互影響。
3基于量子遺傳算法的協(xié)同進(jìn)化檢測器生成算法設(shè)計思路
算法的基本思想：首先對隨機(jī)生成的種群進(jìn)行種群分割，將種群分成若干個子種群。利用空間形態(tài)學(xué)的原理，根據(jù)種群中各個自體間的距離來判斷它們是否屬于一個分割，各個子群之間互相協(xié)作，以確保整個系統(tǒng)的適應(yīng)度不斷提高；用量子遺傳算法對單個子群進(jìn)行進(jìn)化。量子遺傳算法優(yōu)化檢測器的入侵檢測模型如圖1所示。圖1量子遺傳算法優(yōu)化檢測器的入侵檢測模型
（1）種群的初始化策略
在量子遺傳算法中種群初使化操作通常是這樣進(jìn)行的，各個體的量子位概率幅() 2，也就是說各個體的全部狀態(tài)出現(xiàn)的概率相同。協(xié)同進(jìn)化需要多個種群，因此必須增加種群的多樣性，所以在初始化時我們將量子位概率空間平均分為N個，即體表N個子群，0、1極限概率為δ，用公式（1）來初始化第k個子種群，也就是將同子種群內(nèi)的每個個體初始化為量子染色體，每個量子染色體的概率相同，不同子種群個體的狀態(tài)以不同概率出現(xiàn)，以此來達(dá)到增加初始化個體多樣性的目的。（2）量子門更新策略
采用進(jìn)化方程的方式來調(diào)整量子門的旋轉(zhuǎn)角大小和方向。這樣做有兩個好處：一是減少了參數(shù)的個數(shù)，同時算法的結(jié)構(gòu)也得到了簡化；另一個是利用進(jìn)化方程的記憶的，可以利用個體自身的局部最優(yōu)信息，鄰域種群的最優(yōu)信息，以及整個種群最優(yōu)狀態(tài)的信息，從而使旋轉(zhuǎn)角θ能夠得到更加合理的調(diào)整，還能夠更好地跳出局部極值。進(jìn)化方程可定義為：U=?
p -xi，其中k1，k2，k3，k4為影響因子，pi，pj是左右鄰域種群極值，pm為個體所在種群極值，p為全局極值。
（3）具體實現(xiàn)步驟
Step1：將量子位概率空間平均分為N個，即體表N個子群，0、1極限概率為δ，用公式子種群，也就是將同子種群內(nèi)的每個個體初始化為量子染色體，每個量子染色體的概率相同，不同子種群個體的狀態(tài)以不同概率出現(xiàn)，以此增加初始化個體的多樣性。
Step2：初始化步驟1中的每一個子群Qi( )
Step4：依次對Pi( ) t進(jìn)行適應(yīng)度評估；
Step6：保留步驟5中得到的N個最佳個體，如果此時得到了滿意解，則算法終止，否則轉(zhuǎn)入Step7；
Step7：采用（2）中定義的量子門U( )
Step8：以確定的概率進(jìn)行量子變異；
Step9：對于每個新的子代Qi() t+1，算法轉(zhuǎn)至Step4繼續(xù)進(jìn)行。
4結(jié)論
檢測器集的好壞決定了入侵檢測系統(tǒng)的性能,因而檢測器集的生成算法是入侵檢測系統(tǒng)開發(fā)中最核心的部分。該文引入量子遺傳算法來實現(xiàn)檢測器的優(yōu)化過程,設(shè)計了基于遺傳算法的檢測器生成算法。該算法通過模擬自然界協(xié)同進(jìn)化機(jī)制，把需要進(jìn)化的種群劃分為多個子種群，各個種群采用量子遺傳算法進(jìn)行優(yōu)化，使整個入侵檢測系統(tǒng)具有良好的自適應(yīng)性和多樣性。在接下來的研究中，將重點研究侵檢測器中各參數(shù)的影響程度的問題,以提高入侵檢測系統(tǒng)的自適應(yīng)性和有效性，進(jìn)一步提高入侵檢測的準(zhǔn)確率。
參考文獻(xiàn)
[1]卿斯?jié)h,蔣建春,馬恒太,等.入侵檢測技術(shù)研究綜述[J].通信學(xué)報,2004(7):19-29.
[2]林果園,黃皓,張永平.入侵檢測系統(tǒng)研究進(jìn)展[J].計算機(jī)科學(xué),2008,35(2):69-74.
[3]葛麗娜,鐘誠.基于人工免疫入侵檢測檢測器生成算法[J].計算機(jī)工程與應(yīng)用,2005(23):150-152.
[4]楊東勇,陳晉因.基于多種群遺傳算法的檢測器生成算法研究[J].自動化學(xué)報,2009,35(4):425-432.
[5]羅文堅,曹先彬,王煦法.檢測器自適應(yīng)生成算法研究[J].自動化學(xué)報,2005,35(6):907-916.
[6]趙麗,李智勇.求解入侵檢測問題的量子免疫算法[J].計算機(jī)工程與應(yīng)用,2011,47(11).
眾所周知，配電網(wǎng)系統(tǒng)規(guī)模較大、信息聚集點眾多、結(jié)構(gòu)組成復(fù)雜，因此與其相配的繼電保護(hù)裝置也隨之分布在配電網(wǎng)系統(tǒng)中不同的位置，其應(yīng)用范圍上至變電站下到變電站內(nèi)部與配電系統(tǒng)直接相關(guān)聯(lián)的設(shè)備，以及在電網(wǎng)中開閉所、中壓配電饋線、低壓配電網(wǎng)以及配變站等。繼電保護(hù)裝置長久以來就是配電網(wǎng)中的重要組成部分，其發(fā)展經(jīng)歷與電力系統(tǒng)中的繼保裝置是完全相同的，由最初的電磁型繼電保護(hù)裝置，發(fā)展至晶體管型繼電保護(hù)裝置，在電力電子器件廣泛應(yīng)用后又出現(xiàn)了集成電路型繼電保護(hù)裝置。時至今日，伴隨計算機(jī)技術(shù)的日新月異，所使用的繼電保護(hù)裝置多數(shù)屬于微機(jī)型繼電保護(hù)裝置，但仍有各種類型的繼電保護(hù)裝置應(yīng)用于不同的配電網(wǎng)系統(tǒng)中以適用不同層次電網(wǎng)的要求。伴隨著微機(jī)系統(tǒng)繼電保護(hù)裝置性能更加優(yōu)良、操作更加方便、維護(hù)更加簡單，其在高壓特高壓電網(wǎng)中的推廣逐漸成功，其應(yīng)用日益廣泛，更加深得人心。越來越多地適用于中低壓配電網(wǎng)的繼電保護(hù)裝置也被不斷開發(fā)應(yīng)用。
2配電網(wǎng)保護(hù)存在的問題
電力系統(tǒng)繼電保護(hù)的主要工作任務(wù)是切除系統(tǒng)中的故障設(shè)備以保障系統(tǒng)的正常運行。由于技術(shù)等各方面的原因，由常規(guī)繼電保護(hù)裝置構(gòu)成的繼電保護(hù)系統(tǒng)是一種非自適應(yīng)繼電保護(hù)系統(tǒng)，其動作特性不能隨著電力系統(tǒng)的運行方式的變化而自行改變。常規(guī)繼電保護(hù)的整定值是按照離線最嚴(yán)重的情況進(jìn)行的，而且在運行中基本保持不變。因此，在常規(guī)繼電保護(hù)整定計算過程中不得不按照每套保護(hù)對應(yīng)的電力系統(tǒng)最大運行方式來計算保護(hù)的動作值，按照每套保護(hù)對應(yīng)的電力系統(tǒng)最小運行方式來校驗保護(hù)的靈敏度。這種按最嚴(yán)重的運行條件確認(rèn)保護(hù)整定值的方法，雖可保證在電力系統(tǒng)各種運行方式下發(fā)生故障時，繼電保護(hù)能正確動作，但同時存在著兩個缺點：一是按照該方法確定的繼電保護(hù)整定值，對電力系統(tǒng)其它運行方式來講不是最佳的整定值；二是在電力系統(tǒng)最小運行方式下最不利的故障時，繼電保護(hù)系統(tǒng)的性能會嚴(yán)重變壞甚至導(dǎo)致拒動現(xiàn)象。這兩個缺點不但限制了電網(wǎng)運行的靈活性，而且也降低了電網(wǎng)運行的穩(wěn)定性。正是在這樣的背景下提出了自適應(yīng)保護(hù)的概念。自適應(yīng)保護(hù)是指根據(jù)電力系統(tǒng)運行方式和故障狀態(tài)的變化能實時改變保護(hù)性能、特性或定值的保護(hù)。隨著具有高速運算和邏輯判斷能力、強(qiáng)大的記憶能力以及其固有的可編程性的微機(jī)保護(hù)在電力系統(tǒng)中的廣泛應(yīng)用和通信手段與通信技術(shù)的不斷發(fā)展與進(jìn)步，實現(xiàn)自適應(yīng)繼電保護(hù)已成為可能。
3遺傳算法的配電網(wǎng)自適應(yīng)保護(hù)
自適應(yīng)繼電保護(hù)是在上世紀(jì)80年代提出的一個較新的研究課題。它的最主要任務(wù)就是解決目前繼電保護(hù)裝置中所無法解決的問題，使得繼電保護(hù)裝置更趨于完善，現(xiàn)在所研制的適用于輸電線路和配電系統(tǒng)元件的各類型微機(jī)繼電保護(hù)裝置，已經(jīng)具備完全取代傳統(tǒng)裝置的能力，能夠迅速將電力系統(tǒng)中發(fā)生故障的電氣元件進(jìn)行切除，使其免于遭受損壞，并使得其它無故障線路迅速恢復(fù)正常運行。遺傳算法，是建立于達(dá)爾文的生物論以及孟德爾遺傳學(xué)說基礎(chǔ)之上的一種借鑒生物界自然選擇和自然遺傳機(jī)制的高度并行、隨機(jī)、自適應(yīng)搜索算法，具有堅實的生物學(xué)基礎(chǔ)。遺傳算法強(qiáng)調(diào)從生物群體觀點出發(fā)，看待種群優(yōu)化問題。依據(jù)遺傳算法的思想，我們把所求問題中的每一個點都看做是一個個體，這些個體組成了群體，正因為如此，種群中的每一個個體都可以代表一個優(yōu)化問題的可行解。本論文提出的基于遺傳算法的配電網(wǎng)自適應(yīng)繼電保護(hù)，該保護(hù)是利用電網(wǎng)全局信息、保護(hù)定值在線整定的新型保護(hù)。
4基于Matlab算法的仿真和分析
在實際應(yīng)用過程中，第一階段的預(yù)測模型在處理高維度、非線性數(shù)據(jù)時，無法獲得優(yōu)質(zhì)結(jié)果；而神經(jīng)網(wǎng)絡(luò)模型在學(xué)習(xí)樣本數(shù)量有限時，學(xué)習(xí)過程誤差易收斂于局部極小點，預(yù)測精度難以保證；學(xué)習(xí)樣本變量很多時，又容易陷入維數(shù)災(zāi)難。由于影響機(jī)制復(fù)雜，考慮到支持向量機(jī)是建立在結(jié)構(gòu)化風(fēng)險最小化原則之上，可以有效地減少經(jīng)驗風(fēng)險帶來的影響，不僅對小樣本數(shù)據(jù)表現(xiàn)出良好的擬合精度，還對獨立的測試集表現(xiàn)出較小的誤差，在一定程度上對學(xué)習(xí)機(jī)的泛化能力有所提升，而且支持向量機(jī)算法是一個凸優(yōu)化問題，在物流需求預(yù)測方面具有較明顯的優(yōu)勢，本文采用基于支持向量機(jī)學(xué)習(xí)理論的物流園區(qū)需求預(yù)測方法對成都市貨運量進(jìn)行預(yù)測。
支持向量機(jī)參數(shù)的選取直接影響模型的預(yù)測精度，傳統(tǒng)的網(wǎng)格搜索參數(shù)組合已經(jīng)無法滿足對區(qū)域物流需求預(yù)測的精度要求，本文采用遺傳算法對支持向量機(jī)進(jìn)行參數(shù)尋優(yōu)，構(gòu)建GA-SVM區(qū)域物流需求預(yù)測模型，并對成都市物流需求進(jìn)行預(yù)測，結(jié)果證明GA-SVM預(yù)測模型的預(yù)測精度要優(yōu)于傳統(tǒng)的SVM預(yù)測模型。
2 GA-SVM預(yù)測模型的算法設(shè)計
2.1 支持向量機(jī)
支持向量機(jī)（Support Vector Machine，SVM），是Vapnik在20世紀(jì)90年代中期以統(tǒng)計學(xué)為基礎(chǔ)提出的一種新型機(jī)器學(xué)習(xí)方法，作為統(tǒng)計學(xué)理論中比較年輕和實用的理論，已經(jīng)在實際應(yīng)用中得到很大的發(fā)展，尤其是在小樣本、非線性及高維分類和回歸問題中表現(xiàn)出了比較出色的效果。
相較于多項式核函數(shù)和Sigmoid核函數(shù)，徑向基核函數(shù)在先驗知識不足的情況下，擁有更好的預(yù)測精度。因此，本文GA-SVM預(yù)測模型采用徑向基核函數(shù)作為預(yù)測模型的核函數(shù)。則SVM模型的待優(yōu)化參數(shù)有：核函數(shù)參數(shù)、不敏感函數(shù)參數(shù)和懲罰參數(shù)C。核函數(shù)參數(shù)是映射函數(shù)的參數(shù)，通過改變函數(shù)關(guān)系來影響映射的特征空間，表示映射規(guī)律的復(fù)雜程度；不敏感函數(shù)參數(shù)表示所能容忍的最高誤差，影響支持向量的個數(shù)；懲罰參數(shù)C是在確定的特征空間中調(diào)節(jié)學(xué)習(xí)機(jī)器的置信范圍和經(jīng)驗風(fēng)險的比例，對模型的泛化能力有很大影響。為了控制GA-SVM模型的誤差容忍范圍，在后續(xù)試驗中，本文將不敏感函數(shù)參數(shù)確定為0.001。
2.2 遺傳算法
遺傳算法（Genetic Algorithm）是由Holland教授模擬達(dá)爾文生物進(jìn)化理論的自然選擇和遺傳學(xué)機(jī)制的生物進(jìn)化過程而創(chuàng)造出的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。遺傳算法以它的實用、高效和魯棒性強(qiáng)等特點深受國內(nèi)外學(xué)者的青睞。
與其他傳統(tǒng)方法不同的是，遺傳算法并不依賴梯度信息和其他任何外部信息，而是通過模擬自然進(jìn)化過程來搜索最優(yōu)解，以適應(yīng)度函數(shù)作為搜索方向的引導(dǎo)，用選擇算子選擇親代和子代，用交叉和變異算子保證種群的多樣性。遺傳算法作為啟發(fā)式算法的一種，具有對可行解表示的廣泛性和不易陷入局部最優(yōu)解的特點，同時采用自然進(jìn)化的原理來表示復(fù)雜的現(xiàn)象，能夠快速可靠地解決非常困難的問題。隱含的并行性也使算法在計算上的時間大大縮短。本文正是借助遺傳算法的這些特點，通過全局優(yōu)化能力來對支持向量機(jī)的參數(shù)進(jìn)行優(yōu)化。
2.3 GA-SVM預(yù)測模型算法實現(xiàn)
將遺傳算法與支持向量機(jī)算法相結(jié)合，提出一種基于GA-SVM的預(yù)測模型。支持向量機(jī)算法的核函數(shù)采用徑向基核函數(shù)（RBF），利用二進(jìn)制編碼對支持向量機(jī)模型的參數(shù)進(jìn)行編碼，通過遺傳算法的迭代尋優(yōu)得出最優(yōu)解，從而確定最優(yōu)的懲罰函數(shù)C、核函數(shù)參數(shù)，最后通過支持向量機(jī)模型得到最后的預(yù)測結(jié)果。
具體的模型實現(xiàn)步驟如下：
（1）確定支持向量機(jī)參數(shù)的取值范圍。
（2）確定遺傳算法運行參數(shù)的大小。
（3）以二進(jìn)制編碼方式建立NL矩陣作為種群，并隨機(jī)生成初始種群。
（4）將初始種群中的每個個體，利用支持向量回歸機(jī)程序進(jìn)行計算，將輸出結(jié)果與原數(shù)據(jù)進(jìn)行對比，計算出訓(xùn)練樣本的預(yù)測精度，從而得出每個個體的適應(yīng)度大小。
（5）如此循環(huán)N次，直到每個個體都計算出相應(yīng)的適應(yīng)度。
（6）對整個種群進(jìn)行遺傳操作（選擇、交叉、變異），獲得新種群。
（7）當(dāng)滿足終止條件時（達(dá)到最大進(jìn)化次數(shù)或適應(yīng)度連續(xù)系帶沒有變化），停止計算；否則轉(zhuǎn)到步驟（4），直到結(jié)果滿足終止條件。
（8）滿足終止條件獲得的輸出就是最優(yōu)解的懲罰函數(shù)C、核函數(shù)參數(shù)。將最優(yōu)參數(shù)輸入支持向量回歸機(jī)，對數(shù)據(jù)樣本進(jìn)行預(yù)測。
具體算法流程如圖1所示。
3 實例分析
為了驗證GA-SVM算法的預(yù)測精度，本文使用MatlabR2013a作為編程工具對GA-SVM算法進(jìn)行了實現(xiàn)。同時選擇臺灣大學(xué)林智仁教授（Chih-Jen Lin）等開發(fā)的支持向量機(jī)軟件Libsvm-2.88來做實驗結(jié)果的比對。
本文采用成都市貨運量作為被解釋變量，根據(jù)主成分分析法，選擇出相應(yīng)的指標(biāo)體系：第一產(chǎn)業(yè)產(chǎn)值、第二產(chǎn)業(yè)產(chǎn)值、第三產(chǎn)業(yè)產(chǎn)值、社會消費品零售總額、進(jìn)出口貿(mào)易總額、城鎮(zhèn)居民可支配收入、農(nóng)村居民可支配收入、成都市貨運量。以19962010年的數(shù)據(jù)樣本作為訓(xùn)練數(shù)據(jù)，以20112014年的數(shù)據(jù)樣本作為測試數(shù)據(jù)進(jìn)行實驗。為了提高測試結(jié)果的可信程度，本文分別用兩種方法對數(shù)據(jù)樣本進(jìn)行多次實驗和比對。
為了避免經(jīng)驗風(fēng)險帶來的預(yù)測誤差，本文通過調(diào)節(jié)懲罰函數(shù)C、核函數(shù)參數(shù)兩參數(shù)的范圍多次測試獲取預(yù)測精度較高的參數(shù)范圍：CE[0.1，100]，6E[0.01，1000]。最終預(yù)測結(jié)果如表2所示。
根據(jù)表2可知，GA-SVM模型在2013年貨運量的預(yù)測中達(dá)到最低的相對誤差-0.231%，在2012年、2013年、2014年的相對誤差都在10%以內(nèi)達(dá)到了較高的預(yù)測精度。反觀SVM模型，除了2014年的相對誤差在10%以內(nèi)，其余各年份都超過了這個標(biāo)準(zhǔn)，在2011年的預(yù)測中達(dá)到了最高的-61.807%，很明顯GA-SVM的預(yù)測精度要優(yōu)于SVM的預(yù)測精度，如圖2所示。