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

 

Δομες Δεδομενων

 

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

 

 

Α/α

 

 

Άτομα

 

 

 

 

Ατόμου

Συμβολοσειρά 1

x1

Συμβολοσειρά 2

x2

··

·

F(x1,x2,…,xl)

Άλλα στοιχεία

1

01111

15

00111

7

··

·

 

225

···

2

01001

9

00010

2

··

·

101

···

3

00111

7

01001

9

··

·

123

···

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

n

00111

7

00101

5

··

·

81

···

Πίνακας 3.1

 

Με τη βοήθεια αυτού του πίνακα, θα είναι εύκολο να κάνουμε τις δηλώσεις τύπων για τα δεδομένα, σε κάποια δομημένη γλώσσα προγραμματισμού. Για παράδειγμα, σε γλώσσα Pascal, πρέπει να κάνουμε τις παρακάτω δηλώσεις:

 

·        Πρώτα θα δηλώσουμε ορισμένες σταθερές, στο τμήμα δηλώσεων σταθερών, όπως το μέγιστο μέγεθος του πληθυσμού pop_size και το μέγιστο μήκος της συμβολοσειράς m. Αυτές οι σταθερές ορίζουν τα πάνω όρια στο μέγεθος του πληθυσμού και το μήκος της συμβολοσειράς.

 

·        Στη συνέχεια θα δηλώσουμε τον τύπο (type) του πληθυσμού και τις συνιστώσες του στο τμήμα δηλώσεων τύπων (type declaration). Για παράδειγμα ο τύπος population, είναι ένα array που ορίζεται από τον τύπο individual (με δείκτη από 1 έως m). Ο τύπος individual είναι ένα record που καθορίζεται από τη μεταβλητή chrom, που είναι τύπου chromosome, μια πραγματική μεταβλητή που ονομάζεται fittness και μια πραγματική μεταβλητή x. Αυτές οι μεταβλητές αναπαριστούν το τεχνητό χρωμόσωμα, την τιμή της αντικειμενικής συνάρτησης και την αποκωδικοποιημένη τιμή της μεταβλητής x, αντίστοιχα. Εμβαθύνοντας περισσότερο, βλέπουμε ότι ο τύπος chromosome είναι και ο ίδιος ένα array τύπου allele (με δείκτη από 1 μέχρι m), ο οποίος σε αυτή την περίπτωση είναι ένα άλλο όνομα για τον τύπο boolean (ένα απλό bit που παίρνει τιμές true ή false).

 

 

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