referensi : pengantar optimasi non linier
http://luk.staff.ugm.ac.id/optimasi/pdf/Nonlinier2003.pdf
Teknik eliminasi pencarian bebas adalah teknik yang paling sederhana dan mudah difahami, tetapi tidak efisien ditinjau dari segi numeris. Teknik ini dibagi menjadi dua metode yang berbeda dalam pemilihan langkah hitungan
Pendekatan paling dasar dari permasalahan optimasi adalah penggunaan langkah tetap berangkat dari titik tebakan pertama dan bergerak kearah yang dikehendaki. Diandaikan permasalahan yang dihadapi adalah minimisasi suatu fungsi tujuan, maka teknik ini dapat dijabarkan sebagai berikut:
1. Mulai dengan tebakan titik pertama, misalkan x1.
2. Hitung f1 = f(x1).
3. Pilih sebuah ukuran langkah misalkan s, hitung x2 = x1 + s.
4. Hitung f2 = f(x2).
5. Jika f2 < f1, maka pencarian dapat diteruskan kearah ini sepanjang titik-titik x3, x4, … dengan melakukan tes pada setiap dua titik yang terakhir. Cara ini ditempuh terus sampai dicapai suatu keadaan dimana xi = x1 + (i – 1)s memperlihatkan ke- naikan pada nilai fungsinya.
6. Pencarian dihentikan pada xi, dan xi atau xi–1 dapat dianggap sebagai titik optimum.
7. Jika f2 > f1, pencarian harus dilakukan kearah yang berlawanan yaitu sepanjang titik-titik x–2, x–3, … dengan x–j = x1 – (j – 1)s .
8. Jika f2 = f1, maka titik optimum terletak diantara titik-titik x1danx2.
Jika ternyata f2 dan f–2 mempunyai nilai lebih besar dari f1, maka titik optimum terletak diantara titik-titik x–2 dan x2
dengan percepatan langkah adalah Salah satu cara untuk mempercepat proses pencarian titik optimum tersebut yaitu dengan memperbesar langkah pencarian sampai titik optimum terkurung. Pada permasalah maximisasi fungsi tujuan, maka teknik pencarian percepatan langkah dilakukan dengan memperbesar langkah dua kali lipat sepanjang arah gerakan yang menghasilkan bertambahnya nilai fungsi tujuan. Beberapa perbaikan dari teknik ini dapat dikembangkan dari ide yang serupa. Salah satunya adalah dengan mengurangi besar langkah pada saat titik optimum
2.1.2 Pencarian Lengkap[kembali]
Teknik ini dapat digunakan jika telah diketahui bahwa interval dimana terdapat titik optimum telah tertentu. Misal xs dan xf berurutan menunjukkan titik-titik awal dan akhir dari interval yang menjadi perhatian kita. Teknik Pencarian lengkap terdiri atas pencarian nilai fungsi tujuan pada titik-titik tertentu yang berjarak sama dalam interval (xs, xf ). Misal suatu fungsi didefinisikan dalam interval (xs, xf ) dan dievaluasi pada delapan titik-titik hitungan x1 dan x8. Andaikan nilai fungsi yang ditinjau berbentuk kurva seperti disajikan dalam Gambar , maka titik optimum akan terletak diantara titik x5 dan x7. Jadi interval (x5, x7) dianggap sebagai interval pencarian yang baru.
xs x1 x2 x3 x4 x5 x6 x7 x8 xf x
Pada prinsipnya pencarian dikotomi merupakan teknik pencarian yang berikutnya dipengaruhi secara langsung oleh pencarian sebelumnya
Pada pencarian dikotomi, 2 penyelidikan dilakukan pada daerah didekat titik tengah (Xm) dari interval pencarian (Xs,Xf).
Berdasarkan nilai relatif dari fungsi tujuan pada dua titik di sebelah kiri(X1) dan kanan (X2) yang berjarak do/2 dari titik tengah, maka penentuan interval pencarian berikutnya dilakukan.
interval pencarian yang baru mempunyai lebar interval sebesar:
interval-interval yang baru dicari dengan cara yang sama seperti diatas sehingga dapat hubungan antara lebar interval pencarian dengan jumlah pencarian inteval yang telah dilakukan
2.1.4 Pencarian fibonaci[kembali]
Pencarian Fibonacci dapat dipakai untuk mencari maximum dari sebuah fungsi satu variabel, bahkan untuk fungsi yang tidak menerus.Teknik ini, seperti teknik eliminasi yang lainnya mempunyai ciri khas sebagai berikut:
(i) Interval permulaan dimana terletak titik optimum harus diketahui terlebih dahulu.
(ii) Fungsi tujuan yang dioptimasikan harus fungsi unimodal pada interval pencarian.
(iii) Letak yang tepat dari titik optimum tidak dapat ditentukan. Hanya interval pencariannya saja yang dapat diketahui. Interval pencarian dapat diperkecil sesuai dengan ketelitian yang dikehendaki.
(iv) Jumlah nilai fungsi tujuan yang harus dievaluasi dalam pencarian atau jumlah subinterval pencarian harus ditentukan sebelumnya.
Pada teknik Fibonacci ini digunakan sebuah deret yang dinamakan deret Fibonacci (Fn)yang mempunyai ciri sebagai berikut:
Yang menghasilkan deret 1,1,2,3,5,8,13,21,34,55,89,...
2.1.5 Pencarian Rasio Emas[kembali]
Rasio Emas didefinisikan sebagai:
dengan b dan d berurutan adalah sisi pendek dan sisi panjang dari suatu empat persegi panjang. Dari geometri Euclid, diketemukan pula bahwa jika suatu garis dibagi dengan Rasio Emas menjadi dua bagian tidak sama besar, maka nilai perbandingan antara bagian yang besar dibanding panjang keseluruhan sama dengan perbandingan bagian yang kecil dibanding bagian yang besar.
Dari Persamaan diperoleh nilai g dengan
persamaan g2 = g + 1, sehingga nilai g = 1/2(1+√5) = 1.6180339
rasio ini menghasilkan suatu algoritma eleminasi interval yang sangat efisien
Dari ketentuan di atas, maka diperoleh hubungan:
Metode Newton (atau seringkali disebut dengan metode Newton–Raphson) memerlukan fungsi tujuan tanpa kendala dalam interval yang menjadi perhatian dan mempunyai derivasi pertama maupun keduanya. Metode ini banyak pula dikembangkan untuk memecahkan permasalahan optimasi multi variabel. Metode Newton seringkali dipandang sebagai metode untuk mencari akar dari suatu fungsi. Dalam bab ini, metode ini akan diinterpretasikan sebagai pendekatan kuadratik dari suatu fungsi tujuan f. Ditinjau tiga suku pertama dari suatu deret Taylor dari fungsi f pada titik x(k) pada iterasi k.Fungsi F(x) adalah pendekatan kuadratik dari f(x) dan mempunyai derivasi pertama dan kedua yang sama di titik x(k). Kita dapat maximisasi F(x) secara langsung. Jika titik x(k) berada di sekitar titik optimum dari f(x), kurva F(x) akan merupakan pendekatan dari fungsi f(x) pada titik optimum. Jadi maximisasi fungsi pendekatan F(x), merupakan pendekatan dari maximisasi fungsi tujuan asli F(x)
Tidak ada komentar:
Posting Komentar