ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
2.5 Το προβλημα του Πλανοδιου Πωλητη
Στην ενότητα αυτή θα παρουσιαστεί μια προσέγγιση του προβλήματος του Πλανόδιου Πωλητή (Traveling Salesman Problem, TSP) με χρήση Γ.Α. Για λόγους απλότητας θα γίνει αναφορά σε μία μόνο πιθανή προσέγγιση.
Δεδομένων των εξόδων μεταφοράς μεταξύ των διαφόρων πόλεων, το TSP συνίσταται στην προσπάθεια του πλανόδιου πωλητή να επισκεφτεί όλες τις πόλεις της περιοχής του, μία μόνο φορά την καθεμιά, και να επιστρέψει στην πόλη από την οποία ξεκίνησε με το ελάχιστο δυνατό κόστος.
Το TSP ανήκει στην κατηγορία των συνδυαστικών προβλημάτων βελτιστοποίησης και εμφανίζεται σε ένα πολύ μεγάλο αριθμό εφαρμογών. Υπάρχουν αρκετοί προσεγγιστικοί και ευρετικοί αλγόριθμοι που προσπαθούν να επιλύσουν το πρόβλημα, ενώ τα τελευταία χρόνια έχουν γίνει αρκετές προσπάθειες για να προσεγγιστεί το TSP με χρήση Γ.Α. Παρακάτω παρουσιάζεται μία από αυτές τις προσπάθειες προσέγγισης [29, σελίδες 166-179].
Το πρώτο βασικό ερώτημα που
πρέπει να απαντηθεί είναι αυτό σχετικά με τον τρόπο αναπαράστασης του
χρωμοσώματος που θα αναπαριστά τις πιθανές λύσεις. Μπορεί να είναι είτε ένας
πίνακας ακεραίων είτε μια δυαδική συμβολοσειρά. Στα προηγούμενα παραδείγματα η
αναπαράσταση που χρησιμοποιήθηκε ήταν η δυαδική συμβολοσειρά. Αυτό έγινε, διότι
με αυτόν τον τρόπο ήταν δυνατή η χρήση δυαδικής μετάλλαξης και δυαδικής
διασταύρωσης, δυαδικών τελεστών δηλαδή, που παρήγαγαν καινούρια χρωμοσώματα
εντός του επιτρεπτού διαστήματος τιμών. Η αναπαράσταση αυτή, όμως, δεν
ανταποκρίνεται στις απαιτήσεις του συγκεκριμένου προβλήματος του Πλανόδιου
Πωλητή. Κι αυτό γιατί σε μια δυαδική αναπαράσταση για ένα TSP
πόλεων, κάθε πόλη θα έπρεπε να αναπαρασταθεί ως μια δυαδική
συμβολοσειρά
δυαδικών ψηφίων. Αυτό σημαίνει ότι το χρωμόσωμα θα κατέληγε
να αποτελείται από
δυαδικά ψηφία. Κατά τη διαδικασία της μετάλλαξης θα μπορούσε
να εμφανιστεί πρόβλημα, όταν θα δημιουργούταν ακολουθία πόλεων, στην οποία μία
τουλάχιστον πόλη θα εμφανιζόταν παραπάνω από μία φορά. Επιπλέον, για ένα TSP με
πόλεις (όπου για την αναπαράσταση κάθε πόλης θα
χρειαζόντουσαν
δυαδικά ψηφία), μερικές ακολουθίες των
δυαδικών ψηφίων (π.χ. η
) δεν θα αντιστοιχούν σε καμία πόλη. Παρόμοια προβλήματα
μπορεί να εμφανιστούν και κατά την εφαρμογή των τελεστών διασταύρωσης. Απ' όλ'
αυτά συμπεραίνει κανείς, ότι εάν γινόταν χρήση των τελεστών μετάλλαξης και
διασταύρωσης, όπως αυτοί ορίσθηκαν στα προηγούμενα παραδείγματα, θα ήταν
απαραίτητη η ύπαρξη ενός διορθωτικού αλγορίθμου. Ένας τέτοιος αλγόριθμος
(διορθωτικός κανόνας) θα επιδιόρθωνε κάθε χρωμόσωμα μεταφέροντάς το μέσα στο
επιτρεπτό σύνολο τιμών.
Φαίνεται λοιπόν από τα
παραπάνω, ότι η αναπαράσταση με διάνυσμα ακεραίων αποτελεί καλύτερη επιλογή. Κι
αυτό γιατί μ' αυτό τον τρόπο, αντί να εφαρμόζονται διορθωτικοί κανόνες μετά από
τη χρήση των γενετικών τελεστών, μπορούν να ενσωματωθούν η γνώση και οι
πληροφορίες που έχουμε για το συγκεκριμένο πρόβλημα από πριν στους τελεστές
αυτούς. Έτσι, θα απομακρυνόταν με έξυπνο τρόπο ο κίνδυνος για παραγωγή ατόμων
εκτός των ορίων του διαστήματος τιμών. Στη συγκεκριμένη προσέγγιση
χρησιμοποιείται αναπαράσταση με ακέραιους αριθμούς. Ένα διάνυσμα
της μορφής
αντιστοιχεί σε μια διαδρομή από την πόλη
στην
, από την
στην
, κ.τ.λ., από την
στην
και πίσω ξανά στην
. Το
αποτελεί μια διάταξη των
.
Για τη διαδικασία
αρχικοποίησης μπορούμε, είτε να χρησιμοποιήσουμε ευρετικές μεθόδους (π.χ.
δεχόμαστε μερικά αποτελέσματα από ένα άπληστο (greedy) αλγόριθμο για το TSP,
ξεκινώντας κάθε φορά από διαφορετική πόλη), είτε να αρχικοποιήσουμε τον πληθυσμό
με τυχαία δείγματα από ανακατατάξεις του
.
Η αποτίμηση των χρωμοσωμάτων γίνεται με άμεσο και ευθύ τρόπο: δεδομένων των εξόδων μεταφοράς μεταξύ των διαφόρων πόλεων, μπορούμε εύκολα να υπολογίσουμε το συνολικό κόστος ολόκληρης της διαδρομής.
Το ζητούμενο σε ένα TSP είναι η εύρεση της διαδρομής με την βέλτιστη διάταξη των πόλεων. Είναι σχετικά εύκολο να δημιουργήσουμε μοναδιαίους τελεστές που θα ψάχνουν για καλύτερες διατάξεις συμβολοσειρών. Παρ' όλ' αυτά, με τη χρήση μόνο μοναδιαίων τελεστών είναι εξαιρετικά δύσκολο να βρεθούν σχετικά καλές διατάξεις, πόσο μάλλον να βρεθεί η βέλτιστη. Επιπλέον, η δύναμη και η αποτελεσματικότητα των Γ.Α. πηγάζουν από την εναλλαγή της πληροφορίας που επιτυγχάνεται με τη βοήθεια των συνδυασμένων διασταυρώσεων των ατόμων με την καλύτερη απόδοση. Έτσι, αυτό που απαιτείται είναι ένας τελεστής διασταύρωσης που θα εκμεταλλεύεται όσο το δυνατόν καλύτερα τις σημαντικές ομοιότητες μεταξύ των χρωμοσωμάτων. Γι' αυτό το λόγο, χρησιμοποιείται μια παραλλαγή ενός OX τελεστή [18], ο οποίος δεδομένων δύο χρωμοσωμάτων γονιών δημιουργεί ένα χρωμόσωμα απόγονο επιλέγοντας μια ακολουθία πόλεων από τον ένα γονιό και συμπληρώνοντας τις υπόλοιπες πόλεις από τον άλλο. Για παράδειγμα, εάν οι γονείς είναι οι:
και
και η επιλεγμένη ακολουθία είναι η:
τότε ο απόγονος που δημιουργείται είναι ο:
.
Όπως απαιτείται, η δομή του
απόγονου εξαρτάται από τη δομή των γονιών του. Οι γονείς μπορούν στη συνέχεια να
χρησιμοποιηθούν με αντεστραμμένους ρόλους για τη δημιουργία και άλλου απόγονου,
από το ίδιο ζευγάρι γονιών, διαφορετικού εντελώς από τον πρώτο. Ένας Γ.Α.
βασισμένος στον παραπάνω τελεστή διασταύρωσης εκτελεί φυσικά τυχαίο ψάξιμο,
αφήνει όμως σημαντικά περιθώρια βελτίωσης. Αυτός ο Γ.Α. για
τυχαία δημιουργημένες πόλεις έδωσε, μετά από
γενιές, για ολόκληρη τη διαδρομή μεταξύ των πόλεων,
πάνω από τη βέλτιστη αναμενόμενη τιμή.