基于协方差学习的差异进化算法及其应用研究
|
摘要
差异进化算法是一种高效稳健的进化算法,是近年来进化计算研究领域的热点。针对差异进化算法对变量相关问题的求解困难,本文提出一种基于协方差学习机制的差异进化算法LYDE。
LYDE通过对当前解集的协方差矩阵进行特征值分解以选取合适的轴向进行交叉,消除差异进化算法对原坐标系的依赖性,并降低了优化问题变量间的相关性,提高了差异进化算法在旋转问题上的求解性能。LYDE采用双峰参数设置,即交叉概率和变异因子分别服从不同类型的双峰概率分布。交叉概率服从的双峰概率分布由两个不同均值的正态分布构成,使得交叉操作产生的子代高概率的分布在父体附近。变异因子服从的双峰概率分布由两个不同位置参数的柯西分布构成,用以平衡LYDE的全局搜索能力和局部寻优能力。通过对CEC2005中25个标准测试函数的数值试验,验证了LYDE在全局优化尤其是变量相关问题上的有效性以及在噪声问题上的鲁棒性。与现有算法(jDE, SaDE, JADE, EPSDE, CoDE)的对比结果表明LYDE在收敛速率和鲁棒性上优于现有算法。同时,实验也表明LYDE的两项机制对算法的性能有重要影响,对LYDE性能有协同作用。参数实验表明设置采样率为0.4,学习率为0.65的LYDE在测试集上有稳健的性能。
为扩展LYDE的应用范围,本文通过空间映射方案将LYDE的应用领域由连续问题拓展到一类经典的离散组合优化问题——平面图上的集合覆盖问题,此类集合覆盖问题是应急设施选址的抽象问题。空间映射方案基于最小欧氏距离原则将LYDE的连续向量空间映射到离散解空间,从而保持DE的原有结构对离散问题进行求解。空间映射方案利用了平面图顶点间的距离关系,有效的提升了算法的求解性能。实验结果表明LYDE在集合覆盖问题上有优良的求解效果,并且求解性能优于遗传算法,展现了LYDE在离散问题上的应用潜力。
Differential evolution which is an efficient and robust evolutionary algorithm is a hotspot of the evolutionary computation research in recent years. In order to improve the performance in multivariate correlation problems such as rotated problems, a covariance matrix learning based differential evolution (LYDE) is presented.
In LYDE, Eigen decomposition is applied to covariance matrix of current solution set to achieve an Eigen coordinate system for crossover operator. The covariance matrix learning eliminates the coordinate system dependence from differential evolution and improves the performance in multivariate correlation problems. Moreover, we embed bimodal distribution parameter setting in our algorithm. Bimodal distribution for crossover probability is composed of two normal distributions with different mean values, and makes offspring produced by crossover operator distribute around the parents with high probability. Bimodal distribution for mutation factor is composed of two Cauchy distributions with different medians, and balances global exploration and local exploitation. LYDE has been tested on 25 benchmark functions of CEC2005 test suite. The experimental results suggest that LYDE is efficient for global optimization, especially rotated problems and is robust to noise. LYDE has a faster convergence rate and a higher precision than five recent algorithms (i.e. jDE, SaDE, JADE, EPSDE, CoDE) on 25 benchmark functions. The experiment also suggests both covariance matrix learning approach and bimodal parameter setting are critical to LYDE and the two components have a cooperative effect. The parameter sensitivity experiment shows LYDE with sample rate 0.4 and learning rate 0.65 has a robust performance on test suite.
In addition, we propose an approach that mapping the continuous vector space to the discrete solution space based on the minimum Euclidean distance principle. By the above method, keeping the original structure of DE, the application field of LYDE is extended from the continuous problems to a classical discrete combinatorial optimization problem—set cover problem on ichnography, which is an abstraction of emergency facility location. The experiment result shows LYDE has an excellent performance and has a faster convergence rate and a higher precision than genetic algorithm. The application of LYDE for discrete problem is promising.
LYDE通过对当前解集的协方差矩阵进行特征值分解以选取合适的轴向进行交叉,消除差异进化算法对原坐标系的依赖性,并降低了优化问题变量间的相关性,提高了差异进化算法在旋转问题上的求解性能。LYDE采用双峰参数设置,即交叉概率和变异因子分别服从不同类型的双峰概率分布。交叉概率服从的双峰概率分布由两个不同均值的正态分布构成,使得交叉操作产生的子代高概率的分布在父体附近。变异因子服从的双峰概率分布由两个不同位置参数的柯西分布构成,用以平衡LYDE的全局搜索能力和局部寻优能力。通过对CEC2005中25个标准测试函数的数值试验,验证了LYDE在全局优化尤其是变量相关问题上的有效性以及在噪声问题上的鲁棒性。与现有算法(jDE, SaDE, JADE, EPSDE, CoDE)的对比结果表明LYDE在收敛速率和鲁棒性上优于现有算法。同时,实验也表明LYDE的两项机制对算法的性能有重要影响,对LYDE性能有协同作用。参数实验表明设置采样率为0.4,学习率为0.65的LYDE在测试集上有稳健的性能。
为扩展LYDE的应用范围,本文通过空间映射方案将LYDE的应用领域由连续问题拓展到一类经典的离散组合优化问题——平面图上的集合覆盖问题,此类集合覆盖问题是应急设施选址的抽象问题。空间映射方案基于最小欧氏距离原则将LYDE的连续向量空间映射到离散解空间,从而保持DE的原有结构对离散问题进行求解。空间映射方案利用了平面图顶点间的距离关系,有效的提升了算法的求解性能。实验结果表明LYDE在集合覆盖问题上有优良的求解效果,并且求解性能优于遗传算法,展现了LYDE在离散问题上的应用潜力。
Differential evolution which is an efficient and robust evolutionary algorithm is a hotspot of the evolutionary computation research in recent years. In order to improve the performance in multivariate correlation problems such as rotated problems, a covariance matrix learning based differential evolution (LYDE) is presented.
In LYDE, Eigen decomposition is applied to covariance matrix of current solution set to achieve an Eigen coordinate system for crossover operator. The covariance matrix learning eliminates the coordinate system dependence from differential evolution and improves the performance in multivariate correlation problems. Moreover, we embed bimodal distribution parameter setting in our algorithm. Bimodal distribution for crossover probability is composed of two normal distributions with different mean values, and makes offspring produced by crossover operator distribute around the parents with high probability. Bimodal distribution for mutation factor is composed of two Cauchy distributions with different medians, and balances global exploration and local exploitation. LYDE has been tested on 25 benchmark functions of CEC2005 test suite. The experimental results suggest that LYDE is efficient for global optimization, especially rotated problems and is robust to noise. LYDE has a faster convergence rate and a higher precision than five recent algorithms (i.e. jDE, SaDE, JADE, EPSDE, CoDE) on 25 benchmark functions. The experiment also suggests both covariance matrix learning approach and bimodal parameter setting are critical to LYDE and the two components have a cooperative effect. The parameter sensitivity experiment shows LYDE with sample rate 0.4 and learning rate 0.65 has a robust performance on test suite.
In addition, we propose an approach that mapping the continuous vector space to the discrete solution space based on the minimum Euclidean distance principle. By the above method, keeping the original structure of DE, the application field of LYDE is extended from the continuous problems to a classical discrete combinatorial optimization problem—set cover problem on ichnography, which is an abstraction of emergency facility location. The experiment result shows LYDE has an excellent performance and has a faster convergence rate and a higher precision than genetic algorithm. The application of LYDE for discrete problem is promising.
引文
[1]Storn R., Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces [TR]. Berkeley, CA, 1995
[2]Storn R., Price K.V. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces [J]. J. Global Opt.,1997,11(4): 341-359
[3]Liang J.J., Runarsson T.P., Mezura-Montes E., Clerc M., et al. Problem definitions and evaluation criteria for CEC 2006. Special Session on Constrained Real-Parameter Optimization, Technical Report, Nanyang Technological University, Singapore,2006
[4]Zhang Q., Zhou A., Zhao S. Z., et al. Multiobjective optimization test instances for the CEC 2009 special session and competition. Technical Report CES-887, University of Essex and Nanyang Technological University,2008
[5]Wang L., Li L.-P. Fixed-Structure H ∞ Controller Synthesis Based on Differential Evolution with Level Comparison [J], IEEE Trans. Evolut. Comput.,2011,15(1):341-359
[6]Mininno E., Neri F., Cupertino F., Naso D. Compact Differential Evolution[J], IEEE Trans. Evolut. Comput.,2011,15(1):120-129
[7]Greenwood G. W. Using Differential Evolution for a Subclass of Graph Theory Problems [J], IEEE Trans. Evolut. Comput.,2009,13(5):1190-1192
[8]Das S., Abraham A., Konar A. Automatic Clustering Using an Improved Differential Evolution Algorithm [J], IEEE Trans. Syst. Man Cybern. Part A, 2008,38(1):218-236
[9]Sun J., Zhang Q., Tsang EPK. DE/EDA:A new evolutionary algorithm for global optimization [J]. Information Sciences,2005, (169):249-262
[10]Zhang J, Sanderson A. C. JADE:Adaptive Differential Evolution with Optional External Archive [J]. IEEE Transactions on Evolutionary Computation,2009,13(5):945-958
[11]Noman N., Iba H. Accelerating Differential Evolution Using an Adaptive Local Search [J]. IEEE Transactions on Evolutionary Computation,2008, 12(1):107-125
[12]谢晓锋,张文俊,张国瑞等.差异演化的实验研究[J].控制与决策,2004,19(1)：49-52,56
[13]Chiou JP, Chang CF, Su CT. Variable scaling hybrid differential evolution for solving network reconfiguration of distribution systems [J]. IEEE Trans. on Power Systems,2005,20 (2):668-674
[14]Gong W., Cai Z., Jiang L. Enhancing the performance of differential evolution using orthogonal design method [J]. Applied Mathematics and Computation, 2008,206(1):56-69
[15]方强,陈德钊,俞欢军等.基于优进策略的差分进化算法及其化工应用[J].化工学报,2004,55(4)：598-602
[16]Mallipeddi R., Suganthan P. N. Differential evolution algorithm with ensemble of parameters and mutation and crossover strategies [C], In:Swarm Evolutionary and Memetic Computing Conference, Chennai, India,2010
[17]Wang Y., Cai Z., Zhang Q., Differential Evolution with Composite Trail Vector Generation Strategies and Control Parameters [J], IEEE Trans. Evolut. Comput.,2011,15(1):55-66
[18]Nelder J. A., Mead R. A Simplex Method for Function Minimization [J], Computer Journal,1965,7(4):308-313
[19]Price W. L. A controlled random search procedure for global optimization [J], Computer Journal,1977,20(4):367-370
[20]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策,2007,22(7)：721-729
[21]Price K., Storn R., Lampinen J. Differential Evolution-A Practical Approach to Global Optimization [M]. Berlin, Germany:Springer,2005
[22]Das S., Suganthan P. N. Differential Evolution:A Survey of the State-of-the-Art [J], IEEE Trans. Evolut. Comput.,2011,15(1):4-31
[23]Beyer H.-G., Deb K. On Self-Adaptive Features in Real-Parameter Evolutionary Algorithms [J], IEEE Trans. Evolut. Comput.,2001,5(3): 250-270
[24]H.-G. Beyer On the Dynamics of EAs without selection [J], Foundations of Genetic Algorithms,1999,5-26
[25]Zaharie D. Critical values for the control parameters of differential evolution algorithms [C], In:Proc.8th Int. Mendel Conf. Soft Comput.,2002,62-67
[26]Zhang J, Sanderson A. C. Adaptive Differential Evolution-A Robust Approach to Multimodal Problem Optimization [M]. Berlin, Germany:Springer,2009
[27]Kita H. A Comparison Study of Self-Adaptation in Evolution Strategies and Real-Coded Genetic Algorithms [J], Evolut. Comput.,2001,9(2):223-241
[28]Fan H. Y., Lampinen J. A trigonometric mutation operator to differential evolution [J], J. Global Optim.,2003,27(1):105-129
[29]Rahnamayan S., Tizhoosh H. R., Salama M. M. A. Opposition-based differential evolution [J], IEEE Trans. Evolut. Comput.,2008,12(1):64-79
[30]Price K. V. An introducation to differential evolution [M], in New Ideas Optimization. London, U.K.:McGraw-Hill,1999,293-298
[31]Liu J., Lampinen J. A fuzzy adaptive differential evolution algorithm [J], Soft Computing-A Fusion of Foundations, Methodologies and Applications,2005, 9(6):448-462
[32]Brest J., Greiner S., Boskovic B., Mernik M., Zumer V. Self-adapting control parameters in differential evolution:A comparative study on numerical benchmark problems [J], IEEE Trans. Evolut. Comput.,2006,10(6):646-657
[33]Qin K., Huang V. L., Suganthan P. N. Differential evolution algorithm with strategy adaptation for global numerical optimization [J], IEEE Trans. Evolut. Comput.,2009,13(2):398-417
[34]Patton A. L., Goodman E. D., Punch III W. F. Beyond Encoding: Rotationally Invariant Operators for Evolutionary Computation[C], submitted to Genetic Evolut. Comput. Conf., (GECCO 99)
[35]Tsutsui S., Yamamura M., Higuchi T. Multi-parent Recombination with Simplex Crossover in Real Coded Genetic Algorithms [C], In Proc. of the Genetic Evolut. Comput. Conf. (GECCO 1999),657-664
[36]Ono I., Kita H., Kobayashi S. A Robust Real-Coded Genetic Algorithm using Unimodal Normal Distribution Crossover Augmented by Uniform Crossover: Effects of Self-Adaptation of Crossover Probabilities [C], In Proc. Genetic Evolut. Comput. Conf. (GECCO 1999),496-503
[37]Deb K., Anand A., Joshi D. A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization [J], Evolut. Comput.,2002,10(4): 371-395
[38]Hansen N., Ostermeier A. Completely derandomized self-adaptation in evolution strategies [J], Evolut. Comput.,2001,9(2):159-195
[39]Takahashi M., Kita H. A Cross Operator Using Independent Component Analysis for Real-Coded Genetic Algorithms [J], In Proc. IEEE Conf. Evolut. Comput.,2001,643-649
[40]Deb K., Beyer H.-G. Self-Adaptive Genetic Algorithms with Simulated Binary Crossover [J], Evolut. Comput.,2001,9(2):197-221
[41]Suganthan P. N., Hansen N., Liang J. J., et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization [EB/OL]. Available:http://www.ntu.edu.sg/home/EPNSugan
[42]Liang J. J., Qin A. K., Suganthan P. N., S. Baskar Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [J], IEEE Trans. Evolut. Comput.,2006,10(3):281-295
[43]Garcia-Martinez, Lozano M., Herrera F., Molina D., Sanchez A.M. Global and local real-coded genetic algorithms based on parent-centric crossover operators [J], European Journal of Operational Research,2008,185: 1088-1113
[44]Karp R. M. Reducibility among Combinatorial Problems [M], In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York:Plenum.1972,85-103
[45]蔡自兴.人工智能及其应用[M].清华大学出版社,2004
[46]Beasley J. E., Chu P. C. A genetic algorithm for the set covering problem. European Journal of Operational Research [J].1996,99(2):392-404
[47]潘全科,王凌,高亮.离散微粒子群优化算法的研究进展[J].控制与决策,2009,24(10)：1441-1449
[48]周培德.计算几何：算法分析与设计(第2版)[M].清华大学出版社.1995
[49]2009年研究生数学建模竞赛B题数据[EB/OL], http://www.shumo.com/— home/html/481.html,2009
[50]杨丰梅,华国伟,邓猛等.选址问题研究的若干进展.运筹与管理.2005,14(6)：1-7
[51]Prugel-Bennett A. Benefits of a Population:Five Mechanisms That Advantage Population-Based Algorithms [J], IEEE Trans. Evolut. Comput.,2010,14(4): 500-517
[52]Peng F., Tang K., Chen G., Yao X. Population-Based Algorithm Portfolios for Numerical Optimization [J], IEEE Trans. Evolut. Comput.,2010,14(5): 782-800
[53]Balas E., Carrera M. C. A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering [J]. Operation Research.1996,44(6):875-890
[54]Das S., Abraham A., Chakraborty U. K., Konar A. Differential evolution using a neighborhood-based mutation operator [J], IEEE Trans. Evolut. Comput., 2009,13(3):526-553
[55]Salomon R. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms [J], BioSystems,1996,39(3):263-278
[2]Storn R., Price K.V. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces [J]. J. Global Opt.,1997,11(4): 341-359
[3]Liang J.J., Runarsson T.P., Mezura-Montes E., Clerc M., et al. Problem definitions and evaluation criteria for CEC 2006. Special Session on Constrained Real-Parameter Optimization, Technical Report, Nanyang Technological University, Singapore,2006
[4]Zhang Q., Zhou A., Zhao S. Z., et al. Multiobjective optimization test instances for the CEC 2009 special session and competition. Technical Report CES-887, University of Essex and Nanyang Technological University,2008
[5]Wang L., Li L.-P. Fixed-Structure H ∞ Controller Synthesis Based on Differential Evolution with Level Comparison [J], IEEE Trans. Evolut. Comput.,2011,15(1):341-359
[6]Mininno E., Neri F., Cupertino F., Naso D. Compact Differential Evolution[J], IEEE Trans. Evolut. Comput.,2011,15(1):120-129
[7]Greenwood G. W. Using Differential Evolution for a Subclass of Graph Theory Problems [J], IEEE Trans. Evolut. Comput.,2009,13(5):1190-1192
[8]Das S., Abraham A., Konar A. Automatic Clustering Using an Improved Differential Evolution Algorithm [J], IEEE Trans. Syst. Man Cybern. Part A, 2008,38(1):218-236
[9]Sun J., Zhang Q., Tsang EPK. DE/EDA:A new evolutionary algorithm for global optimization [J]. Information Sciences,2005, (169):249-262
[10]Zhang J, Sanderson A. C. JADE:Adaptive Differential Evolution with Optional External Archive [J]. IEEE Transactions on Evolutionary Computation,2009,13(5):945-958
[11]Noman N., Iba H. Accelerating Differential Evolution Using an Adaptive Local Search [J]. IEEE Transactions on Evolutionary Computation,2008, 12(1):107-125
[12]谢晓锋,张文俊,张国瑞等.差异演化的实验研究[J].控制与决策,2004,19(1)：49-52,56
[13]Chiou JP, Chang CF, Su CT. Variable scaling hybrid differential evolution for solving network reconfiguration of distribution systems [J]. IEEE Trans. on Power Systems,2005,20 (2):668-674
[14]Gong W., Cai Z., Jiang L. Enhancing the performance of differential evolution using orthogonal design method [J]. Applied Mathematics and Computation, 2008,206(1):56-69
[15]方强,陈德钊,俞欢军等.基于优进策略的差分进化算法及其化工应用[J].化工学报,2004,55(4)：598-602
[16]Mallipeddi R., Suganthan P. N. Differential evolution algorithm with ensemble of parameters and mutation and crossover strategies [C], In:Swarm Evolutionary and Memetic Computing Conference, Chennai, India,2010
[17]Wang Y., Cai Z., Zhang Q., Differential Evolution with Composite Trail Vector Generation Strategies and Control Parameters [J], IEEE Trans. Evolut. Comput.,2011,15(1):55-66
[18]Nelder J. A., Mead R. A Simplex Method for Function Minimization [J], Computer Journal,1965,7(4):308-313
[19]Price W. L. A controlled random search procedure for global optimization [J], Computer Journal,1977,20(4):367-370
[20]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策,2007,22(7)：721-729
[21]Price K., Storn R., Lampinen J. Differential Evolution-A Practical Approach to Global Optimization [M]. Berlin, Germany:Springer,2005
[22]Das S., Suganthan P. N. Differential Evolution:A Survey of the State-of-the-Art [J], IEEE Trans. Evolut. Comput.,2011,15(1):4-31
[23]Beyer H.-G., Deb K. On Self-Adaptive Features in Real-Parameter Evolutionary Algorithms [J], IEEE Trans. Evolut. Comput.,2001,5(3): 250-270
[24]H.-G. Beyer On the Dynamics of EAs without selection [J], Foundations of Genetic Algorithms,1999,5-26
[25]Zaharie D. Critical values for the control parameters of differential evolution algorithms [C], In:Proc.8th Int. Mendel Conf. Soft Comput.,2002,62-67
[26]Zhang J, Sanderson A. C. Adaptive Differential Evolution-A Robust Approach to Multimodal Problem Optimization [M]. Berlin, Germany:Springer,2009
[27]Kita H. A Comparison Study of Self-Adaptation in Evolution Strategies and Real-Coded Genetic Algorithms [J], Evolut. Comput.,2001,9(2):223-241
[28]Fan H. Y., Lampinen J. A trigonometric mutation operator to differential evolution [J], J. Global Optim.,2003,27(1):105-129
[29]Rahnamayan S., Tizhoosh H. R., Salama M. M. A. Opposition-based differential evolution [J], IEEE Trans. Evolut. Comput.,2008,12(1):64-79
[30]Price K. V. An introducation to differential evolution [M], in New Ideas Optimization. London, U.K.:McGraw-Hill,1999,293-298
[31]Liu J., Lampinen J. A fuzzy adaptive differential evolution algorithm [J], Soft Computing-A Fusion of Foundations, Methodologies and Applications,2005, 9(6):448-462
[32]Brest J., Greiner S., Boskovic B., Mernik M., Zumer V. Self-adapting control parameters in differential evolution:A comparative study on numerical benchmark problems [J], IEEE Trans. Evolut. Comput.,2006,10(6):646-657
[33]Qin K., Huang V. L., Suganthan P. N. Differential evolution algorithm with strategy adaptation for global numerical optimization [J], IEEE Trans. Evolut. Comput.,2009,13(2):398-417
[34]Patton A. L., Goodman E. D., Punch III W. F. Beyond Encoding: Rotationally Invariant Operators for Evolutionary Computation[C], submitted to Genetic Evolut. Comput. Conf., (GECCO 99)
[35]Tsutsui S., Yamamura M., Higuchi T. Multi-parent Recombination with Simplex Crossover in Real Coded Genetic Algorithms [C], In Proc. of the Genetic Evolut. Comput. Conf. (GECCO 1999),657-664
[36]Ono I., Kita H., Kobayashi S. A Robust Real-Coded Genetic Algorithm using Unimodal Normal Distribution Crossover Augmented by Uniform Crossover: Effects of Self-Adaptation of Crossover Probabilities [C], In Proc. Genetic Evolut. Comput. Conf. (GECCO 1999),496-503
[37]Deb K., Anand A., Joshi D. A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization [J], Evolut. Comput.,2002,10(4): 371-395
[38]Hansen N., Ostermeier A. Completely derandomized self-adaptation in evolution strategies [J], Evolut. Comput.,2001,9(2):159-195
[39]Takahashi M., Kita H. A Cross Operator Using Independent Component Analysis for Real-Coded Genetic Algorithms [J], In Proc. IEEE Conf. Evolut. Comput.,2001,643-649
[40]Deb K., Beyer H.-G. Self-Adaptive Genetic Algorithms with Simulated Binary Crossover [J], Evolut. Comput.,2001,9(2):197-221
[41]Suganthan P. N., Hansen N., Liang J. J., et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization [EB/OL]. Available:http://www.ntu.edu.sg/home/EPNSugan
[42]Liang J. J., Qin A. K., Suganthan P. N., S. Baskar Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [J], IEEE Trans. Evolut. Comput.,2006,10(3):281-295
[43]Garcia-Martinez, Lozano M., Herrera F., Molina D., Sanchez A.M. Global and local real-coded genetic algorithms based on parent-centric crossover operators [J], European Journal of Operational Research,2008,185: 1088-1113
[44]Karp R. M. Reducibility among Combinatorial Problems [M], In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York:Plenum.1972,85-103
[45]蔡自兴.人工智能及其应用[M].清华大学出版社,2004
[46]Beasley J. E., Chu P. C. A genetic algorithm for the set covering problem. European Journal of Operational Research [J].1996,99(2):392-404
[47]潘全科,王凌,高亮.离散微粒子群优化算法的研究进展[J].控制与决策,2009,24(10)：1441-1449
[48]周培德.计算几何：算法分析与设计(第2版)[M].清华大学出版社.1995
[49]2009年研究生数学建模竞赛B题数据[EB/OL], http://www.shumo.com/— home/html/481.html,2009
[50]杨丰梅,华国伟,邓猛等.选址问题研究的若干进展.运筹与管理.2005,14(6)：1-7
[51]Prugel-Bennett A. Benefits of a Population:Five Mechanisms That Advantage Population-Based Algorithms [J], IEEE Trans. Evolut. Comput.,2010,14(4): 500-517
[52]Peng F., Tang K., Chen G., Yao X. Population-Based Algorithm Portfolios for Numerical Optimization [J], IEEE Trans. Evolut. Comput.,2010,14(5): 782-800
[53]Balas E., Carrera M. C. A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering [J]. Operation Research.1996,44(6):875-890
[54]Das S., Abraham A., Chakraborty U. K., Konar A. Differential evolution using a neighborhood-based mutation operator [J], IEEE Trans. Evolut. Comput., 2009,13(3):526-553
[55]Salomon R. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms [J], BioSystems,1996,39(3):263-278