Razón Artificial

La ciencia y el arte de crear videojuegos

Algoritmos genéticos

Escrito por carlos el 23 de septiembre de 2010 en Inteligencia Artificial | 6 Comentarios.

Bueno, hoy vamos a hablar sobre los algoritmos genéticos (a partir de ahora AG). La idea básica de los AG es la de resolver los problemas de la misma manera que lo hace la naturaleza. Para ver esto mejor voy a usar una pequeña historia:

“Hace mucho tiempo, había una pequeña colonia de búhos que estaban desde siempre estaban en una pequeña cueva donde no entraba ni un rayo de sol, y por tanto no tenían la necesidad de unos ojos. El agua la obtenían de un pequeño lago que había en el medio, y la comida del musgo que crecía al rededor. Todo era perfecto para ellos, ya que ahí dentro no tenían ningún depredador que les pudiera atacar. Pero un día hubo un pequeño terremoto, y una de las paredes se desprendió, dando lugar a una abertura por donde entraba el sol, y por primera vez sintieron el calor de sus rayos. Unos pocos aventureros salieron en busca de más comida, pero no solo encontraron eso, sino también unas águilas que se llevaron a algunos. En la siguiente generación de búhos unos pocos nacieron con una mutación en sus genes, que les hizo tener una pequeña membrana sensitiva a la luz, que les ayudó a saber si fuera había depredadores, pero todavía estaba muy poco desarrollada. Esta ventaja sobre el resto significó que no murieron en el exterior, eran más fuertes, y por tanto los búhos hembra les preferían para hacer hijitos, por lo que esta membrana se siguió desarrollando en siguientes generaciones, dando lugar a unos ojos muy útiles.”

Esto, más allá de ser una simple historia ha introducido muchos de los términos que vamos a utilizar. Estos son:

  • Cromosoma: es un conjunto de genes. Para nosotros una persona tendra un solo gen.
  • Gen: Es donde se codifica la información sobre esa persona. En esta historia los genes de los búhos pueden ser, el color de las alas, el número de alas, …
  • Aptitud: Esto es la cercanía a la resolución del problema. En el caso de los búhos el problema era encontrar una manera de detectar a las águilas. Cuanto mayor sea la aptitud mayor sera la probabilidad de que hagan bebes que pasen a la siguiente generación.
  • Creación de la nueva generación: Este es el proceso más complejo que hay en todo el AG. Se divide en varias partes:
  1. La ruleta “de la suerte”: Aquí se deciden los padres, que tienen más posibilidad de ser elegidos si su aptitud es mayor, dado que son “mejores”.
  2. El cruce: En este paso se eligen el número de genes de cada padre que llevaran los hijos, que depende de la tasa de cruce, un número con el que se eligen las partes que se tomarán.
  3. Mutación: Existe una pequeña posibilidad de que un gen cambie por completo. En el caso de los búhos si el gen del número de alas mutara, el búho podría tener 3 alas, o ninguna. Esto depende de la tasa de mutación.

Todo esto esta muy bien, os diréis, pero, ¿por que me merece la pena usar esto en vez de una, por ejemplo, FSM?. Para responder a esto voy a usar un ejemplo de un juego para el que necesitamos un sistema de IA:

Imagina que tenemos un juego al estilo WoW. Tiene un sistema de lucha de personajes complejo, incluyendo clases, razas, profesiones que mas tarde aprenda, armas que pueda utilizar, armaduras muy diferentes, … , a demás de la posibilidad de que se ataque en grupo o en separado. La FSM que tratara todo esto sería grandísima, y si quisiéramos añadir algo nuevo habría que reescribirla, algo horroroso y que, al menos a mi, me haría mandarlo todo a la mi… . Pero esto es evitable si tenemos un AG sencillo que se adapte y amolde al jugador sin supervisión alguna. Creo que queda claro su ventaja, ¿no? :-) .

También esto tiene partes difíciles, pero para el nivel al que nos vamos a centrar solo hay una, el decidir como asignamos la aptitud, pero ya esta, el resto va como la seda. Os animo a que probéis, mientras publico las siguientes partes, a practicar con alguna cosilla. No hace falta que sea programando, sino simplemente tomar un problema cualquiera y pensar como representarlo, la manera de asignar la aptitud a ese problema en concreto, como codificar los genes, … .

Para esta guia introductoria vamos a usar un problema más sencillo que el de arriba. Si habéis leído mi anterior artículo probablemente ya sabréis qué sera… ¿lo tenéis?, bueno, si no sabéis a lo que me refiero lo que vamos a implementar es un AG para encontrar un camino, como haríamos con el A*, pero sin pedir que el camino sea el más corto posible.

Bueno, de momento esto es lo que tenéis que saber sobre los algoritmos genéticos, solo queda comenzar la escritura del código, algo que haremos en el siguiente capítulo. Así que, ¡hasta la próxima!.

6 Comentarios en "Algoritmos genéticos"

  1. asdf dice:

    Interesante articulo, expectante por ver el siguiente

    Espero que esta saga de artículos no caiga en el mismo saco que el desarrollo del engine y cierto concurso de ia

  2. […] This post was mentioned on Twitter by Razon Artificial, pablo ar. pablo ar said: Algoritmos genéticos: Bueno, hoy vamos a hablar sobre los algoritmos genéticos (a partir de ahora AG). La idea bás… http://bit.ly/bNLklR […]

  3. adrigm dice:

    Los algoritmos genéticos los está llevando carlos y no yo. Así que no tiene nada que ver.

    Respecto al engine y al concurso no han caído en saco roto, el desarrollo del juego del concurso está casi terminado y respecto al engine pronto habrá novedades de la restructuración que se iba a llevar a cabo. Los que escribimos tenemos también otras obligaciones, espero que lo entiendan.

  4. Carlos dice:

    Me alegro de que te guste, estoy terminando el código y para la semana que viene probablemente ya estén los artículos escritos. Adri tiene razón, nosotros también somos personas (o eso dicen), y tenemos nuestras obligaciones, así que puede que haya cosas que se retrasen, pero nunca se abandonaran, al menos sin previo aviso.

  5. Rodrigo dice:

    Excelente! es un campo demasiado interesante, ansioso por seguir leyendo. Gracias!

  6. LEONOR dice:

    BUENO ESTA ES MI PAGINA SOBRE IA..EN LA CUAL APORTO Y DOY A CONOCER A LAS PERSONAS UN POCO DE INFORMACION SOBRE LO QUE PUEDE HACER UN AGENTE INTELIGENTE POR NOSOTROS..ESPERO COMPARTAN Y PODER INTERCAMBIAR UN POCO DE SU CONOCIMIENTO….

Deja un comentario