Teknik Optimisasi Modern Yang Menyerupai Perilaku Alam

Lintang Erlangga - May 24th, 2021

Selama ini kalau kita mencari nilai yang optimal dari suatu fungsi, biasanya digunakan turunan dari fungsi yang dimaksud. Namun ada beberapa kekurangan apabila menggunakan teknik tersebut. Mengingat bisa saja suatu fungsi ada interval yang kontinyu, atau bisa juga fungsi yang dimaksud diskrit.

Ada beberapa metode optimisasi modern yang mana dalam pencarian nilai optimalnya tidak memerlukan turunan. Metode-metode tersebut umumnya meniru beberapa perilaku yang ada di alam ini. Salah satunya adalah algoritma genetik, yang prosesnya serupa dengan seleksi alam.

Daftar Isi

Algoritma Genetik
- Design Variable
- Fungsi Objektif dan Batasan
Operator Genetik

Algoritma Genetik

Terdapat tiga proses utama dalam algoritma ini, yaitu reproduksi, kawin silang, dan mutasi. Sesuai namanya, metode ini mengadopsi perilaku bagaimana prinsip genetika bekerja. Nanti akan kita bahas ketiganya, tapi di sini saya coba memaparkan apa saja yang perlu disesuaikan atau diubah terlebih dahulu untuk menggunakan algoritma ini.

Design Variable

Dalam penyelesaiannya, algoritma genetik memanfaatkan representasi biner sebagai design variable nya. Gampangannya design variable ini merupakan nilai yang diubah-ubah selama proses pencarian hasil optimalnya. Nanti ketika design variable memberikan hasil yang optimal (bisa maksimum/minimum), maka kemungkinan besar design variable tersebut adalah nilai masukkan (input) yang dicari.

Sebagai contoh, misal angka 10 pengen kita tuliskan dengan biner, maka representasinya yaitu 1 0 1 0 = 2³(1) + 2²(0) + 2¹(1) + 2⁰(0). Contoh lainnya angka 29, representasi binernya yaitu 1 1 1 0 1 = 2⁴(1) + 2³(1) + 2²(1) + 2¹(0) + 2⁰(1). Secara umum bisa dituliskan secara matematis sebagai berikut

$\Sigma_k 2^kb_k$ .

Gimana kasusnya kalau nilai yang ingin dilibatkan berupa bilangan desimal? Nah kalau kasusnya kaya gini, setidaknya kita perlu batasan nilainya. Yaitu berupa, berapa nilai minimal dan maksimal yang mungkin diterima oleh fungsi objektif (yang ingin dicari optimalnya). Misal sebut saja $x_l$ sebagai nilai minimalnya, dan $x_u$ untuk maksimalnya.

Nilai desimal tersebut dituliskan secara matematis sebagai berikut

$x_l + \frac{x_u - x_l}{2^n - 1}\Sigma_k 2^kb_k$

di mana $n$ adalah banyak digit biner yang digunakan.

Dari representasi matematis tersebut nampak terlihat, jika kita ingin angka melibatkan angka di belakang koma yang lebih banyak, maka $n$ nya pun juga harus banyak. Berarti semakin banyak digit biner yang digunakan semakin bagus? Karena kepresisiannya lebih bagus? Semuanya bergantung pada permasalahan yang kita hadapi, ada yang memerlukan tingkat presisi yang tinggi, ada juga yang enggak. Maksudnya gunakan seefisien mungkin, jangan sampe overkill.

Fungsi Objektif dan Batasan

Sebenarnya kalau masalah yang dihadapi tidak melibatkan batasan-batasan atau constraints, tidak ada yang menarik untuk dibahas. Sekarang gimana caranya kalau kita ingin melibatkan batasan-batasan yang dimaksud? Mungkin sebelumnya kalian pernah belajar tentang program linear dua variabel kan, di situ kalian lihat ada batasan-batasan, bisa itu berupa persamaan ataupun pertidaksamaan.

Di algoritma genetik, apabila ingin menyertakkan batasan yang dimaksud, fungsi objektifnya perlu diubah terlebih dahulu. Yakni menjadi seperti berikut

$f(x) + \Sigma_i k_i \langle g_i(x)\rangle^2 + \Sigma_j l_j \langle h_j(x)\rangle^2$

di mana $k_i$ dan $l_j$ merupakan suatu konstanta. Kalau dari sudut pandang saya, konstanta ini saya anggap pembobotan, artinya menentukan seberapa besar pengaruh suatu batasan. Atau bisa juga dianggap sebagai seberapa penting batasan tersebut. Dan satu lagi, simbol $\langle\cdot\rangle$ memberikan nilai nol jika argumennya negatif, dan nilai aslinya jika lebih besar atau sama dengan nol.

Operator Genetik

Seperti yang telah disebutkan sebelumnya, ada tiga proses utama yang disebut sebagai operator genetik, yaitu reproduksi, kawin silang, dan mutasi.

Reproduksi

Proses ini merupakan yang pertama dilakukan pada metode optimisasi ini. Untuk memulainya setidaknya kita telah mendefinisikan populasi dari design variable (mulai sekarang kita akan sebut sebagai string, nama yang diambil dari salah satu gen). Biasanya populasi awal diinisialisasi dengan cara acak, maksudnya secara random kita definisikan nilai-nilai string pada populasi tersebut.

Jadi kurang lebih proses reproduksi itu kayak gini, string yang mempunyai nilai fitness paling tinggi akan cenderung bertahan. Nilai fitness sendiri menyatakan seberapa besar string yang dimaksud memberikan nilai optimal. Kurang lebih proses ini mirip sekali dengan proses seleksi, yang bisa beradaptasi bertahan dan yang tidak gugur.

Nah yang jadi pertanyaan, bagaimana caranya membuat algoritma sehingga nilai fitness yang besar cenderung untuk bertahan di populasi? Caranya kita gunakan teknik yang namanya roulette-wheel selection. Pertama kita perlu memberikan probabilitas atau peluang pada masing-masing string. Peluang tersebut diberi nilai yang mana setara dengan nilai fitness-nya.

Jika nilai fitness masing-masing string adalah $F_i$ , dan totalnya adalah $F_{\text{tot}} = \Sigma_i F_i$ . Besar peluang yang diberikan pada masing-masing string yaitu

$p_i = \frac{F_i}{F_{\text{tot}}}$ .

Selanjutnya kita cari peluang kumulatifnya, yang pada dasarnya, nilai kumulatif pada misal indeks ke-i besarnya adalah besar peluang indeks ke-i ditambah dengan kumulatif sebelumnya.

Dengan adanya peluang kumulatif ini, setiap string mempunyai rentang probabilitasnya masing-masing. Semakin besar nilai fitness-nya, semakin besar juga rentang ini. Jadi apabila kita generate bilangan acak dari 0 sampai 1, string yang mempunyai rentang lebih besar akan cenderung bertahan.

String yang bertahan dari proses ini kemudian dikumpulkan kedalam kolam perkawinan (mating pool), yang intinya merupakan populasi baru kita yang akan digunakan untuk proses berikutnya.

Kawin silang

Tujuan dari proses ini yaitu untuk menghasilkan beberapa string baru dengan cara menukar informasi dari dua string yang terpilih. Misal dipilih 2 string secara acak, lalu jika lokasi titik tukarnya sudah ditentukan, maka digit biner sebelah kiri dari titik tukar tersebut saling berpindah. Ilustrasinya kurang lebih seperti di bawah ini.

Memang proses ini terlihat gambling, mengingat nilai fitness yang besar tidak bisa dijadikan patokan sebagai string yang bagus untuk dikawin silangkan. Syukur-syukur kalau setelah proses ini hasil kawin silangnya memberikan string yang lebih bagus, tapi bisa juga malah menjadi kacau. Untuk strateginya bisa digunakan beberapa string saja, jangan semuanya.

Mutasi

Di proses ini, digit biner pada string yang terpilih di ubah layaknya 0 menjadi 1 dan sebaliknya. Tujuannya untuk menghasilkan string yang baru. Maksudnya gini, bisa jadi pada suatu kondisi string dengan nilai 1 pada digit ke-3 memberikan hasil yang optimal, namun di populasi semua yang tersedia bernilai 0. Tentunya dengan 2 operator sebelumnya, kita tidak dapat merubah digit tersebut.

String terpilih sebenarnya tidak langsung diubah digitnya, jadi secara keseluruhan ada besar threshold probabilitasnya tersendiri untuk digit tersebut berubah.

Caranya pun serupa dengan sebelumnya, kita generate bilangan acak (random number) dari 0 sampai 1. Nanti tinggal diperiksa, apakah lebih besar dari ambang batas yang ditentuin apa enggak.

Tiga proses di atas dilakukan terus menerus hingga simpangannya dari fitness-nya kurang dari nilai tertentu. Nilai tertentunya merupakan toleransi yang kita atur.

Satu perulangan dalam algoritma genetik disebut sebagai generasi. Biasanya ditambahkan juga batasan untuk jumlah generasi ini.

Sumber:

Buku yang saya pakai saat belajar Teknik Optimisasi yaitu Engineering Optimization: Theory and Practice karangan Singiresu S. Rao.