Ελληνικά
English
 

Ευρετικές Μέθοδοι

Διδάσκων/ντες:  Σιφαλέρας Άγγελος  |  

 

Στόχοι:

Στόχος του προτεινόμενου μαθήματος είναι να δώσει μια λεπτομερή εισαγωγή στη χρήση των σύγχρονων μεθευρετικών μεθόδων στην επίλυση πραγματικών προβλημάτων βελτιστοποίησης μεγάλης διάστασης, όπου ένας συμβιβασμός είναι αναγκαίος μεταξύ της ποιότητας της λύσης και του χρόνου επίλυσης.

Δεξιότητες:

Οι μεταπτυχιακοί φοιτητές που θα παρακολουθήσουν επιτυχώς το προτεινόμενο μάθημα θα αναπτύξουν δεξιότητες σχετικά με i) τη μοντελοποίηση σύνθετων πρακτικών προβλημάτων και ii) την αλγοριθμική επίλυση σε σύντομο υπολογιστικό χρόνο.

Προαπαιτήσεις:

Πολύ καλή γνώση μεθόδων επιχειρησιακής έρευνας.

Καλή γνώση προγραμματισμού Η/Υ.

Καλή γνώση δομών δεδομένων.

Περιεχόμενο μαθήματος:

Στην επίλυση προβλημάτων βελτιστοποίησης εφαρμόζονται κυρίως διάφοροι ακριβείς αλγόριθμοι μαθηματικού προγραμματισμού. Ωστόσο, σε προβλήματα συνδυαστικής ή ολικής βελτιστοποίησης οι συμβατικές μέθοδοι δεν είναι συνήθως αρκετά αποτελεσματικές, ειδικά, όταν ο χώρος αναζήτησης του προβλήματος είναι μεγάλος και πολύπλοκος. Η πλειοψηφία αυτών των υπολογιστικών προβλημάτων ανήκουν στην κλάση NP-hard, και δεν είναι δυνατή η εύρεση λύσης σε πολυωνυμικό χρόνο (εκτός αν P = NP).
 
Για την αποδοτική επίλυση τέτοιων προβλημάτων, έχουν μελετηθεί και διαφορετικές ευρετικές μέθοδοι στη συμβιβαστική προσπάθεια αναζήτησης μιας υπό-βέλτιστης λύσης σε σύντομο χρόνο υπολογισμού. Οι ευρετικές μέθοδοι αναζήτησης συνήθως παράγονται με βάση απλής διαισθητικής και δημιουργικής σκέψης του ανθρώπου, και είναι συχνά χρήσιμες στην τοπική αναζήτηση για την γρήγορη εύρεση καλών λύσεων σε μια περιορισμένη περιοχή. Οι μεθευρετικές μέθοδοι είναι μέθοδοι υψηλότερου επιπέδου, οι οποίες με συστηματικό τρόπο καθοδηγούν όλη την διαδικασία της αναζήτησης με χρήση ευρετικών μεθόδων. Οι μεθευρετικοί αλγόριθμοι αν και δεν αποτελούν εγγύηση για την εύρεση μιας ολικά βέλτιστης λύσεως, συχνά προσφέρουν πολύ καλά αποτελέσματα σε πολλά πρακτικά προβλήματα.
 
Στα πλαίσια του μαθήματος, θα παρουσιαστούν τα ακόλουθα θέματα:
 
Εισαγωγή σε δύσκολα υπολογιστικά προβλήματα συνδυαστικής και ολικής βελτιστοποίησης και στις μεθόδους εξαντλητικής αναζήτησης. Βασικές έννοιες, π.χ., αναπαράσταση λύσης, τοπική αναζήτηση, γειτονικές περιοχές και τοπικά βέλτιστα. Εισαγωγή στην αναζήτηση με χρήση μεταβαλλόμενης γειτονιάς, καθώς και σε γενετικούς αλγορίθμους, αλγορίθμους εμπνευσμένους από τη φύση, (π.χ., νοημοσύνη σμήνους), αναζήτηση ταμπού, προσομοιωμένη ανόπτηση. Εφαρμογές μεθευρετικών μεθόδων, π.χ., σε προβλήματα δρομολόγησης, αποθεμάτων κ.α. Έλεγχος στατιστικών υποθέσεων και αναφορά υπολογιστικών πειραμάτων βασισμένων ειδικά σε ευρετικές μεθόδους.

Προτεινόμενη βιβλιογραφία:

Μαρινάκης Ι., Μαρινάκη Μ., Ματσατσίνης Ν. Φ., Ζοπουνίδης Κ., (2011).
Μεθευρετικοί και Εξελικτικοί Αλγόριθμοι σε Προβλήματα Διοικητικής Επιστήμης, Εκδόσεις Κλειδάριθμος
Michalewich Z., Fogel D., (2012). Μοντέρνες Ευρετικές Μέθοδοι για την Επίλυση Προβλημάτων, 2η έκδοση, Εκδόσεις Π.Χ. Πασχαλίδης.

Μέθοδοι αξιολόγησης:

50% τελικές γραπτές εξετάσεις / 50% δυο προσωπικές προγραμματιστικές εργασίες, με προθεσμίες την 10η και 13η διδακτική εβδομάδα αντίστοιχα.

Ιστοσελίδα μαθήματος:

https://openeclass.uom.gr/courses/MAI101

 


επιστροφή
Tessera - Κατασκευή Ιστοσελίδων, E-Shops, Mobile & Tablet Apps