Using Genetic Algorithms in MEMS Design

Introduction

Genetic algorithms belong to a family of algorithms called “stochastic algorithms”.  These algorithms are used to find the optimal solution to a mathematically difficult real-world problem, such as the “traveling salesman problem”.   Real-world applications for these algorithms include determining the most efficient routing of shipping trucks, or the optimal wiring routes for printed circuit boards.  Stochastic optimization (SO) algorithms generate and use random variables, and rely on randomness to converge toward an optimal solution.

Genetic algorithms have proven useful in many applications that cannot be easily addressed using alternative techniques. However, genetic algorithms will not always find the best solution to a problem, even though they can provide an approximate solution.  In fact, genetic algorithms work by generating a significant number of guesses and iterations to arrive at a solution, using a substantial amount of computer processor and memory resources to do so.

MEMS design is an optimization problem that contains a tremendous number of parameter choices and has a very large potential solution space. It lends itself to the use of genetic algorithms and can benefit from this type of mathematical optimization. MEMS device design normally relies on Finite Element Modeling, which is in itself computationally intensive. Therefore, using a genetic algorithm to address MEMS design optimization is computationally challenging.

How does It Work?

Genetic algorithms use a biologically inspired iterative process. In nature, each individual is defined by their unique gene combination. Those genes make an individual potentially more likely to survive and then transmit his or her genes to the next generation. When using genetic algorithms in the context of computer science, individuals or candidates are defined by a combination of parameter values instead of using genes.  An initial set of these candidates or parameters are evaluated through a user-defined “fitness function”, where more “fit” candidates survive to the next generation.  Preserved candidates are used to rebuild a set of potentially “better” candidates through cross-over or recombination. Most common genetic algorithms also rely on “mutations”, which create random changes in the choice of candidates. At each design iteration, the set of solutions will gradually “evolve” and preserve the most appropriate parameters to approach the optimal solution, just like random mutations in nature help living things become more fit for their environment.

Simple Example:

Let’s consider the following optimization problem. Consider x and y as two parameters that will be optimized to maximize the following fitness function:

The optimal solution is obvious, the fitness maximum solution is 6 since both x and y can’t be greater than 3. We will use this problem to illustrate the genetic algorithm approach in Figure 1 (below):

Figure 1: Genetic algorithm scheme

The “common” genetic algorithm includes 5 steps (but many variations are available in the literature):

• The input: These are the original sets of candidate solutions. We start with a population of 4 individual input solutions (inputs #1 – #4), and assign random values to the X and Y parameters for each possible solution (shown in the 2^nd and 3^rd rows of the table)
• Genetic Algorithm steps:
  • Selection: Each member of the population (input number) is evaluated using the fitness function and selected or sorted accordingly. Half of the population with the highest fitness score (largest combined X & Y value) are preserved for the next step. In this case, inputs #1 and #3 have the highest total score, and will go to the next step.
  • Cross over: New population members #5 and #6 are generated from the two preserved members #3 and #1, by switching over the Y values between members #1 and #3.
  • Mutation: An individual parameter is randomly modified, in this case the Y value of member #1 has changed from “0” to “3”.
• The Output: The output contains the final selection of possible solutions once the genetic algorithm has completed the cross-over and mutation steps. The criteria for stopping the calculations could include a limit to the number of iterations or a specific value of the fitness function (i.e. – in this case, the combined X and Y value)

Each generation involves the selection, crossover and mutation steps.   The results of these steps on the current generation will serve as an input for the next generation, until we reach the criteria to stop the process.

Genetic Algorithms in MEMS Design Using MEMS+^®:

The MEMS+ design software in the CoventorMP platform uses advanced finite elements to perform complex device analysis in a fast and computationally efficient manner. Therefore, we can combine genetic algorithms and MEMS+ modeling during simulation to provide a solution in a computationally reasonable timeframe.  All MEMS design applications could potentially benefit from a genetic algorithm methodology, since MEMS design goals can be included in the fitness function. For example, MEMS microphone designers aim to maximize the Signal to Noise Ratio (SNR), and this could be our optimization target.

We will now review an example of using genetic algorithms to optimize a MEMS microphone design. In this example, we will use a reference microphone design included with the CoventorMP installation package. This specific design example has a default SNR value of 70.6 dB, but many design parameters can be modified to enhance this value.

In this example, we will attempt to optimize eight (8) design parameters as shown in Figure 2.

Figure 2: Microphone parameters

The table in Figure 2 specifies a default value, a minimum value, and a maximum value for each of the 8 design parameters.  Minimum and maximum values must be defined carefully, either through experience and/or using foundry process design rules.

The fitness function in our genetic algorithm will use CoventorMP to compute the SNR for each combination of design parameters. The choice of variables with the highest SNR will be considered the “fittest” members of the population.

Running the genetic algorithm on this optimization problem is computationally intensive and requires many design iterations (approximately 420).

The plot shown in Figure 3 displays the evolution of the SNR value for each candidate design solution through different “generations” of design parameter modifications.  Note that each population has been sorted to ease visualization.

Figure 3: Genetic algorithm Signal to Noise Ratio vs. Candidate Solutions (plotted for Each Generation of Design Changes)

As expected, the SNR increases gradually during each generation of design changes, indicating that the genetic algorithm is able to improve the SNR only up to a certain value. The plots tend to end in a flat shape, which can be interpreted as an increase in SNR mean value or a clustering of candidate solutions. In addition, note that even the 21st generation still includes candidate solutions with a low SNR. This is inherent to stochastic algorithms; random variations are essential to optimize the design but will introduce inferior candidate solutions that need to be filtered out at each generation.

The scatter plots can be used to display the distribution of each individual design parameter and its corresponding effect on the SNR value. In Figure 4, we show 4 plots that display the microphone signal-to-noise ratio as a function of changes in 4 of the design parameters. Candidate design parameter values from each generation are plotted in blue, excluding the black data points belonging to the first generation and red data points that belong to the last generation of the genetic algorithm process.

Figure 4: Scatter plot of candidate solution parameter values versus calculated SNR

In the scatter plots, we can see the progressive clustering of all design parameters around the “optimal” value.   In fact, the first generation of design parameter values (shown as black dots in the plot) is evenly distributed along the x axis in a non-optimized manner while the last generation (in red) tends to form a data cluster around specific values of the design parameter that are closer to an optimum value and increase the SNR.   The genetic algorithm was able to improve the SNR of the microphone design from the default value of 70.6 dB to an optimized value of 74.95 dB, through modification of the microphone design parameters during successive generations of the algorithm.

Conclusion:

In this case study, we were able to use genetic algorithms to increase the SNR of a MEMS microphone reference design from 70.6 dB to 74.95 dB.

MEMS design is a lengthy process, which requires both substantial simulation time and substantial design experience to find an optimal design solution. CoventorMP helps engineers optimize their MEMS designs using advanced, high-speed simulation and system design tools. This article illustrates how genetic algorithms could be combined with CoventorMP to automatically explore and further optimize new MEMS designs.