Stochastic Optimization

Johannes Schneider, Scott Kirkpatrick (Autoren)

Buch | Softcover

XVI, 568 Seiten

2010 | 1. Softcover reprint of hardcover 1st ed. 2006
Springer Berlin (Verlag)
978-3-642-07094-5 (ISBN)

Artikel merken

Our purpose in writing this book was to provide a compendium of stochastic optimizationtechniques,someguidesto wheneachisappropriateinpractical situations, and a few useful ways of thinking about optimization as a p- cess of search in some very rich con?guration spaces. Each of us has come to optimization, traditionally a subject studied in applied mathematics, from a background in physics, especially the statistical physics of random m- tures or materials. One of us (SK) has used ideas developed in the study of magnetic alloys to explore the optimal placement of computer circuits s- ject to many con?icting constraints, while at IBM Research, in Yorktown Heights, NY. The other (JJS) while completing his studies in physics under Prof. Ingo Morgenstern in Regensburg, Germany, and working at the IBM Scienti?c Center Heidelberg, was exposed to optimization problems as varied as scheduling the pickup of fresh milk and planning automobile assembly line schedules. We had the opportunity to work together after SK moved from IBM to a professorship at The Hebrew University of Jerusalem, Israel, and JJS was, for a year, a postdoc there. JJS has taught a course on stochastic optimization at the University of Mainz, where his students have used p- tions of the present manuscript. We hope to make this material readable by undergraduates, and useful to graduate students and practitioners as well, in computer science, applied mathematics, physics, and economics. Mainz, April 2006 JohannesJosefSchneider Jerusalem, April 2006 ScottKirkpatrick Contents Part I Theory Overview of Stochastic Optimization Algorithms 0 General Remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Johannes Schneider OFM, Dr. theol., geb. 1956 in Schwaz / Tirol, trat 1977 in den Franziskanerorden ein. 1982 folgte die Priesterweihe. Er absolvierte ein Studium der Franziskanischen Spiritualität in New York und der Spirituellen Theologie in Rom. Seither ist er in der Franziskanerprovinz Austria und in Salzburg in Seelsorge und Franziskanischer Forschung tätig.

Theory Overview of Stochastic Optimization Algorithms.- General Remarks.- Exact Optimization Algorithms for Simple Problems.- Exact Optimization Algorithms for Complex Problems.- Monte Carlo.- Overview of Optimization Heuristics.- Implementation of Constraints.- Parallelization Strategies.- Construction Heuristics.- Markovian Improvement Heuristics.- Local Search.- Ruin & Recreate.- Simulated Annealing.- Threshold Accepting and Other Algorithms Related to Simulated Annealing.- Changing the Energy Landscape.- Estimation of Expectation Values.- Cooling Techniques.- Estimation of Calculation Time Needed.- Weakening the Pure Markovian Approach.- Neural Networks.- Genetic Algorithms and Evolution Strategies.- Optimization Algorithms Inspired by Social Animals.- Optimization Algorithms Based on Multiagent Systems.- Tabu Search.- Histogram Algorithms.- Searching for Backbones.- Applications.- General Remarks.- The Traveling Salesman Problem.- The Traveling Salesman Problem.- Extensions of Traveling Salesman Problem.- Application of Construction Heuristics to TSP.- Local Search Concepts Applied to TSP.- Next Larger Moves Applied to TSP.- Ruin & Recreate Applied to TSP.- Application of Simulated Annealing to TSP.- Dependencies of SA Results on Moves and Cooling Process.- Application to TSP of Algorithms Related to Simulated Annealing.- Application of Search Space Smoothing to TSP.- Further Techniques Changing the Energy Landscape of a TSP.- Application of Neural Networks to TSP.- Application of Genetic Algorithms to TSP.- Social Animal Algorithms Applied to TSP.- Simulated Trading Applied to TSP.- Tabu Search Applied to TSP.- Application of History Algorithms to TSP.- Application of Searching for Backbones to TSP.- Simulating Various Types of Government with Searching for Backbones.- The Constraint Satisfaction Problem.- The Constraint Satisfaction Problem.- Construction Heuristics for CSP.- Random Local Iterative Search Heuristics.- Belief Propagation and Survey Propagation.- Outlook.- Future Outlook of Optimization Business.

From the reviews:

"The book is devoted to stochastic global optimization methods. ... The book is primarily addressed to scientists and students from the physical and engineering sciences but may also be useful to a larger community interested in stochastic methods of global optimization." (A. H. Zilinskas, Mathematical Reviews, Issue 2007 i)

"This book provides a rich collection of stochastic optimization algorithms and heuristics that cope with optimization issues. ... In summary, this is a good book on stochastic optimization. It is important book of any engineering library or laboratory. In my opinion, this book may be used as a quick reference for sophisticated scholars, or as an introductory book for students who are interested in an overview of the state-of-the-art mechanisms in this field." (Wei Yen, Computing Reviews, December, 2007)

"This book presents a compendium of Stochastic Optimisation concerned with the use of heuristics mainly including Markov Chain Monte Carlo methods. It is divided into 3 parts. ... 216 references are listed. They cover the main existing results in the theme. I consider that an outstanding feature of the book is its successful synthesis of giving in an 'altogether' curve information needed for being comfortable with the realms of heuristic algorithms. I warmly recommended it for specialists working in optimization." (Carlos Narciso Bouza Herrera, Zentralblatt MATH, Vol. 1116 (18), 2007)

Erscheint lt. Verlag	19.11.2010
Reihe/Serie	Scientific Computation
Zusatzinfo	XVI, 568 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	871 g
Themenwelt	Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
Schlagworte	algorithm • algorithms • Constraint Satisfaction • Construction • Genetic algorithms • Markov • Monte Carlo • Optimization • Random Numbers • Simulated annealing • stochastic optimization • Tabu Search • Traveling Salesman Problem
ISBN-10	3-642-07094-9 / 3642070949
ISBN-13	978-3-642-07094-5 / 9783642070945
Zustand	Neuware