next up previous contents
Next: Διαδοχική Παρεμβολή Παραβολών Up: ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΣΕ ΜΙΑ ΔΙΑΣΤΑΣΗ Previous: ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΣΕ ΜΙΑ ΔΙΑΣΤΑΣΗ   Contents

Έρευνα για Χρυσή Τομή

Θεωρείστε ότι η 51#51 είναι μία συνάρτηση πραγματικών τιμών που έχει ένα μόνο μέγιστο στο διάστημα 1060#1060. Έστω ότι τα 1183#1183 και 426#426 είναι δύο σημεία μέσα στο διάστημα, με 1227#1227. Η σύγκριση των τιμών 1228#1228 και 1229#1229 της συνάρτησης και η χρήση της ιδιότητάς της να έχει μοναδικό μέγιστο θα μας επιτρέψουν να απορρίψουμε ένα υποδιάστημα, είτε το 1230#1230 είτε το 1231#1231, και να ξέρουμε ότι το ελάχιστο της συνάρτησης βρίσκεται μέσα στο υποδιάστημα που απομένει. Πιο συγκεκριμένα, αν 1232#1232, τότε το ελάχιστο δεν μπορεί να βρίσκεται στο διάστημα 1233#1233. Και αν 1232#1232, τότε το ελάχιστο δε μπορεί να βρίσκεται στο διάστημα 1234#1234. Άρα, έχουμε μείνει με ένα μικρότερο διάστημα, είτε το 1235#1235 είτε το 1236#1236, αντίστοιχα. Επομένως, θα χρειαστεί να υπολογίσουμε μόνο μία νέα αποτίμηση της συνάρτησης για να επαναλάβουμε αυτή τη διαδικασία.

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

Για να πετύχουμε αυτό το στόχο, επιλέγουμε τις σχετικές θέσεις δύο σημείων όπως τ και 1 - τ, όπου 1237#1237, έτσι ώστε 1238#1238 και 1239#1239. Με αυτή την επιλογή, ανεξάρτητα από το ποιό υποδιάστημα έχει απομείνει, η έκτασή του θα σχετίζεται με το προηγούμενο διάστημα σε ένα πεδίο τ, και το εσωτερικό σημείο που απομένει θα σχετίζεται με το νέο διάστημα σε ένα πεδίο τ ή 1 - τ. Aρα, πρέπει να υπολογίσουμε μόνο μία νέα τιμή της συνάρτησης, στο συμπληρωματικό σημείο, για να συνεχίσουμε την επανάληψη. Αυτή η επιλογή των δειγματοληπτικών σημείων λέγεται έρευνα για χρυσή τομή. Ο πλήρης αλγόριθμος είναι αυτός που ακολουθεί:

Αρχική είσοδος: μία συνάρτηση 51#51, ένα διάστημα 1060#1060 στο οποίο η 51#51 έχει μοναδικό μέγιστο, και μία ανεκτικότητα στα σφάλματα tol.


 		 1240#1240

1241#1241
1242#1242
1243#1243
1244#1244
1245#1245
1246#1246
1247#1247
1248#1248
1249#1249
1243#1243
1244#1244
1072#1072
1250#1250
1251#1251
1252#1252
1241#1241
1242#1242
849#849
849#849

Η έρευνα για χρυσή τομή είναι ασφαλής αλλά αργά συγκλίνουσα. Πιο συγκεκριμένα, είναι γραμμικά συγκλίνουσα, με 1054#1054 και 1253#1253.


27#27

Παράδειγμα 6.1   ΈΡΕΥΝΑ ΓΙΑ ΧΡΥΣΗ ΤΟΜΗ.

Παρουσιάζουμε την έρευνα για χρυσή τομή χρησιμοποιώντας την για να ελαχιστοποιήσουμε τη συνάρτηση


1254#1254

Ξεκινώντας με το αρχικό διάστημα 1255#1255, δίνουμε τιμές στη συνάρτηση για τα σημεία 1256#1256 και 1257#1257, και παίρνουμε 1258#1258 και 1259#1259. Αφού ισχύει 1260#1260, ξέρουμε ότι το ελάχιστο πρέπει να βρίσκεται στο διάστημα 1261#1261, και άρα μπορούμε να αντικαταστήσουμε το 365#365 με το 426#426 και να επαναλάβουμε τη διαδικασία. Η πρώτη επανάληψη απεικονίζεται στο σχήμα 6.2, και ολόκληρη η ακολουθία των επαναλήψεων δίνεται αμέσως μετά.


27#27

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

Figure: Πρώτη επανάληψη της έρευνας χρυσής τομής για το πρόβλημα του παραδείγματος
1262#1262



Manolis Vavalis 2000-03-24