Μιμιδικοί και εξελικτικοί αλγόριθμοι στην αριθμητική βελτιστοποίηση και στη μη γραμμική δυναμική

Abstract

Τhe main topic of this thesis involved the development of new efficient Evolutionary Algorithms and their application on interesting scientific and engineering problems. There were two essential objectives. The first one was the investigation of further improvement on the performance of Evolutionary Algorithms by introducing new Memetic Algorithms. These are population-based heuristic search algorithms, designed to perform global optimization by combining evolutionary adaptation with individual learning within a lifetime. The second objective was the application of Evolutionary and Memetic Algorithms to problems of nonlinear dynamics. In the following paragraphs, the contributions of the thesis per objective are roughly described. Regarding the development of new Memetic Algorithms, approaches that combine Particle Swarm Optimization with local search methods were developed. Also, a criterion based on Shannon’s entropy was introduced in order to decide at which stages of the Memetic Algorithm the local search will be applied. All the new schemes were applied on a variety of optimization problems and compared with the standard Particle Swarm Optimization. Specifically, they were applied to global optimization problems with constraints, unconstrained optimization, integer and minimax programming. In the majority of these test problems, Memetic Algorithms significantly outperformed Particle Swarm Optimization or had statistically equivalent behavior in terms of the required number of function evaluations to reach the error-goal, while they exhibited also a higher number of successful experiments, implying their robustness. The proposed Memetic Algorithms were also used to improve Fuzzy Cognitive Maps, which are simulation tools for modeling and studying complex systems. The learning procedure of Fuzzy Cognitive Maps can be reduced to a global optimization problem. Memetic Algorithms were applied for learning in 4 different models. These models have been used to model two control problems, one for the control of a chemical process in industry and another for a heat exchanger system, one medical problem about radiation therapy, and one for the study of pollution in an ecological industrial park. Also, in these problems, a new methodology was proposed regarding the design of Memetic Algorithms, and more specifically for the adaptive determination of the number of function evaluations allowed for local search. Memetic Algorithms were applied successfully in all the aforementioned problems, exhibiting superior performance than Particle Swarm Optimization in terms of function evaluations and percentage of successful experiments. Another interesting field of application involved problems of nonlinear dynamics. The determination of the stability region of conservative maps is a very important issue. A new methodology was proposed to numerically approximate the stability region of conservative maps using the Differential Evolution algorithm and the Smaller ALignment Index method, which is used for the detection of chaotic orbits. Also the correlation dimension of the produced regions was computed to provide an estimation for the dimension of the studied maps. The conservative maps used to test the validity of the new methodology were the 2 and 4-dimensional maps of Hénon, which have been used to model the particles motion inside the particle accelerator’s machines. Furthermore, a new methodology that exploits the aforementioned approach was proposed to find frequencies that result in the map with the biggest possible region of stability. Very interesting results were obtained by both methodologies. The first methodology estimated with satisfactory accuracy the last invariant curve in the 2-dimensional case and the last invariant torus in the 4-dimensional case. The second methodology found a pair of frequencies, which resulted in a map with correlation dimension close to 3 and bounded orbits up to 108 iterations of the map. Further work was done on the existence of resonances in dynamical systems, which constitutes valuable information. The detection of resonances in conservative maps has been transformed to a global optimization problem and Differential Evolution was used to solve this problem. Since the existence of resonances is related with the integrability of a dynamical system, the proposed methodology can also serve as a numerical indicator for the integrability of a dynamical system. The proposed methodology has been applied to well known 2 and 4-dimensional maps, which are known to be chaotic or integrable, with very promising results. Specifically, it recognized resonances in cases where they existed, and in the case of integrable maps it gave no indication for the existence of resonances. The appealing feature of the proposed methodology is its applicability on conservative maps of any dimension. Finally, the problem of detecting periodic orbits was investigated. Periodic orbits comprise a very important tool for the study of dynamical systems, especially in cases of chaotic dynamical systems. Evolutionary and Memetic Algorithms were applied successfully for the detection of periodic orbits of nonlinear maps with high accuracy. These methods are applicable to nonlinear maps of any form, including discontinuous or non-differentiable maps. Also, these methods have performed very well in the case of chaotic maps where conventional methods failed. Memetic Algorithms exhibited better results than Evolutionary Algorithms on the problem of detecting periodic orbits, due to the usage of local search methods that have the ability to operate very effectively when they are in the basin of attraction of the desired optimum.

Η παρούσα διατριβή έχει κύριο αντικείµενο µελέτης τους Εξελικτικούς Αλγόϱιθµους (ΕΑ). Ο εξελικτικός υπολογισµός ϐασίζεται στις θεωρίες της ϐιολογίας και συγκεκριµένα του ∆αρβίνου για την εξέλιξη των ειδών. Προσπαθεί να µιµηθεί τους µηχανισµούς που χρησιµοποιεί η ϕύση στα γονίδια των οργανισµών για την εξέλιξη τους. Τις τελευταίες δύο δεκαετίες, οι ΕΑ έχουν γνωρίσει σηµαντική αποδοχή από την επιστηµονική κοινότητα γιατί κατάφεραν να δώσουν λύσεις σε δύσκολα και πολύπλοκα προβλήµατα, στα οποία οι υπάρχουσες µεθοδολογίες και αλγόριθµοι αποτύγχαναν. Οι Μιµιδικοί Αλγόριθµοι (ΜΑ) είναι αλγόριθµοι εµπνευσµένοι από την πολιτισµική εξέλιξη παρά τη ϐιολογική. Μοιάζουν σε σηµαντικό ϐαθµό µε τους ΕΑ αλλά το κύριο χαρακτηριστικό τους είναι ότι υποστηρίζουν ότι το άτοµο κατά τη διάρκεια της ζωής του µπορεί να µάθει και να προσαρµοστεί στις υπάρχουσες συνθήκες, στοιχεία που µπορούν να επιταχύνουν την εξέλιξη και ικανότητα του. Στη ϐελτιστοποίηση, οι ΜΑ εµφανίζονται σαν υβριδικά σχήµατα τα οποία συνδυάζουν τους ΕΑ µε µεθόδους τοπικής αναζήτησης. Ένα µέρος της παρούσας διατριβής µελετάει τους ΜΑ και δείχνει ότι πράγµατι καταφέρνουν να ϐελτιώσουν την απόδοση των ΕΑ. Προτείνονται νέοι ΜΑ που συνδυάζουν τις µεθόδους Βελτιστοποίησης Σµήνους Σωµατιδίων (ΒΣΣ) και τον ∆ιαφοροεξελικτικό Αλγόριθµο (∆Α) µε ντετερµινιστικές και στοχαστικές µεθόδους αναζήτησης. Επίσης εξετάζονται αυτοί οι ΜΑ ως προς τη θεωρητική τους σύγκλιση. Από αυτούς τους συνδυασµούς προκύπτουν διάφορα σχήµατα τα οποία εφαρµόζονται σε µια πληθώρα προβληµάτων ολικής ϐελτιστοποίησης. Αυτά περιλαµβάνουν προβλήµατα ϐελτιστοποίησης χωρίς περιορισµούς, µε περιορισµούς, ακέραιου και ελαχιστοµέγιστου (minimax) προγραµµατισµού και το πρόβληµα µάθησης στις Ασαφείς Γνωστικές Απεικονίσεις. Τέλος, εξετάζεται η εφαρµογή Εξελικτικών και Μιµιδικών Αλγορίθµων σε θέµατα µη γραµµικών δυναµικών συστηµάτων. Η πολυπλοκότητα που εµφανίζεται στα συστήµατα αυτά είναι πολύ µεγάλη ακόµα και για συστήµατα µικρών διαστάσεων, οπότε η χρήση ευριστικών αλγορίθµων θα µπορούσε να δώσει λύσεις σε ζητήµατα τα οποία δεν µπορούν να αντιµετωπιστούν από αναλυτικές µεθόδους. Συγκεκριµένα, µελετώνται προβλήµατα σε διατηρητικές απεικονίσεις όπως η εκτίµηση της περιοχής ευστάθειας τους και η ανίχνευση συντονισµών σε αυτές. Μια επίσης σηµαντική εφαρµογή αποτελεί ο εντοπισµός περιοδικών τροχιών µεγάλης ακρίβειας σε µη γραµµικές απεικονίσεις.