Belajar Algoritma Genetika Bagian 1

Kali ini kita akan belajar mengenai algoritma genetika dimulai dari sejarah awal pencetusnya, bagaimana algoritma genetika bekerja? langkah-langkah dan hal-hal yang perlu diperhatikan serta yang paling penting adalah menulis algoritma tersebut kedalam suatu bahasa pemrograman yaitu Octave!

Sejarah Algoritma Genetika

Algoritma genetika ini ditemukan oleh John Holland dan dikembangkan oleh muridnya David Goldberg Algoritma Genetika memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi yaitu  individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. “Hanya individu-individu yang kuat yang mampu bertahan”.

Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan. Dalam algoritma genetika ini, proses perkembang-biakan ini menjadi proses dasar yang menjadi perhatian utama, dengan dasar berpikir: “Bagaimana mendapatkan keturunan yang lebih baik”.

John Holland membangun teori dan dasar-dasar algoritma genetika, dimulai dari teori schemata, operator-operator genetik, hingga membuat program komputernya. Selama kurang lebih 3 tahun ( 1962-1965), Holland aktif memberi kuliah tentang algoritma genetika di Univeristas Michigan, dengan muridnya bernama David Goldberg yang terus mengembangkannya.

David Goldberg yang merupakan kandidat doktor USA berhasil mengaplikasikannya algoritma genetika dalam perancangan sistem perpipaan untuk distribusi gas alam. Goldbreg memahamai bahwa masalah perancangan pipa yang dikajinya itu sangat rumit, oleh hal tersebut dikembangkan algoritma genetika untuk memecahkan permasalahan tersebut.

Hasil riset itu dituangkannya dalam buku dengan judul Genetic Alogirthm in Search, Optimization, and Machine Learning terbitan Addison-Wesley Publishing Company tahun 1989, yang saat ini menjadi buku rujukan utama yang ingin mempelajari konsep-konsep algoritma genetika.

Untuk saat ini penerapan algoritma genetika sudah banyak diaplikasikan di berbagai bidang seperti engineering, robotik, manajemen industri (sistem produksi, tata letak fasilitas, penjadwalan produksi), bidang agroindustri pada sistem penyimpanan dan pengawetan hasil laut, sistem bioreaktor, dan prediksi permintaan produk agroindustri

Bagaimana cara kerja algoritma genetika?

Algoritma ini bekerja dengan sebuah populasi yang terdiri dari individu individu, yang masing-masing mempresentasikan sebuah solusi yang mungkin bagi persoalan yang ada. Dalam kaitan ini, individu dilambangkan dengan sebuah nilai fitness yang akan digunakan untuk mencari solusi terbaik dari persoalan yang ada.

Pertahanan yang tinggi dari individu memberikan kesempatan untuk  melakukan reproduksi melalui perkawinan silang dengan individu yang lain dalam populasi tersebut. Individu baru yang dihasilkan dalam hal ini dinamankan keturunan, yang membawa beberapa sifat dari induknya. sedangkan individu dalam populasi yang tidak terseleksi dalam reproduksi akan mati dengan sendirinya, melalui cara ini, beberapa generasi dengan karakteristik yang bagus akan bermunculan dalam populasi tersebut, untuk kemudian dicampur dan ditukar dengan karakter lain. Dengan mengawinkan semakin banyak individu, maka akan semakin banyak kemungkinan terbaik yang dapat diperoleh.

Sebelum Algoritma Genetika dapat dijalankan, maka sebuah kode yang sesuai (representatif) untuk persoalan hams dirancang. Untuk ini maka titik solusi dalam ruang permasalahan dikodekan dalam bentuk kromosom/string yang terdiri atas komponen genetik terkecil yaitu gen. Dengan teori evolusi dan teori genetika, di dalam penerapan Algoritma Genetika akan melibatkan beberapa operator, yaitu:

1. Operasi Evolusi yang melibatkan proses seleksi (selection) di dalamnya.
2. Operasi Genetika yang melibatkan operator pindah silang (crossover) dan mutasi (mutation).

Untuk memeriksa hasil optimasi, kita membutuhkan fungsi fitness, yang menandakan gambaran hasil/solusi yang sudah dikodekan. Selama berjalan, induk harus digunakan untuk reproduksi, pindah silang dan imitasi untuk menciptakan keturunan. Jika Algoritma Genetika didesain secara baik, populasi akan mengalami konvergensi dan akan didapatkan sebuah solusi yang optimum.

Fundamental Algoritma Genetika

Setidaknya ada 6 langkah untuk menggunakan algoritma genetika yaitu

1. Mendefinisikan individu, dimana individu menyatakan salah sate solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidakya sebuah individu atau baik-tidak-nya solusi yang didapatkan.
3. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk.
4. Menentukan proses seleksi yang akan digunakan.
5. Menentukan proses perkawinan silang (cross-over) dan
6. mutasi gen yang akan digunakan.

1. Mendefinisikan Individu dalam Algoritma Genetika

Individu menyatakan salah satu solusi yang mungkin. Individu bisa dikatakan sama dengan kromosom, yang merupakan kumpulan gen. Gen ini bisa biner, float, dan kombinatorial. Beberapa definisi penting yang perlu diperhatikan di mendefinisikan individu untuk membangun penyelesaian permasalahan dengan algoritma genetika adalah sebagai berikut:

• Genotype (Gen) adalah sebuah nilai yang menyatakan satuan dasar yang membentuk suatu anti tertentu dalam saki kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika. gen ini bisa berupa nilai biner. float, integer maupun karakter. atau kombinatorial.
• Allele adalah nilai dari gen.
• Kroxnosom adalah gabungan gen-gen yang membentuk nilai tertentu.
• Individu menyatakan suatu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat
• Populasi merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.
• Generasi, menyatakan satu siklus proses evolusi atau satu iterasi di dalam algoritma genetika.

Lebih jelasnya mengenai pengertian diatas dapat diilustrasikan sebagai berikut

Misalkan didalam kasus traveling sales problem (TSP) dibawah ini, maka individu dinyatakan sebagai jalur yang ditempuh, dalam penentuan nilai maksimal dari F(x,y) individu menyatakan nilai (x,y). Gambar dibawah ini ada 2 kemungkinan jalur yang ditempuh dalam TSP dan cara mempresentasikannya dalam individu

 

Lebih lanjut mengenai kromosom

Proses untuk membuat kode atau membentuk struktur kromosom ini disebut sebagai proses pengkodean (encoding). Sebuah kromosom terdiri atas unit-unit terkecil yang disebut gen. Sebuah gen menggambarkan sebuah unit informasi yang terkandung dalam sebuah ruang pencarian (search space). Kumpulan dari gen-gen membentuk sebuah kromosom yang menggambarkan solusi masalah yang lengkap dan layak. Kromosom adalah simbol dalam bentuk string yang biasanya (tetapi tidak selalu) berbentuk bilangan biner, yaitu kombinasi angka 0 dan 1. Angka 0 dan 1 ini merupakan sebuah gen. Kumpulan dari kromosom-kromosom membentuk sebuah komunitas yang dinamakan populasi.

Kunci dari kekuatan algoritma genetika terletak pada kromosom itu sendiri di mana kromosom tidak mengetahui makna yang terkandung di dalamnya. Sehingga untuk mencari solusi yang paling balk atau paling optimal, digunakanlah fungsi fitness. Fungsi fitness berfungsi untuk mengukur seberapa bagus atau seberapa fit sebuah kromosom. Proses pengkodean kromosom dapat dilakukan menggunakan bilangan biner.

Representasi Kromosom atau teknik pengkodean

Untuk dapat mengaplikasikan algoritma genetika, langkah pertama yang harus dilakukan adalah membuat pengkodean (encoding) calon solusi ke dalam suatu bentuk representasi kromosom. Representasi kromosom yang pertama kali diperkenalkan oleh Holland (1975) adalah representasi string biner. Dalam representasi ini, sebuah kromosom terdiri atas beberapa elemen yang disimbolkan dengan angka nol (0) dan satu (1). Setiap untaian elemen memiliki arti khusus yang menunjukkan nilai fitness kromosom yang bersangkutan.

Bentuk representasi biner yang diperkenalkan oleh Holland (1975), kurang cocok dipakai dalam memecahkan masalah kombinatorial (Gen dan Cheng 1997), seperti masalah Travelling Salesman Problem (TSP) dan masalah penjadwalan flow-shop. Akhir-akhir ini, beberapa peneliti telah memperkenalkan beberapa bentuk representasi baru (non-biner) sesuai dengan masalah yang akan dipecahkan. Contoh representasi non-biner ini adalah representasi bilangan integer dan representasi matrix. Penggunaan representasi ini akan dibahas pada bab selanjutnya.

Dengan demikian kromosom dapat direpresentasikan dengan menggunakan:

• String bit : 10011 dst.
• Array bilangan real:  65.65. -67.98, 77.34 dst.
• Elemen permutasi: E10. E5 dst
• Daftar aturan: RI. R2. R3 dst.
• Elemen program: pemrograman genetika

2. Membangkitkan Populasi Awal

Membangkitkan populasi awal adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Ukuran untuk populasi tergantung pada masalah yang akan diselesaikan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian dilakukan pembangkitan populasi awal. Syarat-syarat yang harus dipenuhi untuk menunjukkan suatu solusi hams benar-benar diperhatikan dalam pembangkitan setiap individunya.

Teknik dalam pembangkitan populasi awal ini ada beberapa cara, diantaranya adalah sebagai berikut:

1. Random Generator: Inti dari cara ini adalah melibatkan pembangkitan bilangan random untuk nilai setiap gen sesuai dengan representasi kromosom yang digunakan.

2. Pendekatan Tertentu (memasukan nilai tertentu ke dalam gen): Cara ini adalah dengan memasukan nilai tertentu kedalam gen dari populasi awal yang dibentuk

3. Permutasi: salah satu cara permutasi gen dalam pembangkitan populasi awal adalah permutasi untuk masalah kombinatorial seperti TSP

3. Fungsi Fitness dan Fungsi Tujuan

Algoritma genetika bekerja dengan mengukur seberapa baik sebuah kromosom dapat menyelesaikan suatu masalah. Pengukuran dilakukan dengan menggunakan fungsi fitness, yaitu fungsi tujuan dari masalah yang hendak diselesaikan. Fungsi fitness hanya menggunakan satu set parameter masalah dan mengembalikan ukuran kegunaannya (efisiensi, biaya, dan sebagainya). Semakin besar nilai fitness, semakin besar pula kromosom dalam populasi sehingga semakin besar kemungkinan kromosom tersebut untuk tetap survive pada generasi berikutnya.

Suatu fungsi fitness dapat sama atau merupakan hasil modifikasi terhadap fungsi tujuan masalah yang hendak diselesaikan.

• Jika masalahnya adalah masalah maksimasi, fungsi fitness-nya sama atau berbanding lurus dengan fungsi tujuan.
• Namun jika masalahnya adalah masalah minimasi, fungsi fitness-nya berbanding terbalik dengan fungsi tujuan. Secara umum, algoritma genetika mengoperasikan kromosom dengan fitness positif dan mencari untuk memaksimumkan fitness ini. Proses minimasi dapat dilakukan dengan mudah, dengan cara membalik fungsi maksimasi.

Apa itu Elitisme?

Proses seleksi yang dilakukan secara random sehingga tidak ada jaminan bahwa suatu indvidu yang bernilai fitness tertinggi akan selalu terpilih. Walaupun individu 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 selama evolusi, maka perlu dibuat satu atau beberapa copy-nya. Prosedure ini dikenal sebagai elitisme

4. Seleksi Kromosom

Seleksi merupakan salah satu operasi untuk memastikan bahwa jumlah perwakilan dari sebuah kromosom yang diterima pada generasi selanjutnya akan bergantung pada nilai fitness-nya yang dibandingkan dengan nilai fitness rata-rata dad populasi yang ada. Kromosom-kromosom yang telah dievaluasi dengan menggunakan fungsi fitness akan diseleksi untuk dijadikan induk. Kromosom-kromosom yang memiliki nilai fitness yang sangat baik akan memiliki peluang yang lebih besar untuk terpilih menjadi induk dan tetap bertahan pada generasi berikutnya, sedangkan kromosom-kromosom yang lebih buruk akan tergantikan oleh kromosom baru.

Pada model seleksi alam, kromosom yang memiliki nilai fitness lebih baik akan memiliki peluang bertahan hidup (survival of the fittest) yang lebih baik pada generasi berikutnya. Sebaliknya, kromosom yang memiliki nilai fitness buruk akan tergantikan oleh kromosom baru yang lebih baik. Proses seleksi dalam algoritma genetika juga meniru prinsip seleksi alam dalam cara kerjanya. Salah satu prinsip umum seleksi adalah peluang masing-masing kromosom untuk terpilih sebanding dengan nilai fitness-nya. Tipe seleksi ini disebut fitness proportional selection. Jadi, jika kromosom A dua kali nilainya dari kromosom B, kromosom A seharusnya memiliki dua kali kesempatan untuk bereproduksi.

Salah satu teknik seleksi dalam algoritma genetika adalah teknik seleksi cakram rolet (roulette wheel selection) yang dikenalkan oleh Goldberg (1989). Teknik seleksi ini diilustrasikan sebagai teknik pemutaran cakram rolet. Setiap kromosom dalam populasi menempati suatu slot pada cakram rolet. Besarnya ukuran slot adalah sama dengan rasio antara nilai fitness suatu kromosom dengan total nilai fitness semua kromosom. Untuk menghasilkan sejumlah populasi, rolet tersebut diputar sebanyak ukuran populasi yang ada.

Seleksi dengan cara Roulette

Metode seleksi dengan mesin roulette ini merupakan metode yang paling sederhana dan sering dikenal dengan nama stochastic sampling with replacement. Cara kerja metode ini adalah sebagai berikut:

1. Dihitung nilai fitness dari masing-masing individu (f. dimana i adalah individu ke-1 s/d ke-n)
2. Dihitung total fitness seinua individu
3. Dihitung probabilitas masing-masing individu
4. dari probabilitas tersebut, dihitung jatah masing-masing individu pada angka 1 sampai 100
5. Dibangkitkan bilangan random antara 1 sampai 100
6. dari bilangan random yang dihasilkan, ditentukan individu main yang terpilih dalam proses seleksi

seleksi dengan turnamen

Pada metode seleksi dengan turnamen. ditetapkan suatu nilai tour untuk individuindividu yang dipilih secara random dari suatu populasi. Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk. Parameter yang digunakan pada metode ini adalah ukuran tour yang bernilai antara 2 sampai N (jumlah individu dalam suatu populasi).

Tujuan utama yang ingin dicapai dalam menggunakan algoritma genetika adalah agar sekumpulan kromosom (talon solusi) yang dibangkitkan secara acak pada populasi awal dapat berkembang biak dengan sendirinya (melalui beberapa generasi) hingga konvergen memberikan suatu nilai fitness yang terbaik (nilai optimal). Kromosom yang terbentuk path generasi baru disebut kromosom anak (offspring).

Sebuah kromosom anak dapat terbentuk melalui dua proses utama yaitu dengan menggabungkan elemen-elemen antara dua kromosom induk (parents) menggunakan operator penyilangan, atau dengan memodifikasi sebuah kromosom induk menggunakan operator, mutasi. Dalam satu generasi, kedua proses di atas dapat terjadi secara berurutan (sequential) maupun paralel. Maksud secara berurutan adalah proses penyilangan terjadi lebih dahulu pada dua kromosom induk, lalu dilanjutkan dengan proses mutasi pada kedua kromosom anak yang baru terbentuk. Proses semacam ini disebut mutation embedded within crossover. Sedangkan maksud secara paralel adalah proses penyilangan dan mutasi terjadi secara terpisah pada kromosom-kromosom induk saja, tidak pada kromosom anak yang baru terbentuk.

5. Penyilangan atau Cross over

Penyilangan (crossover) adalah operator utama atau operator primer dalam algoritma genetika. Operator ini bekerja pada sepasang kromosom induk untuk menghasilkan dua kromosom anak dengan cara menukarkan beberapa elemen (gen) yang dimiliki masing-masing kromosom induk. Tingkat penyilangan atau peluang penyilangan (dinotasikan sebagai Pc) adalah rasio antara jumlah kromosom yang diharapkan mengalami penyilangan dalam setiap generasi dengan jumlah kromosom total dalam populasi. Oleh karena penyilangan adalah operator primer, nilai Pc yang digunakan biasanya cukup tinggi (0,6-1). Tingkat penyilangan yang tinggi menyebabkan semakin besarnya kemungkinan algoritma genetika mengeksplorasi ruang pencarian sekaligus mempercepat ditemukannya solusi optimum. Akan tetapi, apabila tingkat penyilangan terlalu tinggi, hal ini sama artinya dengan membuang-buang waktu mencari solusi pada daerah yang mungkin saja kurang menjanjikan (unpromising region). Penentuan nilai Pc yang tepat sangat bergantung pada permasalahan yang dihadapi.

Holland (1975) telah memperkenalkan operator penyilangan yang disebut penyilangan satu-titik (one-point crossover). Penyilangan satu-titik ini cocok digunakan untuk kromosom dengan representasi biner (0 dan 1). Pada beberapa kasus, seperti masalah TSP (Travelling Salesman Problems), penyilangan satu-titik ini tidak cocok digunakan karena dapat menghasilkan kromosom ilegal. Atas dasar itulah, beberapa peneliti telah mengusulkan teknik penyilangan yang baru, seperti partially-mapped crossover (PMX), order crossover (OX), dan cycle-croossover(CX), position-based crossover, order-based crossover, dan heuristic crossover(Gen dan Cheng 1997). Teknik PMX pertama kali diperkenalkan oleh Goldberg dan Lingle (1985). Teknik PMX dapat dipandang sebagai perbaikan dad teknik penyilangan dua-titik (two- point crossover) yaitu adanya metode perbaikan (repairing procedure) untuk mencegah munculnya kromosom yang ilegal.

6. Mutasi

Mutasi (mutation) adalah operator sekunder atau operator pendukung dalam algoritma genetika yang berperan mengubah struktur kromosom secara spontan. Perubahan spontan ini menyebabkan terbentuknya suatu mutan, yaitu suatu kromosom baru yang secara genetik berbeda dari kromosom sebelumnya. Operator mutasi bekerja pada satu kromosom, tidak pada sepasang kromosom seperti halnya yang dilakukan operator penyilangan. Dalam pencarian solusi optimum, mutasi sangat diperlukan yaitu untuk: (1) mengembalikan gen-gen yang hilang pada generasi-generasi sebelumnya dan (2) memunculkan gengen baru yang belum pernah muncul pada generasi-generasi sebelumnya (Gen dan Cheng 1997).

Tingkat mutasi atau peluang mutasi (dinotasikan sebagai Pm) adalah rasio antara jumlah gen yang diharapkan mengalami mutasi pada setiap generasi dengan jumlah gen total dalam populasi. Oleh karena mutasi adalah operator sekunder, nilai Pm yang digunakan untuk running program biasanya cukup rendah (0,001-0,2). jika tingkat mutasi terlalu rendah, semakin kecil pula kemungkinan memunculkan gen-gen baru. Padahal, gen yang baru sebenarnya sangat diperlukan dalam menunjang keberhasilan memperoleh solusi optimum. Sebaliknya, jika tingkat mutasi terlalu tinggi, akan banyak sekali mutan yang muncul. Akibatnya, banyak karakteristik kromosom induk yang kemungkinan hilang pada generasi berikutnya sehingga algoritma genetika akan kehilangan kemampuan  mengingat atau belajar dari proses pencarian sebelumnya(Gen dan Cheng 1997).

Gen dan Cheng (1997) menyebutkan bahwa dalam beberapa tahun belakangan ini Para peneliti telah memperkenalkan beberapa jenis operator mutasi. Beberapa operator mutasi untuk masalah yang menggunakan permutation representation atau order representation adalah mutasi inversi, mutasi insersi, displacement mutation, dan reciprocal exchange mutation.

Flowchart Algoritma Genetika

Dasar-dasar algoritma genetika dapat dibuat flowchart berikut

Selanjutnya kalian akan belajar menulis algoritma genetika pada bahasa pemrograman

Ref:

Basuki, Achmad. 2003. Algoritma Genetika : Suatu Alternatif Penyelesaian Permasalahan Searching, Optimasi dan Machine Learning. Surabaya : Politeknik Elektronika Negeri Surabaya PENS – ITS.

Kusumadewi, Sri. 2003. Artificial Intellegence – Teknik dan Aplikasinya. Yogyakarta : Graha Ilmu.