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

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.