My First National Computational Intelligence Contest
Murtad sebentar dari dunia Competitive Programming untuk mencoba hal baru
Sebuah Intro
Bismillah.
Hihi, pertama kalinya saya diberi kesempatan untuk menulis di Medium. Mengingat tepat sepekan lalu sebelum post ini di-release, saya mengikuti kompetisi Computational Intelligence di Universitas Kristen Satya Wacana (UKSW), Salatiga. Saya ingin mendokumentasikan kegiatan tersebut mengingat konsep kompetisi tersebut sangat unique di Indonesia (tidak dibilang di Dunia soalnya ada kompetisi serupa di Kaggle).
Computational Intelligence (CI) yang diselenggarakan oleh UKSW ini mengusung konsep kompetisi menyelesaikan permasalah Travelling Salesman Problem (TSP) (maaf, saya british). Kompetisi ini terdiri dari dua babak yaitu babak penyisihan dan babak final. Babak penyisihan dari kontes ini adalah membuat sebuah proposal mengenai solusi permasalahan yang diusulkan dalam menyelesaikan sebuah dataset yang diberikan juri dan tentunya masalah mengenai mencari rute terpendek. Solusi di sini mencakup algoritma yang digunakan dalam menyelesaikan masalah tersebut beserta tools-tools (kakas-kakas) lainnya yang ingin digunakan. Tidak hanya itu, kita juga perlu mengumpulkan jawaban rute tersebut (misal: A C D E F) untuk meyakinkan juri bahwa memang solusi kita sudah berjalan dengan tepat. Seperti Competitive Programming (CP)? Hmm, ini semua jawaban bisa mendapatkan verdict Accepted (AC), tapi untuk penilaian berdasarkan cost-nya yang seminimal mungkin jadinya bukan absolute AC dengan nilai biner 1 atau 0. Ya kesimpulannya bukan CP. Untuk babak final sendiri kita diberikan waktu 12 jam untuk mengimplementasikan solusi kita dengan dataset baru lalu mempresentasikan hasil eksperimen kita pada hari berikutnya.
Hajimemashite
Oh ya saya belum perkenalan tim. Ketua tim dari kontes ini sebenarnya bukan saya karena saya belum banyak ilmu aproksimasi solusi TSP (cuma tau Held-Karp Algorithm doang :(), melainkan Gilang. Tim kami beranggotakan 2 orang, yang pertama Gilang Ardyamandala Al Assyifa (Gilang Ardya) dan yang kedua saya sendiri Jehian Norman Saviero (Jehian Norman Saviero). Nama tim kami awalnya adalah Traveling Sadikin Problem. Dikarenakan ketua tim tidak menyetujui nama itu dipakai di luar Kaggle, jadi kami berganti nama tim menjadi Nyan-Path Problem (NP Problem). Tidak ada alasan khusus untuk pemberian nama tim kecuali untuk membuat tampak lucu dan menggemaskan ❤. (Kalau Traveling Sadikin Problem sih karena emang kami berdua suka ke Sadikin, Hehe)
Is it Prepared?
Kami berangkat ke kompetisi ini tidak modal nekat doang sejatinya. Ada persiapan? Of course! Bagaimana kami mempersiapkan sebelumnya? Tentu dengan mengikuti kontes serupa pada Kaggle. Sistem kontes pun sama dengan yang diselenggarakan UKSW, yang membedakan hanya durasi lombanya. Berikut hasil akhir dari perjuangan kami selama 2 bulan (Soalnya ada deadline TA 1 dan hari terakhir lomba itu saya sidang TA 1 :”))
Babak Penyisihan
Dengan adanya kompetisi dari Kaggle yang dipaparkan sebelumnya serta hasil yang cukup memuaskan, kami memutuskan untuk mengikuti kompetisi CI UKSW. Tahap proposal berjalan cukup lancar karena di-carry Gilang Ardya (maaf kawan-kawan, saya lagi magang di Tokopedia jadi tidak bisa fulltime di kompetisi). Alhamdulillah, pengumuman kami dinyatakan lolos ke babak final! (Hehe, kalau ditanya deadliner apa nggak proposalnya, jelas iya, hehe)
Babak Final
Karena sudah memutuskan untuk berangkat ke final apabila lolos demi kabur dari Tugas Akhir, ya akhirnya kami merencanakan perjalanan dan penginapan di sana nanti. (timeskip jeng-jeng langsung akhirnya tiba di final)
Untuk babak final sendiri dilaksanakan selama 3 hari. Secara sederhana, rangkaian babak final dilaksanakan sebagai berikut:
- Senin, 18 Maret 2019. Peserta babak final melakukan technical meeting guna memperjelas hal yang belum dimengerti oleh peserta mulai dari batasan solusi, waktu pengerjaaan, hal yang boleh dilakukan dan tidak boleh dilakukan, makan siang, makan malam dan snack, hingga break sholat yang disediakan.
- Selasa, 19 Maret 2019. Peserta babak final melakukan implementasi solusi selama 12 jam + 1 jam istirahat (30 menit makan malam + sholat dzuhur dan 30 menit makan malam + sholat maghrib). Selama jam istirahat peserta tidak diperbolehkan melanjutkan pekerjaannya untuk menjunjung keadilan (Keren coy konsepnya. Asli mereka kepikiran ada break kayak gini demi menghormati umat Islam ❤). Untuk CI, peserta tidak diperbolehkan mengakses internet selama pengerjaan. Karena final cuma 6 tim, pengawasan serasa ketat. Jadi, jangan coba-coba.
- Rabu, 20 Maret 2019. Peserta babak final mempresentasikan hasil kerjanya kepada juri berikut tahapan solusi final dan hasil akhir rute beserta cost-nya. Sesi presentasi sendiri terdiri dari 15 menit presentasi dan tanya jawab selama kurang lebih 10 menit.
Layout Solusi Babak Final (versi NP Problem)
Eits, udah kebelet sama hasil finalnya aja. Udah di-spoiler juga kan juara berapa. Ya di sini kami yang diwakilkan oleh saya akan berbagi gambaran kasar solusi yang kami ajukan pada kontes CI kali ini. Secara umum solusi kami terbagi menjadi tiga tahap besar yaitu:
- Initalizing Tour menggunakan Greedy Nearest Neighbour
- Approximation menggunakan Lin-Kernighan Algorithm
- Improving menggunakan Held-Karp Algorithm (DP Bitmask) + Sliding Window
Kita kupas satu persatu isi dari algoritma-algoritma tersebut.
Initializing Tour (Greedy Nearest Neighbour)
Ide yang kami gunakan untuk melakukan inisialisasi tour adalah Greedy Nearest Neighbour. Konsepnya sendiri apabila dijabarkan sebagai berikut:
- Asumsikan titik pertama suatu tour adalah x_1, cari titik terdekat dari x_1.
- Apabila banyak titik yang ditemukan, bebas menggunakan yang mana saja.
- Pilih titik terdekat tersebut lalu ulangi langkah pertama dengan membuang titik x_1 dan menggunakan titik acuan titik terdekat yang didapatkan dari langkah sebelumnya untuk mendapatkan titik berikutnya hingga semua titik sudah digunakan.
Berikut pseudocode dari Greedy Nearest Neighbour yang kami gunakan
initial_point ← Set of Point
result ← {} ∪ (initial_point)_1
initial_point ← initial_point - (initial_point)_1
last ← 1while SIZE(initial_point) > 0
MIN ← INT_MAX
next ← {}
for each point in initial_point
if dist(point, (result)_last) < MIN
MIN ← dist(point, (result)_last)
next ← point
result ← result ∪ next
last ← last + 1
initial_point ← initial_point – result
output(result)
Approximation (Lin-Kernighan Algorithm)
Lin-Kernighan merupakan salah satu researcher dalam permasalahan TSP yang dimana karyanya cukup terkenal dalam menyelesaikan permasalahan TSP secara umum. Insight dari algoritma mereka dapat mendekati nilai optimal (bahkan optimal) dalam menyelesikan masalah TSP secara umum. Berikut dijabarkan aproksimasi algoritma LINK:
- Diberikan sebuah set X, ambil dua buah subset sembarang pada X yang saling lepas dan ukurannya sama (misal x_1 dan x_2).
- Cari pasangan x_1j dan x_2k dimana apabila kedua titik tersebut ditukar, perubahan distance-nya semaksimum mungkin.
- Buang pasangan tersebut dari tiap-tiap subset lalu simpan pasangan tersebut beserta perubahan distance-nya. Lalu ulangi langkah kedua hingga semua isi subset-nya kosong.
- Cari nilai k sehingga total perubahan distance setiap pasangan dari 1 hingga k semaksimum mungkin.
- Jika total perubahan distance maksimumnya lebih dari 0, lakukan penukaran berdasarkan pasangan tersebut (dari 1 hingga k). Lanjutkan kembali ke tahap 2 hingga total perubahan distance maksimumnya tidak lebih dari 0.
Berikut pseudocode dari Lin-Kernighan Algorithm yang kami gunakan
/* ======================================== */
// Initializing subset of X into x_1 and x_2
/* ======================================== */
initial_point ← Set of current point
X ← copy of initial_point
i ← 1
x_1 ← {}
x_2 ← {}
for each point in X
if 2 * i ≤ SIZE(X)
x_1 ← x_1 ∪ point
else
x_2 ← x_2 ∪ point
i ← i + 1/* ======================================== */
// Get Candidate of Swapping
/* ======================================== */
CandidateSwapping:
candidate_swapping ← {}
while SIZE(x_1) > 0 and SIZE(x_2) > 0
GainMax = INT_MIN
a ← {}
b ← {}
for each p_1 in x_1
for each p_2 in x_2
if evaluate(p_1, p_2) > GainMax
GainMax = evaluate(p_1, p_2)
a ← p_1
b ← p_2
candidate_swapping ← candidate_swapping ∪ {{a, b}, GainMax}
x_1 ← x_1 - a
x_2 ← x_2 - b/* ======================================== */
// Get Maximum Total Gain
/* ======================================== */
j ← 1
j_max ← 0
current_total ← 0
total_maximum ← INT_MIN
for each data in candidate_swapping
current_total ← current_total + GainMax(data)
if current_total > total_maximum
total_maximum ← current_total
j_max ← j
j ← j + 1/* ======================================== */
// Swap the candidate
/* ======================================== */if total_maximum > 0
i ← 1
while i ≤ j_max
pos_a ← GetPos(GetA((candidate_swapping)_i), X)
pos_b ← GetPos(GetB((candidate_swapping)_i), X)
Swap((X)_pos_a, (X)_pos_b)
i ← i + 1
goto CandidateSwapping
Improving (DP Bitmask + Sliding Window)
Karena algoritma LINK yang dipaparkan sebelumnya adalah aproksimasi, maka diperlukan algoritma eksak yang dapat meningkatkan hasilnya. Algoritma eksak well known untuk menyelesaikan masalah TSP tercepat hingga saat ini adalah algoritma DP Bitmask (a.k.a. Held-Karp Algorithm). Mengingat kompleksitas DP Bitmask adalah O(N²×2^N), maka kami melakukan pengembangan rute dengan melakukan DP Bitmask + sliding window hanya pada kota yang masuk dalam sliding window.
DP Bitmask
- Untuk state yang disimpan pada DP kali ini dalam bentuk dp[current_city][visited_city] yang menyimpan jarak rute terpendek untuk mencapai kota current_city setelah melewati semua kota visited_city.
- visited_city sendiri direpresentasikan dalam bentuk bit, dimana bit ke-i merupakan kota ke-i dan nilai bit bisa 1 berarti sudah dikunjungi dan 0 apabila belum dikunjungi.
- Jangan lupa menyimpan node untuk keperluan backtracking
Berikut pseudocode dari Held-Karp Algorithm yang kami gunakan
// Held-Karp Algorithmdp(curr, visited)
if visited = ALL
→ {dist_(curr,last), -1}
res ← 0
if visited = ZERO
res ← dist_(first,curr)
tot ← {INT_MAX, -1}
for each next in not visited bit
val ← dp(next, visited ∪ next)
if FIRST(tot) > FIRST(val) + dist_(curr,next)
tot ← {FIRST(val) + dist_(curr,next), next}
→ {FIRST(tot) + res, SECOND(tot)}
Sliding Window
- Karena tidak memungkinkan untuk melakukan DP Bitmask untuk ukuran N>20, maka melakukan rekonstruksi ulang untuk pengembangan menggunakan sliding window.
- Mudahnya, kita akan merekonstruksi solusi terbaik pada path X_i, X_(i+1), X_(i+2), … , X_(i+window_size-1) dengan menggunaan DP Bitmask. Lalu dari posisi terakhir i dilanjut dengan i+window_size, dan seterusnya hingga nilai i>N.
Berikut pseudocode dari Sliding Window yang kami gunakan
// Sliding Windowi ← 1
window_size ← kwhile i ≤ N
j ← i
data_in_window ← {}
count ← 0
while j ≤ N and count < window_size
data_in_window ← data_in_window ∪ X_i
j ← j + 1
count ← count + 1
SET(data_dp_bitmask, data_in_window)
result ← BackTrack(dp(i,0))
for each node in result
X_i ← node
i ← i + 1
Hasil Akhir Kompetisi
Setelah melewati sesi live coding 12 jam dan sesi presentasi, hal yang paling ditunggu-tunggu adalah pengumuman! Kami masih sedikit canggung dan khawatir dengan peserta lain mengingat algoritma TSP General yang sudah baik dalam aproksimaksi sejauh ini adalah LINK dan kami merasa algoritma itu sudah well known sehingga kami hanya berkompetisi dalam ide improving saja. Ya, saya sendiri masih meyakinkan ketua tim saya bahwa “we already do our best.” disaat ketua tim saya merasa sangat khawatir (diem mulu kayak kebelet buang air besar). Sebenernya ini part yang agak sedih sih. Soalnya saya harus pulang ke Bandung pukul 4 sore flight dari Bandara Jenderal Ahmad Yani, Semarang karena mau nampil KPA ❤. Karena pengumuman diestimasi akan sekitar pukul 3, jadi saya pamit pulang terlebih dahulu jam 1 siang mengingat Salatiga — Semarang bisa 2 jam. Ya ketua tim saya sedih gitu karena deg-degannya sendirian (ya saya juga deg-degan, tapi lebih deg-degan ketinggalan pesawat). Tiba di Bandara saya check-in terlebih dahulu dan mendapati pesawatnya delay 1,5 jam (WTF!). Kesal? Jelas! Gak bisa nampil KPA, gak bisa nonton pengumuman, gak bisa ngapa-ngapain, campur aduk dah di Bandara.
Tiba-tiba LO saya melakukan panggilan video call live report pengumuman pemenang. Yang awalnya kacau balau, jadi semangat dan antusias. Urutan ketiga, nama tim kami tidak disebut. Tiba di urutan kedua, nama tim kami belum kunjung disebut. Lalu di urutan pertama… nama tim kami tidak disebut… Sedih… Ternyata cabang lomba Apps Competition WKWKWKWK. Minta dijitak emang LO saya. Saya ngakak sejadi-jadinya. Akhirnya tiba pengumuman cabang CI. Baru saja ketawa lepas, sekarang hening kembali. Dari urutan ketiga, nama tim kami tidak disebut. Lalu tiba di urutan kedua, nama tim kami tidak disebut juga. Lalu, pengumuman juara pertama. Deg-degannya cukup hebat.
“Juara pertama, tim Nyan-Path Problem, dari Institut Teknologi Bandung!”
Waah saya setengah teriak di Bandara (Alhamdulillah masih sadar tempat). Alhamdulillah pulang tidak dengan tangan hampa. Tidak sia-sia perjuangan kabur dari TA sejenak yang akhirnya membawa kami meraih penghargaan tersebut.
Penutup
Maaf anti klimaks penutupnya. Ya inti dari tulisan kali ini sedikit memberi sharing experience lomba Computational Intelligence beserta persiapan kami dalam mengikuti event tersebut. Konsep lomba barunya cukup bagus. Mungkin panitianya cukup safe play dengan membuat lomba TSP-nya TSP General karena takut lombanya menjadi cukup sulit apabila dimodifikasi dengan memberikan konstrain lain. Saya berterima kasih kepada rekan saya sekaligus ketua tim saya yang telah mentraktir saya Sadikin beberapa hari lalu sebelum post ini terbit. Saya sangat menyarankan untuk teman-teman lain untuk mengikuti event ini ke depannya karena event-nya cukup worth it! Mungkin sekian edisi medium saya kali ini. Akhir kata, bila banyak pemilihan kata yang salah saya mohon maaf!
Wassalaam
