79. (Noviembre 2016) Composición algorítmica (III)
Imprimir
Escrito por Paco Gómez Martín (Universidad Politécnica de Madrid)   
Martes 22 de Noviembre de 2016

1.Técnicas matemáticas de composición

Esta entrega es la tercera de la serie composición algorítmica. En la primera [Góm16a] dimos una visión general de algoritmo (con ejemplos tomados de [CLRS01Knu73]) e ilustramos ese concepto con algoritmos de ordenación. Allí insistimos en la importancia de distinguir entre algoritmo y código. En la segunda entrega [Góm16b] reflexionamos sobre la definición de composición musical. Como decíamos en la introducción de esa entrega, por composición musical se puede entender un gran rango de prácticas y merecía la pena reflexionar sobre ellas antes de entrar en la descripción de las técnicas de composición algorítmica propiamente dichas. En este artículo estudiaremos algoritmos genéticos y los procesos estocásticos.

La idea de componer mediante algoritmos ya apareció antes de la propia invención del ordenador. Si se interpreta el concepto de algoritmo como una solución constructiva a un problema, entonces se encuentran precedentes de la composición algorítmica moderna ya en el Renacimiento. Durante este periodo eran relativamente populares los juegos de dados para componer música. Componían a partir de un conjunto de fragmentos que juntaban según el orden dado por las tiradas de un dado. La primer pieza de que tenemos noticia que se compuso con un ordenador fue escrita por Hiller e Isaacson [HI79] en 1957. Era un cuarteto de cuerda y usaron un ordenador de la Universidad de Illinois. La composición algorítmica cobró un gran impulso cuando en 1991 Horner y Goldberg en la IV Conferencia Internacional sobre Algoritmos Genéticos presentan un artículo [HG91] donde muestran como aplicar los algoritmos genéticos a la composición musical. Los algoritmos genéticos como tales fueron presentados por John Holland a principios de los años 70 [Hol92].

2. Algoritmos genéticos y composición musical

2.1. Descripción de los algoritmos genéticos

La expresión algoritmo genético viene de que están inspirados (y descritos) en la biología, en particular, en la teoría de la evolución genético-molecular. Vamos a describir los elementos formales de un algoritmo genético y luego ver cómo se aplican a la composición musical.

Un algoritmo genético está diseñado para resolver algún tipo de problema (para nosotros será obtener una composición musical). La solución se obtiene a través de un proceso iterativo que converge hacia dicha solución. Un algoritmo genético tiene los siguientes elementos:

  1. Una población inicial de candidatos a solución del problema. La población inicial recibe otros nombres como soluciones potenciales, individuos, criaturas. Los individuos tienen una serie de características que los definen y que son los fenotipos.
  2. La información del fenotipo es codificada de una manera específica (binaria, con frecuencia). Esta codificación constituye el genotipo. Cada conjunto de valores del genotipo recibe el nombre de cromosomas.
  3. Se empieza un proceso iterativo, llamado evolución, en el cual el fenotipo de la población cambia a través de una serie de operaciones, llamadas operadores genéticos, entre los que se incluyen selección, recombinación o cruzamiento, mutación y reemplazo.
  4. Para evaluar la idoneidad de un candidato a solución se define una función de aptitud, o simplemente función de evaluación, sobre los candidatos y que toma valores numéricos. La función se aplica en cada paso de la evolución y se espera que las soluciones sucesivas mejoren las propiedades de las generaciones anteriores. Este proceso se llama también evaluación de la descendencia.

Un aspecto importante a tener en cuenta en el diseño de los algoritmos genéticos es cómo codificar la información. Los operadores genéticos actuarán sobre la codificación de las propiedades de los candidatos a solución. La codificación tiene que ser lo suficientemente potente y flexible como para que recoja las propiedades y sea fácil aplicar los operadores genéticos. Véase el libro de Melanie Mitchell [Mit96] para más detalles técnicos sobre el diseño de algoritmos genéticos.

En la figura 1 se muestra un esquema del funcionamiento de un algoritmo genético.

Composición algorítmica (III)

PIC

Figura 1: Esquema del funcionamiento de un algoritmo genético (figura tomada de [Lat16])

Vamos a poner un ejemplo tomado de unas notas de clase bastante claras e instructivas publicadas por el Intelligent System Group de la Euskal Herriko Unibertsitatea [Int16]. La descripción del algoritmo se basará en la figura 2, que proporciona un pseudocódigo del algoritmo genético estándar.

Composición algorítmica (III)

Figura 2: Pseudocódigo de un algoritmo genético (figura tomada de [Int16])

Los algoritmos genéticos tratan de resolver problemas de optimización, con frecuencia la obtención de un máximo o mínimo global de una función. Como dijimos arriba, la población inicial representa las soluciones potenciales del problema. La codificación típica suele ser binaria, en parte porque es muy flexible y en parte por tradición histórica (Holland lo presentó así en su trabajo inicial [Hol92]). En nuestro ejemplo, usaremos también la codificación binaria. En realidad, la elección de la codificación depende en buena medida del problema. La analogía entre genotipo —la composición genética de un organismo—y el fenotipo —y la forma en que esa composición se expresa—se traslada aquí asignando a los valores de las variables independientes el papel del fenotipo y al de su codificación final el papel del genotipo. Los valores de las variables independientes, vistas como vectores numéricos, son los cromosomas. La función de adaptación sirve para evaluar la adaptación al problema de un cierto individuo (solución potencial al problema). La figura 3 ilustra estos conceptos para la función de una variable f(x) = x2. La primera columna es el número de individuo; la segunda contiene los fenotipos o valores de la variable independiente así como su codificación binaria o genotipo; la tercera columna, el valor decimal del genotipo; la cuarta columna muestra el valor de la función de adaptación.

Composición algorítmica (III)

Figura 3: Genotipo, fenotipo y función de adaptación (figura tomada de [Int16])

Durante la fase reproductiva (las iteraciones sucesivas del algoritmo), se seleccionan individuos de la población para cruzarse (véase la quinta columna de la figura 3). Dicho cruce ocurre por medio de los operadores genéticos. Una vez seleccionados dos individuos para cruzarse, sus cromosomas se combinan. El cruce y la mutación son dos de los operadores más frecuentes. En el operador de cruce se elige un punto al azar del cromosoma y se intercambian los códigos genéticos entre dos individuos; véase la figura 4.

Composición algorítmica (III)

Figura 4: Operador de cruce (figura tomada de [Int16])

El operador de cruce no se aplica a todos los individuos sistemáticamente, sino que se establece una función de probabilidad para determinar las parejas de individuos que sufrirán el cruce genético.

El otro operador, el de mutación, no consiste más que en cambiar un valor del cromosoma de un individuo. También lleva asociado una distribución de probabilidad. Se aplica a cada hijo, pero la probabilidad de mutación suele ser pequeña; véase la figura 5.

Composición algorítmica (III)

Figura 5: Mutación de un cromosoma (figura tomada de [Int16])

Si el algoritmo genético está implementado correctamente, entonces se supone que la adaptación media y la adaptación del mejor individuo se acercarán al máximo o mínimo global buscados. Normalmente, se toma como solución final la adaptación del mejor individuo.

2.2. Algoritmos genéticos aplicados a la composición musical

La composición a través de algoritmos genéticos despertó un gran interés desde principios de los años 90 y existe una gran variedad de caminos para usarla. Algunos de esos caminos son:

  1. Composición de variaciones de un motivo o composición existentes [Ral95Jac96].
  2. Composición de música similar a otra composición dada [Hoc06].
  3. Composición de solos o improvisación de melodías a partir de plantillas existentes (por ejemplo, se dan las duraciones o las secuencias de acordes) [Jac96OE08].
  4. Composición de las alturas y de las duraciones a la vez a través del algoritmo genético [Jac96,  Bil94].

Veamos a continuación cómo pasar los elementos del algoritmo genético al contexto musical. En nuestro ejemplo tomaremos dos parámetros musicales: altura y ritmo. Para el caso de la altura, fijaremos el do central como nota de referencia y a partir de ella, contando en semitonos, codificamos las alturas; véase la figura 6.

Composición algorítmica (III)

Figura 6: Codificación de altura de sonidos

La duración se puede codificar de muchas maneras. A veces se codifica dando el tiempo en milisegundos; otras veces se define una duración mínima y todas las demás duraciones son múltiplos de esta; o también se puede usar el sistema del midi, donde se define el número de pulsos por negra en relación al tempo expresado en partes por minuto. En nuestro caso, supondremos que la duración mínima es la semicorchea y pondremos todas las duraciones en función de ella. Hay que añadir una variable que indique si estamos en presencia de un silencio o de una nota; será 0 si es silencio y 1 si es nota. Entonces, la codificación para el primer compás de la figura 6 es:

(0,0,2),(3,1,2),(6,1,2),(7,1,2),(8,1,6),(7,1,2)

donde el primer campo es la altura, el segundo el indicador de nota o silencio y el último la duración.

Elegir una función de adaptación que tenga significado musical es todavía un problema abierto. La música es demasiado compleja para que haya una función de expresión sencilla que produzca resultados aceptables. La forma general de la función de adaptación que se ha empleado en diversos sistemas es:

f = a1f1 + a2f2 + ...+ anfn

donde cada fi es un factor musical del sistema y ai un peso que se da a dicho factor. Ejemplos de dichos factores podrían ser el número de intervalos disonantes, el número de apariciones de ciertos patrones interválicos, la frecuencia de ciertos intervalos, el rango de la melodía, entre muchos otros. La determinación de los pesos ai es también una cuestión muy delicada; no se sabe cómo elegirlos y normalmente se hace de una manera subjetiva o al menos aproximada. Esta fórmula implica que los factores fi tienen la misma preponderancia en todos los compases o en todas las partes de la composición. Se puede generalizar la función para que los pesos de los factores cambien de compás a compás. Si suponemos que la pieza tiene m compases la función es ahora

f = a11 f1 + a21f2 + ...+ an1fn + ......+ a1mf1 + a2mf2 + ...+ anmfn

donde el peso aij representa el peso del factor i en el compás j.

Los operadores genéticos se pueden definir de muchas maneras en la codificación musical. He aquí una breve descripción de las más frecuentes:

  1. Cruzamiento de la melodía. Se toman dos melodías, se cortan en cierto puntos y se intercambian los fragmentos entre sí. La tonalidad se tiene en cuenta y se trasponen acorde a ella.
  2. Mutaciones. En el ámbito de las alturas se tienen: cambios de octava en un tono (para evitar, por ejemplo, los intervalos grandes); cambio de un tono; cambio de una nota cromática. En el ámbito de las duraciones: cambios de las duraciones (con los correspondientes ajustes en el compás); cambio de figuración.

En la figura siguiente tenemos el resultado musical obtenido por Bruce Jacob [Jac96]. En este ejemplo se ha partido de unos motivos básicos que han constituido la población inicial. La función de evaluación incluye parte de evaluación humana.

Composición algorítmica (III)

Figura 7: Composición musical usando algoritmos genéticos (figura tomada de  [Jac96]

En el siguiente vídeo tenemos una charla en la que se explica detalladamente una implementación de los algoritmos genéticos en Phyton:

En este otro vídeo se ve la evolución de una melodía. Los factores usados son autosimilitud, linealidad, tonalidad y rango.

Bibliografía

[Bil94] J.A. Biles. Genjam: A genetic algorithm for generating jazz solos. In Seventh International Conference on Genetic Algorithms, 1994.

[CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. McGraw-Hill Book Company, Cambridge, London, 2. edition, 2001. 1. editon 1993.

[Góm16a] P. Gómez. Composición algorítmica (i). Consultado en julio de 2016.

[Góm16b] P. Gómez. Composición algorítmica (ii). Consultado en octubre de 2016.

[HG91] A. Horner and D. Goldberg. Genetic algorithms and computer-assisted music composition. In Fourth International Conference on Genetic Algorithms, San Mateo, CA, 1991.

[HI79] L. A. Hiller and L. M. E. Knuth Isaacson. Experimental music: Composition with an electronic computer. Greeenwood Publishing Group Inc., 1979.

[Hoc06] R. Hochreiter. Audible Convergence for Optimal Base Melody Extension with Statistical Genre-Specific Interval Distance Evaluation. Lecture Notes in Computer Science, 3907, 2006.

[Hol92] John Holland. Adaptation in Natural and Artificial Systems. MIT, Cambridge, MA, 1992. Edición revisada de la de 1975.

[Int16] Intelligent System Group (EHU). Algoritmos genéticos. Consultado en octubre de 2016.

[Jac96] B.L. Jacob. Algorithmic Composition as a Model of Creativity. Organized Sound, 1(3):157–165, 1996.

[Knu73] Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley, 1973.

[Lat16] Proyecto Latin. Algoritmos genéticos clásicos. Consultado en octubre de 2016.

[Mit96] Melanie Mitchell. An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 1996.

[OE08] E. Özcan and T. Erçal. A Genetic Algorithm for Generating Improvised Music. Lecture Notes in Computer Science, 4927, 2008.

[Ral95] D. Ralley. Genetic algorithm as a tool for melodic development. In Proceedings of the 1995 International Computer Music Conference, San Francisco, CA, 1995.

 
Volver