access icon free Adaptive genetic algorithm-based approach to improve the synthesis of two-dimensional finite impulse response filters

The design of finite impulse response (FIR) filters can be formulated as a non-linear optimization problem reputed to be difficult for conventional approaches. The constraints are high and a large number of parameters have to be estimated, especially when dealing with two-dimensional FIR filters. In order to improve the performance of conventional approaches, the authors explore several stochastic methodologies capable of handling large spaces. The authors specifically propose a new genetic algorithm (GA) in which some innovative concepts are introduced to improve the convergence and make its use easier for practitioners. The algorithm is globally improved by adapting the mutation and crossover and selection operators with the genetic advances. A dynamic ranking selection scheme is introduced to limit the promotion of extraordinary chromosomes. A refreshing mechanism is investigated to manage the trade-off between diversity and elitism. The key point of the proposed approach stems from the capacity of the GA to adapt the genetic operators during the genetic life while remaining simple and easy to implement. Most of the parameters and operators are changed by the GA itself. From an initial calibration, the GA performs the design problem while calibrating and repeatedly re-calibrating itself for solving it. The authors demonstrate on various cases of filter design a significant improvement in performance.

Inspec keywords: FIR filters; genetic algorithms; nonlinear programming; two-dimensional digital filters

Other keywords: selection operator; dynamic ranking selection scheme; crossover operator; nonlinear optimization problem; mutation operator; 2D finite impulse response filters; adaptive genetic algorithm-based approach; 2D FIR filters; genetic life; convergence improvement

Subjects: Optimisation techniques; Signal processing theory; Filtering methods in signal processing; Digital signal processing; Optimisation techniques

References

    1. 1)
    2. 2)
    3. 3)
    4. 4)
    5. 5)
    6. 6)
    7. 7)
    8. 8)
      • 35. Ros, F., Guillaume, S.: ‘An efficient nearest classifier’, Hybrid Evolutionary Systems, Studies in Computational Intelligence, Springer Verlag, 2007, 75, pp. 131147.
    9. 9)
    10. 10)
    11. 11)
    12. 12)
    13. 13)
    14. 14)
    15. 15)
    16. 16)
    17. 17)
    18. 18)
    19. 19)
    20. 20)
    21. 21)
    22. 22)
    23. 23)
    24. 24)
    25. 25)
    26. 26)
    27. 27)
    28. 28)
    29. 29)
    30. 30)
    31. 31)
    32. 32)
    33. 33)
    34. 34)
    35. 35)
    36. 36)
    37. 37)
    38. 38)
      • 32. Reeves, C.R.: ‘A genetic algorithm for flowshop sequencing’, Comput. Oper. Res., 1995, 22, (1), pp. 513 (doi: 10.1016/0305-0548(93)E0014-K).
    39. 39)
      • 29. Akramifar, S.A., Ghassem-Sani, G.: ‘Fast forward planning by guided enforced hill climbing’, Elsevier Eng. Applic. Artif. Intell., 2010, 23, pp. 13271339 (doi: 10.1016/j.engappai.2010.03.006).
    40. 40)
      • 13. Tzeng, S.-T.: ‘Design of 2-D FIR digital filters with specified magnitude and group delay responses by GA approach’, Signal Process., 2007, 87, pp. 20362044 (doi: 10.1016/j.sigpro.2007.01.034).
    41. 41)
      • 35. Ros, F., Guillaume, S.: ‘An efficient nearest classifier’, Hybrid Evolutionary Systems, Studies in Computational Intelligence, Springer Verlag, 2007, 75, pp. 131147.
    42. 42)
      • 33. Holland, J.H.: ‘Genetic algorithms and the optimal allocation of trials’, SIAM J. Comput., 1973, 2, (2), pp. 88105 (doi: 10.1137/0202009).
    43. 43)
      • 21. Boeringer, D.W., Werner, D.H., Machuga, D.W.: ‘A simultaneous parameter adaptation scheme for genetic algorithms with application to phased array synthesis’, IEEE Trans. Antennas Propag., 2005, 53, pp. 356371 (doi: 10.1109/TAP.2004.838800).
    44. 44)
      • 11. Lu, H.C., Yeh, K.H.: ‘2-D FIR filters design using least square error with scaling-free McClellan transformation’, IEEE Trans. Circuits Syst., II, 2000, 47, pp. 11041107 (doi: 10.1109/82.877153).
    45. 45)
      • 39. Shyu, J.J., Pei, S.-C.: ‘A generalized approach to the design of variable fractional-delay FIR digital filters’, Elsevier Signal Process., 2008, 88, pp. 14281435 (doi: 10.1016/j.sigpro.2007.12.009).
    46. 46)
      • 43. Speake, T.C., Mersereau, R.M.: ‘A note on the use of windows for two-dimensional FIR filter design’, IEEE Trans. Acoust. Speech Signal Process., 1981, ASSP-29, (1), pp. 125127 (doi: 10.1109/TASSP.1981.1163515).
    47. 47)
      • 37. Pérez, E., Posada, M., Herrera, F.: ‘Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling’, J. Intell. Manuf., 2012, 23, pp. 341356 (doi: 10.1007/s10845-010-0385-4).
    48. 48)
      • 25. Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: ‘Optimization by simulated annealing’, Science, 1983, 220, pp. 671680 (doi: 10.1126/science.220.4598.671).
    49. 49)
      • 45. Zhu, W.-P., Ahmad, M.O., Swamy, M.N.S.: ‘A closed-form solution to the least-square design problem of 2-D linear-phase FIR filters’, IEEE Trans. Circuits Syst., II, 1997, 44, pp. 10321039 (doi: 10.1109/82.644586).
    50. 50)
      • 50. Lu, W.-S., Hinamoto, T.: ‘A new minimax design for 2-D FIR filters with low group delay’. ISCAS'2005, Kobe, Japan, May 2005, pp. 2028–2031.
    51. 51)
      • 18. Boudjelaba, K., Chikouche, D., Bekka, R.E.: ‘Application des Algorithmes Génétiques pour la Synthèse des Filtres RIF 1-D Passe-Bas’. Proc. du 1er Congrès Int. sur le Génie Electrique CIGE'04, Sétif, Algeria, 10–12 October 2004, pp. 3640.
    52. 52)
      • 51. Lu, W.-S., Hinamoto, T.: ‘A second-order cone programming approach for minimax design of 2-D FIR filters with low group delay’. ISCAS 2006, Island of Kos, Greece, May 2006, pp. 2521–2524.
    53. 53)
      • 19. Boudjelaba, K., Chikouche, D., Ros, F.: ‘Evolutionary techniques for the synthesis of 2-D FIR filters’. 2011 IEEE Workshop on Statistical Signal Processing (SSP'11), Nice, France, 28–30 June 2011, pp. 601604.
    54. 54)
      • 40. Lu, H.-C., Yeh, K.-H.: ‘Optimal design of 2-D FIR digital filters by scaling-free McClellan transformation using least-squares estimation’, Elsevier Signal Process., 1997, 58, pp. 303308 (doi: 10.1016/S0165-1684(97)00031-5).
    55. 55)
      • 16. Quinquis, A.: ‘Le Traitement du Signal sous Matlab, pratique et applications’ (Hermès, Paris, 2000).
    56. 56)
      • 10. Charalambous, C.: ‘The performance of an algorithm of minimax design of two-dimensional linear phase FIR digital filters’, IEEE Trans. Circuits Syst., 1985, 32, pp. 10161028 (doi: 10.1109/TCS.1985.1085627).
    57. 57)
      • 12. Bhattacharya, D., Antoniou, A.: ‘Design of 2-D FIR filters by a feedback neural network’, Multidimens. Syst. Signal Process., Boston, 1999, 10, pp. 319330 (doi: 10.1023/A:1008425226159).
    58. 58)
      • 47. Zhu, W.-P., Ahmad, M.O., Swamy, M.N.S.: ‘Realization of 2-D linear-phase FIR filters by using the singular-value decomposition’, IEEE Trans. Signal Process., 1999, 47, (5), pp. 13491358 (doi: 10.1109/78.757222).
    59. 59)
      • 44. Nguyen, D.T., Swamy, M.N.S.: ‘Approximation design of 2-D digital filters with elliptical magnitude response of arbitrary orientation’, IEEE Trans. Circuits Syst., 1986, 33, pp. 597603 (doi: 10.1109/TCS.1986.1085966).
    60. 60)
      • 15. Williams, T., Ahmadi, M., Hashemian, R., Miller, W.C.: ‘Design of high throughput 2-D FIR filters using singular value decomposition (SVD) and genetic algorithms’. Proc. of the IEEE Pacific RIM Conf. on Signals, Communications and Computers, Victoria, BC, August 2001, pp. 571574.
    61. 61)
      • 49. Lu, W.-S.: ‘A unified approach for the design of 2-D digital filters via semidefinite programming’, IEEE Trans. Circuits Syst., 2002, 49, pp. 814826 (doi: 10.1109/TCSI.2002.1010036).
    62. 62)
      • 5. Kamp, Y., Thiran, J.P.: ‘Chebyshev approximation for two-dimensional nonrecursive digital filters’, IEEE Trans. Circuits Syst., 1975, 22, pp. 208218 (doi: 10.1109/TCS.1975.1084025).
    63. 63)
      • 30. Johnson, A.W., Jacobson, S.H.: ‘A class of convergent generalized hill climbing algorithms’, Elsevier, Appl. Math. Comput., 2002, 125, pp. 359373 (doi: 10.1016/S0096-3003(00)00137-5).
    64. 64)
      • 17. Yeh, K.-H., Lu, H.-C.: ‘Shape parameter in the two-dimensional low-pass FIR digital filters design by transformation’, Elsevier Signal Process., 1996, 53, pp. 6574 (doi: 10.1016/0165-1684(96)00076-X).
    65. 65)
      • 36. Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.V., Lamont, G.B.: ‘Evolutionary algorithms for solving multi-objective problems’ (Kluwer, New York, 2002).
    66. 66)
      • 7. Rajan, P.K., Swamy, M.N.S.: ‘Design of circularly symmetric two-dimensional FIR digital filters employing transformations with variable parameters’, IEEE Trans. Acoust. Speech Signal Process., 1983, 31, (3), pp. 637642 (doi: 10.1109/TASSP.1983.1164130).
    67. 67)
      • 28. Dunn, S.A.: ‘The use of genetic algorithms and stochastic hill-climbing in dynamic finite element model identification’, Elsevier Comput Struct., 1998, 66, (4), pp. 489497 (doi: 10.1016/S0045-7949(97)00092-8).
    68. 68)
      • 27. Bertsimas, D., Tsitsiklis, J.: ‘Simulated annealing’, Stat. Sci., 1993, 8, (1), pp. 1015 (doi: 10.1214/ss/1177011077).
    69. 69)
      • 6. Lu, W.S., Hinamoto, T.: ‘Optimal design of nonlinear-phase fir filters with prescribed phase error’, IEEE Trans. Signal Process., 2009, 57, (9), pp. 33993410 (doi: 10.1109/TSP.2009.2021639).
    70. 70)
      • 42. Speake, T.C., Mersereau, R.M.: ‘A comparison of different window formulations for two dimensional FIR filter design’. IEEE Acoustics Speech Signal Processing Conf. Record, April 1979.
    71. 71)
      • 46. Nordebo, S., Claesson, I.: ‘Minimum norm design of two-dimensional weighted Chebyshev FIR filters’, IEEE Trans. Circuits Syst.-II, 1997, 44, (3), pp. 251253 (doi: 10.1109/82.558459).
    72. 72)
      • 24. Wu, T.-H., Yeh, J.-Y., Chang, C.-C.: ‘A hybrid tabu search algorithm to cell formation problem and its variants’, World Acad. Sci., Eng. Technol., 2009, 53, pp. 10901094.
    73. 73)
      • 52. Lu, W.-S., Hinamoto, T.: ‘Design of FIR filters with discrete coefficients via polynomial programming: towards the global solution’. ISCAS 2007, New Orleans, May 2007, pp. 2048–2051.
    74. 74)
      • 8. Pei, S.-C., Shyu, J.J.: ‘General form for designing two-dimensional quadrantally symmetric linear-phase FIR digital filters by analytical least-squares method’, Elsevier Signal Process., 1996, 48, pp. 165174 (doi: 10.1016/0165-1684(95)00132-8).
    75. 75)
      • 48. Pei, S.C., Wang, P.H.: ‘Design of arbitrary cutoff 2-D diamond-shaped fir filters using the bernstein polynomial’, IEEE Signal Process. Lett., 2000, 7, (11), pp. 310313 (doi: 10.1109/97.873567).
    76. 76)
      • 34. Goldberg, D.E.: ‘Genetic algorithms in search, optimization, and machine learning’ (Addison-Wesley, Reading, MA, 1989).
    77. 77)
      • 38. Erdozain, A., Crespo, P.M.: ‘A new stochastic algorithm inspired on genetic algorithms to estimate signals with finite rate of innovation from noisy samples’, Elsevier Signal Process., 2010, 90, pp. 134144 (doi: 10.1016/j.sigpro.2009.05.022).
    78. 78)
      • 1. Wang, X.-H., He, Y.-G.: ‘A neural network approach to FIR filter design using frequency-response masking technique’, Elsevier Signal Process., 2008, 88, pp. 29172926 (doi: 10.1016/j.sigpro.2008.06.015).
    79. 79)
      • 4. Pei, S.-C., Shyu, J.-J.: ‘Design of two-dimensional FIR digital filters by McClellan transformation and least-squares contour mapping’, Elsevier Signal Process., 1999, 44, pp. 1926 (doi: 10.1016/0165-1684(95)00012-3).
    80. 80)
      • 14. Sriranganathan, S., Bull, D.R., Redmill, D.W.: ‘Design of 2-D multiplierless FIR filters using genetic algorithms’. First Int. Conf. on Genetic Algorithms in Engineering Systems: Innovations and Applications GALESIA 1995, Sheffield, UK, September 1995, pp. 282286.
    81. 81)
      • 26. Bohachevsky, I., Johnson, M.E., Stein, M.L.: ‘Generalized simulated annealing for function optimization’, Technometrics, 1986, 28, pp. 209217 (doi: 10.1080/00401706.1986.10488128).
    82. 82)
      • 20. Boudjelaba, K., Ros, F., Chikouche, D.: ‘An advanced genetic algorithm for designing 2-D FIR filters’. 2011 IEEE Pacific Rim Conf. on Communications, Computers and Signal Processing, Victoria, BC, 23–26 August 2011, pp. 6065.
    83. 83)
      • 31. Mastorakis, N.E., Gonos, I.F., Swamy, M.N.S.: ‘Design of two-dimensional recursive filters using genetic algorithms’, IEEE Trans. Circuits Syst I, 2003, 50, (5), pp. 634639 (doi: 10.1109/TCSI.2003.811019).
    84. 84)
      • 22. Glover, F.: ‘Tabu search – part I, ORSA’, J. Comput., 1989, 1, (3), pp. 190206.
    85. 85)
      • 9. Karaboga, N., Cetinkaya, B.: ‘Design of digital fir filters using differential evolution algorithm’, Circuits Systems Signal Processing, 2006, 25, (5), pp. 649660 (doi: 10.1007/s00034-005-0721-7).
    86. 86)
      • 23. Glover, F.: ‘Tabu search – part II, ORSA’, J. Comput., 1990, 2, (1), pp. 432.
    87. 87)
      • 3. Lee, J.-H., Yang, S.-J., Tang, D.-C.: ‘Minimax design of 2-D linear-phase FIR filters with continuous and powers-of-two coefficients’, Elsevier Signal Process., 2000, 80, pp. 14351444 (doi: 10.1016/S0165-1684(00)00047-5).
    88. 88)
      • 2. Cen, L.: ‘A hybrid genetic algorithm for the design of FIR filters with SPoT coefficients’, Elsevier Signal Process., 2007, 87, pp. 528540 (doi: 10.1016/j.sigpro.2006.06.015).
    89. 89)
      • 41. Sheeba, V.S., Elizabeth, E.: ‘Two-dimensional FIR signal adapted filter banks: optimality and design’, Elsevier Signal Process., 2007, 87, pp. 23812391 (doi: 10.1016/j.sigpro.2007.03.009).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2013.0005
Loading

Related content

content/journals/10.1049/iet-spr.2013.0005
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading