基于负相关搜索的约束优化算法研究

演化算法（evolutionary algorithm，简称 EA）是一类受自然界生物遗传进化启 发的智能优化算法，由于其在复杂搜索空间中的全局优化能力使得它们被广泛地 应用到各类优化问题中。约束优化问题是一类在实际工程问题中常见的优化问题， 通常因为包含复杂形式的约束条件而难以求解。因此，演化算法结合约束处理机 制（constraint handling techniques，简称 CHT）用于求解带有复杂约束条件的约束 优化问题近年来逐渐成为研究热点。 本文基于具有高效全局搜索能力的负相关搜索（negatively correlated search，简 称 NCS）算法，提出了一种新的基于负相关搜索的混合约束优化算法（NCS-E）， 用于求解带有复杂约束条件的优化问题。该算法集成多种互补的约束处理机制，通 过投票决定每一代存活的个体，并利用投票个体在种群中的负相关性衡量约束处 理机制的表现，以鼓励约束处理机制维持不同的并行搜索行为之间的差异，从而 引导种群向不同的可行域搜索。 本文在 57 个公开的约束优化测试问题上对新提出的算法进行测试，先后将其 与基于负相关搜索的单一约束优化算法以及领域内先进的约束优化演化算法进行 对比，实验结果显示提出的算法在高维度且包含复杂约束条件的问题上具备优势。 为了验证提出算法在实际约束优化问题上的有效性，我们将其应用到神经网 络压缩问题中，在保证模型准确度的约束条件下搜索最优的剪枝方案。我们在三 个深度神经网络模型上进行测试，实验表明本文提出的算法相比已有剪枝算法能 够获得更高的剪枝率。

Evolutionary algorithms (EAs) are heuristic optimization algorithms inspired by nature biological evolution, and have been widely used in various optimization problems due to their global optimization ability. Constrained optimization problems (COPs) are common in practical engineering problems and often difficult to solve due to their complex constraints. Therefore, designing effective constraint handling techniques (CHTs) for EAs dealing with COPs has gradually become a hot research topic. This thesis proposes a hybrid constrained optimization algorithm based on negatively correlated search (NCS), an EA with powerful global search ability, to solve real-world optimization problems with complex constraints. The algorithm integrates multiple complementary CHTs, and uses voting mechanism to select the surviving individuals at each generation. It also uses the negative correlation among the voting individuals by each CHT to measure the performance of corresponding CHT, and encourages the CHTs to maintain the diversity of different parallel local search behaviors, thus guiding the population to search different feasible regions. This thesis compares the proposed algorithm with four NCS-based methods and two state-of-the-art methods on 57 constrained optimization test problems, respectively. The experimental results show that the proposed algorithm has advantages on highdimensional and complex constrained problems. To validate the effectiveness of the proposed algorithm on real-world constrained optimization problems, we apply it to neural network compression problem, and search for the optimal pruning scheme under the constraint of model accuracy. Compared with another state-of-the-art method, the proposed algorithm achieves higher pruning rates on three deep neural network models.

[1] XIONG F, CHEN S, MA Z, et al. Approximate model and algorithms for precast supply chainscheduling problem with time-dependent transportation times[J/OL]. International Journal ofProduction Research, 2023, 61(7): 2057-2085. DOI: 10.1080/00207543.2022.2057254.
[2] PEI J, PARDALOS P M, LIU X, et al. Coordination of production and transportation in supplychain scheduling[J]. Journal of Industrial and Management Optimization, 2015, 11(2): 399-419.
[3] ZHENG S, LIU J, WU D. Research on uncertain integrated production planning and scheduling with risk management based on improved collaborative optimization[J/OL]. ConcurrentEngineering, 0, 0(0): 1063293X221138774. DOI: 10.1177/1063293X221138774.
[4] WRIGHT S, NOCEDAL J, et al. Numerical optimization[J]. Springer Science, 1999, 35(67-68):7.
[5] 陈国良, 王煦法, 庄镇泉, 等. 遗传算法及其应用[M]. 北京: 人民邮电出版社, 1996.
[6] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN’95-international conference on neural networks: volume 4. IEEE, 1995: 1942-1948.
[7] DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents[J/OL]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics),1996, 26(1): 29-41. DOI: 10.1109/3477.484436.
[8] 陈少淼, 陈瑞, 李仁发, 等. 面向复杂约束优化问题的进化算法综述[J/OL]. 软件学报, 2023(565-581). DOI: 10.13328/j.cnki.jos.006711.
[9] DE JONG K. Evolutionary computation: A unified approach[C]//Proceedings of the Geneticand Evolutionary Computation Conference Companion. 2017: 373-388.
[10] SONODA T, NAKATA M. Multiple classifiers-assisted evolutionary algorithm based on decomposition for high-dimensional multiobjective problems[J/OL]. IEEE Transactions on Evolutionary Computation, 2022, 26(6): 1581-1595. DOI: 10.1109/TEVC.2022.3159000.
[11] LIAO Z, GONG W, WANG L. Memetic niching-based evolutionary algorithms for solvingnonlinear equation system[J/OL]. Expert Systems with Applications, 2020, 149: 113261. DOI:10.1016/j.eswa.2020.113261.
[12] RAHIMI I, GANDOMI A H, CHEN F, et al. A review on constraint handling techniquesfor population-based algorithms: From single-objective to multi-objective optimization[J].Archives of Computational Methods in Engineering, 2023, 30(3): 2181-2209.
[13] STORN R, PRICE K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359.
[14] HANSEN N, OSTERMEIER A. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation[C/OL]//Proceedings of IEEE InternationalConference on Evolutionary Computation. Nagoya, Japan: IEEE, 1996: 312-317. DOI:10.1109/ICEC.1996.542381.
[15] WANG B C, LI H X, LI J P, et al. Composite differential evolution for constrained evolutionaryoptimization[J/OL]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(7): 1482-1495. DOI: 10.1109/TSMC.2018.2807785.
[16] BEYER H G, SENDHOFF B. Simplify your covariance matrix adaptation evolution strategy[J/OL]. IEEE Transactions on Evolutionary Computation, 2017, 21(5): 746-759. DOI: 10.1109/TEVC.2017.2680320.
[17] ARNOLD D V, HANSEN N. A (1+1)-CMA-ES for constrained optimisation[C/OL]//GECCO’12: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation.New York, NY, USA: Association for Computing Machinery, 2012: 297–304. DOI: 10.1145/2330163.2330207.
[18] SPETTEL P, BEYER H G. Matrix adaptation evolution strategies for optimization under nonlinear equality constraints[J/OL]. Swarm and Evolutionary Computation, 2020, 54: 100653.DOI: 10.1016/j.swevo.2020.100653.
[19] JOINES J A, HOUCK C R, et al. On the use of non-stationary penalty functions to solvenonlinear constrained optimization problems with GA’s.[C]//International Conference on Evolutionary Computation. 1994: 579-584.
[20] BEN HADJ-ALOUANE A, BEAN J C. A genetic algorithm for the multiple-choice integerprogram[J]. Operations Research, 1997, 45(1): 92-101.
[21] BARBOSA H J, LEMONGE A C, BERNARDINO H S. A critical review of adaptive penaltytechniques in evolutionary computation[J]. Evolutionary constrained optimization, 2015: 1-27.
[22] LU K D, ZENG G Q, ZHOU W. Adaptive constrained population extremal optimisation-basedrobust proportional-integral-derivation frequency control method for an islanded microgrid[J].IET Cyber-Systems and Robotics, 2021, 3(3): 210-227.
[23] DE MELO V V, IACCA G. A modified covariance matrix adaptation evolution strategy withadaptive penalty function and restart for constrained optimization[J]. Expert Systems with Applications, 2014, 41(16): 7077-7094.
[24] DEB K. An efficient constraint handling method for genetic algorithms[J]. Computer Methodsin Applied Mechanics and Engineering, 2000, 186(2-4): 311-338.
[25] RUNARSSON T P, YAO X. Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on evolutionary computation, 2000, 4(3): 284-294.
[26] TAKAHAMA T, SAKAI S. Constrained optimization by the 𝜀 constrained differential evolutionwith an archive and gradient-based mutation[C]//IEEE Congress on Evolutionary Computation.IEEE, 2010: 1-9.
[27] ZHANG C, QIN A K, SHEN W, et al. 𝜖-constrained differential evolution using an adaptive 𝜖-level control method[J/OL]. IEEE Transactions on Systems, Man, and Cybernetics: Systems,2020: 1-17. DOI: 10.1109/TSMC.2020.3010120.
[28] GUOL J, CHENG T, FAN Z, et al. LSHADE with s-shape constraint-handling technique inpush and pull search for constrained optimization Pproblems[C]//2020 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2020: 1-8.
[29] JIAO D, YANG P, FU L, et al. Optimal energy-delay scheduling for energy-harvesting WSNswith interference channel via negatively correlated search[J]. IEEE Internet of Things Journal,2019, 7(3): 1690-1703.
[30] WANG Y, CAI Z. A dynamic hybrid framework for constrained evolutionary optimization[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2011, 42(1): 203-217.
[31] WANG B C, LI H X, ZHANG Q, et al. Decomposition-based multiobjective optimization forconstrained evolutionary optimization[J]. IEEE Transactions on systems, man, and cybernetics:systems, 2018, 51(1): 574-587.
[32] WOLPERT D, MACREADY W. No free lunch theorems for optimization[J/OL]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82. DOI: 10.1109/4235.585893.
[33] WU G, WEN X, WANG L, et al. A voting-mechanism-based ensemble framework for constrainthandling Ttchniques[J]. IEEE Transactions on Evolutionary Computation, 2021, 26(4): 646-660.
[34] WANG Y, LI J P, XUE X, et al. Utilizing the correlation between constraints and objective function for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 24(1): 29-43.
[35] TIAN Y, ZHANG T, XIAO J, et al. A coevolutionary framework for constrained multiobjectiveOoptimization problems[J/OL]. IEEE Transactions on Evolutionary Computation, 2021, 25(1):102-116. DOI: 10.1109/TEVC.2020.3004012.
[36] TANG K, YANG P, YAO X. Negatively correlated search[J/OL]. IEEE Journal on SelectedAreas in Communications, 2016, 34(3): 542-550. DOI: 10.1109/JSAC.2016.2525458.
[37] JIAO D, YANG P, FU L, et al. Optimal energy-delay scheduling for energy-harvesting WSNsWith interference channel via negatively correlated search[J/OL]. IEEE Internet of Things Journal, 2020, 7(3): 1690-1703. DOI: 10.1109/JIOT.2019.2954604.
[38] LI G, QIAN C, JIANG C, et al. Optimization based layer-wise magnitude-based pruning forDNN compression[C/OL]//Proceedings of the Twenty-Seventh International Joint Conferenceon Artificial Intelligence. Stockholm, Sweden: International Joint Conferences on ArtificialIntelligence Organization, 2018: 2383-2389. DOI: 10.24963/ijcai.2018/330.
[39] YANG P, YANG Q, TANG K, et al. Parallel exploration via negatively correlated search[J/OL].Frontiers of Computer Science, 2021, 15(5): 155333. DOI: 10.1007/s11704-020-0431-0.
[40] KUMAR A, DAS S, MISRA A K, et al. A 𝑣-constrained matrix adaptation evolution strategy with Broyden-based mutation for constrained optimization[J/OL]. IEEE Transactions onCybernetics, 2022, 52(6): 4784-4796. DOI: 10.1109/TCYB.2020.3042853.
[41] KAILATH T. The divergence and Bhattacharyya distance measures in signal selection[J]. IEEEtransactions on communication technology, 1967, 15(1): 52-60.
[42] RECHENBERG I. Evolutionsstrategie[J]. Optimierung technischer Systeme nach Prinzipienderbiologischen Evolution, 1973.
[43] ZHANG Q, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J/OL]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. DOI: 10.1109/TEVC.2007.892759.
[44] KUMAR A, WU G, ALI M Z, et al. A test-suite of non-convex constrained optimization problems from the real-world and some baseline results[J/OL]. Swarm and Evolutionary Computation, 2020, 56: 100693. DOI: 10.1016/j.swevo.2020.100693.
[45] TRIVEDI A, SRINIVASAN D, BISWAS N. An improved unified differential evolution algorithm for constrained optimization problems[C]//Proceedings of 2018 IEEE congress on evolutionary computation. IEEE, 2018: 1-10.
[46] TRIVEDI A, SANYAL K, VERMA P, et al. A unified differential evolution algorithm forconstrained optimization problems[C/OL]//2017 IEEE Congress on Evolutionary Computation(CEC). 2017: 1231-1238. DOI: 10.1109/CEC.2017.7969446.
[47] HELLWIG M, BEYER H G. A matrix adaptation Eevolution strategy for constrained realparameter optimization[C/OL]//2018 IEEE Congress on Evolutionary Computation (CEC).2018: 1-8. DOI: 10.1109/CEC.2018.8477950.
[48] LECUN Y, BOTTOU L, BENGIO Y, et al. Gradient-based learning applied to document recognition[J/OL]. Proceedings of the IEEE, 1998, 86(11): 2278-2324. DOI: 10.1109/5.726791.
[49] KRIZHEVSKY A, SUTSKEVER I, HINTON G E. ImageNet classification with deep convolutional neural networks[J/OL]. Communications of the ACM, 2017, 60(6): 84–90. DOI:10.1145/3065386.
[50] LECUN Y, DENKER J, SOLLA S. Optimal brain damage[J]. Advances in Neural InformationProcessing Systems, 1989, 2.
[51] RASTEGARI M, ORDONEZ V, REDMON J, et al. XNOR-Net: ImageNet classification usingbinary convolutional neural networks[C]//LEIBE B, MATAS J, SEBE N, et al. Computer Vision– ECCV 2016. Cham: Springer International Publishing, 2016: 525-542.
[52] HINTON G, VINYALS O, DEAN J. Distilling the knowledge in a neural network[A]. 2015.arXiv: 1503.02531.
[53] CHENG Y, WANG D, ZHOU P, et al. A survey of model compression and acceleration for deepneural networks[A]. 2020. arXiv: 1710.09282.
[54] ANWAR S, HWANG K, SUNG W. Structured pruning of deep convolutional neural networks[J/OL]. ACM Journal on Emerging Technologies in Computing Systems, 2017, 13(3). DOI:10.1145/3005348.
[55] HAN S, POOL J, TRAN J, et al. Learning both weights and connections for efficient neural network[C]//CORTES C, LAWRENCE N, LEE D, et al. Advances in Neural InformationProcessing Systems: volume 28. Curran Associates, Inc., 2015.
[56] GUO Y, YAO A, CHEN Y. Dynamic network surgery for efficient DNNs[C]//LEE D,SUGIYAMA M, LUXBURG U, et al. Advances in Neural Information Processing Systems:volume 29. Curran Associates, Inc., 2016.
[57] ULLRICH K, MEEDS E, WELLING M. Soft weight-sharing for neural network compression[A]. 2017. arXiv: 1702.04008.
[58] HE Y, LIN J, LIU Z, et al. AMC: AutoML for model compression and acceleration on mobiledevices[C]//Proceedings of the European Conference on Computer Vision (ECCV). 2018.
[59] LIN M, JI R, ZHANG Y, et al. Channel pruning via automatic structure search[A]. 2020. arXiv:2001.08565.
[60] LIU Z, MU H, ZHANG X, et al. MetaPruning: Meta learning for automatic neural networkchannel pruning[A]. 2019. arXiv: 1903.10258.