微信服务号

微信订阅号

2025-5-16- 10
Home > Archive>Volume 28, Issue 6, 2017 >1529-1546. DOI:10.13328/j.cnki.jos.005259
PDF HTML XML Export Cite reminder
Overview of Constrained Optimization Evolutionary Algorithms
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61173107, 61672215, 91320103, 61672217); Production Study Research Cooperation Projects of Department of Education of Guangdong Province (2012A090300003); Guangdong Provincial Science and Technology Projects (2013B090700003); Graduate Scientific Research Innovation Foundation of Hunan Province (CX2016B067)

  • Article
    • | |
  • Metrics
    • |
  • Reference [72]
    • |
  • Related [20]
    • |
  • Cited by [3]
    • | |
  • Comments
    Abstract:

    Constrained optimization evolutionary algorithm, which mainly studies how to use evolutionary computation method to solve constrained optimization problems, is an important research topic in evolutionary computation field. Discrete constraint, equality constraint, nonlinear constraints are challenges to solving constraint optimization. The basis of this problem solving is how to handle the relationship between feasible solution and infeasible solution. In this study, the definition of constrained optimization problem is firstly provided, and then, the existing constrained optimization approaches are systematically analyzed. Meanwhile, algorithms are classified into six categories (i.e., penalty function method, feasible rules, stochastic ranking, ε-constraint, multi-objective constraint handling, and hybrid method), and the state-of-art constrained optimization evolutionary algorithms (COEAs) are surveyed with respect to constraint-handling techniques. Research progress and challenges of the six categories of constraint handling techniques are discussed in detail. Finally, the issues and research directions of constraint handling techniques are discussed.

    Reference
    [1] Michalewicz Z, Schoenauer M. Evolutionary algorithm for constrained parameter optimization problems. Evolutionary Computation, 1996,4(1):1-32.[doi:10.1162/evco.1996.4.1.1]
    [2] Coello CAC. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms:A survey of the state of the art. Computation Methods in Applied Mechanics and Engineering, 2002,191(11-12):1245-1287.[doi:10.1016/S0045- 7825(01)00323-1]
    [3] Mezura-Montes E, Coello CAC. Constraint-Handling in nature-inspired numerical optimization:Past, present and future. Swarm and Evolutionary Computation, 2011,1(4):173-194.[doi:10/1016/j.swevo.2011.10.001]
    [4] Gong W, Cai ZH, Liang DW. Adaptive ranking mutation operator based differential evolution for constrained optimization. IEEE Trans. on Cybernetics, 2015,45(4):716-727.[doi:10.1109/TCYB.2014.2334592]
    [5] Saha A, Datta R, Deb K. Hybrid gradient projection based genetic algorithms for constrained optimization. In:Proc. of the Congress on Evolutionary Computation. Barcelona:IEEE Service Center, 2010. 2851-2858.[doi:10.1109/CEC.2010.5586303]
    [6] Runarsson TP, Yao X. Stochastic ranking for constrained evolutionary optimization. IEEE Trans. on Evolutionary Computation, 2000,4(3):284-294.[doi:10.1109/4235.873238]
    [7] Takahama T, Sakai S. Constrained optimization by the ε constrained differential evolution with gradient-based mutation and feasible elites. In:Proc. of the 2006 IEEE Int'l Conf. on Evolutionary Computation. Vancouver:IEEE Press, 2006. 372-378.[doi:10.1109/CEC2006.1688283]
    [8] Wang Y, Cai ZX, Guo GQ, Zhou YR. Multi-Objective optimization and hybrid evolutionary algorithm to solve constrained optimization problems. IEEE Trans. on Systems, Man, and Cybernetics (B), 2007,37(3):560-575.
    [9] Mallipeddi R, Suganthan PN. Ensemble of constraint handling techniques. IEEE Trans. on Evolutionary Computation, 2010,14(4):561-579.[doi:10.1109/TEVC.2009.2033582]
    [10] Liang JJ, Runarsson TP, Mezura-Montes E, Clerc M, Suganthan PN, Coellon Coello CA, Deb K. Problem definitions and evaluations criteria for the CEC 2006 special session on constrained real-parameter optimization. Technical Report, #2006005, Singapore:Nanyang Technological University, 2006.
    [11] Mallipeddi R, Suganthan PN. Problem definitions and evaluation criteria for the CEC 2010 competition and special session on single objective constrained real-parameter optimization. Technical Report, #2010004, Singapore:Nanyang Technological University, 2010.
    [12] Wang Y, Cai ZX, Zhou YR, Fan Z. Constrained optimization based on hybrid evolutionary algorithm and adaptive constrainthandling technique. Structural and Multidisciplinary Optimization, 2009,37(4):395-413.[doi:10.1007/s00158-008-0238-3]
    [13] Jia GB, Wang Y, Cai ZX, Jin YC. An improved (μ+λ)-constrained differential evolution for constrained optimization. Information Sciences, 2013,222(10):302-322.[doi:10.1016/j.ins.2012.01.017]
    [14] Homaifar A, Lai SH, Qi X. Constrained optimization via genetic algorithms. Simulation Trans. of the Society for Modeling & Simulation International, 1994,62(4):242-254.[doi:10.1177/003754979406200405]
    [15] Joines J, Houck C. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA's. In:Michalewicz Z, et al., eds. Proc. of the 1st IEEE Conf. on Evolutionary Computation. Orlando:IEEE Press, 1994. 579-584.[doi:10.1109/ICEC.1994.349995]
    [16] Hoffmeister F, Sprave J. Problem-Independent handling of constraints by use of metric penalty functions. In:Fogel LJ, Angeline PJ, Bäck T, eds. Proc. of the 5th Annual Conf. on Evolutionary Programming (EP'96). San Diego:MIT Press, 1996. 289-294.
    [17] Basheed K. An adaptive penalty approach for constrained genetic algorithm optimization. In:Koza JR, et al., eds. Proc. of the 3rd Annual Conf. on Genetic Programming (GP'98)/Symp. on Genetic Algorithms (SGA'98). San Francisco:Morgan Kaufmann Publishers, 1998. 584-590.
    [18] MichaleWicz Z, Attia NF. Evolutionary optimization of constrained problems. In:Sebald AV, Fogel LJ, eds. Proc. of the 3rd Annual Conf. on Evolutionary Programming. River Edge:World Scientific, 1994. 98-108.
    [19] Le RRG, Knopf-Lenoir C, Haftka RT. A segregated genetic algorithm for constrained structural optimization. In:Eshelman LJ, ed. Proc. of the 6th Int'1 Conf. on Genetic Algorithms. San Francisco:Morgan Kaufman Publishers, 1995. 558-565.
    [20] Coello CAC. Use of a self-adaptive penalty approach for engineering optimization problems. Computers in Industry, 2000, 41(2):113-127.[doi:10.1016/S0166-3615(99)00046-9]
    [21] Huang F, Wang L, He Q. An effective co-evolutionary differential evolution for constrained optimization. Applied Mathematics and Computation, 2007,186(1):340-356.[doi:10.1016/j.amc.2006.07.105]
    [22] Hamida SB, Schoenauer M. ASCHEA:New results using adaptive segregational constraint handling. In:Fogel DB, et al., eds. Proc. of the Congress on Evolutionary Computation 2002(CEC 2002). Piscataway:IEEE Service Center, 2002. 884-889.[doi:10.1109/CEC.2002.1007042]
    [23] Farmani R, Wright JA. Self-Adaptive fitness formulation for constrained optimization. IEEE Trans. on Evolutionary Computation, 2003,7(5):445-455.[doi:10.1109/TEVC.2003.817236]
    [24] Xiao JH, Xu J, Shao Z, Jiang CF, Pan L. A genetic algorithm for solving multi-constrained function optimization problems based on KS function. In:Proc. of the 2007 IEEE Congress on Evolutionary Computation. Singapore:IEEE Press, 2007. 4497-4501.[doi:10.1109/CEC.2007.4425060]
    [25] Matias J, Correia A, Mestre P, Serodio C, Couto P, Teixeira C, Melo-Pinto P. Adaptive penalty and barrier function based on fuzzy logic. Expert Systems with Applications, 2015,42(19):6777-6783.[doi:10.1016/j.eswa.2015.04.070]
    [26] Lin CH. A rough penalty genetic algorithm for constrained optimization. Information Sciences, 2013,241(241):119-137.[doi:10.1016/j.ins.2013.04.001]
    [27] Tessema B, Yen G. A adaptive penalty formulation for constrained evolutionary optimization. IEEE Trans. on Systems, Man, and Cybernetics (A), 2009,39(3):565-578.[doi:10.1109/TSMCA.2009.2013333]
    [28] Lemonge ACC, Barbosa HJC, Bernardino HS. Variants of an adaptive penalty scheme for steady-state genetic algorithms in engineering optimization. Engineering Computations, 2015,32(8):2182-2215.[doi:10.1108/EC-07-2014-0158] 1544
    [29] De Melo V, Veloso V, Iacca G. A modified covariance matrix adaptation evolution strategy with adaptive penalty function and restart for constrained optimization. Expert Systems with Applications, 2014,41(16):7077-7049.[doi:10.1016/j.eswa.2014.06.032]
    [30] De Melo V, Iacca G. A CMA-ES-Based 2-Stage memetic framework for solving constrained optimization problems. In:Proc. of the 2014 IEEE Symp. on Foundations of Computational Intelligence (FOCI). Orlando:IEEE Press, 2014. 143-150.[doi:10.1109/FOCI. 2014.7007819]
    [31] Saha C, Das S, Pal K, Mukherjee S. A fuzzy rule-based penalty function approach for constrained evolutionary optimization. IEEE Trans. on Cybernetics, 2014,46(12):2953-2965.[doi:10.1109/TCYB.2014.2359985]
    [32] Deb K. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 2000,186(2-4):311-338.[doi:10.1016/S0045-7825(99)00389-8]
    [33] Zielinski R, Laur R. Constrained single-objective optimization using differential evolution. In:Proc. of the 2006 IEEE Int'l Conf. on Evolutionary Computation. Vancouver:IEEE Press, 2006. 223-230.[doi:10.1109/CEC.2006.1688312]
    [34] Mezura-Montes E, Coello CAC. A simple multimembered evolution strategy to solve constrained optimization problems. IEEE Trans. on Evolutionary Computation, 2005,9(1):1-17.[doi:10.1109/TEVC.2004.836819]
    [35] Mezura-Montes E, Velazquez-Reyes J, Coello Coello CA. Modified differential evolution for constrained optimization. In:Proc. of the 2006 IEEE Int'l Conf. on Evolutionary Computation. Vancouver:IEEE Press, 2006. 332-336.[doi:10.1109/CEC.2006. 1688286]
    [36] Cui CG, Li YJ, Wu TJ. A relative feasibility degree based approach for constrained optimization problems. Frontiers of Information Technology and Electronic Engineering, 2010,11(4):249-260.[doi:10.1631/jzus.C0910072]
    [37] Ullah A, Sarker R, Cornforth D. Search space reduction technique for constrained optimization with tiny feasible space. In:Keijzer M, ed. Proc. of the 10th Annual Conf. on Genetic and Evolutionary Computation. New York:ACM Press, 2008. 881-888.[doi:10.1145/1389095.1389268]
    [38] Elsayed SM, Sarker RA, Essam DL. GA with a new multi-parent crossover for constrained optimization. In:Proc. of the IEEE Congress on Evolutionary Computation (CEC 2011). New Orleans:IEEE Press, 2011. 857-864.[doi:10.1109/CEC.2011.5949708]
    [39] Sarker RA, Elsayed SM, Ray T. Differential evolution with dynamic parameters selection for optimization problems. IEEE Trans. on Evolutionary Computation, 2014,18(5):689-707.[doi:10.1109/TEVC.2013.2281528]
    [40] Wang Y, Wang BC, Li HX, Yen GG. Incorporating objective function information into the feasibility rule for constrained evolutionary optimization. IEEE Trans. on Cybernetics, 2015,46(12):2938-2952.[doi:10.1109/TCYB.2015.2493239]
    [41] Runarsson TP, Yao X. Search biases in constrained evolutionary optimization. IEEE Trans. on Systems, Man, Cybernetics (C), 2005,35(2):233-243.[doi:10.1109/TSMCC.2004.841906]
    [42] Zhang M, Luo WJ, Wang X. Differential evolution with dynamic stochastic selection for constrained optimization. Information Sciences, 2008,178(15):3043-3074.[doi:10.1016/j.ins.2008.02.014]
    [43] Bu C, Luo W, Zhu T. Differential evolution with a species-based repair strategy for constrained optimization. In:Proc. of the 2014 IEEE Congress on Evolutionary Computation. Beijing:IEEE Press, 2014. 967-974.[doi:10.1109/CEC.2014.6900526]
    [44] Brest J, Borko B, Zumer V. An improved self-adaptive differential evolution algorithm in single objective constrained realparameter optimization. In:Proc. of the IEEE Congress on Evolutionary Computation (CEC 2010). Barcelona:IEEE Service Center, 2010. 1073-1078.[doi:10.1109/CEC.2010.5585931]
    [45] Takahama T, Sakai S. Efficient constrained optimization by the ε constrained rank-based differential evolution. In:Proc. of the 2012 IEEE Congress on Evolutionary Computation. Brisbane:IEEE Press, 2012. 1-8.[doi:10.1109/CEC.2012.6256111]
    [46] Takahama T, Sakai S, Iwane N. AI 2005:Advances in Artificial Intelligence. Berlin, Heidelberg:Springer-Verlag, 2005. 389-400.[doi:10.1007/11589990_41]
    [47] Takahama T, Sakai S. Soft Computing as Transdisciplinary Science and Technology. Muroran:Springer-Verlag, 2005. 1019-1029.[doi:10.1007/3-540-32391-0]
    [48] Wang Y, Cai ZX, Zhou YR, Xiao CX. Constrained optimization evolutionary algorithms. Ruan Jian Xue Bao/Journal of Software, 2009,20(1):11-29(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3363.htm[doi:10.3724/SP.J.1001.2009. 03363]
    [49] Surry PD, Radcliffe NJ. The COMOGA method:Constrained optimization by multi-objective genetic algorithm. Control and Cybernetics, 1997,26(3):391-412.
    [50] Venkatraman S, Yen GG. A generic framework for constrained optimization using genetic algorithms. IEEE Trans. on Evolutionary Computation, 2005,9(4):424-435.[doi:10.1109/TEVC.2005.846817]
    [51] Coello CAC. Treating constraints as objectives for single-objective evolutionary optimization. Engineering Optimization, 2000,32(3):275-308.[doi:10.1080/03052150008941301]
    [52] Gong WY, Cai ZH. A multiobjective differential evolution algorithm for constrained optimization. In:Proc. of the 2008 IEEE Congress on Evolutionary Computation. Hong Kong:IEEE Press, 2008. 181-188.[doi:10.1109/CEC.2008.4630796]
    [53] Reynoso-Meza G, Blasco X, Sanchis J, Martínez M. Multiobjective optimization algorithm for solving constrained single objective problems. In:Proc. of the 2010 IEEE Congress on Evolutionary Computation. Barcelona:IEEE Service Center, 2010. 3418-3424.[doi:10.1109/CEC.2010.5586408]
    [54] Singh H, Ray T, Smith W. Performance of infeasibility empowered memetic algorithm for CEC 2010 constrained optimization problems. In:Proc. of the IEEE Congress on Evolutionary Computation. Barcelona:IEEE Service Center, 2010. 3770-3777.[doi:10.1109/CEC.2010.5585946]
    [55] Cai ZX, Wang Y. Combining multiobjective optimization with differential evolution to solve constrained optimization problems. IEEE Trans. on Evolutionary Computation, 2012,16(1):117-134.[doi:10.1109/TEVC.2010.2093582]
    [56] Wang Y, Cai ZX, Guo G, Zhou YR. A dynamic hybrid framework for constrained evolutionary optimization. IEEE Trans. on Systems, Man, and Cybernetics (B), 2012,42(1):203-217.[doi:10.1109/TSMCB.2011.2161467]
    [57] Li XS, Zhang GS. Biased multiobjective optimization for constrained single-objective evolutionary optimization. In:Proc. of the 11th World Congress on Intelligent Control and Automation (WCICA). Shenyang:IEEE, 2014. 891-896.[doi:10.1109/WCICA. 2014.7052834]
    [58] Gao WF, Yen G, Liu SY. A dual-population differential evolution with coevolution for constrained optimization. IEEE Trans. on Cybernetics, 2014,45(5):1108-1121.[doi:10.1109/TCYB.2014.2345478]
    [59] Wang Y, Cai ZX, Zhou YR, Zeng W. An adaptive trade-off model for constrained evolutionary optimization. IEEE Trans. on Evolutionary Computation, 2008,12(1):80-92.[doi:10.1109/TEVC.2007.902851]
    [60] Wang Y, Cai ZX. Hybrid differential evolution and adaptive trade-off model to solve constrained optimization problems. In:Proc. of the IEEE Congress on Evolutionary Computation (CEC 2010). Barcelona:IEEE Press, 2010. 1-5.[doi:10.1109/CEC.2010. 5586189]
    [61] Elsayed SM, Sarker RA, Essam D. Integrated strategies differential evolution algorithm with a local search for constrained optimization. In:Proc. of the IEEE Congress of Evolutionary Computation. New Orleans:IEEE Press, 2011. 2618-2625.[doi:10.1109/CEC.2011.5949945]
    [62] Jiao LC, Li L, Shang RH, Liu F, Stolkin R. A novel selection evolutionary strategy for constrained optimization. Information Sciences, 2013,239:122-141.[doi:10.1016/j.ins.2013.03.002]
    [63] Wang Y, Liu H, Cai ZX, Zhou YR. An orthogonal design based constrained evolutionary optimization algorithm. Engineering Optimization, 2007,39(6):715-736.[doi:10.1080/03052150701280541]
    [64] Cai ZX, Wang Y. A multiobjective optimization based evolutionary algorithm for constrained optimization. IEEE Trans. on Evolutionary Computation, 2006,10(6):658-675.[doi:10.1109/TEVC.2006.872344]
    [65] Tasgetiren MF, Suganthan PN, Pan Q-K, Mallipeddi R, Sarman S. An ensemble of differential evolution algorithms for constrained function optimization. In:Proc. of the IEEE Congress on Evolutionary Computation Vol.5. Barcelona:IEEE Service Center, 2010. 967-975.[doi:10.1109/CEC.2010.5586396]
    [66] Mani A, Parvarhan C. A novel hybrid constraint-handling technique for evolutionary optimization. In:Proc. of the 11th Conf. on Congress on Evolutionary Computation (CEC 2009). Trondheim:IEEE Press, 2009. 2577-2583.[doi:10.1109/CEC.2009.4983265]
    [67] Gan M, Peng H, Peng XY, Chen XH, Inoussa G. An adaptive decision maker for constrained evolutionary optimization. Applied Mathematics and Computation, 2010,215(12):4172-4184.[doi:10.1016/j.amc.2009.12.038] 1546
    [68] Deb K, Datta R. A fast and accurate solution of constrained optimization problems using a hybrid bi-objective and penalty function approach. In:Proc. of the 2010 IEEE Congress on Evolutionary Computation (CEC 2010). Barcelona:IEEE Press, 2010. 1-8.[doi:10.1109/CEC.2010.5586543]
    [69] Datta R, Deb K. An adaptive normalization based constrained handling methodology with hybrid bi-objective and penalty function approach. In:Proc. of the IEEE Congress on Evolutionary Computation (CEC 2012). Brisbane:IEEE Press, 2012. 1-8.[doi:10. 1109/CEC.2012.6252955]
    [70] Datta R, Deb K. Individual penalty based constraint handling using a hybrid bi-objective and penalty function approach. In:Proc. of the 2013 IEEE Congress on Evolutionary Computation. Cancun:IEEE, 2013. 2720-2727.[doi:10.1109/CEC.2013.6557898]
    附中文参考文献:
    [48] 王勇,蔡自兴,周育人,肖赤心.约束优化进化算法.软件学报,2009,20(1):11-29. http//:www.jos.org.cn/1000-9825/3363.htm[doi:10.3724/SP.J.1001.2009.03363]
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李智勇,黄滔,陈少淼,李仁发.约束优化进化算法综述.软件学报,2017,28(6):1529-1546

Copy
Share
Article Metrics
  • Abstract:6060
  • PDF: 12247
  • HTML: 5473
  • Cited by: 0
History
  • Received:May 03,2016
  • Revised:October 11,2016
  • Online: February 21,2017
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044893Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063