Cross Entropy

Metode Cross Entropy termasuk teknik yang cukup baru. Awalnya diterapkan untuk simulasi kejadian langka (rare event). Lalu dikembangkan untuk beberapa kasus seperti optimasi kombinatorial, optimasi kontinyu, machine learning dan beberapa kelas masalah lain. Metoda CE termasuk dalam keluarga teknik Monte Carlo yang bisa digunakan untuk menyelesaikan kasus estimasi maupun optimasi. Dalam hal estimasi, CE memberikan cara yang adaptif untuk menemukan distribusi sampling yang optimal untuk beberapa problem yang cukup luas cakupannya. Jika masalah optimasi bisa kita formulasikan sebagai masalah estimasi maka metoda CE menjadi sangat handal dan berlaku umum sebagai algoritma search stokhastik. Pada bab ini, prinsip-prinsip metode Cross Entropy (CE) akan dijelaskan berdasarkan pada [Boer et al., 2005, Rubinstein and Kroese., 2004].

Metode CE awalnya digunakan sebagai alat untuk mengestimasi probabilitas dari kejadian langka (rare event) dengan penerapan algoritma adaptive untuk pada peristiwa stokhastik yang kompleks [Rubinstein, 1997], dengan cara meminimasi variansi (variance minimization). Pada perkembangan selanjutnya, ditemukan bahwa modifikasi sederhana terhadap metoda CE dapat digunakan tidak hanya untuk mengestimasi probabilitas kejadian langka, tetapi juga untuk menyelesaikan permasalahan optimasi kombinatorial yang kompleks dengan cara meminimasi cross entropy. Hal ini dilakukan dengan menerjemahkan masalah optimasi deterministic menjadi stokhastik, kemudian menggunakan teknik rare event simulation seperti dijelaskan pada [Rubinstein, 1997].

Metoda CE melibatkan prosedur iterasi, dimana tiap iterasi dapat dipecah menjadi dua fase:

1. Melakukan pembangkitan sampel random(x) dengan menggunakan mekanisme atau distribusi tertentu. 
2. Memperbaharui parameter (ν) dari mekanisme random berdasarkan data sampel elite untuk menghasilkan sampel yang lebih baik pada iterasi berikutnya.

Sampel elite adalah berapa persen dari sampel yang kita pilih untuk memperbaiki atau mengupdate parameter ν yang digunakan. Proses tersebut secara matematis dapat ditulis sebagai berikut [Rubinstein and Kroese.,2004]:

1. Tentukan nilai N, yaitu banyaknya sampel, ν0, ρ dan α. 
2. Bangkitkan sampel sebanyak N dengan mekanisme tertentu, memanfaatkan parameter ν0.
3.  Evaluasi sampel ini dengan memasukkan ke dalam fungsi tujuan. Lalu urutkan nilai fungsi tujuan. Ini dilakukan dengan cara memasukan nilai x yang dibangkitkan ke dalam fungsi tujuan f(x). Jika ada N sampel maka didapatkan sebanyak N nilai f. Lalu kita urutkan nilai f ini dari yang terbesar ke yang terkecil (untuk kasus maksimasi lakukan sebaliknya). Pilih 1 − ρ persentil dari N sampel x yang menghasilkan nilai f terkecil. Ini bisa dijelaskan, misalnya N =10,ρ =0.1, maka 1 − 0.1=0.9 persentil dari 10 sampel adalah titik sampel ke 9 dan ke 10 setelah nilai f diurutkan. Kedua sampel ini yang disebut sampel elite. Ingat bahwa yang kita perlukan adalah nilai x-nya bukan nilai f-nya. Nilai f digunakan untuk mencari nilai x mana yang memberikan f terkecil. Sejumlah nilai x terbaik ini gunakan untuk mengupdate parameter ν. 
4. Memperbaharui γt secara adaptif. Untuk ν yang sudah diupdate, gunakan untuk membangkitkan nilai x yang baru. Kemudian masukkan ke dalam γt dan νt−1 yang telah ditetapkan.

Algoritma utama CE untuk optimasi

1. Tentukan parameter awal ν = u, α,dan ρ.Tetapkaniterasi it =1. 
2. Bangkitkan sampel random X1,,XN dari fungsi probabilitas distribusi tertentu f(−; u) dan pilih sampel (1−ρ) quantile dari performansi setelah diurutkan. 
3. Gunakan sampel yang sama untuk memperbarui nilai parameter 
4. Aplikasikan persamaan 7.2 untuk memuluskan vektor ν = u.Kembali ke langkah 2 dengan nilai parameter yang baru, tetapkan it = it +1. 
5. Jika stopping criteria sudah dipenuhi, berhenti.

Perlu dicatat bahwa stopping criteria, vektor solusi awal, ukuran sampel N dan nilai ρ harus dinyatakan secara spesifik dari awal iterasi. Parameter ν di-update hanya berdasarkan sejumlah (1 − ρ) sampel terbaik. Sampel yang digunakan untuk mengupdate parameter ini dinamakan sampel elite.