Stochastic algorithms


Aim of the course

Presentation of the basic groups of stochastic algorithms, I.e. models based on random variables, and their computer simulation. Students will be shown the basics of such constructs of this type of algorithms, methods of their formal verification and simulation, as well as the basics of designing systems based on stochastic algorithms.

Lecture programme

The concept of random variable and stochastic process, Markov chains, ergodicity. Implementation of the generators of random variables. Generator of sets with high discrepancy. Issues of Monte Carlo simulation and search in large data sets. Formal analysis of Monte Carlo methods through the analysis of stochastic convergence of literate sequence. Condition of asymptotic correctness. Solving difficult problems of global optimization. Random Walk algorithms and PRS, analysis of asymptotic properties. Other stochastics-based global optimization algorithms: simulated annealing and taboo search. Genetic algorithms with a finite universe - Markov chain model. Types of convergence of genetic algorithms. Genetic algorithms with heuristics. Algorithms with infinite space codes. Stochastic multicriteria optimization, algorithms EMOA - analysis of convergence.

Overview of the course elements

The course comprises laboratory classes: students are introduced into the engineering of stochastics-based systems. There are foreseen minor projects dealing with the generation of random numbers and sets of low discrepancy. Excercises will relate to the generation of random variables that are elements of stochastic chains for different types of algorithms (Monte Carlo, annealing, genetic algorithms, etc.) . There are foreseen minor projects relating to the use of stochastic algorithms in simulation, optimization, and knowledge engineering as well as software engineering. The content of the classes consolidates and extends the theoretical knowledge taught at the lectures.

Reading list

1. Wit R., Nonlinear Programming Methods. WNT, Warsaw 1986 (in Polish).
2. Panos M. Pardalos, H. Edwin Romeijn; Handbook of Global Optimization, Volume 2 (Nonconvex Optimization and its Applications), Kluver Academic Publisher 2002.
3. Schaefer R., (with the chapter 6 written by Telega H.), Foundation of Global Genetic Optimization. Springer 2007.
4. Jakubowski J., Sztencel R., Introduction to the Probability Theory (in Polish), Script 2004.

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards