菌落挑选仪挑选通量提升算法研究

冯向东+罗玮+张荣福

摘 要：针对菌落挑选仪挑选通量低、耗时长、未挑选菌落易污染的问题，提出一种基于人工蜂群算法的多目标优化菌落挑选仪挑选方案。利用人工蜂群算法对菌落挑选仪中多目标问题进行优化，通过对蜂群初始化方式和邻域搜索方式进行改进，以提高算法寻找最优解的速度和全局搜索能力。将改进后的算法应用于挑选仪中，实验结果表明，该算法在优化菌落挑选仪的挑选行为上具有有效性和优越性。

关键词：人工蜂群算法；多目标优化；菌落挑选仪

DOIDOI：10.11907/rjdk.171262

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）007-0048-04

0 引言

菌落挑选仪的主要功能是在菌种筛选过程中实现菌落智能识别和自动优选，是菌落筛选自动化的基础仪器之一。通过将一些算法应用到菌落挑选仪中，完成挑选探针与待挑选菌落的匹配，可以提高挑选通量、优化挑选行为[1]。目前，菌落挑选仪挑选通量提高方法大都依靠采用先进的三维磁力导轨提高运行速度，或更改挑选仪的机械结构，以实现边挑选边接种。在现有提高挑选通量算法中，只针对路径这一因素进行建模优化。本文通过参考电机的运动参数与菌落污染度，提出基于人工蜂群算法的多目标优化菌落挑选算法，通过提高挑选通量优化挑选行为。人工蜂群算法是一种群体优化算法，源于对蜂群内部分工机制及觅食行为的模拟。该算法实现简单、无需设置较多参数、收敛速度快以及具有较高的收敛精度。产生智能行为的蜂群觅食模型[2]主要由3个基本要素和2个行为模式构成：食物源、受雇佣的觅食者、非受雇佣的觅食者和针对食物源的招募行为、放弃食物源[3]的行为。食物源的位置代表的是所要优化问题的可行解，而此处花蜜的丰富程度代表该可行解的质量。在基于本文目标问题的算法中，菌落和探针的匹配则代表可行解，达到算法的迭代次数后，满足约束条件的则是最优解。实验结果表明，迭代后得到的最优解可以提高菌落挑选仪的通量，优化挑选行为。

1 菌落挑选仪挑选行为模型及分析

1.1 菌落挑选仪挑选行为问题分析

影响挑选仪挑选效率的因素主要有硬件因素和软件因素。硬件因素包括电缸运行速度和探针模块伸缩速度。软件因素包括上位机对挑选仪通信速度以及菌落挑选顺序。在诸多进口样机中，挑选仪通量提高的手段主要是结构优化，例如环形结构，或者采用更先进的电缸，例如磁悬浮导轨电缸，对于挑选时菌落与探针的排序并没有进行优化。由于菌落数量与位置分布的随机性，若不对挑选行程进行优化，探针模块在菌落挑取时将耗费较多时间在移动中，容易造成先前挑取附着在探针上的菌落干裂脱落，也会降低整个挑选仪的通量，同时菌落挑选过程中已挑选菌落的针在挑选时经过未挑选菌落的上方，可能会有菌落滴落造成污染。当挑选仪采用96探针模块对96个菌落目标进行挑选时，其探针与菌落的配对组合有（96！2）种，解空间极大，不适合用遍历法求最佳解。

为了提高菌落挑选仪的挑选通量，缩短菌落挑选仪挑选时间，降低易污染度，本文提出基于這些问题的多目标人工蜂群算法[4]，提高菌落挑选仪的挑选通量，优化挑选行为。在该算法中，蜜源的位置代表了菌落与探针匹配的可行解，蜜源的蜜度值则代表了解的质量。解的质量好坏代表了菌落挑选仪在挑选过程中挑选通量的高低及挑选行为的好坏。蜜度值大的蜜源被采蜜蜂在信息交换区与其它蜂群进行信息交换，招募更多的蜂群前往采蜜[5]。采蜜蜂采用轮盘赌策略招募其它蜂群前往采蜜，蜜源的蜜度值越高招募的蜂群数量也就越大。通过招募其它蜂群对蜜源邻域附近进行搜索，加大对解的搜索力度，提高算法的寻优能力。

1.2 菌落挑选仪挑选行为模型分析

菌落挑选仪探针模块采用的是96针。探针间距为9mm。挑选仪的菌落目标置放在一个直径90mm的标准圆形培养皿中，实际菌落的尺寸不等，菌落的形状、分布呈现不规则状态，如图1所示。

挑选仪以电缸X、Y共同归零时1号探针的坐标作为参考点。设某一时刻探针1坐标（即电缸X、Y反馈的坐标）为（X1，Y1），目标菌落坐标为（Xc，Yc），若要使用第i根探针挑取菌落，则探针模块在X方向和Y方向移动距离分别为：

由于电缸X、Y轴的运动是并行的，因此可以认为运动距离的长短主要由X、Y轴上较长的运动距离决定。

依据上述可得单次挑选过程探针模块移动距离S为：

在实际挑选过程中，挑选仪电缸运行状态是一个起始加速、中段匀速最后减速的过程。在单次挑选中，不同的挑选距离将对应着电缸不同的运动状态，在一次完整的挑选中，相同探针模块的总移动距离，可以对应不同的移动时间。故在挑选算法中引入加减速模式作为算法的影响因子，以探针模块的移动时间作为适值，并以此作为算法解的约束条件。

图2显示了梯形加减速模式下，单步移动距离可能出现的3种情况，其中S2即图中的完整加减速距离2s，当S1>2s时，单步挑选时间由一个完整的加减速时间2t加上一段匀速时间组成；当S1=2s时，单步挑选时间等于一个完整的加减速时间2t；当S1<2s时，可根据移动距离S2求出加减速时间。

在菌落挑选仪器中，已挑选菌落探针上的菌落在经过未挑选的菌落上方时，有可能会滴落，使未挑选的菌落污染，因此在挑选流程中，需要尽可能地使已挑选菌落的针远离未挑选的菌落，降低易污染度的值。对培养皿中未挑选的菌落设立一个2mm的圆形保护区域，当已挑选菌落的针在随后的运动轨迹中，若在保护区域以外，认为探针不会对易污染度造成影响，Pollutei取值为0；若探针在运动轨迹中经过保护区域，则越靠近菌落中心，其易污染度值就越高，Pollutei取值与距离成反比。在经过菌落中心时取最大值200，如图3所示。

在实际挑选过程中，有些路径无法避免要经过保护区域，离菌落中心越远的挑选路径，其表征的此路径在污染度上的评价函数[6]值越高。菌落挑选过程中，存在多个约束条件，属于多目标优化问题，采用权向量法将多目标优化问题转化为单目标优化问题[7]。菌落挑选优化问题模型如图4所示。

2 菌落挑选通量提升算法实现

在人工蜂群算法中，蜂群包括：采蜜蜂、观察蜂、侦查蜂。其中，采蜜蜂占总蜂群数的一半。每个采蜜蜂初始化后都会有一个蜜源的位置相对应，而蜜源花蜜的丰富程度则代表的是解的质量[8]。采蜜蜂在蜂巢附近通过摇摆舞的方式将蜜源信息共享给观察蜂； 侦察蜂则是由采蜜蜂放弃所采蜜源后产生的蜂种，3种蜂群通过共享信息来寻找更好的蜜源[9]。人工蜂群算法是处理连续优化函数的最优化方法，而菌落挑选问题是一个求解最优资源分配的离散问题，因此需要将菌落挑选行为进行适当的编码，以便人工蜂群算法可以进行处理。这里用菌落号1～10代表10个菌落，以探针号1～96代表96根探针，在该编码方式中，前10位代表挑选的菌落号，后10位代表与菌落号对应的探针号，挑选顺序按在编码方式中的前后顺序排列。在1～10和11～106分别产生随机数，采用后面的值迭代前面的值[10]的方法产生随机初始化蜜源位置。菌落号和探针号匹配情况如图5所示。

式（9）中，S、Time、Pollute分别为探针移动的距离、探针移动的时间、污染度，α表示权向量。适度值越大，则代表此处的花蜜质量越好。

当人工蜂群的采蜜蜂观察蜂执行邻域搜索[12]时，由于该问题属于离散问题，不能采用随机数的方式生成邻域，这里随机选择将其中的一处或多处位置进行参数交换，实现邻域搜索，如图6所示。

采蜜蜂在信息交换区会与其它蜂进行信息交换，招募其它蜂群前往采蜜。每个蜂招募的概率采取轮盘赌策略[13]。此决策依据蜜源的适度值占所有蜜源适度值之和的比例确定其在轮盘上的色块区域面积，此面积即代表该蜜源被选中的概率p（θ）。

对于探针移动距离、挑选时间、污染度值，其蜜源评价函数Fit（θ）越小越优秀，设定一个最大值，使用评价函数最大值Fitmax与当前蜜源的评价函数值Fit（θ）之差（Fitmax-Fit（θ））作为构筑“轮盘赌”的依据，选择概率为：

观察蜂跟随采蜜蜂在蜜源附近采用变换步长策略[14]实现更加全面的搜索。大的搜索步长容易产生大的变换，这样可以更好地探索未知蜜源的位置，而小的步长则可以在已知蜜源的附近实现更加精密的搜索。大小步长的结合有利于加速算法收敛，提高算法的搜索效率。在提高菌落挑选通量的算法中，普通情况下，只需交换其中的一对参数，但当观察蜂的搜索在达到阈值次数后仍无法找到更好的蜜源位置时，将加大参数对的交换，使用大步长进行邻域搜索，并将该观察蜂的搜索次数置零。通过该方式，加强了算法的全局搜索能力[15]，可有效避免陷入局部极值。若采蜜蜂在限定搜索次数之后，仍未找到更好的蜜源，则采蜜蜂转换为侦查蜂，并产生新的蜜源位置。

3 仿真实验结果与分析

菌落挑选仪挑选通量提升算法研究中，蜂群参数设置如下：总蜂群数NP=100，采蜜蜂Foodnumber=NP/2=50，侦查蜂 SearchNumber =15，Limit=5。在迭代次数分别为50、100、500、1 000、2 000、5 000时，找到的最优值情况如图7-图9所示。

图7、图8、图9中，给出了该算法中的3个优化目标评价函数值的变化情况。可以看出，解的质量在初始状态比较差，随着迭代次数的增加，解的质量越来越好，1fitness的值变得越来越小，当迭代次数在2 000左右时，算法寻找到的解的质量也趋于平缓。从上述分析中可以了解到改进的领域搜索方法，大大改善了对最优解的搜索效率，提高了算法的开发能力，能够较快地搜索到全局最优解。

4 結语

针对未优化的菌落挑选仪挑选通量低、污染度值高等问题。本文利用人工蜂群算法，结合多目标优化，对菌落挑选仪存在的问题进行了优化。对挑选行为进行分析建模，改进了问题编码的方式和领域搜索方式，加强了算法对最优解的搜索。实验结果展示了该算法对多目标优化问题的可行性，并且优化结果良好。

参考文献：

[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]张长胜.多目标人工蜂群算法及遗传算法的研究与应用[M].长春：东北大学出版社，2013.

[3]王海泉，胡瀛月，廖伍代，等.基于改进人工蜂群算法的机器人路径规划[J].控制工程，2016，23（9）：1407-1411.

[4]周清雷，陈明昭，张兵.多目标人工蜂群算法在服务组合优化中的应用[J].计算机应用研究，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]铭炎，袁东风.人工蜂群算法及其应用[M].北京：科学出版社，2014.

[7]窦连航.基于人工蜂群算法的多机器人路径规划方法研究[D].上海：上海大学，2015.

[8]赵辉，李牧东，翁兴伟，等.分布式人工蜂群免疫算法求解函数优化问题[J].控制与决策，2015（7）：1181-1188.

[9]张冬丽.人工蜂群算法的改进及相关应用研究[D].秦皇岛：燕山大学，2014.

[10]胡中华，赵敏.基于人工蜂群算法的机器人路径规划[J].电焊机，2009，39（4）：93-96.

[11]解书琴.基于多目标混合人工蜂群算法的能效优化调度研究[D].武汉：华中科技大学，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].信息技术，2009，33（12）：127-129.

[14]张泰，屠思远，吴滨，等.增强寻优能力的自适应人工蜂群算法[J].计算机应用研究，2016，33（10）：2946-2948.

[15]孙德轩，赵息，杨黎明.基于提高全局搜索能力的微粒群优化研究[J].机械设计与制造工程，2007，36（9）：76-79.