1 Introduction

The use of web based applications has resulted in rapid increase of internet traffic [1]. Efficient utilization of network resources, such as network bandwidth, is essential to deal with this high volume of traffic. The main objective of network traffic engineering is efficient mapping of traffic on the available network resources to prevent traffic imbalance, if it exists [2].

Routers serve as the main interconnection points of the internet and forward data packets between source and destination nodes via multiple paths. These paths exist between a given source and destination pair. The internet is huge and very complex and is divided into autonomous systems (AS) for managing its complexity. An AS represents a collection of networks under the control of one single entity or organization with a specific routing policy. These policies are determined by a class of routing protocols, namely, interior gateway protocols (IGPs) [3]. Routing across ASs is performed by another class of protocols, namely, exterior gateway protocols (EGPs) [3].

Open shortest path first (OSPF) [3] is an IGP and has received notable attention by researchers for efficient traffic engineering since OSPF is considered the best backbone routing protocol used in the internet [4, 5]. The protocol has shown remarkable performance through significant reduction in maximum utilization over pure shortest path routing [6]. OSPF is based on Dijkstra’s algorithm [7], which determines a shortest path between a source and destination pair. Each link in the network is given a measurable entity called a link weight or OSPF weight. The cost of a path between a given source and destination pair is found by the summation of OSPF weights on the links in that path. The path with minimal cost is labelled as the shortest path.

This paper considers the open shortest path first weight setting (OSPFWS) problem, classified as an NP-hard problem [8]. The OSPFWS problem requires a set of weights to be determined, so as to efficiently utilize network resources. The objectives of this problem are to minimize maximum utilization, minimize the number of congested links, and to minimize the number of unused links. These objectives conflict with each other, i.e. if one objective is improved, at least one of the other objectives may deteriorate. To address this NP-hard problem with conflicting objectives, this paper proposes to apply a fuzzy particle swarm optimization (FPSO) algorithm. The paper also proposes a hybrid PSO, namely, fuzzy evolutionary PSO, where characteristics of simulated evolution algorithm [9] are combined with the fuzzy PSO. The performance of these two variants is empirically assessed and compared.

The rest of the paper is organized as follows: Section 2 provides the necessary background and related work on the OSPFWS problem. Section 3 provides the formal definition of the OSPFWS problem. A brief discussion on fuzzy logic and the Unified And-OR operator is given in Section 4. Section 5 describes the formulation of a fuzzy logic based objective function for the OSPFWS problem. Section 6 presents the proposed fuzzy PSO algorithm, and a variant of the fuzzy PSO, the fuzzy evolutionary PSO, is proposed and discussed in Section 7. The experimental methodology is described in Section 8. Results are provided and discussed in Section 9. A comparative analysis of the fuzzy evolutionary PSO with other algorithms, namely, Pareto-dominance PSO, weighted aggregation PSO, NSGA-II, simulated evolution, and simulated annealing is provided in Section 10. The paper is concluded in Section 11. Finally, the symbols and terminology used in this paper are given in Appendix A. Some additional results related to the analysis of swarm size (discussed in Section 9) are provided in Appendix B.

2 Literature review

Notable research in optimizing OSPF weights has been reported in the literature [2, 4, 6, 10–28]. The pioneering work on the OPSF weight setting problem was done by Fortz and Thorup [8, 10, 29] who used maximum utilization as the optimization objective. The term “maximum utilization” refers to the maximum of all utilization values over all the links in the network. A cost function based on utilization ranges was first formulated by Fortz and Thorup [2], who applied tabu search [30] to minimize “maximum utilization”.

The cost function of Fortz and Thorup was formally defined as

$$ minimize \hspace{0.5cm} {\Phi} = \underset{a\in A}{\sum}{\Phi}_{a}(l_{a}) $$
(1)

subject to the constraints:

$$ l_{a} = \underset{(s,t) \in N \times N }{\sum} f_{a}^{(s,t)}~a\in A, $$
(2)
$$ f_{a}^{(s,t)} \geq 0 $$
(3)

where Φ is the cost function, Φ a is the cost associated with arc a, l a is the total traffic load on arc a, \(f^{(s,t)}_{a}\) represents traffic flow from node s to t over arc a, N defines the set of nodes, and A represents the set of arcs. Equation (2) indicates that the total load (traffic) on arc a is equal to the sum of the traffic load on arc a and the traffic load on all incoming arcs to arc a. The constraint in (3) implies that the traffic flow from node s to t over arc a can be greater than or equal to zero.

In (1), Φ a represents piecewise linear functions, with Φ a (0)=0 and a derivative, \( {\Phi }_{a}^{\prime }(l_{a})\) given by

$$ {\Phi}_{a}^{\prime}(l) = \left\{ \begin{array}{ll} 1 & \text{for }0 \leq l/c_{a}<1/3, \\ 3 & \text{for }1/3 \leq l/c_{a}<2/3, \\ 10 & \text{for }2/3 \leq l/c_{a}<9/10, \\ 70 & \text{for }9/10 \leq l/c_{a}<1, \\ 500 & \text{for }1 \leq l/c_{a}<11/10, \\ 5000 & \text{for }11/10 \leq l/c_{a}< infinity \\ \end{array} \right. $$
(4)

The above function indicates that the utilization (which represents the load to capacity ratio) of a link is acceptable within 100 % of the link’s capacity. According to the function in (4), links with utilization levels less than or equal to 1 (or 100 %) have a low cost, proportional to the level of utilization. These values are 1, 3, 10, or 70. Furthermore, links exceeding 100 % utilization are assigned high costs of 500 and 5000. For example, if utilization is less than one third of a link’s capacity, then a cost of 1 is assigned. For utilization between 1/3 and 2/3 of a link’s capacity, a cost of 3 is assigned, and so on. On the other hand, if the utilization of a link is beyond 1 (which indicates that the number of incoming packets to a link exceed the maximum capacity of the link) then such an over-utilization is not desirable, since it will result in packet loss. Therefore, the cost assigned to the links beyond 100 % utilization is much higher (i.e. 500 for utilization of equal to or more than 100 % but less than 110 %, and 5000 for more than 110 %). Note that as per (4), a link with utilization greater than 100 % and less than 110 % is still preferable compared to a link with utilization greater than 110 %. Fortz and Thorup employed a dynamic shortest path algorithm [31–33] to obtain multiple equidistant shortest paths between a source-destination pair. By this mechanism, traffic load was distributed equally across the links.

Subsequent to the work of Fortz and Thorup, many other researchers attempted to solve the OSPF weight setting problem with different algorithms and different objective functions. Ramakrishnan and Rodrigues [12] proposed a local search procedure using the same cost function as that of Fortz and Thorup. The main difference between the two approaches was that for a heavily used link, Rodrigues and Ramakrishnan’s technique increases the link metric (i.e. the OSPF weight assigned to a link). Ericsson et al. [13] developed a genetic algorithm [34] to solve the OSPFWS problem also using the cost function by Fortz and Thorup. Kandula et al. [6] compared the performance of three OSPF weight optimizers while considering maximum link utilization as the optimization objective. Bhagat [4] also assumed link utilization as weights and used a genetic algorithm for OSPF weight setting while using the cost model of Fortz and Thorup with a minor modification. Abo Ghazala et al. [35] performed a survey of various algorithms applied to the OSPFWS problem, and also proposed a technique based on iterative local search, while considering link utilization as the optimization objective. The underlying cost function was the same as proposed by Fortz and Thorup. In a subsequent research article, Aboghazala et al. [15] assumed maximization of unused bandwidth as the optimization objective and employed simulated annealing and hybrid genetic algorithms for weight optimization. Parmar et al. [16] formulated the OSPF weight setting problem as mixed-integer linear programming problem and developed a branch-and-cut algorithm while assuming minimization of network congestion as the optimization objective. Pioro et al. [22] considered the maximum load on any link in the network as the measure of congestion and proposed two heuristic approaches for weight setting. Srivastava et al. [17] also considered minimization of maximum load on any link and proposed heuristic algorithms based on Lagrangian relaxation to determine feasible solutions for the weight setting problem. Buriol et al. [18] extended the genetic algorithm proposed in [13] to a memetic algorithm by adding a local search procedure while using the same cost function as that of Fortz and Thorup. Bley [19, 20] proposed unsplittable shortest path routing (UPSR) and claimed that the proposed approach can be applied to other routing schemes such as OSPF, while considering minimization of maximum congestion over all arcs. Zagozdzon et al. [14] proposed a two-phase algorithm for resolving the OSPF weight setting problem while considering the residual capacity as the optimization objective. This residual capacity resulted from setting the link weights proportional to the inverse of their capacity. Reis et al. [36] proposed a memetic algorithm for weight setting in OSPF and DEFT algorithms while considering minimization of total link utilization. Lin and Gen [21] proposed a priority-based genetic algorithm for shortest path routing in OSPF. Their results indicated that the proposed GA could be used for weight setting in OSPF and other routing algorithms. Retvari et al. [23, 24] studied the OSPF weight setting problem considering maximization of network throughput and proposed some algorithms that could efficiently optimize the link weights. Nucci et al. [25] proposed a Tabu-search heuristic for choosing link weights that takes into account both service level agreement (SLA) requirements and link failures with the objective of optimization link utilizations. Shirmali et al. [26] devised an approach based on Nash bargaining and decomposition. It was claimed that the proposed approach could be easily modified to yield a mechanism for setting link weights for ISPs using OSPF in a way similar to that of Fortz and Thorup. Riedl [27] presented an algorithm based on simulated annealing to optimize link metrics in OSPF networks. The algorithm took into account the original routing configuration and allowed tradeoff considerations between routing optimality and adaptation impact. Lee et al. [28] modelled the optimal link weight assignment problem as an integer linear programming problem while considering minimization of sum of energy consumption of all links.

It is noteworthy of mentioning that, generally, the aforementioned approaches considered a single objective in the optimization process. For example, the cost function proposed by Fortz and Thorup (1) on which many subsequent attempts were based [4, 12, 13, 18, 26, 35, 37] considered minimization of maximum link utilization. Other researchers [6, 17, 22] also assumed minimization of maximum link utilization. Other objectives considered in the optimization process were maximization of unused link bandwidth [15], minimization of network congestion [16, 19, 20], residual capacity of link [14], minimization of total link utilization [36], maximization of network throughput [23, 24], and minimization of sum of energy consumption of all links [28]. Exceptions from these single-objectives optimization approaches were Nucci et al. [25] where link failure and link no-failure states were used as the optimization objectives, and Sqalli et al. [11, 38] who used minimization of maximum link utilization as well as minimization of congested links as the optimization objectives while using a simulated annealing (SA) algorithm [39].

A cost function developed by Sqalli et al. [11, 38] evolved from the earlier work by Fortz and Thorup. The reason for using the cost function of Fortz and Thorup was that the function was employed in many studies as mentioned above. One novel aspect of the work of Sqalli et al. was the addition of another optimization objective (i.e. minimization of congested link) on top of minimization of maximum link utilization. This resulted in better distribution of traffic in the network since this is one fundamental requirement of network traffic engineering. The function employed by Sqalli et al. is defined as

$$\begin{array}{@{}rcl@{}} {\Phi} = MU + \frac{{\sum}_{a \in SetCA}~{(l_{a}-c_{a})}}{E} \end{array} $$
(5)

where MU is the maximum utilization of the network. S e t C A defines the set of congested links, E represents the total number of links in the network, c a refers to the capacity of link a, and l a is the total traffic on link a.

The second term of (5) after the plus sign defines the extra load on the network. This extra load is found by taking all the congested links, divided by the total number of links present in the network to normalize the entire function. For an uncongested network, the term after the plus sign results in a zero. Thus, (5) results in minimization of maximum utilization provided that there is no congestion in the network. If congestion exists, then the function results in the minimization of maximum utilization as well as the minimization of the number of congested links. Sqalli et al. concluded that the cost function in (5) results in more efficient minimization of the number of congested links compared to the cost function of Fortz and Thorup [2]. Furthermore, Sqalli et al. discovered that the results for maximum utilization with their method were comparable to those obtained by the approach of Fortz and Thorup. Using the cost function of (5), Sqalli et al. applied the simulated evolution (SimE) algorithm [40] to the OSPFWS problem and compared the results with the results of SA [38]. Tabu search using the cost function of Sqalli et al. [11] has also been applied to the OSPFWS problem [41].

A limitation of the cost function of Fortz and Thorup is that it minimizes “maximum utilization” only. This may lead to the existence of links which are either congested or unused. The cost function proposed by Sqalli et al. (5) was aimed at simultaneous optimization of maximum utilization and the number of congested links, without any consideration of unused links. It is, therefore, not guaranteed that optimizing maximum utilization and number of congested links would implicitly optimize the number of unused links as well. This observation points to the fact that to have a more stable traffic flow, traffic from congested links should be shifted to unused links. Therefore, in order to overcome this issue, Mohiuddin et al. [42] proposed a fuzzy logic based cost function that addresses the simultaneous optimization of maximum utilization, number of congested links, and number of unused links through fuzzy logic based aggregation. Mohiuddin et al. used their fuzzy cost function with three iterative heuristics, namely, simulated evolution, simulated annealing, and NGSA-II, and performed a mutual comparison of the three algorithms.

3 Open shortest part first weight setting problem definition

This section provides the details of the OSPFWS problem. More specifically, the section provides a formal definition of the OSPFWS problem, followed by a discussion of the calculation of traffic load on links.

3.1 Open shortest path first weight setting problem

The OSPFWS problem is formulated as follows. Given a network topology and predicted traffic demands, find a set of OSPF weights that optimizes network performance. More precisely, given a directed network G=(N,A), a demand matrix D, and capacity C a for each arc a∈A, determine a positive integer weight q a ∈[1,q m a x ] for each arc a∈A such that the objective function or cost function Φ is minimized. The maximum value of this weight, q m a x , is a user-defined upper limit. Fortz and Thorup [29] discovered that a small set of weight values significantly reduces the overhead of the algorithm. By experimentation, they set w m a x to 20. The chosen weights on arcs determine the shortest paths, which in turn completely determine the routing of traffic flow, the loads on the arcs, and the value of the cost function. The quality of OSPF routing is highly dependent on the selection of weights. Figure 1 shows a topology with weights assigned to each arc. These weights are in the range [1,20]. A solution for this topology can be (18,1,7,15,3,17,14,19,13,18,4,16,16). The weights are arranged through a breadth-first traversal of the graph. For example, for node A, the weights on the outgoing links are 18 and 1. For node B, the weights on outgoing links are 7 and 15, and so on.

Fig. 1
figure 1

Representation of a topology with assigned weights

Full size image

For the purposes of this paper, three objectives are considered. These objectives are maximum utilization, number of congested links, and number of unused links, all of which need to be minimized simultaneously. Minimizing maximum utilization will lead to better distribution of network traffic across all the links such that congestion can be avoided and the network can be utilized well as per its capacity [8]. Network administrators desire less congested links. However, if a network is highly congested, then the preference is to reduce the congestion by at least minimizing the total number of congested links. For example, assume a network with 50 congested links and 20 unused links. It would be preferred to accommodate the traffic of the 50 congested links additionally on the 20 unused links. This indicates that minimizing the number of unused links also affects the performance of the network. This positive effect on the performance is due to traffic distribution across the links of the networks which depends on the routing paths established [42]. Therefore, a new solution might create new routing paths such that traffic on congested links may be distributed on unused links.

3.2 Traffic load calculation

This section provides details of the steps to calculate arc (or link) loads. Given a weight setting {w a } a∈A , the arc loads l a are calculated in five steps. For all demand pairs d s t ∈D, consider one destination t at a time and compute partial arc loads \({l_{a}^{t}}~\forall ~t \in \bar {N} \subseteq N\), where \( \bar {N} \) is the set of destination nodes. The steps are as follows:

  1. 1.

    Compute the shortest distances \({d_{u}^{t}}\) from each node u∈N to t, using Dijkstra’s shortest path algorithm [7]. Dijkstra’s algorithm usually computes the distances away from source s, but since it is required to compute the distance to the sink node t, the algorithm is applied on the graph obtained by reversing all arcs in G.

  2. 2.

    Compute the set A t of arcs on shortest paths to t as,

    $$A^{t} = \{(u,v) \in A: {d_{u}^{t}} - {d_{v}^{t}} = w_{(u,v)}\} $$
  3. 3.

    For each node u, let \( {\delta _{u}^{t}}\) denote its outdegree in G t=(N,A t), i.e.,

    $${\delta_{u}^{t}} = \mid \{ v \in N : (u,v) \in A_{t} \} \mid $$

    If \({\delta _{u}^{t}} >1\), then traffic flow is split at node u to balance the load.

  4. 4.

    The partial loads \({l_{a}^{t}}\) are computed as follows:

    1. (a)

      Nodes v∈N are visited in order of decreasing distance \({d_{v}^{t}}\) to t.

    2. (b)

      When visiting a node v, for all (v,w)∈A t, set

      $$l_{(v,w)}^{t} = 1/[{\delta_{v}^{t}}(d_{vt} + {\sum}_{(u,v)\in A^{t}} l_{(u,v)}^{t})]$$
  5. 5.

    The arc load l a is now summed from the partial loads as:

    $$l_{a}={\sum}_{t\in \bar{N}} {l_{a}^{t}} $$

4 Fuzzy logic and aggregation operators

In general terms, a crisp set X is defined as a collection of objects x∈X, where each object can either belong to the set or not. However, in many practical situations, certain objects do not fulfil this “crisp” membership requirement. In such situations, a need arises for another set theory which could deal with uncertain data. One possible approach is fuzzy set theory (FST), which aims to represent vague information.

The basis of the theory of fuzzy sets [43, 44] is multi-valued logic wherein a statement can be partly false and partly true at the same time. Formally, a fuzzy set is characterized by a membership function, μ, in the range [0,1]. The membership function provides a measure of the degree of presence for every element in the set [45]. A value of μ=1 indicates that the statement is true, while μ=0 indicates that the statement is false.

Similar to crisp sets, set operations such as union, intersection, and complement are also defined on fuzzy sets. A number of operators exist for fuzzy union and fuzzy intersection. Fuzzy intersection operators are referred to as t-norm operators while fuzzy union operators are known as s-norm operators. Generally, the t-norm is implemented using “min” and the s-norm using “max”. However, in the formulation of multi-criteria decision functions, the simple AND (pure “min” function) and simple OR (pure “max” function) does not work well, due to the fact that the simple AND or OR operations consider the effect of only one objective while neglecting the effects of other objectives. This deficiency of the simple AND and simple OR operators resulted in the development of a number of “soft-AND” and “soft-OR” operators, such as the Werners operator [46], Einstein’s operator [46], Hamacher’s operator [47], Frank’s operator [48], Weber’s operator [49], Dubois and Prade’s operator [50], and the Unified And-Or operator [51], among others. These operators allow easy adjustment of the degree of “anding” and “oring” embedded in the aggregation.

Khan and Engelbrecht showed that the Unified And-Or (UAO) operator [51] satisfies the monotonicity, symmetry, and idempotency conditions. One important characteristic of the UAO operator is that a single equation is used to adjust the degree of “anding” and “oring”. Yet, the operator is capable of behaving either as the soft-AND or the soft-OR operator. This is in contrast to other aggregation operators listed above, which use separate equations for AND and OR functions. The behavior of ANDing and ORing of UAO is controlled by a variable, ν≥ 0, whose value decides whether the function behaves as AND or OR. The operator is defined as:

$$ f(a,b)=\frac{ab + \nu \max\{a, b\}} {\nu +\max\{a, b\}}=\left\{\begin{array}{ll} I_{\star} = \mu_{A \cup B}(x) & \text{if}~\nu > 1 \\ I^{\ast} = \mu_{A \cap B}(x) & \text{if}~ 0 \leq \nu \leq 1 \end{array}\right. $$
(6)

where a represents the membership value of μ A (i.e. a = μ A ), b represents the membership value of μ B (i.e. b = μ B ), and f(a,b) represents the value of the overall objective function (i.e. f(a,b) = μ A B ). I ∗ represents the AND operation using the UAO operator, and I ⋆ denotes the OR operation using the UAO operator. For more details of the UAO operator, the interested reader is referred to Khan and Engelbrecht [51].

5 Fuzzy logic approach for the open shortest path first weight setting problem

Although the approach has been previously proposed and explained in Mohiuddin et al. [42], it is again summarized below for the sake of completeness. Details can be found in Mohiuddin et al. [42].

The solution to the OSPFWS problem is to assign a set of weights to network links. The best solution is one which optimizes the network resources efficiently. The design objectives of the OSPFWS problem include maximum utilization (MU), number of congested links (NOC) and number of unused links (NUL). These objectives individually on their own do not provide adequate information for deciding the quality of a solution. The conflicting nature of these objectives further amplifies the complexity of the problem. With this complexity, a mechanism is required to find a solution that provides the best tradeoff covering all the objectives. Fuzzy logic is one approach that can conveniently and efficiently handle the tradeoff issues between multiple objectives.

The rest of this section details the employment of fuzzy logic for combining the three conflicting objectives into a single overall objective. This overall objective assesses the quality of a solution in terms of membership of a given set of weights. A set of weights providing efficient utilization of network resources consists of low MU, low NOC and low NUL.

To formulate the overall objective function, the values of individual objectives need to be determined first, through membership functions. This needs the formulation of membership functions for each individual objective. This process is described below.

To define the membership function of maximum utilization, two extreme values, the minimum and maximum, are determined first. These values could be found mathematically or from prior knowledge. Figure 2 shows the membership function of the objective to be optimized (maximum utilization in this case). Point ‘A’ refers to minimum MU (MinMU) and point ‘B’ refers to maximum MU (MaxMU). The membership value for MU, μ M U , is determined as follows:

$$ \mu_{MU}(x) = \left\{ \begin{array}{ll} 1 & \text{ if }MU \leq MinMU\\ \frac{MaxMU-MU}{MaxMU-MinMU} & \text{ if }MinMU < MU \leq MaxMU\\ 0 & \text{ if }MU > MaxMU\\ \end{array} \right. $$
(7)
Fig. 2
figure 2

Membership function of the objective to be optimized

Full size image

The membership function for NOC, μ N O C , is defined in a similar way. In Fig. 2, point ‘A’ then refers to minimum NOC (MinNOC) and ‘B’ refers to maximum NOC (MaxNOC). The membership function of NOC is defined as follows:

$$ \mu_{NOC}(x) = \left\{ \begin{array}{ll} 1 & \text{ if }NOC \leq MinNOC\\ \frac{MaxNOC-NOC}{MaxNOC-MinNOC} & \text{ if }MinNOC < NOC\\ &\quad \leq MaxNOC\\ 0 & \text{ if }NOC > MaxNOC\\ \end{array} \right. $$
(8)

Finally, the membership function for NUL, μ N U L , is defined as

$$ \mu_{NUL}(x) = \left\{ \begin{array}{ll} 1 & \text{ if }NUL \leq MinNUL\\ \frac{MaxNUL-NUL}{MaxNUL-MinNUL} & \text{ if }MinNUL < NUL\\ &\quad \leq MaxNUL\\ 0 & \text{ if }NUL > MaxNUL\\ \end{array} \right. $$
(9)

where minimum (MinNUL) and maximum (MaxNUL) values correspond to ‘A’ and ‘B’, respectively in Fig. 2.

A good solution to the OSPFWS problem is one that is characterized by a low MU, low NOC, and low NUL. In fuzzy logic, this can be stated by the following fuzzy rule:

Rule 1::

IF a solution X has low MU AND low NOC AND low NUL THEN it is a good solution.

The words ‘low MU’, ‘low NOC’ and ‘low NUL’ are linguistic values, each defining a fuzzy subset of solutions. Using the UAO operator [51], the above fuzzy rule reduces to the following equation.

$$ \mu (x) = \frac{\mu_{1}(x)\mu_{2}(x)\mu_{3}(x) + \nu \times max\{\mu_{1}(x),\mu_{2}(x),\mu_{3}(x)\}}{\nu + max\{\mu_{1}(x),\mu_{2}(x),\mu_{3}(x)\}} $$
(10)

where μ(x) is the membership value for solution x in the fuzzy set “good OSPF Weight set” and ν is a constant in the range [0,1]. Moreover, μ i for i={1,2,3} represents the membership values of solution x in the fuzzy sets low MU, low NOC, and low NUL respectively. The solution which results in the maximum value for (10) is reported as the best solution.

As an example, consider an arbitrary solution S 1, having μ M U =0.19, μ N O C =0.2, and μ N U L =0.17. Also assume that ν=0.5. Then, (10) results in a value of 0.152. Similarly, consider μ M U =0.22, μ N O C =0.23, and μ N U L =0.009 associated with another arbitrary solution S 2. Again assume that ν=0.5. Then, (10) evaluates to 0.164. Thus, solution S 2 is better than solution S 1 in terms of quality. Equation (10) is employed as a fuzzy cost function for solving the OSPFWS problem using the fuzzy PSO and the fuzzy PSO with simulated evolution algorithms. In this paper, the fuzzy cost function is denoted as FuzzyCF.

6 Fuzzy particle swarm optimization for the open shortest path first weight setting problem

The fuzzy PSO (FPSO) algorithm navigates the search space by maintaining a swarm of candidate solutions, with each candidate solution referred to as a particle. Each particle explores new positions in the search space through its own history, and from the experience of other particles. With respect to the OSPFWS problem, each particle reaches a new candidate solution by changing a few weights on the links of the network. As with the basic PSO [52], the guidance in changing these weights is provided by the particle‘s current position, its own best position so far, and the global best position obtained so far by the entire algorithm. Each step of the proposed FPSO algorithm is discussed in the following subsections in detail.

6.1 Particle position and velocity representation

The standard PSO uses floating-point vectors to represent positions and velocities. For the OSPFWS problem, this study uses a set representation for particles. Therefore, for an arbitrary network with nodes from a to q, each particle position is defined as a set,

$$\textbf{X}_{i}(t) = \{w_{ab}, w_{ac}, ..., w_{aq}, w_{bc} ..., w_{pq}\} $$

where w a b is the weight assigned to the link between any two nodes a and b in the network. A constant, W, is also defined as the number of weights in the solution, i.e. |X i (t)| = W. The velocity of particle i is represented as

$$\textbf{V}_{i}(t) = w_{ab} \Leftrightarrow {w^{\prime}_{ab}} $$

which represents a sequence of replacement operators where the weight of link (a,b) is replaced with a new value, \(w^{\prime }_{ab}\), and |V i (t)| gives the total number of changes to particle i.

Example 1

Consider the topology given in Fig. 1. Note that the total number of links is 14. The assigned weights in this figure represent a possible configuration at time t, whereas the configuration represents a solution (i.e. a particle). A solution for this topology can be (18,1,7,15,3,17,5,14,19,13,18,4,16,16). This current solution is represented as

$$\begin{array}{@{}rcl@{}} {X}_{i}(t)=\{18_{AB},1_{AF},7_{BC},15_{BD},3_{CE},17_{CF}, \\ 5_{DA},14_{EA},19_{EG},13_{FB},18_{FD},4_{FG},16_{GB},16_{GD}\}. \end{array} $$

Also assume that at time t, V i (t)={(19⇔18) A B ,(2⇔1) A F ,(4⇔7) B C ,(12⇔15) B D ,(4⇔3) C E ,(15⇔17) C F ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B ,(11⇔18) F D ,(9⇔4) F G ,(17⇔16) G B ,(17⇔16) G D } where the symbol “ ⇔” represents a replacement of weights on the links. That is, the above solution, X i (t), was obtained when weight 19 on link AB was replaced with a weight of 18, weight 2 on link AF was replaced with a weight of 1, and so on. The solution X i (t) is then updated in subsequent steps as discussed in the following subsections.

6.2 Velocity update

The velocity of particle i is updated using

$$\begin{array}{@{}rcl@{}} \textbf{V}_{i}(t+1) &=& w \otimes \textbf{V}_{i}(t) \oplus c_{1}r_{1}(t)\otimes[\textbf{P}_{i}(t) \oslash \textbf{X}_{i}(t)]\\ &&\oplus c_{2}r_{2}(t)\otimes[\textbf{P}_{g}(t) \oslash \textbf{X}_{i}(t)] \end{array} $$
(11)

where P i (t) represents the particle’s own best position, and P g (t) represents the global best position.

In (11), the operator ⊗ is implemented as follows: The number of elements to be selected is determined as ⌊w×|V i (t)| ⌋, where 0<w<1. Then, the result is the above number of elements randomly selected from V i (t). The same approach is applicable to other terms where the operator ⊗ is used.

The operator ⊘ is implemented as a ‘replacement’ operator. For example, the weights in X i (t) are replaced with the weights in P i (t).

The term c 1 r 1(t)⊗[P i (t)⊘X i (t)] is implemented by randomly sampling ⌊c 1 r 1(t)×|P i (t)⊘X i (t)| ⌋ elements from the set P i (t)⊘X i (t), as follows:

$$ c_{1}r_{1}(t)\otimes [{ \textbf{P}}_{i}(t) \oslash \textbf{X}_{i}(t)] =\lfloor c_{1}r_{1}(t) \times |\textbf{P}_{i}(t)\oslash \textbf{X}_{i}(t)|~\rfloor $$
(12)

where |P i (t)⊘X i (t)| represents the cardinality of the set. The result of (12) indicates the number of elements that are randomly selected from the set P i (t)⊘X i (t); c 2 r 2(t)⊗[P g (t)⊘X i (t)] has the same meaning.

The operator ⊕ implements the set addition (union) operator. V m a x is used to limit the number of elements selected from a set.

Example 2

Continuing with Example 1, assume the following parameter values:

w=0.5, V m a x =2, c 1 = c 2=0.5, r 1=0.52 (randomly generated), r 2=0.75 (randomly generated). Further assume that the best goodness so far for particle i was generated by the following position as

$$\begin{array}{@{}rcl@{}} \textbf{P}_{i}(t)=\{18_{AB},12_{AF},7_{BC},15_{BD},3_{CE},16_{CF},\\ 5_{DA},13_{EA},19_{EG},13_{FB},8_{FD},4_{FG},12_{GB},16_{GD}\}. \end{array} $$

Also assume that the best solution so far generated by the entire swarm was achieved by:

$$\begin{array}{@{}rcl@{}} \textbf{P}_{g}(t)=\{18_{AB},2_{AF},7_{BC},15_{BD},3_{CE},15_{CF},\\ 5_{DA},13_{EA},19_{EG},13_{FB},9_{FD},4_{FG},1_{GB},16_{GD}\}. \end{array} $$

The inertia weight, w, determines the number of replacements that will be randomly selected from V i (t) (mentioned in Example 1 above). Since w=0.5, and |V i (t)| = 14, the number of randomly selected replacements is 0.5×|V i (t)| = 7. Thus, any seven replacements from the set V i (t) can be taken randomly. Consider that those replacements are {(2⇔1) A F ,(4⇔7) B C ,(4⇔3) C E ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B }.

The difference between the particle’s current position and its own best position, P i (t)⊘X i (t), is calculated by replacing each link in X i (t) with the link in the corresponding position in P i (t) as:

P i (t)⊘X i (t)={(18⇔18) A B ,(1⇔12) A F ,(7⇔7) B C ,(15⇔15) B D ,(3⇔3) C E ,(17⇔16) C F ,(5⇔5) D A ,(14⇔13) E A ,(19⇔19) E G ,(13⇔13) F B ,(18⇔8) F D ,(4⇔4) F G ,(16⇔12) G B ,(16⇔16) G D }.

Therefore, c 1×r 1⊗(P i (t)⊘X i (t))=0.5×0.52×|P i (t)⊘X i (t)|. Since the cardinality of P i (t)⊘X i (t) is 5, this implies that 0.5×0.52⊗|P i (t)⊘X i (t)|=1.3=1. This means that any one of the five elements in P i (t)⊘X i (t) is randomly chosen. Assume that c 1×r 1⊗(P i (t)⊘X i (t)) = {(18⇔8) F D }.

Similarly,

P g (t)⊘X i (t) = {(18⇔18) A B ,(1⇔2) A F ,(7⇔7) B C ,(15⇔15) B D ,(3⇔3) C E ,(17⇔15) C F ,(5⇔5) D A ,(14⇔13) E A ,(19⇔19) E G ,(13⇔13) F B ,(18⇔9) F D ,(4⇔4) F G ,(16⇔1) G B ,(16⇔16) G D }.

The cardinality of the above set is 5, since replacements involving new and old weights having the same value are ignored. Therefore, 0.5×0.75⊗(P g (t)⊘X i (t))=0.5×0.75×5 = 1.3 = 1 replacement. Assume {(17⇔15) C F } is randomly chosen.

Substituting the above calculations in (11) gives V i (t+1) containing three elements, i.e.

V i (t+1) = {(2⇔1) A F ,(4⇔7) B C ,(4⇔3) C E ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B ,(18⇔8) F D ,(17⇔15) C F }

Since V m a x = 2, only two replacements from V i (t+1) are randomly chosen. Assume that ((18⇔8) F D and (17⇔15) C F are chosen. Then,

V i (t+1) = {(18⇔8) F D ,(17⇔15) C F }

6.3 Particle position update

The position X i (t) of a particle i is updated using

$$ \textbf{X}_{i}(t+1)= \textbf{X}_{i}(t) \biguplus {\textbf{V}}_{i}(t+1) $$
(13)

where \(\biguplus \) is a special operator that updates the links in X i (t) on the basis of weight replacements in V i (t+1), to get the new position X i (t+1).

Example 3

Consider Example 2, for which

$$\begin{array}{@{}rcl@{}} &&\,\,\,\,\,\,\mathbf{X}_{i}(t+1)=\mathbf{X}_{i}(t) \biguplus \mathbf{V}_{i}(t+1) {}=\{18_{AB}, 1_{AF}, 7_{BC},\\&&\!\!\!\!15_{BD},\,\,3_{CE},\,17_{CF}, \,5_{DA},14_{EA},19_{EG},\,{\kern1.5pt}13_{FB},18_{FD},4_{FG},\\&&\!\!\!\!\!16_{GB},\,16_{GD}\} \,\biguplus~\{(18 \Leftrightarrow 8)_{FD},\,(17 \Leftrightarrow 15\,)_{CF}\} = \{18_{AB},\\&&\!\!\!\!1_{AF},\,\,7_{BC},{\kern1.2pt}\,15_{BD},\,3_{CE},\,15_{CF},\, 5_{DA},\,14_{EA},\,19_{EG},\,13_{FB},\\&&\!\!\!\!8_{FD},4_{FG},16_{GB},16_{GD}\} \end{array} $$

Thus, in the new solution, weight 18 on link FD is replaced by 8 and weight 17 on link CF is replaced by 15.

6.4 Fitness evaluation

Each iteration performs a few weight replacements. Because of weight changes, the routes within the network will change. The next step is to calculate the traffic on each link as a result of the new routes. Finally, the cost of the new solution is computed using (10) as discussed in Section 5.

7 Fuzzy evolutionary particle swarm optimization algorithm for open shortest path first weight setting problem

In addition to the fuzzy PSO algorithm for OSPFWS (described in Section 6), a hybrid variant of the fuzzy PSO using the simulated evolution (SimE) algorithm is presented in this section. This hybrid variant is referred to as fuzzy evolutionary PSO (FEPSO). Section 7.1 presents a brief discussion on SimE. This is followed by a discussion on FEPSO in Section 7.2.

7.1 Simulated evolution algorithm

Simulated evolution (SimE) is a search strategy proposed by Kling and Banerjee [9, 53, 54]. Throughout the search, SimE maintains a single solution which is perturbed to generate a new solution. Each solution is comprised of a set of individuals, known as elements. SimE iteratively executes three steps:

  • The evaluation step, which calculates the goodness of each element of the solution. The goodness of an element quantifies the nearness of the element with respect to its optimal value, and is a value in the range [0,1]. The optimal value is problem specific and is determined theoretically or through some empirical analysis. A higher value of goodness indicates that the element is near to its optimal value.

  • The selection step, in which a subset of elements are selected based on their goodness and removed from the current solution. The lower the goodness of a particular element, the higher its selection probability. A bias parameter B in the range [-1, 1] is used to control the number of elements selected. A negative value of B increases the number of elements selected in each iteration, thus favoring exploration. This may result in a high quality solution but at the expense of higher computational time. A positive value of B inflates the goodness of an element, thus reducing the number of elements being selected for reallocation. This may result in reduced execution time, but at the risk of premature convergence to sub-optimal (or local optimal) solution.

  • The allocation step, in which the selected elements are allocated to new positions, with the intention of improving the existing solution. Each element selected in the selection step is removed from the solution and trial allocations are performed. The goodness of the solution resulting from each trial allocation is calculated, and the allocation which results in the highest goodness of the solution is accepted. This process of allocation and goodness calculations is repeated for each selected element. At the end of the allocation step, a new solution is obtained.

Further details about the SimE algorithm can be found in [9, 53, 54].

7.2 Fuzzy evolutionary particle swarm optimization

Particles of the fuzzy PSO algorithm proposed in Section 6 perform weight replacements. These replacements involve replacing an old weights with a new weights on the links. Furthermore, the total number of performed replacements is limited by the parameter V m a x . It is possible that, for a link i, a replacement may remove a weight (to be replaced with another weight) which might already be the optimum (or near-optimum) weight for that link. Note that this replacement is done ‘blindly’. That is, the value of the new weight is chosen randomly. If these blind replacements continue for other links having optimum weights, then it will take a significant amount of time for the algorithm to converge. Rather than having a blind replacement, it would be more appropriate to replace a weight based on its quality. A weight with low quality will have a high probability of being removed from its current position, and vice versa. The question is how to measure the quality of a weight. This can be answered by incorporating the evaluation and selection phases of the SimE algorithm into the FPSO algorithm, as discussed below.

Recall from Section 7.1 that a solution in SimE is comprised of elements. For the OSPFWS problem, elements are the link weights, whose goodness need to be evaluated. In this paper, the function defined by Sqalli et al. [38] is employed to evaluate the goodness of a weight, as given below:

$$ g_{ij} = \left\{\begin{array}{ll} 1-u_{ij} & \text{ if } MU \leq 1\\ 1 - u_{ij} / MU + u_{ij} /MU^{2} & \text{ if } MU > 1\\ \end{array} \right. $$
(14)

where u i j represents the utilization on link connecting nodes i and j, and MU refers to the maximum utilization. The evaluation is performed for all current weights which are part of the set V i (t+1) as defined by (11).

Once the goodness of each existing weight in V i (t+1) is evaluated, the selection phase chooses the weights that would be replaced with new weights. This selection is done probabilistically based on the quality of existing weights in V i (t+1). A random number R a n d o m in the range [0,1] is generated. If R a n d o m ≤ 1−g i j + B, then the existing weight is selected for replacement, otherwise no replacement is done. In the above expression, g i j refers to the goodness of current weight on the link connecting nodes i and j, and B is the selection bias. Figure 3 provides the pseudo-code of the selection function for FEPSO. The selection process is illustrated by the following example.

Fig. 3
figure 3

Weight replacement function of FEPSO

Full size image

Example 4

In Example 2, V i (t+1) was found as follows:

V i (t+1) = {(2⇔1) A F ,(4⇔7) B C ,(4⇔3) C E ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B ,(18⇔8) F D ,(17⇔15) C F }

Since V m a x = 2, only two replacements from V i (t+1) were randomly chosen in FPSO. However, in FEPSO, the replacements will be done based on the goodness of weights. Assume that (4⇔3) C E , (10⇔13) F B and (17⇔15) C F were selected based on the selection procedure. However, since V m a x = 2, only two replacements will be selected randomly out of the three. So, a possible result could be

V i (t+1) = {(10⇔13) F B and (17⇔15) C F }

Although the proposed hybridization between PSO and SimE seems promising in generating high quality results, the approach also has some negative aspects. One major complexity is associated with tuning of another parameter, namely, bias B, on top of tuning of various parameters associated with the PSO algorithm. This adds extra effort and time to find the best combination out of many possible combinations of all design parameters. Another issue is that the complexity of the code increases, thus increasing the execution time. A single iteration of FEPSO will take more time than a single iteration of FPSO. In a broader perspective and with consideration of applying the proposed hybrid algorithm to other optimization problems, it can be argued that the proposed hybridization will allow faster convergence of FEPSO to an optimal or sub-optimal solution as compared to FPSO. However, this is not always guaranteed and can only be established after thorough experimentation and analysis.

8 Experimental methodology

This paper uses test cases from [2] which have been used by many other researchers as discussed in Section 2. Table 1 summarizes the characteristics of the test cases. For each test case, the table lists its network type, the number of nodes (N), and the number of arcs or edges (a). The 2-level hierarchical networks are generated using the GT-ITM generator [55], based on the model of Calvert [56] and Zegura [57]. In hierarchical networks, local access arcs have capacities equal to 200, while long distance arcs have capacities equal to 1000. In Random networks and Waxman networks, capacities are set at 1000 for all arcs. Fortz and Thorup generated the demands to force some nodes to be more active senders or receivers than others, thus modelling hot spots on the network. More specifically, higher demands were assigned to closely located node pairs. Further details can be found in [8].

Table 1 Test cases for the OSPFWS problem. N = number of nodes, a = number of arcs
Full size table

Experiments were done with different combinations of PSO parameters for each test case. Thirty independent runs were executed for each parameter setup, and the average of the best solutions found in each run was reported, with the associated standard deviation. Furthermore, results were validated for statistical significance through non-parametric testing. For this purpose, the Wilcoxon’s rank-sum test was used with confidence level set at 95 %. After experimenting with different values, it was found that 100 iterations were reasonable to observe the trends. Therefore, each run was executed for 100 iterations.

9 Results and discussion

The proposed PSO algorithm was evaluated with respect to all the PSO parameters. These parameters are the swarm size, acceleration coefficients c 1 and c 2, inertia weight w, and velocity clamping V m a x . Table 2 lists all the parameter combinations used. The following parameters were used as default: swarm size =40, V m a x =15, w=0.72, and c 1 = c 2 = 1.49. The values c 1 = c 2 = 1.49 (along with w=0.72) were specifically selected, since they are frequently used in the literature due to the fact that they enhance the probability of convergence [58].

Table 2 PSO parameter settings used in the experiments
Full size table

9.1 Effect of Swarm Size

The effect of swarm size was investigated with 20, 40, 60, 80, and 100 particles, as listed in Table 2. Other parameter values were kept at the defaults. Figures 4 and 5 provide a graphical representation of the effect of varying the swarm size on the quality of solutions obtained for test cases with 50 nodes and 100 nodes, respectively (detailed results are presented in Appendix B). It is observed from the figures that for all test cases, increasing the number of particles enhanced the quality of solution. More specifically, the highest average overall goodness was obtained with the highest swarm size consisting of 100 particles, while the lowest average overall goodness was obtained with the minimum value of swarm size, i.e. 20 particles. Furthermore, the figures show a logarithmic decrease in the gains in quality with increase in swarm size. A validation with Wilcoxon’s test with 95 % significance level for the average overall goodness obtained with different swarm sizes was also performed for the results reported in Tables 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 and 25 (refer to Appendix B). The hypothesis testing was done to check whether the average goodness value obtained with 100 particles was statistically significantly better than those obtained with other swarm sizes. The results confirmed that a swarm size of 100 gave the best results for all test cases.

Fig. 4
figure 4

Effect of swarm size on overall goodness for test cases with 50 nodes: (a) h50N148a (b) h50N212a (c) r50N228a (d) r50N245a (e) w50N169a (f) w50N230a

Full size image
Fig. 5
figure 5

Effect of swarm size on overall goodness for test cases with 100 nodes: (a) h100N280a (b) h100N360a (c) r100N503a (d) r100N403a (e) w100N391a (f) w100N476a

Full size image

Another important observation from Tables 14 to 25 is that, for most test cases, swarms of 80 and 100 particles resulted in no significant difference with respect to solution quality. This happened for the test cases h100N280a, h100N360a, h50N212a, r100N503a, r50N228a, r50N245a, w50N169a, and w50N230a. The test case w50N169a was an exception, where swarm sizes 60, 80, and 100 particles resulted in the same quality of solutions. Therefore, the smaller swarm size was preferred over larger swarm size due to lower computational cost.

Diversity is defined as a measure of the average distance of each particle from the center of the mass. Diversity is calculated at each iteration during the execution of the algorithm [59]. The effect of increase in swarm size on diversity was also studied. The purpose was to observe whether bigger swarm sizes reduced the possibility of getting trapped in local minima (preventing premature convergence), thus resulting in solutions of higher quality. As an example, Fig. 6 shows the diversity plots for different number of particles for the test case w100N476a. The figure suggests that the algorithm did not converge immediately after initialization for all the swarms. Diversity increased until around iteration number 50. The reduction in diversity is seen when the algorithm started converging. Swarms with 20 particles maintained diversity at a higher level compared to other swarm sizes, and quickly converged at around iteration 225. This is followed by swarms with 40 and 60 particles, which converged nearly at the same time, at around iteration number 326. Followed by this, swarm with 80 particles converged at iteration 380. Finally, the swarm with 100 particles converged last, after 400 iterations.

Fig. 6
figure 6

Diversity plots for w100N476a using (a) 100 particles (b) 80 particles (c) 60 particles (d) 40 particles and (e) 20 particles

Full size image

9.2 Effect of acceleration coefficients

The impact of the acceleration coefficients on the algorithm’s performance was also evaluated. Table 3 gives the average overall goodness for different combinations of acceleration coefficients, as given in Table 2. Other algorithm parameters were kept as their defaults.

Table 3 Effect of different acceleration coefficients combinations on overall goodness for different test cases. Best overall goodness for each test case is in boldface
Full size table

As observed in Table 3, a dominant trend was that the best results were obtained when the value of c 1 was much higher than that of c 2. That is, for seven out of twelve test cases, the best overall goodness was obtained when c 1 = 3.0 and c 2 = 0.5. Furthermore, there were two other test cases (r100N403a and w100N391a) where the best overall goodness was obtained with c 1 = 1.4 and c 2 = 0.7. These results indicate that in general, the algorithm resulted in highest overall goodness values when the cognitive component dominated the social component. There were only three test cases (h100N280a, h100N360a and w50N169a) which deviated from the above trend.

The above observations are further supported by the results given in Table 4 which gives the percentage improvements in terms of the best and worst overall goodness values. The results show that the level of improvements achieved ranged between 2.61% and 11.74%. In most instances, the average overall goodness was around 4% or above. Statistical validation with the Wilcoxon’s test proved that in a majority of the cases, the improvements were statistically significant (highlighted in boldface). It is clear from these results that for eight test cases, best overall goodness values were obtained when the value of c 1 was greater than c 2. There were three exceptions, namely, h100N280a, w50N169a, and h100N360 (highlighted in asterisk) which deviated from the above trend. Furthermore, improvements in one test case (r50N245a) turned out to be statistically insignificant. In view of the above results and discussion, it can be fairly concluded that higher quality results produced by PSO were governed by the cognitive component.

Table 4 Results for best and worst overall goodness and their corresponding values of c 1 and c 2. Statistically significant improvements are given in boldface
Full size table

9.3 Effect of inertia weight

The effect of the inertia weight was assessed with respect to the five values listed in Table 2. Other algorithm parameters were kept at their defaults. Table 5 gives the average overall goodness for the different values of the inertia weight. It is observed from this table that, in general, higher values of the inertia weight (w = 0.85 and w = 0.99) tend to show better results than the tried smaller values.

Table 5 Average overall goodness values achieved with different inertia weights. Best overall goodness values are given in boldface
Full size table

In order to validate the above observations, statistical testing was done and results are shown in Table 6. This table shows the percentage improvements obtained when results with two different inertia weights were compared. Although the results show improvements in terms of percentages, statistical testing revealed that in general, improvements were statistically insignificant. Only few improvements were significant which are highlighted in boldface. Based on these observations, it can be confidently claimed that with respect to the five values tried, the inertia weight did not have a notable impact on the output results produced by the algorithm.

Table 6 Comparison of different inertia weights given in Table 5 in terms of percentage differences. Statistically significant differences are highlighted in boldface
Full size table

9.4 Effect of velocity clamping

The effect of velocity clamping was also investigated. Apart from the default value of V m a x = 15, other values of velocity clamping 5, 10, and 20, were tried as listed in Table 2. Other algorithm parameters were kept as defaults. The inspiration for taking the aforementioned values of V m a x comes from the concept of mutation rates in genetic algorithms. Note that the function of V m a x in PSO and mutation in GA is somewhat similar; both parameters control the level of perturbation in the solution. Although the mutation rate is problem specific, a number of studies [59–63] have used the mutation rate of up to 20 %. Therefore, the motivation for choosing the given range of V m a x is the above observation. For the problem in hand, since the size of the solution string varies between 148 and 503 (corresponding to the number of edges on which the weights are varied), the values of V m a x ranging from 5 to 20 correspond to perturbation rates of 1 % to around 12 %.

Table 7 shows the average overall goodness for the four values of V m a x investigated. It is observed from the table that V m a x = 5 produced the highest values of average overall goodness for almost all test cases, with the exception of r100N403a, where V m a x = 10 produced the highest value of average overall goodness. Another deviation from the trend was the case w100N391a where both V m a x = 5 and V m a x = 10 produced the same level of average overall goodness.

Table 7 Analysis of velocity clamping. Best overall goodness is in boldface
Full size table

The best performance of V m a x = 5 was further confirmed by statistical testing which showed that the results produced by V m a x = 5 were indeed significant for all test cases when compared with V m a x = 15 and V m a x = 20, as depicted in Table 8. Furthermore, when compared with V m a x = 10, the results produced by V m a x = 5 were statistically significant for 9 out of the 12 test cases. The above observations and analysis clearly indicate that V m a x = 5 resulted in the highest quality of solutions compared to the other values of V m a x tested.

Table 8 Comparison of different values of velocity clamping. Significant differences are highlighted in boldface
Full size table

It is obvious from the above discussion and analysis that V m a x had a significant impact on the quality of final solutions produced by the proposed PSO algorithm. The results also indicate that better overall goodness values were obtained when velocity clamping was kept low. This can be attributed to the fact that, with larger values of V m a x , the algorithm was biased towards exploration which rather resulted in more randomized search. A lower value of V m a x was therefore able to better balance exploration and exploitation.

9.5 Comparison of Fuzzy Particle Swarm Optimization and Fuzzy Evolutionary Particle Swarm Optimization

Table 9 summarizes the comparison of the proposed fuzzy PSO and the fuzzy evolutionary PSO. The table shows the results of the best parameter combination for FPSO and the corresponding results for FEPSO for the same parameter combination. Thirty runs were executed for each test case and results were statistically validated through Wilcoxon’s rank-sum test. The execution time (not the number of iterations) for both versions was also kept the same. It is clearly observed from the table that the improvements achieved by FESPO were statistically significant for all test cases, with the exception of h100N280a (for which FEPSO had a slightly inferior performance with degradation of 0.91% in the average overall goodness). However, statistical analysis suggested that this deteriorated result was not significant. Therefore, it can be confidently claimed that FEPSO outperformed FPSO in terms of quality of the average overall goodness.

Table 9 Comparison of fuzzy PSO and fuzzy evolutionary PSO. Significant differences are highlighted in bold. NoP = number of particles, % Imp = percentage improvement. Runtime is in seconds
Full size table

The superior performance of FEPSO can be attributed to its design. Recall from Section 7.2 that an existing solution is perturbed by performing moves as governed by (11). These moves result in randomly replacing existing weights on links with new weights. It is quite possible that some of these moves may result in removing a near-optimum (or even optimum) weight from a certain link and introducing an unsuitable weight. In order to avoid this from happening, the concept of “intelligent” move was introduced in FEPSO, which allows the algorithm to converge in less amount of time, or alternatively speaking, producing higher quality results when executed for the same amount of time as that of FPSO.

10 Comparison of fuzzy evolutionary particle swarm optimization with other algorithms

Since fuzzy evolutionary PSO algorithm (FEPSO) performed better than fuzzy PSO (FPSO) algorithm, it was compared with other iterative heuristics, namely, Pareto-dominance PSO (PDPSO) [64], PSO with weighted aggregation (WAPSO) [65], non-dominated sorting genetic algorithm II (NSGA-II)[42, 66], simulated evolution (SimE)[40, 42], and simulated annealing (SA) [39, 42]. PDPSO and WAPSO were adapted for the underlying problem, whereas NSGA-II, SimE, and SA have already been applied to the same problem by Mohiuddin et al. [42]. Details of implementation and comparative analysis of NSGA-II, SimE, and SA can be found in Mohiuddin et al. [42]. Thirty runs were made for each test cases for each algorithm, and average results and standard deviations were reported. All algorithms were run for the same amount of time for fair comparisons.

Tables 10, 11, and 12 present the results obtained for FEPSO, PDPSO, WAPSO, NSGA-II, SimE, and SA for the three objectives, respectively. Since the multi-objective assessment approach for the algorithms is not the same, the overall objective function that shows the combined effect of all three objectives cannot be directly used for comparison. Therefore, each objective was evaluated individually. Table 10 indicates that for the maximum utilization objective, FEPSO obtained the best results for four test cases (h100N360a, r100N503a, r50N245a, w50N230a). For two test cases (r100N403a and r50N228a), both FEPSO and SimE produced the best results. For four cases (h100N280a, h40N212a, w100N391a, and w100N476a), SimE generated the best (minimum) values. For two test cases (h50N148a and w50N169a), SA obtained the best results. As for the objective of number of congested links, the results in Table 11 indicate that FEPSO obtained the best results for nine test cases. The exception was three test cases of h100N280a, h50N148a, and w50N169a where SimE, SA, and NSGA-II were able to achieve the best values, respectively. Finally for the objective of number of unused links, the results in Table 12 indicate that FEPSO was able to achieve optimum values (i.e., no link was left unused) in all test cases, with the exception of r50N245a. However, it should also be noted that there are many instances where other algorithms also achieved the optimum levels.

Table 10 Comparison of Maximum Utilization (MU) achieved by FEPSO, PDPSO, WAPSO, NSGA-II, SimE, and SA. Best (minimum) values are shown in bold
Full size table
Table 11 Comparison of Number of Congested Links (NOC) achieved by FEPSO, PDPSO, WAPSO, NSGA-II, SimE, and SA. Best (minimum) values are shown in bold
Full size table
Table 12 Comparison of Number of Unused Links (NUL) achieved by FEPSO, PDPSO, WAPSO, NSGA-II, SimE, and SA
Full size table

Although the discussion above provides a fair picture of the performance of FEPSO with respect to individual objectives, an overall view of FEPSO‘s performance is desired. Table 13 accumulates the results with regard to the three objectives and displays the best and worst achievers for each objective. The results given in Table 13 are based on results of Tables 10, 11, and 12. The table signifies that in five cases (h100N360a, r100N403a, r100N503a, r50N228a, and w50N230a), FEPSO achieved the best results for all three objectives, while there are four cases (h50N212a, r50N245a, w100N391a, and w100N476a) where FEPSO was dominant through achievement of best results in two objectives. In contrast, algorithms used for comparison with FEPSO achieved best results mostly in only one objective. There are some exceptions where other algorithms achieved best results in two objectives, but achieved worst results in the third objective, which, to some extent, negatively affects their best achievement in two objectives. Such instances are h100N280a, where SimE gets best results for MU and NOC objectives, but shows worst results for the NUL objective. Another example is h50N148a where NSGA-II shows the same trends as that of SimE. There is only one test case of w50N169a where NSGA-II achieved the best results for two objectives (NOC and NUL) but did not achieve worst results for the MU objective. Note that in all results, there is only one instance where FEPSO showed the worst performance (NOC for h100N280a). Based on the above discussion and observations, it can be fairly claimed that, overall, FEPSO showed the best performance compared to all other algorithms considered.

Table 13 Summary of test cases where different algorithms achieved best and worst results for the three objectives
Full size table

The overall better performance of FEPSO lies in its design, which combines the strong searching capabilities of PSO, augmented by the simulated evolution algorithm which allows a more intelligent local search capability. In contrast to this hybrid design of FEPSO, both SimE and SA lack efficient traversing of the whole search space, since both of them are local search algorithms after all. Furthermore, when compared with NSGA-II, PDPSO, and WAPSO, again the intelligent local search capability of FEPSO allowed it to outperform the three algorithms.

11 Conclusion

This paper proposed and investigated a multi-objective particle swarm optimization algorithm to efficiently solve the open shortest path first weight setting problem. Three optimization objectives, namely, maximum utilization, number of congested links, and number of unused links were considered in the optimization process. These conflicting objectives were aggregated into a scalar optimization function using the unified and-or fuzzy aggregation operator. The performance of the proposed algorithm was analyzed with regard to different algorithm parameters including swarm size, acceleration coefficients, inertia weight, and velocity clamping. Results revealed that swarm size, acceleration coefficients, and velocity clamping have a significant effect on the quality of results, but the algorithm was insensitive to variation in the inertia weight. Furthermore, a modified version of the fuzzy PSO, namely, fuzzy evolutionary PSO, was also proposed which incorporated characteristics of the simulated evolution algorithm. A comparison among the basic and modified versions of the PSO revealed that the fuzzy evolutionary PSO was able to produce results of higher quality compared to its basic counterpart. Furthermore, a comparison of fuzzy evolutionary PSO with Pareto-dominance PSO, weighted aggregation PSO, NSGA-II, simulated evolution, and simulated annealing algorithms revealed that the fuzzy evolutionary PSO outperformed the other five algorithms.