Vol.16 No.2. Agustus 2014
Jurnal Momentum
ISSN : 1693-752X
PERANCANGAN BANDSTOP FILTER (BSF) DENGAN ALGORITMA GENETIK Oleh: Muhammad Anwar Dosen Jurusan Teknik Elektronika Universitas Negeri Padang
Abstract A study to find the optimal value required of digital filter design problem is given in this paper. In digital signal processing (DSP), designing an optimal filter is much preferred. Some of methods are commonly based on approximation methods. Genetic algorithm (GA) is a stochastic (random) searching method that mimics the metaphor of natural biological evolution to solve the problem, and in this case, it’s about how to find optimal digital filter design. In its application, GA just need the evaluation function as a problem representation which will to be optimized. The digital filter structures in z-domain indicates the nonlinear problem where the z value is constrained by the stability. The genetic programming can be used, when the transfer function H[z]of bandstop filter has been transferred to evaluation function, and –1 z 1 as the solution bounds and stability guarantee. The genetic programming simulation for solving digital filter problem is to produce the transfer function which has lowest order, stable and meet the prescribed tolerance settings (as design criteria). One of the disadventages using this method is the larger computational loading. However, the findings of this paper can be interpreted that the GA’s performance is different from the other methods in optimal digital filter design, especially in providing guarantees on fulfillment of all the design criteria. Keywords :
genetic algorithm, digital filter, filter structure, design criteria, BSF
mating pool members untuk memperoleh keturunan atau generasi berikutnya. Kromosom tersebut sekaligus menjadi kandidat solusi pada setiap siklus iteratif yang disebut dengan generasi. Gambar 1 menunjukkan siklus algoritma genetik.
PENDAHULUAN Algoritma genetik (genetic algorithm, GA) merupakan suatu wujud pencarian random (stochastic) yang menirukan prinsip proses evolusi biologi alami guna mencari solusi optimal untuk suatu permasalahan kompleks. Algoritma genetik adalah suatu event yang memiliki kebebasan dan fleksibilitas intrinsik untuk memilih solusi yang diinginkan menurut spesifikasi rancangan. Nilai optimal yang diperoleh merupakan produk akhir hasil perkembangan generasi ke generasi dengan individu-individu terbaik dalam jumlah populasi tertentu.
Tahap seleksi dengan mengevaluasi kualitas setiap individu dalam populasi, menghasilkan individu-individu yang akan mengalami proses rekombinasi atau perkawinan. Individu yang mempunyai kualitas yang lebih tinggi mempunyai kemungkinan yang lebih besar untuk dipilih sebagai calon-calon induk bagi generasi berikutnya. Generasi baru inilah sebagai sub-populasi yang akan menggantikan posisi induk sebelumnya dan akan mengalami proses sama. Siklus ini diulangi sesuai jumlah generasi hingga suatu kriteria akhir yang diinginkan tercapai yaitu memperoleh solusi optimal.
Proses pemilihan individu dari suatu populasi disesuaikan dengan tingkat fitness yang ditetapkan berdasarkan fungsi obyektif untuk masalah yang dioptimasi. Individu atau disebut juga kromosom (chromosome) dengan nilai fitness lebih tinggi, akan berpeluang besar terpilih (bertahan hidup) dan menjadi induk atau
101
Vol.16 No.2. Agustus 2014
Jurnal Momentum
ISSN : 1693-752X
Population (chromosomes) Fitness PhenoType
Selection
Mating Pool (parents)
Replacement
Objective Function
Genetic Operation
PhenoType Fitness
Sub-population (offspring) Gambar 1. Siklus algoritma genetik [Man, 1997] Proses evolusi algoritma genetik, dapat dikelompokkan dalam empat tahap dasar sebagaimana bagan alir berikut.
Inisialisasi
Gambar 2. Bagan alir algoritma genetik
Operator genetik
Parameter genetik
Operator-operator genetik berguna untuk memperkenalkan kromosom atau string baru dalam populasi. Operator ini terdiri atas operator genetik dasar dan operator genetik hasil modifikasi. Operator yang biasa digunakan terdiri atas : a. Persilangan (crossover), terutama multipoint crossover b. Mutasi c. Reordering dan inversi d. Pengkodean kembali nol
Untuk mengendalikan operatoroperator genetik diperlukan ukuran parameter. Pemilihan ukuran parameter genetik menentukan kinerja algoritma genetik dalam memecahkan suatu masalah. Ukuran parameter yang sering digunakan terdiri atas ukuran populasi, probabilitas crossover (Pc), dan probabilitas mutasi (Pm ). Ukuran parameter populasi tidak memiliki standar nyata. Pada umumnya semakin besar ukuran populasi,
102
Vol.16 No.2. Agustus 2014
Jurnal Momentum
ISSN : 1693-752X
digital yang memenuhi kriteria perancangan, yakni : menetapkan orde tapis terendah, sehingga implementasinya lebih sederhana tapis harus stabil (pole-pole berada dalam lingkup unit circle), harus memenuhi penetapan tolerans, baik pada jalur pass maupun pada jalur stop. Pada akhirnya memungkinkan untuk direalisasi dengan formulasi algoritma genetik tanpa pembatasan pada jenis rancangan tapis. Setiap jenis tapis, apakah dalam bentuk Low Pass, High Pass, Band Pass maupun Band Stop dapat dengan bebas dioptimisasi hingga orde terendah, walaupun pada kesempatan ini difokuskan pada tapis BSF (bandstop filter). Karena itu dibutuhkan persamaan umum fungsi alih (transfer function, H[z]) untuk jenis tapis BSF, dan secara teoritis, operasi genetik yang menghasilkan kromosom dapat dianggap sebagai solusi potensial untuk H[z], sehingga dengan demikian masalah penaksiran parameter untuk perancangan tapis BSF digital dapat diselesaikan.
semakin cepat mencapai konvergensi dan akan membutuhkan komputasi lebih banyak dengan waktu yang panjang. Dalam berbagai percobaan, ukuran populasi sebaiknya berada dalam rentang 70 hingga 200.
Fungsi fitness Fungsi fitness merupakan ukuran kinerja suatu individu agar tetap bertahan hidup dalam lingkungannya. Dalam algoritma genetik, fungsi fitness adalah fungsi objektif atas masalah yang akan dioptimasi. Fungsi ini sebagai ukuran profit yang ingin dimaksimalkan atau sebagai ukuran cost yang ingin diminimumkan. Untuk setiap masalah yang dioptimasi dibutuhkan pendefinisian fungsi fitness supaya string dengan kinerja yang tinggi dapat menghasilkan nilai fungsi fitness sesuai dengan tujuan.
Pemakaian GA untuk pemecahan masalah, khususnya teknik optimisasi, terus merambah berbagai bidang ilmu, seiring dengan pengembangan teori GA itu sendiri. K.F.Man [1996] mengelompokkan tiga wilayah umum materi tulisan atau penelitian yang membahas bidang algoritma genetik, yaitu tentang desainMETODOLOGI PENELITIAN desain industri, pemrosesan sinyal dan teknik kendali. Dalam sistem pemrosesan sinyal Ruang lingkup materi adalah pengkajian khususnya mengenai tapis, A.Roberts dan spesifikasi input dan proses algoritma genetik G.Wade dari University of Plymouth, Inggris sebagai alat untuk menemukan solusi optimal Raya, telah dua kali melakukan penelitian (1993 pada perancangan BSF digital. Dengan demikian dan 1994) tentang perancangan tapis FIR dengan materi kajian terdiri atas tiga tahap berikut. GA terstruktur (A structured GA for FIR filter a. Pembuatan model fungsi evaluasi sebagai design) dan perancangan tapis FIR tanpa pengali fungsi fitness yang dibentuk oleh solusi menggunakan GA (Multiplier-less FIR filter terkekang untuk jenis BSF. design using a genetic algorithm). Kesimpulan b. Penerapan operator algoritma genetik ke dari penelitian tersebut menunjukkan bahwa dalam pemrograman genetik dengan tapis digital FIR dapat dirancang sebagai suatu implementasi MATLAB. alternatif untuk pemrograman linear dengan c. Penentuan nilai parameter genetik yang algoritma genetik. dibutuhkan, meliputi jumlah generasi (atau Sementara itu, tapis digital dengan iterasi), jumlah populasi, peluang seleksi, unjuk-kerja yang lebih optimal serta memenuhi peluang crossover, dan laju mutasi kriteria jelas amat diperlukan. Perancangan tapis berdasarkan ujicoba program. Fungsi evaluasi merupakan ungkapan atas pokok permasalahan yang akan dioptimasi (persamaan rancangan). Karena itu perlu dirumuskan terlebih dahulu permasalahannya dengan langkahlangkah sebagai berikut: a. Tentukan struktur tapis dasar yang akan digunakan sebagai fungsi alih tapis BSF. Misalnya, bila diambil bentuk bertingkat (cascade) orde empat untuk tapis BSF, maka diperoleh fungsi alih:
H z K
z z
2
2
b11 z b12 z 2 b21 z b22 a11 z a12 z 2 a 21 z a 22
103
Vol.16 No.2. Agustus 2014
Jurnal Momentum
ISSN : 1693-752X
dengan nilai K dan setiap koefisien
berada dalam kekangan yang
memenuhi syarat nilai setiap pole yaitu –1 z 1, dan koefisien
yakni
.
Artinya bahwa K dan seluruh koefisien harus mempunyai nilai dalam kekangan sedemikian sehingga diperoleh solusi otimal. b. Karena kondisi optimal tapis BSF diindikasikan oleh tanggapan magnitudenya, maka fungsi alih dalam domain z harus direpresentasikan dalam domain frekuensi , dengan z e j . Dengan demikian diperoleh fungsi evaluasi, yaitu:
f ( z ) eval f e j , solusi
H (e
j
e ) sol (9) e
x e sol (6) e
sol (8)
j 2
sol (1)e j sol (2)
j 2
sol (3)e j sol (4)
j 2
j
j 2
j
sol (5)e
sol (7 )e
kriteria stabil). Setiap solusi (sol) harus memenuhi kekangan pole sebagai berikut:
dengan nilai meliputi kisar 0 dan orde filter paling minimal yang masih mungkin. Artinya bahwa dengan fungsi evaluasi pada orde lebih kecil dari 4, tidak diperoleh hasil tanggapan magnitude yang optimal (memenuhi
1 sol (1), (2), (3), (4), (6), 8, 9 1 2 sol (5), 7 2
Besar nilai tanggapan magnitude secara ideal dalam spesifikasi praktis untuk bandstop filter dalam rentang adalah:
0 H (e j ) 2 , untuk s1 s2 H (e ) j 1 1 H (e ) 1 1 , untuk 0 p1 , p2 j
0 H (e j ) 0.1, H (e j ) j 0.95 H (e ) 1,
untuk 0.4 0.6 untuk 0 0.24, 0.76 1
Dengan demikian, dapat digambarkan tanggapan magnitude untuk BS seperti berikut.
H (e j ) 1 0.95
0.1
0
0.24 passband
0.4
0.6
stopband
0.76
passband
Gambar 1. Tanggapan magnitude BS praktis
104
Vol.16 No.2. Agustus 2014
Jurnal Momentum
ISSN : 1693-752X
meliputi jumlah generasi, jumlah populasi, peluang seleksi, peluang crossover, dan laju mutasi harus diberikan dalam bentuk yang dipahami oleh bahasa pemrograman genetik. Nilai parameter yang diberikan akan sangat menentukan hasil yang diperoleh. Karena itu, hasil optimal bisa didapatkan dalam beberapa kali ujicoba.
Untuk menerapkan operator algoritma genetik ke dalam pemrograman genetik, maka strukturnya harus direpresentasikan ke dalam bentuk yang dipahami oleh bahasa pemrograman genetik. Pemrograman genetik dalam percobaan penelitian ini, diimplementasikan dengan menggunakan paket (toolbox) perangkat lunak MATLAB. MATLAB merupakan lingkup penghitungan teknis untuk komputasi dan visualisasi numerik unjuk-kerja tinggi. MATLAB memadukan analisis numeris, komputasi matriks, pemrosesan isyarat, dan grafis dalam tatanan yang mudah digunakan. Setiap masalah dan solusi hanya dinyatakan dalam formula matematis biasa, tak seperti pemrograman tradisional. Seperti halnya pada pemrograman genetik, maka segenap parameter genetik
HASIL DAN PEMBAHASAN
Hasil percobaaan penelitian ini adalah didapatkannya fungsi alih untuk jenis tapis BSF digital melalui eksekusi pemrograman genetik secara terpadu. Adapun fungsi evaluasi dengan ruang solusi untuk tapis dimodelkan sebagaimana dalam tabel berikut.
Tabel 1. Fungsi evaluasi untuk setiap jenis tapis Jenis tapis
Fungsi evaluasi
Kriteria
1
2
3 Orde = 4 Tolerans: pass=[1 0.95] stop=[0.1 0] p1 = 0.24 s1 = 0.4 s2 = 0.6 p2 = 0.76
z z z z
2
H (e j ) sol (9)
BSF
2 2 2
sol (3) z sol (4) sol (7) z sol (8)
sol (1) z sol (2) x sol (5) z sol (6)
dengan: z = ej, 0 ruang solusi (1)=(2)=(3)=(4)=(6)=(8)=(9) = [-1 1] ruang solusi (5) = (7) = [-2 2] Data Tabel 1 memperlihatkan hasil pemodelan fungsi evaluasi dengan ruang solusi yang dibentuk berdasarkan struktur tapis cascade form untuk jenis tapis BSF. Besar orde tapis ditetapkan pada nilai terendah, dengan tidak mengabaikan kriteria perancangan yang lain, yakni tetap stabil dan memenuhi batas tolerans. Data ini juga menegaskan bahwa orde filter minimum adalah 4 untuk memastikan criteria yang lain juga dipenuhi.
Tabel 2. Parameter input operator genetik Parameter operator genetik Jumlah populasi Jumlah generasi Koef. Seleksi ‘roulette’ Operator Crossover: Aritmetik Heuristik Simple Operator Mutasi : Boundary Uniform
Selain fungsi evaluasi, parameter input operator genetik juga diberikan untuk menjalankan program secara terpadu, seperti diperlihatkan pada Tabel 2 berikut.
Bandpass filter 99 8242 0.04 [2 0] [2 3] [2 0] [2 0 0] [2 0 0]
Setelah program dijalankan, populasi awal akan dibangkitkan secara acak melalui fungsi inisialisasi. Jumlah individu-individu yang dihasilkan merupakan suatu matriks berdimensi jumlah populasi dengan variabel solusi. Dalam kasus ini, dengan jumlah
105
Vol.16 No.2. Agustus 2014
Jurnal Momentum
ISSN : 1693-752X
sebagaimana tabel di atas. Selanjutnya fungsi evaluasi dapat dinyatakan dalam domain z berupa fungsi alih berikut.
populasi 99 dan variabel solusi yang dicari sebanyak 9 buah, maka jumlah individu membentuk matriks berdimensi 99 x 9. Individu-individu yang menghasilkan nilai fitness fungsi evaluasi paling besar, berarti juga memiliki nilai fitness yang tinggi. Selanjutnya individu-individu (populasi terbaik) tersebut mempunyai peluang paling besar untuk terpilih menjadi induk-induk guna melahirkan populasi baru yang lebih tangguh pada generasi berikutnya. Setelah program dieksekusi maka diperoleh solusi optimal untuk jenis tapis BSF yang memenuhi kriteria perancangan
H(z)BS
0.4295z4 0.0056z3 0.6921z2 0.0006z 0.3484 z4 0.0078z3 0.2501z2 0.0001z 0.2826
Tanggapan magnitude tapis yang didefinisikan kriteria dan fungsi evaluasinya pada Tabel 1, diperlihatkan pada Gambar 2 berikut.
1.4 1.2
H(ej)
1 0.8 0.6 0.4 0.2 0 0
0.2
0.4
0.6
0.8
1
frekuensi
Gambar 4. Tanggapan magnitude tapis hasil perancangan algoritma genetik diperoleh sudah cukup memadai, yakni sesuai dengan kriteria perancangan. Karena itu, sedapat mungkin jumlah variabel diminimalisir dan ruang pencarian solusi tak terlalu lebar. Hal ini akan mengurangi beban komputasi dan lamanya waktu eksekusi, meskipun ini bukanlah masalah utama. b. Jumlah populasi dalam penelitian ini ditetapkan setelah melalui ujicoba trial and error, sehingga tetap ada kemungkinan bahwa jumlah populasi yang dipilih bukan yang memberikan hasil paling optimum. Karena itu frekuensi ujicoba harus lebih tinggi dan jumlah generasi ditetapkan kemudian setelah membandingkan beberapa hasilnya. Jumlah populasi dan generasi berbanding lurus dengan beban dan waktu komputasi. Semakin besar jumlah populasi dan generasi, maka beban komputasi juga semakin besar dan waktu eksekusi
Berdasarkan pada hasil percobaan, terlihat bahwa algoritma genetik memberikan unjukkerja optimal dalam perancangan tapis BSF digital. GA akan menjamin bahwa kriteria perancangan selalu dipenuhi, yaitu stabilitas dan pemenuhan batas tolerans yang diperoleh pada orde tapis terendah. KESIMPULAN Berdasarkan hasil percobaan penelitian dan pembahasan, maka dapat disimpulkan bahwa algoritma genetik bisa digunakan untuk merancang tapis BSF digital secara optimal. Setidaknya ada 2 aspek penting yang sangat mempengaruhi hasil perancangan dengan algoritma genetik. a. Perumusan fungsi evaluasi dan penetapan ruang solusi; terlihat bahwa semakin banyak variabel solusi di dalam fungsi evaluasi, maka algoritma genetik agak kesulitan mencari nilai paling optimal, walaupun secara umum hasil yang
106
Vol.16 No.2. Agustus 2014
Jurnal Momentum
semakin lama. Jumlah populasi yang besar bukan jaminan ditemukannya solusi paling optimal, namun percobaan menunjukkan rentang yang umum yakni dari 70 hingga angka 200. Bagaimanapun jika dibandingkan dengan metode perancangan tapis digital konvensional, ada satu hal yang merupakan kelebihan algoritma genetik. Hal itu adalah adanya jaminan bahwa semua kriteria yang ditetapkan terhadap rancangan tapis digital, akan dipenuhi, baik stabilitas, batas tolerans maupun minimisasi orde filternya. DAFTAR PUSTAKA Davis, Lawrence (edit). 1991. Handbook of Genetic Algorithms. New York : Van Nostrand Reinhold. Goldberg, David E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. New York : AddisonWesley Publishing Company Inc.
ISSN : 1693-752X
Krauss, Thomas P., Shure, Loren dan Little, John N. 1994. Signal Processing Toolbox User’s Guide (for Use with MATLAB). The Mathworks Inc. Kuc, Roman. 1982. Introduction to Digital Signal Processing. New York : McGraw-Hill Book Co. Man, Tang, Kwong dan Halang. 1997. Genetic Algorithms for Control and Signal Processing, Advances in Industrial Control. Grea Britain : SpringerVerlag London Limited. Man, Tang and Kwong. 1996. Genetik Algorithms: Consepts and applications. IEEE Trans. Ind. electron., vol. 43, no. 5, Okt., pp. 519531. Pohlheim, Hartmut.. 1998. Genetic and Evolutionary Algorithms : Principles, Methods and Algorithms. The Mathworks Inc., on his web: www.geatbx.com.
107
