Tutorial Inversi menggunakan Continuous Genetic Algorithm

7:02:00 AM Leo Cahya D 3 Comments

Setelah kemarin saya membuat forward modelling untuk menghitung waktu tiba, sekarang tinggal metode inversinya gimana..

Metode ini bagus buat yang forward enginenya lama menghitungnya karena bisa selesai dalam iterasi yang relatif singkat. Bagus juga untuk parameter skala besar. 

Selama ini sih kendala saya cuma di bagian menghitung derivatifnya itu sendiri.

Yang pernah saya coba : Occam, LM, Gauss Newton.

Metode ini bagus, nggak perlu repot-repot untuk menghitung derivatif dan solusi yang dicari adalah Global Solution diantara constrain parameter yg ditentukan (artinya nggak terjebak di local minima suatu fungsi saat inversi).

Kendala yang saya temuin menggunakan metode-metode tipe ini ya untuk handling parameter yang banyak kurang efektif (misal ratusan/ribuan). Selain itu, kalau forward operatornya lama, pakai yang jenis ini nggak efektif (biasanya butuh sampai ratusan iterasi sekali inversi);

Yang pernah saya coba :VFSA, simple GA, Monte carlo.

Dari metode-metode diatas, yang akan saya coba buat sekarang adalah jenis ke 2, dimana masuk ke dalam Mahzab jenis Genetic Algorithm. Genetic Algorithm (GA) adalah algoritma komputasi yang terinspirasi dari teori evolusi yang kemudian diadopsi untuk mencari solusi suatu permasalahan optimisasi / inversi. Lebih spesifiknya, yang saya akan buat adalah Continous Genetic Algorithm. Sumbernya dari :

Carr, J. 2014. Introduction to Genetic Algorithm.

Kenapa iseng pengen nyobain ini? Karena gak umum banget! Biasanya inversi metode GA itu seluruh parameter dalam kromosom (istilah model parameter dalam Genetic Algorithm) yang dibuat dalam bentuk Binary, jadi gak perlu coding-decoding nilai variabelnya.

 

Supaya lebih paham prosesnya, saya jelaskan dalam bentuk sebuah kasus Curve Fitting atau mencari persamaan dari sebuah kurva.

Misal kita punya data sebagai berikut :

Kita ketahui bahwa bentuk dari persamaan parabola adalah :

F(x)=a.x²+b.x²+c

berarti parameter yang akan kita cari lewat inversi adalah a, b, & c !

Step 1. Buat Populasi

Pada awalnya kita perlu deklarasi secara random sebuah populasi yang terdiri dari sekelompok parameter yang saya namakan individu (dalam simple GA, disebut kromosom, supaya lebih paham saya sebut individu). Saya tentukan satu populasi isinya 12 individu. Nilai parameter tiap individu dibuat batas minimum dan maksimum yang kita tentukan.

Masing-masing parameter tadi dimasukkan ke persamaan parabola, lalu nilai F(x) dihitung. Dihitung selisih F(x) dengan data (error) lalu dibuat ranking mana individu dengan error paling kecil.

Step 2. Survival of the fittest

Setengah dari populasi dengan nilai fittest/error tertinggi akan dieliminasi dari populasi.

Step 3. Kawin <3

Kekosongan individu pada populasi akan diisi oleh anak hasil kawin dari individu-individu yang bertahan. Individu-individu yang kawin ditentukan secara random dengan pembobotan yang dihitung menggunakan persamaan :

Eh...

Kok ini ada kawinnya dua kali ya...

Oke, lupakan, kembali ke topik, parameter dari anak didapat dari kedua orang tua yang saling kawin. Kalau di Simple GA kita lakukan dengan crossing chromosome biner, maka di metode CGA ini dilakukan dengan dua rumus berikut :

Sehingga pada generasi berikutnya kita dapatkan populasi baru :

Pada anak hasil dari perkawinan tiap individu juga dimungkinkan untuk terjadi mutasi, yaitu perubahan nilai dari suatu variabel dengan range antara batas nilai parameter yang ditentukan di awal. Tujuannya agar pencarian nilai parameter tidak mentok di local minima.

Langkah-langkah di atas diulangi kembali sampai sejumlah generasi/iterasi yang dibutuhkan atau sampai nilai error kecocokan data observasi dan data teoritis rendah.

TESTING

Ok, berikut hasil yang telah saya coba. Kira-kira grafiknya seperti berikut. Saya coba hanya dengan 50 iterasi/generasi sudah cukup memuaskan.

So, thats it.

Apakah akan saya aplikasikan ke First Arrival Time Tomography? Mbuh. Nek selo paling. 

aaaand berikut code matlabnya.

See ya,

L