Κυριακή, 16 Νοεμβρίου 2014

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

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


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

Μερικά από τα πλεονεκτήματα των γενετικών αλγορίθμων είναι τα εξής:
  1. Λύνουν δύσκολα προβλήματα γρήγορα και αξιόπιστα.
  2. Συνεργάζονται εύκολα με μοντέλα και συστήματα.
  3. Είναι εξελίξιμοι και επεκτάσιμοι.
  4. Είναι δυνατόν να συμμετέχουν σε υβριδικές μορφές με άλλες μεθόδους.
  5. Οι συναρτήσεις που επεξεργάζονται δεν απαιτούν περιορισμούς.

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

Τα βασικά βήματα ενός γενετικού αλγόριθμου που επιλύει ένα πρόβλημα μεγιστοποίησης μίας συνάρτησης f είναι τα εξής:
  1. Δημιουργείται ένας τυχαίος πληθυσμός πιθανών λύσεων (αρχικοποίηση).
  2. Κάθε λύση αξιολογείται με την βοήθεια της αντικειμενικής συνάρτησης f.
  3. Δημιουργείται ένας νέος πληθυσμός βάση της απόδοσης του κάθε μέλους του προηγούμενου πληθυσμού.
  4. Εφαρμόζονται στον νέο πληθυσμό οι διαδικασίες της διασταύρωσης και της μετάλλαξης.
  5. Με την ολοκλήρωση του βήματος 4 δημιουργείται η νέα γενιά και επιστρέφουμε στο βήμα 2.
  6. Αν μετά από κάποιο αριθμό γενεών καμία βελτίωση δεν παρουσιάζεται ο αλγόριθμος τερματίζεται και το καλύτερο χρωμόσωμα αποτελεί την λύση του προβλήματος.
Πηγή: Εισαγωγή στους γενετικούς αλγορίθμους, Ευστράτιος Φ. Γεωργόπουλος, Σπυρίδων Δ. Λυκοθανάσης

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

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