Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (31): 16-20.

Previous Articles     Next Articles

Personification and genetic combinational algorithm for placement problem of digital microfluidics-based biochips

YANG Jingsong1, YAO Zhenjing1, SONG Yanxing1, ZUO Chuncheng2   

  1. 1.Department of Disaster Prevention Instrument, Institute of Disaster Prevention Science and Technology, Beijing 101601, China
    2.College of Mechanical Science and Engineering, Jilin University, Changchun 130022, China
  • Online:2012-11-01 Published:2012-10-30

数字微流控生物芯片布局的拟人遗传组合算法

杨敬松1,姚振静1,宋燕星1,左春柽2   

  1. 1.防灾科技学院 防灾仪器系,北京 101601
    2.吉林大学 机械科学与工程学院,长春 130022

Abstract: The placement problem of digital microfluidics-based biochips is the key to chip design. It creates a physical representation for each operating in 2D microfluidic array, in order to achieve the smallest biochip area and the shortest of completion time of all operations. This paper formulates the placement problem of digital microfluidic biochips with a personification and genetic combinational algorithm. The personification heuristic algorithm is used to control the packing process. Genetic algorithm is designed, which is used to multi-objective optimize the placement results. The process of microfluidic module physical placement in multiplexed in-vitro diagnostics on human physiological fluids is simulated. The experimental results show that personification and genetic combinational algorithm can achieve not only multi-objective optimization, but also better than the parallel simulated annealing algorithm.

Key words: digital microfluidics-biochips, placement, personification heuristic algorithm, genetic algorithm

摘要: 数字微流控生物芯片布局问题是芯片设计的关键问题,它是在二维微流控阵列上为每个操作布局一个合适的物理位置,以达到完成所有操作的微流控阵列总面积最小和总时间最短两个目标。构建了拟人遗传组合算法,应用拟人启发式算法来控制数字微流控模块的布局过程,用遗传算法对布局结果进行多目标优化,以多元体液检测为实例,模拟了数字微流控生物芯片的布局优化过程。实验结果表明该算法不仅达到了优化目标,且优于并行混合模拟退火算法。

关键词: 数字微流控生物芯片, 布局, 拟人启发式算法, 遗传算法