ΑΡΙΘΜΗΤΙΚΗ ΚΑΙ ΜΟΥΣΙΚΗ ΩΣ ΟΙ ΠΑΛΑΙΟΙ ΕΔΙΔΑΣΚΟΝ (ΙI)


(ΣΥΝΕΧΕΙΑ ΑΠΟ 9/08/13)

Κεφάλαιο Β΄
Θεωρία
ΤΗΝ πρώτη ενότητα αυτού του κεφαλαίου αναφέρονται οι βασικές λειτουργίες και η χρήση των γενετικών αλγορίθμων και η σχέση που έχουν  με την σύνθεση μουσικής. Στη δεύτερη ενότητα περιγράφονται τα κυτταρικά  αυτόματα, η λειτουργία τους καθώς και εφαρμογές σύνθεσης μουσικής με κυτταρικά  αυτόματα όπως το CAMUS, μια μηχανή σύνθεσης που συνδυάζει δύο αυτόματα, το  παιχνίδι της ζωής και το δαιμονικό κυκλικό διάστημα. Η τρίτη ενότητα αναφέρεται στη  μουσική σύνθεση και ειδικότερα στην αλγοριθμική σύνθεση ήχων μουσικής. Επίσης,παρουσιάζονται οι βασικές μέθοδοι μουσικής σύνθεσης και ιδιαίτερη σημασία δίνεται   σε αυτές που χρησιμοποιούν τους γενετικούς αλγόριθμους και τα κυτταρικά αυτόματα,
όπως η σύνθεση με μουσικές μονάδες. Τέλος, γίνεται μια μικρή αναφορά στην  σύνθεση τρισδιάστατου ήχου και τις τεχνικές που χρησιμοποιούνται, όπως η σύνθεση  ηχητικού πεδίου (wave field synthesis).

Β΄.1 Γενετικοί Αλγόριθμοι
Οι γενετικοί αλγόριθμοι αποτελούν μια μέθοδο επίλυσης προβλημάτων, για τα οποία  υπάρχουν εναλλακτικές λύσεις, αλλά η εκτίμησή της βέλτιστης λύσης τους δεν μπορεί  να γίνει αν δεν τεθούν σε εφαρμογή. Τέτοια προβλήματα είναι αυτά που έχουν πολλές  παραμέτρους / διαστάσεις και η επίλυσή τους γίνεται μια μη-αποτελεσματική   διαδικασία όσο αυξάνεται η πολυπλοκότητά τους. Επίσης, οι γενετικοί αλγόριθμοι  αποτελούν μία μέθοδο που εκμεταλλεύεται την ικανότητα του υπολογιστή να εκτελεί   ογκώδεις και συνδυαστικές διεργασίες [1, 13].
Εμπνευσμένοι από τη βιολογία και ειδικότερα από τις διαδικασίες που σχετίζονται με  την εξέλιξη των ειδών, οι γενετικοί αλγόριθμοι προσομοιώνουν μηχανισμούς που  μοιάζουν με αυτούς της φυσικής επιλογής, της διασταύρωσης και της γενετικής   μετάλλαξης. Η δυναμική αυτών των μηχανισμών έγκειται στο γεγονός ότι  επικεντρώνονται μόνο σε γόνιμους συνδυασμούς, δηλαδή σε συνδυασμούς λύσεων που  έχουν μεγαλύτερη πιθανότητα να οδηγήσουν στη βέλτιστη λύση, όπως κάνει και η
φύση [1].
Η υλοποίηση ενός γενετικού αλγόριθμου είναι μία σχετικά απλή διαδικασία, αρκεί  κανείς να κατανοήσει μερικές βασικές έννοιες της βιολογίας, όπως αυτές της φυσικής  επιλογής, της διασταύρωσης των ειδών και της γενετικής μετάλλαξης.

Β΄.1.1 Υλοποίηση γενετικών αλγορίθμων
Β΄.1.1 Κωδικοποίηση
Κάθε οργανισμός έχει κανόνες που περιγράφουν το πώς είναι φτιαγμένος,αποθηκευμένους στο DNA του. Οι αλληλουχίες DNA που περιγράφουν τα   χαρακτηριστικά των ατόμων ενός είδους ονομάζονται χρωμοσώματα και μπορούν να
είναι διαφορετικά σε κάθε οργανισμό. Τα χρωμοσώματα αποτελούνται από μικρότερες   δομικές μονάδες, τα γονίδια. Το σύνολο της πληροφορίας που αποθηκεύεται στα  γονίδια ονομάζεται γενότυπος (genotype). Τα χαρακτηριστικά ενός οργανισμού
δημιουργούνται με την αποκωδικοποίηση του γενότυπου, και αυτό που βλέπουμε  τελικά ονομάζεται φαινότυπος (phenotype)  [12].
Σε αντιστοιχία με έναν οργανισμό, ένα πολυπαραμετρικό πρόβλημα μπορεί να παίρνει  διαφορετικές τιμές για τις παραμέτρους του, όπως κάθε γονίδιο μπορεί να είναι  διαφορετικό για τους οργανισμούς που ανήκουν σε ένα συγκεκριμένο είδος.
Ακολουθώντας τους κανόνες της γενετικής, ο αλγόριθμος διατηρεί ένα σύνολο  κωδικοποιημένων πιθανών λύσεων. Η κωδικοποίηση είναι μια πολύ σημαντική  διαδικασία, γι’ αυτό και πρέπει να βρεθεί η κατάλληλη μέθοδος για το κάθε πρόβλημα.
Η πιο συνηθισμένη κωδικοποίηση είναι να αναπαρασταθεί το χρωμόσωμα σαν μια  ακολουθία δυαδικών αριθμών. Για παράδειγμα, έστω ένας πληθυσμός R  αποτελούμενος από n οντότητες, οι οποίες αναπαριστώνται από 8-bits :
R = ( r1 = 11010110, r2 = 10010111, r3=01001001 …)

Β΄.1.2 Αξιολόγηση
Στη συνέχεια, γίνεται έλεγχος του πληθυσμού-λύσεων για εξακριβωθεί αν εξυπηρετούν  τον αντικειμενικό σκοπό, δηλαδή να δώσουν την βέλτιστη λύση για το πρόβλημα ή τη  διεργασία. Η αξιολόγηση γίνεται σύμφωνα με κάποια συνάρτηση αξιολόγησης η οποία   αποτελεί μέτρο για την καταλληλότητα (fitness) του χρωμοσώματος να λύσει το
πρόβλημα. Και σε αυτή την περίπτωση πρέπει να βρεθεί η κατάλληλη συνάρτηση  αξιολόγησης για το κάθε πρόβλημα. Οι περισσότερες συναρτήσεις καταλληλότητας  είναι σχεδιασμένες ώστε μόνο ένα μικρό μέρος από τις μη- κατάλληλες λύσεις να
επιλέγεται. Αυτό βοηθάει στο να διατηρείται η ποικιλότητα του πληθυσμού,αποφεύγοντας παράλληλα την πρώιμη σύγκλιση σε φτωχές λύσεις [13].
Αν ο πληθυσμός αποτύχει στην αξιολόγηση, το σύστημα εμποδίζει την δημιουργία  επόμενης γενιάς. Μια από τις πιο δημοφιλείς συναρτήσεις αξιολόγησης είναι η   ‘επιλογή πρωταθλητή’ (tournament selection): Ανάλογα με τα αποτελέσματα της
αξιολόγησης, επιλέγονται από τον πληθυσμό οι οντότητες που δείχνουν ότι οδηγούν  στην βέλτιστη λύση. Οι επιλεγμένες οντότητες είναι αυτές που «ζευγαρώνουν» και  αναπαράγονται στην επόμενη γενιά. Οι υπόλοιπες οντότητες συνήθως πεθαίνουν και   έτσι τα χαρακτηριστικά τους δεν κληρονομούνται, συμβάλλοντας ώστε οι επόμενες  γενιές να έχουν ολοένα και πιο βελτιωμένα χαρακτηριστικά.
Από τα προηγούμενα προκύπτει το συμπέρασμα ότι κάθε εκτέλεση του γενετικού  αλγορίθμου μπορεί να συγκλίνει σε διαφορετική λύση και σε διαφορετικό χρόνο. Η  απόδοση εξαρτάται κυρίως από τη συνάρτηση καταλληλότητας και από το κατά πόσο  το μέτρο της περιγράφει την βέλτιστη λύση [13].
Άλλη μια συνάρτηση αξιολόγησης είναι ο τροχός της τύχης (roulette wheel), σύμφωνα  με την οποία κάθε άτομο αντιστοιχεί σε κάποιο τομέα του τροχού και το μέγεθός του  εξαρτάται από την καταλληλότητά του(όσο πιο κατάλληλο είναι, τόσο μεγαλύτερο το  μέγεθός του). Έτσι, η μπίλια του τροχού έχει περισσότερες πιθανότητες να σταματήσει  στα μεγάλα κομμάτια του τροχού, και αυτά να επιλεγούν [14].

Β΄.1.3 Διασταύρωση
Το επόμενο βήμα είναι αυτό της διασταύρωσης. Οι επιλεγμένες λύσεις συνδυάζονται   με τυχαίο τρόπο και κληρονομούν τα χαρακτηριστικά τους στην επόμενη γενιά. Η  διασταύρωση λειτουργεί παρόμοια με τον τρόπο της διασταύρωσης των ειδών. Όπως  τα γονίδια των δύο γονέων συνδυάζονται τυχαία μεταξύ τους και σχηματίζουν τα  γονίδια των απογόνων, έτσι και δύο λύσεις του προβλήματος ανταλλάσσουν τυχαία  κάποιες από τις τιμές των παραμέτρων τους. Στο προηγούμενο παράδειγμα, οι
οντότητες ανταλλάσσουν κομμάτια bits μεταξύ τους σχηματίζοντας διαφορετικές  λύσεις. Εάν υποθέσουμε ότι η διαδικασία της διασταύρωσης επιλέγει την ανταλλαγή    των τριών τελευταίων bit, τότε οι οντότητες r6 και r10 ανταλλάσσουν τα bits τους ως  εξής [1] :

image

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

Β΄.1.4 Μετάλλαξη
Η επόμενη βασική γενετική διαδικασία που λαμβάνει χώρα είναι η μετάλλαξη  (mutation). Στις μεταλλάξεις οφείλεται η ποικιλότητα των χαρακτηριστικών ενός   πληθυσμού, ενώ παίζουν πολύ σημαντικό ρόλο στο παιχνίδι της επιβίωσης. Στην
εξέλιξη των ειδών, οι μεταλλάξεις προκάλεσαν την αλλαγή των χαρακτηριστικών των  οργανισμών και άλλοτε λειτούργησαν αρνητικά οδηγώντας τους στην εξαφάνιση και  άλλοτε θετικά συμβάλλοντας στην επιβίωσή τους.
Κατά ένα παρόμοιο τρόπο, ειδικές συναρτήσεις προκαλούν τυχαίες αλλαγές στα bit  από οποία αποτελούνται τα χρωμοσώματα, με κριτήριο το βαθμό μετάλλαξης  (mutation rate). Στο προηγούμενο παράδειγμα, υποθέτοντας ότι η μετάλλαξη επιδρά  στο πέμπτο bit αλλάζοντας την κατάστασή του από 0 σε 1 και το αντίστροφο , οι  απόγονοι των οντοτήτων r6 και r10 θα τροποποιούνταν ως εξής [1]:

image
Όπως προαναφέρθηκε, οι μεταλλάξεις είναι πολύ σημαντικές για έναν πληθυσμό, όμως  τείνουν να δημιουργούν απογόνους που δεν έχουν τα ίδια χαρακτηριστικά με τους  γονείς τους, ειδικά όταν ο βαθμός μετάλλαξης είναι υψηλός, μειώνοντας έτσι την  αποτελεσματικότητα της διαδικασίας της επιλογής [1].
Στη συνέχεια, η συνάρτηση καταλληλότητας εφαρμόζεται και πάλι στον πληθυσμό και  εφ’ όσον αυτός πληροί τα κριτήρια, ξεκινάει και πάλι η γενετική διαδικασία.
Η γενετική διαδικασία σταματάει όταν:
Α) έχει συμπληρωθεί ένας συγκεκριμένος αριθμός επαναλήψεων.

Β) έχει βρεθεί ένας συνδυασμός χαρακτηριστικών ο οποίος ικανοποιεί την βέλτιστη
λύση του προβλήματος.
Γ) μετά από συγκεκριμένο αριθμό επαναλήψεων οι ανασυνδυασμένες λύσεις δεν
παράγουν καλύτερα αποτελέσματα.

Συνοπτικά, τα στάδια ενός γενετικού αλγόριθμου περιγράφονται παρακάτω (Σχήμα  Β΄.1):
1. Κωδικοποίηση (Coding) – Αποκωδικοποίηση (Decoding)
2. Υπολογισμός ικανότητας ή αξιολόγηση (Fitness calculation ή evaluation)
3. Επιλογή (Selection)
4. Αναπαραγωγή (Reproduction)
5. Διασταύρωση (Crossover)
6. Μετάλλαξη (Mutation)
7. Επανάληψη από το βήμα (2) μέχρι να ικανοποιηθεί το κριτήριο τερματισμού
του Γενετικού Αλγορίθμου

image

(ΣΥΝΕΧΙΖΕΤΑΙ)

About sooteris kyritsis

Job title: (f)PHELLOW OF SOPHIA Profession: RESEARCHER Company: ANTHROOPISMOS Favorite quote: "ITS TIME FOR KOSMOPOLITANS(=HELLINES) TO FLY IN SPACE." Interested in: Activity Partners, Friends Fashion: Classic Humor: Friendly Places lived: EN THE HIGHLANDS OF KOSMOS THROUGH THE DARKNESS OF AMENTHE
This entry was posted in Music and tagged , , , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s