American Institute of Mathematical Sciences

Advanced
October  2014, 10(4): 1279-1296. doi: 10.3934/jimo.2014.10.1279

A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization

Qiang Long 1, and  Changzhi Wu 2,

1. 

School of Science, Information, Technology and Engineering, University of Ballarat, Mt Helen, 3350, Victoria
2. 

School of Built Environment, Curtin University, Perth 4845, WA, Australia

Received  August 2012 Revised  October 2013 Published  February 2014

A new global optimization method combining genetic algorithm and Hooke-Jeeves method to solve a class of constrained optimization problems is studied in this paper. We first introduce the quadratic penalty function method and the exact penalty function method to transform the original constrained optimization problem with general equality and inequality constraints into a sequence of optimization problems only with box constraints. Then, the combination of genetic algorithm and Hooke-Jeeves method is applied to solve the transformed optimization problems. Since Hooke-Jeeves method is good at local search, our proposed method dramatically improves the accuracy and convergence rate of genetic algorithm. In view of the derivative-free of Hooke-Jeeves method, our method only requires information of objective function value which not only can overcome the computational difficulties caused by the ill-condition of the square penalty function, but also can handle the non-differentiability by the exact penalty function. Some well-known test problems are investigated. The numerical results show that our proposed method is efficient and robust.
Keywords: Hooke-Jeeves method, Hybrid method, penalty function method, constrained global optimization., genetic algorithm.
Mathematics Subject Classification: Primary: 90c46, 90c90; Secondary: 90c2.
Citation: Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279
References:
[1]

A. M. Bagirov and A. N. Ganjehlou, A quasisecant method for minimizing nonsmooth functions,, Optimization Methods & Software, 25 (2010), 3.  doi: 10.1080/10556780903151565.  Google Scholar

[2]

M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithm (Third Edition),, Wiley Online Library, (2006).  doi: 10.1002/0471787779.  Google Scholar

[3]

S. Ben Hamida and M. Schoenauer, Aschea: New results using adaptive segregational constraint handling,, in Evolutionary Computation, 1 (2002), 884.   Google Scholar

[4]

Z. Cai and Y. Wang, A multiobjective optimization-based evolutionary algorithm for constrained optimization,, Evolutionary Computation, 10 (2006), 658.  doi: 10.1109/TEVC.2006.872344.  Google Scholar

[5]

G. Camp, Inequality-constrained stationary-value problems,, Journal of the Operations Research Society of America, 3 (1955), 548.  doi: 10.1287/opre.3.4.548a.  Google Scholar

[6]

C. Carroll and A. Fiacco, The created response surface technique for optimizing nonlinear restrained systems,, Operations Research, 9 (1961), 169.  doi: 10.1287/opre.9.2.169.  Google Scholar

[7]

R. Chelouah and P. Siarry, A hybrid method combining continuous tabu search and nelder-mead simplex algorithms for the global optimization of multiminima functions,, European Journal of Operational Research, 161 (2005), 636.  doi: 10.1016/j.ejor.2003.08.053.  Google Scholar

[8]

Z. Chen, S. Qiu and Y. Jiao, A penalty-free method for equality constrained optimization,, Journal of Industrial and Management Optimization, 9 (2013), 391.  doi: 10.3934/jimo.2013.9.391.  Google Scholar

[9]

F. E. Curtis and M. L. Overton, A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization,, SIAM Journal on Optimization, 22 (2012), 474.  doi: 10.1137/090780201.  Google Scholar

[10]

N. Durand and J. Alliot, A combined nelder-mead simplex and genetic algorithm,, in Proceedings of the Genetic and Evolutionary Computation Conference GECCO, 99 (1999), 1.   Google Scholar

[11]

R. Fletcher, An ideal penalty function for constrained optimization,, IMA Journal of Applied Mathematics, 15 (1975), 319.  doi: 10.1093/imamat/15.3.319.  Google Scholar

[12]

D. E. Goldberg, Genetic algorithms in search,, optimization, ().   Google Scholar

[13]

H. Greenberg, The generalized penalty-function/surrogate model,, Operations Research, 21 (1973), 162.  doi: 10.1287/opre.21.1.162.  Google Scholar

[14]

A. Hedar, Global optimization methods and codes,, , ().   Google Scholar

[15]

A. Hedar and M. Fukushima, Hybrid simulated annealing and direct search method for nonlinear global optimization,, Department of Applied Mathematics & Physics Kyoto University, 17 (2002), 891.  doi: 10.1080/1055678021000030084.  Google Scholar

[16]

A. Hedar and M. Fukushima, Derivative-free filter simulated annealing method for constrained continuous global optimization,, Journal of Global Optimization, 35 (2006), 521.  doi: 10.1007/s10898-005-3693-z.  Google Scholar

[17]

E. Karas, A. Ribeiro, C. Sagastizábal and M. Solodov, A bundle-filter method for nonsmooth convex constrained optimization,, Mathematical Programming, 116 (2009), 297.  doi: 10.1007/s10107-007-0123-7.  Google Scholar

[18]

N. Karmitsa, A. Bagirov and M. Mäkelä, Comparing different nonsmooth minimization methods and software,, Optimization Methods and Software, 27 (2012), 131.  doi: 10.1080/10556788.2010.526116.  Google Scholar

[19]

S. Koziel and Z. Michalewicz, Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization,, Evolutionary computation, 7 (1999), 19.  doi: 10.1162/evco.1999.7.1.19.  Google Scholar

[20]

O. Kramer, A review of constraint-handling techniques for evolution strategies,, Applied Computational Intelligence and Soft Computing, 2010 ().  doi: 10.1155/2010/185063.  Google Scholar

[21]

Y. Liu, An exterior point linear programming method based on inclusive nornal cone,, Journal of Industrial and Management Optimization, 6 (2010), 825.  doi: 10.3934/jimo.2010.6.825.  Google Scholar

[22]

D. Luenberger, Introduction to linear, and nonlinear programming., ().   Google Scholar

[23]

R. Mallipeddi and P. N. Suganthan, Ensemble of constraint handling techniques,, Evolutionary Computation, 14 (2010), 561.  doi: 10.1109/TEVC.2009.2033582.  Google Scholar

[24]

E. Mezura-Montes and C. C. Coello, A simple multimembered evolution strategy to solve constrained optimization problems,, Evolutionary Computation, 9 (2005), 1.  doi: 10.1109/TEVC.2004.836819.  Google Scholar

[25]

W. Nakamura, Y. Narushima and H. Yabe, Nonlinear conjugrte gradient methods with sufficient descent properties for uniconstrained optimization,, Journal of Industrial and Management Optimization, 9 (2013), 595.  doi: 10.3934/jimo.2013.9.595.  Google Scholar

[26]

W. Pierskalla, Mathematical programming with increasing constraint functions,, Management Science, 15 (): 416.   Google Scholar

[27]

T. P. Runarsson and X. Yao, Stochastic ranking for constrained evolutionary optimization,, Evolutionary Computation, 4 (2000), 284.  doi: 10.1109/4235.873238.  Google Scholar

[28]

J. Vasconcelos, J. Ramirez, R. Takahashi and R. Saldanha, Improvements in genetic algorithms,, Magnetics, 37 (2001), 3414.  doi: 10.1109/20.952626.  Google Scholar

[29]

Y. Wang, Z. Cai, Y. Zhou and Z. Fan, Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint-handling technique,, Structural and Multidisciplinary Optimization, 37 (2009), 395.  doi: 10.1007/s00158-008-0238-3.  Google Scholar

[30]

C. Yu, K. L. Teo, L. Zhang and Y. Bai, A new exact penalty function method for continuous inequality constrained optimization problems,, Journal of Industrial and Management Optimization, 6 (2010).  doi: 10.3934/jimo.2010.6.895.  Google Scholar

[31]

Q. H. Zhiqiang Meng and C. Dang, A penalty function algorithm with objective parameters for nonlinear mathematical programming,, Journal of Industrial and Management Optimization, 5 (2009), 585.  doi: 10.3934/jimo.2009.5.585.  Google Scholar

show all references

References:
[1]

A. M. Bagirov and A. N. Ganjehlou, A quasisecant method for minimizing nonsmooth functions,, Optimization Methods & Software, 25 (2010), 3.  doi: 10.1080/10556780903151565.  Google Scholar

[2]

M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithm (Third Edition),, Wiley Online Library, (2006).  doi: 10.1002/0471787779.  Google Scholar

[3]

S. Ben Hamida and M. Schoenauer, Aschea: New results using adaptive segregational constraint handling,, in Evolutionary Computation, 1 (2002), 884.   Google Scholar

[4]

Z. Cai and Y. Wang, A multiobjective optimization-based evolutionary algorithm for constrained optimization,, Evolutionary Computation, 10 (2006), 658.  doi: 10.1109/TEVC.2006.872344.  Google Scholar

[5]

G. Camp, Inequality-constrained stationary-value problems,, Journal of the Operations Research Society of America, 3 (1955), 548.  doi: 10.1287/opre.3.4.548a.  Google Scholar

[6]

C. Carroll and A. Fiacco, The created response surface technique for optimizing nonlinear restrained systems,, Operations Research, 9 (1961), 169.  doi: 10.1287/opre.9.2.169.  Google Scholar

[7]

R. Chelouah and P. Siarry, A hybrid method combining continuous tabu search and nelder-mead simplex algorithms for the global optimization of multiminima functions,, European Journal of Operational Research, 161 (2005), 636.  doi: 10.1016/j.ejor.2003.08.053.  Google Scholar

[8]

Z. Chen, S. Qiu and Y. Jiao, A penalty-free method for equality constrained optimization,, Journal of Industrial and Management Optimization, 9 (2013), 391.  doi: 10.3934/jimo.2013.9.391.  Google Scholar

[9]

F. E. Curtis and M. L. Overton, A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization,, SIAM Journal on Optimization, 22 (2012), 474.  doi: 10.1137/090780201.  Google Scholar

[10]

N. Durand and J. Alliot, A combined nelder-mead simplex and genetic algorithm,, in Proceedings of the Genetic and Evolutionary Computation Conference GECCO, 99 (1999), 1.   Google Scholar

[11]

R. Fletcher, An ideal penalty function for constrained optimization,, IMA Journal of Applied Mathematics, 15 (1975), 319.  doi: 10.1093/imamat/15.3.319.  Google Scholar

[12]

D. E. Goldberg, Genetic algorithms in search,, optimization, ().   Google Scholar

[13]

H. Greenberg, The generalized penalty-function/surrogate model,, Operations Research, 21 (1973), 162.  doi: 10.1287/opre.21.1.162.  Google Scholar

[14]

A. Hedar, Global optimization methods and codes,, , ().   Google Scholar

[15]

A. Hedar and M. Fukushima, Hybrid simulated annealing and direct search method for nonlinear global optimization,, Department of Applied Mathematics & Physics Kyoto University, 17 (2002), 891.  doi: 10.1080/1055678021000030084.  Google Scholar

[16]

A. Hedar and M. Fukushima, Derivative-free filter simulated annealing method for constrained continuous global optimization,, Journal of Global Optimization, 35 (2006), 521.  doi: 10.1007/s10898-005-3693-z.  Google Scholar

[17]

E. Karas, A. Ribeiro, C. Sagastizábal and M. Solodov, A bundle-filter method for nonsmooth convex constrained optimization,, Mathematical Programming, 116 (2009), 297.  doi: 10.1007/s10107-007-0123-7.  Google Scholar

[18]

N. Karmitsa, A. Bagirov and M. Mäkelä, Comparing different nonsmooth minimization methods and software,, Optimization Methods and Software, 27 (2012), 131.  doi: 10.1080/10556788.2010.526116.  Google Scholar

[19]

S. Koziel and Z. Michalewicz, Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization,, Evolutionary computation, 7 (1999), 19.  doi: 10.1162/evco.1999.7.1.19.  Google Scholar

[20]

O. Kramer, A review of constraint-handling techniques for evolution strategies,, Applied Computational Intelligence and Soft Computing, 2010 ().  doi: 10.1155/2010/185063.  Google Scholar

[21]

Y. Liu, An exterior point linear programming method based on inclusive nornal cone,, Journal of Industrial and Management Optimization, 6 (2010), 825.  doi: 10.3934/jimo.2010.6.825.  Google Scholar

[22]

D. Luenberger, Introduction to linear, and nonlinear programming., ().   Google Scholar

[23]

R. Mallipeddi and P. N. Suganthan, Ensemble of constraint handling techniques,, Evolutionary Computation, 14 (2010), 561.  doi: 10.1109/TEVC.2009.2033582.  Google Scholar

[24]

E. Mezura-Montes and C. C. Coello, A simple multimembered evolution strategy to solve constrained optimization problems,, Evolutionary Computation, 9 (2005), 1.  doi: 10.1109/TEVC.2004.836819.  Google Scholar

[25]

W. Nakamura, Y. Narushima and H. Yabe, Nonlinear conjugrte gradient methods with sufficient descent properties for uniconstrained optimization,, Journal of Industrial and Management Optimization, 9 (2013), 595.  doi: 10.3934/jimo.2013.9.595.  Google Scholar

[26]

W. Pierskalla, Mathematical programming with increasing constraint functions,, Management Science, 15 (): 416.   Google Scholar

[27]

T. P. Runarsson and X. Yao, Stochastic ranking for constrained evolutionary optimization,, Evolutionary Computation, 4 (2000), 284.  doi: 10.1109/4235.873238.  Google Scholar

[28]

J. Vasconcelos, J. Ramirez, R. Takahashi and R. Saldanha, Improvements in genetic algorithms,, Magnetics, 37 (2001), 3414.  doi: 10.1109/20.952626.  Google Scholar

[29]

Y. Wang, Z. Cai, Y. Zhou and Z. Fan, Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint-handling technique,, Structural and Multidisciplinary Optimization, 37 (2009), 395.  doi: 10.1007/s00158-008-0238-3.  Google Scholar

[30]

C. Yu, K. L. Teo, L. Zhang and Y. Bai, A new exact penalty function method for continuous inequality constrained optimization problems,, Journal of Industrial and Management Optimization, 6 (2010).  doi: 10.3934/jimo.2010.6.895.  Google Scholar

[31]

Q. H. Zhiqiang Meng and C. Dang, A penalty function algorithm with objective parameters for nonlinear mathematical programming,, Journal of Industrial and Management Optimization, 5 (2009), 585.  doi: 10.3934/jimo.2009.5.585.  Google Scholar

[1]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[2]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[3]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[4]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[5]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[6]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[7]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[8]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[9]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[10]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[11]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[12]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[13]

Cicely K. Macnamara, Mark A. J. Chaplain. Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences & Engineering, 2017, 14 (1) : 249-262. doi: 10.3934/mbe.2017016
[14]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[15]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[16]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393
[17]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[18]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[19]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[20]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (384)
  • HTML views (0)
  • Cited by (26)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences