Γενετικοί Αλγόριθμοι

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

Ο τρόπος λειτουργίας των Γενετικών Αλγορίθμων είναι εμπνευσμένος από τη βιολογία. Χρησιμοποιεί την ιδέα της εξέλιξης μέσω γενετικής μετάλλαξης, φυσικής επιλογής και διασταύρωσης. Οι Γενετικοί Αλγόριθμοι είναι αρκετά απλοί στην υλοποίησή τους. Οι τιμές για τις παραμέτρους του συστήματος πρέπει να κωδικοποιούνται με τρόπο ώστε να αναπαρασταθούν από μια μεταβλητή που περιέχει σειρά χαρακτήρων ή δυαδικών ψηφίων (0/1). Αυτή η μεταβλητή μιμείται το γενετικό κώδικα που υπάρχει στους ζωντανούς οργανισμούς. Αρχικά, ο Γενετικός Αλγόριθμος παράγει πολλαπλά αντίγραφα της μεταβλητής/γεννητικού κώδικα, συνήθως με τυχαίες τιμές, δημιουργώντας ένα πληθυσμό λύσεων. Κάθε λύση (τιμές για τις παραμέτρους του συστήματος) δοκιμάζεται για το πόσο κοντά φέρνει την αντίδραση του συστήματος στην επιθυμητή, μέσω μιας συνάρτησης που δίνει το μέτρο ικανότητας της λύσης και η οποία ονομάζεται συνάρτηση ικανότητας (Σ.Ι).

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

Υπάρχουν διάφορες εκδοχές της παραπάνω διαδικασίας για τους Γ.Α από τις οποίες κάποιες περιλαμβάνουν και τη διασταύρωση (ζευγάρωμα) γονιδίων/λύσεων ώστε ο αλγόριθμος να φτάσει στο αποτέλεσμα πιο γρήγορα. Καθώς υπάρχει το στοχαστικό (τυχαίο) συστατικό της μετάλλαξης και ζευγαρώματος, κάθε εκτέλεση του Γ.Α μπορεί να συγκλίνει σε διαφορετική λύση και σε διαφορετικό χρόνο. Η απόδοση του Γ.Α εξαρτάται επί το πλείστον από την συνάρτηση ικανότητας και συγκεκριμένα από το κατά πόσο το μέτρο της περιγράφει την βέλτιστη λύση. Οι γενετικοί αλγόριθμοι είναι ένα πεπερασμένο σύνολο οδηγιών για την εκπλήρωση ενός έργου, το οποίο δεδομένης μιας αρχικής κατάστασης θα οδηγήσει σε μια αναγνωρίσιμη τελική κατάσταση, και το οποίο προσπαθεί να μιμηθεί την διαδικασία της βιολογικής εξέλιξης. Οι γενετικοί αλγόριθμοι προσπαθούν να βρουν τη λύση ενός προβλήματος με το να προσομοιώνουν την εξέλιξη ενός πληθυσμού «λύσεων» του προβλήματος.

Είναι μια τεχνική προγραμματισμού που εισήγαγε στα τέλη της δεκαετίας του 1960 ο Τζον Χόλαντ, ερευνητής του Ινστιτούτου της Σάντα Φε (ΗΠΑ).

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

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

Πως Λειτουργεί[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

Τρόπος Υλοποίησης του Αλγορίθμου[Επεξεργασία | επεξεργασία κώδικα]

Οι Γενετικοί Αλγόριθμοι είναι αρκετά απλοί στην υλοποίησή τους. Οι τιμές για τις παραμέτρους του συστήματος πρέπει να κωδικοποιούνται με τρόπο ώστε να αναπαρασταθούν από μια μεταβλητή που περιέχει σειρά χαρακτήρων ή δυαδικών ψηφίων (0/1). Αυτή η μεταβλητή μιμείται το γενετικό κώδικα (γονιδίωμα) που υπάρχει στους ζωντανούς οργανισμούς.

Αρχικά, ο Γενετικός Αλγόριθμος παράγει πολλαπλά αντίγραφα της μεταβλητής/γενετικού κώδικα, συνήθως με τυχαίες τιμές, δημιουργώντας ένα πληθυσμό λύσεων. Κάθε λύση (τιμές για τις παραμέτρους του συστήματος) δοκιμάζεται για το πόσο κοντά φέρνει την αντίδραση του συστήματος στην επιθυμητή, μέσω μιας συνάρτησης που δίνει το μέτρο ικανότητας της λύσης και η οποία ονομάζεται συνάρτηση ικανότητας (Σ.Ι).

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

Εκδοχές Αλγορίθμου[Επεξεργασία | επεξεργασία κώδικα]

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

Χαρακτηριστικά[Επεξεργασία | επεξεργασία κώδικα]

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

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Έστω ότι έχουμε μια διεργασία Ε η οποία εξαρτάται από τις μεταβλητές x' ,x,x,x'. Η διεργασία Ε παράγει ένα προϊόν Α. Ποιες είναι οι τιμές των x',x,x,x' ώστε το κόστος του Α να είναι το μικρότερο δυνατό; Για να λύσει αυτό το πρόβλημα ο γενετικός αλγόριθμος, δημιουργεί κάποιες αρχικές τυχαίες λύσεις του προβλήματος. Δηλαδή, δημιουργεί ένα πληθυσμό χρωμοσωμάτων όπου το κάθε χρωμόσωμα αντιστοιχεί σε κάποιες τιμές των x. Για την εκτίμηση της καταλληλότητας του χρωμοσώματος αυτού, υπάρχει μια συνάρτηση καταλληλότητας (fitness function) η οποία και κρίνει το κατά πόσο είναι κατάλληλο το κάθε χρωμόσωμα. Κάθε χρωμόσωμα κρίνεται για την καταλληλότητά του, και στη συνέχεια επιλέγονται τα καλύτερα χρωμοσώματα. Αυτά «αναπαράγονται» χρησιμοποιώντας ορισμένους γενετικούς τελεστές, και παράγουν την επόμενη γενιά χρωμοσωμάτων. Μετά από πολλές γενιές, ο πληθυσμός θα έχει χρωμοσώματα τα οποία είναι αρκετά κατάλληλα για το πρόβλημα, οπότε μπορούμε να λάβουμε τα κατάλληλα x για την λύση του προβλήματος.

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Οι πιθανές εφαρμογές είναι πολλές:

  • η καλύτερη δυνατή οργάνωση του ωραρίου ενός σχολείου,
  • η μελέτη της βέλτιστης κατανομής ενός δικτύου από πλατφόρμες πετρελαίου αλλά και
  • η δημιουργία υπολογιστών που θα βελτιώνουν τον τρόπο λειτουργίας τους "μαθαίνοντας" από την εμπειρία τους.
  • εξερεύνηση των δυναμικών βιολογικών διαδικασιών, και της θεωρίας της εξέλιξης. Παράδειγμα ο Κάρλ Σήμς (1994) έκανε Γενετικούς Αλγόριθμους που δημιούργησαν εικονικά "πλάσματα", κάποια από τα οποία θυμίζουν πραγματικά. [1]
  • το πρόβλημα του περιπλανώμενου πωλητή.
  • εξελικτικά νευρωνικά δίκτυα.

Περιορισμοί[Επεξεργασία | επεξεργασία κώδικα]

Οι Γενετικοί Αλγόριθμοι έχουν κάποιους περιορισμούς σε σύγκριση με εναλλακτικούς αλγόριθμους βελτιστοποίησης.

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

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]