Apakah Anda Pernah Mendengar tentang Optimization Problem?

Photo by engin akyurt on Unsplash

Pendahuluan

Sebagai seorang Data Scientist, akan ada saatnya kita perlu membuat script atau model machine learning untuk menjawab pertanyaan kita. Terkadang, ada banyak cara untuk menyelesaikan masalah. Misalnya masalah klasifikasi; kita mungkin menerapkan probability-based model, tree-based model, atau linear-based model. Setelah melakukan Exploratory Data Analysis (EDA), kita akan memilih model dengan asumsi yang sesuai dengan data. Misalnya, kita memilih model Random Forest dan ingin melatih model tersebut.

Banyak dari kita akan menyadari bahwa ada banyak parameter yang bisa diatur, seperti pada gambar di atas. Anda kemudian mencoba setiap kombinasi parameter sampai menemukan parameter ‘terbaik’ untuk model Anda, tetapi itu akan memakan banyak waktu.

Apa yang saya jelaskan di atas disebut sebagai optimization problem.

Secara formal, kita dapat mendefinisikan Optimization Problem sebagai:

"Pencarian keadaan terbaik menurut objektif fungsi."

Perlu dicatat bahwa definisi "keadaan/kasus" dapat bervariasi tergantung pada konteksnya. Kasus tersebut bisa berupa...

• Parameter di model Random Forest.

• Posisi catur di papan;

• Bobot neural network di Model Deep Learning;

• Urutan penempatan stasiun kereta di peta.
  

Hal terpenting di sini adalah ada banyak kemungkinan keadaan, tetapi kita ingin menemukan solusi “terbaik” (atau dalam istilah matematis, objective function, fitness function, cost function, atau loss function). Untuk optimization problem, kita ingin memaksimalkan atau meminimalkan fungsi ini.

Dalam kasus optimization problem, karena kita membandingkan setiap keadaan untuk menemukan fungsi terbaik secara matematis, ini berarti keadaan harus berupa nilai numerik (atau vektor numerik). Optimization problem itu sendiri dapat dibagi menjadi optimasi kontinu atau optimasi diskret tergantung pada variabelnya.

Contoh Matematika

Jika Anda kesulitan membayangkannya, biarkan saya tunjukkan dengan fungsi matematika sederhana. Bayangkan jika kita memiliki fungsi seperti di bawah ini:

di mana x adalah vektor yang terdiri dari keadaan.

Sekarang, misalnya kita memiliki optimization problem di mana kita ingin memaksimalkan fungsi atau mendapatkan nilai maksimum setinggi mungkin dari fungsi tersebut. Dalam masalah kita, fungsi tersebut hanya dapat mengambil nilai antara 0 atau 1. Kita bisa memiliki banyak kombinasi x. Bisa jadi x = [0,0,0], atau x = [0,1,1], dll. tetapi kita ingin memaksimalkan fungsi objektif. Artinya, solusi optimalnya adalah:

di mana fungsi f(x) yang diberikan untuk solusi optimal adalah f(x) = 3. Apa yang saya jelaskan adalah contoh dari optimization problem di mana kita ingin fungsi memberikan nilai maksimum.

Dalam dunia nyata, persamaannya tidak akan sesederhana itu. Masalah yang dihadapi sering melibatkan fungsi yang rumit dan kombinasi keadaan yang banyak. Ini menjadi masalah karena kita tidak dapat mengoptimalkan fungsi dalam waktu yang wajar.

Salah satu cara untuk menyelesaikan masalah ini adalah dengan menerapkan Randomized optimization algorithms. Seperti namanya, kita tidak akan mencoba semua kemungkinan, tetapi kita memulai pada vektor awal “terbaik” kemudian secara acak menghasilkan vektor baru (sering kali tetangga dari keadaan “terbaik” saat ini). Jika vektor baru lebih baik, maka vektor baru menjadi vektor keadaan “terbaik” yang baru. Kita mengulanginya sampai waktu maksimal atau pengulangan maksimal yang diberikan.

Real Application — Travelling Salesperson Problems

Travelling Salesperson Problem (TSP)) adalah masalah optimasi di mana kita mencoba menentukan rute terpendek dari n kota (atau rumah, stasiun, dll), mulai dan berakhir di titik yang sama dan mengunjungi semua lokasi sekali. Misalnya, saya memiliki kumpulan lima kota di grid di bawah ini.

Saya ingin salesperson mengunjungi semua kota tepat satu kali dengan memulai dan mengakhiri di kota yang sama. Jika kita mengatur vektor solusi x = [0,1,2,3,4] dan menganggap kota dimulai dari 0, maka salesman akan bepergian seperti di grid di bawah ini.

Rute yang dilalui tampaknya bukan jalur paling optimal. Di sinilah kita mencoba menemukan rute terpendek atau optimization problem.

Pada artikel ini, saya akan menggunakan modul optimization problem yang disebut mlrose. Jika Anda ingin menginstal modul tersebut, Anda dapat menjalankan kode berikut.

pip install mlrose

Menyelesaikan optimization problem menggunakan mlrose melibatkan tiga langkah:

1. Mendefinisikan fitness function object (Fungsi yang ingin kita minimalkan/maksimalkan).

2. Mendefinisikan optimization problem object (Objek yang berisi semua informasi penting tentang optimization problem yang coba kita selesaikan).

3. Menjalankan randomized optimization algorithm.

Pertama, kita perlu mendefinisikan fitness function object. Untungnya, mlrose sudah memiliki kelas TravellingSales() yang bisa digunakan untuk mendefinisikan fitness function object. Kelas TravellingSales() membutuhkan koordinat (x, y) dari semua kota (atau jaraknya).

import mlrose
# List of city coordinates
coords = [(1, 0), (3, 2), (7, 7), (1, 4), (5, 2)]
# Initialize fitness function object
fitness_coords = mlrose.TravellingSales(coords = coords)

Setelah menginisialisasi fitness function, kemudian kita mendefinisikan optimization problem object. Modul mlrose memiliki TSPOpt() sebagai optimization problem object. Kita hanya perlu mendefinisikan objek tersebut dengan memasukkan beberapa parameter. Dalam contoh di atas, kita ingin menyelesaikan masalah meminimalkan jarak tempuh 5 titik. Dalam hal ini, kita mendefinisikan optimization object seperti di bawah ini.

problem = mlrose.TSPOpt(length = 5, fitness_fn = fitness_coords, maximize=False)

Kita sekarang siap memilih randomized optimization algorithm dan menggunakannya untuk menyelesaikan masalah kita. Randomized optimization algorithm didasarkan pada Evolutionary Algorithm, saya tidak akan menjelaskan secara mendalam, tetapi parameter yang digunakan dalam modul mlrose didasarkan pada itu.

Pada contoh kita, saya mengatur parameter mutation_prob (anggap saja parameter ini sebagai tingkat seberapa besar keadaan berubah berdasarkan keadaan terbaik saat ini) menjadi 0,2 dan max_attempts (jumlah pengulangan) menjadi 100.

best_state, best_fitness = mlrose.genetic_alg(problem, mutation_prob = 0.2,max_attempts = 100, random_state = 2)

print('Best State is:')
print(best_state)

print('Best Fitness (Total Distances) is:')
print(best_fitness)

Kita bisa melihat keadaan terbaik yang ditemukan algoritma adalah [1,0,3,2,4]. Saya juga menyajikan Best Fitness untuk menunjukkan total jarak yang ditempuh, karena yang kita minimalkan dalam masalah ini adalah total jarak (tepatnya Euclidean Distance). Jika kita visualisasikan, salesman kita akan berjalan dengan rute berikut.

Kita sudah menerapkan Optimization Problem ke Travelling Salesman Problem dan menemukan rute terbaik yang bisa dilalui salesman. Begitulah cara kita menggunakan Optimization Problem untuk menyelesaikan pertanyaan yang kita miliki.

Kesimpulan

Optimization Problem adalah masalah untuk menemukan keadaan terbaik sesuai dengan tujuan fungsi. Kasusnya bisa berupa apa saja, mulai dari parameter model Machine Learning hingga rute perjalanan salesman. Tujuannya adalah untuk memaksimalkan atau meminimalkan fungsi objektif dari keadaan yang diberikan.