Clasificar colores

Si estás buscando un algoritmo “mágico” que clasifique colores en esta entrada no lo vas a encontrar, más bien vas a descubrir lo complicado que es un tema que de primeras parece muy simple y posibles alternativas para clasificar colores.

La primera pregunta que tenemos que hacernos es ¿Cuántos colores hay?. Lo más probable es que los que están acostumbrados a trabajar con colores en el ordenador digan “unos dieciséis millones” y es cierto. Pero sería duro ponerle un nombre a cada uno así que seamos un poquito menos quisquillosos y pensemos como agruparlos. Cómo vamos a usar el sistema RGB podemos empezar por los colores que no sean mezcla de ningún otro: rojo, verde y azul. Luego los que son mezcla de otros dos colores: amarillo, cían, magenta. Por último los que son mezcla de los tres: blanco, gris y negro.

Los colores “puros” en RGB serían:

rojo (255,0,0)
verde (0,255,0)
azul (0,0,255)

amarillo (255,255,0)
cian (0,255,255)
magenta (255,0,255)

gris (192,192,192)
blanco (255,255,255)
negro (0,0,0)

Pero no basta con esos colores, claramente hay más: ocre, marrón, turquesa, naranja, morado, lila, malva, rosa…No hay una definición exacta de cuántos colores hay, ni siquiera de que significa cada nombre, algunos colores se solapan. Tanto que directamente a los colores entre los dos algunos les llaman cosas como verde-amarillos, rojo-naranjas,….

Pero aunque nos parezca que los colores son algo bastante universal no es así. Hay influencias culturales que hacen que algunos colores caigan a un lado u otro de la frontera, colores que son verdes o azules dependiendo de la cultura de donde sea el que los ve.

También hay factores fisiológicos que hacen que veamos los colores de forma diferente. No hay más que recordar alguna discusión en internet sobre de qué color es algo que aparece en una foto.

Y por último nuestra percepción de un color puede cambiar por influencia de los colores que lo rodean. Tomas un verde-amarillo lo pones junto a los verdes y lo ves amarillo, lo juntas con estos y lo ves verde. Tan sorprendente como frustrante.

Conociendo todas estas pegas y sabiendo que acertar al 100% es difícil por lo que no hay una solución ideal vamos a ver algunas soluciones.

Usar colores de referencia

Lo primero que se nos ocurre cuando hablamos de clasificar colores es tomar unos colores representativos como referencia. Cuando queramos clasificar un color medimos la distancia a cada uno de estos colores de referencia y elegimos el más cercano. Básicamente es un algoritmo del vecino más cercano. Ya hemos visto como calcular la diferencia entre dos colores, solo nos queda elegir los colores de referencia.

El problema es que no hay un espacio de color con una frontera clara y definida por lo que hace falta una gran cantidad de puntos de referencia. Generar ese listado de puntos es costoso, tiene que ser generado por humanos y resolver las diferencias de opinión entre ellos. Cómo creo que no tenemos recursos para hacer eso y tenemos que trabajar con tamaños de muestra muy pequeños el funcionamiento no es el ideal.

Espacio HSL

Una ventaja del espacio HSL (matiz, saturación, luminosidad) es que es relativamente fácil de saber el color. Basta con fijarse el valor del componente H o matiz, que viene expresado en grados o radianes. Con él ya puedes distinguir entre varios colores. Los más habituales son:

  • 0 rojo
  • 30 naranja
  • 60 amarillo
  • 120 verde
  • 180 cian
  • 240 azul
  • 300 magenta
  • 330 rosa
  • 360 rojo

La componente L el indica “la luminosidad” del color. Viene expresada en %. El 50% es el tono puro del color. Por encima los colores son cada vez más claros y por debajo más oscuros. Si es muy bajo esta cerca de color negro y si es muy claro lo está del blanco. Cómo referencia podemos usar estos valores:

  • 0, 2 negro
  • 3, 8 casi negro
  • 9, 39 oscuro
  • 40, 60 [nada]
  • 61, 91 claro
  • 92, 97 casi blanco98,
  • 100 blanco

El componente S indica la saturación del color, está expresado en %. Un valor muy bajo indica que está cercano al gris:

  • 0-2 gris
  • 3-10 casi gris
  • 10-25 grisáceo
  • 25-50 pálido

Aún así hay colores problemáticos como el marrón que surge de algunos rojos o narajas (o rojo-naranjas) muy oscuros. O los tono pastel que la mayoria surgen cuando la saturación y la luminosidad estan entre el 70% y el 85%.

Lista de colores

Hay otra opción, usar un listado de colores y sus nombres, buscar el más cercano y usarlo como respuesta. Aunque usar términos como “verde menta”, “amarillo eléctrico”, “rosa pastel” nos parezca menos exacto que los métodos anteriores, para los seres humanos resulta más fácil de entenderlos y muy intuitivos.

El principal problema es que no hay un estándar de que es el color “verde menta” puedes encontrar montones de listados y en cada uno puede un valor distinto o el mismo color llamarse de otra manera.

Las listas de colores se pueden conseguir de catálogos de pinturas, de la Wikipedia o de estándares como por ejemplo los colores web.

¿Por cual optar?

Si necesitar clasificar el color dentro de una lista cerrada de los mismos lo mejor es el primer método.

Si necesitas clasificar cualquier color dentro del espacio de colores sin tener colores de referencia.

La tercera resulta útil para mostrar resultado a los humanos.

Como convertir una aplicación de MS-DOS en una aplicación web.

Seguro que todos los que tenemos cierta edad tenemos programas desarrollados para MS-DOS que siempre hemos querido recuperar pero nunca hemos tenido tiempo de volver a programarlos en algo más moderno. En mi caso eran varios videojuegos que había desarrollado cuando era adolescente.

Para ello vamos a usar dos herramientas: DOSBox, JS-DOS (en este caso la versión 6.22).

Preparando la aplicación

Lo primero de todo es montarse DOSBox en tu ordenador e instalar la aplicación que queramos usar en la web. Vamos a llamarla programa.exe. Una vez instalada la iniciamos y la configuramos tal y como queramos que se ejecute desde la web. Si necesitamos incluir algún fichero para que lo abra la aplicación ahora es el momento.

Una vez terminado el paso necesitamos comprimir todos los ficheros necesarios para que funcione la aplicación en un fichero zip. Lo ideal sería que el ejecutable programa.exe quede directamente en la raíz del zip para que al descomprimirlo no quede dentro de ninguna carpeta.

Todo este proceso no es necesario que lo hagamos desde DOSBox, para instalar la aplicación hay que “montar’ una carpeta del ordenador como si fuera una unidad de disco de DOSBox, puedes comprimir allí los ficheros.

Ejecutandola en una web

Vamos a suponer que el fichero se llama programa.zip. Ahora vamos a preparar la web.

Necesitaremos un canvas en el que se ejecutará el emulador de MS-DOS, para referenciarlo vamos a usar el id “jsdos”. Para fijar de el tamaño del canvas usaremos CSS.

Debajo se puede ver el código completo:

<!doctype html>

<head>
    <meta charset="utf-8">
    <title>Programa.exe</title>
    <script src="js-dos.js"></script>
    <style>
        #jsdos, .dosbox-container {
            width: 800px;
            height: 600px;
        }
    </style>
</head>

<body>
    <canvas id="jsdos"></canvas>   
    <script>
    Dos(document.getElementById("jsdos"), {
        autolock: true
    }).ready(function (fs, main) {
        fs.extract("programa.zip").then(function () {
            main(["-c", "programa.exe"]).then(function (ci) {              
                window.ci = ci;
            });
        });
    });
    </script>
</body>

</html>

Su funcionamiento es sencillo y se puede entender sin demasiadas explicaciones, algunos puntos que se necesitan aclarar:

fs.extract(“programa.zip”) descomprime el fichero zip en el directorio raiz C:

main([“-c”, “programa.exe”]) el primer comando va a C: y el segundo ejecuta programa.exe

window.ci = ci; Permite acceder a la API de DosCommandInterface desde cualquier parte de la web.

autolock: true Sirve para capturar el ratón automáticamente cuando se hace click sobre el canvas. Si tu aplicación no usa el ratón para nada puedes prescindir de ponerlo.

Algunas funciones interesantes

  • Entra y salir de modo pantalla completa ci.fullscreen(), ci.exitFullscreen()
  • Realiza una captura de pantalla ci.screenshot()
  • Simular pulsacioenes de teclas ci.simulateKeyPress(keyCode), ci.simulateKeyEvent(keyCode, pressed)
  • Ejecutar comandos ci.shell([cmd1, cmd2, …])

Problemas

Aquí recopilo un listado de cosas que me han dado problemas:

  • Resoluciones raras de pantalla. Forzar la aplicación en formatos que distorsionan mucho el formato 4:3 habitual de los monitores de esa época
  • El sonido no siempre va tan bien como sería deseable
  • El ratón, muchas aplicaciones de MS-DOS usan falsos ratones, imágenes que superponen donde debería estar el ratón. Algunos dan problemas.
  • El uso desde el móvil no está resuelto, aunque no es algo fácil de solucionar. El punto bueno es que te dan la herramientas básicas para que trates de resolverlo.

Ideas interesantes

Algunas ideas interesantes que se me ocurrieron pero no he tenido oportunidad o tiempo de intentaras.

  • Aunque JS-DOS ofrece alguna formas de ejecutar múltiples comandos hay soluciones como los ficheros de procesamiento por lotes .bat
  • Se pueden asociar comandos de MS-DOS, pulsaciones de teclas o del ratón a acciones en la web esto puede dar lugar a interesantes formas de interactuar con la aplicación (incluso de hacerla más accesible)
  • Un gamepad virtual sobre el canvas donde se ejecuta la aplicación. Para usar juegos desde el móvil es imprescindible
  • Usando Apache Cordoba o PhoneGap se podría convertir la web en una aplicación móvil. Aunque no sé si tiene utilidad más allá de entretenerse un rato probando
  • Lo mismo que el punto anterior pero en el escritorio con electron

Calcular la diferencia entre dos colores

Decidir si dos colores se parecen puede parecer sencillo, basta con medir la distancia entre ambos. En formato RGB la distancia entre dos colores es:

SQRT((R1-R2)^2 + (G1-G2)^2 + (B1-B2)^2)

Desgraciadamente no funciona demasiado bien en el espacio de color RGB, que es el que se usa habitualmente en los ordenadores , por lo que tenemos que usar otro espacio. Tenemos varias alternativas las más prometedoras son:

Vamos a apostar por el último que suele ser el que mejor funciona. Esta ideado para representar el espacio de color de forma próxima a como el ojo humano los percibe.

El primer problema es que no hay una conversión directa RGB a Lab. La solución es pasar de RGB a XYZ y luego de XYZ a Lab. En esas conversiones se pierde algo de precisión pero el resultado es lo suficientemente exacto.

Debajo está el código en JavaScript para realizar la conversión de RGB a LAB

function RGBtoLAB(r,g,b){
    //RGBtoXYZ
    var x = RGBtoXYZ_RtoX[r] + RGBtoXYZ_GtoX[g] + RGBtoXYZ_BtoX[b];
    var y = RGBtoXYZ_RtoY[r] + RGBtoXYZ_GtoY[g] + RGBtoXYZ_BtoY[b];
    var z = RGBtoXYZ_RtoZ[r] + RGBtoXYZ_GtoZ[g] + RGBtoXYZ_BtoZ[b];

    if (x > 0.008856)
        x = Math.cbrt(x);
    else
        x = (7.787 * x) + 0.13793103448275862;

    if (y > 0.008856)
        y = Math.cbrt(y);
    else
        y = (7.787 * y) + 0.13793103448275862;

    if (z > 0.008856)
        z = Math.cbrt(z);
    else
        z = (7.787 * z) + 0.13793103448275862;

    L = (116 * y) - 16;
    a = 500 * (x - y);
    b = 200 * (y - z);

    return [L,a,b];
}

RGBtoXYZ_RtoX = [];
RGBtoXYZ_GtoX = [];
RGBtoXYZ_BtoX = [];
RGBtoXYZ_RtoY = [];
RGBtoXYZ_GtoY = [];
RGBtoXYZ_BtoY = [];
RGBtoXYZ_RtoZ = [];
RGBtoXYZ_GtoZ = [];
RGBtoXYZ_BtoZ = [];

for(var i = 0; i < 256; i++){  //i from 0 to 255
    r = parseFloat(i/255) ;    //r from 0 to 1

    if (r > 0.04045 )
        r = Math.pow((r+0.055)/1.055 ,  2.4);
    else
        r = r/12.92;

    r = r * 100

    var ref_X =  95.047;
    var ref_Y = 100.000;
    var ref_Z = 108.883;

    RGBtoXYZ_RtoX[i] = r * 0.4124/ref_X;
    RGBtoXYZ_GtoX[i] = r * 0.3576/ref_X;
    RGBtoXYZ_BtoX[i] = r * 0.1805/ref_X;
    RGBtoXYZ_RtoY[i] = r * 0.2126/ref_Y;
    RGBtoXYZ_GtoY[i] = r * 0.7152/ref_Y;
    RGBtoXYZ_BtoY[i] = r * 0.0722/ref_Y;
    RGBtoXYZ_RtoZ[i] = r * 0.0193/ref_Z;
    RGBtoXYZ_GtoZ[i] = r * 0.1192/ref_Z;
    RGBtoXYZ_BtoZ[i] = r * 0.9505/ref_Z;
}

En el código se usan algunas optimizaciones como usar tablas de consulta para acelerar los cálculos (RGBtoXYX_*).

Los nuevos valores obtenidos ya se pueden comparar usando la distancia euclídea.

SQRT((L1-L2)^2 + (a1-a2)^2 + (b1-b2)^2)

El resultado indica la proximidad entre dos colores, lo parecidos que son. Como referencia un resultado menor de 4 quiere decir que la diferencia entre colores apenas es perceptible a simple vista. Eso no quiere decir que este valor solo se pueda usar para saber si dos colores son iguales, también para agrupar colores similares, encontrar un color en una imagen pese a variaciones de la iluminación (buscando el color más parecido) ,…

Veamos un ejemplo, unos de los puntos débiles más fáciles de ver del espacio de color RGB son los grises. Comparamos el gris medio (128,128,128) con otros dos colores: gris oscuro (28,28,28) y dorado oscuro (128,128,0). Veamos cual de los dos sistemas es más exacto.

RGBLab
Gris oscuro173,2043,31
Dorado Oscuro12858,16
Distancias según el espacio de color que se use

Usando RGB el dorado oscuro está más cerca del gris medio que el gris oscuro, mientras que Lab da el resultado correcto.

El única información privada es la no guardada

Hablar de la privacidad de los datos como algo completamente seguro y cierto es una pequeña mentira que suelen hacer las empresas que viven de ellos. Si un dato está guardado su privacidad puede ser puesta en duda.

Envío de los datos

El primer problema es que hay que mandar los datos. Un dispositivo genera/captura el dato y debe de enviarlo a través de una red de comunicaciones hasta un dispositivo destinatario que lo almacenará. Vamos por partes:

El dispositivo origen es el primer punto débil de la cadena. Si es inseguro o está mal configurado puede filtrar los datos a un tercero y por mucho que te esfuerces en mantener seguro tu móvil o tu ordenador no basta. Muchas veces el dispositivo que envía los datos sobre ti es otro. Una estación de telefonía que envía que tu móvil está conectado a ella, un dispositivo domótico, un electrodoméstico inteligente o un caja de supermercado.

El segundo punto de ataque es el canal de comunicaciones. Todos estamos advertidos de lo inseguro que es conectarse a redes públicas, pero también las privadas pueden estar vulneradas. El router de tu casa quizás tenga una vulnerabilidad sin parchear que algún gusano en Internet ha aprovechado para infectarlo.

Lo mismo pasa con el destino. No sólo hay que fiarse de que el receptor hace un uso correcto de los datos. Sino que seguramente ha subcontratado parte de su infraestructura (bases de datos, servidores, conversión de voz a texto, reconocimiento de imágenes, estadísticas,….) a otras empresas  en las que también tienes que confiar. Y no solo es que ellos no “roben” tus datos es que sean seguros y no permitan que un tercero roben esos datos.

El gobierno siempre puede pedir tus datos

Ahora bien aunque no haya ningún problema y los datos lleguen seguros y sean almacenados de forma segura. Si el gobierno los pide las empresas están obligadas a dárselos. Y no basta con el típico: “no hagas nada para que el gobierno no te investigue”. Los gobiernos piden los  datos basándose en sospechas. Quizás mañana un algoritmo diga que eres sospechoso y pidan tus datos para verificarlo. ¿Qué ocurre luego con esos datos? ¿Se quedan guardados mientras pasa el tiempo y los gobiernos? Los gobiernos a su vez subcontratan las herramientas e infraestructuras a otras empresas y otra vez dependemos la cadena de confianza. ¿Esas empresas respetan la privacidad de nuestros datos? ¿Son seguras?.

Leyes y empresas que cambian

Ahora mismo muchas empresas prometen privacidad. Pero quién sabe si seguirán prometiendola dentro de 20 años. Puede que hayan sido comprada por otra empresa con menos escrúpulos. Que las leyes hayan cambiado. Incluso que el procesado de datos haya alcanzado niveles tales que puedan extraer información de esos datos que no quieres que sepan.

Datos cifrados

Que los datos estén cifrados ofrece cierta protección contra el robo de estos por terceros, pero no para evitar la explotación fraudulenta de los mismos por el receptor.

Al final los datos cifrados no sirven de nada y cuando se procesan tienen que estar descifrados. Durante todo ese procesado son vulnerables.

Por ejemplo si la aplicación de domótica de mi móvil permite controlar con voz las luces de casa pero ellos no han construido una librería de conversión de voz a texto ni una de procesamiento de lenguaje natural, son servicios que contratan a otras dos empresas que a su vez se guardan los datos para mejorar su sistema o para sacar estadísticas. El intercambio entre empresas es cifrado pero una de ellas no guarda los datos cifrados o lo hace pero no ha contratado a un experto y comete errores que permite su descifrado a un tercero que ha burlado sus sistemas y ha robado sus datos.

Cruzar y desanonimizar datos

Una medida muy importante es que los datos estén anonimizados. Es decir que se hayan eliminado los datos que puedan identificar a la persona que generó esos datos. El problema es que según crece la cantidad de datos más difícil es que sigan siendo anónimos.

También cabe la posibilidad de que cruzando datos anonimizados de diferentes fuentes se puedan desanonimizar. Quizas una empresa compra otras dos lo que le permite cruzar sus datos. O se filtren datos de distintas fuentes que cruzando los permita desanonimizarlos.

Exigir el borrado de datos

Gracias a leyes como la nueva normativa europea de protección de datos el usuario puede exigir que eliminen los datos que una empresa tenga de él.

Para empezar no se borran todos los datos ya que muchos se tienen que mantener por ley al menos un tiempo. Por ejemplo los datos de pagos.

Segundo en algunas arquitecturas, en las que los datos se distribuyen en varias copias en diferentes sistemas y servicios, es difícil borrar un dato. Es fácil marcar que ese dato está borrado pero su eliminación física puede ser complicada.

Tercero hay muchos procesos internos que generan copias de los datos. Por ejemplo las copias de seguridad. Es difícil que tus datos sean borrados de todas las copias de seguridad. Si bien lo habitual es sobreescribirlas cada cierto tiempo.

Por último esto solo sirve con empresas que cumplen la ley y es fácil parecer que la cumples sin cumplirla. Tampoco es que sirva con quienes roban los datos.

Metadatos

Si estás preocupado por la privacidad no sólo son importantes los propios dato también los metadatos. Los metadatos son datos sobre los datos que son necesarios generar para que muchos procesos automáticos funcionen. Por ejemplo cuando entras a una web no solo estás enviando la dirección web, también tu IP, tu navegador, tu sistema operativo y alguna cosa más. Con estos datos se pueden deducir a su vez más cosas. Por ejemplo con la IP se puede aproximar tu localización geográfica.

No solo hay metadatos en las conexiones a Internet. Hay metadatos en todas partes. En los ficheros, fotografía, música, antenas de telefonía móvil para tener cobertura….

El problema es que ni siquiera somos conscientes de estos metadatos. Si nos conectamos a una web en Internet se generan gran cantidad de metadatos para que los paquetes lleguen de nuestro PC al servidor de la web. Y carecemos de control sobre ellos.

Los datos son para toda la vida

Los datos pueden ser almacenados durante décadas. Sobrevivir a cambios de servidores, soportes físicos, tecnologías, empresas, gobiernos y leyes. Tus datos pueden sobrevivirte. Y pocas veces pensamos en que será de nuestros datos a largo plazo. Vamos a ver algunas posibilidades.

Basta con que en alguno momento un fallo de seguridad o un error conprometa la privacidad de tus datos  para que pierdas el control de ellos para siempre. No sabrás cuántas copias hay ni quién tiene una.

Con el paso de los años los avances en big data pueden permitir que los datos que cedistes hace años revelen aspectos tuyos que prefieras que no se supieran.

Las leyes pueden exigir que se tomen ciertas medidas que los datos anteriores a esas leyes no cumplen. Lo cual te dejará expuesto ante quien tenga esos datos tuyos.

Un caso de ejemplo

En 2018 se filtraron los datos de una famosa empresa de pulseras deportivas. No estoy seguro si esos datos se enviaban al servidor cifrados y completamente anonimizados pero para el caso vamos a suponer que sí. Los datos filtrados eran las posiciones GPS de las distintas pulseras a lo largo del día.

Al contar con semejante cantidad de datos varios expertos en seguridad los usaron para ver que eran capaz de sacar de ellos. Uno de los casos más espectaculares fue que lograron encontrar varias bases militares secretas.

Obviamente no sabían cuales de esos datos eran de militares estadounidenses. Pero si ves una concentración de pulseras deportivas en un punto del desierto donde no debería haber nada no es difícil llegar a la conclusión de que ahí hay algo. Es más como los daos incluían la posición GPS se puede “dibujar” una nube de puntos que muestra la forma de la base con bastante exactitud. Estoy seguro de que de esos datos se pueden concluir más cosas: una extimación de cuantos hombres hay, teniendo en cuenta la hora saber donde están los comedores o los dormitorios, turnos, descansos,…

Es un ejemplo de como con datos enviados de forma segura y anonimizados se puede poner en peligro algo más que la privacidad de una persona. Y no es que la empresa tuviera malas intenciones, pero cometió un error de seguridad y los datos se filtraron. Al final todo dato almacenado corre el riesgo de volverse en tu contra.

Máquina de estados finitos en Arduino

Vamos a ver cómo crear una máquina de estados finitos muy sencilla para Arduino o Node MCU. Debido a las limitaciones de ambas plataformas vamos a ver una idea muy sencilla.

Empezaremos por aclarar los conceptos básicos:

  • Estados: son los distintos valores que puede tomar la máquina de estados finitos.
  • Eventos: producen el cambio de un estado a otro.
  • Transiciones: definen como los eventos cambian los estados. Cada transición constan de tres elementos, un evento, un estado origen y un estado destino. Indica que cuando se produzca el evento si el estado actual es el estado origen este cambiará por el estado destino.

Una mef (máquina de estados finitos) está siempre en un único estado y hay eventos que producen el cambio de estado siguiendo unas reglas (las transiciones). Aunque con esto ya tenemos una mef, para que sea realmente útil tiene que facilitar la ejecución de funciones asociada a los distintos estados y eventos.

Para facilitar todo esto podemos usar la librería easy finite state machine que simplifica la programación usando macros del preprocesador.

Estados y eventos

Vamos a empezar por los eventos y estados, para ello podemos usar enum de C que nos permite escribir código de forma muy intuitiva.

enum efsmStates {start, step1, step2, finish};
enum efsmEvents {next, back};

O usando las macros de la libreria:

STATES {start, step1, step2, finish};
EVENTS {next, back};

También habrá que definir una variable que guarde el estado actual e inicializarla con el estado inicial.

enum States efsmState = start

Con la librería:

INIT(start)

Cambiar el valor del estado es muy sencillo, basta con hacer:

efsmState = start

O con las macros:

changeState(start)

Así como comparar el valor del estado:

isState(start)

Transiciones:

De todas formas lo habitual no es realizar los cambios de estados directamente sino a través de eventos. Los eventos vamos a gestionarlos con la función efsmEvent(event) que los aglutina todos. Esta función recibe el evento como parámetro y contiene las transiciones. Básicamente son un montón de “if”. Usando la librería se usa la macro TRANSITION

TRANSITION(evento, estadoOrigen, estadoDestino, funcion)

Su significado es: Si se lanza el evento y el estado es el estadoOrigen se pasa al estadoDestino y se llama a función. No es necesario poner una función asociada, se puede dejar en blanco.

Las transiciones se definen entre las macros:

START_TRANSITIONS y END_TRANSITIONS

Las transicione son una gran ayuda, aunque su funcionamiento se puede sustituir con isState(state) y changeState(state).

if(isState(estadoOrigen) ){
  changeState(estadoDestion);
  funcion();
}

Ejecuciones:

Cuando se ejecuta efsmExecute() verifica y llama a la función asociada a cada estados. Es decir, cuando se llama a esta función se verifica en qué estado está la máquina y llama a la función asociada a ese estado. Con la forma que tiene Arduino de funcionar usando una función loop que está en bucle constante la idea es colocar efsmExecute() en la función loop() para que se llame en cada iteración.

EXECUTION(executionState,function())

Si no se asocia ninguna función a un estado no se ejecutará nada.

Se definen entre las macros:

START_EXECUTIONS y END_EXECUTIONS

No es obligatorio definirlas. Por ejemlo cuando la mef solo tenga que lanzar funciones en los cambios de estado (transiciones).

Disparadores:

Los disparadores generan eventos asociados a distintos sucesos. Su idea es facilitar la programación de acciones habituales que lanzan eventos. Se ejecutan cuando se llama a la función efsmTriggers().

Para que un disparador se lance, el estado de la mef ha de ser el mismo que el que se le pasa como primer parámetro. Hay de tres tipos de disparadores:

Un condicional lanza un evento si el condicional especificado se cumple:

CONDITIONAL(state, condition, event)

Un contador lanza un evento después de haber llamado un número determinado de veces a la función efsmTriggers() tras al último evento válido.

COUNTER(state, number, event)

Un temporizador lanza un evento cuando ha pasado un determinado tiempo (en milisegundos) desde que se lanzó el último evento válido.

TIMER(state, number, event)

“Tras el último evento válido’ significa que cada vez que se lanza un evento y este produce una transición los contadores se reinician. Si se quisieran reiniciar a mano se pueden usar: resetTimer() y resetCounter()

Los disparadores se definen entre las macros:

START_TRIGGERS y END_TRIGGERS

No es necesario definir disparadores , si se quiere lanzar algún evento manualmente se puede hacer llamando directamente a efsmEvent(event).

En resumen:

  1. Se definen estados y eventos.
  2. Se establece el estado inicial.
  3. Se crean transiciones que indican que cambios entre estados se producen con cada evento asi como la función que se lanzara cuando se produzca esa transición.
  4. Se escriben la ejecuciones indicando que función se lanzará cuando la máquina este en cada estado.
  5. Se declaran los disparadores que lanzaran eventos (o se programa el lanzamiento a mano).
  6. Se añade a la función loop efsmExecute() y efsmTriggers()

Un ejemplo:

Para ver todo un poco más claro vamos a ver un ejemplo basado en el que incluye la librería. En el se modela la máquina de estados finitos representada en el siguiente diagrama:

Ejemplo de maquina de estados finitos
Máquina de estados finitos del ejemplo

El código es el siguiente:

#include <efsm.h>

STATES {start, step1, step2, finish};
EVENTS {next, back};
INIT(start)

START_TRANSITIONS
TRANSITION(next,start,step1,Serial.println("next")) //next start -> step1
TRANSITION(next,step1,step2,Serial.println("next")) //next step1 -> step2
TRANSITION(next,step2,finish,Serial.println("next")) //next step2 -> finish
TRANSITION(back,step2,step1,Serial.println("back")) //back step2 -> step1
TRANSITION(ANY_EVENT,ANY_STATE,ANY_STATE,Serial.println("FAIL!!!")) //in any other case
END_TRANSITIONS

START_EXECUTIONS
EXECUTION(start,Serial.println("start")) //state is start
EXECUTION(step1,Serial.println("step1")) //state is step1
EXECUTION(step2,Serial.println("step2")) //state is step2
EXECUTION(finish,Serial.println("finish")) //state is finish
END_EXECUTIONS

START_TRIGGERS
COUNTER(start,5,next); //State start wait 5 iterations and launch event next
TIMER(step1,2000,next); //State step1 wait 2 sg and launch event next
END_TRIGGERS

void setup() {
  Serial.begin(9600);
  resetTimer();
  resetCounter();  
}

void loop() {  
  efsmExecute();
    
  if(isState(step2)){
    efsmEvent(next);
  }
  efsmTriggers();
  
  delay(1000);
}

Bases biológicas de los algoritmos genéticos y evolutivos

Esto es una introducción a las bases biológicas que inspiran muchos algoritmos. Debo advertir que es una introducción escrita por un informático para gente interesada en algoritmos así que los que sepáis de biología no seáis muy duros. Soy consciente de que he hecho muchas simplificaciones.

Que algunos algoritmos estén inspirados no significa que sean copias exactas, no siempre la solución aportada por la naturaleza es la más sencilla de llevar acabo, o la que mejor se adapta a nuestros problemas por eso lo que se busca es imitar los métodos para conseguir los mismos resultados que la naturaleza. Una vez conseguida la imitación esta se puede modificar, variar o combinar para dar origen a métodos jamas intentados por la naturaleza.

Un único modelo

Actualmente el único modelo que tenemos de seres vivos es el de aquellos que nos rodean. Esto nos “limita”, ya que pese a su gran variedad toda la vida proviene de un origen en común. Nuestra definición de vida y sus características se han de basar en un único modelo.

La base de este modelo es la célula, esta es la forma de vida más simple (los virus no se considera que esten vivos), todos los seres vivos están compuestos por ellas, ya sean unicelulares o pluricelulares. Es por así decirlo el ladrillo con el que se construye la vida.

La célula

Estudiar la célula en toda su complejidad daría para varios textos como este. Para que nos sea más fácil olvidaremos el resto de funciones de la célula y la veremos como una maquina destinada únicamente a trabajar con la información del ADN.

La célula esta formada por una membrana que la separa del medio, en su interior se encuentra el citoplasma, que se divide en hialoplasma y organulos citoplasmáticos. El hialoplasma es medio que contiene a los organulos citoplasmaticos, en el se realizan numerosas reacciones químicas, esta formado en un 70% de agua y el resto son proteínas, lípidos, glucidos, etc. Los organulos citoplasmáticos desempeñan diversas funciones dentro la célula. Nosotros vamos a centrarnos en el núcleo.

El núcleo y los cromosomas

En el interior del citoplasma, separado por la membrana nuclear, se encuentra el núcleo de la célula con toda la información genética. No todas las células tienen un núcleo, en algunos casos como las algas verdeazuladas, y las bacterias, el material genético se encuentra libre en el citoplasma, las células se dividen en dos grupos según posean o no núcleo diferenciado:

  • Procariotas: Carecen de núcleo diferenciado el material genético se encuentra en el citoplasma.
  • Eucariotas: Poseen una estructura separa del citoplasma donde están los cromosomas, a esta estructura se le denomina núcleo.

El núcleo esta formado principalmente por proteínas denominadas histones y ADN que forman los cromosomas. Estos solo son visibles durante el proceso de división celular cuando se enrrollan para formar la conocida estructura con forma de X

En la mayoría de las células de los animales y plantas poseen células diploides, es decir, con dos copias de cada cromosoma. Las células con un solo juego de cromosomas se conocen como haploides. En la reproducción sexual cada progenitor aporta un cromosoma de cada par. Sabiendo esto es fácil imaginarse que las células reproductoras (gametos) serán haploides, ya que el único cromosoma por par que poseen se juntara con el del otro gameto para formar una célula diploide. Cada especie tiene un numero distinto de cromosomas.

ADN y ARN:

El ADN es una molécula constituida por dos largas secuencias de nucleótidos, ambas se enrollan sobre si mismas formando una espiral, están unidas por puentes de hidrogeno. La información esta codificada por cuatro nucleótidos; adenina (A), timina (T), guanina (G) y citosina (C) en el caso del ADN, en el ARN se sustituye la timina por el uracilo (U). Los nucleótidos se unen unos frente a otros para unir ambas cadenas de nucleotidos, la adenina se una con la timina y la citosina con la guanina de tal modo que si tenemos la secuencia ATGCA sé unirá con la TACGT. Esto significa que ambas cadenas son complementarias y que se puede codificar una a partir de la otra.

Los grupos de tres nucleotidos, se denomina codón, sirven para identificar los distintos aminoácidos, piezas estructurales de lo polipéptidos que a su vez se unen para formar proteínas. No se usan mas de veinte aminoácidos distintos, por eso hace falta tres nucleótidos par definir un aminoácido ya que si fueran dos solo habría 16 (42) combinaciones distintas, con tres se dispone de 42 (43) combinaciones. Además algunos codones se usan para guiar el proceso de transcripción del ADN, indicando donde acaba el gen (STOP) o donde empieza (START). Como sobran combinaciones varios aminoácidos están definidos por más de un codón.

1ª2ª

T C A G
T Fenilanina Serina Tirosina Cisteína T
T Fenilanina Serina Tirosina Cisteína C
T Leucina Serina STOP Selenocisteina
STOP
A
T Leucina Serina Pirrolisina
STOP
Triptófano G
C Leucina Prolina Histidina Arginina T
C Leucina Prolina Histidina Arginina C
C Leucina Prolina Glutamina Arginina A
C Leucina Prolina Glutamina Arginina G
A Isoleucina Treonina Asparagina Serina T
A Isoleucina Treonina Asparagina Serina C
A Isoleucina Treonina Lisina Arginina A
A
Metionina
START
Treonina Lisina Arginina G
G Valina Alanina Ac. Aspártico Glicina T
G Valina Alanina Ac. Aspártico Glicina C
G Valina Alanina Ac. Glutámico Glicina A
G Valina Alanina Ac. Glutámico Glicina G

El ADN codifica la información siguiendo un patrón: el inicio de la información útil es indicado por el codón ATG, a partir de ese momento si este codón vuelve a salir será interpretado como el aminoácido metionina, la traducción de codón a aminoácido sigue hasta llegar a un codón de STOP representados por TAA, TAG, TGA, aunque hay seres vivos donde los dos últimos también sintetizan aminoácidos.

Para que el ADN se traduzca de información a proteínas o a enzimas hace falta que este sea leído y transcrito; vamos a ver como se lleva a cabo este proceso. Se inicia con la transcripción de ADN a ARNm (ARN mensajero). La cadena de ADN se abre y permite que una enzima, la ARN-polimerasa copia el fragmento de ADN traduciendolo a ARNm. El fragmento es complementario con la timina sustituida por el uracilo (recuerda que es ARN) de manera que la cadena AGTCG se codificará como UCAGC.

El ARNm forma una larga y delgada cadena, esta se inserta en los ribosomas que actuan como pequeños automatas recorriendo la cadena de ARNm leyendola y ensamblando aminoacidos hasta llegar al final del gen indicado por un simbolo de STOP (UAA, UAG, UGA). La cadena de ARNm no es recorrida por un solo ribosoma sino que son varios al mismo tiempo. En el ribosoma se encuentra ARNt (ARN de transferencia), que detecta los codones usando la forma complementaria (anticodón), así el ribosoma sabe que aminoácido unir a la cadena. En el caso de las células procariotas, los ribosomas pueden empezar a trabajar antes de que se acabe de traducir el ADN a ARNm. La secuencia de nucleotidos comprendidos entre un START y un STOP definen una enzima o una proteína especifica y se denomina gen o locus.

Genes

Los genes son la unidad mínima de información hereditaria, codifican una proteína o una enzima. Hay que distinguir dos conceptos; el genotipo, la secuencia de ADN de un individuo, y el fenotipo, la manifestación física del genotipo. En individuos con un solo gen el genotipo corresponde con el fenotipo, pero en el caso de los seres con células diploides se plantea el problema de elegir cual de los dos genes se va a usar como modelo. Para solucionar esto los genes poseen distintos “pesos”. Cuando un gen se impone sobre otro se dice que es dominante y se representa con una letra mayúscula, en caso de que el gen sea enmascarado por el otro se dice que es recesivo y se representa con una letra minúscula. A cada una de las variaciones que presenta un gen se le denomina alelo.

Veamos un ejemplo, el albinismo esta relacionado con un gen en particular, es recesivo y el alelo se representa por a, la pigmentacion normal de la piel esta relacionada con el alelo A y es dominante. Por los que hay cuatro combinaciones, que realmente son tres ya que una esta repetida.

  1. AA – Pigmentación normal, ambos genes son dominantes.
  2. Aa – Pigmentación normal, no sufre albinismo pero es portador de la enfermedad
  3. aA – Pigmentación normal, no sufre albinismo pero es portador de la enfermedad
  4. aa – Albino, al tener ambos cromosomas recesivos el albinismo se manifiesta ya que no hay ningún gen para enmascararlo.

Se puedes dar el caso de que lo genes sean codominantes, ninguno domina sobre el otro, y ambos se manifiestan. Un ejemplo lo tenemos en el dondiego de noche una planta que tiene dos alelos para el color de sus flores: rojo y blanco (genotipo). Sin embargo muestra flores de tres colores: blancas, rojas y rosas (fenotipo). Las rojas y las blancas tienen ambos genes del mismo alelo (rojo o blanco), mientras que las flores rosas se produces por la codominancia de ambos alelos (rojo y blanco)

Este no es el único modelo, muchas veces un carácter esta determinado por varios genes, o un gen determina más de un carácter, un ejemplo es la herencia cuantitativa, la idea es que por ejemplo cinco genes determinaran el tamaño de una planta, un gen recesivo r hace que crezca 5 centímetros y uno dominante R que crezca 10 centímetros, así que una planta rR rr RR medirá (10+5+10) 25 centímetros y otra Rr rr rr (10+5+5) 20 centímetros se pueden ver que plantas de distinto genotipo tendrán igual fenotipo, por ejemplo rr RR Rr y RR RR rr. En la vida real los caracteres no están determinado de una manera tan sencilla y lineal.

Los genes no solo cumplen una simple función de almacén de información, también tienen una función reguladora, hay grupos de genes que se ocupan de bloquear o desbloquear la producción de enzimas y proteínas dependiendo de la cantidad de estas. Para ello un gen conocido como regulador produce una proteína represora que funciona de la siguiente manera. En cada gen existe un segmento de ADN llamado promotor al cual se adhiere la ARN-polimerasa, entre este segmento y el gen a veces existe otro segmento de ADN llamado operador al que se liga la proteína represora y evita que la ARN-polimerasa puede generar el ARNm. Dependiendo de la concentración en el medio de ciertas sustancias la proteína represora puede ser inhibida por ellas y no llegar a unirse al operador. Este mecanismo se haya muy estudiado en las bacterias, los seres vivos superiores poseen un mecanismo más complicado y todavía no muy bien comprendido en el que intervienen proteínas ligadas a proteínas que estimulan la transcripción de ADN, en esencia el resultado conseguido es el mismo. A los genes que forman el sistema de regulación completo se les denomina en conjunto operón.

A su vez a otros genes con distintas funciones, como los genes de segregación cuya función es estructural y sirven como punto de apoyo para la construcción de los cromosomas y en la división celular. Y genes sin función aparente conocidos como ADN basura, que es codificado por la ARN-polimerasa en ARNm pero que es desechado por los ribosomas durante la fase de transcripción. El ADN se divide en dos tipos; exones, que es el ADN portador de información y que se codifica en ARNm e intrones, formado por secuencias de ADN no codificante que se intercalan entre los exones dentro de los genes. Actualmente no se conocen todavía todas las funciones de los intrones, presentes solo en las células diploides, excepto los gametos que son haploides. La mayor parte de estos están formados por repeticiones de nucleotidos o por zonas con gran facilidad para recombinarse o como los transposones para saltar de gen en gen o incluso de cromosoma en cromosoma, lo que puede inducir mutaciones.

Un descubrimiento aun no muy bien entendido, es que un mismo gen puede codificar distintas proteínas, el truco esta en que no todos los exones de un gen se codifican para forma una proteína, sino que lo hacen distintas combinaciones de estos, de tal forma que un gen puede llegar a codificar varias de proteínas.

La replicación de los genes

El ADN posee la capacidad de autorreplicarse, puede sacar copias de si mismo y, por lo tanto, de toda la información que porta. Como hemos visto el ADN se compone de dos copias de cada gen. La duplicación de una hebra de ADN da lugar a otra, pero no siempre son iguales, los genes se pueden mezclar entre ellos y cambiar de hebra, dando lugar a hebras con genes que sean mezcla de ambos progenitores.

No es necesario entrar en detalles de cómo se replica el ADN para obtener una copia exacta (ya veremos que no siempre es así) de los genes. Durante la copia se da un proceso conocido con el nombre de sobrecruzamiento. El sobrecruzamiento consiste en que dentro de una pareja de cromosomas los genes de ambos progenitores se mezclan para dar lugar a una cadena de ADN que contiene genes de ambos. Este cruce solo se da dentro de una pareja de cromosomas, y los cruces se hacen, según parece, al azar. El mecanismo es el siguiente, un grupo de genes es separado y ligado con otro grupo para formar una sola cadena de genes, como podréis imaginar a mayor proximidad física de los genes más fácil es que sean heredados juntos,. A los genes que son heredados juntos se dicen que están ligados. Los genes ligados solo se pueden dar en caso de que todos pertenezcan al mismo cromosoma. Hay que tener en cuenta, que dos genes no pueden estar ligados sin que también lo estén los genes que haya entre ellos.

De esta manera a partir de dos cadenas diferentes, sometiéndolas a sobrecruazamiento se obtienen una gran cantidad de cadenas distintas, tan solo combinando genes. Este número es verdaderamente grande, si pensamos que para cada gen hay 2 posibilidades, lo que quiere decir que para un gen habrá 2 combinaciones, para 2 genes habrá 4 (2*2) combinaciones, para 3 genes habrá 8 (2*2*2) combinaciones, para 4 genes habrá 16 (2*2*2*2) combinaciones. Es decir para un numero n de genes habrá 2n combinaciones distintas.

Pero si no hay ninguna variación en los genes. ¿De dónde salen los nuevos alelos?

Mutaciones:

Los genes son simples estructura químicas, que actúan como un mapa para montar aminoácidos. Supongamos que un codón cambia una base por otra, CTT por CTA, en ambos casos sintetiza el aminoácido Leucina. Pero si en lugar de cambiar la tercera base cambia la primera TTT tenemos Fenilanina. Un pequeño cambio puede alterar la estructura de la proteína a sintetizar.

¿Pero como puede darse este cambio de una base por otra?. Las razones pueden ser varias, desde errores en el mecanismo de replicación del ADN hasta causas externas, como la radiación, que alteren las bases. La mayor parte de estas alteraciones, conocidas como mutaciones, no serán viables pero las pocas que si lo sean permitirán crear un individuo con un nuevo alelo para el gen.

Como la mayoría de las mutaciones son nocivas hay mecanismos para reducirlas. Mientras el ADN se replica hay enzimas que realizan una comprobación de que la copia es correcta y en caso de detectar un error lo corrigen. Su eficacia, aunque alta, no es del cien por cien. Como podemos ver el equilibrio es difícil, si se producen muchas mutaciones aparecerán nuevos alelos, pero si se producen demasiadas alguna será letal y las demás mutaciones se perderán ya que el individuo no prosperara.

Evolución

Cuando una mutación resulta en un individuo válido está mutación puede resultar beneficiosa, perjudicial o neutral.

Los seres vivos desarrollan su actividad dentro de un ecosistema, su interacción con este es lo que decide si una mutación le da o no una ventaja al individuo, vamos a ver un ejemplo. La anemia falciforme es una enfermedad de origen genético, causada por el cambio de una única base en un gen. Si ambos genes tienen esa mutación los glóbulos rojos adopten forma de media luna. Estos globulos rojos son menos flexibles y tienen una vida útil menor que los normales lo que causa anemia. En un principio parece ser una mutación que da al individuo una clara desventaja, excepto en algunos lugares de África donde además de la anemia hay otra amenaza mayor el paludismo. La gente con anemia es mucho mas resistente al paludismo, por lo que en muchos pueblos afectados por el paludismo se encuentra gran cantidad de gente que sufre de anemia falciforme y donde una mutación que parecia una desventaja se ha convertido en ventajosa.

Podemos ver que los individuos pueden poseer ventajas que les permita vivir más tiempo o mantenerse en mejor estado, esto les facilita tener más descendencia, esta descendencia será portadora de sus genes y por lo tanto podrá poseer también esa ventaja, lo que a su vez les permitirá vivir más y tener más hijo. Esto hará que ese alelo se extienda por toda la especie. Esto es una pequeña parte de la teoría de la evolución de Darwin-Wallace. Todo esto se podría resumir con la expresión: “La supervivencia del más apto”.

La nueva mutación puede ser dominante o recesiva, dando lugar a distintos casos. Primero supongamos que es dominante y produce una desventaja, todos los individuos con esa mutación lo tendrán más difícil para tener descendencia y es probable que ese alelo desaparezca. En el segundo caso vamos a suponer que es dominante y produce una ventaja, ese alelo se extenderá a gran velocidad. Para el tercer caso vamos a suponer la mutación recesiva y ventajosa, tardara más en extenderse, pero los otros alelos dominantes al representar una desventaja iran desapareciendo. El ultimo caso es el más interesante, la mutación es recesiva y desventajosa, parece que tiene todas las de perder, pero no es así, al “quedar oculta” por otro alelo dominante y ventajoso esta mutación puede permanecer “escondida”. Solo reaparecerá en casos en que se encuentren dos alelos iguales.

Ahora bien, el medio puede cambiar y convertir a individuos aptos en individuos poco aptos, en ese momento los alelos más ventajosos se pueden convertir en una carga para su portador y los alelos desventajosos convertirse en una ventaja. En esas circunstancias los alelos recesivos “escondidos”, pueden volver a aparecer, solo que convertidos en ventaja y extenderse rápidamente. Un caso así lo tenemos en Londres, al principio de la época industrial, en las afueras había un grupo de polillas que podían ser de dos colores, blanco o negro, en un principio las polillas blancas tenían ventaja pues vivían en un bosque de abedules blancos y lo tenían fácil para confundirse con sus troncos y evitar a los depredadores y su color era el mas abundante, pero con la llegada de las fabricas y sus hornos de carbón los arboles se tiñeron de negro y la población cambio, rápidamente el número de polillas negras supero al de blancas. Vemos el medio afecta al rumbo de la evolución.

Podemos pues decir que la evolución no tiene un rumbo marcado, simplemente se adapta al medio, por lo que los términos superior inferior carecen de sentido, y habría que cambiarlos por mejor o peor adaptado. Esta adaptación provoca un curioso efecto, si dos poblaciones idénticas son separadas y colocadas en entornos distintos cada uno evolucionara por caminos diferentes, es lo que se conoce como deriva genética.

Para que una especie pueda adaptarse ha de tener variedad, sus individuos han de presentar múltiples características distintas, cuantas más, mejor, eso permite que se puedan presentar gran cantidad de soluciones adaptativas a un cambio en el entorno. Para una especie con poca variación genética cualquier cambio brusco del medio puede suponer su extinción. Si en el caso de antes de las polillas todas hubieran sido blancas seguramente habrían desaparecido.

Actualmente aun se duda de si la evolución produce avances significativos de golpe, “saltos evolutivos”, o si realiza su trabajo lentamente. Lamentablemente el registro fósil parece apoyar ambas teorías. Aunque cada vez cobran mas fuerza las teorías sobre sistemas caóticos en equilibrio que van acumulando pequeñas mutaciones hasta que este cumulo de mutaciones produce un gran cambio.

Es interesante mencionar una teoría anterior a la actual teoría de la evolución, la teoría Lamarckiana, según la cual a lo largo de la vida un animal desarrolla alguna característica concreta debido a su uso, esta característica pasa a sus descendientes que también la desarrollan y a su vez les da mayor ventaja frente a los otros individuos. Parece fuera de lugar describir esta teoría aquí, puesto que ha sido demostrada errónea y no se corresponde con todo lo explicado hasta ahora del ADN, pero hay algoritmos que sacan partido de ella sometiendo a los individuos a un proceso “de mejora” entre generaciones.

Modelo biológico de lo algoritmos genéticos

Los algoritmos genéticos se pueden implementar de gran variedad de formas, pero generalmente se sigue un mismo modelo que simplifica mucho la implementación, aquí se va a intentar caracterizar a ese modelo con las distintas estrategias de los seres vivos.

Se suele usar una sola cadena, por los que se podría decir que es haploide, a su vez los individuos son asexuados ya que todos se pueden cruzar entre si. La selección se basa en el fenotipo que se obtiene a partir del genotipo, por lo que se acerca al modelo de Darwin-Wallace. El tamaño de la población es fijo y estable, los individuos menos aptos son sustituidos por otros más aptos, por lo que existe competencia. Los individuos están sometidos a mutaciones aleatorias.

Teniendo en cuenta estas características quizás el modelo biológico al que mas se parecen los algoritmos genéticos sea el de una cepa de bacterias, ya que poseen una única hebra de ADN, poseen una alta tasa de mutación y de adaptabilidad, son capaces de intercambiar fragmentos de ADN. Dentro de la cepa las más aptas se extienden rápidamente y van sustituyendo a las menos aptas.

Otras vías de herencia

Hasta aquí es lo que se suele contar como base para los algoritmos genéticos y evolutivos, pero no hay que olvidar otras formas de herencia que también pueden tener su utilidad.

La primera serian las mitocondrias, pequeños orgánulos que actúan como centrales energéticas de las células y están dotadas a su vez de ADN, conocido como ADNm, estos orgánulos se heredan de la madre en la mayoría de las especies, lo que parece contradecir todo lo dicho hasta ahora, pero así es, una parte de nuestra herencia proviene únicamente de la madre, luego sus ventajas o desventajas provienen únicamente de un progenitor sin posibilidad que el otro intervenga. De hecho la evolución del ADNm se puede estudiar separada de la del ADN del resto de la célula.

El segundo caso lo representan las bacterias, que actúan como redes de intercambio de genes, los genes son capaces de separarse y recombinarse con los de otras bacterias. Se ha estudiado este fenómeno desde el punto de vista de la vida artificial usando autómatas celulares.

La tercera vía son los virus, a grandes rasgo, algunos son capaces de insertar en el ADN de la célula fragmentos del suyo para reproducirse, lo que a su vez puede producir el proceso contrario y que parte del ADN de la célula huesped pase a los nuevos virus. Actualmente se usan como vectores para terapia genética.

La cuarta vía son las proteínas, capaces de transformar otras proteínas en copias de si mismas, que a su vez transformaran a otras en lo que se denomina una reacción autocatalizada. Este tipo de proteínas se denominan priones y son la causa de enfermedades como la de las “vacas locas”.

Una quinta sería la clonación o replicación exacta del individuo, es muy usada entre los insectos ya sea para formar colonias o como alternativa a la reproducción sexual en forma de partenogénesis cuando hay escasez de machos. En esta forma la única fuente de variación genética son las mutaciones.

Por ultimo repetir que lo aquí visto no es mas que una introducción y que los métodos de codificación del ADN aun no han sido del todo desentrañados, pero ya se han empezado a encontrar sistemas bastante complejos como cadenas que ADN que codifican en ambos sentidos, cadenas de ARNm que son “asaltadas” y modificadas antes de llegar a los ribosomas, genes que se solapan, microARN (mARN) e interruptores ribosomaticos. No esta de más recordar que la complejidad de una solo célula supera en muchos niveles a la complejidad de cualquier construcción creada por el hombre. Pero toda esta complejidad no hay que verla como un obstáculo ya que cada nuevo proceso o parte que se desentraña, no hace otra cosa que dar más material sobre el que trabajar, más ideas y opciones.

Optimizar la comparación de distancias entre varios puntos

La función distancia se usa muy a menudo en muchos algoritmos para calcular la distancia entre puntos en el espacio. Hay algoritmos que hacen un uso intensivo de esta función como k-nn, k-means, o casi cualquier método que incluya buscar puntos cercanos. Por lo que reducir el coste de calcularla reporta una mayoría considerable de rendimiento.

Distintas distancias

Por suerte podemos usar funciones distancia diferentes. Una función distancia tiene que cumplir las siguientes condiciones cuando
x != y:

dist(x,x) = 0
dist(x,y) != 0
dist(x,y) = dist(y,x)
dist(x,y) <= dist(x,z) + dist(z,y)

Para calcular la distancia entre dos puntos es habitual usar la distancia euclídea:

dist(A,B) = √∑(Ai-Bi)²

Podemos hacer una primera mejora, si solo necesitamos comparar distancias podemos ahorrarnos la raíz cuadrada. Obtenemos una función distancia perfectamente válida y que puede reemplazar la euclídea

Pero hay una mejora más eliminar los cuadrados de las restas. Sin embargo hay un detalle a tener en cuenta, el cuadro de un número negativo es positivo, por lo que no basta con eliminarlos hay que reemplazarlos por el valor absoluto.

Esta parece un mejora menor pero en caso de espacios de muchas dimensiones puede llegar a notarse.

Pero no somos los primeros en llegar a esta conclusión, es conocida como distancia Manhattan:

dist(A,B) = ∑|Ai-Bi|

Realmente podemos reemplazar la distancia euclídea por cualquier distancia (tiene que cumplir los cuatro puntos anteriores) siempre que la nueva distancia cumpla que si en la distancia euclídea la distancia entre dos puntos cualesquiera A y B es mayor (o menor) que entre dos puntos cualesquiera C y D, en la nueva distancia también ha de ser mayor (o menor) en la nueva distancia.

Desigualdad triangular

Viendo la cuarta propiedad de las funciones distancia, conocida como desigualdad triangular, podemos usarla para acelerar la comparación entre distancias.

Teniendo tres puntos A,B,C sabemos que:

dist(A,B) + dist(B,C) >= dist(A,C)

|dist(A,B) – dist(B,C) | <= dist(A,C)

Es decir la suma de dos lados de un triángulo es mayor o igual que el tercer lado y el valor absoluto de la resta de dos lados es menor o igual que el tercer lado.

En la imagen de debajo de este texto se puede ver ejemplos visuales:

Operaciones entre distancias

Esto nos sirve para acotar distancias sin calcularlas. Calculando solo dos distancias podemos acotar el valor mínimo y máximo de la tercera lo cual nos puede permitir descartarla sin calcularla.

Por ejemplo, nos dan un punto C y tenemos que averiguar qué otro punto está más cerca A o B. A y B ya los conocíamos así que tenemos precalculada dist(A,B). Calculamos dist(B,C), si dist(B,C) < |dist(A,B) – dist(B,C)| entonces podemos decir que dist(A,C) > dist(B,C) ¡Sin calcularla!

En muchas situaciones tenemos puntos que son previamente conocidos/aprendidos. Por lo que podemos tener una tabla de distancias entre puntos precalculadas y usarlas para acotar distancias sin necesidad de calcular la distancia entre todos los puntos.

El problema es que una tabla de distancias entre puntos puede ocupar demasiado espacio en memoria. Veamos una alternativa, calcular la distancia de todos los puntos al mismo punto. Si no hay muy buenas razones para usar otro punto usaremos el origen de coordenadas (el punto cuyas coordenadas son todas ceros). Es muy poco costoso calcular la distancia de origen a un punto P

dist(O, P) =  √∑Pi² (euclídea)

dist(O, P) =  ∑Pi (Manhattan)

Ahora si tenemos precalculadas las distancias de los puntos a comparar con el origen y nos dan un nuevo punto P. Calculamos dist(O, P) y tenemos precalculado dist(O,A) y queremos saber dist(A, P).

Sabemos que:

dist(O, A) + dist(O, P) >= dist(A, P) >= |dist(O, A) – dist(O, P)|

Max dist(A, P) = dist(O, A) + dist(O, P) 

Min dist(A, P) = |dist(O, A) – dist(O, P)|

Ya tenemos una cota mínima y máxima de cual es la distancia de de A a P. Realmente por si misma no nos sirve de nada pero si hay que comparar con muchos puntos es suficiente pare descartar muchos de ellos.