You are currently viewing Εισαγωγή στους γενετικούς αλγορίθμους (genetic algorithms)

Εισαγωγή στους γενετικούς αλγορίθμους (genetic algorithms)

Οι γενετικοί αλγόριθμοι (genetic algorithms) αποτελούν μία ενδιαφέρουσα κατηγορία αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης. Οι συγκεκριμένοι αλγόριθμοι συγκαταλέγονται μέσα στους αλγορίθμους οι οποίοι απαρτίζουν τον κλάδο της μηχανικής μάθησης. Η μηχανική μάθηση είναι ένας από τους σημαντικότερους κλάδους της τεχνητής νοημοσύνης (ορισμός ΤΝ).

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

  • Το πρόβλημα του πλανόδιου πωλητή
  • Προβλήματα εφοδιαστικής (logistics)
  • Τα παίγνια (game playing)
  • Ο χρονοπρογραμματισμός (scheduling)
  • Η δρομολόγηση καλωδίων (wire routing)

Η αρχή της έμπνευσης των γενετικών αλγορίθμων έγινε το 1958 από τον Friedberg, ο οποίος συνδύασε μικρά προγράμματα Fortran (γλώσσα προγραμματισμού) για την αυτόματη παραγωγή σύνθετων προγραμμάτων. Έπειτα ο Holland το 1975 χρησιμοποίησε σειρές δυαδικών ψηφίων (bits) ώστε κάθε συνδυασμός bit να είναι μία έγκυρη λειτουργία. wikipedia

Πως λειτουργούν οι γενετικοί αλγόριθμοι;

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

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

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

  1. Μηχανισμός ο οποίος δημιουργεί τυχαία πιθανές λύσεις για το εκάστοτε πρόβλημα.
  2. Ένας τρόπος αναπαράστασης των υποψήφιων λύσεων.
  3. Η συνάρτηση καταλληλότητας η οποία θα βαθμολογήσει της πιθανές λύσεις με βάση τα κριτήρια που του παρέχει ο προγραμματιστής.
  4. Ένας μηχανισμός επιλογής γονέων.
  5. Το σύνολο των γενετικών τελεστών για τη διαδικασία της αναπαραγωγής νέων λύσεων.

Διαδικασία επιλογής γονέων

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

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

Μία δεύτερη τεχνική για την επιλογή των γονέων είναι και η επιλογή τουρνουά (tournament selection). Στην τεχνική αυτή επιλέγονται γονείς με προκαθορισμένη πιθανότητα q ενώ αυτοί που είναι λιγότερο κατάλληλοι έχουν πιθανότητα επιλογής 1-q.

Διαδικασία αναπαραγωγής

Η αναπαραγωγή είναι η διαδικασία της δημιουργίας απογόνων (νέων λύσεων) και είναι αποτελέσματα του ζευγαρώματος δύο γονέων (παλαιών υποψήφιων λύσεων). Στην αναπαραγωγή εμπλέκονται δύο τελεστές η οποίοι αποτελούν τον κύριο μηχανισμό αναπαραγωγής νέων λύσεων. Αυτοί οι τελεστές είναι η:

  1. διασταύρωση (crossover): Ο τελεστής διασταύρωσης παράγει δύο απογόνους από δύο γονείς παίρνοντας επιλεγμένα bit από κάθε γονέα με τέτοιο τρόπο ώστε το i-οστό bit του απογόνου να είναι το i-οστό bit ενός εκ των γονέων του.
  2. μετάλλαξη (mutation): Ο τελεστής μετάλλαξης αλλοιώνει ένα ψηφίο bit που παράγεται με τη δημιουργία του απογόνου ώστε να βελτιωθεί περαιτέρω η λύση.

Γενετικοί αλγόριθμοι και οι εφαρμογές τους

Οι γενετικοί αλγόριθμοι μπορούν να χρησιμοποιηθούν αποτελεσματικά σε διάφορους κλάδους της επιστήμης της πληροφορικής όπως είναι:

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

Αφήστε μια απάντηση