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

Authors: A.M. Al-Fahed Nuseirat, R. Abu-Zitar

Abstract:

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.

Keywords: Filter design, FIR digital filters, LCP, Ising model, MGA, Ising MGA.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058435

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.