¿Sueñan los evolutivos con voluntarios interconectados?

Frente a la capacidad de 360 TFlops de Blue Gene, que actualmente aparece primero en la lista top500 de supercomputadores propietarios, el sistema de computación BOINC obtiene en promedio unos 521 TFlops. Esta capacidad de computo es debida a un total aproximado de 2 millones de nodos de los cuales en promedio unos 400000 se encuentran conectados al sistema a través de Internet. Los recursos de estos nodos son cedidos de forma voluntaria por usuarios que deciden procesar paquetes de información en sus propias máquinas, estamos hablando de lo que se denomina computación voluntaria.

Dentro de la computación voluntaria, el paradigma P2P se revela como alternativa para interconectar enormes cantidades de recursos distribuidos de forma descentralizada, es decir, sin ningún sistema de control central (aunque esta es la visión más estricta). Se puede decir que la fase actual de la Computación P2P está en sus inicios y como tal muchos de los trabajos que intentan aplicar este paradigma a problemas clásicos de cómputo representan tímidos avances.

Este es el caso del trabajo de Wei-Po Lee:

donde nos presenta un sistema paralelo de computación evolutiva que intenta aprovechar los recursos de una red de ordenadores mediante una aproximación basada en agentes, que son desarrollados con el framework JADE. La idea de la Computación P2P subyace en el artículo, si bien, son numerosas las cuestiones que no se abordan (p.ej. tolerancia a fallos, capacidad masivamente paralela o que las fases de la evolución sean sincronizadas) y que el mismo autor apunta en el apartado de conclusiones.

Esquematicamente, Wei-Po Lee propone tres tipos de agentes:

  • Agentes de estado, que controlan en cada nodo si los recursos del mismo están disponibles o no.
  • Agentes móviles, encargados de realizar las fases de la evolución en una población de individuos. Cada uno de estos agentes correspondería a una isla dentro del modelo de islas.
  • Agente de sincronización, se trata de un solo agente que se ejecuta en el nodo principal (por lo que existe cierta centralización). Este agente comprueba el estado de los recursos mediante comunicación con los agentes de estado asignando agentes móviles a recursos libres.

Se han realizado varias pruebas a la arquitectura considerando, en una red de 8 nodos, la resolución mediante Programación Genética del problema de evolucionar controladores de robots. Los resultados muestran una ganancia lineal del tiempo de resolución con respecto al número de nodos.

Desde un punto de vista práctico se trata de un buen trabajo, aunque como todo no se puede tener, dista mucho de una metodología formal para paralelizar masivamente algoritmos evolutivos en entornos P2P de computación voluntaria. No hagamos ruido pues y dejemos que los evolutivos sigan soñando con voluntarios interconectados… por el momento.

Advertisements

Paper on distributed evolutionary computation uploaded to ArXiV

I uploaded a couple of days our paper Self-adaptive Gossip Policies for Distributed Population-based Algorithms, which is a collaboration among a bunch of researchers from 4 different institutions trying to come up with the perfect algorithms that is able to extract all the juice from heterogeneous, peer to peer, dynamic, networks. Here’s the abstract:

Gossipping has demonstrate to be an efficient mechanism for spreading information among P2P networks. Within the context of P2P computing, we propose the so-called Evolvable Agent Model for distributed population-based algorithms which uses gossipping as communication policy, and represents every individual as a self-scheduled single thread. The model avoids obsolete nodes in the population by defining a self-adaptive refresh rate which depends on the latency and bandwidth of the network. Such a mechanism balances the migration rate to the congestion of the links pursuing global population coherence. We perform an experimental evaluation of this model on a real parallel system and observe how solution quality and algorithm speed scale with the number of processors with this seamless approach.

It’s also been submitted to Europar 2007 . Let’s cross our fingers It wasn’t accepted.

(Via BloJJ)

Intelligent Agent Enabled Genetic Ant Algorithm for P2P Resource Discovery (with Spanish summary)

This is my first paper explained in the Geneura Friday Seminar. As a rookie, I’ve found this paper easy to understand and quite interesting because it uses a classical Ant Algorithm and adds an ingenious solution: the use of anti-pheromone. Besides, it uses genetic programming!

Yeah, it’s quite complete, as you can see, and it’s perfect to start to deal with scientific papers that showns interest areas of the GeNeura team.

The author is Prithviraj(Raj) Dasgupta.

Abstract. Rapid resource discovery in P2P networks is a challenging
problem because users search for different resources at different times,
and, nodes and their resources can vary dynamically as nodes join and
leave the network. Traditional resource discovery techniques such as
flooding generate enormous amounts of traffic, while improved P2P re-
source discovery mechanisms such as distributed hash tables(DHT) in-
troduce additional overhead for maintaining content hashes on different
nodes. In contrast, self-adaptive systems such as ant algorithms provide
a suitable paradigm for controlled dissemination of P2P query messages. In this paper, we describe an evolutionary ant algorithm for rapidly dis-
covering resources in a P2P network.
Keywords: Peer-to-peer systems, software agents, ant algorithm, adap-
tive systems, genetic algorithm.

I’ve made a Spanish summary of the paper:

Algoritmo de agentes inteligentes genético basado en hormigas para descubrimiento de recursos en redes P2P.

1. INTRODUCCIÓN

-Inundaciones

-Nodos Super-pares

-DHT Dinamic Hash Tables

El problema de búsqueda de recursos se reduce a un problema de manejo de recursos.

Existen algoritmos basados en hormigas para el balanceo de carga.

Este algoritmo usa diferentes tipos de feromona y hormigas con diferentes comportamientos para hacer el descubrimiento de recursos más eficiente.

2. ALGORITMO DE HORMIGAS PARA DESCUBRIMIENTO DE RECURSOS P2P

El protocolo de descubrimiento P2P tradicional consiste en un mensaje “query” que se transmite por los nodos en una búsqueda primero en profundidad hasta que el recurso se encuentra o se termina el tiempo de vida del mensaje. Si el recurso se encuentra en un nodo se envía un “queryHit” de vuelta al nodo que originó la consulta. El nodo consultador y proveedor inician la descarga.

Este protocolo puede ser más eficiente si la búsqueda uniforme puede ser realizada por una búsqueda heurística basada en información.

Antiferomona: refuerzo negativo en los nodos que no llevan a una solución. Sin embargo, nodos que no son útiles para localizar un recurso pueden serlo para localizar otro. Por eso se usan hormigas Exploradoras que son neutrales a los nodos con feromona, pero son atraídas por nodos con anti-feromona.

Tipos de hormiguitas:

1) Hormigas Recolectoras hacia adelante: visitan nodos en busca de un recurso y depositan feromona en cada uno de ellos. En cada nodo prefieren ir a los vecinos con mayor cantidad de feromona y menor de antiferomona.

2) Hormigas Exploradoras hacia adelante: visitan nodos en busca de un recurso y depositan antiferomona en cada uno de ellos. En cada nodo prefieren ir a los vecinos con mayor cantidad de antiferomona.

3) Hormiga hacia atrás: ambos tipos de hormiga se convierten en este tipo al encontrar el recurso o al alcanzar los límites de la búsqueda sin haberlo encontrado. Recorren el camino hacia atrás dejando feromona si lo han encontrado, y anti-feromona si no.

3 MODELO DEL SISTEMA P2P

Un sistema P2P consiste en una red conectada de N nodos que se unen o dejan la red aleatoriamente. Cada nodo mantiene una tabla hacia adelante conteniendo las direcciones de sus vecinos usando el protocolo de descubrimiento P2P. Cada dirección contiene un peso normalizado que representa la feromona asociada a ese vecino, y que se actualiza cada vez que una hormiga lo selecciona para moverse.

Cuando un usuario en un nodo introduce una consulta para buscar un recurso se crea una hormiga.

3.1 Algoritmo de hormigas

Hormiga recolectora hacia adelante.

Reglas de actualización para la feronoma en el nodo n son las siguientes

Aquí van las ecuaciones, pero no tengo el cd del office.

α se determina experimentalmente y controla el decremento en la cantidad de feromona depositada por la hormiga. El peso de cada nodo por tanto es proporcional al peso actual. Esto previene el exceso de (anti)feromona.

La ecuación 2 se asegura de que los pesos de los nodos de la tabla continúan normalizados después de que el peso de un nodo se actualiza.

Hormiga exploradora hacia adelante.

Se comporta de manera similar a una hormiga recolectora pero usa la probabilidad inversa (1 – wti,n) para seleccionar un nodo. La probabilidad de seleccionar un nodo por una exploradora es proporcional a la cantidad de antiferomona depositada. La hormiga exploradora actualiza la anti-feromona en cada nodo visitado según las siguientes ecuaciones:

Hormiga hacia atrás:

Si la hormiga encuentra el recurso recorre el camino hacia atrás depositando feromona como se ha indicado anteriormente, o depositando anti-feromona si ha llegado a los límites sin encontrarlo.

4 Algoritmo Genético basado en hormigas

Puede ocurrir que la red se particione en rastros predominantes de feromona y anti-feromona con el algoritmo tradicional ejecutándose en cada una (sólo un tipo de hormiga). Usando algoritmos genéticos podemos hacer que las rutas evolucionen. Esto permite re-balancear las cantidades de feromona y anti-feromona y previene que las hormigas sigan rutas no actualizadas debido al carácter dinámico de la red.

Cuando un cierto número de consultas de búsqueda se originan en un nodo particular se ejecuta un AG en el nodo usando las rutas atravesadas por hormigas creadas para cada consulta de búsqueda.

Función de idoneidad:

F = 1- numero de saltos para localizar el recurso / maxSaltos, si tuvo éxito la hormiga.

F = γ si la hormiga fue incapaz de encontrar el recurso

γ es la probabilidad de recombinar los cromosomas hijos en la siguiente generación.

Representación de un cromosoma: Ruta (secuencia de nodos) atravesada por una hormiga.

Operador de cruce: Las rutas 1) no tienen por qué tener la misma longitud y 2) no tienen por qué tener nodos en común.

Escenario 1: no tienen nodos en común. Seleccionamos un único punto de cruce al azar. El nodo origen se introduce en el punto de cruce para asegurar que nuevas entradas no necesiten ser introducidas dentro de las tablas hacia adelante en los nodos en los puntos de cruce de los dos cromosomas participantes.

Escenario 2: Las rutas representadas por los dos cromosomas participantes en el la reproducción tienen uno o más nodos comunes. El operador de cruce se realiza en todos los nodos comunes.

Recombinación: Se reintroducen las hormigas hijas obtenidas en la población de padres. La idoneidad de cada hijo se determina como la media de la idoneidad de los padres.

5 RESULTADOS EXPERIMENTALES

– N=500 nodos en la red de simulación.

– Número de vecinos = distribución normal con media N/20 y desviación típica 1.5

– ρ es la probabilidad de que un nodo tenga un recurso.

– α = 4

– ρ = 0.15

– Limite = 10 saltos.

p = probabilidad de crear la hormiga como exploradora (p=0) o recolectora (p=1). Al inicio no hay feromona, y p=1, y va decreciendo en la simulación hasta que p = 0.

El número de recursos encontrados se incrementa cuando el valor de p va de 0.4 a 0.8, con una media de p=0.72. Se debe al valor de ρ

Con γ = 0.1 se emplean más hormigas exitosas para la recombinación, haciendo que el algoritmo siga visitando nodos ya recorridos.

Con γ = 0.7 se selecciona un número mayor de hormigas no exitosas, mejorando el porcentaje de búsquedas exitosas, ya que se rebalancearán los dos tipos de feromona.

CONCLUSIONES

Este algoritmo es mejor que el tradicional cuando los recursos son escasos.

Como siempre, el trabajo futuro consiste en intercambio de información entre hormigas de diferentes nodos.

___

That’s all. I hope that this post will be interesting for… for you, for example ;)

Oh, by the way, I’ve just see that the evil Sid 6.7 in “Virtuosity” has been created using Genetic Algorithms!

Pablo.

Discussing “Parallelizing evolutionary computation: A mobile agent-based approach”

In our paper seminar today, we are discussing Parallelizing evolutionary computation: A mobile agent-based approach:

Parallel computation models have been widely used to enhance the performance of traditional evolutionary algorithms, and they have been implemented on parallel computers to speed up the computation. Instead of using expensive parallel computing facilities, we propose to implement parallel evolutionary computation models on easily available networked PCs, and present a multi-agent framework to support parallelism. With the unique characteristics of agent autonomy and mobility, mobile agents can carry the EC-code and migrate from machine to machine to complete the computation dynamically. To evaluate the proposed approach we have developed a prototype system on a middleware platform JADE to solve a time-consuming task. Different kinds of experiments have been conducted to assess the developed system and the preliminary results show the promise and efficiency of our mobile agent-based approach.

Juanlu is our MC, and will post a summary later on. Interesting paper, very close to our own work with DREAM

In Search of Simplicity: Self-Organizing Multi-Source Multicast Overlay

Para empezar mi participación en el blog os comentaré brevemente el artículo que leí, comprendí (con ciertas salvedades :-D) y conté a los asistentes a la reunión del dia 9/03/2007.

Dejo el título en inglés, así como algunos términos usados en dicho artículo porque su traducción en muchos casos suena peor que el término anglosajón. ;)

Link al artículo: http://arxiv.org/abs/cs.DC/0702157

Título: In Search of Simplicity: Self-Organizing Multi-Source Multicast Overlay

Autores: M. Ripeanu, I. Foster, A. Iamnitchi, A. Rogers

Abstract: Multicast communication primitives have broad utility as building blocks for distributed applications. The challenge is to create and maintain the distributed structures that support these primitives while accounting for volatile end-nodes and variable network characteristics. Most solutions proposed to date rely on complex algorithms or global information, thus limiting the scale of deployments and acceptance outside the academic realm.
This article introduces a low-complexity, self-organizing solution for maintaining multicast trees, that we refer to as UMM (Unstructured Multi-source Multicast). UMM uses traditional distributed systems techniques: layering, soft-state, and passive data collection to adapt to the dynamics of the physical network and maintain data dissemination trees. The result is a simple, adaptive system with lower overheads than more complex alternatives. We have implemented UMM and evaluated it on a 100-node PlanetLab testbed and on up to 1024-node emulated ModelNet networks Extensive experimental evaluations demonstrate UMM’s low overhead, efficient network usage compared to alternative solutions, and ability to quickly adapt to network changes and to recover from failures.

Temas Relacionados: Sistemas distribuidos (distributed systems), Autoorganización (Self-Organizing), Redes de recubrimiento (overlay networks), multicast.

Continue reading

Let the good times (blog)roll

About time our research group started a new blog. This will be a bilingual blog (Spanish/English) mainly devoted to our research seminars, research results, research beer drinking contests, and anything else that happens to the GeNeura group, a small groups that usually deals with evolutionary computation, neural networks, ant-colony algorithms, and other bioinspired stuff.