Dokument

Summary:
This thesis connects the optimization of stochastic functions and information theory in a new way. New methods for the optimization of stochastic functions are proposed. These methods have been developed with regard to the optimization of non-imaging optical systems whose performance must be evaluated via Monte Carlo ray tracing, but they can be applied to other stochastic merit functions. A function is stochastic if its function values cannot be calculated straightforwardly and probability distributions for function values must be derived from the results of random experiments instead. The elements of a stochastic function’s domain are termed configurations. The core idea of this thesis is to base decisions made during an optimization on a criterion derived from the concept of information entropy. This leads to very efficient optimization methods. Efficiency is the ratio of the gain in information concerning the optimum to the effort invested. By means of the information entropy, the information content of the data collected during the optimization is measured. Criteria for decisions are based on this information measure. For each configuration, the number of random experiments is adjusted according to the demand by means of these criteria. For each option under consideration, the expected information gain is evaluated and the option with the largest expected information gain is chosen. Applying this principle, three methods for the optimization of stochastic functions are developed. Each of these methods is suitable for a specific class of optimization problems. The concept of information entropy is also applied to ranking and selection procedures. The purpose of ranking and selection is to guide the selection of a subset containing several good alternatives from a finite set of alternatives.

Bibliographie / References

1. George Ruppeiner. Riemannian geometry in thermodynamic fluctuation theory. Reviews of Modern Physics, 67(3):605–659, 1995.
2. Robin C. Ball, Thomas M. A. Fink, and Neill E. Bowler. Stochastic annealing. Physical Review Letters, 91(3):030201, 2003.
3. James C. Spall. An overview of the simultaneous perturbation method for efficient optimization. Johns Hopkins APL Technical Digest, 19(4):482–492, 1998.
4. Dirk V. Arnold. Noisy Optimization with Evolution Strategies. Kluwer Academic Publishers, 2002.
5. Gad Allon, Dirk P. Kroese, Tal Raviv, and Reuven Y. Rubinstein. Ap- plication of the cross-entropy method to the buffer allocation problem in a simulation-based environment. Annals of Operations Research, 134(1):137–151, 2005.
6. Virginia Joanne Torczon. Multi-Directional Search: A Direct Search Algorithm for Parallel Machines. PhD thesis, Rice University, Houston, Texas, 1989.
7. Krishna Chepuri and Tito Homem-de-Mello. Solving the vehicle rout- ing problem with stochastic demands using the cross-entropy method. Annals of Operations Research, 134:153–181, 2005. BIBLIOGRAPHY
8. Seong-Hee Kim and Barry L. Nelson. Selecting the best system: Theory and methods. In Proceedings of the 2003 Winter Simulation Conference, pages 101–112, 2003.
9. Tobias Scheffer and Stefan Wrobel. A sequential sampling algorithm for a general class of utility criteria. In International Conference on Knowledge Discovery and Data Mining, pages 330–334, 2000.
10. L. Jeff Hong and Barry L. Nelson. Selecting the best system when systems are revealed sequentially. IIE Transactions, 39:723–734, 2007.
11. Reuven Y. Rubinstein and Dirk P. Kroese. The Cross-Entropy Method. Springer, 2004.
12. Claude E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:379–423,623–656, 1948.
13. Sigrún Andradóttir. A review of simulation optimization techniques. In Proceedings of the 1998 Winter Simulation Conference, pages 151–158, 1998.
14. Xiaohui Ning, Roland Winston, and Joseph O'Gallagher. Dielectric totally internally reflecting concentrators. Applied Optics, 26:300–305, 1987.
15. Robert Hooke and T. A. Jeeves. " Direct search " solution of numerical and statistical problems. Journal of the ACM, 8(2):212–229, 1961.
16. George Ruppeiner, J.M. Pedersen, et al. Ensemble approach to simu- lated annealing. Journal of Physics I, 1:455–470, 1991.
17. Shu-Cherng Fang et al. Entropy optimization and mathematical pro- gramming. Kluwer Academic Publishers, 1997.
18. Ralf Salomon. Evolutionary algorithms and gradient search: Similari- ties and differences. IEEE Transactions on Evolutionary Computation, 2(2):45–55, 1998.
19. Ingo Rechenberg. Evolutionsstrategie '94. Frommann-Holzboog, 1994.
20. W. T. Welford and R. Winston. High Collection Nonimaging Optics. Academic Press, San Diego, 1989.
21. Harald Ries, J. M. Gordon, and Michelle Lasken. High-flux photovoltaic solar concentrators with kaleidoscope-based optical designs. Solar En- ergy, 60(1):11–16, 1997.
22. C. Tim Kelley. Iterative Methods for Optimization. SIAM, 1999.
23. Gunter Dueck. New optimization heuristics The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1):86–92, 1993.
24. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C++. Cambridge University Press, second edition, 2002.
25. Wolfgang Spirkl and Harald Ries. Optimal finite-time endoreversible processes. Physical Review E, 52(4):3485–3489, 1995.
26. Scott Kirkpatrick et al. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.
27. David Goldsman. Ranking and selection in simulation. In Proceedings of the 1983 Winter Simulation Conference, pages 387–393, 1983.
28. Juta Pichitlamken and Barry L. Nelson. Selection-of-the-best procedures for optimization via simulation. In Proceedings of the 2001 Winter Sim- ulation Conference, pages 401–407, 2001.
29. Jürgen Branke, Stephan Meisel, and Christian Schmidt. Simulated an- nealing in the presence of noise. Journal of Heuristics, 2007.
30. Talal M. Alkhamis and Mohamed A. Ahmed. Simulation-based opti- mization using simulated annealing with confidence interval. In Proceed- ings of the 2004 Winter Simulation Conference, pages 514–519, 2004.
31. David Goldsman and Barry L. Nelson. Statistical screening, selection, and multiple comparison procedures in computer simulation. In Proceed- ings of the 1998 Winter Simulation Conference, pages 159–166, 1998.
32. David Goldsman, Seong-Hee Kim, and Barry L. Nelson. Statistical se- lection of the best system. In Proceedings of the 2005 Winter Simulation Conference, pages 178–187.
33. Tobias Christian Schmidt, Harald Ries, and Wolfgang Spirkl. Strat- egy based on information entropy for optimizing stochastic functions. Physical Review E, 75:021108, 2007. BIBLIOGRAPHY
34. M. M. Chen, J. B. Berkowitz-Mattuck, and P. E. Glaser. The use of a kaleidoscope to obtain uniform flux over a large area in a solar or arc imaging furnace. Applied Optics, 2(3):265–271, 1963.
35. Gunter Dueck and Tobias Scheuer. Threshold accepting: A general pur- pose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90(1):161–175, 1990.
36. Tito Homem-de-Mello. Variable-sample methods and simulated anneal- ing for discrete stochastic optimization. Stochastic Programming E-Print Series, 2000-4, 2000. Publisher: Humboldt-Universität zu Berlin, Insti- tut für Mathematik.
37. Bennet L. Fox and George W. Heine. Probabilistic search with overrides. The Annals of Applied Probability, 5(4):1087–1094, 1995.

Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten