GA Chapter 5

Angka pertama dalam setiap pasangan (warna abu-abu) diterjemahkan sebagai posisi gen, sedangkan angka kedua (warna putih) menunjukkan nilai gen. sehingga gambar ini merepresentasikan skema 00111., dan skema S akan memiliki nilai fitness tinggi.

Pengkodean dengan Panjang Bervariasi [BACK]

Untuk permasalahan dmana akurasi yang diinginkan tidak diketahui, maka pendekatan yang dilakukan dengan menggunakan jumlah bit yang panjang. Contoh pengimplementasian pengkodean ini adalah skema JST dan Travelling Salesman.

Pengkodean untuk Jaringan Syaraf Tiruan (JST) [BACK]

JST merupakan prosesor tersebar parallel yang sangat besar yang memiliki kecenderungan untuk menyimpan pengetahuan yang bersifat pengalaman dan membuatnya siap untuk digunakan.

JST menyerupai otak manusia dalam:

1. Pengetahuan dieroleh jaringan melalui proses belajar

2. Kekuatan hubungan antar neuron (synaptic weights) digunakan untuk menyimpan pengetahuan.

Gambar diatas merupakan model matematis dari neuron, dengan elemen dasarnya yaitu:

a. Sinapsis, yang dikarakteristikkan oleh bobot atau kekuatannya

b. Adder, penjumlah sinyal input yang diberikan bobot oleh sinapsi neuron yang bersesuaian. (aturan yang digunakan adalah liniear combiner)

c. Fungsi aktivasi, membatasi amplitude output setiap neuron.

Berdasarkan gambar, output dari neuron k pada waktu t secara matematis adalah :

Salah satu fungsi aktivasi yang dapat digunakan adalah fungsi sigmoid yang membatasi output pada interval [0,1] dan hyperbolic tangent:

Yang membatasi output dalam interval [-1,1]:

Jenis-Jenis JST:

a. FFNN (Fast Forward Neural Networks)

(FFNN): neuron-neuron disusun kedalam layers, dan sinyal-sinyal mengalir dari input ke layer pertama, lalu kedua, dan seterusnya.

Pada input layer, tidak ada neuron. Elemen ini hanya mendistribusikan sinyal output ke neuron hidden layer, sehingga tidak ada fungsi aktivasi pada input layer ini.

b. Recurrent Neural Network (RNN)

RNN: setiap neuron bisa terhubung dengan neuron yang lain.

Pada RNN, neuron tidak tersusun dalam layer, dan output dari neuronnya:

Karena RNN tidak tersusun dalam layer, maka tidak ada neuron output yang pasti, sehingga beberapa neuron dipilih secara random untuk menjadi output neurons.

Pada bagian kiri merupakan FFNN, dan kanan adalah RNN.

Pelatihan JST

Agar JST dapat mengerjakan suatu komputasi yang diinginkan untuk penyelesaian masalah, maka jumlah neuron dan bobot jaringan harus ditentukan secara tepat. Algoritma yang digunakan untuk training FFNN adalah backpropagation.

Penggunaan AG untuk Pelatihan JST

> Pada dasarnya GA dengan sedikit modifikasi dapat digunakan untuk melatih JST dalam menyelesaikan berbagai masalah.

> Pada training FFNN, GA diterapkan dengan menggunakan perhitungan maju, seperti pada gambar berikut,

> Dengan menggunakan real-number-encoding, FNN dengan 3 neuron (2 di hidden layer, 1 di outpur layer) dikodekan ke dalam kromosom yang berisi 9 gen. dalam hal ini masing-masing gen merepresentasikan bobot jaringan.

> Jumlah neuron hidden layer dalam FFNN ditentukan dengan trial and error atau dengan persamaan berikut:

Untuk RNN, bagaimana GA digunakan untuk mendapatkan struktur yang optimal?

Pada RNN banyak variasi struktur jaringan yang mungkin karena tidak adanya susunan yang teratur seperti pada FFNN. Saat GA digunakan untuk membangun stuktur RNN yang optimal, maka ukuran kromosom akan berubah-ubah selama evolusi, sehingga menyebabkan beberapa masalah.

Digunakan beberapa operator mutasi yang dapat mengubah struktur jaringan dan bobot sinaptik, seperti pada gambar berikut:

Lalu, untuk pindah silang antar jaringan sering menyebabkan penurunan nilai fitness. Namun, terdapat suatu operator pindah silang (averaging crossover) yang dapat memodifikasi jaringan dengan mengaplikasikan pada jaringan yang berukuran sama.

Dalam averaging crossover, nilai gen x dalam dua offspring (anak) dinyatakan oleh x1 dan x2:

Pengkodean untuk Traveling Salesman Problem [BACK]

> Traveling Salesman Problem (TSP) merupakan salah satu masalah optimasi kombinatorial.

> Konsepnya : bagaimana cara menemukan rute perjalanan paling murah dari suatu kota dan mengunjungi semua kota lainnya, masing-masing kota dikunjungi satu kali dan harus kembali ke kota asal

> TSP dirumuskan: sekumpulan N node dengan koordinat {xi, yi}, dengan i=1,2,...,N. seperti pada gambar berikut:

Cara GA menyelesaikan TSP:

a. Suatu solusi direpresentasikan ke dalam suatu kromosom yang berisi nomor urut dari semua kota yang ada.

b. Masing-masing nomor urut kota hanya boleh muncul satu kali, sehingga satu kromosom merepresentasikan satu rute perjalanan (permutation encoding).

contoh:

Dalam TSP, operator pindah silang dan operator mutasi harus diimplementasikan secara hati-hati untuk menghindari rute yang tidak valid. Pindah silang diimplementasikan dengan order crossover, seperti pada gambar berikut:

Pada TSP, operator mutasi biasanya diimlementasikan dengan menukarkan gen termutasi dengan gen lain yang dipilih secara random. Misal kromosom {2,3,4,1,5} dapat termutasi menjadi kromosom {4,3,2,1,5}. Proses ini disebut dengan swapping mutation.

Grammatical Encoding [BACK]

> Dalam AG, pengkodean yang mengodekan suatu prosedur untuk membangun JST disebut grammatical encoding schemes. Pada skema ini kromosom dipadang sebagai kalimat yang diekspresikan menggunakan tata bahasa.

> Ketika sebuah kalimat dibaca (kromosom dikodekan), maka individu dibangkitkan menggunakan tata bahasa tersebut.

> Pada skema kitanno, setiap kromosom dikodekan ke dalam suatu string seperti gambar berikut:

> S merupakan start symbol, yang saat dibaca, S akan membangkitkan sebuah matriks yang berisi 4 simbol.

S dan keempat simbol tersebut disebut dengan non-terminals (simbol yang ketika dibaca akan membangkitkan struktur lain > baik terminals maupun non-terminals). terminals merupakan simbol-simbol yang tidak akan diproses lebih lanjut.

Kitano menggunakan 25 huruf kapital untuk non-terminals, sehingga kombinasi simbol non terminals berjumlah 26^4. Setiap huruf kapital ini mengodekan suatu matriks berukuran 2x2 yang berisi 4 huruf kecil (a sampai p). Sehingga, simbol terminals adalah 16^4, contoh terminals sebagai berikut:

Setiap huruf kecil mengodekan suatu matriks biner berukuran 2x2 dengan aturan sbb:

Prosedur penyelesaiannya:

a. bangkitkan matriks 2x2 yang berisi empat huruf besar.

b. bangkitkan matriks 4x4 yang berisi 16 huruf kecil

c. bangkitkan matriks 8x8 yang berisi bilangan biner.

Nilai 1 pada matriks representasi JST (matriks 8x8) ini menunjukkan adanya koneksi, dan 0 menunjukkan tiadanya koneksi.

2. Seleksi Orang Tua [BACK]

Tournament Selection [BACK]

> Metode turnamen ini mengambil dua kromosom secara random, kemudian menyeleksi salah satu yang bernilai fitness paling tinggi untuk menjadi parent pertama.

> Untuk metode yang lebih rumit, adalah mengambil m kromosom secara random lalu kromosom dengan nilai fitness tertinggi akan dipilih jika bilangan random yang dibangkitkan kurang dari nilai batas yang ditentukan (p= [0,1)).

> Pemilihan orang tua akan dilakukan secara random dari m-1 kromosom yang ada jika bilangan random yang dibangkitkan lebih atau sama dengan p.

catatan:

m = tounament size (nilainya sangat kecil, biasanya 4 atau 5)

p = tournament probability (sekitar 0.75)

Seleksi Boltzmann [BACK]

> Konsep ini berdasarkan konsep pemanasan dan pendinginan, atau annealing. Pada skema seleksi ini digunakan parameter T (temperatur) untuk mengatur tingkatan nilai fitness individu.

> Cara untuk pengimplementasian skema ini adalah memilih satu dari sepasang individu yang diambil secara random, berdasarkan fungsi berikut:

> Selama seleksi, sebuah bilangan random r dibangkitkan dan individu j dipilih berdasarkan:

> Jika T bernilai kecil mendekati 0, dan fj1 > dari fj2, maka individu j1 akan terpilih dengan probabilitas mendekati 1, dan sebaliknya.

Alternatif Lainnya:

Seleksi Kompetitif dan Co-Evolution [BACK]

Pada dunia nyata, fungsi fitness tidak ada yang mutlak, oleh karena itu nilai fitness dari suatu individu bergantung kepada individu lain dalam spesies yang sama, maupun yang berbeda. Hal inilah yang mendasari terjadinya skema seleksi competitive selection, yang selalu terhubung dengan co-evolution.

Dalam GA, co-evolution sering diterapkan untuk dua populasi dimana nilai fitness dari individu-individu pada populasi pertama diperoleh dari interaksi dengan individu pada populasi kedua, dan sebaliknya.

Namun, karena nilai fitness tetap ini tidak mudah dilakukan, maka co-evolution jarang digunakan dalam GA.

3. Nilai Fitness [BACK]

Optimasi untuk Banyak Tujuan [BACK]

Pareto-optimality

Misalkan ada vektor x menjadi solusi potensial untuk masalah optimasi, dengan kriteria fi adalah fi(x), i=1,2,...,K. K merupakan kriteria optimasi. Vektor x merupakan pareto-optimal jika tidak ada individu y sedemikian sehingga fi(y) ≥ fi(x), dan fi(y) > fi(x) untuk paling sedikit satu j, dimana j=1,2,...,K.

Optimasi dengan Batasan [BACK]

> Pada bagian sebelumnya dilakukan tanpa ada batasan, jika ditambahkan dengan sejumlah fungsi kriteria, maka permasalahan tersebut menjadi constrained optimization.

Terdapat dua jenis batasan:

a. Soft constrains (boleh dilanggar, tapi nilai fitness akan lebih rendah)

b. Hard constrains (tidak boleh dilanggar)

4. Pindah Silang dengan Batasan [BACK]

SubPopulasi [BACK]

> Pada metode ini N kromosom dalam satu populasi akan dbagi menjadi Nk kelompok. Masing-masing kelompok berisi v=N/Nk individu. Di metode ini crossover dan mutasi hanya terjadi pada subpopulasi.

> Tujuan subpopulasi adalah menghindari konvergensi prematur.

> Agar jumlah individu dalam subpopulasi tidak berubah, maka suatu individu dipilih secara random untuk dipindah ke subpopulasi lainnya.

+ Poin plus dari menggunakan batasan ini adalah prosesnya dapat dikerjakan secara paralel dan terdistribusi ke beberapa komputer.