Εξελικτικοί αλγόριθμοι

[satafaka]

Καλησπέρα σε όλους.

 

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

 

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

 

Το πρόγραμμα λοιπόν θα πρέπει με έναν ΕΞΕΛΙΚΤΙΚΟ ΑΛΓΟΡΙΘΜΟ να βρίσκει την βέλτιστη λύση. Βέλτιστη λύση θεωρούμε ότι όλοι πήραν τις πρώτες τους επιλογές, αλλά συνάμα παίξαν ρόλο και τα κριτήρια γιατί είναι απολύτως λογικό να συμπέσουν πολλές δηλώσεις για την ίδια πτυχιακή.

 

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

 

Την μετάλλαξη δεν την βάζουμε στο παιχνίδι, τουλάχιστον για αρχή μέχρι να ξεκαθαρίσουμε τα αρχικά. Το πρόγραμμα θα γραφεί σε php.

 

Αν έχει κάποιος καμία ιδέα και ξέρει παρακαλώ ας μπει στον κόπο να βοηθήσει.

 

Ευχαριστώ πολύ.

[groot]

Είσαι σίγουρος ότι θέλεις EA; 

 

 

Πιο πολύ για optimization μου κάνει.... και στο score θα μπορεί να μπαίνει στάθμιση για το πόσο πιο μακριά από το 1 είναι η επιλογή πτυχιακής για τον φοιτητή. Π.χ., εάν πάρει την δεύτερη έχει score +1. Εάν την τρίτη, τότε +2 κ.ο.κ. 

[satafaka]

Ναι πρέπει να γίνει με ΕΑ.

 

Έχω κολλήσει στο εξής. Τρέχει την 1ην φορά ο αλγόριθμος και παράγει τυχαία αποτελέσματα (έναν τυχαίο γονέα δηλαδή).

Εγώ πρέπει να φτιάξω νέους γονείς ούτως ώστε κάποια στιγμή να αξιολογήσω τους 2 από αυτούς και να φτιάξω νέο παιδί.

 

Με πιο κριτήριο θα σταματήσω να φτιάχνω γονείς για να κάνω την αξιολόγηση των 2 από αυτών? 

[Lanike71]

 

 

Το πρόγραμμα λοιπόν θα πρέπει με έναν ΕΞΕΛΙΚΤΙΚΟ ΑΛΓΟΡΙΘΜΟ να βρίσκει την βέλτιστη λύση. Βέλτιστη λύση θεωρούμε ότι όλοι πήραν τις πρώτες τους επιλογές, αλλά συνάμα παίξαν ρόλο και τα κριτήρια γιατί είναι απολύτως λογικό να συμπέσουν πολλές δηλώσεις για την ίδια πτυχιακή.

 

 

 

Ο εξελικτικός, έχω την εντύπωση ότι δε βρίσκει απαραίτητα τη βέλτιστη λύση.Βρίσκει το βέλτιστο, για όσο τρέξει (αν τρέχει για ώρα και δε βρει κάτι καλύτερο, σταματάει).Γι' αυτό βάζουμε και μεταλλάξεις στο παιχνίδι, για να βρεθούμε κοντά στο βέλτιστο.

Ναι πρέπει να γίνει με ΕΑ.

 

Έχω κολλήσει στο εξής. Τρέχει την 1ην φορά ο αλγόριθμος και παράγει τυχαία αποτελέσματα (έναν τυχαίο γονέα δηλαδή).

Εγώ πρέπει να φτιάξω νέους γονείς ούτως ώστε κάποια στιγμή να αξιολογήσω τους 2 από αυτούς και να φτιάξω νέο παιδί.

 

Με πιο κριτήριο θα σταματήσω να φτιάχνω γονείς για να κάνω την αξιολόγηση των 2 από αυτών? 

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

Αν μπορείς να διαβάσεις java, ρίξε μία ματιά εδώ:

 

http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3

[satafaka]

Βρήκα και αυτό http://www.abrandao.com/2015/01/21/simple-php-genetic-algorithm/το οποίο είναι κάτι αντίστοιχο (σχεδόν ίδιο) με αυτό που μου έδωσες σε Java. 

 

Θα διαβάσω και άλλο και θα τρέξω και τον κώδικα για να πιάσω παραπάνω το νόημα.