.

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

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

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

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

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

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

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

Πως Λειτουργεί

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

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

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

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

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

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

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

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

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

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

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

Περιορισμοί

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

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

Παραλλαγές
Χρωμοσωμική Αναπαράσταση

Ο απλούστερος αλγόριθμος αντιπροσωπεύει κάθε χρωμόσωμα ως bit string. Τυπικά, τα αριθμητικά μπορεί να αντιπροσωπεύονται από ακέραιους αριθμούς, και αν είναι δυνατόν μπορεί να χρησιμοποιηεί floating point αναπαράσταση. Η αναπαράσταση floating point είναι φυσιολογική στις στρατηγικές εξέλιξης και τον εξελικτικό προγραμματισμό. Η έννοια των γενετικών αλγορύθμων πραγματικής αξίας (real-valued) έχει προσφερθεί, αλλά είναι πραγματικά εσφαλμένη, επειδή δεν αντιπροσωπεύει πραγματικά τη θεωρία οικοδομικό τετράγωνο που προτάθηκε από τον John Henry Holland στη δεκαετία του 1970. Ο βασικός αλγόριθμος εκτελεί διασταύρωσεις και μεταλλάξεις σε επίπεδο bit. Άλλες παραλλαγές αντιμετωπίζουν το χρωμόσωμα ως μια λίστα των αριθμών που είναι δείκτες σε έναν πίνακα της διδασκαλίας, οι κόμβοι σε μια συνδεδεμένη λίστα, hashes, αντικείμενα, ή οποιαδήποτε άλλη δομή δεδομένων μπορεί να φανταστεί κανείς. Διασταύρωσης και μετάλλαξης εκτελούνται έτσι ώστε να σέβεται τα όρια στοιχείο δεδομένων.
Ελιτισμός

Μια πρακτική παραλλαγή της γενικής διαδικασίας της κατασκευής ενός νέου πληθυσμού είναι να επιτρέψει στον καλύτερο οργανισμό (-ούς) από τη σημερινή γενιά να μεταφέρθει στο επόμενο, αναλλοίωτος. Η στρατηγική αυτή είναι γνωστή ως ελιτιστική επιλογή και εγγυάται ότι η ποιότητα που λαμβάνεται από τον γενετικό αλγόρυθμο, δεν θα μειωθεί από τη μια γενιά στην επόμενη.
Παράλληλες Υλοποιήσεις

Παράλληλες υλοποιήσεις των γενετικών αλγορίθμων έρχονται σε δύο γεύσεις. Χονδροειδούς παράλληλοι γενετικών αλγορίθμων προσομειώνουν πληθυσμούς σε κάθε ένα από τους κόμβους του υπολογιστή και τη μετανάστευση των ατόμων μεταξύ των κόμβων. Λεπτόειδούς παράλληλοι γενετικοί αλγόριθμοι υποθέτουν ότι είναι ένα άτομο σε κάθε κόμβο του επεξεργαστή που αλληλεπιδρά με τα γειτονικά άτομα για την επιλογή και την αναπαραγωγή.
Ιστορία

Το 1950, ο Alan Turing πρότεινε τη "μηχανική μάθηση", η οποία θα ήταν παράλληλη με τις αρχές της εξέλιξης. Η υπολογιστική προσομοίωση της εξέλιξης που ξεκίνησε ήδη από το 1954 με το έργο του Nils Aall Barricelli, ο οποίος χρησιμοποιούσε τον υπολογιστή στο Ινστιτούτο των προηγμένων μελετών στο Princeton του New Jersey. Η δημοσίευση του το 1954 δεν είχε ευρέως παρατηρηθεί. Ξεκινώντας το 1957, ο Αυστραλός γενετιστής Alex Fraser δημοσίευσε μια σειρά εγγράφων για την προσομοίωση της τεχνητής επιλογής των οργανισμών με πολλαπλές θέσεις που ελέγχουν ένα μετρήσιμο χαρακτηριστικό. Από αυτές τις αρχές, η προσομοίωση της εξέλιξης από τους βιολόγους έγινε περισσότερο σύνηθες φαινόμενο στις αρχές της δεκαετίας του 1960, και οι μέθοδοι περιγράφονται σε βιβλία από τον Fraser,τον Burnell (1970) και τον Crosby (1973). Οι προσομοιώσεις του Fraser περιλαμβάνονται σε όλα τα ουσιώδη στοιχεία των σύγχρονων γενετικών αλγορίθμων. Επιπλέον, ο Hans-Joachim Bremermann δημοσίευσε μια σειρά εγγράφων το 1960, που ενέκρινε επίσης έναν πλήθος λύσεων στα προβλήματα βελτιστοποίησης, που υποβάλλονται σε ανασυνδυασμό, μετάλλαξη και επιλογή. Η έρευνα του Bremermann περιελάμβανε επίσης τα στοιχεία των σύγχρονων γενετικών αλγορίθμων. Άλλες αξιοσημείωτοι πρωτοπόροι είναι οι Richard Friedberg, George Friedman, και Michael Conrad. Πολλές αρχικές εργασίες ανατυπώθηκαν από τον Fogel (1998). Παρά το γεγονός ότι ο Barricelli, στην εργασία που αναφέρθηκε το 1963, είχε προσομοίωσει την εξέλιξη της ικανότητας να παίξει ένα απλό παιχνίδι, η τεχνητή εξέλιξη έγινε ευρέως αναγνωρισμένη μέθοδος βελτιστοποίησης, ως αποτέλεσμα των εργασιών του Ingo Rechenberg και του Hans-Paul Schwefel στη δεκαετία του 1960 και στις αρχές της δεκαετίας του 1970. Η ομάδα του Rechenberg ήταν σε θέση να επιλύει πολύπλοκα προβλήματα μηχανικής μέσω στρατηγικών εξέλιξης. Μια άλλη προσέγγιση ήταν η εξελικτική τεχνική προγραμματισμού του Lawrence J. Fogel, η οποία προτάθηκε για τη δημιουργία τεχνητής νοημοσύνης. Ο Εξελικτικός προγραμματισμός χρησιμοποιεί αρχικά μηχανές πεπερασμένων καταστάσεων για την πρόβλεψη του περιβάλλοντος και χρησιμοποιεί διακυμάνσεις και επιλογές για τη βελτιστοποίηση των προβλέψεων. Οι γενετικοί αλγόριθμοι έγιναν δημοφιλής μέσα από το έργο του John Holland στις αρχές του 1970, και ιδίως μέσω του βιβλίου του Adaptation in Natural and Artificial Systems (1975). Το έργο του ξεκίνησε με τις σπουδές της κυτταρικά αυτόματα, που διενεργήθηκε από την Ολλανδία και από μαθητές της στο Πανεπιστήμιο του Michigan. Η Ολλανδία εισήγαγε ένα τυποποιημένο πλαίσιο για την πρόβλεψη της ποιότητας της επόμενης γενιάς, γνωστό ως Holland's Schema Theorem. Το πρώτο Διεθνές Συνέδριο για τους Γενετικούς Αλγορίθμους πραγματοποιήθηκε στο Πίτσμπουργκ της Πενσυλβάνιας. Καθώς το ακαδημαϊκό ενδιαφέρον μεγάλωνε, η δραματική αύξηση της υπολογιστική ισχύς επέτρεψε την δημιουργία νέων πρακτικών εφαρμογών. Στα τέλη του 1980, η General Electric άρχισε να πουλά το πρώτο γενετικό αλγόριθμο, ένα mainframe βασισμένο να σχεδιάζει βιομηχανικές διεργασίες.
Δείτε επίσης

Μηχατρονική
(Αγγλικά) Genetic Algorithms in Ruby
Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, freely available from the internet ISBN 978-1-4092-0073-4
(Αγγλικά) Global Optimization Algorithms - Theory and Application

Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License