(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110337821.4 (22)申请日 2021.03.30 (65)同一申请的已公布的文献号 申请公布号 CN 113065310 A (43)申请公布日 2021.07.02 (73)专利权人 福州大学 地址 350108 福建省福州市闽侯县福州大 学城乌龙江北 大道2号福州大 学 (72)发明人 刘耿耿　黄鸿斌　黄兴　徐赛娟　 郭文忠　陈国龙　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 专利代理师 陈鼎桂　蔡学俊 (51)Int.Cl. G06F 30/398(2020.01)G06F 30/27(2020.01) G06N 3/00(2006.01) (56)对比文件 CN 110928648 A,2020.0 3.27 CN 10724784 4 A,2017.10.13 CN 104252383 A,2014.12.31 CN 111510334 A,2020.08.07 US 2020380183 A1,2020.12.0 3 WO 2020181761 A1,2020.09.17 郭文忠 等.基 于混合离 散粒子群优化的轨 道分配算法. 《模式识别与人工智能》 .2019, 审查员 陈银兰 (54)发明名称 基于粒子群算法的连续微流体生物芯片高 级综合设计方法 (57)摘要 本发明涉及一种基于粒子群算法的连续微 流体生物芯片高级综合设计方法， 包括以下步 骤： 步骤S1:根据时序图以及所给定的组件类型 与数量对粒子群进行初始化； 步骤S2:对每个粒 子使用列表调度算法， 进一步得到每个粒子的调 度解;步骤S3:根据该绑定与调度解计算该粒子 的适应度函数值； 步骤S4:根据个体历史最优解 和全局历史最优解迭代更新粒子， 若当前迭代次 数达到迭代阈值， 则得到最优的绑定与调度方 案。 本发明能在不牺牲生化反应执行时间的前提 下， 得到需要更少流通道交叉点数量的绑定与调 度方案。 权利要求书1页 说明书5页 附图2页 CN 113065310 B 2022.06.14 CN 113065310 B 1.一种基于粒子群算法的连续微流体生物芯片高级综合设计方法， 其特征在于， 包括 以下步骤： 步骤S1:根据时序图以及所 给定的组件类型与数量对粒子群进行初始化； 步骤S2:对每 个粒子使用列表调度算法， 得到每 个粒子的调度解； 步骤S3:根据绑定与调度解计算该 粒子的适应度函数值； 步骤S4:根据个体历史最优解和全局历史最优解迭代更新粒子， 若当前迭代次数达到 迭代阈值， 则得到最优的绑定与调度方案； 所述步骤S 1具体为： 粒子群 中的每个粒子的位置向量根据时序图以及所给定的组件类 型与数量进行编码， 编码完成后， 每 个粒子代 表着一组操作对应所要绑定的组件的组合； 所述步骤S2具体为： 步骤S21:根据时序图， 计算每个操作的优先级， 当操作 就绪时会被加入到列表中， 列表 中的操作将会根据优先级 进行调度； 步骤S22:通过对粒子调用列表调度算法， 得到一组绑定与调度 方案及该绑定与调度 方 案下生化反应完成时间； 所述列表调度算法首先根据时序图， 计算每个操作的优先级， 先把已经就绪可以执行 的操作加入到列表中， 根据列表中操作的优先级取出操作进行调度， 优先级越高的操作越 优先进行调度； 调 度完成， 则更新其他操作状态， 若有新的就绪操作， 则加入到列表中， 并重 新按照操作的优先级进行调度； 当列表中没有操作时， 调度完成； 同时， 最后一个调度的操 作的完成时间， 即为整个生 化反应的完成时间。 2.根据权利要求1所述的基于粒子群算法的连续微流体生物芯片高级综合设计方法， 其特征在于， 所述粒子的适应度函数值由流通道交叉点数量和生化反应完成时间的加权得 到 FTI＝α T+β I 其中T为生化反应的执 行时间， I 为流通道交叉点数量， α 和β 为权 重因子。 3.根据权利要求2所述的基于粒子群算法的连续微流体生物芯片高级综合设计方法， 其特征在于， 所述流通道交叉点数量根据已知的绑定与调度方案， 获取所需组件之间的连 接关系， 从而计算出 所需要的开关数量， 即流 通道交叉点数量。权　利　要　求　书 1/1 页 2 CN 113065310 B 2基于粒子群算法的连续微流体生物芯片高级综合设计方 法 技术领域 [0001]本发明属于集成电路计算机辅助设计技术领域， 具体涉及一种基于粒子群算法的 连续微流体生物芯片高级综合设计方法。 背景技术 [0002]过去近十年中， 微流体生物芯片因其试剂/样品消耗低、 制造成本低以及生化反应 执行效率高等原因， 受到越来越多研究人员的关注， 并被广泛地应用在多个领域中。 而随着 微流体生物芯片的广泛应用以及研究的不断深入开展， 越来越多的设计挑战被提出， 也就 需要有更多新的设计优化 算法和工艺。 [0003]微流体生物芯片主要可以分为数字微流体生物芯片和连续微流体生物芯片。 对于 连续微流体生物芯片的设计过程， 主要 可以分为以下几个步骤： 高级综合设计、 流层中的布 局与布线设计、 控制层中的阀门寻址以及控制通道布线设计。 高级综合设计所产生的绑定 与调度结果是流层设计的输入 之一， 因此绑定与调 度结果的质量将会直接影响到流层设计 中的布局与布线， 从而也会影响到整个连续微流控生物芯片的设计结果质量。 为了能够得 到更好地得到连续微流控生物芯片的流层设计与控制层设计结果， 可以将流层设计中的流 通道交叉点数量目标加入到高级综合设计的考虑和 约束中， 从而得到更好的生物芯片设计 结果。 [0004]在高级综合阶段， 需要根据输入的序列图进行绑定与调度。 序列图由复杂的生物 测定协议建模而成， 序列图中的每个节点 都表示一个特定类型的操作(如混合、 加热、 过滤、 检测等)以及相应的执行时间， 而 连接两个节点的边则表示两个操作之间的从属关系， 如图 1所示， 其为包含10个操作的时序图。 根据序列图， 将操作 绑定到相应的生化组件上， 并设计 操作的调度方案， 最终得到如图2所示的绑定与调度方案 。 [0005]一般的高层综合设计算法都是只以最小化生化反应时间为目的， 只通过列表调度 算法对操作进行绑定与调度， 这样的考虑不够全面， 忽视了其他的约束和影响。 因此， 为了 再高层综合设计中考虑更多问题， 有 些研究人员提出了在设计过程中将生化反应过程中的 液体存储次数和所产生的控制端口数量等进 行考虑和 约束。 但针对于流通道交叉点数量的 考虑， 目前还没有研究人员提出。 高层综合设计已经被证明是NP难问题， 当所涉及的组件数 和操作数较大时， 往 往很难得到最优解。 发明内容 [0006]有鉴于此， 本发明的目的在于提供一种基于粒子群算法的连续微流体生物芯片高 级综合设计方法， 以优化流通道交叉点数量、 生化反应执行时间为目标， 最 终得到较好的绑 定与调度方案 。 [0007]为实现上述目的， 本发明采用如下技 术方案： [0008]一种基于粒子群算法的连续 微流体生物芯片高级综合设计方法， 包括以下步骤： [0009]步骤S1:根据时序图以及所 给定的组件类型与数量对粒子群进行初始化；说　明　书 1/5 页 3 CN 113065310 B 3