DESIGN OF TWO-DIMENSIONAL INFINITE IMPULSE RESPONSE RECURSIVE FILTERS USING HYBRID MULTIAGENT PARTICLE SWARM OPTIMIZATION

Abstract

We incorporate the optimization problem of two-dimensional infinite impulse response (IIR) recursive filters and the optimization methodology of hybrid multiagent particle swarm optimization (HMAPSO) and then apply the resultant optimized IIR filter in image processing for justifying HMAPSO robustness over other algorithm and its role in optimizing real-time situations. The design of the 2-D IIR filter is reduced to a constrained minimization problem whose robust solution is being achieved by a novel and optimal algorithm HMAPSO. This algorithm integrates the deterministic solution by the multiagent system, the particle swarm optimization (PSO) algorithm, and bee decision-making process. All agents search parallel in an equally distributed lattice-like structure to save energy and computational time as done by the bees in their hive selection process. Thus making use of deterministic search, multiagent PSO, and bee, the HMAPSO realizes the purpose of optimization. Experimental results and the application of the designed filters to focusing the defocused image show that the HMAPSO approach provides better upshots than the previous design methods.

INTRODUCTION

Over the past few years a lot of research is being done on designing 2-D infinite impulse response (IIR) filters. Two different approaches, transformation approach and optimization approach, are developed for designing digital 2-D filter (Kaczorek, 1985; Tzafestas, 1986; Lu and Antoniou, 1992). Transformation approach involves analog-to-digital transformation based on a given set of prescribed specifications that do not work well for IIR filters (Mastorakis et al., 2003). In the optimization approach the designing problem is formulated as a multiobjective problem satisfying some constraints having various local minimas (Lu and Antoniou, 1992; Mastorakis et al., 2003).

The stability of the designed filters plays a vital role for their practical implementation, which is governed by the optimization technique used. Various researchers used genetic algorithm-based approaches to solve the 2-D filter problem (Kawamata et al., 1994; Tsaia et al., 2009; Lu and Tzeng, 2009; Wang et al., 2006; Zhao, 2005). It is a common observation that in the multiparameter optimization problem, the genetic algorithm (GA)-based approach fails when it gets trapped in the local optima of the objective function where the number of the parameters is large, so one can face numerous local optima in designing digital 2-D IIR filters (Tsaia et al., 2009). To obtain better upshots, researchers have applied various methods to improve GA. Hybrid Taguchi GAs (HTGAs) for one-dimensional (Tsai et al., 2004), two-dimensional (Tsai et al., 2005), and structure-specified filters (Tsaia et al., 2009) are some such approaches. The plight of GA-based approaches is their casual output and time taken for different computation. Some researchers involve the neural network to obtain an enhanced and stable solution (Mladenov and Mastorakis, 2001).

IIR filters, due to their various local minimums, have a multimodal error surface. Therefore a consistent design method proposed for IIR filters, based on a global search procedure, must be used to get better results. Many global optimization techniques are already used, which may include particle swarm optimization (PSO) or artificial bee colony (ABC) algorithm. Swarm optimization approach is a stochastic, population-based evolutionary algorithm for obtaining optimization, used for designing 2-D, zero phase, IIR digital filters (Swagatam and Konara, 2007). The ABC algorithm, which simulates the intelligent foraging behavior of the honey bee swarm, is a simple, robust, and very flexible algorithm also used for designing digital IIR filters (Nurhan Karabogaa, 2009).

Here, we have used a novel multiagent-based hybrid particle swarm optimization technique, termed HMAPSO (Kumar et al., 2009). The algorithm integrates the deterministic multiagent system (MAS), PSO, and bee decision-making approach. The hybrid algorithm comprises two parts search algorithm and other as decision-making process. A search in HMAPSO is based on the multiagent approach and PSO, whereas the decision-making process is based on the bee decision-making processor for its next hive. This algorithm was tested over various cases where HMAPSO shows its robustness and accuracy over GA and PSO (Seeley et al., 2006; Kumar et al., 2009). In this article HMAPSO-based IIR filter results are compared with the HTGA, quasi-Newton, neural network, and traditional GA methods.

The reminder of the article is organized as follows. The next section details the problem formulation of an IIR filter. Next, we describe the HMAPSO algorithm and then elaborated on the experimental results for various methods. Finally, we conclude the paper.

PROBLEM FORMULATION

For design purposes the following 2-D filter is used whose transfer function is expressed in Eq. (1) as used in previous approaches (Mastorakis et al., 2003; Tsaia et al., 2009):

M _d is the desired amplitude response of the 2-D filter, which is function of the frequency of w ₁ and w ₂, where (w ₁, w ₂ ∊ [0, π]). The objective of the system is to find a transfer function H(z ₁, z ₂) as given in Eq. (1) such that the function H(e ^{jw ₁} , e ^{jw ₂} ) gauges the desired amplitude response of M _d (w ₁, w ₂). To obtain the objective, an optimization problem is considered whose aim is to minimize, as stated in Eq. (2):

where M(w ₁, w ₂) = H(z ₁, z ₂)| _{z 1 = e ^{jw 1} z 2 = e ^{jw 2}} and w ₁ = (π/N ₁)n ₁, w ₂ = (π/N ₂)n ₂ p is an even positive integer (usually p = 2 or p = 4).

So Eq. (2) can be written as

Hence, the filter design problem is formulated as a minimization problem having multiobjective constraints to being satisfied. Because we are dealing with only first-degree factors in the denominator, it is well known that the stability constraint can be stated as follows (Kaczorek, 1985; Tzafestas, 1986; Lu and Antoniou, 1992):

Different authors solve this problem with different approaches. Mladenov and Mastorakis (2001) solved this problem using the neural network, whereas Mastorakis et al. (2003) applied GA to find the optimal solution; Tsai et al. (2004, 2005) used the improved GA. PSO is also being tested and used for designing the 2-D, zero-phase IIR, which proves better than previous methods (Swagatam and Konara, 2007). Artificial ABC is also used for designing low- and high-order digital IIR filters (Nurhan Karabogaa, 2009). Novel global, robust optimization approaches have been used, with hybrid features of PSO, MAS, and bee optimization. The result proves its advantage over other approaches.

HMAPSO ALGORITHM

For the HMAPSO algorithm different agents are sent in the whole search area, which is divided into different fragments (Kumar et al., 2009). For a global and robust optimal solution the total range of the independent parameters are divided into smaller volumes, each of which determines the starting point for the exploration for each agent. The agent then finds its own optimized point by a developed optimization technique, the Nelder–Mead method (Nelder and Mead, 1965). Each agent then passes the information regarding the optimized point by bee waggle dance. When all the information of optimized points is obtained, then the best among these is chosen by a consensus method, as in case of honey bee swarms (Seeley et al., 2006; Kumar et al., 2009).

Particle Search Methodology

For optimization of the any objective function, the Nelder–Mead method is modified (Kumar et al., 2009). Deterministic search methodology is used but in a sense similar to swarm local search. Let z = f(x, y) be the function that is to be minimized. For agents this is food function. To start we assume that agent considers three vertices of a triangle as food points for a two variables problem as z ₁, z ₂, and z ₃. z ₁ = (x ₁, y ₁) represents the initial position of agent z ₂ = (x ₂, y ₂) and z ₃ = (x ₃, y ₃) are the positions of probable food points (i.e., local optimal points). The movement of agents from its initial position toward the food position (i.e., optimization point) is as follows. Here we considered the problem as to generate the minima of a function z _i  = f(x _i , y _i ).

The function z _i  = f(x _i , y _i ) for i = 1, 2, 3 is evaluated at each of these three points. The obtained values of z _i are recorded in a way that z ₁ ≤ z ₂ ≤ z ₃ with corresponding agents positions and food points from the best to worst position. The construction process uses the midpoint of the line segment joining the two best food positions z ₁ and z ₂, as shown in Figure 1(a).

FIGURE 1 Agents search movements with the proposed optimization algorithm. (a) Starting of the motion in search of solution. (b) Extension in the direction of good optimal point. (c) Contraction of the movement in case optimal point quality is not good. (d) Shrinking of the space toward optimistic solution.

The value of function decreases as agent moves along z ₃ to z ₁ or z ₃ to z ₂. Hence, it is feasible that f(x, y) takes a smaller value if agent moves toward z ₁₂. For further movement of the agent a test point z _t is chosen in such a way that it is reflection of the worst food point (i.e., z ₃), as shown in Figure 1(a). The vector formula for z _t is

If the function value at z _t is smaller than the function value at z ₃, then the agent has moved in the correct direction toward minimum. Perhaps the minimum is just a bit further than the point z _t . So the line segment is extended further to z _e through z _t and z ₁₂. The point z _e is found by moving as additional distance d/2 along the line, as shown in Figure 1(b). If the function value at z _e is less than the function value at z _t , then the agent has found a better food point than z _t .

If the function value at z ₁₂ and z ₃ are the same, another point must be tested. Two test points are considered by the agent on the both sides of z ₁₂ at distance d/2, as shown in Figure 1(c).

The point of smaller value frames a new triangle with other two best points. If the function value at the two test points is not less than the value at z ₃, the points z ₂ and z ₃ must be shrunk toward z ₁, as shown in Figure 1(d). The point z ₂ is replaced with z ₁₂, and z ₃ is replaced with the midpoint of the line segment joining z ₁ and z ₃. Figure 2 shows the path trace by the agents and the sequences of triangles {T _k } converging to the optimal point for the objective function

FIGURE 2 Movement of the agents for a given problem.

The starting point in any search lattice plays a vital role in getting robust optimal solution. Kumar et al. (2009) concluded that the center of the lattice is a good starting point to get a better optimal solution.

Exploration

In MAS, all agents live in an environment (Wooldridge, 2002). An environment is organized in a structure, as shown in Figures 3-5. In the environment each agent is fixed on a lattice point and each circle represents an agent; the data in the circle represent the position of agent and the evaluated value of the function. The size and dimension of the lattice depends on the variables and search space.

FIGURE 3 Domain of the objective function with one independent parameter.

FIGURE 4 Domain of the objective function with two independent parameters.

FIGURE 5 Domain of the objective function with three independent parameters.

The value of the objective function depends on p number of independent parameters. Let the range of jth parameter ∊ [W _ji , W _jf ], where W _ji and W _jf represent the initial and final value of the parameter. Thus the complete domain of the objective function can be represented by a set of p number of axis. Each axis is in a different dimension and contains the total range of one parameter.

The next step is to divide each axis into smaller parts. Each part is known as a step. Let the jth axis be divided in n _j number of step each of length S _j , where j = 1 to p. This length S _j is known as step size for the jth parameter. The relationship between n _j and S _j can be given as

Hence, each axis is divided into their corresponding branches. If we take one branch from each axis, then these p number of branches constitute a p dimensional volume.

The total number of such volumes can be calculated as

The number of volumes indicates the number of agents going out for exploration. One point inside each volume is chosen as the starting point for the optimization, which in our approach is the midpoint of that volume. The midpoint of total cluster can be calculated as follows;

For an objective function having one independent parameter, the complete domain is given by a single axis, represented as h ₁. Here, each step gives us one volume.

Let us take the following values:

Therefore n ₁ = 5 and N _v  = 5. Thus five agents are sent for exploration. The starting point for each agent is the midpoint of each step, as shown in Figure 3.

For an objective function having two independent parameters, the complete domain is given by a set of two axes represented as h ₁ and h ₂. Let us take the following values:

Therefore n ₁ = 4, n ₂ = 4, and N _v  = 16. Thus 16 agents are sent for exploration, as shown in Figure 4. The starting point of each agent is the midpoint of each volume, which in this case are two-dimensional rectangles.

For an objective function with three independent parameters, the complete domain is given by a set of three axes represented as h ₁, h ₂, and h ₃. Let us take the following values:

Therefore n ₁ = 4, n ₂ = 3, n ₃ = 3 and N _v  = 36. Thus 36 agents are sent for exploration. The starting point for each agent is the midpoint of the corresponding volume, which in this case is 3-dimensional cuboid, as shown in Figure 5. Objective functions with more than three independent parameters can also be solved in the similar manner.

Bee Swarm-Based Decision Process

Honey bee swarms have a highly distributed decision-making process that they use for finding their next hive or a new source of food. Hundreds of bees out of thousands work as scout bees to start a search for the next possible site. Upon finding the site, scouts inform other bees by a waggle dance (Seeley et al., 2006). Discovered nest sites of sufficient quality are reported on the cluster via the scouts' waggle dance. Depending on the waggle dance by scout bees, quiescent bees get activated and decided to recruit or explore for nest site. If an uncommitted bee is not satisfied with any of the scout sites, then she can explore for new sites. When a bee advertises a site more than once, in every subsequent turn she decreases the strength of her dance by about 15 dance circuits. Once the quorum threshold reaches for any one of the sites, the bee starts piping signals that elicit heating by the quiescent bees in preparation for flight. There are two methods used by bee swarms to find out the best nest site, consensus and quorum (Seeley et al., 1991, 42). In consensus widespread agreement among the group is taken into account, whereas in quorum the decision for best site happens when a site crosses the quorum (threshold) value. In this article the consensus algorithm is used for finding out the optimum solution (i.e., best food site) (Kumar et al., 2009).

Waggle Dance

Here in the proposed algorithm the agents provide their individual optimal solution to the centralized systems, which then choose the preferable solution from the searched one. For optimal minimum cases it selects the best optimal solution, which can mathematically stated as

where f _i (X) represent the different search value obtained by an agent. Each of these points is recorded in a table known as optimum vector table X. X is a vector containing p number of elements. These elements contain the value of parameters at that point. So both the optimal solution value and the corresponding variable values are recorded. This record is known as Personal Best (i.e., Pbest in PSO). The function value changes according to the objective function requirement; that is, if the objective function is to be minimized, then the minimum function is used, and if we have to find maximize in an objective function, it will switch over to maximize function.

Consensus

Bee swarms use the consensus method to decide the best obtained or search value, and here we mimic this event and behavior by comparing the results obtained. Once exploration and waggle dance (transmission of data) is finished, the global optimized point is chosen by comparing the fitness values of all the optimized points in the optimum vector table (i.e., global best, gbest as in case of PSO). For minimization problems the point with the lowest fitness value is selected as the global optimized point. The global optimized point X _G is found by

ILLUSTRATIVE EXAMPLE AND COMPARISONS

For comparing the result of the system, a setup is designed, which has already been used by various authors (Mastorakis et al., 2003; Tsaia et al., 2009; Mladenov and Mastorakis, 2001; Swagatam and Konara, 2007). The desired amplitude response of the 2-D filter is given as

Figure 6 shows the desired amplitude response |M _d (w ₁, w ₂)|. The corresponding minimization constraint optimization problem in Eq. (2) is being written as

FIGURE 6 Desired amplitude responses |M(x ₁, x ₂)| at the design condition of p = 2.

subject to the constraints given by

having K = 1, 2 and N ₁ = 50, N ₂ = 50.

With the purpose of illustration, we have taken K = 2 for better comparison. Then, H(z ₁, z ₂) can be expressed from Eqs. (1) to (13). To implement the HMAPSO algorithm the M(w ₁, w ₂) is expressed in term of its constraint in Eq. (14a), where

And

In compact form the M(w ₁, w ₂) can be expressed as

where

Now the magnitude of M(w ₁, w ₂) can be expressed as

And Eq. (18) for constraint can be stated from Eq. (12) as

where K = 1, 2. Hence, the optimization problem comes as solving the equation optimizing at the cost of following constraint vector: x = (a ₀₀, a ₀₂, a ₀₁, a ₁₁, a ₂₀, a ₂₁, a ₂₂, b ₁, b ₂, c ₁, c ₂, d ₁, d ₂, H ₀) ^T .

For proving HMAPSO, a better and optimal approach compared the result with other competitive approaches, which are as follows: HTGA (Tsaia et al., 2009), which emphasizes over convergence of HTGA, and swarm intelligence algorithm, termed MEPSO (Swagatam and Konara, 2007), which uses PSO for designing 2-D zero-phase recursive filters, are two new methods for optimizing the x vector. The classical DE (Tsai et al., 2005) approach, which use binary crossover for GA, is also being compared. The G3 (generalized generation gap) model (Mladenov and Mastorakis, 2001), which incorporates the generic parent centric recombination scheme (PCX) and steady state, elite preserving, scalable, and computationally fast population alteration model of the GA results, is also compared. Others methods include neural method (Mladenov and Mastorakis, 2001), quasi-Newton method (Lu and Tzeng, 2009), and GA (Tsai et al., 2005). An optimal upshot is derived using HMAPSO represented in Eq. (19a). Its optimized constrained vector can be expressed as Eq. (19b):

For defining the space region, the first search is carried out using PSO, as explained in the algorithm. Once the exploration area is defined, different agents are sent to explore within their cavity. Each agent comes up with their individual optimal solutions within their search space. These individual solutions are examined using bee swarm decision method as explained in the algorithm. The algorithm is stated as follows:

1. Initialize the number of parameters, p. Initialize the length of steps (no of axes to be explored), S _j (j = 0 to p).

2. Initialize the range for each parameter as [W _ij , W _fj ] where j = 0, 1,…, p.

3. Calculate the number of steps in each step:

4. Calculate the total number of volumes:

5. For each volume, take the starting point of the exploration as the midpoint of the volume .

6. Explore the volume according to modified Nelder–Mead method.

7. Record the value of optimized point obtained corresponding to each volume in optimum vector table in the following way: [X ₁, X ₂,…, X _{N v} ].

8. After the exploration is completed, the global optimized point is calculated in the following manner using the bee decision approach:

Comparison between the optimal result of J with p = 2 uses different methods, with HMAPSO is performed, and the results are shown in Table 1. Figure 7 shows different method results. HTGA results are taken from Tsaia et al. (2009), and MEPSO, DE, and G3 with PCX results are taken from Mladenov and Mastorakis (2001), with p = 2. Quasi-Newton, neural network, and GA results are taken from Tsaia et al. (2009) for comparison with HMAPSO. Similarly, Table 2 shows time comparison between the methods, where the other results are taken from Tsaia et al. (2009). The result shows the robustness and stability of the HMAPSO for designing of 2-D IIR filter.

FIGURE 7 Comparison of amplitude responses |M(x ₁, x ₂)| by different methods.

TABLE 1 Computational Results for J by Using Different Methods

Method	Best	Average	Standard deviation
HMAPSO	1.586576	1.586576	0.00
HTGA (Tsaia et al. 2009)	2.8664	3.3888	0.2191
MEPSO (Mladenov and Mastorakis 2001)	9.0005	9.01665	0.221
DE (Mladenov and Mastorakis 2001)	11.907	12.1993	0.221
G3 with PCX	10.425	10.0673	0.221
Quasi-Newton (Lu and Tzeng 2009)	7.0810	NA	NA
Neural network (Mladenov and Mastorakis 2001)	3.7772	NA	NA
GA (Tsai et al. 2005)	6.0276	NA	NA

TABLE 2 Computational Time Results Using Different Agent Sizes

Agent Size	Best	Time
HMAPSO	1.586576	1.592468
HTGA (Tsaia et al. 2009)	2.8664	3.3888
Quasi-Newton (Lu and Tzeng 2009)	7.0810	NA
Neural network (Mladenov and Mastorakis 2001)	3.7772	NA
GA (Tsai et al. 2005)	6.0276	NA

To show heftiness of IIR filter so obtained using HMAPSO, it is applied in image processing. A defocused image is taken from Tsaia et al. (2009) for comparison, and Figure 8 shows the results after applying different filters. HMAPSO provides better upshot, which can be used for optimizing IIR filters.

FIGURE 8 Processing results of the designed filters for focusing the image.

CONCLUSION

Here we enumerate the HMAPSO approach to produce a highly optimized, 2-D, IIR digital, structure-specified filter. HMAPSO, due to its hybrid nature of multiagent approach, particle swarm tactics, and bee-based decision-making approach, is well suited for real-time multioptimization problems like 2-D IIR filter. IIR filter is first converted into a multiobjective optimization problem, which satisfies some constraints. The objective function is then solved. The performance of the proposed method was compared with that of a well-known available solution using conventional optimization algorithm, PSO algorithm, GA, and improved GA for the system identification purpose. From the simulation and experimental results, it was observed that the method based on the HMAPSO seems as an alternative approach for designing digital low- and high-order IIR filters. The results shows that HMAPSO removes the randomness in the algorithm and provides a better upshot as compared with its counterparts and improves significantly in global optimization performance of optimizing real-time optimization problems like IIR filter.