ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
Ας θεωρήσουμε ένα παράδειγμα.
Εξομοιώνουμε τον παραπάνω Γ.Α. για τη βελτιστοποίηση μιας συνάρτησης. Έστω
,
και
. Ας υποθέσουμε ότι θέλουμε να μεγιστοποιήσουμε την ακόλουθη
συνάρτηση:
,
με
και
.
Ας υποθέσουμε ακόμη ότι η
απαιτούμενη ακρίβεια είναι τεσσάρων δεκαδικών ψηφίων για κάθε μεταβλητή. Το
εύρος τιμών της μεταβλητής έχει μήκος
, άρα το διάστημα
θα πρέπει να διαχωριστεί σε
ίσα υποδιαστήματα. Αυτό σημαίνει ότι
δυαδικά ψηφία απαιτούνται για τη δυαδική αναπαράσταση της
(και τα οποία θα αποτελούν το πρώτο τμήμα του χρωμοσώματος),
αφού:
.
Η ίδια διαδικασία για τη
προσδιορίζει το
σαν τον απαιτούμενο αριθμό δυαδικών ψηφίων για την
αναπαράσταση των δεκαδικών τιμών της. Επομένως, το συνολικό μήκος του
χρωμοσώματος είναι
δυαδικά ψηφία.
Έστω το άτομο:
.
Τα πρώτα
δυαδικά ψηφία (
) αναπαριστούν τον αριθμό (από την εξίσωση 2.1)
και τα επόμενα
δυαδικά ψηφία (
) τον αριθμό
. Δηλαδή, το άτομο αυτό αντιστοιχεί στο ζεύγος
.
Η απόδοση για αυτό το
χρωμόσωμα είναι .
Ας υποθέσουμε ότι μετά τη διαδικασία της αρχικοποίησης προκύπτει ο ακόλουθος πληθυσμός:
Αρχικά αποκωδικοποιούμε κάθε χρωμόσωμα και υπολογίζουμε την απόδοσή του. Έτσι έχουμε:
eval(v1) |
= |
f(6.084492, 5.652242) |
= |
26.019600 |
eval(v2) |
= |
f(10.348434, 4.380264) |
= |
7.580015 |
eval(v3) |
= |
f(-2.516603, 4.390381) |
= |
19.526329 |
eval(v4) |
= |
f(5.278638, 5.593460) |
= |
17.406725 |
eval(v5) |
= |
f(-1.255173, 4.734458) |
= |
25.341160 |
eval(v6) |
= |
f(-1.811725, 4.391937) |
= |
18.100417 |
eval(v7) |
= |
f(-0.991471, 5.680258) |
= |
16.020812 |
eval(v8) |
= |
f(4.910618, 4.703018) |
= |
17.959701 |
eval(v9) |
= |
f(0.795406, 5.381472) |
= |
16.127799 |
eval(v10) |
= |
f(-2.554851, 4.793707) |
= |
21.278435 |
eval(v11) |
= |
f(3.130078, 4.996097) |
= |
23.410669 |
eval(v12) |
= |
f(9.356179, 4.239457) |
= |
15.011619 |
eval(v13) |
= |
f(11.134646, 5.378671) |
= |
27.316702 |
eval(v14) |
= |
f(1.335944, 5.151378) |
= |
19.876294 |
eval(v15) |
= |
f(11.089025, 5.054515) |
= |
30.060205 |
eval(v16) |
= |
f(9.211598, 4.993762) |
= |
23.867227 |
eval(v17) |
= |
f(3.367514, 4.571343) |
= |
13.696165 |
eval(v18) |
= |
f(3.843020, 5.158226) |
= |
15.414128 |
eval(v19) |
= |
f(-1.746635, 5.395584) |
= |
20.095903 |
eval(v20) |
= |
f(7.935998, 4.757338) |
= |
13.666916 |
Είναι εμφανές ότι το άτομο v15 είναι αυτό με την καλύτερη απόδοση και το άτομο v2 με τη χειρότερη απόδοση στον αρχικό πληθυσμό.
Στην συνέχεια κατασκευάζουμε μια ρουλέτα (roulette wheel). Η συνολική απόδοση (fitness) του πληθυσμού είναι:
Η πιθανότητα επιλογής pi κάθε μέλους το πληθυσμού vi , i=1,…,20, είναι:
p1 = eval(v1)/F = 0.067099 |
p11 = eval(v11)/F = 0.060372 |
p2 = eval(v2)/F = 0.019547 |
p12 = eval(v12)/F = 0.038712 |
p3 = eval(v3)/F = 0.050355 |
p13 = eval(v13)/F = 0.070444 |
p4 = eval(v4)/F = 0.044889 |
p14 = eval(v14)/F = 0.051257 |
p5 = eval(v5)/F = 0.065350 |
p15 = eval(v15)/F = 0.077519 |
p6 = eval(v6)/F = 0.046677 |
p16 = eval(v16)/F = 0.061549 |
p7 = eval(v7)/F = 0.041315 |
p17 = eval(v17)/F = 0.035320 |
p8 = eval(v8)/F = 0.046315 |
p18 = eval(v18)/F = 0.039750 |
p9 = eval(v9)/F = 0.041590 |
p19 = eval(v19)/F = 0.051823 |
p10 = eval(v10)/F = 0.054873 |
p20 = eval(v20)/F = 0.035244 |
Οι συσωρευμένες πιθανότητες (cumulative probabilities) qi για κάθε άτομο vi ,i=1,…,20 του πληθυσμού είναι:
q1 = 0.067099 |
q6 = 0.293917 |
q11 = 0.538381 |
q16 = 0.837863 |
q2 = 0.086647 |
q7 = 0.335232 |
q12 = 0.577093 |
q17 = 0.873182 |
q3 = 0.137001 |
q8 = 0.381546 |
q13 = 0.647537 |
q18 = 0.912932 |
q4 = 0.181890 |
q9 = 0.423137 |
q14 = 0.698794 |
q19 = 0.964756 |
q5 = 0.247240 |
q10 = 0.478009 |
q15 = 0.776314 |
q20 = 1.000000 |
Τώρα είμαστε έτοιμοι να περιστρέψουμε τη ρουλέτα 20 φορές; σε κάθε περιστροφή επιλέγουμε και ένα άτομο για το νέο πληθυσμό. Υποθέτουμε ότι έχουμε παράγει την εξής ακολουθία 20 τυχαίων αριθμών στο διάστημα [0, 1]:
0.513870 |
0.175741 |
0.308652 |
0.534534 |
0.947628 |
0.171736 |
0.702231 |
0.226431 |
0.494773 |
0.424720 |
0.703899 |
0.389647 |
0.277226 |
0.368071 |
0.983437 |
0.005398 |
0.765682 |
0.646473 |
0.767139 |
0.780237 |
Ο πρώτος αριθμός r = 0.513870 είναι μεγαλύτερος του q10 και μικρότερος του q11, γεγονός που σημαίνει ότι το άτομο v11 επιλέγεται για να «περάσει» στο νέο πληθυσμό. Ο δεύτερος αριθμός r = 0.175741 είναι μεγαλύτερος του q3 και μικρότερος του q4, οπότε το άτομο v4 επιλέγεται για το νέο πληθυσμό. Συνεχίζοντας με τον ίδιο τρόπο κατασκευάζουμε το νέο πληθυσμό:
v1* |
= |
(011001111110110101100001101111000) |
(v11) |
v2* |
= |
(100011000101101001111000001110010) |
(v4) |
v3* |
= |
(001000100000110101111011011111011) |
(v7) |
v4* |
= |
(011001111110110101100001101111000) |
(v11) |
v5* |
= |
(000101010011111111110000110001100) |
(v19) |
v6* |
= |
(100011000101101001111000001110010) |
(v4) |
v7* |
= |
(111011101101110000100011111011110) |
(v15) |
v8* |
= |
(000111011001010011010111111000101) |
(v5) |
v9* |
= |
(011001111110110101100001101111000) |
(v11) |
v10* |
= |
(000010000011001000001010111011101) |
(v3) |
v11* |
= |
(111011101101110000100011111011110) |
(v15) |
v12* |
= |
(010000000101100010110000001111100) |
(v9) |
v13* |
= |
(000101000010010101001010111111011) |
(v6) |
v14* |
= |
(100001100001110100010110101100111) |
(v8) |
v15* |
= |
(101110010110011110011000101111110) |
(v20) |
v16* |
= |
(100110100000001111111010011011111) |
(v1) |
v17* |
= |
(000001111000110000011010000111011) |
(v10) |
v18* |
= |
(111011111010001000110000001000110) |
(v13) |
v19* |
= |
(111011101101110000100011111011110) |
(v15) |
v20* |
= |
(110011110000011111100001101001011) |
(v16) |
Στην τελευταία στήλη, μέσα σε παρένθεση, φαίνονται τα άτομα του αρχικού πληθυσμού που έχουν περάσει (αντιγραφεί) στην επόμενη γενιά. Παρατηρούμε ότι ορισμένα άτομα έχουν αντιγραφεί περισσότερες από μία φορές, κάποια άλλα μόνο μία και μερικά δεν υπάρχουν καθόλου, ανάλογα με την απόδοσή τους. Ο παραπάνω πληθυσμός αποτελεί τη δεξαμενή ζευγαρώματος, στην οποία θα εφαρμοστεί η διασταύρωση.
Για κάθε άτομο στον πληθυσμό
επιλέγουμε ένα τυχαίο αριθμό από 0 ως 1. Εάν
, επιλέγουμε το τρέχων άτομο για διασταύρωση.
Ας υποθέσουμε ότι η ακολουθία των τυχαίων αριθμών είναι:
Αυτό σημαίνει ότι τα άτομα
,
,
και
επιλέχθηκαν για διασταύρωση (ο αριθμός των ατόμων είναι ζυγός,
οπότε το ταίριασμά τους είναι εύκολο - στην περίπτωση που ο αριθμός του ήταν
μονός, θα έπρεπε είτε να επιλέξουμε ένα ακόμα άτομο από τον πληθυσμό, ή να
απορρίψουμε κάποιο από αυτά). Στη συνέχεια, ταιριάζουμε με τυχαίο τρόπο άτομα
για ζευγάρωμα. Ας υποθέσουμε ότι ζευγαρώνουν τα πρώτα δύο (
και
) και τα επόμενα δύο (
και
).
Έστω ότι για το πρώτο ζευγάρι
επιλέχθηκε, σαν σημείο διασταύρωσης,
:
.
Τότε, αυτά θα αντικατασταθούν από τα άτομα-απογόνους:
.
Έστω ότι για το δεύτερο
ζευγάρι επιλέχθηκε, σαν σημείο διασταύρωσης,
:
.
Τότε, αυτά θα αντικατασταθούν από τα άτομα-απογόνους:
.
Οπότε, η τρέχουσα μορφή του πληθυσμού έχει ως εξής:
Για τον επόμενο τελεστή, την
μετάλλαξη, είναι , άρα αναμένουμε ότι το 1% περίπου όλων των δυαδικών ψηφίων
του πληθυσμού θα αντιστραφούν. Ο πληθυσμός μας αποτελείται από
δυαδικά ψηφία, άρα αναμένουμε περίπου
μεταλλάξεις ανά γενιά. Για κάθε δυαδικό ψηφίο, πρέπει να
παράγουμε ένα τυχαίο αριθμό
από το διάστημα
. Εάν
, αντιστρέφουμε το δυαδικό ψηφίο.
Έτσι, πρέπει να παράγουμε
τυχαίους αριθμούς. Στον ακόλουθο πίνακα, φαίνονται -για μία
τέτοια εκτέλεση- οι θέσεις στον πληθυσμό των δυαδικών ψηφίων που επελέχθησαν για
μετάλλαξη, ο αριθμός του ατόμου που αντιστοιχούν, καθώς και η θέση τους στα
αντίστοιχα άτομα.
Δηλαδή, τέσσερα άτομα του πληθυσμού θα υποστούν μετάλλαξη. Ακολουθεί ο τελικός πληθυσμός για την τρέχουσα γενιά.
Είναι ενδιαφέρον να δούμε τις αποδόσεις των ατόμων στο νέο πληθυσμό. Αυτό φαίνεται παρακάτω.
Παρατηρείται ότι η συνολική
απόδοση του νέου πληθυσμού είναι
, πολύ μεγαλύτερη από τη συνολική απόδοση του προηγούμενου
πληθυσμού που ήταν
. Επίσης, το χρωμόσωμα με την καλύτερη απόδοση στον καινούριο
πληθυσμό, το
, έχει μεγαλύτερη απόδοση από το χρωμόσωμα με την καλύτερη
απόδοση του προηγούμενου πληθυσμού, το
,
έναντι
.
Τα παραπάνω βήματα του αλγορίθμου επαναλαμβάνονται κυκλικά, μέχρις ότου το κριτήριο τερματισμού ικανοποιηθεί. Συνήθως, το κριτήριο τερματισμού ενός Γ.Α. είναι είτε ένας συγκεκριμένος αριθμός γενιών, είτε ένα συγκεκριμένο ποσοστό βελτίωσης του καλύτερου ατόμου ή του συνολικού πληθυσμού σε σχέση με κάποιον αριθμό προηγούμενων γενιών.
Στο Κεφάλαιο 5 παρουσιάζονται και αναλύονται διάφορες παραλλαγές για όλα τα συστατικά στοιχεία ενός Γ.Α.