Οι Γενετικοί Αλγόριθμοι (GA) βασίζονται σε μια εξελικτική προσέγγιση στην Τεχνητή Νοημοσύνη, όπου χρησιμοποιούνται μέθοδοι εξέλιξης ενός πληθυσμού για την επίτευξη μιας βέλτιστης λύσης σε ένα δεδομένο πρόβλημα. Προτάθηκαν το 1975 από τον John Henry Holland.
Οι Γενετικοί Αλγόριθμοι βασίζονται στις εξής ιδέες:
- Οι έγκυρες λύσεις του προβλήματος μπορούν να αναπαρασταθούν ως γονίδια
- Η διασταύρωση μας επιτρέπει να συνδυάσουμε δύο λύσεις για να αποκτήσουμε μια νέα έγκυρη λύση
- Η επιλογή χρησιμοποιείται για την επιλογή πιο βέλτιστων λύσεων μέσω κάποιας συνάρτησης καταλληλότητας
- Εισάγονται μεταλλάξεις για να αποσταθεροποιηθεί η βελτιστοποίηση και να αποφύγουμε το τοπικό ελάχιστο
Αν θέλετε να υλοποιήσετε έναν Γενετικό Αλγόριθμο, χρειάζεστε τα εξής:
- Να βρείτε έναν τρόπο κωδικοποίησης των λύσεων του προβλήματος χρησιμοποιώντας γονίδια g∈Γ
- Στο σύνολο των γονιδίων Γ πρέπει να ορίσετε μια συνάρτηση καταλληλότητας fit: Γ→R. Μικρότερες τιμές της συνάρτησης αντιστοιχούν σε καλύτερες λύσεις.
- Να ορίσετε έναν μηχανισμό διασταύρωσης για να συνδυάσετε δύο γονίδια και να αποκτήσετε μια νέα έγκυρη λύση crossover: Γ2→Γ.
- Να ορίσετε έναν μηχανισμό μετάλλαξης mutate: Γ→Γ.
Σε πολλές περιπτώσεις, η διασταύρωση και η μετάλλαξη είναι αρκετά απλοί αλγόριθμοι για τη διαχείριση γονιδίων ως αριθμητικές ακολουθίες ή δυαδικούς διανύσματα.
Η συγκεκριμένη υλοποίηση ενός γενετικού αλγορίθμου μπορεί να διαφέρει από περίπτωση σε περίπτωση, αλλά η γενική δομή είναι η εξής:
- Επιλέξτε έναν αρχικό πληθυσμό G⊂Γ
- Επιλέξτε τυχαία μία από τις λειτουργίες που θα εκτελεστούν σε αυτό το βήμα: διασταύρωση ή μετάλλαξη
- Διασταύρωση:
- Επιλέξτε τυχαία δύο γονίδια g1, g2 ∈ G
- Υπολογίστε τη διασταύρωση g=crossover(g1,g2)
- Αν fit(g)<fit(g1) ή fit(g)<fit(g2) - αντικαταστήστε το αντίστοιχο γονίδιο στον πληθυσμό με το g.
- Μετάλλαξη - επιλέξτε τυχαία ένα γονίδιο g∈G και αντικαταστήστε το με mutate(g)
- Επαναλάβετε από το βήμα 2, μέχρι να επιτευχθεί μια αρκετά μικρή τιμή της fit ή μέχρι να φτάσετε το όριο στον αριθμό των βημάτων.
Οι εργασίες που συνήθως λύνονται με Γενετικούς Αλγόριθμους περιλαμβάνουν:
- Βελτιστοποίηση προγράμματος
- Βέλτιστη συσκευασία
- Βέλτιστη κοπή
- Επιτάχυνση εξαντλητικής αναζήτησης
Συνεχίστε τη μάθησή σας στα παρακάτω notebooks:
Μεταβείτε σε αυτό το notebook για να δείτε δύο παραδείγματα χρήσης Γενετικών Αλγορίθμων:
- Δίκαιη διανομή θησαυρού
- Πρόβλημα των 8 Βασιλισσών
Οι Γενετικοί Αλγόριθμοι χρησιμοποιούνται για την επίλυση πολλών προβλημάτων, συμπεριλαμβανομένων των προβλημάτων logistics και αναζήτησης. Το πεδίο είναι εμπνευσμένο από έρευνες που συνδυάζουν θέματα Ψυχολογίας και Πληροφορικής.
"Οι γενετικοί αλγόριθμοι είναι απλοί στην υλοποίηση, αλλά η συμπεριφορά τους είναι δύσκολο να κατανοηθεί." πηγή Κάντε έρευνα για να βρείτε μια υλοποίηση γενετικού αλγορίθμου, όπως η επίλυση ενός παζλ Sudoku, και εξηγήστε πώς λειτουργεί με τη μορφή σκίτσου ή διαγράμματος ροής.
Παρακολουθήστε αυτό το εξαιρετικό βίντεο που μιλάει για το πώς ένας υπολογιστής μπορεί να μάθει να παίζει Super Mario χρησιμοποιώντας νευρωνικά δίκτυα που εκπαιδεύονται από γενετικούς αλγόριθμους. Θα μάθουμε περισσότερα για το πώς οι υπολογιστές μαθαίνουν να παίζουν παιχνίδια σαν αυτό στην επόμενη ενότητα.
Ο στόχος σας είναι να λύσετε τη λεγόμενη Διοφαντική εξίσωση - μια εξίσωση με ακέραιες ρίζες. Για παράδειγμα, εξετάστε την εξίσωση a+2b+3c+4d=30. Πρέπει να βρείτε τις ακέραιες ρίζες που ικανοποιούν αυτή την εξίσωση.
Αυτή η εργασία είναι εμπνευσμένη από αυτή την ανάρτηση.
Υποδείξεις:
- Μπορείτε να θεωρήσετε ότι οι ρίζες βρίσκονται στο διάστημα [0;30]
- Ως γονίδιο, σκεφτείτε να χρησιμοποιήσετε τη λίστα των τιμών των ριζών
Χρησιμοποιήστε Diophantine.ipynb ως σημείο εκκίνησης.