| Περίληψη: | Η παρούσα εργασία πραγματεύεται την επίλυση του προβλήματος ολικής κάλυψης με τη χρήση γενετικών αλγορίθμων. Το πρόβλημα ολικής κάλυψης είναι ένα πρόβλημα χωροθέτησης εγκαταστάσεων, στο οποίο στόχος είναι η εύρεση του ελάχιστου αριθμού θέσεων για την τοποθέτηση εγκαταστάσεων έτσι ώστε να ικανοποιηθούν όλοι οι πελάτες. Αυτό το πρόβλημα είναι συνδυαστικό, γι’αυτό και η χρήση γενετικών αλγορίθμων για την επίλυσή του είναι αναπόφευκτη. Στο Κεφάλαιο 1 της εργασίας γίνεται μια γενική περιγραφή των προβλημάτων χωροθέτησης εγκαταστάσεων, παρουσιάζονται οι πιο βασικές κατηγορίες, και γίνεται αναφορά στην υπάρχουσα βιβλιογραφία για το πρόβλημα ολικής κάλυψης. Στο Κεφάλαιο 2 περιγράφονται η δομή των γενετικών αλγορίθμων και οι βασικές αρχές τους, δηλαδή η αρχικοποίηση (initialization), η αξιολόγηση καταλληλότητας (evaluation of fitness), η επιλογή (selection) και η αναπαραγωγή (reproduction), καθώς επίσης και τα πλεονεκτήματα των γενετικών αλγορίθμων. Στη συνέχεια στο Κεφάλαιο 3 περιγράφεται το πρόβλημα ολικής κάλυψης και η μοντελοποίησή του, περιγράφεται αναλυτικά ο προτεινόμενος αλγόριθμος επίλυσης (διασταύρωση, αξιολόγηση των απογόνων, ο αλγόριθμος διόρθωσης Care and Share, μετάλλαξη) και παρουσιάζονται τα βήματα του αλγορίθμου. Στο Κεφάλαιο 4 υπάρχει η εφαρμογή του αλγορίθμου για ένα πρόβλημα από τη βιβλιογραφία. Στο Κεφάλαιο 5 γίνεται εφαρμογή του ίδιου αλγορίθμου σε 3 ακόμα προβλήματα, τα οποία είναι τυχαία υπό περιορισμούς, παρατίθεται το αντίστοιχο Ντετερμινιστικό πρόβλημα το οποίο λειτουργεί ως απόδειξη για την ποιότητα των λύσεων, και τέλος προτείνονται κάποιες εναλλακτικές σχετικά με τη μορφή του προβλήματος και τη μορφή του γενετικού αλγορίθμου που χρησιμοποιήθηκε.
|
|---|
