Kamis, 21 Maret 2013

Mengoptimalkan Quality Points melalui GA di R

Setelah beberapa hari yang lalu saya telah memberikan posting-an mengenai studi kasus yang akan diselesaikan menggunakan Genetic Algorithm (GA) melalui program R, maka pada postingan kali ini saya mencoba untuk mempublikasikan apa yang dilakukan untuk mengoptimalkan Quality Points dengan keterbatasan waktu yang ada untuk melakukan penyiaran dengan beberapa program on air yang ada. 


untuk menyelesaikan Knapsack Problem ini menggunakan program R, library yang saya gunakan yaitu (genalg). Untuk dapat menggunakan library ini tentunya dengan cara melakukan instalasi pada packages tersebut.
setelah proses instalasi selesai, maka library langsung dapat dideklarasikan pada baris program di R sebelum memasukkan kasusnya. dengan perintah:

library(genalg)

selanjutnya yaitu memasukkan informasi mengenai data yang ingin kita temukan hasil optimalnya. Sesuai dengan data yang telah saya posting pada posting-an sebelumnya. Masukkan perintah di bawah ini setelah memilih library yang digunakan:

dataset <- data.frame(Program = c("Salam Sahabat", "Keliling Hari", "Smile of The Day", "Kurcaci",
+ "Kunci Hidup", "Style Zone", "Retro Mania", "Around You", "Kereta ku", "Your Time",
+ "Got Your Life", "Take your Problem"), Qualitypoints = c(30, 20, 40, 25, 10, 50, 15, 30, 20, 35, 35,
+ 30), Duration = c(150, 60, 30, 120, 60, 120, 15, 45, 90, 150, 90, 120))
> Durationlimit <- 840


seperti yang telah saya jelaskan sebelumnya, pada kasus ini ingin ditentukan program apa saja yang akan disiarkan dengan jumlah jam pernyiaran yaitu 14 jam (840) menit. Tentunya hasil yang diinginkan dengan menemukan Quality Points yang tertinggi.

sebelum menemukan hasil optimal menggunakan GA, misalkan kita menentukan chromosome untuk program yang akan disiarkan yaitu:
1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1 
maka, masukkan perintah seperti di bawah ini:

 chromosome = c(1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1)
> dataset[chromose == 1, ]


maka akan terlihat program yang akan disiarkan yaitu Salam Sahabat, Keliling Hari, Smile of the Day, Kurcaci, Retro Mania, Around You, Kereta ku, Got Your Life, dan Take your Problem.
kemudian untuk melihat Quality Points yang didapat dari program pilihan kita itu dengan perintah:

cat(chromosome %*% dataset$Qualitypoints)

maka akan terlihat: 245> 
Quality points yang didapat yaitu 245.

selanjutnya yaitu menggunakan GA melalui library yang telah digunakan, yaitu untuk melihat hasil terbaik dari algoritma yang ada, dengan mengetikkan perintah:

> evalFunc <- function(x) {
+ current_solution_Qualitypoints <- x %*% dataset$Qualitypoints
+ current_solution_Duration <- x %*% dataset$Duration
+ if (current_solution_Duration > Durationlimit)
+ return(0) else return (-current_solution_Qualitypoints)
+ }
> iter = 100
> GAmodel <- rbga.bin(size = 12, popSize = 200, iters = iter, mutationChance = 0.01,
+ elitism = T, evalFunc = evalFunc)
> cat(summary.rbga(GAmodel))


maka, akan terlihat hasil seperti di bawah ini:

GA Settings
  Type                  = binary chromosome
  Population size       = 200
  Number of Generations = 100
  Elitism               = TRUE
  Mutation Chance       = 0.01

Search Domain
  Var 1 = [,]
  Var 0 = [,]

GA Results
  Best Solution : 0 1 1 1 0 1 1 1 1 1 1 1 


dari hasil di atas terlihat bahwa Best Solution yang diberikan oleh GA menghasilkan chromosome 0 1 1 1 0 1 1 1 1 1 1 1.
Untuk meilihat program apa saja yang akan memberikan hasil maksimal jika disiarkan dari chromosome itu, masukkan perintah:


solution = c(0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1)
> dataset[solution == 1, ]


maka akan terlihat program yang seharusnya disiarkan dengan batasan waktu 840 menit yaitu Keliling Hari, Smile of The Day,
Kurcaci, Style Zone, Retro Mania, Around You, Kereta ku, Your Time, Got Your Life, dan Take Your Problem.
Durasi dari semua program tersebut sama dengan durasi waktu yang tersedia, yaitu 840 menit.
Kemudian, Quality points yang didapat dari GA yaitu 300.


Maka, hasil yang dikeluarkan oleh GA telah optimal dibandingkan dengan kemungkinan program acara yang dipilih sendiri. Terlihat juga dari Quality points dari GA yaitu 300. Sedangkan dihasil awal tanpa menggunakan GA, Quality points hanya 245. Solusi yang diberikan dari GA juga sesuai dengan batasan yan dimiliki, yakni durasi waktu penyiaran dalam sehari yaitu 840 menit.
 





 


 


Minggu, 17 Maret 2013

Solving the Knapsack Problem Using GA in R

Seperti postingan sebelumnya yang telah membahas tentang Knapsack Problem dan juga
Genetic Algirithm (GA), maka pada postingan kali ini langsung akan coba diterapkan dalam
sebuah kasus yang akan diselesaikan menggunakan "R"...

Nah, kasusnya kayak gini...
Sebagai pemula yang ingin membuat sebuah studio penyiaran, tentunya memiliki beberapa rencana program acara yang akan disiarkan  dalam jam penyiaran selama sehari.
Dalam sehari memiliki jam untuk on air selama 14 jam (840 menit). Dengan jadwal yang akan dimulai dari jam 6 Pagi hingga jam 1 Siang, kemudian akan off air selama 2 jam dan akan on air kembali dimulai dari jam 3 sore hingga jam 11 malam.


Tentunya dalam penyiaran ini memiliki beberapa jadwal acara yang berbeda-beda. Baik dari isi program acaranya dan juga durasi waktunya.
Bobot yang diberikan (Quality Points) dari program acara yang diberikan berdasarkan kelas pendengar dan isi program acaranya.


Maka batasan yang dimiliki disini yaitu jam penyiaran yang dimiliki.
Kemudian dengan informasi yang ada yaitu durasi dari setiap penyiarandan juga bobot nilainya.

Informasi berdasarkan gambar tabel berikut:









notes:
* ku rangkai cita dan cinta

Maka yang diharapkan dengan penyelesaian yang digunakan dalam R dapat mendapatkan hasil yang optimal, program acara apa yang diisi dengan batasan waktu tersebut.
           

Genetic Algorithm

Ketika diberikan masalah, genetic algorithm membentuk suatu kumpulan/populasi calon solusi. Genetic algorithm memandang calon solusi ini sebagai individu yang dapat berkembang biak menghasilkan keturunan. Dengan prinsip “orang tua yang bagus menghasilkan keturunan yang lebih bagus”, maka di setiap calon solusi ini diberikan suatu
fitness value/nilai kecocokan untuk menunjukkan seberapa baguskah calon solusi tersebut. Semakin tinggi nilai kecocokannya, semakin tinggi juga kemungkinannya untuk bertahan hidup dan menghasilkan keturunan (menggambarkan proses seleksi alam). Contohnya, pada Knapsack Problem nilai kecocokan dapat didefinisikan sebagai nilai dari barang-barang yang dimasukkan dalam tas.

Pada prakteknya, calon solusi ini biasa direpresentasikan sebagai string/untaian nilai
(menggambarkan kromosom yang terdiri dari untaian gen). Nilai ini dapat berupa angka, huruf, atau kata di mana tiap-tiap nilai ini berkorespondensi dengan variabel tertentu. Contohnya, pada masalah Travelling Salesman Problem calon solusi dapat digambarkan
sebagai untaian angka yang menunjukkan urutan kota yang dikunjungi, jadi individu [3 5 2 1 4] mempunyai arti kota pertama = kota 3, kota kedua = kota 5, dst.

Agar suatu masalah dapat diselesaikan dengan geneticalgorithm, perlu ditentukan hal-hal berikut:
1. representasi solusi dalam untaian nilai, apakah akan digunakan untaian bit atau angka dan apa makna dari tiap nilai tersebut,
2. fungsi untuk menghitung nilai kecocokan,berdasarkan apa kita menentukan suatu individu
itu bagus atau tidak,
3. parameter untuk mengontrol genetic algorithm, yaitu jumlah populasi, probabilitas persilangan, dan probabilitas mutasi,
4. kondisi berhenti, yaitu kapan solusi yang diperoleh dianggap cukup. 

Jumat, 15 Maret 2013

Missyubadly..

Tidak mungkin mengatakan bahwa sesuatu telah tercampakkan..!
Tidak mungkin merasakan kehampaan!!
Tidak mungkin merasa kesepian!

Tidak perlu mencari penghiburan.
Tidak perlu mencari dimana ada cela untuk tawa..
Tidak perlu menyanyikan hati...

karena untuk saat ini, cukup KENANGAN
yang membayar semuanya...
:')

Rindu keluarga... Rindu inguss.. Aco...


hmm..
tidak tahu kapan benih rindu ini ada,
yang jelas,,, rindu ini tidak akan pernah mati.


Terima kasih untuk kebersamaan yang sangat sederhana selama ini..
terima kasih atas tangisan, pukululan, jeritan, tawa, dan kebahagiaan
atas hidup yang telah diisi bersama.. :')


Tidak perlu orang lain yang mengatakan aku sudah bahagia atau belum,
yang penting apa yang aku rasakan.. Kebahagiaan atas kehidupan dalam
keluarga selama ini..

Biarpun aku menuliskan beribu, berjuta bait kata..
sungguh tak akan mampu menyiratkan apa yang ada dihati..

maafkan jika selama ini banyak kesalahan dan kekecawan
yang sering aku sajikan dalam kehidupan kalian..





semoga Allah swt senantiasa memberi kebahagiaan pada
hati kalian dan meridhai setiap kebaikan. aamiin..

My Fam's

Knapsack Problem

What is Knapsack Problem?? --Look at the picture! How to optimize something that you have?...
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.


Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? A multiple constrained problem could consider both the weight and volume of the boxes.
------

(Solution: if any number of each box is available, then three yellow boxes and three grey boxes; if only the shown boxes are available, then all but the green box.)


Computational Complexity
The knapsack problem is interesting from the perspective of computer science for many reasons:
  • The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no known algorithm both correct and fast (polynomial-time) on all cases.
  • While the decision problem is NP-complete the optimization problem is NP-hard, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger, thus solving the decision problem NP-complete).
  • There is a pseudo-polynomial time algorithm using dynamic programming.
  • There is a fully polynomial-time approximation scheme, which uses the pseudo-polynomial time algorithm as a subroutine, described below.
  • Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly.
There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k . On the other hand, if an algorithm finds the optimal value of optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k . Thus, both versions of the problem are of similar difficulty.