~
PEMANF AA T AN ALGORITMA GENETIKA UNTUK ANALISIS DATA HAMBURAN NEUTRON A. Purwanto Puslitbang Iptek Bahan -BATAN; Kawasan PuspiptekSerpong, Tangerang
ABSTRAK PEMANFAATANALGORITMAGENETIKAUNTUKANALISIS DATA HAMBURANNEUTRON.Berbagaiprosedurpencocokanuntuk analisa data, seperti metodaLeast Squares, MaximumEntropy,dan Reve.rsedMr;nte Carlo, te!ah banyak dikembangkandan diterapkanpada berbagaibidang. AlgoritmaGenetikamulai banyak pula digunakanpada berbagaibidangtermasukilmu pengetahuandan permainan. Teknik ini cukup handal dan dapat dikembangkanuntuk ruang lingkup yang cukup luas. Pada makalah ini dibahas usaha untuk menerapkanalgoritma genetika untuk analisa data hamburanneutron pada PuslitbangIPTEK bahan, BATAN,Serpong. Beberapakeunggulandibandingkandengan metodalain dan rencanakerja berikutnyajugadibahas.
ABSTRACT GENETIC ALGORITHM FORNEUTRON SCATTERING DATAANALYSIS. Variousfittingprocedure in dataanalysis,suchas Least SquaresMethods,MaximumEntropy,and ReversedMonteCarlo,havebeenwell established and appliedin manyareas. Recently,genetic algorithm hasalsobeenappliedin variousfieldsincluding gamesandsciences.GeneticAlgorithm technique is robustandcandealsuccessfully witha widerangeof problem areas. Thispaperdiscusses attemptsin applyingthealgorithm for neutronscattering dataanalysisattheResearch and Development Centerfor Materials ScienceandTechnology, BATAN,SerpongSeveraladvantages as compared to othermethodsandfuther worksarehighlighted.
PENDAHULUAN Teknik hamburan neutron yang terdiri dari difraksi dan spektrometri neutron merupakan salah satu teknik yang cukup handal untuk mempelajari sifat bahan secara mikroskopik. Karena tinjauannya yang mikroskopik, analisis datanya melibatkan pembuatan model clan perhitungan yang tidak sederhana. Prinsip analisis datanya adalah menentukan parameter optimal dari suatu model sehingga memberikan hasil perhitungan yang mendekati data pengamatan. Hal tersebut melibatkan proses pencocokan (fitting) antara basil perhitungan terhadap data pengamatan. Semakin kecil perbedaan antara hasil perhitungan dengan data pengamatan, semakin optimal parameter dari model tersebut sehingga dapat dinyatakan bahwa model tersebut didukung oleh data pengamatan. Metoda pencocokan yang paling sering digunakan adalah metoda least-squares yang digunakan antara lain pada perangkat lunak GSAS [1] ataupun RIETAN. Metoda ini cukup handal namun mengandung dua kelemahan. Pertama, metoda ini cenderung terperangkap pada minima lokal clan error bar untuk setiap parameter adalah error bar lokal, meskipun ada
14
~I
teknik-teknik untuk menghindarinya [2]. Hal ini merupakan kelemahan yang serius karena yang harus dicari adalah minima global, bukan minima lokal. Kedua, metoda ini membutuhkan turunan order ke-2 dari fungsi yang akan diminimalkan. Hal ini menyulitkan pengembangan perangkat lunak terutama untuk fungsifungsi yang tidak sederhana. Jika penurunan fungsi dilakukan secara analitik, kemungkinan kesalahan sistematik dapat timbul. Jika dilakukan penurunan fungsi secara diskrit (numerik), akan terdapat kesalahan pembulatan. Algoritma genetika (AG) adalah metode adaptif yang dapat digunakan untuk melakukan proses pencarian dan optimasi. Dasar algoritma tersebut adalah proses genetik dari organisme biologi. Melalui banyak generasi, populasi alamiah berevolusi sesuaidengan prinsip seleksi alam dan survival of the fittest sebagaimanapertama kali dikemukakan oleh Charles Darwin dalam The Origin of Species. Dengan meniru proses ini, algoritma genetika mampu mengevolusikan penyelesaian ke problem nyata jika algoritma tersebut dibuat dengan benar. Misalnya, AG dapat digunakan untuk merancang struktur jembatan
2'JJ~ 2000
~
p~
dengan perbandingan kekuatanlbobot yang maksimum, atau untuk menentukan sisa potongan yang terbuang daTi kain. AG dapat pula digunakan untuk kontrol proses online, seperti pada pabrik kimia atau penyeimbang bebanpada sistem komputer dengan multi-processor. Pada makalah ini dibahas pemanfaatan algoritma g~netika untuk menganalisis data hamburan neutron. Pemanfaatan tersebut merupakan langkah awal untuk membuat suatu perangkat lunak untuk menganalisis data hamburan neutron secarautuh.
PRINSIP DASAR Prinsip dasar dari AG pertarna kali dikemukakan secarajelas oleh Holland [3] daDkemudian banyak dikemukakan pacta banyak artikel lain [4][5]. AG mensimulasi proses tersebut pacta populasi natural yang merupakan dasar dari evolusi. Proses biologi mana yang terpenting, yang berperan kecil atau tidak berperan sarna sekali untuk evolusi memang masih merupakan bahan penelitian, namun dasamya cukup jelas. Dalam alam, individu dalam populasi saling bersaing untuk memperoleh surnber seperti makanan, air dan tempat tinggal. Anggota dari spesiesyang sarnajuga bersaing untuk menarik pasangan. lndividu-individu yang paling berhasil bertahan daD menarik pasangan akan mempunyai relatif lebih banyak keturunan. Individu dengan kemampuan minim akan menghasilkan sedikit atau bahkan tidak actaketurunan sarna sekali. Hal ini berarti bahwa gen dari individu yang paling fit akan menyebar sehingga menambah individu dalam setiap generasi berikutnya. Kombinasi sifat baik dari moyang yang berbeda sering dapat menghasilkan keturunan yang superfit dimana fitness -nya lebih besar daripada fitness orangtuanya. Dengan cara ini, spesies berevolusi untuk menjadi semakin baik untuk lingkungannya. AG menggunakan analogi langsung dari sifat natural. Algoritma ini menggunakan populasi dari individu-individu yang masing-masing mewakili penyelesaian yang mungkin untuk problem yang diberikan. Masing-masing individu mempunyai nilai fitness sesuai dengan kelayakan suatu penyelesaian pacta problem. Misalkan, nilai fitness dapat berupa perbandingan kekuatan/bobot untuk suatu rancangan jembatan (dalam alam, hal ini berarti seberapa efektif suatu organisme bersaing untuk memperoleh surnber). Individu yang sangat fit memperoleh kesempatan untuk reproduce dengan cross breeding dengan individuindividu dalam populasi. Proses ini menghasilkan individu-individu baru sebagai keturunannya yang memiliki beberapa sifat yang sarna dengan sifat orangtuanya. Anggota yang sangat lemah akan tidak mempunyai kemungkinan untuk terpilih untuk berreproduksi, sehingga spesiesnya akan punah. Mula-mula dibuat coding (representasi) yang sesuai. Kita juga membutuhkan fungsi fitness. Dalam eksekusinya, parents harus diseleksi untuk reproduksi daD rekombinasi untuk menghasilkan keturunannya.
~I
A~
C;~
l/~
A~
!)..:t... Ht
N~ A,P'-"'i/l~
Populasi barn yang merupakan penyelesaian yang mungkin diproduksi dengan cara pemilihan individu terbaik dari generasi tertentu clan memasangkannya dengan individu lain untuk menghasilkan sekumpulan individu barn. Generasi baru ini mengandung lebih banyak sifat baik dibandingkan dengan yang dimiliki oleh generasiterdahulu. Dengan cara ini, setelah melalui banyak generasi, sifat baik tersebar, tercampur clan bertukaran di seluruh populasi. Dengan menyukai pasangan yang lebih fit, digali daerah yang lebih baik dalam ruang problem. Jika AG telah dirancang dengan baik, populasi akan konvergen menuju suatu penyelesaianyang optimal. Algoritmanya dapat dilihat pada Gambar 1.
)
('--
Selesai ~
Gambar 1. Diagram alir algoritma genetika sederhana Keunggulan AG bermula dari kenyataan bahwa teknik ini cukup andal clan dapat diterapkan pada berbagai problem termasuk problem yang sulit dipecahkan dengan metoda lain. AG tidak dijamin untuk dapat menemukan optimum global pada suatu problem,
2gJ~ 2000
15
.
p~
A~
G~
U+oM,J,. A~ ~ H~
N~ A.P tl/~
namun secara umum AG cukup baik untuk menemukan penyelesaian yang dapat diterima baik dalam waktu yang relatif cepat. Jika teknik khusus tersedia untuk problem tertentu, kecepatan dan akurasi AG dapat dikalahkan. Keunggulan AG oleh karenanya terletak pacta problem sulit dimana tidak acta teknik penyelesaian yang dapat digunakan. Bahkan jika acta teknik khusus tersebut, perbaikan dapat dilakukan dengan menggabungkan teknik tersebut denganAG. Coding/Representasi Penyelesaian yang mungkin terhadap suatu problem dapat dinyatakan sebagai sekumpulan parameter (misalkan, dimensi dari jembatan pada perancangan jembatan). Parameter ini (dikenal sebagai gen) digabungkan untuk membentuk nilai dari string (sering disebut sebagai kromosom). Literatur menunjukkan bahwa yang terbaik adalah menggunakan alt'abet biner dari string. Misalkan, pada problem untuk memaksimalkan fungsi dari 3 variabel F(x,y,z) kita dapat menyatakan masing-masing variabel dengan bilangan biner 10-bit (dengan skala yang sesuai). Kromosom untuk problem ini mengandung 3 gen dan terdiri dari 30 digit biner. Dalam istilah genetik, sekumpulan parameter yang dinyatakan sebagai kromosom tertentu disebut sebagai genotipe. Genotipe mengandung informasi yang dibutuhkan untuk membuat organisme -yang sering disebut sebagai fenotipe. Istilah yang sama digunakan dalam AG. Sebagai contoh dalam perancanganjembatan, sekumpulan parameter untuk rancangan tertentu disebut sebagaigenotipe sedangkan konstruksi yang telah selesai disebut sebagai fenotipe. Fitness dari suatu individu tergantung pada unjuk kerja fenotipe. Hal ini dapat disimpulkan dari genotipe, yaitu dapat dihitung dari kromosom dengan menggunakan fungsifitness. Fungsi Fitness Fungsi fitness harus dibuat untuk masingmasing problem yang akan diselesaikan. Jika diberikan kromosom tertentu, fungsi fitness mengembalikan nilai fitness atau figure of merit tunggal yang dianggap sebanding dengan utility atau kemampuan individu yang mempunyai kromosom tersebut. Untuk banyak problem, khususnya optimasi fungsi, fungsi fitness merupakan nilai dari fungsi itu sendiri. Namun, hal ini tidak selalu demikian, misalkan untuk optimasi kombinatorial. Dalam perancanganjembatan yang nyata, banyak ukuran unjuk kerja yang hams dioptimasi: perbandingan kekuatan/bobot, lebar, beban maksimum, harga, waktu konstruksi -atau bahkan kombinasi dari semuanya.
yang bagus mungkin dipilih beberapa kali dalam suatu generasi,yang buruk tidak dipilih sarnasekali. Setelah memilih dua parent, kromosomnya digabungkan dengan mekanisme crossover dan mutasi. Bentuk yang paling mendasar dari operator-operator ini adalah sebagai berikut. Crossover mengambil dua individu dan memotong string kromosom pada posisi yang dipilih secara acak untuk menghasilkan dua segmen kepala dan dua segmen ekor. Argumen ekor ditukar untuk menghasilkan dua kromosom dengan panjang penuh yang baru (Gambar 2). Dua keturunan mempunyai gen yang diturunkan dari masing-masing parent-nya. Proses ini dikenal sebagai single point
crossover. Titik Crossover
OIOC
Parent
0
~010010
J! Offspring
I 010
0 I 00 I 0
1 0011001110
-+ Gambar 2. Single Point Crossover Crossover tidak selalu diaplikasikan pada semua pasangan individu yang diseleksi untuk berpasangan. Pilihan acak dilakukan dimana kemungkinan crossover dilakukan biasanya diantara 0,6 dan 1,0. Jika crossover tidak diaplikasikan, keturunan dihasilkan hanya dengan menggandakan parent-nya. Hal ini memungkinkan masing-masing individu untuk tetap hidup tanpa terganggu dengan crossover. Mutasi diaplikasikan pada masing-masing child sesudah crossover. Mutasi mengubah masing-masing gen secara acak dengan probabilitas yang kecil (biasanya 0,001). Gambar 3 menunjukkan gen ke-5 daTi kromosom yang mengalami mutasi. Untuk penelusuran ruang pencarian, crossover berperan lebih penting daripada mutasi. Mutasi memberikan sejumlah kecil pencarian acak dan memastikan pemeriksaan bahwa tidak ada titik dalam ruang pencarian yang mempunyai probabilitas nolo
Titik mutasi
~ Offspring
010210010
Reproduksi
Selama rasa reproduksi AG, individu dipilih dari populasi clan digabungkan, menghasilkan keturunan yang menyusun generasi berikutnya. Parent dipilih
Offspringtermutasi
secaraacak dari populasi denganmenggunakanskema yang menguntungkanindividu yang lebih fit. lndividu
16
~I
2rtJ~ 2000
010110010
Gambar 3. Mutasi Tunggal
Y
p~
A~
G~
U~
Aw.t;.":.,, l>..,1.Ht
N...t..A. PWl-ill~
Konvergensi Jika AG telah diimplementasikan secara bellar, populasi akan ber-evolusi menghasilkan generasigenerasi dengan fitness yang semakin baik dan individu rata-rata pada setiap generasi bertarnbah menuJu optimum global. Konvergensi merupakan kemajuan menuju keseragaman. Gen dikatakan telah konvergen jika 95% daTi populasi mempunyai nilai yang sarna. Populasi dikatakan konvergen jika semua gen telah konvergen.
i
-]
\2
data r (I)
dengan
Ihi' (2) lnormhanya berfungsi sebagai skala. Pada tahap awal ini error belum dirambatkan daTipengamatan.
METODAPEROLEHANDATA Perolehan data sangat tergantung pada peralatan yang tersedia. Peralatan hamburan neutron yang digunakan untuk pengukuran adalah SANS dan HRPD yang tersedia di BATAN, Serpong. Namun demikian, banyak alat serupa yang tersedia pada berbagai fasilitas neutron dengan sumber reaktor seperti JAERI-Jepang, CRL-Canada, ORNL-Amerika. Data serupa bahkan dapat pula diperoleh daTi sumber spalasi seperti yang tersedia di ISIS-Inggris, LANL- dan ANL-Amerika. Reduksi data merupakan tahapan renting sebelum analisis data. Dalam proses reduksi ini, data yang tidak mengandung informasi langsung mengenai bahan dikoreksi sehingga informasi yang didapat dalam analisis data hanya mengenai informasi tentang bahan dan tidak tergantung pada instrumen atau tempat dimana eksperimen dilakukan. Namun untuk analisis difraksi sudut lebar daTi cuplikan berbentuk serbuk untuk penentuan struktur kristal dengan metoda Rietveld [6] proses reduksi tersebut dapat disatukan dengan analisis data. Proses yang dapat dikatakan merupakan proses data reduksi tersebut antara lain adalah perhitungan cacah latar belakang, faktor Lorentz dan resolusi alat yang mempengaruhi profil puncak difraksi.
PENERAPAN ALGORITMA PUSLITBANG IPTEK BAHAN
= L(I hit
GENETIKA DI
Walaupun algoritma genetika mempunyai banyak keunggulan dibandingkan dengan teknik lain, penerapanalgoritma ini masih dalam tahap awal di P31B. Optimasi parameter berdasarkan algoritma ini telah diterapkan untuk analisis data SANS dan HRPD. Pengembangan lebih lanjut sedang dilakukan sehingga diharapkan teknik dengan algoritma genetika dapat diterapkan pada perangkat lunak untuk analisis struktur kristal daTipola difraksi serbuk. Pernrograman dilakukan denganbahasa C++ dan pustaka GALlB [7].
Analisis dataSANS Gambar 4 menunjukkan basil perhitungan dan data pengamatan dari SANS yang diambil daTi serbuk NdFeB. Reduksi data telah dilakukan pada data tersebut. Model yang digunakan didasarkan pada asumsi bahwa bentuk butirnya adalah bola sehingga fungsi yang harus di minimumkan adalah:
~,
Ana/isis data HRPD Gambar 5 menunjukkan gaussian fitting dengan menggunakan algoritma genetika. Data diperoleh dari difraktogram serbuk silikon standar yang diukur dengan menggunakan HRPD. lntensitas perhitungan lhil pacta Pers.(l) adalah
I mt.=
I latar + I maks x eXD '
x-x maks Lebar
(3) dengan Ilatar, Imak" X..ak, dan lebar masing-masing merupakan intensitas Jatar belakang, intensitas maksimum, posisi (sudut hamburan) dimana intensitas adalah maksimum dan parameter yang berkaitan dengan lebar puncak. FWHM (Full Width at Half Maximum) dari puncak sesuai dengan profil Gaussian tersebut dan dapat dinyatakan sebagai:
FWHM = 2 x lebar x JI-;;2
(4)
Lebih lanjut, program komputer yang telah dibuat dapat dengan mudah diterapkan pada PO di BA TAN yang
2ftJ~ 2000
17
-.
P~A~G~U~A~~H~N~ A. P..w~
digunakan untuk menganalisis tegangan sisa. Kemudahan tersebut adalah karena PD terutarna digunakan untuk memperoleh inforrnasi mengenai posisi puncak dengan profil Gaussian. Secara kualitatif, terlihat bahwa hasil perhitungan sudah mendekati data pengamatan dengan parameter optimal intensitas latar belakang, intensitas maksimum, posisi puncak dan lebar kurva yang masing-masing adalah 23,56; 937,18; 56,66; dan 0,14. 1000
I
I I
HBsllPerhitungan DataPengamatan Sd~ih
800
Gambar 6. Susunan atom silikon dalam sel satuan 2-D (bangun dengan garis tidak terputus). Arah sumbu a, b dan c masing-masing ke bawah, kanan dan ke arah pembaca. Angka menunjukkan posisi pada arah sumbu-c. Bangun dengan garis terputus adalah sel satuan lain yang dapat digunakan dengan sumbu koordinat digeser (1/8, 118, 1/8) [9].
600
B .a
~c
400 200
0
.O,"..L'.,,",Y '
...'
-200
55.5
.
I
56
56.5
57
57.!
58.5
58
Sudut Hamburan, derajat
Gambar 5. Gaussian fitting dengan algoritma genetika. Parameter optimal intensitas jatar, intensitas maksimum, posisi puncak dan lebar kurva masing-masing adalah 23,56; 937,18; 56,66; dan 0,14. Kemungkinan penggunaan algoritma genetika untuk menganalisis difraktogram HRPD secara lengkap tengah dilakukan dengan dimulainya perhitungan intensitas difraksi untuk silikon standar yang diperoleh dengan HRPD. Perhitungannya didasarkan pada [8]: I
40
.2
80
100
120
140
SudutHamburan,derajat Gambar 7. Pola difraksi serbuk silikon standard yang diperoleh dengan HRPD, BATAN. Optimasi parameter belum dilakukan.
Ihit
(5) dengan fnorm,.fj, 't dan dj masing-masing menunjukkan faktor skala, panjang hamburan untuk atom ke-J,indeks Miller dan posisi atom ke-j dalam sel satuan. Untuk difraksi dengan cuplikan serbuk silikon standar, posisi atom yang dimasukkan adalah (1/8, 118,1/8); (1/8, 518, 5/8); (5/8, 118,5/8); (5/8, 518, 1/8); (7/8, 318, 3/8);
(7/8, 718, 7/8); (3/8, 318, 7/8); (3/8, 718, 3/8) (lihat Gambar 6). Posisi atom tersebut menunjukkan'"bahwa grup ruangnya [10] adalah F d -3 m (192). Posisi puncak difraksi berkaitan dengan parameter kisi a=5,4307 A. Sebagai catalan, analisis difraksi lengkap dapat dibagi menjadi dua bagian yaitu analisis berdasarkan posisi puncak daD posisi atom (dengan refinement). Metoda Hanawalt atau JCPDF hanya memanfaatkan posisi puncak. Analisis lengkap yang melibatkan posisi puncak daD atom diharapkan dapat dilakukan dengan perangkat lunak yang sedang dibuat
ini.
18
60
~,
Gambar 7 menunjukkan perhitungan intensitas difraksi yang berimpit dengan data difraksi HRPD dari serbuk silikon standar. Terlihat bahwa posisi puncak antara hasil perhitungan dengan data pengamatan sudah sesuai. Namun demikian, intensitasnya masih jauh dari sesuai yang menunjukkan bahwa parameter dari model yang digunakan untuk perhitungan masih belum optimal. Optimasi parameter tersebut akan dilakukan dengan algoritma genetika.
KESIMPULAN Algoritma genetika mulai diterapkan di Puslitbang IPTEK Bahan, BAT AN untuk optimasi parameter daTi suatu model sehingga basil perhitungan mendekati data pengamatan. Algoritma genetika terbukti dapat menggantikan metoda tradisional seperti leas/squares yang membutuhkan turunan sampai order ke-2.
2rtJ~ 2000
[2].
p~
A~
G~
U~ A~
~
1:I t.."
N~ A. Pw~
Pengembangan perangkat lunak untuk analisis data hamburan neutron dengan algoritma genetika masih terus diupayakan. UCAP AN TERIMAKASIH
PenulisberterimakasihkepadaDr. A. Ikram, Ir. S. M. Prasetyo,dan Indarto atas bantuanpengambilan data SANS. Penulisjuga menghargaiTrihardi M.T. dan H. MugiraharjoatasbantuanpengambilandataHRPD. DAFTAR PUSTAKA [I],
C. LARSON DAN R. B. VON DREELE, GSASGeneral Structure Analysis System,Los Alamos NationalLaboratoryReportNo. LA-UR-86-748. W. H. PRESS, S. A. TEUKOLSKY, W. T. VETTERLING DAN B. P. FLANNERY, Numerical Recipesin C, CambridgeUniv. Press, 1992,HIm. 681-188.
[3]. J. H. HOLLAND. Adaptation in natural and artificial systems.MIT Press,1975 [4]. L. DAVIS. Genetic Algorithms and Simulated Annealing.Pitman1987. [5]. L. DAVIS. Handbook of GeneticAlgorithms. Van NostrandReinhold,1991. [6]. H. M. RIETVELD, J. Appl. Crystallogr. 2, 65 ( 1969). [7]. M. WALL, GALIB: A C++ Library of Genetic .4Igorit.hmComponents,MIT, Amerika, versi 2.4, August1996. [8]. G. L. SQUIRES, Introduction to the Theory of Thermal Neutron Scattering, Cambridge Univ. Press,1978,hIm 37. [9]. C. KITTEL, Introduction to Solid State Physics, John Willey & Sons,Inc., 1986,hIm. 19. [10]. International Tablesfor Crystallography,ed. T. Hahn (International Union of Crystallography, 1987),Vol. A.
TANYA-JAWAB Penanya:Ir. MoharnadRarnlan,M.Sc. (UPT LSDE -BPPT) 1. Model matematikaapakahyangdigunakan? 2. Variabelapakahyangdigunakandalarngeneticalgorithm? 3. Bahasakomputerapakahyangdigunakan? Jawaban:
2.
Model matematika yang digunakan adalah simple formula yaitu Gaussian dan Exponential Variabel yang dipakai adalah:
3.
-jumlah populasi -presentasi mutasi -presentasi crossover Bahasa pemrograman yang dipakai adalah C language
1.
~I
Ke Menu Utama
19
2gJ~ 2000
Ke Daftar Isi
