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

邱實　程金光　張榮福

摘要： 單克隆菌落挑選儀是集光學成像、圖像識別和自動控制等技術于一身，應用于生物工程領域的一種高端儀器。對12×8陣列挑選針和無序排列的菌落目標，只有對挑選路徑和順序進行優化，才能有效提高挑選通量。針對這一需求，利用蟻群算法的基本原理，對單克隆菌落挑選儀挑選路徑進行了優化。仿真實驗結果表明，該算法可以有效提高挑選效率。

關鍵詞： 蟻群算法； 信息素策略； 能見度

中圖分類號： TP 391.4文獻標志碼： 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

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

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

1蟻群算法及其在路徑優化中的實現

1.1蟻群算法蟻群算法是一種模擬螞蟻群體覓食行為的仿生優化算法[3]，覓食過程中，雖然每只螞蟻的智能和認知水平有限，但是通過個體與個體之間基于生物化學物質的通信，相互影響，最終能適應苛刻的環境，解決復雜的問題，這是一種群體智能。圖2為反映群體智能的雙橋實驗。

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

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

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

0第k只螞蟻并未經過路徑lij（4）式中，Q為為信息素強度，Lk為螞蟻走過的長度。

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

2模擬仿真實驗

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

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

3結論本文針對單克隆挑選儀研發中遇到的挑選路徑優化問題，結合機械手運動特點，將探針與目標組合，構成抽象城市的概念，根據蟻群算法，對最優挑選步驟進行了啟發式優化，并采取適當的信息素策略控制運算規模。模擬實驗結果表明，蟻群算法的應用有效地減少了菌落挑選探針的移動距離，從而提高了儀器通量。參考文獻：

[1]周瑩莉，曾立波，劉均堂，等.基于圖像處理的菌落自動計數方法及其實現[J].數據采集與處理，2003，18（4）：460464.

[2]陳東科.加強形態學檢查提高細菌鑒定的準確性[J].實驗與檢測醫學，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]李士勇，陳永強，李研.蟻群算法及其應用[M].哈爾濱：哈爾濱工業大學出版社，2004.

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

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

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

[8]詹士昌，徐婕，吳俊.蟻群算法中有關算法參數的最優選擇[J].科技通報，2003，19（5）：381386.

[9]吳春明，陳治，姜明.蟻群算法中系統初始化及系統參數的研究[J].電子學報，2006，（8）：15301533.

（編輯：張磊）