Adaptive multi-strategy particle swarm optimization for solving NP-hard optimization problems

Abstract

Particle Swarm Optimization algorithm (PSO) has been widely utilized for addressing optimization problems due to its straightforward implementation and efficiency in tackling various test functions and engineering optimization problems. Nevertheless, PSO encounters issues like premature convergence and a lack of diversity, particularly when confronted with complex high-dimensional optimization tasks. In this study, we propose an enhanced version of the Island Model Particle Swarm Optimization (IMPSO), where island models are integrated into the PSO algorithm based on several migration strategies. The first contribution consists in applying a new selection and replacement strategies based on tabu search technique, while the second contribution consists in proposing a dynamic migration rate relying on the Biogeography-Based Optimization technique. To assess and validate the effectiveness of the proposed method, several unconstrained benchmark functions are applied. The obtained results confirm that the approach yield better performance than the old version of IMPSO for solving NP-hard optimization problems. Compared to the performance of other well-known evolutionary algorithms, the proposed approach is more efficient and effective.

Keywords

Island Model Particle Swarm Optimization Biogeography Based Optimization unconstrained optimization island model strategies tabu search

1. Introduction

Several evolutionary algorithms (EAs) are based on a population of candidates which are simulated a natural phenomena such as evolution and biology. They have attracted the research community thanks to their simplicity of mathematical modelling. From the most studied algorithms, the genetic algorithms (GA) are presented and are relied on mechanisms of selection, crossover and mutation to search for potential solutions [8]. Moreover, swarm intelligence algorithms, based on a group of agents in interaction, are able to optimize a problem through collaborative research. Evolutionary algorithms derive from the same source of inspiration applying different mechanisms to generate a new population. The difference among them can establish by adaptation to the treated optimization problem (continuous, discrete), likewise EA do not utilize the same concepts to evolve. Swarm intelligence algorithms can be distinguished by the movement of its agents in the search space according to the type of inspiration system (terrestrial, aquatic, micro-organism) [23]. In this context, the particle swarm optimization method (PSO) is characterized by a global and self-organized collective behavior. Firstly, the efficiency of PSO compared to other evolutionary algorithms lies essentially in the stability and adaptability of the swarm which is based on the particle displacements during the search process [7]. For example, the population generation in the GA can provide fluctualisations, during the selection of new descendants, caused by the elimination of certain individuals. However, the population of the artificial bee colony algorithm (ABC) are presented by three families [16]: workers, spectator bees and scout bees, which the interaction among them depend on a setting of parameters quite tricky [15]. Further, the population generation of the cuckoo search algorithm (CS) is based on reproducing new agents in terms of the current state of existing agents and Levy flight mechanism and also on the selection between these agents in order to survive [31, 12]. Its difficulty remains in the choice of the Levy flight strategy [11]. By imitating the social interaction behaviours of bird flocking and fish schooling, PSO was proposed [18], it is based on the interaction between particles to find the best solution. Because of its easy implementation and variety of applications in optimization problems [13], such as continuous, discrete and engineering problems [13], PSO has attracted the attention of the research community [6]. However, PSO has the ability to quickly converge, which can lead to stagnation at local optima. Besides, it does not explore the whole search space, especially in the case of solving optimization problems that have large dimensionality [10, 32, 30]. To improve this algorithm, many hybrid techniques and models, such as the island model, were introduced.

The main contributions of this study can be summarized as follows:

•
The improved IMPSO approach integrates IM techniques. The migration process is triggered after certain number of iterations. Different types of communication topologies among the sub-swarms with various numbers of islands are employed to explore the search space.
•
To enhance island model strategies, a dynamic migration rate is applied based on the migration strategy derived from the Biogeography-Based Optimization algorithm.
•
An innovative selection and replacement technique is adopted. It utilizes a tabu list to store the emigrant particles. Particles with a history of improvements are prioritized for selection to migrate to neighboring islands, while particles with a less favorable history are more likely to be replaced in the migration process.

This paper is divided into three sections:

The first section is dedicated to the background of the used methods, the particle swarm optimization, the island model, the tabu research and the Biogeography-Based Optimization. On the other, the second section focuses on the hybridization between the island model and some evolutionary algorithms such as genetic programming and cuckoo search. The third section defines our contributions to improve IMPSO. In the proposed approach, the BBO algorithm is used to make the migration rate work dynamically. Then, other selection and replacement strategies based on the tabu search are presented. After that, the different steps of the introduced approach escorted by its pseudo-code and its model are described. The fourth section is concerned our approach is validated using the CEC05 benchmark as continuous optimization problems. Subsequently, the obtained results of proposed approach are presented and are compared with other evolutionary algorithms.
2. Related works

2.1 Mono-objective optimization

The optimization problem can be formulated by an objective function to be optimized and a set of equality and inequality constraints to be met simultaneously:

Minimize $f(x)$ Subject to $g(x)\leqslant 0$ ( $m$ inequality constrained) $h(x)=0$ ( $p$ equality constrained) with $x\in R^{n}$ , $g(x)\in R^{m}$ , $h(x)\in R^{p}$

Where $f(x)$ is the objective function and $g(x)$ and $h(x)$ vectors represent respectively $m$ inequality constraints and $p$ equality constraints.

2.2 PSO algorithm

The PSO is based on a population of candidate solutions called a swarm including candidate solutions or particles. In PSO, every particle, having a position in the search space, is a potential solution to the considered optimization problem. This space includes the set of all possible solutions to the optimization problem.

Each particle has a position and a velocity. The position $X_{i}(t)\in X:t$ represents the current iteration in the algorithm. The velocity $V_{i}(t)$ : denotes the movement of the particle in the sense of direction, distance and step size. Therefore, a particle, located in its position $X_{i}(t)$ , moves, at a time step, towards a vector $V_{i}(t)$ .

The particles interact and learn from each other, following the same simple rules, to find the best solution for the optimization problem. In addition to position and velocity, every particle has a memory that saves its best position. Thus, the movement of each member of the swarm is influenced by its personal experience and by the experience of its neighbours. In fact, the PSO algorithm records the common best experience among all the members of the swarm. This experience is called the global best.

In each iteration of PSO, the position and the velocity of each particle are updated according to this simple mechanism:

The particle moves towards the new position. It uses two components: the velocity and the previous position. The new velocity is created according to the previous velocity, personal best, and global best.

The mathematical model is described for the velocity and postion updating as follows:

$\displaystyle V_{i}(t+1)=W*V_{i}(t)+C_{1}*(P_{i}-X_{i}(t))+C_{2}*(G(t)-X_{i}(t))$ (1)

•

$C_{1}*(P_{i}-X_{i}(t))$ : personal influence.

•

$C_{2}*(G(t)-X_{i}(t))$ : social influence.

•

$C_{1}$ and $C_{2}$ are two real random variables between [0, 1].

$\displaystyle X_{i}(t+1)=X_{i}(t)+V_{i}(t+1)$ (2)

For each iteration, the position of the particle is updated according to its previous position and current velocity. The velocity of each particle is also changed according to its personal information which is the best position found during its search and the best position found by the whole swarm. Furthermore, $C_{1}$ and $C_{2}$ are two learning factors. The former controls the personal behaviour of the particle, while the latter $C_{2}$ controls its social behaviour.

2.3 Island model

The first studies based on the island model apply the genetic algorithms [27]. It has been proved that the strategies of island models can enhance remarkably the GA equilibrium between exploration and exploitation in the search space. Nowadays, the IM successfully used in other evolutionary algorithms such as PSO and cuckoo search algorithms [5].

The IM divides the population into subpopulations called islands; each of which finds, in the first step, works to find the best solution among its group of solutions. In the next step, it compares its result with those provided by other islands and replaces its least optimal solution by the best one obtained by its neighbours. Indeed, the IM has specific parameters used to select the candidate solutions in an island. Then, it applies a defined strategy (depending on the topology) to send solutions between two or more islands. However, the most strategy of IM is how the islands cooperate to find the optimum solution. Additionally, in the IM, migration, which is the exchange of solutions between the islands, helps the island get new information from its neighbours, compare it with its data and, finally, update its value if needed.

•
Characteristics of IM

The island model strategy employs specific parameters: the number of islands, migration topology (the structure of interaction between the islands), migratory frequency (the number of migration occurrences), migratory rate (the ratio of migration between the islands), the type of migration (synchronous or asynchronous), the policy of migration (defines which individuals will be replaced from an island and changed during migration) and migratory flow ( the trajectory that emigrants follow).
•
Migration topologies

The migration topology establishes the communication links between the islands. It influences the final result of the algorithm. It can be static or dynamic [21].

2.4 Tabu search

The tabu search is an optimization method based on the history of search [26]. In fact, it has a memory called a tabu list where the last found solutions to which it refused to move are collected. The role of this memory is to allow choosing the best non-tabu neighbour. In the introduced approach, the tabu search is used to save the already sent solutions in order to avoid forwarding them again. Indeed, it depends on the tabu list length because, if the tabu list becomes full in the next iteration, the algorithm will revoke the tabu status from the first saved element on the list (i.e., remove it from the tabu list) and the new element will be saved in the last tabu position.

2.5 Biogeography based optimization

Biogeography is a science inspired from nature. It appeared since 1960 to analyse the geographical distribution of biological organisms. Besides, biogeography applications can be utilized to solve the optimization problems. Precisely, the BBO is a method inspired from the mathematics of biogeography [28]. In fact, the mathematical biogeography models explain the migration of species from one island to another, the development of new species and the disappearance of other ones. In the BBO, an island is any habitat separated geographically from the other similar regions.

In the biogeography, the fitness of each island is determined by their high suitability index (HIS), a measure of the quality of a candidate solution. Each island is represented by Suitability Index Variables (SIV). The best solution for the optimization problem is an island with a low number of species, which corresponds to an island with a large HSI.

The number of species existing on an island depends on the balance between the immigration rate of the new species and that of species already established on the island. In BBO, each habitat has its immigration rate $(\lambda)$ , arrivals from outside and its emigration rate $(\mu)$ and its leaving outward. These parameters are influenced by the number of species (S) present on the island. The immigration rate $(\lambda)$ reduces with the rise in the number of species (S) already surviving on the island. As the number of species already located on the island rises, that of the immigrants belonging to new species decreases. The maximum immigration rate (I) occurs when the island is empty. If all species are present on the island, then $S=\textit{Smax}$ (maximum capacity of the island) and the immigration rate drops to zero, which prevents the settlement of newcomers [22]. In the BBO, the immigration rate $(\lambda)$ depends on three things:

•
The maximum immigration rate I which is a constant value,
•
The island size S,
•
The swarm size SMAX is a user-defined parameter.

$\displaystyle\lambda=I(1-S/\textit{SMAX})$ (3)

The emigration rate $(\mu)$ increases with the number of species (S) located on the island. The maximum emigration rate (E) is obtained when all species are present on the island $(S=\textit{Smax})$ . However, it is equal to zero if the species present on the island extinct (or leave the island). The emigration rate obtained when there are S species on the island is given by:

$\displaystyle\mu=E(S/\textit{SMAX})$ (4)
2.6 Recent PSO variants

While the performance of PSO has seen significant enhancements in recent years, it still possesses certain limitations. Like other Evolutionary Algorithms (EAs), this algorithm suffers from premature convergence because of the lack of diversity. To enhance its search performance, several PSO variants have been introduced. A dynamic neighbourhood-based switching PSO was developed, using a new velocity updating scheme relying on the adjustment of pbest and gbest in terms of a distance-based dynamic neighbourhood, in order to use all swarm evolution information [32]. To resolve the premature convergence of PSO algorithm, Tolabi et al. integrated different strategies including the division of the search space to find the promote zone, and the use of a probabilistic function to manipulate the inadequate particles [6]. PSO with aging leader and challengers (ALC-PSO) was developed in [9]. In ALC-PSO, the swarm’s leader possesses a lifespan that can be tailored by adjusting its leading power, with stronger leading power resulting in a longer leader lifespan. Meanwhile, other particles in the swarm, known as challengers, have the opportunity to assume leadership once the current leader has aged. If the leader maintains a high leading power, it continues to attract other particles; otherwise, new particles are allowed to compete for leadership. A modified PSO approach is develepped using adaptative strategies [20]. In the MPSO algorithm, a non-linear inertia weight based on chaos theory is introduced to effectively harmonize global exploration and local exploitation within PSO. Also stochastic and mainstream learning strategies are adopted to mitigate premature convergence.

2.7 The hybridization between island model and the evolutionary algorithms

2.7.1 Improvement of the island genetic programming

Genetic programming (GP) is considered as one of the most successful evolutionary computation algorithms [19]. Its initialized variables are represented under the form of a tree. In fact, it uses the same techniques as the genetic algorithm (crossover, mutation and selection). It has been used in several domains such as robotic, electrical engineering [14] and other image processing algorithms (e.g., image filtration) [17]. Nevertheless, GP has some weaknesses in terms of premature convergence to the local minimum. Therefore, to improve it, island model genetic programming based on frequent trees IMGP was proposed [24]. In this algorithm, the initialized possible solutions (or populations) were divided into sub-populations (or islands); each of which used the GP to calculate the fitness of its population. Then, it applied the migration strategy to exchange the information (random topology has shown the best migration strategy performance [24]). Moreover, this algorithm can be also enhanced by controlling the frequent tree and the local search [25].

2.7.2 Improvement of the island cuckoo search

CS is a metaheuristic algorithm that simulates how the cuckoo birds deal with their eggs by leaving them in other birds’ nests to grow their chance of survival. In short, there are two kinds of birds (cuckoo and host). The host birds either figure out the different eggs. At this point, the host bird must choose between throwing the egg away or leaving the nest and building a new one. Moreover, CS simulates the levy flight which is a random method that mimics the behaviours of some birds. It is used to select the arbitrary values [3]. For this reason, Island-based Cuckoo Search with Highly Disruptive Polynomial Mutation [5] was proposed to improve the CS algorithm by dividing the CS population into sub-populations and by replacing the levy flight method with another strategy called a polynomial mutation. Moreover, this hybridization provided better results, compared to the CS algorithm.

2.7.3 Improvement of the island particle swarm optimization

IMPSO is an algorithm proposed by [4]. It is based on the hybridization between the PSO algorithm and the island model strategy. The approach starts by dividing the whole swarm into sub-swarms and the IM’s parameters, such as the number of islands (number of sub-swarms), the island size and the arbitrary position and velocity of each particle, are initialized. In fact, the IMPSO calculates the fitness value of each particle. Then, it extracts the best position in all islands. Indeed, at each iteration, there is a new position computed for each particle. Subsequently, the algorithm compares this position with the personal best position. If the new calculated position (called $X_{n}$ ) is better than the old one (called $X_{o}$ ), Xn will take the place of $X_{o}$ . Then, the same operation is repeated between the $X_{n}$ and the global best position $G_{x}$ . If the position $X_{n}$ is better than the position $G_{x}$ , $G_{x}$ will be updated. The next step is the selection of the migration topology (ring, star or torus) that allows the current island to communicate with the other islands in order to enhance the solution of the connected islands (neighbours).

Other integrated strategies of IM are presented as below:

•
Migration rate: It represents the rate of the emigrant particles.
•
Selection strategy: It is the method used to select the emigrant particles. There are many ways to select those particles. The most popular strategy considers the best particles of the current island (according to their fitness) and sends them to the neighbouring islands following the migration topology.
•
Replacement strategy: After the selection step and the migration of the best particles toward the neighbouring islands, a replacement strategy should be applied to substitute some particles in the current island by the emigrant particles. As instance of these strategies, we can mention the replacement of the worst particles by the emigrant particles.

3. Approach

As stated previously, the island model particle swarm optimization algorithm (IMPSO) is a hybrid method combining the PSO and IM. This hybridization was established to improve the performance of the PSO by avoiding some of its weaknesses such as the premature convergence, which can lead to stagnation in local optima, and the lack of exploration in the search space, especially in the case of solving large-scale optimization problems. The IMPSO starts by dividing the population into sub-populations (islands) including a set of particles and having a position (a possible solution) in the search space and a memory to save its best-found position. Later, each island works alone to generate new solutions. In fact, the global algorithm has a variable called Gbest belonging to the whole algorithm to save the global best position. At the end of the search process, the algorithm changes the value of Gbest according to the best solution of the islands. In the migration step, every island communicates with its neighbours following a migration topology (chain, ring or torus), to improve its group by replacing its worst particles by emigrant particles collected from the neighbouring islands. This process depends on two major issues. The first one is the selection strategy applied to select the best current island solutions and send them to its neighbours. The second issue is the replacement of the worst solutions with the best sent ones. The migration policy uses another parameter, called rate, used to define the rate of the emigrant particles. The application of the proposed approach can be divided into two steps:

•
Establishing a dynamically migration rate by using the immigration strategy of the Biogeography Based Optimization (BBO).

Figure 1.
The first priority: Improvement-improvement selection.

Figure 2.
The second priority: Improvement-equality selection.

Figure 3.
The third priority: Equality-improvement selection.

Figure 4.
The fourth priority: Equality-equality selection.

Figure 5.
The first priority: Worst-worst replacement.

•
Applying a new selection and replacement strategies, depending on the history search of the particles: particles having an improvement history are more likely to be selected to emigrate to neighbours and particles having a bad history are more likely to be replaced during the migration process.

The Biogeography Based Optimization BBO, the tabu search algorithm and how their principles are integrated and presented in IMPSO approach. For the selection strategy, four priorities are proposed for choosing the immigrant solution (Figs 1–4). For the replacement strategy as well, three priorities are adapted (Figs 5–7).

Figure 6.
The second priority: Worst-equality replacement.

Figure 7.
The third priority: Equality-worst replacement.

Figure 8.
Improved IMPSO flowchart.

The Algorithm 1 and Fig. 8 illustrate the new version of IMPSO starting by initializing, first, the objective function and the decision variables (the problem to solve) and, then, the parameters of the IMPSO algorithm (swarm size, number of iterations, number of islands and migration topology).

: Island Model Particle Swarm Optimization Algorithm: the proposed approach

Input: The optimization problem Initialize the IMPSO parameters (the number of islands, the number of iterations, the migration strategy (topology), the tabu list size). $i=1$ to iteration number Initialize the parameters and the size of each island. Initialize the velocity and random position of the particles in each dimension of the search space. Calculate $f(x_{i})$ of each particle. Calculate the global best position by computing the position of all particles. the stopping criteria is not satisfied i ranging from 1 to iteration number Calculate the new velocity of each particle. Find the new position of each particle. Calculate $f(x_{i})$ of each particle. $(f(x_{i})$ is better than $f$ (the best position)) best position $=x_{i}$ ( $f(\textit{best position})$ is better than $f(\textit{global best position})$ ) $\textit{Global best}=\textit{best position}$ (migration frequency occurs ) Update (PSO $=I_{1},I_{2}\ldots,I_{n}$ ) every island ( $I_{J}\in I_{1},I_{2}\ldots,I_{n}$ ) Calculate the migration rate of each island. Select the best particles according to the strategy of the emigration to neighbours (based on history). Verify the existence of each received emigrant in the tabu list. emigrant does not exist in the tabu list Replace the worst particle in the current island by the received emigrant and add emigrant to the tabu list. $\textit{Iteration}=\textit{Iteration}+1$ Collect the best solutions for each island in the topology. Output: The best-found solution and its objective function value
4. Results and discussions

4.1 The benchmark functions

To validate the proposed approach, 25 test functions, representing the collection of benchmark functions of IEEE-CEC2005 [29] and having different properties (from F1 to F25),were chosen. These benchmark functions are separable and the rotated ones contain a large number of local minima. They can be divided into four groups defined below:

•
The first five functions (from F1 to F5) represent the unimodal and shifted functions.
•
The next seven functions (from F6 to F12) represent the basic multimodal and shifted functions.
•
The next two functions ( F13 and F14) represent the expanded multimodal functions.
•
The next eleven functions (from F15 to F25) represent the hybrid composition functions.

4.2 Parameters analysis

The CEC competition has a set of priorities and conditions that should be respected. Among these properties, the number of runs must be 25; it means each result is a sum of 25 executions divided by 25, which provides an average of 25 runs. where the average error rate $=$ theaverage of the error $|f(x*)-f(\textit{found solution})|$ over the 25 runs while $x*$ represents the optimum solution. The worst value means the biggest found value(the maximum), while the best value means the lowest obtained result (the minimum). For each function, 3 scenarios were applied by varying the number of islands ( $I_{n}=\{4,8,10\}$ ): the same scenarios of the initial IMPSO was followed in order to compare it with that applied in the proposed approach. The same parameters utilized in the initial IMPSO (the swarm size (80 individuals) and the number of iterations ( $\mu=$ 500 iterations) were also used in the approach developed in the current work.

4.2.1 IMPSO the initial version versus the approach

In this part, we compare the obtained results with those given by the initial version of the IMPSO in order to evaluate the performance of the algorithm. Tables 1–3 show the comparison of the average error rate among the new and old version of IMPSO using the chain, ring and torus topology. Eval refers to the evaluation of the introduced approach compared to the original IMPSO; it contains ( $+$ ) in the case of improvement and ( $-$ ) in the other case.

Table 1
Average error rate obtained by IMPSO using chain topology

Test functions	Old IMPSO	New IMPSO	Eval	Old IMPSO	New IMPSO	Eval	Old IMPSO	New IMPSO	Eval
	Case 1: $I_{n}=4$			Case 2: $I_{n}=8$			Case 3: $I_{n}=10$
F1	4.63E-07	4,85E-08	$+$	0,00E00	1,23E-04	$-$	0,00E00	3,98E-05	$-$
F2	1.14E-09	8,09E-09	$-$	0,00E00	1,56E-07	$-$	9.94E-09	0,00E00	$+$
F3	1.46E-09	0,00E00	$+$	1.12E-09	0,00E00	$+$	1.63E-09	0,00E00	$+$
F4	1.82E-005	7,22E-08	$+$	0.0	1,74E-07	$-$	0.0	7,20E-08	$-$
F5	4.32E-02	5,27E-03	$+$	3.05E-03	5,39E-03	$-$	3.95E-01	5,35E-03	$+$
F6	4.32E-002	0,00E00	$+$	1.23E-10	0,00E00	$+$	1.51E-11	0,00E00	$+$
F7	4.32E-002	5,27E-03	$+$	3.05E-03	5,39E-03	$-$	3.95E-01	5,29E-03	$+$
F8	2.11E+01	2,09E01	$+$	1.92E+01	2,10E01	$-$	2.00E+01	2,10E01	$-$
F9	1.12E-01	2,79E-08	$+$	1.23E-01	1,04E-06	$+$	2.30E-01	8,69E-07	$+$
F10	1.69E+00	1,04E-02	$+$	1.73E+00	9,28E-02	$+$	1.27E+00	5,77E-02	$+$
F11	1.69E+00	9,13E-03	$+$	2.91E-02	7,80E-02	$-$	2,86E-02	4,39E-02	$-$
F12	9.99E-001	1,34E-07	$+$	9.17E-01	1,68E-07	$+$	8.88E-001	1,12E-05	$+$
F13	1.55E+00	3,90E00	$-$	1.19E+00	4,19E00	$-$	1.24E+00	4,12E00	$-$
F14	3.87E+00	2,14E-02	$+$	1.19E+00	8,25E-02	$+$	3.45E+00	6,17E-02	$+$
F15	8.32E+00	1,63E00	$+$	4.88E+00	2,43E00	$+$	4.82E+00	1,93E00	$+$
F16	2.72E+00	7,91E-04	$+$	2.47E+00	1,92E00	$+$	2.41E+00	2,20E00	$+$
F17	4.22E+00	2,11E00	$+$	3.65E+00	1,21E00	$+$	3.79E+00	8,51E-01	$+$
F18	1.47E-07	1,13E-08	$+$	5.18E-08	1,43E-08	$+$	4.91E-08	1,36E-08	$+$
F19	1.23E-06	1,92E-04	$-$	1.15E-05	1,06E-04	$-$	1.67E-057	1,50E-04	$-$
F20	6.25E-07	1,08E-08	$+$	5.34E-08	1,23E-08	$+$	5.44E-08	1,03E-08	$+$
F21	2.15E-06	1,50E-06	$+$	4.28E-07	1,54E-06	$-$	1.99E-07	1,23E-06	$-$
F22	1.21E+01	3,55E00	$-$	7.56E+01	2,28E01	$+$	7.86E+01	3,92E01	$+$
F23	3.37E+00	1,97E00	$+$	1.78E+00	1,52E00	$+$	2.28E+00	1,42E00	$+$
F24	3.37E+00	1,08E00	$+$	9.47E-01	1,27E00	$-$	9.55E-01	1,66E00	$-$
F25	2.49E+01	1,84E01	$+$	1.98E+01	1,93E01	$+$	1.92E+01	2,14E01	$-$

Figure 9.

Convergence rate obtained by IMPSO algorithms using chain topology.

In the chain topology, 21 out of 25 functions showed a remarkable positive improvement in the first demonstration, against14 out of 25 positive improvements, in the second demonstration, and 16 from 25 positive improvements in the third demonstration. It was also obvious that the difference between the two approaches was too small in the negative improvements.

Figure 9 illustrates the difference between the initial and the new versions of IMPSO in terms of convergence rate. Each one represents the best-found result (best average error rate) in the three demonstrations based on the chain topology. The sum of the old error rate $=$ 6,99E+01 and the sum of the new error rate $=$ 5,18E+01 reveal that the error rate provided by the introduced approach is inferior to that given by the old version.

Table 2

Average error rate obtained by IMPSO using ring topology

Test functions	Old IMPSO	New IMPSO	Eval	Old IMPSO	New IMPSO	Eval	Old IMPSO	New IMPSO	Eval
	Case 1: $I_{n}=4$			Case 2: $I_{n}=8$			Case 3: $I_{n}=10$
F1	1.12E-014	1,33E-008	$-$	0,00E+000	1,16E-007	$-$	0,00E+000	5,05E-006	$-$
F2	0,00E+000	2,30E-007	$-$	0,00E+000	2,84E-010	$-$	1.11E-009	2,34E-006	$-$
F3	1.34E-009	0,00E+000	$+$	1.31E-009	0,00E+000	$+$	1.27E-009	0,00E+000	$+$
F4	1.26E-009	3,51E-009	$-$	0,00E+000	9,65E-007	$-$	0,00E+000	3,35E-007	$-$
F5	3.57E-002	4,97E-003	$+$	3.1E-003	5,26E-003	$-$	2.85E-001	5,40E-003	$+$
F6	1.36E-009	0,00E+000	$+$	1.42E-011	0,00E000	$+$	1.56E-011	0,00E+000	$+$
F7	3.57E-002	5,13E-003	$+$	3.1E-003	5,22E-003	$-$	2.85E-001	5,38E-003	$+$
F8	2.01E+001	2,08E+001	$-$	2.00E+001	2,08E+001	$-$	1.89E+001	2,10E+001	$-$
F9	1.22E-001	3,34E-008	$+$	1.02E-001	5,32E-008	$+$	2.57E-001	6,44E-007	$+$
F10	1.14E+000	7,05E-010	$+$	1.68E+000	4,45E-006	$+$	2.57E-001	5,66E-002	$+$
F11	2.74E-001	2,77E-003	$+$	2.87E-002	9,50E-003	$+$	2.54E-002	8,53E-002	$-$
F12	8.79E-001	3,69E-008	$+$	8.21E-001	3,50E-007	$+$	8.90E-001	1,30E-005	$+$
F13	1.61E+000	3,89E+000	$-$	1.01E+000	3,98E+000	$-$	1.17E+000	3,96E+000	$-$
F14	3.24E+000	4,86E-004	$+$	2.2E+000	3,10E-007	$+$	2.43E+000	9,78E-004	$+$
F15	5.67E+000	2,70E-002	$+$	4.75E+000	3,50E-004	$+$	4.53E+000	4,74E+000	$-$
F16	2.68E+000	6,63E-001	$+$	2.41E+000	1,24E-003	$+$	2.37E+000	2,16E-001	$+$
F17	3.55E+000	1,19E+000	$+$	3.69E+000	1,72E+000	$+$	3.75E+000	1,85E+000	$+$
F18	5.5E-008	1,25E-008	$+$	4.76E-008	1,42E-008	$+$	4.81E-008	1,36E-008	$+$
F19	1.81E-006	1,20E-004	$-$	1.34E-006	1,72E-004	$-$	1.54E-006	1,35E-004	$-$
F20	5.19E-007	1,80E-008	$+$	5.26E-008	1,41E-008	$+$	5.57E-008	1,47E-008	$+$
F21	2.07E-006	1,18E-006	$+$	2.00E-007	1,32E-006	$-$	1.95E-007	1,29E-006	$-$
F22	3.47E+001	2,23E+001	$+$	6.89E+001	5,47E+001	$+$	7.01E+001	5,41E+001	$+$
F23	3.23E+000	1,31E000	$+$	2.11E+000	1,51E+000	$+$	2.00E+000	1,50E+000	$+$
F24	9.84E-001	1,02E000	$-$	9.76E-001	1,38E+000	$-$	9.45E-001	1,60E+000	$-$
F25	9.84E-001	2,11E001	$-$	1.89E+001	2,45E+001	$-$	1.95E+001	2,38E+001	$-$

In the ring topology, 17 functions out of 25 demonstrated considerable positive improvement in the first demonstration, against 16 out of 25 positive improvements, in the second demonstration, and 16 out of 25 positive improvements in the third demonstration. It is worth to note that the difference between the two approaches was too small in the negative improvements.

Figure 10.

Convergence rate obtained by IMPSO algorithms ring topology.

Figure 10 illustrates the difference between the initial version of IMPSO and the new one. Each result represents the best-found result (best average error rate) among the three demonstrations in the ring topology. From the sum of the old error rate $=$ 9,12E+01 and the sum of the new error rate $=$ 7,16E+01, we notice that the suggested approach gave less error rate than the old version.

Table 3

Comparison of the average error rate between new and old IMPSO using the torus topology

Test functions	Old IMPSO	New IMPSO	Eval	Old IMPSO	New IMPSO	Eval	Old IMPSO	New IMPSO	Eval
	Case 1: $I_{n}=4$			Case 2: $I_{n}=8$			Case 3: $I_{n}=10$
F1	1.63E-09	6,01E-09	$-$	0,00E00	6,88E-05	$-$	0,00E00	8,57E-0	$-$
F2	1.14E-09	4,58E-09	$-$	0,00E00	6,21E-067	$-$	0,00E00	9,70E-06	$-$
F3	1.46E-09	0,00E00	$+$	1.12E-09	0,00E00	$+$	1.63E-09	0,00E00	$+$
F4	1.00E-009	4,10E-08	$-$	0,00E00	7,48E-06	$-$	0.0	3,18E-07	$-$
F5	4.21E-02	4,99E-03	$+$	3.45E-03	5,38E-03	$-$	3.83E-03	4,98E-03	$-$
F6	1.14E-009	0,00E00	$+$	1.23E-10	0,00E00	$+$	1.51E-11	0,00E00	$+$
F7	4.21E-002	5,37E-03	$+$	3.45E-003	5,10E-03	$+$	3.83E-003	5,29E-03	$-$
F8	2.1E+01	2,09E01	$+$	2.01E+01	2,08E01	$-$	2.00E+01	2,10E01	$-$
F9	1.22E-01	5,98E-09	$+$	1.19E-01	3,34E-07	$+$	2.26E-01	6,00E-07	$+$
F10	1.57E+00	2,38E-07	$+$	1.88E+00	74,36E-01	$+$	1.36E+00	1,12E01	$+$
F11	2.87E-02	2,93E-03	$+$	2.78E-02	1,00E-02	$+$	2.8E-02	1,70E-02	$+$
F12	9.84E-001	3,49E-06	$+$	9.22E-001	1,38E-06	$+$	8.98E-001	8,14E-07	$+$
F13	1.67E+00	3,90E00	$-$	1.25E+00	3,96E00	$-$	1.29E+00	4,04E00	$-$
F14	3.91E+00	9,52E-04	$+$	2.88E+00	1,89E-03	$+$	3.23E+00	4,68E-02	$+$
F15	8.32E+000	2,20E00	$+$	5.64E+000	4,61E00	$+$	5.37E+000	7,15E00	$-$
F16	2.78E+000	3,73E00	$+$	2.54E+000	2,89E-02	$+$	2.49E+000	2,04E00	$+$
F17	4.02E+000	3,57E-01	$+$	3.64E+000	7,24E-01	$+$	3.55E+000	9,73E-01	$+$
F18	5.92E-008	5,70E-08	$+$	5.81E-008	1,44E-08	$+$	4.97E-008	1,59E-08	$+$
F19	1.63E-004	1,08E-04	$-$	1.38E-004	1,30E-04	$+$	1.4E-004	1,64E-04	$-$
F20	6.25E-008	1,24E-08	$+$	5.12E-008	1,63E-08	$+$	4.89E-008	1,49E-08	$+$
F21	2.56E-006	2,06-E06	$+$	3.51E-007	2,85E-07	$+$	2.23E-007	1,09E-06	$-$
F22	1.36E+001	1,85E01	$-$	6.74E+001	5,21E01	$+$	6.81E+001	3,13E01	$+$
F23	2.76E+000	1,41E00	$+$	2.21E+000	1,69E00	$+$	2.46E+000	1,64E00	$+$
F24	9.96E-001	9,71E-01	$+$	9.52E-001	1,48E00	$-$	9.88E-001	1,41E00	$-$
F25	2.52E+001	2,12E01	$+$	2.53E+001	1,87E01	$+$	1.99E+001	2,18E01	$-$

In the torus topology, 19 out of 25 functions exhibited a positive improvement in the first demonstration, against 19 out of10 positive improvements, in the second demonstration, and 13 out of 25 positive improvements in the third demonstration. Besides, we notice that the difference between the two approaches was too small in the negative improvements.

Figure 11.

Convergence rate obtained by IMPSO algorithms torus topology.

Figure 11 illustrates the difference between the initial version of IMPSO and the new one in terms of the convergence rate. It represents the best-found result (best average error rate) among the three demonstrations in the torus topology. The sum of the old error rate $=$ 7,46E+01 and the sum of the new error rate $=$ 6,69E+01reveal that our approach gets less error rate than the old version.

From the above-presented findings, we may deduce that our approach gave better results than the initial IMPSO because, in most cases, it provided more positive improvement in terms of the best average error rate Indeed, in the negative improvement, the difference between the two approaches was too small. It is also clear that, in the three topologies, the developed approach did not provide acceptable result in function f8, which is the same problem found in the initial version of IMPSO. Besides, in the function f15, an interesting improvement was observed, especially in the first demonstration with the chain topology, and the sum of the best average error rate in the three topologies provided by the new version was less than that given by the old version.

The new IMPSO algorithm has demonstrated its effectiveness by achieving the best convergence rates when utilizing various migration topologies (chain, ring, and torus). In fact, new IMPSO attains the lowest average error rates for the majority of multimodal optimization problems. The diverse migration topologies employed facilitate significant movement of solution migrants between different islands, promoting thorough exploration of the search space.

4.2.2 Comparison with other evolutionary algorithms

Table 4
Comparison of the average error rate between new and old IMPSO using the torus topology

Test functions	New IMPSO	SPSO’11	GA	ABC	CS
F1	1,33E-008	3.26E-001	1.31E-005	0.00E+000	7.60E-03
F2	2,30E-007	2.34E-008	1.76E-008	0.00E+00	9.55E-03
F3	0,00E+000	1.47E-001	1.21E+001	2.20E+05	2.17E+06
F4	3,51E-009	1.13E-005	1.37E-008	2.20E+05	1.40E+03
F5	4,97E-003	1.21E-005	3.47E-005	6.02E+03	2.98E+03
F6	0,00E+000	1.55E-006	1.79E+000	1.38E+02	1.78E+01
F7	5,13E-003	4.21E-004	1.92E-001	1.05E+	2.74E-04
F8	2,08E+001	2.01E+001	20.85E+001	2.09E+01	2.09E+01
F9	3,34E-008	9.27E-007	2.96E-001	6.60E+01	2.56E+01
F10	7,05E-010	2.78E+000	5.30E+000	2.01E+02	1.63E+02
F11	2,77E-003	2.54E+001	1.97E+000	3.56E+01	2.93E+01
F12	3,69E-008	1.67+000	2.53E+001	9.55E+04	1.84E+04
F13	3,89E+000	1. 95E-001	4.28E-001	1.07E+01	5.91E+00
F14	4,86E-004	3.37E+000	3.25E+000	1.36E+01	1.29E+01
F15	2,70E-002	5.24E+000	5.65E+000	1.00E+02	2.75E+02
F16	6,63E-001	4.12E+000	4.37E+000	3.06E+02	1.83E+02
F17	1,19E+000	2.63E+000	2.52E+000	3.01E+02	2.13E+02
F18	1,25E-008	1.87E+000	1.74E+000	8.12E+02	9.10E+02
F19	1,20E-004	5.34E+000	2.45E+001	8.17E+02	9.06E+02
F20	1,80E-008	3.73E+001	3.67E+001	7.85E+02	9.02E+02
F21	1,18E-006	3.58E+001	2.94E+001	6.42E+02	5.00E+02
F22	2,23E+001	5.64E+001	5.79E+001	9.04E+02	9.61E+02
F23	1,31E000	4.49E+001	4.38E+001	8.20E+02	5.46E+02
F24	1,02E000	2.38E+001	2.74E+001	2.01E+02	2.00E+02
F25	2,11E001	2.46E+001	2.65E+001	2.00E+02	2.13E+02

To compare the proposed approach performance, four evolutionary algorithms from the state of the art PSO, GA, ABC and CS were adopted. The EAs were applied to solve continuous optimization problems using the set benchmark functions CEC’05 (F1 to F25). The stopping criterion for the PSO algorithm is fixed at 500 iterations while for the GA, ABC and CS algorithms, it is fixed at 20000 evaluations of the objective function. Table 4 presents the average error resulting from 25 test functions obtained by comparative algorithms. The best values are written in bold after 25 executions of each algorithm.

Obviously, the ABC algorithm obtained the best average error rate values for the unimodal functions F1 and F2. While, for the other three functions, the new version of IMPSO outperformed PSO’11 by two out of three functions. For the two groups of multimodal and extended test functions, new IMPSO, PSO’11 and GA are considered the most efficient for reaching the global optimum. Except that, CS algorithm achieved a good result for the function F7. On the group of hybrid composite functions, the new IMPSO had better performance than ABC and CS algorithms.

For the 25 continuous optimization functions, new IMPSO and PSO’11 achieve good results on 15 benchmark functions, compared to GA, ABC and CS algorithms, especially on benchmarks with difficult geometric characteristics such as multimodality, non- separability and discontinuity. Therefore, the proposed approach exhibited powerful ability in solving NP-hard optimization problems. It is also clear that the different proposed island model strategies are feasible and effective in improving the PSO ability to balance diversity and convergence.

While new IMPSO has demonstrated outstanding performance for solving continuous optimization problems, it lacks strong theoretical support for its convergence and stability. Similarly, the results of the proposed approach on functions F8, F22, and F25 are not ideal, revealing a performance gap in MPSO. Our future work will be dedicated to further enhance the performance of IMPSO.

5. Conclusion

This paper presented an adaptive multi-strategy PSO algorithm used to solve continuous optimization problems. The improved island model techniques were embedded into the PSO algorithm in order to combine the convergence rate of PSO with the enhanced exploration performed by the IM parameters. The improved IMPSO integrates the different island model parameters: migration topology, selection strategy replacement strategy, migration frequency and migration rate. The BBO algorithm was introduced to make the migration rate more dynamic. New selection and replacement strategies based on the tabu search were also introduced. The IM consists in launching several sub-populations by applying PSO algorithm and the islands which evolve independently but interact at certain number of iterations. Subsequently, the proposed approach was validated employing different test functions CEC’05. Afterwards, the obtained results are illustrated and compared with those provided by the initial version of IMPSO and other well-known metaheuristic algorithms. This comparative study demonstrated that the introduced approach showed a remarkable improvement in most benchmark functions. For future work, we will apply the developed approaches to classify the massive large-scale, spatial-temporal dependent and uncertain data. In this area, image classification has many problems such as feature selection and parameter optimization. We intend also to propose and examine other island model techniques such as the reinforcement learning and to apply it for solving large-scale optimization problems.

References

Kennedy

Eberhart

. Particle swarm optimization. In International Conference on Neural Networks, IEEE Service Center Piscataway, NJ, USA. 2005.

Dorigo

Gambardella

. Ant colony system: A cooperative learning approach to the traveling salesman problem. In IEEE Transactions on Evolutionary Computation. April 1997; 1(1): 53–66. doi: 10.1109/4235.585892.

Abed-alguni

Paul

. Hybridizing the cuckoo search algorithm with different mutation operators for numerical optimization problems. Journal of Intelligent Systems. 2018; 1–32. doi: 10.1515/jisys-2018-0331.

Abadlia

Smairi

Ghédira

. A hybrid Immigrants schema for particle swarm optimization algorithm. Procedia Computer Science, Elsevier. 2018; 126: 105–115. doi: 10.1016/j.procs.2018.07.214.

Alawad

Abed-alguni

. Discrete island-based cuckoo search with highly disruptive polynomial mutation and opposition-based learning strategy for scheduling of workflow applications in cloud environments. Arab J Sci Eng. 2021; 46: 3213–3233. doi: 10.1007/s13369-020-05141-x.

Bagheri Tolabi

Lashkar Ara

Hosseini

. An enhanced particle swarm optimization algorithm to solve probabilistic load flow problem in a micro-grid. Appl Intell. 2021; 51: 1645–1668. doi: 10.1007/s10489-020-01872-4.

Bigiarini

Clerc

Rojas

. Standard Particle Swarm Optimisation 2011 at CEC-2013: A baseline for future PSO improvements. IEEE Congress on Evolutionary Computation, Cancun, Mexico. 2013; 2337–2344. doi: 10.1109/CEC.2013.6557848.

Carr

. An introduction to genetic algorithms. 2014. url: https://karczmarczuk.users.greyc.fr/TEACH/IAD/GenDoc/carrGenet.pdf.

Chen

Zhang

Lin

Chen

, et al. Particle swarm optimization with an aging leader and challengers. IEEE Trans. Evol. Comput. Apr. 2013; 17(2): 241–258.

10.

Cleghorn

Engelbrecht

. Particle swarm stability: A theoretical extension using the non-stagnate distribution assumption. Swarm Intell. 2018; 12: 1–22. doi: 10.1007/s11721-017-0141-x.

11.

Cuong-Le

Minh

Khatir

Wahab

Tran

Mirjalili

. A novel version of Cuckoo search algorithm for solving optimization problems. Expert Systems with Applications. 2021; 186. doi: 10.1016/j.eswa.2021.115669.

12.

Fister

Jr Yang

Fister

. Cuckoo search: A brief literature review, in: Cuckoo Search and Firefly Algorithm: Theory and Applications, Studies in Computational Intelligence. 2014; 516: 49–62.

13.

Gad

. Particle swarm optimization algorithm and its applications: A systematic review. Arch Computat Methods Eng. 2022; 29: 2531–2561. doi: 10.1007/s11831-021-09694-4.

14.

Hosseini

SSS

Nemati

. Application of Genetic Programming for Electrical Engineering Predictive Modeling: A Review. In: Gandomi A, Alavi A, Ryan C. (eds) Handbook of Genetic Programming Applications. Springer, Cham. 2015. doi: 10.1007/978-3-319-20883-1-6.

15.

Hussain

Salleh

Cheng

Shi

Naseem

. Artificial bee colony algorithm: A component-wise analysis using diversity measurement. Journal of King Saud University – Computer and Information Sciences. 2020; 32(Issue 7): 794–808. doi: 10.1016/j.jksuci.2018.09.017.

16.

Karaboga

Basturk

. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems. In: Melin P, Castillo O, Aguilar LT, Kacprzyk J, Pedrycz W. (eds) Foundations of Fuzzy Logic and Soft Computing. Lecture Notes in Computer Science(), vol 4529. Springer, Berlin, Heidelberg. 20027. doi: 10.1007/978-3-540-72950-1-77.

17.

Khan

Qureshi

Wahab

Hussain

Hamza

. A recent survey on the applications of genetic programming in image processing. Special Issue: Foundations of Biomedical (Big) Data Science. 2021; 37: 1745–1778. doi: 10.1111/coin.12459.

18.

Kennedy

Eberhart

. Particle swarm optimization. In International Conference on Neural Networks, IEEE Service Center Piscataway, NJ, USA. 1995.

19.

Koza

. Human-competitive results produced by genetic programming. Genet Program Evolvable Mach. 2010; 251–284. doi: 10.1007/s10710-010-9112-3.

20.

Liu

Zhang

. A modified particle swarm optimization using adaptive strategy. Expert Systems With Applications. 2020; 152: 113353. doi: 10.1016/j.eswa.2020.113353.

21.

Lopes

Silva,

Campelo

Freitas

Campelo

Guimaraes

. A Study on the Configuration of Migratory Flows in Island Model Differential Evolution. GECCO’14, Vancouver, BC, Canada. 2014.

22.

Simon

Siarry

Yang

Fei

. Biogeography-based optimization: A 10-year review. In IEEE Transactions on Emerging Topics in Computational Intelligence. Oct, 2017; 1(5): 391–407. doi: 10.1109/TETCI.2017.2739124.

23.

Molina

Poyatos

Ser

, et al. Comprehensive taxonomies of nature- and bio-inspired optimization: Inspiration versus algorithmic behavior, critical analysis recommendations. Cogn Comput. 2020; 12: 897–939. doi: 10.1007/s12559-020-09730-8.

24.

Ono

Hanada

Kumano

Kimura

. Island model genetic programming based on frequent trees. 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico. 2013. pp. 2988–2995. doi: 10.1109/CEC.2013.6557933.

25.

Ono

Hanada

Kumano

Kimura

. Enhancing island model genetic programming by controlling frequent trees. Journal of Artificial Intelligence and Soft Computing Research. 2019; 9(1): 51–65. doi: 10.2478/jaiscr-2018-0024.

26.

Prajapati

Jain

Chouhan

. Tabu Search Algorithm (TSA): A Comprehensive Survey. 2020 3rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE). 2020. pp. 1–8. doi: 10.1109/ICETCE48199.2020.9091743.

27.

Rucinskia

Izzo

Biscania

. On the impact of the migration topology on the island model. Parallel Computing Journal. 2010; (36): 555–571. doi: 10.1016/j.parco.2010.04.002.

28.

Simon

. Biogeography-based optimization. IEEE Transactions on Evolutionary Computation. 2008; 12: 702–713. doi: 10.1109/TEVC.2008.919004.

29.

Suganthan

Hansen

Liang

Deb

Chen

Auger

Tiwari

. Problem Definitions and Evaluation Criteria for the CEC’2005 Special Session on Real-Parameter Optimization. Technical Report: Nanyang Technological University, Singapore, 2005.

30.

Song

Cao

. An improved particle swarm optimization algorithm with adaptive weighted delay velocity. Systems Science and Control Engineering. 2021. pp. 188–197. doi: 10.1080/21642583.2021.1891153.

31.

Yang

Deb

. Cuckoo Search via Lévy flights. World Congress on Nature and Biologically Inspired Computing (NaBIC), Coimbatore, India. 2009; 210–214. doi: 10.1109/NABIC.2009.5393690.

32.

Zeng

Wang

Liu

Zhang

Hone

Liu

. A Dynamic Neighborhood-Based Switching Particle Swarm Optimization Algorithm. In IEEE Transactions on Cybernetics. 2020. doi: 10.1109/TCYB.2020.3029748.

Adaptive multi-strategy particle swarm optimization for solving NP-hard optimization problems

Abstract

Keywords

1. Introduction

2.1 Mono-objective optimization

2.2 PSO algorithm

2.5 Biogeography based optimization

2.7 The hybridization between island model and the evolutionary algorithms

2.7.1 Improvement of the island genetic programming

2.7.2 Improvement of the island cuckoo search

2.7.3 Improvement of the island particle swarm optimization

4.1 The benchmark functions

4.2.1 IMPSO the initial version versus the approach

Table 1 Average error rate obtained by IMPSO using chain topology

Table 4 Comparison of the average error rate between new and old IMPSO using the torus topology

References

Table 1
Average error rate obtained by IMPSO using chain topology

Table 4
Comparison of the average error rate between new and old IMPSO using the torus topology