Page 33 - sst-2022b

Ολική Βελτιστοποίηση: Μέθοδος της

Διαφορικής Εξέλιξης και Παραλλαγές

Ευγενία Μαρία Γούλα Δημήτριος Σωτηρόπουλος

Εκπαιδευτικός Ι.Ε και Μεταπτυχιακή Φοιτήτρια Επίκ. Καθηγητής, Παν/μιο Πελοποννήσου και
ΜΣΜ/ΣΘΕΤ, ΕΑΠ Μέλος ΣΕΠ ΜΣΜ/ΣΘΕΤ, ΕΑΠ
dg.sotiropoulos@uop.gr, dgs@eap.gr
eugeniagoula@yahoo.com, std115701@ac.eap.gr

Περίληψη – Ο αλγόριθμος Διαφορικής Εξέλιξης (ΔΕ) του αλγορίθμου. Οι άλλες δύο παράμετροι που θα πρέπει
αποτελεί μία σύγχρονη μεθευρετική μέθοδο βελτιστοποίησης να ορισθούν εξ αρχής είναι ο συντελεστής μετάλλαξης ή
με ευρύ φάσμα εφαρμογών. Η παρούσα μελέτη έχει ως διασποράς F και ο συντελεστής διασταύρωσης CR. Στη
αντικείμενο έρευνας την ολική βελτιστοποίηση συνέχεια γίνεται η αρχικοποίηση του πληθυσμού. Για την
προβλημάτων μη γραμμικών συναρτήσεων με τη χρήση πρώτη γενιά (g=0) επιλέγεται με τυχαίο τρόπο ένας
διαφόρων παραλλαγών της μεθόδου ΔΕ. Διεξάγονται αρχικός διανυσματικός πληθυσμός NP λύσεων έτσι ώστε
να καλύπτεται ολόκληρη η επιτρεπόμενη περιοχή των
πειράματα εφαρμογής διαφορετικών στρατηγικών της μεταβλητών με τον καλύτερο δυνατό τρόπο.
μεθόδου ΔΕ σε πενήντα προβλήματα ελαχιστοποίησης με Συγκεκριμένα, η αρχικοποίηση του πληθυσμού της j-
γνωστό ολικό ελάχιστο (test problems). Στο πλαίσιο των οστής μεταβλητής του i-οστού διανύσματος διάστασης D
πειραμάτων γίνονται ρυθμίσεις και μεταβολές στις γίνεται συχνότερα ως εξής (Price, Storn, & Lampinen,
παραμέτρους ελέγχου του αλγορίθμου με σκοπό να επιτευχθεί 2005):
μία συγκριτική μελέτη που αφορά την απόδοση των = (0,1) ∙ ( − ) +
διαφορετικών στρατηγικών καθώς και αποτελέσματα που , ,0 , , ,
αναφέρονται σε δημοσιευμένες μελέτες των Lampinen & όπου j∈ {1, … , }, ∈ {1, … , }, (0,1) είναι μία

Zelinka (2000) και της Zaharie (2002, 2007). γεννήτρια τυχαίων αριθμών στο διάστημα [0,1) για κάθε
μεταβλητή , ,0 και , τα άνω και κάτω φράγματα
,
,
Λέξεις-Κλειδιά: Βελτιστοποίηση, Διαφορική Εξέλιξη, αντίστοιχα για κάθε μεταβλητή .

Παράμετροι Ελέγχου Αφού αρχικοποιηθεί, η ΔΕ μεταλλάσσει και
αναδιαμορφώνει τον πληθυσμό ώστε να παράγει NP
I. ΕΙΣΑΓΩΓΗ δοκιμαστικά διανύσματα. Συγκεκριμένα, ο τελεστής
μετάλλαξης F εφαρμόζεται σε κάθε διάνυσμα στόχο
Οι Storn και Price (Storn & Price, 1997) ανέπτυξαν την (γονέας) του τρέχοντα πληθυσμού προσθέτοντας μία
μέθοδο Διαφορικής Εξέλιξης (ΔΕ), έναν στοχαστικό σταθμισμένη διαφορά τυχαία επιλεγμένων διανυσμάτων
εξελικτικό αλγόριθμο βελτιστοποίησης άμεσης ⃗ και ⃗ σε ένα τρίτο τυχαία επιλεγμένο διάνυσμα
2 ,
αναζήτησης, με απλή δομή και καλή απόδοση σε μεγάλη 1 , , το οποίο ονομάζεται διάνυσμα βάσης.
ποικιλία προβλημάτων. Η μέθοδος ΔΕ, όπως όλοι οι ⃗ 0 ,
Συγκεκριμένα, για κάθε γονέα, , παράγεται ένα
εξελικτικοί αλγόριθμοι, βασίζεται στον πληθυσμό για την ⃗ ,
⃗
επίλυση προβλημάτων ολικής βελτιστοποίησης. Τα μέλη μεταλλαγμένο διάνυσμα ως εξής (Price, Storn, &
,
του πληθυσμού (άτομα) είναι διανύσματα τα οποία Lampinen, 2005):
αποτελούνται από μεταβλητές, Η βασική ιδέα της μεθόδου ⃗ , = ⃗ 0 , + ∙ ( ⃗ 1 , − ⃗ 2 , ), όπου , ∈
2
1
έγκειται στη χρήση διανυσματικών διαφορών για την {1, … , } και ≠ ≠ ≠ .
1
0
2
διατάραξη (perturbation) των διανυσμάτων του Μετά τη φάση της μετάλλαξης η μέθοδος ΔΕ
πληθυσμού με σκοπό τη δημιουργία νέας γενιάς. χρησιμοποιεί τον τελεστή της διασταύρωσης CR, ο οποίος
Τα βασικά πλεονεκτήματα της μεθόδου είναι η εφαρμόζεται σε κάθε ζεύγος διανύσματος γονέα και
⃗
,
ευρωστία της, η απλή τεχνική της και η ταχύτητα του αντίστοιχου μεταλλαγμένου διανύσματος ώστε να
⃗
σύγκλισης, τα οποία την καθιστούν ένα χρήσιμο ,
εργαλείο ολικής βελτιστοποίησης. Η απλότητα και δημιουργηθεί ένας πληθυσμός ⃗⃗⃗, απογόνων με

⃗
⃗
ευκολία στη χρήση του αλγορίθμου σε σχέση με άλλους δοκιμαστικά διανύσματα . Κάθε δοκιμαστικό
,
εξελικτικούς αλγόριθμους, οφείλεται κυρίως στο γεγονός διάνυσμα (απόγονος) κατασκευάζεται με ανάμειξη
⃗
ότι βασίζεται στη χρήση λιγότερων παραμέτρων ελέγχου, μεταβλητών (γονιδίων) του τρέχοντος διανύσματος
,
οι οποίες όμως πρέπει να επιλεχθούν με ιδιαίτερη προσοχή και μεταβλητών του που έχει παραχθεί από τη
⃗
,
ώστε να επιτευχθεί αποδοτική σύγκλιση. Πειραματικά μετάλλαξη. Υπάρχουν δύο κύριες παραλλαγές
αποτελέσματα έχουν δείξει πως η ΔΕ αποφέρει πολύ καλά διασταύρωσης της ΔΕ: η διωνυμική και η εκθετική. Στην
αποτελέσματα είτε στην ανεύρεση βέλτιστης λύσης, είτε διωνυμική διασταύρωση κάθε μεταβλητή , , του
στην ταχύτητα σύγκλισης, είτε και στα δύο (Price, Storn, διανύσματος επιλέγεται τυχαία από τον γονέα και το
⃗
⃗
,
& Lampinen, 2005). μεταλλαγμένο διάνυσμα και ορίζεται με την ακόλουθη
II. ΜΕΘΟΔΟΛΟΓΙΑ εξίσωση (Gonuguntla, Mallipedi, & Veluvolu, 2015):
, , , (0,1) ≤ ή =

Α. Μεθοδολογία του κλασικού αλγορίθμου ΔΕ , , = { , , , ώ
Η συνθήκη (0,1) ≤ ή = , όπου

Στην έναρξη υλοποίησης της ΔΕ είναι απαραίτητο να ένας τυχαίος δείκτης στο διάστημα [1,…,D], εξασφαλίζει
ορισθούν οι παράμετροι ελέγχου της μεθόδου. Η πρώτη το γεγονός ότι τουλάχιστον ένα γονίδιο του απογόνου, θα
παράμετρος είναι το μέγεθος NP του πληθυσμού, το οποίο προέλθει από το μεταλλαγμένο διάνυσμα (Zaharie, A
θα παραμείνει σταθερό σε όλη τη διάρκεια υλοποίησης
66