Global optimization by continuous grasp. (English) Zbl 1149.90119
Summary: We introduce a novel global optimization method called Continuous GRASP (C-GRASP) which extends Feo and Resende’s greedy randomized adaptive search procedure (GRASP) from the domain of discrete optimization to that of continuous global optimization. This stochastic local search method is simple to implement, is widely applicable, and does not make use of derivative information, thus making it a well-suited approach for solving global optimization problems. We illustrate the effectiveness of the procedure on a set of standard test problems as well as two hard global optimization problems.
MSC:
| 90C26 | Nonconvex programming, global optimization |
Software:
GRASPReferences:
| [1] | Anderssen, R.S.: Global optimization. In: Anderssen, R.S., Jennings, L.S., Ryan, D.M. (eds.) Optimization, pp. 26–48. Queensland University Press, (1972) · Zbl 0335.90047 |
| [2] | Barhen J., Protopopescu V., Reister D. (1997). Trust: a deterministic algorithm for global optimization. Science, 276:1094–1097 · Zbl 1226.90073 · doi:10.1126/science.276.5315.1094 |
| [3] | Butler R.A.R., Slaminka E.E. (1992). An evaluation of the sniffer global optimization algorithm using standard test functions. J. Comput. Phys. 99(1):28–32 · Zbl 0747.65042 · doi:10.1016/0021-9991(92)90271-Y |
| [4] | Chen L., Zhou T., Tang Y. (2005). Protein structure alignment by deterministic annealing. Bioinformatics 21(1):51–62 · doi:10.1093/bioinformatics/bth467 |
| [5] | Cvijović D., Klinowski J. (1995). Taboo search: an approach to the multiple minima problem. Science 267:664–666 · Zbl 1226.90101 |
| [6] | Feo T.A., Resende M.G.C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8:67–71 · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3 |
| [7] | Feo T.A., Resende M.G.C. (1995). Greedy randomized adaptive search procedures. J. Global. Optim. 6:109–133 · Zbl 0822.90110 · doi:10.1007/BF01096763 |
| [8] | Festa P., Resende M.G.C. (2002). GRASP: an annotated bibliography. In: Ribeiro C.C., Hansen P., (eds) Essays and Surveys in Metaheuristics, pp. 325–367. Kluwer, Dordrecht · Zbl 1017.90001 |
| [9] | Floudas, C.A., Pardalos P.M.: A collection of test problems for constrained global optimization algorithms. In: Goods, G., Hartmanis, J., (eds.) Lecture Notes in Computer Science, vol. 455. Springer Berlin Heidelberg New York (1990) · Zbl 0718.90054 |
| [10] | Floudas C.A., Pardalos P.M., Adjiman C., Esposito W., Gumus Z., Harding S., Klepeis J., Meyer C., Schweiger C. (1999). Handbook of Test Problems in Local and Global Optimization. Kluwer, Dordrecht · Zbl 0943.90001 |
| [11] | Granvilliers L., Benhamou F. (2001). Progress in the solving of a circuit design problem. J. Global Optim. 20(2):155–168 · Zbl 0998.65051 · doi:10.1023/A:1011266226870 |
| [12] | Hedar A.R., Fukushima M. (2002). Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optim. Methods Softw. 17:891–912 · Zbl 1065.90081 · doi:10.1080/1055678021000030084 |
| [13] | Hedar A.R., Fukushima M. (2003). Minimizing multimodal functions by simplex coding genetic algorithms. Optim. Methods Softw. 18:265–282 · Zbl 1048.90168 |
| [14] | Hedar A.R., Fukushima M. (2006). Tabu search directed by direct search methods for nonlinear global optimization. Eur. J. Oper. Res. 170:329–349 · Zbl 1093.90091 · doi:10.1016/j.ejor.2004.05.033 |
| [15] | Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd Revised Edition. Springer Berlin Heidelberg New York (1993) |
| [16] | Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Dordrecht 2nd edn. (2000) · Zbl 0966.90073 |
| [17] | Kearfott R.B. (1987). Some tests of generalized bisection. ACM Trans. Math. Softw. 13(3):197–220 · Zbl 0632.65056 · doi:10.1145/29380.29862 |
| [18] | Koon, G.H., Sebald, A.V.: Some interesting test functions for evaluating evolutionary programming strategies. In Proceedings of the Fourth Annual Conference on Evolutionary Programming, pp. 479–499 (1995) |
| [19] | Krokhmal, P., Murphey, R., Pardalos, P.M., Uryasev, S., Zrazhevsky, G.: Robust decision making: addressing uncertainties in distributions. In: Butenko, S., Murphey, R., Pardalos, P.M.: (eds.) Cooperative Control: Models, Applications, and Algorithms, pp. 165–185. Kluwer Dordrecht (2003) |
| [20] | Krokhmal, P., Murphey, R., Pardalos, P.M., Uryasev, S.: Use of conditional value-at-risk in stochastic programs with poorly defined distributions. In: Butenko, S., Murphey, R., Pardalos, P.M., (eds.) Recent Developments in Cooperative Control and Optimization, pp. 225–243. Kluwer Dordrecht (2004) |
| [21] | Meintjes K., Morgan A.P. (1987). A methodology for solving chemical equilibrium systems. Appl. Math. Comput. 22:333–361 · Zbl 0616.65057 · doi:10.1016/0096-3003(87)90076-2 |
| [22] | Meintjes K., Morgan A.P. (1989). Element variables and the solution of complex chemical equilibrium problems. Combust. Sci. Technol. 68:35–48 · doi:10.1080/00102208908924068 |
| [23] | Meintjes K., Morgan A.P. (1990). Chemical equilibrium systems as numerical test problems. ACM Trans. Math. Softw. 16(2):143–151 · Zbl 0900.65153 · doi:10.1145/78928.78930 |
| [24] | Pardalos P.M., Resende M.G.C. (eds) (2002). Handbook of Applied Optimization. Oxford University Press, New York · Zbl 0996.90001 |
| [25] | Park S., Miller K. (1988). Random number generators: good ones are hard to find. Commun ACM 31:1192–1201 · doi:10.1145/63039.63042 |
| [26] | Pham, D.T., Karaboga, D.: Intelligent Optimization Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing, and Neural Networks. Springer Berlin Heidelberg New York (2000) · Zbl 0986.90001 |
| [27] | Ratschek H., Rokne J. (1993). Experiments using interval analysis for solving a circuit design problem. J. Global Optim. 3(3):501–518 · Zbl 0793.90077 · doi:10.1007/BF01096417 |
| [28] | Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 219–249. Kluwer Dordrecht (2003) · Zbl 1102.90384 |
| [29] | Siarry P., Berthiau G., Durbin F., Haussy J. (1997). Enhanced simulated annealing for globally minimizing functions of many continuous variables. ACM Trans. Math. Softw. 23(2):209–228 · Zbl 0887.65067 · doi:10.1145/264029.264043 |
| [30] | Trafalis T.B., Kasap S. (2002). A novel metaheuristics approach for continuous global optimization. J. Global Optim. 23:171–190 · Zbl 1175.90320 · doi:10.1023/A:1015564423757 |
| [31] | Tsai L.W., Morgan A.P. (1985). Solving the kinematics of the most general six- and five-degree-of-freedom manipulators by continuation methods. J. Mech. Transm. Autom. Des. 107:189–200 · doi:10.1115/1.3258708 |
| [32] | Vanderbilt D., Louie S.G. (1984). A Monte Carlo simulated annealing approach to optimization over continuous variables. J. Comput. Phys. 56:259–271 · Zbl 0551.65045 · doi:10.1016/0021-9991(84)90095-0 |
| [33] | Wales D.J., Scheraga H.A. (1999). Global optimization of clusters, crystals, and biomolecules. Science, 285:1368–1372 · doi:10.1126/science.285.5432.1368 |
| [34] | Yang, J.-M., Kao, C.Y.: A combined evolutionary algorithm for real parameters optimization. In: Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 732–737, (1996) |
| [35] | Zabarankin, M., Uryasev, S., Murphey, R.: Aircraft routing under the risk of detection. Naval Res. Logist. (2006), accepted for publication · Zbl 1141.90592 |
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.
