American Institute of Mathematical Sciences

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

 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.
Citation: Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial and 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-18. doi: 10.1080/10556780903151565. [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. [3] S. Ben Hamida and M. Schoenauer, Aschea: New results using adaptive segregational constraint handling, in Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, 1, IEEE, (2002), 884-889. [4] Z. Cai and Y. Wang, A multiobjective optimization-based evolutionary algorithm for constrained optimization, Evolutionary Computation, IEEE Transactions on, 10 (2006), 658-675. doi: 10.1109/TEVC.2006.872344. [5] G. Camp, Inequality-constrained stationary-value problems, Journal of the Operations Research Society of America, 3 (1955), 548-550. doi: 10.1287/opre.3.4.548a. [6] C. Carroll and A. Fiacco, The created response surface technique for optimizing nonlinear restrained systems, Operations Research, 9 (1961), 169-185. doi: 10.1287/opre.9.2.169. [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-654. doi: 10.1016/j.ejor.2003.08.053. [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-409. doi: 10.3934/jimo.2013.9.391. [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-500. doi: 10.1137/090780201. [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-7. [11] R. Fletcher, An ideal penalty function for constrained optimization, IMA Journal of Applied Mathematics, 15 (1975), 319-342. doi: 10.1093/imamat/15.3.319. [12] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning. [13] H. Greenberg, The generalized penalty-function/surrogate model, Operations Research, 21 (1973), 162-178. doi: 10.1287/opre.21.1.162. [14] A. Hedar, Global optimization methods and codes, http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar.html. [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-912. doi: 10.1080/1055678021000030084. [16] A. Hedar and M. Fukushima, Derivative-free filter simulated annealing method for constrained continuous global optimization, Journal of Global Optimization, 35 (2006), 521-549. doi: 10.1007/s10898-005-3693-z. [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-320. doi: 10.1007/s10107-007-0123-7. [18] N. Karmitsa, A. Bagirov and M. Mäkelä, Comparing different nonsmooth minimization methods and software, Optimization Methods and Software, 27 (2012), 131-153. doi: 10.1080/10556788.2010.526116. [19] S. Koziel and Z. Michalewicz, Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization, Evolutionary computation, 7 (1999), 19-44. doi: 10.1162/evco.1999.7.1.19. [20] O. Kramer, A review of constraint-handling techniques for evolution strategies, Applied Computational Intelligence and Soft Computing, 2010. doi: 10.1155/2010/185063. [21] Y. Liu, An exterior point linear programming method based on inclusive nornal cone, Journal of Industrial and Management Optimization, 6 (2010), 825-846. doi: 10.3934/jimo.2010.6.825. [22] D. Luenberger, Introduction to linear and nonlinear programming. [23] R. Mallipeddi and P. N. Suganthan, Ensemble of constraint handling techniques, Evolutionary Computation, IEEE Transactions on, 14 (2010), 561-579. doi: 10.1109/TEVC.2009.2033582. [24] E. Mezura-Montes and C. C. Coello, A simple multimembered evolution strategy to solve constrained optimization problems, Evolutionary Computation, IEEE Transactions on, 9 (2005), 1-17. doi: 10.1109/TEVC.2004.836819. [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-619. doi: 10.3934/jimo.2013.9.595. [26] W. Pierskalla, Mathematical programming with increasing constraint functions, Management Science, 15 (1968/1969), 416-425. [27] T. P. Runarsson and X. Yao, Stochastic ranking for constrained evolutionary optimization, Evolutionary Computation, IEEE Transactions on, 4 (2000), 284-294. doi: 10.1109/4235.873238. [28] J. Vasconcelos, J. Ramirez, R. Takahashi and R. Saldanha, Improvements in genetic algorithms, Magnetics, IEEE Transactions on, 37 (2001), 3414-3417. doi: 10.1109/20.952626. [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-413. doi: 10.1007/s00158-008-0238-3. [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), 895. doi: 10.3934/jimo.2010.6.895. [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-601. doi: 10.3934/jimo.2009.5.585.

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-18. doi: 10.1080/10556780903151565. [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. [3] S. Ben Hamida and M. Schoenauer, Aschea: New results using adaptive segregational constraint handling, in Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, 1, IEEE, (2002), 884-889. [4] Z. Cai and Y. Wang, A multiobjective optimization-based evolutionary algorithm for constrained optimization, Evolutionary Computation, IEEE Transactions on, 10 (2006), 658-675. doi: 10.1109/TEVC.2006.872344. [5] G. Camp, Inequality-constrained stationary-value problems, Journal of the Operations Research Society of America, 3 (1955), 548-550. doi: 10.1287/opre.3.4.548a. [6] C. Carroll and A. Fiacco, The created response surface technique for optimizing nonlinear restrained systems, Operations Research, 9 (1961), 169-185. doi: 10.1287/opre.9.2.169. [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-654. doi: 10.1016/j.ejor.2003.08.053. [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-409. doi: 10.3934/jimo.2013.9.391. [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-500. doi: 10.1137/090780201. [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-7. [11] R. Fletcher, An ideal penalty function for constrained optimization, IMA Journal of Applied Mathematics, 15 (1975), 319-342. doi: 10.1093/imamat/15.3.319. [12] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning. [13] H. Greenberg, The generalized penalty-function/surrogate model, Operations Research, 21 (1973), 162-178. doi: 10.1287/opre.21.1.162. [14] A. Hedar, Global optimization methods and codes, http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar.html. [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-912. doi: 10.1080/1055678021000030084. [16] A. Hedar and M. Fukushima, Derivative-free filter simulated annealing method for constrained continuous global optimization, Journal of Global Optimization, 35 (2006), 521-549. doi: 10.1007/s10898-005-3693-z. [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-320. doi: 10.1007/s10107-007-0123-7. [18] N. Karmitsa, A. Bagirov and M. Mäkelä, Comparing different nonsmooth minimization methods and software, Optimization Methods and Software, 27 (2012), 131-153. doi: 10.1080/10556788.2010.526116. [19] S. Koziel and Z. Michalewicz, Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization, Evolutionary computation, 7 (1999), 19-44. doi: 10.1162/evco.1999.7.1.19. [20] O. Kramer, A review of constraint-handling techniques for evolution strategies, Applied Computational Intelligence and Soft Computing, 2010. doi: 10.1155/2010/185063. [21] Y. Liu, An exterior point linear programming method based on inclusive nornal cone, Journal of Industrial and Management Optimization, 6 (2010), 825-846. doi: 10.3934/jimo.2010.6.825. [22] D. Luenberger, Introduction to linear and nonlinear programming. [23] R. Mallipeddi and P. N. Suganthan, Ensemble of constraint handling techniques, Evolutionary Computation, IEEE Transactions on, 14 (2010), 561-579. doi: 10.1109/TEVC.2009.2033582. [24] E. Mezura-Montes and C. C. Coello, A simple multimembered evolution strategy to solve constrained optimization problems, Evolutionary Computation, IEEE Transactions on, 9 (2005), 1-17. doi: 10.1109/TEVC.2004.836819. [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-619. doi: 10.3934/jimo.2013.9.595. [26] W. Pierskalla, Mathematical programming with increasing constraint functions, Management Science, 15 (1968/1969), 416-425. [27] T. P. Runarsson and X. Yao, Stochastic ranking for constrained evolutionary optimization, Evolutionary Computation, IEEE Transactions on, 4 (2000), 284-294. doi: 10.1109/4235.873238. [28] J. Vasconcelos, J. Ramirez, R. Takahashi and R. Saldanha, Improvements in genetic algorithms, Magnetics, IEEE Transactions on, 37 (2001), 3414-3417. doi: 10.1109/20.952626. [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-413. doi: 10.1007/s00158-008-0238-3. [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), 895. doi: 10.3934/jimo.2010.6.895. [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-601. doi: 10.3934/jimo.2009.5.585.
 [1] Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895 [2] Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 [3] Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485 [4] Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 [5] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [6] Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775 [7] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [8] Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012 [9] Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705 [10] Junjie Peng, Ning Chen, Jiayang Dai, Weihua Gui. A goethite process modeling method by Asynchronous Fuzzy Cognitive Network based on an improved constrained chicken swarm optimization algorithm. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1269-1287. doi: 10.3934/jimo.2020021 [11] He Huang, Zhen He. A global optimization method for multiple response optimization problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022016 [12] Youness El Yazidi, Abdellatif ELLABIB. A new hybrid method for shape optimization with application to semiconductor equations. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021034 [13] Ning Chen, Yan Xia Zhao, Jia Yang Dai, Yu Qian Guo, Wei Hua Gui, Jun Jie Peng. Hybrid modeling and distributed optimization control method for the iron removal process. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022003 [14] Chien-Wen Chao, Shu-Cherng Fang, Ching-Jong Liao. A tropical cyclone-based method for global optimization. Journal of Industrial and Management Optimization, 2012, 8 (1) : 103-115. doi: 10.3934/jimo.2012.8.103 [15] A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319 [16] Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645 [17] Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075 [18] C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 613-631. doi: 10.3934/naco.2020058 [19] Panagiotis Stinis. A hybrid method for the inviscid Burgers equation. Discrete and Continuous Dynamical Systems, 2003, 9 (4) : 793-799. doi: 10.3934/dcds.2003.9.793 [20] Abdulkarim Hassan Ibrahim, Jitsupa Deepho, Auwal Bala Abubakar, Kazeem Olalekan Aremu. A modified Liu-Storey-Conjugate descent hybrid projection method for convex constrained nonlinear equations and image restoration. Numerical Algebra, Control and Optimization, 2022, 12 (3) : 569-582. doi: 10.3934/naco.2021022

2021 Impact Factor: 1.411