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.
GeNeura Team 