YIELD OPTIMIZATION BY SIMULATED ANNEALING Lin-Lin Chen Stephen M. Pollock Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-23 September 1991

Yield Optimization by Simulated Annealing Lin-Lin Chen 1 Stephen M. Pollock Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor July 15, 1991 1The authors would like to thank Professor Robert L. Smith and H. Edwin Romeijn for providing the continuous simulated annealing algorithm.

1 Introduction Consider the design and manufacturing of a product. During the design stage, variables describing the performance of the product are identified, and functional requirements or constraints (in terms of these variables) are produced by applying scientific and engineering knowledge. A simple example of a variable is the diameter of a hole. An associated functional constraint might be the statement that this diameter must be greater than a certain value. The design intent described by the functional requirements are transformed into manufacturing specifications as expressed by dimensions and tolerances. The former specify the "nominal" values of the design variables, while the latter give "allowable" deviations from these nominal values. These dimensions and tolerances in turn determine the machining processes and the manufacturing yield, i.e., the fraction of items produced that actually satisfy the functional requirements or constraints. It is then not unreasonable to raise the question of how these dimensions and tolerances are specified. The manufacturing yield can be defined to be the probability that the manufactured part fulfills the functional requirements. This paper reports on a way to determine the dimensions (or the nominal values) of design variables such that the manufacturing yield is maximized. This is accomplished by the application of a continuous simulated annealing method, Hide&Seek. In section 2, the yield optimization problem is formulated and the applicability of Hide&Seek discussed. In section 3, correctness and convergence rate of Hide&Seek are verified by applying the algorithm to several simple yield optimization problems with known optima. In section 4, Hide&Seek is applied to a classic problem in dimensioning and tolerancing. The results are summarized in section 5. 2 Formulation Let the vector of design variables be x X = (Xix2, in) 1

and let the m different functional requirements be expressed by the inequalities fj(x) > 0, j = 1,...,m. The feasible region of the design is then the set F, defined by F = {: fj(x) > 0, j = 1,..., m}. Any x that falls inside F is considered to be functionally acceptable. The nature of the physical manufacturing process is modeled by letting x be a vector of random variables following some known continuous distribution. In particular, it is assumed that the manufacturing process is such that x has a multivariate normal distribution with a vector of expected values _ I = (= 21,,2 * n) and a variance-covariance matrix E O'7l 7l12... O'ln O21 0'22'* a 2n S. * *.,'anl an2' a nn which describe, respectively, the expected values and the variability of the manufacturing process. The yield is, by definition, the probability that the random vector x falls inside the region F. Usually,,u can be selected by deciding upon particular settings and parameters of the manufacturing process. In this case, the yield, given the selection of Au, is Y(p): Y() = Pr.{eF} (1) xF +X A) dx where +(x; A, E) denotes the probability density function of the multivariate normal distribution N(Q; S). Different choices of E produce different yields. To maximize yield, the vector _ can be found by solving the following optimization problem: max Y(_) (2) 2

To solve this optimization problem, two types of algorithms are needed: one for computing Y(_), and the other for searching for the _ that maximizes the corresponding yield. Suppose, for the moment, that the exact value of Y(,_) can be determined. By restricting it to vary within the feasible region F, the optimization problem (2) is reduced to the following global optimization problem: max Y(_) (3) iiEF Belisle et.al [1] give a continuous simulated annealing algorithm, Hide&Seek, for solving such a constrained global optimization problem and prove convergence to the global optimum. In what follows, Hide&Seek is used for solving problem (3). There is, however, one difficulty in applying Hide&Seek: Computing the value of Y(y) for all _ E F involves the computation of a multidimensional integral, which, in general, is unusually difficult to obtain with the accuracy required to distinguish its behavior as a function of /. In this paper, Y(f_) is not computed, but is instead estimated using Monte Carlo Simulation. This estimated yield (which is unbiased) is then used in conjunction with Hide&Seek. Since the proof of convergence to the global optimum in [1] applies to deterministic objective values, it was not clear how Hide&Seek would perform when the objective values are not deterministic. In the following two sections, the combined algorithm, Monte-Carlo/Hide&Seek (MC/H&S), is applied to several yield optimization problems and empirical results are reported. 3 Initial Tests To verify optimality and convergence of MC/H&S, the combined algorithm was applied to two sets of simple yield optimization problems with known optima. 3.1 Problems with Hypercubical Feasible Regions A test problem called Hypercube is first considered. It assumes a manufactured part with n independent unit-variance dimensions, and a functional 3

constraint set that requires each dimension to be within ~3 standard deviations from the origin. This is perhaps the simplest test problem whose optimum _ can be easily derived. Formally, Problem Hypercube is stated as follows: Problem 1 (Hypercube) max Y(_) = F (x; i, ) dx where: X = (1, X2,..., n), _ X N(y, E) 1.0 0.0... 0.0 0.0 1.0.-. 0.0 0.0 0.0.. 1.0 F = {x:-3.0 < xi < 3.0, i = 1,...,n} By symmetry, the optimum p4 is clearly the origin, (0,0,..., 0). The resulting maximum yield is ($(3.0) - $(-3.0))" _ 0.9974" where ((t) is the cumulative unit normal function. The estimates of the optimal yield, obtained by MC/H&S with 10,000 points in each Monte Carlo simulation, are shown in Figures 1 through 4 for n = 2,4,8, and 16. In these figures and those in section 3.2, percentage of error is calculated as follows: % Error = 1 - (Estimated Yield / Optimal Yield). As these figures show, even for the n = 16 case, convergence to within 5% of the optimum is achieved with fewer than 150 iterations. 4

Est. Yield % Error 1 1 0.8 0.& 0.6 0.6 0.4 0.4 0.2 0. 20o 40 60 80 0 Itetio 20 40 60 80 100 Iteration Figure 1: Yield for Hypercube with n = 2 and optimal yield = 0.99742 Est. Yield * Error o. s1 0.6 0.6 0.4 0.4 0.2 0.2 _ 5 10 0 20Iteration _ Iteration 0 10 10 200 Iteration20 40 60 80 10 10 140 Iteration Figure 2: Yield for Hypercube with n = 4 and optimal yield = 0.99744 Est. Yield % Error 0.&- 6 f0.8 0.6 [ 0.6 0.4 J 0.4 0.2( @0. 100 20 300 40 Iteration Iteraton ISO — ---- ^0 --- 5S --— IT3-0 Iteration. ----- 1 0 200 300 460 Iteration Figure 3: Yield for Hypercube with n = 8 and optimal yield = 0.99748 5

Est. Yield % Error It 1 0.81 _ 0. 0.6F 6 0.6 0.4 0.4 0.2 0.2 iteration Iteration 100 200 300 40 500 600 Iteration 10 200 300 4 500 60 Iteration Figure 4: Yield for Hypercube with n = 16 and optimal yield = 0.997416 3.2 Problems with Hyperspherical Feasible Regions A second simple problem with known optimum is defined as Problem Hypersphere. Here, F is assumed to be a hypersphere of radius 3, centered at the origin. Problem 2 (Hypersphere) Hypersphere is the same as Problem Hypercube except F is now defined by n F= {: x2 < 3.02} 1 By symmetry, the optimum p is again known to be the origin and the maximum yield is X (3.02) where X2 (t) is the cumulative Chi-Square function with n degrees of freedom. The results of applying MC/H&S (where, in each iteration, the yield is estimated by a Monte Carlo simulation of 10,000 points) to Problem Hypersphere-with n = 2,4,8, and 16 are shown in Figures 5 Through 8. These figures show that, for n = 2,4, and 8, the combined algorithm MC/H&S produces solutions within 5% of the optimum with less than 200 iterations. For n = 16, however, slower convergence is exhibited. This phenomenon might be attributable to the fact that, in order to estimate the small optimal yield (0.086586) to the precision required, a much larger sample size is needed in the Monte Carlo Simulation. 6

Est. Yield % Error O.O 0. 0.6. 0.6 0.4, 0.4 0.2 0.2 Iteration _ 2'0 4'0 60 80 100 20 40 60 80 10 Iteration Figure 5: Yield for Hypersphere with n = 2 and optimal yield = 0.988891 Est. Yield I Error 0. ~~~~~~~~~~~~~~0.8 0.64 0 0.6 0. 0.4 0.2 0.' _ 100 10 2M 20-0 Iteration Iteration ---- 5^ ----- ^0 ---- T?00 lo0 150 2200 50 1Itrat ion Figure 6: Yield for Hypersphere with n = 4 and optimal yield = 0.938901 Eat. Yield % Error I1T~~~~~~~~~~~~~~~~~~ 11 0o.8 O.8 0.6 0.6 0.4 0.40.2^ 0.Z, 100 2- 0 300 400 Iteration Iteration ~160 210 2 30 440 Iteration Figure 7: Yield for Hypersphere with n = 8 and optimal yield = 0.657704 7

Est. Yield % Error 1 0.8 0. 0.6 0.6 0.4 0.4 0.2 0.2 iteration Iteration 160 200 300 400 500 600 Iteration 0 20 30 40 50 6 Iteration Figure 8: Yield for Hypersphere with n = 16 and optimal yield = 0.086586 3.3 Test Results The empirical test results indicate that the combined algorithm MC/H&S performs well at least for these symmetric problems. This may have resulted from the fact that the yield approximated by the Monte Carlo simulation is an unbiased estimator of the actual yield. The drastic difference between the (estimated) optimal yields for Hypercube and Hypersphere problems having the same dimension n also demonstrates that a commonly used approximation scheme - fitting the largest inscribed hypersphere within F in order to get a tractable integral - will be poor when n is large. This is shown in Figure 9, which compares the actual yield for the case when the feasible region is a hypercube, and the estimated yield obtained from the inscribed hypersphere scheme, i.e., Y(actual) ~ 0.9974" Y(estimated) = X(3.02) 8

Yield / — actual 0.8 0.6 \ estimated by inscribed hypersphere 0.4 0.2 Dimension 5 10 15 20 25 30 Dimension Figure 9: Comparison of Actual Yield and Estimated Yield 4 Four-Hole Yield Optimization Problem In this section, a more realistic situation is considered: The simultaneous drilling of four holes such that the center of each hole must lie within a circular region'. This situation is illustrated in Figure 10. By sampling a sufficient number of the drilled holes (or by assumption), it is possible to determine: 1. for each hole, the probability distribution of the center, in particular the mean vector and the variance-covariance matrix for the center location random variables, and 2. the relative locations of the mean center vectors. In many cases, it is possible to translate or rotate the fixture holding the part, with respect to the four drilling tools, so that the yield can be improved. (It is assumed that such a translation and/or rotation will affect only the locations of the mean centers, but not the probability distributions of the centers around their respective means.) The following problem seeks a rotation and/or translation such that the yield is maximized:'The center of each drilled hole is assumed to be computable, for example by sampling a certain number of points from the profile of the hole and then fitting an ideal circle to the points. Since different circle-fitting algorithms may give different centers for the same set of sampled points, the selection of an appropriate algorithm is also an important issue, but beyond the scope of this paper. See [3] for a detailed discussion on this issue. 9

0S, i, I g I I I I,1 L',~~','o' II.4 -0.5 I \ - I \ /. \ / ^. % Figure 10: Problem Four-hole Yield Optimization. The center of each of the four holes is required to lie within the corresponding thick-lined circular region. The four dashed circles, with centers at the black dots, shows an example of four holes satisfying the constraints. 10

Problem 3 (Four-hole Yield Optimization) Let Xi be the random variable center location vector (xi1, x2), and let X denote a matrix, in which the ith row represents the vector of the (random variable) center of the ith hole, X11 X12 2Xi -2 X22 X31 X32 X41 X42 Let the vector pi = E[Xi] and the matrix, denote the locations of the mean of the center locations of the four holes,'IL11 L12 I21 I22 I31 I32 L/P41 #42 That is, pij - E[xij]. Assume that the components of Xi are Normally distributed with a high correlation. Thus, Xi = (xi1, X2), Xi, N(ps, ES), i = 1,2,3, 4 where (for example) 0.0009 0.0008 0.0008 0.0009 In addition, assume that the feasible region has been defined by the requirement that the center of each of the four holes must lie within circular regions of radius 0.1 centered at the four corners of the square defined by (1.0, 0.0), (0.0, 1.0), (-1.0, 0.0), and (0.0, -1.0). This feasible region can be written as F = {X:max (xi -cos((i- 1)* r/2))2 + (i2 - sin((i- 1) * 7r/2))2 < 0.12} Let d (dx, dy, de) be the amount of translation and rotation which will be applied simultaneously to the fixture in order to change the mean centers from pi to A', i = 1, 2, 3, 4. That is, for i = 1, 2, 3, 4, [i ]-[ 2 ] fcos(dO) sin(dO) [p I ]= [][-sin(dO) cos(dO) [ dy 11

A translation and rotation d is sought such that the yield will be maximized: max Y(l') = Pr.{X E F} d E R2 X [0,2X] MC/H&S was first applied to this problem with the vector of the initial mean centers p almost at the four corners of a square: 0.9795 -0,0571 -0.0266 0.9367 -1.0205 -0.0693 -0.0144 -1.0632 This initial configuration is shown in Figure 11. (In this figure and those that follow, mean centers are connected by line segments to indicate their relative locations.) 12

Figure 11: Initial configuration for Four-hole Yield Optimization with squarelike relative locations of i/. Shaded regions represent (schematically) the probability distributions of the centers. 13

During each iteration of Hide&Seek, a new mean centers matrix ut was generated by applying to / a translation-rotation dt found by the algorithm. The yield was estimated using Monte Carlo simulation with 10,000 samples of X. The yield obtained at each of the 200 iterations and the corresponding dt are shown in Figures 12 and 13. Since the relative locations of, are squarelike, it is reasonable that the "optimal" translation and rotation d found by MC/H&S should produce a /' that almost coincides with the four points (1.0, 0.0), (0.0, 1.0), (-1.0, 0.0), (0.0, -1.0). This is confirmed by the the final configuration shown in Figure 14. Yield 0.4 0.2 50 100 1- 0 200 Iteration Figure 12: Yield vs. iteration for Four-hole Yield Optimization with squarelike relative locations of 1 14

dO dyzr r,_N^3 -- -- \- / \ 0.0 011600^ Z 01~0 d y / f 00 00 - 0.05 ~ d9 dy 0.02 -. -.. 0 0.0 3 04 x 0.00.0 tion with squareli elative locations of.0 Succssiv dt' are labele b 2h 36 _____^g ddxy -o.02 -o0o0.01 0.2 0.03o. 00 2. 0 0 -0.00.05~~~~~~~~ ~ ~0.0 Figure 13: Amount of translation and rotation for Four-hole Yield Optimization with squarelike relative locations of p. Successive d are labelled by the iteration number t. The optimal d is indicated with a star. 15

Figure 14: Final configuration for Four-hole Yield Optimization with squarelike relative locations of p. Shaded regions represent (schematically) the probability distributions of the centers. 16

In the above example, the mean centers were almost at the corners of a square (representing, for example, a well set up and controlled process). Suppose, however, that the relative locations of / are distorted to start with, and therefore it is no longer possible to rotate and translate P to lie on the four corners of a square. This case can be illustrated by letting 1.1 0.0 0.0 1.0 /- -1.0 0.0 0.0 -1.0 The initial configuration is shown in Figure 15. It is still desirable to determine the translation-rotation d that will maximize yield. Again, the yield at each iteration was estimated using Monte Carlo simulation with 10,000 samples of X. The yield obtained at each iteration and the corresponding dt are shown in Figures 16 and 17. Since the original relative locations are distorted, the yield obtained is substantially less than that obtained in the previous case. The final (yield-maximizing) configuration is shown in Figure 18. 17

\ —0.,5 Figure 15: Initial configuration for Four-hole Yield Optimization with distorted relative locations of /. Shaded Regions represent the probability distributions of the centers. 18

Yield 50 100 1.0 20 Iteration Figure 16: Yield vs. iteration for Four-hole Yield Optimization with distorted relative locations of u 5 Conclusion MC/H&S was first applied to simple yield optimization problems with known optima. These test results are encouraging: in each ease, the solution obtained from applying Hide&Seek converges to the the true optimum after a number of iterations which, although depending on the dimension of the problem, is reasonably small. The results indicate that Hide&Seek promises to work well even when the objective function values are not deterministic. It is conjectured that this is due to the fact that an unbiased estimator of the actual yield is used for the optimization. The problem in Section 4 differs from those in Section 3 in an important aspect: The variables over which the optimization is performed are different from the variables in which the feasible region (and thus the yield) is defined. Therefore, the feasible region and the yield for each set of optimization variables are defined implicitly (rather than explicitly as in Section 3). Again, MC/H&S produces solutions which converge to the optimum in a reasonable number of iterations. It would be interesting to compare the performance of MC/H&S to deterministic optimization algorithms, if an efficient method of computing the yield could be obtained. Less satisfactory is the estimation of yield by Monte Carlo simulation. At each iteration, a large number of n-dimensional random points must be generated in order to estimate the yield to a certain precision. For example, sampling 10,000 10-dimensional points for 100 iterations translates into generating 107 random numbers. This quickly becomes a bottleneck during the 19

dO dy dy3 dO dy o.ol Ir. o.oo, Jfs oi 0.02 y 143.-0.015-0.05-0.055 -0 5 -0.045 4 - 35 -0.02 97' 7 -0.07 Figure 17: Amount of translation and rotation for Four-hole Yield Optimiza=0''' O -0.015. tion with distorted relative locations of. Successive dt are labelled by the -0.0 dO dy iteration number t. The optimal dtis indicated with a star. ~~~~~~~~~~~20~314 0.02 0. 00O. A 65 7 0.01 -0. 15 2 60 0 5.00. 5..O 0..o Co oo 04 o oo Figure 17: Amount of translation and rotation for Four-hole Yield Optimization with distorted relative locations of y. Successive dt are labelled by the iteration number t. The optimal dtis indicated with a star. 2O

0. 5 Figure 18: Final configuration for Four-hole Yield Optimization with distorted relative locations of i. Shaded Regions represent the probability distributions of the centers. 21

optimization process. However, since the feasible region never changes over the entire optimization process, it is suspected that an importance sampling technique [2] might be applied to improve the efficiency of successive yield estimations. References [1] C. J. P. Belisle, H. E. Romeijn, and R. L. Smith, "Hide-and-Seek: A Simulated Annealing Algorithm for Global Optimization", Tech. Rep. 90-25, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Sept. 1990. [2] J. M. Hammersley, "Monte Carlo Methods", London, Methuen; New York, Wiley, 1964. [3] S. Y. Chou, "On Measuring and Characterizing Circularity", Dimensioning and Tolerancing Project Report, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1991. 22