戴紅偉,楊玉,王永泉,李存華

(1.淮海工學(xué)院智能信息系統(tǒng)研究所, 222005, 江蘇連云港; 2.曼徹斯特大學(xué)控制系統(tǒng)中心,M139PL, 英國曼徹斯特; 3.西安交通大學(xué)機(jī)械工程學(xué)院, 710049, 西安)

自適應(yīng)量子交叉克隆選擇算法

戴紅偉1,2,楊玉1,王永泉3,李存華1

(1.淮海工學(xué)院智能信息系統(tǒng)研究所, 222005, 江蘇連云港; 2.曼徹斯特大學(xué)控制系統(tǒng)中心,M139PL, 英國曼徹斯特; 3.西安交通大學(xué)機(jī)械工程學(xué)院, 710049, 西安)

為克服傳統(tǒng)克隆選擇算法易于陷入局部最優(yōu)的缺點(diǎn),提出了自適應(yīng)量子交叉免疫算法。自適應(yīng)量子交叉算子在算法演化初期通過高適配度抗體對(duì)低適配度抗體的影響,加速收斂過程,而在算法演化后期,利用低適配度抗體對(duì)高適配度抗體的擾動(dòng),增加算法跳出局部最優(yōu)的概率。對(duì)旅行商問題、單目標(biāo)和多目標(biāo)孔群加工路徑優(yōu)化問題所做的計(jì)算,結(jié)果表明:自適應(yīng)量子克隆選擇算法能有效平衡全局搜索和局部挖掘能力,在收斂速度和穩(wěn)定性上優(yōu)于同類克隆選擇算法和其他啟發(fā)式算法。

自適應(yīng)量子交叉;孔群加工路徑優(yōu)化;多目標(biāo)優(yōu)化

孔群加工作為數(shù)控加工中的典型過程,加工路徑選擇的合理性將直接影響加工效率和加工成本。以縮短刀具移動(dòng)距離、減少刀具更換次數(shù)和刀具逆向變換次數(shù)為目標(biāo)的孔群加工路徑優(yōu)化問題(HMPOP)成為孔群加工的關(guān)鍵問題。

孔群加工路徑優(yōu)化本質(zhì)上屬于組合優(yōu)化問題,隨著問題規(guī)模的增大,其解空間存在的“組合爆炸”現(xiàn)象使得傳統(tǒng)的數(shù)學(xué)規(guī)劃方法難以有效實(shí)施。文獻(xiàn)[1-2]分別采用簡單遺傳算法和基于聯(lián)賽選擇算子與模擬退火交叉算子的改進(jìn)遺傳算法對(duì)HMPOP問題進(jìn)行了優(yōu)化。也有研究者將蟻群算法、微粒群算法和人工魚群算法應(yīng)用于HMPOP問題[3-5]。然而,上述算法都是將HMPOP簡化為只考慮刀具移動(dòng)成本的單目標(biāo)優(yōu)化問題。人工免疫系統(tǒng)、模擬生物免疫系統(tǒng)固有的自主學(xué)習(xí)、免疫記憶和分布并行處理能力等信息處理機(jī)制,為解決工程問題提供了新穎的方法和手段[6-7]。文獻(xiàn)[8]采用人工免疫算法對(duì)HMPOP問題進(jìn)行求解,該算法雖然針對(duì)刀具移動(dòng)距離和刀具逆序變換次數(shù)兩項(xiàng)指標(biāo)進(jìn)行多目標(biāo)優(yōu)化,但在單目標(biāo)優(yōu)化求解中其性能仍不如改進(jìn)遺傳算法和魚群算法的性能,未能體現(xiàn)人工免疫算法在求解優(yōu)化問題中的優(yōu)勢(shì)。

基于量子重疊與牽連原理的量子計(jì)算為有效解決復(fù)雜優(yōu)化問題提供了新的思路[9]。為克服傳統(tǒng)克隆選擇算法易陷入局部最優(yōu)的缺點(diǎn),受電子雙向躍遷物理現(xiàn)象的啟發(fā),本文針對(duì)多目標(biāo)孔群加工路徑優(yōu)化問題提出了自適應(yīng)量子交叉免疫算法,該算法能有效平衡全局搜索和局部挖掘能力,在收斂速度和穩(wěn)定性上優(yōu)于同類啟發(fā)式算法。

1 量子交叉算子

受量子機(jī)制的啟發(fā),Narayanan提出了全干擾交叉算子[10],文獻(xiàn)[11]將該算子引入克隆選擇算法,較好地解決了受限多播路由問題。然而,該算子采取基于位置信息的被動(dòng)選擇策略,不能有效解決旅行商問題。為克服經(jīng)典全干擾交叉算子的局限性,提出了自適應(yīng)量子交叉算子。

1.1 釋能交叉算子

釋能交叉算子θ(H2L)模擬電子通過釋放能量完成從高能態(tài)到低能態(tài)的躍遷,描述了從高適配度抗體到低適配度抗體構(gòu)造交叉解的過程。如圖1所示,該過程為:從抗體A1中隨機(jī)選取一城市,比如a1,然后躍遷至抗體A2;比較A2中與城市a1相鄰的兩個(gè)城市a2、a5到a1的距離,如果Dis(a5,a1)

圖1 釋能交叉算子θ(H2L)模擬過程示意圖

1.2 吸能交叉算子

吸能交叉算子θ(L2H)模擬電子從低能軌道躍遷至高能軌道吸收能量的過程,如圖2所示。不同于釋能交叉算子θ(H2L),在吸能交叉算子θ(L2H)中增加了低適配度抗體對(duì)高適配度抗體的影響。

圖2 吸能交叉算子θ(L2H)模擬過程示意圖

步驟1.1:從A1中隨機(jī)選取一城市,比如a1,躍遷至A2,確定A2中a1的左右相鄰城市為a5、a2;在A1中執(zhí)行反轉(zhuǎn)操作I1和I2,I1為反轉(zhuǎn)子片段a2-a3-a4-a5,使得a1與a5相連,I2為反轉(zhuǎn)子片段a2-a2;假設(shè)反轉(zhuǎn)操作I1能產(chǎn)生更短的巡回路徑,則選擇a5作為交叉抗體的當(dāng)前城市。

步驟1.2:動(dòng)態(tài)更新抗體A1。

步驟2.1:躍遷至抗體A3,根據(jù)a5在A3中相鄰城市的信息a1、a2,在A1中執(zhí)行反轉(zhuǎn)操作I1和I2,即反轉(zhuǎn)子片段a1-a1與子片段a4-a3-a2;如果反轉(zhuǎn)操作I2能產(chǎn)生更短的巡回路徑,則選擇a2作為交叉抗體的當(dāng)前城市。

步驟2.2:動(dòng)態(tài)更新抗體A1。

依次類推,直到構(gòu)成一個(gè)可行解。

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

對(duì)比釋能交叉算子θ(H2L)與吸能交叉算子θ(L2H)可以發(fā)現(xiàn):θ(H2L)體現(xiàn)了高適配度抗體對(duì)低適配度抗體的影響,促使算法可以更快速地向優(yōu)質(zhì)解聚集,提高收斂速度;θ(L2H)體現(xiàn)了低適配度抗體對(duì)高適配度抗體的影響,雖然從低適配度抗體獲取的信息有可能會(huì)破壞高適配度抗體的優(yōu)質(zhì)模式,但是這種擾動(dòng)卻可以提高算法跳出局部最優(yōu)的概率。自適應(yīng)量子交叉算子AQC的偽代碼描述如下

fort=0:T

QJP=(T-t)/T

if rand( )

θ(H2L)

else

θ(L2H)

end if

end for

式中:QJP為量子躍遷概率控制因子;T為總代數(shù),t為當(dāng)前代數(shù);rand()為隨機(jī)函數(shù)。

2 量子交叉免疫克隆算法及其驗(yàn)證

2.1 自適應(yīng)量子交叉克隆選擇算法

克隆選擇算法是基于克隆選擇學(xué)說而形成的一種免疫計(jì)算方法,其主要過程包括克隆增殖、免疫變異和免疫選擇3個(gè)環(huán)節(jié)[11],量子交叉克隆選擇算法可表示為如下的免疫進(jìn)化過程

假設(shè)種群規(guī)模為N,即A={A1,A2,…,AN},其中Ai(i=1,2,…,N)為適配度從高到低排列的N個(gè)抗體,則免疫進(jìn)化的主要步驟可描述如下。

(1)克隆增殖Γc:對(duì)抗體Ai進(jìn)行規(guī)模為pi的克隆增殖,假設(shè)M為克隆增益因子,則pi可表示為

(1)

經(jīng)過克隆增殖之后,種群變?yōu)?/p>

(2)

(2)免疫變異Γm:針對(duì)克隆后的種群進(jìn)行超變異和受體編輯操作[12],免疫變異不影響種群規(guī)模,變異后的種群為

(3)

(4)

(4)克隆選擇Γs:依據(jù)適配度從當(dāng)前種群中挑選N個(gè)優(yōu)質(zhì)抗體產(chǎn)生下一代種群A(t+1)。

重復(fù)以上過程,直到滿足終止的條件,輸出最終結(jié)果。

2.2 算法的收斂性分析

本文采用隨機(jī)過程中的鞅理論方法對(duì)算法的收斂性進(jìn)行分析。首先給出鞅列與下鞅的定義[13]。

定義1(鞅列) 如果對(duì)?n,E(|Yn|)<∞,且對(duì)?m有

(5)

則隨機(jī)序列Yn為鞅列。如果Xn為(Yn)可知的,且對(duì)?n,E(|Xn|)<∞,?m有

(6)

則稱Xn為(Yn)鞅列。由條件期望的性質(zhì)可知,如果Xn是(Yn)鞅列,則Xn也是鞅列。

定義2(下鞅) 將式(5)、(6)中的“=” 改為“≥”,則對(duì)應(yīng)的隨機(jī)序列稱為下鞅列。

利用鞅的性質(zhì),文獻(xiàn)[13]已經(jīng)證明了遺傳算法的收斂性。其證明思路為:將算法的收斂性問題中的序列轉(zhuǎn)化為某一個(gè)下鞅列或鞅序列,然后證明該序列滿足鞅收斂定理的條件,獲得鞅序列的收斂性,再轉(zhuǎn)化為原來序列的收斂性。

基于2.1節(jié)算法實(shí)現(xiàn)過程的描述,克隆選擇算法的目的在于生成一列種群(解){A(t),t≥0},且該列種群包含有概率分布傾向于具有最佳適配度函數(shù)的候選解。若以種群的平均適配度作為指導(dǎo)原則,則當(dāng)且僅當(dāng)種群中每個(gè)抗體適配度達(dá)到全局最大時(shí)種群的平均適配度達(dá)到最大,因此可以利用平均適配度函數(shù)的收斂性來研究克隆選擇算法的收斂性。同時(shí),每次迭代后,如果新種群的平均適配度關(guān)于當(dāng)前種群的條件期望不低于當(dāng)前種群的平均適配度,就可以把平均適配度函數(shù)fav(A(t))轉(zhuǎn)化為一個(gè)下鞅來考察算法的收斂性,即算法保證通過各種免疫算子的作用使得下一代種群的平均適配度不低于當(dāng)前種群的平均適配度。

自適應(yīng)克隆選擇算法中克隆增殖算子Γc完全復(fù)制父代抗體,免疫變異算子Γm在保留父代抗體信息的基礎(chǔ)上進(jìn)行小概率免疫變異,量子交叉算子Γqc在綜合父代優(yōu)質(zhì)抗體信息的基礎(chǔ)上產(chǎn)生更優(yōu)質(zhì)抗體,而克隆選擇算子Γs確保用高適配度抗體更新父代低適配度抗體,因此自適應(yīng)克隆選擇算法(AQCCSA)可以保證子代種群的平均適配度不低于父代種群的平均適配度,即fav(A(t+1))≥fav(A(t))。

定理1[14]假設(shè)時(shí)刻t算法得到的種群序列為{A(t),t≥0},Φt=Φ(A(1),A(2),…,A(t))為A(1),A(2),…,A(t)可測(cè)的最小σ代數(shù),則fav(A(t))關(guān)于Φt為下鞅,即

(7)

在定理1的條件下,設(shè)B*為全局最優(yōu)解,f*為最優(yōu)適應(yīng)度,當(dāng)種群狀態(tài)有限時(shí),有如下結(jié)論

由以上結(jié)論知,在滿足定理1的條件時(shí),自適應(yīng)克隆選擇算法所產(chǎn)生的種群的適應(yīng)度必趨于最優(yōu)值,算法將以概率1確保在有限迭代次數(shù)內(nèi)達(dá)到問題的最優(yōu)解,算法必然收斂。

2.3 算法復(fù)雜度分析

O(MNa)+O(NqcNa)=

2.4 旅行商問題

TSP是典型的NP難問題,可簡單描述為:給定N個(gè)城市坐標(biāo),找出一條經(jīng)過所有城市一次且僅一次的距離最短的最優(yōu)路徑。

本文提出的自適應(yīng)交叉算子本質(zhì)上是由θ(H2L)和θ(L2H)組成的混合算子,但是兩種算子特性各異且具有互補(bǔ)性。為比較各個(gè)交叉算子的性能,本文進(jìn)行了對(duì)比實(shí)驗(yàn),表1給出了5個(gè)TSP問題的仿真結(jié)果,所有結(jié)果均為50次獨(dú)立運(yùn)行結(jié)果的平均值。從運(yùn)算結(jié)果可以看出,自適應(yīng)量子交叉算子(AQC)性能優(yōu)于單獨(dú)的θ(H2L)或θ(L2H)交叉算子。

表1 不同量子交叉算子的性能比較

注:W表示最差解對(duì)于最優(yōu)解偏差的百分比;M表示平均解對(duì)于最優(yōu)解偏差的百分比;B表示最好解對(duì)于最優(yōu)解偏差的百分比。

為進(jìn)一步分析自適應(yīng)交叉算子的性能,本文采用了文獻(xiàn)[12]所使用的群體多樣性Dpop的定義

Dpop=Dsum/(N-1)

(8)

式中:Dsum為群體內(nèi)抗體與最優(yōu)抗體差異度的和,即

(9)

其中X(Ao,Aj)表示抗體Ao、Aj包含相同邊的數(shù)量。

作為群體算法,能否維持良好的群體多樣性是反映算法性能的重要指標(biāo)之一。根據(jù)文獻(xiàn)[15],理想的群體多樣性為前高后低,即在進(jìn)化前期,較高的多樣性有利于算法在更廣的范圍展開搜索,而在搜索的后期,較低的多樣性有利于在局部空間進(jìn)行開發(fā),增加了找到全局最優(yōu)解的可能性。

圖3a、3b分別給出求解eil51問題的群體多樣性變化和算法收斂過程(50次獨(dú)立運(yùn)行平均結(jié)果),圖3c為最后100代的收斂過程。

(a)群體多樣性變化趨勢(shì)

(b)迭代收斂過程

(c)最后100代收斂過程

從圖3中可以看出,幾種交叉算子的群體多樣性都隨著迭代的進(jìn)行而逐漸減小,然而自適應(yīng)交叉算子卻有著不同于其他交叉算子的平臺(tái)期,即在某個(gè)特定時(shí)期內(nèi),群體多樣性維持較為穩(wěn)定的高位水平,使得算法有機(jī)會(huì)在更大的范圍內(nèi)進(jìn)行搜索,而不至于過早陷入局部最優(yōu)。針對(duì)其他TSP問題的計(jì)算結(jié)果也驗(yàn)證了平臺(tái)期的存在及其對(duì)算法性能的有效提升。

表2給出了不同免疫算法求解TSP問題的對(duì)比結(jié)果,其中RECSA為融合受體編輯的經(jīng)典克隆選擇算法[12],CQCCSA、IQCCSA分別為基于經(jīng)典量子干擾交叉算子和基于距離比較的量子交叉克隆選擇算法[16]。城市數(shù)目在51～124之間的問題迭代1 000次,城市數(shù)目在127～195之間的問題迭代2000次,kroA200問題迭代5000次,lin318問題迭代10000次。黑體數(shù)據(jù)為幾種算法中的最優(yōu)值。由仿真結(jié)果可得,自適應(yīng)量子交叉克隆選擇算法在幾乎所有TSP問題中性能優(yōu)于其他算法。

3 孔群加工路徑優(yōu)化問題

為驗(yàn)證算法性能,本節(jié)針對(duì)機(jī)械加工中的孔群路徑優(yōu)化問題(HMPOP)進(jìn)行求解,并與已有算法進(jìn)行比較。

3.1 單目標(biāo)HMPOP問題

HMPOP問題的目標(biāo)就是選擇合理的加工順序,使總加工成本最小。為保證與其他算法比較的公平性,本文采用最小化刀具行進(jìn)成本為優(yōu)化目標(biāo),抽象為一個(gè)典型的TSP問題。優(yōu)化對(duì)象為一注塑模上模,具體尺寸見文獻(xiàn)[1]。

表2 不同算法求解TSP問題計(jì)算結(jié)果對(duì)比

注:T為運(yùn)行時(shí)間。

表3為不同算法求解單目標(biāo)HMPOP問題的結(jié)果對(duì)比,其中Hopfield、ARTIA(人工免疫算法)、EACS(蟻群算法)數(shù)據(jù)來自文獻(xiàn)[8],IGA為改進(jìn)遺傳算法[2],AFSA為人工魚群算法[5],AQCCSA為本文所提算法。雖然人工魚群算法能找到已知最優(yōu)解,但平均解的質(zhì)量遠(yuǎn)不如本算法的質(zhì)量。

表3 不同算法求解結(jié)果對(duì)比

3.2 多目標(biāo)HMPOP問題

k∈{2,3,…,n-1},j∈{1,2,…,l}

則問題的目標(biāo)函數(shù)為

(10)

刀具的行進(jìn)成本可以表示為

(11)

同時(shí),要求逆序變向次數(shù)和刀具行進(jìn)距離均為最小,該問題為多目標(biāo)優(yōu)化問題。

為解決多目標(biāo)優(yōu)化問題,本文采用快速雙目標(biāo)非支配排序算法[17],表4給出了不同方法求解上述多目標(biāo)孔群加工路徑優(yōu)化問題的計(jì)算結(jié)果,其中種群規(guī)模為100,克隆增益因子為1,進(jìn)化代數(shù)為3。從對(duì)比結(jié)果可以看出,AQCCSA解的質(zhì)量明顯好于另外兩種算法。

表4 多目標(biāo)孔群加工路徑優(yōu)化結(jié)果對(duì)比

4 結(jié) 論

為克服傳統(tǒng)克隆選擇算法易于陷入局部最優(yōu)的缺點(diǎn),本文針對(duì)多目標(biāo)孔群加工路徑優(yōu)化問題提出自適應(yīng)量子交叉免疫算法。自適應(yīng)交叉算子模擬了物理學(xué)中電子雙向躍遷的現(xiàn)象,即電子既可以從高能軌道通過釋放能量躍遷至低能軌道,也可以通過吸收能量從低能軌道躍遷至高能軌道。該算子在算法演化初期通過高適配抗體對(duì)低適配抗體的影響,加速收斂過程,而在算法演化后期,利用低適配度抗體對(duì)高適配度抗體的擾動(dòng),增加算法跳出局部最優(yōu)的概率。不同于其他交叉算子,自適應(yīng)交叉算子在某個(gè)特定時(shí)期內(nèi)存在平臺(tái)期的現(xiàn)象,使群體多樣性維持較穩(wěn)定的高位水平,算法有更多的機(jī)會(huì)在更大的范圍內(nèi)進(jìn)行搜索,而不至于過早陷入局部最優(yōu)。該算法能有效平衡全局搜索和局部挖掘能力,在收斂速度和穩(wěn)定性上優(yōu)于同類啟發(fā)式算法。

[1] 周正武, 丁同梅. 基于TSP和GA孔群加工路徑優(yōu)化問題的研究 [J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2007(7): 30-32.

ZHOU Zhengwu, DING Tongmei. Research on holes machining path planning optimization with TSP and GA [J]. Modular Machine Tool & Automatic Manufacturing Technique, 2007(7): 30-32.

[2] 凌玲, 胡于進(jìn), 王青青, 等. 基于改進(jìn)遺傳算法的孔群加工路徑優(yōu)化 [J]. 華中科技大學(xué)學(xué)報(bào), 2009, 37(8): 88-91.

LING Ling, HU Yujin, WANG Qingqing, et al. Holes machining path optimization using the improved genetic algorithm [J]. Journal of Huazhong University of Science and Technology, 2009, 37(8): 88-91.

[3] ABBAS A, ALY M, HAMZA K. Optimum drilling path planning for a rectangular matrix of holes using ant colony optimisation [J]. International Journal of Production Research, 2011, 49(19): 5877-5891.

[4] ZHU Guangyu, ZHANG Weibo. Drilling path optimization by the particle swarm optimization algorithm with global convergence characteristics [J]. International Journal of Production Research, 2008, 46(8): 2299-2311.

[5] 蔡云, 周立煒. 人工魚群算法在孔群加工路徑優(yōu)化中的應(yīng)用研究 [J]. 武漢科技大學(xué)學(xué)報(bào), 2011, 34(3): 182-185.

CAI Yun, ZHOU Liwei. Holes machining path optimization using an artificial fish swarm algorithm [J]. Journal of Wuhan University of Science and Technology, 2011, 34(3): 182-185.

[6] 焦李成, 杜海峰, 劉芳, 等. 免疫優(yōu)化:計(jì)算、學(xué)習(xí)與識(shí)別 [M]. 北京: 科學(xué)出版社, 2006.

[7] JIAO Licheng, LI Yangyang, GONG Maoguo, et al. Quantum-inspired immune clonal algorithm for global optimization [J]. IEEE Transactions on System, Man and Cybernetics: Part B, 2008, 38(5): 1234-1253.

[8] 肖人彬, 陶振武. 孔群加工路徑規(guī)劃問題的進(jìn)化求解 [J]. 計(jì)算機(jī)集成制造系統(tǒng), 2005, 11(5): 682-689.

XIAO Renbin, TAO Zhenwu. Solution to holes machining path planning by evolutionary methods [J]. Computer Integrated Manufacturing System, 2005, 11(5): 682-689.

[9] LI Yangyang, XIANG Rongrong, JIAO Licheng, et al. An improved cooperative quantum-behaved particle swarm optimization [J]. Soft Computing, 2012, 16(6): 1061-1069.

[10]NARAYANAN A, MOORE M. Quantum-inspired genetic algorithm [C]∥Proceedings of IEEE International Conference on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 1996: 61-66.

[11]李陽陽, 焦李成. 量子克隆多播路由算法 [J]. 軟件學(xué)報(bào), 2007, 18(9): 2063-2069.

LI Yangyang, JIAO Licheng. Quantum clonal algorithm for multicast routing problem [J]. Journal of Software, 2007, 18(9): 2063-2069.

[12]GAO Shangce, DAI Hongwei, YANG Gang, et al. A novel clonal selection algorithm and its application to traveling salesman problems [J]. IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, 2007, 90(10): 2318-2325.

[13]徐宗本, 張講社, 鄭亞林. 計(jì)算智能中的仿生學(xué): 理論與算法 [M]. 北京: 科學(xué)出版社, 2003.

[14]洪露, 紀(jì)志成, 龔成龍. 一種改進(jìn)型克隆選擇算法及其幾乎處處強(qiáng)收斂性研究 [J]. 控制與決策, 2010, 25(5): 725-729.

HONG Lu, JI Zhicheng, GONG Chenglong. On an improved clonal selection algorithm and its almost sure strong convergence [J]. Control and Decision, 2010, 25(5): 725-729.

[15]CHANG Pei-Chann, HUANG Wei-Hsiu, TING Ching-Jung. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems [J]. Expert Systems with Applications, 2010, 37(4): 1863-1878.

[16]DAI Hongwei, YANG Yu, LI Cunhua, et al. Quantum interference crossover-based clonal selection algorithm and its application to traveling salesman problem [J]. IEICE Transaction on Information & System, 2009, 92(1): 78-85.

[17]劉敏, 曾文華, 趙建峰. 一種快速的雙目標(biāo)非支配排序算法 [J]. 模式識(shí)別與人工智能, 2011, 24(4): 538-547.

LIU Min, ZENG Wenhua, ZHAO Jianfeng. A fast biobjective non-dominated sorting algorithm [J]. Pattren Recognition and Artificial Intelligence, 2011, 24(4): 538-547.

[本刊相關(guān)文獻(xiàn)鏈接]

任茂棟,梁晉,唐正宗,等.數(shù)字圖像相關(guān)法中的優(yōu)化插值濾波器.2014,48(7):65-70.[doi:10.7652/xjtuxb201407012]

靳峰,馮大政.利用空間序列描述子的快速準(zhǔn)確的圖像配準(zhǔn)算法.2014,48(6):19-24.[doi:10.7652/xjtuxb201406004]

吳仁斌,姚敏立,賈維敏,等.采用幅度響應(yīng)約束的魯棒自適應(yīng)波束形成算法.2014,48(4):109-114.[doi:10.7652/xjtuxb201404019]

李彬,宋立明,李軍,等.長葉片透平級(jí)多學(xué)科多目標(biāo)優(yōu)化設(shè)計(jì).2014,48(1):1-6.[doi:10.7652/xjtuxb201401001]

郝紅俠,劉芳,焦李成,等.采用結(jié)構(gòu)自適應(yīng)窗的非局部均值圖像去噪算法.2013,47(12):71-76.[doi:10.7652/xjtuxb 201312013]

李帝辰,席光,孫中國.無網(wǎng)格粒子法中復(fù)雜二維形狀的均布離散方法.2013,47(11):120-126.[doi:10.7652/xjtuxb201311021]

劉光輝,任慶昌,孟月波,等.自適應(yīng)先驗(yàn)馬爾可夫隨機(jī)場(chǎng)模型的圖像分割算法.2013,47(10):62-67.[doi:10.7652/xjtuxb201310011]

侯興松,張?zhí)m,肖琳.合成孔徑雷達(dá)圖像的貝葉斯壓縮感知重構(gòu)算法.2013,47(8):74-79.[doi:10.7652/xjtuxb201308013]

(編輯 趙煒)

AdaptivveQuantumCrossoverClonalSelectionAlgorithm

DAI Hongwei1,2,YANG Yu1,WANG Yongquan3,LI Cunhua1

(1. Institute of Intelligent Information System, Huaihai Institute of Technology, Lianyungang, Jiangsu 222005, China;2. Control System Centre, University of Manchester, Manchester M139PL, UK; 3. School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

A clonal selection algorithm with adaptive quantum crossover (AQCCSA) is proposed to overcome the premature convergence drawback of traditional clonal selection algorithms (CSA) and to solve the holes machining path optimization problems (HMPOP). The effect of high affinity antibodies on low affinity antibodies is used to accelerate the convergence process in the first half evolution process. Then the disturbance effect of low affinity antibodies on high affinity antibodies is used to help the algorithm escaping from local optimum in the last half evolution process. Experimental results on traveling salesman problems (TSP), single-objective and multi-objective HMPOP show that the proposed algorithm achieves a good balance between global searches and local mining, and the convergence speed and robustness of the algorithm are better than those of other CSAs and heuristic algorithms.

adaptive quantum crossover; holes machining path planning;multi-objective optimization

2014-03-19。

戴紅偉(1975—),男,副教授。

國家自然科學(xué)基金資助項(xiàng)目(61203325,51375367);江蘇省自然科學(xué)基金資助項(xiàng)目(BK2012663)。

時(shí)間:2014-07-03

10.7652/xjtuxb201409002

TP399;TP301.6

:A

:0253-987X(2014)09-0006-07

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140703.1130.003.html