Jugando con autómatas celulares (14)

2013-09-17

Hace varios artículos, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Hasta ahora, habiamos trabajado con autómatas deterministas. Hoy vamos a sofisticar un poco nuestra biblioteca para poder trabajar con autómatas no deterministas, es decir, autómatas en el que las reglas fijan no cambios que se producen siempre, sino probabilidades de cambio.

Regla no determinista

Vamos a escribir la regla no determinista como una función referencialmente transparente o pura. Solamente tenemos que suministrar números pseudoaleatorios externamente para obtener un comportamiento aparentemente no determinista; una secuencia conocida nos daría resultados trivialmente repetibles. La función generadora de reglas, stochastic-rule, acepta un argumento con una sintaxis similar a la de deterministic-rule en la que las claves son estados de los conjuntos de vecinos y los valores son, en vez de los estados próximos correspondientes, tablas que asocian probabilidades con nuevos estados. Veamos esto con un ejemplo. Supongamos que tenemos un vecindario compuesto por tres celdas (la de la izquierda, la propia celda y la de la derecha, por ejemplo) y dos estados posibles (0 y 1). El nuevo estado de la celda es el estado anterior una de cada diez veces, el complementario del estado anterior dos de cada diez veces y el producto del estado de la izquierda y el estado de la derecha siete de cada diez veces. La tabla que define esta regla es así:
'(((0 0 0) ((1/10 0) (2/10 1) (7/10 0))) ((0 0 1) ((1/10 0) (2/10 1) (7/10 0))) ((0 1 0) ((1/10 1) (2/10 0) (7/10 0))) ((0 1 1) ((1/10 1) (2/10 0) (7/10 0))) ((1 0 0) ((1/10 0) (2/10 1) (7/10 0))) ((1 0 1) ((1/10 0) (2/10 1) (7/10 1))) ((1 1 0) ((1/10 1) (2/10 0) (7/10 0))) ((1 1 1) ((1/10 1) (2/10 0) (7/10 1))))
Esta función generadora de reglas devuelve una función regla que acepta un número aleatorio random-number y una lista neighbours con los estados de los vecinos. Con un valor dado de neighbours y muchos valores de random-number distrubuidos uniformemente entre 0 y 1, la salida de la función regla tendería a seguir una distribución de Bernoulli generalizada con las probabilidades dadas. Podemos hacer esto sin más que acumular las probabilidades y coger el resultado correspondiente a la probabilidad acumulada más pequeña que supera el valor del número aleatorio. Una versión poco eficiente es así:
(define (stochastic-rule table) (lambda (random-number neighbours) (let* ((probabilities (map car (cadr (assoc neighbours table)))) (outcomes (map cadr (cadr (assoc neighbours table)))) (thresholds (cumulative-map + 0 probabilities))) (do ((threshold (car thresholds) (car remaining-thresholds)) (remaining-thresholds (cdr thresholds) (cdr remaining-thresholds)) (outcome (car outcomes) (car remaining-outcomes)) (remaining-outcomes (cdr outcomes) (cdr remaining-outcomes))) ((<= random-number threshold) outcome)))))
La versión en Python es menos densa:
def stochastic_rule(table): def rule(random_number, neighbours): probabilities, outcomes = table[neighbours].items() thresholds = cumulative_map(lambda a, b: a + b, 0, probabilities) for threshold, outcome in zip(thresholds, outcomes): if random_number <= threshold: return outcome return rule
Podemos hacer algo similar en Scheme de varias formas. La siguiente usa continuaciones:
(define (stochastic-rule table) (lambda (random-number neighbours) (call-with-current-continuation (lambda (return) (let* ((probabilities (map car (cadr (assoc neighbours table)))) (outcomes (map cadr (cadr (assoc neighbours table)))) (thresholds (cumulative-map + 0 probabilities))) (for-each (lambda (threshold outcome) (if (<= random-number threshold) (return outcome))) thresholds outcomes))))))

Hay muchas formas de utilizar las reglas no deterministas. Podríamos hacer un código funcional puro en la medida de lo posible, pero habría que crear varias funciones nuevas para pasar los números aleatorios directamente (con una pequeña generalizacion de apply-rule) o encapsular los números aleatorios en la lista de celdas o en la lista de vecinos. Vamos a seguir una alternativa más corta que no es funcional pura, pero sí parece mucho más práctica: modificar únicamente la regla para que vaya generando números aleatorios internamente. Podemos hacer una función wrap-with-generator que acepte una función de dos argumentos (como nuestra regla) y una función generadora que vaya devolviendo valores nuevos a cada invocación, valores que usar como primer argumento de la función de dos argumentos. Es así:
(define (wrap-with-generator function generator) (lambda (argument) (function (generator) argument)))
Es igual en Python:
def wrap_with_generator(function, generator): return lambda argument: function(generator(), argument)
Si tenemos un generador de números aleatorios distribuidos uniformemente entre 0 y 1, podemos usarlo con stochastic-rule y wrap-with-generator para crear una regla aleatoria.

Generación de números pseudoaleatorios

Vamos a hacer un generador de números pseudoaleatorios que funcione igual en Scheme y en Python. Hay muchos tipos de generador con méritos variados; nosotros vamos a usar uno que quizá no vale para mucho más que para dar el pego, pero tiene la ventaja de que es muy cortito.
(define (linear-congruential-generator previous multiplier increment modulus) (modulo (+ (* multiplier previous) increment) modulus))
Es así en Python:
def linear_congruential_generator(previous, multiplier, increment, modulus): return (multiplier * previous + increment) % modulus
Este generador acepta un valor anterior previous y unos parámetros multiplier, increment y modulus para generar el siguiente valor de una secuencia pseudoaleatoria. La calidad de los resultados, que no va a ser excelente, depende de los parámetros.

Vamos a crear una función que devuelve un generador de números aleatorios distribuidos uniformemente entre 0 y 1 a partir de un valor semilla seed que sirve para determinar el estado inicial. Podemos hacerlo con linear-congruential-generator y unos parámetros que dan resultados bastante decentes:
(define (uniform-generator seed) (lambda () (let ((multiplier 1103515245) (increment 12345) (modulus 2147483648)) (set! seed (linear-congruential-generator seed multiplier increment modulus)) (/ (inexact->exact seed modulus)))))
Eso era Scheme. En Python es así:
def uniform_generator(seed): memory = [seed] def generate(): multiplier = 1103515245 increment = 12345 modulus = 2147483648 memory[0] = linear_congruential_generator(memory[0], multiplier, increment, modulus) return float(memory[0]) / 2147483648 return generate
Hacer clausuras con estado mutable es un poco más complicado en Python que en Scheme, pero no es imposible.

Podemos juntar todo así para crear una regla aleatoria:
(wrap-with-generator (uniform-generator 0) (stochastic-rule '(((0 0 0) ((1/10 0) (2/10 1) (7/10 0))) ((0 0 1) ((1/10 0) (2/10 1) (7/10 0))) ((0 1 0) ((1/10 1) (2/10 0) (7/10 0))) ((0 1 1) ((1/10 1) (2/10 0) (7/10 0))) ((1 0 0) ((1/10 0) (2/10 1) (7/10 0))) ((1 0 1) ((1/10 0) (2/10 1) (7/10 1))) ((1 1 0) ((1/10 1) (2/10 0) (7/10 0))) ((1 1 1) ((1/10 1) (2/10 0) (7/10 1))))))

Otros artículos de la serie

Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/09/17/jugando-con-automatas-celulares-14/

SGCG