ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
Το σύστημα που αναπτύχθηκε δέχεται σαν είσοδο ένα σύνολο από κανόνες (οι αρχικοί κανόνες θα πρέπει να βρίσκονται στο αρχείο INITRULS.TXT στο τρέχον directory). Η συγγραφή των κανόνων πρέπει να γίνει με τρόπο τον οποίο καταλαβαίνει ο συντακτικός αναλυτής (parser) του συστήματος, ο οποίος επεξεργάζεται το αρχείο αυτό, ενώ επιτρέπεται και η εισαγωγή σχολίων. Οι παρακάτω κανόνες, οι οποίοι αποτέλεσαν την είσοδο του συστήματος στα πειράματα που έγιναν, αντανακλούν γνώση από εφαρμογές στο Χρηματιστήριο Αξιών Αθηνών.
# How to write rules:
#
# 1. Rules are separated with two consecutive <CR>s.
#
# 2. Each rule must be in the form:
# logical_expression => relational_expression
# where logical_expression is constructed with one or more
# relational_expressions using the logical operators NOT(unary),
# AND(binary) and OR(binary).
# The above order shows the precedence order of these operators.
# Grouping can be done only with {}.
#
# 3. Each relational_expression must be closed with []. No checking # is done in the structure of relational_expressions.
#
# 4. Comments must start with #. The parser ignores everything
# from # to the end of line.
#
# Example:
# [(BondsNOW-BondsOLD)/BondsOLD<0] AND # some comment...
# [(DJUtilNOW-DJUtilOLD)/DJUtilOLD>0] => DJNEW>DJNOW
[(IntRShortNOW-IntRShortOLD)/IntRShortOLD
>(IntRLongNOW-IntRLongOLD)/IntRLongOLD] => [DJNEW<DJNOW]
[(IntRShortNOW-IntRShortOLD)/IntRShortOLD
>(IntRLongNOW-IntRLongOLD)/IntRLongOLD] => [DJNEW>DJNOW]
[(BondsNOW-BondsOLD)/BondsOLD>0] => [DJNEW<DJNOW]
[(BondsNOW-BondsOLD)/BondsOLD<0] => [DJNEW>DJNOW]
[(BondsNOW-BondsOLD)/BondsOLD>0] => [DJUtilNEW>DJUtilNOW]
[(BondsNOW-BondsOLD)/BondsOLD<0] => [DJUtilNEW<DJUtilNOW]
[(DJUtilNOW-DJUtilOLD)/DJUtilOLD>0] => [DJNEW>DJNOW]
[(DJUtilNOW-DJUtilOLD)/DJUtilOLD<0] => [DJNEW<DJNOW]
[(BondsNOW-BondsOLD)/BondsOLD>0] AND
NOT [(DJNOW-DJOLD)/DJOLD<0] => [DJNEW>DJNOW]
NOT [(BondsNOW-BondsOLD)/BondsOLD<0] AND
[(DJNOW-DJOLD)/DJOLD>0] => [DJNEW>DJNOW]
[(BondsNOW-BondsOLD)/BondsOLD>0] AND
NOT [(DJNOW-DJOLD)/DJOLD<0] => [DJNEW<DJNOW]
NOT [(BondsNOW-BondsOLD)/BondsOLD<0] AND
[(DJNOW-DJOLD)/DJOLD>0] => [DJNEW<DJNOW]
[(DollarNOW-DollarOLD)/DollarOLD>0] => [CRBNEW<CRBNOW]
[(DollarNOW-DollarOLD)/DollarOLD<0] => [CRBNEW>CRBNOW]
[(OilNOW-OilOLD)/OilOLD>0] AND [(GoldNOW-GoldOLD)/GoldOLD>0]
=> [CRBNEW>CRBNOW]
[(OilNOW-OilOLD)/OilOLD<0] AND [(GoldNOW-GoldOLD)/GoldOLD<0]
=> [CRBNEW<CRBNOW]
[(CRBNOW-CRBOLD)/CRBOLD<0] AND
[(BondsNOW-BondsOLD)/BondsOLD>0] => [DJUtilNEW>DJUtilNOW]
[(CRBNOW-CRBOLD)/CRBOLD<0] AND
[(BondsNOW-BondsOLD)/BondsOLD<0] => [CommStocksNEW>CommStocksNOW]
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD>0]
=> [GoldNEW>GoldNOW]
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
=> [GoldNEW<GoldNOW]
[(OilStocksNOW-OilStocksOLD)/OilStocksOLD>0] => [OilNEW>OilNOW]
[(OilStocksNOW-OilStocksOLD)/OilStocksOLD<0] => [OilNEW<OilNOW]
[(OilNOW-OilOLD)/OilOLD>0] AND [(GoldNOW-GoldOLD)/GoldOLD>0]
=> [CommStocksNEW>CommStocksNOW]
[(OilNOW-OilOLD)/OilOLD<0] AND [(GoldNOW-GoldOLD)/GoldOLD<0]
=> [CommStocksNEW<CommStocksNOW]
[(OilNOW-OilOLD)/OilOLD>0] AND [(GoldNOW-GoldOLD)/GoldOLD>0]
=> [DJUtilNEW<DJUtilNOW]
[(OilNOW-OilOLD)/OilOLD<0] AND [(GoldNOW-GoldOLD)/GoldOLD<0]
=> [DJUtilNEW>DJUtilNOW]
[(CommStocksNOW-CommStocksOLD)/CommStocksOLD>0]
=> [DJUtilNEW<DJUtilNOW]
[(CommStocksNOW-CommStocksOLD)/CommStocksOLD<0]
=> [DJUtilNEW>DJUtilNOW]
[(TechStocksNOW-TechStocksOLD)/TechStocksOLD>0] => [DJNEW<DJNOW]
[(TechStocksNOW-TechStocksOLD)/TechStocksOLD<0] => [DJNEW>DJNOW]
[(CRBNOW-CRBOLD)/CRBOLD>0] => [CommStocksNEW>CommStocksNOW]
[(CRBNOW-CRBOLD)/CRBOLD<0] => [CommStocksNEW<CommStocksNOW]
[(IntRShortNOW-IntRShortOLD)/IntRShortOLD>0] AND
[(CRBNOW-CRBOLD)/CRBOLD>0] => [DJUtilNEW<DJUtilNOW]
[(IntRShortNOW-IntRShortOLD)/IntRShortOLD<0] AND
[(CRBNOW-CRBOLD)/CRBOLD<0] => [DJUtilNEW>DJUtilNOW]
[(IntRLongNOW-IntRLongOLD)/IntRLongOLD>0] AND
[(CRBNOW-CRBOLD)/CRBOLD>0] => [DJUtilNEW<DJUtilNOW]
[(IntRLongNOW-IntRLongOLD)/IntRLongOLD<0] AND
[(CRBNOW-CRBOLD)/CRBOLD<0] => [DJUtilNEW>DJUtilNOW]
[(NewHighsNOW-NewHighsOLD)/NewHighsOLD>0] => [DJNEW>DJNOW]
[(NewHighsNOW-NewHighsOLD)/NewHighsOLD>0] => [DJNEW<DJNOW]
[(NewHighsNOW-NewHighsOLD)/NewHighsOLD>0] AND
[(GoldNOW-GoldOLD)/GoldOLD<0] => [CRBNEW<CRBNOW]
[(NewLowsNOW-NewLowsOLD)/NewLowsOLD>0] AND
[(GoldNOW-GoldOLD)/GoldOLD>0] => [CRBNEW>CRBNOW]
[(NewHighsNOW-NewHighsOLD)/NewHighsOLD>0] AND
[(GoldNOW-GoldOLD)/GoldOLD<0] => [DJNEW>DJNOW]
[(NewLowsNOW-NewLowsOLD)/NewLowsOLD>0] AND
[(GoldNOW-GoldOLD)/GoldOLD>0] => [DJNEW<DJNOW]
# Variables used:
# IntRShort Short Term Interest Rate
# IntRLong Long Term Interest Rate
# Bonds Bonds
# Dollar Dollar
# Oil Oil
# Gold Gold
# CRB Commodity Research Bureau index
# DJUtil Dow Jones Utilities index
# DJ Dow Jones index
# CommStocks Commodity Stocks index
# OilStocks Oil Stocks index
# GoldStocks Gold Stocks index
# TechStocks Technology Stocks index
# NewHighs Number of stocks reaching New Highs
# NewLows Number of stocks reaching New Lows
Το σύστημα που υλοποιήθηκε παράγει κανόνες της μορφής:
[(GoldNOW-GoldOLD)/GoldOLD>0] => [CommStocksNEW>CommStocksNOW]
ή
[(BondsNOW-BondsOLD)/BondsOLD<0] AND [(GoldNOW-GoldOLD)/GoldOLD>0]
=> [DJUtilNEW<DJUtilNOW]
Το σύστημα δεν συμπεριλαμβάνει βάση δεδομένων για τον έλεγχο της απόδοσης των κανόνων που προκύπτουν με βάση πραγματικά πειραματικά δεδομένα της αγοράς. Η ενσωμάτωση μιας τέτοιας βάσης δεδομένων προβλέπεται σαν επέκταση του συστήματος μελλοντικά. Όλες οι πιθανές επεκτάσεις του συστήματος περιγράφονται στην Ενότητα 6.
Σχήμα 7.1: Ένα δέντρο έκφρασης.
Το σημαντικότερο, ίσως, συστατικό του συστήματος είναι η αναπαράσταση των κανόνων αυτών σαν άτομα του Γ.Α. Είναι φανερό πως η “κλασική” αναπαράσταση με δυαδικές συμβολοσειρές είναι ανεπαρκής για τους κανόνες αυτούς, οι οποίοι και διαφορετικά μεγέθη παρουσιάζουν, αλλά και διαφορετική πολυπλοκότητα. Αλλά, ακόμα και αν χρησιμοποιούνταν η δυαδική αναπαράσταση, η σχεδίαση γενετικών τελεστών για αυτή αποτελεί πραγματικά δύσκολη υπόθεση.
Ένας απλός και άμεσος τρόπος για την αναπαράσταση τέτοιων προτάσεων σαν δομές που ο υπολογιστής μπορεί να διαχειριστεί είναι τα δέντρα εκφράσεων (expression trees). Στα δέντρα εκφράσεων κάθε μη-τερματικός κόμβος περιέχει ένα τελεστή, τα παιδιά του οποίου (κόμβου) αποτελούν τους τελεστές. Οι τελεστές αποθηκεύονται στα φύλλα του δέντρου.
Οπότε, η πρόταση:
[(BondsNOW-BondsOLD)/BondsOLD>0] AND
NOT [(DJNOW-DJOLD)/DJOLD<0] => [DJNEW>DJNOW]
παριστάνεται από το δέντρο του
Σχήματος 7.1 (λαμβάνοντας υπ’ όψη ότι μια συνεπαγωγή της μορφής
ισοδυναμεί με τη λογική έκφραση
).
Δηλαδή σαν τελεστές θεωρούνται οι λογικοί τελεστές AND, OR και NOT και σαν τελεστές οι σχεσιακές αλγεβρικές προτάσεις. Μάλιστα, για τους λογικούς αυτούς τελεστές έχει οριστεί η εξής σειρά προτεραιότητας (από υψηλή προς χαμηλή): NOT, AND, OR. Για την παράκαμψη της ιεραρχίας αυτής, ο χρήστης που θα γράψει κανόνες μπορεί να ομαδοποιήσει λογικές εκφράσεις με τη χρήση αγκύλων ({ }). Οι αγκύλες έχουν τη μεγαλύτερη προτεραιότητα έναντι των άλλων τελεστών.
Το σύστημα διαβάζει τους κανόνες -οι οποίοι θα αποτελέσουν τον αρχικό πληθυσμό- από το αρχείο INITRULS.TXT και, αρχικά, τους μετατρέπει σε postfix μορφή -η μετατροπή αυτή γίνεται ταυτόχρονα με τη μετατροπή από συνεπαγωγή σε λογική έκφραση- (CStack.H, CIn2Post.H, CIn2Post.CPP modules). Η διαδικασία μετατροπής έχει ως εξής:
1) διαβάζεται το επόμενο token από τον κανόνα
2) εάν είναι τελεστής, τοποθετείται στην postfix έκφραση
3) εάν είναι τελεστής, τοποθετείται στη στοίβα λογικών τελεστών, αφού πρώτα αφαιρεθούν από τη στοίβα όλοι οι τελεστές με μεγαλύτερη προτεραιότητα και τοποθετηθούν στην postfix έκφραση
4) εάν είναι κλειστή αγκύλη (}), εκτελούνται pop (και οι τελεστές που αφαιρούνται από τη στοίβα τοποθετούνται στην postfix έκφραση) μέχρι να βρεθεί η πρώτη ανοιχτή αγκύλη ({)
5) τα βήματα 1-4 επαναλαμβάνονται για ολόκληρο τον κανόνα
Παράδειγμα: Έστω ότι έχουμε τον εξής κανόνα:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
AND
NOT { [(DollarNOW-DollarOLD)/DollarOLD>0] AND
[(OilNOW-OilOLD)/OilOLD<0] } => [CommStocksNEW<CommStocksNOW]
Παρακάτω φαίνεται, βήμα προς βήμα, η μετατροπή του κανόνα σε postfix λογική έκφραση. Σε κάθε βήμα, διαβάζεται ένα token από τον κανόνα και γίνονται οι αντίστοιχες ενέργειες. Αρχικά, στη στοίβα τελεστών, τοποθετείται ο τελεστής NOT ακολουθούμενος από μια ανοιχτή αγκύλη ({), και όταν συναντηθεί το σύμβολο συνεπαγωγής =>, επιστρέφεται (σαν token) από τον κανόνα μια κλειστή αγκύλη (}) και ο τελεστής OR. Έτσι, υλοποιείται η μετατροπή από συνεπαγωγή σε λογική έκφραση. Κατά τ’ άλλα, η διαδικασία είναι όπως περιγράφηκε.
Βήμα 0:
Postfix έκφραση: κενή
Στοίβα τελεστών:
ΝΟΤ |
{ |
Βήμα
1: (token
= [(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0])
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
Στοίβα τελεστών:
ΝΟΤ |
{ |
Βήμα
2: (token
= AND)
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
Στοίβα τελεστών:
NOT |
{ |
AND |
Βήμα 3: (token = NOT)
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
Στοίβα τελεστών:
NOT |
{ |
AND |
NOT |
Βήμα
4: (token =
{)
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
Στοίβα τελεστών:
NOT |
{ |
AND |
NOT |
{ |
Βήμα
5: (token =
[(DollarNOW-DollarOLD)/DollarOLD>0])
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0]
Στοίβα τελεστών:
NOT |
{ |
AND |
NOT |
{ |
Βήμα
6: (token =
AND)
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0]
Στοίβα τελεστών:
NOT |
{ |
AND |
NOT |
{ |
AND |
Βήμα
7: (token =
[(OilNOW-OilOLD)/OilOLD<0])
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0][(OilNOW-OilOLD)/OilOLD<0]
Στοίβα τελεστών:
NOT |
{ |
AND |
NOT |
{ |
AND |
Βήμα
8: (token =
})
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0][(OilNOW-OilOLD)/OilOLD<0] AND
Στοίβα τελεστών:
NOT |
{ |
AND |
NOT |
Βήμα
9: (token =
}
& OR
- αντί του
=>)
α) Postfix
έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0][(OilNOW-OilOLD)/OilOLD<0] AND NOT AND
Στοίβα τελεστών:
NOT |
β)
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0][(OilNOW-OilOLD)/OilOLD<0] AND NOT AND NOT
Στοίβα τελεστών:
OR |
Βήμα
10: (token =
[CommStocksNEW<CommStocksNOW])
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0][(OilNOW-OilOLD)/OilOLD<0] AND NOT AND NOT [CommStocksNEW<CommStocksNOW]
Στοίβα τελεστών:
OR |
Βήμα
11: (token =
end-of-rule)
Postfix έκφραση:
[(GoldStocksNOW-GoldStocksOLD)/GoldStocksOLD<0]
[(DollarNOW-DollarOLD)/DollarOLD>0][(OilNOW-OilOLD)/OilOLD<0] AND NOT AND NOT [CommStocksNEW<CommStocksNOW]
OR
Στοίβα τελεστών: ( Κενη )
|
Στη συνέχεια, με τη χρήση μιας στοίβας από δέντρα (CStack.h module), το σύστημα χτίζει τα δέντρα εκφράσεων, ακολουθώντας την εξής διαδικασία
1) διαβάζεται το επόμενο token από την postfix έκφραση και κατασκευάζεται δέντρο με ένα μόνο κόμβο με περιεχόμενο το token αυτό
2) εάν είναι τελεστής, ο κόμβος τοποθετείται (push) στη στοίβα - διαφορετικά, εάν είναι τελεστής, γίνονται τόσα pop (η pop επιστρέφει δέντρα εκφράσεων) όσοι και οι τελεστές αυτού του τελεστή (στην περίπτωσή μας, οι AND και OR παίρνουν δύο τελεστές και ο NOT έναν) και τα δέντρα αυτά εισάγονται σαν παιδιά υπό-δέντρα του τρέχοντα κόμβου
3) τα βήματα 1 και 2 επαναλαμβάνονται για όλη την postfix έκφραση
Λεπτομέρειες στην υλοποίηση των παραπάνω διαδικασιών μπορούν να βρεθούν στα modules που αναφέρονται, τα οποία περιέχουν πλήθος σχολίων για την κατανόησή τους.
Σημείωση: Στην πραγματικότητα, τα δέντρα δεν περιέχουν στα φύλλα αλφαριθμητικά των σχεσιακών αλγεβρικών εκφράσεων. Κατά την ανάγνωση των κανόνων και την μετατροπή τους σε postfix μορφή, κάθε σχεσιακή έκφραση αποθηκεύεται σε ένα προσωρινό αρχείο και αντιστοιχίζεται σε αυτή ένας μοναδικός αριθμός που αποτελεί δείκτη της θέσης της στο αρχείο. Οι αριθμοί αυτοί αποθηκεύονται στα φύλλα των δέντρων. Έτσι, πετυχαίνεται μεγαλύτερη ταχύτητα και οικονομία στη μνήμη. Στη παρούσα έκδοση, κάθε έκφραση που διαβάζεται, αποθηκεύεται και της ανατίθεται ένας μοναδικός αριθμός, ακόμα και αν αυτή η ίδια έκφραση έχει εμφανιστεί προηγουμένως. Δηλαδή, το σύστημα δεν είναι ικανό να διακρίνει ίδιες εκφράσεις μεταξύ τους[1].
Τα δέντρα που υλοποιήθηκαν υποστηρίζουν δύο είδη προσπέλασης:
· Pre-order: Χρησιμοποιήθηκε για την αναδρομική αντιστοίχιση κανόνων στα δέντρα εκφράσεων. Αυτό γίνεται με μια ρουτίνα της μορφής:
print_tree_preorder(treenode *t)
{
print_tree_preorder(t->left);
cout<<t->contents;
print_tree_preorder(t->right);
}
·
Depth-first: Είναι πιο βολική για χρήση στους γενετικούς τελεστές,
οι οποίοι δεν θα πρέπει να καταστρέφουν τη βασική δομή των δέντρων που
αντιστοιχούν σε κανόνες, δηλαδή τα σημεία που επιλέγονται είτε για διασταύρωση,
είτε για μετάλλαξη, θα πρέπει να είναι διάφορα της ρίζας (OR), του αριστερού
παιδιού της (NOT) και του δεξιού παιδιού της (έκφραση πρόβλεψης-forecasting) που
με την depth-first έχουν πάντοτε δείκτες 0, 1 και
αντίστοιχα, όπου
το μέγεθος του δέντρου.
Σχήμα 7. 2: Δέντρα-Γονείς κατά τη διαδικασία της διασταύρωσης.
[1] Η επέκταση του συστήματος, ώστε να παρακάμπτει την αδυναμία αυτή, δεν είναι δύσκολη και μάλιστα μπορεί να υλοποιηθεί με πολύ αποδοτικό τρόπο, χρησιμοποιώντας ένα λεξικό, ένα κατάλληλα προσαρμοσμένο πίνακα κατακερματισμού (hash table).