| Abstract : | Στην παρούσα εργασία παρουσιάζεται η βασική θεωρία των Μαρκοβιανών Μοντέλων Αποφάσεων. Εξηγείται πως ορίζονται τα μοντέλα και σε ποια προβλήματα χρειάζονται. Μελετώνται τριες βασικοί αλγόριθμοι για τη βελτιστοποίηση συστημάτων που μπορούν να μοντελοποιηθούν ως Μαρκοβιανές διαδικασίες διακριτού χρόνου: Ο αλγόριθμος Policy Iteration, ο Value Iteration και ο αλγόριθμος που βασίζεται στο γραμμικό προγραμματισμό. Η βασική θεωρία, όπως για παράδειγμα αυτή που αποδεικνύει τη σύγκιση των αλγορίθμων, εξηγείται με λεπτομέρια. Η σύγκλιση των αλγορίθμων αποδεικνύεται στην παρούσα κάτω από περιοριμούς οι οποίοι ικανοποιούνται στα περισσότερα πρακτικά προβλήματα. Τέλος, λύνονται αριθμητικά προβλήματα βελτιστοποίησης που προκύπτουν από ρεαλιστικές εφαρμογές και σχολιάζεται η απόδοση των αλγορίθμων.
In this project the basic theory of Markov Decision Processes (MDP's) is presented. It is explained how these models are defined and in which problems they are needed. Three basic algorithms for optimizing systems that can be modeled as MDP's are discussed: The Policy Iteration, Value Iteration and Linear Programming algorithms. The basic theoretical background, such as the convergence of the algorithms, is explained in detail. The convergence is proved under certain conditions that are met in most realistic problems. Finally, numerical examples of real world applications are solved and the results and the performance of the algorithms is commented.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.