基于免疫蟻群優化算法的細胞采集路徑規劃研究

王士信,付騰達,陳淑玲

(江西科技學院 信息工程學院,江西 南昌 330098)

0 引言

隨著科技的飛速進步,計算機的普及使得它成了許多領域的重要組成部分,而且基于計算機的全自動化的醫療設備也被廣泛應用。然而細胞采集儀器在臨床中卻很難應用,究其原因主要在于細胞采集儀器速度太慢,很難適用于臨床。因此,提高細胞采集速度就成了細胞采集儀器的當務之急。影響細胞采集速度有多種原因,細胞采集的路徑規劃[1]就是其中一個原因。

細胞采集路徑規劃就是通過計算機控制顯微鏡把載玻片一定區域內的細胞逐個進行采集所走路線。采集路線的不同也就影響著整個標本的采集速度。

傳統的細胞采集路徑是按照行列方式逐行逐列進行采集。然而細胞分布并不是均勻分布的,這就造成了采集時間的浪費,因此本文采用了計算機智能算法進行細胞采集路徑優化。

在進行細胞采樣路線規劃時,螞蟻群算法(Ant Colony Algorithm,ACA)可以實現分布式和并發的全局搜尋[2]。然而,ACA由于沒有足夠的初始條件,導致運算速度較低,而且算法的收斂速度也較高,因此存在明顯的局限性。由于在應用的過程中,ACA經常陷入局部最優,因此沒有辦法做到全局最優[3]。

當使用人工免疫算法[4](Artificial Immune Algorithm,AIA)規劃細胞采集路徑時,這種方法可以進行快速隨機的全局搜索,但系統的反饋信息沒有得到充分利用,需要在一定范圍內重復,這往往會降低求解效率[5]。

通過對人工免疫算法和蟻群算法的比較,本文提出了一種新的混合免疫蟻群優化算法,它具有快速全局搜索的特性,可以有效地找到更優的解決方案,并且可以根據蟻群算法的結果,計算出細胞采集的最佳路徑。

1 問題描述

細胞在載玻片中是隨機分布的,并不是按照行列均勻分布的,細胞分布如圖1所示,在顯微鏡低倍鏡下把每個白細胞的坐標記錄下來后,在高倍鏡下還是按照傳統的采集方式即按照行列方式逐行逐列進行采集,這就造成了采集時間的浪費。傳統采集方式如圖2所示。

圖1 細胞分布圖

圖2 傳統采集方式

把每個細胞的位置坐標(X,Y)記錄下來后,假設有n個細胞,那么所有細胞的坐標為(X1,Y1),(X2,Y2),…,(Xn,Yn)。那么白細胞采集的過程,就可以轉化為各個細胞坐標位置的連接過程,即從一個細胞位置到其他所有細胞位置都經過一次的過程。從一個細胞位置到下一個細胞位置的規劃都有多種方式,不同的規劃方式就會導致采集所有細胞的路徑長度不同,也就會影響采集細胞的時間。這樣細胞采集的問題就轉化為路徑規劃問題。

2 算法及流程

2.1 傳統蟻群算法

蟻群算法是一種根據螞蟻尋找食物過程中總是按照一定的規則找到蟻窩和食物之間最短路徑的方法改進而來的一種智能算法,意大利學者M.Dorigo等人把它應用到求解旅行商問題(Traveling Salesman Problem,TSP)中,得到了比較好的試驗效果[6]。那么細胞的坐標位置就相當于TSP中的城市,顯微鏡物鏡就相當于TSP中的旅行商,因此細胞采集問題可以采用蟻群算法進行路徑規劃。

將整個蟻群中的螞蟻的數目定為m,將細胞的數目定為n,將細胞i與細胞j之間的距離定為dij(i,j-1,2,…,n),在t時刻,細胞i和細胞j之間的信號通道中的信息素濃度為τij(t)。在開始的時候,由于細胞之間的連接路徑中的信息素的含量是一致的,因此可以將τij(0)=τ0。

(1)

ηij(t)是一個啟發性的函數,ηij(t)=1/dij,它表示在t時刻螞蟻從i到j的渴望程度,而allowk(k=1,2,…,m)則表示從螞蟻k出發的細胞以外的所有細胞的總和,它們的總和被稱為allowk,它們的值分別為1、2、m。每當被采集一個細胞,allowk中的細胞就會減少一個,直至allowk中的元素為空,代表所有細胞都已被采集。α是信息素的重要系數,α的值越大,這表明信息素的含量會對轉移產生的影響越大。β可以被視為啟發函數的一個重要的指標,它的值越高,說明啟發函數在遷移過程中的作用就越顯著,這意味著螞蟻可以更有可能遷移到距離較近的細胞。

隨著螞蟻不斷釋放信息素,它們之間的聯系也會變得越來越弱,ρ(0<ρ<1)可以作為一種衡量信息素揮發程度的指標。因此,一旦螞蟻完成一次循環,就需要及時監測細胞之間的信息素濃度,以確保其正常運轉。其計算公式為:

(2)

2.2 人工免疫算法基本思想

人工免疫算法是一種基于免疫學原理的智能計算方法[7],它利用免疫系統的多樣性,可以有效地改善種群的多樣性,從而解決“早熟”問題,并最終達到全局最優的結果。

人工免疫算法具體實現時主要有三大模塊:

(1)初始化抗體,對抗原進行識別。根據需要解決的問題來尋找合適的細胞序列,以用來初始化抗體序列。

(2)克隆篩選。通過不同的免疫操作總結并實現算法中克隆選擇的規律和策略。

(3)通過對抗體與抗原的親和度進行評估,可以實時調整它們之間的匹配度,從而提高抗體與抗原的相互作用效果。

2.3 免疫蟻群算法

2.3.1 算法設計思想

本文提出了一種新的算法即免疫蟻群算法(AIA-ACA),它將人工免疫技術與蟻群算法相結合,以實現更高效的路徑規劃。該算法分3個階段完成,首先,利用人工免疫算法初期的快速隨機搜索能力,找到一個較為有效的解決方案。其次,經過優化的蟻群算法,能夠根據人工免疫算法獲取的可行解,生成出更加準確的信息素分布。最后,利用蟻群算法具有正反饋的特性和并行性,提高算法的求解效率,并且在迭代過程中,不斷改善信息素揮發因子,從而獲得最佳的結果。

2.3.2 人工免疫算子的構造

人工免疫算子可以用來解決細胞采集路徑規劃問題,包括字符換位、字符移位、字符逆轉以及優質字符串的保留等幾種形式,可以幫助人們更好地理解細胞采集路徑,并且可以更有效地實現這些目標[8]。

(1)字符換位。

字符換位算子可以分為兩種:一種是單對字符換位算子,另一種是多對字符換位算子。單對字符換位操作是隨機取兩個不相等的正整數i、j,然后以一定的概率pc交換抗體A=(c1,c2,…,cn)中的一對字符ci,cj的位置;多對字符換位操作是通過預先確定一個正整數uc,在抗體A=(c1,c2,…,cn)中隨機取r(1

(2)字符串移位算子。

字符串移位算子,包括單個字符串移動算子和多個字符串移動算子。單個字符串移位操作是隨機選取兩個不相等的正整數i,j,在抗體A=(c1,c2,…,cn)中選取一個字符串A1,A1是從ci為始點,cj為終點,長度為j-i的字符串。然后按照一定的概率ps在抗體A中依次往右移動字符串A1,最右邊的則移動到最左邊的位置。多個字符串移位操作是指多個字符串按照一定的規則同時做字符串移位的操作。這種規則就是先確定一個正整數us,然后在抗體A中隨機選取小于us的個字符子串進行移位操作。

(3)逆轉算子。

逆轉算子是一種用于處理字符串的方法,它可以用于處理單獨的字符串或者多個字符串的轉換。單個字符串逆轉算子是隨機選取兩個不相等的正整數i、j,在抗體A=(c1,c2,…,cn)中選取一個字符串A1,A1是從ci為始點,cj為終點,長度為j-i的字符串。然后把字符串A1中的字符逆序。多個字符串逆轉算子是指多個字符串按照一定的規則同時做字符串逆轉操作。這種規則就是先確定一個正整數ui,然后在抗體A中隨機選取小于us的個字符子串進行逆序操作。

(4)優質字符串的保留。

優質字符串是指親和力很大的若干個抗體中包含的相同的字符子串。如果抗體中存在優質字符串,那么就想辦法保護這些字符串并且把優質字符串作為一個字符來處理,這種方法就稱為優質字符串的保護。

2.3.3 算法基本步驟

根據算法的基本思想,免疫蟻群優化算法的具體流程如圖3所示。

圖3 免疫蟻群優化算法流程

具體步驟如下:

(1)初始化抗原、抗體、初始參數以及環境條件,以達到最佳效果。

(2)生成初始種群。

(3)計算每個抗體的親和力。

(4)通過測量抗體的濃度,可以有效地激活或減弱具有較強親和力的抗體,而對于具有較弱親和力的抗體,則可以通過降低其濃度來實現調節。

(5)通過采用交叉、變異等技術,可以有效地改善群體的狀態,實現群體的更新。

(6)如果求得的結果符合要求,則繼續按照(7)的步驟進行,否則重新返回(2)的程序。

(7)使用蟻群算法來構建數據集,并記錄其中的元素分布。

(8)重新調整初始參數,以確定狀態轉換的可能性。

(9)更新信息素。

(10)如果條件被滿足,則輸出最佳解,并完成搜索。否則,重新進入步驟(8)。

3 仿真實驗

為了驗證算法的可行性和效果,首先使用通用的TSPLIB中的數據進行仿真實驗來驗證混合算法的可行性,然后再用真實的細胞數據進行實驗來驗證混合算法的效果。

3.1 TSP數據實驗

在實驗開始之前,AIA初始化參數設置為:pc=0.2,ps=0.3,pi=0.4,p0=0.5,uc=us=ui=[n1/4],uc=us=ui=[n1/4]。在每次抗體篩查過程中,將會優先考慮那些能夠和抗原相互匹配得更加完美的抗體,然后將這些隨機抽取出來的初始抗體經過20次遞歸迭代進行預處理。在ACA中,將m值調整至3,ρ值調整至0.7,α值調整至0.5,β值調整至0.9,Q值調整至100。數據采用att48和st70兩個數據,分別使用AIA、ACA及AIA-ACA 3個算法實驗30次,測試結果如表1所示。

表1 3種算法對TSP數據實驗結果比較

從表1實驗結果可以明顯看出免疫蟻群混合算法(AIA-ACA)的精度更高,在att48的實驗中,平均解比蟻群算法提高了1.2%,比人工免疫算法提高了2.6%;在st70的實驗中,平均解比蟻群算法提高了1.7%,比人工免疫算法提高了3.4%。從標準差的比較也可以看出混合算法的魯棒性更好,從而證明混合算法是可行的。

3.2 細胞采集數據實驗

根據實際情況選擇了細胞個數不同的兩個標本:A標本31個細胞,B標本100個細胞,分別使用AIA、ACA及AIA-ACA3個算法對A和B兩個標本數據進行驗證測試,測試結果如表2所示。

從表2實驗結果可以看出,免疫蟻群優化算法(AIA-ACA)在兩個標本的測試中都可以取得更優解,從平均解可以看出,在31個細胞A標本的實驗中,平均解比蟻群算法提高了0.8%,比人工免疫算法提高了3.3%;在100個細胞的B標本的實驗中,平均解比蟻群算法提高了0.2%,比人工免疫算法提高了1.0%。同時魯棒性也更好。

4 結語

在蟻群算法中,螞蟻會運用一種特殊的正向傳播機制以及一種相互促進的相關激勵,來加快搜索的進度,但也會導致搜索結果的不穩定,甚至會發生早熟的情況,從而導致種群的局限性。相比之下,免疫算法的免疫算子更加靈活,可以有效地維護種群的多元性,并且可以有效地預防種群的衰落。通過將蟻群與免疫算法相結合,人們可以更好地發揮它們的優勢,從而構建一種新的免疫蟻群優化算法,并通過對TSP經典數據的測試來驗證免疫蟻群算法的可行性,最后把混合算法應用到細胞采集路徑規劃中也取得了良好的效果,從而驗證了算法的有效性。