Algoritma AMO (Amoeba Method Optimization) / Nelder-Mead Method


Algoritma AMO (Amoeba Method Optimization) / Nelder-Mead Method adalah salah satu algoritma optimasi yang dapat digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi maksimal.
Amoeba Method Optimization, atau disebut juga dengan Nelder-Mead Method dan Simplex Optimization, adalah metode numerik umum yang digunakan untuk mencari nilai minimal atau maksimal dari sebuah fungsi obyektif pada ruang multi dimensi. Simplex Optimization bekerja dengan cara membentuk segitiga solusi yang dikatakan sebagai solusi terbaik – lainnya – terburuk. Pada setiap perhitungan, segitiga ini akan dihitung sehingga semakin mendekati solusi yang terbaik. Apabila segitiga ini digambar secara berurutan pada setiap perulangan, gerakan segitiga yang terjadi mirip dengan pola gerakan Amoeba.



Diasumsikan ada sebaran titik 2 dimensi antara -2 sampai dengan 2
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Tentukan posisi dimana fungsi tersebut mengembalikan nilai maksimal



Fungsi Himmelblau adalah salah satu fungsi yang dapat digunakan untuk mengoptimasi suatu permasalahan. Fungsi ini memiliki sebuah nilai maksimum pada x = -0.270845, and y = -0.923039 dengan nilai fungsi sebesar f(x,y) = 181.617, dengan asumsi bahwa rentang minimal dan maksimal dari sebaran titik adalah -2 sampai dengan 2

Grafik fungsi Himmelblau yang normal, atau untuk sebaran titik tak terbatas adalah sebagai berikut.
Grafik Himmelblau

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.
Grafik Himmelblau -2sd2
Dapat dilihat bahwa pada gambar tersebut, didapatkan area dengan titik tertinggi (berwarna merah) berada pada area x = -0, and y = -1, dimana titik tersebut mengembalikan nilai fungsi tertinggi. Oleh sebab itu digunakan algoritma ini untuk mencari titik di area berwarna merah tersebut.



* Tentukan jumlah Amoeba yang digunakan dalam perhitungan
Jumlah amoeba harus minimal 3 buah, dengan batas maksimal tidak ada
Semakin banyak amoeba yang digunakan, semakin akurat nilai akhirnya, tetapi semakin lama proses perhitungannya
Diasumsikan dalam kasus ini, jumlah amoeba ada 5 buah

* Tentukan posisi minimal dan maksimal dari fungsi yang akan dihitung
Jika tidak ada batasan posisi, tentu saja posisi yang mendekati tak terhingga akan terpilih karena akan mengembalikan nilai fungsi yang sangat besar
Diasumsikan dalam kasus ini, posisi minimal adalah -2, dan posisi maksimal adalah +2

* Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 50 kali


Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi nilai awal untuk semua amoeba
Beri posisi acak untuk tiap-tiap amoeba
Kemudian hitung nilai fungsi untuk posisi acak tersebut

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Amoeba untuk menampung semua data solusi yang diperoleh amoeba tersebut. Deklarasi Class Amoeba adalah sebagai berikut:

2. Lakukan proses pencarian posisi terbaik sebanyak jumlah iterasi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 2a – 2e)

Sedikit pembahasan sebelum memasuki perhitungan utama
Dalam setiap kali perulangan, metode ini akan mencari nilai centroid, reflected, expanded, contracted
Untuk hal tersebut akan digunakan 4 fungsi tambahan untuk menghitung nilai-nilai tersebut
Penjelasan untuk masing-masing nilai tersebut adalah sebagai berikut:

Gunakan fungsi ini untuk mencari nilai centroid
Centroid adalah nilai rata-rata dari semua posisi kecual posisi terburuk

Gunakan 3 fungsi dibawah ini untuk mencari nilai reflected, expanded, contracted
Ilustrasi singkat adalah sebagai berikut:
b----------x----------c----------y----------z
buruk-----------------centroid

Tarik garis lurus antara posisi terburuk dengan posisi centroid
Kemudian tambahkan garis terusan dari posisi centroid sepanjang jarak sebelumnnya
Posisi Reflected berada pada posisi y, dengan jarak (centroid-buruk) * koefisien alpha, dalam contoh ini bernilai 1.0
Posisi Expanded berada pada posisi z, dengan jarak (centroid-buruk) * koefisien gamma, dalam contoh ini bernilai 2.0
Posisi Contracted berada pada posisi x, dengan jarak (centroid-buruk) * koefisien beta, dalam contoh ini bernilai 0.5

Kembali pada proses pencarian posisi terbaik oleh fungsi ProsesPerhitungan (poin 2) yang sudah disebutkan diatas

2a. Hitung nilai centroid, kemudian hitung nilai reflected

2b. Jika nilai reflected lebih baik dari nilai solusi terbaik, maka hitung nilai expanded
Jika nilai expanded ternyata lebih baik dari nilai reflected, maka update posisi terburuk dengan posisi expanded
Jika nilai expanded ternyata tidak lebih baik dari nilai reflected, maka update posisi terburuk dengan posisi reflected

2c. Tentukan apakah nilai reflected ternyata paling buruk (nilai terendah) dari semua nilai selain nilai posisi terburuk

2d. Jika benar nilai reflected ternyata paling buruk (nilai terendah) dari semua nilai selain nilai posisi terburuk, maka:
– Jika nilai reflected ternyata masih lebih baik dari nilai solusi terburuk, maka update posisi terburuk dengan posisi reflected
– Hitung nilai contracted
– Jika nilai contracted ternyata lebih baik dari nilai solusi terburuk, maka update posisi terburuk dengan posisi contracted
– Jika nilai contracted ternyata tidak lebih baik dari nilai solusi terburuk, maka solusi baru tidak ditemukan
Jika solusi baru tidak ditemukan maka lakukan proses perpindahan semua posisi kecual posisi terbaik
Posisi baru untuk masing-masing posisi adalah setengah jarak dari (posisi terbaik dan posisi tersebut), kemudian hitung nilai fungsi baru untuk masing-masing posisi

2e. Lakukan perhitungan poin 2a – 2d sebanyak jumlah iterasi

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Solusi untuk menampung semua data posisi beserta nilai fungsinya. Deklarasi Class Solusi adalah sebagai berikut:


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd34a

Dapat dilihat bahwa hasil akhir perhitungan tidak sama dengan x = -0.270845, and y = -0.923039, tetapi sangat mendekati posisi tersebut. Jika ingin mendapatkan jawaban yang lebih mirip lagi, maka silahkan lakukan penambahan jumlah iterasi, dengan resiko bahwa perhitungan yang dilakukan akan semakin lama.


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *