El Algoritmo de Weasel y el teorema del mono infinito

Un mono mutante, una comadreja, una máquina de escribir y la obra de Hamlet de Shakespeare.

El teorema del mono infinito

No sé quién fue el primero en argumentar que, dado un espacio de tiempo lo suficientemente largo, un mono que pulsara las teclas de una máquina de escribir de manera aleatoria llegaría a escribir todas las obras de Shakespeare. Obviamente, la parte crucial de esta hipótesis es ‘dado un espacio de tiempo lo suficientemente largo’. De todas maneras, limitemos un poco la tarea del mono: supongamos que no tiene que escribir las obras completas de Shakespeare, sino simplemente la frase ME THINKS IT IS LIKE A WEASEL (‘yo creo que se parece a una comadreja’). Pongámosle las cosas aún más fáciles: el mono dispondrá de un teclado más sencillo de lo normal, con sólo las 26 teclas correspondientes al alfabeto inglés (todas mayúsculas) y la barra espaciadora. ¿Cuánto tiempo le llevaría al mono escribir esta frase?

Este extracto del libro ‘El relojero de ciego’, de Richard Dawkins, nos sirve para considerar la posibilidad de que producir una secuencia de 28 caracteres, asumiendo que cada uno de ellos es seleccionado aleatoriamente con un alfabeto de 27²⁸, o aproximadamente 10⁴⁰ es extremadamente reducida. Aun con una velocidad de varios millones de pulsaciones por segundo excederíamos el tiempo de vida del universo. Y esto solamente para crear la frase ME THINKS IT IS LIKE A WEASEL de manera completamente aleatoria, ya no para crear las obras completas de Shakespeare. (Para las canciones de Reggaetón puede ser menos tiempo)

El algoritmo

Encontré algunas implementaciones ya realizadas en c o pascal, pero decidí programarlo con la librería DEAP (Distributed Evolutionary Algorithms in Python) una biblioteca de Python que facilita el desarrollo de algoritmos evolutivos. Estoy usando esta librería en un proyecto y me encanta la simplicidad y adaptabilidad que tiene.

El fitness de cada individuo lo evaluaremos comparando cada carácter posición por posición con la frase objetivo. Si coincide hacemos +1 y dividimos por la longitud de la cadena.

def fitness(mutant, target):
    """
    Obtiene el fitness de que una cadena mutante tiene con respecto al objetivo.
    """
    score = 0
    length = len(target)

    # Comprobamos la igualdad de caracteres para cada posición en las cadenas
    for i in range(length):
        if target[i] == mutant[i]:
            score += 1

    # Devolvemos el score como una fracción del total de caracteres en target
    return score / length

Usaremos una selección por torneo de 3 individuos para aumentar la presión selectiva, ya que los individuos que pasen a la siguiente generación van a tener mayor fitness. Y también elitismo para asegurarnos que la frase más parecida (el mejor individuo) pase a la siguiente generación.

Iniciando la población con 100 individuos, con una probabilidad de mutar de 5% me encuentro que, en mi laptop de gama media, tarda unos 0,3 segundos y escribe la frase ME THINKS IT IS LIKE A WEASEL en menos de 100 generaciones.

Podéis encontrar el código completo en el repositorio de Github

Bonus

Dejo el programa corriendo buscando el estribillo de la canción de reguetón del cantante Colombiano Maluma — Cuatro Babys 

Mutad mucho.