Επίλυση προβλημάτων (τεχνητή νοημοσύνη): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
|||
Γραμμή 2:
== Προβλήματα ==
Ένα [[πρόβλημα]] είναι ένα σύνολο αντικειμένων, ιδιοτήτων και σχέσεων το οποίο ορίζεται από μία αρχική κατάσταση, μία επιθυμητή τελική κατάσταση και τις επιτρεπτές ενέργειες στα αντικείμενα του προβλήματος. Στόχος είναι, ξεκινώντας από την αρχική κατάσταση, να γίνει μία κατάλληλη ακολουθία ενεργειών η οποία να καταλήγει στην τελική κατάσταση. Αυτή η διαδικασία ονομάζεται επίλυση του προβλήματος (π.χ. η διεξαγωγή μίας παρτίδας [[σκάκι]]) και αποτέλεσε στόχο της ΤΝ από τη δεκαετία του '50. Η επίλυση προβλημάτων έχει προφανώς σπουδαίες εφαρμογές στην απόδειξη [[θεώρημα|θεωρημάτων]], στον χρονοπρογραμματισμό ενεργειών, στη διεξαγωγή [[παιχνίδι|παιγνίων]] κλπ, ενώ θεωρείται κεντρικό χαρακτηριστικό της [[ευφυΐα|ευφυΐας]]. Βασικό στοιχείο στην επίλυση προβλημάτων είναι η αναπαράσταση τους και γι' αυτό το σκοπό υπάρχουν δύο μεθοδολογίες: η αναπαράσταση με χώρο καταστάσεων και η αναπαράσταση με αναγωγή. Στη μέθοδο της αναγωγής δομική μονάδα περιγραφής του προβλήματος είναι η ίδια η περιγραφή αναλυόμενη σε πολλαπλές, απλούστερες εκδοχές. Αυτή η ανάλυση συμβαίνει διαδοχικά ώσπου να καταλήξει σε αρχέγονα προβλήματα επιλυόμενα με προφανή τρόπο. Προγραμματιστικά η αναγωγή υλοποιείται με [[αναδρομή]] και κεντρική έννοια σε αυτήν αποτελούν οι τελεστές αναγωγής, διαδικασίες οι οποίες ανάγουν ένα πρόβλημα σε υποπροβλήματα.
Στη μέθοδο χώρου καταστάσεων βασική δομική μονάδα είναι η κατάσταση, το σύνολο δηλαδή των αντικειμένων που εμπλέκονται στο πρόβλημα συν τις ιδιότητες τους και τις μεταξύ τους σχέσεις. Η κατάσταση ορίζεται σε ένα απλουστευμένο, αφαιρετικό [[μοντέλο]] του κόσμου και το σύνολο των καταστάσεων (στιγμιοτύπων) στις οποίες μπορεί να βρεθεί αυτός ο κόσμος του προβλήματος ονομάζεται χώρος καταστάσεων. Το ίδιο το πρόβλημα ορίζεται με βάση την αρχική κατάσταση από την οποία ξεκινάμε, την επιθυμητή τελική
Ο πιο κατάλληλος τρόπος γραφικής αναπαράστασης του προβλήματος είναι ένας [[δένδρο (υπολογιστές)|δενδρικός]] [[γράφος]] με ρίζα την αρχική κατάσταση, φύλλα τις τελικές καταστάσεις και τα αδιέξοδα, κόμβους τις ενδιάμεσες καταστάσεις και κλαδιά τους τελεστές μετάβασης. Επέκταση ενός κόμβου ονομάζεται η εύρεση όλων των παιδιών του στο δένδρο μέσω της εφαρμογής σε αυτόν όλων των πιθανών τελεστών. Οι λύσεις του προβλήματος είναι μονοπάτια από τη ρίζα σε κάποιο φύλλο του δένδρου που αντιστοιχεί σε τελική κατάσταση. Σε πραγματικά προβλήματα το μέγεθος αυτού του δένδρου γίνεται εξαιρετικά μεγάλο μετά την επέκταση λίγων μόλις κόμβων και επομένως η αναζήτηση λύσεων σε ένα τέτοιο δένδρο καθίσταται εξαιρετικά χρονοβόρα. Αυτό το ζήτημα στη βιβλιογραφία της ΤΝ αναφέρεται ως "συνδυαστική έκρηξη".
== Αλγόριθμοι αναζήτησης ==
Υπάρχει μία πλειάδα πραγματικών ή συνθετικών, απλών ή πολύπλοκων προβλημάτων που μπορούν να αναπαρασταθούν με χώρο καταστάσεων. Όλα τα προηγούμενα βρίσκουν εφαρμογή και το μόνο που αλλάζει σε κάθε πρόβλημα είναι οι λεπτομέρειες (οι ιδιότητες των αντικειμένων, οι επιτρεπτοί τελεστές κλπ). Προκειμένου ένα πρόγραμμα να επιλύσει ένα τέτοιο πρόβλημα πρέπει να αναπαραστήσει κατάλληλα και να κατασκευάσει το δένδρο των καταστάσεων, ξεκινώντας από τη ρίζα και επεκτείνοντας τους κόμβους μέχρι να φτάσει σε κάποια τελική κατάσταση. Αν το ζητούμενο είναι να βρεθεί μία οποιαδήποτε λύση τότε το πρόγραμμα μπορεί τότε να τερματίσει επιστρέφοντας το μονοπάτι που οδηγεί στο τρέχον φύλλο, διαφορετικά (''εξαντλητική αναζήτηση'') μπορεί να αποθηκεύσει έναν [[δείκτης (υπολογιστές)|δείκτη]] προς αυτό το φύλλο και να συνεχίσει την κατασκευή του δένδρου μέχρι να ανακαλύψει όλες τις πιθανές καταστάσεις που είναι προσβάσιμες από την αρχική, με τους διαθέσιμους τελεστές μετάβασης, και όλες τις πιθανές λύσεις.
Υπάρχει ένας γενικός αλγόριθμος αναζήτησης που εκτελεί αυτήν τη διερεύνηση και οι πραγματικοί αλγόριθμοι που χρησιμοποιούνται είναι παραλλαγές του που διαφέρουν στα βήματα 7 και 8. Στον αλγόριθμο αυτό Μέτωπο Αναζήτησης (Μ.Α.) είναι το σύνολο των καταστάσεων που έχουμε επισκεφθεί αλλά δεν έχουμε επεκτείνει και Κλειστό Σύνολο (Κ.Σ.) το σύνολο των καταστάσεων που και έχουμε επισκεφθεί και έχουμε επεκτείνει. Το Κ.Σ. είναι απαραίτητο μόνο αν υπάρχει κίνδυνος παγίδευσης του αλγορίθμου σε [[ατέρμων βρόχος|ατέρμονα βρόχο]] λόγω απείρου μήκους κλαδιών στο δένδρο.
1: Μ.Α = NULL; Κ.Σ. = NULL;
Γραμμή 26:
9: }
Οι διάφορες πραγματικές παραλλαγές αυτού του αλγορίθμου διακρίνονται σε αλγορίθμους '''τυφλής αναζήτησης''', που διατάσσουν το Μ.Α. αποκλειστικά με βάση το χρόνο δημιουργίας κάθε κόμβου κατά την κατασκευή του δένδρου, και σε αλγορίθμους '''ευρετικής αναζήτησης''' (heuristic search), όπου τα βήματα 7 και 8 εξαρτώνται από μία επιπλέον πληροφορία που υπολογίζεται σε [[πραγματικός χρόνος|πραγματικό χρόνο]] και που στις περισσότερες περιπτώσεις, αλλά όχι πάντα, είναι σχετικά ακριβής και αξιολογεί προσεγγιστικά τις καταστάσεις σε "καλές" και "κακές". Ένα παράδειγμα ευρετικής πληροφορίας που μπορεί να αντιστοιχιστεί σε κάθε ενδιάμεση κατάσταση είναι η εκτιμώμενη "απόσταση" της (με βάση ένα μέτρο που εξαρτάται από το πρόβλημα και την υλοποίηση) από την τελική. Έτσι μπορούμε, φερ' ειπείν, να κλαδεύουμε τα υποδένδρα με ρίζα "κακή" κατάσταση, αφαιρώντας τη ρίζα τους από το Μ.Α. προτού την επεκτείνουμε (βήμα 7). Προφανώς αυτή η τακτική συμβάλλει στην αντιμετώπιση του φαινομένου της συνδυαστικής έκρηξης.
Μία άλλη κατηγοριοποίηση των αλγορίθμων γίνεται ανάλογα με τον τύπο του προβλήματος που επιλύουν: εκτός από τα συνηθισμένα που προαναφέρθηκαν, υπάρχουν και προβλήματα βελτιστοποίησης (όπου σε κάθε τελεστή μετάβασης αντιστοιχίζεται μία τιμή [[κόστος|κόστους]] και αναζητούμε τη λύση με το μονοπάτι που αθροιστικά έχει το ελάχιστο κόστος) ή προβλήματα ικανοποίησης περιορισμών (όπου η τελική κατάσταση δεν είναι πλήρως γνωστή, γνωρίζουμε όμως κάποιες ιδιότητες της και επιθυμούμε να καταλήξουμε σε μία κατάσταση που να τις διαθέτει). Πληρότητα ενός αλγορίθμου αναζήτησης ονομάζεται το κατά πόσον βρίσκει πάντα μία λύση, εφ' όσον τέτοια υπάρχει.
=== Τυφλή αναζήτηση ===
Οι σπουδαιότεροι αλγόριθμοι τυφλής αναζήτησης είναι ο DFS (''Depth-First Search'' ή ''αναζήτηση κατά βάθος'') και ο BFS (''Breadth-First Search'' ή ''αναζήτηση κατά πλάτος''), οι οποίοι κατασκευάζουν το δένδρο ξεκινώντας από τη ρίζα και παράγοντας κόμβους, ο μεν DFS κατά βάθος (ακολουθεί ένα κλαδί μέχρι να φτάσει σε φύλλο και μετά επεκτείνει έναν κόμβο προηγούμενου επιπέδου· αυτή η μέθοδος ονομάζεται
Ο BFS εγγυάται ότι θα βρει πρώτα τη λύση με την ελάχιστη απόσταση από τη ρίζα (οπότε είναι ιδανικός και για προβλήματα βελτιστοποίησης όπου όλοι οι τελεστές έχουν ίσο κόστος) και είναι πλήρης, το Μ.Α. όμως μπορεί να γιγαντωθεί για μεγάλους χώρους αναζήτησης και άρα έχει μεγάλες απαιτήσεις σε [[μνήμη]]. Από την άλλη ο DFS είναι τυχαίο το ποια λύση θα βρει πρώτα και δεν είναι πλήρης, καθώς αν δε χρησιμοποιείται Κλειστό Σύνολο μπορεί να παγιδευτεί σε κλαδιά απείρου μήκους (αφού ακολουθεί ένα κλαδί μέχρι να καταλήξει σε φύλλο). Από την άλλη έχει μικρές απαιτήσεις σε μνήμη διατηρώντας πάντα μικρό το Μ.Α.
Συμβιβασμό μεταξύ αυτών των δύο αποτελεί ο αλγόριθμος ID (''Iterative Deepening'' ή ''επαναληπτική εκβάθυνση''), ο οποίος είναι κατά βάση DFS αλλά προχωρά μέχρι ένα προκαθορισμένο βάθος, ενώ στη συνέχεια το επιτρεπτό βάθος αυξάνεται και ο αλγόριθμος ξεκινά από την αρχή χωρίς να διατηρεί
Οποιοσδήποτε από αυτούς τους αλγορίθμους μπορεί να χρησιμοποιηθεί με τη μέθοδο BiS (''
Σε προβλήματα βελτιστοποίησης με τελεστές διαφορετικού (αλλά πάντα θετικού) κόστους μπορεί να εφαρμοστεί ο αλγόριθμος τυφλής αναζήτησης B&B (''
=== Ευρετική αναζήτηση ===
Προκειμένου να μειωθεί ο, γιγάντιος για ρεαλιστικά προβλήματα, χώρος αναζήτησης και ο απαιτούμενος για την εύρεση της λύσης χρόνος, μπορούν να χρησιμοποιηθούν αλγόριθμοι που εκμεταλλεύονται ευρετικούς μηχανισμούς
Ένας βασικός ευρετικός αλγόριθμος είναι ο HC (''
Όλοι αυτοί οι ευρετικοί αλγόριθμοι κατάγονται από τη θεωρία μαθηματικής
Άλλος δημοφιλής ευρετικός αλγόριθμος είναι ο BestFS (''
=== Παίγνια ===
Μία ειδική κατηγορία προβλημάτων ΤΝ είναι τα παίγνια δύο αντιπάλων (π.χ. σκάκι). Εδώ υπάρχουν δύο διαφορετικά σύνολα τελεστών μετάβασης που εφαρμόζονται εναλλάξ από δύο ανταγωνιστικά ενεργά συστήματα (τους παίκτες). Οι τελικές καταστάσεις δεν είναι πλήρως γνωστές, έχουν όμως συγκεκριμένα γνωστά χαρακτηριστικά και αντιστοιχούν σε ισοπαλία ή σε νίκη ενός εκ των δύο αντιπάλων / ήττα του άλλου. Στα προβλήματα αυτά ξεκινώντας από μία κατάσταση μπορούμε με συνεχείς επεκτάσεις να δημιουργήσουμε το δένδρο του παιχνιδιού, με όλα τα εναλλακτικά μονοπάτια που πηγάζουν από την τρέχουσα κατάσταση, στο οποίο οι κινήσεις δύο διαδοχικών επιπέδων (όπου κίνηση είναι ένα κλαδί του δένδρου, δηλαδή η μετάβαση από μία κατάσταση σε άλλη) αντιστοιχούν σε διαφορετικό παίκτη. Η ανάπτυξη αυτού του δένδρου μπορεί να γίνει από κάθε πράκτορα προτού προβεί σε μία κίνηση μέχρι κάποιο βάθος (όσο μεγαλύτερο είναι αυτό το βάθος τόσο καλύτερα αποδίδει ο αλγόριθμος). Σε αυτό το σημείο ο παίκτης μπορεί να αξιολογήσει ευρετικά ποια από τις εναλλακτικές κινήσεις οδηγεί στην ευνοϊκότερη γι' αυτόν εξέλιξη. Στα περισσότερα πραγματικά παίγνια το βάθος του κατασκευαζόμενου σε κάθε εκτέλεση δένδρου δεν μπορεί να είναι πολύ μεγάλο λόγω του προβλήματος της συνδυαστική έκρηξης.
Ο σπουδαιότερος αλγόριθμος για επίλυση παιγνίων είναι ο Minimax (''
Ο αλγόριθμος ουσιαστικά εγγυάται πάντα την πιο συμφέρουσα εξέλιξη του παιχνιδιού, υποθέτοντας ότι ο αντίπαλος επιλέγει διαρκώς τις καλύτερες για εκείνον κινήσεις και δεν κάνει λάθη. Με τον Minimax υπάρχουν πάντα δυνατές κινήσεις οι οποίες φαίνεται να συμφέρουν περισσότερο, αγνοούνται όμως όταν μπορεί να οδηγήσουν σε καταστάσεις όπου ο αντίπαλος -ΑΝ κάνει την καλύτερη επιλογή- αποκτά προβάδισμα. Ο αλγόριθμος AB (''Άλφα Βήτα'') είναι παραλλαγή του εξαντλητικού Minimax με κλάδεμα προκειμένου να εξοικονομηθεί χρόνος, όπου αγνοούνται καταστάσεις-παιδιά οι οποίες αποκλείεται να δώσουν την τιμή τους
=== Ικανοποίηση περιορισμών ===
Μία σημαντική κατηγορία προβλημάτων είναι τα προβλήματα ικανοποίησης περιορισμών. Και σε αυτά δεν είναι πλήρως γνωστές οι τελικές καταστάσεις, μόνο κάποιες ιδιότητες τους και οι περιορισμοί που πρέπει να ικανοποιούν, αλλά επίσης δε μας ενδιαφέρει και το μονοπάτι που οδηγεί στη λύση: το μόνο που επιθυμούμε να βρούμε είναι η πλήρης μορφή μίας τελικής κατάστασης. Στα προβλήματα αυτά κωδικοποιούμε τους περιορισμούς με τη βοήθεια μεταβλητών και ενός πεδίου τιμών (διακριτών ή συνεχών, ανάλογα με το πρόβλημα) από το οποίο αυτές λαμβάνουν τιμή. Οι περιορισμοί αφορούν τις πιθανές τιμές που μπορεί να ανατεθούν σε κάθε μεταβλητή (ή σε κάποιες από τις μεταβλητές) και κάθε λύση που τους ικανοποιεί είναι αποδεκτή. Στην ικανοποίηση περιορισμών μπορούν να χρησιμοποιηθούν παραλλαγές του HC προσαρμοσμένες στην αναζήτηση σε χώρο μεταβλητών, όπου εκκινούμε από μία τυχαία ανάθεση τιμών στις μεταβλητές και σταδιακά τη διορθώνουμε (με τη βοήθεια ευρετικής αξιολόγησης) ώστε να παραβιάζει λιγότερους περιορισμούς, πάντα με τον εγγενή στην αναρρίχηση λόφων κίνδυνο να παγιδευτούμε σε τοπικό ελάχιστο του σφάλματος (τοπικά βέλτιστη λύση). Συνήθως σε κάθε επανάληψη του αλγορίθμου είτε γίνεται αναζήτηση, σε όλες τις μεταβλητές, μίας τιμής που ελαχιστοποιεί περαιτέρω τις διενέξεις με τους περιορισμούς, είτε επιλέγεται τυχαία μία μεταβλητή και αναζητώνται μόνο δικές της τιμές που μειώνουν τις διενέξεις.
Εναλλακτικά μπορούμε να κωδικοποιήσουμε περαιτέρω τις μεταβλητές σε καταστάσεις, όπου ο μόνος πιθανός τελεστής είναι η ανάθεση τιμής σε μία μεταβλητή, και να εφαρμόσουμε τυφλή αναζήτηση στο χώρο καταστάσεων που προκύπτει. Η τελευταία μέθοδος όμως δεν αποδίδει καλά σε μεγάλους χώρους λόγω της συνδυαστικής έκρηξης, οπότε μπορεί να συνδυαστεί με αλγορίθμους συνέπειας: οι τελευταίοι ελέγχουν διαδοχικά όλους τους περιορισμούς του προβλήματος και για τον καθέναν εξετάζουν τα πεδία τιμών των μεταβλητών ώστε να αφαιρέσουν τις τιμές που τον παραβιάζουν. Κάθε αφαίρεση απαιτεί επανέλεγχο των περιορισμών αφού μπορεί να επηρεάζονται και άλλες μεταβλητές μέσω αυτών. Οι αλγόριθμοι συνέπειας τόξου (AC) αναπαριστούν τις μεταβλητές ως κόμβους ενός γράφου και τους περιορισμούς ως τόξα που συνδέουν τους κατάλληλους κόμβους.
Ο απλούστερος αλγόριθμος της κατηγορίας είναι ο AC-3, ο οποίος μπορεί να χειριστεί μόνο δυαδικούς περιορισμούς (στους οποίους συμμετέχουν το πολύ δύο μεταβλητές)·
=== Εξελικτικός υπολογισμός ===
Γραμμή 71:
Στους γενετικούς αλγορίθμους αρχικά παράγεται ένα σύνολο Ν υποψήφιων λύσεων για το εκάστοτε πρόβλημα (πληθυσμός n), το οποίο κατασκευάζεται τυχαία και επομένως τα περισσότερα μέλη του είναι άκυρα ή μη βέλτιστα ως λύσεις. Αυτοί οι υποψήφιοι αξιολογούνται με μία καθοριζόμενη από τον χειριστή (συνήθως ευρευτική) πραγματική συνάρτηση διακριτής μεταβλητής, τη συνάρτηση καταλληλότητας, η οποία επιχειρεί να βαθμολογήσει κάθε υποψήφιο ανάλογα με το πόσο κοντά βρίσκεται σε κάποια ιδανική λύση. Ακολούθως από τον αρχικό πληθυσμό σχηματίζονται Ν/2 ζεύγη υποψηφίων ("γονέων"), με μεγαλύτερη προτεραιότητα στις πιο θετικά αξιολογημένες λύσεις, όπου κάθε υποψήφιος μπορεί να συμμετέχει σε περισσότερα από ένα ζεύγη. Τα μέλη κάθε ζεύγους συνδυάζονται με κάποιον τρόπο μεταξύ τους και το αποτέλεσμα είναι δύο νέες υποψήφιες λύσεις ("απόγονοι"). Ο νέος πληθυσμός n+1 αποτελείται από το σύνολο αυτών των απογόνων (''πλήρης ανανέωση''). Εναλλακτικά οι απόγονοι μπορούν να συνυπάρχουν με μέλη του αμέσως προηγούμενου πληθυσμού n (''μερική ανανέωση''), σε κάθε περίπτωση όμως ο [[πληθάριθμος]] Ν παραμένει σταθερός σε κάθε "γενιά".
Το ποσοστό υποψηφίων που αντικαθίσταται από απογόνους ονομάζεται "χάσμα γενεών" και στην πλήρη ανανέωση είναι 100%, ενώ στη μερική ανανέωση η πιθανότητα αντικατάστασης μίας λύσης της γενιάς n από απόγονο της γενιάς n+1 είναι αντιστρόφως ανάλογη της καταλληλότητας της. Η διαδικασία αυτή επαναλαμβάνεται μέχρι να ικανοποιηθεί κάποιο κριτήριο τερματισμού, δηλαδή συνήθως να βρεθεί μία λύση που αξιολογείται ως βέλτιστη από τη συνάρτηση καταλληλότητας ή ο [[μέσος όρος]] των λύσεων του τρέχοντος πληθυσμού να τείνει να συγκλίνει σε μία μόνο λύση (ή μικρές παραλλαγές μίας). Αυτή η μεθοδολογία επιχειρεί να μιμηθεί τη βιολογική ιδέα της [[γενετική διαφοροποίηση|γενετικής διαφοροποίησης]] και της [[φυσική επιλογή|φυσικής επιλογής]], των πυλώνων της εξέλιξης των ειδών, αλλά ουσιαστικώς η φυσική επιλογή αντικαθίσταται από μία τεχνητή επιλογή η οποία γίνεται μέσω της συνάρτησης καταλληλότητας. Η τελευταία αποτελεί και το υπέρτατο κριτήριο για την πραγματική απόδοση του αλγορίθμου.
== Πηγές ==
|