Άσκηση 5η
α) Αναφέρετε δύο στοιχεία του σχεδιασμού ενός Γ.Α. που μπορεί να οδηγήσουν ένα πληθυσμό σε πρόωρη σύγκλιση. Αναφερθείτε στα δύο βασικά βήματα ενός Γ.Α. (επιλογή και διασταύρωση).
2. β) Εξηγείστε σε 2-3 γραμμές γιατί η πιθανότητα μετάλλαξης πρέπει να διατηρείται σε χαμηλές τιμές σε ένα Γ.Α.
Λύση:
α) Όπως γνωρίζετε,
το φαινόμενο της πρόωρης σύγκλισης έχει ως αποτέλεσμα την επικράτηση στον
πληθυσμό του Γ.Α., από τις αρχικές γενιές, κάποιων ατόμων τα οποία δεν είναι τα
βέλτιστα.
Αυτό το φαινόμενο συνήθως οδηγεί σε τοπικά βέλτιστα και όχι στην εύρεση της
ολικά βέλτιστης λύσης. Σε αυτό συμβάλλει σε μεγάλο βαθμό ο τρόπος με τον οποίο
τα άτομα επιλέγονται για διασταύρωση και για αντιγραφή στην επόμενη γενιά.
Επομένως, για την αποφυγή της πρόωρης σύγκλισης πρέπει να χρησιμοποιούνται
τεχνικές που να μην επιτρέπουν σε κάποια άτομα να επικρατούν πρόωρα στον
πληθυσμό του Γ.Α. Η βασικότερη τεχνική αυτού του είδους είναι η τεχνική της
διαβάθμισης η οποία βελτιώνει τον τρόπο με τον οποίο γίνεται η επιλογή των
ατόμων για διαστεύρωση και αντιγραφή στην επόμενη γενιά. Επίσης, σημαντικό ρόλο
παίζει και ο ίδιος ο τελεστής διασταύρωσης που χρησιμοποιείται (π.χ. ο τελεστής
διασταύρωσης πολλαπλού σημείου επιτρέπει λιγότερο την εμφάνιση πρόωρης σύγκλισης
σε σχέση με τον τελεστή διασταύρωσης μονού σημείου).
β) Η πιθανότητα μετάλλαξης πρέπει να διατηρείται σε χαμηλές τιμές (της τάξης του 0.001) γιατί διαφορετικά η αναζήτηση εκφυλίζεται σε τυχαίο ψάξιμο και δεν μπορεί ο αλγόριθμος να δώσει σωστά αποτελέσματα.