Παρασκευή, 31 Ιουλίου 2015

Η λογική πίσω από έναν γενετικό αλγόριθμο

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

Καταρχήν, η ονομασία ενός γενετικού αλγορίθμου παραπέμπει στην γενετική, δηλαδή σε έναν κλάδο της βιολογίας ο οποίος ασχολείται με την μελέτη του γονιδιώματος των οργανισμών. Το γονιδίωμα είναι το σύνολο του γενετικού υλικού που φέρει ένα άτομο, δηλαδή ουσιαστικά είναι το σύνολο των πληροφοριών που καθορίζουν τα χαρακτηριστικά ενός ατόμου. Άτομα του ίδιου είδους φέρουν την ίδια ποσότητα γονιδιώματος. Συγκεκριμένα, το γονιδίωμα οργανώνεται σε χρωμοσώματα και κάθε χρωμόσωμα αποτελείται από έναν συγκεκριμένο αριθμό γονιδίων. Έτσι τα άτομα του ίδιου είδους έχουν τον ίδιο αριθμό χρωμοσωμάτων. Παραδείγματος χάριν, το ανθρώπινο γονιδίωμα αποτελείται από 46 χρωμοσώματα, το γονιδίωμα της γάτας οργανώνεται σε 38 χρωμοσώματα ενώ το γονιδίωμα ενός σκύλου έχει 78 χρωμοσώματα.

ένα ζεύγος χρωμοσωμάτων.

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

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

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

Όμως η πραγματική διαδικασία της εξέλιξης έχει να κάνει με το γονιδίωμα των οργανισμών. Δηλαδή το γονιδίωμα είναι αυτό που υφίσταται τις διαδικασίες της φυσικής επιλογής, της διασταύρωσης και της μετάλλαξης. Αν θέλουμε να εφαρμόσουμε την διαδικασία της εξέλιξης πάνω σε αριθμούς τι γονιδίωμα θα χρησιμοποιήσουμε;

Η λύση σε αυτό το ζήτημα είναι πολύ απλή. Καταρχήν θεωρούμε πως όλα τα άτομα (αριθμοί) που θα προσπαθήσουμε να εξελίξουμε αποτελούνται μόνο από ένα χρωμόσωμα. Έπειτα, ορίζουμε τον αριθμό των γονιδίων αυτού του μοναδικού χρωμοσώματος. Και τέλος μετατρέπουμε τις αριθμητικές τιμές που μας ενδιαφέρουν στο δυαδικό σύστημα. Έτσι παραδείγματος χάριν αν επιλέξουμε πως τα χρωμοσώματα του πληθυσμού μας αποτελούνται από 8 γονίδια, ο αριθμός 10 αντιστοιχεί στο χρωμόσωμα 00001010 ενώ ο αριθμός 142 αντιστοιχεί στο χρωμόσωμα 10001110. 

Οπότε ένας γενετικός αλγόριθμος ακολουθεί τις εξής διαδικασίες:

1) Δημιουργεί έναν τυχαίο αρχικό πληθυσμό αριθμών (πχ 1000 τυχαίοι αριθμοί).
2) Από τον παραπάνω πληθυσμό επιλέγει τους αριθμούς xi που αντιστοιχούν σε μεγάλες τιμές f(xi)
3) Γίνεται εφαρμογή της διασταύρωσης στον αρχικό πληθυσμό. Μία τέτοια διασταύρωση φαίνεται στο σχήμα 1 όπου οι δύο γονείς διασταυρώνονται ώστε να δώσουν δύο απογόνους.

σχήμα 1, τα χρωμοσώματα δύο γονέων συνδυάζονται για να δώσουν δύο απογόνους.
4) Γίνεται εφαρμογή της μετάλλαξης στους απογόνους. Στην διαδικασία αυτή τα γονίδια στα χρωμοσώματα ορισμένων απογόνων αλλάζουν τυχαία, δηλαδή αν είναι 0 γίνονται 1 και το αντίστροφο. Αυτό φαίνεται στο σχήμα 2.

σχήμα 2, η διαδικασία της μετάλλαξης σε ένα χρωμόσωμα 5 γονιδίων.

5) Ο νέος πληθυσμός (απόγονοι) παίζει τον ρόλο του αρχικού πληθυσμού με αποτέλεσμα να επιστρέφουμε στο βήμα 2.

6) Η παραπάνω διαδικασία πραγματοποιείται για έναν συγκεκριμένο αριθμό γενιών που επιλέγει ο χρήστης. Στο τέλος επιλέγουμε ως λύση τον αριθμό (άτομο) που μεγιστοποιεί την συνάρτηση f. Να σημειωθεί πως ο αριθμός αυτός δεν είναι απαραίτητο να βρίσκεται ανάμεσα στα άτομα της τελευταίας γενιάς αλλά μπορεί να βρίσκεται σε οποιαδήποτε γενιά.

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

Πηγές: http://biology-gymn.blogspot.gr/2012/04/blog-post_27.html
          Εισαγωγή στους γενετικούς αλγόριθμους, Ευστράτιος Φ. Γεωργόπουλος, Σπυρίδων Δ.                                       Λυκοθανάσης
         Εξομοίωση της λειτουργίας λεκάνης απορροής με γενετικό αλγόριθμο, Σάββας Γαϊσίδης                                      (συμφοιτητής και φίλος μου, δείτε ολόκληρη την διπλωματική του εδώ)

Παλιότερες αναρτήσεις για γενετικούς αλγορίθμους:
http://fromsciencetoengineering.blogspot.gr/2014/11/blog-post.html
http://fromsciencetoengineering.blogspot.gr/2014/11/blog-post_18.html
http://fromsciencetoengineering.blogspot.gr/2014/12/blog-post_8.html

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου