ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
Η δυαδική κωδικοποίηση που χρησιμοποιήθηκε στο βασικό σχήμα των Γ.Α., αν και αρκετά ευέλικτη, δεν είναι μοναδική και κατάλληλη για όλες τις περιπτώσεις προβλημάτων. Η έρευνα και ο προγραμματισμός έχουν οδηγήσει και σε άλλες τεχνικές κωδικοποίησης (π.χ. πραγματική) που αποδεικνύονται αποδοτικές για ορισμένους τύπους προβλημάτων. Στο προηγούμενο κεφάλαιο επισημάνθηκε η ανάγκη η κωδικοποίηση να γίνεται με τέτοιο τρόπο, ώστε να προκύπτουν ομοιότητες ανάμεσα στα άτομα και να βρίσκει εφαρμογή το Συμπέρασμα των Σχημάτων. Όμως, πολλά πεδία εφαρμογής των Γ.Α., όπως η βελτιστοποίηση μηχανικού σχεδιασμού (engineering design optimization) ή η συνδυαστική βελτιστοποίηση (combinatorial optimization) επιβάλουν από τη φύση τους διαφορετικές κωδικοποιήσεις.
Μέσα από το πλήθος και την ποικιλία των κωδικοποιήσεων που έχουν προταθεί, ξεχωρίζουν δύο κανόνες-αρχές, που αποτελούν καλούς οδηγούς για την κατασκευή μιας επιτυχημένης κωδικοποίησης:
1) Η αρχή της Σημασίας των Δομικών Φορμών (Meaningful Building Blocks principle)
και
2) Η αρχή του Ελάχιστου Αλφάβητου (Minimal Alphabet principle).
H αρχή της Σημασίας των Δομικών Φορμών συνοψίζεται ως εξής: Κύριος στόχος της κωδικοποίησης πρέπει να είναι οι ομοιότητες ανάμεσα σε άτομα μέσα στο περιβάλλον του προβλήματος να συνεπάγονται παραπλήσιες επιδόσεις. Βασικός εκφραστής αυτής της τάσης είναι η δυαδική κωδικοποίηση που είναι και η επικρατέστερη γενικά στους Γ.Α. Η ύπαρξη ομοιοτήτων και κατά συνέπεια δομικών φορμών είναι το χαρακτηριστικό πάνω στο οποίο οικοδομείται όλη η φιλοσοφία της αρχής. Η θεωρία των σχημάτων και, βεβαίως το θεμελιώδες συμπέρασμα των Γ.Α., αναπτύχθηκε με κωδικοποιήσεις αυτής της κατηγορίας. Πάντως, αν κάποιος επιθυμεί να αξιοποιήσει τα πλεονεκτήματα της θεωρίας των σχημάτων και επιλέξει κωδικοποίηση που κατ' εξοχήν την υποστηρίζει, οφείλει να γνωρίζει ότι πέρα από την δυαδική, οποιαδήποτε άλλη κωδικοποίηση απαιτεί συνήθως φαντασία και λίγη "τέχνη" από τον εμπνευστή της για να αποδειχτεί επιτυχημένη.
Στην αρχή του Ελάχιστου Αλφάβητου κύριο μέλημα, όπως εύκολα γίνεται αντιληπτό, είναι η υιοθέτηση του μικρότερου δυνατού αλφάβητου. Αυτό οδηγεί πιο εύκολα σε ανάδειξη των ιδιαίτερων χαρακτηριστικών των δυαδικών συμβολοσειρών και καλύτερη εκμετάλλευση των ομοιοτήτων τους. Το ελάχιστο αλφάβητο που μπορεί να υπάρξει είναι το δυαδικό, επομένως για άλλη μια φορά επιβεβαιώνεται η μεγάλη αξία της δυαδικής κωδικοποίησης. Είναι εύκολο να δειχθεί με μαθηματικό τρόπο, ότι με το δυαδικό αλφάβητο επιτυγχάνεται ο μέγιστος αριθμός σχημάτων ανά δυαδικό ψηφίο ανεξάρτητα με τις όποιες επιμέρους σχεδιαστικές λεπτομέρειες της κωδικοποίησης, που μπορεί να υπάρχουν.
Εξετάζοντας άλλες μορφές κωδικοποίησης που χρησιμοποιούνται συχνά θα ήταν παράλειψη να μην αναφερθούν η πραγματική (real), κωδικοποίηση ταξινομημένης λίστας (ordinal ή order-based list) και η δενδρική κωδικοποίηση (tree).
Η πρώτη χρησιμοποιείται περισσότερο στο μηχανικό σχεδιασμό (engineering design), κάνοντας μ' αυτό τον τρόπο πιο κατανοητό και ελκυστικό το Γ.Α. στους μηχανικούς-χρήστες. Η κωδικοποίηση συνίσταται στη χρησιμοποίηση ενός αριθμού πραγματικών παραμέτρων που περιγράφουν τις διάφορες σχεδιαστικές επιλογές. Σημαντικό πλεονέκτημα είναι ότι έχει καλύτερη απόδοση σε περιπτώσεις που ο χώρος αναζήτησης είναι τεράστιος και η δυαδική κωδικοποίηση δεν παράγει ικανοποιητικά αποτελέσματα. Λόγω της απλότητας που τη χαρακτηρίζει επιτρέπει με μεγαλύτερη άνεση συμμετοχή του αλγόριθμου σε υβριδικά σχήματα. Με την πραγματική κωδικοποίηση, το βήμα της αποκωδικοποίησης στο βασικό σχήμα του αλγορίθμου δεν είναι πλέον απαραίτητο και παραλείπεται.
Η κωδικοποίηση ταξινομημένης λίστας βρίσκει μεγάλο πεδίο εφαρμογής στα συνδυαστικά προβλήματα (π.χ. Travelling Salesman Problem, Graph Colouring Problem, κ.τ.λ.), των οποίων η φύση απαγορεύει τις προηγούμενες κωδικοποιήσεις. Κάθε πιθανή λύση αναπαρίσταται με διατάξεις κόμβων που περιγράφουν πλήρως τον τρόπο επίλυσης (π.χ. για το TSP με τρεις πόλεις μια πιθανή λύση θα μπορούσε να είναι η ΑΒΓ, δηλώνοντας ότι η σειρά επίσκεψης των πόλεων πρέπει να είναι: πρώτη η Α, δεύτερη η Β και τρίτη η Γ). Ιδιαίτερη προσοχή πρέπει να δοθεί στις άλλες λειτουργίες του Γ.Α. (διασταύρωση, μετάλλαξη) που πλέον δε μπορούν να δράσουν με τη γνωστή τους μορφή και πρέπει να προσαρμοστούν στα δεδομένα της κωδικοποίησης (έχουν γίνει πολλές προτάσεις για το συγκεκριμένο θέμα).
Μεγάλο ενδιαφέρον για την Τεχνητή Νοημοσύνη παρουσιάζουν κωδικοποιήσεις στις οποίες τα άτομα είναι Νευρωνικά Δίκτυα [19].
Ένα άλλο αρκετά διαδεδομένο είδος κωδικοποίησης είναι η δενδρική κωδικοποίηση όπως φαίνεται στο σχήμα 5.1, όπου αναπαρίσταται η σχέση x + 5 / y σε postfix μορφή.
Σχήμα 5.1: Δενδρική κωδικοποίηση της σχέσης x + 5 / y σε postfix μορφή.
Πάντως, γενικά αν σε κάποιο πρόβλημα δεν είναι προφανές το είδος της κωδικοποίησης και γίνει μια κακή επιλογή δε σημαίνει ότι ο αλγόριθμος θα οδηγηθεί οπωσδήποτε σε αποτυχία. Οι Γ.Α. είναι από τη φύση τους αρκετά εύρωστοι, αντέχουν σε αλλαγές και "συγχωρούν" λάθη που δε ξεφεύγουν κατά πολύ από τα όριά τους. Επιπλέον, έχουν το πλεονέκτημα της χωρίς ιδιαίτερο κόπο αλλαγής της κωδικοποίησης.
Σε περιπτώσεις που οι μεταβλητές του προβλήματος είναι παραπάνω από μία εφαρμόζεται συνένωση (concatenation) τους σε μια συμβολοσειρά. Όμως, το ποια ακριβώς θα είναι η θέση κάθε μεταβλητής μέσα στη συμβολοσειρά είναι ένα θέμα που απαιτεί ιδιαίτερη προσοχή. Το είδος των αλληλεπιδράσεων ανάμεσα στις μεταβλητές παίζει σημαντικό ρόλο: Αν οι μεταβλητές είναι γραμμικά ανεξάρτητες δεν ενδιαφέρει η σχετική θέση τους μέσα στη συμβολοσειρά. Αν όμως υπάρχει εξάρτηση, τότε είναι καλύτερα να τοποθετούνται οι ανεξάρτητες μεταβλητές κοντά η μία στην άλλη, ώστε να είναι σε θέση ο Γ.Α. να ανακαλύψει τις δομικές φόρμες και κατά συνέπεια να αναδείξει τα καλύτερα άτομα. Αυτό γίνεται πιο εύκολα αντιληπτό αν σκεφτεί κανείς ότι η διασταύρωση θα χώριζε με μεγαλύτερες πιθανότητες μεταβλητές που απέχουν αρκετά μέσα στην δομή της συμβολοσειράς [10].
Άλλη μια αρκετά συνηθισμένη
πρακτική είναι η αντιστοίχηση (mapping) των κωδικοποιημένων τιμών στο πεδίο
ορισμού της υπό εξέταση συνάρτησης. Για παράδειγμα, αν ζητείται το μέγιστο
κάποιας συνάρτησης , δύο μεταβλητών, και οι μεταβλητές μπορούν να κινούνται μόνο
στο διάστημα
είναι φανερό ότι πρέπει να γίνουν τα εξής: Επιλέγοντας
δυαδική κωδικοποίηση, η κάθε συμβολοσειρά πρέπει να περιέχει τιμές και για τις
δύο μεταβλητές. Έστω ότι το μήκος της συμβολοσειράς αποφασίζεται να είναι
(
δυαδικά ψηφία για το
και
για το
). Eπειδή η δυαδική αναπαράσταση που χρησιμοποιείται είναι
απρόσημη, προκύπτει πρόβλημα με τις αρνητικές τιμές. Λύση στο πρόβλημα αυτό
δίνει η αντιστοίχηση του διαστήματος
στο
ως εξής: για κάθε δυαδική συμβολοσειρά υπολογίζεται η
αντίστοιχη δεκαδική της τιμή, η οποία στη συνέχεια πολλαπλασιάζεται με τον
συντελεστή:
όπου
,
είναι αντίστοιχα το άνω και το κάτω όριο του πεδίου ορισμού
της συνάρτησης και
το μήκος της δυαδικής συμβολοσειράς για μια μεταβλητή. Δηλαδή,
,
,
και τελικά
. Έτσι, προκύπτει μια τιμή που ανήκει στο διάστημα
και από την οποία τελικά αφαιρούνται
μονάδες για να βρεθεί το αντίστοιχό της στο
.