1 Introduction

There exists a rich collection of nonlinear optical effects (Kwong and Yang 1997; Aggarwal 2001; Thing et al. 2004; Babcock 1953; Singh and Bansal 2013) in optical WDM systems, each of which manifests itself in a unique way. Out of these nonlinearities, the FWM crosstalk signal is the major dominant noise effects in optical WDM systems employing equal channel spacing (ECS). Four-wave mixing is a third-order nonlinear optical effect in which two or more wavelengths (or frequencies) combine and produce several mixing products. For uniformly spaced WDM channels, the generated FWM product terms fall onto other active channels in the band, causing inter-channel crosstalk. The performance can be substantially improved if FWM crosstalk generation at the channel frequencies is prevented. The efficiency of FWM signals depends on the channel spacing and fiber dispersion. If the frequency separation of any two channels of an optical WDM system is different from that of any other pair of channels, no FWM crosstalk signals will be generated at any of the channel frequencies (Kwong and Yang 1997; Aggarwal 2001; Thing et al. 2004; Babcock 1953; Singh and Bansal 2013).

To suppress the FWM signals in optical WDM systems, unequally spaced channel allocation (USCA) algorithms (Kwong and Yang 1997; Sardesai 1999; Forghieri et al. 1995; Hwang and Tonguz 1998; Tonguz and Hwang 1998; Atkinson et al. 1986; Randhawa et al. 2009) have been proposed, having the limitation of increased channel bandwidth requirement compared to equally spaced channel allocation (ESCA). This paper proposes an unequally spaced optical bandwidth channel allocation algorithm by taking into consideration the concept of near-OGRs (Babcock 1953; Bloom and Golomb 1977; Shearer 1998) to suppress FWM crosstalk in optical WDM systems.

Studies have been shown that Golomb rulers represent a class of NP-complete (http://theinf1.informatik.uni-jena.de/teaching/ss10/oberseminar-ss10) problems. For higher order marks, the exhaustive computer search (Robinson 1979; Shearer 1990) of such problems is difficult. Numerous algorithms (Robinson 1979; Shearer 1990; Galinier et al. 2001; Leitao 2004; Rankin 1993; Cotta et al. 2006) have been proposed to tackle Golomb ruler problem. To date, no efficient algorithm is known for finding the shortest length ruler. The realization of nature-inspired metaheuristic optimization algorithms such as Tabu search (TS) (Cotta et al. 2006), Memetic approach (Cotta et al. 2006), Genetic algorithms (GAs) (Soliday et al. 1995; Robinson 2000; Ayari et al. 2010; Dotú and Hentenryck 2005) and its hybridizations (HGA) (Ayari et al. 2010), hybrid evolutionary (HE) algorithms (Dotú and Hentenryck 2005), Biogeography based optimization (BBO) (Bansal 2014) and Big bang–big crunch (BB–BC) (Bansal 2017; Bansal and Sharma 2017) in finding relatively good solutions to such NP-complete problems provides a good starting point for algorithms of finding near-OGRs. Therefore, nature-inspired algorithms seem to be very effective solutions for such NP-complete problems. This paper proposes the application of five nature-inspired algorithms namely BB–BC algorithm, Firefly algorithm (FA), Bat algorithm (BA), Cuckoo search algorithm (CSA), Flower pollination algorithm (FPA) and their modified forms to find either optimal or near-optimal rulers in a reasonable time and their performance comparison with the existing conventional and nature-inspired algorithms to find near-OGRs.

2 Golomb rulers

Babcock (1953) firstly introduced the concept of Golomb rulers, and further was described by Bloom and Golomb (1977). According to the literatures (Colannino 2003; Dimitromanolakis 2002; Dollas et al. 1998), all of rulers’ up to 8-marks introduced in Babcock (1953) are optimal; the 9- and 10-marks are near-optimal.

Golomb rulers are an ordered set of unevenly marks at positive integer locations such that no distinct pairs of numbers from the set have the same difference (http://www.distributed.net/ogr; Bansal 2019; Drakakis and Rickard 2010; Drakakis 2009). This means that an n-mark Golomb ruler \(G = \left\{ {x_{1} ,x_{2} , \ldots ,x_{n - 1} ,x_{n} } \right\}\begin{array}{*{20}c} {} & {x_{1} < x_{2} < \cdots < x_{n - 1} < x_{n} } \\ \end{array}\) is an ordered set of n different positive integer numbers such that all the positive differences

$$|x_{i} - x_{j} |,\begin{array}{*{20}c} {} & {x_{i} ,x_{j} \in G} \\ \end{array} \begin{array}{*{20}c} {} & \forall \\ \end{array} i > j\,{\text{or}}\,i \ne j$$
(1)

are distinct (Bansal 2017). And

$$\forall i,j,k,l \in \{ 1,2, \ldots ,n - 1,n\} ,x_{i} - x_{j} = x{}_{k} - x_{l} \Leftrightarrow i = k \wedge j = l.$$
(2)

The positive integer numbers are referred to as order or marks. The number of marks on a ruler is referred to as the ruler size. The difference between the largest and smallest number is referred to as the ruler length RL, i.e.

$$RL = \hbox{max} \left( G \right) - \hbox{min} \left( G \right) = x_{n} - x_{1}$$
(3)

where

$$\hbox{max} \left( G \right) = \hbox{max} \left\{ {x_{1} ,x_{2} , \ldots ,x_{n - 1} ,x_{n} } \right\} = x_{n}$$
(4)

and

$$\hbox{min} \left( G \right) = \hbox{min} \left\{ {x_{1} ,x_{2} , \ldots ,x_{n - 1} ,x_{n} } \right\} = x_{{^{1} }}$$
(5)

Generally, the first mark x1 of set G may be assumed on position 0. Then the n-mark Golomb ruler set becomes \(G = \{ 0,x_{2} , \ldots ,x_{n - 1} ,x_{n} \}\) and the RL of such n-mark set G is xn.

An OGR is the shortest length ruler for a given number of marks (http://mathworld.wolfram.com/PerfectRuler.html; http://mathworld.wolfram.com/GolombRuler.html). There can be multiple different OGRs for a specific number of marks. However, the unique optimal Golomb 4-marks ruler is shown in Fig. 1, which measures all the distances from 0 to 6.

Fig. 1
figure 1

A 4-marks OGR with its associated distances

Full size image

A perfect Golomb ruler measures all the integer distances from 0 to RL (http://theinf1.informatik.uni-jena.de/teaching/ss10/oberseminar-ss10; Soliday et al. 1995). The ruler length RL of perfect Golomb ruler set G is (Rankin 1993):

$$RL = \frac{{n\left( {n - 1} \right)}}{2} = \sum\limits_{i = 1}^{n - 1} i$$
(6)

For example, the set (0, 1, 3, 7, 12, 20), shown in Fig. 2 is a non-optimal 6-marks Golomb ruler with a length of 20. As from the differences it is clear that the numbers 10, 14, 15, 16, 18 are missing, so it is not a perfect Golomb ruler set. The distance associated between each pair of marks is also shown in Fig. 2.

Fig. 2
figure 2

A 6-marks non-OGR with its associated distances

Full size image

The OGRs found their potential applications in radio frequency allocation, computer communication network, sensor placement in X-ray crystallography, circuit layout, pulse phase modulation, self-orthogonal codes, VLSI architecture, geographical mapping, coding theory, linear arrays, fitness landscape analysis, radio astronomy, antenna design for radar missions, sonar applications and NASA missions in astrophysics, planetary and earth sciences (Babcock 1953; Bloom and Golomb 1977; Rankin 1993; Soliday et al. 1995; Dimitromanolakis 2002; Dollas et al. 1998; Lam and Sarwate 1988; Lavoie et al. 1991; Robinson and Bernstein 1967; Cotta and Fernández 2005; Fang and Sandrin 1977; Blum et al. 1974; Memarsadegh 2013; http://encompass.gsfc.nasa.gov/cases.html).

On applying OGRs to the channel allocation, it was possible to achieve the smallest distinct number to be used for the optical WDM channel allocation problem. As the difference between any two numbers is distinct, the new FWM frequency signals generated would not fall into the one already assigned for the carrier channels.

3 Nature-inspired metaheuristic algorithms

Due to highly nonlinearity and complexity of the problem of interest, design optimization in engineering fields tends to be very challenging. As conventional computing algorithms are local search algorithm, so they are not the best tools for highly nonlinear global optimization, and thus often miss the global optimality. In addition, design solutions have to be robust, low cost, subject to uncertainty in parameters and tolerance for imprecision of available components and materials. Nature-inspired algorithms are now among the most widely used optimization algorithms. The guiding principle is to devise algorithms of computation that lead to an acceptable solution at low cost by seeking for an approximate solution to a precisely/imprecisely formulated problem (Cotta and Hemert 2008; Yang 2010a, 2012a, 2013a; Koziel and Yang 2011; Rajasekaran and Vijayalakshmi Pai 2004; Mitchell 2004).

This section is devoted to the brief overview of nature-inspired optimization algorithms based on the theories of big bang and big crunch called BB–BC, flash pattern of fireflies called FA, the echolocation characteristics of microbats called BA, brood parasitism of cuckoo species called CSA and flow pollination process of flowering plants called FPA.

The power of nature-inspired optimization algorithms lies in how faster the algorithms explore the new possible solutions and how efficiently they exploit the solutions to make them better. Although all optimization algorithms in their simplified form works well in the exploitation (the fine search around a local optimal), there are some problems in the global exploration of the search space. If all of the solutions in the initial phase of the optimization algorithm are collected in a small part of search space, the algorithms may not find the optimal result and with a high probability, it may be trapped in that sub-domain. One can consider a large number for solutions to avoid this shortcoming, but it causes an increase in the function calculations as well as the computational costs and time. So for the optimization algorithms, there is a need by which exploration and exploitation can be enhanced and the algorithms can work more efficiently. By keeping this in mind two features, fitness (cost) based mutation strategy and random walk i.e. Lévy-flight distribution are introduced in the proposed metaheuristic algorithms, which is the main technical contribution of this paper. The Lévy flights distribution is much faster than the normal random walk. Lévy flights can reduce the required number of metaheuristic algorithms iterations by ~ 4 orders compared to normal random walk (Mareli and Twala 2018). Both the mutation and Lévy flight strategies help the metaheuristic algorithms to jump out of the local optimum, avoid the premature convergence of the algorithm and improve the global search ability so as to maintain the good population diversity. In all the modified algorithms, the mutation rate probability is determined based on the fitness value. The mutation rate probability MRti of each solution xi at running iteration index t, mathematically is given by:

$$MR_{i}^{t} = \frac{{f_{i}^{t} }}{{Max(f_{{}}^{t} )}}$$
(7)

where fti is the fitness value of each solution xi at iteration index t, and \(Max(f^{t} )\) is the maximum fitness value in the population at iteration t. For all proposed algorithms, the mutation equation (Storn and Price 1997; Price et al. 2005) use throughout this paper is:

$$x_{i}^{t} = x_{i}^{t - 1} + p_{m} (x_{best}^{t - 1} - x_{i}^{t - 1} ) + p_{m} (x_{{r_{1} }}^{t - 1} - x_{{r_{2} }}^{t - 1} )$$
(8)

where \(x_{i}^{t}\) is the population at running iteration index t, \(x_{best}^{t - 1} = x_{*}^{t - 1}\) is the current global best solution at iteration one less than running iteration index t, pm is mutation operator, r1 and r2 are uniformly distributed random integer numbers between 1 to size of the given problem. The numbers r1 and r2 are different from running index. Typical values of pm are same as in GA i.e. 0.001 to 0.05. The mutation strategy increases the chances for a good solution, but a high mutation rate (pm = 0.5 and 1.0) results in too much exploration and is disadvantageous to the improvement of candidate solutions. As pm decreases from 1.0 to 0.01, optimization ability increases greatly, but as pm continues to decrease to 0.001, optimization ability decreases rapidly. A small value of pm is not able to sufficiently increase solution diversity (Bansal 2014).

The Lévy flight distribution (Yang 2012b) used for all proposed algorithms in this paper mathematically is given by:

$$L(\lambda ) \sim \frac{\lambda \varGamma (\lambda )\sin (\pi \lambda /2)}{\pi }\frac{1}{{s^{1 + \lambda } }},\begin{array}{*{20}c} {} & {(s > > s_{0} > 0)} \\ \end{array}$$
(9)

Here, Γ(λ) is the standard gamma distribution valid for large steps i.e. for s > 0. Throughout the paper, λ = 3/2 is used. In theory, it is required that \(\left| {s_{0} } \right| > > 0\), but in practice s0 can be as small as 0.1 (Yang 2012b).

By introducing these two features in the simplified forms of proposed algorithms, the basic concept of search space is modified i.e. the proposed algorithms can explore new search space by the mutation and random walk. A fundamental benefit of using mutation and Lévy flight strategies with nature-inspired algorithms in this paper is their ability to improve its solutions over time, which does not seem in the existing algorithms (Cotta et al. 2006; Soliday et al. 1995; Robinson 2000; Ayari et al. 2010; Dotú and Hentenryck 2005; Bansal 2014, 2017; Bansal and Sharma 2017) to find near-OGRs.

3.1 Big bang–big crunch optimization algorithm and its modified forms

Erol and Eksin (2006), inspired by the theories of the evolution of universe; namely, the Big bang and Big crunch theory, developed a metaheuristic algorithm called Big bang–big crunch (BB–BC) optimization algorithm. BB–BC algorithm has two phases: Big bang phase where candidate solutions are randomly distributed over the search space and big crunch phase where a contraction procedure calculates a center of mass or the best fit individual for the population (Erol and Eksin 2006; Afshar and Motaei 2011; Tabakov 2011; Yesil and Urbas 2010). In BB–BC, the centre of mass mathematically is computed by:

$$\mathop x\nolimits_{c} = \frac{{\sum\limits_{i = 1}^{Popsize} {\frac{1}{{f_{i} }}\mathop x\nolimits_{i} } }}{{\sum\limits_{i = 1}^{Popsize} {\frac{1}{{f_{i} }}} }}$$
(10)

where xc = position of the center of mass; xi = position of candidate i; fi = fitness (cost) value of candidate i; and Popsize = population size. Instead of the center of mass, the best fit individual can also be chosen as the starting point in the big bang phase. The new candidates (xnew) around the centre of mass are calculated by adding or subtracting a normal random number whose value decreases as the iterations elapse. This can be formalized as by (Erol and Eksin 2006):

$$x_{new} = x_{c} + r \times c_{1} \times \frac{{(\mathop x\nolimits_{\hbox{max} } - x_{\hbox{min} } )}}{{1 + t/\mathop c\nolimits_{{_{2} }} }}$$
(11)

where r is a random number with a standard normal distribution, c1 is a parameter for limiting the size of the search space, parameter c2 denotes after how many iterations the search space will be restricted to half, xmax and xmin are the upper and lower limits of elite pool, and t is the iteration index.

If fitness based mutation strategy is introduced in the simple BB–BC algorithm, a new Big bang–big crunch algorithm with mutation (BB–BCM) can be formulated.

On adding Lévy-flight distributions in the simple BB–BC algorithm, another new Lévy–flight Big bang–big crunch algorithm (LBB–BC) can be formulated. For LBB–BC, Eq. (11) is randomized via Lévy flights as:

$$x_{new} = x_{c} + r \times c_{1} \times \frac{{(\mathop x\nolimits_{\hbox{max} } - x_{\hbox{min} } )}}{{1 + t/\mathop c\nolimits_{{_{2} }} }} \oplus L(\lambda )$$
(12)

The product \(\oplus\) means entrywise multiplications and L(λ) is the Lévy flight based step size given mathematically by Eq. (9).

If fitness based mutation strategy is applied to LBB–BC algorithm, Lévy flight Big bang–big crunch with mutation (LBB–BCM) algorithm can be formulated.

Based upon the above discussions, the corresponding general pseudo-code for modified BB–BC algorithm (MBB–BC) can be summarized in Fig. 3. If the lines 17–22 in Fig. 3 are removed and Lévy flight distributions in lines 14–16 are not used, then Fig. 3 represents the general pseudo-code for BB–BC algorithm. If from lines 14–16 Lévy flight distributions are not used, then Fig. 3 corresponds to the general pseudo-code for BB–BCM algorithm. If no modifications in Fig. 3 are performed, then it represents the pseudo-code for LBB–BCM algorithm.

Fig. 3
figure 3

General pseudo-code for MBB–BC Algorithm

Full size image

3.2 Firefly algorithm and its modified forms

Yang (2010a, 2012a, 2013a), Koziel and Yang (2011) inspired by the flashing pattern and characteristics of fireflies, developed a novel optimization algorithm called Firefly inspired algorithm or Firefly algorithm (FA). For describing this algorithm, FA uses the following three idealized rules:

  1. 1.

    All fireflies are unisex so that one firefly will be attracted to other fireflies regardless of their sex;

  2. 2.

    The attractiveness is proportional to the brightness and they both decrease as their distance increases. If there is no brighter one than a particular firefly, it will move randomly;

  3. 3.

    The brightness of a firefly is determined by the landscape of the objective function.

In FA, the variation of light intensity and the formulation of attractiveness are two main issues. For maximum optimization problems, the brightness I of a firefly at a particular location X can simply be proportional to the objective function i.e. I(X) \(\propto\)f(X) (Yang 2010a, b, c, 2011a, b, 2012a, 2013a; Koziel and Yang 2011; Yang and Deb 2010a; Yang and He 2013). As both the light intensity and attractiveness decreases as the distance from the source increases, the variations of the light intensity and attractiveness should be monotonically decreasing functions. For a given medium with a fixed light absorption coefficient γ, the light intensity I(r) varies with the distance r between any two fireflies (Yang 2010b) as:

$$I = I_{0} e^{ - \gamma r}$$
(13)

where I0 denotes the original light intensity.

As attractiveness of a firefly is proportional to the light intensity seen by the neighboring fireflies, therefore the attractiveness β of a firefly with the distance r is given by:

$$\beta \left( r \right) = \beta_{0} e^{{ - \gamma r^{2} }}$$
(14)

where β0 is the attractiveness at r = 0.

The distance between any two fireflies i and j at locations Xi and Xj, respectively, is the Cartesian distance as given by (Yang 2010b):

$$r_{ij} = \left\| {X_{i} } \right. - \left. {X_{j} } \right\| = \sqrt {\sum\limits_{k = 1}^{d} {\left( {x_{i,k} - x_{j,k} } \right)^{2} } }$$
(15)

where \(x_{i,k}\) is the kth component of the spatial coordinate Xi of ith firefly and d is the number of dimensions in search space. The movement of a firefly i is attracted to another brighter firefly j is determined by (Yang 2010b):

$$X_{i} = X_{i} + \beta_{0} e^{{ - \gamma r_{ij}^{2} }} \left( {X_{j} - X_{i} } \right) + \alpha \left( {rand - 0.5} \right)$$
(16)

where the second term is due to the attraction and the third term is randomization with a control parameter α, which makes the more efficient exploration of the search space. For most cases in the implementation,\(\beta_{0} = 1\) and \(\alpha \in \left[ {0,1} \right]\).

If mutation strategy is combined with the above mentioned three idealized rules, Firefly algorithm with mutation (FAM) can be formulated. All the parameters and equations for FAM are same as for simple FA. Only the difference between algorithms FAM and simple FA is that mutation strategy is added to simple FA.

By combining the characteristics of Lévy flights with the simple FA, another new algorithm named, Lévy flight Firefly algorithm (LFA) can be formulated. For LFA, the third term in Eq. (16) is randomized via Lévy flights. The firefly movement equation for LFA is approximated by:

$$X_{i} = X_{i} + \beta_{0} e^{{ - \gamma r_{ij}^{2} }} \left( {X_{j} - X_{i} } \right) + \alpha .sign\left( {rand - 0.5} \right) \oplus L(\lambda )$$
(17)

The term \(sign(rand - 0.5)\), where \(rand \in [0,1]\) essentially provides a random direction, while the random step length is drawn from a Lévy distribution having an infinite variance with an infinite mean. In LFA the steps of firefly motion are essentially a random walk process.

If both algorithms FAM and LFA are combine into a single algorithm, then Lévy flight Firefly algorithm with mutation (LFAM) can be formulated.

The corresponding general pseudo-code for modified FA (MFA) is shown in Fig. 4. If lines 15–20 in Fig. 4 are removed and in line 13 Lévy flight distributions are not used, then Fig. 4 corresponds to the general pseudo-code for simple FA. If Lévy flight distributions in line 13 are not used in Fig. 4, then it corresponds to the general pseudo-code for FAM and if no modifications in Fig. 4 are performed then it represents the general pseudo-code for LFAM algorithm.

Fig. 4
figure 4

General pseudo-code for MFA

Full size image

3.3 Bat algorithm and its modified forms

Yang (2010a, c, 2011b, 2012a, Yang 2013a) and Koziel and Yang (2011), inspired by the echolocation characteristics of microbats, introduced a novel optimization algorithm called Bat algorithm (BA). For describing this new algorithm, the author in Yang (2010c) uses the following three idealized rules:

  1. 1.

    To sense the distance, all bats use echolocation and they also know the surroundings in some magical way;

  2. 2.

    Bats fly randomly with velocity vi at position xi, with a fixed frequency range [fmin, fmax], fixed wavelength range [λmin, λmax], varying its pulse emission rate r ∈ [0, 1], and loudness A0 to hunt for prey, depending on the proximity of their target;

  3. 3.

    Although the loudness can vary in different ways, it is assume that the loudness varies from a minimum constant (positive) Amin to a large A0.

In BA, each bat is defined by its position xi, velocity vi, frequency fi, loudness Ai, and the emission pulse rate ri in a d-dimensional search space. Among all the bats, there is a current global best solution x* which is located after comparing all the solutions among all the bats. The new velocities \(\mathop v\nolimits_{i}^{t}\) and solutions \(\mathop x\nolimits_{i}^{t}\) at step t are given by (Yang 2010c, 2013a, b; Li et al. 2019; Guo et al. 2019):

$$f_{i} = f_{\hbox{min} } + (f_{\hbox{max} } - f_{\hbox{min} } )\beta$$
(18)
$$\mathop v\nolimits_{i}^{t} = \mathop v\nolimits_{i}^{t - 1} + (\mathop x\nolimits_{i}^{t - 1} - x_{*} )f_{i}$$
(19)
$$\mathop x\nolimits_{i}^{t} = \mathop x\nolimits_{i}^{t - 1} + \mathop v\nolimits_{i}^{t - 1}$$
(20)

where \(\beta \in [0,1]\) is a random vector drawn from a uniform distribution. A random walk is used for local search that modifies the current best solution according to Eq. (21):

$$x_{new} = x_{best} + \varepsilon A^{t}$$
(21)

where \(x_{best} = x_{*}\), \(\varepsilon \in [ - 1,1]\) is a scaling factor and \(A^{t}\) is loudness. Further the loudness A and pulse rate r are updated according to the Eqs. (22) and (23) respectively as iterations proceed:

$$\mathop A\nolimits_{i}^{t} = \alpha \mathop A\nolimits_{i}^{t - 1}$$
(22)
$$\mathop r\nolimits_{i}^{t} = \mathop r\nolimits_{i}^{0} [1 - e^{ - \gamma t} ]$$
(23)

where α and γ are constants and for simplicity, α = γ is chosen. For most of the simulation α = γ = 0.9 is used (Yang 2010c).

By combining the characteristics of mutation and Lévy flights strategies with the simple BA, three new algorithms, namely, Bat algorithm with mutation (BAM), Lévy flight Bat algorithm (LBA) and Lévy flight Bat algorithm with mutation (LBAM) can be formulated. For LBA, the modification performed in Eq. (21) is given by:

$$x_{new} = x_{best} + \varepsilon A^{t} \oplus L(\lambda )$$
(24)

Based on these idealizations, the basic steps of BA can be described as a general pseudo-code shown in Fig. 5. In Fig. 5, if the concept of Lévy flights in lines 11, 12 and mutation (lines 17–22) are omitted, then Fig. 5 corresponds to the general pseudo-code for simple BA. If only the concept of mutation (lines 17–22) is not used in Fig. 5, then it corresponds to the pseudo-code for LBA, otherwise Fig. 5 shows the general pseudo-code for LBAM algorithm.

Fig. 5
figure 5

General pseudo-code for MBA

Full size image

3.4 Cuckoo search algorithm and its modified form

Yang and Deb (2010b), Gandomi et al. (2013), Yang and Deb (2014), inspired by brood parasitism of some cuckoo species, developed a nature-inspired metaheuristic optimization algorithm called Cuckoo search algorithm (CSA). In addition, CSA algorithm is enhanced by the Lévy flights trajectory of some birds, rather than by simple random walks. For describing this algorithm, Yang et al. uses the following three idealized rules:

  1. 1.

    Each Cuckoo lays one egg at a time, and dumps it in a randomly chosen nest;

  2. 2.

    The best nest with high quality of eggs (solution) are carried over to the next iterations;

  3. 3.

    The number of available host nests is fixed, and a host can discover an alien egg with probability \(p_{a}\) ∈ [0,1]. In this case, the host bird can either throw the egg away or simply abandon the nest so as to build a completely new nest in a new location.

For simplicity, the last assumption can be approximated by a fraction pa of the n host nests being replaced by new nests (with new random solutions). For a maximization problem, the quality i.e. fitness of a solution can simply be proportional to the value of the objective function. When new solutions \(x^{t}\) are generating for, say, a cuckoo i, a Lévy flight is performed as approximated by (Iglesias et al. 2018):

$$x_{i}^{t} = x_{i}^{t - 1} + \alpha \oplus L(\lambda )$$
(25)

where \(\alpha > 0\) is the step size, which should be related to the scale of the specified problem.

As authors in Yang and Deb (2010b), already introduced the Lévy flights distribution concept to enhance the performance, so only mutation strategy is applied to simple CSA to explore the search space. The new modified algorithm so formulated is named as Cuckoo search algorithm with mutation (CSAM). The basic steps of CSAM can be summarized as the pseudo-code shown in Fig. 6. If the concept of mutation (lines 9 to 14) is withdrawn from Fig. 6, then it corresponds to general pseudo-code for simple CSA.

Fig. 6
figure 6

General pseudo-code for CSAM

Full size image

3.5 Flower pollination algorithm and its modified form

Yang (2012b) and Yang et al. (2014), inspired by the flow pollination process of flowering plants, introduced an optimization algorithm called Flower pollination algorithm (FPA). For describing this metaheuristic algorithm, the following four idealized rules were used:

  1. 1.

    For global pollination process, biotic cross-pollination is used and pollen-carrying pollinators obey Lévy flights distributions.

  2. 2.

    For local pollination, abiotic and self-pollination are used.

  3. 3.

    Pollinators such as insects can develop flower constancy, which is equivalent to a reproduction probability that is proportional to the similarity of two flowers involved.

  4. 4.

    The interaction of local pollination and global pollination can be controlled by a switch probability p∈[0,1], with a slight bias towards local pollination.

In FPA, the global pollination and local pollination are two main steps. In the global pollination step, flower pollens are carried by pollinators such as insects, and pollens can travel over a long distance because insects can often fly and travel over a much longer range. The first rule and flower constancy (i.e. third rule) can be written mathematically into a single equation (Yang 2012b):

$$\mathop x\nolimits_{i}^{t} = x_{i}^{t - 1} + \gamma L(\lambda )(x_{{_{*} }} - x_{i}^{t - 1} )$$
(26)

where \(x_{i}^{t}\) is the pollen i or solution vector xi at iteration t, \(x_{{_{*} }}\) is the current best solution (i.e. most fittest) found among all solutions at the current iteration and γ is a scaling factor to control the step size. The Lévy flight based step size L(λ) corresponds to strength of the pollination. Since insects may travel over a long distance with various distance steps, a Lévy flight can be used to mimic this characteristic efficiently. That is, L > 0 is drawn from a Lévy flight distribution.

For local pollination, the second rule and flower constancy can be written mathematically by a single equation:

$$\mathop x\nolimits_{i}^{t} = x_{i}^{t - 1} + \in (x_{j}^{t - 1} - x_{k}^{t - 1} )$$
(27)

where \(x_{j}^{t - 1}\) and \(x_{k}^{t - 1}\) are pollens from different flowers of the same plant species. This essentially mimics the flower constancy in a limited neighborhood. Mathematically, if \(x_{j}^{t}\) and \(x_{k}^{t}\) are selected from the same population, this become a local random walk if \(\in\) is drawn from a uniform distribution in [0,1]. Pollination may also occur in a flower from the neighboring flower than by the far away flowers. For this, a switch probability (i.e. fourth rule) or proximity probability p can be used to switch between global pollination and local pollination.

Like CSA, the author in Yang (2012b) already introduced the concept of Lévy flight distributions in FPA, so only mutation based on fitness value is added to simple FPA. The new algorithm so formed is named in this paper as Flower pollination algorithm with mutation (FPAM) which is summarized as pseudo-code shown in Fig. 7. The only difference in the pseudo-code for FPA and FPAM is only the addition of mutation (lines 19–24) in Fig. 7. If lines 19–24 are not used in Fig. 7 then it corresponds to the general pseudo-code for simple FPA.

Fig. 7
figure 7

General pseudo-code for FPAM

Full size image

4 Finding near-OGRs: problem formulation

Both simplicity and efficiency attracts researchers towards natural phenomenon to solve NP–complete and complex optimization problems. The first problem investigated in this research is to find Golomb rulers for unequal channel allocation. Second problem is to obtain either optimal or near-OGRs through nature-inspired metaheuristic algorithms by optimizing the ruler length so as to conserve the total occupied optical channel bandwidth.

If each individual element in an obtained set (i.e. non-negative integer location) is a Golomb ruler, the sum of all elements of an individual set forms the total occupied optical channel bandwidth. Thus if the spacing between any pair of channels in a Golomb ruler set G is denoted as \(CS\), an individual element is as \(IE\) and the total number of channels/marks is n, then the ruler length \(RL\) and the total optical channel bandwidth \(TBW\) are approximated by the following equations:

Ruler Length (RL):

$$RL = \sum\limits_{i = 1}^{n - 1} {\mathop {(CS)}\nolimits_{i} }$$
(28a)

subject to \((CS)_{i} \ne (CS)_{j}\)

Alternatively, Eq. (28a) can also be approximated as:

$$RL = IE(n) - IE(1)$$
(28b)

Total Bandwidth (TBW):

$$TBW = \sum\limits_{i = 1}^{n} {\mathop {(IE)}\nolimits_{i} } .$$
(29)

subject to \((IE)_{i} \ne (IE)_{j}\)

where \(i,j = 1,2, \ldots ,n\) with \(i \ne j\) are distinct in both Eqs. (28) and (29).

4.1 Nature-inspired algorithms to find near-OGRs

The general pseudo-code to find near-OGRs by using nature-inspired optimization algorithms proposed in this paper is shown in Fig. 8. The core of the proposed algorithms is lines 19–30 which find Golomb rulers for a number of iterations or until either an optimal or near–to–optimal solution is found. Also the size of the generated population must be equal at the end of iteration to the initial population size (Popsize). Since there are many solutions, a replacement strategy must be performed as shown in Fig. 8 to remove the worst individuals. This mean that the proposed algorithms maintain a fixed population of rulers and performs a fixed number of iterations until either an optimal or near–to–optimal solution is found.

Fig. 8
figure 8

General pseudo-code to find near-OGR sequences by using nature-inspired optimization algorithms

Full size image

5 Simulation results

This section presents the performance of proposed optimization algorithms and their performance comparison with best known OGRs (Bloom and Golomb 1977; Shearer 1990; Rankin 1993; Colannino 2003; Dollas et al. 1998; http://mathworld.wolfram.com/GolombRuler.html), two of the conventional computing algorithms i.e. EQC and SA (Kwong and Yang 1997; Randhawa et al. 2009) and three nature-inspired algorithms i.e. GAs (Bansal 2014), BBO (Bansal 2014) and simple BB–BC (Bansal and Sharma 2017), of finding unequal channel spacing. All the proposed algorithms to find near-OGRs have coded and tested in Matlab–R2017a language running under Windows 7, 64–bit operating system. The algorithms have been executed on Intel(R) core™ 2 Duo CPU T6600 @ 2.20 GHz processor Laptop with a RAM of 3 Gb and hard drive of 320 Gb.

5.1 Parameters selection for the proposed algorithms

To find either optimal or near-optimal solutions after a number of careful experimentation, following optimum parameter values of proposed algorithms have finally been settled as shown in Tables 1, 2, 3, 4 and 5. The selection of a suitable parameter values for nature-inspired algorithms are problem specific as there are no concrete rules.

Table 1 Simulation parameters for MBB–BC
Full size table
Table 2 Simulation parameters for FA and MFA
Full size table
Table 3 Simulation parameters for BA and MBA
Full size table
Table 4 Simulation parameters for CSA and CSAM
Full size table
Table 5 Simulation parameters for FPA and FPAM
Full size table

5.2 Near-OGR sequences

With the above mentioned parameters setting, the large numbers of sets of trials for various marks/channels were conducted. Each algorithm was executed 20 times until near-optimal solution was found. The generated near-OGRs for different marks by proposed metaheuristic algorithms are shown in “Appendix”. It has been verified that all the generated sequences are Golomb rulers. Although the proposed metaheuristic algorithms find same near-OGRs, but the difference is in required maximum number of iterations and computational time which is discussed in the following subsections.

5.3 Influence of selecting different population size on the performance of proposed algorithms

In this subsection, the influence of selecting different Popsize on the performance of proposed optimization algorithms for different values of channels is examined. The increased Popsize increases the diversity of potential solutions, and helps to explore the search space. But as the Popsize increase, the computation time required to get either the optimal or near-optimal solutions increase slightly as the diversity of possible solutions increase. But after some limit, it is not useful to increase Popsize, because it does not help in solving the problem faster. The choice of the best Popsize for nature-inspired optimization algorithms depends on the type of the problem (Bansal 2019).

Golomb rulers realized from 10- to 16-marks by TS (Cotta et al. 2006), maximum Popsize set was 190. The hybrid approach proposed in (Ayari et al. 2010) to find Golomb rulers from 11- to 23-marks, the Popsize was set between 20 and 2000. The near-OGRs found by the HE algorithms (Dotú and Hentenryck 2005), maximum Popsize set was 50. For the algorithms GAs and BBO (Bansal 2014), to find near-OGRs, maximum Popsize set was 30.

With the above mentioned parameter settings, the experiment with Popsize varying from 10 to 100 for all the proposed metaheuristic algorithms was performed. It was noted that Popsize has little significant effect on the performance of all proposed metaheuristic algorithms. By carefully looking at the results, the Popsize of 10 in all proposed algorithms was found to be adequate for finding near-OGRs.

5.4 Influence of increasing iterations on total optical channel bandwidth

The choice of the best maximum iteration for metaheuristic algorithms is always critical for specific problems. Increasing the numbers of iteration, will increase the possibility of reaching optimal solutions and promoting the exploitation of the search space so as to obtain the global optimization abilities of the metaheuristic algorithms. This will maintain a better population diversity and the global search ability is improved, which efficiently improves the accuracy and efficiency of the metaheuristic algorithms. This is because after a number of iteration, it is necessary to search from a different path so as to get improved solutions. The algorithm effectively jumps out of the local optimal value and continues to optimize. This means, the chance to find the correct search direction increases considerably.

In this subsection the influence of increasing the number of iterations on proposed algorithms with the same parameter settings as mentioned above subsections is examined. By increasing the number of iterations, the total optical channel bandwidth tends to decrease; it means that the rulers reach their optimal or near-optimal values after certain iterations. This is the point where no further improvement is seen. Figure 9 illustrates the influence of increasing iterations on the performance of proposed algorithms for various channels. It is noted that the iterations have little effect for low value marks. But for higher order marks, the iterations have a great effect on the total optical channel bandwidth i.e. total optical bandwidth gets optimized after a certain numbers of iterations.

Fig. 9
figure 9

Influence of iterations on TBW for a BB-BCM; b LBB-BC; c LBB-BCM; d FA; e FAM; f LFA; g LFAM; h BA; i BAM; j LBA; k LBAM; l CSA; m CSAM; n FPA; and o FPAM for various channels

Full size image

In literatures (Cotta et al. 2006) and (Ayari et al. 2010), the maximum numbers of iterations (Maxiter) for TS algorithm to find Golomb rulers were set to 10000 and 30000 respectively. The hybrid approach proposed in (Ayari et al. 2010) to find Golomb rulers the maximum number of iterations set were 100000. In (Bansal 2014), it was noted that to find near-OGRs, hybrid evolutionary algorithms (Dotú and Hentenryck 2005) get stabilized in and around 10000 iterations, while GAs and BBO algorithms stabilized in and around 5000 iterations. By carefully looking at the results, it is concluded that all the proposed optimization algorithms in this paper to find either optimal or near-OGRs stabilized in or around 1000 iterations. To find n-channel near-OGRs, the value of Maxiter parameter during the simulations was selected to 50 times the number of channel (n), i.e. \(Maxiter = 50 \times n\). In summary, the FPAM algorithm shows stronger optimization performance and higher optimization efficiency and faster convergence rate than the other algorithms.

5.5 Performance comparison of proposed algorithms with previous existing algorithms in terms of ruler length and total optical channel bandwidth

Table 6 enlists the ruler length and total occupied channel bandwidth by different sequences obtained from the proposed algorithms after 20 executions and their performance comparison with best known OGRs (best solutions), EQC, SA, GAs, BBO and simple BB–BC. According to (Kwong and Yang 1997), the applications of EQC and SA is restricted to prime powers only, so the ruler length and total occupied channel bandwidth for EQC and SA are presented by a dash line in Table 6. Comparing the experimental results obtained from the proposed algorithms with best known OGRs and existing algorithms, it is noted that there is a significant improvement in the ruler length and thus the total occupied channel bandwidth that is, the results gets better.

Table 6 Performance comparison of proposed nature-inspired metaheuristic algorithms to channel allocation
Full size table

From Table 6, it is also observed that simulation results are particularly impressive. First observe that for all the proposed algorithms, the ruler length obtained up to 13-marks is same as that of best known OGRs and the total optical channel bandwidth occupied for marks 5 to 9 and 11 is smaller than the best known OGRs, while all the other rulers obtained are either optimal or near-optimal. Second observe that the algorithms BB–BCM and LBB–BC do not find best known rulers after 7-marks, but finds near-optimal rulers for 8- to 20-marks. Algorithm LBB–BCM can find best optimal rulers up to 8-marks, but finds near-optimal rulers after 8-marks. FA can find best rulers for up to 11-marks. Algorithms FAM and LFA can find best rulers for up to 12-marks and near-optimal rulers after 12-marks. By combining algorithms FAM and LFA into a single algorithm named LFAM, best OGRs up to 16-marks and near-optimal rulers for 17- to 20-marks can be find efficiently. BA, BAM and LBA can find best rulers up to 17-marks and near-optimal rulers for 18- to 20-marks. The algorithms LBAM, CSA, CSAM, FPA and FPAM can find best rulers up to 20-marks very efficiently and effectively in a reasonable computational time.

From simulation results, it is concluded that modified forms of the proposed algorithms to find near-OGRs, slightly outperforms the algorithms presented in their simplified forms. As illustrated in Table 6 for higher order marks, the algorithms CSA, FPA, BA and their modified forms outperforms the other algorithms in terms of both the ruler length and total occupied channel bandwidth. Figure 10 shows the graphical representation of Table 6.

Fig. 10
figure 10

Comparison of proposed algorithms in terms of a RL and b TBW with the other existing algorithms

Full size image

5.6 Performance comparison of proposed algorithms in terms of computational time

Finding Golomb rulers is an extremely challenging optimization problem. The OGRs generation by exhaustive parallel search algorithms for higher order marks is computationally very time consuming, which took several hours, months, even years of calculation on the network of several thousand computers (Shearer 1998; Rankin 1993; Dollas et al. 1998; http://www.distributed.net/ogr). For example, rulers with 20- to 26-marks were found by distributed OGR project (http://www.distributed.net/ogr) which took several years of calculations on many computers to prove the optimality of the rulers.

This subsection is devoted to report the experimental average CPU time taken to find either optimal or near-OGRs by the proposed algorithms and their comparison with the computation time taken by existing algorithms (Shearer 1990; Rankin 1993; Soliday et al. 1995; Ayari et al. 2010; Bansal 2014, 2017; Bansal and Sharma 2017; Dollas et al. 1998; http://www.distributed.net/ogr). Figure 11 illustrates the average CPU time taken by proposed metaheuristic algorithms to find near-OGRs up to 20-marks. In (Soliday et al. 1995), it is identified that to find Golomb rulers from heuristic based exhaustive search algorithm, the times varied from 0.035 s to 6 weeks for 5- to 13-marks ruler, whereas by non-heuristic exhaustive search algorithms took approximately 12.57 min for 10-marks, 2.28 years for 12-marks, 2.07 × 104 years for 14-marks, 3.92 × 109 years for 16-marks, 1.61 × 1015 years for 18-marks and 9.36 × 1020 years for 20-marks ruler. In (Ayari et al. 2010), it is reported that CPU time taken by TS algorithm to find OGRs is around 0.1 s for 5-marks, 720 s for 10-marks, 960 s for 11-marks, 1913s for 12-marks and 2516 s (around 41 min) for 13-marks. The OGRs realized by HGA (Ayari et al. 2010) took around 5 h for 11-marks, 8 h for 12-marks, and 11 h for 13-marks. The OGRs realized by the exhaustive search algorithms in (Shearer 1990) for 14- and 16-marks, took nearly one hour and hundred hours respectively, while 17-, 18- and 19-marks OGRs realized in (Rankin 1993) and (Dollas et al. 1998), took around 1440, 8600 and 36200 CPU hours (nearly seven months) respectively on a Sun Sparc Classic workstation. Also, the near-OGRs realized up to 20-marks by algorithms GAs and BBO (Bansal 2014), the maximum execution time was approximately 31 h i.e. nearly 1.3 days, while for BB–BC (Bansal and Sharma 2017) the maximum execution time was around 28 h i.e. almost 1.1 days.

Fig. 11
figure 11

Comparison of average CPU time taken by proposed algorithms for various channels

Full size image

It is noted that for proposed algorithms, the average CPU time varied from 0.000 s for 3-marks ruler to approximately 27 h for 20-marks ruler. The maximum and minimum execution time taken by the proposed algorithms for 20-marks ruler is about 27 and 19 h, respectively. By introducing the concept of mutation and

Lévy flight strategies with the proposed algorithms, the minimum execution time is reduced to approximately 18 h i.e. less than one day. This represents the improvement achieved by the use of proposed optimization algorithms and their modified forms to find near-OGRs. From Fig. 11, it is further observed that algorithm FPAM outperforms the other algorithms in terms of computational time.

5.7 Maximum computation complexity of proposed algorithms in terms of big O notation

The nature-inspired metaheuristic algorithms are stochastic process that execute randomly operations. For this reason, it is not practical to conduct a complexity analysis from a deterministic point of view. However, it is possible to have an idea of this complexity through the mathematical notation called Big O notation.

To find the optimal solutions, the proposed metaheuristic algorithms have an initialization stage and a subsequent stage of iterations. The computational complexity of nature-inspired algorithm depends upon n, Popsize and Maxiter:

$${\text{Computation}}\,{\text{complexity}} = {\text{O}}\left( {n \times Popsize \times Maxiter} \right)$$
(30)

For all the proposed metaheuristic algorithms, the maximum computational complexity in terms of Big O notation is

$${\text{Computation}}\,{\text{complexity}} = {\text{O}}\left( {n \times 10 \times 50 \times n} \right) = {\text{O}}\left( {500n^{2} } \right)$$
(31)

Thus the computational complexity for all the proposed metaheuristic algorithms is directly proportional to the square of the input mark/channel value.

5.8 Wilcoxon rank-sum test of proposed algorithms

In order to validate the proposed algorithms, the non-parametric statistical analysis with 5% significance level is conducted to analyze and rank the algorithms. With the non-parametric statistical analysis, we can make sure that the results are not caused by chance (Li et al. 2019). The Wilcoxon rank-sum statistical analysis (García et al. 2009) is performed on RL, TBW and CPU time. The Wilcoxon statistical comparison analysis between FPAM and other algorithms are listed in Table 7. Since the algorithms BA, CSA, FPA and their improved forms find same near-OGR sequences at different computational time so the RL and TBW p value is shown by a dash line in Table 7. In this experiment p value < 0.05 and h = 1 indicate that the difference between the two data is significant.

Table 7 Comparison of Wilcoxon rank-sum analysis for FPAM and other algorithms
Full size table

6 Conclusions and future scope

In this paper, WDM channel allocation algorithm by considering the concept of OGRs is presented. Finding OGRs through conventional computing algorithms is computationally hard problem because as the number of marks increases, the search for OGRs rises exponentially. The aim to use metaheuristic algorithms is not necessarily to produce perfect solutions, but to produce the near–to–optimal solutions under the given constraints. Even if exact algorithms are able to find optimal/near-OGRs, they remain unpractical in terms of computational time. This paper presented the application of five nature-inspired metaheuristic algorithms (BB–BC, FA, BA, CSA and FPA) to solve near-OGRs problem. The main technical contribution of this paper was to modify the nature-inspired metaheuristic algorithms by applying mutation and Lévy flight strategies. The proposed algorithms have been validated and compared with other existing algorithms to find near-OGRs. It has been observed that modified forms finds near-OGRs very efficiently and effectively than their simplified forms. The enumerated near-OGRs were compared with those enumerated through existing conventional and nature-inspired algorithms in terms of iterations, ruler length, total optical channel bandwidth and computational time. Simulations and comparison show that the proposed algorithms are superior to the existing algorithms. From preliminary results it is also concluded that for large order marks, MFA outperforms FA and MBB–BC, MBA outperforms MFA and BA, CSAM outperforms MBA and CSA, while FPAM is slightly outperforms CSAM and FPA in terms of ruler length, total channel bandwidth, experimental computation time and maximum number of iterations needed to find near-OGRs. The results obtained from simulation experiment and Wilcoxon rank-sum analysis show that the proposed FPAM is potentially more superior in terms of exploitation and exploration abilities, success rate and convergence speed compared with the other algorithms in solving such a NP–complete problem.

To date, none of the researchers show the implementation of their algorithm in real optical WDM systems in order to see the complexity of realizing the unequal channel spacing. Although numerous algorithms have been suggested for finding near-OGRs, yet there is no uniformly accepted formulation. So, in order for these algorithms to be of practical use, it is desired that the performance of these algorithms for higher order OGRs up to about several thousand channels may be evaluated and may be used to provide unequal channel spacing in real WDM system. Though this process will be very time consuming yet this needs be done for this work to be of some use in the field of communication engineering.