Notxor tiene un blog

Defenestrando la vida

Algoritmos genéticos

Notxor
2020-10-13

Hace un par de días alguien preguntó en el grupo de Telegram si alguno de nosotros tenía experiencia con los algoritmos genéticos en erlang. Fue una pregunta bastante directa y sorpresiva, porque en general en el grupo se habla más de Lisp y Emacs. Alguien preguntando por erlang y por algoritmos genéticos: dos fricadas dignas de atención, fue todo un reto. No me he podido resistir.

Definición

Como sabéis un algoritmo es la descripción de un proceso o procedimiento para conseguir un resultado. Formalmente, según la RAE1:

conjunto de instrucciones o reglas definidas y no ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.

El nombre proviene del matemático persa de nombre Al-Juarismi2. Por los años que este señor habló de algoritmos evidentemente no existían computadoras que echarse a la punta de los dedos, así que quizá nos tengamos que modernizar un poco y repasarnos la Tesis Church-Turing3.

Sin embargo, en nuestro caso, el algoritmo lleva además el apellido genético... y ese aspecto no está relacionado con matemáticos ni con informáticos. Curiosa, o naturalmente, el apellido a este tipo de algoritmos se lo puso un biólogo: Richard Dawkins4. En su libro el relojero ciego5 propone un pequeño programa informático para ilustrar cómo funciona el algoritmo de la selección natural y la evolución.

El tema que intenta explicar Richard Dawkins es la intervención del azar en el proceso de la selección natural. El programita que hace el autor es muy simple de entender: toma aquella metáfora de los monos y las máquinas de escribir escribiendo alguna obra literaria completa... me refiero al teorema del mono infinito o de los infinitos monos. Viene a explicar, que el azar puro no soluciona ningún problema6, sin embargo, el punto importante, más importante que el de el azar, es el de la selección.

El algoritmo genético, lo podemos representar así:

algoritmo-genetico.png

El procedimiento no es totalmente aleatorio, sino que tiene una finalidad. En la selección natural, la finalidad es el mejor ajuste al medio ambiente, en el proceso informático o de la ingeniería, igualmente, es la mejora en el resultado.

Algoritmos biológicos

También hay que advertir, que puedes encontrar por ahí información sobre algoritmos biológicos. Realmente, el algoritmo genético es uno de esos algoritmos biológicos. Hace poco hablaba de las redes neuronales, que podrían ser consideradas como una forma particular de lo que es un algoritmo biológico. El Algoritmo Genético sería otra de esas formas particulares.

Como se puede ver, hay veces en que imitar a la naturaleza para resolver algún problema es la manera más directa de hacerlo. ¿Por qué? Pues porque, realmente, la naturaleza nos lleva muchas iteraciones de ventaja y ha encontrado soluciones para las cosas más dispares.

Para explicar cómo funciona el algoritmo genético veamos un ejemplo.

Ejemplo

Me vais a permitir que imite a Richad Dawkins y rehaga su ejemplo. Cuando él lo escribió, estaba intentando demostrar que la selección natural, aunque los cambios en el genoma se produzcan al azar, no es un proceso puramente aleatorio, sino regido por un entorno selectivo. Para ello, proponía encontrar una cadena de texto aplicando el algoritmo genético a la selección de las sucesivas generaciones de cadenas en las que se producen las mutaciones aleatorias. Cada carácter tendría la consideración de un gen individual y la cadena completa sería el genotipo... estirando la analogía.

El ejemplo que aparecía en el libro de Dawkins utilizaba sólo caracteres en mayúsculas, y sólo los que se emplean en inglés. En mi ejemplo lo he extendido un poco a los caracteres imprimibles ASCII. Tampoco contemplo las tildes y las eñes. Es decir, entre los valores ASCII 32 y 126. Esto es, el conjunto de genes que puede expresar nuestro genoma es:

!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

Atención, porque también está el espacio en blanco, pero como está al principio, no se observa muy claramente. Por otro lado, prescindo de los caracteres especiales como la «ñ» o las tildes, dejando la inclusión de las mismas al lector más aventurero, si quiere hacer un script que funcione en utf-8 ─por ejemplo─. Lo dejo así por no añadir las complejidades de conversiones de códigos de caracteres y que nos podamos despistar.

La cadena que he utilizado para la mayoría de las pruebas ha sido: Esto es un Ejemplo... Sí, ya sé que no soy muy original, pero era dar la tecla arriba para las distintas pruebas que he hecho. Aunque el comando era muy sencillo:

./genoma "Esto es un Ejemplo..."

Esa cadena del ejemplo, tiene 21 caracteres contando los espacios en blanco, que como acabo de decir, entran en el conjunto de genes. Como explica Dawkins cuando los creacionistas critican que los cambios en la evolución se produzcan de forma aleatoria ─olvidándose del mecanismo de la selección─, porque calculan la probabilidad de un cambio de todo o nada: conseguir la cadena buscada en un tiempo razonable es casi imposible. Repitamos esos cálculos con nuestro ejemplo:

  1. Elegimos entre 94 genes (caracteres), luego la probabilidad de que se exprese uno y no otro es de 1/94.
  2. Por tanto, la probabilidad combinada de que aparezcan dos caracteres determinados será \(1/94 \times 1/94\), el que aparezcan tres será \(1/94 \times 1/94 \times 1/94 \dots\)
  3. Es decir, la probabilidad de que nuestra cadena aparezca tal cual están escritos y completamente al azar es de \(1/94^{21}\) o dicho de otro modo: habrá una posibilidad entre \(94^{21}\), es decir, una posibilidad entre:

    272.699.866.663.574.113.970.678.989.393.688.730.271.744
    

Os pido perdón por ser incapaz de leer ese número con soltura... los billones de billones se quedan cortos y, en teoría, tendríamos que lanzar los dados todas esas veces para tener una sola oportunidad de conseguir la frase propuesta. Es como jugar a la lotería, aunque creo que en la lotería tienes más posibilidades de que toque... Tan ínfima probabilidad, dicen los creacionistas, hace imposible la aparición azarosa de organismos complejos7. Pero repito, que eso es porque no conocen, o si lo conocen lo obvian, el algoritmo genético.

Para demostrarlo, siguiendo las páginas escritas por Richard Dawkins, me he hecho un pequeño escript8 que evoluciona cadenas en el rango de caracteres que dije antes. Lo he hecho correr varias veces, y el resultado es que encuentra el genoma ─la cadena buscada─, con entre 3.500 y 10.000 generaciones, iteraciones o mutaciones, unos pocos segundos de proceso en un ordenador que ha cumplido ya los 12 años. Incluso en el peor de los casos. Nada que ver con las cifras calculadas para conseguir toda la cadena de una sola tirada.

El código

Vamos a analizar las distintas partes que intervienen en el algoritmo y el código que las implementa. Al final pondré todo el código del programita para que, el que quiera, lo pueda trastear.

Primera generación

El mecanismo de la selección parte siempre de un organismo ya existente y consiste en seleccionar aquellos individuos que mejoran o se adaptan mejor a las circunstancias. No hablo sólo de selección natural en la que el mecanismo está marcado por la naturaleza, no sólo para sobrevivir, sino también para tener oportunidad de reproducirse9. Es el mecanismo que el hombre ha utilizado para seleccionar al perro partiendo de otros cánidos salvajes. Por ello, debemos partir de nuestra primera cadena y la generamos completamente al azar:

primera_generacion(Largo) ->
    lists:map(fun(_) ->
                   obtener_caracter_al_azar()
              end,
              lists:seq(1,Largo)).

Esa función nos devuelve una cadena con el largo que expresa su parámetro Largo. Como sabéis no hay bucles en erlang y la función lo que hace es generar una lista secuencial de números del 1 hasta el Largo: lists:seq(1,Largo). A partir de ella genera una lista formada por caracteres al azar.

La función obtener_caracter_al_azar/0, en la que se apoya la anterior es muy sencilla:

obtener_caracter_al_azar() ->
    %% con valores ASCII entre 32 y 126 al azar
    %% Los 94 caracteres imprimibles entre 32 y 126.
    31 + rand:uniform(95).

En erlang las cadenas son listas de caracteres, ─números enteros, al fin y al cabo─, así pues, lo que hace es devolver un valor numérico entre 32 y 126, que son los caracteres que nos hemos dado como genes básicos.

Para generar dicha primera cadena, pues, lo que se hace en el inicio es llamar a la función primera_generacion/1 con la longitud de la cadena empleada:

Generacion = primera_generacion(length(Cadena)),

Evolución

La función que realiza la evolución tiene dos partes importantes, como vengo explicando: la modificación azarosa y la selección de los resultados de esas modificaciones. La he llamado evoluciona/3. Pongo el código y la explico más despacio después, junto con sus funciones auxiliares:

evoluciona(Genoma,Cadena,Generacion) ->
    Valor_Genoma_Inicial = valor_genoma(Cadena, Genoma),
    io:format("Distancia genoma: ~p, genoma: ~p, generación: ~p~n", [Valor_Genoma_Inicial,Genoma,Generacion]),
    case Valor_Genoma_Inicial of
        0 ->
            io:format("Soluciona la secuencia del genoma en ~p generaciones.~n",[Generacion]);
       _ ->
            Nuevo_Genoma = mutar_genoma(Genoma),
            Valor_Genoma_Evolucionado = valor_genoma(Cadena, Nuevo_Genoma),
            if
                Valor_Genoma_Evolucionado < Valor_Genoma_Inicial ->
                    evoluciona(Nuevo_Genoma, Cadena, Generacion + 1);
                true ->
                    evoluciona(Genoma, Cadena, Generacion + 1)
            end
    end.

Los parámetros que recibe son tres:

  1. Genoma: La cadena que está evolucionando.
  2. Cadena: La cadena de texto original buscada, para poder comparar.
  3. Generacion: Un simple contador para saber el número de generaciones (iteraciones) que se han realizado en el Genoma para que consiga igualarse a la Cadena.

Para que, tanto evolución como selección, funcionen me apoyo en otras funciones auxiliares:

  1. Por un lado, necesitamos tener un modo de comparar un genoma con otro para poder seleccionarlo. El mecanismo es muy básico y se encuentra en la función valor_genoma/2:

    valor_genoma(Cadena,Genoma) ->
        %% Aprovechamos que en erlang las cadenas son listas de números
        %% que representan los caracteres individuales.
        Distancia =
            lists:map(fun(N) ->
                 Valor = lists:nth(N,Cadena) - lists:nth(N,Genoma),
                 if Valor < 0 -> Valor * -1;
                    true -> Valor
                 end
            end,
            lists:seq(1,length(Cadena))),
        lists:sum(Distancia).
    

    Esta función compara las cadenas que recibe como parámetros Cadena y Genoma. Lo hace carácter a carácter calculando la distancia numérica entre ellos y después sumando las distancias individuales. Si la distancia final, o valor del genoma, es 0 tendremos que ambas cadenas recibidas son idénticas.

  2. Establecido el criterio de selección en el punto anterior, también necesitamos algún mecanismo de cambio, o evolución: eso lo hago con la función mutar_genoma/1:

    mutar_genoma(Cadena) ->
        Mutar_gen = rand:uniform(length(Cadena)),   % Mutamos sólo un gen (caracter) de la cadena
        Valor = obtener_caracter_al_azar(),
        {Inicio, [_|Cola]} = lists:split(Mutar_gen - 1, Cadena),
        Inicio ++ [Valor|Cola].
    

    Básicamente lo que hace es decidir al azar qué gen se va a mutar, obtener un valor al azar para ese gen y sustituirlo devolviendo la cadena resultante.

Como vemos en la función evoluciona/3 el programa funciona mientras el valor del genoma que está siendo evolucionado no sea 0. Cuando alcanzamos el 0 sabemos que se ha alcanzado la cadena buscada. Para cualquier otro valor, se obtiene un nuevo genoma y su correspondiente valor. Si dicho valor se aproxima más a cero que el valor de la generación anterior, se itera con el nuevo genoma y si no es así, se itera con el genoma anterior. Por tanto, y para resumir, el factor de selección consiste en que sólo se cambia el genoma evolucionado cuando está más cerca del ajuste, o lo que es lo mismo, más parecida a la cadena propuesta.

Disparador del escript

Para lanzar todo el proceso se utiliza, además, un poco de código que, siendo parte del script, no perteneces realmente al algoritmo, lo único que aporta es leer la entrada desde la línea de comandos y correr el resto del código:

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname genoma
main([Cadena]) ->
    try
        Generacion = primera_generacion(length(Cadena)),
        evoluciona(Generacion,Cadena, 1)
    catch
        _:_ ->
            uso()
    end;
main(_) ->
    uso().

uso() ->
    io:format("Uso: genoma \"cadena de texto\"\nNo se contemplan tildes ni otros caracteres especiales.\n"),
    io:format("Los caracteres utilizables deben estar entre los siguientes:~n ~p~n", [lists:seq(32,126)]),
    halt(1).

Como podemos ver, la cabecera establece qué programa debe ejecutar dicho script:

#!/usr/bin/env escript

Después, las siguientes líneas son parámetros para otros programas. Concretamente la primera le dice a Emacs que utilice el modo erlang al editarlo y la segunda establece algunos parámetros para el intérprete del lenguaje:

%% -*- erlang -*-
%%! -smp enable -sname genoma

El resto del funcionamiento es fácil: la función main/1 intenta generar una primera generación en base a la Cadena que reciba desde la línea de comandos y luego, evoluciona dicha generación hasta encontrar, mediante selección, la cadena deseada. Si se produce algún fallo se mostrará el mensaje de cómo usar el script llamando a la función uso/0.

El código completo

Analizadas las partes, no voy a dar más explicaciones sobre el script, son 65 líneas de código y pienso que quien haya llegado hasta aquí es capaz de entenderlo. No he puesto demasiados comentarios, pues iba a explicar el funcionamiento detalladamente en el artículo, aunque podéis encontrar algún comentario que no esté explicado en este texto.

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname genoma
main([Cadena]) ->
    try
        Generacion = primera_generacion(length(Cadena)),
        evoluciona(Generacion,Cadena, 1)
    catch
        _:_ ->
            uso()
    end;
main(_) ->
    uso().

uso() ->
    io:format("Uso: genoma \"cadena de texto\"\nNo se contemplan tildes ni otros caracteres especiales.\n"),
    io:format("Los caracteres utilizables deben estar entre los siguientes:~n ~p~n", [lists:seq(32,126)]),
    halt(1).

valor_genoma(Cadena,Genoma) ->
    %% Aprovechamos que en erlang las cadenas son listas de números
    %% que representan los caracteres individuales.
    Distancia =
        lists:map(fun(N) ->
             Valor = lists:nth(N,Cadena) - lists:nth(N,Genoma),
             if Valor < 0 -> Valor * -1;
                true -> Valor
             end
        end,
        lists:seq(1,length(Cadena))),
    lists:sum(Distancia).

obtener_caracter_al_azar() ->
    %% con valores ASCII entre 32 y 126 al azar
    %% Los 94 caracteres imprimibles entre 32 y 126.
    31 + rand:uniform(95).

mutar_genoma(Cadena) ->
    Mutar_gen = rand:uniform(length(Cadena)),   % Mutamos sólo un gen (caracter) de la cadena
    Valor = obtener_caracter_al_azar(),
    {Inicio, [_|Cola]} = lists:split(Mutar_gen - 1, Cadena),
    Inicio ++ [Valor|Cola].

primera_generacion(Largo) ->
    lists:map(fun(_) ->
                   obtener_caracter_al_azar()
              end,
              lists:seq(1,Largo)).

evoluciona(Genoma,Cadena,Generacion) ->
    Valor_Genoma_Inicial = valor_genoma(Cadena, Genoma),
    io:format("Distancia genoma: ~p, genoma: ~p, generación: ~p~n", [Valor_Genoma_Inicial,Genoma,Generacion]),
    case Valor_Genoma_Inicial of
        0 ->
            io:format("Soluciona la secuencia del genoma en ~p generaciones.~n",[Generacion]);
       _ ->
            Nuevo_Genoma = mutar_genoma(Genoma),
            Valor_Genoma_Evolucionado = valor_genoma(Cadena, Nuevo_Genoma),
            if
                Valor_Genoma_Evolucionado < Valor_Genoma_Inicial ->
                    evoluciona(Nuevo_Genoma, Cadena, Generacion + 1);
                true ->
                    evoluciona(Genoma, Cadena, Generacion + 1)
            end
    end.

Conclusiones

Los algoritmos genéticos se basan en un script similar, hecho en los años 80, por un biólogo que intentaba explicar cómo funciona la evolución, poniendo un ejemplo del algoritmo que subyace en ese mecanismo. Posteriormente, comprendiendo cómo funcionan estos chismáticos, se han empleado en varias otras disciplinas, ─no sólo la informática o la programación─, para trabajar sobre la optimización de distintos procesos.

El mecanismo de selección puede ser también engañoso o no tan optimizado como se espera. Parte siempre de las pequeñas mejoras obtenidas con anterioridad y así pueden evolucionar también aproximaciones no óptimas. Por ejemplo, en el libro de Dawkins aparece el ejemplo del ojo humano. Brevemente explicado: en el ojo de los mamíferos, nos encontramos los conos y bastones apuntando hacia el interior del ojo10. Por contra, en el ojo de los pulpos nos encontramos los receptores de luz apuntando hacia afuera. Eso nos dice que, al menos dos veces, han evolucionado órganos de visión funcionales. También, que las soluciones pueden necesitar evolucionar de forma paralela y no sólo aquellas aproximaciones más cercanas, sino también es posible que puedan requerir algo de supervisión por parte del programador que las utiliza y probar con otras ramas evolutivas prometedoras que a priori no sean tan efectivas pero tengan la potencialidad de generar un resultado final más óptimo.

Desde luego, si intentara conseguir de un sólo golpe azaroso la cadena propuesta podría estar iterando el intento durante el resto de mi vida y con casi plena seguridad, no se conseguiría la replicación del genoma. Sin embargo, utilizando el mecanismo de evolución y selección, en relativamente pocas generaciones y unos pocos segundos se consigue la cadena deseada.

Evidentemente, si la cadena que introducimos desde la línea de comandos es más corta implicará menos generaciones y si es más larga multiplicará las iteraciones necesarias. Sin embargo, siempre son más asequibles esos procesos que el azar puro.

Y con esto y un bizcocho... ¡evolucionad, evolucionad, malditos!

Footnotes:

1

Bueno, según el diccionario de la Real Academia de la Lengua.

2

Abu Abdallah Muḥammad ibn Mūsā al-Jwārizmī (Abu Yāffar), supongo que lo conoceréis u os sonará. Allá por el año 800. Se le considera el padre del álgebra y le debemos ese término, además del de algoritmo o guarismo.

3

A Turing, supongo que lo conocéis todos. Y aqué Church es el mismo del cálculo lambda, no una, o la, Iglesia.

4

Quizá os suene como un activista defensor de la evolución y el ateísmo enfrentándose al creacionismo y su teoría del diseño inteligente.

5

Rirchard Dawkins The blind watchmaker. 1986. Lectura muy recomendable, si no lo has leído aún.

6

A no ser que te toque la primitiva que algún problema solucionará, por lo menos lo que se solucionen con dinero: la tontería no me la quita, pero puestos a elegir prefiero ser tonto con dinero que tonto sin él.

7

En eso tienen razón, pero obvian el mecanismo de selección que consiste en que el azar sólo interviene en añadir pequeños cambios. Si el cambio es beneficioso se perpetúa y si no lo es, desaparece.

8

sí, script con e, recordad que escript es la herramienta de scripting de erlang.

9

La cola y los colores del macho de pavo real lo hacen una presa más fácil que las hembras, porque tiene llamativos colores y vuela con dificultad para alejarse de los depredadores. Sin embargo, si la cola fuera más reducida o menos vistosa, las hembras no lo elegirían como pareja reproductiva, así pues, el genoma del macho guardara un difícil equilibrio entre la supervivencia y la posibilidad de reproducción del individuo. Una optimización imposible de conseguir con azar puro.

10

Los sensores de luz apuntando en dirección contraria a la entrada del estímulo luminoso.

Categoría: erlang algoritmo evolución

Comentarios

Debido a algunos ataques mailintencionados a través de la herramienta de comentarios, he decidido no proporcionar dicha opción en el Blog. Si alguien quiere comentar algo, me puede encontrar en esta cuenta de Mastodon, también en esta otra cuenta de Mastodon y en Diaspora con el nick de Notxor.

Si usas habitualmente XMPP (si no, te recomiendo que lo hagas), puedes encontrar también un pequeño grupo en el siguiente enlace: notxor-tiene-un-blog@salas.suchat.org

Disculpen las molestias.