Hardware Reference
In-Depth Information
5.3.4.2
Approach 2: Simulated Annealing-Based Device Placement
The computational complexity of Approach 1 may become prohibitively high as the
number of devices on a PCR biochip increases. In this case, we present a genetic
algorithm-based (GA-based) approach to search for an optimal placement of the
devices.
In the GA-based approach, each priority queue that contains all the devices on the
PCR biochip is encoded as a “chromosome”. A chromosome is a vector of random
keys (or “genes”) defined as below:
Chromosome
D
.
gene
.1/;
gene
.2/;
gene
.3/; : : : ;
gene
.n//;
where n is the number of devices that must be placed, and
gene
.i / (i
D
1 to n)is
a number sampled from Œ0; 1. The priority value of device i is set as: P
dev
.i /
D
gene.i/.
By sorting the priority values, a priority queue listing all the devices can be
derived. Then using the device placer introduced in Sect.
5.3.3
, a feasible placement
that satisfies the proximity constraints can be constructed by using any chromosome.
At the beginning of the GA-based approach, 4n chromosomes are randomly
generated. The following evolutionary operators are considered in the heuristic
approach:
•
Reproduction
. The chromosomes that correspond to the minimum value of the
cost function are copied to the next generation.
•
Crossover
. In the crossover procedure, two parent chromosomes are randomly
chosen from the old population. Their offspring chromosome is generated in the
following way:
gene
.i / of the offspring chromosome can either be copied from
gene
.i / of the parent chromosome. The probability that
gene
.i / is inherited from
the father and mother chromosomes are set as P and 1
P , respectively. The
offspring chromosome is added into the new population of the next generation.
•
Mutation
. The new chromosomes of the population are randomly generated to
guarantee the diversity of the population.
In the GA-based heuristic, we keep the number of chromosomes in each genera-
tiontobe4n. During the evolution, the n best chromosomes (i.e., the chromosomes
that correspond to the n minimum values of the cost function) are reproduced into
the next generation. A total of 2n chromosomes in the new population are the
offspring generated from the previous population, and n new chromosomes are
randomly generated. This proportion can be fine-tuned further through experiments.
After several generations of evolution, the chromosome with the minimum value of
cost function is selected from the final population. The solution for the placement
of the devices is constructed by using the chosen chromosome. In Sect.
5.4
, we will
discuss how to optimize droplet transportation and mixing time in the context of a
specific PCR protocol.
