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

 

Εφαρμογη

 

Ας θεωρήσουμε ένα παράδειγμα. Εξομοιώνουμε τον παραπάνω Γ.Α. για τη βελτιστοποίηση μιας συνάρτησης. Έστω ,  και . Ας υποθέσουμε ότι θέλουμε να μεγιστοποιήσουμε την ακόλουθη συνάρτηση:

,

με  και .

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

.

Η ίδια διαδικασία για τη  προσδιορίζει το  σαν τον απαιτούμενο αριθμό δυαδικών ψηφίων για την αναπαράσταση των δεκαδικών τιμών της. Επομένως, το συνολικό μήκος του χρωμοσώματος είναι  δυαδικά ψηφία.

Έστω το άτομο:

.

Τα πρώτα  δυαδικά ψηφία () αναπαριστούν τον αριθμό (από την εξίσωση 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 παρουσιάζονται και αναλύονται διάφορες παραλλαγές για όλα τα συστατικά στοιχεία ενός Γ.Α.

 

 

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