article

Genetic algorithm with integrated computing budget allocation for stochastic problems

Authors:

Aaron M. CramerAuthors Info & Claims

International Journal of Metaheuristics, Volume 5, Issue 2

Pages 115 - 135

https://doi.org/10.1504/IJMHEUR.2016.080257

Published: 01 January 2016 Publication History

Abstract

Stochastic problems are of great interest in many applications, and genetic algorithms GAs have been widely used to solve these kinds of problems. Normally, a large number of samples are needed to evaluate the stochastic function such that the sample mean closely approximates the actual mean in order to rank and select accurately in the GA; however, this method is computationally expensive. Some researchers have integrated different computing budget allocation schemes into the evaluation procedure of the GA to reduce the total computing cost. Herein, a GA is proposed in which computing budget allocation techniques are integrated directly into the selection operator rather than being used during fitness evaluation. This allows fitness evaluations to be allocated towards specific individuals for whom the algorithm requires more information, and this selection-integrated method is shown to be more accurate for the same computing budget than the existing evaluation-integrated methods on several test problems. Different computing budget allocation methods are studied on both traditional test functions and benchmark functions from a recent conference competition, and it is shown that the existing evaluation-integrated algorithm may require up to 225% of the samples required by the proposed selection-integrated GA to achieve results with the same accuracy.

References

[1]

Blum C. and Roli, A. (2003) 'Metaheuristics in combinatorial optimization: overview and conceptual comparison', ACM Computing Surveys (CSUR), Vol. 35, No. 3, pp.268-308.

Digital Library

[2]

Branke, J., Meisel, S. and Schmidt, C. (2008) 'Simulated annealing in the presence of noise', Journal of Heuristics, Vol. 14, No. 6, pp.627-654.

Digital Library

[3]

Buadhachain, S. and Provan, G. (2015) 'An efficient decentralized clustering algorithm for aggregation of noisy multi-mean data', Journal of Heuristics, Vol. 21, No. 2, pp.301-328.

Digital Library

[4]

Chan, R.R. and Sudhoff, S.D. (2010) 'An evolutionary computing approach to robust design in the presence of uncertainties', IEEE Transactions on Evolutionary Computation, Vol. 14, No. 6, pp.900-912.

Digital Library

[5]

Chen, Ch. (2010) 'Stochastic simulation optimization: an optimal computing budget allocation', World Scientific, Singapore.

[6]

Chen, C.H., He, D., Fu, M. and Lee, L.H. (2008) 'Efficient simulation budget allocation for selecting an optimal subset', INFORMS Journal on Computing, Vol. 20, No. 4, pp.579-595.

[7]

Chen, C.H., Lin, J., Yücesan, E. and Chick, S.E. (2000) 'Simulation budget allocation for further enhancing the efficiency of ordinal optimization', Discrete Event Dynamic Systems, Vol. 10, No. 3, pp.251-270.

Digital Library

[8]

Cramer, A.M., Sudhoff, S.D., Zivi, E.L. (2011) 'Metric optimization-based design of systems subject to hostile disruptions', IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, Vol. 41, No. 5, pp.989-1000.

Digital Library

[9]

Deb, K. and Agrawal, R.B. (1994) 'Simulated binary crossover for continuous search space', Complex Systems, Vol. 9, pp.1-34.

[10]

Deb, K. and Deb, D. (2014) 'Analysing mutation schemes for real-parameter genetic algorithms', International Journal of Artificial Intelligence and Soft Computing, Vol. 4, No. 1, pp.1-28.

Digital Library

[11]

Deb, K., Gupta, S., Daum, D., Branke, J., Mall, A.K. and Padmanabhan, D. (2009) 'Reliability-based optimization using evolutionary algorithms', IEEE Transactions on Evolutionary Computation, Vol. 13, No. 5, pp.1054-1074.

Digital Library

[12]

Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. (2002) 'A fast and elitist multiobjective genetic algorithm: NSGA-II', IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, pp.182-197.

Digital Library

[13]

Dill, G.K. and e Silva, A.S. (2013) 'Robust design of power system controllers based on optimization of pseudospectral functions', IEEE Transactions on Power Systems, Vol. 28, No. 2, pp.1756-1765.

[14]

Ermoliev, Y. (1988) Numerical Techniques for Stochastic Optimization, Springer-Verlag, New York, NY.

[15]

Fu, M.C., Chen, C.H. and Shi, L. (2008) 'Some topics for simulation optimization', Proceedings of the 40th Conference on Winter Simulation, pp.27-38, Amsterdam, The Netherlands.

Digital Library

[16]

Ho, S.L., Yang, S., Bai, Y. and Huang, J. (2014) 'A robust metaheuristic combining clonal colony optimization and population-based incremental learning methods', IEEE Transactions on Magnetics, Vol. 50, No. 2, pp.677-680.

[17]

Horng, S.C. and Lin, S.Y. (2013) 'Autionary algorithm assisted by surrogate model in the framework of ordinal optimization and optimal computing budget allocation', Information Sciences, Vol. 233, pp.214-229.

Digital Library

[18]

Jensen, M.T. (2003) 'Generating robust and flexible job shop schedules using genetic algorithms', IEEE Transactions on Evolutionary Computation, Vol. 7, No. 3, pp.275-288.

Digital Library

[19]

Lee, L.H., Chen, C., Chew, E.P., Li, J., Pujowidianto, N.A. and Zhang, S. (2010) 'A review of optimal computing budget allocation algorithms for simulation optimization problem', International Journal of Operations Research, Vol. 7, No. 2, pp.19-31.

[20]

Lee, L.H., Chew, E.P., Teng, S. and Chen, Y. (2008) 'Multi-objective simulation-based evolutionary algorithm for an aircraft spare parts allocation problem', European Journal of Operational Research, Vol. 189, No. 2, pp.476-491.

[21]

Liang, J., Qu, B. and Suganthan, P. (2014) 'Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization', Computational Intelligence Laboratory and Nanyang Technological University, China and Singapore, Tech. Rep. 201311.

[22]

Liu, B., Fernández, F.V. and Gielen, G.G. (2011) 'Efficient and accurate statistical analog yield optimization and variation-aware circuit sizing based on computational intelligence techniques', IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 30, No. 6, pp.793-805.

Digital Library

[23]

Liu, B., Zhang, Q., Fernández, F.V., Gielen, G.G. (2013) 'An efficient evolutionary algorithm for chance-constrained bi-objective stochastic optimization', IEEE Transactions on Evolutionary Computation, Vol. 17, No. 6, pp.786-796.

Digital Library

[24]

Liu, M. and He, J. (2013) 'An evolutionary negative-correlation framework for robust analog-circuit design under uncertain faults', IEEE Transactions on Evolutionary Computation, Vol. 17, No. 5, pp.640-665.

Digital Library

[25]

Mendoza, J., Rousseau, L.M. and Villegas, J. (2015) 'A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints', Journal of Heuristics, online, Vol. 1572-9397, pp.1-28.

[26]

Nesmachnow, S. (2014) 'An overview of metaheuristics: accurate and efficient methods for optimisation', International Journal of Metaheuristics, Vol. 3, No. 4, pp.320-347.

Digital Library

[27]

Paenke, I., Branke, J. and Jin, Y. (2006) 'Efficient search for robust solutions by means of evolutionary algorithms and fitness approximation', IEEE Transactions on Evolutionary Computation, Vol. 10, No. 4, pp.405-420.

Digital Library

[28]

Pan, H., Wang, L. and Liu, B. (2006) 'Particle swarm optimization for function optimization in noisy environment', Applied Mathematics and Computation, Vol. 181, No. 2, pp.908-919.

Digital Library

[29]

Rada-Vilela, J., Johnston, M. and Zhang, M. (2014) 'Population statistics for particle swarm optimization: resampling methods in noisy optimization problems', Swarm and Evolutionary Computation, Vol. 17, pp.37-59.

[30]

Rada-Vilela, J., Zhang, M. and Johnston, M. (2013) 'Optimal computing budget allocation in particle swarm optimization', Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, pp.81-88, Miami, FL.

Digital Library

[31]

Schmidt, C., Branke, J. and Chick, S.E. (2006) 'Integrating techniques from statistical ranking into evolutionary algorithms', Applications of Evolutionary Computing, Vol. 3907, pp.752-763.

Digital Library

[32]

Siddiqui, M. (1964) 'Statistical inference for rayleigh distributions', Journal of Research of the National Bureau of Standards, Vol. Sec D 68, pp.1005-1010.

[33]

Stan, O., Sirdey, R., Carlier, J. and Nace, D. (2014) 'The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks', Journal of Heuristics, Vol. 20, No. 3, pp.261-290.

Digital Library

[34]

Tsutsui, S. and Ghosh, A. (1997) 'Genetic algorithms with a robust solution searching scheme', IEEE Transactions on Evolutionary Computation, Vol. 1, No. 3, pp.201-208.

Digital Library

[35]

Tu, Z. and Lu, Y. (2004) 'A robust stochastic genetic algorithm (stGA) for global numerical optimization', IEEE Transactions on Evolutionary Computation, Vol. 8, No. 5, pp.456-470.

Digital Library

[36]

Wang, L., Zhang, L. and Zheng, D.Z. (2005) 'Genetic ordinal optimisation for stochastic flow shop scheduling', The International Journal of AdvancedManufacturing Technology, Vol. 27, Nos. 1-2, pp.166-173.

[37]

Xiao, H. and Lee, L.H. (2014) 'Simulation optimization using genetic algorithms with optimal computing budget allocation', Simulation, Vol. 90, No. 10, pp.1146-1157.

Digital Library

[38]

Xu, Y., Dong, Z.Y., Meng, K., Zhao, J.H. and Wong, K.P. (2012) 'A hybrid method for transient stability-constrained optimal power flow computation', IEEE Transactions on Power Systems, Vol. 27, No. 4, pp.1769-1777.

Cited By

Chiu CLai CChen C(2023)An evolutionary simulation-optimization approach for the problem of order allocation with flexible splitting rule in semiconductor assemblyApplied Intelligence10.1007/s10489-022-03701-253:3(2593-2615)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s10489-022-03701-2

Genetic algorithm with integrated computing budget allocation for stochastic problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Kursawe and ZDT functions optimization using hybrid micro genetic algorithm (HMGA)

A hybrid micro genetic algorithm (HMGA) is proposed for Pareto optimum search focusing on the Kursawe and ZDT test functions. HMGA is a fusion of the micro genetic algorithm (MGA) and the elitism concept of fast Pareto genetic algorithm. The ...
Simulation optimization using genetic algorithms with optimal computing budget allocation

A method is proposed to improve the efficiency of simulation optimization by integrating the notion of optimal computing budget allocation into the genetic algorithm, which is a global optimization search method that iteratively generates new solutions ...
Dynamic programming decision path encoding of genetic algorithms for production allocation problems

Genetic algorithm is a novel optimization technique for solving constrained optimization problems. The penalty function methods are the popular approaches because of their simplicity and ease of implementation. Penalty encoding method needs more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Metaheuristics

International Journal of Metaheuristics Volume 5, Issue 2

January 2016

80 pages

ISSN:1755-2176

EISSN:1755-2184

Issue’s Table of Contents

Publisher

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chiu CLai CChen C(2023)An evolutionary simulation-optimization approach for the problem of order allocation with flexible splitting rule in semiconductor assemblyApplied Intelligence10.1007/s10489-022-03701-253:3(2593-2615)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s10489-022-03701-2

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents