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

 

6.4     Χρονοπρογραμματισμος

 

Ο χρονοπρογραμματισμός (scheduling) μπορεί να οριστεί ως το πρόβλημα εύρεσης μιας βέλτιστης σειράς για την εκτέλεση ενός πεπερασμένου συνόλου λειτουργιών, χωρίς να παραβιάζεται ένα συγκεκριμένο σύνολο κανόνων [47]. Είναι από τα πιο συνηθισμένα προ-βλήματα που συναντώνται στο χώρο της βελτιστοποίησης, αλλά και από τα πιο δύσκολα, αφού ανήκει στην κατηγορία των NP-complete προβλημάτων. Στην πιο συχνή τους μορφή, αυτού του είδους τα προβλήματα έχουν ως στόχο τη μεγιστοποίηση της χρήσης ανθρώπων ή πόρων και την ταυτόχρονη ελαχιστοποίηση του χρόνου που απαιτείται για την ολοκλήρωση μιας διεργασίας. Προκύπτουν συγκρούσεις από το γεγονός ότι ένα άτομο ή κάποιος πόρος δεν μπορεί να χρησιμοποιηθεί σε περισσότερες από μια εργασίες ταυτόχρονα, ενώ υπάρχουν και περιορισμοί όπως η τήρηση προτεραιοτήτων, η μη διαθεσιμότητα κάποιων πόρων για κάποιο χρονικό διάστημα, κ.τ.λ. Η πιο συνηθισμένη πρακτική για την επίλυση των προβλημάτων χρονοπρογραμματισμού είναι ένας συνδυασμός κάποιας τεχνικής βελτιστοποίησης με ευρετική μέθοδο. Ακολουθούν μερικές εφαρμογές στις οποίες γίνεται χρήση των Γ.Α. με αξιόλογα αποτελέσματα.

 

Ένα πολύπλοκο και με πολλές παραμέτρους πρόβλημα χρονοπρογραμματισμού παρουσιάστηκε στο εργαστήριο του Σταθμού Ελέγχου Ολοκλήρωσης Συστημάτων (System Integration Test Station) του Αμερικάνικου Ναυτικού, στην Καλιφόρνια. Το εργαστήριο διαθέτει μια ποικιλία εξοπλισμού και εγκαταστάσεων για την εκπαίδευση των υποψηφίων αεροπόρων, όπως σκελετούς αεροπλάνων F-14, cockpits, radar, πολεμικά συστήματα ελέγχου κ.τ.λ. που είναι προσαρμοσμένα όλα σε ένα περιβάλλον προσομοίωσης. Ακόμη, ένα πλήθος άλλων βοηθητικών συσκευών είναι διαθέσιμο, όπως υπολογιστές, ραδιόφωνα, καταγραφείς, κ.τ.λ. Το ανθρώπινο δυναμικό που κάνει χρήση αυτού του υλικού είναι οι εκπαιδευόμενοι και το τεχνικό προσωπικό.

 

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

 

1)        Περιορισμοί πόρων, π.χ. περισσότεροι από ένας πόρος μπορούν να είναι ταυτόχρονα διαθέσιμοι σε όλους.

2)        Χρονικοί περιορισμοί, π.χ. όλες οι εργασίες πρέπει να ολοκληρώνονται μέχρι τις 5 μ.μ.

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

 

Ο Gilber Syswerda [67], κατασκεύασε ένα σύστημα χρονοπρογραμματισμού (scheduling system) κατάλληλο για την επίλυση προβλημάτων, όπως του εργαστηρίου που περιγράφηκε παραπάνω. Σε αυτό, γίνεται συνδυασμός των Γ.Α. με ευρετικές μεθόδους. Πιο συγκεκριμένα, σε κάθε πρόβλημα χρονοπρογραμματισμού, στόχος είναι η εύρεση της κατάλληλης σειράς για την εκτέλεση ενός συνόλου εργασιών. Από τις πιθανές σειρές, κάποιες είναι ακατάλληλες, γιατί παραβιάζουν περιορισμούς.

 

Για να αντιμετωπιστεί το πρόβλημα των ακατάλληλων σειρών, χρησιμοποιείται ένας ντετερμινιστικός κατασκευαστής χρονοπρογράμματος (deterministic schedule builder), ο οποίος παίρνει ως είσοδο μια ακολουθία εργασιών και παράγει ως έξοδο ένα έγκυρο πρόγραμμα για αυτές. Η διαδικασία αυτή γίνεται με μέθοδο FCFS (First Come First Served), δηλαδή τοποθετείται η πρώτη εργασία της ακολουθίας στο πρόγραμμα με κάποια ευρετική μέθοδο, έπειτα τοποθετείται η δεύτερη, χωρίς να επηρεάζει τη θέση της πρώτης, κ.ο.κ. (όλες οι τοποθετήσεις γίνονται με τήρηση των περιορισμών). Οι λεπτομέρειες σχεδιασμού και υλοποίησης αυτού του κατασκευαστή δεν ενδιαφέρουν άμεσα.

 

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

 

Όσον αφορά την κωδικοποίηση έγινε μια απλή και προφανής επιλογή. Η κάθε συμβολοσειρά αναπαριστά μια σειρά εργασιών, δηλαδή ένα είδος τακτικής κωδικοποίησης, όπου όμως, η σειρά αυτή καθ' αυτή δεν αντιστοιχεί σε ένα συγκεκριμένο πρόγραμμα. Αντίθετα, η συμβολοσειρά εισάγεται στον schedule builder και από εκεί παράγεται ένα πρόγραμμα, όπως περιγράφηκε παραπάνω.

 

Η λειτουργία του schedule builder είναι εντελώς ανεξάρτητη από τον Γ.Α. Οι λεπτομέρειες, οι περιορισμοί και οι ιδιαιτερότητες του κάθε προβλήματος γίνονται απολύτως αντιληπτές από το schedule builder και ο στόχος του είναι να παράγει νόμιμα προγράμματα.

 

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

 

Ακολουθεί η προσαρμογή των γενετικών λειτουργιών, που είναι ίσως, και το πιο ενδιαφέρον μέρος του σχεδιασμού του Γ.Α. Εδώ οι πειραματισμοί και οι εμπνεύσεις μπορούν και σχεδόν πάντα ποικίλουν. Από την κωδικοποίηση που επιλέχθηκε, είναι εμφανές ότι όσο πιο κοντά στην αρχή της δυαδικής συμβολοσειράς είναι μια εργασία, τόσο πιο πιθανό είναι να τοποθετηθεί στο πρόγραμμα. Επίσης, σημαντικό ρόλο παίζει και η σειρά των εργασιών, αφού μια εργασία μπορεί να είναι κοντά στην αρχή, αλλά να προηγείται κάποια άλλη που χρειάζεται τους ίδιους, μη πολλαπλώς διαθέσιμους, πόρους και έτσι να αποκλειστεί. Έχοντας αυτά υπ' όψη, δοκιμάστηκαν διάφορες ιδέες και παραλλαγές για τις διαδικασίες διασταύρωσης και μετάλλαξης.

 

Όσον αφορά τη διασταύρωση, εξετάστηκαν οι εξής τρεις παραλλαγές:

 

·           Τακτική Διασταύρωση Λίστας (Order-Based Crossover).

·           Διασταύρωση Θέσης (Position-Based Crossover).

·           Διασταύρωση Ακμών (Edge Recombination Crossover).

 

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

 

Παράδειγμα: Έστω οι ακόλουθοι γονείς και οι τυχαία επιλεγμένες θέσεις:

 

γονέας 1 Þ

a b c d e f g h i j

γονέας 2 Þ

e i b d f a j g c h

θέσεις Þ

 - * * - * - -* - - 

 

Τότε, τα δύο παιδιά που θα προκύψουν θα είναι τα εξής:

παιδί 1 Þ a i b d f f g g i j
 
παιδί 2 Þ e b c d e a j h c h .

 

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

Ανάλογος είναι ο πειραματισμός και για τη μετάλλαξη. Εξετάστηκαν τρία είδη μετάλλαξης:

 

·           Μετάλλαξη Θέσης (Position-Βased Μutation).

·           Μετάλλαξη Σειράς (Order-Based Mutation).

·           Μετάλλαξη Αναδιάταξης (Scramble mutation).

 

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

 

Υλοποιώντας όλες τις παραπάνω σχεδιαστικές επιλογές προέκυψε ένα σύστημα με αρκετά αξιόλογες επιδόσεις.

 

Στη Ενότητα 4 του Κεφαλαίου 2 παρουσιάστηκε μια μέθοδος επίλυσης του TSP με Γ.Α. Οι Whitley, Starkweather και Shaner [71] παρουσίασαν ένα εργαλείο Γενετικού Προγραμματισμού με το όνομα GENITOR, που ειδικεύεται στην επίλυση προβλημάτων δρομολόγησης με Γ.Α. Με το εργαλείο αυτό πέτυχαν μια πολύ καλή επίδοση στην εύρεση λύσης για το TSP, χρησιμοποιώντας τη διασταύρωση ακμών. Ο τρόπος λειτουργίας της παρουσιάζεται παρακάτω.

 

Επιλέγοντας τη τακτική κωδικοποίηση, η πληροφορία της κάθε συμβολοσειράς εστιάζεται στις συνδέσεις των κόμβων. Π.χ. η συμβολοσειρά ABCDEF περιέχει την εξής πληροφορία: ακολουθείται η διαδρομή που ορίζεται από τη διατεταγμένη σειρά ακμών-διαδρομών AB, BC, CD, DE, EF και FA. Η σειρά των πόλεων που συνδέει μια ακμή δεν παίζει ρόλο, γιατί δυο οποιεσδήποτε διαδρομές AB και BA κοστίζουν το ίδιο.

 

Μία ιδανική μέθοδος διασταύρωσης θα πρέπει να μπορεί να συνδυάζει τις πληροφορίες σύνδεσης των ακμών των δυο γονέων και να τις κληροδοτεί στους απογόνους. Η διασταύρωση ακμών εξυπηρετεί αυτήν ακριβώς την ιδέα. Προσπαθεί να εκμεταλλευτεί τις πληροφορίες των συνδέσεων κατασκευάζοντας ένα χάρτη ακμών (edge map) και να περάσει όσο το δυνατόν περισσότερες από αυτές στους απογόνους. Ο χάρτης ακμών αποθηκεύει όλες τις συνδέσεις από τους δύο γονείς και έτσι κάθε πόλη θα μετέχει σε δύο έως τέσσερις συνδέσεις (δύο από κάθε γονέα).

 

 

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