基于改進蝙蝠算法的雙聚類算法設計與實現
2021-12-10 02:48:22崔衍薛源
現代計算機 2021年30期
崔衍，薛源
（南京郵電大學物聯網學院，南京 210003）
0 引言
各種生物的生命活動都是由基因調控的，近年來DNA微陣列技術憑借其優點成為研究基因的主要技術［1］。DNA微陣列技術產生的基因表達數據是一個矩陣，反映的是基因轉錄產物mRNA在細胞中的豐度，通過分析這些數據能夠得到當前細胞的生理活動狀態。該矩陣的行代表的是基因，列代表的是條件（實驗環境）。對基因表達數據進行分析的傳統方法是聚類，但是傳統的聚類只能對基因進行聚類或者對條件進行聚類，這樣得到的是部分基因在所有條件下相似的表達模式或者所有基因在部分條件下相似的表達模式［2］，并且得到的聚類元素集合沒有相交，即一個基因或者條件只能在一個聚類里，不能屬于多個聚類［3］，這并不能很好的應用于對基因表達數據進行分析，因為一部分基因可能在多個條件下調節同一生物功能［4］。Cheng和Church［5］在2000年首次將雙聚類應用于基因表達數據分析。雙聚類顧名思義，就是同時對行（基因）和列（條件）進行聚類，得到一個具有相似表達模式的子矩陣。雙聚類已經被證明是一個NP-hard問題，智能優化算法在解決NP-hard問題方面有著獨特的優勢，因此將智能優化算法應用于雙聚類算法是一個很好的研究方向。
Yang［6］在2010年根據蝙蝠回聲定位提出了蝙蝠算法（bat algorithm，BA）。BA算法在解決復雜的優化問題方面有著很好的性能，引起了學者的極大關注，現在已經應用于多個領域來解決問題。本文提出了一個基于改進蝙蝠算法的雙聚類算法。改進了原始蝙蝠算法的位置和速度更新公式，并引入變異算子來提高局部搜索能力。最后在酵母菌數據集上進行實驗，與多個雙聚類算法的實驗結果進行比較。結果表明本文提出的基于蝙蝠算法設計雙聚類算法是一個可行的方法，能夠挖掘出更優的雙聚類。
1 雙聚類定義
Cheng和Church提出CC算法的時候給出了雙聚類的定義［5］，定義如下：
定義1設M行N列的基因表達矩陣為A，G為包含M個基因的基因集，C為包含N個條件的條件合，a i j為基因表達矩陣A的一個元素。雙聚類定義為B=(I,J)，其中I為G的一個子集，J為C的一個子集，b ij為子矩陣B的元素，子矩陣B的平均平方殘差為：
其中：a iJ、a Ij、a IJ分別為子矩陣B的第i行平均值、子矩陣B的第j列平均值和子矩陣B(I,J)的平均值。存在一個δ≥0，如果子矩陣B(I,J)滿足H(I,J)≤δ，則稱該子矩陣為一個δ-bicluster。
雙聚類的目的就是在基因表達數據矩陣中尋找滿足條件的子矩陣，使得子矩陣中基因集在對應的條件集上具有相似的表達模式。
2 蝙蝠算法
蝙蝠算法是基于蝙蝠的回聲定位行為提出來的［7］。蝙蝠的回聲定位能夠幫助蝙蝠探測到目標的方向和位置，還可以幫助蝙蝠躲避障礙物。蝙蝠算法中將蝙蝠的一些行為理想化，理想化的規則如下：
（1）所有的蝙蝠都利用回聲定位來感知自身與目標的距離，并且以某種特殊的方式區別目標與障礙物。
（2）每只蝙蝠都擁有相同的脈沖頻率f、不同的波長λ和不同的響度A，在位置x以速度v隨機飛行。它們根據目標的接近程度調整發射脈沖的波長λ（或頻率f），并調整脈沖發射頻率r。
（3）假設響度從最大值A0變化到Amin。
該算法的主要思想是基于以上理想化規則，改變脈沖發射頻率、脈沖頻率、聲音響度，來尋找最優解［8］。定義蝙蝠的頻率、速度、位置更新公式：
其中f i為第i只蝙蝠的脈沖頻率，fmax和fmin分別為脈沖頻率的最大值和最小值，β是一個服從均勻分布的隨機值且β∈[0,1]，和分別是第i只蝙蝠在第t代和t-1代的飛行速度；和分別為第t代和第t-1代的位置；x*為當前群體中蝙蝠的最優位置（最優解）。
為了改善算法的局部搜索能力，使用如下公式更新進行局部搜索：
其中，At為第t次迭代所有蝙蝠的平均響度，ε∈[-1,1]是一個隨機數。隨著迭代的進行，響度A i和發射脈沖率r i都會進行更新，更新公式如下：
其中，α和γ是常數，是第i只蝙蝠的初始脈沖發射率。
蝙蝠算法的偽代碼如下所示：
算法1原始蝙蝠算法
目標函數：f(x),x=(x1,x2,…,x d)T;
1.初始化蝙蝠種群x i，速度v i，蝙蝠x i的頻率f i，脈沖發射率r i，響度A0，i=1,2,…,n
2.初始化參數蝙蝠種群數n,α,γ和最大迭代數ge nmax
3.根據目標函數找到當前全局最優解
4.fori=1 togenmax:
5.根據公式（4），（5），（6）生成新解
6.ifrand>r i（rand是一個隨機數，且rand∈[0,1]）
7.根據公式（7）生成一個新解
8.end if
9.通過目標函數評價新解
