ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ

 

6.1     Παραδειγματα Προβληματων που επιλυθηκαν απο Γ.Α.

 

Τα προβλήματα στα οποία θα αναφερθούμε σ΄ αυτή την παράγραφο στην πλειοψηφία τους δεν είναι δυνατόν να υπολογιστούν σε κάποιο λογικό χρονικό διάστημα, δηλαδή ανήκουν στην κατηγορία των NP-complete προβλημάτων. Η επίλυσή τους απαιτεί μια διαφορετική προσέγγιση την οποία  και προσφέρουν οι Γ.Α. Μερικά από τα προβλήματα αυτά στα οποία η εφαρμογή Γ.Α. είχε σημαντικά αποτελέσματα είναι τα εξής:

 

1.    Tο εξάπιονο (1967): Μία από τις πρώτες ιστορικές εφαρμογές ήταν το παιχνίδι προσαρμογής του Bagley. Οι δύο παίχτες μετακινούν τρία πιόνια σε μία σκακιέρα 9 (3´3) τετραγώνων. Σκοπός είναι να φτάσει κάποιος στην πλευρά του άλλου.

 

2.    Kυτταρική προσωμοίωση (1970): Ο Weinberg χρησιμοποίησε Γ.Α. σε διαφορετικά επίπεδα ώστε να επιλεγεί ένα καλό σύνολο από σταθερές που θα περιγράφουν την κυτταρική προσομοίωση (Escherichia Coli μοντέλο). Ήθελε τα χρωμοσώματα να προσαρμοστούν ώστε τα χημικά συστατικά του μορίου να ταιριάζουν με τα διαθέσιμα χημικά συστατικά.

 

3.    Ιατρικές εικόνες (1984): Οι Fitzpatrick, Grefenstette και Van Gucht χρησιμοποίησαν Γ.Α. όσο και αν φαίνεται περίεργη η χρήση τους σε αυτό τον τομέα. Η προσπάθειές τους είχαν να κάνουν με την ευθυγράμμιση εικόνων σε ένα σύστημα αγγειγράφισης μέσω ψηφιακής αφαίρεσης. Η τεχνική αυτή επιτρέπει τη θέαση μιας αρτηρίας μέσω της σύγκρισης δύο ακτινογραφιών πριν και μετά από μια φυσιολογική ένεση. Η διαδικασία αυτή απαιτούσε την ακινησία του ασθενή. Επίσης, είχαν συχνά να ταξινομήσουν εικόνες πριν από τον υπολογισμό των διαφορών τους. Έτσι, χρησιμοποιούσαν Γ.Α. για να βρουν τους συντελεστές που ελαχιστοποιούσαν τις διαφορές ανάμεσα στις εικόνες, πριν και μετά από την ένεση.

 

4.    Το δίλημμα του κρατούμενου: Όπως αναφέρθηκε και σε προηγούμενο κεφάλαιο, το δίλημμα του κρατούμενου αποτελεί ένα πολύ κλασσικό πρόβλημα βελτιστοποίησης. Είναι ένα πρόβλημα συμπεριφοράς στο οποίο επιβραβεύεται και η προδοσία. Δύο άνθρωποι είναι κρατούμενοι σε κάποια φυλακή. Έχουν την δυνατότητα, είτε να συνεργαστούν μεταξύ τους είτε να προδώσει ο ένας τον άλλο, για να ελευθερωθούν. Ανάλογα με το τι επιλέγουν να πράξουν αμοίβονται ως εξής:

-     Εάν και οι δύο συνεργαστούν, τότε θα μείνουν μόνο δύο χρόνια στη φυλακή.

-     Εάν μόνο ο ένας συνεργαστεί, θα ελευθερωθεί και ο άλλος θα μείνει για 10 χρόνια έγκλειστος.

-     Εάν και οι δύο προδώσουν, η ποινή τους θα διαρκέσει έξι χρόνια.

 

Το πρόβλημα είναι ιδιαίτερα ενδιαφέρον όταν επαναλαμβάνεται. Το 1985 είχε διοργανωθεί ένα τουρνουά υπολογιστών για τη σύγκριση διαφορετικών αλγορίθμων και μεθόδων επίλυσης του. Ο Axelrod ανέπτυξε τον “eye to eye” Γ.Α. επίλυσης του προβλήματος και κατάφερε να κερδίσει στο τουρνουά αυτό.

 

5.    Το πρόβλημα του πλανώδιου πωλητή: Όπως αναφέρθηκε και σε προηγούμενο κεφάλαιο η επίλυση αυτού του κλασσικού προβλήματος γίνεται σε εκθετικό χρόνο. Ο πωλητής πρέπει να επισκευτεί ένα πλήθος από N πόλεις με το ελάχιστο δυνατό κόστος περνώντας μία φορά από καθεμιά. Για να επιλυθεί αυτό το πρόβλημα πρέπει να δοκιμαστούν όλες οι πιθανές λύσεις. Οι Γ.Α. προσφέρουν μία καλή λύση σε αποδεκτό χρονικό διάστημα.

 

6.    Χρωματισμός γράφων: Οι γράφοι χρησιμοποιούνται σήμερα για την επίλυση πολλών διαφορετικών προβλημάτων. Για παράδειγμα ένας γράφος μπορεί να αναπαριστά έναν προγραμματιστή εξετάσεων μαθημάτων. Κάποιες επιλογές μαθημάτων είναι κοινές σε φοιτητές που ανήκουν σε διαφορετικούς τομείς. Στόχος μας είναι να κάνουμε τον καλύτερο προγραμματισμό έτσι ώστε κάθε φοιτητής να μπορεί να παρευρεθεί στις εξετάσεις των μαθημάτων του και να εξασφαλίσουμε ότι η αίθουσες εξέτασης θα είναι ελεύθυρες. Το παραπάνω αποτελεί μόνο ένα απλό παράδειγμα των εφαρμογών που μπορεί να έχει ο χρωματισμός των γράφων, το πρόβλημα του οποίου έγκειται στηνεύρεση του βέλτιστου γράφου χρησιμοποιώντας τον ελάχιστο δυνατό αριθμό χρωμάτων. Οι Γ.Α. προσφέρουν και σε αυτό το πρόβλημα μια καλή λύση σε σχετικά μικρό χρονικό διάστημα.

 

 

ΑΡΧΗ ΚΕΦΑΛΑΙΟΥ