[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A genetic algorithm based augmented Lagrangian method for constrained optimization

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Among the penalty based approaches for constrained optimization, augmented Lagrangian (AL) methods are better in at least three ways: (i) they have theoretical convergence properties, (ii) they distort the original objective function minimally, thereby providing a better function landscape for search, and (iii) they can result in computing optimal Lagrange multiplier for each constraint as a by-product. Instead of keeping a constant penalty parameter throughout the optimization process, these algorithms update the parameters (called multipliers) adaptively so that the corresponding penalized function dynamically changes its optimum from the unconstrained minimum point to the constrained minimum point with iterations. However, the flip side of these algorithms is that the overall algorithm requires a serial application of a number of unconstrained optimization tasks, a process that is usually time-consuming and tend to be computationally expensive. In this paper, we devise a genetic algorithm based parameter update strategy to a particular AL method. The proposed strategy updates critical parameters in an adaptive manner based on population statistics. Occasionally, a classical optimization method is used to improve the GA-obtained solution, thereby providing the resulting hybrid procedure its theoretical convergence property. The GAAL method is applied to a number of constrained test problems taken from the evolutionary algorithms (EAs) literature. The number of function evaluations required by GAAL in most problems is found to be smaller than that needed by a number of existing evolutionary based constraint handling methods. GAAL method is found to be accurate, computationally fast, and reliable over multiple runs. Besides solving the problems, the proposed GAAL method is also able to find the optimal Lagrange multiplier associated with each constraint for the test problems as an added benefit—a matter that is important for a sensitivity analysis of the obtained optimized solution, but has not yet been paid adequate attention in the past evolutionary constrained optimization studies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

References

  1. Adeli, H., Cheng, N.T.: Augmented Lagrangian genetic algorithm for structural optimization. J. Aerosp. Eng. 7(1), 104–118 (1994)

    Article  Google Scholar 

  2. Adeli, H., Cheng, N.T.: Concurrent genetic algorithms for optimization of large structures. J. Aerosp. Eng. 7(3), 276–296 (1994)

    Article  Google Scholar 

  3. Adeli, H., Kumar, S.: Distributed genetic algorithm for structural optimization. J. Aerosp. Eng. 8(3), 156–163 (1995)

    Article  Google Scholar 

  4. Amstutz, S.: Augmented Lagrangian for cone constrained topology optimization. Comput. Optim. Appl. 49(1), 101–122 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  5. Barbosa, H.J.C.: A genetic algorithm for min-max problems. In: Proceedings of the First International Conference on Evolutionary Computation and Its Application (EvCA’96), pp. 99–109 (1996)

    Google Scholar 

  6. Barbosa, H.J.C., Lemonge, A.C.C.: An adaptive penalty method for genetic algorithms in constrained optimization problems. In: Frontiers in Evolutionary Robotics, pp. 9–34. I-Tech Education and Publishing, Vienna (2008)

    Google Scholar 

  7. Birgin, E.G., Martínez, J.M.: Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization. Comput. Optim. Appl. (2011). doi:10.1007/s10589-011-9396-0

    Google Scholar 

  8. Brest, J.: Constrained real-parameter optimization with ε-self-adaptive differential evolution. In: Constraint-Handling in Evolutionary Optimization, vol. 198, pp. 73–93. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  9. Coello, C.A.C.: Treating objectives as constraints for single objective optimization. Eng. Optim. 32(3), 275–308 (2000)

    Article  Google Scholar 

  10. Deb, K.: Optimal design of a welded beam structure via genetic algorithms. AIAA J. 29(11), 2013–2015 (1991)

    Article  Google Scholar 

  11. Deb, K.: Optimization for Engineering Design: Algorithms and Examples. Prentice-Hall, New Delhi (1995)

    Google Scholar 

  12. Deb, K.: An efficient constraint handling method for genetic algorithms. Comput. Methods Appl. Mech. Eng. 186(2–4), 311–338 (2000)

    Article  MATH  Google Scholar 

  13. Deb, K., Agrawal, R.B.: Simulated binary crossover for continuous search space. Complex Syst. 9(2), 115–148 (1995)

    MathSciNet  MATH  Google Scholar 

  14. Deb, K., Agrawal, S.: A niched-penalty approach for constraint handling in genetic algorithms. In: Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA-99), pp. 235–243. Springer, Berlin (1999)

    Chapter  Google Scholar 

  15. Deb, K., Datta, R.: A fast and accurate solution of constrained optimization problems using a hybrid bi-objective and penalty function approach. In: Proceedings of the IEEE World Congress on Computational Intelligence (WCCI-2010), pp. 165–172 (2010)

    Google Scholar 

  16. Ebenau, C., Rottschäfer, J., Thierauf, G.: An advanced evolutionary strategy with an adaptive penalty function for mixed-discrete structural optimisation. Adv. Eng. Softw. 36(1), 29–38 (2005)

    Article  MATH  Google Scholar 

  17. Fletcher, R.: An ideal penalty function for constraint optimization. J. Inst. Math. Appl. 15(3), 319–342 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  19. Homaifar, A., Lai, S.H.V., Qi, X.: Constrained optimization via genetic algorithms. Simulation 62(4), 242–254 (1994)

    Article  Google Scholar 

  20. Jansen, P.W., Perez, R.E.: Constrained structural design optimization via a parallel augmented Lagrangian particle swarm optimization approach. Comput. Struct. 89, 1352–1366 (2011)

    Article  Google Scholar 

  21. Joines, J.A., Houck, C.R.: On the use of nonstationary penalty functions to solve nonlinear constrained optimization problems with GAs. In: Proceedings of the International Conference on Evolutionary Computation, pp. 579–584 (1994)

    Google Scholar 

  22. Kim, J.H., Myung, H.: Evolutionary programming techniques for constrained optimization problems. IEEE Trans. Evol. Comput. 1(2), 129–140 (1997)

    Article  Google Scholar 

  23. Kowalewski, A., Lasiecka, I., Sokolowski, J.: Sensitivity analysis of hyperbolic optimal control problems. Comput. Optim. Appl. (2011). doi:10.1007/s10589-010-9375-x

    Google Scholar 

  24. Liang, J.J., Runarsson, T.P., Mezura-Montes, E., Clerc, M., Suganthan, P.N., Coello, C.A.C., Deb, K.: Special session on constrained real-parameter optimization. http://www.ntu.edu.sg/home/epnsugan/ (2006)

  25. Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin (1992)

    MATH  Google Scholar 

  26. Michalewicz, Z., Schoenauer, M.: Evolutionary algorithms for constrained parameter optimization problems. Evol. Comput. J. 4(1), 1–32 (1996)

    Article  Google Scholar 

  27. Nema, S., Goulermas, J.Y., Sparrow, G., Helman, P.: A hybrid cooperative search algorithm for constrained optimization. Struct. Multidiscip. Optim. 43, 107–119 (2011)

    Article  MathSciNet  Google Scholar 

  28. Pillo, G.D., Liuzzi, G., Lucidi, S., Palagi, L.: A truncated newton method in an augmented Lagrangian framework for nonlinear programming. Comput. Optim. Appl. 45(2), 311–352 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  29. Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Optimization, pp. 283–298. Academic Press, New York (1969)

    Google Scholar 

  30. Rao, S.S.: Genetic algorithmic approach for multiobjective optimization of structures. In: Proceedings of the ASME Annual Winter Meeting on Structures and Controls Optimization, vol. 38, pp. 29–38 (1993)

    Google Scholar 

  31. Reklaitis, G.V., Ravindran, A., Ragsdell, K.M.: Engineering Optimization Methods and Applications. Wiley, New York (1983)

    Google Scholar 

  32. Rocha, A.M.A.C., Martins, T.F.M.C., Fernandes, E.M.G.P.: An augmented Lagrangian fish swarm based method for global optimization. J. Comput. Appl. Math. 235, 4611–4620 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  33. Rockafellar, R.T.: A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5, 552–562 (1973)

    Article  MathSciNet  Google Scholar 

  34. Rockafellar, R.T.: The multiplier method of hestenes and powell applied to convex programming. J. Optim. Theory Appl. 12(6), 552–562 (1973)

    Article  Google Scholar 

  35. Sarma, K.C., Adeli, H.: Fuzzy genetic algorithm for optimization of steel structures. J. Struct. Eng. 126(5), 596–604 (2000)

    Article  Google Scholar 

  36. Schluter, M., Gerdts, M.: The oracle penalty method. J. Glob. Optim. 47, 293–325 (2010)

    Article  MathSciNet  Google Scholar 

  37. Schwefel, H.P.: Collective intelligence in evolving systems. In: Ecodynamics—Contributions to Theoretical Ecology, pp. 95–100. Springer, Berlin (1987)

    Google Scholar 

  38. Sedlaczek, K., Eberhard, P.: Using augmented Lagrangian particle swarm optimization for constrained problems in engineering. Struct. Multidiscip. Optim. 32, 277–286 (2006)

    Article  Google Scholar 

  39. Srivastava, S., Deb, K.: A genetic algorithm based augmented Lagrangian method for computationally fast constraint optimization. In: Proceedings of the First International Conference on Swarm, Evolutionary and Memetic Computing (SEMCCO 2010), pp. 182–189. Springer, Berlin (2010)

    Google Scholar 

  40. Tahk, M.J., Sun, B.C.: Coevolutionary augmented Lagrangian methods for constrained optimization. IEEE Trans. Evol. Comput. 4(2), 114–124 (2000)

    Article  Google Scholar 

  41. Takahama, T., Sakai, S.: Constrained optimization by the ϵ-constrained differential evolution with gradient-based mutation and feasible elites. In: 2006 IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE Press, Piscatway (2006)

    Google Scholar 

  42. Tessema, B., Yen, G.G.: An adaptive penalty formulation for constrained evolutionary optimization. IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum. 39(3), 565–578 (2009)

    Article  Google Scholar 

  43. Tulshyan, R., Arora, R., Deb, K., Dutta, J.: Investigating ea solutions for approximate KKT conditions for smooth problems. In: Proceedings of Genetic and Evolutionary Algorithms Conference (GECCO-2010), pp. 689–696 (2010)

    Google Scholar 

  44. Volkwein, S.: Application of the augmented Lagrangian-SQP method to optimal control problems for the stationary burgers equation. Comput. Optim. Appl. 16(1), 57–81 (2010)

    Article  MathSciNet  Google Scholar 

  45. Zavala, A.E.M., Aguirre, A.H., Diharce, E.R.V.: Continuous constrained optimization with dynamic tolerance using the COPSO algorithm. In: Constraint Handling in Evolutionary Optimization, pp. 1–24. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  46. Zhou, Y., Li, Y., He, J., Kang, L.: Multi-objective and MGG evolutionary algorithm for constrained optimization. In: Proceedings of Congress on Evolutionary Computation, pp. 1–5 (2003)

    Google Scholar 

  47. Zhou, Y.Y., Yang, X.Q.: Augmented Lagrangian functions for constrained optimization problems. J. Glob. Optim. 52(1), 95–108 (2010)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This study is supported by Academy of Finland under grant 133387.

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, Indian Institute of Technology Kanpur, Kanpur, UP, 208016, India

    Kalyanmoy Deb & Soumil Srivastava

  2. Department of Information and Service Economy, Aalto University, Helsinki, Finland

    Kalyanmoy Deb

  3. Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI, 48824, USA

    Kalyanmoy Deb

Authors
  1. Kalyanmoy Deb
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Soumil Srivastava
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kalyanmoy Deb.

Appendix: Problem formulations

Appendix: Problem formulations

These problems are taken from [24].

1.1 A.1 Problem g01

The problem is given as follows:

$$\everymath{\displaystyle}\begin{array}{l@{\quad}l}\mbox{min.} & f(\mathbf{x})=5\sum_{i=1}^4 x_i-5\sum_{i=1}^4 x_i^2 + \sum_{i=5}^{13} x_i, \\[14pt]\mbox{s.t.} & g_1(\mathbf{x}) \equiv2x_1+2x_2+x_{10} + x_{11}-10\le 0,\\[3pt]&g_2(\mathbf{x}) \equiv2x_1+2x_3+x_{10}+x_{12}-10\le0,\\[3pt]&g_3(\mathbf{x}) \equiv2x_2+2x_3+x_{11}+x_{12}-10\le0,\\ [3pt]&g_4(\mathbf{x}) \equiv -8x_1+x_{10}\le0,\\ [3pt]&g_5(\mathbf{x}) \equiv -8x_2+x_{11}\le0,\\ [3pt]&g_6(\mathbf{x}) \equiv -8x_3 + x_{12}\le0,\\ [3pt]&g_7(\mathbf{x}) \equiv -2x_4-x_5+x_{10}\le0,\\ [3pt]&g_8(\mathbf{x}) \equiv -2x_6-x_7 + x_{11}\le0,\\[3pt]&g_9(\mathbf{x}) \equiv -2x_8-x_9+x_{12}\le0,\end{array}$$
(10)

where 0≤x i ≤1 for i=1,2,…,9, 0≤x i ≤100 for i=10,11,12, and 0≤x 13≤1.

1.2 A.2 Problem g02

The problem is given as follows:

$$\everymath{\displaystyle}\begin{array}{l@{\quad}l}\mbox{min.} & f(\mathbf{x})={-}\!\left|\frac{\sum_{i=1}^{20}\cos^4(x_i)-2\prod _{i=1}^{20}\cos^2(x_i)}{\sqrt{\sum_{i=1}^{20}ix_i^2}}\right|, \\[20pt]\mbox{s.t.} & g_1(\mathbf{x}) \equiv0.75-\prod_{i=1}^{20}x_i\le0, \\[14pt]& g_2(\mathbf{x}) \equiv\sum_{i=1}^{20}x_i-150\le0, \\[14pt]& \quad 0 \leq x_i \leq10, \quad i=1,2,\ldots,20.\end{array}$$
(11)

1.3 A.3 Problem g04

The problem is given as follows:

(12)

1.4 A.4 Problem g06

The problem is given as follows:

$$\everymath{\displaystyle}\begin{array}{l@{\quad}l}\mbox{min.} & f(\mathbf{x}) = (x_1 - 10)^3 + (x_2 - 20)^3, \\[3pt]\mbox{s.t.} & g_1(\mathbf{x}) \equiv-(x_1-5)^2-(x_2-5)^2 + 100\le 0, \\[3pt]& g_2(\mathbf{x}) \equiv(x_1 - 6)^2 + (x_2 - 5)^2 - 82.81 \le0, \\[3pt]&\quad 13 \le x_1 \le100, \quad 0 \le x_2 \le100.\end{array}$$
(13)

1.5 A.5 Problem g07

The problem is given as follows:

(14)

1.6 A.6 Problem g08

The problem is given as follows:

$$\everymath{\displaystyle}\begin{array}{l@{\quad}l}\mbox{min.} & f(\mathbf{x})= -\frac{\sin^3(2\pi x_1)\sin(2\pi x_2)}{x_1^3(x_1+x_2)}, \\[3pt]\mbox{s.t.} & g_1(\mathbf{x}) \equiv x_1^2-x_2+1\le0, \\[3pt]& g_2(\mathbf{x}) \equiv1-x_1+(x_2-4)^2\leq0, \\[3pt]& \quad 0\le x_i \le10, \quad i=1,2.\end{array}$$
(15)

1.7 A.7 Problem g09

The problem is given as follows:

(16)

1.8 A.8 Problem g10

The problem is given as follows:

(17)

1.9 A.9 Problem g12

The problem is given as follows:

(18)

The parameters p i , q j and r k take one of nine interger values in [1, 9]. Thus, the minimum value of 93 or 243 terms within brackets is used as the constraint value. As long as, a point lies inside any of the 243 spheres, the point is feasible.

1.10 A.10 Problem g18

The problem is given as follows:

(19)

1.11 A.11 Problem g24

The problem is given as follows:

$$\everymath{\displaystyle}\begin{array}{l@{\quad}l}\mbox{min.} & f(\mathbf{x}) =-x_1 - x_2, \\[3pt]\mbox{s.t.} & g_1(\mathbf{x}) \equiv-2x^4_1 + 8x^3_1-8x^2_1+x_2-2\leq0, \\[3pt]& g_2(\mathbf{x}) \equiv -4x^4_1 + 32x^3_1 - 88x^2_1 + 96x_1 + x2 - 36 \leq0, \\[3pt]& \quad 0 \leq x_1 \leq3, \quad0 \leq x_2 \leq4.\end{array}$$
(20)

1.12 A.12 Problem weld

The problem is given as follows (x=(h,l,t,b)T) [10, 31]:

$$\everymath{\displaystyle}\begin{array}{l@{\quad}l}\mbox{min.} & f_1(\mathbf{x})=1.10471h^2l+0.04811tb(14.0+l), \\[3pt]\mbox{s.t.} & g_1(\mathbf{x})\equiv13{,}600-\tau(\mathbf{x}) \geq0,\\[3pt]& g_2(\mathbf{x})\equiv30{,}000-\sigma(\mathbf{x}) \geq0, \\[3pt]& g_3(\mathbf{x})\equiv b-h \geq0, \\[3pt]& g_4(\mathbf{x})\equiv P_c(\mathbf{x})-6{,}000 \geq0, \\[3pt]& g_5(\mathbf{x})\equiv0.25-\delta(\mathbf{x}) \geq0, \\[3pt]&\quad 0.125 \leq (h, b) \leq5, \quad 0.1 \leq (l, t) \leq10,\end{array} $$
(21)

where,

Rights and permissions

Reprints and permissions

About this article

Cite this article

Deb, K., Srivastava, S. A genetic algorithm based augmented Lagrangian method for constrained optimization. Comput Optim Appl 53, 869–902 (2012). https://doi.org/10.1007/s10589-012-9468-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9468-9

Keywords

Search

Navigation