Nested Differential Evolution for Τwo-level optimization problems
Creators: name: Αντωνίου, Μαργαρίτα Χριστόφορου
Publisher: name: Aristotle University of Thessaloniki
Year: 2020
Subjects: Εξελεκτικοί Αλγόριθμοι
Διεπίπεδα προβλήματα βελτιστοποίησης
Αλγόριθμος Διαφορικής Εξέλιξης
Evolutionary Algorithm
Bilevel/Two-Level optimization
Differential Evolution

description: Πολύ συχνά στην καθημερινή ζωή, η βέλτιστη λύση ενός προβλήματος εξαρτάται σε μεγάλο βαθμό από την ανταπόκριση και βέλτιστη λύση ενός άλλου προβλήματος, σχηματίζοντας ένα πρόβλημα βελτιστοποίησης δύο επιπέδων (διεπίπεδη βελτιστοποίηση). Παραδέιγματα τέτοιων προβλημάτων μπορεί να συναντήσει κανείς σε διάφορους τομείς όπως αυτόν των μεταφορών, των οικονομικών, σε προβλήματα μηχανικών αλλά και σε προβλήματα τεχνικών υπολογιστικής ευφυίας. Η βελτιστοποίηση ενός προβλήματος δύο επιπέδων στοχεύει στην επίτευξη της βέλτιστης λύσης ενός (ανώτερου ιεραρχικά) επιπέδου, λαμβάνοντας επίσης υπόψη τις βέλτιστες τιμές ενός δεύτερου (χαμηλότερου) επιπέδου. Το πρόβλημα εισάγει πολλές προκλήσεις, επειδή τις περισσότερες φορές δεν ακολουθεί απλοποιημένες ιδιότητες όπως κυρτότητα ή συνέχεια των συναρτήσεων του. Εχει επίσης αποδειχθεί ότι αποτελεί πρόβλημα κλάσης πολυπλοκότητας NP, που σημαίνει ότι δεν μπορεί να επιλυθεί με κάποιον αλγόριθμο ενός πολυωνυμικού χρόνου. Με τον όρο εξελικτικοί αλγόριθμοι (ΕΑ) χαρακτηρίζονται οι αλγόριθμοι αναζήτησης που είναι βασισμένοι στους μηχανισμούς της φύσης και της βιολογικής εξέλιξης για την επίλυση προβλημάτων βελτιστοποίησης. Οι αλγόριθμοι αυτοί μιμούνται τις διαδικασίες φυσικής εξέλιξης που επιτρέπουν στους πληθυσμούς ειδών να προσαρμοστούν στο περιβάλλον τους, όπως η γενετική κληρονομιά και η επιβίωση του πιο κατάλληλου. Η βασική τους ιδέα στηρίζεται στις αρχές προσομοίωσης της εξέλιξης μέσω των διαδικασιών της επιλογής, της αναπραγωγής και της μετάλλαξης. Οι εξελικτικοί αλγόριθμοι είναι πολύ γνωστοί για την καλή τους απόδοση σε σύνθετα και μη γραμμικά προβλήματα βελτιστοποίησης, καθώς δεν υπάρχει ανάγκη για μαθηματικές παραδοχές σχετικά με τη φύση του προβλήματος. Ο αλγοριθμος Διαφορικης Εξελιξης είναι ένας γρήγορος και εύκολος στη χρήση εξελικτικός αλγόριθμος. Η βασική στρατηγική εφαρμόζει τη διαφορά δύο τυχαία επιλεγμένων διανυσμάτων ως πηγή για διαφοροποίηση ενός τρίτου διανύσματος. Αντικείμενο της παρούσας μεταπτυχιακής εργασίας είναι η μελέτη και επίλυση γενικών προβλημάτων δυο επιπέδων με τη χρήση του αλγόριθμου Διαφορικής Εξέλιξης. Σε αυτή τη εργασία, εφαρμόζεται ένας ένθετος εξελικτικός αλγόριθμος για την επίλυση γενικών διεπίπεδων προβλημάτων. Και στα δύο επίπεδα εφαρμόζεται ο αλγόριθμος Διαφορικής Εξέλιξης. Η απόδοση του ένθετου αλγορίθμου αξιολογείται με την επίλυση 4 δισδιάστατων συναρτήσεων δοκιμής που λαμβάνονται από τη βιβλιογραφία.
description: Very often in real-life, an optimal solution of a decision maker depends heavily on the response of another decision maker, formulating a two- level (bilevel) optimization problem. Example of such problems can be found in various domains such as in transportation, economics and engineering. The optimization of a two-level problem aims to achieve the optimum solution of the one (upper) level, taking into consideration the optimal second (lower) level values too. The problem introduces many challenges, because it is sometimes not following simplified properties like convexity or continuity and it is proved that is NP-hard. Evolutionary algorithms (EAs) are a nature-inspired population based search method for solving optimization problems, by applying principles of natural evolution that allow populations of species to adapt to their environment, like the genetic inheritance and also the survival of the fittest. Evolutionary algorithms are very well-known to perform well in complex and non-linear optimization problems, as there is no need for any mathematical assumptions about the nature of the problem. In this thesis, a nested evolutionary algorithm is implemented to solve general unconstrained bilevel problems. In both levels the Differential Evolution algorithm is implemented, a very popular EA for global optimization. The performance of the nested algorithm is evaluated by solving four 2-dimensional test-problems taken from literature.