Δημιουργία ειδικευμένων ευρετικών κανόνων μέσω γενετικού προγραμματισμού
Creators: name: Κωστίκας, Κωνσταντίνος Γ.
Publisher: name: Aristotle University of Thessaloniki
Year: 2005
Subjects: Συνδυαστική βελτιστοποίηση
Ευρετικοί κανόνες
Υβριδικοί αλγόριθμοι
Combinatorial optimization
Hybrid algorithms
Stochastic research

description: Η χρήση ευρετικών κανόνων αποτελεί βασικό χαρακτηριστικό των υπολογιστικών μεθόδων και αλγόριθμων που χρησιμοποιεί η επιχειρησιακή έρευνα για την επίλυση δύσκολων προβλημάτων συνδυαστικής βελτιστοποίησης. Αντικείμενο της διατριβής είναι η δημιουργία προσαρμοσμένων ευρετικών κανόνων μέσω γενετικού προγραμαμτισμού(ΓΠ), μιας τεχνικής στοχαστικής αναζήτησης που συνιστάται στην αυτόματη δημιουργία εκτελέσιμων εκφράσεων-προγραμμάτων. Συγκεκριμένα εξετάζεται η δυνατότητα αντικατάστασης των στατικών ευρετικών κανόνων που περιλαμβάνονται στον αλγόριθμο βελτιστοποίησης με εξειδικευμένους στο προς επίλυση πρόβλημα ευρετικούς κανόνες. Οι ευρετικοί αυτοί κανόνες δημιουργούνται δυναμικά, μέσω ΓΠ, κατά τη διάρκεια της αναζήτησης. Η μέθοδος εξειδικεύεται στην επίλυση προβλημάτων(μικτού) ακέραιου γραμμικού προγραμματισμού με το αλγοριθμικό πλαίσιο επέκτασης και οριοθέτησης. Εισάγεται η υβριδική αλγοριθμική αρχιτεκτονική, που περιλαμβάνει αφενός τον επιλύτη των γραμμικών χαλαρώσεων που συγκροτούν το δένδρο επέκτασης και οριοθέτησης, και αφετέρου τη μονάδα ΓΠ που αναπτύσσει ειδικευμένες στρατηγικές επιλογής κόμβου προς επίλυση. Αναλύεται η πρωτότυπη μέθοδος δυναμικής δημιουργίας συνόλων εκπαίδευσης που είναι απαραίτητη για την αποδοτική λειτουργία του βρόγχου ΓΠ. Παρουσιάζεται ο επιλύτης DBGP που αποτελεί την υλοποίηση σε λογισμικό του υβριδικού αλγοριθμικού πλαισίου και αξιολογείται η απόδοσή του στην επίλυση χαρακτηριστικών προβλημάτων(μικτού) ακέραιου γραμμικού προγραμματισμού. Τα πειραματικά αποτελέσματα δείχνουν πως η προτεινόμενη προσέγγιση συντελεί στην επιτάχυνση της επίλυσης των προβλημάτων ή στη δημιουργία ποιοτικότερων λύσεων, σε σχέση με τις κλασσικές μεθόδους
description: Heuristic rules are an important component of the computational methods and algorithms utilized in operational research for the solution of hard compinational optimization problems. This work is about the use of genetic programming(GP), a stochastic search technique, for the automatic creation of specialized heuristic rules used in algorithms for compinatorial optimization problems. Key idea of the research performed is the replacement of the general-purpose static heurestic rules contained in the optimization algorithm with more specialized ones, automatically evolved for the specific problem at hand by a genetic programming component. The general framework of the proposed approach is presented and the main characteristics are discussed from a theoretical point of view. The method is applied to the branch and bound algorithmic framework for the solution of mixed integer linear programming(MIP) problems. The hydrid architecture comprised of the GP. The linear programming solver, and the branch and bound is discussed. Various methods for the unattended creation creation of the training sets, essential for the effective functioning of the GP component are introduced and discussed. The hybrid DBGP solver, based on the proposed architecture, is discussed and tested to a number of MIP problem suites. Computational results suggest that the hybrid solver performs same or better to comparable classical approaches, regarding the computational effort required and the quality of the solution reached