文章快速检索 高级检索

1. 贵州大学 大数据与信息工程学院, 贵阳 550025;
2. 贵州大学 理学院 系统科学及信息技术研究所, 贵阳 550025

Micro-immune optimization algorithm for solving probabilistic optimization problems
ZHANG Zhuhong1 , ZHANG Renchong2
1. College of Big Data & Information Engineering, Guizhou University, Guiyang 550025, China ;
2. Institute of System Science and Information Technology, College of Science, Guizhou University, Guiyang 550025, China
Received: 2015-09-01; Accepted: 2015-10-18; Published online: 2016-03-15
Foundation item: National Natural Science Foundation of China (61563009); Doctoral Fund of Ministry of Education of China (20125201110003); Graduate Innovation Fund of Guizhou University (2015057)
Corresponding author. Tel.:0851-83629086,E-mail:zhzhang@gzu.edu.cn
Abstract: This paper investigates a micro-immune optimization algorithm for the problem of nonlinear probabilistic optimization with unknown random variable distribution. In the design of algorithm, an implicit parallel optimization structure is developed based on the danger theory, while individuals can be identified through a proposed adaptive sampling method. Those danger regions and subpopulations can be decided dynamically through regulating danger radiuses, and meanwhile multiple kinds of mutation strategies are used to guide individuals to move towards multiple directions. Such algorithm has the merits of small population, few adjustable parameters, structural simplicity and so forth; the computational complexity depends on iteration number, variable dimension and population size. Based on the theoretical test examples and a bus scheduling problem, numerically comparative experiments show that the proposed algorithm possesses some advantages of search efficiency and optimized effect, and has potential for solving complex probabilistic optimization problems.
Key words: single-objective P-model     immune optimization     danger theory     adaptive sampling     micro population

1 问题描述

2 危险理论

 图 1 μIOA的流程图 Fig. 1 Flowchart of μIOA
3 算法描述

 (1)

 (2)

 (3)

B1中B细胞克隆实施高斯变异，B2中B细胞克隆实施柯西变异，B3中B细胞克隆实施多项式变异，B4~Bd-1中B细胞克隆实施非均匀变异，Bd中B细胞克隆实施柯西变异，获得变异后的群体B1*,B2*,…,Bd*

1) 危险半径更新： x i的危险半径为

 (4)

2) 群体分割：基于危险半径更新，A中落入超正方体V1中的B细胞构成未感染群B1，然后将B1中的B细胞从A中删除，余下的B细胞中，由亲和力最高的B细胞和其危险区域按同样方式产生子群B2，依此重复，直到产生最后一个子群，不妨设共有d个子群。第2~d-1个子群称为易感染群，第d个子群称为已感染子群Bd

3) 自适应采样：对于规模为J的B细胞群C，由于随机因素的影响，很容易误认为较差B细胞是优质的，而最好的B细胞是劣质的，因此为了削减计算开销和提高寻优效率，优质B细胞被分配大的样本大小，而劣质B细胞被分配小的样本大小。为此，记C={ x 1,x 2,…,x J}。群体C的样本大小设置为

 (5)

B细胞 x i依据式(6)获得样本大小:

 (6)

 (7)

 (8)
4 计算复杂度分析

 (9)

5 数值实验

 σ 算法 min max mean St.Dev CI AR/(′′) 1 Xiao-SPSO 1.280 1 1.423 1 1.322 8 0.028 6 [1.318 1,1.327 6] 1.53 Ai-SPSO 1.282 2 1.432 8 1.324 6 0.030 5 [1.319 5,1.329 6] 1.50 GA 1.324 8 1.883 1 1.537 8 0.135 4 [1.515 4,1.560 3] 1.49 μIOA 1.277 9 1.377 3 1.311 9 0.019 7 [1.308 7,1.315 2] 0.63 10 Xiao-SPSO 12.833 4 13.618 8 13.140 5 0.176 1 [13.111 3,13.169 8] 1.50 Ai-SPSO 12.754 5 14.009 9 13.160 4 0.252 5 [13.118 5,13.202 3] 1.50 GA 12.883 5 15.606 0 13.888 8 0.589 3 [13.790 9,13.986 6] 1.49 μIOA 12.781 7 13.549 6 13.111 2 0.179 8 [13.081 4,13.141 1] 0.64 30 Xiao-SPSO 38.273 9 41.828 7 39.319 6 0.685 5 [39.205 7,39.433 4] 1.50 Ai-SPSO 38.285 0 42.274 9 39.403 7 0.661 5 [39.293 8,39.513 5] 1.50 GA 38.743 7 45.725 2 40.830 7 1.367 3 [40.603 7,41.057 7] 1.50 μIOA 38.478 5 41.435 1 39.405 7 0.553 6 [39.313 7,39.497 6] 0.83 50 Xiao-SPSO 63.915 0 70.895 6 65.731 9 1.164 6 [65.538 5,65.925 3] 1.50 Ai-SPSO 63.732 3 68.823 8 65.573 3 1.075 8 [65.394 7,65.751 9] 1.50 GA 64.476 6 74.933 1 68.000 4 2.271 7 [67.623 2,68.377 6] 1.50 μIOA 63.883 7 70.992 7 66.456 7 1.517 0 [66.204 8,66.708 6] 1.15

 图 2 问题1的平均搜索曲线比较 Fig. 2 Comparison of average search curves for Problem 1

 σ 算法 min max mean St.Dev CI AR/(′′) 1 Xiao-SPSO 1.285 1 9.834 6 3.610 5 1.295 8 [3.395 3,3.825 6] 1.72 Ai-SPSO 1.817 6 12.659 6 4.329 7 1.502 6 [4.080 2,4.579 2] 1.68 GA 3.100 3 889.281 0 63.838 3 152.833 0 [38.461 9,89.214 7] 1.69 μIOA 1.287 3 5.873 1 2.417 6 1.102 2 [2.234 6,2.600 6] 0.75 10 Xiao-SPSO 12.863 9 19.934 3 15.711 2 1.337 6 [15.489 1,15.933 3] 1.70 Ai-SPSO 13.536 9 23.544 1 16.370 1 1.698 8 [16.088 0,16.652 1] 1.69 GA 15.483 2 318.454 0 36.822 2 52.716 7 [28.069 1,45.575 3] 1.68 μIOA 12.757 2 17.835 4 14.299 5 1.298 5 [14.083 9,14.515 1] 0.73 30 Xiao-SPSO 38.906 6 45.734 8 42.096 9 1.491 9 [41.849 2,42.344 7] 1.70 Ai-SPSO 38.364 2 46.901 1 42.886 8 1.669 9 [42.609 6,43.164 1] 1.68 GA 40.001 0 341.166 0 65.544 4 47.410 7 [57.672 3,73.416 5] 1.69 μIOA 39.064 8 44.282 8 41.080 8 1.362 3 [40.854 6,41.307 0] 0.73 50 Xiao-SPSO 64.491 9 73.881 8 68.375 1 1.692 6 [68.094 0,68.656 1] 1.69 Ai-SPSO 65.139 6 75.697 2 69.772 2 2.183 3 [69.409 7,70.134 8] 1.68 GA 68.293 3 349.510 0 98.991 4 58.956 7 [89.202 3,108.781 0] 1.68 μIOA 64.492 9 74.245 5 67.943 3 1.958 1 [67.618 2,68.268 4] 0.73

 图 3 问题2的平均搜索曲线比较 Fig. 3 Comparison of average search curves for Problem 2

 α 算法 min max mean St.Dev CI AR/(′′) 0.4 Xiao-SPSO -0.817 2 -0.028 9 -0.755 0 0.122 8 [-0.775 3,-0.734 6] 4.71 Ai-SPSO -0.811 7 -0.055 8 -0.708 7 0.183 5 [-0.739 1,-0.678 2] 4.63 GA -0.827 5 -0.747 8 -0.800 9 0.015 3 [-0.803 4,-0.798 3] 4.64 μIOA -0.823 6 -0.700 9 -0.790 6 0.020 8 [-0.794 1,-0.787 1] 1.11 0.9 Xiao-SPSO 1.212 4 2.181 2 1.518 6 0.237 2 [1.479 2,1.558 0] 2.73 Ai-SPSO 1.224 1 2.204 7 1.502 9 0.216 0 [1.467 0,1.538 7] 2.71 GA 1.186 7 2.059 6 1.350 3 0.192 0 [1.318 5,1.382 2] 2.71 μIOA 1.187 7 1.513 0 1.280 0 0.069 8 [1.268 4,1.291 6] 1.23

 图 4 问题3的平均搜索曲线比较 Fig. 4 Comparison of average search curves for Problem 3

 α 算法 min max mean St.Dev CI AR/(′′) 0.4 Xiao-SPSO 16 506.8 17 498.7 17 292.9 257.449 0 [17 250.1,17 335.6] 488.53 Ai-SPSO 14 149.9 17 430.8 16 770.5 547.360 0 [16 679.6,16 861.3] 507.26 GA 12 357.1 17 414.4 15 954.0 832.824 0 [15 815.7,16 092.2] 444.24 μIOA 17 231.9 17 505.4 17 436.5 52.579 8 [17 427.8,17 445.2] 269.99 0.9 Xiao-SPSO 16 010.2 17 029.9 16 752.5 289.599 0 [16 704.4,16 800.6] 493.90 Ai-SPSO 12 148.8 16 969.9 16 324.8 703.621 0 [16 208.0,16 441.7] 534.86 GA 13 081.7 16 857.9 15 573.8 781.660 0 [15 444.0,15 703.6] 516.73 μIOA 16 849.0 17 212.5 17 003.0 39.528 4 [16 996.4,17 009.5] 271.18

 图 5 问题4的平均搜索曲线比较 Fig. 5 Comparison of average search curves for Problem 4
6 结 论

1) 计算复杂度依赖于迭代数、变量维数和群体规模。

2) 具有群体规模小、可调参数少、自适应能力强和执行效率高等优点。

3) 搜索效果具有明显优势，噪声抑制能力强，对复杂的P-模型具有一定的应用潜力。

 [1] LIU B D. Uncertainty theory:A branch of mathematics for modeling human uncertainty[M]. Berlin: Springer-Varlag, 2010 : 81 -113. [2] 麻倩倩.一类随机机会约束规划的算法及应用研究[D].保定:华北电力大学,2006:1-28. MA Q Q.Research on the algorithm and application for a class of stochastic chance-constrained programming[D].Baoding:North China Electric Power University,2006:1-28(in Chinese). [3] LIU B D. Theory and practice of uncertain programming[M]. 2nd ed Berlin: Springer-Varlag, 2009 : 25 -55. [4] 丁晓东, 吴让泉, 邵世煌. 含有模糊和随机参数的混合机会约束规划模型[J]. 控制与决策, 2002, 17 (5) : 587 –590. DING X D, WU R Q, SHAO S H. Hybrid programming model with fuzzy and stochastic parameters[J]. Control and Decision, 2002, 17 (5) : 587 –590. (in Chinese) [5] NING Y,TANG W,WANG H.Hybrid genetic-SPSA algorithm based on random fuzzy simulation for chance-constrained programming[M]//WANG L,JIN Y.Fuzzy systems and know-ledge discovery.Berlin:Springer-Varlag,2005:332-335. [6] 刘宝碇, 赵瑞清. 随机规划与模糊规划[M]. 北京: 清华大学出版社, 1998 : 74 -94. LIU B D, ZHAO R Q. Stochastic programming and fuzzy programming[M]. Beijing: Tsinghua University Press, 1998 : 74 -94. (in Chinese) [7] LIU X, LIN L, ZANG D. Stochastic programming models and hybrid intelligent algorithm for unbalanced bidding problem[J]. Computer and Information Science, 2009, 2 (1) : 188 –194. [8] ZHANG H, HA M, XING H. Chance-constrained programming on Sugeno measure space[J]. Expert Systems with Applications, 2011, 38 (9) : 11527 –11533. DOI:10.1016/j.eswa.2011.03.029 [9] 肖宁, 曾建潮. 基于随机模拟与 PSO 算法相结合的随机机会约束规划算法[J]. 计算机应用与软件, 2009, 26 (4) : 40 –41. XIAO N, ZENG J C. Algorithm of stochastic chance-constrained programming based on combination of random simulation and PSO algorithm[J]. Computer Application and Software, 2009, 26 (4) : 40 –41. (in Chinese) [10] 肖宁. 求解随机机会约束规划的混合智能算法[J]. 计算机工程与应用, 2010, 46 (22) : 43 –46. XIAO N. Solving stochastic chance-constrained programming problems with hybrid intelligent algorithm[J]. Computer Engineering and Applications, 2010, 46 (22) : 43 –46. (in Chinese) [11] 卢福强, 黄敏, 王兴伟. 虚拟企业风险管理的机会约束规划模型及算法[J]. 信息与控制, 2009, 38 (4) : 399 –405. LU F Q, HUANG M, WANG X W. Chance-constraint programming model and algorithm for risk management of virtual enterprise[J]. Information and Control, 2009, 38 (4) : 399 –405. (in Chinese) [12] 艾宁宁.基于混合智能算法求解随机期望值模型和机会约束规划[D].西安:长安大学,2012:1-41. AI N N.A study hybrid algorithm solving stochastic expected value models and chance-constrained programming[D].Xi'an:Chang'an University,2012:1-41(in Chinese). http://cdmd.cnki.com.cn/article/cdmd-10710-1013017779.htm [13] XIAO N. An algorithm for solving stochastic chance-constrained programming problem[J]. Advanced Materials Research, 2014, 912-914 : 1138 –1141. DOI:10.4028/www.scientific.net/AMR.912-914 [14] 段富, 杨茸. 求解随机机会约束规划的混合智能算法及应用[J]. 计算机应用, 2012, 32 (8) : 2230 –2234. DUAN F, YANG R. Hybrid intelligent algorithm for solving stochastic chance-constrained programming and its application[J]. Journal of Computer Applications, 2012, 32 (8) : 2230 –2234. (in Chinese) [15] MATZINGER P. Tolerance,danger,and the extended family[J]. Annual Review of Immunology, 1994, 12 : 991 –1045. DOI:10.1146/annurev.iy.12.040194.005015 [16] WU D, GAN D Q, JIANG J N. An improved micro-particle swarm optimization algorithm and its application in transient stability constrained optimal power flow[J]. International Transactions on Electrical Energy Systems, 2014, 24 : 395 –411. DOI:10.1002/etep.v24.3 [17] VIVEROS-JIMÉNEZ F, MEZURA-MONTES E, GELBUKH A. Empirical analysis of a micro-evolutionary algorithm for numerical optimization[J]. International Journal of Physical Sciences, 2012, 7 (8) : 1235 –1258. [18] ABIYEV R H, TUNAY M. Optimization of high-dimensional functions through hypercube evaluation[J]. Computational Intelligence and Neuroscience, 2015, 2015 : 1 –11. [19] 许旺土, 何世伟, 宋瑞, 等. 多时段公交发车间隔优化的随机期望值模型[J]. 北京理工大学学报, 2009, 29 (8) : 676 –679. XU W T, HE S W, SONG R, et al. Stochastic expected value model for multiple bus headways optimization[J]. Transaction of Beijing Institute of Technology, 2009, 29 (8) : 676 –679. (in Chinese)

#### 文章信息

ZHANG Zhuhong, ZHANG Renchong

Micro-immune optimization algorithm for solving probabilistic optimization problems

Journal of Beijing University of Aeronautics and Astronsutics, 2016, 42(9): 1785-1794
http://dx.doi.org/10.13700/j.bh.1001-5965.2015.0563