Tienen varias finalidades, pero las que más podemos destacar son la posibilidad de aprendizaje y la búsqueda de la mejor solución a un problema. En principio la teoría podría parecer algo difícil de entender: ¿Cómo es que aprende? ¿Cómo encuentra la forma? Si bien estos algoritmos son de mucha ayuda y dan un toque más de realismo a los juegos, el “cómo aprende” depende más de lo que se haga fuera que dentro. Si entienden la lógica, pueden modificarlos como quieran y readaptarlos para la finalidad que necesiten.

• DEFINICIÓN
• IMPLEMENTACIÓN
• ¡A CODEAR!
• SELECCIONANDO A LOS PADRES: SelectionProcess()
• APAREANDO A LOS PADRES: CrossOver()
• MUTACIÓN
• EJEMPLO DE USO

La gran pregunta: ¿Qué son? Bueno… Son algoritmos que pueden encontrar la solución a un problema específico, simulando la evolución genética. Sin entrar en mucho tecnicismo, vamos a usar esa definición.

En muchos casos puede que incluso sepamos cuál es exactamente la solución. Por ejemplo: tenemos la posición de un enemigo, ¿Para qué necesito gastar recursos en un algoritmo que aprenda cómo llegar hasta un enemigo? No siempre queremos que nuestra inteligencia artificial sepa dónde está nuestro personaje, ya que eso haría muy fácil todo el asunto, y si tiene tan buen ojo, tan buen oído, tan buena puntería, perderíamos esa particularidad que hace que se parezca a otra personaje jugando.

Básicamente son algoritmos que hacen evolucionar a una población haciendo que estos pasen por determinadas acciones (funciones). Estas acciones modifican sus cromosomas para obtener valores diferentes. Luego cada individuo usará los valores de esos cromosomas para hacer alguna tarea para la cual queramos entrenarlos. Se le deberá dar puntos por cada acción realizada correctamente y/o restar por haberla hecho mal (opcional). Luego el algoritmo se quedará con los habitantes más aptos, y creará una nueva población, en base esos padres. Este proceso se repetirá hasta obtener los valores deseados o a hasta que el algoritmo llegue a su máxima convergencia o punto límite (punto en el cual ya no puede evolucionar más).

Hay muchas formas de implementar un algoritmo genético. Voy a tratar de mostrar una corta y sencilla, para luego hacerle algunos ajustes, pero voy a tratar de dejarla lo más general posible, ya que lo que importa es el concepto más que una implementación en particular. Cada algoritmo genético debería implementarse de una manera distinta dependiendo de cuál sea el objetivo… Empecemos!

En esa imagen podemos ver a grandes rasgos los procesos que ocurren en un algoritmo genético. Vamos a explicarlos de a uno:

Bueno… Empecemos con la parte divertida: El código. Para empezar vamos a necesitar 3 scripts, los cuales voy a crear sólo las variables y funciones, sin nada adicional. Voy a crear un algoritmo genético básico.

Individual.cs

public class Individual
{
    //Valor que simboliza qué tan apto es este individuo.
    public float fitness;

    //Esto también podría ser una lista de cromosomas. Pero por el momento sólo necesitamos uno.
    //También se podría usar uno sólo con muchos genes.
    public Chromosome chromosome;
}

Chromosome.cs

using System.Collection.Generic;

public class Chromosome
{
    //Lista de valores. Cada uno representa una solución a un problema.
    //Generalmente se rellena con valores entre -1 y 1.
    public List genes;

    //No es "completamente" necesario, pero sirve para crear la lista
    //de valores inicial. Le pasamos por parámetro la cantidad de genes.
    //Deberíamos usar un gen para cada problema a resolver.
    //Por ejemplo, si lo querémos usar como dirección, necesitamos 3:
    //x, y, z.
    public void Create(int count, float min, float max)
    {
        genes = new List();
        for(int i=0; i<count; i++)
        {
            genes[i] = Random.Range(min, max);
        }
    }
}

GeneticAlgorithm.cs

using System.Collection.Generic;

//Este script sí podría heredar de MonoBehaviour, puesto que así podríamos arrastrarlo
//a un objeto y probarlo.
public class GeneticAlgorithm : MonoBehaviour
{
    //Cantidad de individuos en este algoritmo.
    public int individualCount;

    //Cantidad de genes que va a contener cada individuo.
    public int genesCount;

    //Lista de todos los individuos en este algoritmo.
    public List<Individual> allIndividuals;

    //Crea la población inicial.
    public void CreateInitialPopulation()
    {
        
    }

    //Devuelve una lista de los mejores padres. Para este ejemplo debería devolver 2 individuos,
    //pero puede devolver la cantidad que sea necesaria.
    public List SelectionProcess()
    {
        
    }

    //Inicia el proceso de cruce. En este caso recibe una madre y un padre, pero puede
    //recibir también una lista de padres (no necesariamente debe respetar el proceso natural).
    public void CrossOver(Individual mother, Individual father)
    {
        
    }

    //Como su nombre lo indica, se encarga de llamar a las dos funciones anteriores para crear
    //una nueva población. No es necesario eliminar directamente a la población actual, también se
    //puede sobreescribir los valores de sus genes.
    public void StartRepoblation()
    {
        List parents = SelectionProcess();
        CrossOver(parents[0], parents[1]);
    }
}

Esto es un algoritmo genético básico. No se definió, aún, el comportamiento de las dos funciones principales: SelectionProcess y CrossOver. Vamos de a poco, pero antes de empezar, tengan en cuenta que este tutorial está marcado como “avanzado“, así que voy a deducir que si están leyendo esto, tienen conocimientos medianamente avanzados acerca de programación. Si no es así, a esta altura les habrá agarrado una embolia cerebral.

Continuemos…

En la función “SelectionProcess()” podríamos utilizar un lambda para obtener a los dos mejores padres. Para este caso, tomemos que los dos mejores son siempre los que tengan mayor puntaje (fitness). Así que la función quedaría así:

public List SelectionProcess()
{
    return allIndividuals.OrderByDescending( currentIndividual => currentIndividual.fitness ).Take(2).ToList();
}

La función “OrderByDescending()” recibe un DELEGADO O LAMBDA que reciba por parámetro un individuo (porque la lista es de Individual), y devuelva un número. El número que devuelva se usará para ordenar la lista de menor a mayor. De esa lista tomamos 2 y devolvemos la lista formada por los dos individuos (padres). Y con esto ya tenemos a los padres que vamos a pasarle a la función “CrossOver“. Así que estamos listos para aparear a esos padres!

Existen múltiples criterios para seleccionar a los padres, y cada uno de ellos depende de nosotros. Uno muy común es hacer que los que más puntos de fitness tengan se encuentren con una probabilidad mayor de salir. Esto hace que puedan salir generaciones con padres no muy aptos, pero abre el campo evolutivo a más respuestas. Siempre deberíamos probar soluciones diferentes, para ver cuál obtiene reacciones más aceptables. Recuerden siempre que queremos emular un comportamiento, y no tener el comportamiento más perfecto posible, ya que si así lo quisiéramos directamente le diríamos lo que tiene que hacer.

Este es el proceso en el cual obtenemos una nueva población, sacada de los padres obtenidos anteriormente. Para este caso vamos a hacer de cuenta que sólo tenemos dos (padre y madre), pero también tengan en cuenta que pueden tener la cantidad de padres que quieran para esta etapa.

La función “CrossOver()” consta de 4 pasos lógicos, a saber:

1. Recorro todos los individuos.
2. Elijo un punto aleatorio entre los genes de los padres.
3. Recorro desde el primer gen hasta el punto de corte para los genes de la madre.
4. Recorro desde el punto de corte hasta el final para los genes del padre.

Esta es UNA de las miles de formas que hay de cruzarlos. Sean creativos y elijan la que más les convenga o quieran probar. Básicamente con el punto de corte aleatorio quedaría algo como esto:

Como dije, hay muchas, y ustedes pueden inventar la suya propia también.

A continuación, el código podría ser algo como esto (digo “podría” porque ustedes pueden inventarlo):

public void CrossOver(Individual mother, Individual father)
{
    //1) Recorro todos los individuos...
    for(int i=0; i<allIndividuals.Count; i++)
    {
        //Chequeamos que los individuos a modificar no sean ni el padre ni la madre...
        if(allIndividuals[i] != mother && allIndividuals[i] != father)
        {
            //2) Elijo un punto aleatorio de corte.
            var plotPoint = Random.Range(0, allIndividuals[i].chromosome.genes.Count);
            
            //3) Recorro desde el primer gen hasta el punto de corte para los genes de la madre.
            for(int indexMother=0; indexMother<plotPoint; indexMother++)
            {
                allIndividuals[i].chromosome.genes[indexMother] = mother.chromosome.genes[indexMother];
            }

            //4) Recorro desde el primer gen hasta el punto de corte para los genes de la madre.
            for(int indexFather=plotPoint; indexFather<allIndividuals[i].chromosome.genes.Count; indexFather++)
            {
                allIndividuals[i].chromosome.genes[indexFather] = mother.chromosome.genes[indexFather];
            }
        }
    }
}

Con esto cumplimos los 4 pasos que nombre arriba. A continuación, vamos con el siguiente proceso, que es…

La mutación consiste en agarrar genes de manera aleatoria o basada en algún criterio en particular, y cambiarle un valor por otro. Este valor puede ser también completamente aleatorio. La finalidad de esto es obtener más soluciones y evitar que las generaciones se estanquen. Si, por ejemplo, tomamos siempre a los mejores individuos como padre, puede pasar que en varias generaciones no aprendan nada, no ganen ningún punto, y el algoritmo seguiría creando a los mismos individuos una y otra vez, impidiendo que estos evolucionen. Así que con esto hacemos que al menos uno tome valores diferentes, lo cual nos provee soluciones diferentes.

Hay muchas maneras de mutar genes, algunas pueden consistir, por ejemplo, en elegir dos genes aleatorios e intercambiarlos:

Alternativamente también tenemos otro que consiste en sólo ponerle su valor opuesto. Por supuesto que “OPUESTO” se refiere a cada contexto según corresponda. Podríamos sólo multiplicar por -1 o simplemente cambiar un “1” por un “0”.

La que voy a mostrar a continuación es la más sencilla, que consiste en agarrar un individuo cualquiera, elegir al azar uno de sus genes y ponerle un valor aleatorio. Así que para esto, lo que vamos a hacer es agregarlo a lo que ya teníamos, o sea, luego de haber creados a la nueva generación. Quedaría de la siguiente manera:

public void CrossOver(Individual mother, Individual father)
{
    //1) Recorro todos los individuos...
    for(int i=0; i<allIndividuals.Count; i++)
    {
        //Chequeamos que los individuos a modificar no sean ni el padre ni la madre...
        if(allIndividuals[i] != mother && allIndividuals[i] != father)
        {
            //2) Elijo un punto aleatorio de corte.
            var plotPoint = Random.Range(0, allIndividuals[i].chromosome.genes.Count);
            
            //3) Recorro desde el primer gen hasta el punto de corte para los genes de la madre.
            for(int indexMother=0; indexMother<plotPoint; indexMother++)
            {
                allIndividuals[i].chromosome.genes[indexMother] = mother.chromosome.genes[indexMother];
            }

            //4) Recorro desde el primer gen hasta el punto de corte para los genes de la madre.
            for(int indexFather=plotPoint; indexFather<father.chromosome.genes.Count; indexFather++)
            {
                allIndividuals[i].chromosome.genes[indexFather] = mother.chromosome.genes[indexFather];
            }
        }
    }

    //Probabilidad de mutación.
    if(Random.Range(0f, 1f) < mutationProbability)
    {
        var individualIndex = Random.Range(0, allIndividuals.Count);
        var genIndex = Random.Range(0, allIndividuals[individualIndex].chromosome.genes.Count);
        allIndividuals[individualIndex].chromosome.genes[genIndex] = Random.Range(-1, 1); //Debería ser entre el mínimo y máximo de los genes.
    }
}

Y con esto tenemos un algoritmo genético básico. Así que quedaría probar su funcionamiento. Tengan en cuenta que dicho algoritmo deberá procesarse por su propia cuenta. Nuestro trabajo consiste en guardar a uno de sus individuos en un objeto que queramos que aprenda, por ejemplo, un pez, un personaje, un auto, etc. Lo que haría este “personaje” sería usar los genes del individuo para hacer algo, lo que sea. Por ejemplo, podríamos ponerle 3 genes a nuestro algoritmo y usarlos como un vector, o sea, un valor para X, otro para Y, uno para Z. Entonces nuestro personaje se movería usando ese vector. Lo que veríamos en un principio es que cada “personaje” se movería en direcciones completamente sin sentido. Pero… Cuando alguno de esos personajes logre ganar algún punto, al generar una nueva población de individuos, se tomarán a los que más puntos tengan. Esto quiere decir que en algún momento toda una generación tomará decisiones más acertadas, puesto que los individuos con más fitness representaran a los que mejores decisiones tomaron.

Imaginemos que tenemos unos peces que tienen que encontrar hacia dónde hay comida. Lo que haríamos en nuestro script “Fish.cs” sería decirle que cada vez que colisione con comida, le sume a su individuo (el que saca del algoritmo genético), un punto de fitness. Y cada vez que el ciclo vuelve a iniciar posicionamos al pez nuevamente en su posición de inicio.

En principio vamos a crear en algún script a todos los peces:

Main.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Main : MonoBehaviour {

    public GameObject prefabFish;
    public List<Fish> allFishes;

    public GeneticAlgorithm ga;
    public float timeToRepoblate;
    public bool accelerateTime;

    // Use this for initialization
    void Start () {
        ga = this.GetComponent<GeneticAlgorithm>();
        ga.CreateInitialPopulation();

        for (int i = 0; i < ga.individualCount; i++)
        {
            var fish = GameObject.Instantiate(prefabFish).GetComponent<Fish>();
            fish.individual = ga.allIndividuals[i];
            fish.SetStartPosition(); //Esta función la creamos en el pez para posicionarlo en Vector3.zero.
            allFishes.Add(fish);
        }

        StartCoroutine(Repoblate());
    }
    
    //Esta corutina hace que cada X tiempo se cree una nueva generación.
    IEnumerator Repoblate()
    {
        while(true)
        {
            yield return new WaitForSeconds(timeToRepoblate);

            ga.StartRepopulation();
            for (int i = 0; i < ga.individualCount; i++)
            {
                allFishes[i].SetStartPosition();
            }
        }
    }

    // Update is called once per frame
    void Update () {
        //Esto lo usamos si querémos acelerar el proceso de aprendizaje.
        Time.timeScale = accelerateTime ? 15 : 1;
    }
}

Ahora vamos al script de nuestro pez, cuya misión será sumar puntos a su individuo cada vez que agarre la comida. Lo que vamos a hacer es que sume puntos mientras esté tocando su alimento, así los peces que estuvieron más tiempo tocando la comida van a tener más puntos.

Fish.cs

using System.Linq;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Fish : MonoBehaviour
{
    public Vector3 targetDirection;
    public float speed;
    public Individual individual;

    //Pone al pez en la posición inicial.
    public void SetStartPosition()
    {
        this.transform.position = Vector3.zero;

        //Actualizamos los valores de la dirección, sacados de cada gen.
        targetDirection.x = individual.chromosome.genes[0];
        targetDirection.y = individual.chromosome.genes[1];
        targetDirection.z = individual.chromosome.genes[2];
    }

  //Se llama al pintar la pantalla...
  void Update ()
  {
        //this.transform.position += targetDirection * Time.deltaTime * speed;
        var rb = this.GetComponent<Rigidbody>();
        rb.velocity = targetDirection * speed;

        if(rb.velocity.normalized != Vector3.zero)
            this.transform.forward = rb.velocity.normalized;
    }
    
    //Vision...
    private void OnTriggerStay(Collider c)
    {
        if(c.transform.tag == "Food")
        {
            individual.fitness++;
        }
    }
}

Lo que vamos a ver si dejamos al algoritmo un tiempo trabajando es cómo los peces van “aprendiendo”. Básicamente el algoritmo se va quedando con los mejores padres, y los va llevando de una generación a la otra, creando una población que está siempre basada en los que obtuvieron mejores resultados.

A continuación vamos con algunos ejemplos que ya fueron desarrollados. Por ejemplo, para Mario Bros se hicieron algunas.

Ejemplos de usos en otro en vehículos:

Algunos ejemplos adicionales: