Genetika_algoritma.docx

Tugas III Kercerdasan Buatan GENETIKA ALGORITMA

Diajukan untuk memenuhi Tugas Mata Kuliah Kecerdasan Buatan (Artificial Intelligent)

Oleh : Nama : Steven Lim NPM : 1421021

JURUSAN TEKNIK ELEKTRO FAKULTAS TEKNIK INDUSTRI UNIVERSITAS INTERNASIONAL BATAM 2015

Bab I Landasan Teori Algoritma genetika merupakan evolusi/ perkembangan dunia komputer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan. Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika sama dengan apa yang terjadi pada evolusi biologi Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministic. Metodenya sangat berbeda dengan kebanyakan algoritma optimasi lainnya, yaitu mempunyai ciri-cirinya sebagai berikut :

1. Menggunakan hasil pengkodean dari parameter, bukan parameter itu sendiri. 2. Bekerja pada populasi bukan pada sesuatu yang unik. Menggunakan nilai satu-satunya pada fungsi dalam prosesnya. 3. mengunakan fungsi luar atau pengetahuan luar lainnya. 4. Menggunakan fungsi transisi probabilitas, bukan sesuatu yang pasti. Algoritma genetika yang dikembangkan oleh Goldberg adalah algoritma komputasi yang diinspirasi teori evolusi Darwin yang menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat adalah yang menang”. Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk dapat dipertahankan melalui proses reproduksi, crossover, dan mutasi. Konsep dalam teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”

2

Golberg (1989) mengemukakan bahwa algoritma genetik mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain, yaitu: 1. Algoritma genetik dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dean bukan parameter itu sendiri. 2. Algoritma genetik pencarian pada sebuah solusi dari sejumlah individuindividu yang merupakan solusi permasalahan bukan hanya dari sebuah individu. 3. Algoritma genetik informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi. 4. Algoritma genetik menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministic. Sebuah solusi yang dibangkitkan dalam algoritma genetika disebut sebagai chromosome, sedangkan kumpulan chromosome-chromosome tersebut disebut sebagai populasi. Sebuah chromosome dibentuk dari komponen-komponen penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol ataupun karakter tergantung dari permasalahan yang ingin diselesaikan. Chromosome-chromosome tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi chromosome-chromosome tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan (fungsi_objektif) menggunakan ukuran yang disebut dengan fitness. Untuk memilih chromosome yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses seleksi chromosome menggunakan konsep aturan evolusi Darwin yang telah disebutkan sebelumnya yaitu chromosome yang mempunyai nilai fitness tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya. Chromosome-chromosome baru yang disebut dengan offspring, dibentuk dengan cara melakukan perkawinan antar chromosome-chromosome dalam satu

3

generasi yang disebut sebagai proses crossover. Jumlah chromosome dalam populasi yang mengalami crossover ditetukan oleh paramater yang disebut dengan crossover_rate. Mekanisme perubahan susunan unsur penyusun mahkluk hidup akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam chromosome dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan mutation_rate. Setelah beberapa generasi akan dihasilkan chromosome-chromosome yang nilai gen-gennya konvergen ke suatu nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap permasalahan yang ingin diselesaikan. Perbandingan istilah alam dengan Algoritma Genetika : Table 1.1 Tabel Perbandingan Alam dengan GA. Alam Algoritma Genetika Chromosome

String

Locus

Posisi String

Gene

Karakter

Allele

Nilai Karakter

Genotype

Struktur

Phenotype

Kode Struktur

Algoritma genetik merupakan proses pencarian yang heuristik dan acak sehingga penekanan pemilihan operator yang digunakan sangat menentukan keberhasilan algoritma genetik dalam menemukan solusi optimum suatu masalah yang diberikan. Hal yang harus diperhatikan adalah menghindari terjadinya konvergensi premature, yaitu mencapai solusi optimum yang belum waktunya, dalam arti bahwa solusi yang diperoleh adalah hasil optimum local. Operator genetik yang digunakan setelah proses evaluasi tahap pertama membentuk populasi baru dari generasi sekarang. Operator-operator tersebut adalah operator seleksi, crossover dan mutasi.

4

1. Seleksi Seleksi bertujuan memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit. Langkah pertama dalam seleksi ini adalah pencarian nilai fitness. Masing-masing individu dalam suatu wadah seleksi akan menerima probabilitas reproduksi yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam wadah seleksi tersebut. Nilai fitness inilah yang nantinya akan digunakan pada tahap seleksi berikutnya. Kemampuan algoritma genetik untuk memproduksi kromosom yang lebih baik secara progresif tergantung pada penekanan selektif (selective pressure) yang diterapkan ke populasi. Penekanan selektif dapat diterapkan dalam dua cara. Cara pertama adalah membuat lebih banyak kromosom anak yang dipelihara dalam populasi dan memilih hanya kromosom-kromosom terbaik bagi generasi berikut. Walaupun orang tua dipilih secara acak, metode ini akan terus menghasilkan kromosom yang lebih baik berhubungan dengan penekanan selektif yang diterapkan pada individu anak tersebut.

2. Crossover Crossover bertujuan untuk menambah keanekaragaman sting dalam populasi dengan penyyilangan antara string satu dengan string lainya yang diperoleh sebelumnya. Crossover memiliki beberapa jenis yaitu : a) Crossover 1-titik. Pada crossover dilakukan dengan memisahkan suatu string menjadi dua bagian dan selanjutnya salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain yang telah dipisahkan dengan cara yang sama. Proses yang demikian dinamakan operator crossover satu titik. Tabel 1.2 Contoh Crossover 1-titik Kromosom Orangtua 1

11001011

Kromosom Orangtua 2

11011111

Keturunan

11001111

b) Crossover 2-titik. 5

Proses crossover ini dilakukan dengan memilih dua titik crossover. Kromosom keturunan kemudian dibentuk dengan barisan bit dari awal kromosom sampai titik crossover pertama disalin dari orangtua pertama, bagian dari titik crossover pertama dan kedua disalin dari orangtua kedua, kemudian selebihnya disalin dari orangtua pertama lagi.

Tabel 1.3 Contoh Crossover 2-titik Kromosom Orangtua 1

11001011

Kromosom Orangtua 2

11011111

Keturunan

11011111

c) Crossover Seragam. Crossover seragam manghasilkan kromosom keturunan dengan menyalin bit-bit secara acak dari kedua orangtuanya.

Tabel 1.4 Contoh Crossover seragam Kromosom Orangtua 1

11001011

Kromosom Orangtua 2

11011111

Keturunan

11011111

3. Mutasi. Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom. Operasi crossover yang dilakukan pada kromosom dengan tujuan untuk memperoleh kromosom-kromosom baru sebagai kandidat solusi pada generasi mendatang denga fitness yang lebih baik, dan lama-kelamaan menuju solusi optimum yang diinginkan. Akan tetapi, untuk mencapai hal ini, penekanan selektif juga memegang peranan yang penting. Jika dalam proses pemilihan kromosom-kromosom cenderung pada kromosom yang memiliki fitness yang tinggi saja, konvergensi premature, yaitu mencapai solusi yang optimal lokal sangat mudah terjadi.

6

Untuk menghindari konvergensi premature tersebut dan tetap menjaga perbedaan (diversity) kromosom-kromosom dalam populasi, selain melakukan penekanan selektif yang lebih efisien, operator mutasi juga dapat digunakan. Proses mutasi dalam system biologi berlangsung dengan mengubah isi allele gen pada suatu locus dengan allele yang lain. Proses mutasi ini bersifat acak sehingga tidak selalu menjamin bahwa setelah proses mutasi akan diperoleh kromosom dengan fitness yang lebih baik.

7

Bab II Metode Penyelesaian

Gambar 2.1 Interface Program Genetika Algoritma. Interface di atas menunjukan bagaimana form tersebut disusun. Cara kerja daam penentuan nilai algoritma menggunakan program ini cukup mudah. Pertama, anda harus mengisikan target yang diinginkan pada textbox yang disediakan (Penulis menggunakan Nomor Kemahasiswaanya. Saat target sudah diisikan makan akan muncul Nama dan button inisialisasi akan menyala (Active). Berikut adalah coding untuk menampilkan nama dari target input. { for (int n = 0; n < num; n++) { if (target == number[n]) { npm = n; flag = true; break; } else { flag = false; //Application.ExitThread(); } } if (flag == true ) { MessageBox.Show("Your value target is your student's number = " + target + "\n Your name is : " + nama[npm], "Answers", MessageBoxButtons.OK, MessageBoxIcon.Information); label1.Text = "Nama : " + nama[npm] + " Npm : " + number[npm];

8

InpTar.Enabled = false; inptarget.Enabled = false; Init.Enabled = true; Auto.Enabled = true; } }

Gambar 2.2 Interface Setelah Target Input dimasukan. Bila Interface sudah tampak seperti pada gambar 2.2 maka langkah selanjutnya adalah menggunakan Button Inisialisasi yang akan menampilkan angka(n) setiap individu dengan coding sebagi berikut. private void init_chromosome() { Random rnd = new Random(); int i, k; listBox1.Items.Add("----Inisialisasi----"); for (i = 0; i <= pop - 1; i++) { for (k = 0; k <= gen - 1; k++) { chromosome[i, k] = Convert.ToInt32(rnd.Next(minrand, maxrand)); } listBox1.Items.Add("Individu [" + i + "] : " + (chromosome[i, 0]) + " , " + (chromosome[i, 1]) + " , " + (chromosome[i, 2]) + " , " + (chromosome[i, 3])); } }

9

Gambar 2.3 Interface setelah menggunakan Button inisialisasi. Setelah menggunakan Button inisialisasi dan individu sudah muncul selanjutnya adalah menggunakan Button evaluasi. Button Evaluasi akan muncul karena coding yang telah menghubungkan inisialisasi dengan evalusi sehingga saat buttoninitial click di jalankan akan memunculkan atau mengaktifkan button evaluasi untuk tahap selanjutnya seperti pada coding berikut. private void Init_Click(object sender, EventArgs e) { Init.Enabled = false; Eval.Enabled = true; Sel.Enabled = false; Cross.Enabled = false; Mut.Enabled = false; Clear.Enabled = false; listBox1.Items.Clear(); listBox2.Items.Clear(); init_chromosome(); }

Tahap selanjutnya sama seperti tahap sebelumnya yaitu, menggunakan Button yang muncul selanjutnya yaitu seleksi. Button seleksi akan muncul saat kita telah menjalankan Button sebelumnya yaitu Button evaluasi.

10

Gambar 2.4 Interface Setelah Button evaluasi di jalankan. Berikut adalah Coding yang digunakan untuk menghubungkan evaluasi dan seleksi : private void Eval_Click(object sender, EventArgs e) { Init.Enabled = false; Eval.Enabled = false; Sel.Enabled = true; Cross.Enabled = false; Mut.Enabled = false; Clear.Enabled = false; evaluasi_chromosome(); }

Selanjutnya adalah proses seleksi, tahap seleksi ini akan memunculkan Button Crossover yang dihubungkan dengan kode sebagai berikut. private void Sel_Click(object sender, EventArgs e) { Init.Enabled = false; Eval.Enabled = false; Sel.Enabled = false; Cross.Enabled = true; Mut.Enabled = false; Clear.Enabled = false; Seleksi(); }

Pada proses seleksi ini juga akan memunculkan data baru pada listbox 1 dan listbox 2 dimana pada listbox 2 adalah Individu baru. Berikut adalah tampilan Interface setelah menggunakan seleksi.

11

Gambar 2.5 Interface Setelah Button seleksi di jalankan.

Tahap selanjutnya adalah Button Crossover yang akan menyilangkan individu-individu baru pada listbox 2 untuk menghasilkan Chromosome yang akan menjadi individu pada tahap selanjutnya. Berikut adalah coding pada Button Crossover yang akan memunculkan Button Mutasi: private void Cross_Click(object sender, EventArgs e) { Init.Enabled = false; Eval.Enabled = false; Sel.Enabled = false; Cross.Enabled = false; Mut.Enabled = true; Clear.Enabled = false; crossover(); }

Mutasi merupakanproses selanjutnya. Pada proses mutasi, program akan memunculkan Chart. Chart tersebut berfungsi untuk menunjukan pada generasi keberapa target kita ditemukan. Setlah itu akan muncul Button Clear Listbox. Berikut adalah tampilan interface dan coding setelah mutasi dilakukan. private void Mut_Click(object sender, EventArgs e) { Init.Enabled = false; Eval.Enabled = false; Sel.Enabled = false; Cross.Enabled = false; Mut.Enabled = false; Clear.Enabled = true; mutasi();

12

Gambar 2.6 Interface Setelah Button Mutasi dijalankan. Button Clear listbox berfungsi untuk memunculkan individu baru atau memulai dengan generasi baru. Setelah Button Clear listbox dijalankan maka generasi baru akan muncul pada listbox 1 dan menggunakan Tahap yang sama untuk mendapatkan target. Perbedaan dengan tahap awal adalah button inisialisasi tidak diaktifkan melainkan langsung menuju ke Button Evaluasi. private void Clear_Click(object sender, EventArgs e) { Init.Enabled = false; Eval.Enabled = true; Sel.Enabled = false; Cross.Enabled = false; Mut.Enabled = false; Clear.Enabled = false; listBox1.Items.Clear(); listBox2.Items.Clear();

Gambar 2.7 Interface Setelah 15 Generasi.

13

Pada chart terdapat 2 garis yang berbeda warna. Garis dengan warna biru merupakan target yang ingin kita dapatka sedangkan garis berwana merah adalah output atau hasil yang kita dapatkan. Button auto pada program ini berfungsi untuk kita mendapatkan hasil yang kitainginkan tanpa menggunakan cara diatas. Dengan Button auto maka hasil akan dicari dengan sendirinya dan akan berhenti ketika mencapai target yang diinginkan.

Gambar 2.8 Menggunakan Button auto. Pencarian otomatis akan berhenti ketika kita mencapai target maka sebelum itu ingatlah untuk menggunakan batasan generasi dengan range cukup jauh, bila mengguanakan range yang hanya 10 atau 200 maka pencarian akan berhenti pada range yang ditentukan, tidak peduli apakah hasil sudah didapatkan atau belum. (int generation = 4000;)

Gambar 2.9 Interface saat pencarian mencapai target yang diinginkan. Pada gambar 2.9 ditunjukan bahwa pencarian berhenti pada generasi 1421 karena telah menemukan target yang diinginkan yaitu 1421021. 14

Gambar 2.10 Flowchart Genetika Algoritma

15

Bab III Analisa Data Berikut adalah analisa yang dilakukan pada program diatas namun menggunakan data yang berbeda dari data yang digunakan pada metode pengerjaan. 1. INISIALISASI private void init_chromosome() { Random rnd = new Random(); int i, k; listBox1.Items.Add("----Inisialisasi----"); for (i = 0; i <= pop - 1; i++) { for (k = 0; k <= gen - 1; k++) { chromosome[i, k] = Convert.ToInt32(rnd.Next(minrand, maxrand)); } listBox1.Items.Add("Individu [" + i + "] : " + (chromosome[i, 0]) + " , " + (chromosome[i, 1]) + " , " + (chromosome[i, 2]) + " , " + (chromosome[i, 3])); } }

Pada program ini, inisialisasi merupkan proses dimana program akan memberikan nilai awal terhadap gen-gen yang akan digunakan untuk mencapai targer serta sesuai dengan batasan nilai yang ditentukan

Gambar 3.1 Coding untuk menentukan batasan nilai Sesuai dengan batasan yang digunakan program tersebut maka batasan nilainya adalah 1000 dan minimal nilainya adalah 10. Misalkan populasi yang kita gunakan adalah 6 seperti yang ditumjukan pada gambar berikut.

16

Gambar 3.2 Inisialisasi populasi Dapat dilihat bahwa nilai a,b,c,d sesuai dengan batasan yaitu nilai terkecil dari inisialisasi diatas adalah 71 dan nilai 71 > 10(batasan minimal) dan nilai terbesar adalah 988 dan nilai 988 < 1000(batasan maksimal). 2. EVALUASI } private void evaluasi_chromosome() { double temp = 0; int i; listBox1.Items.Add("----Evaluasi----"); for (i = 0; i <= pop - 1; i++) { f_obj[i] = Math.Abs((Math.Pow(chromosome[i, 0], 2)) + (Math.Pow(chromosome[i, 1], 2)) + (Math.Pow(chromosome[i, 2], 2)) + chromosome[i, 3] - target); listBox1.Items.Add("Fungsi Obyektif [" + i + "] : " + f_obj[i]); temp = temp + f_obj[i]; } f_obj_avg = temp / pop; listBox1.Items.Add("Rata-rata Obyektif = " + f_obj_avg); }

Koding diatas merupakan koding untuk evaluasi. Dalam program ini, permasalahan yang ingin kita selesaikan berdasarkan variable yang digunakan adalah A, B, C, dan D 𝐴2 + 𝐵 2 + (𝐶 2 + 𝐷) = 𝑁𝑃𝑀………………………………………….(1) Mangka fungsi objektif yang digunakan adalah 𝑓𝑜𝑏𝑗(𝑖) = |𝐴2 + 𝐵 2 + (𝐶 2 + 𝐷) − 𝑁𝑃𝑀|………………………………(2) Persamaan diatas diambil dari coding yang di blok sebagai berikut.

17

Berdasarkan inisialisasi individu yang kita dapatkan tadi dapat di hitung fungsi objektifnya, 𝑓𝑜𝑏𝑗(0) = |(912 + 9882 + (7952 + 465)) − 1421021| = | (8281 +976144 +(632025 + 465)) – 1421021| = 195894 𝑓𝑜𝑏𝑗(1) = |3392 + 9282 + (6102 + 561) − 1421021| = |(114921 + 861184 +(372100 + 561)) – 1421021| = |-72255| = 72255 𝑓𝑜𝑏𝑗(2) = |9162 + 712 + (9532 + 774) − 1421021| = |1753080- 1421021| = 332059 𝑓𝑜𝑏𝑗(3) = |6122 + 9662 + (3502 + 840) − 1421021| = 10019 𝑓𝑜𝑏𝑗(4) = |3242 + 5592 + (4252 + 74) − 1421021| = 822865 𝑓𝑜𝑏𝑗(5) = |8522 + 2162 + (2932 + 90) − 1421021| = 562522 Maka rata-rata dari fungsi objektif diatas adalah 𝑓𝑜𝑏𝑗(𝑡𝑜𝑡𝑎𝑙) ÷ 6…………………………………………………………(3)

Dengan menggunakan persamaan diatas hasil rata-rata dapat kita dapatkan dengan hasil sebagai berikut. rata-rata = (195894 + 72255 + 332059 + 10019 + 822865 + 562522) / 6 = 332602,3333333

Gambar 3.3 Hasil dari Evaluasi. 18

3. SELEKSI Proses seleksi dilakukan dengan cara membuat chromosome yang mempunyai fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan fungsi fitness. 1

𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (𝑖) = fobj(i)+1……………………………………………….(4)

fungsi_objektif perlu ditambah 1 untuk menghindari kesalahan program yang diakibatkan pembagian oleh 0. Fungsi diatas juga didapatkan dari coding pada program sebagai berikut. { fitness[i] = 1 / (f_obj[i] + 1); temp = temp + fitness[i]; listBox1.Items.Add("Fitness [" + i + "] : " + fitness[i]); }

Berikut adalah pengujian untuk membuktikan fungsi yang diberikan memiliki hasil yang sesuai dengan program. 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (0) = 1/(𝑓𝑜𝑏𝑗(0) + 1) = 1/ (195894 + 1) = 5.10 x 10-6 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (1) = 1/(𝑓𝑜𝑏𝑗(1) + 1) = 1/ (72255 +1) = 1.38 x 10-5 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (2) = 1/(𝑓𝑜𝑏𝑗(2) + 1) = 1/ (332059 + 1) = 3.01 x 10-6 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (3) = 1/(𝑓𝑜𝑏𝑗(3) + 1) = 1/( 10019 +1) = 9.98 x 10-5 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (4) = 1/(𝑓𝑜𝑏𝑗(4) + 1) = 1.21 x 10-6 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 (5) = 1/(𝑓𝑜𝑏𝑗(5) + 1) = 1.77 x 10-6

19

} tot_fit = temp; listBox1.Items.Add("Total Fitness : " + tot_fit); max = fitness[0]; for (i = 1; i <= pop - 1; i++) { max = Math.Max(max, fitness[i]); if (max == fitness[i]) { winner = i; } } listBox1.Items.Add("Max : " + max); listBox1.Items.Add("Number Chromosome : " + winner); for (i = 0; i <= pop - 1; i++) { prob[i] = fitness[i] / tot_fit; listBox1.Items.Add("Probability [" + i + "]: " + prob[i]); } for (i = 0; i <= pop - 1; i++) { temp = 0; int k = 0; for (k = 0; k <= i; k++) { com_prob[i] = temp + prob[k]; temp = com_prob[i]; } listBox1.Items.Add("Roulete [" + i + "]: " + com_prob[i]); } for (i = 0; i <= pop - 1; i++) { roulwheel[i] = rnd.NextDouble(); listBox1.Items.Add("Roulete Wheel [" + i + "]: " + roulwheel[i]); } for (i = 0; i <= pop - 1; i++) { if (roulwheel[i] < com_prob[0]) { numb_chro[i] = 0; } else { int k; for (k = 0; k <= pop - 1; k++) { if ((roulwheel[i] > com_prob[k]) & (roulwheel[i] < com_prob[k + 1])) { numb_chro[i] = k + 1; } } } } for (i = 0; i <= pop - 1; i++) {

20

for (j = 0; j <= gen - 1; j++) { new_chrom[i, j] = chromosome[numb_chro[i], j]; } listBox2.Items.Add("New Individu [" + i + "]: " + (new_chrom[i, 0]) + " , " + (new_chrom[i, 1]) + " , " + (new_chrom[i, 2]) + " , " + (new_chrom[i, 3])); } }

Dari coding diatas dapat dimengerti bahwa setelah mencari hasil fitness selanjutnya adalah mencari nilai total fitness , probability, cumulative probability , lalu menggunakan roulette wheel untuk menyeleksi chromosome. Untuk mencari hasil dari total fitness ukup mudah , yaitu dengan menjumlahkan seluruh hasil fitness dengan persamaan sebagai berikut. ∆𝑓𝑖𝑡𝑛𝑒𝑠𝑠 = 𝑓(0) + 𝑓(1) + ⋯ + 𝑓(𝑛)…………………………………(5) Dengan menggunakan persamaan diatas dapat ditemukan bahawa nilai total_fitness pada program ini adalah 0.0001247. Kemudian, untuk mencari probability dapat digunakan persamaan sebagai berikut. 𝑃(𝑖) =

𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝑖) ∆𝑓𝑖𝑡𝑛𝑒𝑠𝑠

………………………………………………………..(6)

Program ini mapu mengerjakan persamaan tersebut dikarenakan coding yang ada pada program tersebut. { prob[i] = fitness[i] / tot_fit; listBox1.Items.Add("Probability [" + i + "]: " + prob[i]); }

Berikut adalah pengujian 2 sample menggunakan persamaan diatas secara manual untuk menguji ketepatan perhitungan program. P(0)

= fitness (0) / ∆fitness = 5.10 x 10-6 / 0.0001247 = 0.040

P(3)

= fitness (3) / ∆fitness = 9.98 x 10-5 / 0.0001247 = 0.800

21

Bila dilihat dari data yang ada pada program dapat dopastikan nilai yang dicari secara manual dan program adalah sama.

Gambar 3.4 Hasil dari Pencarian data Probability. Dari data diatas dapat dilihat bahwa chromosome ke 3 memiliki data fitness terbesar maka chromosome ini memiliki probabilitas untuk terpili pada generasi selanjutnya akan lebih besar bila dibandingkan dengan generasi yang lainya. Untuk menggunakan seleksi roulette wheel terlebih dahulu kita mencari cumulative probability dari chromosome diatas terlebih dahulu menggunakan persamaan sama seperti coding berikut. { com_prob[i] = temp + prob[k]; temp = com_prob[i]; }

C(0)

= 0.040

C(1)

= 0.040 + 0.110 = 0.15

C(2)

= 0.040 + 0.110 + 0.024 =0.0176

C(3)

= 0.040 + 0.110 + 0.024 + 0.800 = 0.976

C(4)

= 0.040 + 0.110 + 0.024 + 0.800 = 0.985

C(5)

= 0.040 + 0.110 + 0.024 + 0.800 + 0.015 = 1

Setelah dihitung cumulative probabilitasnya maka proses seleksi menggunakan roulete-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan bilangan acak R dalam range 0-1. Jika R[k] < C[1] maka pilih chromosome 1 sebagai induk, selain itu pilih chromosome ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Kita putar roulete wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acak R) dan pada tiap putaran, kita pilih satu chromosome untuk populasi baru.

22

Dengan menggunakan program ini , hasil yang kita peroloeh adalah sebagai berikut.

Gambar 3.5 Hasil dari seleksi dengan metode roulette wheel. 4. CROSSOVER Setelah proses seleksi maka proses selanjutnya adalah proses crossover. Metode yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu posisi dalam chromosome induk kemudian saling menukar gen. Chromosome yang dijadikan induk dipilih secara acak dan jumlah chromosome yang mengalami crossover dipengaruhi oleh parameter crossover_rate Berikut adalah coding yang digunakan dalam proses Crossover. private void crossover() { listBox2.Items.Add("----Crossover----"); Random rnd = new Random(); int k = 0; int j = 0; int i; double pc = 0.5; int count = 0; int[] off_num = new int[6]; int[] cross = new int[6]; for (i = 0; i <= pop - 1; i++) { RR[i] = rnd.NextDouble(); } for (i = 0; i <= pop - 1; i++) { if (RR[i] < pc) { for (k = 0; k <= gen - 1; k++) {

23

parent[i, k] = new_chrom[i, k]; } off_num[count] = i; count++; } listBox2.Items.Add("Parent [" + i + "]: " + (parent[i, 0]) + " , " + (parent[i, 1]) + " , " + (parent[i, 2]) + " , " + (parent[i, 3])); } for (i = 0; i <= count - 1; i++) { listBox2.Items.Add("off spring number [" + i + "] : " + off_num[i]); } for (i = 0; i <= count - 1; i++) { for (k = 0; k <= gen - 1; k++) { mutation[i, k] = parent[off_num[i], k]; } listBox2.Items.Add("mutation [" + i + "] : " + mutation[i, 0] + " ; " + mutation[i, 1] + " ; " + mutation[i, 2] + " ; " + mutation[i, 3]); } for (i = 0; i <= count - 1; i++) { cross[i] = Convert.ToInt32(rnd.Next(0, count)); } for (i = 0; i <= count - 1; i++) { for (k = 0; k <= gen - 1; k++) { if (k == 0) { child[i, k] = mutation[i, k]; } else { child[i, k] = mutation[cross[i], k]; child[i, k] = mutation[cross[i], k]; child[i, k] = mutation[cross[i], k]; } } listBox2.Items.Add("child [" + i + "] : " + child[i, 0] + " ; " + child[i, 1] + " ; " + child[i, 2] + " ; " + child[i, 3]); } for (i = 0; i <= pop - 1; i++) { if (i == off_num[j]) { for (k = 0; k <= gen - 1; k++) { chromosome[i, k] = child[j, k]; } j++; } else { for (k = 0; k <= gen - 1; k++)

24

{ chromosome[i, k] = new_chrom[j, k]; } } listBox2.Items.Add("Chromosome [" + i + "] : " + chromosome[i, 0] + " , " + chromosome[i, 1] + " , " + chromosome[i, 2] + " , " + chromosome[i, 3]); } }

Karena Crossover_rate (pc) pada program adalah 0.5. maka, dari data diatas yang akan kita jadikan induk adalah R(4) dan R(5).

Gambar 3.6 Hasil Induk untuk crossover. Posisi dalam penyilangan ini adalah dengan menyilangkan kedua induk chromosome tadi , yaitu : chromosome[4] >< chromosome[5] chromosome[5] >< chromosome[4] setelah penyilangan , hasil yang didapatkan adalah akan menjadi generasi yang baru.

Gambar 3.7 generasi yang baru dan akan di mutasikan.

25

5. MUTASI Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan oleh parameter mutation_rate. Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak. Prosesnya adalah sebagai berikut. Pertama kita hitung dahulu panjang total gen yang ada dalam satu populasi. Dalam kasus ini panjang total gen adalah total_gen

= (jumlah gen dalam chromosome) * jumlah populasi =4*6 = 24

Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara membangkitkan bilangan integer acak antara 1 sampai total_gen, yaitu 1 sampai 24. Jika bilangan acak yang kita bangkitkan lebih kecil daripada variabel mutation_rate (ρm) maka pilih posisi tersebut sebagai subchromosome yang mengalami mutasi. Misal ρm kita tentukan 10% maka diharapkan ada 10% dari total_gen yang mengalami populasi: jumlah mutasi

= 0.1 * 24 = 2.4 =2

Dalam program ini yang mengalami mutasi adalah chromosome ke 1, 4 dan 5.

26

Gambar 3.8 Hasil akhir dari mutasi. Dapat dilihat bahwa hasil dari fungsi_objektif tersebut tidak sesuai dengan target. Untuk mendapatkan target agar lebih mudah, kita dapat menggunakan Button auto. private void timer1_Tick_1(object sender, EventArgs e) { if ((epoch == generation) || (val == target)) { timer1.Enabled = false; } else { listBox1.Items.Clear(); listBox2.Items.Clear(); evaluasi_chromosome(); Seleksi(); crossover(); mutasi(); } chart1.Series[0].Points.AddXY(epoch, target); chart1.Series[1].Points.AddXY(epoch, val); epoch++; }

Dan bila target sudah didapatkan maka pencarian akan berheti secara otomatis erta akan menunjukan pada generasi keberapa target tersebut didapatkan.

27

Gambar 3.9 Hasi pencarian auto namun tidak sesuai target. Dalam pencarian diatas terjadi error dalam pencarian yaitu 7 x 10-5 % dari target yang diinginkan.

Gambar 3.10 Hasil pencarian auto dan mendapatkan target. Pencarian pada gambar 3.10 mencapaitarget yang diinginkan pada generasi ke 2532.

28

Bab IV Kesimpulan 1. Interface program Yang diberikan cukup membantu karena button yang ingin diaktifkan akan aktif setelah button sebelumnya di jalankan. 2. Pengujian yang dilakukan sebanyak 5 kali mendapatkan hasil 2/5 berhasil dengan tingkat keberhasilan 40% 3. Nilai gen dalam chromosome memiliki nilai min dan max rang yang memiliki pengaruh dalam timer untuk mencari hasil yang menjadi target. Dengan nilai yang kecil akan memakan waktu yang cukup lama dibandingkan dengan nilai yang besar. 4. Fungsi objective dilakukan untuk mendapatkan nilai target yang diinginkan yaitu dengan persamaan |A2 + B2 + (C2 + D) – NPM| = 0 5. Dalam program yang digunakan, chart yang muncul merupakan noise yang menyebabkan hasil sulit mencapai target. 6. Algoritma genetik merupakan proses pencarian yang heuristik dan acak sehingga penekanan pemilihan operator yang digunakan sangat menentukan keberhasilan algoritma genetik dalam menemukan solusi optimum suatu masalah yang diberikan.

29

Daftar Pustaka.  Suyanto (2014) Artificial Intelligent : Informatika Bandung  Firman (2007). Algoritma serta Aplikasinya. [online] “http://www.firmanits.com/2007/05/17/algoritma-genetika-dan-contoh-aplikasinya/”

30