ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
Η Ρομποτική (Robotics) είναι από τους τομείς που παρουσιάζουν προβλήματα βελτιστοποίησης με ιδιαίτερες απαιτήσεις. Ειδικότερα, τα προβλήματα καθορισμού της κίνησης ενός ρομπότ (robot trajectory generation) είναι αρκετά πολύπλοκα, γιατί ανήκουν στην κατηγορία των διεργασιών, όπου η σειρά εφαρμογής των κανόνων (rules) είναι καθοριστική για την απόδοση. Οι παραδοσιακές μέθοδοι βελτιστοποίησης χρησιμοποιήθηκαν κατά κόρον για την παραγωγή ρομποτικής κίνησης, αλλά λόγω του τεράστιου και γεμάτου τοπικά ακρότατα χώρου αναζήτησης δεν κατόρθωσαν να ικανοποιήσουν πλήρως με τις επιδόσεις τους. Συνήθως, έχουν καλά αποτελέσματα σε περιπτώσεις όπου το μοντέλο, πάνω στο οποίο γίνεται η επεξεργασία, περιγράφεται με μεγάλη ακρίβεια ή όταν ο χώρος αναζήτησης δεν είναι πολύ μεγάλος.
Σ' ένα τέτοιο περιβάλλον, όπου οι αλληλοεξαρτήσεις των παραμέτρων δεν είναι γνωστές με ακρίβεια και ο αριθμός των βαθμών ελευθερίας του συστήματος είναι αρκετά μεγάλος, είναι φανερό ότι μια αυτοπροσαρμοζόμενη στρατηγική αναζήτησης, όπως ο Γ.Α. έχει αρκετές πιθανότητες επιτυχίας. Τα πλεονεκτήματα που προσφέρουν οι Γ.Α. καλύπτουν ικανοποιητικά τις ανάγκες των προβλημάτων αυτής της κατηγορίας, καθώς δεν απαιτείται ένα σαφές μοντέλο περιγραφής της συμπεριφοράς του προβλήματος, ενώ η ενδογενής παράλληλη επεξεργασία του Γ.Α. αποδεικνύεται κάτι παραπάνω από χρήσιμη σε ένα περιβάλλον μεγάλης πολυπλοκότητας.
O Yuval Davidor [17], ασχολούμενος διεξοδικά με προβλήματα ρομποτικής κίνησης, διατύπωσε μία ιδέα χρησιμοποίησης των Γ.Α. για τη βελτιστοποίηση του σχεδιασμού της τροχιάς που πρέπει να ακολουθήσει ένας ρομποτικός βραχίονας για την μετακίνησή του από ένα σημείο σε κάποιο άλλο. Η πρότασή του παρουσιάζει μερικά πρωτοποριακά στοιχεία για την εφαρμογή των Γ.Α., όπως μια νέα μορφή διασταύρωσης που βασίζεται στο φαινότυπο και όχι στη γενετική κωδικοποίηση.
Η μελέτη του Davidor αναπτύχθηκε πάνω σε ένα μοντέλο μηχανικού ρομποτικού βραχίονα. Ο βραχίονας αποτελείται από τρία τμήματα και τέσσερις συνδέσμους, ενώ στο τέλος του τελευταίου τμήματος υπάρχει η δαγκάνα (end-effecter) που αποτελεί και το λειτουργικό τμήμα του βραχίονα και η θέση της συγκεντρώνει το μεγαλύτερο ενδιαφέρον για το σχεδιασμό της κίνησης.
Μια συγκεκριμένη θέση του βραχίονα περιγράφεται από τις θέσεις των συνδέσεων (και πιο συγκεκριμένα από τις γωνίες που σχηματίζουν) και, αφού το μήκος των τμημάτων είναι γνωστό, είναι εύκολος ο υπολογισμός της θέσης της δαγκάνας.
Για την μετακίνηση της δαγκάνας μεταξύ δύο σημείων απαιτείται ο καθορισμός της κίνησης στις ενδιάμεσες θέσεις, που βεβαίως δεν είναι δυνατό να είναι άπειρες, γιατί είναι πεπερασμένοι οι πόροι που διατίθενται για τον προγραμματισμό της κίνησης. Έτσι, ο στόχος της βελτιστοποίησης σε αυτό το πρόβλημα είναι η εύρεση εκείνης της διαδρομής που επιτυγχάνει τον καλύτερο αριθμό και καλύτερο συνδυασμό των ενδιάμεσων θέσεων.
Ο υπολογισμός αυτός ίσως να μην φαίνεται εκ πρώτης όψεως δύσκολος, αλλά είναι πολλοί οι παράγοντες που πρέπει να ληφθούν υπ' όψη για τον προγραμματισμό μιας σωστής ακολουθίας κινήσεων, όπως δυναμικοί παράγοντες που οφείλονται στο υλικό.
Ο Γ.Α. που χρησιμοποίησε ο Davidor ξεφεύγει από το κλασσικό μοντέλο, γιατί αυτό δεν είναι ικανό να αντεπεξέλθει στις ανάγκες του προβλήματος. Μια πρώτη μετατροπή είναι η υιοθέτηση αναπαράστασης ατόμων μεταβλητού μήκους. Κάθε άτομο αναπαριστά μια διαφορετική τροχιά που δεν περιλαμβάνει πάντα τον ίδιο αριθμό ενδιάμεσων κινήσεων και άρα δεν είναι πρακτικό και αποδοτικό να έχει σταθερό μήκος. Η κωδικοποίηση της τροχιάς είναι της παρακάτω μορφής:
Όπως φαίνεται, κάθε
συμβολοσειρά αποτελεί μια παράθεση διαδοχικών θέσεων που η κάθε μία περιγράφεται
από ένα σύνολο τιμών για όλες τις
συνδέσεις (γωνίες) του βραχίονα. Έτσι, αν μια τροχιά
περιλαμβάνει
θέσεις, τότε η συμβολοσειρά που της αντιστοιχεί αποτελείται
από
-άδες. Είναι σημαντικό να τονιστεί ότι η σειρά των θέσεων μέσα
στη συμβολοσειρά παίζει πολύ μεγάλο ρόλο και είναι απολύτως καθοριστική για την
μορφή της τροχιάς.
Η αναπαράσταση αυτή είναι φυσικό ότι απαιτεί τροποποίηση των λειτουργιών του Γ.Α. και κυρίως της διασταύρωσης. Το κύριο πρόβλημα που προκύπτει εδώ είναι πώς θα εξασφαλιστεί ότι τα νέα άτομα που θα παραχθούν από το ζευγάρωμα των παλιών θα έχουν νόημα μέσα στα πλαίσια του αλγορίθμου και δεν θα αποτελούν τετριμμένες ή ακραίες περιπτώσεις τροχιών.
Η λύση δόθηκε με την επινόηση μιας πρωτότυπης μορφής διασταύρωσης που καθιερώθηκε με το όνομα Ανάλογη Διασταύρωση (Analogous Crossover) [16]. Στην ανάλογη διασταύρωση, όλη η λειτουργία του ζευγαρώματος γίνεται με βάση το φαινότυπο των ατόμων. Πιο συγκεκριμένα, τα σημεία κοπής δεν καθορίζονται με τυχαίο τρόπο, αλλά επιλέγονται τα σημεία τομής των διαδρομών που διαγράφουν οι δαγκάνες. Αυτό γίνεται πιο εύκολα αντιληπτό από το Σχήμα 6.3.
Σχήμα 6.3: Ανάλογη Διασταύρωση
Είναι φανερό ότι τα σημεία τομής αποτελούν καλές επιλογές για τη διασταύρωση, γιατί κατ' αυτόν το τρόπο γίνεται ένας λογικός και οικονομικός (μέσα στα πλαίσια του Γ.Α.) συνδυασμός των δύο γονέων. Πλέον, δεν υπάρχει κίνδυνος να προκύψουν απόγονοι που, ναι μεν θα διατηρούν γενετικά χαρακτηριστικά των γονέων, αλλά θα αντιστοιχούν σε παράδοξες διαδρομές. Αν στους φαινοτύπους των γονέων δεν υπάρχουν σημεία τομής, τότε επιλέγονται τα πλησιέστερα δυνατά σημεία. Αυτή η απλότητα στη λειτουργία της ανάλογης διασταύρωσης έχει ως αντίβαρο κάποια μειονεκτήματα. Αρχικά, το να βασίζεται η διασταύρωση σε φαινοτυπικά χαρακτηριστικά είναι κάτι που έχει υπολογιστικό και φυσικά χρονικό κόστος. Αφ’ ετέρου, τα σημεία τομής είναι πιθανό να αντιστοιχούν σε σημεία εντός μιας θέσης στην κωδικοποιημένη συμβολοσειρά, κάτι που είναι ανεπιθύμητο, γιατί παράγει μη νόμιμα άτομα.
Έτσι, η ανάλογη διασταύρωση υφίσταται κάποιες τροποποιήσεις, προκειμένου να εξαλειφθούν αυτά τα μειονεκτήματα και, τελικά η νέα της μορφή ονομάζεται Διασταύρωση Μεταχωρισμού (Segregation Crossover), που εφαρμόζεται με τα εξής βήματα:
1) Επιλέγονται δύο συμβολοσειρές.
2)
Επιλέγεται τυχαία μια -άδα μέσα σε μια από τις δύο συμβολοσειρές.
3)
Σαρώνεται η άλλη συμβολοσειρά από το ένα άκρο ως το άλλο μέχρι να βρεθεί
μια -άδα του που μοιάζει γενετικά περισσότερο στην επιλεγμένη
-άδα. Το σημείο ακριβώς μετά από αυτήν την
-άδα θα είναι το σημείο κοπής.
4) Επανάληψη των βημάτων 1 και 2 για την επιλογή δεύτερου σημείου κοπής.
5) Εκτέλεση της διασταύρωσης με ανταλλαγή των αντίστοιχων μερών κατά τα γνωστά.
Ο σχεδιασμός της μετάλλαξης έγινε λαμβάνοντας υπ’ όψη την αναπαράσταση και η εφαρμογή της αφορά σε αλλαγές στα μήκη των συμβολοσειρών. Χρησιμοποιήθηκαν δύο μορφές μετάλλαξης:
·
Μετάλλαξη Πρόσθεσης (Addition Mutation):
Δημιουργείται ένα πιστό αντίγραφο μιας
-άδας που επιλέχθηκε με τυχαίο τρόπο και τοποθετείται
γειτονικά με το πρωτότυπό της. Ως αποτέλεσμα αυξάνεται το μήκος της
συμβολοσειράς.
·
Μετάλλαξη Απαλοιφής (Deletion Mutation): Απαλείφεται
μια -άδα, πάλι τυχαία επιλεγμένη, με άμεση συνέπεια τη μείωση του
μήκους της συμβολοσειράς.
Όσον αφορά τα αποτελέσματα, ο
Γ.Α. έδειξε την υπεροχή του σε σύγκριση με άλλες τεχνικές. Το πρόβλημα που
τέθηκε αφορούσε την εύρεση της βέλτιστης τροχιάς για την μετακίνηση ενός
βραχίονα μήκους μέτρων της μορφής του σχήματος παραπάνω. Το μέγεθος του χώρου
αναζήτησης αυτού του προβλήματος είναι της τάξεως
. Το μέγεθος του πληθυσμού καθορίστηκε στον αριθμό
. Ο Γ.Α. συναγωνίστηκε με επιτυχία δύο κλασσικές τεχνικές: το
τυχαίο ψάξιμο και το hill-climbing.