ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
Άσκηση 1η
α) Να αναφέρεται ένα πρόβλημα βελτιστοποίησης του οποίου η λύση μπορεί να κωδικοποιηθεί με ένα χρωμόσωμα και ένα του οποίου η κωδικοποίηση της λύσης απαιτεί ένα γονότυπο.
β) Ποιο στοιχείο είναι εκείνο που επιτρέπει στους Γ.Α. να κάνουν παράλληλη επεξεργασία δεδομένων; Να αιτιολογήσετε την απάντησή σας σε πέντε σειρές.
Υπόδειξη: α) Το γονότυπο αποτελείται από πολλά χρωμοσώματα μαζί.
β) Ο πληθυσμός ενός Γ.Α. αποτελείται από πολλά διαφορετικά, ανεξάρτητα μεταξύ τους, άτομα.
Άσκηση 2η
1. α) Αν κατά το τρέξιμο ενός Γ.Α. σε κάποια γενιά τα καλύτερα άτομα που θα προκύψουν δίνουν χειρότερες τιμές για την αντικειμενική συνάρτηση,
σε σχέση με τους προγόνους τους, πρέπει να διακοπεί η εκτέλεση του αλγορίθμου;
2. β) Όταν τελειώσει η εκτέλεση του αλγορίθμου, αφού πρώτα ικανοποιηθεί η συνθήκη τερματισμού, πως μπορούμε να είμαστε σίγουροι
ότι το καλύτερο χρωμόσωμα της τελευταίας γενιάς είναι το καλύτερο που έχει εμφανιστεί σε όλες τις γενιές;
Υπόδειξη: α) Η βελτίωση της απόδοσης "πρέπει" να είναι συνεχής; (Σκεφτείτε την περίπτωση τοπικών ακρότατων).
β) "Ελιτισμός".
Άσκηση 3η
Έξι συμβολοσειρές έχουν τις ακόλουθες τιμές της αντικειμενικής συνάρτησης: 5, 10, 15, 25, 50, 100. Κάνοντας χρήση της εξαναγκασμένης
ρουλέτας, να υπολογίσετε τον αναμενόμενο αριθμό αντιγράφων κάθε συμβολοσειράς στο νέο πληθυσμό, αν σε κάθε γενιά διατηρείται
ένας σταθερός πληθυσμός μεγέθους n=6.
Υπόδειξη: Χρησιμοποιείστε τον τύπο της εξαναγκασμένης ρουλέτας για τον υπολογισμό των πιθανών αντιγράφων στο νέο πληθυσμό.
Άσκηση 4η
Έστω ότι θέλετε να υλοποιήσετε ένα Γ.Α., ο οποίος από ένα πληθυσμό 100 ατόμων θα ξεχωρίζει εκείνο το χρωμόσωμα (μήκους 100), το οποίο περιέχει τους περισσότερους άσους. Ποια αντικειμενική συνάρτηση θα χρησιμοποιήσετε;
Άσκηση 5η
α) Αναφέρετε δύο στοιχεία του σχεδιασμού ενός Γ.Α. που μπορεί να οδηγήσουν ένα πληθυσμό σε πρόωρη σύγκλιση. Αναφερθείτε στα δύο βασικά βήματα ενός Γ.Α. (επιλογή και διασταύρωση).
2. β) Εξηγείστε σε 2-3 γραμμές γιατί η πιθανότητα μετάλλαξης πρέπει να διατηρείται σε χαμηλές τιμές σε ένα Γ.Α.
Υπόδειξη: α) Αναφερθείτε στον τρόπο επιλογής των ατόμων για διασταύρωση.
β) Με τι ισοδυναμεί ένας Γ. Α. με πιθανότητα μετάλλαξης ίση με 1;
Άσκηση 6η
Συζητήστε το ζήτημα "εξερεύνηση εναντίον εκμετάλλευσης" (exploration vs exploitation) στους Γ.Α.
Άσκηση 7η
Έστω ότι θέλουμε να ελαχιστοποιήσουμε τη συνάρτηση f(x)=-x2+5x+3 όπου το x ανήκει στο διάστημα [0, 63]. Πόσα δυαδικά ψηφία θα χρειαστούν για να κωδικοποιηθούν όλες οι πιθανές ακέραιες τιμές του x στο διάστημα 0 έως 63;
Άσκηση 8η
Επιλέξτε τη σωστή απάντηση.
Οι Γ.Α. θεωρούναι μία από τις πιο εύρωστες και αποδοτικές μεθόδους άμεσης αναζήτησης και βελτιστοποίησης, διότι:
1. Είναι σε θέση να συνδυάζουν στοιχεία από άμεσες και πιο στοχαστικές τεχνικές αναζήτησης.
2. Είναι στοχαστικοί αλγόριθμοι και λειτουργούν προσεγγιστικά
3. Διατηρούν ένα πληθυσμό πιθανών λύσεων πάνω στον οποίο πειραματίζονται σε αντίθεση με άλλες μεθόδους αναζήτησης, που επεξεργάζονται ένα μόνο σημείο του χώρου αναζήτησης κάθε φορά.
4. Το 1 και το 2.
5. Το 1 και το 3.
6. Όλα τα παραπάνω.
Υπόδειξη: Η λύση βρίσκεται στις υποενότητες 1.6 και 2.1.
Άσκηση 9η
Επιλέξτε τη σωστή απάντηση.
Η εφαρμογή των Γ.Α. σε μεγάλο φάσμα εφαρμογών οφείλεται:
1. Στο ότι η μόνη επικοινωνία τους με το περιβάλλον είναι η αντικειμενική συνάρτηση.
2. Στη χρησιμοποίηση μόνο πληροφοριών της συνάρτησης, που πρόκειται να βελτιστοποιήσουν, δίχως να ενδιαφέρει άμεσα ο ρόλος της μέσα στο σύστημα ή η ίδια η δομή του συστήματος.
3. Στο ότι είναι εύκολα επεκτάσιμοι και εξελίξιμοι και μπορούν να συμμετέχουν σε υβριδικές μορφές με άλλες μεθόδους.
4. Στην ελευθερία επιλογής των κριτηρίων, τα οποία καθορίζουν την επιλογή μέσα στο τεχνητό περιβάλλον και η μή απαίτηση για ύπαρξη περιορισμών.
5. Σε όλα τα παραπάνω.
1.
Υπόδειξη: Η λύση βρίσκεται στις υποενότητες 1.6 και 2.1.