The objective of this thesis is the study and research of effective algorithmic approaches for addressing computationally hard optimization problems, through the analysis and the proposal of hybrid evolutionary methods and the formulation of the framework for applying them to specific problems. Initially, the mechanisms that rule the evolutionary methods and other metaheuristics (in particular those of the local search algorithms) are investigated and thoroughly analyzed. In addition, an extensive survey of their implementation on classical and modern combinational optimization problems is performed, with an emphasis on their hybrid schemes. The main goal of the hybrid evolutionary approach that is analyzed and proposed is to exploit the separate advantages and to encounter the weaknesses of the evolutionary processes and the local search algorithms, by combining them in a unified scheme. The approach consists of two stages: In the first stage, the evolutionary process is used for global exploration of the search space, while in the second stage a local search method is employed in order to take advantage of the knowledge obtained from global exploration. A genetic algorithm and a generalized pattern search algorithm are selected respectively for the implementation and the evaluation of the approach. Depending on the nature and the formulation of the optimization problem, distinction between the restrictive conditions with respect to their importance is introduced and different treatment of the candidate solutions that violate each category of constraints is performed.
Αντικείμενο της παρούσας διατριβής αποτελεί η μελέτη και έρευνα αποτελεσματικών αλγοριθμικών προσεγγίσεων για την αντιμετώπιση υπολογιστικά δύσκολων προβλημάτων βελτιστοποίησης, μέσω της ανάλυσης και πρότασης μεθοδολογιών υβριδικών εξελικτικών αλγορίθμων και της διατύπωσης του πλαισίου εφαρμογής τους σε συγκεκριμένα προβλήματα. Στην κατεύθυνση αυτή, αρχικά εξετάζονται και αναλύονται διεξοδικά οι μηχανισμοί που διέπουν τις εξελικτικές μεθόδους και άλλες επιλεγμένες μετα-ευρετικές μεθόδους βελτιστοποίησης, με έμφαση στους αλγορίθμους τοπικής αναζήτησης, ενώ επίσης γίνεται εκτενής αναφορά στην εφαρμογή των μεθόδων αυτών σε κλασσικά και σύγχρονα προβλήματα συνδυαστικής βελτιστοποίησης, κατά κύριο λόγο στις συνδυαστικές τους μορφές. Αναλύεται και προτείνεται μια μεθοδολογία υβριδικής εξελικτικής προσέγγισης, η οποία έχει ως βασικό στόχο την αξιοποίηση των ξεχωριστών πλεονεκτημάτων και την αντιμετώπιση των αδυναμιών των εξελικτικών διαδικασιών και των αλγορίθμων τοπικής αναζήτησης, συνδυάζοντάς τους σε ένα ενιαίο υβριδικό αλγοριθμικό σχήμα. Η προσέγγιση περιλαμβάνει δύο στάδια: Κατά το πρώτο, η εξελικτική διαδικασία χρησιμοποιείται για την ολική εξερεύνηση του χώρου λύσεων, ενώ κατά το δεύτερο, η εφαρμοζόμενη μέθοδος τοπικής αναζήτησης αξιοποιεί τη γνώση που αποκτήθηκε από την εξερεύνηση αυτή. Για την υλοποίηση, την εφαρμογή και την αξιολόγηση της προσέγγισης, επιλέγονται ένας γενετικός αλγόριθμος και ένας αλγόριθμος γενικευμένης πρότυπης αναζήτησης, αντίστοιχα. Επιπρόσθετα, ανάλογα με τη φύση και τη διατύπωση του προβλήματος που εξετάζεται, πραγματοποιείται διάκριση των περιορισμών σε θεμελιώδεις και ελαστικούς και υιοθετείται διαφορετική αντιμετώπιση των προκυπτουσών λύσεων, που παραβιάζουν κάθε κατηγορία περιορισμών.
