Stochastyczne algorytmy obliczeniowe

RSS

Cel przedmiotu

Prezentacja podstawowych grup algorytmów stochastycznych, tj. bazujących na modelach zmiennych losowych, oraz ich komputerowej symulacji. Studenci zostaną zapoznani tak z podstawami konstrukcji tego typu algorytmów, z metodami ich formalnej i symulacyjnej weryfikacji, jak i z podstawami projektowania systemów opartych o algorytmikę stochastyczną.

Program wykładu

Pojęcie zmiennej losowej i procesu stochastycznego, łańcuchy Markowa, ergodyczność. Generatory realizacji zmiennych losowych. Generatory zbiorów o dużej dyskrepancji. Metody Monte Carlo w symulacji oraz zagadnieniach przeszukiwania wielkich zbiorów danych. Analiza formalna metod Monte Carlo poprzez analizę zbieżności stochastycznej ciągu literat. Warunek asymptotycznej poprawności. Rozwiązywanie trudnych problemów optymalizacji globalnej. Algorytmy Random Walk i PRS, analiza własności asymptotycznych. Inne algorytmy stochastyczne optymalizacji globalnej: symulowane wyżarzanie i tabu serach. Algorytmy genetyczne o skończonym uniwersum – model łańcucha Markowa. Rodzaje zbieżności algorytmów genetycznych. Algorytmy genetyczne z heurystyka˛. Algorytmy z nieskończona˛ przestrzenią kodów. Stochastyczna optymalizacja wielokryterialna, algorytmy EMOA – analiza zbieżności.

Charakterystyka pozostałych zajęć

W ramach ćwiczeń laboratoryjnych studenci będą wprowadzani będą w inżynierię systemów opartych na algorytmach stochastycznych. Tworzone będą małe projekty dotyczące generacji liczb losowych oraz zbiorów o niskiej dyskrepancji. Ćwiczone będą metody generacji zmiennych losowych będących elementami łańcuchów stochastycznych dla różnych typów algorytmów (Monte Carlo, wyżarzania, genetycznych, etc.). Tworzone będą także małe projekty związane z zastosowaniami algorytmów stochastycznych w symulacji, optymalizacji oraz inżynierii wiedzy oraz inżynierii oprogramowania. Utrwalane i pogłębiane będą również fundamentalne pojęcia i wyniki teoretyczne wprowadzone na wykładzie.

Bibliografia

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.

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards