PERBANDINGAN KINERJA ALGORITMA LMS DAN ALGORITMA GENETIK UNTUK FILTER ADAPTIF PENGHILANG NOISE

Simposium Nasional I Rapi 2002

PERBANDINGAN KINERJA ALGORITMA LMS DAN ALGORITMA GENETIK UNTUK FILTER ADAPTIF PENGHILANG NOISE Renaldi Bonadr Jurusan Teknik Elektro Undip Jl. Prof. Sudharto, Tembalang Semarang [email protected]

Sumardi Jurusan Teknik Elektro Undip Jl. Prof. Sudharto, Tembalang Semarang [email protected]

Sudjadi Jurusan Teknik Elektro Undip Jl. Prof. Sudharto, Tembalang Semarang [email protected]

ABSTRAK Filter adaptif merupakan sebuah filter dengan pengatur koefisien. Pada penghilang noise parameter filter diatur sehingga dapat mengoptimalkan sinyal dari distorsi (cacat) seminimal mungkin. Algoritma LMS digunakan sebagai algoritma pada filter adaptif FIR, yang kinerjanya bisa menghilangkan noise dari sinyal yang telah terkena noise, tapi tidak cukup baik untuk menghilangkan sebagian besar noise pada sinyal yang terkena noise. Untuk mengatasi permasalahan ini maka digunakan algoritma genetik. Algoritma genetik merupakan suatu algoritma yang berbasiskan pendekatan evolusi, yang melakukan seleksi berdasarkan kemampuan bertahan hidup suatu individu. Pembanding kedua algoritma ini (algoritma LMS dan algoritma genetik) adalah MSE (mean square error) yang minimum, MSE semakin minimum maka sinyal yang dihasilkan semakin mirip dengan sinyal yang diinginkan. Penggunaan algoritma LMS pada filter adaptif FIR menghasilkan MSE sebesar 0.0080476, sedangkan hasil yang lebih baik didapat saat penggunaan algoritma genetik dengan MSE sebesar 3.04 x10 −6 . Kata Kunci: Algoritma LMS, Algoritma genetik, minimum MSE.

I. PENDAHULUAN Penyelesaian masalah terdistorsinya sinyal dengan noise ini bisa diselesaikan dengan filter adaptif. Komponen kunci dari filter adaptif adalah pengesetan aturan, atau algoritma yang berfungsi untuk mengkoreksi pada proses adaptasi. Koreksi yang dihasilkan harus mengurangi MSE (mean square error). Algoritma sering digunakan yaitu algoritma least mean square (LMS). Algoritma ini bisa menghasilkan solusi pada lokal minimal, sehingga hasil yang diinginkan jadi keliru. Algoritma genetik digunakan sebagai pembanding pada makalah ini, dimana genetik mendapatkan solusi pada multi titik, sehingga bisa didapat solusi yang terbaik. Algoritma genetik sangat cocok digunakan untuk memecahkan masalah optimasi komplek dan juga untuk aplikasi yang membutuhkan pemecahan masalah adaptif. Dengan keunggulan tersebut, algoritma genetik diterima pada berbagai kalangan dan telah diaplikasikan pada berbagai bidang, seperti kontrol, robotika, identifikasi sistem (Man,1997), penghilang noise (Hayes,1996). II. TUJUAN Tujuan dari makalah ini adalah membandingkan kinerja filter adaptif penghilang noise menggunakan algoritma LMS dan algoritma genetik, dengan melihat pada nilai MSE (mean square error). III. DASAR TEORI 3.1. Filter Adaptif FIR Aplikasi filter adaptif penghilang noise (sinyal interferensi) dapat dibuat blok diagram seperti gambar 1. Pada penghilang noise, filter adaptif membuang noise dari sinyal dalam waktu riil. Sinyal yang diinginkan x(n) adalah kombinasi noise v1(n) dan informasi yang dibutuhkan d(n). Untuk menghilangkan noise, dibutuhkan noise referensi v2(n) . Noise yang dipakai pada simulasi ini adalah noise murni Gaussian.

ISSN : 1412-9612

E - 67

Simposium Nasional I Rapi 2002

x(n)=d(n)+v 1(n)

+ -

v 2(n)

Filter Adaptif

y(n)

+ e(n)

Gambar 1. Filter adaptif penghilang noise

3.2. Algoritma LMS (least mean square) Persamaan dasar filter FIR (Ifeachor, 1993) adalah N −1

H ( z ) = ∑ h(k ) z − k

(1)

k =0

Tanggapan filter FIR yang menghasilkan estimasi mean-square (akar rata-rata) yang minimum dari proses yang diharapkan d(n), estimasi sinyal yang diinginkan adalah: p

y (n) = ∑ wn (k )v 2 (n − k ) = wnT v 2 (n)

(2)

k =0

Dimana wn = [wn(0), wn(1), ..., wn(p)]T (3) wn adalah vektor koefisien filter pada waktu n, dan v2(n) = [v2(n), v2(n-1), ..., v2(n-p)]T (4) Pada keadaan yang sebenarnya sinyal yang diinginkan d(n) tidak diketahui dan cenderung dinyatakan dengan fungsi random, tapi untuk kepentingan simulasi maka diumpamakan sinyal d(n) merupakan sinyal yang dibentuk dari sinyal sinus dan beramplitudo maksimum sama dengan satu. Disini diharapkan sinyal hasil keluaran dari proses adaptif e(n) akan mendekati sinyal yang diinginkan d(n). Semakin mirip dengan sinyal yang diinginkan maka MSE akan semakin minimum,

ξ (n) =

1 N

N −1

∑ d ( n ) − e( n )

2

(5)

n =0

dimana

e(n) = x(n) − y (n) = x(n) − wnT v 2 (n)

(6)

update untuk wn adalah:

wn +1 = wn + µE{e(n)v 2* (n)}

(7) dan dikenal sebagai algoritma LMS. Algoritma LMS konvergen dalam rata-rata jika ukuran langkah µ memenuhi persamaan: (8) 0 < µ <1 3.3. Pendekatan Pencarian Genetik Algoritma genetik merupakan teknik pencarian yang diilhami oleh mekanisme evolusi dan genetik alam. Menurut teori evolusi, hanya individu terkuat saja yang dapat bertahan dan menghasilkan keturunan yang lebih berkualitas. Dalam bentuk matematis, suatu algoritma genetik akan memetakan suatu masalah pada suatu himpunan gen yang berbentuk string biner, kemudian akan di konversi kedalam nilai riil untuk menghasilkan pnenotype yang merupakan kode riil dari parameter dalam suatu ruang solusi dimana masing-masing string tersebut merepresentasikan suatu kandidat solusi bagi suatu masalah. Kemudian algoritma genetik akan memanipulasi kandidat-kandidat solusi tersebut dengan menggunakan operasi-operasi genetik, sehingga dihasilkan kandidat-kandidat solusi yang lebih berkualitas. Operator genetik adalah seleksi, rekombinasi (crossover), dan mutasi. 3.3.1 Seleksi Seleksi berguna untuk mencapai nilai target yang ditentukan dari parameter optimasi yang ingin dicapai. Operator seleksi dapat dikatakan merupakan model dari siapa yang terkuat (fittest) dia yang bertahan (survive) yang terjadi pada evolusi alam.

ISSN : 1412-9612

E - 68

Simposium Nasional I Rapi 2002

3.3.2 Crossover Rekombinasi gen merupakan suatu mekanisme yang penting untuk terjadinya evolusi. Dalam algoritma genetik, metode yang biasa digunakan adalah pindah silang (crossover) Proses pindah silang bertujuan untuk menambahkan keanekaragaman individu didalam populasi dengan “mengawinkan” individu-individu pada populasi. Individu baru akan mewarisi sifat dari induknya. 3.3.3 Mutasi Keanekaragaman individu dalam populasi telah dihasilkan dengan menggunakan proses seleksi dan pindah silang. Dengan kedua operator genetik tersebut dapat terjadi hilangnya struktur gen tertentu sehingga tidak bisa diperoleh kembali informasi yang terkandung didalamnya. Operator mutasi diperkenalkan sebagai cara untuk mengembalikan informasi yang hilang tersebut. Melalui mutasi, individu baru dapat diciptakan dengan melakukan pengubahan terhadap satu atau lebih nilai gen pada individu yang sama. 3.4 Pendekatan Algoritma Genetik untuk Filter Adaptif FIR Seperti pada algoritma LMS, genetik pada filter adaptif penghilang noise juga berberfungsi untuk mengadaptasi koefisien filter untuk mendapatkan sinyal hasil yang terbaik. Fungsi objektif yang digunakan untuk melaksanakan operator genetik adalah:

J=

1 N

N −1

∑ e( n ) − d ( n )

2

(14)

n =0

IV. PERANCANGAN SIMULASI Struktur filter yang digunakan pada filter adaptif menggunakan algoritma LMS dan algoritma genetik adalah struktur transversal. noise referensi yang digunakan adalah noise aditif Gaussian yang dibangkitkan secara random pada algoritma LMS dan diplot tetap. Pengukuran MSE (mean square error) pada kedua algoritma (LMS dan genetik) diukur pada 50 iterasi terakhir. Alasannya karena cara kerja algoritma LMS yang secara bertahap memperbaiki sinyal keluaran dengan mengadaptasi koefisien filter, berbeda dengan algoritma genetik yang mendapatkan hasil estimasi dengan berdasarkan jumlah generasi. Data simulasi a. Algoritma LMS Pada Filter FIR, ukuran langkah µ yang digunakan 0.1, 0.25, dan 0.5 dengan orde filter yang disimulasikan orde 1, orde 3 dan orde 7. b. Algoritma genetik Orde yang digunakan sama seperti pada algoritma LMS. Simulasi dilakukan masing-masing 6 kali untuk setiap jenis filter dengan mengubah-ubah jumlah populasi (MAXGEN), probabilitas crossover (Pc), dan probabilitas mutasi (Pm), seperti dibawah ini. 1. MAXGEN=30, Pc = 0.75 dan Pm = 0.01 2. MAXGEN=30, Pc = 0.85 dan Pm = 0.001 3. MAXGEN=30, Pc = 0.95 dan Pm = 0.001 4. MAXGEN=100, Pc = 0.75 dan Pm = 0.01 5. MAXGEN=100, Pc = 0.85 dan Pm = 0.001 6. MAXGEN=100, Pc = 0.95 dan Pm = 0.001 V. HASIL SIMULASI Pengharapan pada simulasi ini adalah didapat MSE yang seminimum mungkin, sehingga sinyal x(n) dapat direduksi noisenya mendekati sinyal yang diinginkan d(n). Pada aplikasi filter adaptif untuk menghilangkan noise dari sinyal masukan yang mengandung noise x(n) seperti pada gambar 2. Pada aplikasi ini juga dibutuhkan noise referensi seperti pada gambar 3.

ISSN : 1412-9612

E - 69

Simposium Nasional I Rapi 2002

1.5

1

0.5

0

-0 .5

-1

-1 .5 0

50

100

150

200

250

Gambar 2. Contoh sinyal yang telah tercampur dengan noise x(n). 0.8

0.6

0.4

0.2

0

-0 .2

-0 .4

-0 .6 0

50

100

150

200

250

Gambar 3 Contoh sinyal noise referensi v2(n) 1.5 S i n y a l d ii n g in k a n d (n ) H a s il p ro s e s e (n )

1

0.5

0

-0 . 5

-1

-1 . 5 0

50

100

150

200

250

Gambar 4. Sinyal hasil dengan filter FIR LMS orde 1 1 .5 S in y a l d iin g in k a n d (n ) S in y a l h a s il e (n )

1

0 .5

0

-0 . 5

-1

-1 . 5 0

50

100

150

200

250

Gambar 5. Sinyal hasil dengan Filter FIR LMS orde 3

Simulasi menggunakan algoritma LMS pada filter adaptif FIR penghilang noise memberikan MSE (error akar rata-rata) sebesar 0.0080476, pada orde 1 dengan µ senilai 0.25.

ISSN : 1412-9612

E - 70

Simposium Nasional I Rapi 2002

Pada orde 3 dengan µ=0.25 MSE yang didapat sebesar 0.01059, dan pada orde 7 hasil MSE yang didapat sebesar 0.013807 dengan ukuran langkah yang lebih kecil, yaitu µ=0.1 Ternyata orde 1 memberikan nilai MSE yang paling kecil, perbaikan hingga 0.0025454 dibandingkan orde 3 dan pada orde 7 sebesar 0.0057594. Terlihat bahwa penambahan orde filter tetap tidak memberikan hasil yang lebih baik, dan sebaliknya sinyal hasil dan MSE yang didapatkan lebih buruk daripada hasil simulasi pada orde 1. Kita juga dapat menyimpulkan bahwa nilai ukuran langkah µ yang terbaik digunakan adalah 0.25 yang memberikan nilai MSE yang lebih kecil pada filter orde 1 dan orde 3 yang disimulasikan. Sedangkan untuk orde yang lebih besar yaitu orde 7 dibutuhkan µ yang lebih kecil untuk mendapatkan MSE yang minimum. Hasil simulasi filter FIR menggunakan algoritma genetik pada 30 generasi dan 100 generasi hanya memberikan sedikit perbedaan pada MSE yang didapatkan, sehingga dapat ditarik kesimpulan bahwa penggunaan populasi besar (100 generasi) pada simulasi ini hanya memberikan sedikit koreksi dan tidak seimbang dengan waktu pencarian yang jauh lebih lama. Pada simulasi ini orde filter yang lebih kecil relatif memberikan nilai MSE yang lebih besar, sehingga penggunaan orde filter yang lebih besar memberikan grafik hasil yang lebih baik. Peningkatan orde mempunyai pengaruh pada filter FIR orde 3, yang dapat menghasilkan MSE yang lebih kecil dibandingkan dengan orde 1. Grafik hasil penghilang noise yang terbaik terjadi pada filter FIR orde 3 dengan probabilitas crossover 0.75 dan probabilitas mutasi 0.01 yang memberikan nilai MSE 3.04 x10 −6 , nilai ini memberikan perbaikan 5.53 x10 −4 daripada MSE yang terminimum pada filter FIR orde 1, dan perbaikan 5.48 x10 −6 daripada MSE minimum pada orde 7. Grafik hasil pada filter FIR menggunakan genetik memberikan sinyal hasil yang sudah sangat mendekati sinyal yang diinginkan d(n). Semua hasil estimasi yang paling baik dari seluruh orde filter FIR yang disimulasikan memberikan hasil yang paling optimum pada penggunaan operator genetik Pc=0.75 dan Pm=0.01, operator yang paling berpengaruh pada nilai Pm-nya, hal ini disebabkan adanya probabilitas mutasi yang lebih besar sehingga kemungkinan terjadinya perubahan gen semakin besar, sehingga dengan adanya semakin banyak variasi maka akan mendorong untuk tercapainya hasil yang optimum secepat mungkin. Tabel 1 merupakan rangkuman hasil simulasi dari penggunaan 2 algoritma (LMS dan genetik) dan jenis filter orde yang digunakan. Pada tabel terlihat bahwa untuk filter adaptif FIR menggunakan algoritma LMS menghasilkan MSE yang paling baik sebesar 0.0080476, yang didapat pada Orde 1 dengan penggunaan µ=0.25, hasil ini sangat jauh perbedaannya dengan hasil yang didapat pada algoritma genetik yang memberikan MSE yang paling minimum pada orde 3 dengan operator genetik Pc=0.75 dan Pm=0.01 yang memberikan MSE sebesar 3.04 x10 −6 . Tabel 1. Hasil simulasi filter adaptif dengan algoritma LMS dan genetik

No 1 2 3 4 5 6

Algoritma Orde LMS 1 LMS 3 LMS 7 Genetik 1 Genetik 3 Genetik 7

µ Maxgen 0.25 0.25 0.1 100 100 100

Pc 0.75 0.75 0.75

Pm

MSE - 0.0080476 0.01059 0.013807 0.01 0.00055633 0.01 3.0402E-06 0.01 8.52E-06

VI. KESIMPULAN Hasil optimasi algoritma LMS (least mean square) dibandingkan dengan algoritma genetik untuk filter adaptif penghilang noise, dapat diambil kesimpulan sebagai berikut: 1. Algoritma genetik bisa diaplikasikan pada penghilang noise filter adaptif untuk filter digital FIR. 2. Filter adaptif FIR menggunakan algoritma LMS untuk menghilangkan noise menghasilkan MSE yang minimum sebesar 0.0080476 pada orde 1.

ISSN : 1412-9612

E - 71

Simposium Nasional I Rapi 2002

3. Penggunaan algoritma genetik untuk filter adaptif FIR penghilang noise memberikan MSE yang minimum sebesar 3.04 x10−6 pada orde 3. 4. Pada algoritma LMS penentuan parameter ukuran langkah sangat mempengaruhi pada besarnya MSE yang didapatkan. 5. Parameter yang sangat berpengaruh pada pencapaian MSE yang minimum pada algoritma genetik adalah probabilitas crossover Pc dan probabilitas mutasi Pm. DAFTAR PUSTAKA Chen, S., Istepanian, R., and Luk, B.L., Digital IIR Filter Design Using Adaptive Simulated Annealing, Department of Electronics and Computer Science, University of Southampton. Chipperfield, A., Fleming, P., Pohlheim, H., Fonseca, C., Genetic Algorithm Toolbox for Use with MATLAB, Version 1.2 User’s Guide, Department of Automatic Control and Systems Engineering, University of Sheffield. Coletti, M., Lash, T., Mandsager, C., Michalski, R.S., and Moustafa, R., 1999, An Experimental Application of Learnable Evolution Model and Genetic Algorithms to Parameter Estimation in Digital Signal Filters Design, P99-9, MLI 99-5. Davis, L., 1991, Hand Book of Genetic Algorithm, Van Nostrand Reinhold, New York. Flockton, S.J., and White, M.S., 1993, The Application of Genetic Algorithms to Infinite Impulse Response Adaptive Filters, In IEE Colloquium Digest 1993/039, page 9/1-4, IEE. Golberg, D.H, 1989, Genetic Algorithms in Search, Optimization, and Machine Learning, New York: Addison-Wesley. Hayes, M.H., 1996, Statistical Digital Signal Processing and Modeling, New York: John Wiley & Sons, Inc. Haykin, S., Adaptive Filter Theory, Second Edition, Prentice-Hall, Englewood-Cliffs, NJ, 1991. Ifeachor, E.C., Jervis, B.W., 1993, Digital Signal Processing A pratical Approach, AddisonWesley Publishing Company, Wokingham. Man, K.F., Tang, K.S., and Kwong, S., 1996, Genetic Algorithms: Conceps and Applications, IEEE Transactions on Industrial Electronics, Vol. 43, No.5, pp: 519-534. Man, K.F., Tang, K.S., Kwong, S., and Halang, W.A., 1997, Genetic Algorithms for Control and Signal Processing Advances in Industrial Control, Springer, London. Malik, Leevy D., 2000, Optimasi Base Point Unit Pembangkit Thermal Multi Area dengan Algoritma Genetik, Tugas Akhir, Universitas Diponegoro, Semarang. MathWorks, 2000, Filter Design Toolbox for Use with MATLAB, Version 2 User’s Guide, The MathWorks. Inc. Ng, S.C., Leung, S.H., Chung, C.Y., Luk, A., and Lau, W.H., 1996, The Genetic Search Approach, A New Learning Algorithm for Adaptive IIR Filtering, IEEE Signal Processing Magazine, pp. 38-46. Shynk, J.J., 1989, Adaptive IIR Filtering, IEEE ASSP mag., pp. 4-21. Sundaralingam, S., and Sharman, K., Genetic Evlution of Adaptive Filters, Dept. of Electronics & Electrical Engineering, The University of Glasgow. White, M.S., and Flockton, S.J., Adaptive Recursive Filtering Using Evolutionary Algorithms, Department of Physics, Royal Holloway, University of London. Widrow, B. and Stearns, S., 1985, Adaptive Signal Processing, Prentice-Hall, Englewood Cliffs, NJ. Wirnitzer, B., Prof., 1999, Adaptive Filter A Matlab (Nano) Toolbox and Laboratory Exercises, ver. 1.0, FH-Mannheim, Institut fűr digitale Signalverarbeitung.

ISSN : 1412-9612

E - 72