Διάφορα Ζητήματα Εξελικτικών Αλγορίθμων

Α. (5/15) Θεωρείστε το πρόβλημα της εύρεσης της συντομότερης διαδρομής διαμέσου ενός συνόλου πόλεων, έτσι ώστε κάθε πόλη να επισκέπτεται μόνο μια φορά και επιστροφή στην πόλη-αφετηρία (το Πρόβλημα Περιοδεύοντα Πωλητή).  Υποθέστε ότι για να λύσουμε αυτό το πρόβλημα, χρησιμοποιούμε ένα γενετικό αλγόριθμο, στον οποίο τα γονίδια είναι οι συνδέσεις μεταξύ δύο πόλεων. Για παράδειγμα, ένας σύνδεσμος μεταξύ London και Paris, αναπαρίσταται από ένα απλό γονίδιο “LP”. Υποθέστε επίσης ότι η κατεύθυνση του ταξιδιού, δεν παίζει ρόλο και είναι LP=PL (συμμετρικό πρόβλημα). Πόσα γονίδια θα χρησιμοποιηθούν στο χρωμόσωμα κάθε ατόμου, αν ο αριθμός των πόλεων είναι 10 και πόσα γονίδια θα περιέχει το αλφάβητο του αλγορίθμου;

Β. (10/15) Μια αεροπορική εταιρία λειτουργεί με 3 αεροπλάνα και 5 πληρώματα καμπίνας. Μόνο ένα πλήρωμα εργάζεται σε ένα αεροπλάνο κάθε μέρα και κανένα πλήρωμα δεν μπορεί να εργαστεί πάνω από 2 συνεχόμενες ημέρες. Η εταιρία χρησιμοποιεί και τα 3 αεροπλάνα κάθε μέρα. Ένας γενετικός αλγόριθμος χρησιμοποιείται για να βρίσκει τον καλύτερο συνδυασμό πληρωμάτων κάθε μέρα.

α) Τι χρωμόσωμα θα μπορούσε να αναπαριστά ένα άτομο του πληθυσμού;

β) Ποιο θα μπορούσε να είναι το αλφάβητο; Τι μέγεθος θα έχει; Δώστε ένα παράδειγμα.

γ) Να περιγράψετε μια συνάρτηση καταλληλότητας για αυτό το πρόβλημα.

δ) Πόσες λύσεις υπάρχουν σε αυτό το πρόβλημα; Είναι απαραίτητο να χρησιμοποιηθεί ΓΑ για τη λύση του; Ισχύει το ίδιο, αν η εταιρία είχε k αεροπλάνα και n πληρώματα;