Γενετικοί αλγόριθμοι και εφαρμογές σε συνδυαστικά προβλήματα
Loading...
Date
2023-10-03
Authors
Νίκας, Παναγιώτης
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στην παρούσα διπλωματική γίνεται μια αναλυτική έρευνα στην χρησιμότητα των γενετικών αλγορίθμων
για την επίλυση συνδυαστικών προβλημάτων. Αρχικά γίνεται μια παρουσίαση της βασικής δομής των
γενετικών αλγορίθμων και των θεμελιωδών στοιχείων τους. Αυτή περιλαμβάνει την ανάλυση των
διάφορων τελεστών κωδικοποίησης, επιλογής, διασταύρωσης και μετάλλαξης με παραδείγματα για την
κατανόηση τους. Αυτή η εισαγωγή αποτελεί τις προαπαιτούμενες γνώσεις για την σύγκριση των
γενετικών αλγορίθμων με άλλες καθιερωμένες μεθόδους. Η σύγκριση γίνεται σε τρία κλασσικά
συνδυαστικά προβλήματα: Το πρόβλημα του πλανόδιου πωλητή , το πρόβλημα του σακιδίου και το
πρόβλημα της ικανοποιησιμότητας .
Το πρόβλημα του πλανόδιου πωλητή αποτελεί ένα πρόβλημα βελτιστοποίησης που αφορά την εύρεση
της συντομότερης διαδρομής που μπορεί να επιλέξει ένας πωλητής έτσι ώστε να επισκέπτεται ένα
σύνολο πόλεων ακριβώς μια φορά και να επιστρέφει στην αρχική. Αρχικά γίνεται η παρουσίαση κάποιων
μεθόδων για την ακριβή επίλυση του προβλήματος και στην συνέχεια κάποιων ευρετικών αλγορίθμων.
Στην συνέχεια παρουσιάζεται ο γενετικός αλγόριθμος για την επίλυση του προβλήματος του πλανόδιου
πωλητή και γίνεται μία σύγκριση μεταξύ των μεθόδων. Στην σύγκριση παρατηρούνται οι περιορισμοί
των ακριβών μεθόδων επίλυσης του προβλήματος του πλανόδιου πωλητή λόγο του υψηλού
υπολογιστικού κόστος τους. Τέλος γίνεται σύγκριση μεταξύ των γενετικών αλγορίθμων και των δύο
ευρετικών αλγορίθμων που αναπτύχθηκαν: του αλγορίθμου του πλησιέστερου γείτονα και του
άπληστου αλγορίθμου.
Το πρόβλημα του σακιδίου αποτελεί ένα άλλο κλασσικό πρόβλημα βελτιστοποίησης, στην βασική του
μορφή δίνεται ένα σύνολο αντικειμένων με συγκεκριμένο βάρος και αξία. Στόχος είναι η επιλογή των
αντικειμένων έτσι ώστε να μεγιστοποιηθεί η συνολική αξία των αντικειμένων στο σακίδιο και το
συνολικό βάρος να μην ξεπερνάει την μέγιστη χωρητικότητα του σακιδίου. Αρχικά γίνεται μια
παρουσίαση των παραλλαγών του προβλήματος του σακιδίου και εφαρμόζονται δύο ακριβείς
αλγόριθμοι, ο εξαντλητικός αλγόριθμος και ο αλγόριθμος δυναμικού προγραμματισμού, για την επίλυση
της βασικής μορφής του προβλήματος. Ενώ οι ακριβείς αλγόριθμοι εγγυούνται την εύρεση της βέλτιστης
λύσης η πολυπλοκότητα τους τους κάνει ακατάλληλους για την επίλυση μεγάλων περιπτώσεων του
προβλήματος του σακιδίου. Στην συνέχεια αναλύεται ο άπληστος αλγόριθμος για το πρόβλημα του
σακιδίου και γίνεται η σύγκριση του με έναν γενετικό αλγόριθμο που αναπτύχθηκε για το πρόβλημα
Το πρόβλημα της ικανοποιησιμότητας αντιπροσωπεύει ένα ακόμα σημαντικό συνδυαστικό πρόβλημα
που αναλύεται σε αυτήν την εργασία. Το πρόβλημα αφορά την εύρεση μιας ανάθεσης τιμών σε ένα
σύνολο μεταβλητών έτσι ώστε μία συνάρτηση σε μορφή Boole να ικανοποιείται. Οι αλγόριθμοι για την
επίλυση του χωρίζονται σε δύο κατηγορίες. Τους πλήρεις αλγορίθμους που εγγυούνται την εύρεση
ανάθεσης μεταβλητών που να ικανοποιεί την συνάρτηση ή διαφορετικά την απόδειξη ότι η συνάρτηση
είναι μη ικανοποιήσιμη. Επιπλέον, υπάρχουν και οι ημιτελείς αλγόριθμοι που δεν μπορούν να
αποδείξουν αν μια συνάρτηση είναι μη ικανοποιήσιμη όπως οι αλγόριθμοι τοπικής αναζήτησης και οι
γενετικοί αλγόριθμοι. Στην συνέχεια γίνεται η ανάπτυξη ενός γενετικού αλγορίθμου για την επίλυση
προβλημάτων ικανοποιησιμότητας και σύγκριση μεταξύ των αλγορίθμων που αναπτύχθηκαν στο
κεφάλαιο σε τυχαίες περιπτώσεις του 3-SAT.
Οι γενετικοί αλγόριθμοι αποτελούν μια καλή επιλογή για την επίλυση των τριών συνδυαστικών
προβλημάτων που αναπτύχθηκαν στην εργασία. Η ικανότητα τους να εξερευνούν ένα μεγάλο μέρος του
χώρου των λύσεων τους δίνει την δυνατότητα να βρίσκουν την βέλτιστη λύση ή καλές προσεγγίσεις τις βέλτιστης λύσης συχνά. Η ευελιξία των γενετικών αλγορίθμων τους δίνει την δυνατότητα να
εφαρμοστούν σε πληθώρα προβλημάτων και τις παραλλαγές τους με ελάχιστες αλλαγές.
Συμπερασματικά οι γενετικοί αλγόριθμοι είναι ένα καλό εργαλείο γενικής χρήσεως για συνδυαστικά
προβλήματα με εντυπωσιακή επίδοση
Description
Keywords
Γενετικοί αλγόριθμοι, Συνδυαστικά προβλήματα