Προσεγγίσεις γενετικού προγραμματισμού για διαχείριση της πολυπλοκότητας συστημάτων με εφαρμογή στη διοίκηση παραγωγής

Abstract

Genetic programming is a subclass of nature-inspired methods of Artificial Intelligence. It mimics DNA's function in the evolutionary reproduction of organisms to construct solutions. Afterward, the algorithm evaluates these solutions and assesses their effectiveness in solving the posed problem. When the problem to be solved belongs to the category of symbolic regression, it is represented by a data vector that should be verified in the best possible way by the function created as a solution by genetic programming. Genetic programming exploits the hidden information in the data without requiring explicit guidance from the human experimenter, who indirectly intervenes, reducing the impact of human bias. It belongs to the category of metaheuristic algorithms and is proposed as the method for investigating complex systems' behavior. Here the focus is on the production systems found in industry and are part of operations research. The principles in modeling these systems are also found in other systems such as queuing networks, operations management, workflows such as those found in the public sector, telecommunications, and elsewhere. The problem to be solved by genetic programming is the extraction of formulas for approximating the throughput of these systems. The problem counts almost seven decades after the publication of the first formula for such a system. During this time, very few exact formulas have been proposed demonstrating the difficulty of the problem. Even an accurate numerical solution can be done for relatively small systems, while for the more complex ones, it becomes a computationally impossible problem even for supercomputers. A data organization process is used herein to create approximate relationships that generalize well. The genetic programming implementations are fed by Markovian analysis data to provide reasonable approximate solutions for various systems. The results' meta-analysis shows that the ratio of two polynomials is often encountered as the solution's ultimate structure. Moreover, solutions that have a different structure are somehow related to a polynomial ratio. The investigation of the above observation led to creating a hybrid scheme where genetic programming constructs the solution's structure, and a genetic algorithm adjusts the values of the coefficients and exponents of monomials, which create a ratio of two polynomials. Thus, the hybrid scheme of genetic programming and genetic algorithm creates only solutions that are the ratio of two polynomials. The scheme generalizes better than genetic programming giving strong indications that the exact solutions have this structure. From this perspective, the existing exact solutions are reexamined to induce solutions for larger systems. Using graphs, which are used in production systems mainly as an imaging tool, a probability space was created, and a method was developed to derive the stationary probabilities of the systems in symbolic form. That was done by interpreting the spanning tree and enumerating all spanning trees that end up in a system state. From this point on, the expression of all system performance metrics is a matter of algebra. Several systems were solved, some outside of production systems, using the general method developed in the present dissertation. The method solves symbolically or even numerically at least the systems that can be expressed as Markov chains. Remarks were made about the size of the solutions, their structure, and the appearance of patterns on the graphs that increase the exact solutions' size at an alarmingly fast rate. The large size of the exact solutions is, in fact, the factor that did not allow the extraction of exact closed-form formulas in all the previous years. The use of classical methods such as differential calculus and probability calculus makes them tools that are extremely difficult to use. Graph theory was used here through a model of the Markovian model of underlying systems that allowed these systems to be solved and is expected to contribute in the future to expand our knowledge of them.

Ο γενετικός προγραμματισμός είναι μία κατηγορία των μεθόδων της Τεχνητής Νοημοσύνης που είναι εμπνευσμένες από τη φύση. Μιμείται την λειτουργία του DNA στην εξελικτική αναπαραγωγή των οργανισμών για να κατασκευάζει λύσεις που στη συνέχεια υπόκεινται σε μία διαδικασία αξιολόγησης της αποτελεσματικότητος τους στην επίλυση του τιθέμενου προβλήματος. Όταν το πρόβλημα για επίλυση ανήκει στην κατηγορία της συμβολικής παλινδρόμησης, απεικονίζεται από ένα διάνυσμα δεδομένων το οποίο θα πρέπει να επαληθεύεται με τον καλύτερο δυνατό τρόπο από τη συνάρτηση που δημιουργεί ως λύση ο γενετικός προγραμματισμός. Ο γενετικός προγραμματισμός εκμεταλλεύεται την πληροφορία που υπάρχει κρυμμένη στα δεδομένα χωρίς να απαιτεί ρητή καθοδήγηση από τον άνθρωπο πειραματιστή, ο οποίος επεμβαίνει με έμμεσο τρόπο, μειώνοντας την επίδραση της ανθρώπινης προκατάληψης. Ανήκει στην κατηγορία των μεθευρετικών αλγορίθμων και προτείνεται ως η μέθοδος για την διερεύνηση της συμπεριφοράς πολύπλοκων συστημάτων. Εδώ γίνεται επικέντρωση στα συστήματα παραγωγής που συναντώνται στη βιομηχανία και εντάσσονται στην επιχειρησιακή έρευνα. Οι αρχές στην μοντελοποίηση αυτών των συστημάτων συναντώνται και σε άλλα συστήματα όπως τα συστήματα αναμονής, στην διοίκηση λειτουργιών, σε ροή εργασιών όπως αυτές που απαντώνται στο δημόσιο τομέα, στις τηλεπικοινωνίες και αλλού. Το πρόβλημα που καλείται να επιλύσει ο γενετικός προγραμματισμός είναι η εξαγωγή μαθηματικών σχέσεων για την προσεγγιστική εκτίμηση του ρυθμού παραγωγής αυτών των συστημάτων. Το πρόβλημα μετρά σχεδόν επτά δεκαετίες από την δημοσίευση της πρώτης σχέσης για ένα τέτοιο σύστημα. Σε αυτό το χρονικό διάστημα ελάχιστες ακριβείς σχέσεις έχουν προταθεί καταδεικνύοντας την δυσκολία του προβλήματος. Ακόμη και η ακριβής αριθμητική επίλυση μπορεί να γίνει για μικρά σχετικά συστήματα, ενώ για τα αμέσως πολυπλοκότερα, γίνεται ένα υπολογιστικά αδύνατο πρόβλημα ακόμη και για τα πλέον σύγχρονα υπολογιστικά συστήματα. Για την εξαγωγή προσεγγιστικών σχέσεων που γενικεύουν καλά μία διαδικασία παραγωγής δεδομένων εκπαίδευσης των αλγορίθμων μεθοδεύεται στην παρούσα διδακτορική διατριβή. Δεδομένα από τη Μαρκοβιανή ανάλυση τροφοδοτούν υλοποιήσεις του γενετικού προγραμματισμού που δίνει καλές λύσεις για μία σειρά συστημάτων. Η μεταανάλυση των αποτελεσμάτων δείχνει ότι συναντάται συχνά ως δομή της λύσης ο λόγος δύο πολυωνύμων. Και οι λύσεις που έχουν άλλη δομή με κάποιο τρόπο σχετίζονται με λόγο πολυωνύμων. Η διερεύνηση της παραπάνω παρατήρησης οδήγησε στην δημιουργία ενός υβριδικού σχήματος όπου ο γενετικός προγραμματισμός κατασκευάζει τη δομή της λύσης και ένας γενετικός αλγόριθμος ρυθμίζει τις τιμές των συντελεστών και εκθετών μονωνύμων. Αυτά τα μονώνυμα δημιουργούν το λόγο δύο πολυωνύμων. Έτσι το υβριδικό σχήμα γενετικού προγραμματισμού και γενετικού αλγορίθμου δημιουργεί μόνον λύσεις που είναι λόγος δύο πολυωνύμων. Το σχήμα γενικεύει καλύτερα από το γενετικό προγραμματισμό δίνοντας σοβαρές ενδείξεις ότι η ακριβείς λύσεις έχουν αυτή τη δομή. Υπό αυτή την οπτική έγινε η επανεξέταση των ακριβών λύσεων που υπάρχουν, έχοντας σαν σκοπό ότι μπορεί να γίνει η επαγωγή λύσεων για μεγαλύτερα συστήματα. Με τη χρήση των γράφων, που χρησιμοποιούνται στα συστήματα παραγωγής κυρίως ως απεικονιστικό εργαλείο, περιγράφηκε ένας χώρος πιθανότητας και αναπτύχθηκε μία μέθοδος για την εξαγωγή των στάσιμων πιθανοτήτων των συστημάτων με συμβολική μορφή. Αυτό έγινε με την ερμηνεία του ζευγνύοντος δέντρου, και την απαρίθμηση όλων των ζευγνυόντων δέντρων που καταλήγουν σε μία κατάσταση του συστήματος. Από το σημείο αυτό και μετά η έκφραση όλων των μετρικών απόδοσης των συστημάτων είναι θέμα άλγεβρας. Μία σειρά από συστήματα επιλύθηκαν, κάποια εκτός συστημάτων παραγωγής, με τη χρήση της γενικής μεθόδου που αναπτύχθηκε στην παρούσα διατριβή. Η μέθοδος επιλύει συμβολικά ή και αριθμητικά τουλάχιστον τα συστήματα που μπορούν να εκφραστούν ως Μαρκοβιανές αλυσίδες. Έγιναν παρατηρήσεις σχετικά με το μέγεθος των λύσεων, τη δομή τους και την εμφάνιση μοτίβων στους γράφους που αυξάνουν με τρομακτικά ταχύ ρυθμό το μέγεθος των ακριβών λύσεων. Το μεγάλο μέγεθος των ακριβών λύσεων είναι στην ουσία ο παράγοντας που δεν επέτρεψε την εξαγωγή μαθηματικών σχέσεων κλειστού τύπου όλα τα προηγούμενα χρόνια. Η χρήση κλασσικών μεθόδων όπως διαφορικός λογισμός και λογισμός πιθανοτήτων τις καθιστά εξαιρετικά δύσχρηστες. Εδώ χρησιμοποιήθηκε η θεωρία των γράφων, μέσα από ένα μοντέλο του μοντέλου των Μαρκοβιανών διαδικασιών των υποκείμενων συστημάτων που επέτρεψε την επίλυση αυτών των συστημάτων και αναμένεται να συνεισφέρει μελλοντικά στη διεύρυνση των γνώσεων μας γι αυτά.