{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,29]],"date-time":"2023-01-29T06:04:00Z","timestamp":1674972240887},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[1999,10]]},"abstract":"We discuss the choice of the estimation of the optimal solution when random search methods are applied to solve discrete stochastic optimization problems. At the present time, such optimization methods usually estimate the optimal solution using either the feasible solution the method is currently exploring or the feasible solution visited most often so far by the method. We propose using all the observed objective function values generated as the random search method moves around the feasible region seeking an optimal solution to obtain increasingly more precise estimates of the objective function values at the different points in the feasible region. At any given time, the feasible solution that has the best estimated objective function value (largest one for maximization problems; the smallest one for minimization problems) is used as the estimate of the optimal solution. We discuss the advantages of using this approach for estimating the optimal solution and present numerical results showing that modifying an existing random search method to use tnhis approach for estimating the optimal soluation appears to yield improved performance. We also present sereval rate of convergence results for random search methods using our approach for estimating the optimal solution. One these random search methods is a new variant of the stochastic comparison method; in addition to specifying the rate of convergence of this method, we prove that it is guaranteed to converge almost surely to the set of global optimal solutions and present a result that demonstrates that this method is likely to perform well in practice.<\/jats:p>","DOI":"10.1145\/352222.352225","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:28:46Z","timestamp":1027769326000},"page":"349-380","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":85,"title":["Accelerating the convergence of random search methods for discrete stochastic optimization"],"prefix":"10.1145","volume":"9","author":[{"given":"Sigr\u00fan","family":"Andrad\u00f3ttir","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta"}]}],"member":"320","published-online":{"date-parts":[[1999,10]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"406","volume-title":"Proceedings of the Winter Conference on Simulation (WSC '96","author":"ALREFAEI M. H."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.45.5.748"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"ALREFAEI M. H. AND ANDRAD TTIR S. 2000a. A modification of the stochastic ruler method for discrete stochastic optimization. Working paper. ALREFAEI M. H. AND ANDRAD TTIR S. 2000a. A modification of the stochastic ruler method for discrete stochastic optimization. Working paper.","DOI":"10.1016\/S0377-2217(00)00190-9"},{"key":"e_1_2_1_4_1","unstructured":"ALREFAEI M. H. AND ANDRAD TTIR S. 2000b. Discrete stochastic optimization using variants of the stochastic ruler method. Working paper. ALREFAEI M. H. AND ANDRAD TTIR S. 2000b. Discrete stochastic optimization using variants of the stochastic ruler method. Working paper."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.41.12.1946"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0806027","article-title":"A global search method for discrete stochastic optimization","volume":"6","author":"ANDRAD TTIR S.","year":"1996","journal-title":"SIAM J. Optim."},{"key":"e_1_2_1_7_1","unstructured":"ANDRAD TTIR S. 2000. Rate of convergence of random search methods for discrete optimization using steady-state simulation. Working paper. ANDRAD TTIR S. 2000. Rate of convergence of random search methods for discrete optimization using steady-state simulation. Working paper."},{"key":"e_1_2_1_8_1","unstructured":"BILLINGSLEY P. 1968. Convergence of Probability Measures. John Wiley and Sons Inc. New York NY. BILLINGSLEY P. 1968. Convergence of Probability Measures. John Wiley and Sons Inc. New York NY."},{"key":"e_1_2_1_9_1","volume-title":"2nd. ed","author":"CHUNG K. L."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/TSMC.1976.5408396","article-title":"On the convergence of statistical search","volume":"6","author":"DEVROYE L.","year":"1976","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1109\/TSMC.1976.5408782","article-title":"Probabilistic search as a strategy selection procedure","volume":"6","author":"DEVROYE L.","year":"1976","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1017\/S0269964800001662","article-title":"Randomized play-the-leader rules for sequential sampling from two populations","volume":"4","author":"DURHAM S. D.","year":"1990","journal-title":"Probab. Eng. Inf. Sci."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02022562","article-title":"Integrating and acccelerating tabu search, simulated annealing, and genetic algorithms","volume":"41","author":"L.","year":"1993","journal-title":"Ann. Oper. Res."},{"key":"e_1_2_1_14_1","volume-title":"Monte Carlo and Quasi Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S"},{"key":"e_1_2_1_15_1","first-page":"1087","article-title":"Probabilistic search with overrides","volume":"6","author":"HEINE G.W.","year":"1996","journal-title":"Ann. Appl. Probab."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF00939629","article-title":"Simulated annealing with noisy or imprecise energy measurements","volume":"62","author":"GELFAND S. B.","year":"1989","journal-title":"J. Optim. Theory Appl."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 31st Conference on Decision Control, 795-800","author":"GONG W. -B.","year":"1992"},{"key":"e_1_2_1_18_1","first-page":"252","article-title":"Random search in the presence of noise","volume":"4","author":"GURIN L. S.","year":"1966","journal-title":"Eng. Cybern."},{"key":"e_1_2_1_19_1","first-page":"1505","article-title":"Convergence of the random search method in the presence of noise","volume":"26","author":"GURIN L. S.","year":"1965","journal-title":"Autom. Remote Contr."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00229298","article-title":"Simulated annealing for noisy cost functions","volume":"8","author":"GUTJAHR W. J.","year":"1996","journal-title":"J. Global Optim."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01797280","article-title":"Ordinal optimization of DEDS","volume":"2","author":"SREENIVAS R. S.","year":"1992","journal-title":"Discrete Event Dyn. Syst."},{"key":"e_1_2_1_22_1","first-page":"1091","article-title":"Adaptive treatment allocation and the multi-armed bandit problem","volume":"15","author":"LAI T. L.","year":"1987","journal-title":"Ann. Stat."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90004-7"},{"key":"e_1_2_1_24_1","unstructured":"LEE g. -Y. 1995. Faster simulated annealing techniques for stochastic optimization problems with application to queueing network simulation. Ph.D. Dissertation. North Carolina State University at Raleigh Raleigh NC. LEE g. -Y. 1995. Faster simulated annealing techniques for stochastic optimization problems with application to queueing network simulation. Ph.D. Dissertation. North Carolina State University at Raleigh Raleigh NC."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"MARTI K. 1982. Minimizing noisy objective functions by random search methods. Z. Angew. Math. Mech. 62 T377T380. MARTI K. 1982. Minimizing noisy objective functions by random search methods. Z. Angew. Math. Mech. 62 T377T380.","DOI":"10.1515\/9783112547083-064"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"747","DOI":"10.2307\/1427186","article-title":"Convergence and finite-time behavior of simulated annealing","volume":"18","author":"MITRA D.","year":"1986","journal-title":"Adv. Appl. Probab."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"NELSON B. L. SWANN J. GOLDSMAN D. AND SONG W. 2000. Simple procedures for selecting the best simulated system when the number of alternatives is large. Working paper School of Industrial and Systems Engineering. College of Computing Georgia Institute of Technology Atlanta GA. NELSON B. L. SWANN J. GOLDSMAN D. AND SONG W. 2000. Simple procedures for selecting the best simulated system when the number of alternatives is large. Working paper School of Industrial and Systems Engineering. College of Computing Georgia Institute of Technology Atlanta GA.","DOI":"10.1287\/opre.49.6.950.10019"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1090\/S0002-9904-1952-09620-8","article-title":"Some aspects of the sequential design of experiments","volume":"58","author":"ROBBINS H.","year":"1952","journal-title":"Bull. Am. Math. Soc."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1214\/aoms\/1177698507","article-title":"A sequential procedure for selecting the largest of k means","volume":"39","author":"ROBBINS H.","year":"1968","journal-title":"Ann. Math. Stat."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0331003"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0378-3758(92)90001-9","article-title":"Machine learning for optimal blackjack counting strategies","volume":"33","author":"YAKOWITZ S.","year":"1992","journal-title":"J. Stat. Plan. Inference"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0330034"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/352222.352225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T23:52:16Z","timestamp":1672617136000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/352222.352225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,10]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1999,10]]}},"alternative-id":["10.1145\/352222.352225"],"URL":"http:\/\/dx.doi.org\/10.1145\/352222.352225","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":["Computer Science Applications","Modeling and Simulation"],"published":{"date-parts":[[1999,10]]},"assertion":[{"value":"1999-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}