# A Parallel Island Genetic Algorithm for Triangle-based Image Reconstruction

Jean-Philippe Valois, Thomas Firmin, Nouredine Melab

► To cite this version:

Jean-Philippe Valois, Thomas Firmin, Nouredine Melab. A Parallel Island Genetic Algorithm for Triangle-based Image Reconstruction. AICCSA 2025 - ACS/IEEE International Conference on Computer Systems and Applications, Oct 2025, Doha, Qatar. pp.1-8, 10.1109/AICCSA66935.2025.11315373. hal-05458101

HAL Id: hal-05458101

https://hal.science/hal-05458101v1

Submitted on 22 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A Parallel Island Genetic Algorithm for Triangle-based Image Reconstruction

Jean-Philippe Valois*, Thomas Firmin†, Nouredine Melab‡

Université de Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISTAL, Lille, France

*jean-philippe.valois@inria.fr, †thomas.firmin@univ-lille.fr, ‡nouredine.melab@univ-lille.fr

**Abstract**—In this paper, we investigate the application of Genetic Algorithms (GAs) and their parallelization via the Island Model (IMGA) for polygonal image reconstruction. The objective is to approximate a target image using a fixed number of colored triangles, formulating the problem as a high-dimensional optimization challenge. A standard GA is first implemented to assess its effectiveness using various objective functions. We then introduce a parallel IMGA framework, featuring multiple subpopulations evolving independently with periodic migration in a ring topology. Migration parameters are calibrated, revealing optimal settings for preserving diversity and improving convergence. Experimental results indicate that IMGA achieves up to a 50% improvement in reconstruction quality compared to the standard GA, with minimal additional computational cost. Moreover, our approach significantly outperforms the current state of the art for this problem, which relies on a hybrid method combining genetic algorithms and machine learning. These findings highlight the effectiveness and scalability of island models in addressing complex, high-dimensional optimization problems such as image reconstruction.

**Index Terms**—Genetic Algorithms, Island Model, Parallel metaheuristics, Image reconstruction.

## I. INTRODUCTION

Genetic Algorithms (GAs) are particularly effective for solving complex, nonlinear, and high-dimensional optimization problems, especially when traditional deterministic methods are impractical or insufficient. As part of the broader class of evolutionary algorithms, these algorithms rely on biologically inspired metaheuristic operators such as selection, crossover, and mutation [1]. To further enhance their efficiency, various hybridization strategies have been explored, such as incorporating local search techniques or machine learning components. In addition, techniques such as the island model [2] have been developed to improve scalability and robustness. In particular Island Model Genetic Algorithms (IMGAs), also referred to as multi-island genetic algorithms, introduce population-level subdivision to promote diversity and are well suited to parallel computing environments. These algorithms have shown promising results in various real-world applications, including engineering design optimization [3] and material parameter identification in fracture mechanics [4], reinforcing their practical relevance.

A particularly challenging application where these methods prove effective is polygonal image reconstruction, and more specifically, triangle-based image reconstruction. In addition to offering a visually interpretable benchmark, this

approach provides practical advantages over storing high-resolution raster images, such as reduced storage requirements and vectorization. In this work, our primary interest lies not in the application itself, but in the complexity of the problem and its resolution using metaheuristic algorithms. This reconstruction task was first addressed by Wiransky [5] using a genetic algorithm and was later improved by Cavallaro et al. [6] through a hybrid approach integrating machine learning techniques. Building on these foundations, our work is motivated by the desire to evaluate the effectiveness of a parallel genetic algorithm based on the island model for solving this computationally intensive optimization problem, which offers a demanding and insightful testbed for assessing evolutionary algorithms and their extensions.

The primary contributions of this work can be summarized as follows.

* We revisit the polygonal image reconstruction problem through our implementation of a genetic algorithm.

* We extend this baseline approach by introducing a parallel variant based on the island model.

* We demonstrate the effectiveness of this multi-island strategy in addressing high-dimensional optimization problems of this nature and compare our approach to the current state of the art.

The following sections describe the remainder of the paper's structure. In Section II, we formalize the image reconstruction task as an optimization problem. In Section III, we introduce a baseline solution using a genetic algorithm, followed by its enhancement through the island model. In Section IV, we present our experimental results, which outperform those presented in [6] while maintaining controlled computational costs. Finally, in Section V, we present our concluding remarks and outline some directions for future work.

## II. PROBLEM FORMULATION

The problem consists in reconstructing a given image using an ordered set of colored triangles. Triangles that can overlap and be of any shape, size, color, or opacity. In other words, the objective is to determine the optimal set of coordinates and color attributes for *N* triangles, such that the image resulting from their superposition approximates a target image with minimal loss of information.

Images are represented in RGB format and can be mathematically defined as a tensor of size $H \times W \times 3$, where $H$ and $W$ denote the image height (number of pixel rows)
and width (number of pixel columns), respectively. The third dimension corresponds to the three color channels: Red (R), Green (G), and Blue (B). Since the images are in 8-bit format, the tensor values are integers ranging from 0 to 255. Based on this representation, the image reconstruction task can be formulated as the following optimization problem.

**Definition (Image Reconstruction Problem).** Given a target image $X \in [0, 255]^{H \times W \times 3}$, find $z \in \mathcal{T}^N$ such that $Y = g(z) \in [0, 255]^{H \times W \times 3}$ minimizes $f(X, Y)$:

$$ \min_{z \in \mathcal{T}^N} f(X, g(z)). \qquad (1) $$

where:

* $\mathcal{T} := ([0, W-1] \times [0, H-1])^3 \times [0, 255]^4$ defines the set of all possible configurations of a single triangle, with integer-valued (pixel) coordinates for their vertices and an associated color in 8-bit RGBA format. Here, A denotes the alpha channel, representing the opacity of the triangle.

* $g: \mathcal{T}^N \to [0, 255]^{H \times W \times 3}$ is the rendering function that takes an ordered set of N colored triangles and outputs the resulting image tensor obtained by superimposing these triangles.

* $f: ([0, 255]^{H \times W \times 3})^2 \to \mathbb{R}$ denotes the objective function, which quantifies the discrepancy between the target image X and a candidate reconstruction Y.

Naturally, problem (1) can be generalized to polygons with more than three vertices. However, any such polygon can be decomposed into multiple triangles. Additionally, allowing more complex polygons would significantly increase the dimensionality of the problem. For these reasons, we restrict ourselves to using triangles throughout this study, as the corresponding search space $\mathcal{T}^N$ is already of considerable size. For example, reconstructing a 500 × 500 pixel image using $N = 100$ colored triangles yields a search space of cardinality $(500^6 \times 256^4)^{100}$, which is approximately $10^{2582}$ possible configurations. The sheer scale and complexity of this high-dimensional combinatorial landscape make traditional deterministic methods impractical. Consequently, exploration-oriented metaheuristics, and in particular genetic algorithms, emerge as well-suited candidates for tackling this class of optimization problems.

Before detailing the design and implementation of our GA, we briefly address the choice of the objective function $f$. We introduce three widely used image similarity measures to assess the quality of reconstructed images. These metrics were also included in the comparative evaluation conducted by Sara et al. [7], and provide complementary perspectives on image fidelity, noise sensitivity, and perceptual similarity.

**Mean Squared Error (MSE).** The most straightforward pixel-wise comparison between two images X and Y:

$$ \text{MSE}(X, Y) = \frac{1}{3WH} \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} \sum_{k=0}^{2} (X_{i,j,k} - Y_{i,j,k})^2. \quad (2) $$

**Peak Signal-to-Noise Ratio (PSNR).** Another common

pixel-wise computation derived from the MSE:

$$ \text{PSNR}(X, Y) = 10 \log_{10} \left( \frac{L^2}{\text{MSE}(X, Y)} \right). \qquad (3) $$

Here, $L$ denotes the dynamic range of the pixel values, given by $L = 2^b - 1$ where $b$ is the number of bits per pixel. For our 8-bit images, $L = 255$. Note that a higher PSNR indicates a closer match between X and Y. Consequently, when PSNR is used as $f$, problem (1) becomes a maximization problem.

**Structural Similarity Index (SSIM).** Unlike the MSE and PSNR functions which are purely numerical comparisons, the SSIM uses luminance, contrast, and local image structure. These metrics combined yield the following definition of the SSIM function, where the final value is computed as the average over the three color channels:

$$ \text{SSIM}(X, Y) = \frac{1}{3} \sum_{k=0}^{2} \frac{(2\mu_{X_k} \mu_{Y_k} + c_1)(2\sigma_{X_k Y_k} + c_2)}{(\mu_{X_k}^2 + \mu_{Y_k}^2 + c_1)(\sigma_{X_k}^2 + \sigma_{Y_k}^2 + c_2)} \quad (4) $$

Here, for $k \in \{0, 1, 2\}$, $X_k$ and $Y_k$ denote the red, green, and blue channels of images X and Y, respectively, each of size $W \times H$. $\mu_{X_k}$ and $\sigma_{X_k}$ are respectively, the mean and standard deviation of channel $X_k$, and similarly for $Y_k$. $\sigma_{X_k Y_k}$ denotes the unbiased covariance between $X_k$ and $Y_k$:

$$ \sigma_{X_k Y_k} = \frac{1}{WH-1} \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} (X_{i,j,k} - \mu_{X_k})(Y_{i,j,k} - \mu_{Y_k}). \quad (5) $$

The constants $c_1 := (0, 01L)^2$ and $c_2 := (0, 03L)^2$ ensure numerical stability when the denominators approach zero. SSIM returns values in the range $[0, 1]$, with higher values indicating greater similarity. This metric can thus be interpreted as a percentage-like measure of similarity, and just as with PSNR, using SSIM as $f$ implies that problem (1) becomes a maximization problem.

### III. ISLAND GENETIC ALGORITHM DESIGN

#### A. Standard Genetic Algorithm

In order to tackle the image reconstruction problem (1), we start by implementing the GA described in Algorithm 1, which evolves a population of individuals over a fixed number of iterations, referred to as generations. In this context, each individual represents an ordered set of N colored triangles.

**Initialization.** The initial population $P_0$ consists of a collection of P individuals, where each individual is a set of N completely random triangles.

**Selection.** A new population $P_i$ is formed by selecting the most promising individuals from $P_{i-1}$. To introduce stochasticity, we adopt tournament selection: in each tournament, the best individual (i.e., the one with the lowest objective function value) is selected from a subset of Q randomly chosen individuals. This process is repeated P times.

**Crossover.** Assuming the population size P is even, individuals in $P_i$ are paired. Each pair being considered as parents. Two offsprings are generated from each pair by swapping R randomly chosen triangles between the parents.
<table><thead><tr><th colspan="2">Algorithm 1: Genetic Algorithm</th></tr></thead><tbody><tr><td><i>X</i></td><td>target image</td></tr><tr><td><i>f</i></td><td>objective function</td></tr><tr><td><i>g</i></td><td>conversion function</td></tr><tr><td><i>G</i></td><td>number of generations</td></tr><tr><td><i>P</i></td><td>population size</td></tr><tr><td><i>P</i><sub>0</sub></td><td>RandomPopulation (<i>P</i>)</td></tr><tr><td><i>Y</i><sub>0</sub></td><td>Rendering (<i>P</i><sub>0</sub>, <i>g</i>)</td></tr><tr><td><i>F</i><sub>0</sub></td><td>Evaluation (<i>X</i>, <i>Y</i><sub>0</sub>, <i>f</i>)</td></tr><tr><td>for <i>i</i> &lt; 1 to <i>G</i> do</td><td></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>P</i><sub><i>i</i></sub></td><td>Selection (<i>P</i><sub><i>i</i></sub>−1, <i>F</i><sub><i>i</i></sub>−1)</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>P</i><sub><i>i</i></sub></td><td>Crossover (<i>P</i><sub><i>i</i></sub>)</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>P</i><sub><i>i</i></sub></td><td>Mutation (<i>P</i><sub><i>i</i></sub>)</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>Y</i><sub><i>i</i></sub></td><td>Rendering (<i>P</i><sub><i>i</i></sub>, <i>g</i>)</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>F</i><sub><i>i</i></sub></td><td>Evaluation (<i>X</i>, <i>Y</i><sub><i>i</i></sub>, <i>f</i>)</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>P</i><sub><i>i</i></sub>, <i>F</i><sub><i>i</i></sub></td><td>Elitism (<i>P</i><sub><i>i</i></sub>−1, <i>P</i><sub><i>i</i></sub>, <i>F</i><sub><i>i</i></sub>−1, <i>F</i><sub><i>i</i></sub>)</td></tr><tr><td>end</td><td></td></tr><tr><td>return</td><td>BestIndividual (<i>P</i><sub><i>G</i></sub>, <i>F</i><sub><i>G</i></sub>)</td></tr></tbody></table>

**Mutation.** Each individual in $\mathcal{P}_i$ is subject to a slight change, called a mutation, with probability $p_m$. A mutation consists in either a random modification of one vertex of a randomly selected triangle, or a random modification of its color. These two types of mutation are equally likely and at most one of them can be applied per individual.

**Rendering.** Each individual in $\mathcal{P}_i$, represented as a set of triangles, is converted into an image tensor to form the set $Y_i$. This is achieved by sequentially overlaying each triangle onto a blank canvas.

**Evaluation.** The candidate images in $Y_i$ are evaluated against the target image $X$ using the objective function $f$, yielding a fitness value for each individual in $\mathcal{P}_i$.

**Elitism.** The best half (in terms of fitness) of the current population $\mathcal{P}_i$ is merged with the best half of the previous population $\mathcal{P}_{i-1}$ to form the new population.

Regarding the choice of genetic operators, we adopt the same selection and mutation operators as in the study conducted in [6]. However, in contrast to their use of Simulated Binary Crossover, we employ a simpler crossover strategy. In addition, we incorporate an elitism mechanism designed to enhance the algorithm's stability and promote a better balance between exploration and exploitation.

Since both the selection and elitism operators require individuals to be ranked by fitness, we sort the population after each evaluation step. To this end, we use merge sort, a stable algorithm with a time complexity of $O(n \log n)$. Given that both $\mathcal{P}_i$ and $\mathcal{P}_{i-1}$ are already sorted, the elitism step is efficiently implemented by using a two-way merge.

## B. Island Genetic Algorithm

We now turn to a parallel implementation of our genetic algorithm, using an algorithm-level parallelization strategy known as the island model [2]. Instead of evolving a single population of size $P$, the algorithm runs on $K$ distinct islands, each hosting its own population of size $P$, where identical genetic operators are applied independently and concurrently.

The goal is to enhance both the robustness and quality of the solutions by increasing the exploratory capacity of the algorithm, without incurring additional computational cost since all islands are processed in parallel.

To further enhance the robustness of the island model GA, we introduce a migration mechanism designed to slow premature convergence and promote diversity. At the end of each generation, the $M$ best and $M$ worst individuals (in terms of fitness) from each island are exchanged with neighboring islands in a ring topology, as illustrated in Fig. 1. This dual migration policy draws inspiration from diversity-preserving strategies in the literature, such as the MultiKulti algorithm by Araujo et al. [8] and the DM-LIMGA model by Gozali and Fujimura [9], both of which highlight the benefits of introducing varied genetic material to sustain exploration and prevent stagnation. This migration occurs every $T$ generations, where $T$ is a user-defined migration period.

To maximize its effectiveness, migration is scheduled before the exploration-oriented operators crossover and mutation, thereby strengthening cooperation between islands and increasing diversity. Concretely, individuals are sent out immediately after the elitism step and received just before selection and crossover. Upon arrival, migrants replace randomly chosen individuals within the destination population. An additional advantage of this approach is that, since crossover does not require a sorted population (unlike selection), no extra sorting step is necessary after migration. The pseudo-code for this island model-based genetic algorithm, which we will refer to as IMGA, is presented in Algorithm 2.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Depiction of the IMGA with ring topology, illustrating the migration mechanism between neighboring islands.</figcaption></figure>

## IV. EXPERIMENTAL RESULTS

### A. Experimental setup

The algorithms used in this study are implemented in C++ using a highly object-oriented design, leveraging the OpenCV library for image processing operations [10]. All of the experiments are conducted on the Grid'5000 platform, specifically on a computing node of the *chirop* cluster at the Lille site, equipped with two Intel Xeon Platinum 8358 CPUs. Given the stochastic nature of genetic algorithms, each experimental configuration is executed ten times independently. Unless otherwise stated, all reported numerical results (fitness values and computational times) correspond to the average values obtained across these ten runs, thereby ensuring statistical robustness and mitigating variance due to randomness.
<caption>**Algorithm 2: Island Genetic Algorithm**</caption>

K : number of islands
M : migration count
T : migration period
**for** j ← 0 **to** K − 1 **do in parallel**
  $\mathcal{P}_0^j$ ← RandomPopulation($P$)
  $Y_0^j$ ← Rendering($\mathcal{P}_0^j$, $g$)
  $\mathcal{F}_0^j$ ← Evaluation($X$, $Y_0^j$, $f$)
  **for** i ← 1 **to** G **do**
    $\mathcal{P}_i^j$ ← Selection($\mathcal{P}_{i-1}^j$, $\mathcal{F}_{i-1}^j$)
    MigrationReceive($\mathcal{P}_i^j$, $M$, $T$)
    $\mathcal{P}_i^j$ ← Crossover($\mathcal{P}_i^j$)
    $\mathcal{P}_i^j$ ← Mutation($\mathcal{P}_i^j$)
    $Y_i^j$ ← Rendering($\mathcal{P}_i^j$, $g$)
    $\mathcal{F}_i^j$ ← Evaluation($X$, $Y_i^j$, $f$)
    $\mathcal{P}_i^j$, $\mathcal{F}_i^j$ ← Elitism($\mathcal{P}_{i-1}^j$, $\mathcal{P}_i^j$, $\mathcal{F}_{i-1}^j$, $\mathcal{F}_i^j$)
    MigrationSend($\mathcal{P}_i^j$, $M$, $T$)
  **end**
**end**
**return** BestIndividual($\mathcal{P}_G^0$, ..., $\mathcal{P}_G^{K-1}$, $\mathcal{F}_G^0$, ..., $\mathcal{F}_G^{K-1}$)

In order to evaluate the performances of our algorithms, we employ the diverse set of benchmark images shown in Fig. 2. The resolution (in pixels) of each of these images varies and serves as an additional parameter, allowing us to further adjust the level of complexity of the problem.

## B. Standard Genetic Algorithm baseline

1) *Objective function comparison:* Our first experiment applies the standard GA (Algorithm 1) using each of the three metrics defined in Section II (MSE, PSNR SSIM) as the objective function *f*. The goal is to identify which metric is most appropriate for the image reconstruction task. The algorithm is executed to reconstruct the portrait of *Mona Lisa* (Fig. 2b) with a resolution of 128 × 128 pixels, using the set of parameters listed in Table I. For each objective function, the reconstructed image corresponding to the best fitness value across ten independent runs is shown in Fig. 3.

<table><caption>TABLE I: Genetic algorithm parameters used for objective function evaluation.</caption><thead><tr><td>symbol</td><td>description</td><td>value</td></tr></thead><tbody><tr><td>G</td><td>number of generations</td><td>5000</td></tr><tr><td>P</td><td>population size</td><td>100</td></tr><tr><td>Q</td><td>tournament selection size</td><td>20</td></tr><tr><td>N</td><td>number of triangles</td><td>100</td></tr><tr><td>R</td><td>number of triangle swaps</td><td>50</td></tr><tr><td>p<sub>m</sub></td><td>mutation probability</td><td>0.7</td></tr></tbody></table>

Overall, the visual quality of the reconstructed images is comparable across the three objective functions. However, a slight advantage can be attributed to MSE and PSNR, as the average execution time of the algorithm is approximately 830 seconds with these metrics, compared to 850 seconds when using SSIM. For the sake of simplicity and computational

efficiency, we therefore adopt MSE as the objective function *f* for the remainder of this study.

2) *Calibration of the Number of Triangles:* In the previous experiment, the genetic algorithm parameters were selected based on values commonly used in similar algorithms (cf. Table I). The exception is *N*, the number of triangles used in the reconstruction (and consequently *R*, the number of triangle swaps during crossover). Unlike the other parameters, *N* is problem-dependent, and its value was empirically set to 100.

To better understand the influence of *N*, we conduct an experimental calibration to assess whether varying the number of triangles improves reconstruction quality and how it affects computational cost. Fig. 4a shows the MSE fitness of the algorithm output for reconstructing the five benchmark images (Fig. 2) with increasing values of $N \in \{20, 40, 60, \dots, 200\}$. Fig. 4b presents the corresponding average execution times. All other GA parameters remain fixed (Table I), with *R* set to half of *N* in each case.

Contrary to intuition, increasing the number of triangles *N* does not consistently lead to significant improvements in reconstruction quality, as illustrated in Fig. 4a. While, in theory, a higher value for *N* could capture finer details of the target image, it also introduces more overlap in the reconstructed image and significantly increases the dimensionality of the search space, both of which complicate the optimization process for the genetic algorithm. Furthermore, as shown in Fig. 4b, the execution time of the GA scales linearly with *N*. Taking into account both reconstruction quality and computational cost, $N = 100$ emerges as a reasonable compromise. We therefore retain this value for the remainder of this work.

3) *Image reconstruction results:* Having selected both the objective function and the number of triangles for reconstruction, we then evaluate the performance of our genetic algorithm (Algorithm 1) on the set of benchmark images shown in Fig. 2. The GA parameters are identical to those used in the previous experiments (Table I).

The reconstruction experiments are conducted at a target resolution of 128 × 128 pixels. Table II reports final performance for each image in terms of MSE (used as the optimization objective), along with PSNR and SSIM as complementary similarity metrics, and average execution times in seconds.

The numerical results presented in Table II highlight that the quality of the reconstruction produced by the GA is primarily influenced by the intrinsic characteristics of the target image. As previously reported in [6], images with high entropy or fine details, such as *Basic-Fit*, pose a greater challenge for accurate reconstruction than more homogeneous images like *Saturn*, which aligns with expectations. This observation is consistent with the results from Section IV-B2.

## C. Island Genetic Algorithm performance evaluation

1) *Migration parameters calibration:* We now turn to the evaluation of our parallel variant of the genetic algorithm, referred to as IMGA (Algorithm 2), based on the island model. Prior to assessing its performance, we conduct an experimental calibration of the algorithm-specific parameters: the migration
<figure><img src="image_3.png" /><figcaption>(a) Mario</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Mona Lisa</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Bibi & Lala</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(d) Saturn</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(e) Basic-Fit</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(a) MSE</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(b) PSNR</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(c) SSIM</figcaption></figure>

<caption>Fig. 3: Reconstructed images using the standard GA with MSE, PSNR, and SSIM as objective functions.</caption>

<table><caption>TABLE II: Quantitative performance of the GA at 128 × 128 pixels: average MSE, PSNR, SSIM, and execution time.</caption><thead><tr><th>Image</th><th>MSE</th><th>PSNR</th><th>SSIM</th><th>Time (s)</th></tr></thead><tbody><tr><td>Mario</td><td>812</td><td>19.1</td><td>0.901</td><td>822</td></tr><tr><td>Mona Lisa</td><td>256</td><td>24.1</td><td>0.928</td><td>826</td></tr><tr><td>Bibi & Lala</td><td>773</td><td>19.2</td><td>0.882</td><td>824</td></tr><tr><td>Saturn</td><td>168</td><td>25.9</td><td>0.971</td><td>782</td></tr><tr><td>Basic-Fit</td><td>1089</td><td>17.8</td><td>0.789</td><td>824</td></tr></tbody></table>

count *M* and the migration period *T*. To facilitate this calibration, we define the migration rate per generation *M*₁ as *M*₁ = *M*/*T*. This parameter represents the average number of individuals exchanged per generation. During calibration, we vary *M*₁ while incrementally increasing the migration period *T*, and compute the actual migration count *M* accordingly. For example, with *M*₁ = 4 and *T* = 3, the algorithm exchanges the 12 best and 12 worst individuals (i.e., 24 in total) every three generations between populations.

The experimental setup remains consistent with previous experiments, except that we now leverage 64 CPU cores per run with *K* = 64 islands, each maintaining a population of 100 individuals. All other GA parameters are identical to those reported in Table I. We perform the calibration on the reconstruction task of the *Bibi & Lala* image (Fig. 2c) at a resolution of 128 × 128 pixels. Table III presents the average final MSE values over ten independent runs of IMGA for various combinations of *M*₁ and *T*, where applicable. Execution times are not reported, as they were found to be similar across all configurations.

The results in Table III suggest that for optimization tasks requiring significant exploration such as the image reconstruction problem, frequent and substantial migration is beneficial.

<table><caption>TABLE III: Calibration of IMGA migration parameters: average final MSE for varying migration rates (*M*₁) and periods (*T*) on the *Bibi & Lala* image.</caption><thead><tr><th>T</th><th>M<sub>1</sub></th><th>4</th><th>8</th><th>12</th><th>16</th><th>20</th><th>24</th><th>28</th><th>32</th><th>36</th></tr></thead><tbody><tr><td>1</td><td></td><td>520</td><td>494</td><td>504</td><td>497</td><td>482</td><td>484</td><td>484</td><td>486</td><td>488</td></tr><tr><td>2</td><td></td><td>523</td><td>500</td><td>486</td><td>492</td><td>485</td><td>484</td><td></td><td></td><td></td></tr><tr><td>3</td><td></td><td>524</td><td>489</td><td>492</td><td>486</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td></td><td>525</td><td>499</td><td>490</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>5</td><td></td><td>527</td><td>499</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

In our experiments, the configuration *T* = 1 and *M*₁ = 20 (i.e., *M* = 20) appears as a solid choice for maximizing the solution quality achieved by our island genetic algorithm. This setup corresponds to exchanging 40% of each local population at every generation, promoting strong inter-island cooperation and diversity maintenance throughout the search.

2) Image reconstruction results: Having determined suitable migration parameters, we then evaluate the performance of our island genetic algorithm, IMGA (Algorithm 2), on the set of benchmark images shown in Fig. 2, each with a resolution of 128 × 128 pixels. This evaluation is conducted in comparison with the standard GA (Algorithm 1) baseline, presented earlier. Specifically, IMGA is executed to reconstruct each image using an increasing number of processes, corresponding to an increasing number of population islands, with *K* ∈ {2, 4, 8, 16, 32, 64}. For the migration parameters, we use *M* = 20 and *T* = 1. The remaining parameters are the same as those previously used and listed in Table I.

For each value of *K*, we compare the reconstruction performance in terms of MSE to the results obtained in Section IV-B3 with the standard GA using a single population (*K* = 1). The reported values in Table IV correspond to the average MSE over ten independent executions of IMGA. Table V presents the associated standard deviations (*sd*) of the MSE values, as well as the average execution times in seconds, averaged across the five benchmark images.

IMGA is implemented as an extension of our original GA code, using the Boost.MPI library [11] to manage inter-process communication. Migration-related data exchanges are handled asynchronously, allowing communication overhead to be effectively overlapped with the computational workload of the selection phase.

To better visualize the impact of the island model, Fig. 5a shows, for each island count *K*, the average relative improvement.
<figure><img src="image_11.png" /><figcaption>Fig. 4: Effect of the number of triangles on reconstruction quality (a) and execution time (b).</figcaption></figure>

<table><caption>TABLE IV: Effect of island count ($K$) on reconstruction MSE for the benchmark images using IMGA.</caption><thead><tr><th>Image</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th><th>64</th></tr></thead><tbody><tr><th>Mario</th><td>812</td><td>670</td><td>604</td><td>563</td><td>495</td><td>466</td><td>408</td></tr><tr><th>Mona Lisa</th><td>256</td><td>219</td><td>200</td><td>184</td><td>174</td><td>157</td><td>143</td></tr><tr><th>Bibi & Lala</th><td>773</td><td>670</td><td>611</td><td>582</td><td>545</td><td>507</td><td>482</td></tr><tr><th>Saturn</th><td>168</td><td>139</td><td>119</td><td>108</td><td>95</td><td>87</td><td>79</td></tr><tr><th>Basic-Fit</th><td>1089</td><td>986</td><td>950</td><td>886</td><td>828</td><td>796</td><td>772</td></tr></tbody></table>

<table><caption>TABLE V: Average MSE standard deviation and execution time across the benchmark images for IMGA with varying island counts.</caption><thead><tr><th>Islands</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th><th>64</th></tr></thead><tbody><tr><th>Average sd</th><td>29.5</td><td>23.5</td><td>23</td><td>26</td><td>28.1</td><td>17.3</td><td>17.1</td></tr><tr><th>Average time (s)</th><td>816</td><td>848</td><td>848</td><td>851</td><td>850</td><td>858</td><td>914</td></tr></tbody></table>

ment in solution quality. It is defined as

$$ \bar{f} = \frac{1}{5} \sum_{i=1}^{5} \frac{f_{K}^{i}}{f_{1}^{i}}, \qquad (6) $$

where $f_K^i$ denotes the MSE of the $i$-th reconstructed image using $K$ islands. Similarly, Fig. 5b depicts the average relative increase in computational cost, defined as

$$ \bar{t} = \frac{1}{5} \sum_{i=1}^{5} \frac{t_{K}^{i}}{t_{1}^{i}}, \qquad (7) $$

where $t_K^i$ represents the execution time for reconstructing the $i$-th image using $K$ islands.

To sum up, IMGA yields a substantial improvement in reconstruction quality. Compared to the standard genetic algorithm, it achieves up to a 43% average reduction in MSE, with a computational overhead of no more than 12% (Fig. 5a, Fig. 5b). Table IV further shows that for some images, notably *Mario* and *Saturn*, the improvement reaches about 50%, effectively doubling reconstruction quality. Moreover, Table V highlights that MSE variance drops markedly with

many islands, indicating greater robustness and consistency under the island model.

To further illustrate the qualitative benefits of the island model, Table VI provides a visual comparison between reconstructions produced by the usual GA and those obtained using IMGA with $K = 64$ islands. The reported images correspond to the best output, i.e., the reconstruction with the lowest MSE fitness, among the ten independent runs performed for each method. These examples highlight IMGA's ability to capture finer image details, such as the “M” on Mario's cap or the Mona Lisa's eyes.

3) *Scalability evaluation:* To further assess the reliability of IMGA (Algorithm 2), we evaluate its scalability by reconstructing images at increasing resolutions. Specifically, we test IMGA on the same benchmark set and with the same parameter configuration as in Section IV-C2, using $K = 64$ population islands and four target resolutions: 64×64, 128×128, 256×256, and 512×512 pixels.

Table VII reports the average MSE across ten independent runs for each benchmark image, while Table VIII presents the corresponding average execution times (in seconds), aggregated over the five images. The results confirm the negative effect of resolution on reconstruction accuracy: MSE values gradually increase as the resolution rises, though the degradation remains moderate. As observed earlier (Section IV-B3), the input image itself remains the dominant factor; for example, IMGA reconstructs *Mona Lisa* at 512 × 512 with substantially lower error than *Basic-Fit* at 64 × 64.

In contrast, computational cost is strongly resolution-dependent. Execution times grow roughly quadratically with resolution (i.e., linearly with the number of pixels), reaching over 16 000 seconds (~4.5 hours) for 512 × 512 images.

4) *Comparison with related work:* To conclude our evaluation, we compare the performance of our parallel island genetic algorithm IMGA (Algorithm 2) with the current state of the art for the triangle-based image reconstruction problem, as presented by Cavallaro et al. [6]. In their work, the authors proposed a hybrid approach, referred to as Genetic Algorithm with Machine Learning (GAML), that enhances a genetic
<figure><img src="image_12.png" /><figcaption>Fig. 5: Relative changes in reconstruction quality (a) and execution time (b) of IMGA compared to the baseline GA as the number of islands *K* increases.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>TABLE VI: Comparison of the benchmark image reconstructions (128 × 128 pixels) produced by the standard GA and IMGA (*K* = 64).</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>TABLE VII: Effect of image resolution on reconstruction MSE for the benchmark images using IMGA with *K* = 64 islands.</figcaption></figure>

<table><caption>TABLE VIII: Effect of image resolution on the average execution time of IMGA with *K* = 64 islands.</caption><thead><tr><th rowspan="2">Image</th><th colspan="4">Resolution</th></tr><tr><th>64 px</th><th>128 px</th><th>256 px</th><th>512 px</th></tr></thead><tbody><tr><td>Mario</td><td>323</td><td>408</td><td>463</td><td>444</td></tr><tr><td>Mona Lisa</td><td>117</td><td>143</td><td>191</td><td>279</td></tr><tr><td>Bibi & Lala</td><td>370</td><td>482</td><td>543</td><td>617</td></tr><tr><td>Saturn</td><td>48</td><td>79</td><td>117</td><td>176</td></tr><tr><td>Basic-Fit</td><td>436</td><td>772</td><td>1121</td><td>1389</td></tr></tbody></table>

<table><thead><tr><th>Resolution</th><th>64 px</th><th>128 px</th><th>256 px</th><th>512 px</th></tr></thead><tbody><tr><th>Average time (s)</th><td>353</td><td>914</td><td>3515</td><td>16419</td></tr></tbody></table>

algorithms using machine learning techniques based on linear regression. This approach enables dynamic adjustment of genetic operator parameters during execution. Their results showed that GAML significantly outperformed both their standard genetic algorithm baseline and the original method introduced by Wiransky [5], achieving superior reconstruction quality and reduced computational cost.

For a concrete comparison, we replicate the image reconstruction experiment conducted in [6], which focuses on reconstructing the 165 × 190 pixel portrait of *Mona Lisa* shown in Fig. 6a. In their setup, GAML was executed for 10 000 generations with a population size of 197, using *N* = 100 triangles and the MSE as the objective function. Our experiment adopts a similar configuration, detailed in Table IX, and applies it to IMGA with *K* = 64 population islands.

Fig. 6 presents a visual comparison between the reconstructions produced by GAML and by IMGA, while Table X provides a quantitative comparison using multiple similarity metrics, along with the respective execution times in seconds. It is important to note that execution times are reported only for indicative purposes, as the programming environments and hardware platforms differ between the two studies. Our results
are based on the average of ten independent IMGA runs, with the image shown in Fig. 6c corresponding to the best reconstruction obtained in terms of MSE fitness. Quantitatively, IMGA significantly outperforms GAML, particularly with respect to the MSE metric used as the optimization objective, achieving an improvement by a factor of nearly five in reconstruction fitness, as shown in Table X.

<table><caption>TABLE IX: Parameter configuration replicating GAML's setup for evaluating IMGA on the Mona Lisa image.</caption><thead><tr><td>Symbol</td><td>Description</td><td>Value</td></tr></thead><tbody><tr><td>G</td><td>number of generations</td><td>10 000</td></tr><tr><td>P</td><td>population size per island</td><td>196</td></tr><tr><td>Q</td><td>tournament selection size</td><td>40</td></tr><tr><td>N</td><td>number of triangles</td><td>100</td></tr><tr><td>R</td><td>number of triangle swaps</td><td>50</td></tr><tr><td>p<sub>m</sub></td><td>mutation probability</td><td>0.7</td></tr><tr><td>K</td><td>number of islands</td><td>64</td></tr><tr><td>M</td><td>migration count</td><td>40</td></tr><tr><td>T</td><td>migration period</td><td>1</td></tr><tr><td>f</td><td>objective function</td><td>MSE</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>Fig. 6: Mona Lisa portrait reconstructions: (a) target image, (b) GAML output [6], (c) IMGA output with 64 islands.</figcaption></figure>

<table><caption>TABLE X: Comparison of GAML and IMGA on the Mona Lisa reconstruction: similarity metrics and execution time.</caption><thead><tr><td></td><td>GAML</td><td>IMGA</td></tr></thead><tbody><tr><td>MSE</td><td>1378</td><td>281</td></tr><tr><td>PSNR</td><td>16.7</td><td>23.6</td></tr><tr><td>SSIM</td><td>0.522</td><td>0.946</td></tr><tr><td>Time (s)</td><td>7142</td><td>6487</td></tr></tbody></table>

## V. CONCLUSION AND FUTURE WORKS

This work has demonstrated the effectiveness of parallelism and, more specifically, the ability of the island model to improve the performance of genetic algorithms for complex optimization problems. Triangle-based image reconstruction provided a meaningful and visually interpretable benchmark to evaluate our parallel island genetic algorithm (IMGA). Extensive experimentation showed that IMGA offers significant improvements in both solution quality and robustness compared to a classical genetic algorithm, particularly when

emphasizing exploration through frequent and substantial migration processes.

By carefully calibrating migration parameters and leveraging large-scale parallelism, our approach achieved state-of-the-art performance while maintaining reasonable computational costs. In some cases, such as the reconstruction of structured images, the improvements in quality reached up to 50%, clearly illustrating the benefits of the proposed model.

Despite these advancements, the computational demands of genetic algorithms for this type of problem remain important, especially as image resolution increases. Future work could explore finer-grained parallelism such as iteration-level strategies to reduce execution times. Another promising direction would be the integration of adaptive data-driven techniques, such as those based on machine learning, into the island model framework. These could enable dynamic tuning of algorithmic parameters and further enhance solution quality.

## ACKNOWLEDGMENTS

Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations.

This work is partly supported by the French National Research Agency (ANR) through the UltraBO PRCI project (ANR-22-CE46-0011) and the PEPR IA program (ANR-23-PEIA-0002).

## REFERENCES

[1] El-Ghazali Talbi. *Metaheuristics: from design to implementation*. Wiley, 2009.

[2] Enrique Alba and José M. Troya. Analyzing synchronous and asynchronous parallel distributed genetic algorithms. *Future Generation Computer Systems*, 17(4), 2001.

[3] Wenbin He, Xian Tang, Wanwei Ji, Liju Meng, Jiachen Wei, Donghao Cao, Ciwen Ma, Qi Li, and Chuangting Lin. An improved multi-island genetic algorithm and its utilization in the optimal design of a micropositioning stage. *Expert Systems with Applications*, 2024.

[4] Tianxiang Shi, Miao Pang, Yangyang Wang, and Yongqiang Zhang. Inverse parameter identification framework for cohesive zone models based on multi-island genetic algorithm. *Engineering Fracture Mechanics*, 300, 2024.

[5] Eyal Wirsansky. *Hands-On Genetic Algorithms with Python: Apply genetic algorithms to solve real-world AI and machine learning problems*. Sciendo, 2024.

[6] Claudia Cavallaro, Vincenzo Cutello, Mario Pavone, and Francesco Zito. Machine learning and genetic algorithms: A case study on image reconstruction. *Knowledge-Based Systems*, 284, 2024.

[7] Umme Sara, Morium Akter, and Mohammad Shorif Uddin. Image quality assessment through FSIM, SSIM, MSE and PSNR: A comparative study. *Journal of Computer and Communications*, 7, 2019.

[8] Lourdes Araujo, Juan J. Merelo Guervos, Carlos Cotta, and Francisco Fernandez de Vega. MultiKulti Algorithm: Migrating the Most Different Genotypes in an Island Model, 2008.

[9] Alfian Gozali. DM-LIMGA: Dual Migration Localized Island Model Genetic Algorithm—a better diversity preserver island model. *Evolutionary Intelligence*, 12, 2019.

[10] Gary Bradski. The OpenCV library. *Dr. Dobb's Journal of Software Tools*, 2000.

[11] Douglas Gregor and Matthias Troyer. Boost.MPI library. In *Proceedings of the 18th ACM International Conference on Supercomputing (ICS'04)*. ACM, 2004.