Research on Increasing the Performance of Evolutionary Algorithm in Searching Robust Optimal Solutions Based on Quasi-Monte Carlo Method
ZHU Yun-Fei1,2, LUO Biao2, ZHENG Jin-Hua2, CAI Zi-Xing1
1.School of Information Science and Engineering, Central South University, Changsha 410083 2.Collage of Information Engineering, Xiangtan University, Xiangtan 411105
Abstract:Robust optimal solution is of great significance in engineering application. It is one of the most important and difficult topics in evolutionary computation. Monte Carlo Integral (MCI) is generally used to approximate effective objective function (EOF) in searching robust optimal solution with evolutionary algorithm (EA). However, due to the low accuracy in existing crude Monte Carlo (C-MC) method, the performance of searching robust optimal solution with EA is unsatisfactory. Therefore, a Quasi-Monte Carlo (Q-MC) method is proposed to estimate EOF. The experimental results demonstrate that the proposed Q-MC methods-SQRT sequence, SOBOL sequence and Korobov Lattice approximate EOF more precisely compared with C-MC method, and consequently, the performance of searching robust optimal solution with EA is improved.
朱云飞,罗彪,郑金华,蔡自兴. 基于拟蒙特卡罗方法的进化算法搜索鲁棒最优解的性能提高研究[J]. 模式识别与人工智能, 2011, 24(2): 201-209.
ZHU Yun-Fei, LUO Biao, ZHENG Jin-Hua, CAI Zi-Xing. Research on Increasing the Performance of Evolutionary Algorithm in Searching Robust Optimal Solutions Based on Quasi-Monte Carlo Method. , 2011, 24(2): 201-209.
[1] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor, USA: University of Michigan Press, 1975 [2] Jensen M T. Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms. IEEE Trans on Evolutionary Computation, 2003, 7(3): 275-288 [3] Thompson A. Evolutionary Techniques for Fault Tolerance // Proc of the UKACC International Conference on Control. Exeter, UK, 1996, 693-698 [4] Anthony D K, Keane A J. Robust-Optimal Design of a Lightweight Space Structure Using a Genetic Algorithm. AIAA Journal, 2003, 41(8): 1601-1604 [5] Jin Y, Branke J. Evolutionary Optimization in Uncertain Environments-A Survey. IEEE Trans on Evolutionary Computation, 2005, 9(3): 303-317 [6] Yang S, Ong Y S, Jin Y, eds. Evolutionary Computation in Dynamic and Uncertain Environments. Berlin: Springer, 2007 [7] Branke J, Schmidh C. Faster Convergence by Means of Fitness Estimation. Soft Computing, 2005, 9(1): 13-20 [8] Tsutsui S, Ghosh A. Genetic Algorithm with a Robust Solution Searching Scheme. IEEE Trans on Evolutionary Computation, 1997, 1(3): 201-208 [9] Jin Y, Sendhoff B. Trade-Off between Performance and Robustness: An Evolutionary Multiobjective Approach // Proc of the 2nd International Conference on Evolutionary Multi-Criterion Optimaization. Faro, Portugal, 2003: 237-251 [10] Lim D, Ong Y S, Jin Y, et al. Inverse Multi-Objective Robust Evolutionary Design. Genetic Programming and Evolvable Machines, 2006, 7(4): 383-404 [11] Deb K, Gupta H. Searching for Robust Pareto-Optimal Solutions in Multi-Objective Optimization // Proc of the 3rd International Conference on Evolutionary Multi-Criterion Optimization. Guanajuato, Mexico. 2005: 150-164 [12] Barrico C, Antune C H. Robustness Analysis in Multi-Objective Optimization Using a Degree of Robustness Concept // Proc of the 2006 IEEE Congress on Computation Intelligence. Vancouver, Canada, 2006: 6778-6783 [13] Luo B, Zheng J H. A New Methodology for Searching Robust Pareto Optimal Solutions with MOEAs // Proc of the 2008 IEEE Congress on Evolutionary Computation. Hongkong, China, 2008: 580-586 [14] Deb K, Agrawal R B. Simulated Binary Crossover for Continuous Search Space. Complex Systems. 1995, 9(6): 115-148 [15] Deb K, Beyer H G. Self-Adaptive Genetic Algorithms with Simulated Binary Crossover. Evolutionary Computation, 2001, 9(2): 197-221 [16] Deb K, Goyal M. A Combined Genetic Adaptive Search (GeneAS) for Engineering Design. Computer Science and Informatics, 1996, 26(4): 30-45 [17] Niederreiter H. Random Number Generation and Quasi-Monte Carlo Methods. Philadelphia: Society for Indnstrial and Applied Mathematics, 1992 [18] Niederreiter H. Quasi-Monte Carlo Methods and Pseudo-Random Numbers. Bulletin of the American Mathematical Society, 1978, 84: 957-1041 [19] Hua L K, Wang Y. Applications of Number Theory to Numerical Analysis. Berlin: Springer-Verlag, 1981 [20] Zaremba S K. Some Applications of Multidimensional Integration by Parts. Annales Polonici Mathematici, 1968, 21: 85-96, [21] Beck J, Chen W. Irregularities of Distribution. Cambridge: Cambridge University Press, 1987 [22] Borel J P, Pagès G, Xiao Y. Suites à Discrépance Faible Et Intégration Numérique // Bouleau N, Talay O, eds. Probabilités Numériques. France: INRIA, 1991 [23] Sobol I M. Uniformly Distributed Sequences with an Additional Uniform Property. USSR Computational Mathematics and Mathematical Physics, 1976, 16(5): 236-242 [24] Sobol I M. The Distribution of Points in a Cube and the Approximate Evaluation of Integrals. USSR Computational Mathematics and Mathematical Physics, 1967, 7(4): 86-112 [25] Fox B L. Algorithm 659: Implementing Sobols Quasirandom Sequence Generator. ACM Trans on Mathematical Software, 1988, 14(1): 88-100 [26] Korobov N M. The Approximate Computation of Multiple Integrals. Doklady Akademii Nauk SSSR, 1959, 124: 1207-1210 (in Russian) [27] Hlawka E. Funktionen von Beschrnkter Variation in Dertheorie Dergleichverteilung. Annalidi Matematica Puraed Applicata, 1961, 54(4): 325-333 [28] Branke J. Evolutionary Optimization in Dynamic Environments. Norwell, MA: Kluwer, 2002 [29] Beyer H, Olhofer M, Sendhoff B. The Influence of Stochastic Quality Functions on Evolutionary Search // Tan K C, Lim M H, Yao X, Wang L, eds. Recent Advances in Simulated Evolution and Learning. New York, USA: World Scientific, 2004: 152-172 [30] Branke J. Creating Robust Solutions by Means of an Evolutionary Algorithm // Proc of the 5th International Conference on Parallel Problem Solving from Nature. Amsterdam, The Netherlands, 1998: 119-128