Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14754
Title: Μελέτη Και Υλοποίηση Ευφυών Αλγορίθμων Σε Ηλεκτρονικά Κυκλώματα Πολύ Υψηλής Κλίμακας Ολοκλήρωσης
Authors: Δογιάμης Γεώργιος
Τζαφέστας Κωνσταντίνος
Keywords: γενετικός αλγόριθμος
fpga
πρόβλημα περιοδεύοντος πωλητή (tsp)
vhdl
vlsi
ip
σύνθεση
place & route
Issue Date: 11-Dec-2006
Abstract: Οι γενετικοί αλγόριθμοι (ΓΑ) είναι μια τεχνική τυχαίας αναζήτησης που επεξεργάζεται έναν πληθυσμό από λύσεις και βασίζεται στο νόμο της φυσικής επιλογής του Δαρβίνου. Ωστόσο, η σύγκλισή τους προς το βέλτιστο μπορεί να είναι υπερβολικά αργή για δύσκολα και περίπλοκα προβλήματα βελτιστοποίησης, με αποτέλεσμα να γίνεται δύσκολη η χρήση τους σε εφαρμογές πραγματικού χρόνου (real-time applications). Στην παρούσα διπλωματική εργασία ένας πλήρως παραμετρικός γενετικός αλγόριθμος έχει σχεδιαστεί και υλοποιηθεί σε υλικό (hardware), πετυχαίνοντας με αυτό τον τρόπο εντυπωσιακές επιταχύνσεις της ταχύτητας σύγκλισης συγκρινόμενος με τον ίδιο γενετικό αλγόριθμο ανεπτυγμένο σε λογισμικό. Ο όρος «πλήρως παραμετρικός» αναφέρεται στην παραμετροποίηση των βασικών χαρακτηριστικών του γενετικού αλγορίθμου, όπως το μέγεθος του πληθυσμού, η ανάλυση σε bit του κάθε γονιδίου, η πιθανότητα μετάλλαξης και η ανάλυσή της σε bit, οι μέθοδοι διασταύρωσης και μετάλλαξης που υιοθετούνται, ο μέγιστος αριθμός γενεών, ο αριθμός των ελίτ απογόνων κάθε γενιάς κ.α.. Η αρχιτεκτονική που παρουσιάζεται στην παρούσα εργασία υλοποιήθηκε σε ένα ψηφιακό κύκλωμα προγραμματιζόμενης λογικής (FPGA) με τη χρήση της γλώσσας περιγραφής υλικού VHDL και προχωρημένης τεχνολογίας εργαλεία σύνθεσης, τοποθέτησης και διασύνδεσης του συστήματός μας στο υλικό. Ο υλοποιημένος σε υλικό (hardware) γενετικός αλγόριθμος που παρουσιάζεται εδώ επιτυγχάνει συχνότητα λειτουργίας ίση με 92 MHz (10,8 nsec) και η απόδοση του αξιολογείται τόσο με τη χρήση του γνωστού μας προβλήματος του περιοδεύοντος πωλητή όσο και με ειδικές συναρτήσεις αξιολόγησης (benchmarking functions).
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14754
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2006-0275.pdf3.1 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.