Algoritma Genetika - Eka Risky Personal Site
Algoritma GenetikaMata Kuliah : Kecerdasan BuatanDosen Pembimbing : Victor Amrizal, MKomDisusun oleh :Eka Risky Firmansyah(1110091000043)Syukri Sayyid Ahmad(1110091000060)Nurul Hikmah Agustin(1110091000061)Teknik Informatika 5 BFakultas Sains dan TeknologiUniversitas Islam Negeri Syarif Hidayatullah Jakarta2012
KATA , wr. wb.Puji dan syukur senantiasa kita panjatkan kehadirat Allah SWT, shalawat serta salamsemoga senantiasa dilimpahkan kepada Nabi Muhammad SAW, juga untuk para keluarga,sahabat dan pengikutnya sampai akhir zaman. Karena atas rahmat-Nya, penyusun dapatmenyelesaikan penyusunan makalah ini yang berjudul “Algoritma Genetika”.Makalah ini disusun untuk memenuhi tugas mata kuliah “Kecerdasan Buatan”.Penyusun mengucapkan terimakasih kepada Bapak Victor Amrizal, MKom. selaku dosenpengampu, teman-teman dan semua pihak yang membantu dalam penyelesaian karya tulisini.Penyusun berharap makalah ini dapat menambah pengetahuan pembaca danmemberikan gambaran mengenai materi terkait yaitu Algoritma Genetika. Sehingga pembacadapat menggunakan makalah ini sebagai literatur pendukung dalam pengembangan bidangilmu selanjutnya yang terkait dengan penggunaan algoritma genetika.Penyusun menyadari bahwa makalah ini masih jauh dari kesempurnaan, makapenyusun mengharapkan saran dan kritik yang membangun untuk perbaikan makalah ini.Besar harapan penyusun agar penulisan makalah ini dapat berguna bagi siapapun yangmenjadikan makalah ini sebagai bahan literatur mengenai materi terkait.Wassalamualaikum, wr. wb.Penyusun1
DAFTAR ISIKATA PENGANTAR. 1DAFTAR ISI . 2BAB I PENDAHULUAN . 4I.1Latar Belakang . 4I.2Tujuan Penulisan. 4I.3Manfaat Penulisan . 4I.4Metodologi Penulisan. 4BAB II LANDASAN TEORI . 5II.1Sejarah Algoritma Genetika . 5II.2Aplikasi Algoritma Genetika . 5II.3Keuntungan Menggunakan Algoritma Genetika . 6BAB III PEMBAHASAN . 8III.1 Pengertian Algoritma Genetika . 8III.2 Struktur Umum Algoritma Genetika. 9III.3 Komponen Utama Algoritma Genetika . 9III.4 Hal-Hal Yang Harus Dilakukan Dalam Algoritma Genetika . 13III.4.1Pengertian individu . 13III.4.2Nilai Fitness . 15III.4.3Elitisme . 15III.5 Hal-Hal Yang Harus Diperhatikan Dalam Pemakaian Algoritma Genetika . 15III.6 Contoh Pemakaian Algoritma Genetika . 15III.6.1Pembentukan Kromosom . 17III.6.2Inisialisasi . 17III.6.3Evaluasi Kromosom . 17III.6.4Seleksi Kromosom . 182
III.6.5Crossover . 20III.6.6Mutasi. 22BAB IV KESIMPULAN & SARAN . 26IV.1 Kesimpulan . 26IV.2 Saran. 26DAFTAR PUSTAKA . 273
BAB IPENDAHULUANI.1Latar BelakangKehidupan merupakan suatu kesatuan dari kejadian-kejadian dinamis yang bisa jadimerupakan suatu masalah ataupun solusi atas kemungkinan-kemungkinan masalah yang akanterjadi. Dinamisnya kehidupan menuntut siapa saja yang berada di dalamnya untuk menjadilebih kebal terhadap keadaan buruk suatu kejadian. Pemilihan tindakan sudah sebagaimanamestinya haruslah memenuhi kriteria sebuah solusi sehingga pemecahan masalah benar-benardidapatkan pada akhirnya.Seperti proses evolusi yang mutlak terjadi sebagai bentuk representasi kehidupanyang mengharuskan siapapun menjadi lebih kebal secara genetika sehingga dapatmelewatkan proses seleksi alam yang terjadi. Dimana yang lebih kuatlah yang mampubertahan, sehingga yang kuat itulah yang merupakan suatu kualitas solusi optimal dari sebuahmasalah. Terinspirasi dari kehidupan dan seleksi alam yang terjadi di dalamnya, algoritmagenetika kemudian dikembangkan sebagai bentuk algoritma khusus yang digunakan dalammencari solusi optimal terhadap masalah yang diangkat dengan teknis yang disesuaikandengan proses evolusi. [1]I.2Tujuan PenulisanMakalah ini disusun bertujuan untuk :1. Mengetahui dan memahami mengenai algoritma genetika2. Memahami teknis kerja algoritma genetika sampai mendapatkan solusi optimal darimasalah yang diangkat.I.3Manfaat PenulisanPenyusunan makalah ini diharapkan dapat memberikan kontribusi dalam menambahwawasan, pengetahuan, dan pemahaman mengenai algoritma genetika.I.4Metodologi PenulisanPenyusunan makalah dilakukan dengan metode analisis literatur mengenai materialgoritma genetika yang didapatkan dari internet dan buku teks.4
BAB IILANDASAN TEORIII.1Sejarah Algoritma GenetikaAlgoritma genetika pertama kali ditemukan oleh Jhon Holland dari UniversitasMichigan pada awal 1970-an di New York, Amerika Serikat. Jhon Holland bersama muridmuridnya serta rekan kerjanya lalu menghasilkan buku yang berjudul “Adaption in Naturaland Artificial Systems” pada tahun 1975, yang cara kerjanya berdasarkan pada seleksi dangenetika alam. Konsep yang dipergunakan dalam algoritma genetika adalah mengikuti apayang dilakukan oleh alam. [2]Algoritma genetik khususnya diterapkan sebagai simulasi komputer dimana sebuahpopulasi representasi abstrak (kromosom) dari solusi-solusi calon (individual) pada sebuahmasalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secaratradisional solusi-solusi tersebut dilambangkan dalam biner sebagai string '0' dan '1',walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusidimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasigenerasi. Dalam tiap generasi kemampuan keseluruhan populasi dievaluasi, kemudianmultiple individuals dipilih dari populasi sekarang (current) secara stochastic (berdasarkankemampuan mereka) lalu dimodifikasi (dengan mutasi atau rekombinasi) menjadi bentukpopulasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya darialgoritma.II.2Aplikasi Algoritma GenetikaAlgoritma genetika sudah banyak digunakan pada masalah praktis yang berfokus padapencarian parameter-parameter atau solusi yang optimal. Hal ini membuat banyak orangmengira bahwa algoritma genetika hanya dapat digunakan untuk menyelesaikan masalahoptimasi saja. Namun, pada kenyataanya algoritma genetika juga memiliki kemampuan untukmenyelesaikan masalah-masalah selain optimasi. Algoritma genetika banyak diaplikasikanuntuk berbagai macam permasalahan, yaitu :1. OptimasiBeberapa penggunaan algoritma genetika untuk optimasi antara lain untuk optimasinumerik dan optimasi kombinatorial seperti Traveling Salesmen Problem (TSP),5
Perancangan Integrated Circuit atau IC, Job Scheduling, dan Optimasi video dansuara.2. Pemrograman OtomatisAlgoritma genetika untuk pemrograman otomatis antara lain untuk melakukan prosesevolusi terhadap program komputer dalam merancang struktur komputasional, seperticellular automata dan sorting networks.3. Machine LearningAlgoritma genetika juga telah berhasil diaplikasikan untuk memprediksi strukturprotein. Algoritma genetika juga berhasil diaplikasikan dalam perancangan neuralnetworks (jaringan syaraf tiruan) untuk melakukan proses evolusi terhadap aturanaturan pada learning classifier system atau symbolic production system dan dapatdigunakan untuk mengontrol robot.4. Model EkonomiDalam bidang ekonomi, algoritma genetika digunakan untuk memodelkan prosesproses inovasi dan pembangunan bidding strategies.5. Model Sistem ImunisasiContoh penggunaan algoritma genetika dalam bidang ini untuk memodelkan berbagaiaspek pada sistem imunisasi alamiah, termasuk somatic mutation selama kehidupanindividu dan menemukan keluarga dengan gen ganda (multi gen families) sepanjangwaktu evolusi.6. Model EkologisAlgoritma genetika juga dapat digunakan untuk memodelkan fenomena ekologisseperti host-parasite co evolutions, simbiosis dan aliran sumber di dalam ekologi.II.3Keuntungan Menggunakan Algoritma GenetikaKeuntungan penggunaan algoritma genetika terlihat dari kemudahan implementasidan kemampuannya untuk menemukan solusi yang optimal dan bisa diterima secara cepatuntuk masalah-masalah berdimensi tinggi. Algoritma Genetika sangat berguna dan efisienuntuk masalah dengan karakteristik sebagai berikut : Ruang masalah sangat besar, kompleks, dan sulit dipahami, Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikanmasalah ke dalam ruang pencarian yang lebih sempit, Tidak tersedianya analisis matematika yang memadai,6
Ketika metode-metode konvensional sudah tidak mampu menyelesaikan masalahyang dihadapi, Solusi yang diharapkan tidak harus paling optimal, tetapi cukup “bagus” atau bisaditerima, Terdapat batasan waktu, misalnya dalam real time system atau sistem waktu nyata.7
BAB IIIPEMBAHASANIII.1Pengertian Algoritma GenetikaAlgoritma genetika adalah algoritma komputasi yang diinspirasi teori evolusi yangkemudian diadopsi menjadi algoritma komputasi yang biasa digunakan untuk memecahkansuatu pencarian nilai dalam sebuah masalah optimasi. Algoritma ini didasarkan pada prosesgenetik yang ada dalam makhluk hidup; yaitu perkembangan generasi dalam sebuah populasiyang alami, secara lambat laun mengikuti prinsip seleksi alam atau “siapa yang kuat, dia yangbertahan (survive)”. Dengan meniru teori evolusi ini, algoritma genetika dapat digunakanuntuk mencari solusi permasalahan-pemasalahan dalam dunia nyata.Ada 4 kondisi yang sangat mempengaruhi proses evolusi, yaitu :1. Kemampuan organisme untuk melakukan reproduksi,2. Keberadaan populasi organisme yang bias melakukan reproduksi,3. Keberagaman organisme dalam suatu populasi dan4. Perbedaan kemampuan untuk survive. [3]Gambar 1 - Flowchart Algoritma Genetika [4]8
III.2Struktur Umum Algoritma GenetikaAlgoritma genetika memiliki struktur umum, antara lain : Populasi, istilah pada teknik pencarian yang dilakukan sekaligus atas sejumlahkemungkinan solusi. Kromosom, individu yang terdapat dalam satu populasi dan merupakan suatu solusiyang masih berbentuk simbol. Generasi, populasi awal dibangun secara acak sedangkan populasi selanjutnyamerupakan hasil evolusi kromosom-kromosom melalui iterasi. Fungsi Fitness, alat ukur yang digunakan untuk proses evaluasi kromosom. Nilaifitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasitersebut. Generasi berikutnya dikenal dengan anak (offspring) yang terbentuk dari gabungandua kromosom generasi sekarang yang bertindak sebagai induk (parent) denganmenggunakan operator penyilang (crossover). III.3Mutasi, operator untuk memodifikasi kromosom.Komponen Utama Algoritma GenetikaDalam algoritma genetika terdapat enam komponen utama, yaitu :1. Teknik PenyandianTeknik penyandian meliputi penyandian gen dari kromosom. Gen merupakan able.Gendapatdirepresentasikan dalam bentuk : string bit, pohon, array bilangan real, daftar aturan,elemen permutasi, elemen program dan lain-lain.2. Prosedur InisialisasiUkuran populasi tergantung pada permasalahan yang akan dipecahkan dan jenisoperator genetika yang akan diimplementasikan. Setelah ukuran populasi telahditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapatpada populasi tersebut. Inisialisasi kromosom dapat dilakukan secara acak, namundemikian harus tetap memperhatikan domain solusi dan kendala permasalahan yangada.9
3. Fungsi EvaluasiAda dua hal yang harus dilakukan dalam melakukan evaluasi kromosom yaitu :evaluasi fungsi objektif dan konversi fungsi objektif kedalam fungsi fitness4. SeleksiMemiliki tujuan untuk memberikan kesempatan reproduksi yang lebih besar bagianggota populasi yang paling fit. Seleksi akan menentukan individu-individu manasaja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana offspringterbentuk dari individu-individu terpilih tersebut. Langkah pertama yaitu pencariannilai fitness. Langkah kedua adalah nilai fitness yang diperolah digunakan pada tahaptahap seleksi selanjutnya.Ada beberapa definisi yang bisa digunakan untuk melakukan perbandingan terhadapbeberapa metode yang akan digunakan, antara lain : Selective Pressure : probabilitas dari individu terbaik yang akan diseleksidibandingkan dengan rata-rata probabilitas dari semua individu yang diseleksi. Bias : perbedaan absolut antara fitness ternormalisasi dari suatu individu danprobabilitas reproduksi yang diharapkan. Spread : range nilai kemungkinan untuk sejumlah offspring dari suatuindividu. Loss of diversity: proposi dari individu-individu dalam suatu populasi yangtidak terseleksi selama fase seleksi. Selection intensity : nilai fitness rata-rata yang diharapkan dalam stribusiGaussternormalisasi). Selection variance : variansi yang diharapkan dari distribusi fitness stribusiGaussternormalisasi).Ada beberapa metode seleksi dari induk, yaitu : Rank-based fitness assignmentPopulasi diurutkan menurut nilai objektifnya. Nilai fitness dari tiap-tiapindividu hanya tergantung pada posisi individu tersebut dalam urutan, dantidak dipengaruhi oleh nilai objektifnya.10
Roulette wheel selectionIstilah lainnya adalah stochastic sampling with replacement. Individu-individudipetakan dalam suatu segmen garis secara berurutan sedemikian hingga tiaptiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnya.Sebuah bilangan random dibangkitkan dan individu yang memiliki segmendalam kawasan segmen dalam kawasan bilangan random tersebut akanterseleksi. Proses ini berulang hingga didapatkan sejumlah individu yangdiharapkan. Stochastic universal samplingMemiliki nilai bias nol dan penyebaran yang minimum. Individu-individudipetakan dalam suatu segmen garis secara berurut sedemikian hingga tiaptiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnyaseperti halnya pada seleksi roda roulette. Kemudian diberikan sejumlahpointer sebanyak individu yang ingin diseleksi pada garis tersebut. AndaikanN adalah jumlah individu yang akan diseleksi, maka jarak antar pointer adalah1/N, dan posisi pointer pertama diberikan secara acak pada range [1, 1/N]. Local selectionSetiap individu yang berada di dalam konstrain tertentu disebut dengan namalingkungan lokal. Interaksi antar individu hanya dilakukan di dalam wilayahtersebut. Lingkungan tersebut ditetapkan sebagai struktur dimana populasitersebut terdistribusi. Lingkungan tersebut juda dapat dipandang sebagaikelompok pasangan-pasangan yang potensial. Langkah pertama yangdilakukan adalah menyeleksi separuh pertama dari populasi yang berpasangansecara random. Kemudian lingkungan baru tersebut diberikan pada setiapindividu yang terseleksi.Struktur lingkungan pada seleksi lokal dapat berbentuk : linear (full ring danhalf ring), dimensi-2 (full cross dan half cross, full star dan half star), dandimensi-3 dan struktur yang lebih kompleks yang merupakan kombinasi darikedua struktur diatas. Jarak antara individu dengan struktur tersebut akansangat menentukan ukuran lingkungan. Individu yang terdapat dalamlingkungan dengan ukuran yang lebih kecil, akan lebih terisolasi dibandingkandengan individu yang terletak pada lingkungan dengan ukuran yang lebihbesar.11
Truncation selectionMerupakan seleksi buatan yang digunakan oleh populasi yang jumlahnyasangat besar. Individu-individu diurutkan berdasarkan nilai fitnessnya. Hanyaindividu yang terbaik saja yang akan diseleksi sebagai induk. Parameter yangdigunakan adalah suatu nilai ambang trunc yang mengindikasikan ukuranpopulasi yang akan diseleksi sebagai induk yang berkisar antara 50% -10%.Individu-individu yang ada dibawah nilai ambang tidak akan menghasilkanketurunan. Tournament selectionDitetapkan suatu nilai tour untuk individu-individu yang dipilih secararandom dari suatu populasi. Individu-individu yang terbaik dalam kelompokini akan diseleksi sebagai induk. Parameter yang digunakan adalah ukurantour yang bernilai antara 2 sampai N (jumlah individu dalam populasi).5. Operator GenetikaAda dua operator genetika dalam algoritma genetika, yaitu :a. Operator untuk melakukan rekombinasi, yang terdiri dari :i.Rekombinasi bernilai real, yaitu :1. Rekombinasi diskrit : menukar nilai variabel antar kromosominduk.2. Rekombinasi intermediate : metode rekombinasi yang hanyadapat digunakan untuk variabel real. Nilai variabel anak dipilihdi sekitar dan antara nilai-nilai variable induk.3. Rekombinasi garis : hamper sama dengan rekombinasimenengah, hanya saja nilai alpha untuk semua variable sama.4. Rekombinasi garis yang diperluasii.Rekombinasi bernilai biner (Crossover), yaitu :1. Crossover satu titik2. Crossover banyak titik3. Crossover seragam4. Crossover dengan permutasib. Mutasi, yang terdiri dari :i.Mutasi bernilai realii.Mutasi bernilai biner12
6. Penetuan ParameterParameter adalah parameter control algoritma genetika, yaitu ukuran populasi(popsize), peluang crossover (pc) dan peluang mutasi (pm). Rekomendasi untukmenentukan nilai parameter :i.Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jongmerekomendasikan nilai parameter : (popsize; pc; pm) (50;0,6;0,001)ii.Bila rata-rata fitness setiap generasi digunakan sebagai indikator, makaGrefenstette merekomendasikan : (popsize; pc; pm) (30;0,95;0,01)iii.Bila fitness dari individu terbaik dipantau pada setiap generasi, makausulannya adalah : (popsize; pc; pm) (80;0,45;0,01)iv.Ukuran populasi sebaiknya tidak lebih kecil dari 30, untuk sembarang jenispermasalahan. [5]III.4Hal-Hal Yang Harus Dilakukan Dalam Algoritma GenetikaBeberapa hal yang harus dilakukan dalam algoritma genetika adalah : Mendefinisikanindividu,dimanaindividumenyatakan salah satu solusi(penyelesaian) yang mungkin dari permasalahan yang diangkat. Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individuatau baik-tidaknya solusi yang didapatkan. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukandengan menggunakan pembangkitan acak seperti random-walk. Menentukan proses seleksi yang akan digunakan. Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akandigunakan. [6]III.4.1 Pengertian individuIndividu menyatakan salah satu solusi yang mungkin. Individu bisa dikatakansama dengan kromosom, yang merupakan kumpulan gen. Gen ini bisa bersifat biner,float, dan kombinatorial. Beberapa definisi penting yang perlu diperhatikan dalammendefinisikan individu untuk membangun penyelesaian permasalahan denganalgoritma genetika adalah sebagai berikut : Genotype (gen), sebuah nilai yang menyatakan satuan dasar yang membentuksuatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam13
algoritma genetika, gen ini bisa brupa nilai biner, float, integer maupunkarakter, atau kombinatorial. Allele, nilai dari gen. Kromosom, gabungan gen-gen yang membentuk nilai tertentu. Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satusolusi yang mungkin dari permasalahan yang diangkat. Generasi, menyatakan satu siklus proses evolusi atau satu iterasi di dalamalgoritma genetika. [7]Gambar 2 - Ilustrasi representasi penyelesaian permasalahan dalam algoritma genetika14
III.4.2 Nilai FitnessNilai fitness adalah nilai yang menyatakan baik tidaknya suatu solusi(individu). Nilai fitness ini yang dijadikan acuan dalam mencapai nilai optimal dalamalgoritma genetika. Algoritma genetika bertujuan mencari individu dengan nilaifitness yang paling tinggi.III.4.3 ElitismeProses seleksi yang dilakukan secara random sehingga tidak ada jaminanbahwa suatu indvidu yang bernilai fitness tertinggi akan selalu terpilih. Walaupunindividu bernilai fitness tertinggi terpilih, mungkin saja individu tersebut akan rusak(nilai fitnessnya menurun) karena proses pindah silang (crossover). Oleh karena itu,untuk menjaga agar individu bernilaifitness tertinggi tersebut tidak hilang selamaevolusi, maka perlu dibuat satu atau beberapa copy-nya. Prosedure ini dikenal sebagaielitisme. [8]III.5Hal-Hal Yang Harus Diperhatikan Dalam Pemakaian Algoritma GenetikaBeberapa hal yang perlu diperhatikan dalam pemakaian algoritma genetika adalah : Algoritma genetika adalah algoritma yang dikembangkan dari proses pencarian solusimenggunakan pencarian acak, ini terlihat pada proses pembangkitan populasi awalyang menyatakan sekumpulan solusi yang dipilih secara acak. Berikutnya pencarian dilakukan berdasarkan proses-proses teori genetika yangmemperhatikan pemikiran bagaimana memperoleh individu yang lebih baik, sehinggadalam proses evolusi dapat diharapkan diproleh individu yang terbaik.III.6Contoh Pemakaian Algoritma GenetikaKita akan membahas sebuah contoh aplikasi algoritma genetika yang digunakan untukmenyelesaikan masalah kombinasi. Misalkan ada persamaan :“a 2b 3c 4d 30”Kita mencari nilai a, b, c, dan d yang memenuhi persamaan diatas. Kita mencobamenggunakan algoritma genetika untuk menyelesaikan permasalahan diatas. Flowchart darialgoritma genetika untuk menyelesaikan permasalahan diatas dapat dilihat dibawah ini.[9]15
Gambar 3 - Flowchart contoh penggunaan algoritma genetika16
Penjelasan mengenai langkah-langkah penyelesaian permasalahan dari flowchartdiatas menggunakan algoritma genetika adalah sebagai berikut :III.6.1 Pembentukan KromosomKarena yang dicari adalah nilai a, b, c, d maka variabel a, b, c, d dijadikansebagai gen-gen pembentuk kromosom. Batasan nilai variabel a adalah bilanganinteger 0 sampai 30. Sedangkan batasan nilai variabel b, c, dan d adalah bilanganinteger 0 sampai 10.III.6.2 InisialisasiProses inisialisasi dilakukan dengan cara memberikan nilai awal gen-gendengan nilai acak sesuai batasan yang telah ditentukan. Misalkan kita tentukan jumlahpopulasi adalah 6, maka : Kromosom[1] [a;b;c;d] [12;05;03;08] Kromosom[2] [a;b;c;d] [02;01;08;03] Kromosom[3] [a;b;c;d] [10;04;03;04] Kromosom[4] [a;b;c;d] [20;01;10;06] Kromosom[5] [a;b;c;d] [01;04;03;09] Kromosom[6] [a;b;c;d] [20;05;07;01]III.6.3 Evaluasi KromosomPermasalahan yang ingin diselesaikan adalah nilai variabel a, b, c, dan d yangmemenuhi persamaan a 2b 3c 4d 30, maka fungsi objektif yang dapatdigunakan untuk mendapatkan solusi adalah“fungsi objektif(kromosom) (a 2b 3c 4d) – 30 ”Kita hitung fungsi objektif dari kromosom yang telah dibangkitkan :i.fungsi objektif(Kromosom[1]) Abs(( 12 2*5 3*3 4*8 ) - 30) Abs((12 10 9 32 ) - 30) Abs(63 - 30) 33ii.fungsi objektif(Kromosom[2]) Abs(( 2 2*1 3*8 4*3 ) - 30) Abs(( 2 2 24 12 ) - 30) Abs(40 - 30) 1017
iii.fungsi objektif(Kromosom[3]) Abs(( 10 2*4 3*3 4*4 ) - 30) Abs(( 10 8 9 16 ) - 30) Abs(43 - 30) 13iv.fungsi objektif(Kromosom[4]) Abs(( 20 2*1 3*10 4*6 ) - 30) Abs(( 20 2 30 24 ) - 30) Abs(76 - 30) 46v.fungsi objektif(Kromosom[5]) Abs(( 1 2*4 3*3 4*9 ) - 30) Abs(( 1 8 9 36 ) - 30) Abs(54 - 30) 24vi.fungsi objektif(Kromosom[6]) Abs(( 20 2*5 3*7 4*1 ) - 30) Abs(( 20 10 21 4) - 30) Abs(55 - 30) 25Rata-rata dari fungsi objektif tersebut adalah (33 10 13 46 24 25)/6 151 / 6 25.167III.6.4 Seleksi KromosomProses seleksi dilakukan dengan cara membuat kromosom yang mempunyaifungsi objektif kecil mempunyai kemungkinan terpilih yang besar atau mempunyainilai probabilitas yang tinggi. Untuk itu dapat digunakan“fungsi fitness (1 / (1 fungsi objektif))”Fungsi objektif perlu ditambah 1 untuk menghindari kesalahan program yangdiakibatkan pembagian oleh 0.i.fitness[1] 1 / (fungsi objektif[1] 1) 1 / 34 0.0294ii.fitness[2] 1 / (fungsi objektif[2] 1) 1 / 11 0.0909iii.fitness[3] 1 / (fungsi objektif[3] 1) 1 / 14 0.0714iv.fitness[4] 1 / (fungsi objektif[4] 1) 1 / 47 0.0212v.fitness[5] 1 / (fungsi objektif[5] 1) 1 / 25 0.0400vi.fitness[6] 1 / (fungsi objektif[6] 1) 1 / 26 0.038518
total fitness 0.0294 0.0909 0.0714 0.0212 0.04 0.0385 0.2914Rumus untuk mencari probabilitas : “P[i] fitness[i] / total fitness”i.P[1] 0.0294 / 0.2914 0.1009ii.P[2] 0. 0909 / 0.2914 0.3119iii.P[3] 0. 0714 / 0.2914 0.2450iv.P[4] 0. 0212 / 0.2914 0.0728v.P[5] 0.04 / 0.2914 0.1373vi.P[6] 0.0385 / 0.2914 0.1321Dari probabilitas diatas dapat kita lihat kalau kromosom ke-2 yangmempunyai fitness paling besar maka kromosom tersebut mempunyai probabilitasuntuk terpilih pada generasi selanjutnya lebih besar dari kromosom lainnya. Untukproses seleksi kita gunakan roulette wheel, untuk itu kita harus mencari dahulu nilaikumulatif probabilitasnya :i.C[1] 0.1009ii.C[2] 0.1009 0.3119 0.4128iii.C[3] 0.1009 0.3119 0.2450 0.6578iv.C[4] 0.1009 0.3119 0.2450 0.0728 0.7306v.C[5] 0.1009 0.3119 0.2450 0.0728 0.1373 0.8679vi.C[6] 0.1009 0.3119 0.2450 0.0728 0.1373 0.1321 1Setelah dihitung kumulatif probabilitasnya maka proses seleksi menggunakanroulette-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan bilanganacak R dalam range 0-1. Jika R[k] C[1] maka pilih kromosom 1 sebagai induk,selain itu pilih kromosom ke-k sebagai induk dengan syarat C[k-1] R C[k]. Kitaputar roulete wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acakR) dan pada tiap putaran, kita pilih satu kromosom untuk populasi baru. Misal :i.R[1] 0.201ii.R[2] 0.284iii.R[3] 0.009iv.R[4] 0.82219
v.R[5] 0.398vi.R[6] 0.501Angka acak pertama R[1] adalah lebih besar dari C[1] dan lebih kecil daripadaC[2] maka pilih Kromosom[2] sebagai kromosom pada populasi baru, dari bilanganacak yang telah dibangkitkan diatas maka populasi kromosom baru hasil prosesseleksi adalah :i.Kromosom[1] Kromosom[2]ii.Kromosom[2] Kromosom[2]iii.Kromosom[3] Kromosom[1]iv.Kromosom[4] Kromosom[5]v.Kromosom[5] Kromosom[2]vi.Kromosom[6] Kromosom[3]Kromosom baru hasil proses seleksi :i.Kromosom[1] [02;01;08;03]ii.Kromosom[2] [02;01;08;03]iii.Kromosom[3] [12;05;03;08]iv.Kromosom[4] [01;04;03;09]v.Kromosom[5] [02;01;08;03]vi.Kromosom[6] [10;04;03;04]III.6.5 CrossoverSetelah proses seleksi maka proses selanjutnya adalah proses crossover.Metode yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acaksatu posisi dalam kromosom induk kemudian saling menukar gen. Kromosom yangdijadikan induk dipilih secara acak dan jumlah kromosom yang mengalami crossoverdipengaruhi oleh parameter crossover rate (ρc). Pseudo-code untuk proses crossoveradalah sebagai berikut :begink 0;while (k populasi) doR[k] random(0-1);20
if (R[k] ρc ) thenselect Chromosome[k] as parent;end;k k 1;end;end;Misal kita tentukan crossover probability adalah sebesar 25%, makadiharapkan dalam satu generasi ada 50% kromosom (3 kromosom) dari satu generasimengalami proses crossover. Prosesnya adalah sebagai berikut :i.Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi R[1] 0.191 R[2] 0.259 R[3] 0.760 R[4] 0.006 R[5] 0.159 R[6] 0.340Maka kromosom ke-k akan dipilih sebagai induk jika R[k] ρc, dari bilanganacak R diatas maka yang dijadikan induk adalah Kromosom[1], Kromosom[4]dan Kromosom[5].ii.Setelah melakukan pemilihan induk proses selanjutnya adalah menentukanposisi crossover. Ini dilakukan dengan cara membangkitkan bilangan acakdengan batasan 1 sampai (panjang kromosom - 1), dalam kasus ini bilanganacak yang dibangkitkan adalah 1 – 3. Misalkan didapatkan posisi crossoveradalah 1 maka kromosom induk akan dipotong mulai gen ke-1 kemudianpotongan gen tersebut saling ditukarkan antar induk.iii. Kromosom[1] Kromosom[4] Kromosom[4] Kromosom[5] Kromosom[5] Kromosom[1]Posisi cut-point crossover dipilih menggunakan bilangan acak 1-3 sebanyakjumlah crossover yang terjadi, misal : C[1] 1 C[2] 121
C[3] 2 offspring[1] Kromosom[1] Kromosom[4] [02;01;08;03] [01
and Artificial Systems” pada tahun 1975, yang cara kerjanya berdasarkan pada seleksi dan genetika alam. Konsep yang dipergunakan dalam algoritma genetika adalah mengikuti apa yang dilakukan oleh alam. [2] Algoritma genetik khu
1. Mengungkap miskonsepsi materi genetika pada buku ajar biologi di SMA. 2. Mengungkap faktor penyebab miskonsepsi materi genetika pada buku ajar biologi di SMA 3. Memperbaiki kesalahan konsep genetika yang ditemukan pada buku biologi SMA. D. Urgensi Penelitian Konsep genetika saat ini berbeda dengan konsep genetika yang dipahami sebelumnya.
Pada gambar 1.1 dapat dijelaskan langkah-langkah awal dalam penyelesaian algoritma Genetika dimulai dari inisialisasi populasi awal (secara acak atau berdasarkan kriteria tertentu). Evaluasi nilai fitness dari setiap kromosom. Seleksi, digunakan untuk mendapatkan kumpulan kromosom baru calon anggota populasi berikutnya.
penyakit stroke serta belum dilakukannya komparasi algoritma C4.5 berbasis PSO dan C4.5 berbasis GA Atas dasar alasan tersebut diatas, maka dilakukan penelitian menggunakan metode klasifikasi algoritma C4.5 berbasis PSO (Particle Swarm Optimization) dan juga C4.5 berbasis Genetic Algorithm dalam memprediksi penyakit stroke.
Risky deal, risky business Khudoni hydropower plant, Georgia June 2009. Author: Manana Kochladze. Acknowledgements: Ketevan Gujaraidze, Green Alternative, Georgia. . the project, the data presented does not include evidence that all relevant external costs are integrated in-to the project budget. In addition, the regional overview study of .
Risky decision making in a computer card game: An information integration experiment information integration in risky decision making was studied by using a functional measurement approach.Participants (N 84) played a computerized risky card game inco1porating a within-subject design with the J factors ( a) probability of negative or positive .
GEA Canada Inc, Barr-Rosin division Gene Bridges, Gmbh Genedata Genencor A Danisco Division Genera Energy Inc General Motors Genetika Institute Genetika, Research Instititute of Industrial Microorganisms Genomatica, Inc Genome Prairie Genome Quebec Genopole GenScript Corporation
Teen Court: Risky Business Packet 1 LEON COUNTY TEEN COURT 301 S. MONROE ST. SUITE 225 TALLAHASSEE, FLORIDA 32301 Phone: (850) 577-4468 Fax: (850) 487-7947 Risky Business Packet PLEASE READ THE ARTICLES AND PROVIDE A SUMMARY OF EACH TOPIC AS THEY RELATE TO YOUR PERSONAL EXPERIENCE. 1. High School Dropout 2. Making Ethical Decisions 3.
Thus it might seem that Scrum, the Agile process often used for software development, would not be appropriate for hardware development. However, most of the obvious differences between hardware and software development have to do with the nature and sequencing of deliverables, rather than unique attributes of the work that constrain the process. The research conducted for this paper indicates .
