13 Maret 2011

Tips Terbaik Untuk Optimasi Algoritma

Ada beberapa teknik optimasi yang tersedia di PROC NLMIXED. Anda dapatmemilih optimizer tertentu dengan opsi = nama TECH dalam laporan NLMIXEDPROC. Tidak ada algoritma untuk mengoptimalkan fungsi nonlinier umum ada yang selalu menemukan optimum global untuk masalah minimisasi umum nonlinier dalam jumlahwaktu yang wajar. Karena tidak ada teknik optimasi tunggal selalu lebih unggul dariorang lain, PROC NLMIXED menyediakan berbagai teknik optimasi yang bekerjadengan baik di berbagai keadaan. Namun, Anda dapat menemukan masalah yang tidak ada teknik PROC NLMIXED dapat menemukan solusi yang tepat. Selain itu,optimasi nonlinier dapat komputasi mahal dalam hal waktu dan memori, sehingga Anda harus berhati-hati ketika mencocokkan suatu algoritma untuk suatu masalah.

Semua teknik optimasi yang digunakan PROC NLMIXED O (n2) memori kecuali metode gradien konjugat, yang menggunakan hanya O (n) dari memori dan dirancang untuk masalah mengoptimalkan dengan banyak parameter. Karena teknik yang berulang, mereka memerlukan perhitungan berulang-ulang nilai fungsi (kriteria optimasi) vektor gradien (orde pertama derivatif parsial) untuk beberapa teknik, (perkiraan) Hessian matriks (orde kedua derivatif parsial) Namun, karena masing-masing dari pengoptimalan membutuhkan derivatif yang berbeda, beberapa efisiensi komputasi dapat diperoleh. Tabel berikut menunjukkan, untuk setiap teknik optimasi, yang derivatif diperlukan (FOD: orde pertama turunannya;SOD: orde kedua derivatif). 
Setiap metode optimasi kriteria konvergensi mempekerjakan satu atau lebih yangmenentukan ketika telah menyatu. Kriteria berbagai terminasi terdaftar dan dijelaskandi bagian "NLMIXED PROC Statement ". Sebuah algoritma dianggap telah berkumpulketika salah satu dari kriteria konvergensi terpenuhi. Sebagai contoh, di bawah pengaturan standar, algoritma QUANEW akan berkumpul jika ABSGCONV <1E-5,FCONV <10-FDIGITS, atau

Memilih Algoritma Optimasi

Faktor-faktor yang masuk ke dalam memilih teknik optimasi tertentu untuk masalah tertentu yang rumit dan bisa melibatkan trial and error. Untuk masalah optimasi banyak, komputasi gradien membutuhkan waktu komputer lebih dari menghitung nilai fungsi, dan menghitung Hessian kadang-kadang membutuhkan waktu lebih banyak komputer dan memori dari komputasi gradien, terutama bila ada banyak variabel keputusan. Sayangnya, optimasi teknik yang tidakmenggunakan beberapa jenis pendekatan Hessian biasanya membutuhkan banyak iterasi lebih dari teknik yang menggunakan matriks Hessian, dan sebagai hasilnya run time total teknik ini sering lagi. Teknik yang tidak menggunakan Hessian juga cenderung kurang dapat diandalkan. Sebagai contoh, mereka dapat lebih mudah berakhir pada titik stasioner dari pada di optima sikan global.

Sebuah komentar umum beberapa hal mengenai berbagai teknik optimasi adalah sebagai berikut :

Metode kedua-derivatif TRUREG, NEWRAP, dan NRRIDG yang terbaik untuk masalah kecil dimana matriks Hessian tidak mahal untuk menghitung. Kadang-kadang algoritma NRRIDG bisa lebih cepat dari pada algoritma TRUREG, tetapi TRUREG bisa lebih stabil. Algoritma NRRIDG hanya memerlukan satu matriks dengan n (n +1) / 2 kata ganda; TRUREG dan NEWRAP membutuhkan dua matriks tersebut.

Metode pertama derivatif QUANEW dan DBLDOG yang terbaik untuk masalah menengah di mana fungsi objektif dan gradien yang lebih cepat untuk mengevaluasi dari Hessian. Algoritma QUANEW dan DBLDOG, pada umumnya, memerlukan iterasi lebih dari TRUREG, NRRIDG, dan NEWRAP, namun setiap iterasi dapat lebih cepat.Para QUANEW dan algoritma DBLDOG hanya memerlukan gradien untuk pembaruan Hessian perkiraan, dan mereka memerlukan memori sedikit kurang dari TRUREG atau NEWRAP (dasarnya satu matriks dengan n (n +1) / 2 kata ganda). QUANEW adalah metode optimasi default.

Metode CONGRA pertama-derivatif yang terbaik untuk masalah-masalah besar di mana fungsi objektif dan gradien dapat dihitung jauh lebih cepat daripada Hessian dan dimana terlalu banyak memori yang diperlukan untuk menyimpan (perkiraan) Hessian. Algoritma CONGRA, secara umum, membutuhkan iterasi lebih dari QUANEW atau DBLDOG, tapi setiap iterasi dapat lebih cepat. Sejak CONGRA hanya membutuhkan faktor memori n ganda-kata, banyak aplikasi besar PROC NLMIXED dapat diselesaikan hanya dengan CONGRA. Metode no-derivatif NMSIMP yang terbaik untuk masalah kecil dimana derivatif ini tidak terus-menerus atau sangat sulit untuk menghitung.

Deskripsi Algoritma

Beberapa rincian tentang teknik optimasi adalah sebagai berikut:
Trust Daerah Optimization (TRUREG)

Metode wilayah kepercayaan menggunakan gradien dan Hessian matriks, oleh karena itu mensyaratkan bahwa fungsi objektif mempunyai derivatif kontinu pertamadan orde kedua di daerah layak. Metode wilayah kepercayaan iteratif mengoptimasikan pendekatan kuadratik ke fungsiobjektif nonlinier dalam wilayah kepercayaan hyperelliptic dengan radius yangmembatasi ukuran langkah yang sesuai dengan kualitas pendekatan kuadrat. Metodewilayah kepercayaan diimplementasikan dengan menggunakan Dennis, Gay, danWelsch (1981), Gay (1983), dan Mor dan Sorensen (1983).

Metode wilayah kepercayaan melakukan baik untuk masalah kecil-menengah, dan tidak memerlukan banyak fungsi, gradien, dan panggilan Hessian. Namun, jika perhitungan matriks Hessian komputasi mahal, salah satu (dual) kuasi-Newton ataualgoritma gradien conjugate mungkin lebih efisien.

Newton-Raphson Optimasi dengan Line Cari (NEWRAP)


Teknik NEWRAP menggunakan gradien dan Hessian matriks, oleh karena itu mensyaratkan bahwa fungsi objektif mempunyai derivatif kontinu pertama dan orde kedua di daerah layak. Jika kedua-order derivatif dihitung secara efisien dan tepat, metode NEWRAP dapat melakukan baik untuk menengah untuk masalah besar, dan tidak memerlukan banyak fungsi, gradien, dan panggilan Hessian.  Algoritma ini menggunakan sebuah langkah Newton murni ketika Hessian adalah positif pasti dan ketika langkah Newton mengurangi nilai fungsi objektif berhasil. Jika tidak, kombinasi garis ridging dan pencarian dilakukan untuk menghitung langkah-langkah sukses. Jika tidak Hessian definit positif, kelipatan dari matriks identitas ditambahkan ke matriks Hessian untuk membuatnya pasti positif (Eskow dan Schnabel 1991).

Pada setiap iterasi, garis pencarian dilakukan sepanjang arah pencarian untuk menemukan perkiraan optimal dari fungsi objektif. Standar garis-metode pencarian menggunakan interpolasi kuadratik dan ekstrapolasi kubik (LIS = 2).

Newton-Raphson Ridge Optimization (NRRIDG)


Teknik NRRIDG menggunakan gradien dan Hessian matriks, oleh karena itu mensyaratkan bahwa fungsi objektif mempunyai derivatif kontinu pertama dan orde kedua di daerah layak. Algoritma ini menggunakan langkah Newton murni ketika Hessian adalah positif pasti dan ketika langkah Newton mengurangi nilai fungsi objektif berhasil. Jika setidaknya salah satu dari kedua kondisi ini tidak puas, kelipatan dari matriks identitas ditambahkan ke matriks Hessian.

Metode NRRIDG berkinerja baik untuk masalah kecil-menengah, dan tidak memerlukan banyak fungsi, gradien, dan panggilan Hessian. Namun, jika perhitungan matriks Hessian komputasi mahal, salah satu (dual) kuasi-Newton atau algoritma gradien conjugate mungkin lebih efisien.

Karena teknik NRRIDG menggunakan dekomposisi ortogonal dari perkiraan Hessian, masing-masing iterasi dari NRRIDG dapat lebih lambat dari pada teknik NEWRAP, yang bekerja dengan dekomposisi Cholesky. Biasanya, bagaimanapun, NRRIDG membutuhkan iterasi kurang dari NEWRAP.
Kuasi-Newton Optimization (QUANEW)

The (dual) kuasi-Newton menggunakan metode gradien, dan tidak perlu menghitung turunan orde kedua karena mereka didekati. Ini bekerja baik untuk menengah untuk masalah optimasi yang cukup besar di mana fungsi objektif dan gradien yang lebih cepat untuk menghitung dari Hessian, tetapi, secara umum, hal ini memerlukan iterasi lebih dari teknik NRRIDG TRUREG, NEWRAP, dan, yang menghitung orde kedua derivatif. QUANEW adalah algoritma optimasi default karena memberikan keseimbangan yang tepat antara kecepatan dan stabilitas yang diperlukan untuk sebagian besar aplikasi model nonlinier campuran.
Teknik QUANEW adalah salah satu dari berikut ini, tergantung pada nilai option = UPDATE.

algoritma kuasi-Newton asli, yang update perkiraan dari Hessian invers
algoritma dual kuasi-Newton, yang update faktor Cholesky dari (default) perkiraan Hessian
Anda dapat menentukan rumus memperbarui empat dengan opsi = UPDATE:

DBFGS melakukan Broyden ganda, Fletcher, Goldfarb, dan Shanno (BFGS) update dari faktor Cholesky dari matriks Hessian. Ini adalah baku.  DDFP melakukan Davidon ganda, Fletcher, dan Powell (DFP) update dari faktor Cholesky dari matriks Hessian.  BFGS melakukan BFGS asli update dari Hessian matriks invers.
DFP melakukan update DFP asli dari Hessian matriks invers.
Pada setiap iterasi, garis pencarian dilakukan sepanjang arah pencarian untuk menemukan perkiraan optimal. Standar garis-metode pencarian menggunakan interpolasi kuadratik dan kubik ekstrapolasi untuk mendapatkan ukuran langkah yang sesuai dengan kondisi Goldstein. Salah satu syarat Goldstein dapat dilanggar jika daerah layak menetapkan batas atas ukuran langkah. Melanggar kondisi Goldstein sisi kiri dapat mempengaruhi kedefinitan positif dari update kuasi-Newton. Dalam hal ini, baik pembaruan dilewati atau iterasi ulang dengan identitas sebuah matriks, yang mengakibatkan turunnya curam atau arah pendakian pencarian. Anda dapat menentukan garis-algoritma pencarian selain default dengan opsi = LIS.

Algoritma QUANEW melakukan teknik sendiri line-pencarian. Semua pilihan dan parameter (kecuali option = punggung kaki) mengendalikan cari baris di algoritma lain tidak berlaku di sini. Pada beberapa aplikasi, langkah besar di iterasi pertama merepotkan. Anda dapat menggunakan opsi punggung kaki = untuk menerapkan batas atas untuk ukuran langkah selama lima iterasi pertama. Anda juga dapat menggunakan INHESSIAN [= r] pilihan untuk menentukan pendekatan awal yang berbeda untuk Hessian. Jika Anda menetapkan hanya opsi INHESSIAN, faktor Cholesky dari sebuah pendekatan beda (mungkin bergerigi) hingga dari Hessian digunakan untuk menginisialisasi proses update kuasi-Newton. Nilai dari LCSINGULAR =, LCEPSILON =, dan LCDEACT = pilihan, yang mengendalikan pengolahan kendala linier dan batas, hanya berlaku untuk subroutine pemrograman kuadratik digunakan dalam setiap iterasi dari algoritma QUANEW.

Double Dogleg Optimization (DBLDOG)


Metode dogleg ganda optimasi menggabungkan ide-ide dari quasi-Newton dan metode kepercayaan wilayah. Pada setiap iterasi, algoritma dogleg ganda menghitung langkah s (k) sebagai kombinasi linier dari keturunan curam atau pendakian arah pencarian s1 (k) dan arah pencarian kuasi-Newton s2 (k).

Langkah ini diminta untuk tetap berada dalam wilayah radius kepercayaan prespecified; lihat Fletcher (1987, hal 107). Dengan demikian, subrutin DBLDOG menggunakan update kuasi-Newton dual tetapi tidak melakukan pencarian garis.Anda dapat menentukan rumus update dua dengan opsi = UPDATE:
DBFGS melakukan Broyden ganda, Fletcher, Goldfarb, dan memperbarui Shanno faktor Cholesky dari matriks Hessian. Ini adalah baku.

DDFP melakukan Davidon ganda, Fletcher, dan memperbarui Powell faktor Cholesky dari matriks Hessian.
Teknik dogleg ganda optimasi bekerja dengan baik untuk menengah untuk masalah optimasi yang cukup besar di mana fungsi objektif dan gradien yang lebih cepat untuk menghitung dari Hessian. implementasi ini didasarkan pada Dennis dan Mei (1979) dan Gay (1983), tetapi diperpanjang untuk berurusan dengan kendala batas dan linier.Teknik DBLDOG umumnya membutuhkan iterasi lebih dari teknik TRUREG, NEWRAP, atau NRRIDG, yang membutuhkan turunan orde kedua, namun masing-masing iterasi DBLDOG komputasi murah. Selanjutnya, teknik DBLDOG hanya memerlukan panggilan gradien untuk update dari faktor Cholesky dari Hessian perkiraan.


Conjugate Gradient Optimization (CONGRA)

Kedua-order derivatif yang tidak diperlukan oleh algoritma CONGRA dan bahkan tidak didekati. Algoritma CONGRA bisa mahal dalam panggilan fungsi dan gradien, tetapi hanya memerlukan O (n) memori untuk optimasi tidak dibatasi. Secara umum, banyak iterasi yang diperlukan untuk mendapatkan solusi tepat, tetapi masing-masing dari iterasi CONGRA komputasi murah. Anda dapat menentukan empat formula update yang berbeda untuk menghasilkan arah konjugat dengan menggunakan pilihan UPDATE =:
PB melakukan restart otomatis memperbarui metode Powell (1977) dan Beale (1972). Ini adalah baku.
FR melakukan update Fletcher-Reeves (Fletcher 1987).
PR melakukan update Polak-Ribiere (Fletcher 1987).
CD melakukan update konjugasi-keturunan dari Fletcher (1987).
Default, UPDATE = PB, berperilaku terbaik dalam contoh tes yang paling. Anda disarankan untuk menghindari opsi UPDATE = CD, yang berperilaku terburuk di contoh tes yang paling.

CONGRA Subroutine yang harus digunakan untuk masalah optimasi dengan besar n.Untuk tidak dibatasi atau batas terbatas kasus, CONGRA hanya memerlukan O (n) byte memori kerja, sedangkan semua metode optimasi lainnya membutuhkan pesanan O (n2) byte memori kerja. Selama iterasi n berturut-turut, terganggu oleh restart atau perubahan dalam working set, algoritma gradien konjugasi menghitung siklus n arah pencarian conjugate. Pada setiap iterasi, garis pencarian dilakukan sepanjang arah pencarian untuk menemukan perkiraan optimal dari fungsi objektif.Standar garis-metode pencarian menggunakan interpolasi kuadratik dan kubik ekstrapolasi untuk mendapatkan ukuran langkah yang sesuai dengan kondisi Goldstein. Salah satu syarat Goldstein dapat dilanggar jika daerah layak menetapkan batas atas untuk ukuran langkah. Lain-line algoritma pencarian dapat dispesifikasikan dengan opsi = LIS.
Nelder-Mead Simplex Optimization (NMSIMP)

Metode Simplex Nelder-Mead tidak menggunakan derivatif dan tidak berasumsi bahwa fungsi objektif telah derivatif kontinu. Fungsi tujuan itu sendiri perlu terus-menerus. Teknik ini cukup mahal dalam jumlah panggilan fungsi, dan mungkin tidak dapat menghasilkan hasil yang tepat untuk. Algoritma Nelder-Mead simpleks asli dilaksanakan dan diperluas ke kendala batas.Algoritma ini tidak menghitung tujuan untuk titik tidak layak, namun mengubah bentukberadaptasi simplex ke nonlinier dari fungsi objektif, yang memberikan kontribusi kepada peningkatan kecepatan konvergensi. Ini menggunakan kriteria penghentian khusus.

oke semoga bermanfaat untuk semua pembaca, jika ada kekeliruan atau kesalahan silahka anda komentar untu bisa saya perbaiki atau kembangkan agar lebih baik lagi. terimakasih.

9 komentar:

esagelo mengatakan...

Wah keren mas informasinya :)
Tapi saya ga ngerti sama yang ginian... Hehe...
Salam :)

Dunia Optimasi mengatakan...

esagelo, sama bos saya juga belum ahli betul masih belajar untuk menelitilebih lanjut, o iya terimakasih komentarnya, salam sahabat.

assyafieq mengatakan...

berkunjung di malam hari sambil baca optimasi algoritma...

Dunia Optimasi mengatakan...

assyafieq, terimakasih sahabat sudah ebaca artikel saya, salam sahabat.

Cyber Boss mengatakan...

Hi,
I recently came across your site and have been learning along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed this site. Nice site. I will keep visiting this site very often. Unique and useful to follower. Best of luck to you! Don’t Forget To Visit My Blog and refer to all my Ads. Thanks.
Cheers,
Lets traveled to change your life
Low AirFare And Cheap Hotels
London Five Star Hotels
New York Five Star Hotels

Dunia Optimasi mengatakan...

Cyber Boss, thank you already commented on my blog, and I am very glad of your visit to read my article, hopefully useful to you, I also later will visit your home if there is a good time. thanks friends.

Ambae.exe mengatakan...

mantap abis infox
keep spirit tuk next artikel

Dunia Optimasi mengatakan...

Ambae, sama-sama saya juga berterimakasih, semoga bermanfaat untuk saudara.

GunkZ blog mengatakan...

teman saya sedang bingung untuk mencari algoritma dan metode optimasi, yang saya tahu hanya genetik algoritma, dan saya dapat membaca ada yang namanya PSO apa itu algoritma optimasi,.?? apa si PSO itu bagaimana cara implementasi dan contohnya? terimakasih teman ku,...

Anda boleh mempublikasikan tulisan kami dengan catatan : 1. Wajib mencantumkan sumber kami dengan LINK AKTIF yang menuju HALAMAN INI. 2. Tidak mengubah baik sebagian atau pun keseluruhan tulisan. Termasuk SEMUA LINK YANG ADA DI DALAM ARTIKEL harus tetap ada dan aktif. Mengcopy artikel kami tanpa memberi link aktif berarti mengambil hak milik penulis. Hak cipta dilindungi oleh Undang-Undang.
 
Template by Dunia Optimasi .
Template Name : Simple Optimasi | sedang pengembangan