Άσκηση 6η

 

Συζητήστε το ζήτημα ¨εξερεύνηση εναντίον εκμετάλλευσης¨ (exploration vs exploitation) στους Γ.Α.

 


Λύση:

 

Στους Γ.Α. ένας πληθυσμός ατόμων μπορεί να θεωρηθεί ως η προσπάθεια αναζήτησης σε ένα n+1 διάστασης χώρο λύσεων, όπου το n είναι, για παράδειγμα, ο αριθμός των γονιδίων σε ένα χρωμόσωμα του Γ.Α. Έτσι, κάθε νέα γενιά ατόμων αντιπροσωπεύει μία νέα συλλογή από σημεία μέσα στο χώρο. Έστω ότι με R(n) συμβολίζεται η ελάχιστη περιοχή που περιέχει όλα αυτά τα σημεία για τη γενιά n.

Η εξερεύνηση και η εκμετάλλευση αποτελούν σημαντικά μεγέθη σύγκρισης των περιοχών R(n) και R(n+1). Όταν ένας Γ.Α. εξερευνά, τότε μπορεί να παρουσιαστούν μεγάλα άλματα στο χώρο των λύσεων από την τρέχουσα γενιά στην επόμενη. Έτσι, οι περιοχές R(n) και R(n+1) θα παρουσιάζουν μικρή επικάλυψη. Αντίθετα, σύμφωνα με την εκμετάλλευση, ο Γ.Α. έχει βρει κάποια καλής απόδοσης άτομα στη γενιά n τα οποία επιθυμεί να διατηρήσει και στη γενιά n+1. Δηλαδή, ο Γ.Α. επιθυμεί κάποια από τα άτομα της γενιάς n+1 να μοιάζουν (ή να είναι ακριβή αντίγραφα) με τα υψηλότερης απόδοσης άτομα της γενιάς n. Επομένως, η περιοχή R(n+1) θα είναι παρόμοια (ίσως να αποτελεί και υποπεριοχή) της R(n). 

Το ζήτημα ¨εξερεύνηση εναντίον εκμετάλλευσης¨ αποτελεί την απόφαση για είτε α)περαιτέρω εξέλιξη πολλά υποσχόμενων λύσεων/ατόμων είτε β) δημιουργία πολλών εξολοκλήρου νέων λύσεων/ατόμων.

Τυπικές τιμές που επηρεάζουν τον ανταγωνισμό ¨εξερεύνηση εναντίον εκμετάλλευσης¨ είναι οι πιθανότητες διασταύρωσης και μετάλλαξης. Όταν κάποια από τις δύο πιθανότητες είναι μεγάλη, η εξερεύνηση τίνει να υπερνικήσει την εκμετάλλευση για πολλές γενιές και πιθανόν για ολόκληρη την εκτέλεση του Γ.Α.