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

 

5.3     αμβλυνση του Ανταγωνισμου - Αποφυγη προωρης συγκλισης

 

Μετά από την παραγωγή μερικών γενεών, ο Γ.Α. αρχίζει σιγά σιγά να συγκλίνει προς το βέλτιστο σημείο του χώρου αναζήτησης. Ο όρος “σύγκλιση”, όσον αφορά τα άτομα του πληθυσμού, σημαίνει ότι τα περισσότερα από αυτά μοιάζουν αρκετά μεταξύ τους. Άμεσο αποτέλεσμα αυτού είναι οι ικανότητές τους να διαφέρουν από ελάχιστα έως καθόλου και κατά συνέπεια στην επιλογή υπάρχει πολύ μεγάλος ανταγωνισμός για το ποιος θα δώσει απογόνους στην επόμενη γενιά. Έτσι, τα άτομα που είναι τα πιο ικανά, έστω και με ελάχιστη διαφορά, δεν κατορθώνουν -κατά πάσα πιθανότητα- να επιβληθούν μέσα στο περιβάλλον τους και η πρόοδος του αλγορίθμου από ένα σημείο και πέρα γίνεται με πολύ αργούς ρυθμούς, χωρίς όμως η σύγκλιση να γίνεται προς το βέλτιστο σημείο, αλλά προς ένα τοπικό ακρότατο. Το φαινόμενο αυτό ονομάζεται πρόωρη σύγκλιση (premature convergence).

 

Η πρόωρη σύγκλιση μπορεί να αποφευχθεί με χρήση μηχανισμών διαβάθμισης (scaling mechanisms). Πρόκειται για τεχνικές που έχουν στόχο την επαύξηση των διαφορών -όσο μικρές κι αν είναι- των ικανοτήτων των ατόμων και την πιο εύκολη ανάδειξη των καλύτερων μέσα από την λειτουργία της επιλογής. Με τους μηχανισμούς διαβάθμισης εγκαταλείπεται το κλασσικό μοντέλο της ρουλέτας και πλέον οι ευκαιρίες των ατόμων στην επιλογή δεν είναι ανάλογες της ικανότητάς τους. Οι κυριότεροι μηχανισμοί που σήμερα επικρατούν είναι:

·           Γραμμική διαβάθμιση (Linear scaling).

·           Εκθετική διαβάθμιση (Power law scaling).

·           Διαβάθμιση με βάση τη σειρά (Fitness ranking).

·           Παραθυροποίηση (Windowing).

 

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

όπου τα ,  υπολογίζονται με βάση τις εξής δύο συνθήκες:

1)        ο μέσος όρος των ικανοτήτων πριν και μετά τον μετασχηματισμό να μην αλλάζει και

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

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

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

Στη διαβάθμιση με βάση τη σειρά, στους μετασχηματισμούς που λαμβάνουν χώρα, δε χρησιμοποιείται καμία παράμετρος. Τα άτομα ταξινομούνται με βάση τις ικανότητές τους από το μικρότερο προς το μεγαλύτερο. Αποδίδεται στο μικρότερο μια νέα ικανότητα και συνεχίζοντας διαδοχικά προς το μεγαλύτερο, οι νέες ικανότητες αυξάνουν κατά μία σταθερή τιμή.

 

Η παραθυροποίηση είναι τεχνική που χρησιμοποιείται στο πακέτο γενετικού προγραμματισμού GENESIS. Σύμφωνα με αυτήν, οι τιμές των ικανοτήτων τροποποιούνται πριν από την επιλογή ως εξής: Αφαιρείται από την ικανότητα κάθε ατόμου ποσό ίσο με την μικρότερη ικανότητα που υπάρχει στον πληθυσμό. Έτσι, οι διαφορές ικανοτήτων των ατόμων γίνονται πιο εμφανείς. Επειδή όμως κατ' αυτόν τον τρόπο, τα λιγότερο ικανά άτομα έχουν μηδαμινές ευκαιρίες επιλογής, μπορεί να τεθεί ένα κάτω όριο των ικανοτήτων μεγαλύτερου του μηδενός. Όλα αυτά φαίνονται καλύτερα στο παράδειγμα του ακόλουθου πίνακα.

 

Πραγματικές ικανότητες

150

148

147

140

138

137

Παραθυροποίηση με κάτω όριο 0

13

11

10

3

1

0

Παραθυροποίηση με κάτω όριο 3

13

11

10

3

3

3

Στην πρώτη σειρά του πίνακα φαίνονται οι ικανότητες ενός πληθυσμού στην εξέλιξη του Γ.Α. Ο πληθυσμός έχει συγκλίνει, που σημαίνει ότι δεν υπάρχει μεγάλο εύρος ποικιλίας στις τιμές των ικανοτήτων. Κάνοντας την επιλογή με τις πραγματικές ικανότητες, ο ανταγωνισμός των ατόμων στην κατανομή των απογόνων θα είναι μεγάλος. Η μεγαλύτερη ικανότητα είναι μόλις 1.09 φορές μεγαλύτερη της μικρότερης. Τα τμήματα της ρουλέτας που αντιστοιχούν σε αυτόν τον πληθυσμό δεν θα διαφέρουν κατά πολύ μεταξύ τους σε μέγεθος και είναι δύσκολο για το ικανότερο άτομο να κυριαρχήσει.

 

Με την παραθυροποίηση τα πράγματα βελτιώνονται. Από την κάθε ικανότητα αφαιρείται η τιμή 137 (που είναι η μικρότερη του πληθυσμού) και οι νέες ικανότητες έχουν μεγαλύτερες σχετικές διαφορές. Η μικρότερη όμως ικανότητα είναι 0, που σημαίνει ότι δε θα έχει καθόλου ευκαιρίες αναπαραγωγής στην επιλογή. Επειδή κάτι τέτοιο δεν είναι επιθυμητό, ορίζεται ένα μεγαλύτερο κάτω όριο (π.χ. 3) για τις νέες ικανότητες, ώστε να εξασφαλίζονται ευκαιρίες για όλα τα άτομα. Τελικά, όπως φαίνεται από τις τιμές στην τρίτη σειρά του πίνακα, τα καλύτερα άτομα πλέον θα μπορέσουν να επιβληθούν πιο εύκολα στις επόμενες γενιές. Ο νέος λόγος μεγαλύτερου προς μικρότερο είναι τώρα 4.33, πράγμα που σημαίνει ότι οι ευκαιρίες του ικανότερου ατόμου έχουν αυξηθεί κατά πολύ.

 

 

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