Σ’ αυτή την ενότητα χρησιμοποιούμε ένα γενετικό αλγόριθμο για να εκπαιδεύσουμε ένα νευρωνικό δίκτυο να μάθει μια δοσμένη συνάρτηση (μια συνάρτηση Boolean) χωρίς τη χρήση κάποιου αλγορίθμου καθολικής μάθησης (δηλαδή Error Back-Propagation).
Το μοντέλο του νευρωνικού δικτύου που θα επεξεργαστεί ο γενετικός αλγόριθμος, επιλέχτηκε να είναι όσο πιο γενικό γίνεται. Έτσι, χρησιμοποιήσαμε το δίκτυο πολλαπλών επιπέδων Perceptron ( Multilayer Perceptron network). Όπως γνωρίζουμε, τα δίκτυα πολλαπλών επιπέδων Perceptron αποτελούν μια σημαντική κλάση πολλαπλών επιπέδων τροφοδοτούμενων προς τα μπρος (feedforward) δικτύων. Ένα χαρακτηριστικό δίκτυο αυτού του είδους αποτελείται από ένα σύνολο αισθητήριων νευρώνων (νευρώνες πηγής) που συγκροτούν το επίπεδο εισόδου, ένα ή περισσότερα κρυμμένα επίπεδα υπολογιστικών νευρώνων, και ένα επίπεδο εξόδου από υπολογιστικούς νευρώνες. Το σήμα εισόδου απλώνεται μέσα στο δίκτυο σε μια προς τα μπρος κατεύθυνση, από το ένα επίπεδο στο επόμενο. Στο μοντέλο του νευρωνικού δικτύου που υλοποιήσαμε έγιναν οι ακόλουθες υποθέσεις:
· Κάθε (υπολογιστικός) νευρώνας στο δίκτυο παριστάνεται από το μοντέλο McCulloch-Pitts. Υποθέτοντας ότι ο νευρώνας k παριστάνεται από αυτό το μοντέλο, το εσωτερικό επίπεδο δράσης του νευρώνα k, δίνεται από:
και η έξοδος του νευρώνα k είναι:
yk = 1, αν uk >= 0
ή
yk = 0, αλλιώς
όπου p είναι ο αριθμός των εισόδων, wkj ,j=1...p, είναι τα συναπτικά βάρη του νευρώνα k, xj ,j=1...p, είναι τα σήματα εισόδου, wk0 = qk το κατώφλι που χρησιμοποιείται στο νευρώνα k και x0 = -1 είναι το αντίστοιχο σήμα εισόδου.
· Τα bits 0 και 1 αναπαρίστανται από τα επίπεδα 0 και +1 αντίστοιχα.
Το μοντέλο του δικτύου είναι πλήρως συνδεδεμένο με τροφοδοτούμενες προς τα μπρος (feedforward) συνδέσεις (κάθε νευρώνας συνδέεται με κάθε άλλο νευρώνα με τροφοδοτούμενες προς τα μπρος συνάψεις). Έτσι, κάθε νευρώνας στο επίπεδο εισόδου συνδέεται με κάθε νευρώνα στα κρυμμένα επίπεδα, με τον ίδιο τρόπο που κάθε νευρώνας σε ένα κρυμμένο επίπεδο συνδέεται με κάθε νευρώνα στα επίπεδα που ακολουθούν. Το ίδιο ισχύει για τις συνδέσεις ανάμεσα στους νευρώνες των κρυμμένων επιπέδων και τους νευρώνες του επιπέδου εξόδου. Επιπλέον, εισάγουμε απ’ ευθείας συνδέσεις τροφοδοτούμενες προς τα εμπρός ανάμεσα στους νευρώνες εισόδου και εξόδου. Το σχήμα 9 απεικονίζει ένα τμήμα του γενικού μοντέλου του νευρωνικού δικτύου.
|
Ο στόχος της προσέγγισής μας ήταν να υλοποιήσουμε ένα νευρωνικό δίκτυο, που να μπορεί να πραγματοποιήσει την βέλτιστη δομή του δυναμικά. Γι’ αυτό, έχουμε χρησιμοποιήσει, δυναμικές δομές δεδομένων, όπως διασυνδεδεμένες λίστες. Το συνολικό νευρωνικό δίκτυο κατασκευάζεται σαν μια διασυνδεδεμένη λίστα επιπέδων. Ενώ κάθε επίπεδο οργανώνεται σαν μια διασυνδεδεμένη λίστα από νευρώνες και κάθε νευρώνας σαν μια διασυνδεδεμένη λίστα από συνάψεις (συνδέσεις), όπου κάθε σύναψη προσδιορίζεται από το νευρώνα στον οποίο συνδέεται και από την ισχύ της (βάρος). Έτσι μπορούμε να προσθέσουμε και να σβήσουμε επίπεδα από το νευρωνικό δίκτυο, να προσθέσουμε και να σβήσουμε νευρώνες από το δίκτυο ή από ένα επίπεδο, να προσθέσουμε και να σβήσουμε συνδέσεις, και ούτω καθεξής. Μια σύντομη παρουσίαση των βημάτων του αλγορίθμου, είναι χρήσιμη για την περιγραφή της υλοποίησης του:
1. Αρχικοποίηση : Δημιούργησε έναν αρχικό πληθυσμό από μονάδες (νευρωνικά δίκτυα). Κάθε μονάδα δημιουργείται με τυχαίο τρόπο. Κάθε νευρωνικό δίκτυο δημιουργείται μ’ αυτό τον τρόπο, μόνο ο αριθμός των εισόδων και εξόδων (και συνεπώς ο αριθμός των νευρώνων εισόδου και εξόδου) είναι σταθερός. Ο αριθμός των κρυμμένων επιπέδων καθώς και ο αριθμός των νευρώνων σε κάθε κρυμμένο επίπεδο επιλέγονται με τυχαίο τρόπο (με χρήση μιας γεννήτριας τυχαίων αριθμών). Με τον ίδιο τρόπο παράγουμε με τυχαίο τρόπο τα βάρη των συνάψεων στο διάστημα [-1,1]. Έτσι, στο τέλος της διαδικασίας αρχικοποίησης έχουμε έναν πληθυσμό από τυχαία παραγόμενες μονάδες (νευρωνικά δίκτυα).
2. Υπολόγισε την καταλληλότητα κάθε μονάδας: Παρουσίασε τα σχέδια εκπαίδευσης (σχέδια εισόδου και επιθυμητές έξοδοι), για κάθε σχέδιο εισόδου και υπολόγισε την έξοδο κάθε νευρώνα εξόδου του δικτύου και σύγκρινε αυτές με τις επιθυμητές εξόδους. Μ’ αυτό τον τρόπο, υπολογίζεται ο αριθμός των σωστών bits που έχουν μαθευτεί για κάθε σχέδιο εκπαίδευσης. Έτσι, αν η συνάρτηση που έχουμε να μάθουμε στο δίκτυο n bits εισόδου και r bits εξόδου, έχουμε να ελέγξουμε 2n ενδεχόμενα, που έχουν ως αποτέλεσμα 2n r bits να μπορεί να είναι true ή false. Ύστερα, εκτίμησε την απόδοση κάθε μονάδας (νευρωνικού δικτύου) χρησιμοποιώντας μια πολύ απλή συνάρτηση καταλληλότητας που ισοδυναμεί με τον αριθμό των σωστών bits της Boolean συνάρτησης. Τέλος, υπολόγισε τις συναρτήσεις καταλληλότητας κάθε μονάδας.
3. Επέλεξε και δημιούργησε ένα νέο πληθυσμό: Χρησιμοποιώντας σαν μέτρο τις συναρτήσεις καταλληλότητας των μονάδων, που υπολογίστηκαν στο προηγούμενο βήμα, επέλεξε αυτές τις μονάδες που πρόκειται να αντιγραφούν στο νέο πληθυσμό. Αυτό μπορεί να γίνει με διάφορους τρόπους. Ένας τρόπος είναι να βρεθούν οι καλύτερες μονάδες στον πληθυσμό ( αυτές με τις μεγαλύτερες συναρτήσεις καταλληλότητας), να απομακρυνθεί ένας ορισμένος αριθμός rd από τις χειρότερες μονάδες από τον πληθυσμό, και να αντιγραφούν, στη θέση τους, οι καλύτερες r1 φορές, οι δεύτερες καλύτερες r2 φορές, και τα λοιπά, έτσι ώστε πάντα rd=r1 + r2 + . . . ( υποθέτουμε ότι το μέγεθος του πληθυσμού είναι σταθερό). Ένας άλλος τρόπος είναι με χρήση της κλασσικής ή μιας elitist επιλογής τροχού ρουλέτας. Έχουμε υλοποιήσει και τις τρεις διαδικασίες επιλογής.
4. Μετάβαλε τις μονάδες: Με μια ορισμένη πιθανότητα επέλεξε μονάδες από τον πληθυσμό και απομάκρυνε ένα δοσμένο αριθμό νευρώνων από τα κρυφά επίπεδα και πρόσθεσε ένα δοσμένο αριθμό νευρώνων. Τα βάρη των νέων συνδέσεων κατανέμονται τυχαία στο διάστημα [-1,1]. Αυτό το είδος της μεταβολής δεν είναι το καλύτερο, αλλά ακόμα και αυτή η απλή ιδέα μεταβολής ταιριάζει για τη βελτίωση του μεγέθους ενός νευρωνικού δικτύου με τη χρήση γενετικών αλγορίθμων και είναι σημαντικό το ότι δεν είναι ανάγκη να καθορίσουμε μια πολύπλοκη δομή πληροφορίας ή ένα καθολικό κανόνα μάθησης.
Τα βήματα 2,3 και 4 επαναλαμβάνονται μέχρι να λυθεί το πρόβλημά μας ή μέχρις ότου ικανοποιηθεί μια συνθήκη εξόδου από το βρόχο (για παράδειγμα ένας μέγιστος αριθμός κύκλων). Το σχήμα 10 απεικονίζει την παραπάνω διαδικασία με ένα διάγραμμα ροής.
|
ΣΧΗΜΑ 10. Γενικό διάγραμμα ροής για την υλοποίηση του GA.
Η παραπάνω διαδικασία είναι κοινά αποδεκτή για την υλοποίηση ενός γενετικού αλγορίθμου. Η απόδοση του προτεινόμενου αλγορίθμου αποτιμήθηκε χρησιμοποιώντας διάφορες δυαδικές συναρτήσεις. Ένα πολύ δημοφιλές πρόβλημα που ένα νευρωνικό δίκτυο πρέπει να μπορεί να λύνει είναι το πρόβλημα XOR. Ο πίνακας 1 παρουσιάζει μερικά παραδείγματα μάθησης της απλής XOR συνάρτησης στο προτεινόμενο γενετικά εκπαιδευόμενο δίκτυο. Ο πίνακας 2 παρουσιάζει το μέσο αριθμό γενεών, που χρειάζονται για να λυθεί το πρόβλημα XOR, και το μέσο αριθμό νευρώνων στα κρυφά επίπεδα του καλύτερου δικτύου. Για να πάρουμε τον πίνακα 2 τρέξαμε το πρόγραμμά μας για το XOR πρόβλημα έναν επαρκή αριθμό φορών.
Αριθμός Γενεών |
Αριθμός Κρυφών Νευρώνων |
15 |
2 |
0 |
2 |
8 |
11 |
102 |
6 |
123 |
3 |
ΠΙΝΑΚΑΣ 1. Τα πρώτα πέντε τρεξίματα με μέγεθος πληθυσμού ίσο με δέκα νευρωνικά δίκτυα.
Μέγεθος Πληθυσμού |
Μέσος Αριθμός Γενεών |
Μέσος Αριθμός Κρυφών Νευρώνων |
10 |
52.45 |
7,38 |
20 |
30.38 |
7,30 |
ΠΙΝΑΚΑΣ 2. Ο μέσος αριθμός γενεών που απαιτούνται για το πρόβλημα XOR, και ο μέσος αριθμός κρυφών νευρώνων στο καλύτερο δίκτυο, για 40 τρεξίματα.
Στον πίνακα 3 παρουσιάζουμε μερικά παραδείγματα μάθησης μιας απλής XOR συνάρτησης σε ένα γενετικά εκπαιδευόμενο νευρωνικό δίκτυο, από την προσέγγιση που αναφέρεται στο [19]. Σ΄ αυτή την εργασία χρησιμοποιείται ένα αμβλυμμένο (diluted) βιολογικό νευρωνικό δίκτυο. Τα καλύτερης ποιότητας αποτελέσματα που απεικονίζονται από το γενικό μοντέλο, σε σχέση με αυτά του διαλυμένου μοντέλου, απαληθεύουν ότι οι συνδέσεις εισόδου-εξόδου βελτιώνουν τη μάθηση.
Μέγεθος Πληθυσμού |
Αριθμός Γενεών |
Αριθμός Κρυφών Νευρώνων |
10 |
1200 |
22 |
10 |
2400 |
7 |
10 |
5000 |
8 |
10 |
5500 |
13 |
10 |
6000 |
12 |
ΠΙΝΑΚΑΣ 3. Ο αριθμός των γενεών και των κρυμμένων νευρώνων (που αναφέρονται στο [19])
Τέλος, ένα παράδειγμα αναπαράστασης ενός νευρωνικού δικτύου που βγαίνει χρησιμοποιώντας το γενικό μοντέλο και εξελικτικές (evolution) τεχνικές, για το πρόβλημα XOR απεικονίζεται στο σχήμα 11.
|
ΣΧΗΜΑ 11. Ένα γενετικά παραγόμενο νευρωνικό δίκτυο που επιλύει το πρόβλημα XOR.