ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ

 

5.6     Παραλλαγες στη Διασταυρωση

 

Ο ρόλος της διασταύρωσης στην αναπαραγωγική διαδικασία επισημάνθηκε σε προηγούμενο κεφάλαιο. Η πιο στοιχειώδης μορφή διασταύρωσης, με την οποία απαντάται και στη φύση, είναι η διασταύρωση μονού σημείου (single-point crossover) όπως φαίνεται στο σχήμα 5.2.

 

Σχήμα 5.2: Ο ένας από τους δύο απόγονους που δημιουργούνται από διασταύρωση μονού σημείου

 

 Ωστόσο, παρ’ όλη την αποτελεσματικότητά της, έχει κάποια μειονεκτήματα που της στερούν τη δυνατότητα μεγαλύτερης απόδοσης. Το κυριότερο είναι η αδυναμία της να συνδυάζει συγκεκριμένα σχήματα υψηλής απόδοσης λόγω του τρόπου λειτουργίας της. Για παράδειγμα [19], έστω οι επόμενες δύο συμβολοσειρές:

 

 

και
.

 

Τα δυαδικά ψηφία που είναι υπογραμμισμένα θεωρείται ότι αποτελούν σχήματα πολύ υψηλής ικανότητας. Η συνεύρεση των δύο σχημάτων σε μια συμβολοσειρά είναι κάτι παραπάνω από επιθυμητή, ώστε να προκύψει σχήμα ακόμη πιο ικανό. Κάτι τέτοιο όμως, είναι αδύνατο να επιτευχθεί μέσω της διασταύρωσης μονού σημείου και όχι μόνο αυτό, αλλά είναι σίγουρο ότι ένα από τα δύο σχήματα θα καταστραφεί και οι πολύτιμες πληροφορίες του θα χαθούν.

 

Λύση σε αυτό το πρόβλημα έρχεται να δώσει η διασταύρωση διπλού σημείου (two-point crossover) όπως φαίνεται στο σχήμα 5.3Α, που παρουσιάστηκε για πρώτη φορά στη διδακτορική εργασία του Cavicchio το 1970. Η λειτουργία της είναι απλή και στην ουσία,

Σχήμα 5.3Α: Ο ένας από τους δύο απόγονους που δημιουργούνται από διασταύρωση διπλού σημείου

 

όπως εύκολα μαντεύει κανείς, πρόκειται για διαδοχική εφαρμογή της διασταύρωσης μονού σημείου δύο φορές. Επιλέγονται με τυχαίο τρόπο δύο θέσεις που θα αποτελέσουν τα σημεία κοπής και γίνεται ανταλλαγή του γενετικού υλικού που υπάρχει ανάμεσά τους.

 

Με τη διασταύρωση διπλού σημείου είναι δυνατός ο συνδυασμός των δύο σχημάτων του παραδείγματος σε ένα. Στο Σχήμα 5.3Β φαίνεται η λειτουργία της διασταύρωσης διπλού σημείου με διαδοχική εφαρμογή σε δύο βήματα της διασταύρωσης μονού σημείου στα σημεία κοπής 4 και 10.

Βήμα 1: Σημείο κοπής = 4.                                                          γονείς  και

 

 

ενδιάμεσα παιδιά  και

Βήμα 2: Σημείο κοπής = 10.                                                Ενδιάμεσα παιδιά και

 

παιδιά  και

Σχήμα 5.3Β: Διασταύρωση διπλού σημείου.

 

Το πρώτο από τα τελικά παιδιά λαμβάνει και τα δύο σχήματα και πλέον είναι πολύ ικανό άτομο.

 

Από εκεί και πέρα, δοκιμάστηκαν σε διάφορες μελέτες και άλλες πιο περίπλοκες διασταυρώσεις με περισσότερα σημεία κοπής. Στη διδακτορική εργασία του De Jong παρουσιάζεται μια παραμετροποιημένη μορφή διασταύρωσης με το όνομα γενικευμένη διασταύρωση (generalized crossover). Σε αυτήν, ο αριθμός των σημείων κοπής καθορίζεται από τον χρήστη. Αν ο αριθμός είναι ζυγός, τότε η συμβολοσειρά παίρνει την μορφή δακτυλιδιού ενώνοντας το τέλος με την αρχή της. Η ανταλλαγή του γενετικού υλικού γίνεται εναλλάξ ανάμεσα στα σημεία κοπής.

 

Σε περίπτωση που ο αριθμός των σημείων κοπής είναι μονός, τότε γίνεται, κατά τα γνωστά, ισάριθμες φορές διασταύρωση απλού σημείου.

Τα πολλά σημεία κοπής στη διασταύρωση, όπως παρατηρεί ο De Jong, είναι καλό να αποφεύγονται διότι ανακατεύουν το γενετικό υλικό και αυξάνουν τις πιθανότητες να χαθούν χρήσιμες πληροφορίες, κάτι που είναι εις βάρος της απόδοσης.

 

Παρ’ όλο που η διασταύρωση διπλού (ή πολλαπλού) σημείου είναι πιο αποτελεσματική στην παραγωγή αποδοτικών σχημάτων, υπάρχουν περιπτώσεις στις οποίες δεν έχει ικανοποιητική επίδοση. Έτσι, οι ερευνητές στράφηκαν σε άλλες λύσεις, από τις οποίες η πιο σημαντική είναι η ομοιόμορφη διασταύρωση (uniform crossover) όπως φαίνεται στο σχήμα 5.4.

 

Σχήμα 5.4: Ο ένας από τους δύο απόγονους που δημιουργούνται από ομοιόμορφη διασταύρωση

 

 Σύμφωνα με αυτήν, δύο συμβολοσειρές-γονείς λαμβάνουν μέρος σε μια διαδικασία ανταλλαγής γενετικού υλικού από την οποία προκύπτουν δύο παιδιά. Η διαδικασία λαμβάνει χώρα με βάση μια συμβολοσειρά-φόρμα (template) που, αναλόγως με την τιμή του δυαδικού ψηφίου της κάθε θέσης, καθορίζει για κάθε παιδί το γονέα από τον οποίο θα προέλθει το γενετικό υλικό για τη συγκεκριμένη θέση. Για παράδειγμα, έστω οι ακόλουθοι γονείς και η παρακάτω φόρμα:

 

γονέας ,
γονέας

και
φόρμα .

 

Τα παιδιά που προκύπτουν από την εφαρμογή της ομοιόμορφης διασταύρωσης είναι:

 


Η φόρμα επιλέγεται με τυχαίο τρόπο. Η τιμή του δυαδικού ψηφίου της κάθε θέσης της, προσδιορίζει το γονέα από τον οποίο θα προέλθει το δυαδικό ψηφίο για το παιδί. Όταν το δυαδικό ψηφίο της φόρμας είναι 1, τότε το πρώτο παιδί παίρνει την αντίστοιχη τιμή του γονέα 1, ενώ όταν είναι 0 παίρνει την τιμή του γονέα 0. Το δεύτερο παιδί παίρνει το δυαδικό ψηφίο του άλλου γονέα κάθε φορά.

 

Όλες οι παραπάνω μορφές διασταύρωσης επινοήθηκαν με βάση τη δυαδική κωδικοποίηση. Ωστόσο, σε περιπτώσεις πραγματικής και κωδικοποίησης ταξινομημένης λίστας, προκύπτει η ανάγκη επαναπροσδιορισμού της διασταύρωσης λόγω της διαφορετικής φύσης των ατόμων.

 

Στην πραγματική κωδικοποίηση ουσιαστικά δεν υπάρχει πρόβλημα εφαρμογής της διασταύρωσης μονού σημείου ή της ομοιόμορφης, όπως περιγράφηκαν παραπάνω, γι' αυτό και υλοποιήθηκαν πολλά συστήματα με αυτόν τον τρόπο. Όμως, οι έρευνες οδήγησαν σε μια νέα μορφή διασταύρωσης που εκμεταλλεύεται το γεγονός της αριθμητικής αναπαράστασης των ατόμων: τη διασταύρωση μέσου όρου (average ή arithmetic crossover). Η διασταύρωση μέσου όρου ενεργεί πάνω σε δυο γονείς και παράγει ένα νέο άτομο, που είναι το αποτέλεσμα υπολογισμού του αριθμητικού μέσου όρου των γονέων του. Μερικές φορές μάλιστα, οι δυο γονείς δεν μετέχουν ισότιμα, αλλά με βάρη στον υπολογισμό. Είναι επίσης δυνατό να γίνει συνδυασμός της διασταύρωσης μέσου όρου με τις κλασσικές μορφές, αναλόγως με την περίπτωση του προβλήματος. Ο πειρασμός και η φαντασία μπορούν να οδηγήσουν σε πολύ καλά αποτελέσματα μερικές φορές. Πάντως, για την πραγματική κωδικοποίηση η διασταύρωση μέσου όρου δουλεύει πολύ καλά, πέρα από το γεγονός ότι ταιριάζει διαισθητικά με την μορφή των ατόμων, και είναι αρκετά δημοφιλής στις εφαρμογές.

 

Στην κωδικοποίηση ταξινομημένης λίστας το κύριο πρόβλημα με τις βασικές μορφές διασταύρωσης είναι η παραγωγή μη "νόμιμων" παιδιών, δηλαδή λύσεων που δεν έχουν νόημα στα πλαίσια του αλγορίθμου (π.χ. διπλή παρουσία ενός κόμβου στο TSP). Για την περίπτωση αυτή επινοήθηκε μια διασταύρωση που η λειτουργία της θυμίζει έντονα την ομοιόμορφη διασταύρωση, γι' αυτό και της δόθηκε το όνομα ομοιόμορφη διασταύρωση ταξινομημένης λίστας (uniform order-based list crossover). Στόχος της είναι να διατηρήσει σε κάθε παιδί της επόμενης γενιάς μέρος του ενός γονέα και να ενσωματώσει σε αυτό πληροφορίες από τον άλλο. Σημασία έχει να διατηρηθεί η διάταξη των κωδικοποιημένων συμβόλων του κάθε γονέα στα παιδιά και όχι η ακριβής θέση τους. Για παράδειγμα [19], ας δούμε την λειτουργία της τακτικής ομοιόμορφης διασταύρωσης στο TSP με 8 πόλεις. Έστω δύο τυχαία επιλεγμένες συμβολοσειρές που παριστάνουν μια πιθανή σειρά επισκέψεων των πόλεων, οι οποίες αριθμούνται από το 1 έως το 8:

 

γονέας
γονέας

Και εδώ (όπως και στην απλή ομοιόμορφη διασταύρωση), καταλυτικό ρόλο παίζει μια συμβολοσειρά-φόρμα, που είναι αυστηρά δυαδική και δεν έχει καμία σχέση με την κωδικοποίηση. Η φόρμα αυτή καθορίζει το γονέα από τον οποίο κάθε παιδί θα λάβει γενετικό υλικό. Έστω στο παράδειγμά μας, ότι έχουμε την εξής φόρμα:

.

Η όλη λειτουργία γίνεται σε δύο βήματα:

1)        Στο πρώτο βήμα κάθε παιδί παίρνει υλικό από τον γονέα που του υποδεικνύει η φόρμα. Στην περίπτωση του παραδείγματος, όταν το δυαδικό ψηφίο της φόρμας είναι 0, τότε το πρώτο παιδί παίρνει το αντίστοιχο δυαδικό ψηφίο του γονέα-0, αλλιώς παίρνει μια παύλα, που, προς το παρόν, σημαίνει ότι δε λαμβάνει τιμή. Αν το δυαδικό ψηφίο της φόρμας είναι 1, τότε το δεύτερο παιδί παίρνει το αντίστοιχο δυαδικό ψηφίο του γονέα-1, διαφορετικά στη θέση σημειώνεται παύλα. Δηλαδή, στα πλαίσια του παραδείγματος, τα ενδιάμεσα παιδιά είναι:


  

2)        Στο δεύτερο βήμα ενσωματώνονται σε κάθε παιδί πληροφορίες από τον άλλο γονέα αντίστοιχα. Οι κενές θέσεις συμπληρώνονται με τις πόλεις που λείπουν από κάθε παιδί, αλλά όχι με τυχαίο τρόπο: η σειρά τους συμπίπτει με την σειρά εμφάνισής τους στον άλλο γονέα. Δηλαδή, για το πρώτο παιδί, μετά το πρώτο βήμα του λείπουν 4 πόλεις, οι 2,3,5 και 6. Το πώς θα μοιραστούν αυτές οι πόλεις στις θέσεις που έχουν παύλα το καθορίζει ο γονέας 1. Η σχετική σειρά εμφάνισής τους πρέπει να συμπίπτει με αυτή του γονέα 1. Εκεί πρώτα εμφανίζεται το 6, έπειτα το 2 και μετά το 5 και το 3. Έτσι οι κενές θέσεις του πρώτου παιδιού συμπληρώνονται με αυτή τη σειρά. Ανάλογα εκτελείται η διαδικασία και για το άλλο παιδί, όποτε έχουμε:


.

Στην περίπτωση της δενδρικής αναπαράστασης ο κυριότερος τελεστής διασταύρωσης που μπορούμε να εφαρμόσουμε είναι αυτός που περιγράφεται στο σχήμα 5.5.

 

Το θέμα των παραλλαγών της διασταύρωσης δεν εξαντλείται πλήρως σε αυτή την παράγραφο, όπου παρουσιάστηκαν οι πιο συνηθισμένες και δοκιμασμένες μορφές. Οι Γ.Α. με τη μεγάλη ευελιξία που παρέχουν δίνουν την δυνατότητα στο σχεδιαστή να προσαρμόσει τη διασταύρωση, όπως και κάθε άλλη λειτουργία τους, στις ανάγκες και τη φύση του κάθε προβλήματος. Η προσαρμογή αυτή μπορεί να αφορά σε απλές αλλαγές των παραμέτρων της λειτουργίας (π.χ. μεταβολή της πιθανότητας πραγματοποίησης), μέχρι ριζική τροποποίηση της δομής της, όμως πάντα μέσα στα πλαίσια των στόχων και της φιλοσοφίας της. Στο Κεφάλαιο 6, όπου παρουσιάζονται διάφορες εφαρμογές των Γ.Α., παρατίθενται άλλες περιπτώσεις διασταυρώσεων που δεν έχουν εξεταστεί εδώ και δίνουν πολύ ικανοποιητικά αποτελέσματα. Επίσης, τίποτα δεν αποκλείει την εμφάνιση νέων μορφών, αφού είναι σε εξέλιξη μεγάλος αριθμός ερευνητικών προσπαθειών και εφαρμογών στο χώρο.

 

Σχήμα 5.5: Ο ένας από τους δύο απόγονους που δημιουργούνται από δενδρική διασταύρωση

 

 

ΑΡΧΗ ΚΕΦΑΛΑΙΟΥ