Metode Nelder-Mead

Artikel ini perlu dirapikan agar memenuhi standar Wikipedia
Merapikan artikel bisa berupa membagi artikel ke dalam paragraf atau wikifisasi artikel. Setelah dirapikan, tolong hapus pesan ini.

Metode Nelder-Mead, dikenal pula sebagai metode Polihedron Fleksibel, atau metode Simplex atau metode Downhill Simplex, adalah suatu metode yang umumnya digunakan sebagai algoritma pemecahan masalah optimasi yang tidak linier. Metode ini ditemukan oleh Nelder & Mead pada tahun 1965. Metode ini dikategorikan sebagai metode numerik.

Metode ini bermanfaat untuk mencari harga-harga ekstrim suatu fungsi dengan banyak variabel, terutama apabila turunan dari fungsi tersebut sulit untuk dicari dengan menggunakan metode kalkulus. Metode polihedron fleksibel menggunakan pencerminan (reflection), ekspansi (expansion) dan penyusutan (contraction) dalam melakukan penelusuran. Metode ini digunakan untuk mencari solusi optimal pada masalah dengan N variabel. Sebagai contoh penerapan, metode ini dapat dipakai untuk menghitung komposisi beton bertulang pada struktur beton bertulang, sehingga dapat diketahui komposisi struktur yang efisien apabila diketahui harga masing masing komponen struktur beton bertulang.

Metode ini menggunakan banyak titik coba, dengan jumlah titik coba N titik minimum sama dengan jumlah variabel desain (JVD) ditambah satu. N titik = JVD +1 dipakai oleh Harb dan Mattews pada tahun 1987. Box mengusulkan N titik = 2 * JVD, sedangkan N titik = JVD + 2 diusulkan oleh Biles pada tahun 1983. Jumlah titik coba makin banyak dimaksudkan untuk mengurangi terjadinya konvergen prematur, tetapi memperlambat konvergensi.

Berikut ini adalah Prosedur untuk contoh masalah meminimumkan fungsi sasaran f = f(x,y), dengan dua variabel desain x dan y, dan memakai jumlah titik coba N titik = JVD + 1 = 3:

1. Tentukan atau acak tiga buah titik di dalam ruang variabel disain, kemudian hitung nilai fitnessnya. Titik terbaik disebut titik B (best) dengan koordinat (XB,YB), titik terjelek disebut titik W (worst) dengan koordinat (XW,YW), sedang titik lainnya disebut titik G (good) dengan koordinat (XG,YG)

2. Hitung titik pusat M dengan koordinat (XM,YM) yang didapat dengan merata – rata titik coba selain titik W, sehingga :

XM = 0.5*(XB + XG)

YM = 0.5*(YB + YG)

3. Tentukan arah penelusuran, yaitu garis yang menghubungkan titik W dan titik M dan dinyatakan sebagai :

XS = XN - XW

YS = YN - YW

4. Cari titik coba baru dalam arah S (search) yang memberikan nilai fitness lebih baik daripada fitness dititik W, titik coba ini tidak boleh identik dengan titik M. Titik coba baru T (try) dengan koordinat XT,YT adalah :

XT = XW + λ.XS

YT = YW + λ.YS

λ adalah koefisien refleksi. Kalau tidak ditemukan titik coba baru yang lebih baik dari titik W maka dilakukan penyusutan menuju B, besarnya penyusutan sama dengan setengah jaraknya terhadap titik b, sehingga titik B baru adalah :

XW baru = 0.5 * (XW + XB)

YW baru = 0.5 * (YW + YB)

dan titik G baru adalah

XG baru = 0.5 * (XW+XG)

YG baru = 0.5 * (Yw+YG)

Kemudian diperiksa apakah sudah konvergen atau belum, kalau sudah maka berhenti kalau belum ulangi ke langkah dua lagi.

Pemeriksaan konvergensi dapat menggunakan persamaan-persamaan yang ada di bawah ini :

|XB – XG| <= ξ

|XB – XW| <= ξ

|XW – XG| <= ξ

|YB – YG| <= ξ

|YB – YW| <= ξ

|YW – YG| <= ξ

dengan ξ adalah suatu nilai konvergensi dan diambil sekecil mungkin, misalnya 0.0003.

Secara umum metoda ini membuat sebuah segi banyak dalam ruang variabelnya yang terus diiterasi sehingga segi banyak itu makin lama makin mengecil, dan akan didapatkan hasil yang optimum begitu segi banyak itu menjadi sangat kecil sekali, yang ditentukan nilainya sebagai suatu nilai konvergensi.

[sunting] Pranala luar

J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308-313 [1]
Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
John Nelder FRS
Nelder-Mead (Simplex) Method
Nelder-Mead Search for a Minimum