Αριστοποίηση Simplex

Θεωρία

Το simplex είναι ένας απλός αλγόριθμος αριστοποίησης που αναζητεί το διάνυσμα παραμέτρων το οποίο αντιστοιχεί στο "παγκόσμιο ακρότατο" (global extreme), δηλ. το μέγιστο ή ελάχιστο, μιας n-διάστατης συνάρτησης F(x₁, x₂,..,x_n), στον παραμετρικό χώρο ("περιοχή αναζήτησης").

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

Ένα simplex δύο διαστάσεων ξεκινά με τρεις παρατηρήσεις με τρία διαφορετικά ζεύγη παραμέτρων (x₁, x₂) (δηλ. τρεις "δοκιμές" με διαφορετικές συνθήκες). Οι τρεις παρατηρήσεις ορίζουν τις τρεις κορυφές ενός τριγώνου που αποτελεί το 1ο simplex. Στο τρισδιάστατο χώρο απαιτούνται τέσσερις αρχικές τριάδες παραμέτρων, που αντίστοιχα ορίζουν τέσσερα σημεία στο χώρο και επομένως το simplex θα είναι ένα τετράεδρο. Για χώρους με περισσότερες από τρεις διαστάσεις (υπερχώροι) είναι δύσκολο να φανταστεί κανείς το πώς θα μπορούσε να αντιπροσωπευθεί ένα simplex, αλλά η αρχή του αλγορίθμου είναι η ίδια. 

Στο δισδιάστατο simplex, μετά τη μέτρηση της απόκρισης (response) κάθε παρατήρησης τα τρία σημεία κατατάσσονται ως εξής: Β (best) το σημείο με την καλύτερη απόκριση (RB), NB (next-to-best) το σημείο με την αμέσως καλύτερη απόκριση (RNB) και W (worst) το σημείο με τη χειρότερη απόκριση (RW). Ο αλγόριθμος (με βάση τα τρία αυτά σημεία) θα προτείνει ένα επόμενο σημείο, δηλαδή, τις επόμενες πειραματικές συνθήκες που θα πρέπει να δοκιμασθούν. Το νέο σημείο θα υποδειχθεί με μία από τις ακόλουθες τρεις διαδικασίες: ανάκλαση (reflection, R), επέκταση (extension, E) και σύμπτυξη (contraction, C). Οι ίδιες διαδικασίες πραγματοποιούνται και στο γενικό simplex n-διαστάσεων. Οι διαδικασίες αυτές στην περίπτωση του δισδιάστατου simplex δείχνονται στο επόμενο "ζωντανό" σχήμα.

Συνοπτικά, ο αλγόριθμος simplex ακολουθεί τα εξής βήματα:

1. Υπολογίζεται η θέση του κεντροειδούς (centroid ) CEN στο ενδιάμεσο των σημείων B και NB.

2. Πραγματοποιείται ανάκλαση (reflection) του χειρότερου σημείου W ως προς το CEN και μετρείται η απόκριση του νέου σημείου R.

3. Εάν το R βρίσκεται μέσα στην εξεταζόμενη περιοχή και η απόκρισή του RR είναι καλύτερη από την RW, τότε σχηματίζεται ένα νέο simplex με αντικατάσταση του W με το σημείο R. Έτσι έχουμε μια "κίνηση" του simplex. Η διαδικασία επαναλαμβάνεται από το βήμα <1> με το νέο simplex.

4. Εάν η απόκριση RR είναι ακόμη καλύτερη, δηλαδή καλύτερη και από την RB, αυτό αποτελεί ένδειξη ότι η κίνηση γίνεται προς τη σωστή κατεύθυνση και δοκιμάζεται επέκταση (extension) προς το σημείο Ε, που απέχει δυο φορές περισσότερο από το CEN απ' ό,τι το R.

5. Εάν το Ε βρίσκεται μέσα στην εξεταζόμενη περιοχή και η απόκρισή του RE είναι καλύτερη από εκείνη του RR, τότε το W αντικαθίσται από το Ε, εάν όχι αντικαθίσταται από το R. Η διαδικασία επαναλαμβάνεται από το βήμα <1> με το νέο simplex.

6. Εάν η αρχική ανάκλαση αποτύχει, δηλ. αν το R βρίσκεται εκτός της εξεταζόμενης περιοχής ή η απόκρισή του RR είναι χειρότερη της RW, τότε πραγματοποιείται σύμπτυξη (contraction) προς το σημείο C. Το C βρίσκεται ενδιάμεσα των W και CEN. Η διαδικασία επαναλαμβάνεται από το βήμα <1> με το νέο simplex.

Οι επαναλήψεις του κύκλου τερματίζονται όταν δεν παρατηρείται σημαντική βελτίωση κατά τις κινήσεις του simplex, ή όταν οι προτεινόμενες μετακινήσεις είναι πλέον αμελητέες.

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

Applet

Με αυτό το applet μπορείτε να παρατηρήσετε τις κινήσεις που προτείνει ο αλγόριθμος simplex και πώς το simplex κινείται για να εντοπίσει το παγκόσμιο ακρότατο (το ελάχιστο στο συγκεκριμένο παράδειγμα) μέσα στην περιοχή αναζήτησης.

Πρέπει να ορίσετε 3 σημεία μέσα στην περιοχή αναζήτησης (1 "αριστερό κλικ" με το ποντίκι για κάθε σημείο). Πατήστε το πλήκτρο Step για να δείτε τη νέα κίνηση του simplex και συνεχείστε έτσι, έως ότου τερματισθεί η αναζήτηση. Το σημείο με την άριστη απόκριση (ελάχιστη τιμή) σημειώνεται με ένα λευκό σταυρό.

Στο χώρο αναζήτησης τα περιγράμματα (contours) με διάφορες αποχρώσεις του μπλε-μαύρου επιτρέπουν στο χρήστη να γνωρίζει που περίπου βρίσκεται το "παγκόσμιο" ακρότατο ή άλλα τοπικά ακρότατα και το κατά πόσο το simplex κινείται προς τη σωστή κατεύθυνση. Πρασπαθήστε να προβλέψετε ποιά θα είναι η επόμενη κίνηση (δηλ. ανάκλαση, επέκταση, σύμπτυξη) πριν πατήσετε το πλήκτρο Step.

Υπάρχουν 6 διαφορετικές συναρτήσεις F(x₁, x₂) (οι F1, F2, .., F6). Κάθε μία από αυτές "παράγει" μια διαφορετική επιφάνεια απόκρισης. Οι συναρτήσεις F5 and F6 παράγουν επιφάνειες με τοπικά ελάχιστα, όπου συχνά (ανάλογα με τη θέση του 1ου simplex) ο αλγόριθμος του simplex "παγιδεύεται" ή παραμένει στατικός, αποτυγχάνοντας έτσι, να εντοπίσει το "παγκόσμιο" ελάχιστο.