A Simulated Annealing with Ranking and Selection for Stochastic Optimization

Abstract:

We consider the problem of stochastic optimization, where the objective function values are not available and need to be simulated to get their estimates. When the function values are available one can use the simulated annealing algorithm. In this paper, we modify an algorithm that uses the hill climbing feature of simulated annealing with fixed temperature to search the feasible solution set. The proposed algorithm uses indifference zone approach of ranking and selection method to compare the current optimal solution and the potential solution that guarantee the optimal solution with a pre specified level of confidence. The algorithm is tested on a (s, S) inventory problem and compared to other competing algorithm. The numerical results show that the proposed method outperforms the competing method and indeed locate the optimal solution quickly.

• Periodical: Advanced Materials Research (Volumes 488-489)
• Pages: 1335-1340
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.488-489.1335
• Online since: March 2012
• Authors: Mahmoud H. Alrefaei, Ali H. Diabat
• Keywords: Ranking, Selection, Simulated Annealing (SA), Stochastic Optimization

References

[1] M. A. Ahmed, A Modification of the Simulated Annealing Algorithm for Discrete Stochastic Optimization. Eng. Opt. 2007, 39(6): 701–714.

DOI: 10.1080/03052150701280533

[2] M. A. Ahmed and T. M. Alkhamis, Simulation-Based Optimization using Simulated Annealing with Ranking and Selection. Comp. & Oper. Res. 2002, 29: 387–402.

DOI: 10.1016/s0305-0548(00)00073-3

[3] M. H. Alrefaei and S. Andradόttir, A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization. Manag. Sci. 1999, 45(5): 748–764.

DOI: 10.1287/mnsc.45.5.748

[4] M. H. Alrefaei and A. H. Diabat, A Simulated Annealing Technique for Multi-Objective Simulation Optimization. Appl. math. Comp. 2009, 215: 3029–3035.

DOI: 10.1016/j.amc.2009.09.051

[5] S. Andradόttir and A. A. Purdius, Balanced Explorative and Exploitative Search with Estimation for Simulation Optimization. INFORMS Jour. Comp. 2009, 21: 193-208.

DOI: 10.1287/ijoc.1080.0309

[6] R. E. Bechhofer, T. J. Santner, and D. M. Goldsman, Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. Wiley, 1995.

[7] S. B. Gelfand and S. K. Mitter, Simulated Annealing with Noisy or Imprecise Energy Measurements. J. Opt. Theo. App. 1989, 62: 49–62.

DOI: 10.1007/bf00939629

[8] D. Goldsman and B. L. Nelson, Ranking, Selection and Multiple Comparisons in Computer Simulation. In J. D. Tew, S. Manivannan, D. A. Sadowski, and A. F. Seila, (eds.). Proc. of the 1994 Wint. Sim. Conf. New Jersey: Institute of Electrical and Electronics Engineers, 1994, p.192–199.

[9] W. J. Gutjahr, and G. Ch. Pflug, Simulated Annealing for Noisy Cost Functions. J. Glob. Opt. 1996, 8: 1–13.

DOI: 10.1007/bf00229298

[10] S. Kirkpatrick., C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing. Science. 1983, 220: 671 – 680.

DOI: 10.1126/science.220.4598.671

[11] Y. Rinott, On Two–Stage Selection Procedures and Related Probability–Inequalities. Comm. Stats.: Theo. Meth. 1978, A7: 799–811.

DOI: 10.1080/03610927808827671

[12] R. R. Wilcox, A table for Rinott's selection procedure. J. Qual. Tech. 1984, 16: 97–100.

[13] L. Wang and L. Zhang, Stochastic optimization using simulated annealing with hypothesis test. Appl. Math.Comp. 2006, 174: 1329-1342.

DOI: 10.1016/j.amc.2005.05.038