Στον τομέα της τεχνητής νοημοσύνης, ένας εξελικτικός αλγόριθμος (EA) είναι ένα υποσύνολο υπολογισμών συνολικού πληθυσμού που βασίζονται στη μεταευρετική βελτιστοποίηση. Η EA χρησιμοποιεί μηχανισμούς εμπνευσμένους από τη βιολογική ανάπτυξη, όπως η αναπαραγωγή, η μετάλλαξη, ο ανασυνδυασμός και η επιλογή. Η υποψήφια λύση στο πρόβλημα των αλγορίθμων εξελικτικής βελτιστοποίησης παίζει το ρόλο των ατόμων στον πληθυσμό. Και επίσης η λειτουργία φυσικής κατάστασης καθορίζει την ποιότητα των απαντήσεων.
Οι εξελικτικοί αλγόριθμοι συχνά προσεγγίζουν καλά τις λύσεις σε όλους τους τύπους προβλημάτων. Επειδή στην ιδανική περίπτωση δεν κάνουν υποθέσεις σχετικά με το υποκείμενο τοπίο φυσικής κατάστασης. Οι μέθοδοι που χρησιμοποιούνται για την εξελικτική μοντελοποίηση και τους γενετικούς αλγόριθμους συνήθως περιορίζονται σε μελέτες μικροεξελικτικών διαδικασιών και μοντέλων σχεδιασμού που βασίζονται σε κυτταρικά στάδια. Στις περισσότερες πραγματικές εφαρμογές EA, η υπολογιστική πολυπλοκότητα είναι ένας απαγορευτικός παράγοντας.
Στην πραγματικότητααυτό το ζήτημα σχετίζεται με την εκτίμηση της συνάρτησης φυσικής κατάστασης. Η προσέγγιση της φυσικής κατάστασης είναι μια λύση για να ξεπεραστεί αυτή η δυσκολία. Ωστόσο, ένα φαινομενικά απλό EA μπορεί να λύσει συχνά πολύπλοκα προβλήματα. Επομένως, δεν μπορεί να υπάρξει άμεση σχέση μεταξύ της πολυπλοκότητας της ακολουθίας και του προβλήματος. Περισσότερες λεπτομέρειες μπορείτε να βρείτε στα βιβλία "Evolutionary Algorithms".
Εφαρμογή
Το πρώτο βήμα είναι να δημιουργήσετε έναν αρχικό πληθυσμό ατόμων τυχαία.
Το δεύτερο βήμα είναι να αξιολογήσετε την καταλληλότητα κάθε ατόμου σε αυτήν την ομάδα (χρονο όριο, επαρκής ετοιμότητα κ.λπ.).
Βήμα τρίτο - επαναλάβετε τα ακόλουθα βήματα αναγέννησης μέχρι την ολοκλήρωση:
- Επιλέξτε τα πιο κατάλληλα άτομα για αναπαραγωγή (γονείς).
- Φέρτε νέα άτομα που έχουν περάσει τον εξελικτικό αλγόριθμο χρησιμοποιώντας διασταύρωση και μετάλλαξη για να αποκτήσετε απογόνους.
- Αξιολογήστε την ατομική φυσική κατάσταση νέων ανθρώπων.
- Αντικαταστήστε τον λιγότερο κατάλληλο πληθυσμό με αυτούς.
Τύποι
Ο Γενετικός Αλγόριθμος είναι μια εξελικτική ακολουθία, ο πιο δημοφιλής τύπος Expert Advisor. Μια λύση στο πρόβλημα αναζητείται με τη μορφή συμβολοσειρών αριθμών (παραδοσιακά δυαδικοί, αν και οι καλύτερες αναπαραστάσεις είναι συνήθως αυτές που αντικατοπτρίζονται περισσότερο στο πρόβλημα που επιλύεται) με την εφαρμογή τελεστών όπως ο ανασυνδυασμός και η μετάλλαξη (μερικές φορές ένας, σε ορισμένες περιπτώσεις και οι δύο). Αυτός ο τύπος Expert Advisor χρησιμοποιείται συχνά σε προβλήματα βελτιστοποίησης. Ένα άλλο όνομα για αυτό είναι fetura (από τα λατινικά για "γέννηση"):
- Γενετικός προγραμματισμός. Παρουσιάζει λύσεις ως κωδικούς υπολογιστή και η καταλληλότητά τους καθορίζεται από την ικανότητά τους να εκτελούν υπολογιστικές εργασίες.
- Εξελικτικός προγραμματισμός. Παρόμοιο με τον εξελικτικό γενετικό αλγόριθμο, αλλά η δομή είναι σταθερή και οι αριθμητικές του παράμετροι μπορούν να αλλάξουν.
- Προγραμματισμός γονιδιακής έκφρασης. Αναπτύσσει εφαρμογές υπολογιστή, αλλά εξερευνά το σύστημα γονότυπου-φαινοτύπου, όπου έργα διαφορετικών μεγεθών κωδικοποιούνται σε γραμμικά χρωμοσώματα σταθερού μήκους.
- Στρατηγική. Λειτουργεί με διανύσματα πραγματικών αριθμών ως αναπαραστάσεις λύσεων. Συνήθως χρησιμοποιεί αυτοπροσαρμοστικούς αλγόριθμους ρυθμού εξελικτικής μετάλλαξης.
- Διαφορική ανάπτυξη. Βασίζεται σε διανυσματικές διαφορές και επομένως είναι κατά κύριο λόγο κατάλληλο για προβλήματα αριθμητικής βελτιστοποίησης.
- Νευροεξέλιξη. Παρόμοια με τον εξελικτικό προγραμματισμό και τους γενετικούς αλγόριθμους. Αλλά τα τελευταία είναι τεχνητά νευρωνικά δίκτυα, που περιγράφουν τη δομή και το βάρος των συνδέσεων. Η κωδικοποίηση του γονιδιώματος μπορεί να είναι άμεση ή έμμεση.
Σύγκριση με βιολογικές διεργασίες
Ένας πιθανός περιορισμός πολλών εξελικτικών αλγορίθμων είναι η έλλειψη σαφούς διάκρισης μεταξύ γονότυπου και φαινοτύπου. Στη φύση, ένα γονιμοποιημένο ωάριο υφίσταται μια περίπλοκη διαδικασία γνωστή ως εμβρυογένεση για να γίνει ώριμο. Αυτή η έμμεση κωδικοποίηση πιστεύεται ότι κάνει τις γενετικές αναζητήσεις πιο αξιόπιστες (δηλαδή, λιγότερο πιθανό να προκαλέσουν θανατηφόρες μεταλλάξεις) και μπορεί επίσης να βελτιώσει την ικανότητα του οργανισμού να αναπτυχθεί. Τέτοια έμμεσα (με άλλα λόγια,οι γενετικές ή αναπτυξιακές) κωδικοποιήσεις επιτρέπουν επίσης στην εξέλιξη να εκμεταλλευτεί την κανονικότητα στο περιβάλλον.
Πρόσφατες εργασίες στην τεχνητή εμβρυογένεση ή στα αναπτυξιακά συστήματα επιδιώκουν να αντιμετωπίσουν αυτά τα ζητήματα. Κατά τον προγραμματισμό της γονιδιακής έκφρασης, η περιοχή γονότυπου-φαινοτύπου διερευνάται με επιτυχία, όπου το πρώτο αποτελείται από γραμμικά πολυγονιδιακά χρωμοσώματα σταθερού μήκους και το δεύτερο από πολλά δέντρα έκφρασης ή προγράμματα υπολογιστή διαφόρων μεγεθών και σχημάτων.
Σχετικές τεχνικές
Οι αλγόριθμοι περιλαμβάνουν:
- Βελτιστοποίηση αποικίας μυρμηγκιών. Βασίζεται στην ιδέα ότι τα έντομα αναζητούν τροφή συνδέοντας με φερομόνες για να σχηματίσουν μονοπάτια. Κατάλληλο κυρίως για συνδυαστική βελτιστοποίηση και προβλήματα γραφημάτων.
- Αλγόριθμος ρυθμιστικού ρίζας. Ο δημιουργός εμπνεύστηκε τη λειτουργία των ριζών των φυτών στη φύση.
- Αλγόριθμος για τεχνητές αποικίες μελισσών. Με βάση τη συμπεριφορά των μελισσών. Προτείνεται κυρίως για αριθμητική βελτιστοποίηση και επεκτείνεται για την επίλυση συνδυαστικών, περιορισμένων και πολυσκοπικών προβλημάτων. Ο αλγόριθμος των μελισσών βασίζεται στην τροφοσυλλεκτική συμπεριφορά των εντόμων. Έχει εφαρμοστεί σε πολλές εφαρμογές όπως η δρομολόγηση και ο προγραμματισμός.
- Βελτιστοποίηση σμήνος σωματιδίων - με βάση ιδέες συμπεριφοράς κοπαδιών ζώων. Και επίσης κατά κύριο λόγο κατάλληλο για εργασίες αριθμητικής διεργασίας.
Άλλες δημοφιλείς μεταευρετικές μέθοδοι
- Αναζήτηση κυνηγιού. Μια μέθοδος που βασίζεται στην ομαδική σύλληψη ορισμένων ζώων, όπως οι λύκοι, για παράδειγμα, πουκατανέμουν τα καθήκοντά τους για να περιβάλλουν το θήραμα. Κάθε ένα από τα μέλη του εξελικτικού αλγορίθμου σχετίζεται με τα άλλα κατά κάποιο τρόπο. Αυτό ισχύει ιδιαίτερα για τον ηγέτη. Αυτή είναι μια μέθοδος συνεχούς βελτιστοποίησης προσαρμοσμένη ως μέθοδος συνδυαστικής διαδικασίας.
- Αναζήτηση κατά μετρήσεις. Σε αντίθεση με τις μεταευρετικές μεθόδους που βασίζονται στη φύση, ο αλγόριθμος προσαρμοστικής διαδικασίας δεν χρησιμοποιεί τη μεταφορά ως κύρια αρχή. Αντίθετα, χρησιμοποιεί μια απλή μέθοδο προσανατολισμένη στην απόδοση που βασίζεται στην ενημέρωση της παραμέτρου αναλογίας διαστάσεων αναζήτησης σε κάθε επανάληψη. Ο αλγόριθμος Firefly είναι εμπνευσμένος από το πώς οι πυγολαμπίδες προσελκύουν η μία την άλλη με το φως που αναβοσβήνει. Αυτό είναι ιδιαίτερα χρήσιμο για πολυτροπική βελτιστοποίηση.
- Αναζήτηση αρμονίας. Βασισμένο στις ιδέες της συμπεριφοράς των μουσικών. Σε αυτήν την περίπτωση, οι εξελικτικοί αλγόριθμοι είναι ο τρόπος για τη συνδυαστική βελτιστοποίηση.
- Γκαουσιανή προσαρμογή. Με βάση τη θεωρία της πληροφορίας. Χρησιμοποιείται για τη μεγιστοποίηση της απόδοσης και της μέσης διαθεσιμότητας. Ένα παράδειγμα εξελικτικών αλγορίθμων σε αυτήν την κατάσταση: εντροπία στη θερμοδυναμική και τη θεωρία πληροφοριών.
Memetic
Μια υβριδική μέθοδος που βασίζεται στην ιδέα του Richard Dawkins για ένα μιμίδιο. Συνήθως παίρνει τη μορφή αλγορίθμου βασισμένου σε πληθυσμό σε συνδυασμό με μεμονωμένες διαδικασίες μάθησης ικανές να εκτελούν τοπικές βελτιώσεις. Δίνει έμφαση στη χρήση γνώσεων σχετικά με το πρόβλημα και επιχειρεί να οργανώσει λεπτομερείς και καθολικές αναζητήσεις με συνεργιστικό τρόπο.
ΕξελικτικόΟι αλγόριθμοι είναι μια ευρετική προσέγγιση σε προβλήματα που δεν μπορούν εύκολα να επιλυθούν σε πολυωνυμικό χρόνο, όπως τα κλασικά προβλήματα NP-σκληρών και οτιδήποτε άλλο θα χρειαζόταν πολύ χρόνο για να επεξεργαστεί εξαντλητικά. Όταν χρησιμοποιούνται ανεξάρτητα, συνήθως χρησιμοποιούνται για συνδυαστικά προβλήματα. Ωστόσο, οι γενετικοί αλγόριθμοι χρησιμοποιούνται συχνά παράλληλα με άλλες μεθόδους, λειτουργώντας ως ένας γρήγορος τρόπος για την εύρεση πολλαπλών βέλτιστων θέσεων εκκίνησης.
Η υπόθεση του εξελικτικού αλγορίθμου (γνωστός ως σύμβουλος) είναι αρκετά απλή δεδομένου ότι είστε εξοικειωμένοι με τη διαδικασία της φυσικής επιλογής. Περιλαμβάνει τέσσερα κύρια βήματα:
- αρχικοποίηση;
- επιλογή;
- γενετικοί τελεστές;
- τέλος.
Κάθε ένα από αυτά τα βήματα αντιστοιχεί κατά προσέγγιση σε μια συγκεκριμένη πτυχή της φυσικής επιλογής και παρέχει εύκολους τρόπους για να διαμορφώσετε αυτή την κατηγορία αλγορίθμων. Με απλά λόγια, στην EA, τα πιο κατάλληλα μέλη θα επιβιώσουν και θα αναπαραχθούν, ενώ τα ακατάλληλα μέλη θα πεθάνουν και δεν θα συνεισφέρουν στη γονιδιακή δεξαμενή της επόμενης γενιάς.
Αρχικοποίηση
Για να ξεκινήσετε τον αλγόριθμο, πρέπει πρώτα να δημιουργήσετε ένα σύνολο λύσεων. Ο πληθυσμός θα περιέχει έναν αυθαίρετο αριθμό πιθανών δηλώσεων προβλημάτων, που συχνά αναφέρονται ως μέλη. Συχνά δημιουργούνται τυχαία (εντός των περιορισμών της εργασίας) ή, εάν είναι γνωστή κάποια προηγούμενη γνώση, επικεντρώνονται δοκιμαστικά γύρω από αυτό που θεωρείται ιδανικό. Είναι σημαντικό ο πληθυσμός να καλύπτει ένα ευρύ φάσμα λύσεων,γιατί ουσιαστικά είναι μια γονιδιακή δεξαμενή. Επομένως, εάν κάποιος θέλει να εξερευνήσει πολλές διαφορετικές δυνατότητες μέσα σε έναν αλγόριθμο, θα πρέπει να προσπαθήσει να έχει πολλά διαφορετικά γονίδια.
Επιλογή
Μόλις δημιουργηθεί ο πληθυσμός, τα μέλη του πρέπει τώρα να αξιολογηθούν σύμφωνα με τη συνάρτηση φυσικής κατάστασης. Η συνάρτηση fitness λαμβάνει τα χαρακτηριστικά ενός μέλους και δίνει μια αριθμητική αναπαράσταση του πόσο ταιριάζει το μέλος. Η δημιουργία τους μπορεί συχνά να είναι πολύ δύσκολη. Είναι σημαντικό να βρείτε ένα καλό σύστημα που να αντιπροσωπεύει με ακρίβεια τα δεδομένα. Αυτό είναι πολύ συγκεκριμένο για το πρόβλημα. Τώρα είναι απαραίτητο να υπολογίσετε την καταλληλότητα όλων των συμμετεχόντων και να επιλέξετε μερικά από τα καλύτερα μέλη.
Συναρτήσεις πολλαπλών αντικειμένων
Οι ΕΑ μπορούν επίσης να επεκταθούν για τη χρήση αυτών των συστημάτων. Αυτό περιπλέκει κάπως τη διαδικασία, επειδή αντί να προσδιορίζεται ένα βέλτιστο σημείο, λαμβάνεται ένα σύνολο κατά τη χρήση τους. Το σύνολο των λύσεων ονομάζεται σύνορο Pareto και περιέχει στοιχεία που είναι εξίσου κατάλληλα με την έννοια ότι καμία από αυτές δεν κυριαρχεί σε κανένα άλλο.
Γενετικοί τελεστές
Αυτό το βήμα περιλαμβάνει δύο υποστάδια: διασταύρωση και μετάλλαξη. Μετά την επιλογή των καλύτερων όρων (συνήθως οι κορυφαίοι 2, αλλά αυτός ο αριθμός μπορεί να ποικίλλει), χρησιμοποιούνται τώρα για τη δημιουργία της επόμενης γενιάς στον αλγόριθμο. Εφαρμόζοντας τα χαρακτηριστικά των επιλεγμένων γονέων δημιουργούνται νέα παιδιά που αποτελούν ένα μείγμα ιδιοτήτων. Αυτό μπορεί συχνά να είναι δύσκολο ανάλογα με τον τύπο των δεδομένων, αλλά συνήθως σε συνδυαστικά προβλήματαείναι πολύ πιθανό να αναμειχθούν και να βγουν έγκυροι συνδυασμοί.
Τώρα είναι απαραίτητο να εισαχθεί νέο γενετικό υλικό στη γενιά. Εάν δεν γίνει αυτό το σημαντικό βήμα, ο επιστήμονας πολύ γρήγορα θα κολλήσει σε τοπικά ακραία και δεν θα έχει τα βέλτιστα αποτελέσματα. Αυτό το βήμα είναι μια μετάλλαξη και γίνεται πολύ απλά, αλλάζοντας ένα μικρό μέρος των παιδιών με τέτοιο τρόπο ώστε κατά κύριο λόγο να μην αντικατοπτρίζουν υποσύνολα των γονιδίων των γονιών. Η μετάλλαξη εμφανίζεται συνήθως πιθανολογικά, καθώς η πιθανότητα να την αποκτήσει ένα παιδί, καθώς και η σοβαρότητά της, καθορίζονται από την κατανομή.
Τερματισμός
Στο τέλος, ο αλγόριθμος πρέπει να τελειώσει. Αυτό συμβαίνει συνήθως σε δύο περιπτώσεις: είτε έχει φτάσει σε κάποιο μέγιστο χρόνο εκτέλεσης είτε έχει φτάσει σε ένα όριο απόδοσης. Σε αυτό το σημείο, επιλέγεται και επιστρέφεται η τελική λύση.
Παράδειγμα εξελικτικών αλγορίθμων
Τώρα, για να δείξετε το αποτέλεσμα αυτής της διαδικασίας, πρέπει να δείτε τον σύμβουλο σε δράση. Για να γίνει αυτό, μπορούμε να θυμηθούμε πώς πολλές γενιές δεινοσαύρων έμαθαν να περπατούν (σταδιακά να κυριαρχούν στη γη), βελτιστοποιώντας τη δομή του σώματός τους και εφαρμόζοντας μυϊκή δύναμη. Παρόλο που τα ερπετά πρώιμης γενιάς δεν μπορούσαν να περπατήσουν, ο σύμβουλος μπόρεσε να τα εξελίξει με την πάροδο του χρόνου μέσω μετάλλαξης και διασταύρωσης σε μια μορφή που μπορούσε να περπατήσει.
Αυτοί οι αλγόριθμοι γίνονται όλο και πιο σχετικοί στον σύγχρονο κόσμο, καθώς οι λύσεις που βασίζονται σε αυτούς χρησιμοποιούνται όλο και περισσότερο σε κλάδους όπως το ψηφιακό μάρκετινγκ, τα χρηματοοικονομικά καιυγειονομική περίθαλψη.
Πού χρησιμοποιούνται οι EA;
Ευρύτερα, οι εξελικτικοί αλγόριθμοι χρησιμοποιούνται σε μια μεγάλη ποικιλία εφαρμογών όπως η επεξεργασία εικόνας, η δρομολόγηση οχημάτων, η βελτιστοποίηση κινητών επικοινωνιών, η ανάπτυξη λογισμικού, ακόμη και η εκπαίδευση σε τεχνητά νευρωνικά δίκτυα. Αυτά τα εργαλεία βρίσκονται στην καρδιά πολλών από τις εφαρμογές και τους ιστότοπους που χρησιμοποιούν οι άνθρωποι σε καθημερινή βάση, συμπεριλαμβανομένων των Χαρτών Google, ακόμη και παιχνιδιών όπως το The Sims. Επιπλέον, ο ιατρικός τομέας χρησιμοποιεί την ΕΑ για να βοηθήσει στη λήψη κλινικών αποφάσεων σχετικά με τη θεραπεία του καρκίνου. Στην πραγματικότητα, οι εξελικτικοί αλγόριθμοι είναι τόσο ισχυροί που μπορούν να χρησιμοποιηθούν για την επίλυση σχεδόν κάθε προβλήματος βελτιστοποίησης.
Νόμος του Moore
Ο αυξανόμενος επιπολασμός της EO οφείλεται σε δύο κύριους παράγοντες: τη διαθέσιμη υπολογιστική ισχύ και τη συσσώρευση μεγάλων συνόλων δεδομένων. Το πρώτο μπορεί να περιγραφεί από τον νόμο του Moore, ο οποίος ουσιαστικά δηλώνει ότι η ποσότητα της υπολογιστικής ισχύος σε έναν υπολογιστή διπλασιάζεται περίπου κάθε δύο χρόνια. Αυτή η πρόβλεψη ισχύει για δεκαετίες. Ο δεύτερος παράγοντας σχετίζεται με την αυξανόμενη εξάρτηση από την τεχνολογία, η οποία επιτρέπει στα ιδρύματα να συλλέγουν έναν απίστευτα μεγάλο όγκο δεδομένων, που τους επιτρέπει να αναλύουν τις τάσεις και να βελτιστοποιούν τα προϊόντα.
Πώς μπορούν οι εξελικτικοί αλγόριθμοι να βοηθήσουν τους εμπόρους;
Οι συνθήκες της αγοράς αλλάζουν ταχέως και είναι πολύ ανταγωνιστικές. Αυτό ανάγκασε τους διευθυντές μάρκετινγκ να ανταγωνίζονται για καλύτερη λήψη αποφάσεων. Αύξηση των διαθέσιμωνΗ υπολογιστική ισχύς οδήγησε τους εργαζόμενους να χρησιμοποιούν την EA για την επίλυση προβλημάτων.
Βελτιστοποίηση μετατροπών
Ένας από τους κύριους στόχους είναι η αύξηση του ποσοστού επισκεπτών στον ιστότοπο. Αυτό το πρόβλημα καταλήγει στη βελτιστοποίηση του αριθμού των χρηστών που κάνουν αυτό που θέλει ο έμπορος. Για παράδειγμα, εάν μια εταιρεία πουλά φορητούς υπολογιστές, το ιδανικό είναι να αυξήσει τον αριθμό των επισκεπτών του ιστότοπου που τελικά αγοράζουν το προϊόν. Αυτή είναι η ουσία της βελτιστοποίησης ποσοστού μετατροπών.
Μία από τις εκπληκτικά σημαντικές πτυχές είναι η επιλογή της διεπαφής χρήστη. Εάν το web design δεν είναι πολύ φιλικό προς το χρήστη, υπάρχουν εκείνοι που τελικά δεν αγοράζουν το προϊόν για τον έναν ή τον άλλο λόγο. Ο στόχος λοιπόν είναι να μειωθεί ο αριθμός των χρηστών που τελικά δεν πραγματοποιούν μετατροπές, γεγονός που αυξάνει το συνολικό κέρδος.
