Ανάπτυξη μεταευρετικών αλγορίθμων για την επίλυση προβλημάτων μη γραμμικού προγραμματισμού και σύνθετων προβλημάτων συνδυαστικής βελτιστοποίησης

Abstract

Mathematical optimization is of primary importance for all practical sciences. However, the determination of the optimal solution in for many optimization problems is not possible with the conventional methodologies. This happens for example for the non linear programming problems that are non convex or the mathematical relations that compose them are non differentiable or not continuous. It also happens to combinatorial optimization problems characterized as NP-Hard. In the recent years, a new generation of heuristic - metaheuristic techniques has lead to the approximate solution of such complex optimization problems. The success of these methodologies relies also greatly to the progress of computer systems. This new research area is open and can be subjected to many improvements concerning the quality and the reproducibility of the solutions as well as the computational times. In the present thesis new hybrid metaheuristic algorithms have been developed for the solution of nonlinear and complex combinatorial optimisation problems. We give a concise presentation of the mathematical modelling of the problems under consideration and of the tools used for the recognition and analysis of their difficulty, which justifies the use of heuristic methods. First, a complete method for the solution of constrained nonlinear optimisation problems (NLP) has been developed. The method was based on the differential evolutionary algorithm with an ordered classification of the solutions (Line-Up Differential Evolution, shortly LUDE), which we propose for the solution of unconstrained nonlinear problems. The handling of linear and nonlinear constrains in the present work is done by incorporating them in an augmented Lagrange function. In this augmented function the values of the penalty parameters and the multipliers are adjusted, as the execution of the algorithm develops. The LUDE algorithm maintains a population of solutions, which is continuously improved as it passes from generation to generation. In the population of each generation the solutions are classified in an order that depends on the value of objective function produced from each one of them. The position of each solution in the line-up is very important, since it determines to what extent the crossover and mutation operators are applied to each solution. The efficiency of the proposed method is illustrated by solving numerous unconstrained and constrained optimization problems and comparing it with other optimization techniques that can be found in the literature. Τhe proposed method can face a larger variety of problems and in the majority of the cases it produces results of better quality with smaller computational cost and at the same time it presents great performance stability.

Η μαθηματική βελτιστοποίηση είναι πρωταρχικής σημασίας σε όλες τις θετικές επιστήμες. Σε πολλά όμως προβλήματα βελτιστοποίησης που προκύπτουν στον πραγματικό κόσμο, ο προσδιορισμός της ακριβούς βέλτιστης λύσης δεν είναι δυνατός με τις συμβατικές μεθοδολογίες. Αυτό συμβαίνει για παράδειγμα σε προβλήματα μη γραμμικού προγραμματισμού τα οποία δεν είναι κυρτά ή οι μαθηματικές σχέσεις που συμμετέχουν σε αυτά δεν είναι παραγωγίσιμες ή δεν είναι συνεχείς. Συμβαίνει ακόμη σε προβλήματα συνδυαστικής βελτιστοποίησης που χαρακτηρίζονται ως NP-Hard. Τα τελευταία χρόνια, μια νέα γενιά ευρετικών -μεταευρετικών τεχνικών οδήγησε στην προσεγγιστική επίλυση τέτοιων σύνθετων προβλημάτων βελτιστοποίησης. Η επιτυχία των μεθοδολογιών αυτών βασίζεται σε μεγάλο ποσοστό στη ραγδαία εξέλιξη των υπολογιστικών συστημάτων. Η νέα αυτή ερευνητική περιοχή είναι ανοικτή και επιδέχεται πολλών βελτιώσεων τόσο ως προς την ποιότητα και επαναληψιμότητα των παραγόμενων λύσεων όσο και ως προς τους απαιτούμενους υπολογιστικούς χρόνους. Στο πλαίσιο της παρούσας διατριβής αναπτύχθηκαν νέοι υβριδικοί μεταευρετικοί αλγόριθμοι για την επίλυση μη γραμμικών προβλημάτων βελτιστοποίησης και σύνθετων προβλημάτων συνδυαστικής βελτιστοποίησης. Αρχικά, αναπτύχθηκε μια πλήρης μέθοδος για την επίλυση μη γραμμικών προβλημάτων βελτιστοποίησης (nonlinear programming, NLP) με περιορισμούς. Η μέθοδος βασίστηκε στον διαφορικό εξελικτικό αλγόριθμο με κατάταξη των λύσεων σε σειρά (Line-Up Differential Evolution ή εν συντομία LUDE), ο οποίος αναπτύχθηκε για την επίλυση μη γραμμικών προβλημάτων χωρίς περιορισμούς. Ο χειρισμός των γραμμικών και μη γραμμικών περιορισμών συνίσταται στην ενσωμάτωσή τους σε μια επαυξημένη συνάρτηση Lagrange, στην οποία οι τιμές των παραμέτρων ποινής και των πολλαπλασιαστών αναπροσαρμόζονται, καθώς εξελίσσεται η εκτέλεση του αλγόριθμου. Ο αλγόριθμος LUDE βασίζεται σε έναν πληθυσμό από λύσεις, οι οποίες συνεχώς βελτιώνεται καθώς παράγονται οι νέες γενιές. Στον πληθυσμό κάθε γενιάς οι λύσεις κατατάσσονται σε σειρά, ανάλογα με τις αντίστοιχες τιμές της αντικειμενικής συνάρτησης που προκύπτουν. Η θέση της κάθε λύσης στη σειρά είναι πολύ σημαντική γιατί καθορίζει σε ποιο βαθμό εφαρμόζονται σε αυτή οι τελεστές διασταύρωσης και μετάλλαξης. Η αποτελεσματικότητα του προτεινόμενου αλγόριθμου εξετάστηκε λύνοντας μεγάλο αριθμό μη γραμμικών προβλημάτων βελτιστοποίησης με και χωρίς περιορισμούς και τα αποτελέσματα συγκρίθηκαν με αυτά που έχουν παραχθεί από τεχνικές βελτιστοποίησης που περιγράφονται στη διεθνή βιβλιογραφία. Η προτεινόμενη μέθοδος μπορεί να αντιμετωπίσει μεγαλύτερη ποικιλία προβλημάτων, στην πλειοψηφία των περιπτώσεων παράγει αποτελέσματα καλύτερης ποιότητας με μικρότερο υπολογιστικό κόστος και παράλληλα παρουσιάζει μεγάλη σταθερότητα στην απόδοσή της.