Knapsack Problem dengan Algoritma Genetika
1. KNAPSACK PROBLEM
Knapsack Problem merupakan suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang mempunyai weight dan profit masing-masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.
Knapsack problem merupakan salah satu dari persoalan klasik yang banyak ditemukan dalam literatur-literatur lama dan hingga kini permasalahn tersebut masih sering ditemukan dalam kehidupan sehari-hari. Contoh nyata dari Knapsack Problem ini misalnya, jika ada seorang pedagang barang kebutuhan rumah tangga yang berkeliling menggunakan gerobak. Tentu saja gerobaknya memiliki kapasitas maksimum, sehingga ia tidak bisa memasukkan semua barang dagangannya dengan seenak hatinya. Pedagang tersebut harus memilih barang-barang mana saja yang harus ia angkut, dengan pertimbangan berat dari barang yang dibawanya tidak melebihi kapasitas maksimum gerobak dan memaksimalkan profit dari barang-barang yang ia bawa.
Banyak algoritma yang dapat digunakan untuk menyelesaikan Knapsack Problem ini, misalnya Algoritma Brute Force, Branch and Bound, Greedy, dana lain-lain. Untuk tugas AI kali ini, kami akan mencoba menyelesaikan Knapsack Problem dengan menggunakan Algoritma Genetika.
2. ALGORITMA GENETIKA
Algoritma genetika adalah algoritma komputasi yang diinspirasi oleh teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang alamiah. Algoritma ini dikembangkan oleh Goldberg yang terinspirasi dari teori evolusi Darwin yang menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi oleh aturan “yang kuat adalah yang menang”. Darwin juga mengatakan bahwa kelangsungan hidup suatu makhluk dapat dipertahankan melalui proses reduksi, crossover, dan mutasi.
Sebuah solusi yang dibangkitkan dalan Algoritma Genetika disebut sebagai kromosom, sedangkan kumpulan kromosom-kromosom tersebut disebut sebagai populasi. Sebuah kromosom dibentuk dari komponen-komponen penyusun yang disebuat sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol atau pun karakter tergantung dari permasalahan yang ingin diselesaikan. Kromosom-kromosom tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi, kromosom-kromosom tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan (fungsi_objektif) menggunakan ukuran yang disebut fitness.
Untuk memilih kromosom yang tetap dipertahankan untuk generasi selanjutnya, dilakukanlah proses seleksi. Kromosom dengan nilai fitness tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya.
Offspring merupakan kromosom-kromosom baru yang dibentuk dengan cara melakukan perkawinan antar kromosom dalam satu generasi, atau sering disebut sebagai proses crossover. Jumlah kromosom yang mengalami crossover ditentukan oleh parameter Pcrossover. Mekanisme perubahan susunan unsur penyusun makhluk hidup akibat adanya faktor alam disebut dengan mutasi. Jadi, mutasi direpresentasikan sebagai suatu proses berubahnya satu atau leih nilai gen dalam kromosom dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter Pmutasi. Setelah beberapa generasi akan dihasilkan kromosom-kromosom yang nilai gennya konvergen ke suatu nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh Algoritma Genetika terhadap permasalahan yang ingin diselesaikan.
Recent Comments