×

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem. (English) Zbl 1176.90479

Summary: The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.

MSC:

90C27 Combinatorial optimization

Software:

DIMACS; MPFR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alkhamis, T. M.; Ahmed, M. A.; Tuan, V. K., Simulated annealing for discrete optimization with estimation, European Journal of Operational Research, 116, 3, 530-544 (1999) · Zbl 1009.90076
[2] Balaprakash, P.; Birattari, M.; Stützle, T., Improvement strategies for the F-Race algorithm: Sampling design and iterative refinement, (Bartz-Beielstein, T.; Blesa, M.; Blum, C.; Naujoks, B.; Roli, A.; Rudolph, G.; Sampels, M., Hybrid Metaheuristics of LNCS, vol. 4771 (2007), Springer-Verlag: Springer-Verlag Berlin, Germany), 113-127
[3] Balaprakash, P., Birattari, M., Stützle, T., Dorigo, M., 2007b. Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem: A complete analysis. Technical Report TR/IRIDIA/2007-015, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium. <http://iridia.ulb.ac.be/IridiaTrSeries/IridiaTr2007-015r002.pdf>; Balaprakash, P., Birattari, M., Stützle, T., Dorigo, M., 2007b. Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem: A complete analysis. Technical Report TR/IRIDIA/2007-015, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium. <http://iridia.ulb.ac.be/IridiaTrSeries/IridiaTr2007-015r002.pdf>
[4] Balaprakash, P., Birattari, M., Stützle, T., Dorigo, M., 2008. Extended empirical analysis of adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem. IRIDIA Supplementary Page. <http://iridia.ulb.ac.be/supp/IridiaSupp2008-010/>; Balaprakash, P., Birattari, M., Stützle, T., Dorigo, M., 2008. Extended empirical analysis of adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem. IRIDIA Supplementary Page. <http://iridia.ulb.ac.be/supp/IridiaSupp2008-010/>
[5] Bentley, J. L., Fast algorithms for geometric traveling salesman problems, ORSA Journal on Computing, 4, 4, 387-411 (1992) · Zbl 0758.90071
[6] Bertsimas, D., 1988. Probabilistic combinatorial optimization problems. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA.; Bertsimas, D., 1988. Probabilistic combinatorial optimization problems. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA.
[7] Bertsimas, D.; Jaillet, P.; Odoni, A., A priori optimization, Operations Research, 38, 6, 1019-1033 (1990) · Zbl 0721.90062
[8] Bianchi, L., 2006. Ant colony optimization and local search for the probabilistic traveling salesman problem: A case study in stochastic combinatorial optimization. Ph.D. Thesis, Université Libre de Bruxelles, Brussels, Belgium.; Bianchi, L., 2006. Ant colony optimization and local search for the probabilistic traveling salesman problem: A case study in stochastic combinatorial optimization. Ph.D. Thesis, Université Libre de Bruxelles, Brussels, Belgium.
[9] Bianchi, L.; Campbell, A., Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem, European Journal of Operational Research, 176, 1, 131-144 (2007) · Zbl 1137.90686
[10] Bianchi, L.; Knowles, J.; Bowler, N., Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms, European Journal of Operational Research, 162, 206-219 (2005) · Zbl 1132.90364
[11] Birattari, M., 2004. The problem of tuning metaheuristics as seen from a machine learning perspective. Ph.D. Thesis, Université Libre de Bruxelles, Brussels, Belgium.; Birattari, M., 2004. The problem of tuning metaheuristics as seen from a machine learning perspective. Ph.D. Thesis, Université Libre de Bruxelles, Brussels, Belgium. · Zbl 1101.68748
[12] Birattari, M.; Balaprakash, P.; Dorigo, M., The ACO/F-RACE algorithm for combinatorial optimization under uncertainty, (Doerner, K. F.; Gendreau, M.; Greistorfer, P.; Gutjahr, W. J.; Hartl, R. F.; Reimann, M., Metaheuristics - Progress in Complex Systems Optimization Operations Research/Computer Science Interfaces Series (2006), Springer-Verlag: Springer-Verlag Berlin, Germany), 189-203 · Zbl 1173.90587
[13] Birattari, M., Balaprakash, P., Stützle, T., Dorigo, M., 2007. Extended empirical analysis of estimation-based local search for stochastic combinatorial optimization. IRIDIA Supplementary Page. <http://iridia.ulb.ac.be/supp/IridiaSupp2007-001/>; Birattari, M., Balaprakash, P., Stützle, T., Dorigo, M., 2007. Extended empirical analysis of estimation-based local search for stochastic combinatorial optimization. IRIDIA Supplementary Page. <http://iridia.ulb.ac.be/supp/IridiaSupp2007-001/>
[14] Birattari, M.; Balaprakash, P.; Stützle, T.; Dorigo, M., Estimation-based local search for stochastic combinatorial optimization using delta evaluations: A case study in the probabilistic traveling salesman problem, INFORMS Journal on Computing, 20, 4, 644-658 (2008) · Zbl 1243.90154
[15] Chervi, P., 1988. A computational approach to probabilistic vehicle routing problems. Master’s Thesis, Massachusetts Institute of Technology, Cambridge, MA.; Chervi, P., 1988. A computational approach to probabilistic vehicle routing problems. Master’s Thesis, Massachusetts Institute of Technology, Cambridge, MA.
[16] Fousse, L.; Hanrot, G.; Lefèvre, V.; Pélissier, P.; Zimmermann, P., MPFR: A multiple-precision binary floating-point library with correct rounding, ACM Transactions on Mathematical Software, 33, 2, 1-15 (2007), <http://www.mpfr.org/> · Zbl 1365.65302
[17] Gutjahr, W.J., 2004. S-ACO: An ant based approach to combinatorial optimization under uncertainity. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (Eds.), Ant Colony Optimization and Swarm Intelligence, Fifth International Workshop, ANTS 2004, of LNCS, vol. 3172. Springer-Verlag, Berlin, Germany, pp. 238-249.; Gutjahr, W.J., 2004. S-ACO: An ant based approach to combinatorial optimization under uncertainity. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (Eds.), Ant Colony Optimization and Swarm Intelligence, Fifth International Workshop, ANTS 2004, of LNCS, vol. 3172. Springer-Verlag, Berlin, Germany, pp. 238-249.
[18] Gutjahr, W. J.; Strauss, C.; Toth, M., Crashing of stochastic activities by sampling and optimization, Business Process Management Journal, 12, 125-135 (2000) · Zbl 1034.90005
[19] Gutjahr, W. J.; Strauss, C.; Wagner, E., A stochastic branch-and-bound approach to activity crashing in project management, INFORMS Journal on Computing, 12, 125-135 (2000) · Zbl 1034.90005
[20] Homem-de-Mello, T., Variable-sample methods for stochastic optimization, ACM Transactions on Modeling and Computer Simulation, 13, 2, 108-133 (2003) · Zbl 1390.65003
[21] Hoos, H.; Stützle, T., Stochastic Local Search: Foundations and Applications (2005), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA · Zbl 1126.68032
[22] Jaillet, P., 1985. Probabilistic traveling salesman problems. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA.; Jaillet, P., 1985. Probabilistic traveling salesman problems. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA.
[23] Johnson, D. S.; McGeoch, L. A., The travelling salesman problem: A case study in local optimization, (Aarts, E. H.L.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), John Wiley and Sons: John Wiley and Sons Chichester, UK), 215-310 · Zbl 0947.90612
[24] Johnson, D.S., McGeoch, L.A., Rego, C., Glover, F., 2001. In: Eighth DIMACS Implementation Challenge. <http://www.research.att.com/dsj/chtsp/>; Johnson, D.S., McGeoch, L.A., Rego, C., Glover, F., 2001. In: Eighth DIMACS Implementation Challenge. <http://www.research.att.com/dsj/chtsp/>
[25] Lourenço, H. R.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G., Handbook of Metaheuristics of International Series in Operation Research and Management Science, vol. 57 (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 321-353 · Zbl 1116.90412
[26] Penky, J. F.; Miller, D. L., A staged primal-dual algorithm for finding a minimum cost perfect two-matching in an undirected graph, ORSA Journal on Computing, 6, 1, 68-81 (1994) · Zbl 0798.90128
[27] Pichitlamken, J.; Nelson, B. L., A combined procedure for optimization via simulation, ACM Transactions on Modeling and Computer Simulation, 13, 2, 55-179 (2003) · Zbl 1390.65024
[28] Rubinstein, R. Y., Simulation and the Monte Carlo Method (1981), John Wiley and Sons Inc.: John Wiley and Sons Inc. New York, NY · Zbl 0529.68076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.