亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2015-08-04 04:16:24邱實(shí)程金光張榮福
        光學(xué)儀器 2015年3期
        關(guān)鍵詞:蟻群算法能見(jiàn)度

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

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

        關(guān)鍵詞: 蟻群算法; 信息素策略; 能見(jiàn)度

        中圖分類(lèi)號(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)域的一種高端儀器,在我國(guó)處于起步研制階段。在經(jīng)過(guò)誘變和培養(yǎng)的數(shù)以萬(wàn)計(jì)的菌株中,僅有百分之幾是符合要求的高性能菌株。傳統(tǒng)的挑選菌株方式是通過(guò)目視菌落形態(tài)顏色等特征,人工方式取出優(yōu)質(zhì)菌株,該方法不僅重復(fù)性差,而且效率極低。為了提高挑選效率和可靠性,美國(guó)、德國(guó)、瑞士等國(guó)相繼開(kāi)發(fā)出基于光學(xué)成像和圖像識(shí)別技術(shù)的單克隆菌落挑選儀。其工作原理是對(duì)菌落圖像進(jìn)行分析,通過(guò)分析菌落形態(tài)、大小、圓度、長(zhǎng)短徑比和顏色等特征,進(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ā)面臨的重要問(wèn)題之一。圖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),以期通過(guò)減小單次運(yùn)動(dòng)量縮短總路徑長(zhǎng)度,該方法稱(chēng)為最近點(diǎn)法。最近點(diǎn)法是一種貪心算法,單次運(yùn)動(dòng)量對(duì)路徑優(yōu)化具有啟發(fā)性,但不是決定性的。針對(duì)這一典型的組合優(yōu)化問(wèn)題,本文使用蟻群算法進(jìn)行優(yōu)化。

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

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

        如圖2(a)所示蟻穴A與食物D之間存在障礙,起初蟻穴中的螞蟻隨機(jī)地尋找能繞過(guò)障礙搬運(yùn)食物的路徑,同時(shí)在這些路徑上留下能被同伴嗅覺(jué)捕捉的信息素。不同的路徑長(zhǎng)度不一,如圖(b)中的ABD、ACD,螞蟻往返在較短的路徑上將留下更多的信息素,隨著信息素的濃度的差異,大多數(shù)的螞蟻將選擇較短的路徑如圖(c)所示。蟻群算法即仿照螞蟻群的這種行為特征,利用一組數(shù)據(jù)作為算子間通信的生物信息素,啟發(fā)算法進(jìn)行尋優(yōu)搜索,可以解決復(fù)雜的組合優(yōu)化問(wèn)題。假設(shè)有n個(gè)目標(biāo)地點(diǎn),開(kāi)始有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)過(guò)同一目標(biāo),需設(shè)置禁忌表tabu,記錄已經(jīng)去過(guò)的目標(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ā)因素(能見(jiàn)度)在路徑選擇時(shí)的作用;ηij為啟發(fā)函數(shù),是路徑長(zhǎng)度dij的倒數(shù)。每次螞蟻完成了一條路徑,就會(huì)更新各處的信息素。遍歷過(guò)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)過(guò)路徑lij

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

        1.2蟻群算法在挑選儀單克隆菌落挑選儀優(yōu)化中的實(shí)現(xiàn)蟻群算法可用在求解旅行商問(wèn)題,旅行商問(wèn)題(travelling salesman problem,TSP)即為一名旅行商需要去拜訪(fǎng)若干城市,尋找只拜訪(fǎng)各城市一次后返回出發(fā)點(diǎn)的最短路線(xiàn)的問(wèn)題。其數(shù)學(xué)模型描述[5]為C={c1,c2,…,cn}為城市,L={lijci,cjC} 是集合C中元素兩兩之間的路徑集合,dij為lij長(zhǎng)度。G=(C,L)是一個(gè)有向圖,求解旅行商問(wèn)題是從G中找到長(zhǎng)度最短的Hamilton圈。區(qū)別于傳統(tǒng)旅行商問(wèn)題,在對(duì)挑選儀進(jìn)行優(yōu)化時(shí),需要做以下處理:(1)在對(duì)挑選儀路徑優(yōu)化時(shí),相對(duì)目標(biāo)移動(dòng)的不是一個(gè)點(diǎn),而是矩形探針陣列(以下稱(chēng)運(yùn)動(dòng)針盤(pán)),算法中的每次移動(dòng)取決于運(yùn)動(dòng)針盤(pán)上要使用的探針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)針盤(pán)安裝在正交的二維導(dǎo)軌組成的機(jī)械手上,由伺服電機(jī)驅(qū)動(dòng),以脈沖信號(hào)控制。在常加速度模式下,伺服電機(jī)接收到指定脈沖信號(hào)開(kāi)始以a=0.3 g起步加速,加速至預(yù)先設(shè)定的工作速率vm,脈沖停止時(shí)開(kāi)始減速剎車(chē)[6]。在統(tǒng)計(jì)行程時(shí)依據(jù)機(jī)械手運(yùn)動(dòng)的兩個(gè)特點(diǎn)①兩條導(dǎo)軌分別由各自電機(jī)驅(qū)動(dòng),定位時(shí)間由兩條導(dǎo)軌中行程長(zhǎng)的一維決定;②電機(jī)的行程和時(shí)間對(duì)應(yīng)關(guān)系可視為為線(xiàn)性關(guān)系t=vma+svm。(3)蟻群算法工作建立在個(gè)體通信的基礎(chǔ)上,對(duì)于大規(guī)模TSP問(wèn)題,使用蟻群算法會(huì)產(chǎn)生極其龐大的運(yùn)算開(kāi)銷(xiāo),本文研究的探針與目標(biāo)組合數(shù)達(dá)到了962,完整的信息素記錄可能多達(dá)幾千萬(wàn)組,因此平衡通信開(kāi)銷(xiāo)和搜索空間的充分性是改進(jìn)蟻群算法的必要工作。算法工作者為改進(jìn)蟻群算法提出了多種信息素更新策略[7]。在解決本問(wèn)題時(shí),引入能見(jiàn)度閾值的概念,運(yùn)動(dòng)針盤(pán)可選路徑很多時(shí)(如在最開(kāi)始的幾步),決定運(yùn)動(dòng)方向前先根據(jù)各目標(biāo)位置進(jìn)行初步過(guò)濾,忽略運(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ù)蟻群算法編寫(xiě)了優(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)仿真圖見(jiàn)圖3。根據(jù)菌落挑選儀在圖像捕獲時(shí)刻的位置關(guān)系,將兩者初始相對(duì)位置設(shè)定為常數(shù)。目標(biāo)排列的形狀與探針形狀相符的程度決定著最優(yōu)解的大小,極端情況下,目標(biāo)排列與探針陣列完全相同,則整個(gè)挑選過(guò)程只需一次移動(dòng)。為了減少“巧合”造成的影響,實(shí)驗(yàn)通過(guò)對(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。繪制出平均路徑長(zhǎng)度收斂曲線(xiàn)如圖4,由圖中可見(jiàn),算法在1次迭代將最優(yōu)解值收斂到415 mm,在5次內(nèi)開(kāi)始優(yōu)于最近點(diǎn)法,隨迭代次數(shù)增加,收斂逐漸趨于平緩。圖5反映了不同樣本分別用最近點(diǎn)法和蟻群算法優(yōu)化最終結(jié)果的差異。經(jīng)過(guò)蟻群算法優(yōu)化,路徑總長(zhǎng)度相比最近點(diǎn)法得到進(jìn)一步縮短,而且沒(méi)有因樣本差異產(chǎn)生顯著波動(dòng)。

        3結(jié)論本文針對(duì)單克隆挑選儀研發(fā)中遇到的挑選路徑優(yōu)化問(wèn)題,結(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.

        (編輯:張磊)

        猜你喜歡
        蟻群算法能見(jiàn)度
        阿克蘇機(jī)場(chǎng)2010年—2021年低能見(jiàn)度沙塵天氣統(tǒng)計(jì)分析
        能見(jiàn)度三百米
        2005—2017年白云機(jī)場(chǎng)能見(jiàn)度變化特征及其與影響因子關(guān)系研究
        CVRP物流配送路徑優(yōu)化及應(yīng)用研究
        云計(jì)算中虛擬機(jī)放置多目標(biāo)優(yōu)化
        基于蟻群算法的一種無(wú)人機(jī)二維航跡規(guī)劃方法研究
        蟻群算法基本原理及綜述
        一種多項(xiàng)目調(diào)度的改進(jìn)蟻群算法研究
        科技視界(2016年18期)2016-11-03 00:32:24
        低能見(jiàn)度下高速公路主動(dòng)誘導(dǎo)技術(shù)的應(yīng)用
        前向散射能見(jiàn)度儀的常見(jiàn)異?,F(xiàn)象處理及日常維護(hù)
        99精品视频在线观看| 国产一区二区三免费视频| 一本色道久久亚洲加勒比| 男女性杂交内射妇女bbwxz| 少妇被啪出水在线视频| 久久久99精品免费视频| 国产三级a三级三级| 亚洲日本va中文字幕| 亚洲国产精品久久久久久久| 无码成人AV在线一区二区| 麻豆成年人视频在线观看| 国产一区亚洲二区三区| 人人妻人人爽人人澡欧美一区| 色妞色综合久久夜夜| 无码91 亚洲| 偷拍视频这里只有精品| 夫妻免费无码v看片| 国产精品自在线拍国产手机版| 国产偷国产偷高清精品| 久久色悠悠亚洲综合网| 蜜桃一区二区三区在线视频| 精品久久久少妇一区二区| 亚洲综合av一区二区三区| 亚洲av色无码乱码在线观看| 伊人色综合九久久天天蜜桃| 在线视频观看一区二区| 成年免费a级毛片免费看| 成人看片黄a免费看那个网址| 亚洲 欧美 国产 日韩 精品| 一区二区三区国产精品| 丝袜美腿福利视频在线| 97久久综合区小说区图片区| 蜜桃精品免费久久久久影院| 色窝综合网| 成av人大片免费看的网站| 亚洲av无码国产精品色午夜字幕| 色妞www精品视频| 蜜桃av多人一区二区三区| 手机在线播放av网址| 中文字幕在线日亚洲9| 中文幕无线码中文字蜜桃|