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

 

9.3     Ο Γενετικος Αλγοριθμος

 

Το GAlib υποστηρίζει τρεις τύπους Γ.Α. (σαν ονόματα θα δίνονται πάντα τα ονόματα των αντίστοιχων κλάσεων της βιβλιοθήκης):

 

·                    GASimpleGA: ο βασικός Γ.Α. που περιγράφεται στο βιβλίο του Goldberg [29] και ο οποίος χρησιμοποιεί μη επικαλυπτόμενους πληθυσμούς,

·                    GASteadyStateGA: ο Γ.Α. που περιγράφεται από τον De Jong στο [21] και ο οποίος χρησιμοποιεί επικαλυπτόμενους πληθυσμούς και

·                    GAIncrementalGA: ο Γ.Α. που υλοποιείται στο μοντέλο GENITOR και ο οποίος χρησιμοποιεί μεν επικαλυπτόμενους πληθυσμούς, αλλά με πολύ μικρό ποσοστό επικά-λυψης.

 

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

Επιπλέον, το αντικείμενο του Γ.Α. καταγράφει διάφορα στατιστικά στοιχεία, όπως τρέχον αριθμός γενιάς και καλύτερο τρέχον άτομο (στην πραγματικότητα περιέχει σαν data member ένα αντικείμενο της κλάσης GAStatistics, η οποία υποστηρίζει πολλές δυνατότητες για καταγραφή και επεξεργασία στατιστικών στοιχείων), περιέχει τις παραμέτρους του Γ.Α., όπως ενεργοποίηση ή μη του ελιτισμού (στην πραγματικότητα περιέχει ένα αντικείμενο της κλάσης GAParameterList για το χειρισμό των παραμέτρων) και τον τρόπο επιλογής των ατόμων (όμοια σαν αντικείμενο της κλάσης GASelectionScheme).  Η κλάση GASelectionScheme αποτελεί abstract class και κατά την κατασκευή του αντικειμένου του Γ.Α. θα πρέπει να προσδιοριστεί μια derived class της GASelectionScheme (αυτή η ενέργεια δεν είναι απαραίτητη εάν χρησιμοποιηθεί το default σχήμα επιλογής).  Μερικές από τις κλάσεις που παρέχει το GAlib για την επιλογή των ατόμων είναι:

 

·                    Roulette Wheel Selector: στην επιλογή αυτή, κάθε φορά η πιθανότητα p για την επιλογή ενός ατόμου είναι ίση με την απόδοση (fitness) του ατόμου προς το συνολικό άθροισμα των αποδόσεων όλων των ατόμων του πληθυσμού (population fitness), δηλαδή όσο μεγαλύτερο είναι το score ενός ατόμου (που επιστρέφεται από την αντικειμενική συνάρτηση), τόσο μεγαλύτερη είναι η πιθανότητα να επιλεγεί (αυτή είναι και η καλύτερη μέθοδος για τα περισσότερα προβλήματα, αφού επιτυγχάνει το συνδυασμό γενετικού υλικού από "καλά" άτομα, χωρίς παράλληλα να χάνει βασικές γενετικές πληροφορίες με αποτέλεσμα να οδηγείται σε μια τοπική βέλτιστη λύση)

·                    Tournament Roulette Wheel Selector: όταν χρησιμοποιείται αυτή η μέθοδος, κάθε φορά επιλέγονται δυο άτομα με την Roulette Wheel και στη συνέχεια επιλέγεται αυτό με το καλύτερο fitness (ο τρόπος αυτός επιλογής δίνει καλύτερα αποτελέσματα από τον απλό Roulette Wheel σe αρκετές περιπτώσεις, όπου υπάρχει γενικά ανάγκη για επιλογή σχετικά καλύτερων ατόμων από τον πληθυσμό)

 

·                    Uniform Selector: στη μέθοδο αυτή, κάθε φορά επιλέγεται ένα τυχαίο άτομο, χωρίς να λαμβάνονται υπ' όψη τα fitnesses (δηλαδή η πιθανότητα επιλογής ενός ατόμου είναι ίση με το λόγο 1/N, όπου N το μέγεθος του πληθυσμού), δηλαδή ο Γ. Α. ισοδυναμεί με τυχαίο ψάξιμο στο χώρο λύσεων

 

Τέλος, το αντικείμενο του Γ.Α. περιέχει και ένα αντικείμενο της κλάσης GAPopulation, το οποίο περιέχει τον πληθυσμό των ατόμων και τις μεθόδους για την διαχείρισή του.  Το αντι-κείμενο αυτό είναι συνδεδεμένο με το αντικείμενο που υλοποιεί το σχήμα επιλογής των ατόμων.

 

 

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