Nanocell Optimization Techniques

Table of Contents

     Along each edge of the nanocell, there are pins that can be classified as either input, output, or control pins. Currently, in the nanocell simulation, the control pins are not varied with respect to voltage, and remain constant throughout the optimization process. Our goal is to vary the voltage on these pins in order to find a more optimal solution to the nanocell problem. Once the internal switches have been set by the initial genetic algorithm, a second optimization can then be run (at lower voltages so as not to reset the internal switches) to find the desired value of the control pins. The following work discusses the different optimization algorithms (and modifications made to these algorithms) in order to find the most accurate and efficient solutions to the nanocell optimization problem.

Background

     The Nelder-Mead Simplex algorithm, also known as the Amoeba Algorithm, is based on a simplex algorithm and is used to for minimization or maximization of a multidimensional function. In order to understand the modifications in the Nelder-Mead algorithm, one must first understand the standard simplex algorithm:

     In order to test the modified algorithms, I found several evaluation functions that have been used in previous optimization tests by other researchers. To begin with, I used three separate two dimensional functions, which can be seen with their respective graphs below.

Rosenbrock's Banana Function f(x,y) = 100(y - x2)2 + (1 - x)2 Starting Point: (-1.2, 1) Minimum: 0 at (1,1)
Freudenstein and Roth Function f(x,y) = (-13 + x + ((5 - y)y - 2)y)2 + (-29 + x + ((y + 1)y - 14)y)2 Starting Point: (0.5, -2) Minimum: 0 at (5,4) and 48.9842 at (11.41, -0.8986)
Beale's Function f(x,y) = (1.5 - x(1 - y))2 + (2.25 - x(1 - y2))2 + (2.625 - x(1 - y3))2 Starting Point: (1, 1) Minimum: 0 at (3,0.5)

Figure 2: Two - Dimensional Test Functions

     For the functions above, I used the amoeba algorithm to find the minimum, and varied the contraction factor as discussed above. The ALPHA constant was also varied. The tolerance of the termination criteria was set at 2.5 x 10^-9, and the maximum number of trials allowed was 2500. The results with the fewest trials are in bold.

     As referenced in the tables above, the exponential test provides the best results. By varying the contraction factor according to an exponential curve, the algorithm needed fewer tests to find the same minimum. Thus I propose that by varying the contraction factor in this method, one can improve upon the amoeba algorithm. It should once again be noted that the constants play a major role in the results of the algorithm - and thus I next attempted to use the exponential test results with varied constants. I first ran tests to see if the square root function were optimal, or if another root would provide even better results. Although the results varied greatly, I determined that the square root function was indeed the optimal solution for the tests. I similarly varied the maximum number of trials, of which the exponential curve is dependent on. Although it would be extremely time consuming to exhaustively test the combination of the exponential variable and the number of trials variable for each function/for each alpha value, I came to find that the exponential value of 0.5 and the maximum number of 2500 returned positive results, as can be seen in the tables. More results are forthcoming in a search to improve upon the exponential algorithm.

     Another way in which I attempted to improve upon the exponential factor results is to add some randomization into the results. Instead of following the exponential curve, I multiplied the contraction factor by a variable determined by a gaussian probability. This variation, in turn, led to several new constants to test, namely the amplitude of of the probability and the mean of the gaussian function. After a few initial tests, it became clear that large variations from the exponential curve resulted in disastrous results, most likely due to the fact that abnormally large contractions could have occurred in a undesireable location. I am currently continuing to examine this possiblity with small amplitudes on the order of 0.01 and less.

²Barton, Russell R. and John S. Ivey, Jr., "Nelder-Mead Simplex Modifications for Simulation Optimization," Management Science, Institute of Management Sciences, Providence, R.I., 42(1996), pp. 954-973.

³More, Jorge J., Burton S. Garbow, and Kenneth E. Hillstrom, "Testing Unconstrained Optimization Software," ACM Transactions on Mathematical Software, ACM, 7(1981), pp. 17-41.

⁴Press, William H., Numerical Recipies in C, Cambridge University Press, Cambridge, N.Y., 1995, pp. 408-412.

⁵Trabia, Mohamed B. and Xiao Bin Lu, "A Fuzzy Adaptive Simplex Seartch Optimization Algorithm," 25^th Design Automation Conference, ASME, Las Vegas, 1999, DETC99/DAC-8586.