Μελέτη σύγκλισης εξελικτικών δυναμικών για τον σχεδιασμό αποδοτικών αλγορίθμων
Loading...
Date
2024-07-17
Authors
Ματαράς, Στυλιανός
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πεδίο της Εξελικτικής θεωρίας γραφημάτων παρουσιάστηκε για πρώτη φορά στην εργασία των Lieberman, Hauert και Nowak στην οποία γενικεύεται το αρχικό μοντέλο του P.A.P.Moran, το οποίο περιέγραφε την εξέλιξη ενός αδόμητου, «well-mixed», πεπερασμένου πληθυσμού στον οποίο ανταγωνίζονται δύο είδη (μεταλλαγμένοι,μη-μεταλλαγμένοι). Η γενίκευση σε γραφήματα, σε μια προσπάθεια εισαγωγής της δομής του πληθυσμού στην εξέλιξη του, τοποθέτησε τα μέλη του πληθυσμού σε κορυφές ενός γραφήματος n κορυφών. Η γενίκευση της διεργασία Moran πάνω σε ένα γράφημα(GMP), έχει αξιοποιηθεί για την περιγραφή αρκετών προβλημάτων σε πληθώρα επιστημονικών πεδίων, δύο παραδείγματα εκ των οποίων είναι η περιγραφή της εξέλιξης κυττάρων σε πολυκύτταρους οργανισμούς καθώς και η συνδεσιμότητα διαφορετικών οικολογικών οικοτόπων. Το βασικό πρόβλημα που εξετάζεται σε αυτό το μοντέλο είναι ο υπολογισμός της πιθανότητας εισβολής. Δηλαδή, την πιθανότητα σταθεροποίησης των μεταλλαγμένων ατόμων του πληθυσμού όταν η αρχική του σύσταση περιέχει μονάχα ένα μεταλλαγμένο άτομο το οποίο επιλέγεται τυχαία. ́Αρρηκτα συνδεόμενο με το πρόβλημα της πιθανότητας σταθεροποίησης, είναι ο χρόνος που απαιτείται για τα μεταλλαγμένα άτομα του πληθυσμού να σταθεροποιηθούν ή να εξαφανιστούν από τον πληθυσμό, ο οποίος γενικά αποκαλείται χρόνος απορρόφησης της διεργασίας. Ο υπολογισμός του αναμενόμενου χρόνου απορρόφησης ή της πιθανότητας σταθεροποίησης της διεργασίας Moran, πάνω σε ένα γενικό γράφημα, είναι υπολογιστικά μη-εφικτός. Πρόσφατα η διεργασία, GMP, γενικεύθηκε εκ νέου ως μια διεργασία Moran η οποία εξελίσσεται πάνω σε δύο γραφήματα με το ίδιο σύνολο κορυφών. Η γενίκευση αυτή, αποκαλούμενη διεργασία Moran δύο γραφημάτων, γενικεύει το σύνολο πιθανών δομών που μπορούν να περιγραφούν με μια διεργασία Moran καθώς δύναται να περιγράψει πληθυσμούς των οποίων η δομή που αντιλαμβάνεται μια κορυφή εξαρτάται από τον τύπο της. Η δυσκολία υπολογισμού της πιθανότητας σταθεροποίησης καθώς και του αναμενόμενου χρόνου απορρόφησης, ποσότητες που δεν αλλάζουν στην γενίκευση της διεργασίας, παραμένει και στην διεργασία πάνω σε δύο γραφήματα.
Στην παρούσα διπλωματική εργασία μελετάται το πρόβλημα προσέγγισης της πιθανότητας σταθεροποίησης, στην διεργασία Moran δύο γραφημάτων, μέσω αλγορίθμων τύπου Markov Chain Monte Carlo, που βασίζονται σε αυστηρά άνω όριο στον αναμενόμενο χρόνο απορρόφησης. Συγκεκριμένα, η σχέση ανάμεσα στην δομή των δύο γραφημάτων και τον αναμενόμενο χρόνο απορρόφησης εξετάζεται, με στόχο να επεκταθούν σημαντικά αποτελέσματα για τον αναμενόμενο χρόνο απορρόφησης της GMP, όταν αυτή εξελίσσεται γραφήματα που ανήκουν σε συγκεκριμένες οικογένειες γραφημάτων. Αρχικά, γίνεται ειδική προσπάθεια στην παρουσίασή της σχέσης μεταξύ διεργασιών τύπου Moran και αλυσίδων Markov διακριτού χρόνου, σε συνδυασμό με την παρουσίασή των σημαντικότερων εκ των θεμελιωδών αποτελεσμάτων σε κάθε μοντέλο διεργασίας Moran. ́Υστερα, η δυσκολία του προβλήματος υπολογισμού της πιθανότητας σταθεροποίησης τόσο στην διεργασία Moran πάνω σε ένα γράφημα όσο και στην γενίκευση σε δύο γραφήματα παρουσιάζεται, με σκοπό να γίνει κατανοητή η ανάγκη προσέγγισης. ́Οπως αναφέρθηκε και παραπάνω, ο βασικός τρόπος προσέγγισης της πιθανότητας σταθεροποίησης, σε οποιαδήποτε εκ των δύο διεργασιών Moran σε γραφήματα, είναι η ανάπτυξη αλγορίθμων Monte Carlo που αποδεικνύεται πως αποτελούν προσεγγιστικοί αλγόριθμοι τύπου Πλήρως Πολυωνυμικού Τυχαιοκρατικού Σχεδίου Προσέγγισης(FPRAS). Αυτό ο ισχυρισμός υποστηρίζεται, παρουσιάζοντας τους πιο σημαντικούς αλγορίθμους τόσο για την GMP όσο και για την διεργασία σε δύο γραφήματα. Τέλος, γίνεται προσπάθειά ανάδειξης της αδυναμίας ευρέως χρησιμοποιούμενων τεχνικών, να αποδείξουν ικανοποιητικά άνω φράγματα στον αναμενόμενο χρόνο απορρόφησης της διεργασίας Moran σε δύο γραφήματα, όταν η δομή ενός τουλάχιστον εκ των δύο γραφημάτων δεν είναι τετριμμένη(πχ. Πλήρες Γράφημα). Επιπρόσθετα, ακόμα και στην περίπτωση που ένα εκ των γραφημάτων ικανοποιεί την προαναφερθείσα ιδιότητα, αναδεικνύεται πως η δομή του άλλου γραφήματος πάνω στο οποίο εξελίσσεται η διεργασία, δεν φαίνεται να επηρεάζει το άνω όριο της πιθανότητας σταθεροποίησης. Οι προαναφερθείσες αδυναμίες, αναδεικνύουν την ανάγκη μιας διαφορετικής προσέγγισης στο πρόβλημα εύρεσης αυστηρών άνω ορίων στον αναμενόμενο χρόνο απορρόφησης της διεργασίας Moran σε δύο γραφήματα. Προς αυτόν τον σκοπό, παρουσιάζεται μια νέα προτεινόμενη μέθοδος, η οποία βασίζεται στην διαμέριση της εξέλιξης της διεργασίας Moran σε δύο γραφήματα, σε τρία μέρη καθώς και μια εικασία για την σχέση ανάμεσα στον αναμενόμενο χρόνο απορρόφησης της αρχικής διεργασίας και τον αναμενόμενο χρόνο απορρόφησης της, όταν περιορίζεται σε κάθε ένα από τα τρία μέρη της.
Description
Keywords
Εξελικτικά δυναμικά, Τυχαιοκρατικοί προσεγγιστικοί αλγόριθμοι, Διεργασία Μοράν