# Logarithmic negativity and ground-state phase diagram of the 1D
antiferromagnetic spin-$1$ Heisenberg model with single-ion anisotropy

Vl. V. Papoyan<EMAIL_ADDRESS>Bogoliubov Laboratory of Theoretical
Physics, Joint Institute for Nuclear Research, 141980 Dubna, Russian
Federation  Dubna State University, Dubna, Russian Federation  G. Gori
<EMAIL_ADDRESS>Institut für Theoretische Physik, Universität
Heidelberg, 69120 Heidelberg, Germany  CNR-IOM DEMOCRITOS Simulation Center,
Via Bonomea 265, I-34136 Trieste, Italy  V. V. Papoyan (Jr.)
<EMAIL_ADDRESS>Meshcheryakov Laboratory of Information Technologies, Joint
Institute for Nuclear Research, 141980 Dubna, Russian Federation  Dubna State
University, Dubna, Russian Federation  A. Trombettoni<EMAIL_ADDRESS>Department of Physics, University of Trieste, Strada Costiera 11, I-34151
Trieste, Italy  CNR-IOM DEMOCRITOS Simulation Center, I-34136 Trieste, Italy
N. Ananikian<EMAIL_ADDRESS>National Science Laboratory, Alikhanian Br. 2,
0036 Yerevan, Armenia  CANDLE Synchrotron Research Institute, Acharyan 31,
0040 Yerevan, Armenia

###### Abstract

Ground-state entanglement properties in the 1D antiferromagnetic spin-$1$
Heisenberg model with external magnetic field $B$ and single-ion anisotropy
$D$ are investigated. The logarithmic negativity for nearest and non-nearest
neighbor sites on finite chains is obtained. The resulting phase diagram is
discussed in the $B-D$ plane, and a line where the energy density is
independent on the size is determined and shown to end in a triple point.
Finally, results for the logarithmic negativity on finite chains at finite
temperature as a function of $B$ and $D$ are presented.
Keywords: Heisenberg model, quantum spin chains, antiferromagnetism,
entanglement, logarithmic negativity

###### pacs:

74.25.Ha, 03.67.Mn, 75.50.-Ee 75.10.-b

##  I Introduction

Quantum magnetism encompasses a wide range of correlated materials and
physical phenomena. Quantum entanglement is conveniently employed to study
phase transitions in magnetic systems and many-body systems [1]. Quantum
fluctuations and competing interactions in many-body quantum systems are very
important because they contain important information emerging in the
quantification of various physical observables and leading to unusual and
exciting physical properties connected to the occurrence of strong
correlations [1, 2].

Entanglement has been successfully expressed in terms of correlation functions
[3], and it is related to magnetic susceptibility [4]. Thermal quantum
correlations play an important role in antiferromagnetic systems that have
rich phase diagrams, and in particular in low-temperture magnetism resulting
in interesting phenomena such as magnetization plateaus.

Great interest in quantum frustrated systems has surrounded the experimental
observation of the $1/3$ magnetization plateau in the diamond chain compound
of natural material azurite $Cu_{3}(CO_{3})_{2}(OH)_{2}$, with two broad peaks
observed at around $20$ and $5K$ in both magnetic susceptibility and specific
heat [5]. High magnetic field $Cu$ NMR spectra were used for determination of
the local spin polarization in the $1/3$ magnetization plateau, specific heat,
magnetic susceptibility, magnetocaloric properties, entanglement properties of
azurite and anisotropic Heisenberg-Isingc chains by applying density
functional theory, the density matrix renormalization group method, transfer
matrix techniques, and the Gibbs-Bogoliubov inequality [6, 7, 8, 9, 10].

The entanglement entropy ($EE$) behavior for nearest and non-nearest neighbor
sites was investigated in the Heisenberg antiferromagnetic chain [11], with
entanglement that may exist between non-nearest neighbors at low temperatures.
In the present manuscript, logarithmic negativity ($LN$) for nearest and non-
nearest neighbors is defined in the 1D spin-$1$ antiferromagnetic Heisenberg
chain with single-ion anisotropy. The thermal negativity for small Heisenberg
clusters of frustrated spin-$1$ anisotropic model with bilinear-biquadratic
exchange, single-ion anisotropy and magnetic field has been studied in [12].
Morever, the single-ion anisotropy properties effect on the magnetization
plateaus, magnetic susceptibility, specific heat, and Schottky peaks of an
octanuclear nickel phosphonate cage
$Ni_{8}(\mu_{3}-OH)_{4}(OMe)_{2}(O_{3}PR_{1})_{2}(O_{2}C^{t}Bu)_{6}(HO_{2}C^{t}Bu)_{8}$
has been theoretically discussed [13]. The results are in excellent agreement
with experimental data [14, 15]. Magnetic behavior and susceptibility of
homometallic molecular
$[Ni_{3}(fum)_{2}-(\mu_{3}-OH)_{2}(H_{2}O)_{4}]_{n}(2H_{2}O)_{n}$ ferrimagnet
on a diamond chain with alternating spin values $S=2$ and $S=1$ were measured
at low temperatures [16]. The magnetization plateaus, specific heat, Schottky
peaks, superstable points in a $2D$ mapping, and thermal entanglement
(negativity) of the spin-$1$ Ising-Heisenberg with single-ion anisotropy on
infinite diamond chain for homometallic molecular
$[Ni_{3}(fum)_{2}-(\mu_{3}-OH)_{2}(H_{2}O)_{4}]_{n}(2H_{2}O)_{n}$ ferrimagnet
have been studied using the transfer-matrix approach and dynamical system
theory [17, 18, 19, 20]. The magnetic, entropy and magnetocaloric properties,
and the Grüneisen parameter of the mixed spin-$(1/2,1)$ two-leg model on an
Ising-Heisenberg ladder in fully anisotropic case with different Landé
$g$-factors have been examined using the transfer matrix technique [21].

The homodinuclear nickel complex (NAOC) [22] serves as an experimental
realization of the spin-$1$ Heisenberg dimer [23]. The bipartite thermal
entanglement (negativity) of the quantum antiferromagnetic spin-$1$ has been
discussed, and as well the negativity plateaus as a function of the magnetic
field and the uniaxial single-ion anisotropy in the ground states for quantum
antiferromagnetic and ferrimagnetic coupling are also shown for NAOC. Specific
heat, susceptibility, and magnetization measurements have obtained in the
spin-$1$ antiferromagnetic Heisenberg chain
$Ni[C_{2}H_{8}N_{2}]_{2}Ni[CN]_{4}$ with uniaxial single-ion anisotropy $D$
was studied [24]. One can find the behavior of the entanglement entropy $EE$
or logarithmic negativity $LN$ for nearest and non-nearest neighbors for low
temperatures, the external magnetic field $B$ and the single-ion anisotropy
$D$. The points $B_{c}$ or $D_{c}$ at which entanglement disappears in the
ground state have been obtained for the antiferromagnetic Heisenberg chain
$Ni[C_{2}H_{8}N_{2}]_{2}Ni[CN]_{4}$ and many efforts have also been devoted to
the study the entanglement entropy $EE$ and logarithmic negativity $LN$ [25,
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38].

The presentation is organized as follows. In Section II we consider the 1D
antiferromagnetic spin-$1$ Heisenberg $XXX$ model with external magnetic field
$B$ and single-ion anisotropy $D$ and we give the definition of $LN$. The
properties of entanglement states, $LN$, and critical points in the ground-
state phase diagram are discussed in Section III. The $LN$ for nearest and
non-nearest neighbors on finite chains with sizes $N=4,5,6,7,8$ at low
temperatures for different values of external magnetic field $B$ and single-
ion anisotropy $D$ are investigated in Section IV. Finally, concluding remarks
are presented in Section V.

##  II Model and Definitions

The Hamiltonian for the 1D antiferromagnetic spin-$1$ Heisenberg $XXX$ model
with external magnetic field $B$ and single-ion anisotropy $D$ is given as

$\displaystyle H$ $\displaystyle=$ $\displaystyle
J\sum_{i=1}^{N}\vec{S}_{i}\cdot\vec{S}_{i+1}+D\sum_{i=1}^{N}(S_{i}^{z})^{2}+B\sum_{i=1}^{N}S_{i}^{z}.$
(1)

where $J=1$ to fix the energy scale, $D$ represents uniaxial single-ion
anisotropy, $B$ is the controllable parameter (periodic boundary conditions
are assumed). The local spin vector $\vec{S}_{i}$ for each site has the
components of the spin-$1$ operators:

$\displaystyle S^{x}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\begin{array}[]{lll}0&1&0\\\ 1&0&1\\\
0&1&0\end{array}\right),\hskip
11.38092ptS^{y}=\frac{1}{\sqrt{2}}\left(\begin{array}[]{lll}0&-i&0\\\
i&0&-i\\\ 0&i&0\end{array}\right),\hskip
11.38092ptS^{z}=\left(\begin{array}[]{lll}1&0&0\\\ 0&0&0\\\
0&0&-1\end{array}\right).$ (11)

At thermal equilibrium, the state of the system is determined by the density
matrix

$\hat{\rho}(T)=\frac{e^{-{\frac{H}{k_{B}T}}}}{Z}=\sum_{\alpha}\frac{e^{-{\frac{E_{\alpha}}{k_{B}T}}}}{Z}|\psi_{\alpha}\rangle\langle\psi_{\alpha}|,$
(12)

where $E_{\alpha}$ are the eigenvalue of the $\alpha$-th quantum many body
eigenstate and the partition function is $Z=\sum_{\alpha}e^{-\beta
E_{\alpha}}$ with $\beta={1/k_{B}T}$ (from now on $k_{B}=1$).

For spin-$1$ system the degree of pairwise entanglement, measured in terms of
the negativity $Ne$, can be employed to evaluate the thermal state of concern
[25, 26]. The negativity of a state $\rho_{ab}$ is defined as

$\textit{Ne}=\sum_{i}\ |\mu_{i}|,$ (13)

where the $\mu_{i}$’s are negative eigenvalues of $\rho_{ab}^{T_{1}}$ and
$T_{1}$ denotes the the partial pairwise transpose with respect to the first
system, i.e., for bipartite system in state $\rho_{ab}$ it is defined as

$\langle i_{1},j_{2}|\rho_{ab}^{T_{1}}|k_{1},l_{2}\rangle\equiv\langle
k_{1},j_{2}|\rho_{ab}|i_{1},l_{2}\rangle,$ (14)

for any orthonormal but fixed basis. Here $\rho_{ab}$ is a partial trace of
density matrix. Definition (13) is equivalent to

$\textit{Ne}=\frac{\parallel\rho_{ab}^{T_{1}}\parallel_{1}-1}{2},$ (15)

where $||\rho_{ab}^{T_{1}}||_{1}$ is trace norm of $\rho_{ab}^{T_{1}}$
($||*||_{1}=Tr\sqrt{*^{{\dagger}}*}$). For unentangled states negativity
vanishes, while Ne$>$0 gives a computable measure of thermal entanglement.

The logarithmic negativity $LN$ is an entanglement measure defined as

$\displaystyle
LN=\log_{2}\left(\parallel\rho_{ab}^{T_{1}}\parallel_{1}\right)=\log_{2}\left(\sum_{k}|\lambda_{k}|\right)$
(16)

where the $\lambda_{k}$’s are the eigenvalues of the partially transposed
matrix $\rho_{ab}^{T_{1}}$. Since values of negativity for nearest and non-
nearest neighbors are small we consider, as entanglement measure, the
logarithmic negativity $LN$.

##  III Logarithmic negativity of ground-states

We first examine the ground state of 1D antiferromagnetic spin-$1$ Heisenberg
$XXX$ models with external magnetic field $B$ and single-ion anisotropy $D$ on
the finite chain with sizes $N=4$ and $N=6$. The behavior of logarithmic
negativity $LN$ as a function of $B$ for nearest, next-nearest and next-next-
nearest neighbors is displayed in Fig. 1, for $D=1$. There is a point $B_{c}$
in which the entanglement for $B\geq B_{c}$ disappears. $B_{c}$ is the point
of a quantum phase transition [2]. At the same time the critical point $B_{c}$
will be different for fixed values of $D$: e.g., $B_{c}=3$ at $D=-1$,
$B_{c}=4$ at $D=0$, $B_{c}=5$ at $D=1$ in the ground state ($T=0$).

In Fig. 2 we present the behavior of logarithmic negativity $LN$ as a function
of $D$ for nearest, next-nearest and next-next-nearest neighbors. In the
ground state the point of a quantum phase transition from which entanglement
exists is exactly zero, $D_{c}=0$, at $B=4$ for all values of $N$.

Figure 1: The logarithmic negativity $LN$ of the ground state as a function of
external magnetic field $B$ at fixed $D=1$ (here and in the figures $J=1$).
The upper curve shows the variation in $LN$ the amount of entanglement of the
nearest neighbors, the middle and lowest curves show the same for the next-
nearest and next-next-nearest neighbors, respectively. Plot (a) corresponds to
the finite chain of size $N=4$, while plot (b) corresponds to $N=6$. Figure 2:
The logarithmic negativity $LN$ of the ground state as a function of the
single-ion anisotropy parameter $D$ at fixed $B=4$. The upper curve shows the
variation of $LN$ for nearest-neighbors, the middle and lowest curves show the
same for the next-nearest and next-next-nearest neighbors, respectively. Plot
(a) corresponds to $N=4$, and plot (b) to $N=6$.

Fig. 3 shows the plot of the logarithmic negativity $LN$ as a function of $B$
and in ground state for finite chains of sizes $N=4$ and $N=6$.

Figure 3: The logarithmic negativity $LN$ as a function of external magnetic
field $B$ and single-ion anisotropy $D$ in ground state for finite chain of
size $N=4$ (a) and $N=6$ (b).

We also found out the $T=0$ phase diagram in the $B-D$ plane at fixed value of
$J$, see Fig. 4 (with $J=1$). By inspection, for $N$ even, one finds two
curves separating the two phases having vanishing and non-vanishing
logarithmic negativity, to which we will refer as the entanglement ($LN\neq
0$) and non entanglement ($LN=0$) phases. The ground state of the system has a
wave function corresponding to the state with all spins down
($\Psi_{GS}=|\downarrow\downarrow....\downarrow\rangle$) in the non
entanglement region.

We have obtained the equations of these curves for $N=2$:

$B=4+D\hskip 14.22636pt\left(\text{for}\,\,D>-\frac{4}{3}\right),$ (17)
$B=\frac{1}{2}\left(3+D+\sqrt{D^{2}-2D+9}\right)\hskip
14.22636pt\left(\text{for}\,\,D<-\frac{4}{3}\right).$ (18)

The line (17) is found to be valid for any even $N$, while the second one,
given by equation (18), does depend on $N$, so that for $D<-\frac{4}{3}$ the
separatrix between the entanglement and non entanglement phases will depend on
$N$ as well. It is important to observe that on the line (17) the energy
density, i.e., the energy of the ground state divided by $N$, is also found to
be independent on $N$. So the independence on $N$ of the entanglement-non
entanglement separatrix line is ultimately connected (and due) to the fact
that the energy density is constant.

There is a third curve, starting from the corner point, and defined by

$B=-1+\sqrt{D^{2}-2D+9}.$ (19)

The area of entanglement between this curve and the straight line (17)
corresponds to the first nonzero plateau shown on the Fig. 3, as well as the
rightmost plateau on Fig. 1, and the leftmost one on Fig. 2. The equation (19)
depends on $N$. However, the intersection of the three curves, given by
$D=-\frac{4}{3}$ and $B=\frac{8}{3}$, is the same for all even values of $N$.

Figure 4: Ground-state phase diagram in the $B-D$ plane at fixed value.

A very interesting behavior of logarithmic negativity occurs on the first non-
zero plateau. At values of external magnetic field $B$ and single-ion
anisotropy $D$ determining this plateau, the ground state wave function is
defined follow:

$\Psi_{GS}=\frac{1}{\sqrt{N}}\sum_{p=1}^{N}(-1)^{p}|\overbrace{\underbrace{\downarrow...\downarrow
0}_{p}\downarrow...\downarrow}^{N}\rangle,$ (20)

where only one spin is zero ($|0\rangle$) on position $p$ and all the other
spins are down ($|\downarrow\rangle$). The logarithmic negativity $LN$ on this
plateau is determined by only single negative eigenvalue of
$\rho_{ab}^{T_{1}}$ (14). This unique property is violated in other regions
and also on the higher plateaus shown in Fig. 1. At variance the structures of
the ground state wave functions are more complex for odd $N$, although we may
expect that they have the structure previously discussed on the first non-zero
plateau.

##  IV Logarithmic negativity at low temperatures

We examine in this section the 1D antiferromagnetic spin-$1$ Heisenberg $XXX$
model with external magnetic field $B$ and fixed single-ion anisotropy $D$ on
the finite chain with sizes $N=4,5,6,7,8$ at low temperatures $T$. The
behavior of logarithmic negativity $LN$ as a function of $B$ for nearest,
next-nearest and next-next-nearest neighbors is displayed in Fig. 5, 6, 7 at
$T=0.1$ and $J=1$ for $D=-1,0,1$ respectively.

For finite low temperature $T$, the entanglement disappears in a special point
$B_{s}$. In contrast of the ground state where the critical point $B_{c}$ is
the same for all values of $N$, the value $B_{s}$ might depend on $N$.
Moreover $B_{s}>B_{c}$.

On the other hand, Fig. 5, 6, and 7 show that non-nearest neighbors
entanglement only appears after $B$ is larger than the other special point
$B_{e}$.For the Heisenberg model with spin $\frac{1}{2}$ $B_{e}=B_{E}$,
results for entanglement of next-nearest and next-next-nearest neighbors in
the ground state are unviersal [11]. In our case for the model with spin $1$,
the values of $B_{e}$ are different for entanglement of next-nearest and next-
next-nearest neighbors (see Fig. 5, 6, 7).

Figure 5: The logarithmic negativity $LN$ as a function of the external
magnetic field $B$ at $T=0.1$ with fixed $D=-1$. The upper curve shows $LN$
for nearest neighbors, the middle and lowest curves the same for the next-
nearest and next-next-nearest neighbors, respectively. Plot (a) corresponds to
the finite chain of size $N=6$, plot (b) to $N=8$. Figure 6: The same as Fig.
5, but with fixed $D=0$. Figure 7: The same as Fig. 5, but with fixed $D=1$.
Figure 8: The logarithmic negativity $LN$ as a function of the external
magnetic field $B$ and single-ion anisotropy $D$ at $T=0.1$. Plot (a)
corresponds to the finite chain of size $N=5$, plot (b) to $N=7$. Figure 9:
The logarithmic negativity $LN$ as a function of the external magnetic field
$B$ and single-ion anisotropy $D$ at $T=0.1$ for a finite chain of size $N=6$.

As we can see from Fig. 8, the behavior of logarithmic negativity $LN$ is as
expected qualitatively similar for chains of sizes $N=5,7$ and different for
the chain of size $N=6$ (see Fig. 9). We do not provide results here for other
even sizes $N=4$ and $N=8$, but they are qualitatively similar to $N=6$.

Now we will consider the behavior of the logarithmic negativity $LN$ of the 1D
antiferromagnetic spin $1$ Heisenberg $XXX$ model as a function of the single-
ion anisotropy parameter $D$ with fixed external magnetic $B$. The Fig. 10
shows the dependence of the entanglement $LN$ of the nearest neighbors, next-
nearest and next-next-nearest neighbors on $D$ with $T=0.1$ and $B=4$ for
finite chains of sizes $N=4,5,6,7,8$. Again we can see from Fig. 10 the
behavior of LN is qualitatively similar for chains of even sizes and different
for chains of odd sizes.

There is another special point $D_{s}$ starting from which entanglement exist.
point $D_{s}$ is the same for the entanglement of the nearest neighbors and
for the non nearest neighbors. The value of $D_{s}$ is found to be weakly
dependent on $N$ (see Fig. 10). We have tested this property for various
values of external magnetic fixed $B$ at low temperatures.

Figure 10: The logarithmic negativity $LN$ is plotted as a function of the
single-ion anisotropy parameter $D$ for $T=0.1$ and $B=4$. The upper curve
shows $LN$ for nearest neighbors, the middle and lowest curves show the same
for the next-nearest and next-next-nearest neighbors, respectively. Plot (a)
corresponds to the finite chain of size $N=4$, (b) to $N=6$, (c) to $N=8$, (d)
to $N=5$, and plot (e) to $N=7$.

Let discuss now the properties of logarithmic negativity $LN$ as function of
the temperature $T$ for an external magnetic field slightly larger than
$B_{s}$ and at a fixed fixed single-ion anisotropy, for the case of nearest
neighbors. In Fig. 11 we plot the dependence of $LN$ on $T$ for $N=4$ $-$ $8$
and at fixed single-ion anisotropy ($D=-1,0,1$). The figure shows that $LN$
for even $N$ decrease, while for odd $N$ states increases with $N$.

Figure 11: The nearest-neighbors logarithmic negativity $LN$ as a function of
$T$ for various values of $N$ (from top to bottom, $N=4$, $N=6$, $N=8$, $N=7$
and $N=5$) at (a) $B=3.2$, $D=-1$; (b) $B=4.2$, $D=0$; (c) $B=5.2$, $D=1$.

##  V Conclusion

The study of logarithmic negativity $LN$ behaviour for nearest and non-nearest
neighbors in quatum spin systems is a rich and active field of research. We
have investigated here the 1D antiferromagnetic spin-$1$ Heisenberg $XXX$
model with external magnetic field $B$ and single-ion anisotropy $D$. We first
studied the logarithmic negativity for nearest and non-nearest neighbors on
the finite chain with sizes $N=4,6$ in the ground state. Critical points
$B_{c}$ and $D_{c}$ are also found, at which the entanglement measure
disappears at zero temperature. The phase diagram is presented in the $B-D$
plane, where the entanglement and non-entanglement phases are separated and a
specific triple point is demonstrated. In the ground state, plateaus of
logarithmic negativity $LN$ for sizes $N=4,6$ are plotted as a function of $B$
and $D$. The wave function corresponding to first non-zero plateau for all
even $N$ is found. It would be interesting as future work to study the ground
state wave function for odd $N$.

A discussion of the behavior of logarithmic negativity $LN$ on finite chains
with sizes $N=4-8$ for nearest, next-nearest and next-next-nearest neighbors
as a function of $B$ and $D$ is presented at low temperatures. The
entanglement disappears at the special point $B_{s}$. The latter is larger
than the critical point $B_{c}$ in the ground state and might depend on $N$.
We also discuss the properties of the logarithmic negativity $LN$ as a
function of temperature $T$ at an external magnetic field close to $B_{s}$,
and for a fixed single-ion anisotropy. The nearest-neighbor logarithmic
negativity increases from zero temperature to $T=1.4$ and reaches a maximum,
which as an example is less than $0.035$ for $B=3.2$, $D=-1$; $B=4.2$, $D=0$;
$B=5.2$, $D=1$ for sizes $N=4,6,8,7,5$. We have briefly mentioned experimental
applications. The theoretical results obtained from studying the behavior of
logarithmic negativity $LN$ for nearest and non-nearest neighbors at low
temperatures may allow, in the near future, the experimental confirmation of
interesting effects like the entanglement disappearance in the special point
for the external magnetic field $B_{s}$ and single-ion anisotropy $D_{s}$ for
a spin-$1$ antiferromagnetic polymer [24].

##  VI Acknowledgments

N.A. acknowledge the receipt of the grant in the frame of the research
projects No.SCS 21AG-1C006 and No.SCS 19IT-008. N.A. and A.T. acknowledge
support from the CNR/MESRA project “Statistical Physics of Classical and
Quantum Non Local Hamiltonians: Phase Diagrams and Renormalization Group”.

## References

  * [1] L. Amico, R. Fazio, A. Osterloh, and V. Vedral, Entanglement in Many-Body Systems, Rev. Mod. Phys. 80 (2008) 517, and references therein.
  * [2] S. Sachdev, Quantum Phase Transitions, Cambridge University Press, Cambridge, 1999.
  * [3] U. Glaser, H. Büttner, and H. Fehske, Entanglement and correlation in anisotropic quantum spin systems, Phys. Rev. A 68 (2003) 032318.
  * [4] M. Wieśniak, V. Vedral and Č. Brukner, Magnetic susceptibility as a macroscopic entanglement witness, New J. Phys. 7 (2005) 258.
  * [5] H. Kikuchi, Y. Fujii, M. Chiba et al., Experimental Observation of the $1/3$ Magnetization Plateau in the Diamond-Chain Compound $Cu_{3}(CO_{3})_{2}(OH)_{2}$, Phys. Rev. Lett. 94 (2005) 227201.
  * [6] K. C. Rule, A. U. B. Wolter, S. Süllow et al., Nature of the Spin Dynamics and $1/3$ Magnetization Plateau in Azurite, Phys. Rev. Lett. 100 (2008) 117202.
  * [7] F. Aimo, S. Krämer, M. Klanjšek et al., Spin Configuration in the $1/3$ Magnetization Plateau of Azurite Determined by NMR, Phys. Rev. Lett. 102 (2009) 127205.
  * [8] H. Jeschke, I. Opahle, H. Kandpal et al., Multi-step approach to microscopic models for frustrated quantum magnets – the case of the natural mineral azurite, Phys. Rev. Lett. 106 (2011) 217201.
  * [9] O. Rojas, M Rojas, N. S. Ananikian, and S. M. de Souza, Thermal entanglement in an exactly solvable Ising-XXZ diamond chain structure, Phys. Rev. A 86 (2012) 042330.
  * [10] N. Ananikian, H. Lazaryan, and M. Nalbandyan, Magnetic and quantum entanglement properties of the distorted diamond chain model for azurite, Eur. Phys. J. B 85 (2012) 223.
  * [11] M. C. Arnesen, S. Bose, and V. Vedral, Natural Thermal and Magnetic Entanglement in the 1D Heisenberg Model, Phys. Rev. Lett. 87 (2001) 017901.
  * [12] V. S. Abgaryan, N. S. Ananikian, L. N. Ananikyan, and A. N. Kocharian, Phase transitions and entanglement properties in spin-$1$ Heisenberg clusters with single ion anisotropy, Phys. Scr. 83 (2011) 055702\.
  * [13] H. Arian Zad, R. Kenna, and N. Ananikian, Magnetic and thermodynamic properties of the octanuclear nickel phosphonate-based cage, Physica A 538 (2020) 122841.
  * [14] J. A. Sheikh, A. Adhikary, H. S. Jena, S. Biswas, and S. Konar, High Nuclearity (Octa, Dodeca, and Pentadecanuclear) Metal (M = CoII, NiII) Phosphonate Cages: Synthesis, Structure, and Magnetic Behavior, Org. Chem. 53 (2014) 1606.
  * [15] J. A. Sheikh, H. S. Jena, A. Clearfield, and S. Konar, Phosphonate Based High Nuclearity Magnetic Cages, Acc. Chem. Res. 49 (2016) 1093.
  * [16] S. Konar, P. S. Mukherjee, E. Zangrando, F. Lloret, and N. R. Chaudhuri, A Three-Dimensional Homometallic Molecular Ferrimagnet, Angew. Chem. 114 (2002) 1631.
  * [17] V.S. Abgaryan, N.S. Ananikian, L.N. Ananikyan, and V. Hovhannisyan, Quantum transitions, magnetization and thermal entanglement of the spin-$1$ Ising-Heisenberg diamond chain, Solid State Commun. 224 (2015) 15.
  * [18] V. Hovhannisyan, J. Strecka, and N. Ananikian, Exactly solvable spin-$1$ Ising-Heisenberg diamond chain with the second-neighbor interaction between nodal spins, J. Phys.: Condens. Matter 28 (2016) 085401.
  * [19] N. Ananikian, R. Artuso, and H. Poghosyan, Superstable cycles and magnetization plateaus for antiferromagnetic spin-$1$ Ising and Ising–Heisenberg models on diamond chains, Physica A 503 (2018) 892.
  * [20] N. Ananikian, Č. Burdik, L. Ananikyan, H. Poghosyan, Magnetization Plateaus and Thermal Entanglement of Spin Systems, J. Phys.: Conf. Ser. 804 (2017) 012002.
  * [21] H. Arian Zad and N. Ananikian, Enhanced magnetocaloric effect in a mixed spin-($1/2$, $1$) Ising–Heisenberg two-leg ladder with strong–rung interaction, Eur. Phys. J. Plus 136 (2021) 597.
  * [22] A. Ghannadan and J.Strečka, Magnetic-Field-Orientation Dependent Thermal Entanglement of a Spin-$1$ Heisenberg Dimer: The Case Study of Dinuclear Nickel Complex with an Uniaxial Single-Ion Anisotropy, Molecules 26 (2021) 3420.
  * [23] A. Escuer, R. Vicente, J. Ribas, J. Jaud, and B. Raynaud, Octahedral $\mu$-oxalato-nickel(II) dinuclear complexes with water and tridentate amines as blocking ligands: Magnetostructural correlations, Inorg. Chim. Acta 216 (1994) 139.
  * [24] M. Orendáč, A. Orendáčová, J. Černák, A. Feher, P. J. C. Signore, M. W. Meisel, S. Merah, and M. Verdaguer, Thermodynamic and magnetic properties of the $S=1$ Heisenberg chain $Ni[C_{2}H_{8}N_{2}]_{2}Ni[CN]_{4}$: Experiments and theory, Phys. Rev. B 52 (1995) 3435.
  * [25] G. Vidal and R. F. Werner, Computable measure of entanglement, Phys. Rev. A 65 (2002) 032314.
  * [26] X. Wang, H.-B. Li, Z. Sun, and Y.-Q. Li, Entanglement in spin-$1$ Heisenberg chains, J. Phys. A 38 (2005) 8703.
  * [27] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81 (2009) 865.
  * [28] H. Wang, C. Xiang, The Scaling of Entanglement Entropy for One Spatial XXZ Spin Chain, JAMP 4 (2016) 48.
  * [29] G.-H. Liu, L. Qiang, and G.-S. Tian, Entanglement spectrum and magnetization plateaus in an $S=1$ bond-alternative Heisenberg chain with single-ion anisotropy and magnetic field, Eur. Phys. J. B 86 (2013) 321.
  * [30] G.-H. Liu, W. Li, W.-L. You, G.-Sh. Tian, and G. Su, Matrix product state and quantum phase transitions in the one-dimensional extended quantum compass model, Phys. Rev. B 85 (2012) 184422.
  * [31] M. Srednicki, Entropy and area, Phys. Rev. Lett. 71 (1993) 666.
  * [32] P. Calabrese and J. Cardy, Entanglement entropy and quantum field theory, J. Stat. Mech. (2004) P06002.
  * [33] G. Gori, S. Paganelli, A. Sharma, P. Sodano, and A. Trombettoni, Explicit Hamiltonians inducing volume law for entanglement entropy in fermionic lattices, Phys. Rev. B 91 (2015) 245138 (pp 13).
  * [34] M. B. Plenio, Logarithmic negativity: A full entanglement monotone that is not convex, Phys. Rev. Lett. 95 (2005) 090503.
  * [35] Y. Javanmard, D. Trapin, S. Bera, J. H. Bardarson, and M. Heyl, Sharp entanglement thresholds in the logarithmic negativity of disjoint blocks in the transverse-field Ising chain, New J. Phys. 20 (2018) 083032.
  * [36] Y. Khedif and M. Daoud, Thermal quantum correlations in the two-qubit Heisenberg XYZ spin chain with Dzyaloshinskii–Moriya interaction, Mod. Phys. Lett. A 36 (2021) 2150074.
  * [37] P. Ruggiero, V. Alba, and P. Calabrese, Entanglement negativity in random spin chains, Phys. Rev. B 94 (2016) 035152.
  * [38] F. Benabdahand and M. Daoud, Dynamics of quantum discord based on linear entropy and negativity of qutrit-qubit system under classical dephasing environments, Eur. Phys. J. D 75 (2021) 231.


# Reconfigurable Heterogeneous Parallel Island Models

Lucas A. da Silveira†, Thaynara A. de Lima‡ and Mauricio Ayala-Rincón†
†Department of Computer Science, Universidade de Brasília, 70900–010 Brasília
D.F., Brazil
‡Institute of Mathematics and Statistics, Universidade Federal de Goiás —
Campus II, 74690–900 Goiânia, Brazil

###### Abstract

Heterogeneous Parallel Island Models (HePIMs) run different bio-inspired
algorithms (BAs) in their islands. From a variety of communication topologies
and migration policies fine-tuned for homogeneous PIMs (HoPIMs), which run the
same BA in all their islands, previous work introduced HePIMs that provided
competitive quality solutions regarding the best-adapted BA in HoPIMs. This
work goes a step forward, maintaining the population diversity provided by
HePIMs, and increasing their flexibility, allowing BA reconfiguration on
islands during execution: according to their performance, islands may
substitute their BAs dynamically during the evolutionary process. Experiments
with the introduced architectures (RecHePIMs) were applied to the NP-hard
problem of sorting permutations by reversals, using four different BAs,
namely, simple Genetic Algorithm (GA), Double-point crossover Genetic
Algorithm (GAD), Differential Evolution (DE), and self-adjusting Particle
Swarm Optimization (PSO). The results showed that the new reconfigurable
heterogeneous models compute better quality solutions than the HePIMs closing
the gap with the HoPIM running the best-adapted BA.

##  I Introduction

Evolutionary computing relies on the evolution of candidate solutions over a
finite number of generations to obtain accurate solutions for complex
optimization problems. Genetic Algorithms (GAs) and Particle Swarm
Optimization (PSO), among other Bio-inspired algorithms (BAs), have been
applied to successfully solve a diversity of such problems applied in
engineering and sciences. BAs guide the evolution of a population of
individuals (candidate solutions) to improve their fitness to achieve a
feasible solution to the target problem. BAs apply specialized computational
rules to promote individual information exchange to the benefit of the
population. However, optimization through such BA approaches demands
exhaustive computations and efficient resources. Parallelization is one of the
natural mechanisms applied to speed up and improve the accuracy of solutions
obtained by BAs.

This work studies Parallel Island Models (PIMs) that partition the population
among their islands (processors) and simultaneously run a BA in each island.
In addition to the exchange of individuals, PIMs promote migration between
islands. When all islands run the same BA, such models are called homogeneous
PIMs (HoPIMs). This work improves heterogeneous PIMs (HePIMs) [1], in which
islands may run different BAs, allowing algorithmic reconfiguration on their
islands, i.e., islands may dynamically update their BAs. In addition to an
adequate and well-calibrated migration policy required by HePIMs,
reconfigurable HePIMs exchange information between islands to decide how
islands should reconfigure their BAs.

Silveira et al. [1] introduced reconfigurable HePIMs running four different
BAs in their islands, namely, Genetic Algorithm (GA), double-point crossover
GA (GAD), Differential Evolution (DE), and self-adjusting Particle Swarm
Optimization (PSO) (see e.g., [2], [3], and [4]). PIMs performance depends on
a good calibration of the breeding cycle parameters (related to the involved
BA) and, in addition to vital aspects of the parallel island architecture as
island communication synchronism, island migration frequency, communication
topology, and migration policy. We select two successful asynchronous HePIMs
from [1] maintaining their parameters and adding the reconfiguration
frequency.

The new reconfigurable HePIMs are tested in solving the unsigned reversal
distance problem (URD), an ${\cal NP}$-hard problem ([5]). Approaches to solve
URD are applied in combinatorics to explain algebraic aspects of permutations
([6]) and, in genomics, to analyze the evolutionary distance between genomes
([7]), also represented as permutations.

Main contributions. We design new reconfigurable HePIMs that run GA, GAD, DE,
and PSO in their islands using two successful asynchronous topologies from
[1]. Non-reconfigurable HePIMs computed competitive solutions regarding most
HoPIMs. The new reconfigurable architectures showed promising results
computing solutions that exceed the quality of pure HePIMs and are very
competitive regarding the best adapted HoPIMs, namely, the ones that run DE in
all their islands. The heterogeneity of the new model effectively shares,
through the migration policy, the good results experimented by individuals
guided by different BAs in each island to the whole architecture. Furthermore,
the reconfiguration ability shares the good experiences of the BAs in each
island of the model. Adding the reconfiguration capability, the new model
exceeds the flexibility of HoPIMs (all islands may update their BA to a unique
BA) and of HePIMs (reconfiguration may update island BAs to the fix
configuration of any non-reconfigurable HePIM)

Organization. Sec. II discusses PIMs, the unsigned reversal distance problem,
and the four selected BAs: GA, GAD, DE, and PSO. Sec. III introduces the new
reconfigurable HePIMs explaining how different BAs are reconfigured. Then,
Sec. IV presents experiments and discusses accuracy results and statistical
analysis. Finally, Sec. V present related work before Sec. VI that concludes
and discussed future work. Source and data used in the experiments are
available at http://genoma.cic.unb.br.

##  II Background

###  II-A Parallel island model (PIM)

PIMs were proposed initially for GAs [8] and, besides improving speed-up, it
is expected that such models also boost the solutions provided by sequential
GA.

The population is distributed into islands whose number is determined by the
developer, running their BAs in parallel. The connection between the islands
establishes the model’s topology. Static PIMs maintain the connections fixed
during the execution, whereas dynamic models admit changes during the process.
Linked islands exchange individuals to evolve. Such a transfer can be uni- or
bi-directionally. Different topologies and strategies to implement them are
available (e.g. [9, 10, 11]). Homogeneous PIMs execute the same BA in all
islands, whereas heterogeneous models admit different BAs running in their
islands. Figure 2 illustrates an heterogeneous static bi-directional tree
topology. The edges show the connections between islands and remain unchanged,
while vertices represent the islands with their BAs.

A migration policy guides the exchange of individuals between islands during
the evolutionary process. PIMs have breeding-cycle and migration parameters
tuned to improve the quality of solutions. In the following, the migration
parameters are briefly presented. Some of them consider the classification of
individuals as best, worst and random, based on a rank established according
to their fitness. The first half corresponds to the best and the second to the
worst individuals, whereas random individuals are selected randomly.

  * •

Individuals number (IN): number of individuals emigrating from each island.

  * •

Emigrant Individuals (EMI): rule the type of individuals selected for
emigration among: 1\. best, 2. worst, and 3. random.

  * •

Immigrant Individuals (IMI): determines the type of individuals in the target
island replaced by immigrants among: 1\. worst, 2. random, and 3. similar.
Similar individuals have the same classification as their replacement
immigrants according to the fitness rank.

  * •

Emigration Policy (EP): defines whether individuals are cloned or removed in
the local island when they emigrate to the target island.

  * •

Migration Interval (MI): corresponds to a percentage of iterations of the
evolutionary process, called generations, after which the migration process is
redone. Each island separately evolves its population by
$\textit{MI}\times\textit{maxIt}$ generations, where maxIt is the total number
of iterations performed by each BA.

PIMs are classified according to the synchroneity in which islands evolve
their population. In Synchronous PIMs, islands evolve performing each
generation simultaneously, whereas, in asynchronous PIMs, islands evolve
independently even during migration. The latest mimics the behavior found in
nature.

Here, we introduce reconfigurable heterogeneous PIMs. First, at a fixed
generation percentage, called Reconfiguration Frequency (RF), it is checked
what islands have the best and the worst solutions regarding a metric based on
the fitness average and the variance of the population. Then, the worst island
updates its BA to the BA applied by the best island.

###  II-B Case-study

The evolutionary distance between two organisms can be computed as the number
of rearrangements needed to transform a genome into another one by using some
evolutionary measure. The authors consider the minimum number of reversals to
compute the distance between unichromosomal organisms in this work.

Permutations on $\\{1,\cdots,n\\}$ represent a genome containing $n$ genes.
Given a genome $\pi=(\pi_{1},\pi_{2},...,\pi_{n})$, where $1\leq i,\pi_{i}\leq
n$, a reversal $\rho^{j,k}$, for $1\leq j\leq k\leq n$, transforms $\pi$ into
$\pi^{\prime}=(\cdots,\pi_{j-1},\pi_{k},\cdots,\pi_{j},\pi_{k+1},\cdots)$,
that is, it inverts the elements between $\pi_{j}$ and $\pi_{k}$. If the
orientation of the genes is known, each one receives a positive or negative
sign, and the genome is a signed permutation. There are two evolutionary
problems related to computing the distance by reversals. The signed reversal
distance (SRD) problem asks for the minimum number of reversals needed to
transform a signed permutation into another. On the other hand, the unsigned
reversal distance (URD) problem consists of computing such a number between
unsigned permutations, which orientation of genes is unknown. It is well-known
that SRD belongs to class $\cal P$ [12], whereas URD is an ${\cal NP}$-hard
problem [5].

Our models are applied to solve URD. The fitness used by the algorithms is
computed over signed permutations, generated after a random assignment of
signs to each gene of a permutation.

###  II-C Local Evolutionary Engines — bio-inspired Algorithms

Four BAs, widely used for analyzing optimization problems and having distinct
adaptability characteristics are applied.

  * •

Simple Genetic Algorithm (GA): to evolve local population, GA considers a
breeding cycle where the best parents are selected and produce offspring by
applying one-point crossover (Fig. 1 (a)). Then, the descendants replace the
worst individuals in the current population. The breeding cycle relies on four
parameters, namely, the percentages of selection and replacement, and the
probability of application of mutation and crossover. GA was developed by J.
H. Holland in the 1970s [2].

  * •

Double-point Crossover Genetic Algorithm (GAD): it has a similar behavior than
GA except by the technique to promote crossover, illustrated in Fig. 1 (b),
and how the local population evolves: in contrast with GA descendants replace
individuals randomly selected in GAD.

  * •

Differential Evolution (DE): it was proposed by Storn and Price [3], and is a
method to optimize functions over the real multidimensional space
$\mathbb{R}^{n}$. We adapt the algorithm by restricting the domain of the
function as the set of permutations. Two main parameters guide the
evolutionary process: the mutation factor $F_{M}$, applied to individuals
randomly selected from the population to generate mutants, and the probability
of crossover $P_{C}$. The local population evolves by replacing individuals
having the worst fitness with mutants.

  * •

Self-adjusting Particle Swarm Optimization (PSO): it was introduced by
Eberhart and Kennedy [4] and is based on the behavior of social organisms in
groups. Originally, PSO was developed to optimize continuous functions from
particles’ velocity and position in an $n$-dimensional space. At each
iteration, the vector representing a particle velocity is built from the best
positions of such a particle and all particles, the velocity of the particle
in the previous iteration, the individual and global acceleration (that
influence the distance a particle can cover), and the weight of inertia
(momentum). In this paper, we use the PSO proposed in [13], which is self-
adaptive since momentum and the individual and global acceleration
coefficients are self-tuning during the search process.

To adapt PSO and DE to URD, to each $n$-dimensional real vector $v$ randomly
generated is associated a signed permutation constructed from the unsigned
permutation $\pi=(\pi_{1},\ldots,\pi_{n})$ gave as input: if the $i-$th entry
of $v$ belongs to the interval $[0,0.5)$ then $\pi_{i}$ receives a negative
orientation; case such a coordinate is in $[0.5,1]$ then $\pi$ is assigned
positively. However, if the continuous vector representation has an entry
outside of the interval $[0,1]$, a correct orientation is randomly generated.
For GA and GAD, the orientation of the genes in each individual is randomly
generated as $\pm 1$. After the transformation of an unsigned to signed
permutations, the linear algorithm to solve the SRD problem, proposed by Bader
_et al._ [14], computes the fitness of each particle/individual.

$\begin{array}[]{c}\mbox{(a) One-point crossover}\\\\[5.69054pt]
\begin{array}[]{c}\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil 1\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&2\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&3\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&4\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&5\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&6\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&7\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&8\hfil\hskip 2.84526pt\\\ \hline\cr\end{array}\\\\[5.69054pt]
{\color[rgb]{0,1,1}\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil 5\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&8\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&6\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&4\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&3\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&1\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&2\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&7\hfil\hskip 2.84526pt\\\
\hline\cr\end{array}}\end{array}{\color[rgb]{0,0,1}\huge\leadsto}\begin{array}[]{c}\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil 1\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&2\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&3\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}4}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}3}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}1}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}2}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}7}\hfil\hskip 2.84526pt\\\
\hline\cr\end{array}\\\\[2.84526pt]
\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil{\color[rgb]{0,1,1}5}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}8}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}6}\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&4\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&5\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&6\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&7\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&8\hfil\hskip 2.84526pt\\\
\hline\cr\end{array}\end{array}\end{array}$

$\begin{array}[]{c}\mbox{(b) Double-point crossover}\\\\[5.69054pt]
\begin{array}[]{c}\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil 1\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&2\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&3\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&4\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&5\hfil\hskip 2.84526pt\vrule\vrule\hskip 2.84526pt&6\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&7\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&8\hfil\hskip 2.84526pt\\\ \hline\cr\end{array}\\\\[5.69054pt]
{\color[rgb]{0,1,1}\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil 5\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&8\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&6\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&4\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&3\hfil\hskip 2.84526pt\vrule\vrule\hskip 2.84526pt&1\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&2\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&7\hfil\hskip 2.84526pt\\\
\hline\cr\end{array}}\end{array}{\color[rgb]{0,0,1}\huge\leadsto}\begin{array}[]{c}\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil 1\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&2\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&3\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}4}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}3}\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&6\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&7\hfil\hskip 2.84526pt\vrule\hskip 2.84526pt&8\hfil\hskip
2.84526pt\\\ \hline\cr\end{array}\\\\[2.84526pt]
\begin{array}[]{|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}||@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}|}\hline\cr\hskip
2.84526pt\lx@intercol\hfil{\color[rgb]{0,1,1}5}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}8}\hfil\hskip
2.84526pt\vrule\hskip 2.84526pt&{\color[rgb]{0,1,1}6}\hfil\hskip
2.84526pt\vrule\vrule\hskip 2.84526pt&4\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&5\hfil\hskip 2.84526pt\vrule\vrule\hskip
2.84526pt&{\color[rgb]{0,1,1}1}\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&{\color[rgb]{0,1,1}2}\hfil\hskip 2.84526pt\vrule\hskip
2.84526pt&{\color[rgb]{0,1,1}7}\hfil\hskip 2.84526pt\\\
\hline\cr\end{array}\end{array}\end{array}$

Figure 1: One-point and double-point crossing operators.

##  III Communication Topologies

We select a static and a dynamic topology that successfully addressed URD in
[10] for homogeneous PIMs and in [1] for non reconfigurable heterogeneous
PIMs. We choose asynchronous models since the dynamic asynchronous HePIM was
the one that provided the best results.

The static topology is a 12-island bi-directional binary tree (tree to the
left in Figure 2), and the dynamic topology is the 12-island complete graph
(graph to the left in Figure 3). In the complete graph topology all pairs of
islands may exchange individuals. The island communication dynamism is
acquired by exploring diversity and quality into each island, given by fitness
variance and average metrics. Variance measures islands’ diversity: high
variance represents high individuals’ diversity, improving the chances of
evolution into islands. Fitness average measures the quality of island
populations. According to such metrics, the islands are ranked as good, bad,
and medium. Migrations exchange individuals between good and bad islands, and
medium and medium islands only (for short, gbmm). Reconfiguration uses the
same metric to update the BA executed by islands, according to the best
performance experienced by other islands. So, reconfigurable HePIMs perform
migration and updating of BAs at some intervals during their evolution.

The models introduced in this paper are ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny Tr12A}}$ and ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny gbmm12A}}$. The former one uses the static tree topology
and the latter one the dynamic complete graph topology. Both topologies are
asynchronous and evolve through a refined migration policy that allows
exchange of individuals maintaining diversity of the model, and furthermore,
through the new feature of dynamic reconfiguration that allows updating the
BAs executed in their islands, improving in this manner the performance of the
island model. Reconfiguration cycles for ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny Tr12A}}$ and ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny gbmm12A}}$are illustrated in Figures 2 and 3,
respectively.

Figure 2: Example of reconfiguration in the static binary tree topology. Red
dotted nodes represent islands that have undergone current reconfiguration,
while black dotted nodes label islands that have undergone reconfiguration in
previous cycles. Figure 3: Example of reconfiguration in the dynamic complete
graph topology. Red dotted nodes represent islands that have undergone current
reconfiguration, while black dotted nodes label islands that have undergone
reconfiguration in previous cycles.

##  IV Experiments and analysis of accuracy

As in [1], all PIMs, including the new reconfigurable models were implemented
using the MPI library of C in Linux, and for the sake of comparison,
experiments were executed on a computational platform using two Xeon E5-2620
2.4 GHz six core processors with hyper-threading.

The basis to compare the performance of PIMs, are sequential versions of GA,
GAD, DE and PSO with populations of size $24n\log n$ and breeding cycles fixed
as $n$. Also, we select eight 12-island asynchronous HoPIMs, designed in [10],
running exclusively one of the BAs: GA, GAD, DE or PSO. Furthermore, we select
two asynchronous HePIMs designed in [1]. The homogeneous models are ${\cal
P}^{\mbox{{GA}}}_{\mbox{\tiny Tr12A}}$, ${\cal P}^{\mbox{{GAD}}}_{\mbox{\tiny
Tr12A}}$, ${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$, ${\cal
P}^{\mbox{{PSO}}}_{\mbox{\tiny Tr12A}}$, ${\cal P}^{\mbox{{GA}}}_{\mbox{\tiny
gbmm12A}}$, ${\cal P}^{\mbox{{GAD}}}_{\mbox{\tiny gbmm12A}}$, ${\cal
P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$, and ${\cal
P}^{\mbox{{PSO}}}_{\mbox{\tiny gbmm12A}}$. The superscripts denote the BA used
by the homogeneous model; the subscript prefixes, whether the model use the
static tree (Tr) or the dynamic complete graph topology (gbmm); and, the
subscript suffix 12A indicates the number of islands and that the model is
asynchronous. From [1], we select the heterogeneous PIMs ${\cal
P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ and ${\cal P}^{\mbox{\tiny
Het}}_{\mbox{\tiny gbmm12A}}$, being the latter one the HePIM that provided
the best quality results.

###  IV-A Parameter Setup

The parameters for BAs, HoPIMs and non-reconfigurable HePIMs obtained in [1]
were used. The _parameter tuning_ adopted the “taxonomy T1” in [15]. Table I
presents the parameter ranges. For percentages, the tested values range
between $2\%$ and $100\%$. For probabilities, the values range from $0.02$ to
$1.0$, and for the mutation parameter from $0.01$ to $0.02$. For DE, the
$F_{M}$ parameter ranges from $1\%$ to $2\%$ since values above $2\%$ degrade
the quality of solutions. For PSO, the parameters to guide the particles in
the search space are self-adjusting.

The setup tested BAs, HoPIMs and HePIMs over packages of twenty $n$-gene
permutations, $n\in\\{50,60,\ldots,140,150\\}$. All parameters reference
values were evaluated and those that provided the best solutions selected (see
Tables II and III). HePIMs use the same evolutionary parameters than HoPIMs,
and only migration parameters were calibrated. Reconfigurable HePIMs add
reconfiguration frequency to the associated HePIMs (see Table IV).

TABLE I: Estimated Values for the Parameters | Parameter | Estimated values
---|---|---
GA and GAD | crossover | $0.02,0.04,\cdots,0.98,1.0$
mutation | $0.01,0.011,\cdots,0.019,0.02$
selection | $2\%,4\%,\cdots,98\%,100\%$
replacement | $2\%,4\%,\cdots,98\%,100\%$
DE | $P_{C}$ | $0.02,0.04,\cdots,0.98,1.0$
$F_{M}$ | $1\%,1.1\%,\cdots,1.9\%,2\%$
Migration | IN | 1,2,3,4,5,6,7,8,9,10,11,12,13
EMI | 1=Best, 2=Worst, 3=Random
EP | 1=Clone, 2=Remove
IMI | 1=Worst, 2=Random, 3=Similar
MI | $2\%,4\%,\cdots,98\%,100\%$
TABLE II: Parameter Settings for GA, GAD, and associated HoPIMs. |  | ${\cal P}^{\mbox{{GA}}}$ |  | ${\cal P}^{\mbox{{GAD}}}$
---|---|---|---|---
Parameter | GA | Tr12A | gbmm12A | GAD | Tr12A | gbmm12A
crossover | $.90$ | $.98$ | $.96$ | $.92$ | $.98$ | $.98$
mutation | $.02$ | $.015$ | $.011$ | $.01$ | $.01$ | $.01$
selection | $60\%$ | $92\%$ | $94\%$ | $98\%$ | $98\%$ | $94\%$
replacement | $60\%$ | $70\%$ | $70\%$ | $90\%$ | $80\%$ | $90\%$
IN |  | 9 | 5 |  | 12 | 5
EMI |  | 1 | 1 |  | 1 | 1
EP |  | 2 | 2 |  | 2 | 1
IMI |  | 1 | 1 |  | 1 | 1
MI |  | $30\%$ | $30\%$ |  | $14\%$ | $12\%$
TABLE III: Parameter Settings for DE, PSO, and associated HoPIMs. |  | ${\cal P}^{\mbox{{DE}}}$ | ${\cal P}^{\mbox{{PSO}}}$
---|---|---|---
Parameter | DE | Tr12A | gbmm12A | Tr12A | gbmm12A
$P_{C}$ | $.74$ | $.72$ | $.78$ |  |
$F_{M}$ | $1\%$ | $1.4\%$ | $1\%$ |  |
IN |  | 3 | 5 | 6 | 5
EMI |  | 1 | 1 | 3 | 3
EP |  | 1 | 2 | 2 | 2
IMI |  | 1 | 1 | 1 | 2
MI |  | $14\%$ | $12\%$ | $12\%$ | $22\%$
TABLE IV: Parameter Settings for HePIMs. Parameter | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12S}}$ | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$
---|---|---|---|---
IN | 3 | 3 | 6 | 6
EMI | 1 | 1 | 3 | 3
EP | 2 | 2 | 1 | 1
IMI | 3 | 3 | 3 | 3
MI | $10\%$ | $10\%$ | $14\%$ | $14\%$
RF |  | 14% |  | 24%

###  IV-B Analysis of Accuracy

HePIMs use parameters taken from Tables II, III and IV according to the
parameter setting obtained in [1]. In addition, the new reconfigurable HePIMs
performed reconfigurations after each 14% and 24% generations, giving a total
of seven and four reconfiguration cycles, respectively, for the static tree
and dynamic complete graph topologies.

For each permutation size, $n\in\\{100,110,\ldots,150\\}$, one package of one
hundred unsigned permutations with $n$ genes was randomly generated. All PIMs
were executed ten times using each one of the $n$ permutations of size $n$,
and the average of these executions for each permutation is taken as the
result. The average gives the computed number of reversals for each unsigned
permutation.

The accuracies of non- and reconfigurable HePIMs are compared. The radar chart
in Fig. 4, from previous experiments, shows that DE is the best adapted BA for
the URD problem [1]. In contrast, PSO provided the worst results, while GA and
GAD, in this order, gave competitive results. The six radii of the chart
represent the accuracy for inputs of size $100,110$ to $150$. The ranges and
scales in each radius of the radar chart are adjusted for the sake of
presentation.

PIMs with the tree and the complete graph topologies outperformed, as
expected, their sequential versions [1]. The radar charts to the left in Figs.
5 and 6 show that the HoPIMs maintained the order of competitivity of their
best and worst adapted BAs: the best quality solutions were obtained by ${\cal
P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$and the worst by ${\cal
P}^{\mbox{{PSO}}}_{\mbox{\tiny Tr12A}}$ for the static tree model, while for
the dynamic complete graph topology, the best solutions were computed by
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ and the worst by ${\cal
P}^{\mbox{{PSO}}}_{\mbox{\tiny gbmm12A}}$. In contrast to the fact that GAD
provided better accuracy than GA, the homogeneous models ${\cal
P}^{\mbox{{GA}}}_{\mbox{\tiny Tr12A}}$ and ${\cal
P}^{\mbox{{GA}}}_{\mbox{\tiny gbmm12A}}$ respectively outperformed ${\cal
P}^{\mbox{{GAD}}}_{\mbox{\tiny Tr12A}}$ and ${\cal
P}^{\mbox{{GAD}}}_{\mbox{\tiny gbmm12A}}$.

Table V exemplify the final island configuration. We ran ${\cal
P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$and ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny gbmm12A}}$ over one hundred entries of size 100 and
computed the average of the final distribution of the four BAs over the
islands. Surprisingly the proportion of islands running GA is dominant for
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ that can be explained
since the final average results of sets of islands with the same BA are very
similar for this model (see right chart on Fig. 5). On the other side, the
distribution BAs over islands for ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny
gbmm12A}}$ is better balanced (cf. right chart on Fig. 6).

Figure 4: Accuracy of the sequential BAs DE, GA, GAD and PSO.

Figs. 5 and 6 include the accuracy for the HePIMs ${\cal P}^{\mbox{\tiny
Het}}_{\mbox{\tiny Tr12A}}$ and ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny
gbmm12A}}$, respectively. The charts on the left show that the accuracy of
these models is very competitive regarding the HoPIMs with the same
architecture being only surpassed by ${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny
Tr12A}}$ and ${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$, respectively.
The charts on the right show (dashed lines) the best final average results
obtained by each set of three islands in the HePIMs (${\cal P}^{\mbox{\tiny
Het}}_{\mbox{\tiny Tr12A}}$, and ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny
gbmm12A}}$, respectively) that execute the same BA. These charts make it
evident that the migration policy and application of diverse BAs in the
islands of the heterogeneous architectures successfully propagates the results
obtained in all islands, but are not enough to outperform the quality of the
homogeneous model running the best adapted BA, ${\cal
P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ and ${\cal
P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$, respectively.

Performance of the new reconfigurable models is also included in Figs. 5 and
6. The reconfigurable HePIM ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny
Tr12A}}$ computed better quality results than the pure heterogeneous model
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$, and closed the gap between
this and the best adapted homogeneous architecture ${\cal
P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$, running DE (see radar chart on the
left in Fig. 5). It makes evident that adding the versatility of
reconfiguration to the heterogeneous PIMs may improve their performance. On
the other side, the reconfigurable HePIM ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny gbmm12A}}$ computed quality results that are
indistinguishable from the competitive ones computed by the non reconfigurable
heterogeneous model, ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$.

Figure 5: (a) Accuracy of ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny
Tr12A}}$, ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$and related
HoPIMs; (b) Accuracy of ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$,
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$and average results of each
set of islands in ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ running
the same BA.

Figure 6: (a) Accuracy of ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny
gbmm12A}}$, ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$and related
HoPIMs; (b) Accuracy of ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny
gbmm12A}}$, ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$and average
results of each set of islands in ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny
gbmm12A}}$ running the same BA.

Fig. 7 compares the accuracy of the four non- and reconfigurable HePIMs:
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$, ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny Tr12A}}$, ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny
gbmm12A}}$, and. ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$. From
the experiments, it is clear that the new reconfigurable heterogeneous
architectures, ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ and
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$, add to the
versatility of heterogeneous PIMs the flexibility of dynamically updating the
BA executed in each island promoting in this manner not only data diversity,
but also algorithmic dynamism. Reconfigurable heterogeneous PIMs open up a
promising new exploration space where, unlike von Newman’s style of
algorithmic exploration focused on efficient information data management,
algorithmic data dynamism enters as a crucial player in the game (see, for
example, [16], [17]).

Figure 7: Accuracy of the non reconfigurable and reconfigurable HePIMs TABLE V: Example of the final distribution of GA, GAD, DE and PSO. | GA | GAD | DE | PSO
---|---|---|---|---
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 49.25% | 4.09% | 18.08% | 28.58%
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 29.42% | 17.5% | 28.25% | 24.83%

###  IV-C Statistical Analysis

Statistical tests validated experiments using $95\%$ of significance level
represented in the tests as $\alpha=0.05$. The samples are the sets of one
hundred outputs obtained in Section IV-B. Initially, the Friedman test was
applied to define the control algorithm. Then, Holm’s test was applied to
check the null hypothesis that the performance of the control algorithm is the
same concerning the remaining algorithms, according to García and Herrera
approach [18] (see also [19], and [20]).

Table VI presents the statistical results for the PIMs with binary tree
topology: ${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$, ${\cal
P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$, and ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny Tr12A}}$. The Friedman test selects ${\cal
P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ as the control algorithm, and the null
hypothesis is discarded for all samples. The model ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny Tr12A}}$ is the second-best confirming the discussion in
Section IV-B. Table VII shows the statistical results for the models with
complete graph topology, ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$,
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$, and the best
homogeneous version, ${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$, which is
selected as the control algorithm. Finally, Table VIII gives the statistical
tests for the four reconfigurable and non-reconfigurable HePIMs. The selected
control algorithm was ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$.
Holm’s procedure rejects the null hypotheses (for $p$-value $\leq 0.05$),
thus, ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ has statistical
significance only for ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ and
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$, and compared to ${\cal
P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ there is no statistical
significance confirming the discussion in Section IV-B.

TABLE VI: Holm test for the tree topology PIMs.  L | Control | i | Algorithm | $p$-value | $\alpha/i$
---|---|---|---|---|---
| Algorithm |  |  |  |
100 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 7.74959960741012E-11 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 1.8505741383968991E-9 | 0.050
110 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 1.346035421050821E-15 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 5.560820039745642E-15 | 0.050
120 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 3.722840351917189E-19 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 3.2599374788722365E-13 | 0.050
130 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 4.218936534105464E-12 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 1.449490502746956E-11 | 0.050
140 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 3.1593469401304723E-16 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 1.4870457587052685E-9 | 0.050
150 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 5.124221656690746E-19 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny Tr12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 9.723622409009922E-15 | 0.050
TABLE VII: Holm test for the complete graph PIMs.  L | Control | i | Algorithm | $p$-value | $\alpha/i$
---|---|---|---|---|---
| Algorithm |  |  |  |
100 |  | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 7.43098372370352E-7 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ | 1 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 1.1648657367238803E-5 | 0.050
110 |  | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 9.672204071723814E-19 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ | 1 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2.9294885290101255E-14 | 0.050
120 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 1.792019989925749E-15 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 1.792019989925749E-15 | 0.050
130 |  | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 3.943363947351002E-17 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ | 1 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2.3828362635579084E-15 | 0.050
140 |  | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 4.82026808703977E-22 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ | 1 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 1.0213251630273183E-20 | 0.050
150 |  | 2 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 3.4176814448375205E-24 | 0.025
${\cal P}^{\mbox{{DE}}}_{\mbox{\tiny gbmm12A}}$ | 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 1.440728401105864E-23 | 0.050
TABLE VIII: Holm test for reconf. and non-reconf. HePIMs.  L | Control | i | Algorithm | $p$-value | $\alpha/i$
---|---|---|---|---|---
| Algorithm |  |  |  |
100 |  | 3 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 6.219448336201955E-7 | 0.016
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 3.5448303585580045E-5 | 0.025
| 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 0.3958980057181269 | 0.05
110 |  | 3 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 2.1442166253671064E-13 | 0.016
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 7.221976514824151E-13 | 0.025
| 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 0.1709035202307971 | 0.05
120 |  | 3 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 2.1442166253672077E-13 | 0.016
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 3.908557567773197E-9 | 0.025
| 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 0.7218258402177081 | 0.05
130 |  | 3 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 1.076195601000617E-12 | 0.016
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 3.415515804642443E-11 | 0.025
| 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 0.4113137917762579 | 0.05
140 |  | 3 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 4.342593992240847E-19 | 0.016
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 2.1442166253671531E-13 | 0.025
| 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 0.8694817827381613 | 0.05
150 |  | 3 | ${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ | 3.3892419952526653E-19 | 0.016
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny gbmm12A}}$ | 2 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ | 2.4806730968270847E-15 | 0.025
| 1 | ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ | 0.912770619096563 | 0.05

##  V Related Work

As far as we know, no HePIM has been proposed that may dynamically update
their BAs as proposed in this work. Here, we discuss a few works related to
non-reconfigurable HePIMs.

Bianchini and Brown [21] proposed HePIMs with ring and torus topologies and
applied them to the task map scheduling problem showing that HePIMs compute
better solutions than HoPIMs. In addition, they observed that adding islands
is better than increasing the population. Also, Lin et al. [22] proposed
HePIMs, considering several migration strategies and topologies addressing the
graph partitioning problem. They showed that 25-island PIMs are better than
the sequential GA, using a migration strategy that replaces the worst
individuals on target islands. Furthermore, they showed that exchanging
individuals regarding their fitness-based population similarity instead gets
good results without speed degradation.

Izzo et al. [23] proposed an asynchronous-migration HePIM from variations of
the DE algorithm. Asynchrony was shown more intuitive and suitable over
TCP/IP, where resources might become available/unavailable at any time. Izzo
et al. models showed better performance than their sequential versions.

Gong and Fukunaga [24] proposed a GA-based HePIM that randomly selects
different parameters for each processor. Some processors are expected to be
assigned parameters that perform well on a given problem. Such model may be
considered a one-cycle reconfigurable model. However, it applies only an
initial adjust of the same algorithm and does not update BAs dynamically as
ours reconfigurable HePIMs.

Duarte et al. [25] proposed an attractiveness-based migration policy for five-
island HePIMs that is based on island solutions’ quality. Attractiveness was
adjusted in [9], inspired by the natural phenomenon known as stigmergy [26],
and the mechanism to compute islands’ connections.

Silveira et al. [27] proposed HoPIMs for a sequential GA introduced in [28] to
solve the unsigned translocation problem. Such PIMs outperformed the accuracy
obtained by the GA after careful calibration of the migration and breeding
cycle parameters and exploration of a variety of topologies [29, 30]. Further,
Silveira et al. [10] analyzed synchronous HoPIMs for GA, PSO, and the Social
Spider Algorithm (SSA). Experiments showed that HoPIMs applying PSO and GA are
competitive, while those running SSA gave the best speed-ups but computed the
worst-accuracy solutions. Finally, Silveira et al. [1] proposed a variety of
HePIMs to deal with URD. In this work, we select Lucas et al. models ${\cal
P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ and ${\cal P}^{\mbox{\tiny
Het}}_{\mbox{\tiny gbmm12A}}$ for our comparison with the new reconfigurable
HePIMs.

HePIMs also have been conceived to solve multiobjective optimization problems
(MOPs). We believe that MOPs are exciting applications to our reconfigurable
HePIMs since each island may update its BA to optimize a single objective
function. For example, Zang _et al._ [31] proposed a multi-swarm optimizer
that handles each objective function of a MOP with a different slave swarm,
and a master swarm covers gaps among non-dominated optima using a
multiobjective PSO. Also, Xu _et al._ [32] proposed a model with EAs using two
subpopulations to solve dynamic interval MOPs, which are MOPs that change
interval parameters of their objectives or constraints over time. In addition,
Gong _et al._ [33] proposed a model that handles a cooperative co-evolutionary
MOP based on dynamic interval similarity. Gong _et al._ approach split
decision variables according to their interval similarity and interval
parameters. Then, decision variables are optimized cooperatively. Furthermore,
Hashimoto _et al._ [34] proposed a HePIM to solve multi-task problems, where
each island evaluates an objective. Migrants are selected at high migration
frequency, and removed randomly on each local island, replacing the worst
individuals in the target islands. Since immigrants went to islands
responsible for different objectives, their fitness values are the worst,
assuming they have fewer chances of being suitable for the target island
objective.

##  VI Conclusions and future work

Reconfigurable heterogeneous PIMs were introduced. Such architectures can run
and dynamically update different bio-inspired algorithms on their islands. Two
reconfigurable PIM architectures with two different archipelago-topologies
were designed: a static binary tree topology, ${\cal P}^{\mbox{\tiny
recHet}}_{\mbox{\tiny Tr12A}}$, and a dynamic complete graph topology, ${\cal
P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$. The asynchronous models ran
four different BAs in their islands: GA, GAD, PSO, and DE. The new
reconfigurable HePIMs were tested over the unsigned reversal distance problem
and computed results that outperformed the quality of associated non-
reconfigurable HePIMs.

Experiments, evaluated statistically, made evident the potential of
reconfigurable HePIMs. Such reconfigurable models preserve the power of
heterogeneous PIMs to navigate efficiently in the space of feasible solutions
through a healthy balance between individual and island diversity and
migration policy. Also, the new reconfiguration feature gives the architecture
the flexibility to evolve dynamically, improving the model’s algorithmic
adaptability to solve the target problem.

The architectures ${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny Tr12A}}$ and
${\cal P}^{\mbox{\tiny recHet}}_{\mbox{\tiny gbmm12A}}$ reached quality
results very competitive regarding non-reconfigurable associated architectures
${\cal P}^{\mbox{\tiny Het}}_{\mbox{\tiny Tr12A}}$ and ${\cal P}^{\mbox{\tiny
Het}}_{\mbox{\tiny gbmm12A}}$, closing the gap with the homogeneous best-
adapted model that uses DE.

Future work will explore reconfigurable HePIMs over different problems and
with a greater variety of BAs. In particular, we believe that the dynamic
algorithmic heterogeneity promoted by the new model will be helpful to deal
with multiobjective optimization problems. Indeed, the reconfiguration would
promote the application of the best-adapted BA to each target problem over the
islands.

## References

  * [1] L. A. da Silveira, J. L. Soncco-Álvarez, T. A. de Lima, and M. Ayala-Rincón, “Heterogeneous Parallel Island Models,” in IEEE Symposium Series on Computational Intelligence (SSCI), 2021.
  * [2] J. H. Holland, “Genetic Algorithms and the Optimal Allocation of Trials,” SIAM Journal on Computing, vol. 2, no. 2, pp. 88–105, 1973.
  * [3] R. Storn and K. Price, “Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces,” J. of Global Optimization, vol. 11, no. 4, pp. 341–359, 1997.
  * [4] R. Eberhart and J. Kennedy, “Particle swarm optimization,” in IEEE Int. Conf. on neural networks, vol. 4, pp. 1942–1948, 1995.
  * [5] A. Caprara, “Sorting by reversals is difficult,” in Proc. of the first ACM annual Int. Conf. on Comp. molecular Biology, pp. 75–83, 1997.
  * [6] T. A. de Lima and M. Ayala-Rincón, “On the average number of reversals needed to sort signed permutations,” Discrete Applied Mathematics, vol. 235, no. Supplement C, pp. 59 – 80, 2018.
  * [7] J. Kececioglu and D. Sankoff, “Exact and approximation algorithms for the inversion distance between two chromosomes,” in Proc. Combinatorial Pattern Matching (CPM), pp. 87–105, Springer, 1993.
  * [8] T. G. Crainic and M. Toulouse, Parallel Strategies for Meta-Heuristics, pp. 475–513.  Boston, MA: Springer US, 2003.
  * [9] G. R. d. C. L. Duarte, A. C. da Fonseca, L. G. de Lima, and B. S. L. Pires, “An Island Model based on Stigmergy to solve optimization problems,” Natural Computing, pp. 1–29, 2020.
  * [10] L. A. da Silveira, J. L. Soncco-Álvarez, T. A. de Lima, and M. Ayala-Rincón, “Behavior of Bioinspired Algorithms in Parallel Island Models,” in IEEE Cong. on Evol. Comp. (CEC), 2020.
  * [11] D. Sudholt, Springer Handbook of Computational Intelligence, ch. Parallel Evolutionary Algorithms, pp. 929–959.  Springer, 2015.
  * [12] S. Hannenhalli and P. A. Pevzner, “Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals,” J. of the ACM, vol. 46, no. 1, pp. 1–27, 1999.
  * [13] K. Yasuda and K. Yazawa, “Parameter self-adjusting strategy for particle swarm optimization,” in 11th Int. Conf. on Intelligent Systems Design and Applications, pp. 265–270, IEEE, 2011.
  * [14] D. Bader, B. Moret, and M. Yan, “A linear-time algorithm for computing inversion distance between signed permutations with an experimental study,” J. of Comp. Biology, vol. 8, no. 5, pp. 483–491, 2001.
  * [15] A. Eiben and S. Smit, “Parameter tuning for configuring and analyzing evolutionary algorithms,” Swarm and Evol. Comp., vol. 1, no. 1, pp. 19–31, 2011.
  * [16] R. W. Hartenstein, “Reconfigurable Computing: boosting software education for the multicore era: Why we need to reinvent computing,” in VI Southern Programmable Logic Conference (SPL), IEEE Computer Society, 2010.
  * [17] R. W. Hartenstein, “The tunnel vision syndrome: Massively delaying progress,” in 24th International Conference on Application-Specific Systems, Architectures and Processors, (ASAP), IEEE Computer Society, 2013\.
  * [18] S. García and F. Herrera, “An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons,” J. of Machine Learning Research, vol. 9, pp. 2677–2694, 2008.
  * [19] J. Demšar, “Statistical comparisons of classifiers over multiple data sets,” J. of Machine Learning Research, vol. 7, pp. 1–30, 2006.
  * [20] J. Derrac, S. García, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evol. and swarm intelligence algorithms,” Swarm and Evol. Comp., vol. 1, no. 1, pp. 3–18, 2011.
  * [21] R. Bianchini and M. C. Brown, “Parallel Genetic Algorithms on Distributed-Memory Architectures,” in NATUG-6: Proc. of the Sixth Conf. of the North American Transputer Users Group on Transputer Research and Applications 6, IOS Press, 1993.
  * [22] S. C. Lin, W. F. Punch, and E. D. Goodman, “Coarse-grain parallel genetic algorithms: categorization and new approach,” in Proc. 6th IEEE Symp. on Parallel and Distributed Processing, pp. 28–37, 1994.
  * [23] D. Izzo, M. Rucinski, and C. Ampatzis, “Parallel global optimisation meta-heuristics using an asynchronous island-model,” in IEEE Cong. on Evol. Comp. (CEC), pp. 2301–2308, 2009.
  * [24] Y. Gong and A. Fukunaga, “Distributed island-model genetic algorithms using heterogeneous parameter settings,” in IEEE Cong. on Evol. Comp. (CEC), pp. 820–827, 2011.
  * [25] G. Duarte, A. Lemonge, and L. Goliatt, “A New Strategy to Evaluate the Attractiveness in a Dynamic Island Model,” in IEEE Cong. on Evol. Comp. (CEC), 2018.
  * [26] P. V. S. Z. Capriles, L. G. Fonseca, H. J. C. Barbosa, and A. C. C. Lemonge, “Rank-based ant colony algorithms for truss weight minimization with discrete variables,” Communications in Numerical Methods in Engineering, vol. 23, no. 6, pp. 553–575, 2007.
  * [27] L. A. da Silveira, J. L. Soncco-Álvarez, and M. Ayala-Rincón, “Parallel memetic genetic algorithms for sorting unsigned genomes by translocations,” in IEEE Cong. on Evol. Comp. (CEC), pp. 185–192, 2016\.
  * [28] L. A. da Silveira, J. L. Soncco-Álvarez, T. A. de Lima, and M. Ayala-Rincón, “Computing translocation distance by a genetic algorithm,” in 2015 Latin American Computing Conf. (CLEI), pp. 1–12, 2015\.
  * [29] L. A. da Silveira, J. L. Soncco-Álvarez, T. A. de Lima, and M. Ayala-Rincón, “Parallel multi-island genetic algorithm for sorting unsigned genomes by reversals,” in IEEE Cong. on Evol. Comp. (CEC), 2018\.
  * [30] L. A. da Silveira, J. L. Soncco-Álvarez, T. A. de Lima, and M. Ayala-Rincón, “Parallel Island Model Genetic Algorithms applied in NP-Hard problems,” in IEEE Cong. on Evol. Comp. (CEC), 2019.
  * [31] Y. Zhang, D. Gong, and Z. Ding, “Handling multi-objective optimization problems with a multi-swarm cooperative particle swarm optimizer,” Expert Systems with Applications, vol. 38, pp. 13933–13941, 2011.
  * [32] B. Xu, Y. Zhang, D. Gong, Y. Guo, and M. Rong, “Environment Sensitivity-Based Cooperative Co-Evolutionary Algorithms for Dynamic Multi-Objective Optimization,” IEEE/ACM Trans. on Comp. Biology and Bioinformatics, vol. 15, no. 6, pp. 1877–1890, 2018.
  * [33] D. Gong, B. Xu, Y. Zhang, Y. Guo, and S. Yang, “A Similarity-Based Cooperative Co-Evolutionary Algorithm for Dynamic Interval Multiobjective Optimization Problems,” IEEE Trans. on Evol. Comp., vol. 24, no. 1, pp. 142–156, 2020.
  * [34] R. Hashimoto, H. Ishibuchi, N. Masuyama, and Y. Nojima, “Analysis of Evolutionary Multi-Tasking as an Island Model,” in Proc. of the Genetic and Evol. Comp. Conf. (GECCO), pp. 1894–1897, ACM, 2018.