NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download". Try It in NetLogo Web

## ΓΕΝΙΚΗ ΠΕΡΙΓΡΑΦΗ

Η προσωμοίωση γίνεται σε έναν λαθύρινθο που κατασκευάζεται τυχαία στην αρχή. Είναι μία επίδειξη της λειτουργίας των γενετικών αλγορίθμων και δεν αποσκοπεί στο να βρίσκει τη λύση του λαβυρίνθου. Για αυτό, αφού υπολογίσει την κλειστή λύση του λαβυρίνθου θέτει έναν αρχικό πληθυσμό από τυχαίες χελώνες οι οποίες εξελικτικά προσπαθούν να βρουν τη διαδρομή προς την έξοδο.

## ΛΕΙΤΟΥΡΓΙΑ - ΠΕΡΙΓΡΑΦΗ ΤΩΝ ΑΛΓΟΡΙΘΜΩΝ

### Δημιουργία του λαθυρίνθου

Ο λαβύρινθος αρχικά έχει διαστάσεις 17x17. Το κάτω αριστερό άκρο έχει συνταταγμένες (-8,-8) και το πάνω δεξιά (8,8). Όλο το πρόγραμμα όμως είναι προσαρμοσμένο στο να αντιμετωπίζει οποιδήποτε διάσταση για το λαβύρινθο. Η αλλάγή μπορεί να γίνει από το "settings" στο "interface" του προγράμματος όπου αλλάζουμε την τιμή για το max_xcor και το max_ycor (8 είναι το default). Αυτόματα αλλάζουν και οι αντίστοιχες για τα min_xcor και min_ycor. Εφόσον αλλάξουμε τη διάσταση ή ανεξάρτητα από το αν την αλλάξουμε, μπορούμε από το "patch size" να προσαρρμόσουμε το μέγεθος του λαθυρίνθου στην ανάλυση της οθόνης που χρησιμοποιούμε.

Η είσοδος του λαβυρίνθου θα βρίσκεται πάντα στο (-8,-7) (<- (min_xcor,minycor+1)) και η έξοδος στο (8,7) (<- (max_xcor, max_yocr-1)). Όλα τα υπόλοιπα περιμετρικά σημεία του λαθυρίνθου είναι τοίχοι (λευκά patches). Αρχικά turtles (στον κώδικα έχουν το breed "workers"), ξεκινούν περιμετρικά από τον λαβύρινθο και προχωρούν τυχαία στο εσωτερικό τους φτιάχνοντας τοίχο στο σημείο που βρίσκονται, αν δεν δημιουργεί αυτή η κατασκευή ένωση με τον τοίχο κάποιου άλλου worker. Έτσι εξασφαλίζεται η ύπαρξη λύσης.

### Κλειστή λύση του λαβυρίνθου

Όπως είπαμε, αρικά λύνουμε τον λαβύρινθο με κλειστό (ντετερμινιστικό) τρόπο. Το πρόγραμμα χρησιμοποιεί τη μέθοδο Flood Fill, ξεκνώντας από το την έξοδο και τερματίζει αφού επισκεφτεί κάθε patch που δεν είναι τοίχος. Έπειτα χρωματίζει μία από τις βέλτιστες λύσεις (μπορεί να είναι και μοναδική), για να μπορεί εύκολα ο παρητηρητής να αναγνωρίζει αργότερα την πρόοδο στις γενιές των χελώνων. Μετά τον τερματισμό της εύρεσης λύσης κάθε patch έχει αποθηκεύσει στην εσωτερική του μετταβλητή "step", την απόστασή του σε βήματα από την έξοδο του λαβυρίνθου. Οι τοίχοι έχουν την τιμή 1000 αλλά αυτή η τιμή δεν παίζει κάποιο ρόλο.

### Ο γενετικός αλγόριθμος

Υπάρχουν αρκετοί τρόποι για να υλοποιηθεί ένας γενετικός αλγόριθμος. Εδώ υλοποιήθηκε μία απλή μέθοδος αφού ο σκοπός είναι διδακτικός και σε δευτερεύοντα ρόλο η αποδοτικότητα.

Αρχικά έχουμε ένα πληθυσμό χελωνών (στον κώδικα έχουν το breed "mazers") με τυχαία χρωμοσώματα που έχουν αλυσίδες DNA αποτελούμενες από τις βάσεις "r", "l" και "f". Αυτές αποτελούν τον γονότυπο των mazers. O φαινότυπος είναι η διαδρομή που κάνει κάθε mazer ξεκινώντας από την είσοδο και ακολουθώντας τις εντολές του γενετικού του κώδικα: με "r" ο mazer στρίβει και κινείται δεξιά, με "l" ο mazer στρίβει και κινείται αριστερά και με "f" ο mazer κινείται μπροστά.

Στη συνέχεια υπολογίζονται τα fitness των mazers. Το fitness είναι η απόσταση του patch στο οποίο τερματίζει η κίνηση του mazer, υψωμένη στο τετράγωνο για να δημιουργεί μεγάλη απόκλιση συν κάποιο πέναλτυ που δίνεται κάθε φορά που ο mazer χτυπάει σε τοίχο. Όταν ο mazer φτάνει στην έξοδο, το fitness γίνεται 0. Άρα το καλύτερο fitness είναι το μικρότερο και το ζητούμενο από τον αλγόριθμο είναι η ελαχιστοποίησή του.

Στο επόμενο βήμα γίνεται η επιλογή (selection). Η μέθοδος που χρησιμοποιεί είναι το tournament selection, με μεγάλο δείγμα (το ένα τρίτο όλου του πληθυσμού) για να παρουσιάζει σταθερότητα ο αλγόριθμος (δεν χάνονται εύκολα οι καλές λύσεις αλλά έχουμε αργή πρόοδο). Προφανώς η μέθοδος δεν αξιοποιεί την απόκλιση στο fitness του πληθυσμού, αλλά η απόκλιση δημιουργήθηκε με στόχο την μελοντική υλοποίηση και άλλων μεθόδων επιλογής. Επίσης καθορίζεται με παράμετρο από τον χρήστη το ποσοστό του πληθυσμού που θα διασταυρωθεί και το υπόλοιπο προκύπτει με αντιγραφή (clone) του ήδη υπάρχοντα πληθυσμού.

Τέλος η διασταύρωση (crossover) γίνεται με τον απλό τρόπο του τυχαίου κοψίματος του χρωμοσώματος. Τα τέσσερα κομάτια που δημιουργούνται από τα δύο χρωμοσώματα των γονέων επανενώνονται σταυρωτά για να δημιουργήσουν τα δύο χρωμοσώματα που θα κληρονομήσουν τα δύο παιδιά. Αμέσως μετά οι αλυσίδες περνούν από τη διαδικασία της μετάλλαξης (mutation) που καθορίζεται με ποσοστό από τον χρήστη. Με αυτό τον τρόπο δημιουργείται η νέα γενιά και συνεχίζει να εκτελείται ο αλγόριθμος υπολογίζοντας τα fitness της νέας γενιάς.

## ΟΔΗΓΙΕΣ - ΠΕΡΙΓΡΑΦΗ ΤΟΥ INTERFACE

Αρχικά με το **"καινούριο περιβάλλον"** δημιουργούνται οι workers που θα κατασκευάσουν τον λαβύρινθο. Επίσης μαρκάρεται το περίγραμμα του λαβυρίνθου με τους τοίχους, την είσοδο και την έξοδο. Οποιαδήποτε αλλαγή στις διαστάσεις του λαβυρίνθου πρέπει να γίνει πριν πατηθεί το πλήκτρο.

Έπειτα με το **"κατασκευή του λαβυρίνθου"** εφαρμόζεται ο αλγόριθμος κατασκευής από τους workers. Με το τέλος της κατασκευής ξαναπατάμε το πλήκτρο για να σταματήσουν οι workers, και με το **"τέλος κατασκευής"** σβήνονται (πεθαίνουν) οι workers για να ελευθερωθεί η μνήμη.

Έπειτα πατάμε το **"κλειστή λύση"** για να υπολογιστούν οι αποστάσεις που θα χρησιμοποιηθούν στον υπολογισμό του fitness. Η διαδικασία τελειώνει μόλις χρωματιστεί η βέλτιστη διαδρομή από την είσοδο στην έξοδο. Για αισθητικούς λόγους και μόνο, ξαναπατάμε το πλήκτρο για την απενεργοποίησή του. Στο τέλος σε κάθε patch του λαβυρίνθου μπορούμε να δούμε με δεξιό κλικ την τιμή της μεταβλητής step που δείχνει την απόσταση σε βήματα του patch από την έξοδο.

Με το πλήκτρο **"αρχικός πληθυσμός"** δημιουργείται η πρώτη γενιά από mazers, εμφανίζονται στον λαβύρινθο και υπολογίζεται το fitness τους.

Πλέον ενεργοποιώντας το πλήκτρο **"επόμενη γενιά"** υπολγίζονται συνεχώς με τον τρόπο που περιγράφουμε πιο πάνω οι επόμενες γενιές των mazers.

Τα τρία sliders που υπάρχουν αλλάζουν τις παραμέτρους του γενετικού αλγορίθμου. Το **"population-size"** τον αριθμό των mazers που θα έχει κάθε γενιά, το **"mutation-rate"** την πιθανότητα μετάλλαξης στην κάθε βάση που υπάρχει στα χρωνοσώματα και το **"crossover-rate"** το ποσοστό του πληθυσμού που στην νέα γενιά θα διασταυρωθεί, ενώ το υπόλοιπο προκύπτει με αντιγραφή. Και τα τρία sliders μπορούν να αλλάζουν ακόμη και αν ο αλγόριθμος είναι online.

Κάτω αριστερά υπάρχουν οι δύο διαγράμματα για την εποπτεία πάνω στην πορεία του αλγορίθμου. Το πρώτο δείχνει τον αριθμό των mazers που έχουν φτάσει στην έξοδο, ενώ το δεύτερο δείχνει την πορεία του fitness στον πληθυσμό (μικρότερο-μέσο-μεγαλύτερο). Και τα δύο διαγράμματα μπορούν σε κάθε στιγμή να κάνουν επανεκκίνηση με δεξιό κλικ πάνω στο διάγραμμα και "clear".

## ΣΤΡΑΤΗΓΙΚΗ - ΠΑΡΑΤΗΡΗΣΕΙΣ

## ΕΠΕΚΤΑΣΗ (TODO)

* εμφάνιση slider για την παραμετρικοποίηση του μεγέθους του δείγματος στο tournament selection. (Σε αυτήν την έκδοση το μέγεθος είναι αρκετά μεγάλο για τους λόγους που περιγράφονται πιο πάνω)

* εμφάνιση chooser για την επιλογή διαφορετικών τεχνικών στην επιλογή (selection). Συγκεκριμένα μία καλή τεχνική είναι η τεχνική της ρουλέτας η οποία λαμβάνει υπόψην της και την απόκλιση του fitness. Για την υλοποίησή της όμως πρέπει να γίνει κατάλληλος μετασχηματισμός για να μετατραπεί το πρόβλημα σε πρόβλημα μεγιστοποίησης.

* εμφάνιση συμβιωτικού και ανταγωνιστικού πληθυσμού στον λαθύρινθο με υποβοηθητικούς ή αντιφατικούς σκοπούς αντίστοιχα, για τη μελέτη και εποπτεία των σημείων ισσοροπίας του αντίστοιχου διαφορικού μοντέλου.

## ΒΙΒΛΙΟΓΡΑΦΙΑ
* Kramer, Oliver (2017) Genetic Algorithm Essentials, Springer

* [NetLogo manual](https://ccl.northwestern.edu/netlogo/docs/)

* Χρησιμοποιήθηκε κώδικας από το [Simple Genetic Algorithms model](https://ccl.northwestern.edu/netlogo/models/SimpleGeneticAlgorithm) που βρίσκεται στην NetLogo Sample Models Library.

##  CITATION

* Mouratidis, C. (2021) NetLogo mazer with genetic algorithm

* Wilensky, U. (1999) NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

## COPYRIGHT AND LICENSE

[](https://creativecommons.org/publicdomain/zero/1.0/)

Public Domain: Christophoros Mouratidis has waived all copyright and related or neighboring rights together with all associated claims and causes of action with respect to this model to the extent possible under the law.

<!-- 2021 CC0 Cite: Mouratidis, C. -->