3 | 

9 4

 

 

Περίληψη  

Η τεχνητή νοημοσύνη έχει μεταμορφώσει τις βιομηχανικές δραστηριότητες. Μία από 

τις  πιο  σημαντικές  εφαρμογές  της  τεχνητής νοημοσύνης  είναι  η  μείωση  του  υπολογιστικού 

κόστους βελτιστοποίησης.  

Τα    τελευταία  χρόνια  παρατηρείται  η  ολοένα  και  περισσότερο  χρήση  της  τεχνητής 

νοημοσύνης για την επίλυση προβλημάτων με μεγάλη χρονική πολυπλοκότητα.  

Με τον όρο βελτιστοποίηση εννοούμε ότι ελαχιστοποιούμε ή μεγιστοποιούμε κάποια 

μεγέθη ανάλογα με το πρόβλημα που έχουμε να αντιμετωπίσουμε.   

Οι αλγόριθμοι βελτιστοποίησης ταξινομούνται σε δύο τύπους: ακριβείς αλγόριθμους 

και  κατά  προσέγγιση  αλγόριθμους.  Οι  ακριβείς  αλγόριθμοι  μπορούν  να  βρουν  με  ακρίβεια 

βέλτιστες  λύσεις,  αλλά  δεν  ισχύουν  για  πολύπλοκα  προβλήματα  βελτιστοποίησης  και  ο 

χρόνος  λύσης  τους  αυξάνεται  εκθετικά  σε  τέτοια  προβλήματα.  Οι  κατά  προσέγγιση 

αλγόριθμοι  μπορούν  να  βρουν  σχεδόν  βέλτιστες  λύσεις  για  δύσκολα  προβλήματα 

βελτιστοποίησης σε σύντομο χρονικό διάστημα. 

Στην  παρούσα  διπλωματική  εργασία  λύνουμε  κατά  προσέγγιση  ένα  πρόβλημα 

βελτιστοποίησης  υπό  περιορισμούς  με  τη  χρήση  γενετικού  αλγόριθμου.  Πιο  συγκεκριμένα, 

λύνουμε  το  πρόβλημα  της  δημιουργίας  βελτιστοποιημένων  σχηματικών  ψηφιακών 

κυκλωμάτων. Δύο είναι τα βασικά υποπροβλήματα που έχουμε να αντιμετωπίσουμε, πρώτον 

είναι το πρόβλημα της τοποθέτησης αντικειμένων σε δισδιάστατο χώρο  με βέλτιστο τρόπο 

και  δεύτερον  το  πρόβλημα  της  εύρεσης  συντομότερης  διαδρομής  για  την  διασύνδεση  των 

στοιχείων μεταξύ τους.  

Επιπλέον,  θα  χρησιμοποιήσουμε  το  εργαλείο  Logisim  που  είναι  ένα  λογισμικό  για 

σχεδίαση  ψηφιακών  κυκλωμάτων.  Το  Logisim  είναι  λογισμικό  ανοιχτού  κώδικα, 

χρησιμοποιείται  από  Πανεπιστημιακά  τμήματα  για  την  διεξαγωγή  των  μαθημάτων  της 

Ψηφιακής  Σχεδίασης  και  είναι  διαθέσιμο  για  χρήση  χωρίς  χρέωση.  Μπορεί  κάποιος  να  το 

κατεβάσει ελεύθερα από 

http://www.cburch.com/logisim/download.html

. 

Για  τον  λόγο  αυτό  αναπτύχθηκε  ένα  εργαλείο  γραμμής  εντολών,  που  δέχεται  σαν 

είσοδο ένα αρχείο (.dot) με τον ορισμό του ψηφιακού κυκλώματος και σαν έξοδο έχουμε ένα 

αρχείο (.circ) συμβατό με το Logisim, που περιέχει το σχηματικό του ψηφιακού κυκλώματος