单克隆菌落挑选仪是集光学成像、图像识别和自动控制等技术于一身,应用于生物工程领域的一种高端仪器,在我国处于起步研制阶段。在经过诱变和培养的数以万计的菌株中,仅有百分之几是符合要求的高性能菌株。传统的挑选菌株方式是通过目视菌落形态颜色等特征,人工方式取出优质菌株,该方法不仅重复性差,而且效率极低。为了提高挑选效率和可靠性,美国、德国、瑞士等国相继开发出基于光学成像和图像识别技术的单克隆菌落挑选仪。其工作原理是对菌落图像进行分析,通过分析菌落形态、大小、圆度、长短径比和颜色等特征,进而标记出高性能菌落^{[1, 2]},并利用机械手带动探针实现菌落的挑取和转移。

单克隆菌落挑选仪的一个重要考核指标是单位时间内能完成的操作数量(即通量),通量与机械手行走的路径直接相关。因此为了实现高通量,需要找到最科学合理的挑选路径,这也是仪器研发面临的重要问题之一。

图 1

Fig. 1

图 1 菌落挑选仪探针阵列 Fig. 1 Probe array on selection instrument

菌落挑选仪探针阵列如图 1所示,机械手末端为12×8的探针阵列,菌落目标则随机分布在圆形培养皿区域内。随机械手移动到相应位置,探针逐一伸出,每根探针挑取一个目标后,一次性放入标准96孔深孔板。在设计初期,每次挑选匹配间隔距离最小的探针和菌落目标,以期通过减小单次运动量缩短总路径长度,该方法称为最近点法。最近点法是一种贪心算法,单次运动量对路径优化具有启发性,但不是决定性的。针对这一典型的组合优化问题,本文使用蚁群算法进行优化。 1 蚁群算法及其在路径优化中的实现 1.1 蚁群算法

蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法^[3],觅食过程中,虽然每只蚂蚁的智能和认知水平有限,但是通过个体与个体之间基于生物化学物质的通信,相互影响,最终能适应苛刻的环境,解决复杂的问题,这是一种群体智能。图 2为反映群体智能的双桥实验。

图 2

Fig. 2

图 2 双桥实验 Fig. 2 Dual bridge experiment

如图 2(a)所示蚁穴A与食物D之间存在障碍,起初蚁穴中的蚂蚁随机地寻找能绕过障碍搬运食物的路径,同时在这些路径上留下能被同伴嗅觉捕捉的信息素。不同的路径长度不一,如图(b)中的ABD、ACD,蚂蚁往返在较短的路径上将留下更多的信息素,随着信息素的浓度的差异,大多数的蚂蚁将选择较短的路径如图(c)所示。

蚁群算法即仿照蚂蚁群的这种行为特征,利用一组数据作为算子间通信的生物信息素,启发算法进行寻优搜索,可以解决复杂的组合优化问题。

假设有n个目标地点,开始有m只蚂蚁随机地分布在n个地点上,记t时刻i到j的路径l_ij上的信息素强度为τ_ij(t),在t+1时刻,m只蚂蚁各自向下一目标移动,为了防止蚂蚁反复经过同一目标,需设置禁忌表tabu,记录已经去过的目标,随移动进程变动。蚂蚁k在t时间内选择i到j的路径l_ij的概率可以根据路径上的信息素计算出^[4]

遍历过n个城市后在路径l_ij上的信息素为

蚁群算法可用在求解旅行商问题,旅行商问题(travelling salesman problem,TSP)即为一名旅行商需要去拜访若干城市,寻找只拜访各城市一次后返回出发点的最短路线的问题。其数学模型描述^[5]为C={c₁,c₂,…,c_n}为城市,L={l_ijc_i,c_j⊂C} 是集合C中元素两两之间的路径集合,d_ij为l_ij长度。G=(C,L)是一个有向图,求解旅行商问题是从G中找到长度最短的Hamilton圈。

区别于传统旅行商问题,在对挑选仪进行优化时,需要做以下处理:

(1)在对挑选仪路径优化时,相对目标移动的不是一个点,而是矩形探针阵列(以下称运动针盘),算法中的每次移动取决于运动针盘上要使用的探针p以及目标菌落t,组合集合C={(p,t)p∈P,t∈T}(P,T分别为96枚探针的集合和96处菌落目标的集合),由于探针和菌落均不重复使用,故约束任意两个C的元素c_k=(p_i,t_i)和c_l=(p_j,t_j),有p_i≠p_j且t_i≠t_j。

(2)运动针盘安装在正交的二维导轨组成的机械手上,由伺服电机驱动,以脉冲信号控制。在常加速度模式下,伺服电机接收到指定脉冲信号开始以a=0.3 g起步加速,加速至预先设定的工作速率v_m,脉冲停止时开始减速刹车^[6]。在统计行程时依据机械手运动的两个特点①两条导轨分别由各自电机驱动,定位时间由两条导轨中行程长的一维决定;②电机的行程和时间对应关系可视为为线性关系。

(3)蚁群算法工作建立在个体通信的基础上,对于大规模TSP问题,使用蚁群算法会产生极其庞大的运算开销,本文研究的探针与目标组合数达到了96²,完整的信息素记录可能多达几千万组,因此平衡通信开销和搜索空间的充分性是改进蚁群算法的必要工作。算法工作者为改进蚁群算法提出了多种信息素更新策略^[7]。在解决本问题时,引入能见度阈值的概念,运动针盘可选路径很多时(如在最开始的几步),决定运动方向前先根据各目标位置进行初步过滤,忽略运动跨度较大的路径上的信息素,这种跨越必然是不合理的。一种阈值设置方法Q_d=w(d_min+dmax),其中系数w∈(0,1),d_min、d_max分别为未使用的各探针与各目标的距离的最小、最大值。

此外,在算法程序中设置信息素字典动态记录路径被采用的概率,信息素持续挥发值小于一定值时,将此记录删除以节省存储空间。 2 模拟仿真实验 2.1 实验设计

本文根据蚁群算法编写了优化程序,并设计了仿真实验测试优化效果。在直径9 cm的区域内随机生成96个点作为菌落目标,探针排列为12列8行,相邻间隔9 mm,在菌落区域移动仿真图见图 3。根据菌落挑选仪在图像捕获时刻的位置关系,将两者初始相对位置设定为常数。

图 3

Fig. 3

图 3 仿真程序 Fig. 3 Simulation program

目标排列的形状与探针形状相符的程度决定着最优解的大小,极端情况下,目标排列与探针阵列完全相同,则整个挑选过程只需一次移动。为了减少“巧合”造成的影响,实验通过对多组目标优化,分析最优解的收敛情况。 2.2 实验结果

实验参数^{[8, 9]}中α=2.5、β=4.5、ρ=0.5、Q=400、m=20。绘制出平均路径长度收敛曲线如图 4,由图中可见,算法在1次迭代将最优解值收敛到415 mm,在5次内开始优于最近点法,随迭代次数增加,收敛逐渐趋于平缓。图 5反映了不同样本分别用最近点法和蚁群算法优化最终结果的差异。经过蚁群算法优化,路径总长度相比最近点法得到进一步缩短,而且没有因样本差异产生显著波动。

图 4

Fig. 4

图 4 最优解收敛曲线 Fig. 4 Convergence of the optimal solution

图 5

Fig. 5

图 5 蚁群算法与最近点法的算法结果比较 Fig. 5 Comparison between ACO and nearest tactics

本文针对单克隆挑选仪研发中遇到的挑选路径优化问题,结合机械手运动特点,将探针与目标组合,构成抽象城市的概念,根据蚁群算法,对最优挑选步骤进行了启发式优化,并采取适当的信息素策略控制运算规模。模拟实验结果表明,蚁群算法的应用有效地减少了菌落挑选探针的移动距离,从而提高了仪器通量。