Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων
Η διαδικασία της βελτιστοποίησης αποτελεί ζήτημα ζωτικής σημασίας σε όλους τους κλάδους των επιστημών και της τεχνολογίας. Κάποιες από τις εφαρμογές της είναι η μεγιστοποίηση του κέρδους αλλά και η ελαχιστοποίηση του κόστους παραγωγής κάποιας επιχείρησης, η εύρεση βέλτιστης τροχιάς κάποιου οχήματος...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2016
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/9337 |
| id |
nemertes-10889-9337 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Βελτιστοποίηση Γενετικοί αλγόριθμοι Σημεία pivot Optimization Genetic algorithms Pivot points 519.62 |
| spellingShingle |
Βελτιστοποίηση Γενετικοί αλγόριθμοι Σημεία pivot Optimization Genetic algorithms Pivot points 519.62 Παπανικολάου, Αθανασία Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| description |
Η διαδικασία της βελτιστοποίησης αποτελεί ζήτημα ζωτικής σημασίας σε όλους τους κλάδους των επιστημών και της τεχνολογίας. Κάποιες από τις εφαρμογές της είναι η μεγιστοποίηση του κέρδους αλλά και η ελαχιστοποίηση του κόστους παραγωγής κάποιας επιχείρησης, η εύρεση βέλτιστης τροχιάς κάποιου οχήματος ή αντικειμένου κ.α.. Στα προβλήματα βελτιστοποίησης, κατασκευάζεται μία συνάρτηση-εκπρόσωπος του προβλήματος, η οποία ονομάζεται αντικειμενική συνάρτηση και χρησιμοποιείται ως μέτρο σύγκρισης των πιθανών λύσεων. Σκοπός μας είναι να εντοπίσουμε τις τιμές των μεταβλητών στις οποίες η αντικειμενική συνάρτησή λαμβάνει την μέγιστη ή ελάχιστη τιμή, σε ένα πεδίο ορισμού.
Οι μέθοδοι γραμμικής αναζήτησης και οι μέθοδοι περιοχών εμπιστοσύνης αποτελούν τους κυριότερους εκπροσώπους των ντετερμινιστικών μεθόδων βελτιστοποίησης. Η βασική φιλοσοφία των μεθόδων γραμμικής αναζήτησης είναι η επιλογή κατάλληλης κατεύθυνσης κίνησης και στη συνέχεια μήκους βήματος έτσι ώστε η επόμενη τιμή της αντικειμενικής συνάρτησης να είναι μικρότερη (αν αντιμετωπίζουμε πρόβλημα ελαχιστοποίησης) από την προηγούμενη. Στις μεθόδους περιοχής εμπιστοσύνης αναζητούμε ένα τετραγωνικό μοντέλο το οποίο εμπιστευόμαστε ότι αντιπροσωπεύει επαρκώς την αντικειμενική συνάρτηση σε μία γειτονιά. Οπότε, σκοπός μας είναι η βελτιστοποίηση του μοντέλου-αντιπροσώπου.
Στην κατηγορία των στοχαστικών μεθόδων βελτιστοποίησης ανήκουν οι Γενετικοί Αλγόριθμοι (ΓΑ) και αποτελούν παρακλάδι των Εξελικτικών Αλγορίθμων. Η βασική ιδέα των ΓΑ είναι η μίμηση των διαδικασιών της εξέλιξης που συναντάμε στην φύση. Σύμφωνα με την Θεωρία Εξέλιξης των Ειδών του Δαρβίνου στη φύση επιβιώνει ο πιο δυνατός οργανισμός, οπότε, καθώς το φυσικό περιβάλλον μεταβάλλεται, οι οργανισμοί θα πρέπει να εξελίσσονται συνεχώς προκειμένου να επιβιώσουν. Βασισμένοι, λοιπόν σε αυτή την ιδέα, οι ΓΑ, διατηρούν ένα πληθυσμό πιθανών λύσεων ο οποίος σε κάθε επανάληψη του αλγορίθμου βελτιώνεται, με την έννοια ότι τα άτομα που τον αποτελούν πλησιάζουν όλο και περισσότερο στη λύση του προβλήματος.
Στην παρούσα διπλωματική εργασία θα ξεκινήσουμε κάνοντας μία σύντομη ανάλυση των μεθόδων γραμμικής αναζήτησης καθώς και των μεθόδων περιοχών εμπιστοσύνης (Κεφάλαιο 1). Στη συνέχεια, θα μελετήσουμε τους Γενετικούς Αλγόριθμους (Κεφάλαιο 2) και θα προτείνουμε μία παραλλαγή αυτών για την βελτιστοποίηση συναρτήσεων (Κεφάλαιο 3). Η διαφορά αυτής της νέας μεθόδου, έναντι των κλασσικών ΓΑ, έγκειται στην αρχικοποίηση του πληθυσμού για την εφαρμογή του αλγορίθμου. Τα σημεία που δίνουμε ως είσοδο στον ΓΑ (pivot σημεία) επιλέγονται με μία συγκεκριμένη και ιδιαιτέρως σημαντική ιδιότητα, την quasi – solution property, πράγμα το οποίο φαίνεται να βελτιώνει την απόδοση του κλασσικού ΓΑ. Η μέθοδος δοκιμάστηκε σε κάποια χαρακτηριστικά παραδείγματα και τα προκαταρκτικά αποτελέσματα που προέκυψαν είναι ενθαρρυντικά. Περαιτέρω έρευνα αξίζει να γίνει σε μία μελλοντική εργασία. |
| author2 |
Γράψα, Θεοδούλα |
| author_facet |
Γράψα, Θεοδούλα Παπανικολάου, Αθανασία |
| format |
Thesis |
| author |
Παπανικολάου, Αθανασία |
| author_sort |
Παπανικολάου, Αθανασία |
| title |
Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| title_short |
Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| title_full |
Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| title_fullStr |
Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| title_full_unstemmed |
Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| title_sort |
μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων |
| publishDate |
2016 |
| url |
http://hdl.handle.net/10889/9337 |
| work_keys_str_mv |
AT papanikolaouathanasia miaapotelesmatikoterēarchikopoiēsētouplēthysmoutōngenetikōnalgorithmōngiabeltistopoiēsēsynartēseōn AT papanikolaouathanasia amoreeffectiveinitializationofgeneticalgorithmpopulationforfunctionoptimization |
| _version_ |
1771297299729743872 |
| spelling |
nemertes-10889-93372022-09-05T20:19:11Z Μια αποτελεσματικότερη αρχικοποίηση του πληθυσμού των γενετικών αλγορίθμων για βελτιστοποίηση συναρτήσεων A more effective initialization of genetic algorithm population for function optimization Παπανικολάου, Αθανασία Γράψα, Θεοδούλα Γράψα, Θεοδούλα Κωτσιαντής, Σωτήρης Ανδρουλάκης, Γεώργιος Papanikolaou, Athanasia Βελτιστοποίηση Γενετικοί αλγόριθμοι Σημεία pivot Optimization Genetic algorithms Pivot points 519.62 Η διαδικασία της βελτιστοποίησης αποτελεί ζήτημα ζωτικής σημασίας σε όλους τους κλάδους των επιστημών και της τεχνολογίας. Κάποιες από τις εφαρμογές της είναι η μεγιστοποίηση του κέρδους αλλά και η ελαχιστοποίηση του κόστους παραγωγής κάποιας επιχείρησης, η εύρεση βέλτιστης τροχιάς κάποιου οχήματος ή αντικειμένου κ.α.. Στα προβλήματα βελτιστοποίησης, κατασκευάζεται μία συνάρτηση-εκπρόσωπος του προβλήματος, η οποία ονομάζεται αντικειμενική συνάρτηση και χρησιμοποιείται ως μέτρο σύγκρισης των πιθανών λύσεων. Σκοπός μας είναι να εντοπίσουμε τις τιμές των μεταβλητών στις οποίες η αντικειμενική συνάρτησή λαμβάνει την μέγιστη ή ελάχιστη τιμή, σε ένα πεδίο ορισμού. Οι μέθοδοι γραμμικής αναζήτησης και οι μέθοδοι περιοχών εμπιστοσύνης αποτελούν τους κυριότερους εκπροσώπους των ντετερμινιστικών μεθόδων βελτιστοποίησης. Η βασική φιλοσοφία των μεθόδων γραμμικής αναζήτησης είναι η επιλογή κατάλληλης κατεύθυνσης κίνησης και στη συνέχεια μήκους βήματος έτσι ώστε η επόμενη τιμή της αντικειμενικής συνάρτησης να είναι μικρότερη (αν αντιμετωπίζουμε πρόβλημα ελαχιστοποίησης) από την προηγούμενη. Στις μεθόδους περιοχής εμπιστοσύνης αναζητούμε ένα τετραγωνικό μοντέλο το οποίο εμπιστευόμαστε ότι αντιπροσωπεύει επαρκώς την αντικειμενική συνάρτηση σε μία γειτονιά. Οπότε, σκοπός μας είναι η βελτιστοποίηση του μοντέλου-αντιπροσώπου. Στην κατηγορία των στοχαστικών μεθόδων βελτιστοποίησης ανήκουν οι Γενετικοί Αλγόριθμοι (ΓΑ) και αποτελούν παρακλάδι των Εξελικτικών Αλγορίθμων. Η βασική ιδέα των ΓΑ είναι η μίμηση των διαδικασιών της εξέλιξης που συναντάμε στην φύση. Σύμφωνα με την Θεωρία Εξέλιξης των Ειδών του Δαρβίνου στη φύση επιβιώνει ο πιο δυνατός οργανισμός, οπότε, καθώς το φυσικό περιβάλλον μεταβάλλεται, οι οργανισμοί θα πρέπει να εξελίσσονται συνεχώς προκειμένου να επιβιώσουν. Βασισμένοι, λοιπόν σε αυτή την ιδέα, οι ΓΑ, διατηρούν ένα πληθυσμό πιθανών λύσεων ο οποίος σε κάθε επανάληψη του αλγορίθμου βελτιώνεται, με την έννοια ότι τα άτομα που τον αποτελούν πλησιάζουν όλο και περισσότερο στη λύση του προβλήματος. Στην παρούσα διπλωματική εργασία θα ξεκινήσουμε κάνοντας μία σύντομη ανάλυση των μεθόδων γραμμικής αναζήτησης καθώς και των μεθόδων περιοχών εμπιστοσύνης (Κεφάλαιο 1). Στη συνέχεια, θα μελετήσουμε τους Γενετικούς Αλγόριθμους (Κεφάλαιο 2) και θα προτείνουμε μία παραλλαγή αυτών για την βελτιστοποίηση συναρτήσεων (Κεφάλαιο 3). Η διαφορά αυτής της νέας μεθόδου, έναντι των κλασσικών ΓΑ, έγκειται στην αρχικοποίηση του πληθυσμού για την εφαρμογή του αλγορίθμου. Τα σημεία που δίνουμε ως είσοδο στον ΓΑ (pivot σημεία) επιλέγονται με μία συγκεκριμένη και ιδιαιτέρως σημαντική ιδιότητα, την quasi – solution property, πράγμα το οποίο φαίνεται να βελτιώνει την απόδοση του κλασσικού ΓΑ. Η μέθοδος δοκιμάστηκε σε κάποια χαρακτηριστικά παραδείγματα και τα προκαταρκτικά αποτελέσματα που προέκυψαν είναι ενθαρρυντικά. Περαιτέρω έρευνα αξίζει να γίνει σε μία μελλοντική εργασία. The process of optimization is vital in all fields of science and technology. Some of its applications are to maximize profit and minimize the production cost of some businesses, to find the optimal trajectory of a vehicle or object, etc. In optimization problems, a function-representative of the problem is created, which is called objective function and is used in evaluating possible solutions. Our aim is to identify the values of the variables in which the objective function reaches its maximum or minimum value in a domain. The main representatives of deterministic optimization methods are linear search methods and trust region methods. The basic philosophy of a linear search method is the choice of an appropriate search direction followed by the choice of a step length so that the next value of the objective function is smaller (if facing a minimization problem) than its predecessor. In a trust region method we seek for a square model that we trust to adequately represent the objective function in a neighborhood. So, our goal is to optimize the model-representative. Genetic Algorithms (GA) are stochastic optimization methods and an offshoot of Evolutionary Algorithms. The main idea of a GA is the imitation of the development processes we encounter in nature. According to the Darwinian Evolution of Species, in nature, the fittest organism survives. Consequently, as the environment changes, organisms must continually evolve in order to survive. Based on this idea, a GA preserves a population of potential solutions which, in each iteration of the algorithm, is improved, meaning that the individuals that make up the population are approaching the problems’ solution. In the present master thesis we will begin by briefly analyzing linear search methods and trust region methods. Following, we will study Genetic Algorithms and also recommend one alteration of these for function optimization. The difference of this new method, that will be called pivot GA, compared to the classic GA, lies in the initialization of the population in order to implement the algorithm. Pivot GA is initialized by individuals (pivot points) that hold a particular and extremely important property, the quasi -solution property, which seems to improve the performance of the classic GA. The method was tested on some characteristic examples and preliminary results are promising. Further research should be done in future work. 2016-06-09T12:45:58Z 2016-06-09T12:45:58Z 2015-09-30 Thesis http://hdl.handle.net/10889/9337 gr 0 application/pdf |
