Ewolucja

Poniżej opisano zasady ewolucji fraz muzycznych jaka ma miejsce w programie MusicGen. Autorzy zakładają, że czytelnik posiada podstawowe wiadomości z dziedziny Algorytmy ewolucyjne. W przeciwnym przypadku odsyłamy do książek:

• Zbigniew Michalewicz "Algorytmy genetyczne + struktury danych = programy ewolucyjne WNT, Warszawa, 1996"
• D. E. Goldberg "Algorytmy genetyczne i ich zastosowania", WNT, Warszawa, 1995

Dużo informacji związanych z tematem znajduje się również w sieci, polecamy stronę odnośników jako początek poszukiwań.

Zasady ewolucji i selekcji

Proces ewolucyji w programie MusicGen skład się z następujących faz:

• Usunięcie fraz zaznaczonych przez użytkownika jako do usunięcia ;
• Ocena fraz ;
• Selekcja fraz do krzyżowania – Selekcja jest dokonywana na podstawie rankingu pareto, na podstawie którego tworzona jest ruletka. Losowane są następnie dwa osobniki które z prawdopodobieństwem określonym przez parametry procesu ewolucji będą poddane procesowi krzyżowania tworząc nową frazę muzyczną.
• Krzyżowanie ;
• Usuwanie nadmiarowych osobników – usuwane są zawsze osobniki najgorsze względem utworzonego w poprzedniej fazie rankingu pareto.;
• Mutacja – mutacji mogą podlegać wszystkie geny każdego z osobników populacji. Prawdopodobieństwo mutacji każdego z genów jest parametrem procesu ewolucji. Niektóre z genów mają jednak zmniejszone prawdopodobieństwo mutacji. Są to geny wprowadzające duże zmiany do genotypu (np. metrum).

Zastosowany model ewolucji zakłada stałą wielkość populacji w trakcie procesu ewolucji. Odstępstwo od tej zasady jest dopuszczalne w następującym przypadku- jeżeli użytkownik usunie z populacji frazy. Nowe frazy wstawiane na miejsce usuniętych zostaną dodane jedynie jako powstałe na drodze krzyżowania. Ze wzgędu na niedeterminizm tej fazy procesu ewolucji populacja może się zmniejszyć.

Generowanie rozwiązań początkowych

Rozwiązania początkowe, występujące w procesie ewolucji, dzielimy na dwa typy:

• Rozwiązania początkowe losowe – geny takiego rozwiązania mają charakter losowy. Zastosowano jednak do takiego rozwiązania pewne ograniczenia mające na celu stworzenie frazy akceptowalnej (zgodnie z ogólnymi zasadami estetyki muzycznej). Nie są to silne ograniczenia – np. generacja rozwiązania jest przeprowadzana w taki sposób aby odległości pomiędzy dźwiękami w frazie nie były zbyt duże.
• Rozwiązania początkowe wczytywane z pliku – Istnieje możliwość dodawania pewnych np. ulubionych lub o porządanych cechach fraz muzycznych i w ten sposób sterowania procesem ewolucji fraz. W szczególnym przypadku również mogea być to rozwiązania losowe.
  

Genotyp

Genotyp osobnika (fraza muzyczna) składa się z genów opisujących następujące własności:

• Skala - jest indeksem do tablicy skal z których korzysta program MusicGen (predefiniowanych skal jest około 50, dla uproszczenia przyjęto, że dźwiękiem podstawowym jest zawsze środkowe C);
• Metrum - metrum frazy muzycznej (dla uproszczenia przyjęto, że jest stałe w całej frazie i zawsze jest wielokrotnością 1/4);
• Tempo - liczba ćwierćnut na minutę;
• Liczba taktów melodii
• Nuty – każda z nut ma takie własności jak: wysokość, położenie, długość i siła artykulacji;

Operatory

Krzyżowanie

• Krzyżowanie zwykłe – Nowy osobnik tworzony jest na podstawie dwóch "rodziców", przez losowe kopiowanie genów z jednego i drugiego osobnika ze zwiększonym prawdopodobieństwem kopiowania genu z rodzica od którego gen był kopiowany ostatnio. Geny kodujące nuty frazy muzycznej mogą być kopiowane "od początku" lub "od końca", zdecydowanie większe jest prawdopodobieństwo kopiowania "od początku". Warto zwrócić uwagę na to, że taki sposób krzyżowania zaburza w dużym stopniu brzmienie nowo powstałej frazy w stosunku do brzmienia rodziców. Przy kopiowaniu genów nie jest brane pod uwagę położenie czasowe kopiowanych nut, kolejna nuta jest dokładana zawsze za ostatnią w tworzonej frazie.
• Krzyżowanie muzyczne – W dużym stopniu jest podobne do poprzedniego. Zmiany dotyczą jednak sposobu tworzenia genów nowego osobnika odpowiedzialnych za kodowanie nut frazy muzycznej. Podczas kopiowania tych genów brane jest pod uwagę ich położenie w sensie czasowym w rodzicach, jak również wysokość kolejnych nut w obu rodzicach. Dokładniej wygląda to w następujący sposób: zawsze jest kopiowana ta z kolejnych nut w rodzicach która występuje wcześniej, a do jej wysokości sumowana jest losowa wartość (zgodnie z rozkładem normalnym) związana z wysokością drugiej nuty z pary.

Mutacja

• Mutacja prosta - Każdy z genów ma szansę mutować. Geny odpowiadające wysokości dźwięku, jego położeniu w frazie, długości i sile akcentu z jakim dźwięk jest artykułowany mają jednakowe prawdopodobieństwo mutacji. Metrum frazy muzycznej ma zmniejszone prawdopodobieństwo mutacji, jest to spowodowane faktem, że zmiana tego pojedynczego genu ma wpływ na postać całej frazy- w odróżnieniu od pozostałych. Podobnie rozwiązywana jest mutacja indeksu skali (w programie MusicGen rozpatrywana jest jedynie zamiana skali w obrębie skal pamiętanych przez program). Charakterystyki czasowe w obrębie frazy są zmieniane w sposób losowy zgodnie z rozkładem normalnym.

Nowe Krzyżowanie

W ogólności, omawiane krzyżowanie pomyślane zostało tak, by do uzyskanego wyniku przenieść jak najwięcej cech wspólnych osobników wejściowych, o ile takie cechy udało się znaleźć.

Nowy osobnik tworzony jest na podstawie dwóch "rodziców" w 2 etapach:

1. ustalanie „kompromisowych” wartości cech (kolejno: skali, długości, metrum i tempa) i transformowanie obu rodziców. Należy zaznaczyć (co jest być może pewna słabością procesu krzyżowania), ze melodie poddawane są „uzgadnianiu” i transformacji ze względu na kolejne cechy, tj. podczas wyboru nowej cechy i transformacji do niej nie bierze się pod uwagę, jak podjęte w tym etapie decyzje wpłyną na następne etapy; co więcej, podczas ustalania wspólnej wartości genu nie bierze się pod uwagę „łatwości”, z jaka można by dane frazy transformować do odpowiedniej wartości (przykład: dane są frazy 12-taktowa, w której „widać” powtórzenia 2-taktowych fragmentów i 19-taktowa, z której można „wygodnie” usunąć 5-taktowy odcinek; mimo, ze faktycznie najkorzystniejsze jest sprowadzenie obu osobników do 14 taktów, podczas losowania faworyzowane będą 15 i 16)
2. utworzenie nowej melodii na podstawie 2 osobników w jednakowej skali, metrum, tempie i o jednakowej liczbie taktów, lecz o innej liczbie nut (i – oczywiście – różnej wysokości dźwięków)

Miary odległości – wybór wartości wspólnej

Funkcje miary odległości używane są do ustalenia wspólnej wartości danego genu, gdy dwie różniące się melodie należy przetransformować do możliwie najbardziej podobnych reprezentacji oraz podczas mutacji, tak by prawdopodobieństwo przyjęcia pewnej nowej wartości było tym większe, im jest ona bliższa wartości oryginalnej.

W ogólności, prawdopodobieństwo wylosowania danej aleli jest proporcjonalne do kwadratu odległości do odpowiedniej wartości oryginalnej frazy w przypadku mutacji, a do sumy kwadratów tych odległości – w przypadku krzyżowania.

Długość melodii (w sensie liczby taktów), metrum i tempo pozwalają na bezpośrednie wzięcie ich wartości jako miary; w przypadku skali konieczne było stworzenie specjalnej funkcji odległości.

Odległość skal

Odległość od skali A do B jest zależna od 4 składników:

• różnicy w liczbie stopni (liczonej względem liczby stopni w skali A),
• liczbie wspólnych stopni, czyli interwałów od dźwięku podstawowego (względem liczniejszej skali),
• zgodności interwałów miedzy kolejnymi stopniami (np. wszystkie skale diatoniczne są pod tym względem zgodne, gdyż występują w nich jedynie sekundy małe i wielkie, w odróżnieniu od kilku skal, których pojawiają się sekundy zwiększone lub skali całotonowej, w której występują tylko sekundy wielkie) oraz
• zgodności interwałów pomiędzy wszystkimi stopniami skali (najczęściej wewnątrz skali można uzyskać wszystkie interwały, zdarzają się jednak wyjątki – w przypadku skali całotonowej można wykonać skok jedynie o wielokrotność całego tonu).

Transformacje

Zmiana skali

Podczas transformacji skali frazy do z góry zadanej innej skali, tworzony jest wektor par .... Należy dodać, że wspomniany "wektor mapowania" tworzony jest wyłącznie na podstawie tonów zawarytch w rozpatrywanych skalach, nie uwzględnia się więc faktycznej zawartości frazy.

Wektor budowany jest z pomocą algorytmu porównywania łańcuchów tekstowych (kolejne znaki "stringów" odpowiadają tonom tworzącym kolejne stopnie skali) tak, by możliwie jak najwięcej ich wspólnych fragmentów było mapowanych 1:1.

Zmiana długości melodii

Zmianę długości frazy można uzyskać w ogólności na 2 sposoby: usunięcia lub powtórzenia fragmentu melodii oraz rozciągnięcia lub ściśnięcia kilku taktów. Jeżeli melodia ma zostać skrócona lub wydłużona co najmniej dwukrotnie, stosuje się rozciągniecie lub ściśniecie całej melodii, równocześnie kompensując te modyfikacje zmiana tempa, tak by melodia brzmiała tak samo (przykład: dana jest fraza składająca się z 4 taktów, która trzeba przetransformować do 10 – w pierwszej kolejności dzieli się ją na 8 taktów, podwajając tempo i zachowując metrum, a dopiero po tej operacji wykonywane jest wydłużenie o 2 takty podstawową techniką).

Usuwanie i powielanie fragmentu frazy

Wewnątrz melodii szuka się przedziałów o długości całkowitej liczby taktów, takich, ze:

1. zarówno początek jak i koniec przedziału znajdują się „wewnątrz” odgrywanych dźwięków, wtedy wymaga się dodatkowo, by były to dźwięki tej samej wysokości

lub

2. początek i koniec przedziału znajdują się „wewnątrz” pauz.

Rozpatrywane są także przedziały o długości różniącej się od pożądanej, w szczególności bierze się pod uwagę nie usuwanie żadnego fragmentu z melodii (co jest szczególnie istotne, gdy nie znaleziono przedziałów spełniających warunek (a) lub (b)). Prawdopodobieństwo wylosowania każdego z przedziałów zależne jest od zgodności sąsiedztwa: „melodycznej” - tj. bliskości (w sensie interwału muzycznego) dźwięków bezpośrednio poprzedzających i następujących po granicach przedziału oraz „czasowej” – odległość od najbliższych zdarzeń początku/końca nuty następujących po obu granicach przedziału powinny być zbliżone (podobnie zdarzenia występujące bezpośrednio przed granicami). „Zwycięzca” losowania jest usuwany z melodii (jeśli transformacja polega na skróceniu melodii) lub podwajany (w p.p.).

Jeśli wylosowany fragment miał inna długość niż różnica miedzy zadana a oryginalną długością melodii, przeprowadza się ściśnięcie lub rozciągnięcie (w obu przypadkach dwukrotne) odpowiedniej liczby sąsiednich taktów.

Zmiana metrum

Zmiana metrum odbywa sie w dwóch etapach: ustalenie nowego metrum na podtawie metrum dwóch fraz (w tym wypadku metrum fraz będących rodzicami tworzonego w procesie krzyżowania osobnika), właściwa zmiana metrum (powstającego w wyniku procesu krzyżowania osobnika).

Ustalanie nowego metrum

Nowe metrum jest losowane z przedziału < metrum_pierwszego_rodzica, metrum_drugiego_rodzica >. Przy założeniu, że metrum_pierwszego_rodzica < metrum_drugiego_rodzica i 2*metrum_pierwszego_rodzica > metrum_drugiego_rodzica. Gdy drugi z warunków nie jest spełniony metrum_pierwszego_rodzica jest zwiększane dwukrotnie (przy jednoczesnym zmniejszaniu tempa – tak by zachować charakter melodii), aż do spełnienia tego warunku. Przy losowaniu faworyzowane są wartości metrum leżące w środku wspomnianego powyżej przedziału.

Zmiana metrum

Zmiana metrum na nowe powoduje, że każdy z dzwięków melodii musi zostać przemapowany tak aby mieścił się w nowej długości taktu. Takie podejście do problemu sprawia, że dostosowywanie frazy do nowego metrum będziemy rozpatrywać dzieląc melodię na takty. W każdym takcie każda nuta zostanie przeskalowana w następujący sposób:

• Wybór punktów charakterystycznych – na płaszczyźnie X, Y gdzie X odpowiada liczba osemek (metrum) w takcie pierwszej frazy Y'owi liczba osemek w takcie drugiej frazy. Szukamy krzywej odcinkami liniowej któa będzie podstawą transformacji każdego taktu frazy do nowego metrum. Krzywa ta jest wybierana w sposób losowy.
• Transformacja wszystkich nut frazy na podstawie otrzymanej w pierwszym etapie krzywej.

Faktyczne krzyżowanie: tworzenie nowej melodii

W drugim etapie krzyżowania tworzony jest potomek 2 osobników o jednakowej skali, metrum, tempie oraz jednakowej liczbie taktów; inna może być jednak liczba nut i wysokości dźwięków.

Początki i długości nut

Przy ustalaniu miejsc zdarzeń początku i końca nut kierowano się następującymi zasadami:

1. w wynikowej frazie nuty mogą „brzmieć” tylko w tych miejscach, w których trwają jakieś dźwięki w przynajmniej jednym z osobników wejściowych (to samo dotyczy pauz);
2. liczby nut zaczynających się między dowolnymi dwoma punktami w melodiach potomków (które po transformacjach mają tę samą długość i metrum) tworzą przedział dopuszczalnej liczby nut pomiędzy tymi samymi punktami w tworzonej frazie.

Dodatkowo przyjęliśmy, że w nowej melodii dźwięki zaczynać będą się jedynie w tych punktach, w których zaczyna się przynajmniej jedna nuta z fraz wejściowych (założenie to ma zapobiec „rozdrobnieniu” rytmu). Długości nut losowane były na podstawie długości pauz (w osobnikach rodziców) poprzedzających miejsce, w którym w tworzonym osobniku miała początek następna nuta (przy zachowaniu założenia (a)).

Wysokości dźwięków

Podobnie jak w przypadku generowania rozwiązań początkowych, wysokość dźwięków ustalana jest „od końca” frazy (ostatni dźwięk ma zawsze wysokość podstawowego tonu wybranej skali). W przedziałach, które w osobnikach wejściowych odpowiadają czasowo rozpatrywanej nucie, odczytywane występujące tam nuty. Wysokość i czas trwania tych dźwięku wpływa na losowany ton wg zasady odwrotności ważonej (wg czasu trwania w ramach rozpatrywanego przedziału) sumy kwadratów odległości (tu: różnicy wysokości między tonem, którego prawdopodobieństwo wylosowania jest ustalane, a wszystkimi występującymi w rodzicach nutami). Dodatkowo obliczana jest najbardziej centralna wysokość z dopuszczalnego przedziału tonów. Różnica między tą „wartością oczekiwaną” a wybraną uwzględniana jest przy kolejnych losowaniach.

Według bardzo podobnej zasady ustalana jest siła ataku (Velocity) każdej nuty.