Investigating a hybrid simulated annealing and local search algorithm for constrained optimization. (English) Zbl 1175.90377
Summary: Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.
MSC:
| 90C30 | Nonlinear programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
constrained optimization; global and local search; simulated annealing; feasible sequential quadratic programmingReferences:
| [1] | Bennage, W. A.; Dhingra, A. K., Single and multi-objective structural optimization in discrete continuous variables using simulated annealing, International Journal of Numerical Methods and Engineering, 38, 2753-2773 (1995) · Zbl 0855.73052 |
| [2] | Carlson, S., Shonkwiler, R., Babar, S., Aral, M. 1998. Annealing a genetic algorithm over constraints. SMC 98 Conference. Available from: <http://www.math.gatech.edu/shenk/body.html; Carlson, S., Shonkwiler, R., Babar, S., Aral, M. 1998. Annealing a genetic algorithm over constraints. SMC 98 Conference. Available from: <http://www.math.gatech.edu/shenk/body.html |
| [3] | Coello, C. A.C., Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art, Computational Methods in Applied Mechanics and Engineering, 191, 1245-1287 (2002) · Zbl 1026.74056 |
| [4] | Coconut, Coconut Test Problems on Constrained Optimization Problems - Library2. Available from: <www.mat.univie.ac.at/ neum/glopt/coconut/; Coconut, Coconut Test Problems on Constrained Optimization Problems - Library2. Available from: <www.mat.univie.ac.at/ neum/glopt/coconut/ |
| [5] | Corana, A.; Marchesi, M.; Marini, C.; Ridella, S., Minimizing multimodal functions of continuous variables with the simulated annealing algorithm, ACM Transactions of Mathamatical Software, 13, 262-279 (1987) · Zbl 0632.65075 |
| [6] | Deb, K., An efficient constraint handling method for genetic algorithms, Computational Methods in Applied Mechanics and Engineering, 186, 311-338 (2000) · Zbl 1028.90533 |
| [7] | Dembo, R. S., A set of geometric programming test problems and their solutions, Mathematical Programming, 10, 192-213 (1976) · Zbl 0349.90066 |
| [8] | Dekkers, A.; Aarts, E., Global optimization and simulated annealing, Mathematical Programming, 50, 367-393 (1991) · Zbl 0753.90060 |
| [9] | Epperly, T.G., 1995. Global optimization of nonconvex nonlinear programs using parallel branch and bound, Ph.D dissertation, University of Wisconsin-Madison.; Epperly, T.G., 1995. Global optimization of nonconvex nonlinear programs using parallel branch and bound, Ph.D dissertation, University of Wisconsin-Madison. |
| [10] | Floudas, C. A.; Pardalos, P. M., A collection of Test Problems for Constrained Global Optimization Algorithms, Lecture Notes in Computer Science, vol. 455 (1990), Springer-Verlag · Zbl 0718.90054 |
| [11] | Ingber, L., Adaptive simulated annealing (ASA): Lessons learned, Control and Cybernetics, 25, 33-54 (1996) · Zbl 0860.93035 |
| [12] | Joines, J.; Houck, C., On the use of non-stationary penalty functions to solve non-linear constrained optimization problems with GAs, (Proceedings of the First IEEE International Conference on Evolutionary Computation (1994), IEEE Press), 579-584 |
| [13] | Hansen, P.; Jaumard, B.; Lu, S.-H., An analytical approach to global optimization, Mathematical Programming, 52, 227-254 (1991) · Zbl 0747.90091 |
| [14] | Hedar, A. R.; Fukushima, M., Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization, Optimization Methods and Software, 17, 891-912 (2002) · Zbl 1065.90081 |
| [15] | Hedar, A. R.; Fukushima, M., Heuristic pattern search and its hybridization with simulated annealing for nonlinear global optimization, Optimization Methods and Software, 19, 291-308 (2004) · Zbl 1059.90149 |
| [16] | Hedar, A.R., Fukushima, M., 2005. Derivative-free filter simulated annealing method for constrained continuous global optimization. To appear in the Journal of Global Optimization.; Hedar, A.R., Fukushima, M., 2005. Derivative-free filter simulated annealing method for constrained continuous global optimization. To appear in the Journal of Global Optimization. · Zbl 1133.90421 |
| [17] | Kazarlis, S.; Petridis, V., Varying fitness functions in genetic algorithms: studying the rate of increase in the dynamic penalty terms, (Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (1998), Springer Verlag: Springer Verlag Berlin), 211-220 |
| [18] | Kirkpatrick, A.; Gelatt, C. D.; Vechi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [19] | Lawrence, C.T., Zhou, J.L., Tits, A.L., 1997. User’s Guide for CFSQP version 2.5: A Code for Solving (Large Scale) Constrained Nonlinear (minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints, Institute for Systems Research, University of Maryland, College Park, MD.; Lawrence, C.T., Zhou, J.L., Tits, A.L., 1997. User’s Guide for CFSQP version 2.5: A Code for Solving (Large Scale) Constrained Nonlinear (minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints, Institute for Systems Research, University of Maryland, College Park, MD. |
| [20] | Leite, J. P.B.; Topping, B. H.V., Parallel simulated annealing for structural optimization, Computers and Structures, 73, 545-564 (1999) · Zbl 1049.74748 |
| [21] | Michalewicz, Z., Genetic algorithms, numerical optimization, and constraints, (Proceedings of the Sixth International Conference on Genetic Algorithms (1995), Morgan Kaufmann), 151-158 |
| [22] | Michalewicz, Z.; Attia, N., Evolutionary optimization of constrained problems, (Proceedings of the Third Annual Conference on Evolutionary Programming (1994), World Scientific), 98-108 |
| [23] | Michalewicz, Z.; Nazhiyath, G., GENOCOP III: A Co-evolutionary algorithm for numerical optimization problems with nonlinear constraints, (Proceedings of the Second IEEE International Conference on Evolutionary Computation (1995), IEEE Press), 647-651 |
| [24] | Morales, K.A., Quezada, C.C., 1998. A universal eclectic genetic algorithm for constrained optimization. In: Proceedings 6th European Congress on Intelligent Techniques & Soft Computing, EUFIT’98, pp. 518-522.; Morales, K.A., Quezada, C.C., 1998. A universal eclectic genetic algorithm for constrained optimization. In: Proceedings 6th European Congress on Intelligent Techniques & Soft Computing, EUFIT’98, pp. 518-522. |
| [25] | Myung, H.; Kim, J.-H.; Fogel, D. B., Preliminary Investigations into a Two-State Method of Evolutionary Optimization on Constrained Problems, Evolutionary Programming, 449-463 (1995) |
| [26] | Özdamar, L.; Demirhan, M., Experiments with new stochastic global optimization search techniques, Computers and OR, 27, 841-865 (2000) · Zbl 0967.90086 |
| [27] | Schoenauer, M.; Michalewicz, Z., Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization, Evolutionary Computation, 7, 19-44 (1999) |
| [28] | Shang, Y., Fromherz, M., Crawford, L., 2002. An Efficient Cooperative Solver for Nonlinear Continuous Constraint Problems. In: Int’l Congress of Mathematical Software (ICMS), Beijing, China.; Shang, Y., Fromherz, M., Crawford, L., 2002. An Efficient Cooperative Solver for Nonlinear Continuous Constraint Problems. In: Int’l Congress of Mathematical Software (ICMS), Beijing, China. · Zbl 1011.68184 |
| [29] | Smith, A. E.; Coit, D. W., Constraint handling techniques – penalty functions. Constraint handling techniques – penalty functions, Handbook of Evolutionary Computation (1997), Oxford University Press and Institute of Physics Publishing, Ch. C 5.2 |
| [30] | Swaney, R.E., 1990. Global Solution of algebraic nonlinear programs. AIChE Annual Meeting, Chicago, IL.; Swaney, R.E., 1990. Global Solution of algebraic nonlinear programs. AIChE Annual Meeting, Chicago, IL. |
| [31] | Visweswaran, V.; Floudas, C. A., A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-II. Application of theory and test problems, Computers and Chemical Engineering, 14, 1419-1434 (1990) |
| [32] | Wah, B.W., Wang, T., 1999. Constrained simulated annealing with applications in nonlinear continuous constrained global optimization. In: Proc. 11th IEEE Int’l Conf. on Tools with Artificial Intelligence, pp. 381-388.; Wah, B.W., Wang, T., 1999. Constrained simulated annealing with applications in nonlinear continuous constrained global optimization. In: Proc. 11th IEEE Int’l Conf. on Tools with Artificial Intelligence, pp. 381-388. |
| [33] | Wah, B. W.; Wang, T., Tuning strategies in constrained simulated annealing for nonlinear global optimization, International Journal on Artificial Intelligence Tools, 9, 3-25 (2000) |
| [34] | Wah, B. W.; Chen, Y. X., Optimal anytime constrained simulated annealing for constrained global optimization, (Dechter, R., LNCS, 1894 (2000), Springer-Verlag), 425-440 · Zbl 1044.68807 |
| [35] | Wong, K. P.; Fung, C. C., Simulated-annealing-based economic dispatch algorithm, IEE Proceedings Part C, 140, 509-515 (1993) |
| [36] | Wong, K. P.; Wong, Y. W., Thermal generator scheduling using hybrid genetic/simulated-annealing approach, IEE Proceedings - C Generation Transmission and Distribution, 142, 372-380 (1995) |
| [37] | Wong, K. P.; Wong, S. Y.W., Combined genetic algorithm/simulated annealing/fuzzy set approach to short-term generation scheduling with take-or-pay fuel contract, IEEE Transactions on Power Systems, 11, 112-118 (1996) |
| [38] | Wong, K. P.; Wong, S. Y.W., Hybrid genetic/simulated annealing approach to short-term multiple-fuel-constrained generation scheduling, IEEE Transactions on Power Systems, 12, 776-784 (1997) |
| [39] | Wong, Y. C.; Leung, K. S.; Wong, C. K., Simulated annealing-based algorithms for the studies of the thermoelastic scaling behavior, IEEE Transactions on Systems, Man, and Cybernetics, Part C, 30, 506-516 (2000) |
| [40] | Yeniay, O., Penalty function methods for constrained optimization with genetic algorithms, Mathematical and Computational Applications, 10, 45-56 (2005) |
| [41] | Zhou, J. L.; Tits, A. L., An SQP Algorithm for finely discretized continuous minimax problems and other minimax problems with many objective functions, SIAM Journal on Optimization, 6, 461-487 (1996) · Zbl 0858.49027 |
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.
