Page 34 - sst-2022b

Comparative Analysis of Crossover Variants in μεγαλύτερος ο χρόνος σύγκλισης του αλγορίθμου.
Differential Evolution, 2007). Στην εκθετική Μεγάλες τιμές του F, ευνοούν την εξερεύνηση μεγάλων
διασταύρωση, γίνεται αρχικά, επιλογή ενός τυχαίου περιοχών του χώρου αναζήτησης λύσεων, όμως μπορεί
ακέραιου αριθμού στο διάστημα [1, … ]. Ο αριθμός κατά την εξερεύνηση να «υπερπηδήσουν» ένα καλό
αυτός θα αποτελέσει το σημείο εκκίνησης του βέλτιστο. Η τιμή λοιπόν του F πρέπει να είναι αρκετά
διανύσματος στόχου, από όπου θα ξεκινήσει η ανταλλαγή μικρή ώστε να επιτρέπει στον αλγόριθμο την επαρκή
γονιδίων με το μεταλλαγμένο διάνυσμα. Στη συνέχεια εξερεύνηση μικρών περιοχών (χωρίς μεγάλα άλματα), και
επιλέγεται ένας άλλος ακέραιος αριθμός στο διάστημα αρκετά μεγάλη ώστε να διατηρεί την ποικιλία των
[1, … ], που δείχνει τον αριθμό των διαδοχικών γονιδίων περιοχών που εξερευνά. Όσο το μέγεθος του πληθυσμού
(η μέτρηση γίνεται κυκλικά) που θα περιέχει το αυξάνεται, πρέπει αντίστοιχα να μειωθεί η τιμή του F.
δοκιμαστικό διάνυσμα από το μεταλλαγμένο. Μετά την Εμπειρικά αποτελέσματα δείχνουν πως μεγάλες τιμές των
επιλογή των παραμέτρων n και L, το δοκιμαστικό NP και F έχουν συχνά ως αποτέλεσμα την πρόωρη
διάνυσμα προκύπτει ως εξής (Zaharie, A Comparative σύγκλιση του αλγορίθμου (Engelbrecht, 2007).
Analysis of Crossover Variants in Differential Evolution, Ο συντελεστής διασταύρωσης CR επηρεάζει άμεσα
2007) : την ποικιλία του αλγορίθμου. Ο CR ελέγχει τον αριθμό
⃗
, , = 〈 〉 , 〈 + 1〉 , … . , 〈 + − 1〉 των στοιχείων ενός γονέα, ,που θα αλλάξουν. Όσο

, , = { μεγαλύτερη είναι η τιμή του CR, τόσο μεγαλύτερη θα είναι
, , ώ
Μετά τον τελεστή διασταύρωσης, το τελικό στάδιο της η ποικιλομορφία των ατόμων του νέου πληθυσμού. Η
μεθόδου είναι η επιλογή. Στη φάση της επιλογής, αύξηση του , συχνά οδηγεί σε ταχύτερη σύγκλιση, ενώ
υπολογίζεται η τιμή της αντικειμενικής συνάρτησης του η μείωση του αυξάνει την ευρωστία της αναζήτησης
δοκιμαστικού διανύσματος ( ) και η αντίστοιχη τιμή (Engelbrecht, 2007).
⃗
⃗
,
Οι παράμετροι ελέγχου που χρησιμοποιούνται στη
του διανύσματος γονέα ( ). Αν η τιμή του είναι μέθοδο ΔΕ εξαρτώνται σε μεγάλο βαθμό από το πρόβλημα
⃗
⃗
⃗
,
,
ίση ή καλύτερη από την τιμή του γονέα , τότε βελτιστοποίησης που καλείται να επιλύσει ο χρήστης. Οι
⃗
,
αντικαθιστά τον γονέα για την επόμενη γενιά. Αλλιώς, το περισσότερες εφαρμογές στρατηγικών της ΔΕ διατηρούν
διάνυσμα γονέας διατηρεί τη θέση του στον πληθυσμό για σταθερές τις παραμέτρους ελέγχου. Οι διαδικασίες
ακόμη μία τουλάχιστον γενιά. Η σχέση αυτή εξασφαλίζει αναζήτησης δοκιμής και λάθους που μπορούν
το γεγονός ότι η μέση καταλληλότητα του πληθυσμού δεν χρησιμοποιηθούν για την ρύθμιση των παραμέτρων

χειροτερεύει. Αν : → , η αντικειμενική συνάρτηση ελέγχου απαιτούν πολλές δοκιμές και πρόσθετο
που τίθεται προς βελτιστοποίηση, ο τελεστής επιλογής σε υπολογιστικό χρόνο.
πρόβλημα ελαχιστοποίησης μπορεί να εκφραστεί μέσω
της εξίσωσης (Gonuguntla, Mallipedi, & Veluvolu, 2015): Γ. Στρατηγικές των Price και Storn για τη μέθοδο ΔΕ- Ο
⃗
, ( ) ≤ ( ) συμβολισμός DE/x/y/z.
⃗
⃗
⃗
⃗
,
,
,
⃗ , +1 = { Η γενική σημειολογία DE/x/y/z, χρησιμοποιείται με
, ώ σκοπό τη διάκριση και τον χαρακτηρισμό των
⃗
,
Αν είναι γνωστό το ολικό βέλτιστο, όπως στην παραλλαγών της ΔΕ. Χρησιμοποιώντας αυτή τη
παρούσα μελέτη, ο αλγόριθμος τερματίζει με βάση την σημειολογία, το x αναφέρεται στη μέθοδο επιλογής του
τιμή της αντικειμενικής συνάρτησης. Ένα μέτρο διανύσματος γονέα, δηλαδή τη μέθοδο μετάλλαξης, το y
σφάλματος που εξαρτάται από τη διαφορά με το βέλτιστο υποδεικνύει τον αριθμό των διανυσματικών διαφορών και
μπορεί να χρησιμοποιηθεί για την ανίχνευση της το z υποδεικνύει τη στρατηγική διασταύρωσης των
σύγκλισης. Άλλα κριτήρια τερματισμού του αλγορίθμου διανυσμάτων. Οι Price και Storn πρότειναν 10
ΔΕ εξαρτώνται από τον αριθμό επαναλήψεων, τον διαφορετικές στρατηγικές της ΔΕ και μερικές
υπολογιστικό χρόνο, τιμές στατιστικών δεδομένων και τη κατευθυντήριες γραμμές για την εφαρμογή αυτών των
διασπορά του πληθυσμού. Επίσης τα κριτήρια στρατηγικών σε οποιοδήποτε πρόβλημα (Price & Storn,
τερματισμού μπορεί να είναι συνδυαστικά, εφόσον λόγω 2007). Οι στρατηγικές και ο αντίστοιχος τρόπος
της διαφορετικότητας των προβλημάτων υπολογισμού του μεταλλαγμένου διανύσματος είναι οι
βελτιστοποίησης, ο συνδυασμός διάφορων κριτηρίων εξής:
μπορεί να αποτελέσει πλεονέκτημα για την εξαγωγή • S1: DE/best/1/exp. Για την στρατηγική αυτή, το
καλών αποτελεσμάτων (Zielinski, Weitkemper, Laur, & διάνυσμα ⃗ με την «καλύτερη» τιμή της
Kammeyer, 2006). αντικειμενικής συνάρτησης στον τρέχοντα πληθυσμού
⃗
επιλέγεται ως διάνυσμα γονέας, δηλαδή = ⃗ +

( − )
⃗
⃗
Β. Παράμετροι ελέγχου • S2: DE/rand/1/exp, όπου = + ( − ).
1
2
Το μέγεθος του πληθυσμού NP επηρεάζει άμεσα την ⃗ ⃗ ⃗ ⃗ ⃗ 0 ⃗ 1 ⃗ 2
ικανότητα εξερεύνησης λύσεων του αλγορίθμου ΔΕ. Όσο Ισχύει ότι ≠ ≠ ≠ ∈ [1, … , ] και , ,
0
2
2
0
1
1
περισσότερα είναι τα άτομα που υπάρχουν στον τυχαία.
πληθυσμό, τόσο περισσότερα είναι τα διανύσματα • S3: : DE/rand-to-best/1/exp. Αυτή η στρατηγική
διαφοράς που είναι διαθέσιμα και άρα οι διευθύνσεις που συνδυάζει τις στρατηγικές rand και best για να
μπορούν να εξερευνηθούν. Εντούτοις, πρέπει να υπολογίσει το μεταλλαγμένο διάνυσμα ως εξής: =
⃗

σημειωθεί πως η ύπαρξη ενός αρκετά μεγάλου πληθυσμού ⃗ + (1 − ) + ( − ),
⃗
⃗
⃗
αυξάνει την υπολογιστική πολυπλοκότητα σε κάθε γενιά 1 2 3 και , ,
του αλγορίθμου. Πειραματικές μελέτες δείχνουν πως μία όπου ≠ ≠ ≠ ∈ [1, … , ] 1 2 3
1
3
2
κατάλληλη τιμή του μεγέθους του πληθυσμού είναι ≈ τυχαία επιλεγμένα. Το ∈ [0,1] ελέγχει την απληστία
10 , όπου D η διάσταση των διανυσμάτων-ατόμων του του τελεστή μετάλλαξης. Αν γ=0, τότε αυτή η
πληθυσμού (Storn & Price, 1997). στρατηγική ταυτίζεται με την DE/rand/1/exp. Αν γ=1,
Ο συντελεστής μετάλλαξης, ∈ (0, ∞), ρυθμίζει το τότε η στρατηγική ταυτίζεται με την DE/best/1/exp.
εύρος των διανυσμάτων διαφοράς ( − ). Όσο • S4: DE/best/2/exp. Για τη στρατηγική αυτή
⃗
⃗
3
2
μικρότερη είναι η τιμή του F, τόσο μικρότερα είναι τα χρησιμοποιούνται δύο διανύσματα διαφοράς ως εξής:
μεγέθη βήματος του τελεστή μετάλλαξης και άρα τόσο = ⃗ + [( − ) + ( − )], όπου ≠
⃗
⃗
⃗
⃗
⃗

2
1
4
3
67