Διαδρομή: Αρχική Σελίδα » 1. Επιστήμη και Τεχνολογία Η/Υ » Α' Εξάμηνο - Πίνακας 1.Α » Ευρετικές Μέθοδοι »

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

Στόχοι:

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

Δεξιότητες:

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

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

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

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

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

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

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

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

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

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