background image

88 | 

9 4

 

 

6.  Συμπεράσματα και βελτιώσεις για το μέλλον 

6.1 

Σύνοψη 

 

Αφού  εκτελέσαμε  το  πρόγραμμα  για  διάφορες  πιθανότητες  μετάλλαξης  και 

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

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

ενδιαφέρει  να  βρούμε  με  ποιον  συνδυασμό  μεγιστοποιείται  η  μέση  τιμή  της  συνάρτησης 

αξιολόγησης. Όπως φαίνεται και από τα γραφήματα για 0.15 πιθανότητα μετάλλαξης και 0.7 

πιθανότητα διασταύρωσης η μέση τιμή της συνάρτησης αξιολόγησης έχει ξεπεράσει τις 600 

μονάδες  κατά  μέσο  όρο,  με  το  καλύτερο  κύκλωμα  να  είναι  στις  750  μονάδες.  Σ  αυτό  το 

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

να επιτευχθεί.   

Αυτό  το  συμπέρασμα  επιβεβαιώνεται  και  από  άλλους  επιστήμονες  που  μελέτησαν 

τους γενετικούς αλγόριθμους. 

Γενικά  το  πρόβλημα  έχει  αυξημένη  χρονική  πολυπλοκότητα  και  η  συχνά 

χρησιμοποιούμενη  λειτουργία  είναι  αυτή  της  αναζήτησης  A*.  Αν  ένα  κύκλωμα  έχει  10 

διασυνδέσεις  και  τρέξουμε  τον  αλγόριθμο  για  πληθυσμό  1.000  και  για  1.000  γενιές  τότε  η 

αναζήτηση  Α*  θα  τρέξει  τουλάχιστον  10.000.000  φορές.  Τουλάχιστον,  διότι  κάποια 

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

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

ο

 

στάδιο  του  Α*  (αυτό  με  τις  λιγότερες  δυνατές  αλλαγής  κατεύθυνσης)  μόνο  στα  καλύτερα 

κυκλώματα,  τα  οποία  ενδέχεται  να  εξαχθούν  στην  έξοδο.  Επιπλέον,  καθεμία  φορά  που 

κάνουμε την αναζήτηση Α*, χρειάζεται να γίνονται κοστοβόροι έλεγχοι περιορισμών ως προς 

την καλωδίωση, διότι το περιβάλλον αλλάζει δυναμικά. 

Στο  επόμενο  κεφάλαιο  θα  δούμε  κάποιες  τεχνικές  που  θα  μπορούσαν  σε  κάποια 

μελλοντική  έκδοση  να  προστεθούν.  Κάποιες  τεχνικές  που  αφορούν  την  βελτίωση  της 

απόδοσης και τον βαθμό της βελτιστοποίησης.