Top > JACIII > An Evolutionary Algorithm for Black-Box Chance-Constrained Fun ...

single-jc.php

JACIII Vol.17 No.2 pp. 272-282
doi: 10.20965/jaciii.2013.p0272
(2013)

Paper:

Views over last 60 days: 1,106

An Evolutionary Algorithm for Black-Box Chance-Constrained Function Optimization

Kazuyuki Masutomi*, Yuichi Nagata**, and Isao Ono*

*Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology,

*4259 Nagatsuta-cho, Midori-ku, Yokohama 226-8502, Japan
Education Academy of Computational Life Sciences, Tokyo Institute of Technology,

**4259 Nagatsuta-cho, Midori-ku, Yokohama 226-8501, Japan

Received:
November 27, 2012
Accepted:
February 15, 2013
Published:
March 20, 2013
Creative Commons License
Keywords:
evolutionary algorithm, black-box chanceconstrained function optimization, uncertainty
Abstract
This paper presents an evolutionary algorithm for Black-Box Chance-Constrained Function Optimization (BBCCFO). BBCCFO is to minimize the expectation of the objective function under the constraints that the feasibility probability is higher than a userdefined constant in uncertain environments not given the mathematical expressions of objective functions and constraints explicitly. In BBCCFO, only objective function values of solutions and their feasibilities are available because the algebra expressions of objective functions and constraints cannot be used. In approaches to BBCCFO, a method based on an evolutionary algorithm proposed by Loughlin and Ranjithan shows relatively good performance in a realworld application, but this conventional method has a problem in that it requires many samples to obtain a good solution because it estimates the expectation of the objective function and the feasibility probability of an individual by sampling the individual plural times. In this paper, we propose a new evolutionary algorithm that estimates the expectation of the objective function and the feasibility probability of an individual by using the other individuals in the neighborhood of the individual. We show the effectiveness of the proposed method through experiments both in benchmark problems and in the problem of a inverted pendulum balancing with a neural network controller.
Cite this article as:
K. Masutomi, Y. Nagata, and I. Ono, “An Evolutionary Algorithm for Black-Box Chance-Constrained Function Optimization,” J. Adv. Comput. Intell. Intell. Inform., Vol.17 No.2, pp. 272-282, 2013.
Data files:
References
  1. [1] A. Charnes and W. W. Cooper, “Chance-Constrained Programming,” Manag. Sci., Vol.6, No.1, pp. 73-79, 1960.
  2. [2] V. Heidrich-Meisner and C. Igel, “Uncertainty Handling in Evolutionary Direct Policy Search,” NIPS-08 Workshop on Model Uncert. and Risk in RL, 2008.
  3. [3] L. Busoniu, R. Babuska, and B. de. Schutter, “A Comprehensive Survey ofMulti-Agent Reinforcement Learning,” IEEE Trans. Sys., Man, Cyber., Vol.38, No.2, pp. 156-172, 2008.
  4. [4] D. K. Pratihar, “Evolutionary robotics – A review,” Sadhana, Vol.28, No.6, pp. 999-1009, 2003.
  5. [5] A. Charnes and W. W. Cooper, “Deterministic equivalents for optimizing and satisfying under chance constraints,” Oper. Res., Vol.11, pp. 18-39, 1963.
  6. [6] W. W. Cooper, H. Hemphill, and D. Sullivan, “Survey of mathematical programming models in air pollution management,” Euro. J. Oper. Res., Vol.96, 1997.
  7. [7] K. Deb, S. Gupta, and D. Daum, “Reliability-Based Optimization Using Evolutionary Algorithms,” IEEE Trans. Evol. Comput., Vol.13, No.5, pp. 1054-1074, 2009.
  8. [8] Y. Jin and J. Branke, “Evolutionary Optimization in Uncertain Environments – A Survey,” IEEE Trans. Evol. Comput., Vol.9, No.3, pp. 303-317, 2005.
  9. [9] S. R. Loughlin and S. R. Ranjithan, “Chance-constrained genetic algorithms,” Proc. Genetic Evol. Comput. Conf., pp. 369-376, 1999.
  10. [10] L. Davis, “The Handbook of Genetic Algorithms,” Van Nostrand Reinhold, 1990.
  11. [11] L. Eshelman, “Real-Coded Genetic Algorithms and Interval-Schemata,” Found. Genetic Algo., Vol.2, pp. 187-202, 1993.
  12. [12] K. Deb, D. Joshi, and A. Anand, “Real-coded evolutionary algorithms with parent-centric recombination,” Proc. IEEE Cong. Evol. Comput., Vol.1, pp. 61-66, 2002.
  13. [13] C. Herväs-Martïnez, D. Ortiz-Boyer, and N. Garcïa-Pedrajas, “Theoretical Analysis of the Confidence Interval Based Crossover for Real-Coded Genetic Algorithms,” Paral. Prob. Solv. Nat. VII, pp. 153-161, 2002.
  14. [14] F. Herrera, M. Lozano, and A. Sanchez, “A Taxonomy for the Crossover Operator for Real-Coded Genetic Algorithms: An Experimental Study,” Int. J. Intel. Sys., Vol.18, pp. 309-338, 2003.
  15. [15] P. Ballester and J. Carter, “An Effective Real-Parameter Genetic Algorithm with Parent Centric Normal Crossover for Multimodal Optimisation,” Proc. Genetic Evol. Comput. Conf. Vol.3102, pp. 901-913, 2004.
  16. [16] J. Sakuma and S. Kobayashi, “Latent variable crossover for k-tablet structures and its application to lens design problems,” Proc. Genetic Evol. Comput. Conf., pp. 1347-1354, 2005.
  17. [17] H. Someya, “Promising Search Regions of Crossover Operators for Function Optimization,” Proc. 20th Int. Conf. Indust., Eng. & Other Appl. Appl. Intel. Sys., pp. 434-443, 2007.
  18. [18] H. Kita and M. Yamamura, “A functional specialization hypothesis for designing genetic algorithms,” Proc. IEEE SMC ’99 Conf., pp. 579-584, 1999.
  19. [19] S. Kobayashi, “The Frontiers of Real-Coded Genetic Algorithms,” Trans. Jpn. Soc. Artif. Intel., Vol.24, No.1, pp. 147-162, 2009 (in Japanese).
  20. [20] Y. Akimoto, Y. Nagata, J. Sakuma, I. Ono, and S. Kobayashi, “Analysis of the behavior of MGG and JGG as a selection model for real-coded genetic algorithms,” Trans. Jpn. Soc. Artif. Intel., Vol.25, No.2, pp. 281-289, 2010 (in Japanese).
  21. [21] I. Ono, S. Kobayashi, and K. Yoshida, “Global and Multi-objective Optimization for Lens Design by Real-coded Genetic Algorithms,” SPIE Proc. Int. Optical Design Conf., Vol.3482, pp. 110-121, 1998.
  22. [22] K. Boese, “Cost Versus Distance in the Traveling Salesman Problem,” Tech. Rep. TR-950018, UCLA CS Depart., 1995.
  23. [23] J. Branke, “Creating robust solutions by means of an evolutionary algorithm,” Proc. Int. Conf. Paral. Prob. Solv. Nat., pp. 119-128, 1998.
  24. [24] Y. Sano and H. Kita, “Optimization of noisy fitness functions by means of genetic algorithms using history of search,” Proc. Int. Conf. Paral. Prob. Solv. Nat., pp. 571-580, 2000.
  25. [25] J. Branke, C. Schomidt, and H. Schmeck, “Efficient Fitness Estimation in Noisy Environments,” Proc. Genetic Evol. Comput. Conf. pp. 243-250, 2001.
  26. [26] H. Someya, “Theoretical Parameter Value for Appropriate Population Variance of the Distribution of Children in Real-coded GA,” Proc. IEEE Cong. Evol. Comput., pp. 2722-2729, 2008.
  27. [27] A. J. F. van Rooij, L. C. Jain, and R. P. Johnson, “Neural Network Training Using Genetic Algorithms,” World Scientific, 1996.
  28. [28] G. F. Franklin, J. D. Powell, and A. Emami-Naeini, “Feedback Control of Dynamic Systems,” Pearson Prentice Hall, 6th ed., 2010.
  29. [29] S. Tsutsui, S. Yamamura, and T. Higuchi, “Multi-parent recombination with simplex crossover in real-coded genetic algorithms,” Proc. Genetic Evol. Comput. Conf., pp. 657-664, 1999.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 22, 2024