3.2.1. Wolf pack hierarchy

The keystone of the grey wolf pack is its hierarchy, which is structured into four groups: Alpha, Beta, Delta and Omega (Figure 3.1).

3.2.2. The four phases of pack hunting

The grey wolf pack hunts their prey by progressing through four phases, as illustrated in Figure 3.2:

1. 1) search;
2. 2) pursue;
3. 3) surround and harass the prey until trapped or exhausted;
4. 4) attack the prey.

The hierarchy of the pack and the four phases of its hunting technique constitute the two pillars of the GWO metaheuristic. These are modeled mathematically in the next section.

3.3.1. Pack hierarchy

Wolf agents Alpha, Beta and Delta (Figure 3.3) are the most important wolves in the pack and assume prime position when surrounding prey during hunting (Figure 3.4). They will therefore be respectively the first, second and third best solutions to the optimization problem. The Omega wolves alter their position based on the positions of the Alpha, Beta and Delta.

3.3.2. Four phases of hunt modeling

3.3.2.2. Encirclement and harassment

The encirclement and harassment of prey by wolf agents are modeled by equations [3.1]–[3.5].

[3.1]

[3.2]

• – t indicates the current iteration;
• – (t) is the Omega wolf position at iteration t ;
• – (t+1) is the Omega wolf position at the next iteration t + 1
• – is the prey position;
• – , and are vectors defined by equations [3.3], [3.5] and [3.1];
• – a is a coefficient that decreases linearly from 2 to 0 in terms of until maximum iteration itMax.

Vectors , and are calculated as follows:

[3.3]

[3.4]

[3.5]

Based on equations [3.1] and [3.2] in a search area of size N, wolf agents evolve in a hypercube around the prey (the best solution). Figures 3.5 and 3.6 graphically illustrate the hypercube created by a wolf around the prey before the attack with equations [3.1] and [3.2] for N = 2 and N = 3, respectively. In the attack equations [3.6]–[3.12], the position of the prey is represented by the three best solutions at the iteration t: Alpha, Beta and Delta. Therefore, three hypercubes will be created for each of them.

3.3.2.3. Attack

According to the social order established by the hierarchy of the pack, the Alpha, Beta and Delta wolf agents guide the attack. The postulate of the pack is based on the principle that the hierarchy has a better perception of the position of prey. Therefore, the Omega will update their position from the encirclement areas around the prey, created by the positions of the Alpha, Beta and Delta: .

To do this, equations [3.1] and [3.2] are used with positions , and to obtain , , in the encirclement areas of the Alpha, Beta and Delta. , , are provided by equations [3.6], [3.9] and [3.11]. The wolf agents will update their position on the mean of , and with equation [3.12]. This update allows the pack to approach the best solutions.

[3.6]

[3.7]

[3.8]

[3.9]

[3.10]

[3.11]

[3.12]

The vectors and are strategic random vectors for the GWO algorithm. Indeed, their stochastic nature supports the exploration phase. is the vector that leads the exploration and exploitation phases. stochastically models the obstacles between the wolf and the prey. also plays a fundamental role in the exploration and exploitation phases. The closer || is to 2, the more complex it will be to attack the prey and therefore the more the wolf will have to explore other areas around the prey in order to access it. On the other hand, the closer || is to 0, the closer the wolf is getting to the area around the prey that favors exploitation.

For example, if N = 2, the equations [3.6] and [3.7] are calculated as follows:

By doing the same for the next agent position is:

3.3.3. Research phase – exploration

The search for prey requires wolves to occupy the search area by spreading out. When |A| ≥ 1, the wolf agents are in the exploration phase which involves a random search for promising areas. The wolf agents change positions by dispersing and are therefore better placed to find new promising zones around prey.

|C| is stochastic and randomly evolves from 0 to 2. If |C| ≥ 1, it removes the wolf agents from the prey and promotes exploration.

3.3.4. Attack phase – exploitation

Attacking prey is the exploitation phase of the hunt when 1 > |A| ≥ 0. Indeed, in this interval, the wolf agents will progress toward the prey by getting closer to one another.

If |C| < 1, the wolf agents are brought closer to the prey after overcoming obstacles and this promotes exploitation.

Figure 3.7 graphically illustrates the evolution of A between exploration and exploitation phases and Figure 3.8 shows the position of the wolf in relation to the prey in the exploration and exploitation phase.

It can be noted that the first half of the iterations, when , promotes the exploration with 2 ≥ a ≥ 1 , and the second half, when , promotes the exploitation with 1 > a ≥ 0.

3.3.5. Grey wolf optimization algorithm pseudocode

We now have all the elements allowing us to understand the mathematical modeling of the GWO algorithm. The understanding and mastery of the key points of this algorithm is an imperative for the remainder of this chapter. In the following section, we are going to approach the main topic of this chapter: feature selection. We must first know the theoretical fundamentals of feature selection and optimization in a binary discrete search space.

3.4.1. Feature selection definition

Feature selection is the problem of how to choose the fewest features in the original dataset that are often high-dimensional (Almomani et al. 2019). It is therefore an extraction process that eliminates irrelevant and redundant features for a better understanding of datasets (Sharma and Kaur 2021). In practice, feature selection consists of exploiting ad hoc algorithms for processing a dataset with N features as the input and providing at the output a subset of p feature data with p < N. Figure 3.9 illustrates this process. But what are the methods to achieve it?

3.4.2. Feature selection methods

There are two main feature selection algorithm families: chaotic and binary (Sharma and Kaur 2021). The binary feature selection is the most used in the literature thanks to its good performance and a better theoretical and practical control. It is therefore the binary selection that we will implement in this chapter.

The binary feature selection family has two predominant types of feature selection methods: the filter method and the wrapper method (Chandrashekar and Sahin 2014; Almomani et al. 2019; Sakr et al. 2019; Sharma and Kaur 2021).

3.4.3. Filter method

The filter method is independent of the optimization problem and classifier; its key advantage. It uses statistical algorithms that make it possible to calculate a weight for each feature by analyzing any attributes specific to the data. The weights will be compared to a threshold that will provide a feature classification. This ranking will make it possible to delete the feature superior to the threshold. However, this method provides much less precision than selection of the wrapper method. The most used filter methods in the literature are (Sakr et al. 2019):

• – information gain;
• – principal component analysis;
• – characteristics correlation selection.

3.4.4. Wrapper method

The wrapper method uses the machine learning classifier to guide the metaheuristic to lead the feature selection process. This method is therefore adherent to the classifier. In addition, the wrapper method requires more calculation and processing time than the filtering method. However, its main advantage is that it provides better precision and thus better results in solving the feature selection problem. The literature confirms that wrapper methods outperform the filtering methods (Siarry 2014; Sakr et al. 2019; Sharma and Kaur 2021).

In addition, the use of population-based multiple solution metaheuristics provides better results than single solution metaheuristics (Sakr et al. 2019; Sharma and Kaur 2021). The GWO algorithm is therefore suitable for solving the feature selection problem.

Therefore, in this chapter, GWO will be integrated with the wrapper binary feature selection method (Emary et al. 2016). The binary feature selection can be done either by forward selection or by backward elimination.

3.4.5. Binary feature selection movement

The wrapper method allows two feature selection “moves”: forward selection and backward elimination. The selection of forward or backward will depend mainly on the binary vector initialization method chosen.

3.4.6. Benefits of feature selection for machine learning classification algorithms

The benefits of feature selection on machine learning classification algorithms are multiple. We list the most important here:

• – removal of redundant and irrelevant data;
• – noise reduction;
• – extraction from the curse of the dimension;
• – decrease in classifier complexity;
• – improvement in the quality of supervised learning;
• – increased classification accuracy;
• – decreased classifier response time;
• – material resources saving when running the classifier: memory, CPU, GPU processors and energy.

In view of the benefits listed above, feature selection is a vital step in data processing before the learning phase of a classifier. Being a powerful algorithm for solving NP-hard multi-objective optimization problems, metaheuristics GWO has become one of the keystones in the process of creating a successful classifier. Indeed, feature selection is an NP-hard multi-objective optimization problem in a binary search space. So a modern and powerful metaheuristic like GWO is able to solve this problem. But before developing the binary GWO metaheuristics, we must first know the mathematical modeling of the problem of optimizing feature selection in a binary search space.

3.5.1. Optimization problem definition

Patrick Siarry (Collette and Siarry 2002) defines optimization as “the search for the minimum or the maximum of a given function”. It is therefore a matter of searching in the search space for a data vector which minimizes or maximizes the objective function. The search space of interest to us is the discrete binary search space.

3.5.2. Binary discrete search space

The binary discrete search space is a search space whose vector components can only take the discrete values 0 or 1.

The mathematical representation of a binary vector in the binary search space ^N with N features is .

The binary search space ^N is represented by a hypercube with 2^N vertices. The 2^N binary vectors of the search space ^N are positioned on the vertices. For example, for N=3, ³ is a cube with eight binary vectors positioned on the eight vertices as illustrated in Figure 3.10.

Therefore, there are 2^N – 1 solutions for a problem of feature selection with N features. The null vector is ignored because it means to select no features.

Thus, the space research ^N exponentially increases with the size of N features. But why would metaheuristics be more appropriate than other algorithms to solve the problem of feature selection? The reason is simple: it is not possible, unless you devote several hours or even several days, to use a deterministic method to solve the problem of feature selection (Zita et al. 2010; Sharma and Kaur 2021). What we need is an acceptable solution within a reasonable wait time. However, the literature abounds with articles demonstrating the effectiveness of population-based metaheuristics, such as GWO.

Before moving on to the next section, we need to understand how to translate a binary vector into a feature selection problem. To do this, let us take the example of a dataset with N = 6. The space research ⁶ consists of binary vectors . There are therefore 63 possible solutions. Translating each vector into a feature selection solution in this search space is extremely simple: 0 means that the feature is not selected and 1 means the opposite. Take one of the vertices of the hypercube: _p = (0,1,0,0,1,0) . This vector selects the two features D2 and D5 as illustrated in Figure 3.11.

These binary vectors will be produced by the GWO metaheuristic as input to the objective functions of the feature selection problem.

3.5.3. Objective functions for the feature selection

We have previously stated that a feature selection problem is a multi-objective problem, to be precise a bi-objective problem. Indeed, we must maximize the accuracy of the classifier and minimize the number of selected features. But before setting the two mathematical functions to be optimized, it is necessary to define the vocabulary making it possible to measure the quality of a classifier.

3.5.3.6. False negative (FN)

This is the number of images containing a dog but classified as not containing a dog.

The confusion matrix below illustrates the result of the CNN classification (source image: https://www.kaggle.com/).

Let us now set the two mathematical functions to be optimized.

The function A(B_i) is the classifier accuracy depending on the binary vector and the function D(B_i) is the number of selected features by the binary B_i and N is the feature size. The feature selection problem is defined by equations [3.13]. [3.14] and [3.15]:

[3.13]

[3.14]

The two objective functions f1 and f2 of the feature selection problem are provided by [3.15]. It is about maximizing these two functions.

[3.15]

Being a two-objective optimization problem, it will be necessary to find the dominant solutions; the optimal solutions in the Pareto are on the Pareto border as illustrated in Figure 3.12.

To solve this problem of feature selection, a uniobjective function is more suitable for GWO metaheuristics. To do this, it suffices to aggregate the two equations into one linked by a weighting coefficient: θ ϵ [0,1]

[3.16]

The coefficient θ is used to assign a weight to each function in order to distribute the importance of the desired objective: do we want to promote the performance of the classifier or decrease the number of features? This coefficient is therefore not trivial to determine.

In addition, since the inherent nature of GWO is to minimize, it would be more expedient to take into account the error rate ℰ(B_i) [3.17] instead of the accuracy A(B_i) [3.13]. In the same way, instead of the removed feature rate we take the selected feature rate . This provides the new objective function [3.18]:

[3.17]

[3.18]

We now have the new uniobjective function to be minimized for our optimization problem. This uniobjective optimization problem is easier to implement in the wrapper feature selection method. We will detail in the next part how to adapt a metaheuristic, designed for optimization on a continuous search space, to a metaheuristic for optimization on a discrete binary search space.

3.6.1. Module M1

This step is similar to the process of normalizing continuous variables which allow, for each feature, the transition from ℝ to [0,1]. This process uses S or V transfer functions. The most commonly used functions in the literature are listed in Table 3.1 and graphically represented by Figure 3.13.

Transfer functions are used to assess the probability that a component of a binary vector B_i changes from 0 to 1 or vice versa. The transfer functions are defined mathematically by [3.20]:

[3.20]

S function transfer	V function transfer

We now know the transfer functions S and V allowing the first module to make the transition from space ℝ^N to [0,1]^N. Now let us move on to the binarization module M2 allowing transition from [0,1]^N to B^N.

3.6.2. Module M2

The first module transforms a vector in to a vector in [0,1]^N. The second module applies logical rules R on the vector The result creates a binary vector B_i = . The rules R are mathematically defined by [3.21]:

[3.21]

In the literature, binary metaheuristics applied to the feature selection (Crawford et al. 2017) mainly use the following rules:

• – the change rate rule R1;
• – the standard rule R2;
• – the 1’s complement rule R3;
• – the statistical rule R4.

3.6.2.1. Change rate rule R1

The rule R1 is the simplest but is somewhat risky because it requires us to define by ourselves. in metaheuristics. a threshold probability or rate of modification TM. Unlike the standard rule R2 which is based on dynamic thresholds defined by T, the rule R1 is static.

For each component of the binary vector will take the value 1 only if the modification rate TM is greater than rand with rand a random value between 0 and 1. The rule R1 is defined by equation [3.22].

[3.22]

This rule has been used in the bABC metaheuristics (Schiezaro and Pedrini 2013) with mixed results. As we specified above, this rule is too “simplistic” because it does not take into account the feedback between the metaheuristics, the objective function and the updating of the positions of the agents in the search space as the standard rule R2 does.

3.6.2.2. Standard rule

The standard rule R2 exploits the dynamism of the S transfer function to provide the value , making it possible to measure the probability of to be 0 or 1.

This rule will be applied to each bit of the binary vector B_i = The obtained probability values will be compared to a random value rand ∈ [0,1]. The rule R2 is defined by equations [3.23]:

[3.23]

This rule has been used in the bDA metaheuristics (Mafarja et al. 2018) and has provided very good results.

The rule R3 that we will see below is a variant of R2.

3.6.2.3. 1’s complement rule R3

The 1’s complement rule R3 is similar to the standard rule R2. There are two differences:

• – the rule R3 is used with V transfer functions while R2 is used with S transfer functions;
• – R3 uses the 1’s complement to calculate the value (t) of the binary vector .

  The rule R3 is defined by equation [3.24]:

[3.24]

The rule R3 has been used in the bPSO metaheuristic (Collette and Siarry 2002) by demonstrating the performances of V transfer functions compared to S transfer functions.

The three rules R1, R2 and R3 provide a binary value from a logical condition. The statistic rule R4 will make it possible to make a choice between three binary values depending on the probability value and a real value θ.

3.6.2.4. Statistic rule R4

As explained above, the statistical rule R4 uses the probability value and ? to generate three logical conditions. These three logical conditions form a stochastic crossover operation between the values , and . At the end of this operation, will take one of the values , or . The rule R4 is defined by equation [3.25]:

[3.25]

This rule will be used in the bGWO metaheuristic (Emary et al. 2016) below.

We now have all theoretical knowledge and mathematical tools to adapt the GWO to optimization in a binary research space. This adaptation will lead to the bGWO metaheuristic that will provide an acceptable solution in a reasonable time to the problem of feature selection.

3.7.1. First algorithm bGWO1

In this approach, each bit (t) of the binary vectors , and is calculated respectively using equations [3.27]–[3.29], [3.30]–[3.32] and [3.33]–[3.35].

In this approach, the module M1 will use the following S transfer function [3.26]:

[3.26]

The module M2 uses the standard rule R2 and the statistical rule R4 to calculate the next bit position of the grey wolves.

In the following we will implement the modules Ml and M2 on the vector . The process is the same for vectors and .

3.7.1.1. Module M1

In the continuous version GWO version

The module M1 uses the value to measure the remoteness from the position of the prey. Let x = in the S transfer function [3.27]. The result measures the probability of having the value 1 or 0.

[3.27]

3.7.1.2. Module M2

The module M2 uses the standard rule [3.28] to obtain the binary value , and the logic rule [3.29] to obtain the binary value knowing that is a binary value.

Vector

[3.28]

[3.29]

Equations [3.30]–[3.32] and [3.33]–[3.35] apply the modules M1 and M2 in the same way in order to calculate the vectors and .

Vector ₂

[3.30]

[3.31]

[3.32]

Vector

[3.33]

[3.34]

[3.35]

The module M2 ends by calculating the next binary position with the statistical rule [3.36] by performing a stochastic crossing of with .

[3.36]

The first algorithm bGWO1 makes it possible to search for the best binary position of a wolf agent to solve the optimization problem in a binary search space ^N with N features. The quality of bGWOI is that it retains the same optimization strategy as GWO while binarizing it thanks to modules M1 and M2. Indeed, these two modules are implemented to calculate the binary positions , and in the surrounding areas created by the hierarchy of the pack and then to calculate the new binary position of the wolf agents of the pack.

In the second algorithm, bGWO2 reduces the binarization phases. Only the calculation for updating the positions of wolf agents is binarized.

3.7.2. Second algorithm bGWO2

In this second approach, as in the first approach, the module M1 uses the transfer function [3.26] and the standard rule R2 in the module M2.

As we have just explained, in bGWO2, only the update phase of the bit positions is binarized. To do this, each component will be calculated using the average of from the positions and . Therefore, in function tranfers [3.26].

Thus, the module M1 calculates in [3.37] which makes it possible to evaluate the probability that takes the value 1 or 0.

[3.37]

The module M2 calculates the next value of by using the standard rule R2 in [3.38].

[3.38]

The bGWO2 algorithm is more attractive than bGWO1 because only the step of updating the pack positions is binarized. Everything else in the bGWO2 algorithm is identical to GWO.

The pseudocodes of bGWO1 and bGWO2, respectively, provided by Algorithm 2 and Algorithm 3 allow them to be compared to the GWO algorithm and to confirm the consistency of the hunting strategy used in the GWO.

3.7.3. Algorithm 2: first approach of the binary GWO

In: Population size N, Number of iterations ItMax, fitness function F

Out: Binary vector and fitness value F()

Initialization of the grey wolf binary population agents Initialize a, A, and C

Calculate the fitness F(_i) of each search agent _i

Define:

• = the first best search agent
• = the second best search agent
• = the third best search agent

3.7.4. Algorithm 3: second approach of the binary GWO