Algoritmo di branching a numero di walker costante

Nel nostro lavoro abbiamo utilizzato un particolare algoritmo di branching che tiene fisso il numero di walker, variando il peso assegnato ad ogni singolo walker. Quest'algoritmo è già stato utilizzato in precedenti lavori (vedi [30,31,32]). Ad ogni passo dell'evoluzione temporale dei walker, generata dall'equazione 2.10, il peso attribuito a ciascun walker viene moltiplicato per quello del passo precedente. Questo avviene per un certo numero di passi k.

$$W_a(R_i)=w(R_i)w(R_{i-1})....w(R_{i-k})$$ (2.11)

dove $a$ indica l'indice del walker e va da $1$ a $N_w$. Dopo $k$ passi, anziché proseguire l'evoluzione, viene generato un nuovo set di $N_w$ walker, tutti con peso unitario, la cui distribuzione è legata a quella del passo precedente dall seguente regola:

• Per ogni vecchio walker vengono generati $n_i$ nuovi walker, con $n_i$ dato da:
  

  $$n_i = INT \left [ N_w\frac{W_i}{\sum_j W_j} \right ]$$ (2.12)

  
  
  in questo modo si generano $m$ nuovi walker con $m < N_w$
• Visto che vogliamo lavorare con $N_w$ costante ne restano $N_w - m$, che vengono generati con probabilità:
  

  $$p_i = N_w \frac{W_i}{\sum_j W_j} - INT \left [N_w \frac{W_i}{\sum_j W_j} \right ]$$ (2.13)

  
  
  a partire dai vecchi.

Questa riconfigurazione evita che, durante l'evoluzione, i pesi dei singoli walker non diventino troppo differenti tra loro, lasciando che pochi walker dominino su tutti gli altri.
Un altro vantaggio, non indifferente di questo algoritmo, è il fatto di essere più efficiente nell'implementazione su macchine parallele. Infatti tenendo fisso il numero di walker, è possibile distribuire su tutti i processori di un calcolatore parallelo un ugual numero di walker, e quindi lo stesso carico di lavoro. Algoritmi con numero di walker variabile portano ad un diverso carico di lavoro per diversi processori: il numero di walker fluttua nel tempo in modo casuale sui diversi processori, facendo sì che alcuni di essi debbano aspettare quelli con maggior carico di lavoro.