×

Recent trends in metaheuristics for stochastic combinatorial optimization. (English) Zbl 1262.90115

Summary: This short overview is an addendum to a recent literature survey by L. Bianchi et al. [J. Nat. Comp.. 8, 239–287 (2009; doi:10.1007/s11047-008-9098-4)] on metaheuristics for stochastic combinatorial optimization (SCO). It outlines some new developments that occurred in this field during the last few years. Special attention is given to multi-objective SCO as well as to combinations of metaheuristics with mathematical programming.

MSC:

90C15 Stochastic programming
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

ParadisEO-MOEO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bianchi L., Dorigo M., Gambardella L., Gutjahr W.J., A survey on metaheuristics for stochastic combinatorial optimization, NAT COMP, 2009, 8, 239–287 · Zbl 1162.90591 · doi:10.1007/s11047-008-9098-4
[2] Jin Y., Branke J., Evolutionary optimization in uncertain environments – a survey, IEEE T EVOLUT COMPUT, 2005, 9, 303–17 · Zbl 05452035 · doi:10.1109/TEVC.2005.846356
[3] Gendreau M., Potvin Y., Handbook of Metaheuristics, 2nd Edition, International Series in Operations Research and Management Science vol. 146, Springer, New York, 2010 · Zbl 1198.90002
[4] Birattari M., Balaprakash P., Stützle T., Dorigo M., Estimation-based local search for stochastic combinatorial optimization using delta evaluations: a case study on the probabilistic traveling salesman problem, INFORMS J COMPUT, 2008, 20, 644–658 · Zbl 1243.90154 · doi:10.1287/ijoc.1080.0276
[5] Balaprakash P., Birattari M., Stützle T., Dorigo M., Adaptive sample size and importance sampling in estimationbased local search for the probabilistic traveling salesman problem, EUR J OPER RES, 2009, 199, 98–110 · Zbl 1176.90479 · doi:10.1016/j.ejor.2008.11.027
[6] Balaprakash P., Birattari M., Stützle T., Dorigo M., Estimation-based metaheuristics for the probabilistic traveling salesman problem, COMPUT OPER RES, 2010, 37, 1939–1951 · Zbl 1188.90208 · doi:10.1016/j.cor.2009.12.005
[7] Hansen P., Mladenovic N., Moreno Perez J., Variable neighbourhood search: methods and applications, ANN OPER RES, 2010, 175, 367–407 · Zbl 1185.90211 · doi:10.1007/s10479-009-0657-6
[8] Gutjahr W.J., Katzensteiner S., Reiter P., A VNS algorithm for noisy problems and its application to project portfolio analysis, In: Hromkovic J. et al. (Ed.), Proc. SAGA 2007 (Stochastic Algorithms: Foundations and Applications) (2007, Berlin Heidelberg), Springer, 2007, 93–104 · Zbl 1175.90330
[9] Schilde M., Doerner K.F., Hartl R.F., Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports, Dept. of Business Administration, University of Vienna, 2010 · Zbl 1215.90014
[10] Dorigo M., Stützle T., Ant Colony Optimization: Overview and Recent Advances, In: Gendreau M., Potvin J.-Y. (Eds.), Handbook of Metaheuristics, International Series in Operations Research and Management Science vol. 146, Springer US, New York, 2010 · Zbl 1102.90378
[11] Poli R., Kennedy J., Blackwell T., Particle swarm optimization, SWARM INTELLIGENCE, 2007, 1, 33–57 · doi:10.1007/s11721-007-0002-0
[12] Balaprakash P., Birattari M., Stützle T., Yuan Z., Dorigo M., Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem, SWARM INTELLIGENCE, 2009, 3, 223–242 · Zbl 1176.90479 · doi:10.1007/s11721-009-0031-y
[13] Marinakis Y., Marinaki M., A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem, COMPUT OPER RES, 2010, 37, 432–442 · Zbl 1173.90515 · doi:10.1016/j.cor.2009.03.004
[14] Gutjahr W.J., S-ACO: An Ant-Based Approach to Combinatorial Optimization under Uncertainty, In: Dorigo M., Birattari M., Blum C., Gambardella L.M., Mondada F., Stützle T., Ant Colony Optimization and Swarm Intelligence, 4th International Workshop, ANTS 2004 (2004, Berlin Heidelberg New York), Springer LNCS, 2004, 238–249
[15] Vitanov I.V., Vitanov V.I., Harrison D.K., Buffer capacity allocation using ant colony optimisation algorithm, In: Rossetti M.D., Hill R.R., Johansson B., Dunkin A., Ingalls R.G., Proceedings of the 2009 Winter Simulation Conference (2009, Austin, TX), WSC, 2009, 3158–3168
[16] Brailsford S.C., Gutjahr W.J., Rauner M., Zeppelzauer W., Combined discrete-event simulation and ant colony optimisation approach for selecting optimal screening policies for diabetic retinopathy, COMPUTATIONAL MANAGEMENT SCIENCE, 2007, 4, 59–83 · Zbl 1106.92029 · doi:10.1007/s10287-006-0008-x
[17] Brailsford S.C., Tutorial: Advances and challenges in healthcare simulation modeling, In: Henderson S.G., Biller B., Hsieh M.-H., Shortle J., Tew J.D., Barton R.R. (Eds.), Proceedings of the 2007 Winter Simulation Conference (2007, Washington, DC), WSC, 2007, 1436–1448
[18] Birattari M., Balaprakash P., Dorigo M., The ACO/F-Race Algorithm for Combinatorial Optimization Under Uncertainty, In: Doerner K.F., Gendreau M., Greistorfer P., Gutjahr W., Hartl R.F., Reimann M., Metaheuristics, Operations Research/Computer Science Interfaces vol. 39, Springer US, New York, 2007 · Zbl 1173.90587
[19] Escobar A.H., Romero R.A., Gallego R.A., Transmission network expansion planing considering uncertainty in generation and demand, Proc. Transmission and Distribution Conference and Exposition: Latin America, 2008 IEEE/PES (2008, Bogota, Colombia), IEEE/PES, 2008, 1–6
[20] Gutjahr W.J., Stochastic search in metaheuristics, In: Gendreau M., Potvin Y., Handbook of Metaheuristics, 2nd Edition, International Series in Operations Research and Management Science vol. 146, Springer, New York, 2010
[21] Chang H.S., On convergence of evolutionary computation for stochastic combinatorial optimization, The Institute for Systems Research, James Clark School of Engineering, Univ. of Maryland, 2009, 16
[22] Hannah L., Powell W., Evolutionary Policy Iteration Under a Sampling Regime for Stochastic Combinatorial Optimization, IEEE T AUTOMAT CONTR, 2010, 55, 1254–1257 · Zbl 1368.90120 · doi:10.1109/TAC.2010.2042766
[23] Prudius A.A., Andradottir S., Two simulated annealing algorithms for noisy objective functions, In: Kuhl M.E., Steiger N.M., Armstrong F.B., Joines J.A. (Eds.), Proc. Winter Simulation Conference 2005 (2005, Orlando, FL), WSC, 2005, 797–802
[24] Prudius A.A., Adaptive random search methods for simulation optimization, PhD thesis, Georgia Institute of Technology, USA, 2007
[25] Branke J., Meisel S., Schmidt C., Simulated annealing in the presence of noise, J HEURISTICS, 2008, 14, 627–654 · Zbl 1173.90589 · doi:10.1007/s10732-007-9058-7
[26] Fink T.M.A., Inverse protein folding, hierarchical optimisation and tie knots, PhD thesis, University of Cambridge, 1998
[27] Maniezzo V., Stützle T., Voss S., Matheuristics: Hybridizing Metaheuristics and Mathematical Programming Springer, New York Dordrecht Heidelberg London, 2009
[28] Till J., Sand G., Urselmann M., Engell S., A hybrid evolutionary algorithm for solving two-stage stochastic integer programs in chemical batch scheduling, COMPUT CHEM ENG, 2007, 31, 630–647 · doi:10.1016/j.compchemeng.2006.09.003
[29] Tometzki T., Engell S., Hybrid evolutionary optimizatio of two-stage stochastic integer programming problems: an empirical investigation, EVOL COMPUT, 2009, 17, 511–526 · Zbl 05766604 · doi:10.1162/evco.2009.17.4.17404
[30] Hvattum L.M., Lokketangen A., Using scenario trees and progressive hedging for stochastic inventory routing problems, J HEURISTICS, 2009, 15, 527–557 · Zbl 1176.90025 · doi:10.1007/s10732-008-9076-0
[31] Crainic T.G., Fu X., Gendreau M., Rei W., Wallace S.W., Progressive hedging-based meta-heuristics for stochastic network design, CIRRELT Montreal, January 2009, 03 · Zbl 1233.90084
[32] Rei W., Gendreau M., Soriano P., A hybrid Monte Carlo branching algorithm for the single vehicle routing problem with stochastic demands, TRANSPORT SCI, 2010, 44, 136–146 · doi:10.1287/trsc.1090.0295
[33] Fischetti M., Lodi A., Local branching, MATH PROGRAM B, 2003, 98, 23–47 · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[34] Hannah L., Powell W., Stewart J., One-stage R & D portfolio optimization with an application to solid oxide fuel cells, ENERGY SYSTEMS, 2010, 1, 141–163 · doi:10.1007/s12667-009-0008-3
[35] Norkin V.I., Ermoliev Y.M., Ruszczynski A., On optimal allocation of indivisibles under uncertainty, OPER RES, 1998, 46, 381–395 · Zbl 0987.90064 · doi:10.1287/opre.46.3.381
[36] Norkin V.I., Pflug G.Ch., Ruszczynski A., A branch and bound method for stochastic global optimization, MATH PROGRAM, 1998, 83, 425–450 · Zbl 0920.90111
[37] Caballero R., Cerdá E., del Mar Munoz M., Rey L., Stochastic approach versus multiobjective approach for obtaining efficient solutions in stochastic multiobjective programming problems, EUR J OPER RES, 2004, 158, 633–648 · Zbl 1056.90081 · doi:10.1016/S0377-2217(03)00371-0
[38] Claro J., de Sousa J., A multiobjective metaheuristic for a mean-risk multistage capacity investment problem, J HEURISTICS, 2010, 16, 85–115 · Zbl 1181.90145 · doi:10.1007/s10732-008-9090-2
[39] Claro J., de Sousa J., A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem, COMPUT OPTIM APPL, 2010, 46, 427–450 · Zbl 1200.90132 · doi:10.1007/s10589-008-9197-2
[40] Hughes E.J., Evolutionary multi-objective ranking with uncertainty and noise, In: Zitzler E., Deb K., Thiele L., Coello Coello C.A., Corne D. (Eds.), Proc. EMO’ 01 (Evolutionary Multicriterion Optimization) (2001, Berlin), Springer, 2001, 329–343
[41] Teich J., Pareto-front exploration with uncertain objectives, In: Zitzler E., Deb K., Thiele L., Coello Coello C.A., Corne D. (Eds.), Proc. EMO’ 01 (Evolutionary Multicriterion Optimization) (2001, Berlin), Springer, 2001, 314–328
[42] Eskandari H., Rabelo L., Mollaghasemi M., Multiobjective simulation optimization using an enhanced genetic algorithm, In: Kuhl M.E., Steiger N.M., Armstrong F.B., Joines J.A., Proceedings of the 37th conference on Winter simulation, WSC’ 05 (Winter Simulation Conference) (2005, Orlando, Florida), WSC, 2005, 833–841
[43] Ding H., Benyucef L., Xie X., A simulation-based multi-objective genetic algorithm approach for networked enterprises optimization, ENG APPL ARTIF INTEL, 2006, 19, 609–623 · doi:10.1016/j.engappai.2005.12.008
[44] Amodeo L., Prins C., Sanchez D., Comparison of Metaheuristic Approaches for Multi-objective Simulation-Based Optimization in Supply Chain Inventory Management, In: Giacobini M., Brabazon A., Cagnoni S., Caro G.A., Ekart A., Esparcia-Alcázar A.I., Farooq M., Fink A., Machado P., McCormack J., O’Neill M., Neri F., Preuß M., Rothlauf F., Tarantino E., Yang S. (Eds.), Applications of Evolutionary Computing, Lecture Notes in Computer Science vol. 5484, Springer, Berlin, Heidelberg, 2009
[45] Eskandari H., Geiger Ch., Evolutionary multiobjective optimization in noisy problem environments, J HEURISTICS, 2009, 15, 559–595 · Zbl 1180.90287 · doi:10.1007/s10732-008-9077-z
[46] Syberfeldt A., Ng A., John R.I., Moore Ph., Multi-objective evolutionary simulation-optimisation of a real-world manufacturing problem, ROBOT CIM-INT MANUF, 2009, 25, 926–931 · doi:10.1016/j.rcim.2009.04.013
[47] Gutjahr W.J., Two metaheuristics for multiobjective stochastic combinatorial optimization, In: Lupanov O.B., Kasim-Zade O.M., Chaskin A.V., Steinhoefl K. (Eds.), Proc. SAGA 2005 (Stochastic Algorithms: Foundations and Applications) (2005, Berlin Heidelberg), Springer, 2005, 116–125 · Zbl 1159.68641
[48] Gutjahr W.J., A provably convergent heuristic for stochastic bicriteria integer programming, J HEURISTICS, 2009, 15, 227–258 · Zbl 1172.90477 · doi:10.1007/s10732-008-9071-5
[49] Gutjahr W.J., Reiter P., Bi-objective project portfolio selection and staff assignment under uncertainty, OPTIMIZATION, 2010, 59, 417–445 · Zbl 1191.90018 · doi:10.1080/02331931003700699
[50] Gutjahr W.J., Runtime Analysis of an Evolutionary Algorithm for Stochastic Multi-Objective Combinatorial Optimization, Dept. of Statistics and Decision Support Systems, University of Vienna, 2010
[51] Basseur M., Zitzler E., Handling uncertainty in indicator-based multiobjective optimization, INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE RESEARCH, 2006, 2, 255–272 · doi:10.5019/j.ijcir.2006.66
[52] Liefooghe A., Basseur M., Jourdan L., Talbi E.-G., Combinatorial Optimization of Stochastic Multi-objective Problems: An Application to the Flow-Shop Scheduling Problem, In: Obayashi S., Deb K., Poloni C., Hiroyasu T., Murata T. (Eds.), Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science vol. 4403, Springer, Berlin, Heidelberg, 2007
[53] Liefooghe A., Basseur M., Jourdan L., Talbi E.-G., ParadisEO-MOEO: A Framework for Evolutionary Multi-objective Optimization, In: Obayashi S., Deb K., Poloni C., Hiroyasu T., Murata T. (Eds.), Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science vol. 4403, Springer, Berlin, Heidelberg, 2007 · Zbl 1189.90143
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.