A cuckoo search algorithm: Effects of coevolution and application in the development of distributed layouts

Abstract

This article presents a cuckoo search algorithm, via Lévy flight, considering the effects of coevolution on the displacement dynamics of animal communities, and applies this algorithm to the development of maximally distributed physical arrangements. Some variables are introduced such as egg weight and the acquired learning of host birds. The results show that the proposed algorithm prevails, in the majority of the interviewed instances, in the degree of distribution in comparison with the classic TARGET and ALVO methods, and with the Genetic Algorithm. The proposed algorithm was shown to be able to obtain a low degree of distribution in a satisfactory computational time, especially in large problems.

Introduction

Manufacturing cells are composed of a set of machines responsible for the execution of products, whose operations have some level of homogeneity. Thus, products that do not claim machines from a given cell would not need to be moved to it. Due to the convenient positioning of each machine incorporated within each cell, the unit flow of product can be established. In recent decades, the concept of virtual cells has spread, in which the types of machines that compose such cells transmute incessantly. This is because the types of products and the quantities of each type alternate constantly without ceasing, as a consequence of the chaotic environment. Studies highlight that one of the best opportunities for virtual cell design is through an appropriate spreading of machines on the shop floor. Three types of distributed physical arrangements (layouts) have been disseminated: randomly distributed layout, partially distributed layout and maximally distributed layout. The distributed layouts receive these three denominations by virtue of the degree of scattering. The more distant the machines of the same type are from one another, the better the spreading is. Therefore, the greater the size of the physical arrangement and types of machines, the greater the complexity of defining the best positioning of the machines is.

Over a number of years, an abundance and diversity of heuristics have been developed in countless branches of expertise, notably in the engineering field, helping to define procedures for reaching a good solution. A good solution is considered to be one that is close to the global optimum. Of these developed heuristics, many of them are inspired by nature (metaheuristic) and replicate in reality what has been done for thousands of years, sometimes minimizing temperature or optimizing displacement, etc., with an extraordinary capacity to provide satisfactory results in a short time. Each of them requires adaptations for each type of problem, therefore constituting the labourious part of the problem. Accordingly, metaheuristics must be chosen and applied according to its peculiarity.

The cuckoo search algorithm, developed by Yang and Deb, ¹ consists of analysing the behaviour of the host birds, in the search for the best spatial coordinate for the nesting, and the cuckoos’ birds, in the search for the host nest egg to deposit in it. The basis of this algorithm is, by means of the motion specified by the Lévy equations, the spatial coordinates, where the eggs that obtain greater chances of survival are more likely to repeat the same coordinates again (or those nearby). In this way, irrelevant movements that do not confer benefits are eliminated, thus reducing the search time.

Although little research has examined the scope of the development of manufacturing systems, it is now important to investigate the relevant adaptations of this metaheuristic to unveil its contribution to the elucidation of this peculiar type of presented problem with respect to the generation of maximally distributed layouts. The classical configuration of this type of algorithm is very limited and only examines the relationship between host birds and cuckoo birds. In nature, all types of animals live in communities and interact with each other (coevolution) with peaceful or harmful coexistence.

With the purpose of more faithfully imitating nature, this article considers the effects of coevolution of animals in the model of displacement of communities via Lévy flight. In addition, some variables such as the egg weight and acquired learning of host birds are introduced. There is still no evidence in the literature describing this type of approach that considers the interaction as a whole; therefore, this study presents an important contribution.

Ultimately, this article presents seven topics. It starts with the presentation of the study methodology, the types of data, etc. and describes the methodologies that are adopted in this work, as shown in topic 2. The literature review (topic 3) then goes on to present the concepts about the manufacturing system under analysis. In the next topic, the characteristics of the classic cuckoo search algorithm are presented, which are important for the proposal presented in this article (topic 5). Input data are presented to the model for the computer simulation, thus composing topic 6, and finally, the conclusions and more proposals for future work are discussed in topic 7.

Research methodology

This topic briefly presents the literature on the scientific methodology and, from this, defines the most appropriate ones for conducting the research proposal presented here.

Cervo and Bervian ² commented that, in general, there are three types of research: bibliographical (where knowing and analysing the existing contributions on the subject is facilitated); descriptive (where variables are observed, analysed and correlated without manipulating them); experimental (where the researcher controls the variables of the object being studied). For Gil, ³ the research inquiry is developed based on the available knowledge, with the careful use of methods, techniques and other scientific procedures. With respect to data collection, Chizzotti ⁴ stated that there are basically two types of data: quantitative (measurement of pre-established variables, seeking to verify and explain their influence on other variables) and qualitative (based on data collected in interactions that are interpersonal, with co-participation of the informants’ statements, and analysed from the meaning they give to their actions).

According to the presentation of the scientific methodology, this work adopts the bibliographic type of research, presenting the characteristics of each type of distributed physical arrangement, the virtual cell concept and the degree of distribution. We present the main works already published about the distributed layout, the techniques used to generate each type of physical arrangement, and finally, a discussion that shows the gap with the works already published. In addition, we review the classic cuckoo search algorithm. The method chosen for conducting the research is the computational modelling and simulation of physical arrangements (the proposed algorithm, Genetic Algorithm, TARGET algorithm and ALVO algorithm). In addition to these models, others are built-in or built to be used in the simulation for the generation of parts’ features (sequence of operations, lot sizing, etc.) and for the identification of virtual cells. The data collected for comparative study are of the quantitative type, which are: degree of distribution, distance travelled and computational time.

In summary, the methodological procedure adopted in this work is shown in Figure 1.

Figure 1.

Methodology used to conduct this research work.

Literature review

According to Rheault, ⁵ the market is increasingly chaotic, exerting strong influences on companies and requesting constant changes in types and volumes of production. Traditional physical arrangements are no longer capable of properly behaving according to these contemporary impositions. Therefore, the development of a type of physical arrangement was conceived, called robust, that could associate some peculiarities of the traditional ones to allow the apportionment of costs by the volume of production and, concomitantly, provide high variety. Among the newly proposed physical arrangements are the distributed layouts. These last ones were conceived from the perception of establishing several cells according to the sequence of operations. In this way, the modification of the attributes of the product over time is accompanied by changes in the types of machines that integrate the cells. The recognition of cells, the virtual cells, is not physically visible as in a traditional cell. These are computationally identified and reserved according to the operations required by the product. As a result, the triumph of implementing a distributed physical arrangement is subject to a refined and updated information system of the productive process in real time.

The virtual cells work similarly to the common cell, with the unit flow of parts. Each virtual cell is responsible for producing a particular type of product, and upon completion, machines have the opportunity to be employed for designing another virtual cell. To implement the unit flow, the machines that comprise it must not be far from each other. Usually, the virtual cells are obtained by identifying the machine and its subsequent one that is as close as possible; repeating the procedure for all of the machines that will execute the piece; calculating the sum of the total distance of the identified machines and minimizing this sum by identifying other replicas of the same types of machines. Note that to qualify machines for virtual cell formation, it is assumed that each machine is already allocated.

Three types of distributed physical arrangements are known. The first is called a randomly distributed, which describes machines that are randomly dispersed. In this type of physical arrangement, scattering is not subject to any particular specificity. The second type is the partially distributed, as shown in Figure 2. In the example, the mentioned layout originates from the functional physical arrangement. In this case, the productive resources of each department were divided into two or three parts and then scattered on the factory floor. This fragmentation, according to the authors, is defined by K. When K = 1, it symbolizes that a department type is fragmented into two parts, and when K = 2, it reveals that it is divided into three parts. Subsequent to fragmentation, the allocation of the parts can be performed. This allocation can be aided by spatial filling curves, similarly titled as Peano curves.

Figure 2.

Example of process versus partially distributed layouts (Source: Lahmar and Benjaafar ⁶ ).

We emphasize that the goal is to develop a physical arrangement that is robust, with the ability to work efficiently in accordance with a product whose profile is unknown. In this way, developing a physical arrangement was idealized such that it makes available the different types of machines that are as close as possible. This provides a greater chance of locating a machine with the ability to perform a differentiated operation, providing the operational flexibility needed to operate in a chaotic environment. Then, a third type was conceived called the maximally distributed, as shown in Figure 3. This type of problem is known as NP-hard, since there are many possibilities of allocating machines, mainly due to the number of types of machines and the replica of each one of them. Benjaafar and Sheikhzadeh ⁷ proposed a mathematical formula to evaluate the degree of distribution of the machines that helps in the generation of this type of physical arrangement. According to the authors, an appropriate scattering of machines is obtained as the calculated degree decreases. Júnior ⁸ clarified that in the works of Montreuil et al. ⁹ and Montreuil and Venkatadri, ¹⁰ another method of calculating the degree of distribution was illusively disclosed. However, in essence, the effect is equivalent to that proposed by Benjaafar and Sheikhzadeh. ⁶ According to the author, the dissimilarity is that these two studies employ the probability of movement between different types of machines; once these probabilities are dispensed, the result is equivalent.

Figure 3.

Example of maximally distributed layout (Source: Benjaafar et al. ³⁰ ).

In this last cited layout, at the heart of this article, we find research using a Genetic Algorithm, according to Montreuil and Venkatadri. ¹⁰ In the work of these authors, it is possible to verify that the application of this metaheuristic provides a degree of distribution of low value, although needing numerous generations to obtain it, especially in relation to large problems.

Montreuil et al. ⁹ proposed the TARGET algorithm. The authors’ method consists of two phases: the first is to generate a distributed physical arrangement by randomly positioning the machines. The calculation of the degree of distribution is performed. Then, a replica of a certain type of machine is selected and induced to one of the adjacent positions (e.g. up). The degree of distribution is again calculated. If the current degree of distribution is better than the previous one, then this best position should be memorized. The procedure is performed for the same replica of the chosen machine for other adjacent positions (low, right and left). The procedure is repeated for all replicas and for all types of machines. Thus, the best position of each replica of each type of machine is defined; moreover, because the method involved the overlap of the machines, the second phase was proposed precisely to untangle this situation. The authors propose to investigate the rate of utilization of the machine, the information obtained by analysing the number of replicates, and the demand and the execution time of each type of part that requests such a machine. If the investigated machine cannot be allocated to the ideal position defined in the first phase, positions closest to the ideal position, which are still available, are chosen. Thus, according to the authors, the maximal spreading is obtained.

In the work of Júnior, ⁸ a study of contrast of the computational behaviour was conducted to reach a maximally distributed layout by the Genetic Algorithm and by the proposed method, which the author called ALVO. The author’s idealized method forwards each type of machine to unique locations. The stages are organize the types of machines according to the number of replicas, from the smallest to the largest, detect the best positions (based on the centre of the shop floor) and allocate the replica if the place is available; otherwise, inquire nearby; and repeat the procedure for all types of machines. According to the author, the proposed method provides a maximally distributed physical arrangement (lower degree of distribution) with computational performances as good (or even better) as that obtained by the Genetic Algorithm. The author does not justify the basis of the pretext to choose the centre and much less the reason to choose the least number of replicas to start the allocation.

For Benjaafar and Sheikhzadeh, ⁷ because of technological limitations, the maximally distributed layout is more difficult to implement. Lahmar and Benjaafar ⁶ reinforced the argument that rarely is the total unbundling of departments justified (maximally distributed) since the same benefits can be obtained with the partially distributed layout.

Júnior ⁸ conducted a computational model study in which the operations to be performed on the parts were flexible, that is, when they do not necessarily respect a given chain of operations. Upon being submitted to the functional physical arrangements and to the distributed physical arrangements, he concluded that the performance of the maximally distributed layout surpasses that of the functional layout and that of the partially distributed layout, both considering the rigid sequence and the flexible sequence of operations. Irrefutably, this result contradicts, a priori, the conclusions of Lahmar and Benjaafar,^6,11 who argued that, despite the benefits gained, the total breakdown is seldom justified. However, taking as an argument the discrepancies between the initial conditions of each study, such as the characteristics of the pieces, this alternation of superiority between the maximally distributed and the partially distributed approach was already foreshadowed. In addition to this, at no time, do the studies exclude the merit of the maximally distributed, which only weakens in the issue of implementation difficulties, as Benjaafar and Sheikhzadeh ⁷ quoted. Fortunately, the intense technological advancement experienced currently already points to the opportunity of such a practice. As Atzori et al. ¹² commented that the manufacturing systems observed today are increasingly advanced, using a considerable amount of technology, such as sensors, software, etc., thus allowing productive resources to be increasingly more connected. In this sense, Azizi ¹³ and Azzizi et al. ¹⁴ proposed in their studies an analysis of one of these technologies, which is the emission of radio waves via antennas. They propose different models capable of optimizing these installations, considering a series of constraints such as transmission efficiency, coverage region, etc., which optimizes the flow of signals.

Baykasoglu ¹⁵ and Baykasoglu and Gindy ¹⁶ focused their studies not on the development of maximally distributed but on how to enhance the benefits of it through the proper formation of virtual cells. Especially, in the first study, the author used simulated annealing to identify the virtual cells based on analysis of the capacity of each type of machine. The author claimed that the machines are capable of performing more than one different operation; otherwise, an operation can be performed on more than one type of machine.

As suggested by Baykasoglu, ¹⁵ Shafigh et al. ¹⁷ proposed in their study to define a distributed dynamic physical arrangement (whose machines can be change positions according to the time). For this purpose, they developed a mathematical model considering variables such as fluctuations of demand, lot size, capacity of operation of each machine, etc. In addition, Hamedi and Esmaeilian ¹⁸ present other important results regarding the processing capacity of each type of machine during virtual cell formation. Li and Li ¹⁹ considered human factors, comfort, safety, etc. in the mathematical model for the development of dynamic layouts. The authors also consider costs related to the reallocation of resources. With the cooperation of ant colony metaheuristics, they obtained important results, concluding that the human factor should not be ignored and impacts the performance of the productive system as a whole.

In addition to those cited, there is no evidence in the literature of specific later publications regarding the development of other metaheuristics that contribute to the spreading process of machines for robust physical arrangements (machines do not change position according to time).

The cuckoo search

In general, when the breeding season arrives, a pair of birds builds a nest in a particular location, usually on tree tops or rocks, to ensure the safety of their eggs from predators. After the period of incubation, the eggs hatch, and then, the birds’ parents go in search of food to meet the nutritional needs of the chicks. Rarely do all of the nestlings survive, either due to lack of food, disease, predators, etc. As the chick grows, it can migrate from one region to another in search of better survival conditions as well as to find new partners.

There is a kind of bird that in addition to laying eggs with physical dimensions above average does not build the nest itself. They are the cuckoo birds. ²⁰ A striking feature is that they take advantage of the neglect of a host bird to lay eggs in its nest. Moksnes and Røskaft ²¹ stated that although cuckoo birds can infect more than 100 species of birds, curiously, when living in a certain habitat and depending on the cuckoo species, they insist on infecting the same species of host.

Sometimes, the host bird may notice if a particular egg was from an intruder bird. As a consequence, the host bird moves the egg out of the nest, or else migrates to another location and remakes another nest. In order to avoid it, mysteriously throughout evolution, cuckoo birds have become able to mimic the appearance of both the shape and the colour of eggs very close to that of the host bird. ²²

Their eggs (cuckoos) hatch approximately two to three days on average before those of the host bird. Being larger and stronger, the newborn chick moves the other eggs that have not hatched out of the host nest. Thus, it receives all possible food from the host bird. According to Moksnes et al., ²³ the cuckoo bird can remove up to more than one egg host. If the egg host can hatch, the chance of survival is minimal, as it cannot properly receive food.

Depending on the cuckoo bird species, the size of the egg may be distinct. The larger the egg is, the harder for the mother bird to carry it to a higher location. Therefore, putting eggs in lower places can be a good alternative, as Rajabioun ²² pointed out. Considering that the protein content offered by the egg is also greater for predators, the chance of the egg going unnoticed is small.

Unfortunately, the cuckoo birds do not have control of how many eggs it will conceive during each reproductive cycle. Therefore, nature itself takes on this role to maintain the balance, which is to serve the egg as food for predators. According to Wyver, ²⁴ a cuckoo bird can lay up to 25 eggs per season and in different nests. Each season consists of three to five reproductive cycles.

The dynamics of cuckoo birds are succinctly represented in pseudocode, as developed by Yang and Deb ¹ and shown in Figure 4:

Figure 4.

Pseudocode of the cuckoo search algorithm (Source: Yang and Deb ¹ ).

According to the steps, cuckoo birds are conditioned to host birds or vice versa. Note that cuckoo birds produce the desired solution. Also note that the movement of Lévy is realized. Briefly, the Lévy flight is characterized by movements of a material point that occur in a dimensional field of the type with long and short movements. A typical example is represented by animals in search of food. When the food in a particular region runs out, the animals employ larger bigger routes until they find another source of food, and as soon as they find it, they make smaller movements in that region until the food is depleted and so on. According to Lévy, ²⁵ the distance of the walk can be represented by a discrete state, and the transition between states follows the rule of a power probability distribution, which can be described as type y = x^−a, with variable ‘a’ varying between 1 and 3. The variable ‘y’ represents the size of the movement performed, and ‘x’ represents the time. Finally, by incorporating the walking distance to the position of a material point at time t, the new position of the material point at time t + 1 is obtained through equation (1)

$$\text{Position}\left(t+\text{1}\right)=\text{Position}\left(t\right)+\alpha .t^{-\lambda }$$

(1)

where: λ

ranges from 1 to 3 and is different for each cuckoo;

t

represents the tth generation;

α

represents the step size, with α > 0.

The proposed algorithm

The cuckoo search algorithm in the classical version presented basically considers the relationship between the host and cuckoo birds. In the real life of animals, all of them, as well as predators, live in communities, exerting influence over one another. Therefore, in this work, the dynamics of displacement of each community (predators, cuckoos and hosts) are considered, together with the weights of eggs (quantity of eggs), the acquired learning of the host birds regarding the nest that was eliminated by the cuckoo or by predator, etc.

The flowchart shown in Figure 5 shows the steps for the implementation of the proposed algorithm:

Figure 5.

Proposed flowchart: first part – definition of the input data to the adapted cuckoo search algorithm.

According to the flowchart, the number of host bird communities (species) and those of cuckoo and predator birds is defined. The space field delimited by X and Y represents the place where all species of animals live. Furthermore, it represents all possible positions that the host nest may occupy.

Figure 6 shows the various iterations of the proposed algorithm (loops). In it, the host must be started because without host nests, the cuckoo cannot lay eggs and predators cannot act. For each community (host, cuckoo and predator), the centroid must be defined. Moreover, the spatial region and the location that each of the communities will occupy is defined. For example, if the total area of the spatial field is 100 u.d. ² , and the number of host communities is 12, then the area of the region of each host community is 8.33 u.d. ² . Despite equal areas, the formats of each may have irregular shapes. The flowcharts of the birds that follow are explained in ‘Female hosts’ and ‘Female cuckoo birds’ sections.

Figure 6.

Proposed flowchart: second part – definition of the areas occupied by each community, position of each animal, etc.

Within each predator community, there are several animals in search of food. In this work, the movement of Lévy will not be executed for every living being that lives within each community. This is because the predator, by the smell that nests present, knows where the exact location of the egg is. Therefore, it is not a random move.

Each community of predator species has different sniff skills. In addition, there are several types of predators in nature; some have the ability to dig, while others can climb to treetops. In this work, it was defined that the predators live in the median-inferior regions of the space field. The unknown β represents the predation rate (sniff skills), which measures the egg’s ability to survive, ranging from 0 to 1. Following the flowchart, the calculation and comparison of the indexes will be presented later in ‘Movement of communities for future generations’ section.

Finally, applicable to all species of animals, from time to time, there is a need to move in a region in search of food and partners for reproduction. Thus, for each generation, the communities realize the movement of Lévy to obtain a new coordinate of the centroid.

Female hosts

Birds, in general, live in different places with respect to each other, but when they are in the breeding season, they need to live in communities to provide a partner for reproduction. Each community (that is, each species) consists of a certain amount of birds. Together, the couple of birds search for food, a task often exercised mainly by the female.

The female can deposit several eggs (some, only one egg; others, three to five eggs) at each reproductive cycle, and all in the same nest. By virtue of the weight provided by the egg that each bird carries, it can hardly be reached in the coordinate suggested by Lévy flight. In this study, it is assumed that both altitude (x) and longitude (y) are halfway between the initial flight position and the suggested coordinate.

When the female discovers that there is some intruder in her nest, she destroys the intruder egg or else leaves the nest and remakes another in different place. The host bird may, in its generation, have several reproductive cycles as cited, but this will not be considered in the present work. When the egg hatches, the chick bird will grow in the future, thus repeating the cycle as that of the parent birds.

Although host birds are irrational beings, they are endowed with intelligence to build nests, to sing, to drive away opponents, etc. The birds that make up each community have the perception of places that offers the greatest risk of survival, of finding food, and of providing security to the offspring. Thus, when the female host bird decides to build its nest, it will not automatically do so in places little chosen by its community.

In other words, if a particular nest has already been visited by a predator or an intruder bird, the chance of choosing such a location should be as small as possible (4). These proposed equations, which describe the coordinates of the female hosts, are defined on the basis of what has been learned by the birds in each time window n. This behaviour learned from host birds has already been advocated by Winfree. ²⁶ According to the author, this learned behaviour directly affects the behaviour of the movements of subsequent generations.

Figure 7 shows an example of the proposal in the present work with 12 generations, N = 4, where n is formed with periods of three generations each.

Figure 7.

Example of multiple generation periods.

The acquired learning of the birds about each nest, in each time window, is calculated based on equation (2)

$$N{A}_n=\frac{N{F}_{\left(K\right)}}{T{T}_{\left(K\right)}}$$

(2)

where: NF_(K)

number of failures in nest egg installation in K generations

TT_(K)

total attempts to install the egg in the nest in K generations

N

corresponds to the number of multiple generation periods

Over time (advancement of the number of generations), some of what was learned in the less recent past about the nest is forgotten, thus receiving smaller weights.

For multiple periods, the acquired learning of host bird communities about each nest, acquired over generations, is given by equation (3)

$$\gamma ={\displaystyle \sum _{n=1}^N{\varphi }_{n}xN{A}_n}$$

(3)

where: Ø

learning weight

$${\displaystyle \sum _{n=1}^N{\varphi }_n=1}$$

The correction of the coordinates is obtained through equation (4)

$$\begin{array}{c}{x}_{\mathit{novo}}\leftarrow x_{\mathit{L}é\mathit{vy}}\pm x_{\mathit{L}é\mathit{vy}}.\gamma \\ y_{\mathit{novo}}\leftarrow y_{\mathit{L}é\mathit{vy}}\pm y_{\mathit{L}é\mathit{vy}}.\gamma \end{array}$$

(4)

The equations suggest adaptations to the coordinates obtained by Lévy flight (1) obtained by each host bird, which due to threats suffered by previous generations, prevent them from installing in the suggested coordinates.

Figure 8 shows the flowchart the activities mentioned above by the female host birds, where p_a corresponds to the probability that the nest is abandoned because of discovering the intruder egg, as mentioned by Yang and Deb. ¹

Figure 8.

Flowchart of female hosts.

Female cuckoo birds

Similarly, cuckoo birds also live in communities, finding partners for reproduction within their own community. In the reproductive period, the female searches for host nests, leaving her community. This is because the movement of the cuckoos is conditioned to the position of the host nest, and where there is an egg in it. Therefore, the movement of this, unlike a host bird, should not be restricted to the community to which it belongs.

Through Lévy flight, one searches for some nest of a host that contains an egg. The methodology proposed here considers the possibility of the cuckoo infecting different species of hosts. Because of the amount of eggs it carries in the reproductive period, the weight is greater, and therefore it is difficult to reach the coordinates as suggested by Lévy flight.

The more eggs it carries, the more difficult it is to raise high flights (x). In the same way, there is greater difficulty to reach nests of hosts located in more distant regions (y). As the egg is deposited, the flight becomes lighter. This work proposes an adaptation after the application of the Lévy movement through equation (5)

$$\begin{array}{l}{x}_{Lévy}\leftarrow x_{Lévy}-0.5x_{Lévy}.\left(\frac{n_{\mathit{eggs}}-n_{\mathit{deposited}\_\mathit{eggs}}}{n_{\mathit{eggs}}}\right)\\ y_{Lévy}\leftarrow y_{Lévy}-0.5y_{Lévy}.\left(\frac{n_{\mathit{eggs}}-n_{\mathit{deposited}\_\mathit{eggs}}}{n_{\mathit{eggs}}}\right)\end{array}\}$$

(5)

If the new suggested position does not find a host nest, the search for the nearest nest is carried out.

When depositing the egg in the nest of the host, the female departs from the position of where it is and, by Lévy flight, reaches another nest, repeating equation (5).

The described activities of female cuckoos are represented by the following flowchart (Figure 9).

Figure 9.

Flowchart of female cuckoos.

Movement of communities for future generations

After understanding the dynamics of each type of animal, it can be seen that the movement of each community is not a random event, but rather, conditioned to situations that allow better survival of the species. Thus, the movements of the centroids, obtained by Lévy flight, must also undergo adaptations throughout the generations.

In the case of hosts, each species (community) tends to choose the coordinates that give it the best chance of egg hatching, which are the closest positions to the centroid and are higher (far from predators) and far from intruders. For the cuckoos, the centroid should be directed to the coordinate where it has the highest number of eggs of its species hatched (higher and closer to its community) and fewer abandoned nests. For predators, they should target the coordinate of the centroid where their community has obtained eggs to feed and which is closer to their community.

After a more in-depth analysis, the dynamics of the animals are summarized in flowcharts, as shown in Figures 10 and 11.

Figure 10.

Updating the centroid to the next generation – female hosts and cuckoos.

Figure 11.

Updating the centroid to the next generation – predators.

Calculation of indexes – Example of an application of the proposed procedure

For the illustration of the proposed index, consider the following example, where the cuckoo search algorithm has already been executed, providing the information of the rows and columns, as shown in Figure 12. The number of rows and columns represent the spatial field where all communities of all species of animals live. The more distant regions of predators are located in higher places, so they are most preferred by birds.

Figure 12.

Example of spatial field where communities live.

According to the example, the space field is formed by X = 7 rows and Y = 8 columns. Each cell in the matrix represents the position where a nest host can be installed. When the cell is null, it indicates that either the cuckoo bird did not infect the host’s nest, or there is no nest host, or the nest egg was used as food for predators. Regardless of the scenario, what matters are the numbers other than zero. Note that the numbers, except the null value, vary from 1 to 5, indicating that there are five types of cuckoos. The illustrated cuckoos represent the positions of the cuckoos that succeeded in installing the egg in the host's nest, unnoticed by the host bird and not used as food by the predator.

Each type of cuckoo bird, for this article, represents one type of machine. The seven rows represent the number of available positions for machine allocation, which is the total number of machines. The replicas of each type of machine adopted in this example are: 2, 1, 1, 1 and 2 for machine types 1, 2, 3, 4 and 5, respectively. The numbering of positions (or locations) starts from the centre of the shop floor to the ends, always closer to the centroid, as shown in Figure 13. Nevertheless, the centroid is always the most preferred for positioning machines; see Appendix 1. According to the example, the centroid is obtained through $x_{\mathit{centroid}}=y_{\mathit{centroid}}=\left(\text{3}+\text{1}\right)/\text{2}$ .

Figure 13.

Correlation between the regions of the space field with the factory floor.

When reading the first row, note that there are three different numbers from zero. In addition, it is noticed that the proposed algorithm suggests that the three types of machines can be chosen for allocation in the best place (higher, therefore near the plant centre). The chance that each machine type 1, 2 and 4 is chosen is 2/4, 1/4 and 1/4, respectively. The recommendation of Júnior ⁷ is that machines with fewer replicates are the priority ones. This justification is now shown in Appendix 2.

This work proposes the following equation (6) as a tie-breaking criterion, which takes into account the allocation suggested by the cuckoo search algorithm as well as the number of replicas of each type of machine. The type of machine k that has the highest index should be chosen. After this index comparison analysis, if the tie situation still prevails, then any type of machine may be chosen

$$\mathit{index}\left(k\right)=A/B$$

(6)

where:

$$A=A\text{1}/A\text{2}$$

A1

represents the number of times machine k appears on the ith line

A2

represents the number of nests successfully infected

$$B=B\text{1}/B\text{2}$$

B1

represents the number of replicas of the k-type machine

B2

represents the total number of machines

If the types of machines present in a particular row no longer have replicas, the corresponding position must be available for future allocation (replicas pending allocation).

From the pending allocation machines, starting from the positions closest to the centre, choose the ones that have lowest number of replicas. By doing this, every distributed layout is generated, and then the degree of distribution can be calculated. After several generations, the best physical arrangement (lowest degree of distribution) is the maximally distributed layout.

Computational experiments and discussion of results

This topic presents the parameters used in the simulation and discussion of the results. The computational models were developed in Pascal programming and simulated with a Pentium Dual Core with 2.0 GB RAM.

For the definition of the parts profiles, it is important to know that, generally, the sequences of operations are defined according to the number of replicas. That is, the larger the numbers of replicas of a particular type of machine, the greater the chance that it will be chosen in the operation. However, this situation does not apply to turbulent environments, since the profile of the piece is unknown and it changes constantly. Therefore, the sequence of operations, the number of operations, the lot sizes and the duration of each operation are randomly generated: a variety of 30–60–90 types of parts; a sequence of operations ranging from 1 to 15; the number of lots ranging from 50 to 100 and the duration of each operation varying from 10 to 100 units of time.

The parameters adopted for each type of metaheuristic are shown in Table 1.

Table 1.

Parameters adopted for the simulation.

Genetic algorithm

Proposed cuckoo search

Crossover probability = 0.8 Mutation probability = 0.02 Size of population = 40 individuals Number of generations = 50

Space field size (Y) = 600 units of distance Proportion between types of hosts and types of cuckoos = 3:1 Types of predators = 30 Height where predators live = 0.85 (i.e. 0.85 × total of machines) pa = 0.25 Number of host birds living within their community = 10–50 Number of cuckoos living within their community = 2–10 Number of eggs each cuckoo bird can carry = 1–5 α = 1.2 (Lévy flight factor) Number of generations = 50 N = 2 (two periods of generations) K = 3 (each period with three generations) Ø = 0.1 (learning weight)

The value for Y must be large enough to simulate the vast field of nature and must not extrapolate computational capacity. For this study, Y = 600 units of distance (u.d.) was adopted.

Most cuckoo birds are dependent on host birds for the perpetuation of the species in subsequent generations. Thus, it is recommended that the number of host types as well as the number of each community be greater than that of cuckoos. A proportion of 3:1 was defined. It is also assumed that two species or more of cuckoos cannot occupy the same nest, and birds, per generation, have only one reproductive cycle.

The variety of predators was arbitrarily defined at 30, and they are active up to 85% of the maximum established height. Finally, both metaheuristics were defined arbitrarily in 50 generations for simulation.

It is worth noting that from the machine-directed algorithms (TARGET and ALVO), the iterations of these algorithms have already been performed to obtain the best layout. Therefore, there is no need to generate multiple instances of physical arrangement for analysis. Heuristics inspired by nature, however, are executed over several generations.

Performance evaluation among classical methods, Genetic Algorithm and cuckoo search proposed

The results obtained with the simulation are in Tables 2 and 3. The experiments were conducted using mostly the total number of machines of classic references of this subject, as shown in Table 5 in Appendix 3.

Table 2.

The results of the 13 experiments for each type of algorithm.

Experiment	TARGET		ALVO
	DD	CPU	DD	CPU
1	4.63	0	4.37	0
2	4.12	0	4.06	0
3	6.45	0	6.08	0
4	6.80	0	7.29	0
5	20.11	0	19.67	0
6	12.40	0	14.34	0
7	7.56	0	9.14	0
8	38.11	0	34.12	0
9	21.02	0	20.31	0
10	20.48	0	19.42	0
11	8.21	0	9.81	0
12	41.46	0	37.16	0
13	115.88	1 s	117.82	0

Note: Bold and underlined values represent the best results.DD: degree of distribution (in u.d.); CPU: computational time.

Table 3.

The results of the 13 experiments for each type of metaheuristic after 50 generations.

Experiment	Genetic algorithm		Proposed cuckoo search
	DD	CPU (s)	DD	CPU
1	3.88	8	3.79	8 min 13 s
2	3.97	9	3.78	9 min 50 s
3	5.68	9	5.78	10 min 50 s
4	6.67	12	6.46	20 min 31 s
5	17.83	14	19.01	22 min 10 s
6	12.45	13	13.09	24 min 33 s
7	7.81	14	8.17	24 min 34 s
8	36.42	18	35.89	27 min 27 s
9	20.01	17	19.85	27 min 27 s
10	19.75	17	19.10	26 min
11	7.80	17	8.17	32 min
12	40.72	25	38.23	41 min
13	111.97	35	110.43	1 h 42 min

Note: Bold and underlined values represent the best results.DD: degree of distribution (in u.d.); CPU: computational time.

Comparing the results of TARGET and ALVO, in terms of the degree of distribution, the first was better in five experiments and the second in eight of them.

Observing the results, comparing the relation between the total number of machines and the replicates used in each study, there is strong evidence that when the layout is medium to large, the greater the proximity between the quantities of each type of machine, the better the performance of TARGET is. On the other hand, the larger the difference of replicas, the better the performance of ALVO is. For smaller layouts, the performance of the ALVO algorithm seems to be indisputably better, independent of the replicas of the machines.

The following are the simulation results for the two metaheuristics:

The results show that the performances regarding the degree of distribution alternate. From the 13 experiments conducted, the proposed algorithm of cuckoo search was better in eight of them, while the Genetic Algorithm was better in five. It is also noticed that a correlation exists between the total of machines and the number of replicas of each type of machine, as analysed in the results obtained from previous algorithms. The smaller the difference between replicas of each type of machine, the better the efficiency of the Genetic Algorithm is; otherwise, the cuckoo algorithm excels. This fact is independent of the size of the layout.

Merging the results of all simulations:

in regard to the degree of distribution: TARGET had a lower degree of distribution in two experiments; the ALVO algorithm in two experiments; the Genetic Algorithm in three experiments; the cuckoo search algorithm in six experiments;

in terms of computational time: TARGET and ALVO presented similar results. According to the reports, both had advantages for the ability to obtain a low degree of distribution (not necessarily the best) in a short period of time.

In addition, we showed the efficiency of the proposed cuckoo search to obtain the lowest degree of distribution, with the counterpart of a high computational time in relation to the other methods. This is because in order to obtain each result, the displacements of each animal are simulated, together with the egg weight, egg predation, etc., demanding a longer computational time. This fact is concretized when considering the larger space field X and Y.

The main difficulty in this type of physical arrangement is to define the best positioning of each type of machine in large physical arrangements. Therefore, the results obtained are considered promising, since the proposed algorithm was able to meet this requirement.

It is to be expected that a physical arrangement with a low degree of distribution is more robust to meeting the constant variations of the pieces. To verify this robustness, the production of pieces was simulated, and the distance covered by the part in the virtual cell was counted. Table 4 shows the expected course performed by the parts in the formed virtual cell.

Table 4.

Comparison of the results in the total routing distance, in u.d.

	30 types of parts				60 types of parts				90 types of parts
Experiment	T	A	GA	PCS	T	A	GA	PCS	T	A	GA	PCS
1	218	224	212	204	464	484	444	424	627	636	598	573
2	209	232	222	208	456	471	450	447	607	636	600	600
3	286	265	248	254	565	553	507	515	745	719	663	681
4	316	355	309	316	638	699	637	623	805	914	828	811
5	423	419	428	413	924	884	892	858	1177	1176	1189	1149
6	413	432	397	424	873	966	862	890	1143	1204	1096	1168
7	394	444	401	404	851	935	842	869	1051	1191	1045	1098
8	566	488	517	476	1140	979	1082	1043	1460	1315	1370	1365
9	440	472	436	422	929	963	912	905	1210	1273	1175	1166
10	474	474	450	434	950	929	920	891	1202	1203	1182	1147
11	454	519	431	447	929	1036	925	938	1176	1324	1169	1202
12	643	590	550	579	1249	1179	1194	1151	1585	1531	1526	1507
13	975	1001	947	898	2096	2052	1999	1979	2668	2677	2652	2526

Note: Bold and underlined values represent the best results.T: TARGET; A: ALVO; GA: genetic algorithm; PCS: proposed cuckoo search.

It is noted that in some experiments, a low degree of distribution did not guarantee that a low routing distance could be obtained, as in experiments 4, 5, 6, 7, 8, and 12. This reinforces the idea of elaborating a more efficient procedure in the spreading of different types of machines than the degree of distribution proposed by Benjaafar and Shekhzadeh. ⁷

According to Baykasoglu, ¹⁵ the scattering of the machines themselves does not guarantee the reduction of travelling distance. Furthermore, the author commented that the virtual cell is not formed just by looking at the sequence of operation of each type of part. It is fundamental to analyse the ability of each type of machine to perform different operations. Thus, the benefits of machine scattering can be enhanced when parts can be run on different machines and not necessarily restricted to machines in the formed virtual cell.

Regarding the proposed algorithm, in addition to obtaining a layout with a low degree of distribution in most of the experiments, its efficiency in the total routing distance by the pieces in the virtual cells is confirmed.

To verify the efficiency of the cuckoo search algorithm, larger physical arrangements must be tested, as presented by Montreuil et al. ⁹ At the time, the authors conducted simulations for 1296 machines and 125 types of machines. This number of machines was exclusively established to verify the behaviour of the proposed method (TARGET) in terms of computational time and degree of distribution. However, this total amount of machines is unrealistic. Based on the work of Narayanan, ³¹ a physical arrangement that presents up to approximately 16 machines is considered small, up to 30 machines is medium-sized and above that amount is already considered large (up to 120 machines). In fact, this could be confirmed in most of the experiments conducted in the literature, as shown in the simulation results tables.

The following topics are intended to attest to the efficiency of the proposed algorithm for obtaining a maximally distributed layout. The following experiments were conducted only for the physical arrangement size considered critical, that is, the large size (150 machines).

Performance evaluation for the large physical arrangement between the Genetic Algorithm and the proposed Cuckoo Search

Figure 14 shows the evolution of the degree of distribution between the Genetic Algorithm and the proposed cuckoo search algorithm. Note that the quantities of each type of machine play an important role in the performance of each of the algorithms, especially for the cuckoo search algorithm, since with a few generations, a reduced value of the degree of distribution could be obtained. This result can be verified in experiments 2, 4, 8, 10, 12 and 13. This result was already expected, and given the experiments mentioned, many machines have few replicates, so the local priority relation (best local) and priority machine (few replicas) could be satisfied.

Figure 14.

Performance evaluation of the Genetic Algorithm and Cuckoo Search to obtain the degree of distribution (parts 1 and 2).

Cuckoo search performance

This subtopic aims exclusively to evaluate the performance of the proposed algorithm, altering some parameters of Table 1 and setting the others. Due to the limitations of the developed model, only the number of cuckoos’ eggs, the predators operating height, the Lévy factor, the spatial field Y, the number of predator types and the probability of abandonment will be altered.

Number of cuckoo eggs (per each reproductive cycle)

The first experiment analyses the performance by altering the number of eggs each bird cuckoo can deposit and impacts on the degree of distribution. Simulations with four hypothetical situations were performed, wherein the first situation the birds deposited only one egg in their generation. The second situation had from one to five eggs and so on. It was suspected at first that the more eggs each bird could carry, the greater the chance of covering the space field. As a consequence, a higher chance of locating the best position for the cuckoo (machine) in less time (generations) was expected.

Figure 15 presents the results of these simulations. Interestingly, the higher the number of eggs, the worse the performance of the algorithm seems to be. On the other hand, a low number of eggs tends to exhibit the same performance over time.

Figure 15.

Impact of the number of cuckoo eggs on the degree of distribution.

This shows that egg weights should not be omitted, since it is the way that nature has adopted limiting one of its variables in pursuing performance optimization that benefits the system as a whole. The best amount of eggs, per reproductive cycle, confirms Wyver’s ²⁴ research.

Predator operating height

The following are simulations for four possible heights where the predators can act, which are 55 (that is, acting up to 55% of the maximum height), 70, 85 and 100% (maximum height). This simulation aims to verify the importance of predators in eliminating an undesirable solution (position of the egg in a certain nest) and obtaining a better one.

The results of the simulations are presented in Figure 16. When the predator is able to act in higher regions, the efficiency of cuckoo search is impaired. This result was expected because by increasing the field of action of the predators, the good positions obtained from the cuckoos’ eggs are eliminated, and all efforts of the algorithm are wasted. Moreover, acting in lower regions, most of the nests installed do not suffer enough threats to justify repositioning the nests. Therefore, there is no evidence of a better solution.

Figure 16.

Impact of the height of action of predators on the degree of distribution.

Flight factor of Lévy (α)

Four α values were defined for analysis. According to the Lévy equations, the greater the value of this variable, the greater the amplitude reached by the birds. It is hoped, therefore, to cover the greater range of locations where the nests will be positioned and thus obtain the degree of distribution in less time. When the model is executed, due to the interactions among the variables, this premise is not satisfied.

The results are shown in Figure 17. It can be seen that the degree of distribution is inert to values above α = 1, since the curves overlap. These results, surprisingly, confirm the statements of Yang and Deb, ¹ by stating that the value of α ≥ 1 is usually used. This fact confirms the importance of analysing the interactions between animal species, which adjusts to maintain the balance of the system as a whole.

Figure 17.

Impact of the Lévy factor on the degree of distribution.

Space field size (Y)

The larger the spatial field, the greater the chance of having a larger variety of cuckoo (types of machines) candidates to settle in preferred (higher) locations is. In fact, Figure 18 shows that for a larger search field, the smaller the result of the degree of distribution will be. The best distribution grade value for Y = 800 is 109.27 u.d., which was already reached between the 30th and 40th generation. This value of the degree of distribution even surpasses (better) that presented in Table 3.

Figure 18.

Impact of the Y space field on the degree of distribution.

Number of predators

This simulation aims to analyse the importance of predators in eliminating eggs (either host or cuckoo), improving or worsening the degree of distribution value due to the repositioning of the egg positions over generations. The results show that up to the 20th generation, there is alternation in the results. This fact was expected, since each type of predator will find, in each generation, more or less nests with eggs within its community to feed upon. The results also show that a median variety of predators has been able to perform adequately across the spatial field, and adding a greater variety of predator types does not bring expected benefits; see Figure 19.

Figure 19.

Impact of the number of predator types on the degree of distribution.

Probability of intruder egg discovery promoting nest abandonment (P_a)

For Stevens, ³² when the host bird has spotted a cuckoo bird, the egg nest’s intrusion rate tends to increase. In the author’s words, this is one reason why the cuckoo birds’ population is declining. For this simulation, we want to verify if this increase in the probability of discovery would affect the degree of distribution.

In fact, if the abandonment rate is higher, it means that the cuckoo’s egg (the type of machine) has the greatest chance of being unable to be installed, thus requiring more generations to do so, as shown in Figure 20. For this reason, when the abandonment rate increases, few changes in the degree of distribution could be verified, since no new and better position of the cuckoo was obtained.

Figure 20.

Impact of the abandonment rate p_a on the degree of distribution.

The best results are obtained by adopting p_a = 0.25, whose value proves the recommendation of Yang and Deb, ¹ which is the best value for the solution (cuckoo).

Conclusion

This work presented the necessary adaptations to the limited version of the classic cuckoo search algorithm, applied to the distributed layout generation problem. The highest computational time required during the simulation was expected due to the characteristics of the dynamics of the birds themselves. Although entailing a computational time that was greater than the others, the advantage is that in the majority of the analysed instances, the degree of distribution that is obtained is smaller.

However, a maximally distributed physical arrangement that presents a lower degree of distribution does not guarantee that for a set of analysed parts, the travelling distance of parts is reduced. In parallel, properly choosing the virtual cells also has its due importance that deserves special attention, as explained by Baykasoglu. ¹⁵ Furthermore, it is essential that other distribution grade methods are developed to ensure the fidelity of the distance and degree of distribution relationship.

The cuckoo search algorithm was the one that presented the best degree of distribution. Although the advantages are obtained by the proposed method, the present work does not aim to disqualify the works already published because the characteristics of each methodology for the generation of the physical arrangement differ from each other; however, it is important to show that the cuckoo search algorithm can be as good or even better in some cases.

In addition, this requires a high space field for the simulation of the dynamics of the animal’s displacement, easily extrapolating the capacity of data storage in matrices. Moreover, the computational time grows according to the size of the matrix. Another difficulty was defining the initial parameters to execute the proposed cuckoo algorithm. As seen in the experiments, the vast majority of variables should be carefully chosen because they directly interfere with the results, either for better or for worse.

It is important to note that not all types of cuckoos are not always in the space field due to abandonment or because they are used as food by the predator. Thus, the degree of distribution cannot always be calculated in each generation.

It is surprising to know that the best parameters are used in the simulation, are confirmed by authors in experiments in other areas of application or are found in observations in nature.

In this work, the area occupied by each community is the same, albeit with irregular formats between each one. As a suggestion for future work, it is important to consider unequal areas.