FIR Filter Design via Linear Complementarity Problem, Messy Genetic Algorithm, and Ising Messy Genetic Algorithm

In this paper the design of maximally flat linear phase finite impulse response (FIR) filters is considered. The problem is handled with totally two different approaches. The first one is completely deterministic numerical approach where the problem is formulated as a Linear Complementarity Problem (LCP). The other one is based on a combination of Markov Random Fields (MRF's) approach with messy genetic algorithm (MGA). Markov Random Fields (MRFs) are a class of probabilistic models that have been applied for many years to the analysis of visual patterns or textures. Our objective is to establish MRFs as an interesting approach to modeling messy genetic algorithms. We establish a theoretical result that every genetic algorithm problem can be characterized in terms of a MRF model. This allows us to construct an explicit probabilistic model of the MGA fitness function and introduce the Ising MGA. Experimentations done with Ising MGA are less costly than those done with standard MGA since much less computations are involved. The least computations of all is for the LCP. Results of the LCP, random search, random seeded search, MGA, and Ising MGA are discussed.

Authors:

• A.M. Al-Fahed Nuseirat
• R. Abu-Zitar

Keywords:

• Filter design
• FIR digital filters
• LCP
• Ising model
• MGA
• Ising MGA.

References:

[1] L. R. Rabiner, "The Design of Finite Impulse Response Digital Filters
using Linear Programming Techniques", Bell Syst. Tech. J., 51, 1117-1198, 1972.
[2] P. P. Vaidyanathan and T. Q. Nguyen, "Eigenfilters: A New Approach to Least-Square FIR Filter Design and Applications Including Nyquist
Filters", IEEE Trans. Circuits Syst., CAS-34 (1), 11 - 23, 1987.
[3] G. W. Medlin, J. W. Adams, and C. T. Leondes, "Lagrange Multiplier
Approach to the Design of FIR Filters for Multirate Applications", IEEE
Trans. Circuits Syst., 35, 1210 - 1219, 1988.
[4] M. H. Er and C. K. Siew, "Design of FIR Filters Using Quadratic Programming Approach", IEEE Trans. Circuits Syst. II, 42 (3), 217 -
220, 1995.
[5] E. Gislason, M. Johansen, K. Conradsen, B. K. Erboll, and S. K.
Jacobsen, "Three Different Criteria for the Design of 2-D Zero-Phase
FIR Digital Filters", IEEE Trans. Signal Processing, 41, 3070 -3074,1993.
[6] Y. C. Lim, J. H. Lee, C. K. Chen, and R. H. Yang, "A Weighted Least
Square Algorithm for Quasi-Equiripple FIR and IIR Digital Filter Design", IEEE Trans. Signal Processing, 40, 551 -558, 1992.
[7] C. -H. Hseih, C. -M. Kuo, Y. -D Jou, and Y. L. Han, "`Design of Two-
Dimensional FIR Digital Filters by Two-Dimensional WLS Technique",,
IEEE Trans. Circuits Syst. II, 44, 348 - 358, 1997.
[8] V. R. Algazi, M. Suk, and C. -S. Rim, "Design of Almost Minimax FIR
Filters in One and Two Dimensions by WLS Technique", IEEE Trans.
Circuits Syst., CAS-33, 590 - 596, 1986.
[9] M. Lang, I. W. Selesnick, and C. S. Burrus, "Constrained Least Squares
Design of 2-D FIR Filters", IEEE Trans. Signal Processing, 44, 1234 -
1241, 1996.
[10] W. P. Zhu, M. O. Ahmad, and M. N. S. Swamy, "A Closed-Form
Solution to the Least-Square Design Problem of 2-D Linear-Phase FIR
Filters", IEEE Trans. Circuits Syst. II, 44, 1032 - 1039, 1997.
[11] K. C. Haddad, H. Stark, and Nickolas P. Galatsanos, "Constrained FIR
Filter Design by the Method of Vector Space Projection", IEEE Trans.
Circuits Syst. II, 47, 714 - 725, 2000.
[12] W. P. Zhu, "Weighted Least-Square Design of FIR Filters Using a Fast
Iterative Matrix Inversion Algorithm", IEEE Trans. Circuits Syst. I, 41
(11), 1620 - 1628, 2002.
[13] Magdy T. Hanna, "Design of Linear Phase FIR Filters with a Maximally
Flat Passband", IEEE Trans. Circuits Syst. II, 43 (2), 142 - 147, 1996.
[14] J. Besag, "Spatial interaction and the statistical analysis of lattice
systems (with discussions)", J. of the Royal Statistical Society, 36, 192 -
236, 1974.
[15] D. F. Brown, A. B. Garmendia-Doval, and J. A. W. McCall, "A genetic
algorithm framework using Haskell", Proc. of the 2nd Asia-Pacific
Conference on Genetic Algorithms, Global Link Publishing, May 2000.
[16] D. F. Brown, A. B. Garmendia-Doval, and J. A. W. McCall, "A
functional frame-work for the implementation of genetic algorithms:
comparing Haskell and Stan-dard ML.", In S. Gilmore, editor, Trends in
Functional Programming, volume 2, pp., 27 - 37, Portland, Oregon.
Intellect Books, 1999.
[17] H. Derin, and P. A. Kelly, "Discrete-index Markov-type random fields",
Proc. of the IEEE, 77, 1485 - 1510, 1989.
[18] S. Z. Li, Markov Random Field Modelling in Computer Vision, Springer,
1995.
[19] N. Metropolis, "Equations of state calculations by fast computational
machine", J. of Chemical Physics, 21, 1087 - 1091, 1953.
[20] M. Mitchell, J. H. Holland, and S. Forrest, "When will a genetic
algorithm outper-form hillclimbing?", In J. D. Cowan, G. Tesauro, and J.
Alspector, editors, Advances in Neural Information Processing Systems
6. Morgan Kaufmann, 1994.
[21] M. Pelikan, and D. E. Goldberg, "Research on theBayesian Optimization
Algorithm", Technical Report 2000010, Illinois Genetic Algorithms
Lab, UIUC, Urbana, IL, 2000.
[22] M. Pelikan, D. E. Goldberg, and E. Cant'u-Paz, "BOA: The Bayesian
Optimization Algorithm", In W. Banzhaf et al., editor, Proc. of the
Genetic and Evolution-ary Computation Conference (GECCO99),
volume I, pp., 525 - 532, San Fransisco, CA. Morgan Kaufmann
Publishers, 1999.
[23] M. Pelikan, D. E. Goldberg and F. Lobo, "A survey of optimization by
building and using probabilistic models", Technical Report 99018,
Illinois Genetic Algorithms Lab, UIUC, Urbana, IL, 1999.
[24] C.-T. Chen, Digital Signal Processing: Spectral Compuattion and Filter
Design, Oxford Univ. Press, New York, 2001.
[25] E. C. Ifeachor and B. W. Jervis , Digital Signal Processing: A Practical
Approach, Addison - Wesley, 1993.
[26] K. G. Murty, Linear Complementarity: Linear and Nonlinear
Programming, Berlin: Heldermann Verlag, 1988.
[27] B. H. Ahn, "Solution of Nonsymmetric Linear Complementarity
Problems by Iterative Methods", J. of Optimization Theory and
Applications, 33(2), 175 - 185, 1981.