| Περίληψη: | H παρούσα διπλωματική εργασία επικεντρώνεται σε μεθόδους βελτιστοποίησης με σκοπό την εύρεση των καλύτερων λύσεων σε διαδικασίες μηχανικής μάθησης και εκπαίδευσης.
Αρχικά παρατίθεται το βασικό, για τα κεφάλαια που ακολουθούν, μαθηματικό υπόβαθρο. Αυτό περιλαμβάνει στοιχεία της Διανυσματικής ανάλυσης, της Γραμμικής άλγεβρας, της Θεωρίας των Πιθανοτήτων και της Στατιστικής.
Ακολουθεί μια σύντομη αναφορά στις έννοιες της στοχαστικής διαδικασίας, της διαδικασίας Bernoulli (Bernoulli process) και του τυχαίου περιπάτου (Random walk), ενώ περισσότερη έμφαση δίνεται στις αλυσίδες Markov και στα Hidden Markov Models (HMM).
Τα επόμενα κεφάλαια επικεντρώνονται σε μεθόδους βελτιστοποίησης, η εφαρμογή των οποίων απαντάται σε πληθώρα προβλημάτων. Καταρχάς, αναλύονται μέθοδοι βελτιστοποίησης που εφαρμόζονται σε προβλήματα δίχως περιορισμούς. Πιο συγκεκριμένα, γίνεται λόγος για αλγορίθμους που βασίζονται στον υπολογισμό παραγώγων της συνάρτησης που μοντελοποιεί το προς επίλυση πρόβλημα. Τέτοιοι μέθοδοι είναι οι gradient descent, conjugate gradient και Newton-Rapson. Στη συνέχεια, τίθεται το πρόβλημα του γραμμικού προγραμματισμού, το οποίο υπόκειται σε περιορισμούς καθώς και ο αλγόριθμος Simplex. Το κεφάλαιο 3 ολοκληρώνεται με την περιγραφή αλγορίθμων για προβλήματα συνδυαστικής βελτιστοποίησης, τα οποία μοντελοποιούνται με χρήση γράφων (graphs). Ειδικότερα, αφού δοθεί η αντίστοιχη ορολογία αναπτύσσονται ο αλγόριθμος Branch and Bound, το πρόβλημα του συντομότερου μονοπατιού με τον αλγόριθμο Dijkstra και τέλος η εφαρμογή των αλγορίθμων του Prim και του Kruskal στο πρόβλημα του Minimum Spanning Tree.
Στο κεφάλαιο 4 προσδιορίζονται οι heuristics και metaheuristics μέθοδοι, οι οποίες εφαρμόζονται στα σύγχρονα προβλήματα συνδυαστικής βελτιστοποίησης. Παράλληλα, γίνεται μελέτη δύο γνωστών metaheuristic τεχνικών: των γενετικών αλγορίθμων (genetic algorithms) και της προσομοιωμένης ανόπτησης (simulated annealing).
|
|---|
