菌落挑選儀挑選通量提升算法研究

馮向東+羅瑋+張榮福

摘 要：針對菌落挑選儀挑選通量低、耗時長、未挑選菌落易污染的問題，提出一種基于人工蜂群算法的多目標(biāo)優(yōu)化菌落挑選儀挑選方案。利用人工蜂群算法對菌落挑選儀中多目標(biāo)問題進(jìn)行優(yōu)化，通過對蜂群初始化方式和鄰域搜索方式進(jìn)行改進(jìn)，以提高算法尋找最優(yōu)解的速度和全局搜索能力。將改進(jìn)后的算法應(yīng)用于挑選儀中，實(shí)驗(yàn)結(jié)果表明，該算法在優(yōu)化菌落挑選儀的挑選行為上具有有效性和優(yōu)越性。

關(guān)鍵詞：人工蜂群算法；多目標(biāo)優(yōu)化；菌落挑選儀

DOIDOI：10.11907/rjdk.171262

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）007-0048-04

0 引言

菌落挑選儀的主要功能是在菌種篩選過程中實(shí)現(xiàn)菌落智能識別和自動優(yōu)選，是菌落篩選自動化的基礎(chǔ)儀器之一。通過將一些算法應(yīng)用到菌落挑選儀中，完成挑選探針與待挑選菌落的匹配，可以提高挑選通量、優(yōu)化挑選行為[1]。目前，菌落挑選儀挑選通量提高方法大都依靠采用先進(jìn)的三維磁力導(dǎo)軌提高運(yùn)行速度，或更改挑選儀的機(jī)械結(jié)構(gòu)，以實(shí)現(xiàn)邊挑選邊接種。在現(xiàn)有提高挑選通量算法中，只針對路徑這一因素進(jìn)行建模優(yōu)化。本文通過參考電機(jī)的運(yùn)動參數(shù)與菌落污染度，提出基于人工蜂群算法的多目標(biāo)優(yōu)化菌落挑選算法，通過提高挑選通量優(yōu)化挑選行為。人工蜂群算法是一種群體優(yōu)化算法，源于對蜂群內(nèi)部分工機(jī)制及覓食行為的模擬。該算法實(shí)現(xiàn)簡單、無需設(shè)置較多參數(shù)、收斂速度快以及具有較高的收斂精度。產(chǎn)生智能行為的蜂群覓食模型[2]主要由3個基本要素和2個行為模式構(gòu)成：食物源、受雇傭的覓食者、非受雇傭的覓食者和針對食物源的招募行為、放棄食物源[3]的行為。食物源的位置代表的是所要優(yōu)化問題的可行解，而此處花蜜的豐富程度代表該可行解的質(zhì)量。在基于本文目標(biāo)問題的算法中，菌落和探針的匹配則代表可行解，達(dá)到算法的迭代次數(shù)后，滿足約束條件的則是最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，迭代后得到的最優(yōu)解可以提高菌落挑選儀的通量，優(yōu)化挑選行為。

1 菌落挑選儀挑選行為模型及分析

1.1 菌落挑選儀挑選行為問題分析

影響挑選儀挑選效率的因素主要有硬件因素和軟件因素。硬件因素包括電缸運(yùn)行速度和探針模塊伸縮速度。軟件因素包括上位機(jī)對挑選儀通信速度以及菌落挑選順序。在諸多進(jìn)口樣機(jī)中，挑選儀通量提高的手段主要是結(jié)構(gòu)優(yōu)化，例如環(huán)形結(jié)構(gòu)，或者采用更先進(jìn)的電缸，例如磁懸浮導(dǎo)軌電缸，對于挑選時菌落與探針的排序并沒有進(jìn)行優(yōu)化。由于菌落數(shù)量與位置分布的隨機(jī)性，若不對挑選行程進(jìn)行優(yōu)化，探針模塊在菌落挑取時將耗費(fèi)較多時間在移動中，容易造成先前挑取附著在探針上的菌落干裂脫落，也會降低整個挑選儀的通量，同時菌落挑選過程中已挑選菌落的針在挑選時經(jīng)過未挑選菌落的上方，可能會有菌落滴落造成污染。當(dāng)挑選儀采用96探針模塊對96個菌落目標(biāo)進(jìn)行挑選時，其探針與菌落的配對組合有（96！2）種，解空間極大，不適合用遍歷法求最佳解。

為了提高菌落挑選儀的挑選通量，縮短菌落挑選儀挑選時間，降低易污染度，本文提出基于這些問題的多目標(biāo)人工蜂群算法[4]，提高菌落挑選儀的挑選通量，優(yōu)化挑選行為。在該算法中，蜜源的位置代表了菌落與探針匹配的可行解，蜜源的蜜度值則代表了解的質(zhì)量。解的質(zhì)量好壞代表了菌落挑選儀在挑選過程中挑選通量的高低及挑選行為的好壞。蜜度值大的蜜源被采蜜蜂在信息交換區(qū)與其它蜂群進(jìn)行信息交換，招募更多的蜂群前往采蜜[5]。采蜜蜂采用輪盤賭策略招募其它蜂群前往采蜜，蜜源的蜜度值越高招募的蜂群數(shù)量也就越大。通過招募其它蜂群對蜜源鄰域附近進(jìn)行搜索，加大對解的搜索力度，提高算法的尋優(yōu)能力。

1.2 菌落挑選儀挑選行為模型分析

菌落挑選儀探針模塊采用的是96針。探針間距為9mm。挑選儀的菌落目標(biāo)置放在一個直徑90mm的標(biāo)準(zhǔn)圓形培養(yǎng)皿中，實(shí)際菌落的尺寸不等，菌落的形狀、分布呈現(xiàn)不規(guī)則狀態(tài)，如圖1所示。

挑選儀以電缸X、Y共同歸零時1號探針的坐標(biāo)作為參考點(diǎn)。設(shè)某一時刻探針1坐標(biāo)（即電缸X、Y反饋的坐標(biāo)）為（X1，Y1），目標(biāo)菌落坐標(biāo)為（Xc，Yc），若要使用第i根探針挑取菌落，則探針模塊在X方向和Y方向移動距離分別為：

由于電缸X、Y軸的運(yùn)動是并行的，因此可以認(rèn)為運(yùn)動距離的長短主要由X、Y軸上較長的運(yùn)動距離決定。

依據(jù)上述可得單次挑選過程探針模塊移動距離S為：

在實(shí)際挑選過程中，挑選儀電缸運(yùn)行狀態(tài)是一個起始加速、中段勻速最后減速的過程。在單次挑選中，不同的挑選距離將對應(yīng)著電缸不同的運(yùn)動狀態(tài)，在一次完整的挑選中，相同探針模塊的總移動距離，可以對應(yīng)不同的移動時間。故在挑選算法中引入加減速模式作為算法的影響因子，以探針模塊的移動時間作為適值，并以此作為算法解的約束條件。

圖2顯示了梯形加減速模式下，單步移動距離可能出現(xiàn)的3種情況，其中S2即圖中的完整加減速距離2s，當(dāng)S1>2s時，單步挑選時間由一個完整的加減速時間2t加上一段勻速時間組成；當(dāng)S1=2s時，單步挑選時間等于一個完整的加減速時間2t；當(dāng)S1<2s時，可根據(jù)移動距離S2求出加減速時間。

在菌落挑選儀器中，已挑選菌落探針上的菌落在經(jīng)過未挑選的菌落上方時，有可能會滴落，使未挑選的菌落污染，因此在挑選流程中，需要盡可能地使已挑選菌落的針遠(yuǎn)離未挑選的菌落，降低易污染度的值。對培養(yǎng)皿中未挑選的菌落設(shè)立一個2mm的圓形保護(hù)區(qū)域，當(dāng)已挑選菌落的針在隨后的運(yùn)動軌跡中，若在保護(hù)區(qū)域以外，認(rèn)為探針不會對易污染度造成影響，Pollutei取值為0；若探針在運(yùn)動軌跡中經(jīng)過保護(hù)區(qū)域，則越靠近菌落中心，其易污染度值就越高，Pollutei取值與距離成反比。在經(jīng)過菌落中心時取最大值200，如圖3所示。

在實(shí)際挑選過程中，有些路徑無法避免要經(jīng)過保護(hù)區(qū)域，離菌落中心越遠(yuǎn)的挑選路徑，其表征的此路徑在污染度上的評價函數(shù)[6]值越高。菌落挑選過程中，存在多個約束條件，屬于多目標(biāo)優(yōu)化問題，采用權(quán)向量法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題[7]。菌落挑選優(yōu)化問題模型如圖4所示。

2 菌落挑選通量提升算法實(shí)現(xiàn)

在人工蜂群算法中，蜂群包括：采蜜蜂、觀察蜂、偵查蜂。其中，采蜜蜂占總蜂群數(shù)的一半。每個采蜜蜂初始化后都會有一個蜜源的位置相對應(yīng)，而蜜源花蜜的豐富程度則代表的是解的質(zhì)量[8]。采蜜蜂在蜂巢附近通過搖擺舞的方式將蜜源信息共享給觀察蜂； 偵察蜂則是由采蜜蜂放棄所采蜜源后產(chǎn)生的蜂種，3種蜂群通過共享信息來尋找更好的蜜源[9]。人工蜂群算法是處理連續(xù)優(yōu)化函數(shù)的最優(yōu)化方法，而菌落挑選問題是一個求解最優(yōu)資源分配的離散問題，因此需要將菌落挑選行為進(jìn)行適當(dāng)?shù)木幋a，以便人工蜂群算法可以進(jìn)行處理。這里用菌落號1～10代表10個菌落，以探針號1～96代表96根探針，在該編碼方式中，前10位代表挑選的菌落號，后10位代表與菌落號對應(yīng)的探針號，挑選順序按在編碼方式中的前后順序排列。在1～10和11～106分別產(chǎn)生隨機(jī)數(shù)，采用后面的值迭代前面的值[10]的方法產(chǎn)生隨機(jī)初始化蜜源位置。菌落號和探針號匹配情況如圖5所示。

式（9）中，S、Time、Pollute分別為探針移動的距離、探針移動的時間、污染度，α表示權(quán)向量。適度值越大，則代表此處的花蜜質(zhì)量越好。

當(dāng)人工蜂群的采蜜蜂觀察蜂執(zhí)行鄰域搜索[12]時，由于該問題屬于離散問題，不能采用隨機(jī)數(shù)的方式生成鄰域，這里隨機(jī)選擇將其中的一處或多處位置進(jìn)行參數(shù)交換，實(shí)現(xiàn)鄰域搜索，如圖6所示。

采蜜蜂在信息交換區(qū)會與其它蜂進(jìn)行信息交換，招募其它蜂群前往采蜜。每個蜂招募的概率采取輪盤賭策略[13]。此決策依據(jù)蜜源的適度值占所有蜜源適度值之和的比例確定其在輪盤上的色塊區(qū)域面積，此面積即代表該蜜源被選中的概率p（θ）。

對于探針移動距離、挑選時間、污染度值，其蜜源評價函數(shù)Fit（θ）越小越優(yōu)秀，設(shè)定一個最大值，使用評價函數(shù)最大值Fitmax與當(dāng)前蜜源的評價函數(shù)值Fit（θ）之差（Fitmax-Fit（θ））作為構(gòu)筑“輪盤賭”的依據(jù)，選擇概率為：

觀察蜂跟隨采蜜蜂在蜜源附近采用變換步長策略[14]實(shí)現(xiàn)更加全面的搜索。大的搜索步長容易產(chǎn)生大的變換，這樣可以更好地探索未知蜜源的位置，而小的步長則可以在已知蜜源的附近實(shí)現(xiàn)更加精密的搜索。大小步長的結(jié)合有利于加速算法收斂，提高算法的搜索效率。在提高菌落挑選通量的算法中，普通情況下，只需交換其中的一對參數(shù)，但當(dāng)觀察蜂的搜索在達(dá)到閾值次數(shù)后仍無法找到更好的蜜源位置時，將加大參數(shù)對的交換，使用大步長進(jìn)行鄰域搜索，并將該觀察蜂的搜索次數(shù)置零。通過該方式，加強(qiáng)了算法的全局搜索能力[15]，可有效避免陷入局部極值。若采蜜蜂在限定搜索次數(shù)之后，仍未找到更好的蜜源，則采蜜蜂轉(zhuǎn)換為偵查蜂，并產(chǎn)生新的蜜源位置。

3 仿真實(shí)驗(yàn)結(jié)果與分析

菌落挑選儀挑選通量提升算法研究中，蜂群參數(shù)設(shè)置如下：總蜂群數(shù)NP=100，采蜜蜂Foodnumber=NP/2=50，偵查蜂 SearchNumber =15，Limit=5。在迭代次數(shù)分別為50、100、500、1 000、2 000、5 000時，找到的最優(yōu)值情況如圖7-圖9所示。

圖7、圖8、圖9中，給出了該算法中的3個優(yōu)化目標(biāo)評價函數(shù)值的變化情況?？梢钥闯觯獾馁|(zhì)量在初始狀態(tài)比較差，隨著迭代次數(shù)的增加，解的質(zhì)量越來越好，1fitness的值變得越來越小，當(dāng)?shù)螖?shù)在2 000左右時，算法尋找到的解的質(zhì)量也趨于平緩。從上述分析中可以了解到改進(jìn)的領(lǐng)域搜索方法，大大改善了對最優(yōu)解的搜索效率，提高了算法的開發(fā)能力，能夠較快地搜索到全局最優(yōu)解。

4 結(jié)語

針對未優(yōu)化的菌落挑選儀挑選通量低、污染度值高等問題。本文利用人工蜂群算法，結(jié)合多目標(biāo)優(yōu)化，對菌落挑選儀存在的問題進(jìn)行了優(yōu)化。對挑選行為進(jìn)行分析建模，改進(jìn)了問題編碼的方式和領(lǐng)域搜索方式，加強(qiáng)了算法對最優(yōu)解的搜索。實(shí)驗(yàn)結(jié)果展示了該算法對多目標(biāo)優(yōu)化問題的可行性，并且優(yōu)化結(jié)果良好。

參考文獻(xiàn)：

[1]REKABY A，YOUSSIF A A，SHARAF ELDIN A.Introducing adaptive artificial bee colony algorithm and using it in solving traveling salesman problem[C].Science and Information Conference，IEEE，2013：502-506.

[2]張長勝.多目標(biāo)人工蜂群算法及遺傳算法的研究與應(yīng)用[M].長春：東北大學(xué)出版社，2013.

[3]王海泉，胡瀛月，廖伍代，等.基于改進(jìn)人工蜂群算法的機(jī)器人路徑規(guī)劃[J].控制工程，2016，23（9）：1407-1411.

[4]周清雷，陳明昭，張兵.多目標(biāo)人工蜂群算法在服務(wù)組合優(yōu)化中的應(yīng)用[J].計算機(jī)應(yīng)用研究，2012，29（10）：3625-3628.

[5]YE T，XU H，LI F.A modified artificial bee colony algorithm[J].Journal of Changchun University of Science & Technology，2014，37（3）：137-140，145.

[6]銘炎，袁東風(fēng).人工蜂群算法及其應(yīng)用[M].北京：科學(xué)出版社，2014.

[7]竇連航.基于人工蜂群算法的多機(jī)器人路徑規(guī)劃方法研究[D].上海：上海大學(xué)，2015.

[8]趙輝，李牧東，翁興偉，等.分布式人工蜂群免疫算法求解函數(shù)優(yōu)化問題[J].控制與決策，2015（7）：1181-1188.

[9]張冬麗.人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用研究[D].秦皇島：燕山大學(xué)，2014.

[10]胡中華，趙敏.基于人工蜂群算法的機(jī)器人路徑規(guī)劃[J].電焊機(jī)，2009，39（4）：93-96.

[11]解書琴.基于多目標(biāo)混合人工蜂群算法的能效優(yōu)化調(diào)度研究[D].武漢：華中科技大學(xué)，2014.

[12]GAO W，LIU S，HUANG L.A global best artificial bee colony algorithm for global optimization[J].Journal of Computational & Applied Mathematics，2012，236（11）：2741-2753.

[13]梁宇宏，張欣.對遺傳算法的輪盤賭選擇方式的改進(jìn)[J].信息技術(shù)，2009，33（12）：127-129.

[14]張?zhí)?，屠思遠(yuǎn)，吳濱，等.增強(qiáng)尋優(yōu)能力的自適應(yīng)人工蜂群算法[J].計算機(jī)應(yīng)用研究，2016，33（10）：2946-2948.

[15]孫德軒，趙息，楊黎明.基于提高全局搜索能力的微粒群優(yōu)化研究[J].機(jī)械設(shè)計與制造工程，2007，36（9）：76-79.