Module also offered within study programmes:
General information:
Code:
UBPJO-114
Name:
Stochastic algorithms – applications and analysis
Profile of education:
Academic (A)
Lecture language:
English
Semester:
Fall
Responsible teacher:
Schaefer Robert (schaefer@agh.edu.pl)
Academic teachers:
Schaefer Robert (schaefer@agh.edu.pl)
Module summary

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Student understand the necessity of continuous studying and learning algorithms, methods and computer systems implementing complex stochastic searches and their applications. Activity during classes
Skills
M_U001 Student is able to perform the individual literature study in area of stochastic searches and their applications. Case study
M_U002 Student can apply the archived knowledge for designing and implementing stochastic search systems. Case study
M_U003 Student can utilize the modern computer environment and libraries for implementing and running parallel and distributed stochastic systems. Case study
Knowledge
M_W001 Student possess the knowledge in area of basic mechanisms of stochastic searches, their algorithmic formulation and formal analysis (guarantee of success and convergence). Activity during classes
M_W002 Student possess the knowledge in area of stochastic search applications in technology and geophysics. Activity during classes
M_W003 Student possess the knowledge of complexity analysis, memory analysis and the stochastic correctness of a stochastic searches. Activity during classes
M_W004 Student possess the specific knowledge in area of designing parallel and distributed software implementing complex stochastic strategies. Activity during classes
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Student understand the necessity of continuous studying and learning algorithms, methods and computer systems implementing complex stochastic searches and their applications. + - - - - - - - - - -
Skills
M_U001 Student is able to perform the individual literature study in area of stochastic searches and their applications. - - + - - - - - - - -
M_U002 Student can apply the archived knowledge for designing and implementing stochastic search systems. - - + - - - - - - - -
M_U003 Student can utilize the modern computer environment and libraries for implementing and running parallel and distributed stochastic systems. - - + - - - - - - - -
Knowledge
M_W001 Student possess the knowledge in area of basic mechanisms of stochastic searches, their algorithmic formulation and formal analysis (guarantee of success and convergence). + - - - - - - - - - -
M_W002 Student possess the knowledge in area of stochastic search applications in technology and geophysics. + - - - - - - - - - -
M_W003 Student possess the knowledge of complexity analysis, memory analysis and the stochastic correctness of a stochastic searches. + - - - - - - - - - -
M_W004 Student possess the specific knowledge in area of designing parallel and distributed software implementing complex stochastic strategies. + - - - - - - - - - -
Module content
Lectures:
Stochastic algorithms – applications and analysis

1. Random variables, stochastic process with a continuous and discrete space of states, stochastic chain, Markov and shift conditions, ergodicity, Prochorov theorem.
2. Monte Carlo methods and Pure Random Walk and Pure Random Search.
3. Asymptotic guarantee of success and stochastic asymptotic correctness.
4. Computational and memory complexity of stochastic searches. Simplest definition of stochastic convergence. Approximation of the first hitting time.
5. Formal analysis of Monte Carlo methods by the first hitting time evaluation.
6. Rigorous formulation of global optimization problems. Important examples: Analyzing huge data repositories, minimizing L-J potential for complicated particles, inverse problems in optimal design, defectoscopy and oil investigation.
7. Other stochastic algorithms: Simulated Annealing, Tabu Search, etc.
8. Genetic algorithms with a finite genetic universum. Space of states and the Markov model of dynamics.
9. Genetic algorithms with heuristic. SGA cese. Vose asymptotic theorems and application of the Prochorov theorem.
10. Algorithms with a continuous search space.
11. Multi-deme searches: Island Model, Hierarchic Genetic Strategy, memetic strategies.
12. Adaptive searches. Balancing exploration and exploitation. Adaptation of the search accuracy.
13. Two-phase strategies. Clustered genetic search.
14. Stochastic polioptimization, EMOA strategies.
15. Stochastic methods of solving inverse problems.

Laboratory classes:
Stochastic algorithms – applications and analysis

1.Introduction into selection and application of random generators. Designing and running uniform distribution generators. Gauss and Cauchy distribution generators in one and many dimensions. Generation of the alpha-stable random variables. Generation of sets with a large discrepancy.
2. Methodology of testing stochastic searches. Finite budget and finite accuracy programs.
3. Preparing materials for the project. Bibliographical analysis of the selected group of algorithms.
4. Algorithmic inventions in area of selected group of algorithms.
5. Benchmark selection and test program. Parameter tuning.
6. Working out test results. Deriving qualitative conclusions.
7. Project assessment and defense.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 166 h
Module ECTS credits 6 ECTS
Preparation for classes 60 h
Completion of practical placements 40 h
Contact hours 56 h
Examination or Final test 10 h
Additional information
Method of calculating the final grade:

Student has to get a positive lab assessment and a positive test result which checks the knowledge tought during the lectures.

Final assessment will based on the average of test and lab assessments – sr.
The final mark OK will be determined by the following rule:

if sr > 4.75 then OK := 5.0 else {if sr > 4.25 then OK := 4.5 else {if sr > 3.75 then OK := 4.0 else {if sr > 3.25 then OK := 3.5 else OK := 3}}}
Prerequisites and additional requirements:

Mathematical analysis, Algebra, Mathematical statistics

Recommended literature and teaching resources:

1)Billingsley P.; Probability and Measure. John Willey ans Sons, New York, Chichaster, Brisbane, Toronto, 1979.
2)Birattari M.; Tuning Metaheuristics. Springer 2009.
3)Neri F., Cotta C., Moscato P. (eds.); Handbook of Memetic Algorithms, Springer 2012.
4)Panos M. Pardalos, H. Edwin Romeijn; Handbook of Global Optimization, Volume 2 (Nonconvex Optimization and its Applications), Kluver Academic Publisher 2002.
5)Schaefer R., (with the chapter 6 written by Telega H.), Foundation of Global Genetic Optimization. Springer 2007.

Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

None