Island-based Cuckoo Search with elite opposition-based learning and multiple mutation methods for solving optimization problems

Abstract

The island Cuckoo Search (iCSPM) algorithm is a variation of Cuckoo Search that uses the island model and highly disruptive polynomial mutation to solve optimization problems. This article introduces an improved iCSPM algorithm called iCSPM with elite opposition-based learning and multiple mutation methods (iCSPM2). iCSPM2 has three main characteristics. Firstly, it separates candidate solutions into several islands (sub-populations) and then divides the islands among four improved Cuckoo Search algorithms: Cuckoo Search via Lévy flights, Cuckoo Search with highly disruptive polynomial mutation, Cuckoo Search with Jaya mutation and Cuckoo Search with pitch adjustment mutation. Secondly, it uses elite opposition-based learning to improve its convergence rate and exploration ability. Finally, it makes continuous candidate solutions discrete using the smallest position value method. A set of 15 popular benchmark functions indicate iCSPM2 performs better than iCSPM. However, based on sensitivity analysis of both algorithms, convergence behavior seems sensitive to island model parameters. Further, the single-objective IEEE-CEC 2014 functions were used to evaluate and compare the performance of iCSPM2 to four well-known swarm optimization algorithms: distributed grey wolf optimizer, distributed adaptive differential evolution with linear population size reduction evolution, memory-based hybrid dragonfly algorithm and fireworks algorithm with differential mutation. Experimental and statistical results suggest iCSPM2 has better performance than the four other algorithms. iCSPM2’s performance was also shown to be favorable compared to two powerful discrete optimization algorithms (generalized accelerations for insertion-based heuristics and memetic algorithm with novel semi-constructive crossover and mutation operators) using a set of Taillard’s benchmark instances for the permutation flow shop scheduling problem.

1 Introduction

Exact algorithms are usually used to find optimal solutions for simple optimization problems such as the feature selection problem (Yusta 2009; Komusiewicz and Kratsch 2020). However, NP-hard optimization problems, such as the traveling salesman problem and shortest path problem (Zhou et al. 2019; Abed-alguni and Alawad 2021), typically cannot be solved with exact algorithms and require heuristic or optimization algorithms to solve them. This is because the search area of an NP-hard optimization problem is either extremely large or infinite. An optimization algorithm can be applied iteratively to compare different candidate solutions for an optimization problem until finding a satisfactory or optimal solution. In the optimization field, the term single-solution optimization describes an optimization algorithm that iteratively optimizes a single candidate solution, while the term population-based optimization is used to describe an optimization algorithm that iteratively optimizes multiple candidate solutions at the same time. A general problem with optimization algorithms is that they may converge to unaccepted solutions (premature convergence) during an early stage of their optimization process. Besides, the performance and speed of optimization algorithms degrade with the increase of the dimensionality (i.e., number of decision variables) of optimization problems (Abed-alguni and Barhoush 2018; Abed-alguni 2019; Mehta and Kaur 2019).

One frequently used option of population-based optimization algorithms is the island-based approach, which is based on the principle of divide and conquer. In island-based optimization algorithms, an island model divides the overall candidate solution population into smaller, equal-sized independent sub-populations (islands) to ensure diversity of candidate solutions through a structured, distributed approach. An optimization algorithm is then independently applied to each island, though the process of migration is modelled by the islands regularly communicating with each other (Abed-alguni 2019; Abed-Alguni et al. 2019; Al-Betar et al. 2019; Al-Betar and Awadallah 2018).

Island-based optimization algorithms [e.g., island artificial bee colony (Awadallah et al. 2020), island flower pollination algorithm (Al-Betar et al. 2019), island bat algorithm (Al-Betar and Awadallah 2018), island-based harmony search (Al-Betar et al. 2015), island-based genetic algorithm (Mohammed et al. 2016) and island-based Cuckoo Search with highly disruptive polynomial mutation (iCSPM) Abed-alguni 2019] have been used with a high degree of success in both continuous and discrete problems. According to Abed-alguni (2019); Alawad and Abed-alguni (2020), iCSPM exhibits a superior performance compared to other island-based optimization algorithms. There are three possible reasons for this. Firstly, the iCSPM model, especially in conjunction with its abandon method, helps increase diversity in each island. Secondly, low-fitness solutions are given the opportunity to evolve to improved solutions. Thirdly, the included highly disruptive polynomial mutation (HDP) method allows the exploration of the entire search space regardless of the decision variable’s current value.

In this research study, we introduce an improved iCSPM algorithm, iCSPM2, which incorporates three modifications into iCSPM. Firstly, it partitions its n candidate solutions between s independent islands and then equally divides them among four Cuckoo Search (CS) algorithms: CS via Lévy flights (CS1) (Yang and Deb 2009), CS with HDP mutation (CS10) (Abed-Alguni and Paul 2018), CS with Jaya mutation (CSJ) and CS with pitch adjustment mutation (CS11) (Abed-Alguni and Paul 2018). Secondly, it uses elite opposition-based learning (EOBL) (Zhou et al. 2013) to explore solutions around the current elite solutions (best solutions) in each island’s population. Finally, it employs the smallest position value (SPV) (Ali et al. 2019) with scheduling problems to convert the continuous values of any decision variables to discrete ones in a candidate solution.

There are five expected benefits for iCSPM2, which are mainly because of the unique advantages that each CS variation has to offer. First, CS1 uses the Lévy flight mutation, which has a better exploration capability than the random mutation method (Yang and Deb 2009). Second, CS10 uses the HDP mutation method that can sample the entire search space between the lower and upper bounds of a decision variable regardless of its value (Abed-Alguni and Paul 2018; Abed-alguni 2019; Alawad and Abed-alguni 2020). Third, CSJ uses the Jaya mutation method that mutates the candidate solutions using stochastic moves based on the best and worst candidate solutions (Rao 2016). Fourth, CS11 uses the pitch adjustment mutation, which is known for its quick convergence (Abed-Alguni and Paul 2018; Al-Betar et al. 2015). Finally, we are particularly interested to use EOBL in iCSPM2 because it is capable of speeding up the convergence speed of optimization algorithms by exploring the opposite solutions of the best-known candidate solutions (Paiva et al. 2017; Zhang et al. 2017). By combining these techniques, it is expected that iCSPM2 will be able to realize some of the advantages of each variation.

The main contributions of this paper are as follows:

• 1. We propose iCSPM2, which is an improved island-based CS algorithm with multiple exploration and exploitation techniques.

• 2. To the best of the authors’ knowledge, it is the first time that four variations of CS (CS1, CS10, CSJ and CS11) are applied synchronously to the island model. Besides, it is the first time that the EOBL method is used to improve the convergence rate and exploration ability of an island-based algorithm.

• 3. We use the SPV method with scheduling problems to convert continuous candidate solutions into discrete ones.

• 4. We present results of three sets of experiments to test and evaluate the efficiency of iCSPM2 compared to other popular optimization algorithms using popular benchmark suites for continuous and discrete problems.

  • Firstly, we used 15 popular benchmark functions to compare iCSPM2 to iCSPM. The experimental results indicate that iCSPM2 exhibits better performance than iCSPM.

  • Secondly, we used 30 IEEE-CEC 2014 functions to compare the performance of iCSPM2 against the performance of four state-of-the-art swarm optimization algorithms: distributed grey wolf optimizer (DGWO) (Abed-alguni and Barhoush 2018), distributed adaptive differential evolution with linear population size reduction evolution (L-SHADE) (Tanabe and Fukunaga 2014), memory-based hybrid dragonfly algorithm (MHDA) (Ks and Murugan 2017) and fireworks algorithm with differential mutation (FWA-DM) (Yu et al. 2014). The overall simulation and statistical results clearly indicate that iCSPM2 outperforms the other tested swarm optimization algorithms.

  • Finally, we used a set of Taillard’s benchmark instances for the permutation flow shop scheduling problem (PFSSP) (Taillard 1990) to evaluate and compare iCSPM2 to two powerful discrete evolutionary algorithms (generalized accelerations for insertion-based heuristics (GAIbH) (Fernandez-Viagas et al. 2020) and memetic algorithm with novel semi-constructive crossover and mutation operators (MASC) (Kurdi 2020). The simulation results indicate that iCSPM2 produces better schedules than GAIbH and MASC.

The remainder of the paper is organized as follows: We first review the preliminaries in Sect. 2. In Sect. 3, we provide a critical review of recently proposed island-based algorithms. Section 4 then presents our proposed variation of iCSPM. In Sect. 5, we demonstrate the performance of iCSPM2 compared to the other island-based algorithms and discuss these results in Sect. 6. Finally, Sect. 7 concludes the paper and presents future work.

2 Preliminaries

This section provides a summary of some of the underlying concepts of the Cuckoo Search algorithm (Sect. 2.1), as well as some existing improvements to Cuckoo Search, including Cuckoo Search with pitch adjustment (Sect. 2.2); Cuckoo Search with Jaya mutation (Sect. 2.3); and island-based Cuckoo Search with highly disruptive polynomial mutation (Sect. 2.4). Elite opposition-based learning, which explores opposite solutions of best-known candidates to help speed up convergence, is then discussed in Sect. 2.5. Finally, Sect. 2.6 provides a description of the permutation flow shop scheduling problem.

2.1 Cuckoo Search algorithm

The Cuckoo Search (CS) algorithm (Yang and Deb 2009; Abed-alguni et al. 2021; Alkhateeb et al. 2021) is a nature-inspired, evolutionary algorithm. It aims to optimize a population of candidate solutions for a given optimization problem using two simulation models related to the behaviors of birds in nature. The first model simulates the parasitic procreation habit of cuckoos, while the second model simulates the random actions of flying and landing of birds using Lévy flights (Yang and Deb 2009; Rakhshani and Rahati 2016).

In CS, an egg (current candidate solution) can be mutated into a cuckoo’s egg. CS generates, at each iteration, a mutated solution using a function that comprises the Lévy-flight operator. It then attempts to swap the new solution with a lower quality solution in the population. Two parameters control the optimization process of CS: the population size (number of eggs) n and the fraction of the worst candidate solutions that get replaced with randomly generated solutions ($p_a\in [0,1]$). The simulation models of CS are based on the following notations and assumptions:

• $\mathbf {\overrightarrow{X}^i}=\langle x_1^i, \ldots , x_m^i\rangle$ is the ith candidate solution that contains m decision variables, where $x_j^i$ is the jth decision variable in $\mathbf {\overrightarrow{X}^i}$.

• The value $x_j^i$ is a random value generated using a uniform-random, generation function $x_j^i = {\text {LB}}_j^i +({\text {UB}}_j^i - {\text {LB}}_j^i)\times U(0,1)$, where U(0, 1) represents a uniform random number in the interval (0, 1), ${\text {LB}}_j^i$ is the lower bound and ${\text {UB}}_j^i$ is the upper bound of the search range of $x_j^i$.

• $f(\mathbf {\overrightarrow{X}}^i)$ is the objective or fitness value of the candidate solution $\mathbf {\overrightarrow{X}}^i$.

• $\mathbf {\overrightarrow{X}}^i (i = 1, 2, \ldots , n)$ is a population of n candidate solutions.

• At the last step of each iteration, the CS algorithm replaces a fraction $p_a\in [0,1]$ of the lowest fitted solutions with new randomly generated solutions.

• The new modified population is then moved to the next iteration of CS.

The CS algorithm initially produces a population of n candidate solutions $\mathbf {\overrightarrow{X}^i} (i = 1, 2, \ldots , n)$ from the range of possible solutions of the fitness function $f(\mathbf {\overrightarrow{X}^i})$. The maximum number of iterations (MaxItr) of the improvement loop of CS is specified according to of complexity of $f(\mathbf {\overrightarrow{X}^i})$.

CS attempts, at each iteration, to enhance a randomly selected, candidate solution $(\mathbf {\overrightarrow{X}^i}(t))$ using a Lévy-flight mutation function and produces a new solution ($\mathbf {\overrightarrow{X}^i}(t+1))$ as follows:

$$\begin{aligned} \mathbf {\overrightarrow{X}^{{i}}}(t+1)=\mathbf {\overrightarrow{X}^{{i}}}(t)+ \beta \oplus \text {L}\acute{\mathrm{e}}\text {vy}(\lambda ), \end{aligned}$$

(1)

where $\beta >0$ controls the distance of mutation and $\oplus$ represents entry-wise multiplication. The Lévy flight is conventionally defined as a special random walk with a dynamic step length. The step length is generated from an infinite, heavy-tailed, Lévy distribution that follows the power law:

$$\begin{aligned} \text {L}\acute{\mathrm{e}}\text {vy} \sim u=L^{-\alpha }, \end{aligned}$$

(2)

where $\alpha \in (1,3]$ is the parameter of fractal dimension and L is the step size. This distribution produces a small percentage of random solutions around the local optimal solutions, while producing the majority of random solutions away from the local optimums. Therefore, the Lévy flight-mutation method has a better exploration capability than a standard random walk, since the distance value increases gradually during the simulation. At the end of each iteration of CS, an abandon process takes place, where a fraction ($p_a$) of the worst candidate solutions in the population are replaced with new randomly generated candidate solutions.

2.2 Cuckoo Search with pitch adjustment

Cuckoo Search with pitch adjustment (CS11) is an algorithm that uses the pitch adjustment (PA) method in place of Lévy flight. PA is a probabilistic method (Geem et al. 2001) that mutates $\mathbf {\overrightarrow{X}^j}(t)$ by mutating each one of its decision variables with probability PAR$\in (0,1)$:

$$\begin{aligned} x_i^j(t+1) = \left\{ \begin{array}{rl} x_i^j(t) \pm U(-1,1) \times \text {BW}&{}r\le \text{ PAR } \\ x_i^j(t)\qquad \qquad \qquad \qquad \qquad \qquad &{}r> \text{ PAR } \end{array} \right. \end{aligned}$$

(3)

where r is a random number in [0, 1], BW (bandwidth) determines the mutation distance and $U\!(-1,1)$ is a random number in $(-1,1)$.

2.3 Cuckoo Search with Jaya mutation

The Jaya algorithm (Rao 2016) is an evolutionary algorithm that was designed according to the concept of victory. In the improvement loop of Jaya, the candidate solutions are randomly moved between the best and worst candidate solutions. This behavior aims to explore the search area between the worst and best candidate solutions (Alawad and Abed-alguni 2021).

We propose a new variant of CS called Cuckoo Search with Jaya mutation (CSJ), which replaces the Lévy flight operator of CS with Jaya mutation. In CSJ, the decision variables of $\mathbf {\overrightarrow{X}^j}(t)$ are updated one by one using the corresponding decision variables of the best candidate solution $\mathbf {\overrightarrow{X}^B}(t)$ and worst candidate solution $\mathbf {\overrightarrow{X}^W}(t)$ at iteration t as follows:

$$\begin{aligned} x^{j}_i(t+1)= x^{j}_i(t) + r_1 \,x^{B}_i(t) + r_2 \,x^{W}_i(t), \end{aligned}$$

(4)

where $x^{j}_i(t)$, $x^{B}_i(t)$ and $x^{W}_i(t)$ are the values of ith decision variables of $\mathbf {\overrightarrow{X}^j}(t)$, $\mathbf {\overrightarrow{X}^B}(t)$ and $\mathbf {\overrightarrow{X}^W}(t)$, respectively at iteration t. $r_1$ and $r_2$ are random parameters in [0,1]. After mutating all decision variables of $\mathbf {\overrightarrow{X}^j}(t)$, if the fitness value of $\mathbf {\overrightarrow{X}^j}(t+1)$ is an improvement over the fitness of $\mathbf {\overrightarrow{X}^j}(t)$, the solution $\mathbf {\overrightarrow{X}^j}(t)$ is replaced by $\mathbf {\overrightarrow{X}^j}(t+1)$.

2.4 Island-based Cuckoo Search with highly disruptive polynomial mutation

The island Cuckoo Search (iCSPM) is a parallel variation that integrates two modifications to CS. Firstly, it uses a structured population model called the island model (Corcoran and Wainwright 1994) to organize candidate solutions in CS to smaller manageable sub-populations (islands). This model increases the probability that unfit candidate solutions are improved into better solutions and improves the diversity of the candidate solutions (Al-Betar et al. 2019; Al-Betar and Awadallah 2018). Secondly, it uses CS with HDP mutation (CS10) (Abed-Alguni and Paul 2018) to optimize the candidate solutions on each island. This is because, according to several experimental studies (Hasan et al. 2014; Alkhateeb and Abed-Alguni 2017; Abed-alguni and Alkhateeb 2018), CS10 is a better exploratory algorithm than the CS algorithm. Besides, the HDP mutation used in CS10 can sample the entire search space between the lower and upper bounds of a decision variable regardless of its value (Alawad and Abed-alguni 2020; Abed-alguni 2019; Abed-Alguni and Paul 2018).

CS10 uses the HDP method to alter the values of the decision variables of $\mathbf {\overrightarrow{X}^j}(t)$ by mutating each of its decision variables with probability $P_m\in [0,1]$ as follows (Doush et al. 2014):

$$\begin{aligned}&x_i^j(t+1) \leftarrow x_i^j(t) + \delta _k .({\text {UB}}_i-{\text {LB}}_i), \text {where} \end{aligned}$$

(5)

$$\begin{aligned}&\delta _k= \left\{ \begin{array}{rl} {(2r)+(1-2r)\times (1-\delta _1)^{\eta _m+1}]^{\frac{1}{\eta _m+1}-1}\quad \quad \quad \quad }&{}{\quad \quad r\le P_m} \\ {1-[2(1-r)+2(r-0.5) \times (1-\delta _2)^{\eta _m+1}]^{\frac{1}{\eta _m+1}} } &{}{\quad \quad r>P_m} \end{array} \right. \nonumber \\ \end{aligned}$$

(6)

$$\begin{aligned}&\delta _1\leftarrow \frac{x_i^j(t)-{\text {LB}}_i}{{\text {UB}}_i-{\text {LB}}_i} \end{aligned}$$

(7)

$$\begin{aligned}&\delta _2\leftarrow \frac{{\text {UB}}_i-x_i^j(t)}{{\text {UB}}_i-{\text {LB}}_i} \end{aligned}$$

(8)

The definitions of the parameters in the above equations are as follows:

• $x_i^j(t)$: the ith decision variable of the jth candidate solution $\mathbf {\overrightarrow{X}^j}(t)$ at iteration t

• r: a uniform random number in [0, 1]

• $P_m$: the probability of mutation

• ${\text {LB}}_i$: the lower boundary of $x_i^j(t)$

• ${\text {UB}}_i$: the upper boundary of $x_i^j(t)$

• $\delta _1$: the distance between $x_i^j(t)$ and ${\text {LB}}_i$ over the closed interval [${\text {UB}}_i$, ${\text {LB}}_i$]

• $\delta _2$: the distance between ${\text {UB}}_i$ and $x_i^j(t)$ over the closed interval [${\text {UB}}_i$, ${\text {LB}}_i$]

• $\eta _m$: the distribution index, which is a non-negative number

A vital part of the island model is the migration procedure that periodically allows the islands to exchange candidates solutions. It enables iCSPM to select and transfer a subset of candidate solutions among the different islands, depending on two factors. Firstly, the number of generations that should evolve in each island before the triggering the migration procedure (the migration frequency, $M_f$). Secondly, the fraction of the candidate solutions on each island that can be moved between neighboring islands (the migration rate, $M_r$). After each $M_f$ iterations of iCSPM, the islands are organized in a random ring shape, with each island establishing one connection in from a neighboring island, and one connection out to its other neighbor.

The iCSPM algorithm uses a “best-worst migration policy”, which determines the best candidate solutions on one island to be swapped with the worst candidate solutions on a neighboring island. The algorithmic details and the source code of iCSPM are available in Abed-alguni and Alkhateeb (2018).

2.5 Elite opposition-based learning

Sihwail et al. (2020) proposed a special type of opposition-based learning by the name EOBL (short for elite opposition-based learning). EOBL was inspired from the intuition that opposite solutions of elite (best) solutions are more likely to be close to the global optima than any other solutions. EOBL was used with optimization methods such as the Bat algorithm (Paiva et al. 2017) and Harris–Hawks optimization algorithm (Zhang et al. 2017) to improve their efficiency.

We can apply EOBL to decision variables of candidate solutions. Let $\mathbf {\overrightarrow{X}} = \langle x_1, x_2 \ldots , x_m\rangle$ be an elite candidate solution with m decision variables. The elite opposite-based solution $\mathbf {\overrightarrow{X}}^{o}$ can be calculated using Equation 9:

$$\begin{aligned} \mathbf {\overrightarrow{X}}^{o}= \langle x_1^{o}, x_2^{o} \ldots , x_m^{o}\rangle , \text {where}\, x_i^{o}= \delta ({\text {d}}a_i + {\text {d}}b_i) -x_i \end{aligned}$$

(9)

In the above equation, $\delta \in (0,1)$ is a parameter used to control the opposition magnitude, and ${\text {d}}a_i$ and ${\text {d}}b_i$ are the dynamic boundaries which are calculated as follows:

$$\begin{aligned} {\text {d}}a_i= \min (x_i), \, \, {\text {d}}b_i= \max (x_i) \end{aligned}$$

(10)

The value of an opposite decision variable $x_i^{o}$ may be outside [${\text {LB}}_i$, ${\text {UB}}_i$]. This can be solved using the following equation:

$$\begin{aligned} x_i^o= {\text {rand}}({\text {LB}}_i, {\text {UB}}_i), \text { if } x_i^{o}< {\text {LB}}_i \text { or } x_i^{o}> {\text {UB}}_i \end{aligned}$$

(11)

where ${\text {rand}}({\text {LB}}_i, {\text {UB}}_i)$ is a random number between ${\text {LB}}_i$ and ${\text {UB}}_i$.

2.6 Permutation flow shop scheduling problem

The permutation flow shop scheduling problem (PFSSP) is a popular $\mathcal {NP}$-hard combinatorial optimization problem. It is a discrete optimization problem that is commonly used as a benchmark for investigating the efficiency of discrete optimization algorithms (Alawad and Abed-alguni 2021). Several heuristic- and optimization-based scheduling algorithms have been evaluated using the PFSSP (Alawad and Abed-alguni 2020; Abed-alguni and Alawad 2021; Kurdi 2016; Wang et al. 2017). The mathematical model of the PFSSP is built around two lists. Firstly, a list of n jobs ($j_1, j_2, \ldots , j_n$), where each job comprises m sequential operations ($O_{i,1}, O_{i,2}, \ldots ,O_{i,m}$). Secondly, a list of m machines ($M_1,M_2, \ldots , M_m$), where each machine can execute only the corresponding operation in a job. In PFSSP, $t_{i,j}$ denotes the processing time required for machine j to complete job i and $O_{i,j}$ is the processing operation of job i on machine j. There is a strict order of jobs that have to be processed by each machine, and each machine can only process one job at a time. A candidate schedule is a permutation of jobs $\pi =\{\pi _1,\pi _2, \ldots ,\pi _n\}$ for which completion times of all operations can be calculated. The completion time $C_j$ of job j is defined to be the completion of job j’s last operation $O_{j,m}$ ($C_j$ = $C_{j,m}$). The optimal solution in PFSSP is the candidate schedule that has the lowest total completion time of all jobs. The equations of the PFSSP are as follows (Wang et al. 2017; Alawad and Abed-alguni 2021):

$$\begin{aligned}&C_{1,1}= t_{1,1} \end{aligned}$$

(12)

$$\begin{aligned}&C_{j,1} = C_{j-1,1} + t_{j,1},\quad j = 2,\ldots , n, \end{aligned}$$

(13)

$$\begin{aligned}&C_{1,k} = C_{1,k-1} + t_{1,k},\quad k = 2,\ldots , m, \end{aligned}$$

(14)

$$\begin{aligned}&C_{j,k}= \max \{C_{j-1,k} ,C_{j,k-1}\}, \quad \nonumber \\&\quad j = 2,\ldots , n,\, k = 2,\ldots ,m, \end{aligned}$$

(15)

$$\begin{aligned}&C_{\max } = \max \{C_{n,m}\}, \end{aligned}$$

(16)

$$\begin{aligned}&f = \max \{C_{\max }\}. \end{aligned}$$

(17)

We used the above equations in Sect. 5.7 to test the performance of iCSPM2 using 12 instances of Taillard’s benchmark for the PFSSP (Taillard 1990).

3 Related Work

The island model is a structured-population strategy that has been incorporated into many evolutionary algorithms to improve their population diversity and convergence speed (Abed-alguni and Barhoush 2018; Abed-Alguni et al. 2019; Al-Betar et al. 2019; Al-Betar and Awadallah 2018; Awadallah et al. 2020; Al-Betar et al. 2015; Alawad and Abed-alguni 2020; Abed-alguni and Alawad 2021; Kurdi 2016; Lardeux and Goëffon 2010; Kushida et al. 2013; Abadlia et al. 2017; Michel and Middendorf 1998). This section provides a critical review of recently proposed island-based optimization algorithms.

The island-based differential evolution algorithm (island-based DE) is a variation of differential evolution (DE) that is based on the multi-size island model (Skakovski and Jedrzejowicz 2019). This model can be applied to the population of candidate solutions using two different approaches. In the first approach, the population of candidate solutions can be divided to islands with different sizes. In the second approach, the algorithm starts its optimization process with one population and then changes its size over the course of optimization process. In both approaches, a copy of DE is applied to each island, where communication between islands, or migration of candidate solutions, is not permitted. Island-based DE was compared in Skakovski and Jedrzejowicz (2019) to DE and IBDEAmd (island-based DE algorithm with islands of equal sizes) using complex scheduling problems. The results showed that island-based DE is the best performing algorithm. However, island-based DE requires more computational resources than the other algorithms in the beginning of its optimization process. In addition, if it is executed sequentially, it may require longer running time than the other algorithms.

The parallel multi-population chaotic bat algorithm (CBAS) (Guo et al. 2019) is an island-based algorithm that incorporates four modifications into the bat algorithm (BA): the island model (Al-Betar et al. 2019), chaotic maps (Mugemanyi et al. 2020), Lévy flight search (Liu et al. 2020) and contraction factor. The island model is used to divide the population of CBAS into islands. The chaotic maps are evolution functions with chaotic behaviors usually used to generate random numbers in BA. The contraction factor is a parameter that controls the direction of optimization in BA. The Lévy flight search is based on the Lévy flight operator, which is a special random walk with a dynamic step length. The experimental results in Guo et al. (2019), using a few general benchmark functions, suggest that CBAS outperforms some variations of BA (suggested also by the same authors) such as shrink factor BA, chaotic BA and Lévy-flight BA. However, the performance of CBAS should be compared to the performance of state-of-the-art swarm optimization algorithms such as DGWO and L-SHADE using strong benchmark suite such as the CEC 2015 test suite. This will allow us to fairly evaluate the performance of CBSA.

The HS algorithm is a widely used optimization algorithm inspired by the improvisation of music players (Geem et al. 2001). The island-based HS (iHS) (Al-Betar et al. 2015) is a variation of HS that integrates the concepts of island model into with HS. The optimization loop of HS is applied to each island independently. The quality of each island’s solutions is periodically improved by exchanging candidate solutions among island through a migration process. The experimental study in Al-Betar et al. (2015) suggests that iHS provides more accurate fitness values than the original HS algorithm for a large number of continuous numerical problems. The iHS was utilized in Al-Betar (2021) to solve the economic load dispatch problem (i.e., the scheduling for an electrical generation system to provide the load demand in addition to the transmission loss with the objective of minimizing generation fuel cost). According to the experimental results in Al-Betar (2021), iHS outperformed the original HS algorithm and other algorithms (e.g., island bat algorithm Al-Betar and Awadallah 2018) by providing the best results for three out of five real-world economic load dispatch test cases.

Chen et al., proposed the chaotic multi-population hybrid DE and Harris–Hawks optimization (CMDHHO) algorithm for solving the single-objective optimization problems (Chen et al. 2020). CMDHHO integrates the chaos maps, island model and optimization operators of DE into the Harris–Hawks optimization (HHO) algorithm. The experimental and statistical results in Chen et al. (2020) using CEC 2011 and CEC 2107 suggest that CDHHO is faster and provides better performance than HHO and DE. However, CMDHHO requires more computational resources than DE and HHO in the beginning of its optimization process. Besides, the chaotic maps in CMDHHO are more suitable to continuous optimization problems than discrete problems.

Lardeux and Goëffon (2010) proposed a dynamic island model for the genetic algorithm (GA). This model uses complete graph modeling that allows the implementation of any type of migration topologies from edgeless graphs to popular island topologies such as uni-directional or bi-directional, rings and lattices. This model is called dynamic because the topology in it continues to evolve during the search process following the rewards and penalties received during previous migration waves. The experimental results in Lardeux and Goëffon (2010) using 0/1 Knapsack and MAX-SAT problems suggest that the dynamic island model helps GA to achieve good results. However, a problem with this model is that it uses a GA that is sensitive to its internal parameters and methods such as the rate of mutation, rate of crossover, population size and selection method.

Kurdi (2016) suggested the island model genetic algorithm (IMGA) for solving the PFSSP. In IMGA, islands use different variations of the GA (GA with insertion operator, GA with swap operator and GA with inversion operator). Results in Kurdi (2016) suggest that IMGA offers improved performance than the variations of GA that depend on a single evolutionary method.

Alawad and Abed-alguni (2020) proposed discrete iCSPM with opposition-based learning strategy (DiCSPM), a discrete variation of iCSPM. This algorithm provides efficient schedules for workflow applications in distributed environments. It uses random generation and opposition-based learning approaches to generate diverse initial population candidate solutions. It also optimizes decision variable values in candidate solutions using the SPV method. The simulation results in Alawad and Abed-alguni (2020) using WorkflowSim (Casanova et al. 2014) suggest that DiCSPM provides efficient schedules in cloud computing environments.

Particle swarm optimization (PSO) is a well-known algorithm that was inspired from the movement behavior of birds in a group (Kennedy and Eberhart 1995). The island model was integrated into PSO in a new algorithm called the dynamic island model PSO (DIMPSO) algorithm (Abadlia et al. 2017). The goal of DIMPSO is to increase the diversity of the population and the convergence speed of PSO. DIMPSO was evaluated using the CEC 2005 test suite, and the results suggest it is more efficient and accurate than PSO.

The island bat algorithm (iBA) (Al-Betar and Awadallah 2018) incorporates the island model into BA. Similar to iHS, the population in iBA is divided into smaller sub-populations, where the improvement loop of BA is applied independently to each sub-population. A migration process and the ring topology are used in iBA to improve the diversity of the candidate solutions in each sub-population and improve the convergence speed. iBA was evaluated in Al-Betar and Awadallah (2018) using 25 IEEE-CEC2005 benchmark functions. Results indicate that iBA improves the performance of BA.

The ant colony algorithm has also been modified to an island model in the ant colony optimization with lookahead (ACO) algorithm (Michel and Middendorf 1998). It was proposed to help solve the problem of finding the shortest supersequence str of two sequences str1 and str2 such that both sequences are part of str. AOC incorporates the same principles of the island model as iHS and iBA, but it additionally uses a lookahead function to mutate the candidate solutions taking into account the influence of the current mutation on the mutation in the next iteration.

The distributed grey wolf optimizer (DGWO) algorithm (Abed-alguni and Barhoush 2018) is a distributed variation of the grey wolf optimizer (GWO) algorithm (Mirjalili et al. 2014). DGWO attempts to increase the convergence speed of GWO by improving diversity through the incorporation of the principles of the island model into GWO. DGWO was compared to four optimization algorithms (GWO, distributed adaptive differential evolution with linear population size reduction evolution (L-SHADE) (Tanabe and Fukunaga 2014), memory-based hybrid dragonfly algorithm (MHDA) (Ks and Murugan 2017) and fireworks algorithm with differential mutation (FWA-DM) Yu et al. 2014) using 30 CEC 2014 functions. DGWO performs significantly better than the other tested algorithms.

Abed-alguni and Alawad (2021) proposed a discrete variation of DGWO for scheduling of dependent tasks to virtual machines in distributed environments. It uses the largest order value (LOV) method to produce discrete job permutations from continuous candidate solutions. The simulation results using WorkflowSim Casanova et al. (2014) indicate that the discrete variation of DGWO is efficient for solving scheduling problems.

The flower pollination algorithm (FPA) is an evolutionary algorithm based on the biological evolution of pollination of flowers (Yang 2012). In Al-Betar et al. (2019), the island model was applied to FPA to control its diversity and solve its premature convergence problem. The proposed algorithm was called IsFPA. 23 test functions were used to evaluate the performance of IsFPA compared to GA, PSO, gravitational search algorithm (GSA), multi-verse optimizer (MVO), iBA and iHS. IsFPA was found to perform better than each of the other algorithms.

The artificial bee colony (ABC) algorithm (Karaboga and Basturk 2007) simulates honey bee foraging behavior to solve various optimization problems. It is an efficient algorithm, but may very quickly converge to sub-optimal solutions at the beginning of its optimization process. The island artificial bee colony (iABC) algorithm (Awadallah et al. 2020) helps overcome this problem by distributing ABC’s optimization process over multiple islands. Evaluation of the performance of iABC using the IEEE-CEC 2015 indicated that iABC indeed improved diversity and performance of ABC and also provided interesting performance compared to 18 other tested algorithms.

The island-based differential evolution (iDE) algorithm (Kushida et al. 2013) modifies the DE algorithm to use an island model. iDE divides the population of candidate solutions to islands with varying population size and parameters. Therefore, each island has different convergence behavior compared to the other islands. iDE was evaluated in Kushida et al. (2013) using a set of basic test functions and found to be more efficient than DE.

The whale optimization algorithm (WOA) simulates humpback whale bubble-net hunting mechanisms to solve optimization problems (Mirjalili and Lewis 2016). However, WOA may suffer from the premature convergence, degrading the performance of the evolutionary algorithm (Abed-alguni and Klaib 2018). To mitigate this issue, Abed-Alguni et al. (2019) modified WOA to incorporate the island model. Results show the iWOA has improved accuracy over WOA for 18 test functions.

In conclusion, island-based optimization algorithms have been used extensively in the literature (Abed-alguni and Barhoush 2018; Abed-Alguni et al. 2019; Al-Betar et al. 2019; Al-Betar and Awadallah 2018; Awadallah et al. 2020; Al-Betar et al. 2015; Alawad and Abed-alguni 2020; Abed-alguni and Alawad 2021; Kurdi 2016; Lardeux and Goëffon 2010; Kushida et al. 2013; Abadlia et al. 2017; Michel and Middendorf 1998) to improve the diversity of the population in population-based optimization algorithms and improve their convergence rate to optimality. However, typical island-based optimization algorithms apply only a single optimization algorithm to all islands. Therefore, in this paper, we investigate the simultaneous use of several variations of CS on different islands. Such an algorithm should benefit from some of the unique advantages each CS variation has to offer.

4 Proposed algorithm: iCSPM with elite opposition-based learning and multiple mutation methods

In this section, we present iCSPM2 which is a variation of iCSPM with EOBL and four mutation methods. Fig. 1 illustrates the flowchart of iCSPM2. The main steps of the flowchart are as follows:

• 1. The first step is to randomly generate a population of n candidate solutions using a generating function. The n candidate solutions are then randomly divided among s islands.

• 2. The s islands are then divided equally among four variations of CS: CS1, CS10, CSJ and CS11.

• 3. Each variation is then independently executed for $M_f$ iterations on the islands assigned to it, with EBOL executed at the end of each generation to replace any elite candidate solution with its opposite if the opposite is determined to be a better candidate (as described in Sect. 2.5). This step can be performed in parallel because each variation of CS is applied to an independent set of islands. Even the optimization loop in each variation of CS can be executed in parallel. This issue is explained in Algorithm 1, which shows the algorithmic details of iCSPM2.

• 4. The n islands are arranged based on a random ring topology. Some example random ring topologies are presented in Fig 2. The direction of migration between an island and its neighboring island is represented in the figure as a unidirectional edge between the two islands. An important constraint in the topology is that each island has exactly one incoming and one outgoing edge.

• 5. The migration process takes place among the islands following the chosen ring topology.

• 6. If the maximum number of iterations has not been reached the algorithm repeats from step 3. Otherwise, the algorithm ends.

Fig. 1

General framework of iCSPM2

Fig. 2

Random ring topologies (Abed-alguni 2019)

Algorithm 1 has two differences compared to iCSPM. Firstly, it divides the islands among four variations of CS: CS1, CS10, CSJ and CS11 (Line 7). The optimization loop (Lines 12–25) is applied to each island according to the CS variation assigned to it (Line 13). This allows the optimization loops to be performed in parallel because the islands only communicate with each other during the migration process. Secondly, it applies EOBL to a fraction ($p_b$) of the elite solutions in each island (Line 20). The elite-opposite solutions are generated using the procedure and equations discussed in Sect. 2.5. An opposite-elite solution replaces its corresponding elite solution if it has a better fitness than the elite solution.

The generated candidate solutions at lines 6, 13 and 20 in Algorithm 1 are composed of continuous values that can be used directly with continuous optimization problems. However, in order to solve discrete optimization problems such as the PFSSP, these values should be converted to meaningful discrete values. In this paper, we also show how iCSPM2 can be used with the PFSSP. To this end, the SPV method (Ali et al. 2019) can be used with iCSPM2 to convert candidate solutions’ continuous decision variables into discrete ones (job numbers).

SPV is applied as follows. Let $\mathbf {\overrightarrow{X}^i}=<x^i_1,x^i_2, \ldots , x^i_m>$ be a candidate solution that contains m real values. The position values in $\mathbf {\overrightarrow{X}^i}$ are sorted in ascending order and the ordered positions are used to generate a job permutation $\pi$. An example of the SPV method is shown in Table 1, where $\mathbf {\overrightarrow{X}^i}=<x_1, x_2, x_3, x_4>=<7.86, 12.11, 10.46, 5.66>$ and the calculated job permutation is $\mathbf {\pi ^i}=<4, 1, 3, 2>$, since $x_4> x_1> x_3 > x_2$.

Table 1 A candidate solution using the SPV method

5 Experiments

This section describes the experiments conducted to compare iCSPM2 to existing algorithms. Section 5.1 summarizes the experimental setup for all the algorithms and Sect. 5.2 describes the benchmark functions used in the experiments. The experimental design of the paper is described in Sect. 5.3. Section 5.4 then compares the sensitivity of iCSPM2 to its island model parameters to that of iCSPM. After this, Sect. 5.5 provides a comparison of the simulation results of iCSPM2 to the reported simulation results in Abed-alguni and Barhoush (2018) of four popular optimization algorithms (DGWO, L-SHADE, FWA-DM and MHDA), with statistical analysis provided in Sect. 5.6. Finally, Sect. 5.7 provides a comparison of the performance of iCSPM2 to the performance of GAIbH and MASC using 12 instances of Taillard’s benchmark.

5.1 Setup

The experiments were executed using a 3.5GHz 8-core Intel Xeon W processor, Turbo Boost up to 4.0GHz with 32GB of DDR4 ECC memory running macOS 11.0.1, Big Sur. The algorithms were all programmed in Java.

5.2 Benchmarking

The 15 benchmark functions described in Table 2 are well-recognized functions that have frequently been used to evaluate the efficiency of optimization algorithms (Hasan et al. 2014; Doush et al. 2014). These functions were used in Sect. 5.4 to test the sensitivity of iCSPM and iCSPM2 to the island model parameters.

Table 2 Details of popular 15 benchmark functions

The 30 single-objective real-parameter optimization functions of CEC2014 are various complex functions: $F_1$ - $F_3$ are unimodal functions, $F_4$ - $F_{16}$ are multimodal functions, $F_{17}$ - $F_{22}$ are hybrid functions, and $F_{23}$ - $F_{30}$ are composite functions (Liang et al. 2013). The search range of each function is [-100, 100]$^D$. We have previously used the single-objective functions of CEC2014 to compare the convergence speeds and the reliability of six popular optimization algorithms: CS, GWO, DGWO (Abed-alguni and Barhoush 2018), L-SHADE (Tanabe and Fukunaga 2014), MHDA (Ks and Murugan 2017) and FWA-DM (Yu et al. 2014). In Sect. 5.5, we compared the simulation results of iCSPM2 using the single-objective functions of CEC2014 to the four best performing algorithms in Abed-alguni and Barhoush (2018) (DGWO, L-SHADE, MHDA and FWA-DM).

Taillard’s benchmark (Taillard 1990) is a benchmark for evaluating discrete optimization problems. In Sect. 5.7, we compared iCSPM2 to two powerful optimization-based scheduling algorithms (generalized accelerations for insertion-based heuristics (GAIbH) (Fernandez-Viagas et al. 2020) and memetic algorithm with novel semi-constructive crossover and mutation operators (MASC) Kurdi 2020) using 12 instances of Taillard’s benchmark for the PFSSP.

5.3 Experimental design

In order to determine how sensitive the performance of iCSPM and iCSPM2 are to the island model parameters (s, $M_f$, $M_r$), the experiments in Sect. 5.4 were run over nine scenarios (presented in Table 3). The main goal of Scenarios 1–3 is to understand the relationships between the number of islands s and the performance of iCSPM and iCSPM2. The purpose of Scenarios 4-6 is to measure the effect of migration frequency $M_f$ on the performance of iCSPM and iCSPM2. The goal of Scenarios 7–9 is to investigate the migration rate $M_r$’s influence on the performance of iCSPM and iCSPM2. Fig. 3 shows the graphical representation of the values in Table 3.

Table 3 Nine experimental scenarios to evaluate the sensitivity of iCSPM and iCSPM2 to the parameters of island model

Fig. 3

Boxplot of the experimental scenarios

In all the experiments, the size of the population, n, and the fraction of abandon solutions, $p_a$, in iCSPM and iCSPM2 were dynamically tuned over multiple simulations as recommended in Abed-alguni and Alkhateeb (2017). The maximum number of iterations of each algorithm was limited to 10,000. The control parameters of iCSPM2 were as follows: $L=1$ in the Lévy flight method, PAR=0.3 in the PA method and the fraction of elite solutions $p_b$ was set to a value equal to the value of $p_a$.

Section 5.5 presents a comparison of iCSPM2 to the reported simulation results in Abed-alguni and Barhoush (2018) for four popular optimization algorithms (DGWO Abed-alguni and Barhoush 2018, L-SHADE Tanabe and Fukunaga 2014, FWA-DM Yu et al. 2014 and MHDA Ks and Murugan 2017). In Sect. 5.6, a nonparametric statistical test (Friedman’s test Derrac et al. 2011; Friedman 1940) is applied to the FEV for each of the 30 CEC 2014 functions in Table 7.

5.4 Sensitivity analysis of iCSPM2 to the parameters of Island model

Tables 4, 5 and 6 show the average over 50 runs of the best objective values of the experimental scenarios in Table 3 for the 15 benchmark functions in Table 2. The best objective value for a benchmark function is its lowest value that is achieved after applying the tested optimization algorithms to it for a specified number of iterations (MaxItr). The number of decision variables (dimension) of each benchmark function was 10 except for the two-dimensional six-hump camel-back function ($f_10$). In each table, two rows correspond to each function. The first row contains the simulation results of iCSPM, while the second row contains the results of iCSPM2. Each row’s best results are marked with bold font.

Table 4 The effect of various values of s on the performance of iCSPM and iCSPM2. D = 10, runs = 50 and number of iterations = 10,000

Table 5 The effect of various values of $M_f$ on the performance of iCSPM and iCSPM2. D = 10, runs = 50 and number of iterations = 10,000

Table 6 The effect of various values of $M_r$ on the performance of iCSPM and iCSPM2. D = 10, runs = 50 and number of iterations = 10,000 and number of runs is 50

Table 4 shows the experimental results of the first three scenarios in Table 3. The results clearly indicate that both iCSPM and iCSPM2 performance are sensitive to the value of s. Their performance becomes better with every increase in the value of s. This is expected because any increase in the value of s means that more search regions with smaller sizes are explored simultaneously. Besides, larger islands have better diffusion than smaller islands (Abed-alguni 2019; Abed-Alguni et al. 2019; Al-Betar et al. 2019; Al-Betar and Awadallah 2018). Therefore, $s=12$ was selected for the next six scenarios.

Table 5 shows the simulation results of the next three experimental scenarios (Scenario4, Scenario5 and Scenario6), which were designed to show the effect of different values of $M_f$ on the convergence behavior of iCSPM and iCSPM2. The rank of the scenarios in Table 5 were: Scenario4 ($M_f=100$), Scenario5 ($M_f=50)$ and finally Scenario6 ($M_f=500)$. This means that low and medium migration frequencies generate better results than large-migration frequencies. This may be because large-scale migrations have more effects on the diversity of populations in the islands compared to low-scale migrations. The value of $M_f=100$, which achieved the best results in Table 5, was used in the last three experimental scenarios.

Table 6 shows the simulation results for the last three experimental scenarios (Scenario7, Scenario8 and Scenario9). There is no clear indication in Table 6 on the effects of low and high values of $M_r$ on the performance of iCSPM and iCSPM2. This is maybe because of the small dimension of the benchmark functions.

The results in Tables 4, 5 and 6 show that iCSPM and iCSPM2 achieved similar results for 7 benchmark functions ($f_1, f_ 2, f_3, f_5, f_7, f_8, f_9$). However, iCSPM2 outperformed iCSPM for 8 out of 15 functions. These observations suggest that iCSPM2 has better performance than iCSPM.

5.5 Comparison between iCSPM2 and other well-known optimization algorithms

We used the 30 single-objective, real-parameter, optimization, functions of CEC2014, described in Sect. 5.2, to compare the simulation results of iCSPM2 (Scenario 8) to the reported simulation results in Abed-alguni and Barhoush (2018) for four popular optimization algorithms (DGWO Abed-alguni and Barhoush 2018, L-SHADE Tanabe and Fukunaga 2014, FWA-DM Yu et al. 2014 and MHDA Ks and Murugan 2017).

Table 7 shows the function error values (FEV) for the 30 CEC 2014 functions. FEV is the distance between the best objective value calculated over multiple runs by an optimization algorithm and the actual optimal value. In the table, the best FEV for each function is highlighted in Bold. It is obvious that iCSPM2 outperforms all the algorithms in Table 7 by achieving the lowest FEV values for 14 out of the 30 functions. We suggest three possible reasons for the superior performance of iCSPM2. Firstly, it partitions the population of n candidate solutions for a given optimization between s independent islands and then it equally divides them among 4 efficient variations of CS: CS1, CS10, CSJ and CS11. Secondly, the island model and its migration process provide a suitable environment for unfitted solutions to evolve to better solutions. Thirdly, it uses EOBL to explore the neighborhood of the elite solutions in the population of each island.

In addition, L-SHADE is the algorithm with the second best performance in Table 7. It achieved the lowest FEV for almost a third of the 30 CEC2014 functions, which may be because L-SHADE dynamically adjusts its internal parameters and population size during its optimization process.

Figure 5 shows the convergence charts of iCSPM2, DGWO and L-SHADE over the first 1000 iterations for selected functions from CEC2014 (F$_2$, F$_5$, F$_{11}$, F$_{15}$, F$_{20}$, F$_{27}$). The charts clearly show that iCSPM2 converges to good solutions faster than DGWO and L-SHADE. This is because iCSPM2 is based on the island model and obtains the advantages of the multiple mutation methods it uses with CS. The charts also show that L-SHADE is the second fastest algorithm followed by DGWO.

Table 7 Simulation results for iCSPM2, DGWO, L-SHADE, FWA-DM and MHDA

Table 8 Results of Friedman’s test

5.6 Results of statistical tests

The results of Friedman’s test (Table 8 and Fig. 4) are statistical information about the ranks of iCSPM2, DGWO, L-SHADE, MHDA and FWA-DM. In this table, the best rank is marked with bold font. The order of ranks of the algorithms was as follows: iCSPM2, L-SHADE, DGWO, MHDA and FWA-DM, respectively. This means that iCSPM2 performed best amongst the tested algorithms (Fig. 5).

5.7 Performance analysis of iCSPM2 in comparison to GAIbH and MASC using Taillard’s benchmark for PFSSP

We compared the performance of iCSPM2 to the performance of GAIbH and MASC using 12 instances of Taillard’s benchmark (described in Sect. 5.2). Table 9 shows the mean makespans over 50 runs and the ARD (average relative difference) values. An ARD value shows the relative difference between the obtained mean value using an optimization algorithm to the best-known value for a given benchmark function. The ARD values were computed using the following equation Wang et al. (2017):

$$\begin{aligned} ARD = \frac{100 \times (C^{\text {opt}} - C^{A})}{C^{\text {opt}}} \end{aligned}$$

(18)

where $C^{A}$ is the makespan achieved by the tested algorithm and $C^{opt}$ is the upper bound with the minimum value for the tested instance of Taillard’s benchmark.

The simulation results in Table 9 suggest that iCSPM2 outperforms GAIbH and MASC. iCSPM2 achieved the best known results (lowest Mean and ARD) for 10 instances out of the 12 instances of Taillard’s benchmark and it also scored the lowest total average ARD (0.23%). This may be because iCSPM2 incorporates four powerful variations of CS into the island model, which increases the diversity of its candidates solutions and improves its convergence behavior.

6 Discussion

The simulation results in Table 7 showed that iCSPM2 outperforms all the algorithms by achieving the lowest FEV values for 14 out of the 30 CEC 2014 functions ($F_1$-$F_4$, $F_{6}$, $F_{9}$-$F_{12}$, $F_{16}$, $F_{20}$, $F_{23}$, $F_{27}$). iCSPM2 also achieved the second lowest FEV values for 12 out of the 30 CEC 2014 functions ($F_5$, $F_7$, $F_{13}$, $F_{14}$, $F_{17}$, $F_{19}$, $F_{21}$, $F_{25}$, $F_{26}$, $F_{28}$-$F_{30}$). L-SHADE provides competitive results (second best performing algorithm with the lowest FEV values for 9 out of the 30 CEC 2014 functions) compared to iCSPM2. This is mainly because it follows a dynamic adjustment procedure for its internal parameters and population size during its optimization process. Besides, it is based on the DE algorithm, which is one of the most efficient basic evolutionary algorithms (Tanabe and Fukunaga 2014). According to Table 7, DGWO is the third best performing algorithm and it provides competitive results to the results of iCSPM2 and L-SHADE. This is because DGWO is a variation of GWO that is based on the island model that improves the diversity and performance of GWO. The performance of FWA-DM and MHDA are the worst among all the algorithms in Table 7. This is maybe because the exploration operators of these algorithms are not efficient as the ones of iCSPM2, L-SHADE and DGWO. Further, the results of Friedman’s test in Table 8 showed that iCSPM2 achieved the highest rank among all tested algorithms, which means that the simulation results of iCSPM2 are significant and provide sufficient evidence that iCSPM2 is the best performing algorithm. The results of Friedman’s test also confirm that DGWO is the third best performing algorithms and strongly competitive to L-SHADE.

Fig. 4

The average ranks of the algorithms according to Friedman’s Test

The results in Table 9 also showed that iCSPM2 is the best performing algorithm by achieving the lowest ARD values for 10 out of the 12 Taillard’s benchmark instances for the PFSSP. Note that iCSPM2 provided the lowest ARD values for the most complex instances of Taillard’s benchmark (Ta110 and Ta120). The results also showed that iCSPM2 has the lowest average ARD value (0.23) for the 12 instances of Taillard’s benchmark over 50 independent runs. This means that iCSPM2, in general, provides better schedules for the 12 instances of Taillard’s benchmark than other tested algorithms. On the other hand, MASC in Table 9 is the second best performing algorithm and also provides competitive results compared to the results of iCSPM2. This may be because it combines the strengths of the simulated annealing and Nawaz–Enscore–Ham algorithms into the GA algorithm. Note that GAIbH is the worst performing algorithm in Table 9. This may be because GAIbH is only based on a heuristic procedure that calculates the completion times of all jobs in a job permutation based on the job position in other existing partial job permutations.

There are three main explanations for the superior performance of iCSPM2 in solving the CEC 2014 suit and 12 instances of Taillard’s benchmark for the PFSSP.

Firstly, iCSPM2 is based on the island model, while the other tested algorithms (DGWO, L-SHADE, MHDA, FWA-DM, GAIbH and MASC) are not based on the island model. The island model provides several advantages when integrated with an evolutionary algorithm (Abed-alguni and Barhoush 2018; Al-Betar et al. 2019; Al-Betar and Awadallah 2018; Awadallah et al. 2020). It increases the chances of candidate solutions with low objective values evolving into better ones. It can also be run in parallel on several processing devices or a device that supports parallel processing. The migration mechanism in the island model regulates population diversity and lowers the possibility of early convergence.

Fig. 5

The convergence charts of iCSPM2, DGWO and L-SHADE over the first 1000 iterations for selected functions from CEC2014 (F$_2$, F$_5$, F$_{11}$, F$_{15}$, F$_{20}$, F$_{27}$)

Table 9 Results of iCSPM2, GAIbH and MASC

Secondly, the four variations of CS used in iCSPM2 have unique advantages. CS1 utilizes the Lévy flight mutation, which has a better exploration capability than the random mutation method (Yang and Deb 2009). CS10 uses the HDP mutation method that can sample the entire search space between the lower and upper bounds of a decision variable regardless of its value (Abed-Alguni and Paul 2018; Abed-alguni 2019; Alawad and Abed-alguni 2020). CSJ uses the Jaya mutation method that mutates the candidate solutions using stochastic moves based on the best and worst candidate solutions (Rao 2016). CS11 uses the pitch adjustment mutation, which is known for its quick convergence (Abed-Alguni and Paul 2018; Al-Betar et al. 2015). In summary, we conclude that the mutation methods in iCSPM2 collectively provide it with strong exploration and exploitation capabilities.

Finally, iCSPM2 utilizes two well-known opposition learning approaches (OBL and EOBL), while the other tested algorithms in Sect. 5 do not utilize any opposition learning approach. The OBL approach is used in the initialization step of iCSPM2 to widen the search are by considering the opposite solutions of randomly generated solutions. This helps in increasing the diversity of initial population. The EOBL approach speeds up the convergence of iCSPM2 by exploring the opposite solutions of the best-known candidate solutions (Paiva et al. 2017; Zhang et al. 2017).

7 Conclusions and future work

This paper introduced an improved variation of the island-based Cuckoo Search algorithm by the name island-based Cuckoo Search with elite opposition-based learning and multiple mutation methods (iCSPM2). The source code of iCSPM2 is publicly available at https://github.com/bilalh2021/iCSPM2. The new algorithm distributes the population of candidate solutions for a given optimization among s independent islands and then it evenly divides the islands among 4 variations of Cuckoo Search (Cuckoo search via Lévy flights, Cuckoo Search with polynomial mutation, Cuckoo Search with Jaya mutation, Cuckoo Search with pitch adjustment mutation). This means that each variation of Cuckoo Search is applied to n/4 islands. Besides, iCSPM2 uses elite opposition-based learning to explore the neighborhood of elite solutions in the population of each island. iCSPM2 is capable of solving complex, scheduling problems as well as continuous optimization problems. This is because it uses the smallest position value method with complex scheduling problems, such as the permutation flow shop scheduling problem, to convert the continuous candidate solutions into discrete ones.

iCSPM2 has been shown to perform better than a number of other well-known optimization algorithms through several experiments conducted in order to test its performance using popular benchmark suites. Firstly, the sensitivity of iCSPM and iCSPM2 to the number of islands, s, the migration frequency, $M_f$, and the migration rate, $M_r$, were studied and analyzed based on different experimental scenarios. Overall results indicate that higher values of s and lower values of $M_f$ give better performance for both iCSPM and iCSPM2. However, it remains unclear whether high or low values of $M_r$ improve either algorithm’s performance. In any case, the experimental results indicate that iCSPM2 outperforms iCSPM. Secondly, performance of iCSPM2 was compared against four well-known swarm optimization algorithms: DGWO (Abed-alguni and Barhoush 2018), L-SHADE (Tanabe and Fukunaga 2014), MHDA (Ks and Murugan 2017) and FWA-DM (Yu et al. 2014) using the single-objective IEEE-CEC 2014 functions. The overall results show that iCSPM2 performs better than the other well-known swarm optimization algorithms on these functions. Finally, we conducted experiments using 12 instances of Taillard’s benchmark for the PFSSP to show that iCSPM2 is an efficient algorithm for scheduling problems. In these experiments, iCSPM2 was compared to two efficient discrete evolutionary algorithms (GAIbH Fernandez-Viagas et al. 2020 and MASC Kurdi 2020). The results indicate that iCSPM2 is a better scheduling algorithm than GAIbH and MASC.

However, iCSPM2 has two main limitations. Firstly, the computational complexity of iCSPM2 is O($M_w.s.M_f .k$), which is more than the computational complexity of the basic CS algorithm (O(MaxItr.n)). Hence, we recommend iCSPM2 be executed over s parallel devices, which will reduce its computational complexity to O($M_w.M_f.k$). Secondly, iCSPM2 can only be directly applied to single-objective optimization problems. Therefore, one of our future goals is to develop a variation of iCSPM2 that can solve some multi-objective optimization problems.

In the future, the following would be interesting research studies:

• Incorporating the mutation methods from Equilibrium optimizer (Faramarzi et al. 2020), Jaya (Rao 2016), Grasshopper (Saremi et al. 2017), L-SHADE and MHDA into iCSPM2.

• Applying iCSPM2 to multi-agent cooperative reinforcement learning (Abed-alguni et al. 2015a, b; Abed-alguni and Ottom 2018; Abed-Alguni et al. 2016) based on the models described in Abed-alguni (2018, 2017); Abed-Alguni (2014).

• Incorporating iCSPM into an intelligent distributed recommender system based on the problem model discussed in Alawad et al. (2016).

• Incorporating the island model with the arithmetic optimization algorithm (Abualigah et al. 2021) and Aquila optimizer (Abualigah et al. 2021) to solve the feature-section problem described in Abualigah et al. (2019).

• Finally, it could be possible to improve other heuristics and metaheurisics by enhancing them with different mutation methods and elite opposition-based learning in a similar manner to how island-based Cuckoo Search was improved in this paper.