Εξελικτική Υπολογιστική

E-mail Εκτύπωση PDF
Εβδομαδιαίες ώρες διδασκαλίας:   2 θεωρία + 1 ασκήσεις πράξεις + 2 εργαστήριο
Tυπικό εξάμηνο διδασκαλίας:        Ζ’

Διδασκαλία: Η διδασκαλία του μαθήματος έχει τη μορφή 15 διαλέξεων και ισάριθμων εργαστηριακών ασκήσεων, στο πλαίσιο των οποίων υπάρχει η δυνατότητα ανάληψης εργασιών.

Ενδεικτικά προαπαιτούμενα: Προγραμματισμός C, C++, Αλγόριθμοι και Δομές 

Διδακτικές μονάδες: 6 

Σκοπός και στόχοι του μαθήματος:

Το μάθημα αποσκοπεί στο να εισάγει τον φοιτητή στην θεωρία και την πρακτική της Εξελικτικής Υπολογιστικής, που αποτελεί ένα νέο αλλά εξελισσόμενο τομέα της Υπολογιστικής Νοημοσύνης, που περικλείει ένα σύνολο από ισχυρά εργαλεία βελτιστοποίησης και αναζήτησης λύσεων σε δύσκολα πραγματικά προβλήματα όπου δεν υπάρχουν αναλυτικές ή άλλες μέθοδοι επίλυσης. Αναλύονται οι αρχές λειτουργίας των εξελικτικών αλγορίθμων, η ιστορία τους και οι διαφορετικές τους μορφές. Περιγράφονται οι αρχές λειτουργίας και η θεωρία των Γενετικών Αλγορίθμων, τα δομικά τους στοιχεία, οι τεχνικές εφαρμογής τους σε πραγματικά προβλήματα (συνεχών παραμέτρων, συνδυαστικά, πολλαπλών στόχων, προβλήματα με περιορισμούς). Αναπτύσονται ειδικές εφαρμογές των Γ.Α. όπως τα Συστήματα Εκμάθησης Κανόνων, και οι Παράλληλοι Γενετικοί Αλγόριθμοι. Περιγράφονται άλλες εξελικτικές τεχνικές όπως οι Εξελικτικές Στρατηγικές, ο Εξελικτικός Προγραμματισμός, ο Γενετικός Προγραμματισμός, και το Εξελισσόμενο Υλικό. Τέλος αναλύονται οι αλγόριθμοι της Τεχνητής Ζωής και οι εφαμρογές τους. 

Περίγραμμα μαθήματος:

  • Επιστημονική ταξινόμηση της Εξελ.Υπολ., Υπολογιστική Ευφυία, Εισαγωγή στις αρχές της Εξελικτικικής Υπολογιστικής, ιστορική εξέλιξη, διαφορετικές μορφές αλγορίθμων, στόχοι και πεδίο εφαρμογής,
  • Οι Γενετικοί Αλγόριθμοι, αρχές λειτουργίας, αντιστοιχία με τα βιολογικά συστήματα, συνάρτηση ποιότητας, κωδικοποίηση των λύσεων - είδη κωδικοποίησης, αλγόριθμοι επιλογής γονέων, βασικοί γενετικοί τελεστές (ανασυνδυασμός – crossover, μετάλλαξη – mutation), άλλοι γενετικοί τελεστές, συνδυαστικοί τελεστές, αναπαραγωγή λύσεων – παραγωγή πληθυσμού απογόνων, κριτηρια τερματισμού - σύγκλισης, άλλες τεχνικές (ελιτισμός, κλιμάκωση ποιότητας, προσαρμογή τελεστών, τελεστές αναρρίχησης, υβριδικά σχήματα, περιορισμοί ζευγαρώματος, ενίσχυση διασποράς),
  • Θεωρία σχημάτων, Εσωτερικός Παραλληλισμός, Θεωρήματα σύγκλισης, Εφαρμογή Γ.Α σε προβλήματα με περιορισμούς, μέθοδοι αντιμετώπισης περιορισμών, Εφαρμογή σε Δυναμικά Προβλήματα Βελτιστοποίησης, Εφαρμογές Γενετικών Αλγορίθμων (προβλήματα συνεχών παραμέτρων – συνδυαστικά προβλήματα), Βελτιστοποίηση Πολλαπλών Στόχων, Μικρογενετικοί Αλγόριθμοι, Μεμετικοί Αλγόριθμοι.
  • Συστήματα εκμάθησης κανόνων (GBML – Classifier Systems), αρχές λειτουργίας, ανιχνευτές και δράστες (detectors-effectors), αναπαράσταση κανόνων, αλγόριθμοι εκμάθησης κανόνων (Bucket Brigade Algorithm), Αντιστοιχία με Νευρωνικά Δίκτυα, Εφαρμογές Σ.Ε.Κ.
  • Παράλληλοι Γενετικοί Αλγόριθμοι, Μοντέλα Π.Γ.Α., Μοντέλο Χαμηλής Ανάλυσης, Μοντέλο Υψηλής Ανάλυσης, Υβριδικά Μοντέλα, Μοντέλα διαφορετικών εξελικτικών συμπεριφορών.
  • Εξελικτικές Στρατηγικές, αρχές λειτουργίας, κατηγοριοποίηση Ε.Σ., χρήση και αντικατάσταση γονέων, Εφαρμογές Ε.Π.
  • Εξελικτικός Προγραμματισμός, αρχές λειτουργίας, κωδικοποίηση πραγματικών αριθμών, πιθανοτική μετάλλαξη σε πραγματικούς, εφαρμογές Ε.Π.
  • Γενετικός Προγραμματισμός, αρχές λειτουργίας, κωδικοποίηση λύσεων ιεραρχικής και δενδροειδούς δομής, λύσεις μεταβλητού μήκους, ειδικοί τελεστές ανασυνδυασμού και μετάλλαξης δένδρων, εφαρμογές Γ.Π.
  • Εξελισσόμενο Υλικό (Evolutionary Hardware), αρχές λειτουργίας, περιγραφή υλικού – FPGAs, μέθοδοι κωδικοποίσης λύσεων, τελεστές ανασυνδυασμού και μετάλλαξης γράφων, εφαρμογές Ε.Υ.
  • Αλγόριθμοι Τεχνητής Ζωής (Artificial Life, Μulti Agent Systems, Ant Colony Optimization, Cultural Algorithms),

Βασική Βιβλιογραφία:

  1. Σημειώσεις του μαθήματος «Εξελικτική Υπολογιστική», Α.Τ.Ε.Ι. Σερρών.
  2. D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
  3. L Davis, K De Jong, G Vose, Evolutionary Algorithms, 1999, Springer Verlag,
  4. Th. Bäck, Evolutionary Algorithms in Theory and Practice, Oxford University Press, 1996
  5. D.B. Fogel, Evolutionary Computation, IEEE Press, 1995

Συμπληρωματική Βιβλιογραφία:

  1. L. Davis, The Handbook of Genetic Algorithms, Van Nostrand & Reinhold, 1991
  2. T Baeck, D Fogel, Z Michalewicz, Handbook of Evolutionary Computation, 1997, Institute of Physics Publishing and Oxford University Press.
  3. Ζ. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, 3rd ed., 1996
  4. J. Koza, Genetic Programming, MIT Press, 1992
  5. H.-P. Schwefel, Evolution and Optimum Seeking, Wiley & Sons, 1995
  6. D Fogel, Evolutionary Computation: The Fossil Record, 1998, IEEE Press

 

Ηλεκτρονικές Υπηρεσίες