Ελληνικά
English
 

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

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

 

Στόχοι:

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

Δεξιότητες:

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

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

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

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

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

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

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

Για την αποδοτική επίλυση τέτοιων προβλημάτων, έχουν μελετηθεί και διαφορετικές ευρετικές μέθοδοι στη συμβιβαστική προσπάθεια αναζήτησης μιας υπό-βέλτιστης λύσης σε σύντομο χρόνο υπολογισμού. Οι ευρετικές μέθοδοι αναζήτησης συνήθως παράγονται με βάση απλής διαισθητικής και δημιουργικής σκέψης του ανθρώπου, και είναι συχνά χρήσιμες στην τοπική αναζήτηση για την γρήγορη εύρεση καλών λύσεων σε μια περιορισμένη περιοχή. Οι μεθευρετικές μέθοδοι είναι μέθοδοι υψηλότερου επιπέδου, οι οποίες με συστηματικό τρόπο καθοδηγούν όλη την διαδικασία της αναζήτησης με χρήση ευρετικών μεθόδων. Οι μεθευρετικοί αλγόριθμοι αν και δεν αποτελούν εγγύηση για την εύρεση μιας ολικά βέλτιστης λύσεως, συχνά προσφέρουν πολύ καλά αποτελέσματα σε πολλά πρακτικά προβλήματα.

Στα πλαίσια του μαθήματος, θα παρουσιαστούν τα ακόλουθα θέματα: 

Εισαγωγή σε δύσκολα υπολογιστικά προβλήματα συνδυαστικής και ολικής βελτιστοποίησης και στις μεθόδους εξαντλητική αναζήτησης.Βασικές έννοιες, π.χ., αναπαράσταση λύσης, τοπική αναζήτηση, γειτονικές περιοχές και τοπικά βέλτιστα. Εισαγωγή στην αναζήτηση με χρήση μεταβαλλόμενης γειτονιάς, καθώς και σε γενετικούς αλγορίθμους, αλγορίθμους εμπνευσμένους από τη φύση, (π.χ., νοημοσύνη σμήνους), αναζήτηση ταμπού, προσομοιωμένη ανόπτηση. Εφαρμογές μεθευρετικών μεθόδων, π.χ., σε προβλήματα δρομολόγησης, αποθεμάτων κ.α. Έλεγχος στατιστικών υποθέσεων και αναφορά υπολογιστικών πειραμάτων βασισμένων ειδικά σε ευρετικές μεθόδους.

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

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

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

50% Τελική γραπτή εξέταση / 50% δυο προσωπικές εργασίες. Η πρώτη εργασία αφορά σε βιβλιογραφικό παραδοτέο και έχει προθεσμία την 10η διδακτική εβδομάδα ενώ η δεύτερη εργασία αφορά σε προγραμματιστικό παραδοτέο και έχει προθεσμία την ημερομηνία εξετάσεων του μαθήματος.

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

http://compus.uom.gr/MINF199/


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