基于蟻群算法的單克隆菌落挑選儀路徑規(guī)劃

邱實(shí)　程金光　張榮福

摘要： 單克隆菌落挑選儀是集光學(xué)成像、圖像識(shí)別和自動(dòng)控制等技術(shù)于一身，應(yīng)用于生物工程領(lǐng)域的一種高端儀器。對(duì)12×8陣列挑選針和無序排列的菌落目標(biāo)，只有對(duì)挑選路徑和順序進(jìn)行優(yōu)化，才能有效提高挑選通量。針對(duì)這一需求，利用蟻群算法的基本原理，對(duì)單克隆菌落挑選儀挑選路徑進(jìn)行了優(yōu)化。仿真實(shí)驗(yàn)結(jié)果表明，該算法可以有效提高挑選效率。

關(guān)鍵詞： 蟻群算法； 信息素策略； 能見度

中圖分類號(hào)： TP 391.4文獻(xiàn)標(biāo)志碼： Adoi： 10.3969/j.issn.10055630.2015.03.016

Abstract： The highthroughput monoclonal colony selection instrument is a highend equipment applied to biological cell engineering which contains the technologies of optical imaging， image recognition and automatic control. For the 12×8 probe array and the targets in random order， only the optimization of selected path and order can improve the throughput. Thus， this paper presents the principle of the basic ant colony algorithm and optimizes the selection path based on the algorithm. Then results of the experiment prove the method can greatly improve the selection efficiency.

Keywords： ant colony algorithm； pheromone update strategy； visiability

引言單克隆菌落挑選儀是集光學(xué)成像、圖像識(shí)別和自動(dòng)控制等技術(shù)于一身，應(yīng)用于生物工程領(lǐng)域的一種高端儀器，在我國處于起步研制階段。在經(jīng)過誘變和培養(yǎng)的數(shù)以萬計(jì)的菌株中，僅有百分之幾是符合要求的高性能菌株。傳統(tǒng)的挑選菌株方式是通過目視菌落形態(tài)顏色等特征，人工方式取出優(yōu)質(zhì)菌株，該方法不僅重復(fù)性差，而且效率極低。為了提高挑選效率和可靠性，美國、德國、瑞士等國相繼開發(fā)出基于光學(xué)成像和圖像識(shí)別技術(shù)的單克隆菌落挑選儀。其工作原理是對(duì)菌落圖像進(jìn)行分析，通過分析菌落形態(tài)、大小、圓度、長短徑比和顏色等特征，進(jìn)而標(biāo)記出高性能菌落[12]，并利用機(jī)械手帶動(dòng)探針實(shí)現(xiàn)菌落的挑取和轉(zhuǎn)移。單克隆菌落挑選儀的一個(gè)重要考核指標(biāo)是單位時(shí)間內(nèi)能完成的操作數(shù)量（即通量），通量與機(jī)械手行走的路徑直接相關(guān)。因此為了實(shí)現(xiàn)高通量，需要找到最科學(xué)合理的挑選路徑，這也是儀器研發(fā)面臨的重要問題之一。圖1菌落挑選儀探針陣列

Fig.1Probe array on selection instrument菌落挑選儀探針陣列如圖1所示，機(jī)械手末端為12×8的探針陣列，菌落目標(biāo)則隨機(jī)分布在圓形培養(yǎng)皿區(qū)域內(nèi)。隨機(jī)械手移動(dòng)到相應(yīng)位置，探針逐一伸出，每根探針挑取一個(gè)目標(biāo)后，一次性放入標(biāo)準(zhǔn)96孔深孔板。在設(shè)計(jì)初期，每次挑選匹配間隔距離最小的探針和菌落目標(biāo)，以期通過減小單次運(yùn)動(dòng)量縮短總路徑長度，該方法稱為最近點(diǎn)法。最近點(diǎn)法是一種貪心算法，單次運(yùn)動(dòng)量對(duì)路徑優(yōu)化具有啟發(fā)性，但不是決定性的。針對(duì)這一典型的組合優(yōu)化問題，本文使用蟻群算法進(jìn)行優(yōu)化。

1蟻群算法及其在路徑優(yōu)化中的實(shí)現(xiàn)

1.1蟻群算法蟻群算法是一種模擬螞蟻群體覓食行為的仿生優(yōu)化算法[3]，覓食過程中，雖然每只螞蟻的智能和認(rèn)知水平有限，但是通過個(gè)體與個(gè)體之間基于生物化學(xué)物質(zhì)的通信，相互影響，最終能適應(yīng)苛刻的環(huán)境，解決復(fù)雜的問題，這是一種群體智能。圖2為反映群體智能的雙橋?qū)嶒?yàn)。

如圖2（a）所示蟻穴A與食物D之間存在障礙，起初蟻穴中的螞蟻隨機(jī)地尋找能繞過障礙搬運(yùn)食物的路徑，同時(shí)在這些路徑上留下能被同伴嗅覺捕捉的信息素。不同的路徑長度不一，如圖（b）中的ABD、ACD，螞蟻往返在較短的路徑上將留下更多的信息素，隨著信息素的濃度的差異，大多數(shù)的螞蟻將選擇較短的路徑如圖（c）所示。蟻群算法即仿照螞蟻群的這種行為特征，利用一組數(shù)據(jù)作為算子間通信的生物信息素，啟發(fā)算法進(jìn)行尋優(yōu)搜索，可以解決復(fù)雜的組合優(yōu)化問題。假設(shè)有n個(gè)目標(biāo)地點(diǎn)，開始有m只螞蟻隨機(jī)地分布在n個(gè)地點(diǎn)上，記t時(shí)刻i到j(luò)的路徑lij上的信息素強(qiáng)度為τij（t），在t+1時(shí)刻，m只螞蟻各自向下一目標(biāo)移動(dòng)，為了防止螞蟻反復(fù)經(jīng)過同一目標(biāo)，需設(shè)置禁忌表tabu，記錄已經(jīng)去過的目標(biāo)，隨移動(dòng)進(jìn)程變動(dòng)。螞蟻k在t時(shí)間內(nèi)選擇i到j(luò)的路徑lij的概率可以根據(jù)路徑上的信息素計(jì)算出[4]Pkij（t）=[τij（t）]α·[ηij（t）]β∑sallowedk[τis（t）]α·[ηis（t）]βjallowedk

0else（1）式中：allowedk表示螞蟻k下一步允許選擇的目標(biāo)，即全部目標(biāo)集合C減去k的禁忌表集合；α為信息啟發(fā)因子，表征信息素在路徑選擇時(shí)的作用；β為期望啟發(fā)因子，表征距離啟發(fā)因素（能見度）在路徑選擇時(shí)的作用；ηij為啟發(fā)函數(shù)，是路徑長度dij的倒數(shù)。每次螞蟻完成了一條路徑，就會(huì)更新各處的信息素。遍歷過n個(gè)城市后在路徑lij上的信息素為τij（t+n）=ρτij（t）+Δτij（2）

Δτij =∑mk=1Δτkij（3）式中，ρ為揮發(fā)系數(shù)，Δτij為在該次移動(dòng)中由其他螞蟻留下的信息素，Δτkij為螞蟻k在路徑lij上留下的信息素。根據(jù)基本的信息素策略[3]，信息素表達(dá)式為Δτkij=QLk第k只螞蟻經(jīng)過路徑lij

0第k只螞蟻并未經(jīng)過路徑lij（4）式中，Q為為信息素強(qiáng)度，Lk為螞蟻?zhàn)哌^的長度。

1.2蟻群算法在挑選儀單克隆菌落挑選儀優(yōu)化中的實(shí)現(xiàn)蟻群算法可用在求解旅行商問題，旅行商問題（travelling salesman problem，TSP）即為一名旅行商需要去拜訪若干城市，尋找只拜訪各城市一次后返回出發(fā)點(diǎn)的最短路線的問題。其數(shù)學(xué)模型描述[5]為C={c1，c2，…，cn}為城市，L={lijci，cjC} 是集合C中元素兩兩之間的路徑集合，dij為lij長度。G=（C，L）是一個(gè)有向圖，求解旅行商問題是從G中找到長度最短的Hamilton圈。區(qū)別于傳統(tǒng)旅行商問題，在對(duì)挑選儀進(jìn)行優(yōu)化時(shí)，需要做以下處理：（1）在對(duì)挑選儀路徑優(yōu)化時(shí)，相對(duì)目標(biāo)移動(dòng)的不是一個(gè)點(diǎn)，而是矩形探針陣列（以下稱運(yùn)動(dòng)針盤），算法中的每次移動(dòng)取決于運(yùn)動(dòng)針盤上要使用的探針p以及目標(biāo)菌落t，組合集合C={（p，t）p∈P，t∈T}（P，T分別為96枚探針的集合和96處菌落目標(biāo)的集合），由于探針和菌落均不重復(fù)使用，故約束任意兩個(gè)C的元素ck=（pi，ti）和cl=（pj，tj），有pi≠pj且ti≠tj。（2）運(yùn)動(dòng)針盤安裝在正交的二維導(dǎo)軌組成的機(jī)械手上，由伺服電機(jī)驅(qū)動(dòng)，以脈沖信號(hào)控制。在常加速度模式下，伺服電機(jī)接收到指定脈沖信號(hào)開始以a=0.3 g起步加速，加速至預(yù)先設(shè)定的工作速率vm，脈沖停止時(shí)開始減速剎車[6]。在統(tǒng)計(jì)行程時(shí)依據(jù)機(jī)械手運(yùn)動(dòng)的兩個(gè)特點(diǎn)①兩條導(dǎo)軌分別由各自電機(jī)驅(qū)動(dòng)，定位時(shí)間由兩條導(dǎo)軌中行程長的一維決定；②電機(jī)的行程和時(shí)間對(duì)應(yīng)關(guān)系可視為為線性關(guān)系t=vma+svm。（3）蟻群算法工作建立在個(gè)體通信的基礎(chǔ)上，對(duì)于大規(guī)模TSP問題，使用蟻群算法會(huì)產(chǎn)生極其龐大的運(yùn)算開銷，本文研究的探針與目標(biāo)組合數(shù)達(dá)到了962，完整的信息素記錄可能多達(dá)幾千萬組，因此平衡通信開銷和搜索空間的充分性是改進(jìn)蟻群算法的必要工作。算法工作者為改進(jìn)蟻群算法提出了多種信息素更新策略[7]。在解決本問題時(shí)，引入能見度閾值的概念，運(yùn)動(dòng)針盤可選路徑很多時(shí)（如在最開始的幾步），決定運(yùn)動(dòng)方向前先根據(jù)各目標(biāo)位置進(jìn)行初步過濾，忽略運(yùn)動(dòng)跨度較大的路徑上的信息素，這種跨越必然是不合理的。一種閾值設(shè)置方法Qd=w（dmin+dmax），其中系數(shù)w∈（0，1），dmin、dmax分別為未使用的各探針與各目標(biāo)的距離的最小、最大值。此外，在算法程序中設(shè)置信息素字典動(dòng)態(tài)記錄路徑被采用的概率，信息素持續(xù)揮發(fā)值小于一定值時(shí)，將此記錄刪除以節(jié)省存儲(chǔ)空間。

2模擬仿真實(shí)驗(yàn)

2.1實(shí)驗(yàn)設(shè)計(jì)本文根據(jù)蟻群算法編寫了優(yōu)化程序，并設(shè)計(jì)了仿真實(shí)驗(yàn)測(cè)試優(yōu)化效果。在直徑9 cm的區(qū)域內(nèi)隨機(jī)生成96個(gè)點(diǎn)作為菌落目標(biāo)，探針排列為12列8行，相鄰間隔9 mm，在菌落區(qū)域移動(dòng)仿真圖見圖3。根據(jù)菌落挑選儀在圖像捕獲時(shí)刻的位置關(guān)系，將兩者初始相對(duì)位置設(shè)定為常數(shù)。目標(biāo)排列的形狀與探針形狀相符的程度決定著最優(yōu)解的大小，極端情況下，目標(biāo)排列與探針陣列完全相同，則整個(gè)挑選過程只需一次移動(dòng)。為了減少“巧合”造成的影響，實(shí)驗(yàn)通過對(duì)多組目標(biāo)優(yōu)化，分析最優(yōu)解的收斂情況。

2.2實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)參數(shù)[89]中α=2.5、β=4.5、ρ=0.5、Q=400、m=20。繪制出平均路徑長度收斂曲線如圖4，由圖中可見，算法在1次迭代將最優(yōu)解值收斂到415 mm，在5次內(nèi)開始優(yōu)于最近點(diǎn)法，隨迭代次數(shù)增加，收斂逐漸趨于平緩。圖5反映了不同樣本分別用最近點(diǎn)法和蟻群算法優(yōu)化最終結(jié)果的差異。經(jīng)過蟻群算法優(yōu)化，路徑總長度相比最近點(diǎn)法得到進(jìn)一步縮短，而且沒有因樣本差異產(chǎn)生顯著波動(dòng)。

3結(jié)論本文針對(duì)單克隆挑選儀研發(fā)中遇到的挑選路徑優(yōu)化問題，結(jié)合機(jī)械手運(yùn)動(dòng)特點(diǎn)，將探針與目標(biāo)組合，構(gòu)成抽象城市的概念，根據(jù)蟻群算法，對(duì)最優(yōu)挑選步驟進(jìn)行了啟發(fā)式優(yōu)化，并采取適當(dāng)?shù)男畔⑺夭呗钥刂七\(yùn)算規(guī)模。模擬實(shí)驗(yàn)結(jié)果表明，蟻群算法的應(yīng)用有效地減少了菌落挑選探針的移動(dòng)距離，從而提高了儀器通量。參考文獻(xiàn)：

[1]周瑩莉，曾立波，劉均堂，等.基于圖像處理的菌落自動(dòng)計(jì)數(shù)方法及其實(shí)現(xiàn)[J].數(shù)據(jù)采集與處理，2003，18（4）：460464.

[2]陳東科.加強(qiáng)形態(tài)學(xué)檢查提高細(xì)菌鑒定的準(zhǔn)確性[J].實(shí)驗(yàn)與檢測(cè)醫(yī)學(xué)，2012，30（5）：419422.

[3]ERIC B，MARCO D，GUY T.Swarm intelligence：from natural to artificial systems[M].Oxford：Oxford University Press，1999.

[4]李士勇，陳永強(qiáng)，李研.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.

[5]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

[6]黃兆斌，黃云龍，余世明.幾種步進(jìn)電機(jī)加減速方法的對(duì)比研究及其應(yīng)用[J].機(jī)電工程，2011，28（8）：951974.

[7]岑宇森，熊芳敏，曾碧卿.基于新型信息素更新策略的蟻群算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（6）：20802083.

[8]詹士昌，徐婕，吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇[J].科技通報(bào)，2003，19（5）：381386.

[9]吳春明，陳治，姜明.蟻群算法中系統(tǒng)初始化及系統(tǒng)參數(shù)的研究[J].電子學(xué)報(bào)，2006，（8）：15301533.

（編輯：張磊）