DESA: a new hybrid global optimization method and its application to analog integrated circuit sizing. (English) Zbl 1172.90494
Summary: This paper presents a new hybrid global optimization method referred to as DESA. The algorithm exploits random sampling and the metropolis criterion from simulated annealing to perform global search. The population of points and efficient search strategy of differential evolution are used to speed up the convergence. The algorithm is easy to implement and has only a few parameters. The theoretical global convergence is established for the hybrid method. Numerical experiments on 23 mathematical test functions have shown promising results. The method was also integrated into SPICE OPUS circuit simulator to evaluate its practical applicability in the area of analog integrated circuit sizing. Comparison was made with basic simulated annealing, differential evolution, and a multistart version of the constrained simplex method. The latter was already a part of SPICE OPUS and produced good results in past research.
MSC:
| 90C30 | Nonlinear programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
optimization; simulated annealing; differential evolution; analog integrated circuit sizingReferences:
| [1] | Box, M.J.: A new method of constrained optimization and a comparison with other methods. Comput. J. 8, 42–52 (1965) · Zbl 0142.11305 |
| [2] | Powell, M.J.: Direct search algorithms for optimization calculations. Acta Numer. 7, 287–336 (1998) · Zbl 0911.65050 · doi:10.1017/S0962492900002841 |
| [3] | Torczon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7(1), 1–25 (1997) · Zbl 0884.65053 · doi:10.1137/S1052623493250780 |
| [4] | Preux, P., Talbi, E.G.: Towards hybrid evolutionary algorithms. Int. Trans. Oper. Res. 6, 557–570 (1999) · doi:10.1111/j.1475-3995.1999.tb00173.x |
| [5] | Garcia-Palomares, U.M., Gonzales-Castaño, F.J., Burguillo-Rial, J.C.: A combined global & local search (CGLS) approach to global optimization. J. Glob. Optim. 34, 409–426 (2006) · Zbl 1149.90426 · doi:10.1007/s10898-005-3249-2 |
| [6] | Schmidt, H., Thierauf, G.: A combined heuristic optimization technique. Adv. Eng. Software 36, 11–19 (2005) · Zbl 1062.90077 · doi:10.1016/j.advengsoft.2003.12.001 |
| [7] | Ho, S.L., Yang, S., Ni, G., Mochado, J.M.: A modified ant colony optimization algorithm medeled on tabu-search methods. IEEE Trans. Magn. 42(4), 1195–1198 (2006) · doi:10.1109/TMAG.2006.871425 |
| [8] | Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 1277–1292 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [9] | Storn, R., Price, K.: Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. J. Glob. Optim. 11, 341–359 (1997) · Zbl 0888.90135 · doi:10.1023/A:1008202821328 |
| [10] | Ochotta, E., Mukherjee, T., Rutenbar, R., Carley, L.: Practical Synthesis of High-Performance Analog Circuits. Kluwer Academic, Norwell, MA (1998) · Zbl 0928.68114 |
| [11] | Harlani, R., Rutenbar, R., Carley, L.: OASYS: a framework for analog circuit synthesis. IEEE Trans. Comp. Aided Des. 8(12), 1247–1266 (1989) · doi:10.1109/43.44506 |
| [12] | Gielen, G. et al.: Analog circuit design optimization based on symbolic simulation and simulated annealing. IEEE J. Solid-State Circuits 25, 707–713 (1990) · doi:10.1109/4.102664 |
| [13] | Fernández, F.V., Guerra, O., Rodríguez-García, J.D., Rodríguez-Vázquez, A.: Symbolic analysis of large analog integrated circuits: the numerical reference generation problem. IEEE Trans. Circuits Systems II: Analog Digital Signal Process. 45(10), 1351–1361 (1998) · doi:10.1109/82.728848 |
| [14] | Gielen, G., Wambacq, P., Sansen, W.: Symbolic analysis methods and applications for analog circuits: A tutorial overview. Proc. IEEE 82, 287–304 (1990) · doi:10.1109/5.265355 |
| [15] | Shi, C.J., Tan, X.: Symbolic analysis of large analog circuits with determinant decision diagrams. In: Proceedings, ACM/IEEE ICCAD, pp. 366–373 (1997) |
| [16] | Yu, Q., Sechen, C.: A unified approach to the approximate symbolic analysis of large analog integrated circuits. IEEE Trans. Circuits Syst. 43, 656–669 (1996) · doi:10.1109/81.526681 |
| [17] | Daems, W., Gielen, G., Sansen, W.: Circuit complexity reduction for symbolic analysis of analog integrated circuits. In: Proceedings, ACM/IEEE, Design Automation Conf., 958–963, Jun. 1999 |
| [18] | Wambacq, P., Vanthienen, J., Gielen, G., Sansen, W.: A design tool for weakly nonlinear analog integrated circuits with multiple inputs (mixers, multipliers). In: Proceedings, IEEE CICC, San Diego, CA, pp. 5.1.1–5.1.4, May 1991 |
| [19] | Ochotta, E., Rutenbar, R., Carley, L.: Synthesis of high-performance analog circuits and ASTRX/OBLX. IEEE Trans. Comput. Aided Des. 15, 237–294 (1996) · doi:10.1109/43.489099 |
| [20] | Alpaydın, G., Balkır, S., Dündar, G.: An evolutionary approach to automatic synthesis of high-performance analog integrated circuits. IEEE Trans. Evol. Comput. 7(3), 240–252 (2003) · doi:10.1109/TEVC.2003.808914 |
| [21] | Gielen, G.G.E., Rutenbar, R.A.: Computer-aided design of analog and mixed-signal integrated circuits. Proc. IEEE 88(12), 1825–1849 (2000) · doi:10.1109/5.899053 |
| [22] | Gielen, G.G.E.: CAD tools for embedded analogue circuits in mixedsignal integrated systems on chip. Proc. IEEE Comput. Digit. Tech. 152(3), 317–332 (2005) · doi:10.1049/ip-cdt:20045116 |
| [23] | Rutenbar, R.A., Gielen, G.G.E., Roychowdhury, J.: Hierarchical modeling, optimization, and synthesis for system-level analog and RF designs. Proc. IEEE 95(3), 640–669 (2007) · doi:10.1109/JPROC.2006.889371 |
| [24] | Phelps, R., Krasnicki, M., Rutenbar, R., Carley, R., Hellums, J.: Simulation-based synthesis of analog circuits via stochastic pattern search. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 19(6), 703–717 (2000) · doi:10.1109/43.848091 |
| [25] | SPICE OPUS circuit simulator homepage: http://www.fe.uni-lj.si/spice/ . Accessed 1 Dec. 2005 (2005) |
| [26] | Burmen, Á., Strle, D., Bratkovič, F., Puhan, J., Fajfar, I., Tuma, T.: Automated robust design and optimization of integrated circuits by means of penalty functions. AEU-Int. J. Electron. C. 57(1), 47–56 (2003) · doi:10.1078/1434-8411-54100139 |
| [27] | Antreich, K.J., Graeb, H.E., Wieser, C.U.: Circuit analysis and optimization driven by worst-case distances. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 13(1), 703–717 (1994) |
| [28] | Schwencker, R., Schenkel, F., Pronath, M., Graeb, H.: Analog circuit sizing using adaptive worst-case parameter sets. In: Proceedings, Design, Automation and Test (2002) |
| [29] | Yang, R.L.: Convergence of the simulated annealing algorithm for continuous global optimization. J. Optim. Theor. Appl. 104(3), 691–716 (2000) · Zbl 1060.90085 · doi:10.1023/A:1004697811243 |
| [30] | Bilbro, G.L.: Fast stochastic global optimization. IEEE Trans. Syst. Man. Cybern. 24(4), 684–689 (1994) · Zbl 1371.90093 · doi:10.1109/21.286389 |
| [31] | Thompson, D.R., Bilbro, G.L.: Sample-sort simulated annealing. IEEE Trans. Syst. Man. Cybern. B Cybern. 35(3), 625–632 (2005) · doi:10.1109/TSMCB.2005.843972 |
| [32] | Puhan, J., Burmen, Á., Tuma, T.: Analogue integrated circuit sizing with several optimization runs using heuristics for setting initial points. Can. J. Electr. Comput. Eng. 28(3–4), 105–111 (2003) · doi:10.1109/CJECE.2003.1425097 |
| [33] | Puhan, J., Tuma, T., Fajfar, I.: Optimisation methods in SPICE, a comparison. In: Proceedings, European Conference on Circuit Theory and Design. Stresa, Italy, Vol. 2, pp. 1279–1282 (1999) |
| [34] | Yao, X., Liu, Y., Lin, G.: Evolutionary programming made faster. IEEE Trans. Evol. Comput. 3(2), 82–102 (1999) · doi:10.1109/4235.771163 |
| [35] | Birbil, Ş\.I., Fang, S.C., Sheu, C.L.: On the convergence of a population-based global optimization algorithm. J. Glob. Optim. 30, 301–318 (2004) · Zbl 1066.90086 · doi:10.1007/s10898-004-8270-3 |
| [36] | He, J., Yu, X.: Conditions for the convergence of evolutionary algorithms. J. Syst. Architect. 47, 601–612 (2001) · doi:10.1016/S1383-7621(01)00018-2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
