Skema pengkodean pada Algoritma Genetika (Genetic Algorithm)

Menurut Gen dan Cheng (2000) menyatakan bahwa dalam merepresentasikan suatu solusi ke dalam kromosom terdapat empat (4) cara, yaitu; 1). menggunakan pengkodean secara biner, 2). pengkodean bilangan riil positif, 3). pengkodean bilangan bulat dan 4). struktur data umum. Pada Gambar 1 menjelaskan representasi tiga pengkodean dari empat pengkodean yang ada. Dalam postingan kali ini hanya akan mengimplementasikan pengkodean menggunakan bilangan biner.

Gambar 1. Skema Pengkodean

Berdasarkan Gambar 1(a) terdapat tiga individu x1, x2 dan x3 yang diwakili dengan masing-masing tiga gen dalam panjang kromosom sebanyak sembilan gen. Pada masalah klasifikasi setiap individu ini mewakili parameter yang digunakan dalam pengelompokkan.

Pengkodean bertujuan untuk memperoleh nilai biner dari setiap gen g dengan cara (persamaan 1) jika bilangan acak x [0,1) memiliki nilai x > 0.5 maka gen g=1, demikian juga sebaliknya. Setiap gen g berupa nilai bilangan biner 0 atau 1. Representasi setiap individu dengan jumlah gen tertentu disebut dengan panjang bit.

Pendekodean bertujuan untuk mendapatkan kembali nilai individu x dari bentuk biner dalam rentang nilai tertentu. Jika menggunakan rentang interval tertentu dengan batas atas Ra dan batas bawah Rb, maka untuk pendekodean individu X dengan cara biner dirumuskan dalam persamaan 2.

Referesi:

Gen, M. & Cheng, R., 2000. Genetic Algorithms and Engineering Optimization. s.l.:John Wiley & Sons, Inc.

Evaluasi Individu dalam Algoritma Genetika untuk kasus klasifikasi

Evaluasi individu bertujuan untuk mengukur nilai performansi (fitness) dari suatu individu x. Pada evolusi alamiah hanya individu yang memiliki nilai fitness yang tinggi yang akan mampu bertahan hidup. Sedangkan yang memiliki nilai rendah akan mati. Secara umum fitness f yang digunakan pada masalah optimasi untuk memaksimalkan nilai fungsi h maka f=h. Tetapi pada masalah klasifikasi yang digunakan adalah meminimalkan jarak, maka fungsi fitness adalah f=1/h dari suatu fungsi. Untuk mengatasi pembagian dengan nol, maka perlu dikalikan dengan bilangan a, yaitu bilangan yang dianggap sangat kecil. Hasil evaluasi individu untuk meminimalkan fungsi dirumuskan dalam persamaan berikut;

Rumusan untuk mendapatkan fitness ini sangat bergantung pada masalah yang akan diselesaikan. Jika rumusan evaluasi untuk mendapatkan fitnes adalah Eval(Vi) untuk setiap individu Vi(i=1,2,...,N), N adalah ukuran populasi, maka nilai fitness dari seluruh individu dalam populasi dirumuskan pada persamaan berikut

Langkah-Langkah Algoritma Genetika

Langkah-langkah persiapan secara umum yang harus dilakukan pada penggunaan algoritma genetika adalah sebagai berikut;

1.      Menentukan bentuk representasi genetik. Gen dikodekan berdasarkan suatu skema tertentu. Pengkodean gen dapat direpresentasikan menggunakan:

a.    Representasi Bit, allele dari setiap gen hanya dapat memiliki nilai bilangan biner 0 atau 1.

b.    Representasi Floating Point, allele dari setiap gen memiliki nilai bilangan pecahan riil positif.

c.    Representasi Integer, allele dari setiap gen memiliki nilai bilangan bulat yang biasanya positif.

2.      Menentukan cara untuk menciptakan populasi awal.

3.      Menentukan fungsi fitness. Fungsi ini tergantung pada kasus optimasi yang ingin diselesaikan.

4.      Menentukan operasi-operasi genetik yang akan digunakan

5.      Menentukan parameter-parameter pengendali jalannya proses algoritma genetika, yaitu;

a.       Ukuran populasi (UkPop), yaitu banyaknya individu yang terdapat dalam populasi.

b.      Jumlah maksimum generasi (Generasi), yaitu jumlah maksimum iterasi yang akan dijalankan pada algoritma genetik.

c.       Probabilitas crossover (Pc),  yang menentukan besarnya kemungkinan individu untuk melakukan operasi pindah silang.

d.      Probabilitas mutasi (Pm), yang menentukan besarnya kemungkinan individu terkena mutasi.

e.        Probabilitas reproduksi (Pr), yang menentukan besarnya kemungkinan individu untuk melakukan reproduksi.

6.      Menentukan suatu kriteria untuk menghentikan jalannya algoritma, yaitu:

a.       Apabila generasi saat ini telah mencapai jumlah maksimum generasi.

b.       Apabila solusi yang paling optimal telah ditemukan.

7.      Menentukan individu terbaik yang terdapat dalam populasi pada saat kriteria pemberhentian jalannya algoritma terpenuhi.

Setelah melakukan langkah-langkah persiapan secara umum penggunaan algoritma genetika maka langkah-langkah implementasi Algoritma Genetika dalam bentuk yang paling sederhana dan hanya menggunakan operator-operator genetik dasar terdiri dari langkah-langkah berikut (Nurwijaya, 2007):

1.      Bangkitkan populasi awal yang terdiri dari kromosom-kromosom yang masing-masing mewakili sebuah individu. Individu-individu dalam populasi awal tersebut dibangkitkan secara acak.

2.      Langkah-langkah berikut dilakukan secara berulang hingga kondisi terminasi terpenuhi:

a.         Kalkulasi dan simpan nilai fitness masing-masing individu dalam populasi sebagai parameter utama proses seleksi.

b.          Hasilkan populasi baru dengan melakukan operasi-operasi genetik dasar yang dipilih secara probabilistik. Untuk setiap operator genetik diberikan suatu probabilitas tertentu yang menentukan tingkat kemungkinan operator tersebut terjadi. Individu yang akan mengalami operasi genetik dipilih melalui proses seleksi.

                                       i.          Reproduksi, setiap individu memiliki peluang untuk dapat terus berlanjut ke generasi berikutnya, peluang ini sebanding dengan tingkat fitness individu tersebut. Operasi ini dilakukan dengan mereproduksi individu tersebut lalu memasukkannya ke populasi baru.

                                      ii.          Crossover (Kawin Silang), setiap individu memiliki kemungkinan untuk melakukan perkawinan dengan individu lain yang besarnya proporsional dengan nilai fitness. Hasil perkawinan adalah dua offspring yang selajutnya dimasukkan ke populasi baru.

                                     iii.          Mutasi, Operasi ini menghasilkan individu baru dengan cara melakukan perubahan secara acak pada kromosom.

3.      Individu yang memiliki nilai fitness tertinggi dari semua generasi mewakili solusi dari permasalahan optimal yang didapat saat itu.

Referensi:

Nurwijaya, 2007. Analisis Penggunaan Algoritma Genetika Untuk Optimalisasi Jaringan Syaraf Tiruan. Bandung: Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung.

Algoritma Genetika

Kemunculan Algoritma Genetika dipengaruhi atau terinspirasi dari teori-teori dalam ilmu biologi. Algoritma genetika dirintis oleh John Holland dan dikembangkan oleh muridnya David Goldberg. Algoritma Genetika adalah algoritma yang dikembangkan dari proses pencarian solusi menggunakan pencarian secara acak dan memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi.

Pada proses evolusi individu secara terus-menerus mengalami perubahan genetik untuk menyesuaikan dengan lingkungan hidupnya. Hanya individu-individu yang memiliki performansi yang baik yang mampu bertahan. Proses seleksi alamiah ini melibatkan perubahan genetik yang terjadi pada individu melalui proses perkembangbiakan. Proses perkembangbiakan ini menjadi proses dasar yang menjadi perhatian utama dengan dasar bagaimana mendapatkan keturunan dari proses perkawinan yang lebih baik.

Prinsip-prinsip dasar

Proses perkembangbiakan yang terjadi dalam algoritma genetika tidak terlepas dari istilah-istilah yang diadopsi dari teori evolusi genetika dalam ilmu biologi. Istilah-istilah yang berasal dari ilmu biologi yang dipakai dalam algoritma genetika.

Genotype (Gen) merupakan  sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan. Setiap gen mempunyai sebuah nilai yang disebut dengan allele dan berada pada posisi tertentu dalam kromosom yang disebut dengan loci/locus. Allele tersebut dapat berupa angka biner (0/1) atau bertipe floating point tergantung dari bentuk representasi genetik yang digunakan. Beberapa bentuk nilai-nilai gen dalam algoritma genetika dapat berupa nilai biner, desimal, bilangan bulat maupun karakter huruf. Lebih lanjut tentang nilai-nilai gen yang akan digunakan dalam penelitian ini dibahas dalam bahasan skema pengkodean.

Chromossom (kromosom), merupakan gabungan gen-gen yang membentuk kesatuan yang mewakili suatu nilai tertentu. Kesatuan kromosom akan membentuk individu menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat. Seringkali individu-individu yang ada dalam populasi disebut dengan kromosom (string) yang mempunyai panjang yang sama. Setiap kromosom terdiri dari gen-gen yang tersusun secara linier.

Sekumpulan individu yang sejenis akan membentuk populasi. Populasi  merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. Setiap proses siklus evolusi dinyatakan dengan istilah generasi. Individu dalam sebuah generasi akan mengalami evaluasi untuk mendapatkan suatu nilai yang dinyatakan dalam istilah fitness. Fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.

Menurut Bandyopadhyay dan Pal (2007) menyatakan bahwa algoritma genetika memiliki karakteristik yang menguntungkan untuk permasalahan sebagai berikut;

1.      Masalah yang tidak atau kurang adaptif terhadap penyelesaian secara analitik matematis.

2.      Masalah yang harus diselesaikan secara paralel.

3.      Solusi yang diharapkan tidak harus paling optimal tetapi dapat diterima.

4.      Dalam keterbatasan waktu, ruang masalah cukup besar, kompleks dan sulit dipahami.

Referensi: 
Bandyopadhyay, S. & Pal, S. K., 2007. Classification and Learning Using Genetic Algorithms: Application in Bioinformatics and Web Intellegence. New York: Springer. 

Mengurutkan data

Bermain-main array menggunakan bahasa pemrograman visual basic (VB6) khususnya yang diaplikasikan dalam bentuk fungsi atau prosedur sangat menarik. Ni,.. salah satu buktinya, kita buat untuk mengurutkan data dalam bentuk array atau larik satu dimensi. Memang sih sebenarnya terdapat banyak metode atau cara mengurutkan data, disini akan dibuat fungsi untuk pengurutan sederhana (kalau tidak salah biasanya disebut buble sort). Kode fungsinya adalah sebagai berikut:

Kisi-Kisi SBD

Agar dapat menyelesaikan ujian akhir semester di harapkan mahasiswa memahami dan menjelaskan menggunakan contoh-contoh dari hal-hal berikut;
1. Jenis-jenis atribut
2. Aljabar relasi (baik dari operasi dasar, additional maupun extended)
3. Bahasa SQL, yang dikaitkan dengan aljabar relasi
4. Teori optimasi (metode pohon hirarki) aljabar relasi dan dapat menterjamahkan ke dalam bentuk bahasa SQL.
5. Entity relational diagram (ER-D), simbol-simbol dasar maupun simbol ER-D lanjut, dapat memetakan ER-D ke dalam skema database.

Notifikasi:
Ujian boleh menggunakan catatan kuliah.
selain catatan kuliah tidak diperbolehkan.