Belajar Genethic Algorithm beserta Studi Kasusnya | Kecerdasan Buatan dengan Meniru Algoritma Manusia

 

Pengertian Genetic Algorithm (GA)

Genetic Algorithm (GA) adalah Teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

GA mensimulasikan proses yang terjadi pada populasi alamiah yang merupakan hal penting dalam proses evolusi. Di alam, individu di populasi saling bersaing untuk memperoleh sumber daya untuk kehidupannya. Individu yang berhasil akan bertahan hidup sedangkan individu yang tidak, akan mati dan punah. Keunggulan individu-individu ini diuji melalui suatu fungsi yang dikenal sebagai fitness function. Fitness dalam GA didefinisikan sebagai gambaran kelayakan suatu solusi terhadap suatu permasalahan.

Sejarah Genetic Algorithm (GA)

Algoritme Genetik pertama kali diusulkan oleh John Holland pada tahun 1970-an di New York, untuk aplikasi seluler otomata dan menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Cikal bakal penggunaan GA untuk pencarian dalam system buatan diprakarsai oleh beberapa ahli biologi yang menggunakan komputer digital untuk mengerjakan simulasi dari system genetika. Diantara para ahli tersebut adalah:

• Baricelli, N.A - 1957 melakukan penelitian tentang proses evolusi simbio genetik yang direalisasikan dengan sistem artificial.
• Baricelli, N.A - 1962 mengajukan teori evolusi dan analisis numeriknya
• Fraser, A.S - 1960 menyimulasikan sistem genetika dengan komputer, yang meliputi aspek-aspek S-linkage, dominasi dan epistasis.

GA diimplementasikan sebagai proses simulasi yang dijabarkan sebagai berikut: Populasi dari representasi abstrak (disebut kromosom, genotip, atau genom) dari candidate solution (disebut individual, atau fenotip) dari optimasi yang berevolusi ke solusi yang lebih baik. Biasanya solusi direpresentasikan ke dalam string biner. Evolusi dimulai dari populasi dari individu yang dihasulkan secara random dan terjadi dalam generasi.

Skema Genetic Algorithm

Di setiap generasi, fitness dari setiap individu dalam populasi dievaluasi, beberapa individu dipilih secara stokastik (berdasarkan fitness) dan dimodifikasi (crossover dan kemungkinan mutasi) untuk membentuk populasi baru. Populasi baru lalu dimanfaatkan untuk iterasi selanjutnya. Secara umum, algoritma selesai jika telah menghasilkan generasi maksimum atau hasil dalam populasi dirasa memuaskan (berdasarkan berbagai parameter). 

1. [Start] Generate random population of n chromosomes
2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population.
3. [New population] Create a new population by repeating following steps :
a. [Selection] Select two parent chromosomes from a population according to their fitness (the better  fitness, the bigger chance to be selected)
b. [Crossover] with a crossover probability cross over the parents to form a new offspring (children).
c. [Mutation] with a mutation probability mutate new offspring at each locus (position in chromosome).
d. [Accepting] Place new offspring in a new population
4. [Replace] Use new generated population for a further run of algorithm
5. [Test] If the end condition is satisfied, stop, and return the best solution in current population. If unsatisfied go to step 2.

Genetic Algorithm Element dan Operator

Representasi atau pengkodean kromosom adalah salah satu masalah, ketika Anda mulai menyelesaikan masalah dengan GA. Pengkodean sangat tergantung pada masalahnya. Dalam beberapa hal kromosom harus berisi informasi tentang larutan yang diwakilinya. Cara pengkodean yang paling banyak digunakan adalah string biner. Pengkodean biner adalah yang paling umum, terutama karena karya pertama tentang GA menggunakan jenis pengkodean ini. Dalam pengkodean biner setiap kromosom adalah untaian bit, 0 atau 1. Kromosom tersebut kemudian bisa terlihat seperti Tabel 

Fungsi kebugaran adalah jenis fungsi objektif tertentu yang menentukan optimalitas solusi (yaitu, kromosom) dalam algoritme genetika sehingga kromosom tertentu dapat diberi peringkat terhadap semua kromosom lainnya. Fungsi kebugaran selalu bergantung pada masalah. Misalnya, dalam masalah ransel seseorang ingin memaksimalkan nilai total benda yang dapat dimasukkan ke dalam ransel dengan kapasitas tetap. 

Representasi dari solusi mungkin berupa array bit, di mana setiap bit mewakili objek yang berbeda, dan nilai bit (0 atau 1) menunjukkan apakah objek berada di ransel atau tidak. Tidak semua representasi tersebut valid, karena ukuran objek mungkin melebihi kapasitas ransel. Kesesuaian solusi adalah jumlah nilai dari semua objek di knapsack jika representasi valid, atau 0 jika tidak.

Initialization. Awalnya, banyak solusi individu dibuat secara acak untuk membentuk populasi awal. Ukuran populasi bergantung pada sifat masalah, tetapi biasanya berisi ratusan atau ribuan solusi yang mungkin. Secara tradisional, populasi dihasilkan secara acak, mencakup seluruh rentang solusi yang mungkin (ruang pencarian). Kadang-kadang, solusi dapat disebarluaskan di area di mana solusi optimal mungkin ditemukan.

Ukuran populasi menunjukkan berapa banyak kromosom dalam populasi (dalam satu generasi). Jika terdapat terlalu sedikit kromosom, GA memiliki sedikit kemungkinan untuk melakukan persilangan dan hanya sebagian kecil dari ruang pencarian yang dieksplorasi. Sebaliknya, jika terlalu banyak kromosom, GA melambat. Penelitian menunjukkan bahwa setelah beberapa batasan (yang terutama bergantung pada pengkodean dan masalah), tidak berguna untuk meningkatkan ukuran populasi, karena tidak membuat penyelesaian masalah lebih cepat.

Selection. Seleksi adalah tahap algoritma genetika di mana genom individu dipilih dari suatu populasi untuk berkembang biak nanti (rekombinasi atau persilangan). Ada banyak cara bagaimana cara memilih kromosom terbaik, cara yang paling terkenal adalah pemilihan roda roulette. Dalam pemilihan roda roulette, orang tua dipilih sesuai dengan kebugaran mereka. Semakin baik kromosomnya, semakin besar peluang mereka untuk dipilih. Bayangkan sebuah roda roulette yang menempatkan semua kromosom dalam populasi, masing-masing memiliki tempat yang besar sesuai dengan fungsi fitnessnya, seperti pada Gambar. 

Crossover. Dalam algoritma genetika, crossover adalah operator genetika yang digunakan untuk memvariasikan pemrograman suatu kromosom atau kromosom dari satu generasi ke generasi berikutnya. Hal ini sejalan dengan reproduksi dan persilangan biologis, yang menjadi dasar algoritma genetik. Ada banyak cara untuk melakukan crossover. Crossover memilih gen dari kromosom induk dan menciptakan keturunan baru. Cara termudah untuk melakukan ini adalah dengan memilih secara acak beberapa titik silang dan semua yang sebelum titik titik ini menyalin dari induk pertama dan kemudian semuanya setelah salinan titik silang dari induk kedua. Crossover kemudian dapat terlihat seperti Tabel

Mutation. Dalam algoritma komputasi genetika, mutasi adalah operator genetika yang digunakan untuk menjaga keragaman genetik dari satu generasi populasi kromosom algoritma ke generasi berikutnya. Ini analog dengan mutasi biologis. Contoh klasik dari operator mutasi melibatkan probabilitas bahwa bit sembarang dalam urutan genetik akan berubah dari keadaan aslinya.

Setelah persilangan dilakukan, mutasi terjadi. Ini untuk mencegah jatuhnya semua solusi dalam populasi ke dalam solusi optimal lokal masalah. Mutasi mengubah keturunan baru secara acak. Untuk pengkodean biner kita dapat mengganti beberapa bit yang dipilih secara acak dari 1 ke 0 atau dari 0 ke 1. Bit inversi - bit yang dipilih dibalik. Mutasi kemudian bisa menjadi berikut: 

Terminating. Proses GAs diulangi sampai kondisi penghentian tercapai. Kondisi penghentian yang umum adalah : 

- Solusi ditemukan yang memenuhi kriteria minimum, jumlah generasi tetap tercapai
- Anggaran yang dialokasikan (waktu/uang komputasi) tercapai.
- Kesesuaian solusi peringkat tertinggi sedang mencapai atau telah mencapai dataran tinggi sehingga pengulangan yang beruntun tidak lagi memberikan hasil yang baik
- Pemeriksaan manual
- Kombinasi di atas.

Studi Kasus Implementasi Genetic Algorithm

Penerapan GA untuk penyelesaian masalah Vehicle Routing di PT.MIF

Transportasi merupakan komponen yang vital dalam manajemen logistik suatu perusahaan. Pengurangan biaya transportasi dapat dilakukan dengan menentukan rute pengiriman yang efisien.Penulisan penelitian ini bertujuan untuk menghasilkan suatu rute pengiriman yang memiliki total jarak tempuh terpendek Vehicle Routing Problem with Time Windows (VRPTW) merupakan permasalahan membentuk sekumpulan rute yang optimal dengan menggunakan model matematis berdasarkan pertimbangan jarak dan waktu.untuk dapat memperoleh solusi dari permasalahan ini digunakan algoritma genetik (GA), Genetic Algorithm dipilih karena Genetic Algorithm tidak mempunyai kriteria khusus yang dijumpai pada algoritma heuristik lainnya, maka waktu komputasi juga relatif lebih singkat, serta dapat menghasilkan beberapa alternatif solusi yang mempunyai nilai obyektif yang sama. 

Karena GA bersifat iteratif dan jadwal pengiriman di PT MIF berubah-ubah, maka perlu dibuat suatu program khusus untuk menyelesaikan tiap iterasi dan tiap perubahan customer dan jadwal di PT MIF. Dari hasil penelitian diperoleh rute untuk kendaraan 1 adalah dari depo menuju customer 6, customer 1, customer 18, customer 7 kemudian kembali ke depo, dengan total jarak tempuh 140km, sedangkan rute kendaraan 2 dari depo menuju customer 8 kemudian kembali lagi ke depo dengan total jarak 17,9 km. Persentase penghematan yang dapat diperoleh apabila rute hasil perhitungan metode optimasi ini diterapkan pada perusahaan adalah sebesar 7,88 %.

Sumber : https://media.neliti.com/media/publications/231929-penerapan-algoritma-genetik-untuk-penyel-0d2aca31.pdf

Penerapan Algotitma Genetika Traveling Salesman Problem with Time Window: Studi kasus Rute Antar Jemput Laundry

Optimasi pemilihan rute merupakan masalah yang banyak dibahas pada penelitian ilmu komputer. Antar jemput laundry dengan pelanggan yang memiliki waktu khusus untuk menerima barang adalah salah satu contoh kasus pemilihan rute. Penghitungan rute tercepat memegang peranan penting karena harus tepat waktu dan semua pelanggan dapat dilayani. Berbeda dengan traveling salesman problem (TSP) konvensional yang bertujuan untuk meminimalkan jarak, kasus ini juga harus dipertimbangkan waktu ketersediaan setiap pelanggan. 

Pencarian solusi untuk permasalahannya adalah dengan mengkombinasikan solusi-solusi (kromosom) untuk menghasilkan solusi baru dengan menggunakan operator genetika (seleksi, crossover dan mutasi). Untuk mencari solusi terbaik digunakan beberapa kombinasi probabilitas crossover dan mutasi serta ukuran populasi dan ukuran generasi. Dari hasil pengujian kombinasi probabilitas crossover yang terbaik adalah 0,4 dan mutasi adalah 0,6 sedangkan untuk ukuran generasi optimal adalah 2000. Dari nilai-nilai parameter ini didapatkan solusi yang memungkinkan untuk melayani semua pelanggan dengan time window masing - masing.

Sumber : https://ojs.uajy.ac.id/index.php/jbi/article/view/407

Penerapan Algoritma Genetika untuk Optimasi Penjadwalan Tebangan Hutan

Penjadwalan Cuts Away Forest merupakan salah satu kendala yang dihadapi kawasan kehutanan. Semua masalah penting dalam menyelesaikan masalah ini adalah untuk menentukan pemeriksaan hutan yang akan ditebang dengan suatu tujuan untuk memaksimalkan volume kayu hasil di setiap periode pemotongan dan tetap mempertahankan konsep hutan yang lestari. 

Metode yang telah dikembangkan untuk menyelesaikan masalah ini dengan menerapkan linier program dengan metode simpleks. Pada metode ini setiap langkah diambil Berdasarkan rumus yang tepat dinilai tidak memuaskan baik untuk diselesaikan masalah ini. Algoritma genetika merupakan salah satu alternatif solusi masalah penjadwalan memotong hutan ini. 

Ide ini Algoritma berasal dari Teori Evolusi Charles Darwin, yang hanya merupakan rute terbaik yang dipilih. Seorang individu dipilih dari populasi induk dan kemudian digabungkan kembali menjadi individu lain yang telah dipilih dari orang tua lain populasi untuk membuat individu baru. Individu baru ini diharapkan menjadi lebih baik dari seluruh individu dalam populasi. Dengan metode ini, algoritma genetika ternyata mampu menawarkan Penjadwalan Terbaik Menghilangkan Masalah Hutan.

Sumber : https://media.neliti.com/media/publications/93030-ID-penerapan-algoritma-genetika-untuk-optim.pdf