Μελέτη Και Υλοποίηση Ευφυών Αλγορίθμων Σε Ηλεκτρονικά Κυκλώματα Πολύ Υψηλής Κλίμακας Ολοκλήρωσης

Abstract

Οι γενετικοί αλγόριθμοι (ΓΑ) είναι μια τεχνική τυχαίας αναζήτησης που επεξεργάζεται έναν πληθυσμό από λύσεις και βασίζεται στο νόμο της φυσικής επιλογής του Δαρβίνου. Ωστόσο, η σύγκλισή τους προς το βέλτιστο μπορεί να είναι υπερβολικά αργή για δύσκολα και περίπλοκα προβλήματα βελτιστοποίησης, με αποτέλεσμα να γίνεται δύσκολη η χρήση τους σε εφαρμογές πραγματικού χρόνου (real-time applications). Στην παρούσα διπλωματική εργασία ένας πλήρως παραμετρικός γενετικός αλγόριθμος έχει σχεδιαστεί και υλοποιηθεί σε υλικό (hardware), πετυχαίνοντας με αυτό τον τρόπο εντυπωσιακές επιταχύνσεις της ταχύτητας σύγκλισης συγκρινόμενος με τον ίδιο γενετικό αλγόριθμο ανεπτυγμένο σε λογισμικό. Ο όρος «πλήρως παραμετρικός» αναφέρεται στην παραμετροποίηση των βασικών χαρακτηριστικών του γενετικού αλγορίθμου, όπως το μέγεθος του πληθυσμού, η ανάλυση σε bit του κάθε γονιδίου, η πιθανότητα μετάλλαξης και η ανάλυσή της σε bit, οι μέθοδοι διασταύρωσης και μετάλλαξης που υιοθετούνται, ο μέγιστος αριθμός γενεών, ο αριθμός των ελίτ απογόνων κάθε γενιάς κ.α.. Η αρχιτεκτονική που παρουσιάζεται στην παρούσα εργασία υλοποιήθηκε σε ένα ψηφιακό κύκλωμα προγραμματιζόμενης λογικής (FPGA) με τη χρήση της γλώσσας περιγραφής υλικού VHDL και προχωρημένης τεχνολογίας εργαλεία σύνθεσης, τοποθέτησης και διασύνδεσης του συστήματός μας στο υλικό. Ο υλοποιημένος σε υλικό (hardware) γενετικός αλγόριθμος που παρουσιάζεται εδώ επιτυγχάνει συχνότητα λειτουργίας ίση με 92 MHz (10,8 nsec) και η απόδοση του αξιολογείται τόσο με τη χρήση του γνωστού μας προβλήματος του περιοδεύοντος πωλητή όσο και με ειδικές συναρτήσεις αξιολόγησης (benchmarking functions).