programer skripsi tesis tugas akhir
-

Contoh Program Source Code   /

Algoritma Genetika

Posted on 00.04
Join with us

Algoritma Genetika


Algoritma genetika adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetika adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritma Genetika pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma Genetika khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. 

Evolusi

Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.
Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: 

(1) representasi genetik dari penyelesaian
(2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (obyek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit mewakili obyek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah obyek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran obyek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua obyek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi.

Algoritma genetik merupakan suatu metode yang menggunakan seleksi alam yang merupakan bagian utama dari prinsip evolusi sebagai dasar pemikiran untuk menyelesaikan suatu permasalahan. Prinsip ini dikemukakan oleh Charles Darwin, dimana tanpa menghiraukan prinsip dasar penurunan sifat, Darwin mengemukakan penggabungan kualitas induk pada generasi berikutnya, disamping itu bahwa individu yang mampu beradaptasi dengan lingkunganya akan mempunyai kesempatan hidup yang lebih besar.

Penggunaan prinsip genetika pada komputer dimulai pada tahun 1950 ketika beberapa ahli Biologi mengunakan komputer untuk simulasi sistem biologi. Akhir tahun 1975 John Holland dari Universitas Michigan melalui paper yang berjudul “Adaption in Natural and Artificial System” mengunakan konsep dasar algoritma genetika. Algoritma genetika bekerja dengan suatu populasi string dan melakukan proses pencarian nilai optimal secara parallel, dengan mengunakan operator genetika. Algoritma genetika akan melakukan rekombinasi antar individu.

Algoritma genetika memiliki elemen dasar berupa string yang tersusun dari rangkaian substring (gen), yang masing-masing merupakan kode dari parameter dalam ruang solusi dimana suatu string (kromosom) menyatakan kandidat solusi. Kumpulan string dalam populasi berkembang dari generasi ke generasi melalui operator genetika. Pada setiap iterasi, individu-individu (Kromosam) dalam populasi itu akan dievolusi dan diseleksi untuk menentukan populasi pada generasi berikutnya. Populasi ini akan terus berulang sampai menemukan suatu parameter dengan nilai yang paling optimal sesuai dengan yang diinginkan. Adapun struktur umum algoritma genetika dapat diilustrasikan pada gambar berikut:

Gambar 1. Struktur umum Algoritma Genetika

Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah allele yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukancrossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahanknapsack atau pengepakan, dimana ada beberapa barang dengan jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung olehk napsack tanpa harus menambah kapasitasnya.

Istilah-istilah yang digunakan dalam Algoritma genetika ini hampir sama dengan istilah-istilah yang dipakai dalam bidang biologi genetika, antara lain Gen, Kromosom, Populasi, Fungsi Fitness, dan operator genetika yang meliputi mutasi dan crossover.

Gen adalah suatu sel dari suatu kromosom atau nilai yang terdapat dalam Algoritma genetika ini dapat dibentuk oleh sebuah byte bahkan tidak menutup kemungkinan suatu string. Gen ini mewakili sebagian kecil dari solusi permasalahan.

Individu dalam populasi disebut string, genotype atau kromosom-kromosom terdiri dari unit-unit yang dinamakan Gen, Karakter, Decoder. Kromosom ini dapat mewakili suatu solusi, dimana dapat diilustrasikan dalam gambar dibawah ini:


Gambar 2. Kromosom dalam 
Untuk mempresentasikan kromosom dilakukan dengan proses encoding, dibawah ini akan dijelaskan beberapa proses encoding yang biasa digunakan dalam beberapa kasus tertentu.

Permutation Encoding

Untuk jenis Permutation Encoding ini digunakan untuk permasalahan proses pengurutan, misalnya terdapat kasus optimasi jadwal atau pada kasus traveling salesman. Pada Permutation Encoding, setiap Gen pada kromosom berupa angka dimana dapat ditampilkan seperti gambar di bawah ini:
Gambar 3. Permutation Encoding
Permutation Encoding hanya berlaku untuk permasalahan pengurutan, untuk itu dalam kasus-kasus yang ada pada Permutation Encoding terdapat beberapa jenis crossover dan mutasi yang harus dibuat untuk mempertahankan kromosom agar tetap konsisten. Contoh penggunaan Permutation Encoding ini adalah pada kasus trvelling salesman, dimana terdapat beberapa kota dengan jarak masing-masing. Pada kasus traveling salesman ini seorang salesman harus mengunjungi semua kota yang ada, tetapi tidak harus berjalan jauh untuk mencapai seluruh kota. Permasalahanya adalah menentukan urutan kota yang akan dikunjungi untuk meminimalisasi jarak yang harus ditempuh.

Binary encoding

Binary encoding adalah jenis encoding yang paling sering digunakan karena kasus pertama yang ada pada Algiritma Genetik menggunakan algoritma jenis ini. Setiap kromosom padaBinary encoding merupakan bit 0 dan 1 dimana dapat ditampilkan pada gambar bawah:
Gambar 4. Binary encoding
Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah Gen yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukancrossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahanknapsack atau pengepakan, dimana ada beberapa barang dengna jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung oleh knapsack tanpa harus menambah kapasitasnya.

Crossover

Crossover adalah operator algoritma genetika yang membutuhkan parameter dua kromosom. Dua buah kromosom tersebut disebut kromosom induk. Operator ini akan menghasilkan dua buah kromosom baru. Ada beberapa jenis crossover yang sering digunakan dalam algoritma genetika antara lain:

Ordered Based Crossover

Ordered based Crossover diawali dengan menentukan posisi-posisi gen secara random pada induk pertama misalnya didapatkan posisi 3,4,6 dan 9 pada induk.

P1= ( 1 2 3 4 5 6 7 8 9 )

P1= ( 4 5 2 1 8 7 6 9 3 )

Kemudian Gen-gen pada induk yang berada tepat dibawah posisi-posisi tersebut dicatat yaitu 2,1,7 dan 3 untuk Q1 disalin dari P1 dengan menghilangkan angka-angka 2,1,7 dan3 tersebut sehingga menjadi

Q1= ( x x x 4 5 6 x 8 9 )

Subset 2,1,7, dan 3 ini di masukan dalam Q1 dimulai dari kiri dengan mempertahankan urutan sehingga menjadi

Q1 = (2 1 7 4 5 6 3 8 9)

Untuk Q2 diperlukan sama hanya perlu meukar induk pertama menjadi induk kedua dan induk kedua menjadi induk pertama yang menjadi:

Q2 = (3 5 2 1 8 7 4 6 9)

One-Point Crossover

Contoh kerja operator ini adalah dengan menentukan crossover point (gen tertentu). Kromosom baru pertama berisi gen pertama sampai gen crossover point dari kromosom induk pertama ditambah dengan gen dari crossover point sampai gen terakhir dari kromosom induk kedua. Kromosom baru kedua berisi gen pertama sampai gen crossover point dari induk kedua ditambahkan dengan gen dari crossover point sampai gen dari kromosom induk pertama. Adapun metode crossover ini dapat diilustrasikan pada gambar berikut:
Gambar 5. Proses crossover dengan satu crossover point
Dari ilustrasi di atas maka contoh penerapan metode One-Point Crossover adalah sebagai berikut:

Parent 1: 1 2 3 4 5 | 6 7 8 9
Parent 2: 4 5 3 6 8 | 9 7 2 1

Setelah proses crossover turunan yang dapat dihasilkan adalah dari kedua parent diatas adalah:

Parent 1: 1 2 3 4 5 | 9 7 2 1
Parent 2: 4 5 3 6 8 | 6 7 8 9

Two-Point Crossover

Proses Two-Point Crossover hampir sama dengan prosedur One-Point Crossover, kecuali pada Two-Point Crossover harus dipilih dua crossover point dan hanya gen yang ada di antara kedua crossover point itu yang akan ditukarkan.
Metode ini dapat menjadi bagian awal dan akhir dari kromosom dan hanya menukar bagian tengahnya saja.

N-Point Crossover

Prosedur N-Point Crossover hampir sama baik dengan prosedur one-point crossover maupuntwo-point crossover, hanya saja dalam n-point crossover ini harus dipilih n crossover point dan hanya gen di antara crossover point ganjil dan genap yang dapat ditukarkan sedangkan gen diantara genap dan ganjil operator crossover tidak berubah. Atau dengan kata lain harus dipilih posisi n dan hanya bit antara ganjil dan genap posisi crossover yang akan dihilangkan.

Contoh:
P1= 9 7 6 3 2 8
P2= 2 1 9 7 4 5

Jika didapatkan angka random untuk n=3 dan diacak 1,2 dan 4 sebagai posisi dari gen yang akan di crossover, didapatkan kromosom turunan:

T1= 9 1 6 3 4 5
T2= 2 7 9 7 2 8

Mutasi

Mutasi adalah operator yang membutuhkan satu perameter. Kromosom operator ini merupakan nilai suatu gen dari sebuah kromosom sehingga kromosom yang baru ini berbeda dengan kromosom yang lama. Sekumpulan kejadian dengan suatu nilai pelanggaran maksimal dapat dengan mudah dihilangkan selama evaluasi fitness “tujuan dari proses mutasi ini, untuk mempertahankan kehilangan permanent dari suatu bit atau gen” (Whitley,1993:16). Seluruh proses mutasi ini menjanjikan keuntungan melalui pengarahan mutasi kemana mutasi ini tersebut sangat dibutuhkan. Oprator mutasi digunakan untuk melakukan modifikasi satu atau lebih dari nilai gen dalam individu yang sama. Mutasi memastikan bahwa probabilitas untuk pencarian pada daerah tertentu dalam persoalan tidak akan pernah nol dan mencegah kehilangan total materi genetika setelah pemilihan dan penghapusan. Mutasi ini bukanlah operator genetika yang utama, yang dilakukan secara acak pada gen dengan kemungkinan yang lebih kecil. Metode ini disebut metasi gen (gene mutation) terdapat metode lain yaitu: “order mutation” dimana dimungkinkan untuk menghilangkan seluruh gen dari dua gen yang dipilih secara acak. Terdapat empat operator yang biasa digunakan untuk permasalahan penjadwalan antara lain:

Violation Directed Mutation (VDM)

Memilih sutatu kejadian dengan suatu nilai pelanggaran maksimal, dan secara acak mengubah waktu penugasan.

Event Freeing Mutation (EFM)

Memilih suatu kejadian dengan sauatu pelanggaran maksimal, kemudian memberi waktu baru yang mana akan mengurangi secara maksimal angka ini.

Secara stokastik memilih suatu kejadian ,bias melalui kejadian itu dengan nilai pelanggaran yang tinggi, kemudian secara stokastik memilh waktu baru untuk kejadian ini, bisa melalui waktu yang mana akan mengurangi secara maksimal angka pelanggaran kejadian.

Fungsi Objektif

Fungsi objektif adalah tujuan dari optimasi permasalahan. Biasanya fungsi objektif ini hanya dua macam yaitu memaksimalkan dan meminimalkan

Model Pengembangan Algoritma Genetika

Algoritma genetika menyelesaikan permasalahan dengan cara menghasilkan, mengubah dan mengevaluasi kandidat solusi dari permasalahan tersebut. Awalnya sebuah populasi acak yang terdiri dari kromosom-kromosom di hasilkan kemudian kromosom-kromosom itu diubah oleh operator genetika yaitu crossover dan mutasi, kemudian kromosom-kromosom tersebut dievaluasi oleh fungsi fitness.

Terdapat beberapa cara dalam menentukan inisialisasi diantaranya biner dan non biner. Untuk inisialisasi masalah penjadwalan yang paling sederhana dapat dilihat sebagai masalah penetapan V even atau kejadian dalam S selang waktu dengan kata lain definisi dari masalah penjadwalan adalah:

E adalah definisi dari sejumlah V even (e1.e2,….en)
T adalah definisi dari sejumlah S selang waktu (t1,t2,…tn)

Berdasarkan definisi tersebut maka permasalahan penjadwalan tersebut ditetapkan sebagai pasangan terurut (a,b) yang berarti a Є E dan b Є T, dengan intepretasi bahwa evena terjadi pada selang waktu b.

Terdapat berbagai versi pengkodean masalah penjadwalan diantaranya adalah representasi klasik dan representasi Tuples. Dalam representasi kalsik digunakan matrik dua dimensi. Bagian kolom merupakan bagian produksi dan bagian baris merupakan interval waktu. Isi dari matrik M(i,j) adalah staf atau karyawan yang mengerjakan WOdan jumlah shiftnya. Jadi matrik M(i,j) dibaca sebagai karyawan dengan shift m mengerjakan WOpada bagian produksi.

Metode penentuan lokasi awal sangat berpengaruh terhadap kinerja algoritma genetika. Ada dua cara yang bisa digunakan untuk menghasilkan dua populasi awal. Cara yang pertama dengan menghasilkan seluruh kromosom secara acak. Sedangkan cara yang kedua sebagain kromosom dihasilkan dengan metode tertentu, yang dikenal dengan populasi awal terarah. Salah satu metode untuk membangkitkan populasi awal adalah metodeJoshepus permutation.

Berikut adalah algoritma joshepus permutation:


Step 1 = [ Nilai awal ]
For i=1 to N Step1
Plist[i]  0
End for
N Loop  random (N) + 1
F gen  random (N) + 1
K=1
Step 2 = [ Isi nilai gen ]
Kromosom [k]  F gen
Plist [F gen]  1
Step 3 = [ Cek kondisi ]
If ( K= n ) then go to Step 7
End if
Step 4 = [ Cari nilai gen selanjutnya ]
For i=1 to N Loop Step1
Repeat
F gen  F gen + 1
If (F gen > N) then
F gen  1
Until Plist [F gen] <> 1
End if
End for
Step 5 = [ Naikan ounter k ]
K =K+1
Step 6 = [ Ulangi Step2 sampai Step 5 ]
Go to Step 2
Step 7 = [ Ulangi untuk kromosom selanjutnya ]
If Belum_semua_krm_telah_diinisialisasi then
Kromosom  parameter_ke_krm_berikutnya_dalam_populasi
Go to Step 2
End if
Step 8 = [ Selesai ]
Return


N adalah jumlah allele dalam seluruh kromosom, Plist adalah sebuah array dengan jumlah element sebanyak N, random (x) adalah fungsi generator bilangan random antara 0 sampai x-1. element array dimulai dari 1. kromosom adalah element dari array populasi yang menampung urutan allele.

Fungsi Evaluasi atau Fungsi Fitness

Fungsi adalah salah satu aspek terpenting dalam algoritma genetika. Fungsi evaluasi yang baik harus mampu menghasilkan suatu kurva silo. Siklus yang cukup baik dan dapat mewakili permasalahan yang dihadapi.Pengumpulan dini dalam algoritma genetika terjadi ketika beberapa kromosom dengan nilai fitness yang tinggi (tapi bukan optimal) memdominasi populasi dengan mengakibatkan algoritma genetika konvergen pada local optima. Ketika populasi konvergenkemampuan algoritma genetika untuk mencari solusi manjadi lebih baik. Crossover antara kromosom yang hampir identik menghasilkan kromosom baru yang identik dalam operasi ini hanya operasi mutasi yang mampu menghasilkan kromosom yang relatif baru dan merupakan cara untuk menghidarkan kromosom yang super mendominasi populasi.


Algoritma Genetika


Algoritma genetika adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetika adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritma Genetika pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma Genetika khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. 

Evolusi

Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.
Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: 

(1) representasi genetik dari penyelesaian
(2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (obyek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit mewakili obyek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah obyek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran obyek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua obyek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi.

Algoritma genetik merupakan suatu metode yang menggunakan seleksi alam yang merupakan bagian utama dari prinsip evolusi sebagai dasar pemikiran untuk menyelesaikan suatu permasalahan. Prinsip ini dikemukakan oleh Charles Darwin, dimana tanpa menghiraukan prinsip dasar penurunan sifat, Darwin mengemukakan penggabungan kualitas induk pada generasi berikutnya, disamping itu bahwa individu yang mampu beradaptasi dengan lingkunganya akan mempunyai kesempatan hidup yang lebih besar.

Penggunaan prinsip genetika pada komputer dimulai pada tahun 1950 ketika beberapa ahli Biologi mengunakan komputer untuk simulasi sistem biologi. Akhir tahun 1975 John Holland dari Universitas Michigan melalui paper yang berjudul “Adaption in Natural and Artificial System” mengunakan konsep dasar algoritma genetika. Algoritma genetika bekerja dengan suatu populasi string dan melakukan proses pencarian nilai optimal secara parallel, dengan mengunakan operator genetika. Algoritma genetika akan melakukan rekombinasi antar individu.

Algoritma genetika memiliki elemen dasar berupa string yang tersusun dari rangkaian substring (gen), yang masing-masing merupakan kode dari parameter dalam ruang solusi dimana suatu string (kromosom) menyatakan kandidat solusi. Kumpulan string dalam populasi berkembang dari generasi ke generasi melalui operator genetika. Pada setiap iterasi, individu-individu (Kromosam) dalam populasi itu akan dievolusi dan diseleksi untuk menentukan populasi pada generasi berikutnya. Populasi ini akan terus berulang sampai menemukan suatu parameter dengan nilai yang paling optimal sesuai dengan yang diinginkan. Adapun struktur umum algoritma genetika dapat diilustrasikan pada gambar berikut:

Gambar 1. Struktur umum Algoritma Genetika

Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah allele yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukancrossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahanknapsack atau pengepakan, dimana ada beberapa barang dengan jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung olehk napsack tanpa harus menambah kapasitasnya.

Istilah-istilah yang digunakan dalam Algoritma genetika ini hampir sama dengan istilah-istilah yang dipakai dalam bidang biologi genetika, antara lain Gen, Kromosom, Populasi, Fungsi Fitness, dan operator genetika yang meliputi mutasi dan crossover.

Gen adalah suatu sel dari suatu kromosom atau nilai yang terdapat dalam Algoritma genetika ini dapat dibentuk oleh sebuah byte bahkan tidak menutup kemungkinan suatu string. Gen ini mewakili sebagian kecil dari solusi permasalahan.

Individu dalam populasi disebut string, genotype atau kromosom-kromosom terdiri dari unit-unit yang dinamakan Gen, Karakter, Decoder. Kromosom ini dapat mewakili suatu solusi, dimana dapat diilustrasikan dalam gambar dibawah ini:


Gambar 2. Kromosom dalam 
Untuk mempresentasikan kromosom dilakukan dengan proses encoding, dibawah ini akan dijelaskan beberapa proses encoding yang biasa digunakan dalam beberapa kasus tertentu.

Permutation Encoding

Untuk jenis Permutation Encoding ini digunakan untuk permasalahan proses pengurutan, misalnya terdapat kasus optimasi jadwal atau pada kasus traveling salesman. Pada Permutation Encoding, setiap Gen pada kromosom berupa angka dimana dapat ditampilkan seperti gambar di bawah ini:
Gambar 3. Permutation Encoding
Permutation Encoding hanya berlaku untuk permasalahan pengurutan, untuk itu dalam kasus-kasus yang ada pada Permutation Encoding terdapat beberapa jenis crossover dan mutasi yang harus dibuat untuk mempertahankan kromosom agar tetap konsisten. Contoh penggunaan Permutation Encoding ini adalah pada kasus trvelling salesman, dimana terdapat beberapa kota dengan jarak masing-masing. Pada kasus traveling salesman ini seorang salesman harus mengunjungi semua kota yang ada, tetapi tidak harus berjalan jauh untuk mencapai seluruh kota. Permasalahanya adalah menentukan urutan kota yang akan dikunjungi untuk meminimalisasi jarak yang harus ditempuh.

Binary encoding

Binary encoding adalah jenis encoding yang paling sering digunakan karena kasus pertama yang ada pada Algiritma Genetik menggunakan algoritma jenis ini. Setiap kromosom padaBinary encoding merupakan bit 0 dan 1 dimana dapat ditampilkan pada gambar bawah:
Gambar 4. Binary encoding
Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah Gen yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukancrossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahanknapsack atau pengepakan, dimana ada beberapa barang dengna jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung oleh knapsack tanpa harus menambah kapasitasnya.

Crossover

Crossover adalah operator algoritma genetika yang membutuhkan parameter dua kromosom. Dua buah kromosom tersebut disebut kromosom induk. Operator ini akan menghasilkan dua buah kromosom baru. Ada beberapa jenis crossover yang sering digunakan dalam algoritma genetika antara lain:

Ordered Based Crossover

Ordered based Crossover diawali dengan menentukan posisi-posisi gen secara random pada induk pertama misalnya didapatkan posisi 3,4,6 dan 9 pada induk.

P1= ( 1 2 3 4 5 6 7 8 9 )

P1= ( 4 5 2 1 8 7 6 9 3 )

Kemudian Gen-gen pada induk yang berada tepat dibawah posisi-posisi tersebut dicatat yaitu 2,1,7 dan 3 untuk Q1 disalin dari P1 dengan menghilangkan angka-angka 2,1,7 dan3 tersebut sehingga menjadi

Q1= ( x x x 4 5 6 x 8 9 )

Subset 2,1,7, dan 3 ini di masukan dalam Q1 dimulai dari kiri dengan mempertahankan urutan sehingga menjadi

Q1 = (2 1 7 4 5 6 3 8 9)

Untuk Q2 diperlukan sama hanya perlu meukar induk pertama menjadi induk kedua dan induk kedua menjadi induk pertama yang menjadi:

Q2 = (3 5 2 1 8 7 4 6 9)

One-Point Crossover

Contoh kerja operator ini adalah dengan menentukan crossover point (gen tertentu). Kromosom baru pertama berisi gen pertama sampai gen crossover point dari kromosom induk pertama ditambah dengan gen dari crossover point sampai gen terakhir dari kromosom induk kedua. Kromosom baru kedua berisi gen pertama sampai gen crossover point dari induk kedua ditambahkan dengan gen dari crossover point sampai gen dari kromosom induk pertama. Adapun metode crossover ini dapat diilustrasikan pada gambar berikut:
Gambar 5. Proses crossover dengan satu crossover point
Dari ilustrasi di atas maka contoh penerapan metode One-Point Crossover adalah sebagai berikut:

Parent 1: 1 2 3 4 5 | 6 7 8 9
Parent 2: 4 5 3 6 8 | 9 7 2 1

Setelah proses crossover turunan yang dapat dihasilkan adalah dari kedua parent diatas adalah:

Parent 1: 1 2 3 4 5 | 9 7 2 1
Parent 2: 4 5 3 6 8 | 6 7 8 9

Two-Point Crossover

Proses Two-Point Crossover hampir sama dengan prosedur One-Point Crossover, kecuali pada Two-Point Crossover harus dipilih dua crossover point dan hanya gen yang ada di antara kedua crossover point itu yang akan ditukarkan.
Metode ini dapat menjadi bagian awal dan akhir dari kromosom dan hanya menukar bagian tengahnya saja.

N-Point Crossover

Prosedur N-Point Crossover hampir sama baik dengan prosedur one-point crossover maupuntwo-point crossover, hanya saja dalam n-point crossover ini harus dipilih n crossover point dan hanya gen di antara crossover point ganjil dan genap yang dapat ditukarkan sedangkan gen diantara genap dan ganjil operator crossover tidak berubah. Atau dengan kata lain harus dipilih posisi n dan hanya bit antara ganjil dan genap posisi crossover yang akan dihilangkan.

Contoh:
P1= 9 7 6 3 2 8
P2= 2 1 9 7 4 5

Jika didapatkan angka random untuk n=3 dan diacak 1,2 dan 4 sebagai posisi dari gen yang akan di crossover, didapatkan kromosom turunan:

T1= 9 1 6 3 4 5
T2= 2 7 9 7 2 8

Mutasi

Mutasi adalah operator yang membutuhkan satu perameter. Kromosom operator ini merupakan nilai suatu gen dari sebuah kromosom sehingga kromosom yang baru ini berbeda dengan kromosom yang lama. Sekumpulan kejadian dengan suatu nilai pelanggaran maksimal dapat dengan mudah dihilangkan selama evaluasi fitness “tujuan dari proses mutasi ini, untuk mempertahankan kehilangan permanent dari suatu bit atau gen” (Whitley,1993:16). Seluruh proses mutasi ini menjanjikan keuntungan melalui pengarahan mutasi kemana mutasi ini tersebut sangat dibutuhkan. Oprator mutasi digunakan untuk melakukan modifikasi satu atau lebih dari nilai gen dalam individu yang sama. Mutasi memastikan bahwa probabilitas untuk pencarian pada daerah tertentu dalam persoalan tidak akan pernah nol dan mencegah kehilangan total materi genetika setelah pemilihan dan penghapusan. Mutasi ini bukanlah operator genetika yang utama, yang dilakukan secara acak pada gen dengan kemungkinan yang lebih kecil. Metode ini disebut metasi gen (gene mutation) terdapat metode lain yaitu: “order mutation” dimana dimungkinkan untuk menghilangkan seluruh gen dari dua gen yang dipilih secara acak. Terdapat empat operator yang biasa digunakan untuk permasalahan penjadwalan antara lain:

Violation Directed Mutation (VDM)

Memilih sutatu kejadian dengan suatu nilai pelanggaran maksimal, dan secara acak mengubah waktu penugasan.

Event Freeing Mutation (EFM)

Memilih suatu kejadian dengan sauatu pelanggaran maksimal, kemudian memberi waktu baru yang mana akan mengurangi secara maksimal angka ini.

Secara stokastik memilih suatu kejadian ,bias melalui kejadian itu dengan nilai pelanggaran yang tinggi, kemudian secara stokastik memilh waktu baru untuk kejadian ini, bisa melalui waktu yang mana akan mengurangi secara maksimal angka pelanggaran kejadian.

Fungsi Objektif

Fungsi objektif adalah tujuan dari optimasi permasalahan. Biasanya fungsi objektif ini hanya dua macam yaitu memaksimalkan dan meminimalkan

Model Pengembangan Algoritma Genetika

Algoritma genetika menyelesaikan permasalahan dengan cara menghasilkan, mengubah dan mengevaluasi kandidat solusi dari permasalahan tersebut. Awalnya sebuah populasi acak yang terdiri dari kromosom-kromosom di hasilkan kemudian kromosom-kromosom itu diubah oleh operator genetika yaitu crossover dan mutasi, kemudian kromosom-kromosom tersebut dievaluasi oleh fungsi fitness.

Terdapat beberapa cara dalam menentukan inisialisasi diantaranya biner dan non biner. Untuk inisialisasi masalah penjadwalan yang paling sederhana dapat dilihat sebagai masalah penetapan V even atau kejadian dalam S selang waktu dengan kata lain definisi dari masalah penjadwalan adalah:

E adalah definisi dari sejumlah V even (e1.e2,….en)
T adalah definisi dari sejumlah S selang waktu (t1,t2,…tn)

Berdasarkan definisi tersebut maka permasalahan penjadwalan tersebut ditetapkan sebagai pasangan terurut (a,b) yang berarti a Є E dan b Є T, dengan intepretasi bahwa evena terjadi pada selang waktu b.

Terdapat berbagai versi pengkodean masalah penjadwalan diantaranya adalah representasi klasik dan representasi Tuples. Dalam representasi kalsik digunakan matrik dua dimensi. Bagian kolom merupakan bagian produksi dan bagian baris merupakan interval waktu. Isi dari matrik M(i,j) adalah staf atau karyawan yang mengerjakan WOdan jumlah shiftnya. Jadi matrik M(i,j) dibaca sebagai karyawan dengan shift m mengerjakan WOpada bagian produksi.

Metode penentuan lokasi awal sangat berpengaruh terhadap kinerja algoritma genetika. Ada dua cara yang bisa digunakan untuk menghasilkan dua populasi awal. Cara yang pertama dengan menghasilkan seluruh kromosom secara acak. Sedangkan cara yang kedua sebagain kromosom dihasilkan dengan metode tertentu, yang dikenal dengan populasi awal terarah. Salah satu metode untuk membangkitkan populasi awal adalah metodeJoshepus permutation.

Berikut adalah algoritma joshepus permutation:


Step 1 = [ Nilai awal ]
For i=1 to N Step1
Plist[i]  0
End for
N Loop  random (N) + 1
F gen  random (N) + 1
K=1
Step 2 = [ Isi nilai gen ]
Kromosom [k]  F gen
Plist [F gen]  1
Step 3 = [ Cek kondisi ]
If ( K= n ) then go to Step 7
End if
Step 4 = [ Cari nilai gen selanjutnya ]
For i=1 to N Loop Step1
Repeat
F gen  F gen + 1
If (F gen > N) then
F gen  1
Until Plist [F gen] <> 1
End if
End for
Step 5 = [ Naikan ounter k ]
K =K+1
Step 6 = [ Ulangi Step2 sampai Step 5 ]
Go to Step 2
Step 7 = [ Ulangi untuk kromosom selanjutnya ]
If Belum_semua_krm_telah_diinisialisasi then
Kromosom  parameter_ke_krm_berikutnya_dalam_populasi
Go to Step 2
End if
Step 8 = [ Selesai ]
Return


N adalah jumlah allele dalam seluruh kromosom, Plist adalah sebuah array dengan jumlah element sebanyak N, random (x) adalah fungsi generator bilangan random antara 0 sampai x-1. element array dimulai dari 1. kromosom adalah element dari array populasi yang menampung urutan allele.

Fungsi Evaluasi atau Fungsi Fitness

Fungsi adalah salah satu aspek terpenting dalam algoritma genetika. Fungsi evaluasi yang baik harus mampu menghasilkan suatu kurva silo. Siklus yang cukup baik dan dapat mewakili permasalahan yang dihadapi.Pengumpulan dini dalam algoritma genetika terjadi ketika beberapa kromosom dengan nilai fitness yang tinggi (tapi bukan optimal) memdominasi populasi dengan mengakibatkan algoritma genetika konvergen pada local optima. Ketika populasi konvergenkemampuan algoritma genetika untuk mencari solusi manjadi lebih baik. Crossover antara kromosom yang hampir identik menghasilkan kromosom baru yang identik dalam operasi ini hanya operasi mutasi yang mampu menghasilkan kromosom yang relatif baru dan merupakan cara untuk menghidarkan kromosom yang super mendominasi populasi.

Contoh Program Algoritma Genetika

Source Code Algoritma Genetika

Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman

Tutorial belajar Algoritma Genetika

VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic

Gratis download Algoritma Genetika

Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow

Penerapan implementasi Algoritma Genetika Algoritma Genetika

Posted by: Project-G Contoh Program Algoritma Genetika Updated at : 00.04
Jika Anda perlu source code terkait dengan artikel di atas atau ada yang ingin di tanyakan anda bisa melakukan konsultasi gratis kepada kami, melalui form di bawah. Hasil konsultasi akan di kirimkan ke email Anda. Kami mohon supportnya dengan mengklik beberapa tombol berikut :


Contoh Program Algoritma Genetika

perhatian

Informasi Penting Untuk Mahasiswa !

Kami menawarkan layanan jasa konsultan bimbingan pembuatan program untuk Tesis Skripsi dan Tugas Akhir Informatika, Komputer, Elektro dan Teknik lainnya yang bidang minatnya mengarah ke teknologi informasi. BASED PROJECT :Mobile Development (Java, Adobe, AS3, Android, BB, iOS, WPhone dll), Web & Desktop Development (.Net, C#, MATLAB, PHP, Delphi, Visual Basic dll). BONUS : Di bimbing untuk penguasaan materi dan coding dan revisi.
detail
Label: , ,
Konsultasi gratis