Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

14.1 Introduction

In the last several decades, optimization played a crucial role in many aspects of various problems, including but not limited to engineering problems. Often, such problems include complicated objective functions, numerous decision variables, and a considerable number of constraints, which adds complexity to an already complicated optimization problem. The aforementioned characteristics limit the efficiency of traditional optimization techniques. Consequently, the search for an alternative method leads to a new field of study—swarm intelligence (SI), which was introduced by Beni and Wang in the late 1980s (Bei and Wang 1993). SI, ultimately, aims to imitate the social intelligence of the nature’s group living creatures (Bonabeau et al. 1999). Each newly proposed algorithm attempts to improve two main features: (1) decreasing the distance between the reported solutions and the actual global optima; and/or (2) reducing the solution searching time. Although each proposed optimization algorithm has its unique characteristics, with both merits and drawbacks, it has been proven that there is no single algorithm that could outperform all its rivals (Wolpert and Macready 1997). Subsequently, a wide range of alternative novel optimization algorithms have been proposed, each of which has its exclusive advantages.

One of these newly proposed algorithms is the crow search algorithm (CSA), which was initially introduced by Askarzadeh (2016). CSA attempts to imitate the social intelligence of crow flock and their food gathering process. The primary results illustrated the improved efficiency of CSA over many conventional optimization algorithms, such as genetic algorithm (GA), particle swarm optimization (PSO), and harmony search (HS), in both convergence time and the accuracy of the results (Askarzadeh 2016). Ultimately, it can be concluded that CSA is a proper alternative method for solving complex engineering optimization problems.

14.2 Crow Flock’s Food Gathering Imitation

Crows are a widely distributed genus of birds, which have been credited with intelligence throughout folklore. Recent experiments investigating the cognitive abilities of crows have begun to reveal the intelligence capability of these species (Emery and Clayton 2004, 2005; Prior et al. 2008). The studies have demonstrated that some species of crows are not only superior in intelligence to other birds but also rival many nonhuman primates. Observations of the crows’ tool use in the wild are an example of their complex cognition (Emery and Clayton 2004). Further studies have also revealed their self-awareness, face recognition capabilities, sophisticated communication techniques, and food storing and retrieving skills across seasons (Emery and Clayton 2005; Prior et al. 2008).

Interestingly, a crow individual has a tendency to tap into the food resources of other species, including the other crow members of the flock. In fact, each crow attempts to hide its excess food in a hideout spot and retrieve the stored food in the time of need. However, the other members of the flock, which have their own food reservation spots as well, try to tail one another to find these hiding spots and plunder the stored food. Nevertheless, if a crow senses that it has been pursuited by other members of the flock, in order to lose the tail and deceive the plunderer, it maneuvers its path into a fallacious hideout spot (Clayton and Emery 2005). Plainly, the aforementioned is the core principles of the CSA, in which each crow individual searches the decision space for hideouts with the best food resources (i.e., the global optima from the point of view of optimization). Thus, each crow individual’s motion is induced by two main features: (1) finding the hideout spots of the other members of the flock; and (2) protecting its own hideout spots.

In the standard CSA, the flock of crows spread and search throughout the decision space for the perfect hideout spots (global optima). Since any efficient optimization algorithm should be compatible with arbitrary dimensions and each arbitrary dimension is to represent a decision variable, a d-dimensional environment is assumed for the search space. Initially, it is assumed that N crow individuals (the flock size) occupy a position in the d-dimensional space, randomly. The position of the ith crow individual at the tth iteration in the search space is represented by x (i,t), which is, in fact, a feasible array of the decision variables. Additionally, each crow individual can memorize the location of the best encountered hideout spot. At the tth iteration, the position of the hideout spot of the ith crow individual is represented by m (i,t), which is the best position that the ith crow individual has spotted, so far.

Subsequently, each crow individual shall make a motion based on the two basic principles of the CSA: (1) protecting its own hideout spot; and (2) detecting the other members’ hideout spots. Assume that at the tth iteration, the jth crow individual attempts to retrieve food from its hideout spot [m (j,t)], while the ith crow decides to tail the jth crow individual, in order to plunder its stored food. In such circumstances, two situations may occur: (1) the jth crow individual could not detect that it has been tailed leading to the reveal of the hideout spot to the ith crow individual; or (2) the jth crow individual senses the presence of a plunderer, which leads to a deceiving maneuver by the jth crow.

In the first case, the lack of attention of the jth crow individual would enable the ith crow to spot and plunder the jth crow’s hideout spot. In such a case, the repositioning of the ith crow can be obtained as follows (Askarzadeh 2016):

$$ x_{(i,t + 1)} = x_{(i,t)} + r_{i} \times fl_{(i,t)} \times \left[ {m_{(j,t)} - x_{(i,t)} } \right] $$
(14.1)

in which r i  = a random number with the uniform distribution and the range of [0,1]; and fl (i,t) = flight length of the ith crow individual at the tth iteration.

It is worth to be mentioned that fl (i,t) is one of the algorithm’s parameters and it can affect the searching capability of the algorithm. Assume that smaller values of fl lead to the local search at the vicinity of x (i,t), while larger values of fl would widen the searching space. In terms of optimization, smaller values of fl would help intensify the results, while larger values of fl would diversify the results. Both well-intensification and -diversification are the characteristics of an efficient optimization algorithm (Gandomi et al. 2013).

There could also be the case, in which the jth crow individual would sense that it had been tailed by one of the members of the flock (say the ith crow). As a result, in order to protect its food supply from the plunderer, the jth crow would deceitfully fly over a non-hideout spot. To imitate such an action in the CSA, a random place in the d-dimensional decision space would be assumed for the ith crow.

In summary, the tailing motion of crow individuals for the aforementioned two cases can be expressed as (Askarzadeh 2016)

$$ x_{(i,t + 1)} = \left\{ {\begin{array}{*{20}l} {x_{(i,t)} + r_{i} \times fl_{(i,t)} \times \left[ {m_{(j,t)} - x_{(i,t)} } \right]} \hfill & {r_{j} \ge AP_{(j,t)} } \hfill \\ {{\text{a}}\,{\text{random}}\,{\text{position}}} \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$
(14.2)

in which r j  = a random number with the uniform distribution and the range of [0,1]; and AP (j,t) = the awareness probability of the jth crow at the tth iteration.

As mentioned previously, an efficient metaheuristic algorithm should provide a good balance between diversification and intensification (Yang 2010). In the CSA, intensification and diversification are mainly controlled by two parameters: the flight length (fl) and the awareness probability (AP). By decreasing the awareness probability, the chance of detecting the hideout spots by the members of the crow flock would increase. As a result, CSA tends to focus the search on the vicinity of the hideout spots. Thus, it can be assumed that smaller values of AP would amplify the intensification aspect of the algorithm. On the other hand, by increasing the awareness probability, the flock of crows is more likely to search the decision space in a random manner for, in fact, such an action would decrease the chance of discovering the real hideout spots by the plunderers. As a result, larger values of AP would amplify the diversification aspect of the algorithm.

14.3 CSA Implementation for Optimization

For an efficient implementation of a metaheuristic algorithm, one needs to tune the parameters of the algorithm. Parameter setting, however, is a time-consuming process. Thus, the algorithms with a limited number of parameters are easier to be implemented in different optimization problems. The aforementioned addresses one of the major advantages of the CSA over many conventional metaheuristic algorithms, since it has only two major parameters that require tuning (i.e., fl and AP). After the parameter adjustment, the flock size (N) and the maximum number of iterations (T) are assumed, as well.

The first step is to locate N crows, randomly, in a d-dimensional decision space. Since the crows have no experiences at the initial iteration, it is assumed that they have hidden their foods at their initial positions. After the initial step, the CSA relocates each crow individual, say the ith crow, as follows: the ith crow individual would assume the role of a plunderer for a randomly selected member of the flock, say the jth crow. Using Eq. (14.2), the new position of the ith crow is calculated.

To avoid unfeasible answers, it is suggested in the standard CSA to check the feasibility of the new location in the decision space. If an unfeasible location is generated in the latter process, the crow must stay still. An alternative for such a procedure is the implementation of a penalty function for unfeasible answers. In any case, the crow updates its memory as follows (Askarzadeh 2016):

$$ m_{(i,t)} = \left\{ {\begin{array}{*{20}l} {x_{(i,t + 1)} \,{\text{if}}\,f\left[ {x_{(i,t + 1)} } \right]} \hfill & {{\text{is}}\,{\text{better}}\,{\text{than}}\,f[m_{(i,t)} ]} \hfill \\ {m_{(i,t)} } \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$
(14.3)

in which f[] = objective function. These steps are repeated until the termination criterion is satisfied. At that point, the best position that is memorized by the members of the crow flock is reported as the optimum solution. Figure 14.1 illustrates the flowchart of the standard CSA. Additionally, Table 14.1 summarizes the characteristics of the CSA.

Fig. 14.1
figure 1

Flowchart of the standard CSA

Full size image
Table 14.1 Characteristics of the CSA
Full size table

14.4 Pseudo Code of the CSA

14.5 Conclusion

This chapter described the crow search algorithm (CSA), which is a novel, yet relatively new metaheuristic optimization algorithm, based on the intelligent behavior of crows. CSA is a population-based optimization algorithm, with mainly two adjustable parameters (flight length and awareness probability). Such characteristics make CSA a viable option for complex engineering optimization problems. In the final section, a pseudocode of the standard CSA was also presented.