基于免疫蟻群優(yōu)化算法的細(xì)胞采集路徑規(guī)劃研究

王士信,付騰達(dá),陳淑玲

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

0 引言

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

細(xì)胞采集路徑規(guī)劃就是通過計(jì)算機(jī)控制顯微鏡把載玻片一定區(qū)域內(nèi)的細(xì)胞逐個(gè)進(jìn)行采集所走路線。采集路線的不同也就影響著整個(gè)標(biāo)本的采集速度。

傳統(tǒng)的細(xì)胞采集路徑是按照行列方式逐行逐列進(jìn)行采集。然而細(xì)胞分布并不是均勻分布的,這就造成了采集時(shí)間的浪費(fèi),因此本文采用了計(jì)算機(jī)智能算法進(jìn)行細(xì)胞采集路徑優(yōu)化。

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

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

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

1 問題描述

細(xì)胞在載玻片中是隨機(jī)分布的,并不是按照行列均勻分布的,細(xì)胞分布如圖1所示,在顯微鏡低倍鏡下把每個(gè)白細(xì)胞的坐標(biāo)記錄下來后,在高倍鏡下還是按照傳統(tǒng)的采集方式即按照行列方式逐行逐列進(jìn)行采集,這就造成了采集時(shí)間的浪費(fèi)。傳統(tǒng)采集方式如圖2所示。

圖1 細(xì)胞分布圖

圖2 傳統(tǒng)采集方式

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

2 算法及流程

2.1 傳統(tǒng)蟻群算法

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

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

(1)

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

隨著螞蟻不斷釋放信息素,它們之間的聯(lián)系也會(huì)變得越來越弱,ρ(0<ρ<1)可以作為一種衡量信息素?fù)]發(fā)程度的指標(biāo)。因此,一旦螞蟻完成一次循環(huán),就需要及時(shí)監(jiān)測(cè)細(xì)胞之間的信息素濃度,以確保其正常運(yùn)轉(zhuǎn)。其計(jì)算公式為:

(2)

2.2 人工免疫算法基本思想

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

人工免疫算法具體實(shí)現(xiàn)時(shí)主要有三大模塊:

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

(2)克隆篩選。通過不同的免疫操作總結(jié)并實(shí)現(xiàn)算法中克隆選擇的規(guī)律和策略。

(3)通過對(duì)抗體與抗原的親和度進(jìn)行評(píng)估,可以實(shí)時(shí)調(diào)整它們之間的匹配度,從而提高抗體與抗原的相互作用效果。

2.3 免疫蟻群算法

2.3.1 算法設(shè)計(jì)思想

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

2.3.2 人工免疫算子的構(gòu)造

人工免疫算子可以用來解決細(xì)胞采集路徑規(guī)劃問題,包括字符換位、字符移位、字符逆轉(zhuǎn)以及優(yōu)質(zhì)字符串的保留等幾種形式,可以幫助人們更好地理解細(xì)胞采集路徑,并且可以更有效地實(shí)現(xiàn)這些目標(biāo)[8]。

(1)字符換位。

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

(2)字符串移位算子。

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

(3)逆轉(zhuǎn)算子。

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

(4)優(yōu)質(zhì)字符串的保留。

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

2.3.3 算法基本步驟

根據(jù)算法的基本思想,免疫蟻群優(yōu)化算法的具體流程如圖3所示。

圖3 免疫蟻群優(yōu)化算法流程

具體步驟如下:

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

(2)生成初始種群。

(3)計(jì)算每個(gè)抗體的親和力。

(4)通過測(cè)量抗體的濃度,可以有效地激活或減弱具有較強(qiáng)親和力的抗體,而對(duì)于具有較弱親和力的抗體,則可以通過降低其濃度來實(shí)現(xiàn)調(diào)節(jié)。

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

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

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

(8)重新調(diào)整初始參數(shù),以確定狀態(tài)轉(zhuǎn)換的可能性。

(9)更新信息素。

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

3 仿真實(shí)驗(yàn)

為了驗(yàn)證算法的可行性和效果,首先使用通用的TSPLIB中的數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)來驗(yàn)證混合算法的可行性,然后再用真實(shí)的細(xì)胞數(shù)據(jù)進(jìn)行實(shí)驗(yàn)來驗(yàn)證混合算法的效果。

3.1 TSP數(shù)據(jù)實(shí)驗(yàn)

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

表1 3種算法對(duì)TSP數(shù)據(jù)實(shí)驗(yàn)結(jié)果比較

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

3.2 細(xì)胞采集數(shù)據(jù)實(shí)驗(yàn)

根據(jù)實(shí)際情況選擇了細(xì)胞個(gè)數(shù)不同的兩個(gè)標(biāo)本:A標(biāo)本31個(gè)細(xì)胞,B標(biāo)本100個(gè)細(xì)胞,分別使用AIA、ACA及AIA-ACA3個(gè)算法對(duì)A和B兩個(gè)標(biāo)本數(shù)據(jù)進(jìn)行驗(yàn)證測(cè)試,測(cè)試結(jié)果如表2所示。

從表2實(shí)驗(yàn)結(jié)果可以看出,免疫蟻群優(yōu)化算法(AIA-ACA)在兩個(gè)標(biāo)本的測(cè)試中都可以取得更優(yōu)解,從平均解可以看出,在31個(gè)細(xì)胞A標(biāo)本的實(shí)驗(yàn)中,平均解比蟻群算法提高了0.8%,比人工免疫算法提高了3.3%;在100個(gè)細(xì)胞的B標(biāo)本的實(shí)驗(yàn)中,平均解比蟻群算法提高了0.2%,比人工免疫算法提高了1.0%。同時(shí)魯棒性也更好。

4 結(jié)語

在蟻群算法中,螞蟻會(huì)運(yùn)用一種特殊的正向傳播機(jī)制以及一種相互促進(jìn)的相關(guān)激勵(lì),來加快搜索的進(jìn)度,但也會(huì)導(dǎo)致搜索結(jié)果的不穩(wěn)定,甚至?xí)l(fā)生早熟的情況,從而導(dǎo)致種群的局限性。相比之下,免疫算法的免疫算子更加靈活,可以有效地維護(hù)種群的多元性,并且可以有效地預(yù)防種群的衰落。通過將蟻群與免疫算法相結(jié)合,人們可以更好地發(fā)揮它們的優(yōu)勢(shì),從而構(gòu)建一種新的免疫蟻群優(yōu)化算法,并通過對(duì)TSP經(jīng)典數(shù)據(jù)的測(cè)試來驗(yàn)證免疫蟻群算法的可行性,最后把混合算法應(yīng)用到細(xì)胞采集路徑規(guī)劃中也取得了良好的效果,從而驗(yàn)證了算法的有效性。