1 Introduction

Combinatorial optimization [1] is a subfield of discrete mathematics where the decision variables are combinations or permutations that respect a predefined set of constraints. Such optimization problems can be defined as given finite objects ℘ and an objective function [2]:

$$ f:\wp \to O $$
(1)

where Ο is an ordered set that associates with a cost or a profit of each object. The objective is to find an object ℘ with value (cost or profit) that best minimize or maximize the objective function with respect to some constraints.

One of the most important combinatorial optimization problems is bin packing problem (BPP). The classical bin packing problem consists of a set of items that need to be packed into one bin only. Each item has a weight and each bin has a capacity. The main goal of the problem is to pack all items in the few possible number of bins where each bin does not exceed its capacity. Thereby, BPP involved in each field contains packing problem such as multiprocessor scheduling [3], supply chain [4], logistics [5], telecommunications [6], and cloud computing [7].

The contribution of this paper is to propose a new variant of whale optimization algorithm named improved Lévy-based whale optimization algorithm (ILWOA). According to the no-free-lunch theorem [8, 9] in optimization, there is no algorithm to solve all optimization problems. It has observed that WOA performs well on combinatorial problems, and this motivated our attempts to improve and adapt this algorithm. Therefore, the exploration capabilities of whale optimization algorithm (WOA) [10] is enhanced with deploying Lévy flight for whale movements. Second, WOA is embedded with a new mutation phase to improve convergence speed. Finally, a logistic chaotic map is used for efficient switch between exploration and exploitation phases. In order to map between the continuous search space and the combinatorial one, the largest order value (LOV) [11] technique is applied. By conducting experiments and statistical analysis, the effectiveness of amendments to improve the performance of WOA and superiority of the improved algorithm comparators to solve the given problem were proved.

The remaining structure of this paper is as follows. An in-depth literature review is given in Sect. 2. Problem formulation is provided in Sect. 3. The WOA and proposed algorithm are discussed in Sects. 4 and 5. The experimental results are shown in Sect. 6.The results analysis is presented in Sect. 7. Finally, the conclusions and future works are provided in Sect. 8.

2 Literature review

BPP belongs to NP-hard problems [12] so that using exact methods (e.g., branch and bound algorithm [13] and branch and price algorithm [14]) or basic heuristic algorithms may become deficient for handling large BPPs. Initially, many heuristics were proposed for solving BPP as next fit [15], first fit [15], worst fit [16], best fit [17], graph-based algorithm [18], etc. Indeed, heuristic algorithms can guarantee a good solution for small-scale instances and they can be defined as “a type of strategy that dramatically limits the search for solutions” [19, 20]. Thus, the new trends are directed towards using meta-heuristic algorithms which are not problem-specific heuristic that can find a high-quality solution through the tradeoff between the exploitation and exploration of search space [21, 22]. For example, the authors in [23, 24] solved BPP with genetic algorithm (GA) [25] which was combined with grouping mechanism for handling the problem. In [26], Layeb and Boussalia combined cuckoo search (CS) [27] algorithm with a binary quantum technique for solving BPP. Also, the authors in [28] applied CS for solving the problem but they used FF and ranked order value (ROV) [29] for adapting the algorithm. In [30], Levine and Ducatelle proposed ant system (AS) algorithm [31] with local search technique for solving the problem. While in [32], the authors hybridized the previous technique with firefly algorithm (FA) [33]. Sonuc et al. [34] solved BPP with simulated annealing (SA) [35] which combined with a swap function for enhancing the solution.

Roughly speaking, the main challenge of bin packing problem is obtaining a good solution but with less time. In continuous search space, WOA can obtain a high-quality solution in negligible time. Thereby, this paper employs the improved WOA capabilities to solve BPP with more convergence speed.

3 Problem formulation

In general, BPP can be defined as follows: Given a set of items with their weights, and a set of fixed-size bins, find the minimum number of bins that can hold all items. Mathematically, the formulation of BPP can be expressed as an integer programming problem as follows [36]:

$$ {\displaystyle \begin{array}{c}\mathit{\min}\sum \limits_{i=1}^n{y}_i\\ {}s.t.\kern0.5em {\sum}_{j=1}^n{w}_j{x}_{ij}\le {cy}_ii\in N=\left\{1,\dots, n\right\},\\ {}\sum \limits_{i=1}^n{x}_{ij}=1,\kern0.5em j\in N,\\ {}\begin{array}{cc}{y}_i\in \left\{0,1\right\},& i\in N,\end{array}\\ {}\begin{array}{cc}{x}_{ij}\in \left\{0,1\right\},& i\in N,j\in N,\end{array}\end{array}} $$
(2)

where y i is a binary variable that indicates whether bin i contains items, x ij is a binary variable that indicates whether if item j is assigned to bin i, w j is the weight of item j, 푐 is bin capacity, and n is number of available bins. BPP can be extended with no conceptual difficulty to higher dimensions (two or three dimensions) or other variants like knapsack problem [37], bin packing with conflicts [38], colored bin packing [39], etc. Also, BPP can be divided to online and offline problem according to the number of items is fixed or variable.

4 Whale optimization algorithm

4.1 Biological inspiration

Humpback whales are known for their unique acrobatic aerial breaching, the ability to configure a language for mating and hunting through their complex sounds, and the rare hunting “bubble net” strategy [40]. For the feeding strategy, the humpback whales can intelligently corporate together in order to trap fish into a ring of air by emitting a stream of bubbles. In particular, the emitted bubbles take two shapes: a spiral shape and a shrinking circle shape (as shown in Fig. 1). After that, the trapped fish are swallowed up by all humpback whales [41]. For more information, see [42,43,44].

Fig. 1
figure 1

Whale hunting strategy

Full size image

4.2 Main procedures of WOA

Whale optimization algorithm (WOA) [10] is a novel population and swarm intelligence-based meta-heuristic that was inspired by the bubble-net feeding strategy previously discussed, i.e., after the humpback whales determine the prey position, they begin to emit a stream of bubbles in two manners (shrinking circle and spiral shape) around their prey. In WOA, the search for the prey represents the exploration phase and the bubble net with shrinking circle and spiral shape represent exploitation phase. Mathematically, the fish positions are randomly initialized which represent the initial population and evaluated in order to find the current best solution. Then, the other candidate solutions are updated according to the current best solution as follows:

$$ \overrightarrow{D}=\left|\overrightarrow{C}.\overrightarrow{x^{\ast }}(t)-\overrightarrow{x}(t)\right| $$
(3)
$$ \overrightarrow{x}\left(t+1\right)=\overrightarrow{x^{\ast }}(t)-\overrightarrow{A}\bullet \overrightarrow{D} $$
(4)

where \( \overrightarrow{x^{\ast }}(t) \) is the current best solution at time t, and \( \overrightarrow{C} \) and \( \overrightarrow{A} \) are two coefficient vectors that can be calculated as

$$ \overrightarrow{A}=2\overrightarrow{a}\bullet \overrightarrow{r}-\overrightarrow{a} $$
(5)
$$ \overrightarrow{C}=2\bullet \overrightarrow{r} $$
(6)

where \( \overrightarrow{\mathrm{a}} \) is linearly decreased from 2 to 0 during iterations which represents the shrinking encircling behavior and \( \overrightarrow{\mathrm{r}} \) is a random number between [0, 1].

For better diversification of the search space, WOA combines two exploration search mechanisms (depending on the current best or random solution) that switched according to the value of \( \overrightarrow{A} \). In other words, if \( \overrightarrow{A}<1 \), then the new solution is generated using Eq. (3). In other cases, the new solution is calculated as the follows:

$$ \overrightarrow{D}=\left|\overrightarrow{C}.\overrightarrow{x_r}(t)-\overrightarrow{x}(t)\right| $$
(7)
$$ \overrightarrow{x}\left(t+1\right)=\overrightarrow{x_r}(t)-\overrightarrow{A}\bullet \overrightarrow{D} $$
(8)

where \( \overrightarrow{x_r}(t) \) is a solution selected randomly from the same population.

For simulating the humpback whale spiral movement around their prey (the current best solution), the following formulation is used:

$$ {\overrightarrow{D}}^{\prime }=\left|\overrightarrow{x^{\ast }}(t)-\overrightarrow{x}(t)\right| $$
(9)
$$ \overrightarrow{x}\left(t+1\right)={\overrightarrow{D}}^{\prime}\bullet {e}^{bl}\bullet \cos \left(2\pi l\right)+\overrightarrow{x^{\ast }}(t) $$
(10)

where b is a predefined constant for defining the shape of the logarithmic spiral and l is a random number between [−1, 1].

figure a

Pseudocode 1. WOA.

During WOA iterations, a probability of 50% is assumed to alter between the searching of food and hunting mechanisms to update the candidate solutions as follows:

$$ \overrightarrow{x}\left(t+1\right)=\left\{\begin{array}{c}\overrightarrow{x}(t)-\overrightarrow{A}\bullet \overrightarrow{D}\kern7.5em ,r<p\ \\ {}{\overrightarrow{D}}^{\prime}\bullet {e}^{bl}\bullet \cos \left(2\pi l\right)+\overrightarrow{x^{\ast }}(t)\kern1.75em ,r\ge p\end{array}\right. $$
(11)

where \( \overrightarrow{x^{\ast }}(t) \) is the current best solution at time t, p is equal to 0.5, and r is a random number between [0, 1] (see Pseudocode 1).

5 Improved ILWOA

Despite the efficiency of WOA, its convergence rate and performance still need to be improved. For this reason, several enhancements are proposed in this paper in order to improve the performance and the convergence rate of WOA. The pseudocode of the proposed algorithm is shown in Pseudocode 2. Also, the flowchart of ILWOA is presented in Fig. 2.

Fig. 2
figure 2

ILWOA flowchart

Full size image
figure b

Pseudocode 2. ILWOA.

5.1 The application of ILWOA to BPP

5.1.1 Discretization of search space

The basic version of WOA was proposed for solving optimization problems in continuous search space. For applying the proposed algorithm in combinatorial search space, LOV [11] is used. LOV can be used to convert the continuous solution to a discrete one through descending order of values as shown in Fig. 3. For BPP, the discrete solution means the order of item allocation to bins which are filled using BF algorithm. In BF, each item is placed in a bin which will leave the least leftover space. If the item does not fit in any bin, a new bin is opened.

Fig. 3
figure 3

Mapping between continuous and discrete solution using LOV

Full size image

5.1.2 Objective function

Roughly speaking, the use of the bin number as a fitness function may lead to the algorithm stagnation because there can be many permutations that have the same number of bins. So, it is more efficient to use bin occupancy as a mean of the solution evaluation. The following formulation was introduced by Hyde et al. [45]:

$$ \mathit{\min}F=1-\left(\frac{\sum \limits_{i=1}^n{\left({ocup}_i/c\right)}^k}{n}\right) $$
(12)

where n is the number of used bins, ocup i is the occupancy of each bin i, c is the bin capacity, and k is a constant (usually k = 2) .

5.2 Lévy flight distribution

Lévy distribution is a mathematical model used to describe anomalous diffusion which has infinite mean and variance that cause much longer movement from its current position (see Fig. 4); thus, it is more efficient in the search space exploration [46]. In the proposed algorithm, the parameter \( \overrightarrow{\mathrm{C}} \) is replaced with a random step drawn from isotropic Lévy distribution as follows:

$$ L\overset{\hbox{'}}{\mathrm{e}} vy\sim \frac{\lambda \varGamma \left(\lambda \right)\mathit{\sin}\left(\frac{\pi \lambda}{2}\right)}{\pi}\frac{1}{s^{1+\lambda }}\kern2em ,\left(s\gg {s}_0>0\right) $$
(13)
$$ s=\frac{U}{{\left|V\right|}^{\lambda^{-1}}}\kern0.5em ,\kern0.75em U\sim \left(0,{\sigma}_u^2\right),\kern0.75em V\sim \left(0,{\sigma}_v^2\right) $$
(14)
$$ {\sigma}_u^2={\left[\frac{\varGamma \left(1+\lambda \right)}{\lambda \varGamma \left(\left(1+\lambda \right)/2\right)}.\frac{\mathit{\sin}\left(\frac{\pi \lambda}{2}\right)}{2^{\left(\lambda -1\right)/2}}\right]}^{1/\lambda },{\sigma}_v^2=1 $$
(15)

where \( L\overset{\hbox{'}}{e} vy \) is a step size drawn from Lévy distribution, Γ(λ) is the standard gamma function with large steps s > 0 which is drawn according to Mantegna algorithm [47], U and V are samples drawn from Gaussian normal distribution where mean is equal zero, and \( {\sigma}_u^2 \) and \( {\sigma}_v^2 \) are variances [48].

Fig. 4
figure 4

Isotropic Lévy Distribution

Full size image

5.3 Chaotic maps

Mathematically, the chaotic maps can be defined as the following: given a set Λ (where f : Λ → Λ), f is considered a chaotic map on Λ if [49]:

  1. 1.

    f is unpredictable as it sensitively depends on initial conditions.

  2. 2.

    fcannot be decomposed to subsystem as it is transitive based on a topology.

  3. 3.

    f has an element of regularity because points are periodically dense in Λ.

In other words, Chaotic maps are evolutionary functions that produce a deterministic bounded sequence of random numbers depending on initial condition. There are different types of maps like logistic map, Chebyshev map, tent map, etc. After several trials of different chaotic maps, logistic (or quadratic) is selected in the proposed algorithm because it obtained the best results (see Fig. 5). Chaotic map is selected for determining the value of the switching probability p because of being random-like, non-period, and non-converging for parameter adaptation. The logistic map can be formulated as

$$ {x}_{n+1}=a{x}_n\left(1-{x}_n\right)\kern2.75em ,x\in \left(0,1\right),0<a\le 4 $$
(16)

where a is a positive constant (sometimes also denoted “biotic potential”) that gives the logistic map. Figure 6 shows a comparative example between objective function values (Eq. (12)) of logistic map and other seven maps including Chebyshev map, Gaussian map, tent map, circle map, piecewise map, iterative map, and sine map. It is clear that logistic reaches the minimum values of objective function during 5 iterations with 10 search agents.

Fig. 5
figure 5

Logistic chaotic map simulation

Full size image
Fig. 6
figure 6

Logistic map vs. other maps

Full size image

5.4 Mutation phase

In ILWOA, mutation phase is done before the end of each iteration, i.e., the current best number of bins is checked whether it reached the optimal or not. The optimal solution can be computed as

$$ \mathrm{optimal}\ \mathrm{number}\ \mathrm{ofbins}=\frac{\sum \mathrm{itemsizes}}{\mathrm{bin}\ \mathrm{capacity}} $$
(17)

If the current best number of bins is optimal, the search stops. Otherwise, it is randomly modified through mutation phase, which is divided to three operators: swap, displacement, and reversion. The swap operator selects and swaps two items’ indexes randomly [50]. Displacement operator cuts a random subset of item indexes and inserts it in another random place [51]. Reversion operator cuts a random subset of items’ indexes and reverses it [52] (see Fig. 7).

Fig. 7
figure 7

Mutation operators

Full size image

6 Experimental results

In order to test the validity of the proposed algorithm, two experiments are conducted on different benchmarks (all datasets can be downloaded from [53]). All experiments are carried out on a 64-bit operating system with a 2.60 GHz CPU and 6 GB RAM. In addition, the experimental results are analyzed with non-parametric Friedman test [54] to show the differences in performance between ILWOA and the compared algorithms. Friedman test is a non-parametric, rank-based version of one-way ANOVA with repeated measures which can be performed on more than two dependent samples. In other words, Friedman test compares the means of three or more variables measured on the same respondents.

The first experiment is conducted on selected benchmarks from Scholl uniformly distributed instances [55] which were divided into three classes according to its difficulty: easy, medium, and hard class. ILWOA is compared with all other population and swarm intelligence-based algorithms that have solved BPP, including adaptive cuckoo search (ACS) algorithm [28], firefly colony optimization (FCO) algorithm [32], quantum inspired cuckoo search algorithm (QICS) [26], firefly algorithm (FA) [33], and ant system algorithm (AS) [35]. The results of ACS, QICS, and AS are obtained from [28] while the results of FA are obtained from [32]. For parameter settings, the number of search agents is set to 10 agents and the maximum number of iterations are set to only 5 iterations, whereas for ACS, it needed 20 search agent and 100 iterations in the literature which indicate the ability of ILWOA to find a good solution with a few number of search agents and iterations. Table 1 shows the experimental results of easy instances. Besides, Table 2 and Fig. 8 present the descriptive statistics of the easy class experiment and the results of Friedman test, respectively. As shown, the proposed algorithm finds the best-known solution like other algorithms (except FA) and their performances are similar. While for the medium and hard classes, the results of the proposed algorithm are superior for many instances (bolded values) as shown in Tables 3 and 5. The descriptive statistics and Friedman test results of the medium class are presented in Table 4 and Fig. 9, respectively (Table 5). The descriptive statistics of the hard class are presented in Table 6 and Friedman test results in Fig. 10. It is clear that the proposed algorithm has the same descriptive statistics and ranked mean as ACS for the medium class. For the hard class, the result of ILWOA for ”HARD7” instance outperforms other algorithms even ACS. In addition, the proposed algorithm scores the minimum mean as shown in Table 6 and the minimum ranked mean as shown in Fig. 10. Although results of ACS and ILWOA are almost similar, the proposed algorithm is significantly faster than ACS as ILWOA can find a good solution with a few number of search agents and iterations.

Table 1 Experimental results of easy class
Full size table
Table 2 Descriptive statistics of easy class
Full size table
Fig. 8
figure 8

Friedman test of easy class

Full size image
Table 3 Experimental results of medium class
Full size table
Table 4 Descriptive statistics of medium class
Full size table
Fig. 9
figure 9

Friedman test of medium class

Full size image
Table 5 Experimental results of hard class
Full size table
Table 6 Descriptive statistics of hard class
Full size table
Fig. 10
figure 10

Friedman test of hard class

Full size image

The second experiment is conducted on selected benchmarks from “Sch_Wae2” instances [56] which are very difficult for first fit decreasing heuristic (FFD) [57], best fit decreasing heuristic (BFD) [58], and Martello-Toth packing (MTP) algorithm [36]. So, ILWOA is compared with theses algorithms in finding the optimal number of bins. For the parameter settings, a few number of search agents and iterations are set to ILWOA. The number of search agents is set to 10 agents and the maximum number of iterations are set to 30 iterations. The results of FFD and MTP are obtained from [53]. The experimental results of the second test are presented in Table 7. The descriptive statistics of the second experiment and Friedman test results are presented in Table 8 and Fig. 11, respectively. It is clear that the proposed algorithm is efficiently able to get the optimal solution (bolded values) in most instances compared to the other algorithms. In addition, it scores the lower ranked mean with a significant difference comparing to the other algorithms as shown in Fig. 11.

Table 7 Experimental results of Sch_Wae2 instances
Full size table
Table 8 Descriptive statistics of Sch_Wae2 instances
Full size table
Fig. 11
figure 11

Friedman test of Sch_Wae2 instances

Full size image

7 Results of analysis

The values of the bin capacity, items weights, and the number of items mainly affect computational time and solution quality of algorithms [55]. Consequently, the previous issues are taken into consideration when benchmarks are selected in this paper. In the first experiment, different difficulty benchmarks are selected to evaluate the searching capabilities of ILWOA in various cases. For the easy class, the number of items was between 50 and 500 with weights between 1 and 100. The capacity of a bin is between 100 and 150.Also, the number of items is between 50 and 500 in medium class. The capacity of a bin is equal to 1000.The items weights were calculated according to bin capacity that range between bin capacity/9 and bin capacity/3 with a deviation between 20 and 90%.While in the hard class, the number of items is equal to 200. The capacity of a bin is equal to 100,000 and item weights are between 20,000 and 35,000.The second experiment is conducted in Sch_Wae2 instances where the number of items is 120 items with weights ranging between 150 and 200, and the bin capacity is equal to 1000.

The main improvement in ILWOA is mutation phase which significantly increases the convergence speed of WOA. It is clear from the defined number of search agents and iterations. For other improvements, they help in controlling the search in continuous search space which also affects the solution quality.

Obviously, ILWOA obtains rapidly better results in the first experiment instances although the high variation between item weights especially for the hard class characterized by larger values of bin capacity, items weights, and the number of items. This indicates the high stochastic behavior of ILWOA. Also for Sch_Wae2 instances, ILWOA finds the optimal solution in most cases which indicates the good searching performance of ILWOA (see Fig. 12).

Fig. 12
figure 12

Examples of ILWOA performance on different problem cases

Full size image

8 Conclusion and future works

In this paper, a new variant of WOA is developed and applied for one-dimension BPP. First, the proposed algorithm is adjusted to be applied to solve BPP in combinatorial search space. Second, the randomization of the WOA exploration phase is enhanced by utilizing the capabilities of isotropic Lévy flight and chaotic maps. Finally, a mutation strategy is employed for increasing the convergence rate.

Two experiments are conducted and the results are analyzed with non-parametric Friedman test. In the first experiment, ILWOA is compared to QICS, ACS, FCO, FA, and AS. The results of the first experiment prove the superiority of ILWOA in efficiency and rapidity. For the second experiment, the proposed algorithm is compared to FFD, BFD, and MTP. The results show the high efficiency and the ability of the proposed algorithm to find the optimal solution. Besides, the obtained results are discussed and analyzed according to the problem size.

For future work, we suggest applying the proposed algorithm to other variants of BPP. Also, ILWOA can be applied to other combinatorial optimization problems, such as the traveling salesman problem and vehicle scheduling problem. In order to conduct a comprehensive test of ILWOA performance, Internet of Things and cloud computing to manage big data in health services applications [59,60,61,62,63] should be applied in the future.