{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T13:52:26Z","timestamp":1718632346977},"reference-count":33,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2013,3,8]],"date-time":"2013-03-08T00:00:00Z","timestamp":1362700800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Int Trans Operational Res"],"published-print":{"date-parts":[[2013,5]]},"abstract":"Abstract<\/jats:title>The main drawback of most metaheuristics is the absence of effective stopping criteria. Most implementations of such algorithms stop after performing a given maximum number of iterations or a given maximum number of consecutive iterations without improvement in the best\u2010known solution value, or after the stabilization of the set of elite solutions found along the search. We propose effective probabilistic stopping rules for randomized metaheuristics such as GRASP (Greedy Randomized Adaptive Search Procedures). We show how the probability density function of the solution values obtained along the iterations of such algorithms can be used to implement stopping rules based on the tradeoff between solution quality and the time needed to find a solution that might improve the best solution found. We show experimentally that, in the particular case of GRASP heuristics, the solution values obtained along its iterations fit a normal distribution that may be used to give an online estimation of the number of solutions obtained in forthcoming iterations that might be at least as good as the incumbent. This estimation is used to validate the stopping rule based on the tradeoff between solution quality and the time needed to find a solution that might improve the incumbent. The robustness of this strategy is illustrated and validated by a thorough computational study reporting results obtained with GRASP implementations to four different combinatorial optimization problems.<\/jats:p>","DOI":"10.1111\/itor.12010","type":"journal-article","created":{"date-parts":[[2013,3,8]],"date-time":"2013-03-08T13:05:12Z","timestamp":1362747912000},"page":"301-323","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Probabilistic stopping rules for GRASP heuristics and extensions"],"prefix":"10.1111","volume":"20","author":[{"given":"Celso C.","family":"Ribeiro","sequence":"first","affiliation":[{"name":"Department of Computer Science Universidade Federal Fluminense, Rua Passo da P\u00e1tria 156 Niter\u00f3i RJ 24210\u2010240 Brazil"}]},{"given":"Isabel","family":"Rosseti","sequence":"additional","affiliation":[{"name":"Department of Computer Science Universidade Federal Fluminense, Rua Passo da P\u00e1tria 156 Niter\u00f3i RJ 24210\u2010240 Brazil"}]},{"given":"Reinaldo C.","family":"Souza","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering Pontif\u00edcia Universidade Cat\u00f3lica do Rio de Janeiro Rio de Janeiro RJ 22453\u2010900 Brazil"}]}],"member":"311","published-online":{"date-parts":[[2013,3,8]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.3846\/13928619.2006.9637715","article-title":"Optimality testing in stochastic and heuristic algorithms","volume":"12","author":"Bartkut\u00e9 V.","year":"2006","journal-title":"Technological and Economic Development"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-008-9502-3"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591684"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008293323270"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20003"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0328048"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199910)34:3<181::AID-NET2>3.0.CO;2-Y"},{"key":"e_1_2_7_9_1","volume-title":"Statistical Distributions","author":"Evans M.","year":"2000"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01096763"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00663.x"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00664.x"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494277317"},{"key":"e_1_2_7_14_1","volume-title":"The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling","author":"Jain R.","year":"1991"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907742"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24838-5_27"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-006-9014-3"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.11.018"},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1971.10482319"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011319115230"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10065"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-25383-1_2"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1665-5_10"},{"key":"e_1_2_7_25_1","volume-title":"Search Methodologies","author":"Resende M.G.C.","year":"2013"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:HEUR.0000019986.96257.50"},{"key":"e_1_2_7_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45706-2_131"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2006.11.007"},{"key":"e_1_2_7_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_7_30_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601716"},{"key":"e_1_2_7_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.29.4.482"},{"key":"e_1_2_7_32_1","volume-title":"Approximation Algorithms","author":"Vazirani V.V.","year":"2004"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10500990"},{"key":"e_1_2_7_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-005-2060-2"}],"container-title":["International Transactions in Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Fitor.12010","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/itor.12010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T12:33:19Z","timestamp":1696163599000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/itor.12010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,8]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["10.1111\/itor.12010"],"URL":"https:\/\/doi.org\/10.1111\/itor.12010","archive":["Portico"],"relation":{},"ISSN":["0969-6016","1475-3995"],"issn-type":[{"value":"0969-6016","type":"print"},{"value":"1475-3995","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,8]]},"assertion":[{"value":"2013-01-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
