Algoritmos Bioinspirados

En nuestro entorno se dan una serie de acontencimientos que han inspirado algunos algoritmos de búsqueda de soluciones. Algoritmos genéticos y colonia de hormigas son algunos de ellos.
Estos algoritmos ofrecen soluciones óptimas y pseudoóptimas, y su estudio ha demostrado que se pueden obtener muy buenos resultados en un tiempo en el que otros algoritmos de búsqueda en profundidad no se acercaría ni por asomo a una solución semejante.

Genético:

El funcionamiento del genético se basa en la generación de estados mediante un conjunto de individuos, que forman una población.
Cada individuo se compone de un conjunto de genes, que suelen ser 0 y 1s, aunque pueden ser enteros, caracteres... todo es cuestión de saber interpretar el estado y la solución obtenida según la representación del individuo escogida.
Esta población se va modificando mediante la reproducción de unos individuos que han pasado un proceso de selección, mezclando sus genes. La probabilidad de que un individuo sea escogido para la reproducción es proporcional a lo bueno que sea ese individuo, para lo que deberemos implementar una función, denominada fitness, que nos da dicho valor.
Una vez pasada la etapa de selección, se inicia la etapa de reproducción. Podemos elegir que los individuos se procreen 2 a 2 por la mitad, o con un random... escogiendo los genes que conservará el hijo de cada individuo padre y formando la siguiente generación.
Ahora solo nos queda la etapa de mutación. En esta etapa se procede a mutar los genes, según cierta probabilidad, que suele ser muy baja. Una probabilidad alta nos da una convergencia lenta, pero una alta amplia el espacio de búsqueda cuando el algoritmo se ha estancado en una solución debido a que hemos alcanzado un máximo local.
Este proceso se repite durante un número de iteraciones definido por el usuario.
Una vez implementado el algoritmo, se trata de jugar con los parámetros probabilidad de selección, probabilidad de mutación, numero de individuos y número de iteraciones.

Colonia de hormigas:

En la naturaleza, las hormigas encuentran el camino óptimo desde el alimento hasta el hormiguero ayudandose de una sustancia denominada feromona que es depositada por las hormigas y se evapora con el tiempo. A mayor cantidad de feromona mejor es el camino. Cada hormiga escogerá los caminos de mejor feromona. Así, inicialmente se mueven de forma aleatoria hasta encontrar el alimento. Es en la vuelta al hormiguero cuando depositan el rastro de feromona para que otras hormigas lo sigan.
En esto es básicamente en lo que se basa este algoritmo.
Las hormigas son agentes computacionales, que colaboran entre sí para encontrar la solución óptima, almacenando en cada paso cómo de bueno es el camino escogido.
Existen varios tipos de algoritmos que implementan este comportamiento, pero solo me voy a centrar en explicar a nivel general en qué consiste la idea.
Cada agente puede explorar el espacio de estados o explotar la feromona, según un valor probabilístico.
Explorar el espacio de estados significará que avanzará al siguiente estado vecino, sin importarle la distancia ni la feromona.
Al explotar la feromona el agente eligirá el siguiente estado en función de una probabilidad dada por la distancia al siguiente estado y por la feromona que hay en ese camino. Esta feromona como ya he comentado se decrementa con el tiempo.
A la vuelta del recorrido el agente actualiza los niveles de feromona, indicando como de bueno ha sido el recorrido.

Lo curioso de estos algoritmos es lo bien que funcionan basándose simplemente en parámetros de probabilidad, en el que escoger el siguiente estado es "pseudoaleatorio" en cierto modo.

Sobre punteros c

Empty your memory,
with a free()…
like a pointer!

If you cast a pointer to a integer,
it becomes the integer,
if you cast a pointer to a struct,
it becomes the struct…
The pointer can crash…,
and can Overflow…
Be a pointer my friend…

¿Quién no ha tenido nunca más de un quebradero de cabeza con una violación de segmento, o un core? A veces te vale la excusa de "es que en casa sí funciona...", pero créeme, en la mayoría de los casos no.

Trabajar con punteros es relativamente sencillo si tienes una idea clara de cómo referenciar a memoria y si sigues una metodología sistemática a la hora de hacerlo.
Intenta entender los siguientes aspectos, es posible que una vez entendidos disminuyas considerablemente el número de cores o fallos provocados por accesos a memoria:

1. A la hora de realizar alguna comparación, ten cuidado cuando las variables implicadas sean punteros, es posible que no quieras comparar el VALOR DEL PUNTERO (es decir, la dirección de memoria) y que lo que quieras comparar realmente es el VALOR al que apunta el puntero (es decir, el valor contenido en memoria).
2. Asegurate de que liberas los punteros para evitar fugas de memoria (o memory leaks). Esto es un problema sobretodo en proyectos grandes. Imagínate que en tu programa realizas una llamada a una función que reserva 1 KB, que olvidas liberar. Esto no es problema si tu programa terminase, pero si actua como demonio, en segundo plano... y además no realiza esa llamada una vez, sino varias, tu programa estaría consumiendo de forma innecesaria memoria del sistema de forma incremental.
3. De igual modo que en 1.-, ten cuidado a la hora de asignar valores a punteros. Tenemos una tendencia a copiar un puntero en otro puntero con el operador igual. Esto solo es válido si lo que quieres copiar son las referencias a memoria. Si no, deberías copiar elemento a elemento o mediante un memcpy...
4. A la hora de trabajar con paso por referencia, es más comodo reservar la variable que vas a pasar por referencia de forma estática y en la llamada al procedimiento/función pasarle la dirección con el operador &.
5. Recuerda que si reservas memoria dentro de un procedimiento/función la estás reservando en pila, por lo que cuando llames a otras 1 o 2 funciones más se machacará, probocando un core. Si quieres reservar memoria dentro de un procedimiento para una variable que le pasas por referencia debes pasar el puntero por referencia, y no la variable. Es decir, la signatura del parámetro debe ser "puntero a puntero" y no "puntero"
6. Ten en cuenta que la mayoría de las veces que declaras un puntero debes reservar memoria, a no ser que lo vayas a usar como un puntero auxiliar o algo por el estilo.
7. Presta especial atención a no acceder a posiciones del puntero que sobrepasen lo que has reservado para el. Recuerda siempre que debes indexar entre 0 y TAMAÑO-1.
   

Veamos un ejemplo del caso 1.-




















Este ejemplo está testeado en un ubuntu 9.10.
Los resultados son los esperados:

• La primera comparación, en la que comparamos los punteros, nos dice que no son iguales.
• La segunda, en la que comparamos el contenido de cada posición, nos dice que sí.
  

Si te fijas en cómo comparo elemento a elemento, sumo -i- al puntero. Hubiera dado lo mismo si lo hubiese hecho con -[i]-, pero es por diferenciar un poco entre memoria estática y dinámica.
Efectos del caso 2.-

Veamos un ejemplo de como producir una fuga de forma "involuntaria".











Podemos observar en el código que la memoria reservada en foo() no se libera, y que se llama a dicha función en el código de forma indefinida mediante un while(1), por lo que si este proceso se ejecuta en segundo plano provocará un incremento del uso de memoria a medida que pase el tiempo.

Una forma de monitorizar el uso de memoria en linux es a través de ps aux, observando la columna stat:








Efectos del caso 3.-

En rojo encuadro el error habitual y en azul una forma correcta de hacerlo.




















La parte comentada sería la forma incorrecta de hacerlo. Está así porque da un core. Los printfs están colocados a posta para que se machaque la pila, si no estuvieran es posible que no se pudiera reproducir el core.
Si te fijas, al llamar a foo2, el parámetro viene precedido del símbolo &. Esto significa que es la dirección de esa variable que le pasamos como parámetro, que sería la dirección del puntero, es decir, un puntero a puntero, cumpliendo con la signatura de la cabecera de la función.
Esto es todo de momento...
SALUDOS!



Vuelos Baratos
Anuns