Δευτέρα, 8 Δεκεμβρίου 2014

Σύγκριση απλού αλγόριθμου μεγιστοποίησης με γενετικό αλγόριθμο

Θα συγκρίνουμε έναν απλό αλγόριθμο μεγιστοποίησης με έναν γενετικό αλγόριθμο. Θα προσπαθήσουμε δηλαδή να λύσουμε το πρόβλημα μεγιστοποίησης της συνάρτησης
στο εύρος τιμών x1E[-3,12] και x2E[4,6] με δύο τρόπους και θα συγκρίνουμε τα αποτελέσματα αλλά και την ταχύτητα που προκύπτουν αυτά τα αποτελέσματα.
Αρχικά, συντάχθηκε ο ακόλουθος αλγόριθμος μεγιστοποίησης:

Private Sub Command1_Click()

'δηλώνονται οι μεταβλητές του προβλήματος
Dim q As Integer, x1 As Double, x2 As Double, a1 As Double, a2 As Double, b1 As Double, b2 As Double

'εισάγονται μέσω μίας φόρμας παράμετροι όπως το εύρος τιμών (a1, a2, b1, b2) που θα αναζητηθεί το μέγιστο και το πλήθος των δεκαδικών (q) που θα κρατάει ο υπολογιστής
q = Text1.Text
a1 = Text2.Text
b1 = Text3.Text
a2 = Text4.Text
b2 = Text5.Text

'η αρχική τιμή του x1 ορίζεται ως a1
x1 = a1

'η αρχική τιμή του x2 ορίζεται ως a2
x2 = a2

'θέτουμε το αρχικό μέγιστο ως έναν πολύ μικρό αριθμό
fmax = -10 ^ 10

'όσο το x1 είναι μικρότερο του b1 ο αλγόριθμος κάνει επαναληπτική διαδικασία
Do While x1 <= b1

'όσο το x2 είναι μικρότερο του b2 ο αλγόριθμος κάνει επαναληπτική διαδικασία
Do While x2 <= b2

'για κάθε ζεύγος τιμών x1 και x2 υπολογίζεται η αντίστοιχη τιμή της συνάρτησης
f = 21.5 + x1 * Sin(4 * 3.14 * x1) + x2 * Sin(20 * 3.14 * x2)

'αν βρεθεί μία τιμή της συνάρτησης μεγαλύτερη από το υπάρχον μέγιστο τότε αυτή θέτεται ως η τρέχουσα τιμή του μεγίστου
If f > fmax Then
fmax = f
End If

'πήγαινε στο επόμενο x2
x2 = x2 + 1 / (10 ^ q)
Loop

'πήγαινε στο επόμενο x1
x1 = x1 + 1 / (10 ^ q)

'το x2 ορίζεται ξανά ως a2
x2 = a2
Loop

'στην φόρμα εκτυπώνεται το τελικό μέγιστο
Text6.Text = Format(fmax, "0.00000")

End Sub

Ο παραπάνω αλγόριθμος δημιουργεί ένα πλέγμα τιμών του x1 και του x2 και για κάθε ζευγάρι (x1, x2) βρίσκει την τιμή της f. Από όλες τις τιμές της f κρατάει την μεγαλύτερη και με αυτό τον τρόπο βρίσκεται το μέγιστο της f. Στην εικόνα 1 φαίνεται η φόρμα εισαγωγής των δεδομένων και εξαγωγής των αποτελεσμάτων.
εικόνα 1, η φόρμα από την οποία εισάγονται τα δεδομένα στο
αλγόριθμο.
Έτσι εισάγουμε στην φόρμα τα στοιχεία επιλέγοντας ως πλήθος δεκαδικών ψηφίων 1 και το αποτέλεσμα που παίρνουμε φαίνεται στην εικόνα 2.
εικόνα 2, η φόρμα μετά την εκτέλεση του αλγόριθμου για πλήθος
δεκαδικών ψηφίων ίσο με 1.
Παρατηρούμε ότι η μέγιστη τιμή είναι το 31.7292. Παρακάτω θα δούμε ότι είναι μία άστοχη λύση του προβλήματος καθώς χρησιμοποιώντας μόνο ένα δεκαδικό ψηφίο δεν έχουμε αρκετή ακρίβεια. Τρέχοντας τον κώδικα με δύο δεκαδικά ακρίβεια παίρνουμε ως αποτέλεσμα το 39.01279 και με τρία δεκαδικά ακρίβεια παίρνουμε ως αποτέλεσμα το 39.05899 . Χρησιμοποιώντας ένα ή δύο δεκαδικά ο αλγόριθμος δίνει αμέσως αποτέλεσμα ενώ για τρία δεκαδικά χρειάζεται μερικά δευτερόλεπτα για να δώσει αποτέλεσμα. Όμως αν αυξήσουμε τα δεκαδικά σε τέσσερα ο κώδικας σταματάει να ανταποκρίνεται και δεν παίρνουμε αποτέλεσμα (ίσως να πάρουμε μετά από πολύ ώρα). Τελικά το μέγιστο που προκύπτει από τον αλγόριθμο αυτόν είναι το 39.05899 .

Τώρα χρησιμοποιούμε τον γενετικό αλγόριθμο που παρουσιάστηκε στην ανάρτηση http://fromsciencetoengineering.blogspot.gr/2014/11/blog-post_18.html . Καθώς όμως έχουμε να αντιμετωπίσουμε διαφορετική συνάρτηση αυτή την φορά αλλάζουμε την σειρά:
ev(i)=5-(val1(i))^2-(val2(i))^2
και την αντικαθιστούμε με την σειρά:
ev(i) = 21.5 + val1(i) * Sin(4 * 3.14 * val1(i)) + val2(i) * Sin(20 * 3.14 * val2(i))

Έπειτα τρέχουμε τον αλγόριθμο. Στην εικόνα 3 φαίνονται τα στοιχεία που εισάγαμε. Αρχικά θα δοκιμάσουμε να χρησιμοποιήσουμε μόνο 1 δεκαδικό ψηφίο
εικόνα 3, η φόρμα του γενετικού αλγόριθμου μετά την εκτέλεση.
Το μέγιστο που παίρνουμε είναι το 38.200708 που είναι μεγαλύτερο από το 31.7292 που βρήκαμε από τον απλό αλγόριθμο για ένα δεκαδικό ακρίβεια όμως που είναι μικρότερο από το 39.05899 που βρήκαμε ως τελικό αποτέλεσμα από τον απλό αλγόριθμο. Για να χρησιμοποιηθεί σωστά ένας γενετικός αλγόριθμος πρέπει να τον τρέξουμε αρκετές φορές και να κρατήσουμε την μεγαλύτερη από τις τιμές που μας δίνει. Αυτό συμβαίνει γιατί ο γενετικός αλγόριθμος χρησιμοποιεί τον παράγοντα της τύχης και κάθε φορά δίνει δίνει διαφορετικό μέγιστο. Έτσι αυξάνουμε τα δεκαδικά στα 4 και τον τρέχουμε 10 φορές (κάθε εκτέλεση κρατάει μερικά δευτερόλεπτα) με αποτέλεσμα να πάρουμε τον παρακάτω πίνακα:

φορά εκτέλεσης           αποτέλεσμα
1η                                 38.798124
2η                                 38.841906
3η                                 38.803483
4η                                 38.794773
5η                                 38.755526
6η                                 38.856692
7η                                 38.725296
8η                                 38.564857
9η                                 38.975326
10η                               38.829242

Έτσι ως μέγιστο από τον γενετικό αλγόριθμο παίρνουμε το 38.975326 το οποίο είναι μικρότερο από το 39.05899.

Το συμπέρασμα της παραπάνω σύγκρισης είναι ότι στο συγκεκριμένο πρόβλημα ο απλός αλγόριθμος βρίσκει με μεγαλύτερη ακρίβεια το μέγιστο και πιο γρήγορα. Όμως ο γενετικός αλγόριθμος μπορεί να διαχειριστεί μεγαλύτερα προβλήματα και πιο γρήγορα από τον απλό. Αυτό μπορούμε να το καταλάβουμε από το γεγονός ότι ο συγκεκριμένος γενετικός αλγόριθμος εκτελεί 10000 γενιές και κρατάει 4 δεκαδικά ψηφία ενώ η κάθε εκτέλεση του διαρκεί μόνο λίγα δευτερόλεπτα. Ο απλός αλγόριθμος όταν κρατάει 4 δεκαδικά δεν μπορεί να τρέξει. Ακόμη στο συγκεκριμένο πρόβλημα το εύρος τιμών είναι πολύ μικρό και έτσι ο απλός αλγόριθμος δίνει σχετικά γρήγορα λύση. Τι θα γινόταν στην περίπτωση που θα είχαμε μεγαλύτερο εύρος τιμών; Η ταχύτητα του γενετικού αλγόριθμου δεν θα επηρεαζόταν γιατί χρησιμοποιεί πάντα σταθερό μέγεθος πληθυσμού. Έτσι συμπεραίνουμε πως σε μεγαλύτερα προβλήματα ο γενετικός αλγόριθμος θα έδινε γρηγορότερα λύση. Και τέλος, μπορούμε να παρατηρήσουμε πως το μέγιστο που έδωσε ο γενετικός αλγόριθμος δεν έχει σημαντική διαφορά από το μέγιστο που έδωσε ο απλός αλγόριθμος.

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου