摘要
改进并应用项目调度遗传算法解决了数字微流控生物芯片中液滴的调度优化问题。在给出该问题的有向图模型和数学模型的基础上,详细阐述了算法的编码、交叉、变异和评价等操作步骤。用真实的生物化验的操作步骤作为实例(多元体液的体外检验),对算法进行计算机仿真。实验结果表明,对于大规模的生物化验来说,该算法得到的结果最接近问题的最优解,可以求得一个既满足次序约束又满足资源约束的液滴最优调度顺序,其搜索性能优于与其对比分析的其他调度算法。对于数字微流控生物芯片的体系结构设计具有一定的理论和实际应用价值。
An optimal Genetic Algorithm for Project Scheduling （GAPS） was proposed to solve the problem of biochemical scheduling of digital microfluidics-based biochips under resource constrains. The directed graph model and the mathematic model were presented. Then the encoding of the solution and the operations, such as crossover, mutation and evaluation, were described. An example of a real-life biochemical operation procedure （Multiplexed in-vitro Diagnostics on Human Physiological Fluid） was used to evaluate the proposed methodology. Experiments show that, for a biomedical assay of large scale, the results obtained by GAPS are close to the provable lower bounds, indicating that GAPS outperforms other scheduling algorithms. GAPS can provide the optimal scheduling sequences for the droplets of digital microfluidics-based biochips subject both to the precedence constrains and the resource constrains. It plays an important role in architectural-level synthesis of digital microfluidies-based biochips.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2007年第6期1380-1385,共6页
Journal of Jilin University:Engineering and Technology Edition
基金
'863'国家高技术研究发展计划项目(2006AA04Z305)
吉林省科技发展计划项目(20030524)
关键词
计算机应用
数字微流控
生物芯片
资源约束项目调度
遗传算法
生物化验
computer application
digital microfluidics
biochips
resource-constrained project scheduling
genetic algorithm
biochemical assay
