Nature–inspired metaheuristic algorithms to find near–OGR sequences for WDM channel allocation and their performance comparison

2.1 Algebraic Properties of Golomb Rulers

The simple algebraic properties that find new Golomb ruler set G′ are the translation property, the multiplication property, linearity property, and the mirror image or reflection property [39, 40, 47].

2.2 Perfect Golomb Ruler

A perfect Golomb ruler measures all the positive integer distances from 1 to ruler length RL [20, 27].

2.3 Optimal Golomb Rulers (OGRs)

Since perfect Golomb rulers for n > 4 cannot exist, the higher mark rulers are stated in terms of whether or not they are optimal. So, an optimal Golomb ruler (OGR) is the shortest length ruler for a given number of marks [48, 49].

Definition (Optimal Golomb ruler)

An n–marks Golomb ruler set G = {0, x₂, ...,x_n-1,x_n} is referred to as optimal if it is of shortest possible length.

There can be multiple different OGRs for a specific number of marks. However, the unique optimal 4-marks Golomb ruler is shown in Figure 1. In a case where a Golomb ruler is not optimal, but its length is near to optimal, it will be considered as a near or non–optimal Golomb ruler. For example, the set G = {0,1,3,7} is a 4-marks near–OGR since its differences are {1 = 1 - 0; 2 = 3 - 1; 3 = 3 - 0; 4 = 7 - 3; 6 = 7 - 1; 7 = 7 - 0}, all of which are distinct. It is clear from the differences that the integer number 5 is absent so it cannot be designated as a perfect Golomb ruler. An n–marks Golomb ruler is said to be an optimal Golomb ruler if and only if, [30]

1. there is no other n–marks Golomb ruler with the smaller ruler length, and

2. the ruler is in canonical form as the smaller of the equivalent rulers {0, x₂, ...,x_n-1,x_n} and {0,..., x_n -x₂, x_n}. This smaller means that the difference distance between the first two marks in the ruler set is less than the corresponding distance in the equivalent ruler.

For example the set G = {0,1,3,7,12,20}, shown in Figure 2 is a non–optimal 6-marks Golomb ruler having ruler length 20. From the differences it is clear that the numbers 10,14,15,16,18 are missing, so it is not a perfect Golomb ruler sequence. The distance associated between each pair of marks is also shown in Figure 2.

Figure 2

A 6-marks non–OGR with its associated distances

The OGRs play an important role in a variety of real–world applications including radio frequency allocation, sensor placement in X–ray crystallography, computer communication network, pulse phase modulation, circuit layout, geographical mapping, self–orthogonal codes, VLSI architecture, 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 [7, 17, 25, 27, 41, 42, 50-56].

Although the definition of Golomb rulers does not place any limitation on the ruler length, researchers are usually interested in rulers with smallest length, i.e. to find the n–marks OGR, the function G(n) is given by:

(2.25) G ( n ) = min { R L ( G ) : G is Golomb ruler set , | G | = n }

So far the exact values of OGRs G(n) for up to n = 27 are known and there are some prospects for OGRs up to 158–marks [57, 58]. Firstly, the idea of Golomb rulers up to 10–marks were studied by W. C. Babcock [7], while analyzing the position of radio channels in the frequency spectrum. According to the literatures [40–42], all of rulers’ up to 8–marks introduced by Babcock are optimal; the 9 and 10–marks are near–to–optimal. A. Dimitromanolakis [41] computationally estimated and proved a detailed discussion of OGRs for every integer n that

(2.26) G ( n ) ≤ n 2 , ∀ n ≤ 65000

As there are n 2 − n 2 distinct non–negative differences between any two marks, so the ruler length is at least the same as given by equation 2.24. The computer searches give the largest known value of G(n). The 27-marks OGR has an optimal ruler length of 553 i.e. from the equation 2.25, G(27) = 553 which satisfies the equation 2.26 as well. The search for OGRs and to prove its optimality took several months or even years. The optimal Golomb rulers for 5 to 7-marks were found by J. P. Robinson et. al. [51] and for 8 to 11-marks by W. Mixon. The OGRs with 12 and 13-marks were found by J. P. Robinson [21], those from 14 to 17-marks were found by J. B. Shearer [22] by exhaustive computer search. According to [41, 57, 58], the rulers for 17 and 18-marks were proved to be optimal by O. Silbert, while 19-marks OGR was found by W. T. Rankin [25] computer search approach. The search for OGRs for 20 to 27-marks was completed by distributed.net [43] OGR project. Distributed.net is now actively searching the OGRs for n > 27.

3.1 Bat Algorithm and its Modified forms

X. S. Yang [61-65, 72, 73], inspired by the echolocation characteristics of microbats, introduced an optimization algorithm called Bat algorithm (BA). In describing this new algorithm, the author in [73] uses the following three idealized rules:

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

2. Bats fly randomly with a velocity v_i at position x_i, with a fixed frequency range [f_min, f_max], fixed wavelength range [λ_min, λ_max], varying its pulse emission rate r ∈ [0,1], and loudness A⁰ to hunt for prey, depending on the proximity of their target;

3. Although the loudness can vary in different ways, it is assumed that the loudness varies from a minimum constant (positive) A_min to a large A⁰.

In BA, each bat has its position x_i, velocity v_i, frequency f_i, loudness A_i, and the emission pulse rate r_i 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 v i t and solutions x i t at step t are given by the following equations [61, 62, 73-76]:

where β ∈ [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:

where x_best = x_∗, ε ∈[-1,1] is a scaling factor and A^t is loudness. Further the loudness A and pulse rate r are updated according to the equations 3.8 and 3.9 respectively as the iterations proceed:

where α and γ are constants and for simplicity, α = γ is chosen. For most of the simulation α = γ = 0.9 is used [73-76].

By combining the characteristics of mutation strategy (equations 3.1 and 3.2), Lévy flights distribution (equation 3.3), 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 equation 3.7 is given by:

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

Figure 3

The general pseudo–code for MBA

3.2 Cuckoo Search Algorithm and its Modified form

X. S. Yang et al. [77-80], inspired by brood parasitism of some cuckoo species, developed a novel nature–inspired metaheuristic optimization algorithm called a Cuckoo search algorithm (CSA). In addition, CSA algorithm is enhanced by the Lévy flight trajectory of some birds, rather than by simple random walks. For describing this new algorithm, X. S. Yang et al. use the following three idealized rules:

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

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

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 p_a 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 [77]:

where α > 0 is the step size, which should be related to the scale of the specified problem.

As the authors in [77], already introduced the Lévy flights distribution concept to enhance the performance, so only mutation strategy is applied to the simple CSA to explore the search space. The new modified algorithm so formulated is named as a Cuckoo search algorithm with mutation (CSAM). The basic steps of CSAM can be summarized as the pseudo–code shown in Figure 4. If the concept of mutation (lines 9 to 14) is withdrawn from Figure 4, then it corresponds to the pseudo–code for simple CSA.

Figure 4

The general pseudo–code for CSAM.

3.3 Flower Pollination Algorithm and its Modified form

X. S. Yang et. al [71, 81, 82], inspired by the flow pollination process of flowering plants, introduced a novel nature–inspired optimization algorithm called Flower pollination algorithm (FPA). For describing this novel metaheuristic algorithm, the authors in [71] use the following four idealized rules:

1. For global pollination process, biotic cross–pollination is used and pollen–carrying pollinators obey Lévy flight movements;

2. For local pollination, abiotic and self–pollination are used;

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. The interaction of local pollination and global pollination can be controlled by a switch probability p ∈ [0,1], with a slight bias towards local polination.

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 as [71]:

where x i t is the pollen i or solution vector x_i 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 the 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 [71]:

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 ∈ 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 [71] already introduced the concept of Lévy flight distributions in FPA, so only mutation based on the fitness value (equations 3.1 and 3.2) is added to simple FPA. The new algorithm so formed is named in this paper as a Flower pollination algorithm with mutation (FPAM) which is summarized as pseudo–code shown in Figure 5. The only difference in the pseudo–code for FPA and FPAM is only the addition of mutation (lines 19 to 24) in Figure 5. If lines 19 to 24 are not used in Figure 5 then it corresponds to the pseudo–code for simple FPA.

Figure 5

The general pseudo–code for FPAM

4.1 Nature–Inspired Algorithms to Find Near–OGRs

The general pseudo–code to find near–OGR sequences as WDM channel allocation by using nature–inspired optimization algorithms proposed in this paper is shown in Figure 6. The core of the proposed nature–inspired algorithms are lines 20 to 31 which find Golomb ruler sequences 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 Figure 6 to remove the worst individuals. This means 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.

Figure 6

The general pseudo–code to find near–OGRs as WDM channel allocation by using nature–inspired optimization algorithms

5.1 Simulation 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 nature–inspired algorithms have finally been settled as shown in Tables 1 to 3. The selection of a suitable parameter values of nature– inspired algorithms are problem specific as there are no concrete rules.

For BA, CSA, FPA, and their modified forms all the parameter values were varied from 0.0 to 1.0. By looking precisely at the obtained results, it was noted that A = 0.8, r = 0.5, p_m = 0.01 are the best choices for BA and MBA (Table 1), α = 0.01, p_a = 0.5, p_m = 0.05 are the best choices for CSA and CSAM (Table 2), and γ = 1.0, p = 0.8, p_m = 0.01 are the best choices for FPA and FPAM (Table 3) to find near–OGRs.

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 25 times until near–optimal solution was found. A set of 10 trials with n = 6, 8 and 15 for the proposed nature–inspired algorithms are reported in Tables 4 and 5. The performance of all the sets is nearly the same as reported in Tables 4 and 5. The generated near–OGR sequences for different values of marks verify that they are Golomb rulers. Although the proposed algorithms find same near–OGR sequences, the difference is in a required maximum number of iterations, computational time, and computational complexities as 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 the different population size (Popsize) on the performance of proposed nature–inspired 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 [84]. Table 6 shows the influence of Popsize on the performance of the proposed algorithms to find near–OGRs for 7,9 and 14-marks. In this experiment, all the parameter settings for proposed nature–inspired algorithms are the same as mentioned in Tables 1 to 3.

Golomb ruler sequences realized from 10 to 16-marks by Tabu search algorithm [26], the maximum Popsize was set to 190. In the hybrid approach proposed in [29] to find Golomb rulers from 11 to 23-marks, the Popsize was set between 20 and 2000. The near–OGR sequences found by algorithms GAs and BBO [30], maximum Popsize was 30. The BB–BC algorithm proposed in [33, 34] finds near–OGRs upto 11-marks with a maximum Popsize of 10. For the hybrid evolutionary (HE) algorithms [39], to find near–OGRs, maximum Popsize was 50.

From Table 6, it is noted that Popsize has little effect on the performance of all proposed nature–inspired optimization algorithms. By carefully looking at the results, the Popsize of 10 in all proposed algorithms was found to be adequate for finding near–OGR sequences.

5.4 Influence of Increasing Iterations on Total Optical Channel Bandwidth

The choice of the best maximum iteration (Maxiter) for nature–inspired 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. This means, the chance to find the correct search direction increases considerably.

Here, all the parameter values for proposed nature–inspired algorithms are the same as mentioned in above subsections. By increasing the number of iterations, the total optical channel bandwidth tends to decrease; it means that the rulers reach their optimal or near–to-optimal values after certain iterations. This is the point where no further improvement is seen. Tables 7 and 8 illustrate 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 (such as n = 7 and 8). 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 number of iterations.

In the literatures [26,29], the Maxiter for Tabu search algorithm to find Golomb ruler sequences were set to 10000 and 30000, respectively. For the hybrid approach proposed in [29] to find Golomb ruler sequences the maximum number of iterations set were 100000. In [30], it was noted that to find near–OGRs, GAs and BBO algorithms stabilized in and around 5000 iterations, while hybrid evolutionary algorithms [39] were stabilized in and around 10000 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–optimal Golomb rulers, stabilized at or around 1000 iterations.

5.5 Performance Comparison of Proposed Algorithms with Previous Existing Algorithms in Terms of Ruler Length and Total Optical Channel Bandwidth

Table 9 enlists the ruler length and total occupied channel bandwidth by different sequences obtained from the proposed nature–inspired algorithms after 25 executions and their performance compared with best known OGRs (best solutions), EQC, SA, GAs, BBO and BB–BC. According to [1], 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 9. 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 become improved.

From Table 9, it is also observed that simulation results are particularly impressive. First, observe that the algorithms 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 the simulation results, it is concluded that modified forms of the proposed nature–inspired algorithms to find either optimal or near–OGRs slightly outperform the algorithms presented in their simplified forms. As illustrated in Table 9 for higher order marks, the proposed algorithms outperform the other existing algorithms in terms of both the ruler length and total occupied channel bandwidth.

5.6 Performance Comparison of Proposed Algorithms in Terms of Computational Time

Finding Golomb ruler sequences 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 [19, 25, 42, 43, 57,58]. For example, rulers with 20 to 27-marks were found by distributed OGR project [43] 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–optimal Golomb rulers by the proposed algorithms and their comparison with the computation time taken by existing algorithms [22, 25, 27, 29, 30, 33-36, 42, 43]. Table 10 reports the average CPU time taken by proposed algorithms to find near–OGRs up to 20-marks. The experimental CPU time taken by BB–BC algorithm to find near–OGRs is not reported in [33]. Then, using the same parameter values as mentioned in [33], algorithm BB–BC to find near–OGRs was executed to obtain the average computational CPU time. Figure 7 illustrates the graphical representation of the Table 10.

Figure 7

Performance comparison of proposed algorithms in terms of computational time