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

Μια εικόνα ενός γονιδίου

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

Τι είναι ο γενετικός αλγόριθμος;

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

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

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

Η διαδικασία εργασίας του γενετικού αλγορίθμου

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

διαδικασία φυσικής επιλογής (απλοποιημένη)

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

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

διαδικασία εργασίας γενετικού αλγορίθμου

Κατ 'αρχάς, η διαδικασία εργασίας του γενετικού αλγορίθμου ξεκινά επίσης έχοντας έναν αρχικό πληθυσμό. Το πρώτο κύριο στάδιο είναι ο υπολογισμός της φυσικής κατάστασης, ο υπολογισμός της φυσικής κατάστασης μπορεί να θεωρηθεί ως μέρος της διαδικασίας επιλογής, καθώς βασικά χρησιμοποιήθηκε για τον υπολογισμό της «βαθμολογίας» κάθε ατόμου για να δείξει αν είναι ισχυρό άτομο ή αδύναμο. Όλες οι ισχυρές οντότητες στη συνέχεια επιλέχθηκαν και πέρασαν σε ένα στάδιο που ονομάζεται cross over, αυτό το στάδιο είναι σαν το στάδιο ζευγαρώματος στο προηγούμενο διάγραμμα. Σε αυτό το στάδιο, επιλέγονται 2 τυχαίοι γονείς από τη λίστα ισχυρών οντοτήτων για να εκτελέσουν κάτι που ονομάζεται crossover το οποίο θα συζητήσουμε αργότερα. Μετά την εκτέλεση cross over, ένα παιδί δημιουργείται και μεταλλάσσεται για να προσθέσει κάποια παραλλαγή στο γονίδιο. Τέλος, αυτό το παιδί επανέρχεται στον πληθυσμό και η διαδικασία επαναλαμβάνεται ξανά.

Αυτό που είναι το γυμναστήριο

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

Προσπαθήστε να φανταστείτε ότι σας δίνεται ένα πρόβλημα, το πρόβλημα είναι να βρείτε την καλύτερη διαδρομή για την κόκκινη κουκούλα για να ταξιδέψετε στο σπίτι της γιαγιάς της. Ας υποθέσουμε ότι θέλει να φτάσει στο σπίτι της γιαγιάς της στο συντομότερο δυνατό χρονικό διάστημα, επομένως η καταλληλότητα μιας διαδρομής μπορεί να υπολογιστεί χρησιμοποιώντας τον χρόνο που χρειάστηκε για να ταξιδέψει. Εάν υπάρχει διαδρομή που έχει μήκος 400 μέτρα και χρειάστηκε 10 λεπτά για να ταξιδέψει, τότε η φυσική της κατάσταση θα είναι σίγουρα λιγότερη από την φυσική κατάσταση μιας διαδρομής μήκους 500 μέτρων, αλλά της πήρε μόνο 8 λεπτά για να ταξιδέψει ως φυσική κατάσταση Η διαδρομή υπολογίζει τη βάση του χρόνου ταξιδιού και όχι το μήκος της. Επομένως, η διαδρομή μήκους 500 μέτρων είναι πιθανότερο να επιλεγεί για να συνδυαστεί με άλλες διαδρομές.

Επιλέγοντας το καλό!

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

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

  • Αναλογική επιλογή καταλληλότητας
  • Επιλογή τουρνουά
  • Επιλογή περικοπής
  • Ομοιόμορφη επιλογή γυμναστικής

Η παραπάνω λίστα δεν είναι κατάλληλη λίστα, μπορείτε να βρείτε περισσότερες μεθόδους εδώ.

Ας πάρουμε ως παράδειγμα την πρώτη μέθοδο. Σε αντίθεση με το όνομά της, η πραγματική ιδέα πίσω από αυτήν τη μέθοδο είναι παράλογα απλή. Η αναλογική επιλογή γυμναστικής AKA η επιλογή τροχών ρουλέτας, είναι η μέθοδος επιλογής «πιθανών» λύσεων για ανασυνδυασμό.

Φανταστείτε, εάν υπάρχουν 10 μάρμαρα σε μια τσάντα, συγκεκριμένα, 5 μπλε μάρμαρα, 3 κόκκινα μάρμαρα και 2 λευκά μάρμαρα. Μπορείτε εύκολα να υπολογίσετε ότι αν διαλέξετε ένα τυχαίο μάρμαρο από την τσάντα, θα έχετε 5/10 πιθανότητα να επιλέξετε ένα μπλε, 3/10 για κόκκινο και 2/10 για λευκό. Έτσι λειτουργεί η αναλογική επιλογή φυσικής κατάστασης, ωστόσο, η διαδικασία είναι λίγο διαφορετική.

Στην αναλογική επιλογή φυσικής κατάστασης, επιλέγεται πρώτα ένας τυχαίος αριθμός και στη συνέχεια θα χρησιμοποιηθεί για σύγκριση με την καταλληλότητα μιας λύσης τυχαίας επιλογής. Η τιμή φυσικής κατάστασης συνήθως περιορίζεται από 0 έως 1. Εάν η τυχαία τιμή είναι μικρότερη από αυτή τη βαθμολογία φυσικής κατάστασης, τότε θα επιλεγεί η λύση. Έτσι, όσο υψηλότερη είναι η καταλληλότητα μιας λύσης, τόσο περισσότερες πιθανότητες θα επιλεγεί. Για παράδειγμα, εάν ένας τυχαίος αριθμός κυμαίνεται από 0 έως 1, υπάρχει 50% θα είναι μικρότερος από 0,5 και 80% θα είναι μικρότερος από 0,8, ωστόσο, δεν είναι πιθανό να είναι μικρότερος από 0,2, αυτό σημαίνει, εάν η λύση έχει φυσική κατάσταση 0,8, υπάρχει 80% που θα επιλεγεί για ανασυνδυασμό και η λύση που έχει 0,2 φυσική κατάσταση θα έχει μόνο 20% που πρέπει να επιλεγεί. Παρόλο που η λύση φυσικής κατάστασης 0,2 σπάνια επιλέγεται, αλλά βοηθά επίσης στη διαφοροποίηση των χαρακτηριστικών της λύσης, καθώς αυτή η λύση μπορεί να περιέχει ορισμένα χαρακτηριστικά που χρειάζονται για μελλοντική επιτυχία.

Εκτέλεση crossover

Το Crossover είναι το στάδιο όπου οι επιλεγμένες λύσεις συνδυάζονται για να σχηματίσουν νέες λύσεις. Ακριβώς όπως το στάδιο επιλογής, υπάρχουν επίσης πολλές τεχνικές crossover και μπορείτε επίσης να τις βρείτε εδώ.

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

  • Διασταύρωση ενός σημείου
  • Crossover δύο σημείων
  • Ομοιόμορφη διασταύρωση
  • Τρεις γονείς crossover

Για καλύτερη κατανόηση, θα εξηγήσω την ομοιόμορφη τεχνική crossover που είναι η τεχνική που θεωρώ ότι είναι η πιο εύκολη τεχνική για εφαρμογή.

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

Το πρώτο βήμα στο ομοιόμορφο crossover είναι να επιλέξετε 2 τυχαίες λύσεις από το σύνολο των λύσεων που έχουν επιλεγεί στο προηγούμενο στάδιο επιλογής. Στη συνέχεια, κάθε μέρος των 2 λύσεων θα επιλεγεί για να προσθέσει τη βάση του παιδικού διαλύματος σε μια μεταβλητή που ονομάζεται λόγος ανάμειξης. Η αναλογία ανάμειξης είναι αυτό που αποφασίζει την πιθανότητα να επιλεγεί μια λύση για προσθήκη στο παιδικό διάλυμα. Για παράδειγμα, υπάρχουν 2 λύσεις: Α και Β και θέλετε η θυγατρική λύση να έχει περισσότερα μέρη που έχουν ληφθεί από τη λύση Α, μπορείτε να αυξήσετε την αναλογία ανάμειξης, μετά από αυτό το βρόχο σε όλα τα μέρη της λύσης Α και Β. Σε κάθε βρόχο , δημιουργήστε έναν νέο τυχαίο αριθμό και συγκρίνετε τον με την αναλογία ανάμιξης, εάν είναι μικρότερος από τον λόγο ανάμιξης, επιλέξτε το διάλυμα A άλλο μέρος επιλέξτε το B. Ομοίως, εάν ο λόγος ανάμιξης είναι 0,5 τότε οι Α και Β θα έχουν περίπου 50% επιλέγεται.

Ομοιόμορφο crossover με αναλογία ανάμιξης 0,5

Η παραπάνω εικόνα, δείχνει το παιδικό διάλυμα C που δημιουργείται χρησιμοποιώντας τα διαλύματα Α και Β με αναλογία ανάμιξης 0,5 ή 50%. Κάθε μέρος και των δύο λύσεων αποφασίστηκε να επιλεγεί ή να μην βασίζεται στην αναλογία ανάμιξης και η αναλογία ανάμιξης συγκρίθηκε με έναν τυχαίο αριθμό που θα αποφασιστεί. Είναι σαν να πετάς ένα κέρμα για να επιλέξεις πού πρέπει να χρησιμοποιείται το Α αντί για το Β και το αντίστροφο.

Σίγουρα το παιδί!

Όχι όχι όχι, δεν πρόκειται να μετατρέψουμε τα παιδιά μας σε μερικά παιδιά με μεταλλικά νύχια και να τα αφήσουμε να πεθάνουν σε έναν τυχαίο κορμό δέντρου!

Αντίθετα, η προσθήκη μετάλλαξης σε ένα παιδί είναι σαν να το βοηθάς

Σκεπτόμενος διαφορετικά, ένα άτομο μπορεί να γίνει ο ηγέτης του κοπαδιού ή ένας πλήρης χαζός.

Ένα παράδειγμα μετάλλαξης

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

Για να μεταλλάξετε ένα παιδί, υπάρχουν επίσης μια ποικιλία τεχνικών που μπορείτε να χρησιμοποιήσετε:

  • Μετάλλαξη συμβολοσειράς bit
  • Flip Bit
  • Μη ομοιόμορφη
  • Στολή

Μπορείτε να βρείτε περισσότερα από αυτά εδώ.

Για να το καταλάβω καλύτερα, θα δείξω την τεχνική «μετάλλαξης συμβολοσειράς bit».

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

Η "μετάλλαξη συμβολοσειράς bit" χρησιμοποιείται συνήθως για δυαδική συμβολοσειρά καθώς αυτή η μέθοδος αναστρέφει 1 ή περισσότερα τυχαία επιλεγμένα bits στο γονίδιο. Για παράδειγμα:

Παράδειγμα μετάλλαξης συμβολοσειράς bit

Τώρα, προσπαθήστε να μετατρέψετε 1 και 0 σε αριστερά και δεξιά και σκεφτείτε πώς θα αποδώσει το bot. Καθώς το bot μπορεί να κολλήσει όταν αντιμετώπισε ένα μεγάλο αντικείμενο, η μετάλλαξη θα βοηθήσει τους απογόνους του να επιλέξουν μια νέα κατεύθυνση για να κινηθούν και να αποφύγουν αυτό το αντικείμενο. Φανταστείτε, για πολλές γενιές, το bot στρίβει δεξιά μόνο όταν συναντά ένα αντικείμενο και πεθάνει, αλλά, στην επόμενη γενιά, το bot γύρισε ξαφνικά αριστερά καθώς μια δεξιά συμβολοσειρά στο γονίδιό της ανατράπηκε προς τα αριστερά και το bot τελικά έφτασε στον προορισμό του. Αυτός είναι βασικά ο τρόπος λειτουργίας της «μετάλλαξης συμβολοσειράς bit».

Το τέλος της διαδικασίας

Μετά τη μετάλλαξη του παιδιού, θα επιστρέψει με άλλο μεταλλαγμένο παιδί για να μεταρρυθμίσει έναν νέο πληθυσμό και η όλη διαδικασία θα ξεκινήσει ξανά.

Λοιπόν, όταν σταματά; Η απάντηση είναι εξαιρετικά απλή, πότε σταματάτε να πληκτρολογείτε πληκτρολόγιο με 10 δάχτυλα; Όταν η δεξιοτεχνία σας είναι τέλεια φυσικά. Το ίδιο πράγμα με τον γενετικό αλγόριθμο, η διαδικασία θα σταματήσει εάν η φυσική κατάσταση μιας συγκεκριμένης λύσης φτάσει στην επιθυμητή φυσική κατάσταση Για παράδειγμα, θέλετε το bot στο προηγούμενο παράδειγμα να φτάσει στον προορισμό με τον μικρότερο δυνατό χρόνο.

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

συμπέρασμα

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

Ακολουθούν ορισμένοι σύνδεσμοι για να εξερευνήσετε περισσότερα σχετικά με τον γενετικό αλγόριθμο:

  • Βίντεο του Daniel Shiffman σχετικά με τον γενετικό αλγόριθμο:
  • Το παράδειγμά μου για τη χρήση γενετικού αλγορίθμου για να μαντέψω έναν κωδικό πρόσβασης
  • tutorialspoint tutorial σχετικά με τον γενετικό αλγόριθμο
  • Goran Muric βίντεο σχετικά με ένα παράδειγμα που χρησιμοποιεί γενετικό αλγόριθμο για να βρει μονοπάτι