Τρίτη, 18 Νοεμβρίου 2014

Χρήση γενετικού αλγόριθμου για την εύρεση του μεγίστου μίας συνάρτησης δύο μεταβλητών

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

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

Ο κώδικας που επιλύει το παραπάνω πρόβλημα είναι ο ακόλουθος:

Private Sub Command1_Click()

'δήλωση των μεταβλητών
Dim xk(20) As Double, ev(20) As Double, p(20) As Double, m(20) As Double, z(20) As Double, B() As Integer, val1(20) As Double, y1() As Double, y2() As Double
Dim val2(20) As Double, A() As Integer, cross(20) As Double, c() As Integer, id(20) As Integer, xs() As Integer, xf() As Integer, random() As Double
Dim a1v As Double, b1v As Double, a2v As Double, b2v As Double, q As Integer, pc As Double, pm As Double, valn1(20) As Double, valn2(20) As Double

'εισαγωγή των δεδομένων από την φόρμα
a1v = Text1.Text
b1v = Text2.Text
q = Text3.Text
a2v = Text4.Text
b2v = Text5.Text
pc = Text6.Text
pm = Text7.Text

'υπολογισμός του μεγέθους του χρωμοσώματος
Do Until 2 ^ n1 > (b1v - a1v) * (10 ^ q)
n1 = n1 + 1
Loop

Do Until 2 ^ n2 > (b2v - a2v) * (10 ^ q)
n2 = n2 + 1
Loop

'επαναδήλωση του μεγέθους ορισμένων πινάκων
ReDim B(20, n1 + n2) As Integer, y1(n1) As Double, y2(n2) As Double, A(20, n1 + n2) As Integer
ReDim c(20, n1 + n2) As Integer, xs(20, n1 + n2) As Integer, xf(20, n1 + n2) As Integer, random(20, n1 + n2) As Double

'δημιουργία τυχαίων χρωμοσωμάτων (αρχικοποίηση)
For i = 1 To 20
For j = 1 To n1 + n2
A(i, j) = Int(Rnd + 0.5)
Next j
Next i

'έναρξη των επαναλήψεων για 10000 γενιές
For gen = 1 To 10000

'μετατροπή των χρωμοσωμάτων στο δεκαδικό σύστημα
For i = 1 To 20
valn1(i) = 0
For j = 1 To n1
valn1(i) = valn1(i) + A(i, j) * (2 ^ (n1 - j))
val1(i) = a1v + valn1(i) * (b1v - a1v) / (2 ^ n1 - 1)
Next j
Next i

For i = 1 To 20
valn2(i) = 0
For j = n1 + 1 To n1 + n2
valn2(i) = valn2(i) + A(i, j) * (2 ^ (n2 + n1 - j))
val2(i) = a2v + valn2(i) * (b2v - a2v) / (2 ^ n2 - 1)
Next j
Next i

'υπολογισμός της απόδοσης των χρωμοσωμάτων βάση της αντικειμενικής συνάρτησης
For i = 1 To 20
ev(i) = 5 - (val1(i)) ^ 2 - (val2(i)) ^ 2
F = F + ev(i)
Next i

'επιλογή του χρωμοσώματος που έχει προσαρμοστεί καλύτερα στο περιβάλλον του
For i = 1 To 20
If ev(i) > final Then
final = ev(i)
End If
Next i

'υπολογισμός της απόδοσης του κάθε χρωμοσώματος
For i = 1 To 20
p(i) = ev(i) / F
Next i

'δημιουργία αθροιστικών πιθανοτήτων και 20 τυχαίων αριθμών στο διάστημα [0,1]
For i = 1 To 20
m(i) = m(i - 1) + p(i)
z(i) = Rnd
Next i

'επιλογή των χρωμοσωμάτων βάση της απόδοσης τους
For i = 1 To 20
For j = 1 To 20
If z(i) < m(j) And z(i) > m(j - 1) Then
For k = 1 To n1 + n2
B(i, k) = A(j, k)
Next k
End If
Next j
Next i

'επιλογή χρωμοσωμάτων για την διασταύρωση (crossover)
kn = 0
For i = 1 To 20
cross(i) = Rnd
If cross(i) < pc Then
kn = kn + 1
For j = 1 To n1 + n2
c(kn, j) = A(i, j)
id(kn) = i
Next j
End If
Next i

'αν ο αριθμός των χρωμοσωμάτων που επιλέχθηκε είναι περιττός απορρίπτουμε το τελευταίο
If kn Mod 2 = 1 Then
kn = kn - 1
End If

'ανταλλαγή των γονιδίων των χρωμοσωμάτων
For i = 1 To kn / 2
pos = Int(Rnd * (n1 + n2 - 2) + 1)
For j = 1 To pos
xf(i, j) = c(i, j)
xs(i, j) = c(i + kn / 2, j)
Next j
Next i

For i = 1 To kn / 2
For j = 1 To pos
c(i, j) = xs(i, j)
c(i + kn / 2, j) = xf(i, j)
Next j
Next i

For i = 1 To kn
For j = 1 To n1 + n2
A(id(i), j) = c(i, j)
Next j
Next i

'δημιουργία τυχαίων αριθμών για την μετάλλαξη των γονιδίων (mutation)
For i = 1 To 20
For j = 1 To n1 + n2
random(i, j) = Rnd
Next j
Next i

'μετάλλαξη των γονιδίων
For i = 1 To 20
For j = 1 To n1 + n2
If random(i, j) < pm Then
If A(i, j) = 1 Then
A(i, j) = 0
ElseIf A(i, j) = 0 Then
A(i, j) = 1
End If
End If
Next j
Next i

'ξεκινάει η επόμενη γενιά
Next gen

'εκτύπωση του καλύτερου χρωμοσώματος από όλες τις γενιές στην φόρμα
Text8.Text = final

End Sub

Τα στοιχεία που πρέπει να εισαχθούν μέσα στον κώδικα, θα εισαχθούν μέσω μίας φόρμας (εικόνα 1).
εικόνα 1, η φόρμα εισαγωγής των στοιχείων στον κώδικα.
Στην φόρμα a1 και b1 είναι τα άκρα του διαστήματος τιμών που παίρνει το x, a2 και b2 είναι τα άκρα του διαστήματος τιμών που παίρνει το y, q είναι το πλήθος των δεκαδικών που θέλουμε να κρατήσουμε, pc είναι η πιθανότητα διασταύρωσης και pm είναι η πιθανότητα μετάλλαξης. Όταν συμπληρώσουμε τα παραπάνω πεδία και πατήσουμε το κουμπί "resolve" στο πεδίο maxima θα πάρουμε την τιμή του μέγιστου της συνάρτησης στο εύρος τιμών που επιλέξαμε. Έτσι συμπληρώνουμε τα απαραίτητα πεδία (εικόνα 2) και κάνοντας επίλυση παίρνουμε την τιμή του μεγίστου (εικόνα 3).
εικόνα 2, η φόρμα συμπληρωμένη με τα απαραίτητα στοιχεία.
εικόνα 3, φαίνεται η τιμή του μεγίστου της συνάρτησης.
Οπότε μέσω του γενετικού αλγόριθμου βρίσκουμε ότι το μέγιστο στην συγκεκριμένη περιοχή του χώρου είναι 4.999997 . Αυτό μπορούμε να το επαληθεύσουμε καθώς είναι γνωστό πως το μέγιστο της f(x,y) είναι το 5 στην συγκεκριμένη περιοχή.

Η ανάρτηση "Γενετικοί αλγόριθμοι": http://fromsciencetoengineering.blogspot.gr/2014/11/blog-post.html

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

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