La cara del guerrero – Algoritmo Genético

Cuentan viejas historias, que hace muchos años, en la aldea de Heike, algún pescador recogió sus redes llenas de peces y cangrejos y, mientras separaba las especies, encontró un cangrejo que tenía la cara de un guerrero, grabada sobre su caparazón.

El pescador no podía llevarse a la olla a una imagen que le recordaba a un entrañable ancestro, por lo que decidió devolverla al mar.

Con el pasar de los años, eran muchos los pescadores que repitieron la misma historia una y otra vez, hasta que en la actualidad, los cangrejos de esta aldea, llevan todos sobre sus caparazones, el imborrable recuerdo de un guerrero.

El fallecido Carl Sagan, con su incomparable capacidad para divulgar, nos comenta lo que debió haber pasado con estos cangrejos:

Motivado por esta impresionante historia, he decidido echar un vistazo a la teoría de algoritmos genéticos para plasmar este modelo en mi computadora. Recurriendo a viejos apuntes, la Wikipedia y la interesantísima página de Mat Buckland: ai-junkie, he elaborado el programa que sirve de base para el presente artículo.

Algoritmo genético

Está clasificado dentro de los algoritmos evolutivos, pues se basa en la manera como los genes van pasando de generación en generación, incorporando cambios muy ligeros hasta alcanzar un determinado estado, que bien puede ser considerado como una solución.

Un algoritmo de este tipo no sirve para demostrar las teorías genéticas o evolutivas, como tampoco serviría un “algoritmo de población espacial por infección interplanetaria” para demostrar que somos el resultado de una infección de otro mundo. Sin embargo, los algoritmos genéticos se han destacado por dar soluciones inesperadas donde otros algoritmos han resultado ineficientes. Por ejemplo, se han patentado antenas que fueron diseñadas por medio de este algoritmo.

El corazón del algoritmo: épocas o ciclos

El algoritmo genético funciona en base al tiempo. Cada unidad de tiempo es representada por una época o ciclo. La gran ventaja es que este ciclo puede representar lapsos inmensos de tiempo y ejecutarse en una fracción de segundo.

Cada ciclo tiene la siguiente estructura:

    Public Sub Cycle()
        UpdateFitScores()
        Dim numBabies As Integer = 0
        Dim babyGenomes As New ArrayList
        While numBabies < mPopSize
            Dim mum As CGenome = SelectOne()
            Dim dad As CGenome = SelectOne()
            Dim baby1 As New CGenome(mCromoSize)
            Dim baby2 As New CGenome(mCromoSize)
            CrossOver(mum, dad, baby1, baby2)
            baby1 = Mutate(baby1)
            baby2 = Mutate(baby2)
            babyGenomes.Add(baby1)
            babyGenomes.Add(baby2)
            numBabies = numBabies + 2
        End While
        mGenomes = babyGenomes
        mGeneration = mGeneration + 1
    End Sub

Dentro de esta estructura podemos ver todos los elementos importantes de un algoritmo genético y entender su funcionamiento.

Básicamente, se trata de obtener una descendencia y seleccionar aquello que obtenga una mejor calificación.

Primero, se actualizan las calificaciones de cada individuo de la población actual por medio de la función UpdateFitScores. Los criterios de calificación corren por parte de quien desarrolla la aplicación y más abajo daremos un ejemplo.

Lo siguiente es seleccionar un padre y una madre (dad y mum), por medio de la función SelectOne. Esta función debe estar lo suficientemente elaborada como para seleccionar de entre “lo mejorcito” (tomando como referencia la calificación realizada), pero evitando seleccionar siempre los mismos padres. Para esto es necesario introducir algún patrón aleatorio, pues si seleccionamos siempre a los mismos padres, no habrá casi variación en los hijos y la evolución se detendrá.

En esta implementación, he experimentado con una nueva idea: la del “macho dominante”, que consiste en utilizar un solo padre en cada época. La obtención de una solución satisfactoria, ha sido mucho más rápida.

Sin importar como obtengamos los padres, vamos a obtener dos hijos, cuyas características saldrán del cruce entre los padres tras llamar al método CrossOver(mum, dad, baby1, baby2).

A continuación hacemos que los hijos sufran pequeñas mutaciones con la función Mutate(baby1).

Finalmente todos los hijos así obtenidos, reemplazan a la población anterior, dando por terminada la época o ciclo.

Patrón de referencia

En este caso, queremos que la espalda de nuestros cangrejos, tenga la cara de un guerrero samurai. Vean mi versión de este (sin burlarse, por favor):

Para el diseño de esta cara, he utilizado una matriz numérica de 15×15. Los colores han sido codificados de acuerdo a la siguiente tabla:

0	Blanco
1	Amarillo
2	Naranja
3	Negro

De tal manera que la matriz es la siguiente:

    Dim crab(,) As Integer = _
        {{3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3}, _
         {3, 0, 0, 3, 1, 1, 1, 1, 1, 1, 1, 3, 0, 0, 3}, _
         {3, 0, 3, 3, 3, 1, 1, 1, 1, 1, 3, 3, 3, 0, 3}, _
         {3, 0, 3, 3, 3, 2, 1, 1, 1, 1, 3, 3, 3, 0, 3}, _
         {1, 0, 0, 3, 0, 3, 1, 1, 1, 3, 0, 3, 0, 0, 2}, _
         {1, 3, 0, 0, 0, 0, 3, 1, 3, 0, 0, 0, 0, 3, 2}, _
         {1, 1, 3, 0, 0, 3, 2, 2, 1, 3, 0, 0, 3, 2, 2}, _
         {1, 1, 1, 3, 3, 2, 1, 1, 1, 1, 3, 3, 2, 1, 1}, _
         {1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1}, _
         {1, 1, 1, 3, 2, 1, 1, 1, 2, 2, 2, 3, 2, 1, 1}, _
         {1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1}, _
         {1, 1, 1, 3, 1, 2, 3, 2, 3, 2, 1, 3, 1, 1, 1}, _
         {1, 1, 3, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 1}, _
         {1, 1, 3, 3, 2, 3, 2, 1, 1, 3, 2, 3, 3, 2, 1}, _
         {1, 1, 1, 2, 3, 3, 2, 1, 1, 3, 3, 2, 2, 2, 1}}

Esa matriz debe ser tomada como referencia. En nuestro problema, la referencia nos indica “este cangrejo no debe ser comido, porque tiene (o se parece) esta cara, la cara de un guerrero”.

Representación genética

Cada individuo está representado por una cadena de bits, los suficientes como para contener una solución al problema planteado. En este caso, como cada individuo debe contener un patrón de 15×15, con cuatro colores posibles (00, 01, 10, 11 = 2 bits por color), la cadena debe contener 15×15x2 = 450 elementos.

Estos 450 elementos, contienen toda la información necesaria como para reproducir la cara del guerrero que estamos buscando.

Public MAP_HT As Integer = 15
Public MAP_WD As Integer = 15
Private mPattern(MAP_HT - 1, MAP_WD - 1) As Integer

Calificación de cada individuo

Uno de los puntos clave de este algoritmo, es una correcta calificación. En cada problema, debemos garantizar que los mejores individuos van a ser calificados con los mejores puntajes. Si es un problema de rutas, el mejor puntaje podría otorgarse a la ruta más corta; si es un problema de finanzas, al mayor capital obtenido; si es un problema de patrones –como lo es en este caso-, al patrón más parecido y así sucesivamente.

En todo caso y problema, los individuos que sobreviven son los que tienen más oportunidad de dejar descendencia. Por eso es que debemos calificar con mejor puntaje a los que son más parecidos al patrón dado o al objetivo del problema.

Al comparar dos patrones, lo haremos píxel por píxel. Como los valores de nuestros píxeles van del 0 al 3, la mayor diferencia por cada píxel será precisamente esa: 3 puntos (3 – 0 = 3). Si todos los elementos de nuestra matriz obtuvieran la mayor diferencia posible, y como se trata de una matriz de 15×15, tendremos que el peor de los puntajes es 15×15x3, lo que nos da un total de 675 puntos en contra. Este puntaje “malo”, es de referencia y se mantendrá como valor constante. Lo llamaremos “el peor de los puntajes” (PP). Nótese que aún no hemos evaluado el patrón de cada individuo.

Ahora si, el patrón de cada individuo es analizado píxel por píxel. Nunca va a obtener más de 675 puntos en contra y a los puntos obtenidos les llamaremos dT (Diferencia Total). Conocido “el peor de los puntajes” (PP=675), podemos aplicar la siguiente fórmula para calificar a cada individuo:

1 – dT / PP

La fórmula nos garantiza un valor real entre 0 y 1, muy útil para cálculos estadísticos.

La siguiente función realiza el cálculo descrito anteriormente:

    Public Function TestPattern(ByVal Pattern(,) As Integer) As Double
        Dim dT As Double = 0
        For i = 0 To MAP_HT - 1
            For j = 0 To MAP_WD - 1
                dT = dT + Abs(Pattern(i, j) - mPattern(i, j))
            Next
        Next
        TestPattern = 1 - dT / PP
    End Function

Esa función luego es invocada al momento de actualizar los puntos de toda la población:

    Public Sub UpdateFitScores()
        For i = 0 To mPopSize - 1
            Dim genome As CGenome
            genome = mGenomes(i)
            genome.Fitness = mPattern.TestPattern(Decode(genome.Bits))
        Next
    End Sub

Esa misma función puede ser utilizada para hallar al mejor individuo, al peor, obtener un promedio, un conteo, una suma de los elementos… en fin, lo que necesitemos de acuerdo al problema.

Cruce de individuos

Como hemos visto, los individuos se cruzan y tienen hijitos. En este caso, 2 hijos cada vez. Y eso depende del método de cruce que se decida utilizar. En este caso yo he utilizado la técnica de división en un punto. Esto significa que se elige un punto al azar dentro de la cadena de bits y a partir de este se parten en dos los genes del padre y la madre. Las mitades resultantes se combinan y listo: tenemos dos hijos:

dad = D1 + D2
mum = M1 + M2
baby1 = D1 + M2
baby2 = D2 + M1

El cruce de individuos puede realizarse de muchas otras maneras, incluso las que uno mismo intuya. Sin embargo hay que tener cuidado. Uno podría estar tentado a sacar un promedio de los valores de padre y madre, sin darse cuenta que de esta manera van desapareciendo valores extremos que a veces necesitan ser parte de la solución.

¡Mutación!

En contra de lo que algunos piensan, la mutación es muy poco frecuente. La mayoría de las veces es perjudicial, provocando la incompetencia de un organismo; pero el resto de las veces, es un poco más de lo que se necesita para que haya variedad y pueda darse el paso hacia una solución.

Para implementar la mutación, debemos recorrer la cadena de bits de cada individuo y, bajo una probabilidad muy baja (del orden del 0.001), proceder a cambiar el bit correspondiente.

Ejecución del ejemplo

Por medio de la interfaz mostrada, he conseguido los datos que se resumen a continuación. La imagen mostrada en cada ciclo corresponde al mejor individuo con respecto al patrón objetivo.

Objetivo

Calificación = 1.0000

Época	1	5	10	30
Mejor imagen obtenida
Calif. Máx.	0.5851	0.6311	0.6829	0.7614
Calif. Min.	0.5504	0.5644	0.6103	0.7111

Época	50	100	150	200
Mejor imagen obtenida
Calif. Máx.	0.8266	0.8874	0.8992	0.9096
Calif. Min.	0.7559	0.8200	0.8429	0.8373

Puede apreciarse tras 200 generaciones, y esto ocurre casi siempre, que los resultados de este algoritmo no son óptimos al 100%. Sin embargo, dada la complejidad de los problemas que se pueden resolver, suele ser imposible o demasiado costoso encontrar mejores soluciones por otros métodos.

Comentarios finales

Con “La cara del guerrero”, vemos que recién a partir de un 85% de similitud (aproximadamente), se puede decir que se ha formado una cara reconocible y para el momento en que este rango de similitud se presenta dentro de la población, el mínimo ha superado el 80%.

El haber utilizado un “macho dominante”, tan sólo ha acortado los ciclos, no ha influido apreciablemente en la brecha entre las calificaciones máximas y mínimas, la cual si se ve afectada por el tamaño de la población.

Entonces, ¿es verdadera la historia de los cangrejos Heike?

Es bastante probable. Otra posible solución sería que antes de la selección que llevaron a cabo los pescadores, hubiese existido otro proceso (de seguro natural) que diera como resultado una población con 80 – 90% de similitud y, a partir de entonces, empezaran a actuar los humanos.

¿Cuál pudo haber sido ese proceso previo?

Posiblemente los cangrejos hubieron desarrollado patrones parecidos a ojos por haber tenido más oportunidad de sobrevivir al ataque de sus depredadores, -en la naturaleza hay varios ejemplos de otras criaturas que se sirven de este mecanismo de defensa-. Consideremos incluso que éste pudiera haber sido el único proceso y que los pescadores jamás actuaron como moldeadores de las generaciones actuales de cangrejos Heike.

Como curiosidad final les diré que el presente ejemplo, con algunas modificaciones, podría servir como una de las muchas maneras en que una cara humana puede ser reconocida por medio de un algoritmo de computadora.