Genetické algoritmy pro generaci scénářů ve stochastickém programování: motivace a obecné základy

Genetic Algorithms for Scenario Generation in Stochastic Programming: Motivation and General Framework

book chapter

en

Stochastic programs have been developed as useful tools for modeling of various application problems. The developed algorithms usually require a solution of large-scale linear and nonlinear programs because the deterministic reformulations of the original stochastic programs are based on empirical or sampling discrete probability distributions, i.e. on so-called scenario sets. The scenario sets are often large, so the reformulated programs must be solved. Therefore, the suitable scenario set generation techniques are required. Hence, randomly selected reduced scenario sets are often employed. Related confidence intervals for the optimal objective function values have been derived and are often presented as tight enough. However, there is also demand for goal-oriented scenario generation to learn more about the extreme cases. Traditional deterministic max-min and min-min techniques are significantly limited by the size of scenario set. Therefore, this text introduces a general framework how to generate and modify suitable scenario sets by using genetic algorithms. As an example, the search of absolute lower and upper bounds by using GA is presented and further enhancements are discussed. The proposed technique is implemented in C++ and GAMS and then tested on real-data examples.

Modely stochastického programování se osvědčily pro různé aplikační problémy. Algoritmy pro uvedené modely vyžadují řešení rozsáhlých úloh lineárního a nelineárního programování, protože deterministické přepisy původních úloh stochastického programování jsou založeny na empirických a výběrových diskrétních rozděleních pravděpodobnosti tzv. množinách scénářů. Množiny scénářů jsou často rozsáhlé, ale přepsané programy musí být řešeny. Proto jsou žádány vhodné generátory pro množiny scénářů. Používají se proto redukované množiny scénářů získané z původní množiny. Byly odvozeny intervaly spolehlivosti pro optimální hodnotu účelové funkce a úspěšně jsou používány. Ukazuje se také jako důležité zabývat se technikami cíleného nejen náhodného generování množin scénářů a zkoumat extrémní případy těchto množin. Klasické deterministické maxmin a minmin přístupy jsou významně limitovány velikostí množin scénářů. Text uvádí obecný rámec pro generování a modifikace vhodných množin scénářů pomocí genetických algoritmů. Jsou uvedeny příklady hledání absolutních dolních a horních mezí pomocí GA a další zlepšení jsou diskutována. Navržený algoritmus je implementován v C++ a v GAMSu a testován na reálných aplikačních datech.

Stochastic programs have been developed as useful tools for modeling of various application problems. The developed algorithms usually require a solution of large-scale linear and nonlinear programs because the deterministic reformulations of the original stochastic programs are based on empirical or sampling discrete probability distributions, i.e. on so-called scenario sets. The scenario sets are often large, so the reformulated programs must be solved. Therefore, the suitable scenario set generation techniques are required. Hence, randomly selected reduced scenario sets are often employed. Related confidence intervals for the optimal objective function values have been derived and are often presented as tight enough. However, there is also demand for goal-oriented scenario generation to learn more about the extreme cases. Traditional deterministic max-min and min-min techniques are significantly limited by the size of scenario set. Therefore, this text introduces a general framework how to generate and modify suitable scenario sets by using genetic algorithms. As an example, the search of absolute lower and upper bounds by using GA is presented and further enhancements are discussed. The proposed technique is implemented in C++ and GAMS and then tested on real-data examples.

Stochastické programování, scénáře, heuristické algoritmy, genetické algoritmy

Stochastic programming, scenarios, worst case analysis, heuristic and genetic algorithms

2008

01.09.2008

Springer

Netherlands

978-1-4020-8918-3

Lecture Notes in Electrical Engineering, book series: Advances in Computational Algorithms and Data Analysis, Vol. 14 Ao, S.L., Rieger, B., Chen, S.S. (Eds.).

1

527–536

9