基于正態(tài)云模型的自適應細菌覓食優(yōu)化算法

杜文軍，孫 斌

(東北電力大學 教務處，吉林 吉林 132012)

杜文軍，孫 斌

(東北電力大學 教務處，吉林 吉林 132012)

在研究細菌覓食算法趨化、復制、遷徙操作等相關理論的基礎上，將云模型和遺傳算法相關理論引入，對細菌覓食算法進行優(yōu)化和改進，在趨化操作中運用X條件云發(fā)生器自適應調整細菌靈敏度，控制游動步長，提高了算法的收斂速度；在復制操作中利用遺傳算法交叉編譯原理，設計交叉算子和遺傳算子對算法的復制操作改進，提高算法的局部搜索能力和種群的多樣性；在遷徙操作中，利用正向正態(tài)云發(fā)生器，修正非線性自適應的遷移概率，增強了算法全局尋優(yōu)能力。最后將改進后的算法應用于自動組卷系統(tǒng)，并與遺傳算法進行實驗結果比較分析。

細菌覓食優(yōu)化算法；正態(tài)云模型；自動組卷

細菌覓食優(yōu)化算法(Bacterial Foraging Optimization Algorithm BFOA)是由Passing[1]等人由大腸桿菌的群體覓食行為所啟發(fā)于2002年提出是一種群集智能優(yōu)化算法，具有較強的局部搜索能力及全局搜索能力，因其在解決實際應用領域中優(yōu)化問題的高效性被廣泛應用，成為仿生算法研究領域的熱點。ZHOU Y L[2，3]等人采用余弦函數(shù)的遞減性對算法的趨化操作的游動步長進行改進，提高了算法的局部搜索能力；李珺[4，5]等人設計了自適應動態(tài)步長調整函數(shù)，自適應調整步長，提高了算法的收斂精度；童雅林[6]在算法的復制操作中引入了輪盤賭選機制，提高算法的收斂速度；周文宏[7]等人在算法遷徙操作中引入方差理論，更新菌群的群體適應度，防止算法陷入局部最優(yōu)，提高算法的靈活性和全局搜索能力；程翔[8]等人引入維度自適應學習算法，提高了解的精度和搜索效率；LIU X Z[9]等人將免疫理論引入算法，設計了一種免疫算法與菌群算法結合的細菌覓食優(yōu)化算法?？傊?，來自不同領域的學者對BFOA進行了一系列改進優(yōu)化，廣泛應用于車間調度[10]、圖像處理[11]、PID控制器設計[12]、電網(wǎng)規(guī)劃[13]、故障診斷[14]等領域中。目前針對BFOA的研究對細菌覓食過程中自然環(huán)境的隨機性和模糊信息的處理尚未有充分的考慮，對細菌覓食算法在自動組卷系統(tǒng)的應用研究還不成熟。

本文在研究細菌覓食算法相關理論的基礎上，將云模型理論中正態(tài)云發(fā)生器和X條件云發(fā)生器引入算法，結合遺傳算法交叉、變異理論，設計了一種基于云模型的自適應細菌覓食優(yōu)化算法。

1 相關理論研究

1.1 細菌覓食算法[15-18]

細菌覓食算法的思想源于大腸桿菌的覓食行為，大腸桿菌表面遍布著鞭毛，在覓食過程中通過鞭毛來移動和旋轉，當鞭毛沿逆時針方向轉動時，大腸桿菌向前游動，當鞭毛沿順時針方向轉動時，大腸桿菌在原地旋轉(翻轉)，通常大腸桿菌在食物較多的環(huán)境中較多的游動，而在食物匱乏的區(qū)域較多的翻轉。大腸桿菌的覓食過程主要包括尋找食物源區(qū)域、在區(qū)域中尋找食物、根據(jù)食物的消耗決定是否遷徙。細菌覓食算法正式利用大腸桿菌的這一覓食過程而提出的一種仿生搜索算法。趨化(Chemotaxis)、復制(Reproduction)和遷徙-消亡(Elimination-Dispersal)操作是BFOA算法的主要步驟。

(1)趨化操作

θi(j+1，k，l)=θi(j，k，l)+C(i)φ(i，j)，

(1)

(2)

其中：θi(j+1，k，l)為細菌個體i在第j次趨向性操作、第k次復制操作和第l次遷徙操作之后的位置；φ(i，j)為隨機方向上的單位向量。

(2)復制操作

復制操作模擬了細菌種群優(yōu)勝劣汰的繁殖過程，大腸桿菌在進行一段覓食過程后，部分尋找食物能力弱的細菌(適應度或健康度)會被淘汰，剩余適應能力強的細菌為了維持群體的規(guī)模將進行繁殖。在細菌覓食算法中細菌的覓食能力強弱描述為健康度或適應度。數(shù)學表示為適應度函數(shù)

(3)

適應度函數(shù)值越大表示細菌的覓食能力越強，按照適應度值的優(yōu)劣對細菌排序，淘汰適應度值差的Sr=S/2個細菌，復制Sr個覓食能力強的細菌，保持細菌的總體規(guī)模不變。

(3)遷徙操作

由于細菌的生活區(qū)域受環(huán)境變化和其他外力的影響可能導致細菌群體遷移到新的區(qū)域或集體死亡。在BFOA算法中描述為遷徙操作，遷徙通常以一定的概率發(fā)生。表述為Ped。如果個體滿足遷徙發(fā)生的概率則這個細菌個體滅亡，并在解空間區(qū)域的任意位置隨機地生成一個新個體。在BFOA算法中以給定的遷徙概率Ped和[0，1]的隨機數(shù)r對菌群中的每一個個體循環(huán)操作，達到使一些細菌被以很小概率的隨機地滅亡，同時新細菌在搜索空間的隨即位置被初始化。

1.2 云模型

云模型思想由李德毅[19，20]院士等于1995年提出，云模型實現(xiàn)了定性概念與定量數(shù)值之間的轉換，正態(tài)云模型在知識表達時模糊中帶有確定性、穩(wěn)定中帶有變化的規(guī)律，能夠將定性概念的模糊性和隨機性有機地結合在一起。

(1)云模型

李德毅院士的云模型是用語言值表示的某個定性概念與定量表示之間的不確定性轉換模型。期望Ex(Expected Value)、熵En(Entropy)和超熵He(Hyper Entropy)是云模型的3個數(shù)字特征，表示為C(Ex，En，He)。期望是定性概念的點，是概念量化的樣本；熵是定性概念的不確定性度量；超熵是熵的不確定量度。

(2)正太云發(fā)生器

云發(fā)生器是云生成的實現(xiàn)，正向云發(fā)生器(Forward Cloud Generator)是從定性概念到其定量表示的映射，它根據(jù)云的數(shù)字特征(Ex，En，He)產(chǎn)生云滴，每個云滴都是該概念的一次具體實現(xiàn)。正向正態(tài)云發(fā)生器的算法表述見文獻[21]，條件云發(fā)生器是正向正態(tài)云發(fā)生器的一種。

1.3 遺傳算法交叉變異理論

遺傳算法(Genetic Algorithm)由J.Holland[22]75年首先提出，又叫基因進化算法，屬于啟發(fā)式搜索算法一種。具有內在的隱并行性和全局尋優(yōu)能力，能自動優(yōu)化的搜索空間，自適應地調整搜索方向，已被人們廣泛地應用于過程控制和人工智能等領域[23]。交叉和變異操作是遺傳算法的核心步驟，交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作以提高算法的搜索能力；變異是指對群體中的個體碼串隨機挑選一個或多個基因座并對這些基因座的基因值做變動以提高算法的局部搜索能力。

2 細菌覓食優(yōu)化算法的改進

基于上述研究，本文在BFOA算法中引入正向云發(fā)生器和X條件云發(fā)生器，依據(jù)生物學理論，提出細菌活性的概念，利用X條件云發(fā)生器調整和控制細菌游動步長，改進趨化操作，提高算法的自適應性和收斂速度；引入遺傳算法交叉變異理論，改進算法的復制操作，在算法的復制操作中增加雜交算子和變異算子，使算法跳出局部最優(yōu)和提高細菌種群的多樣性；引入正向正態(tài)云發(fā)生器動態(tài)調整算法的遷徙概率，提高算法的全局尋優(yōu)能力。

2.1 趨化操作的改進

趨化操作步驟主要是翻轉和游動，李榮[24，25]等人采用線性遞減的方法調整細菌靈敏度，本文在此基礎上，利用X條件云發(fā)生器控制細菌的游動步長，使其以正向正態(tài)云的形狀遞減，以提高算法的收斂和防止陷入局部最優(yōu)。

(1)細菌活性初始值

(4)

式中：V0為細菌活性初值；Xmax、Xmin為變量的邊界；fi為細菌i的適應度；fmax為種群的最大適應度值；r為[0，1]之間的隨機數(shù)。

(2)翻轉操作定義

θi(j+1，k，l)=θi(j，k，l)+C(i)φ(i，j)，

(5)

式中：θi(j+1，k，l)為第i個細菌在進行第j次趨化操作、第k次復制操作以及第l次遷移操作后的位置；C(i)>0為細菌i當前游動的步長；φ(i，j)為細菌i翻轉后選擇的隨機單位方向。

(3)游動操作

Ex=Sa，

(6)

En=(Smax-Smin)/m1，

(7)

(8)

(9)

(10)

其中：Sa為游動次數(shù)的平均值；Si為當前細菌游動的次數(shù)；V為游動步長；m1、n1為控制參數(shù)。

2.2 復制操作的改進

BFOA算法的復制包括選擇策略和復制策略，引入遺傳算法的雜交和變異理論，通過雜交算子將當前最差的一半細菌個體與當前優(yōu)秀細菌個體進行雜交，讓最差的一半細菌個體向著最好的位置前進；變異算子對當前搜索到的適應度函數(shù)值最好的半數(shù)細菌在其自身位置周圍進行微小的位置擾動，從而避免算法陷入早熟。雜交算子的公式為

X′(i，k)=λX(i，k)+(1-λ)X(best，k)k=1，2，…，p,

(11)

其中：λ為[0，1]之間的均勻分布的隨機數(shù)；X(best，k)為到目前為止菌群中搜索到的最優(yōu)位置。變異算子如下所示：

X′(i)=X(i)+N(0，1).

(12)

2.3 遷徙操作的改進

引入正向正態(tài)云發(fā)生器動態(tài)調整細菌的遷移概率Pe，隨機選擇一個個體的適應度作為正態(tài)云發(fā)生器的期望，以種群適應度兩級差值為搜索邊界生成云滴，適應度值大的細菌生成較多的云滴，適應度值小的細菌生成較少的云滴。

Ex=fa，

(13)

(14)

(15)

(16)

(17)

其中：fa為個體的適應度(健康度)值；fmax、fmin和fav分別為適應度(健康度)值的最大值、最小值和平均值；m2、n2為控制參數(shù)。遷移操作隨機生成新個體：

Ex=Xa，

(18)

En=Q/m3，Q=t3(Xfmax-Xfmin)，

(19)

(20)

(21)

(22)

(23)

3 試驗及分析

將改進算法應用于實踐是驗證算法改進有效途徑，為驗證本文改進的細菌覓食優(yōu)化算法的有效性，將改進后的應用于智能組卷系統(tǒng)，通過與遺傳算法的實驗數(shù)據(jù)進行比較分析。崔金玲[26，27]等人對智能組卷系統(tǒng)的數(shù)學模型進行了詳細的論述，本文在此基礎上構建試卷的數(shù)學模型和實驗算法。

3.1 試卷模型

試卷中的試題主要包含以下屬性：(1)試題編號(試題的唯一標識)；(2)題型編號(1-單選題，2-多選題，3-判斷題，4-填空題，5-問答題)；(3)試題難度系數(shù)(學生的失分率)；(4)試卷區(qū)分度(區(qū)分學生水平能力)；(5)考試時間；(6)題分。

將一份試卷映射為一個細菌個體，試卷中每道試題由上述6個屬性約束，構成一個屬性向量(題號a1，題型a2，難度a3，區(qū)分度a4，時間a5，題分a6)，含有m道試題的試卷可以看作m×6矩陣A。

其中：aij表示第i道試題的第j個屬性。試卷模型的約束條件如下：

3.2 約束函數(shù)

表1 收斂精度比較

3.3 算法步驟

步驟1 編碼。本文采用二進制編碼，將一份試卷映射為一個細菌個體，將試題編號作為細菌個體基因，按照不同題型分段編碼。

步驟2 初始化參數(shù)。各參數(shù)設置如表1所示。

步驟3 適應度函數(shù)：f=e-βF，β=0.03；

步驟4 初始化種群；

步驟5 遷移循環(huán)：l=l+1；

步驟6 復制循環(huán)：K=k+1；

步驟7 趨化循環(huán)：j=j+1：

(1)根據(jù)公式(1)計算fi，fmax求得V0。

(2)翻轉。從相應的題型的試題庫中隨機挑選試題替換，對細菌i隨機產(chǎn)生題型編號Q1，隨機產(chǎn)生Q1種題型的題數(shù)Q2做為新個體。

(3)游動。根據(jù)公式(5)至公式(9)計算游動步長C。

步驟8 若j>Nc，則轉向步驟7。

步驟9 復制操作。選出適應度值最大的個體做為精英細菌，對適應度值較小的一半按公式(10)進行變異操作，對另一半通過精英細菌按公式(11)進行雜交操作。

步驟10 若k

步驟11 遷徙操作。比較fa與fav，根據(jù)公式(12)至公式(16)計算遷移率Pe，若需要生成新的個體，則根據(jù)公式(17)至公式(22)更新個體。

步驟12 若l

圖1 試驗結果

3.3 結果及分析

本文所使用的實驗環(huán)境為matlab7.1(作為仿真軟件)，SQL Server2008數(shù)據(jù)庫。試題庫中測試題目數(shù)為1 000，設置單選題、多選題，填空題，判斷題、問答題等五種題型，各題型的測試數(shù)目為200。分別運行算法，對其收斂精度、收斂時間進行比較分析，可見改進后的BFOA算法應用于智能組卷系統(tǒng)中，其收斂精度優(yōu)于遺傳算法，可以較快收斂至最優(yōu)解，組卷成功率較高。

4 總 結

本文將云模型及遺傳算法的相關理論融入到細菌覓食算法的改進中，提出了一種基于云模型的自適應細菌覓食優(yōu)化算法，在算法趨化操作中，采用云模型正態(tài)云發(fā)生器中的X條件云發(fā)生器動態(tài)自適應控制游動步長，提高了算法的收斂速度；在復制操作中，引入交叉算子和變異算子，提高了算法搜索全局最優(yōu)的能力，避免了算法早熟，提高了解的精度；在遷徙操作中利用正向正態(tài)云發(fā)生器提高適應度值較大個體的遷移概率，提高算法的全局搜索速度。最后將改進后的算法應用于智能組卷系統(tǒng)，通過實驗分析證明算法改進的效果和價值。

[1] J.R.Koza.Genetic programming：on the programming of computers by means of natural evolution[M].Boston：MIT Press，1992.

[2] Y.L.Zhou.Research and application on bacteria foraging optimization algorithm[J].Computer Engineering and Applications，2010，46(20)：16-21.

[3] 姜建國，周佳薇，鄭迎春.一種自適應細菌覓食優(yōu)化算法[J].西安電子科技大學學報，2015，42(1)：75-81.

[4] 李珺，黨建武，卜鋒.自適應步長的細菌覓食優(yōu)化算法研究[J].蘭州交通大學學報，2013，32(6)：10-14.

[5] C.J.Chen，W.G.Hu，Y.X.Du.Adaptive variable step size bacterial foraging optimization[J].Commputer Engineering and Applications，2012，48(33)：29-33.

[6] 童雅林.基于自適應的細菌覓食優(yōu)化算法研究[D].合肥：合肥工業(yè)大學，2015.

[7] 周文宏，雷欣，姜建國，等.變概率混合細菌覓食優(yōu)化算法[J].系統(tǒng)工程與電子技術，2016，38(4)：960-964.

[8] 程翔，劉升.云自適應混合細菌覓食優(yōu)化算法[J].微電子學與計算機，2015，32(5)：111-117.

[9] X.Y.Liu，L.K.Zhao.Bacteriaforging optimization algorithm based on immune algorithm[J].Journal of Computer Applications，2012，32(3)：634-637.

[10] 崔靜靜，孫延明，車蘭秀.改進細菌覓食算法求解車間作業(yè)調度問題[J].計算機應用研究，2011，28(9)：3324-3326.

[11] 馬苗，梁建慧，郭敏.基于細菌覓食算法的SAR圖像閾值分割[J].西安電子科技大學學報：自然科學版，2011，38(6)：152-158.

[12] 謝平平，李銀紅，劉曉娟，等.基于社會學習自適應細菌覓食算法的互聯(lián)電網(wǎng)AGC最優(yōu)PI/PID控制器設計[J].中國機電工程學報，2016，36(20)：5540-5548.

[13] 劉波，賀志佳，金昊.風力發(fā)電現(xiàn)狀與發(fā)展趨勢[J].東北電力大學學報，2016，36(2)：7-13.

[14] 李杰，彭月英，元昌安，等.基于細菌覓食優(yōu)化算法的自適應閾值邊緣檢測[J].計算機工程，2012，38(21)：179-181.

[15] 車偉偉.菌群優(yōu)化算法的研究與應用[D].南京：南京理工大學，2012.

[16] 匡芳君.群智能混合優(yōu)化算法及其應用研究[D].南京：南京理工大學，2014.

[17] 馮春時.群智能優(yōu)化算法及其應用[D].合肥：中國科學技術大學，2009.

[18] 汪定偉，王俊偉，王洪峰，等.智能優(yōu)化方法[M].北京，高等教育出版社，2007.

[19] 李德毅，孟海軍，史雪梅.隸屬云和隸屬云發(fā)生器[J].計算機研究與發(fā)展，1995，32(6)：15-20.

[20] 李德毅，劉常昱.論正態(tài)云模型的普適性[J].中國工程科學，2004，6(8)：28-34.

[21] 張光衛(wèi)，何銳，劉禹.基于云模型的進化算法[J].計算機學報，2008，31(7)：1082-1091.

[22] J.H.Holland.Adaption in Natural and Artificial System[M].Boston：MIT Press，1975：10-56.

[23] 王迪，吳鑫強，王振浩.基于改進遺傳算法的含分布式電源配電網(wǎng)故障定位[J].東北電力大學學報，2016，36(1)：1-6.

[24] 許鑫.細菌覓食優(yōu)化算法的研究[D].長春：吉林大學，2012.

[25] 李榮，簡獻忠，陳青.基于免疫進化細菌覓食優(yōu)化算法的無功優(yōu)化[J].上海理工大學學報，2014，36(3)：245-249.

[26] 牛輝.智能組卷的數(shù)學模型[D].武漢：華中科技大學，2013.

[27] 崔金玲，吳迪.基于免疫進化細菌覓食優(yōu)化算法的無功優(yōu)化[J].河南師范大學學報：自然科學版，2014，44(2)：148-156.

Abstract：On the basis of studying the process of chemotaxis，reproduction，migration theories of Bacteria Foraging Optimization Algorithm，the theory of cloud model and genetic algorithm is introduced into the improvement.Firstly，adjusted by the X-conditional cloud generator for controlling swim steps in the operation of chemotaxis，the convergence rate is improved by this method.Secondly，In the reprodurtion operation，give both the cross operator and mutation operator to improve the local search ability and population diversity.then，in the operation of elimination and dispersal，the adaptive and norrlincar probability of elimination and dispersal is adopted by the forward normal cloud generator，which improves the global-optimization capability.Finally，this algorithm is used to the system of automatic test，compared and analyzed with the experiment of Ucnetic Algorithm.

Keywords：Bacteria foraging optimization algorithm；Normal cloud model；Automatic test

TheAdaptiveBacteriaForagingOptimizationAlgorithmBasedonNormalCloudModel

DuWenjun，SunBin

(Teaching Affairs Department，Northeast Electric Power University，Jilin Jilin 132012)

TP29

A

2017-05-12

杜文軍(1982-)，男，碩士，助教，主要研究方向：計算機理論與應用.

電子郵箱：114339185@qq.com(杜文軍)；358538315@qq.com(孫斌)

1005-2992(2017)05-0102-07