Cuando las matemáticas emulan a la naturaleza: los algoritmos genéticos
Muchos de los profesores de biología habrán oído hablar de como, muchas veces, la ingeniería emula diseños de la naturaleza para fabricar determinados aparatos. Por ejemplo, la forma en huso de los submarinos, similar a las de los peces. Sin embargo, no son solamente los ingenenieros los que se inspiran en la naturaleza. También científicos tan abstractos como los matemáticos lo hacen. Una de las similitudes más curiosas es la de los algoritmos genéticos.
Sobre este tipo de métodos matemáticos he oído algunos comentarios, como que no son una buena idealización de la evolución. Esto es cierto, pero es que tales algoritmos sólo se inspiran en la evolución biológica, no intentan modelarla. Emplean un método de resolución de problemas calcado del que usa la naturaleza para resolver el problema de adaptar una forma de vida al entorno, pero nada más.
Un algoritmo genético es, en esencia, un método de optimización de funciones matemáticas que utiliza mecanismos similares a los que emplea la evolución natural, esto es: selección, recombinación y mutación. Por optimización de funciones se entiende calcular el valor máximo que posee una función en un determinado dominio, o conjunto de valores posibles donde puede evaluarse.
Si bien hay multitud de posibilidades para construir un algoritmo genético, voy a describir, brevemente, uno sencillo, para dar idea de cómo se construyen este tipo de métodos. Supongamos una función que toma valores enteros en un plano, esto es, una de la forma: z=f(x,y). Deseamos obtener su máximo en una región del plano denominada D (si queremos su mínimo, calculamos el máximo de -f(x,y) y le cambiamos el signo, es fácil ver que es un problema equivalente). El primer paso es crear el "código genético" asociado a cada punto (x,y) del plano. Por lo general, y porque funciona mejor así, se suele codificar en binario. Así, a cada valor de una coordenada se le asocia un número binario. Por ejemplo, supongamos que codifico las coordenadas x e y con un binario de longitud 8 cada una - (01010011,00110011) por poner uno -. Como con 8 binarios puedo
llegar a escribir 256 números diferentes, este "código genético" puede representar 256 por 256 puntos de D. Es obvio que mientras más largo el código genético, más precisión tendrá el método.
Una vez creado el "código genético", se genera una población aleatoria de "individuos", cada uno con un código genético determinado al azar. En los algoritmos genéticos celulares, llamados así porque se modelan con métodos similares a los autómatas celulares, estos individuos se ordenan en un casillero. El procedimiento a seguir es sencillo: se recorre el casillero haciendo que cada individuo se aparee con otro y dé lugar, en su propia casilla, a un hijo que lo sustituye. Los pasos son:
1) Selección: el individuo se "aparea" con el vecino que dé un valor más alto a f(x,y).
2) Recombinación: el "genoma" del nuevo individuo se obtendrá a partir del de sus progenitores, por medio de determinadas reglas.
3) Mutación: el "genoma" resultante tendrá una probabilidad muy baja de sufrir cambios (un 1 por un 0 o al revés) aleatorios.
Si se deja evolucionar el sistema un tiempo, los puntos tenderán a acercarse, cada vez más, al valor que maximice la función problema.
Si desean ampliar información, aquí tienen estos dos vínculos:
Informática evolutiva
Biotmates: algoritmos genéticos
Juan Cuquejo Mira.
Sobre este tipo de métodos matemáticos he oído algunos comentarios, como que no son una buena idealización de la evolución. Esto es cierto, pero es que tales algoritmos sólo se inspiran en la evolución biológica, no intentan modelarla. Emplean un método de resolución de problemas calcado del que usa la naturaleza para resolver el problema de adaptar una forma de vida al entorno, pero nada más.
Un algoritmo genético es, en esencia, un método de optimización de funciones matemáticas que utiliza mecanismos similares a los que emplea la evolución natural, esto es: selección, recombinación y mutación. Por optimización de funciones se entiende calcular el valor máximo que posee una función en un determinado dominio, o conjunto de valores posibles donde puede evaluarse.
Si bien hay multitud de posibilidades para construir un algoritmo genético, voy a describir, brevemente, uno sencillo, para dar idea de cómo se construyen este tipo de métodos. Supongamos una función que toma valores enteros en un plano, esto es, una de la forma: z=f(x,y). Deseamos obtener su máximo en una región del plano denominada D (si queremos su mínimo, calculamos el máximo de -f(x,y) y le cambiamos el signo, es fácil ver que es un problema equivalente). El primer paso es crear el "código genético" asociado a cada punto (x,y) del plano. Por lo general, y porque funciona mejor así, se suele codificar en binario. Así, a cada valor de una coordenada se le asocia un número binario. Por ejemplo, supongamos que codifico las coordenadas x e y con un binario de longitud 8 cada una - (01010011,00110011) por poner uno -. Como con 8 binarios puedo
llegar a escribir 256 números diferentes, este "código genético" puede representar 256 por 256 puntos de D. Es obvio que mientras más largo el código genético, más precisión tendrá el método.
Una vez creado el "código genético", se genera una población aleatoria de "individuos", cada uno con un código genético determinado al azar. En los algoritmos genéticos celulares, llamados así porque se modelan con métodos similares a los autómatas celulares, estos individuos se ordenan en un casillero. El procedimiento a seguir es sencillo: se recorre el casillero haciendo que cada individuo se aparee con otro y dé lugar, en su propia casilla, a un hijo que lo sustituye. Los pasos son:
1) Selección: el individuo se "aparea" con el vecino que dé un valor más alto a f(x,y).
2) Recombinación: el "genoma" del nuevo individuo se obtendrá a partir del de sus progenitores, por medio de determinadas reglas.
3) Mutación: el "genoma" resultante tendrá una probabilidad muy baja de sufrir cambios (un 1 por un 0 o al revés) aleatorios.
Si se deja evolucionar el sistema un tiempo, los puntos tenderán a acercarse, cada vez más, al valor que maximice la función problema.
Si desean ampliar información, aquí tienen estos dos vínculos:
Informática evolutiva
Biotmates: algoritmos genéticos
Juan Cuquejo Mira.
publicado por Juan a las
11:38 PM
2 Comentarios:
Según lo que he estudiado en análisis ya hay un método para hacer este tipo de problemas. Qué varía en cuanto al resultado utilizando el sistema binario?
Saludos!
By
Anya, at 2:02 PM
Hola Anya
En teoría, nada. El resultado deberá ser el mismo independientemente de la técnica que emplees.
Hay muchos métodos de cálculo numérico para cualquier tipo de problema matemático, entre ellos, el de calcular los máximos de una función. Lo que sucede es que, según qué función tengas, hay unos métodos que funcionan mejor o peor, hasta el punto de que para un problema, una técnica puede no converger hacia la solución deseada, mientras que esa misma técnica puede ser usada con gran éxito para resolver problemas diferentes.
Los algoritmos genéticos tienen la diferencia de ser métodos basados en el azar e inspirarse en la naturaleza. De esta forma, tienen éxito donde otros métodos se atascan, ya que son menos sensibles a máximos locales; como un algoritmo genético evalúa al tiempo diferentes regiones del espacio, en el caso de que una población de puntos prospere en él, acabará extinguiéndose cuando alguna otra se aproxime al máximo.
Un saludo.
Juan.
By
Juan, at 9:05 PM
Publicar un comentario en la entrada
<< Inicio