ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ

 

Ασκησεισ Κεφαλαιου  4 :

 


 

Άσκηση 1η

Να αποδειχτεί ότι οποιαδήποτε δυαδική συμβολοσειρά μήκους λ αποτελεί στιγμιότυπο από 2λ διαφορετικά σχήματα.

 

Υπόδειξη: Πόσες διαφορετικές τιμές μπορεί να πάρει κάθε θέση μιας δυαδικής συμβολοσειράς μς μήκος λ;

 

 Λύση


 

Άσκηση 2η

Υπάρχουν περιπτώσεις στις οποίες ένας πληθυσμός από n δυαδικές συμβολοσειρές μήκους λ περιέχει ακριβώς n ´ 2λ διαφορετικά σχήματα;

 

Υπόδειξη: Χρησιμοποιείστε και την απάντηση της 1ης άσκησης.

 

 Λύση


 

Άσκηση 3η

Πότε η ένωση δύο σχημάτων είναι επίσης ένα σχήμα; Για παράδειγμα, η  είναι ένα σχήμα , αλλά η  δεν είναι.

Πότε είναι η τομή δύο σχημάτων επίσης ένα σχήμα; Ποια η διαφορά των δύο σχημάτων;

 

 Λύση


 

Άσκηση 4η

Να ορίσετε την αντικειμενική συνάρτηση f της δυαδικής συμβολοσειράς x, με μήκος λ = 4, έτσι ώστε να ισούται με τον ακέραιο που αναπαριστάται από το δυαδικό αριθμό x

(π.χ. ).

Ποια είναι η μέση απόδοση του σχήματος , σε σχέση με την αντικειμενική συνάρτηση f; Ποια είναι η μέση απόδοση του σχήματος  σε σχέση με την f;

 

Υπόδειξη: Αφού ορίσετε την αντικειμενική συνάρτηση, βρείτε πόσα άτομα ανήκουν σε κάθε σχήμα για να υπολογίσετε την μέση απόδοσή του.

 

 Λύση


 

Άσκηση 5η

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

Να δώσετε τη σχέση για τη μέση απόδοση ενός σχήματος S, το οποίο έχει k ορισμένα δυαδικά ψηφία όλα ίσα με 1, σε σχέση με το μήκος της δυαδικής συμβολοσειράς λ και το k.

 

 Λύση


 

Άσκηση 6η

Έστω ότι μια αντικειμενική συνάρτηση έχει την παρακάτω μορφή:

 

 

όπου το x είναι μια δυαδική συμβολοσειρά.

Ποια είναι η μέση απόδοση των σχημάτων ,  και .

 

Υπόδειξη: Βείτε πόσα άτομα ανήκουν σε κάθε σχήμα και υπολογίστε την μέση απόδοσή του σύμφωνα με τη δεδομένη αντικειμενική συνάρτηση.

 

 Λύση


 

Άσκηση 7η

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

 

 Λύση


 

Άσκηση 8η

Θεωρήστε τις τρεις επόμενες δυαδικές συμβολοσειρές ,  και  και τα έξι επόμενα σχήματα

 

, , , ,  και .

α) Ποιες συμβολοσειρές ταιριάζουν σε κάθε σχήμα;

β) Βρείτε την τάξη και το καθορισμένο μήκος κάθε σχήματος.

γ) Υπολογίστε την πιθανότητα επιβίωσης κάθε σχήματος, όταν υποβάλλεται σε μετάλλαξη και η πιθανότητα μιας απλής μετάλλαξης είναι .

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

 

Υπόδειξη: Ανατρέξτε στη θεωρία για τον ορισμό της τάξης και του καθορισμένου μήκους καθώς επίσης και για τον τύπο της πιθανότητας επιβίωσης ενός σχήματος (Κεφ. 4ο).

 

 Λύση


 

Άσκηση 9η

Ένας πληθυσμός περιλαμβάνει στη γενιά 0 τις ακόλουθες δυαδικές συμβολοσειρές και τις αντίστοιχες αποδόσεις τους:

 

A/A

Δυαδική συμβολοσειρά

Απόδοση

1

10001

20

2

11100

10

3

00011

5

4

01110

15

 

Η πιθανότητα μετάλλαξης είναι pm=0.01 και η πιθανότητα διασταύρωσης είναι pc=1.0.

α) Υπολογίστε τον αναμενόμενο αριθμό σχημάτων της μορφής S1=() που θα υπάρχουν στη γενιά 1.

β) Υπολογίστε τον αναμενόμενο αριθμό σχημάτων της μορφής S2=() που θα υπάρχουν στη γενιά 1.

 

Υπόδειξη: Εκτελέστε τον αλγόριθμο για μία γενιά και υπολογίστε τον αριθμό των ατόμων που ανήκουν σε κάθε σχήμα.

 

 Λύση


 

Άσκηση 10η

Πόσα διαφορετικά σχήματα υπάρχουν σε συμβολοσειρές με μήκος  όταν το αλφάβητο κωδικοποίησης που χρησιμοποιείται είναι το δυαδικό;

Πόσα διαφορετικά ξεχωριστά σχήματα τάξης 3 υπάρχουν σε δυαδικές συμβολοσειρές μήκους ;

Υπολογίστε το λογικό άνω και κάτω όριο για τον αριθμό των σχημάτων που επεξεργάζονται από ένα γενετικό αλγόριθμο όταν χρησιμοποιούνται δυαδικές συμβολοσειρές

μήκους  και ο πληθυσμός έχει μέγεθος m = 50.

Θεωρήστε ότι το μήκος του σημαντικού κορμού οικοδόμησης ισούται με το 10% του συνολικού μήκους της συμβολοσειράς.

 

 Λύση


 

Άσκηση 11η

Θεωρείστε ότι ένα σχήμα Η όταν υπάρχει σε μια συγκεκριμένη δυαδική συμβολοσειρά την κάνει να εμφανίζει απόδοση 25% μεγαλύτερη από τη μέση απόδοση του

τρέχοντος πληθυσμού.

Εάν οι πιθανότητες καταστροφής λόγω διασταύρωσης και μετάλλαξης για το παραπάνω σχήμα είναι αμελητέες, καθορίστε σε ποια γενιά το σχήμα Η θα επικρατήσει σε ένα

πληθυσμό μεγέθους n = 20, 50, 100 και 200, όταν ένας και μόνο ένας εκπρόσωπος του σχήματος αυτού περιέχεται στον πληθυσμό κατά τη γενιά 0.

 

Υπόδειξη: Το σχήμα Η θα επικρατήσει σε κάποιον πληθυσμό όταν οι συμβολοσειρές που ανήκουν σ’ αυτό αποτελούν τουλάχιστον το 50% του πληθυσμού αυτού.

 

 Λύση


 

Άσκηση 12η

Θεωρείστε ότι ένα σχήμα Η όταν υπάρχει σε μια συγκεκριμένη δυαδική συμβολοσειρά την κάνει να εμφανίζει απόδοση 10% μικρότερη από τη μέση απόδοση του τρέχοντος

πληθυσμού.

Εάν οι πιθανότητες καταστροφής λόγω διασταύρωσης και μετάλλαξης για το παραπάνω σχήμα είναι αμελητέες, καθορίστε σε ποια γενιά το σχήμα Η θα εξαφανιστεί από

ένα πληθυσμό μεγέθους n = 20, 50, 100 και 200, όταν οι εκπρόσωποι του σχήματος αυτού αποτελούν το 60% στον πληθυσμό κατά τη γενιά 0.

 

 Λύση


 

Άσκηση 13η

Θεωρήστε ένα πρόβλημα που είναι κωδικοποιημένο ως ένας χωρίς πρόσημο δυαδικός ακέραιος μεταξύ του 0 και του 127 (με βάση το 10), όπου 00000002=010,

10000002=6410 και 11111112=12710.

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

, , , , , .

 

Υπόδειξη: Βρείτε τις δυαδικές συμβολοσειρές που αντιστοιχούν σε καθένα από τα παραπάνω σχήματα και υπολογίστε το πλήθος των ακεραίων αριθμών που αντιπροσωπεύουν.

 

 Λύση


 

Άσκηση 14η

Δίνεται ο εξής πληθυσμός συμβολοσειρών τη γενιά 0: 11011, 01011, 11001, 10111

και η εξής αντικειμενική συνάρτηση:  , όπου το bi είναι το i-οστό δυαδικό ψηφίο (το πρώτο δυαδικό ψηφίο έχει δείκτη i=0).

Επίσης δίνεται η παρακάτω λίστα τυχαίων αριθμών που έχει παραχθεί με χρήση μιας γεννήτρια τυχαίων αριθμών:

0.25, 0.73, 0.15, 0.52, 0.81, 0.65

Θεωρήστε ότι:

1.       Ο Γ.Α. χρησιμοποιεί τελεστή επιλογής που βασίζεται στην απόδοση της αντικειμενικής συνάρτησης  κάθε ατόμου (κάθε άτομο επιλέγεται ανάλογα με την απόδοσή του) και πλήρη αντικατάσταση των ατόμων κάθε γενιάς (κανένας γονέας δεν αντιγράφεται στην επόμενη γενιά).

2.       Πιθανότητα μετάλλαξης ίση με 0.

3.       Η επιλογή των ατόμων που θα συμμετέχουν στη διασταύρωση γίνεται με βάση τον τελεστή επιλογής και τους τυχαίους αριθμούς που προέκυψαν από τη γεννήτρια τυχαίων αριθμών. Ο τελεστής διασταύρωσης  είναι μονού σημείου με πιθανότητα διασταύρωσης 1.0, με το σημείο διασταύρωσης να επιλέγεται τυχαία ανάμεσα στα τέσσερα πιθανά σημεία διασταύρωσης κάθε συμβολοσειράς. Με βάση κάποιο τυχαίο αριθμό τα σημεία διασταύρωσης θα επιλέγονται από τα αριστερά προς τα δεξιά με ίδια πιθανότητα και για τα τέσσερα πιθανά σημεία (0.25 για κάθε πιθανή θέση). Δηλαδή εάν ο τυχαίος αριθμός είναι ο 0.45 το σημείο διασταύρωσης θα είναι ανάμεσα στο δυαδικό ψηφίο 1 και το δυαδικό ψηφίο 2 (το πιο αριστερό ψηφίο έχει αριθμό 0).

4.       Και τα δύο παιδιά που προκύπτουν από μία διασταύρωση προστίθενται στον πληθυσμό της επόμενης γενιάς, επομένως μόνο δύο διασταυρώσεις χρειάζονται για να δημιουργηθεί ο πληθυσμός της γενιάς 1 από τον πληθυσμό της γενιάς 0.

Να υπολογίσετε τα ακόλουθα:

1.       Την απόδοση της αντικειμενικής συνάρτησης για κάθε άτομο του πληθυσμού στις γενιές 0 και 1.

2.       Την μέση απόδοση του πληθυσμού στις γενιές 0 και 1.

3.       Τη ρουλέτα που χρησιμοποιείτε για την επιλογή των ατόμων από τη γενιά 0. Να φαίνεται καθαρά το ποσοστό που αντιστοιχεί σε κάθε άτομο του αρχικού πληθυσμού.

4.       Τον πληθυσμό των ατόμων στη γενιά 1.

5.       Τον αριθμό των ατόμων του πληθυσμού που ανήκουν στα σχήματα 1###1 και ##01# στην γενιά 0 και στη γενιά 1.

6.    Τη μέση απόδοση των παραπάνω σχημάτων στη γενιά 0 και στη γενιά 1.

 

 Λύση


 

 

ΑΡΧΗ ΚΕΦΑΛΑΙΟΥ