Extended approaches based on Genetic Algorithms (GAs) for MIMO singular systems approximation

Abstract

In this paper we present an extension of three important model reduction techniques: namely, the stability equation, the modified pole clustering and the dominant modes methods for conventional (regular) systems to reduce complexity relating to high dimensionality of mathematical models representing physical, generalized (also called singular) systems. Combining these methods to Genetic Algorithms’ tools and exploiting a special representation base where a full order singular system is deflating into proper and improper subsystems, different natures of stable, optimal low order models are obtained. To show the effectiveness of the proposed algorithms, a numerical example is given, where six approximants are derived from a multi-input multi-output singular system. By the use of two optimal norms, the MOR errors are quantified and permits to conclude to the quality of the proposed reduced order models.

Keywords

Singular system model order reduction (MOR)Genetic Algorithms (GAs)stability equation modified pole clustering dominant modes norms ISE stability

Introduction

Developing reduced models that approximate complex systems is necessary because model reduction decreases the simulation time in comparison with the original high order model. It enables real time applications, and produces acceptable accuracy. The genetic algorithms have been widely used in control engineering because of its popularity to provide answers to the limitations of more conventional methods (Hongxing et al., 2005). This tool is essentially exploited to solve the optimization problem (Grefenstette, 2007) in different fields of applications mainly because of their ability to find the optimal solution or to provide a solution close to the global minimum unlike other mathematical method used on the minimization terms. The Genetic Algorithm employs search procedures based on mechanics of natural selection and survival of the fittest (Habib and Prasad, 2008). Our main contribution is to exploit and extend some important tools based on the Model Order Reduction (MOR) of standard (also called conventional/regular) state space systems: namely, the stability equation (Parmar et al., 2007), the modified cluster methods (Kumar and Tiwari, 2012), dominant modes (Rommes and Martins, 2006), combined with Genetic Algorithms’ (GAs) tools and evaluated for stable, linear, continuous-time invariant, multi-input multi-output (MIMO), singular systems (also called generalized state space systems or descriptor systems) model reduction.

The main step is the decomposition of original singular systems on the Weierstrass canonical form (Adamou-Mitiche et al., 2003). Based on Adamou-Mitiche et al. (2007), the optimal low order models are constructed as follows: According to each specified algorithm presented in this work, the reduced order denominators are determined in a specified manner. The reduced order numerators are identified by GA’s tools (Vilbe and Calvez, 1990). Each algorithm gives two low models of different natures: singular when only the singular system proper part model reduction is considered, but the improper part is entirely copied; and nonsingular when the proper and improper parts are subject to model reduction. To effectively estimate the obtained reduced order models, some norms are calculated and different responses are traced.

A brief description of GA’s MOR principal is presented in the second section. The two important MOR-based GA techniques are introduced: namely, the stability equation and the modified pole clustering methods, and the proposed approach is presented. In the third section, after a statement of the problem position of any singular system model reduction scheme, a procedure for constructing a different low order model for singular systems is presented, followed by an illustrative example that allows us to draw some important conclusions.

GA-based MOR

The essence of all GA’s techniques in regular MOR systems is stated as follows. Starting with an original system of full order n, represented by its transfer function $G_{n} (s)$ , given as

G_{n} (s) = \frac{N (s)}{D (s)} = \frac{a_{0} + a_{1} s + a_{2} s^{2} + \dots + a_{n - 1} s^{n - 1}}{b_{0} + b_{1} s + b_{2} s^{2} + \dots + b_{n} s^{n}}

(1)

where $a_{i}$ , $i = \bar{0, n - 1}$ are the numerator coefficients, and $b_{i}$ , $i = \bar{0, n}$ are the denominator coefficients. An approximant of low-order r represented by its transfer function $G_{r} (s)$ , given as

G_{r} (s) = \frac{\hat{N} (s)}{\hat{D} (s)} = \frac{c_{0} + c_{1} s + c_{2} s^{2} + \dots + c_{r - 1} s^{r - 1}}{d_{0} + d_{1} s + d_{2} s^{2} + \dots + d_{r} s^{r}}

(2)

where $c_{i}, i = \bar{0, r - 1}$ are the numerator coefficients and $d_{i},$ $i = \bar{0, r}$ are the denominator coefficients, is constructed according to two major steps. The first one is the reduced-order system denominator construction achieved according a chosen algorithm, while the second step is the reduced-order system numerator determination by means of the GA’s tools.

Stability equation technique and GA-based MOR

The reduced order model is calculated using the step-by-step procedure.

Input: The full order transfer function model (1), and the reduced order r.

Step 1: Compute the denominator of the low order system using the stability equation technique Therapos (1983). For stable $G_{n} (s)$ , the n order system is divided into even and odd parts, Chen et al. (1980) as

\begin{matrix} D (s) = \sum_{i = 0}^{n} b_{i} s^{i} \\ D (s) = D_{e} (s) + D_{o} (s) \\ ↙ ↘ \\ The even part The odd part \end{matrix}

(3)

where

D_{e} (s) = \sum_{i = 0, 2, 4}^{n} b_{i} s^{i} = b_{0} Π_{i = 1}^{m_{1}} (1 + \frac{s^{2}}{z_{i}^{2}})

(4)

D_{o} (s) = \sum_{i = 1, 3, 5}^{n} b_{i} s^{i} = b_{1} s Π_{i = 1}^{m_{2}} (1 + \frac{s^{2}}{p_{i}^{2}})

(5)

with $m_{1}$ , $m_{2}$ being the integer parts of $\frac{n}{2}$ and $\frac{n - 1}{2}$ , respectively.

The coefficients $z_{i}$ and $p_{i}$ are the roots of the even and odd equations, respectively.

By rejecting the factors with the largest magnitudes of $z_{i}^{2}$ and $p_{i}^{2}$ on $(4, 5)$ , the even and the odd parts of the low order reduced order system are stated as

D_{e}^{r} (s) = \sum_{i = 0, 2, 4}^{r} b_{i} s^{i} = b_{0} Π_{i = 1}^{m_{3}} (1 + \frac{s^{2}}{z_{i}^{2}})

(6)

D_{o}^{r} (s) = \sum_{i = 1, 3, 5}^{r} b_{i} s^{i} = b_{1} s Π_{i = 1}^{m_{4}} (1 + \frac{s^{2}}{p_{i}^{2}})

(7)

where $m_{3}$ , $m_{4}$ are the integer parts of $\frac{r}{2}$ , and $\frac{r - 1}{2}$ , respectively. Combining these equations, the normalized reduced denominator is given as

D_{r} (s) = D_{e}^{r} (s) + D_{o}^{r} (s)

(8)

This step is summarized in Figure 1.

Step 2: Determination of the low order numerator coefficients by minimization of the objective function J Vilbe and Calvez (1990)

J = \int_{0}^{\infty} (y (t) - y_{r} (t))^{2} dt

(9)

where $y (t)$ and $y_{r} (t)$ are the unite impulse responses of the original and reduced system, respectively.

Output: The reduced order transfer function model (2) is then constructed.

The typical parameters of GA are taken according to Table 1 (Pal et al., 1995).

Table 1.

Typical parameters for the genetic algorithm.

Parameter	Type or value
Number of generation	200
Selection	Stochastic
Population size	50
Mutation	Gaussian
Crossover function	Arithmetic

Modified pole clustering technique and GA-based MOR

The reduced order model is calculated using the step-by-step algorithm.

Input: The full order transfer function model (1), and the reduced order r.

Step 1: Compute the denominator of the low order approximant using the modified pole clustering technique (Pal et al., 1995; Vishwakarma and Prasad, 2009).

Let the k real poles in the ith cluster be defined as $p_{1}, p_{2}, \dots p_{k}$ , where $| p_{1} | < | p_{2} | \dots < | p_{k} |$ .

The centroid cluster $p_{ei}$ can be obtained by using the modified pole clustering algorithm presented as below. Let m pairs of complex conjugate poles in a jth cluster be

[(α_{1} \pm j β_{1}), (α_{2} \pm j β_{2}), \dots, (α_{m} \pm j β_{m})]

(10)

Using the same algorithm separately for real and imaginary parts of the complex conjugate poles, the centroid cluster is obtained as

ϕ_{ej} = A_{ej} + j B_{ej}

(11)

To achieve that, a procedure is given as below.

Let k the number of the real poles in a cluster be given as $| p_{1} | < | p_{2} | \dots < | p_{k} | .$

Set $j = 1 .$

Find the centroid cluster pole as

c_{j} = (\sum_{i = 1}^{k} (\frac{- 1}{| p_{i} |}) / k)^{- 1}

(12)

Set $j = j + 1 .$

Find the new centroid cluster from

c_{j} = ((\frac{- 1}{| p_{i} |} + \frac{- 1}{| c_{j - 1} |}) / 2)^{- 1}

(13)

Is $k = j ?$ If not go to 4 otherwise go to 7.

Take a modified centroid cluster of the rth cluster as

p_{er} = c_{j}

(14)

For synthesizing the common denominator polynomial, one of the following cases may occur.

Case 1. If all the new centroid clusters are real, then the reduced model denominator of order r is

D_{r} (s) = Π_{i = 1}^{r} (s - p_{ei})

(15)

Case 2. If all the new centroid clusters are complex conjugate, then the reduced model denominator of order r order reduced model is

D_{r} (s) = \prod_{i = 1}^{\frac{r}{2}} (s - {\hat{ϕ}}_{e i}) (s - {\overset{⌣}{ϕ}}_{e i})

(16)

where

{\hat{ϕ}}_{er} = A_{er} + j B_{er}

(17)

{\overset{⌣}{ϕ}}_{e r} = A_{e r} - j B_{e r}

(18)

Case 3. If some centroid clusters are real and some are complex conjugate, then the reduced model denominator of order r order reduced model is

D_{r} (s) = \prod_{i = 1}^{\frac{r - 2}{2}} (s - p_{e i}) (s - {\hat{ϕ}}_{e 1}) (s - {\overset{⌣}{ϕ}}_{e 1})

(19)

Step 2: The same as Step 2 of the stability equation MOR.

Output: The reduced order transfer function (2) is then built.

The proposed approach: Dominant modes combined GA

This method is constructed essentially from the idea of retaining the faster modes of the full order system combined to GA’s. Simplicity, accuracy and speed of calculating the reduced order proposed approximant are guaranteed, since it does not require any mathematical skills. As a result, the low order system behaviour fits adequately the original one. The reduced order model is calculated using the step-by-step procedure.

Input: The full order transfer function model (1), and the reduced order r.

Step 1: Select the r faster modes $p_{i}, i = \bar{1, r},$ of the full system and calculate the reduced order denominator

D_{r} (s) = Π_{i = 1}^{r} (s - p_{i})

(20)

Step 2: The same as Step 2 of the stability equation MOR.

Output: The reduced order transfer function model (2) is then constructed.

Descriptor model reduction

Problem formulation

Consider a linear continuous-time, (m_inputs, p_outputs) MIMO, stable, singular system, of full order n given by the generalized state space matrices $(E, A, B, C, D)$ , as follows

G (s) = [\begin{matrix} sE - A & B \\ C & D \end{matrix}]

(21)

where $E, A \in R^{n \times n}$ , $B \in R^{n \times m}$ , and $C \in R^{p \times n}$ are constant matrices, with E singular. Assume that the pencil $λ E - A$ is regular (Adamou-Mitiche et al., 2003).

The goal of any singular model reduction approach is to replace the original system of complete order n (21) by a reduced model of order r (22) given by the generalized state space $(E_{r}, A_{r}, B_{r}, C_{r}, D_{r})$

G_{r} (s) = [\begin{matrix} s E_{r} - A_{r} & B_{r} \\ C_{r} & D_{r} \end{matrix}]

(22)

The system $(22)$ must preserve the essential properties of the initial system (21), like stability, and a smaller approximation error.

The algorithm

The proposed MOR algorithm produces two natures of reduced models. The first reduced model $H_{r}$ is modelled by the generalized state space matrices ( $E_{r 1}, A_{r 1}, B_{r 1}, C_{r 1}, D_{r 1}$ ), is the result of an order reduction carried out only on the proper part of the singular original system, the improper part is entirely copied, while the reduced-order model $H_{rr}$ , coming from the second approach, and is represented by the realization $(E_{r 2}, A_{r 2}, B_{r 2}, C_{r 2}, D_{r 2})$ . It is obtained from the simultaneous reduction of the proper and improper parts.

These two reduced models $H_{r}$ and $H_{rr}$ are computed as follows.

Input: The state space matrices $(E, A, B, C, D)$ of the singular system (21) such that $λ E - A$ is regular and stable.

Step 1: Transform E and A to the Generalized UPper TRIangular (GUPTRI) form (Demmel and Kangstrom, 1993)

E = V [\begin{matrix} E_{n_{f}} & E_{u} \\ 0 & E_{n_{\infty}} \end{matrix}] U^{T}

(23)

A = V [\begin{matrix} A_{n_{f}} & A_{u} \\ 0 & A_{n_{\infty}} \end{matrix}] U^{T}

(24)

where $E_{n_{f}}$ is upper triangular, nonsingular and $E_{n_{\infty}}$ is upper triangular with zeros on the diagonal, $A_{n_{f}}$ is upper quasi-triangular and $A_{n_{\infty}}$ is upper triangular, nonsingular and compute the solutions Y and Z of the generalized Sylvester equation (Adamou-Mitiche et al., 2007)

E_{n_{f}} Y - Z E_{n_{\infty}} = - E_{u}

(25)

A_{n_{f}} Y - Z A_{n_{\infty}} = - A_{u}

(26)

Step 2: Construct

V^{T} B = [\begin{matrix} B_{n_{f}} \\ B_{n_{\infty}} \end{matrix}]

(27)

CU = [\begin{matrix} C_{n_{f}} & C_{n_{\infty}} \end{matrix}]

(28)

that permit to form the proper nonsingular transfer matrix

G = [\begin{matrix} E_{n_{f}}^{- 1} A_{n_{f}} & E_{n_{f}}^{- 1} B_{n_{f}} \\ C_{n_{f}} & D \end{matrix}]

(29)

Step 3: Construct the reduced order models according to the specified MOR algorithm given in the previous section.

Step 4: Since $A_{n_{\infty}}$ is nonsingular, consider the improper part $(E_{n_{\infty}}, A_{n_{\infty}}, B_{n_{\infty}}, C_{n_{\infty}})$ , and transform it into a nonsingular, discrete-time system (Adamou-Mitiche et al., 2007)

\begin{matrix} A_{n_{\infty}} q (k + 1) & = & E_{n_{\infty}} q (k) + B_{n_{\infty}} η (k) \\ γ (k) & = & C_{n_{\infty}} q (k) \end{matrix}

(30)

Use its continuous equivalent system represented by its transfer function and use the same operations as in Step 3. The proposed method gives a reduced model $(E_{\infty r}, A_{\infty r}, B_{\infty r}, C_{\infty r})$ of the improper model.

Output: The two reduced-order state-space descriptor systems $H_{r}$ and $H_{rr}$ are given by (31) and (32) respectively

H_{r} = [\begin{matrix} s E_{r 1} - A_{r 1} & B_{r 1} \\ C_{r 1} & D_{r 1} \end{matrix}]

(31)

where

\begin{matrix} s E_{r 1} - A_{r 1} = diag [s E_{fr} - A_{fr}, s E_{\infty r} - A_{\infty r}] \\ B_{r 1} = [B_{fr}, B_{\infty r}]^{T}, C_{r 1} = [C_{fr}, C_{\infty r}], D_{r 1} = D \\ H_{rr} = [E_{r 2}, A_{r 2}, B_{r 2}, C_{r 2}, D_{r 2}] \end{matrix}

(32)

Remark: Note that even if no model reduction occurs in (Step 4), the approximant $H_{rr}$ corresponds always to a nonsingular system.

Simulation comments

A simulation example is presented in this section. For each technique, the order reduction is occurs firstly on the proper part of the two-inputs/two-outputs singular system, and after on the twice parts of the original system. To solve the generalized Sylvester equation use the package SLICOT (Benner et al., 1999). Consider a 16th-order singular system where $n_{f} = 6$ and $n_{\infty} = 10$ . The typical parameters for the genetic algorithm are given in Table 1. The proposed algorithm computes different optimal reduced-order models $H_{r}$ and $H_{rr}$ , for $l_{f} = 2$ , and $l_{\infty} = 2$ . The approximant $H_{r}$ is singular of order $r 1 = 12$ , but $H_{rr}$ is nonsingular of order $r 2 = 4$ , and both are stable. Figures 2 and 4, show the ( $1 st I / 1 st O$ ) magnitude response in dB and the impulse responses, respectively, of the original singular system and its three approximants of order 12, where only the proper part is reduced. In Figures 3 and 5, the ( $1 st I / 1 st O$ ) magnitude responses in dB and the impulse responses, respectively, of the original singular system and its three approximants of order 4 are traced, where both the proper and improper parts are reduced. In Figure 6, the frequency response error in dB, for the $1 st I / 1 st O$ channel, for the reduced-order model $H_{rr}$ is presented. Similar results are obtained for the other channels. These plots show that the stability is always guaranteed for the reduced order models $H_{r}$ and $H_{rr}$ , and how well all the approximants fit the original system behaviour with a not significant error. This is confirmed by a measure of the closeness of each low order model to the original system is computed in terms of the $H_infinity$ error norm (for each subsystem) (see Tables 2 –4). In the time domain, another measure of the approximation performance, the Integral Square Error (ISE) (see 9), is achieved (see Table 5). From the resulting responses and different measures, we can easily conclude that the time and frequency behaviour of the initial system and its approximants are very close, and the errors are very small, but the best MOR goes to the dominant modes combined GAs (see Tables 2 –4; for the lowest ISE see Table 5).

Table 2.

Estimated norm error of the two reduced-order models via the proposed approach.

$I / O$	$sup_{ω \in R} \| \| H (j ω) - H_{r} (j ω) \| \|_{\infty}$	$sup_{ω \in R} \| \| H (j ω) - H_{rr} (j ω) \| \|_{\infty}$
1/1	0.0642	0.0787
1/2	0.6000	0.6932
2/1	0.5000	0.5037
2/2	0.1129	0.1140

Table 3.

Estimated norm error of the two reduced-order models via the modified cluster approach.

$I / O$	$sup_{ω \in R} \| \| H (j ω) - H_{r} (j ω) \| \|_{\infty}$	$sup_{ω \in R} \| \| H (j ω) - H_{rr} (j ω) \| \|_{\infty}$
1/1	0.0668	0.0808
1/2	0.6001	0.6933
2/1	0.5000	0.5037
2/2	0.1380	0.1390

Table 4.

Estimated norm error of the two reduced-order models via the stability approach.

$I / O$	$sup_{ω \in R} \| \| H (j ω) - H_{r} (j ω) \| \|_{\infty}$	$sup_{ω \in R} \| \| H (j ω) - H_{rr} (j ω) \| \|_{\infty}$
1/1	0.1669	0.1731
1/2	0.6001	0.6932
2/1	0.5001	0.5038
2/2	0.1782	0.1771

Table 5.

ISE values.

$H_{r}$ Subsystems	Proposed method	Stability method	Cluster method
$r_{11} (s)$	$3.25991 \times 10^{- 3}$	$11.72507 \times 10^{- 3}$	$5.19828 \times 10^{- 3}$
$r_{12} (s)$	$27.05108 \times 10^{- 3}$	$25.21817 \times 10^{- 3}$	$24.40447 \times 10^{- 3}$
$r_{21} (s)$	$17.901257 \times 10^{- 3}$	$23.84915 \times 10^{- 3}$	$21.65958 \times 10^{- 3}$
$r_{22} (s)$	$6.4574387 \times 10^{- 3}$	$17.88279 \times 10^{- 3}$	$10.02560 \times 10^{- 3}$
$H_{rr}$ Subsystems	Proposed method	Stability method	Cluster method
$r_{11} (s)$	$3.85632 \times 10^{- 3}$	$11.58018 \times 10^{- 3}$	$5.42949 \times 10^{- 3}$
$r_{12} (s)$	$37.24307 \times 10^{- 3}$	$29.78637 \times 10^{- 3}$	$29.39316 \times 10^{- 3}$
$r_{21} (s)$	$16.43334 \times 10^{- 3}$	$23.84915 \times 10^{- 3}$	$21.83992 \times 10^{- 3}$
$r_{22} (s)$	$8.52738 \times 10^{- 3}$	$17.83778 \times 10^{- 3}$	$9.94305 \times 10^{- 3}$

Conclusion

In this paper, based on the canonical forms of Adamou-Mitiche et al. (2003) for a continuous-time, original, singular system of full order n, three MOR techniques are extended to the approximation of singular systems using GA’s tools: namely, the stability equation, the modified cluster method and the proposed approach – dominant mode combined GA. Each approach gives two different approximants: in the first, only the proper part (corresponding to the finite eigenvalues of the pencil $λ E - A$ ) is reduced; and the improper part (corresponding to the infinite eigenvalues of the pencil) is fully preserved. The second approach offers an interesting characterization since it is described by a nonsingular state-space realization. For the two reduced-order models stability is always guaranteed and the distance between the original model and its approximants can be measured. Different time and frequency responses are traced and several norms are calculated (Glover, 1984; Kohler, 2014). This allows us to conclude the quality of our approximants and the superiority of our proposed approach, besides its ease of use, simplicity of implementation, and the significant advantage in execution time and its advantage of not requiring any computation effort compared to the stability and modified cluster techniques.

Footnotes

Acknowledgements

The authors are very indebted to the anonymous reviewers for their constructive comments that have helped greatly improve the quality of the paper.

Conflict of Interest Statement

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

References

Adamou-Mitiche

ABH

Mitiche

Sima

(2003) Descriptor systems approximation. International Journal of General Systems 33(1): 99–110.

Adamou-Mitiche

ABH

Mitiche

Haddadi

(2007)) MIMO-descriptor system model reduction. International Journal of Modelling and Simulation 27(3): 226–232.

Benner

Mehrmann

Sima

et al . (1999) SLICOT – A subroutine library in systems and control theory. In: Datta

(ed.) Applied and Computational Control, Signals, and Circuits. Boston, MA: Birkhauser, 499–539.

Chen

Chang

Han

(1980) Stable reduced order Padé approximants using stability equation method. Electronic Letters 16(9): 345–346.

Demmel

Kagstrom

(1993) The generalized Schur decomposition of an arbitrary pencil A−λ B: Robust software with error bounds and applications. Part I: Theory and algorithms. ACM Transactions on Mathematical Software 19(2): 160–174.

Glover

(1984) All optimal Hankel approximations of linear multivariable systems and their L^∞-errors bounds. International Journal of Control 39(6): 1115–1193.

Grefenstette

(2007) Optimization of control parameters for genetic algorithms systems. IEEE Transactions on Man and Cybernetics 16: 122–128.

Habib

Prasad

(2008) An observation on the differentiation and modified Cauer continued fraction expansion approaches of model reduction technique In: XXII National systems Conference, 17–19 December 2008, pp. 574–579. India: IIT Roorkee Engineering Systems Society of India.

Hongxing

Jinshi

Hongshu

(2005) Model reduction using the genetic algorithm and Routh approximations. Journal of Systems Engineering and Electronics 16: 632–639.

10.

Kohler

(2014) On the closest stable descriptor system in the respective spaces RH₂ and RH_∞. Linear Algebra and its Applications 443: 34–49.

11.

Kumar

Tiwari

(2012) Clustering method for reducing order of linear system using factor division algorithm. International Journal of Applied Information Systems 3(5): 1–4.

12.

Pal

Sinha

(1995) Reduced order modeling using pole-clustering and time-moment matching. Journal of the Institute of Engineers 76: 1–6.

13.

Parmar

Prasad

Mukherjee

(2007) Order reduction of linear dynamic systems using stability equation method and GA. International Journal of Computer, Information, and Systems Science, and Engineering 1(1): 26–32.

14.

Rommes

Martins

(2006) Efficient computation of transfer function dominant poles using subspace acceleration. IEEE Transactions on Power Systems 21(3): 1218–1226.

15.

Therapos

(1983) Stability equation method to reduce the order of fast oscillating systems. Electronic Letters 19(5): 183–184.

16.

Vilbe

Calvez

(1990) On order reduction of linear systems using an error minimization technique. Journal of Franklin Institute 327: 513–514.

17.

Vishwakarma

Prasad

(2009) MIMO system reduction using modified pole clustering and genetic algorithm. Modelling and Simulation in Materials Science and Engineering 2009(2009): 1–5.