## 5 Heuristic Approaches
### Dynamic Island Model
#### 5.2.1 Principle
```
Input :\((S,f)\) : optimization problem; \(\alpha\) : learning rate ; \(\beta\) : noise rate; \(N\) : initial population size in each island; \(itmax\) : number of iterations; \(p_{c}\) : crossover rate; \(p_{m}\) : mutation rate Result :\(s\) : a solution \(D_{ij}=0\); \(M_{ij}=\frac{1}{v}\) ; \(P_{i}=\text{populate}(N)\) ; \(it=0\) ; while(\(it<itmax\))do for(\(i=1\), \(i\leq\
u\), \(i=i+1\))do \(r=\text{genRandom(0,1)}\) ; if(\(r<p_{c}\))then \(p_{1}\), \(p_{2}\) = select(\(P_{i}\)) ; \(children\) = crossover(\(p_{1}\),\(p_{2}\)) ; \(o_{i}(children,p_{m})\) ; \(P_{i}=P_{i}\cup children\); \(worst\) = selectWorst(\(f\),\(P_{i}\)) ;  replace(\(P_{i}\),\(worst\),\(children\)) ;  end while  end while  update(\(M\),\(D\)) ;  migrate(\(P\),\(M\));  analyze(\(D\),\(f\)); \(it=it+1\) ;  end while \(s=\)best(\(f\), \(\cup_{i=1}^{\
u}P_{i}\)) ; return\(s\)
```  
**Algorithm 2**DIM Algorithm  
```
Input :\((S,f)\) : optimization problem; \(\alpha\) : learning rate ; \(\beta\) : noise rate; \(N\) : initial population size in each island; \(itmax\) : number of iterations; \(p_{c}\) : crossover rate; \(p_{m}\) : mutation rate Result :\(s\) : a solution \(D_{ij}=0\); \(M_{ij}=\frac{1}{v}\) ; \(P_{i}=\text{populate}(N)\) ; \(it=0\) ; while(\(it<itmax\))do for(\(i=1\), \(i\leq\
u\), \(i=i+1\))do \(r=\text{genRandom(0,1)}\) ; if(\(r<p_{c}\))then \(p_{1}\), \(p_{2}\) = select(\(P_{i}\)) ; \(children\) = crossover(\(p_{1}\),\(p_{2}\)) ; \(o_{i}(children,p_{m})\) ; \(P_{i}=P_{i}\cup children\); \(worst\) = selectWorst(\(f\),\(P_{i}\)) ;  replace(\(P_{i}\),\(worst\),\(children\)) ;  end if  end while  update(\(M\),\(D\)) ;  migrate(\(P\),\(M\));  analyze(\(D\),\(f\)); \(it=it+1\) ;  end while
```  
**Algorithm 3**DIM Algorithm  
``` Input :\((S,f)\) : optimization problem; \(\alpha\) : learning rate ; \(\beta\) : noise rate; \(N\) : initial population size in each island; \(itmax\) : number of iterations; \(p_{c}\) : crossover rate; \(p_{m}\) : mutation rate Result :\(s\) : a solution \(D_{ij}=0\); \(M_{ij}=\frac{1}{v}\) ; \(P_{i}=\text{populate}(N)\) ; \(it=0\) ; while(\(it<itmax\))do for(\(i=1\), \(i\leq\
u\), \(i=i+1\))do \(r=\text{genRandom(0,1)}\) ; \(r=\text{genRandom(Update

This process allows modifying the transitions \(M_{ij}\) only for the best islands \(i\). This is possible with intermediates vectors: a reward vector \(R\) and a stochastic noise vector \(N\) (\(\sum_{j=1}^{v}N_{j}=1\)) defined for each island \(j=1,\ldots,v\). A set \(B\) is also defined to store the indexes of the best island according to \(D\). \[R_{j}=\left\{ \begin{array}{ll}\frac{1}{B}&\text{if $j\in B$}\\ 0&\text{otherwise.}\end{array} \right. \tag{41}\]

\[B=\underset{i=1,\ldots,v}{\text{argmax }}D_{ij}\]

The transition \(M_{ij}\) for each pair of islands \((i,j)\) is then updated as follows. \[M_{ij}=(1-\beta)(\alpha M_{ij}+(1-\alpha)R_{j})+\beta N_{j} \tag{42}\]

As stated in [14], only the islands where the individuals obtained significant improvements benefit from a reward, thus reinforcing the best operators. In the calculation of \(M_{ij}\), the parameter \(\alpha\) represents the inertia (or exploitation) and \(\beta\), the amount of noise necessary to explore other search space areas. Migrate

The migration process involves every individual from each island and the transition matrix \(M\). In this process, a random number \(r\sim\mathcal{U}(0,1)\) is drawn from a uniform distribution for each individual of the population \(P_{i}\). For each destination island \(j\), if \(r<M_{ij}\) then the individual is sent to island \(j\) and remove from island \(i\). Analyze

This process retrieves for each pair of islands \((i,j)\) the best fitness among individuals that have migrated from island \(i\) to island \(j\) in the previous iteration, thus measuring the benefits of the transition \(i\to j\). \[D_{ij}=\underset{s\in P_{ji}}{\max}f(s) \tag{43}\] \[P_{ji}=\{s\in P_{j}s\text{ comes from }i\}\]

The 'analyze' process needs the originating island of individuals at previous iteration. Consequently, this information is stored in the solution.