Nelder-Mead

Metoda polihedron fleksibel merupakan metoda pengembangan dari metoda simplex, yang dikembangkan oleh Nelder-Mead (Haftka, 1991, halaman 64), dasar pemikiran metoda simplex adalah menurunkan nilai fungsi sasaran secara kontinu dimulai dari suatu nilai fungsi awal sampai mencapai nilai fungsi minimum terpenuhi (Haftka, 1991, halaman 64).
Metoda ini bermanfaat untuk mencari harga-harga extrem suatu fungsi dengan banyak variabel, dengan turunan dari fungsi tersebut sulit untuk dicari. Metoda polihedron fleksibel menggunakan pencerminan (reflection), ekspansi (expansion) dan penyusutan (contraction) dalam melakukan penelusuran.
Polihedron Fleksibel menggunakan banyak titik coba, dengan jumlah titik coba Ntitik minimum sama dengan jumlah variabel desain JVD ditambah satu. Ntitik = JVD +1 dipakai oleh Harb dan Mattews pada tahun 1987. Box mengusulkan Ntitik = 2 * JVD, sedangkan Ntitik = JVD + 2 diusulkan oleh Biles pada tahun 1983. Jumlah titik coba makin banyak dimaksudkan untuk mengurangi terjadinya konvergen prematur, tetapi memperlambat konvergensi.
Masalah meminimumkan fungsi sasaran f = f(x,y), dengan dua variabel desain x dan y, dan memakai jumlah titik coba Ntitik = JVD + 1 = 3, prosedurnya adalah sebagai berikut :
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.