An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochips

Jiang，Chen; Yang，Rong Quan; Yuan，Bo

2022-10-01

10.1016/j.engappai.2022.105305

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE   Impact Factor & Quartile

0952-1976

1873-6769

As a revolutionary platform for miniaturizing laboratory procedures, the digital microfluidic biochip (DMFB) has the advantages of flexibility and re-configurability over its flow-based counterpart. Droplet routing is one of the most challenging problems in the design automation of DMFBs, which aims to schedule the movements of a set of droplets from their source electrodes to their target electrodes and satisfy both static and dynamic fluidic constraints. In this paper, we propose an evolutionary algorithm (EA) based droplet routing method with an indirect encoding scheme and an improved Dijkstra-based decoding strategy, to minimize the arrival time of the droplets. To be specific, the priority of the movements of the droplets are encoded in the chromosome instead of directly encoding the solution of the problem, i.e., a complete path from the source to the target for each droplet. In the 2D-routing decoding stage, a problem-specific cost function is defined and introduced in the Dijkstra algorithm for obtaining a more time-efficient path for each droplet. Meanwhile, to avoid accidental mixing of the droplets during their movements, several strategies are proposed to modify the paths for satisfying the fluidic constraints in different scenarios of both 2D-routing and 3D-compaction. Compared with the state-of-the-art droplet routing algorithms, the experimental results demonstrate the superiority of the proposed method based on two synthetic benchmark suites and a real-world bioassay benchmark suite.

Digital microfluidic biochip Droplet routing Evolutionary algorithm Indirect encoding

SCI ; EI

English

First ; Corresponding

National Natural Science Foundation of China[61976111];Science, Technology and Innovation Commission of Shenzhen Municipality[JCYJ20180504165652917];

Automation & Control Systems ; Computer Science ; Engineering

Automation & Control Systems ; Computer Science, Artificial Intelligence ; Engineering, Multidisciplinary ; Engineering, Electrical & Electronic

WOS:000862793500009

PERGAMON-ELSEVIER SCIENCE LTD

20223412612796

Biochips ; Blood ; Computer aided design ; Cost functions ; Decoding ; Digital microfluidics ; Drops ; Electrodes ; Encoding (symbols) ; Routing algorithms ; Signal encoding

Bioengineering and Biology:461 ; Biological Materials and Tissue Engineering:461.2 ; Microfluidics:632.5.1 ; Information Theory and Signal Processing:716.1 ; Computer Software, Data Handling and Applications:723 ; Data Processing and Image Processing:723.2 ; Computer Applications:723.5 ; Optimization Techniques:921.5

ENGINEERING

2-s2.0-85136236622

Scopus

Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China

Jiang，Chen,Yang，Rong Quan,Yuan，Bo. An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochips[J]. ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE,2022,115.

Jiang，Chen,Yang，Rong Quan,&Yuan，Bo.(2022).An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochips.ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE,115.

Jiang，Chen,et al."An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochips".ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 115(2022).