Adaptive sampling immune algorithm solving joint chance-constrained programming
Tóm tắt
This work investigates one immune optimization algorithm in uncertain environments, solving linear or nonlinear joint chance-constrained programming with a general distribution of the random vector. In this algorithm, an a priori lower bound estimate is developed to deal with one joint chance constraint, while the scheme of adaptive sampling is designed to make empirically better antibodies in the current population acquire larger sample sizes in terms of our sample-allocation rule. Relying upon several simplified immune metaphors in the immune system, we design two immune operators of dynamic proliferation and adaptive mutation. The first picks up those diverse antibodies to achieve proliferation according to a dynamical suppression radius index, which can ensure empirically potential antibodies more clones, and reduce noisy influence to the optimized quality, and the second is a module of genetic diversity, which exploits those valuable regions and finds those diverse and excellent antibodies. Theoretically, the proposed approach is demonstrated to be convergent. Experimentally, the statistical results show that the approach can obtain satisfactory performances including the optimized quality, noisy suppression and efficiency.
Tài liệu tham khảo
W. van Ackooij, R. Zorgati, R. Henrion, et al. Chance constrained programming and its applications to energy management. Stochastic Optimization — Seeing the Optimal for the Uncertain. I. Dritsas (Ed.). Rijeka: InTech, 2011: 291–320.
B. Liu, R. Zhao. Stochastic Programming and Fuzz Programming. Beijing: Tsinghua University Press, 1998.
S. Ahmed, A. Shapiro. Solving chance-constrained stochastic programs via sampling and integer programming. INFORMS: Tutorials in Operations Research. Washington, 2008: http://www2.isye.gatech.edu/?sahmed/cctutorial.pdf.
A. Nemirovski, A. Shapiro. Convex approximations of chance constrained programs. Society for Industrial and Applied Mathematics, 2006, 17(4): 969–996.
L. Hong, Y. Yang, L. Zhang. Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach. Operations Research, 2011, 59(3): 617–630.
R. Henrion, C. Strugarek. Convexity of chance constraints with independent random variables. Computational Optimization and application, 2008, 41(2): 263–276.
S. Ahmed. Convex relaxations of chance constrained optimization problems. Optimization Letters, 2013: DOI 10.1007/s11590-013-0624-7.
D. Dasgupta, S. Yu, F. Nino. Recent advances in artificial immune systems: Models and applications. Applied Soft Computing, 2011, 11(2): 1574–1587.
A. Simões, E. Costa. CHC-based algorithms for the dynamic traveling salesman problem. Applications of Evolutionary Computation. Heidelberg: Springer-Verlag, 2011: 354–363.
K. Trojanowski, S. T. Wierzchoń. Immune-based algorithms for dynamic optimization. Information Sciences, 2009, 179(10): 1495–1515.
L. N. de Castro, J. Timmis. Artificial Immune Systems. A New Computational Iintelligence Approach. London: Springer-Verlag, 2002.
V. S. Aragó, S. C. Esquivel. Optimizing constrained problems through a T-Cell. Journal of Computer Science and Technology, 2008, 8(3):158–165.
A. Shapiro. Monte Carlo simulation approach to stochastic programming. Proceedings of the Winter Simulation Simulation Conference. Arlington: IEEE, 2001: 428–431.
J. Luedtke, S. Ahmed. A sample approximation approach for optimization with probabilistic constraints. SIAM Journal on Optimization, 2008, 19(2): 674–699.
B. K. Pagnoncelli, S. Ahmed, A. Shapiro. Sample average approximation method for chance constrained programming: Theory and applications. Journal of Optimization Theory and Applications, 2009, 142(2): 399–416.
B. Liu, R. Zhao, G. Wang. Uncertainty Programming and Its Applications. Beijing: Tsinghua University Press, 2003.
X. Ning. Solving stochastic chance-constrained programming problems with hybrid intelligent algorithm. Computer Engineering and Applications, 2010, 46(22): 43–46.
C. A. Poojari, B. Varghese. Genetic algorithm based technique for solving chance constrained problems. European Journal of Operational Research, 2008, 185(3): 1128–1154.
M. Brand. Reformulation of general chance constrained problems using the penalty functions. Stochastic Programming E-print Series (SPEPS), 2010: http://edoc.hu-berlin.de/series/speps/2010-2/PDF/2.pdf.
J. L. Higle, L. Zhao. Adaptive and Nonadaptive Samples in Solving Stochastic Linear Programs: A Computational Investigation. Tucson: The University of Arizona, 2004.
D. H. Loughlin, S. R. Ranjithan. Chance-constrained genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference. San Francisco: Morgan Kaufmann, 1999: 369–376.
C. Chen, J. Lin. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems: Theory and Applications, 2000, 10(3): 251–270.
C. Chen, D. He. Efficient simulation budget allocation for selecting an optimal subset. Journal on Computing, 2008, 20(4): 579–595.
K. H. Sahin, U. M. Diwekar. Better optimization of nonlinear uncertain systems (BONUS): A new algorithm for stochastic programming using reweighting through kernel density estimation. Annals of Operations Research, 2004, 132(1/4): 47–68.
Z. Zhang. Noisy immune optimization for chance-constrained programming problems. Applied Mechanics and Materials, 2011, 48(49): 740–744.
Z. Zhang, X. Tu. Immune algorithm with adaptive sampling in noisy environments and its application to stochastic optimization problems. IEEE Computational Intelligence Magazine, 2007, 2(4): 29–40.
M. W. Tanner. New Solution Methods for Joint Chance-constrained Stochastic Programs with Random Left-hand Side. Texas: Texas A & M University, 2009.
M. W. Tanner, L. Ntaimo. IIS branch-and-cut for joint chance-constrained programs with random technology matrices. European Journal of Operational Research, 2010, 207(1): 290–296.
U. Özcan. Balancing stochastic two-sided assembly lines: A chanceconstrained, piecewise-linear, mixed integer program and a simulated annealing algorithm. European Journal of Operational Research, 2010, 205(1): 81–97.
Q. Bin. An immune algorithm for optional selection problem of investment projects. The 5th International Conference on Natural Computation. Tianjin: IEEE, 2009: 8–11.
S. Mao, Y. Cheng, X. Pu. Probabilistic Theory and Mathematical Statistic Tutorial. Beijing: Higher Education Press, 2004.
X. Huang, Z. Zhang, C. He, et al. Modern Intelligent Algorithm: Theory and Applications. Beijing: Science Press, 2005.