Blog de robótica e inteligencia artificial

9/15/2014

¿Cómo se programa un algoritmo inspirado en la naturaleza?

Existen múltiples ejemplos de algoritmos que sirven para resolver sistemas de ecuaciones e inecuaciones. De esa manera, se pueden encontrar las raíces de un sistema, su punto máximo y mínimo, extremos, puntos concretos que busquemos, etc. Una de las grandes ventajas de nuestro tiempo es que los ordenadores nos ayudan a ejecutar esos algoritmos de manera automática y mucho más rápido que haciéndolos a mano.

Por ejemplo, uno de los más corrientes que todo alumno de ingeniería aprende durante la carrera es el algoritmo de Newton-Raphson, que sirve para hallar la raíz de una ecuación. 

En esta ocasión, en este artículo se tratará de explicar cuáles son los pasos según los cuales se programa un algoritmo que se inspira en la naturaleza. Concretamente, según su autor se inspira en bandadas de pájaros o bancos de peces. Estoy hablando de uno de los muchos algoritmos de este tipo, y se llama algoritmo de optimización por enjambre de partículas (particle swarm optimization, PSO). Se basa en que muchas partículas-miembros de la bandada ayudan a encontrar la solución óptima del problema. PSO se emplea normalmente para calcular el mínimo de un conjunto de datos. Además, las características de su funcionamiento permiten que no se atasque en mínimos locales, sino que llegue al mínimo absoluto. 



Vamos a intentar explicar los pasos que se darían en este algoritmo, y el ejemplo de la curva anterior nos puede servir de ejemplo:

1- Se crean las partículas que queramos (pongamos 10), que se colocan aleatoriamente a lo largo de toda la curva. 

2- La posición de estas partículas se va a determinar por la coordenada X en la que se sitúan. Es decir, tendremos 10 pares de puntos (X,Y). Pero queremos minimizar la coordenada Y. 

3- En este instante, se comprueba cuál de las 10 partículas tiene la coordenada Y más baja y en qué posición de X está.

4- El resto de las partículas se mueven un poquito hacia la posición de esa partícula en el Y más bajo (de momento).

5- Este proceso se repite unas cuantas veces, dependiendo de la complejidad del problema.

Ahora, veamos en marcha el algoritmo PSO. En el problema de la animación se trata de encontrar el punto mínimo de esa superficie.



Lógicamente, debido a que el algoritmo tiene una parte de aleatoriedad, el algoritmo no va a comportarse exactamente igual en todas las ocasiones. Además, en el paso 4, la velocidad a la que las partículas se acercan a la partícula óptima es variable a voluntad, lo cual puede permitir que se llegue antes a la solución.

El PSO tiene una base de funcionamiento muy parecida a la de los algoritmos genéticos, pero hay diferencias.

En la vida real, no se trata de buscar el punto más bajo de una curva por el mero hecho de hacerlo. Supongamos que tenenemos una máquina que tiene tres parámetros que rigen su funcionamiento (velocidad de giro, temperatura de funcionamiento, y corriente eléctirca, por decir unos): Gracias al PSO podemos calcular cuáles son los valores de esos parámetros para que el sistema tenga un consumo mínimo, por ejemplo.

Este algoritmo tiene modificaciones que hacen que las partículas "aprendan" o que las partículas no se atasquen en ciertas posiciones del problema a resolver. Pero eso lo dejaremos para otro artículo.



Este artículo participa en la Edición 5.6 del Carnaval de Matemáticas, el cua en esta ocasión lo aloja el brillante blog Cifras y Teclas.


Comparte:

0 comentarios:

Publicar un comentario

Sígueme en redes:

descripción descripción descripción

En mi mesilla

Blog Archive