12 0 338 KB
Metode Gradien Konjugasi Pendahuluan Kami sekarang melihat pengoptimalan dalam n-dimensi; ruang desain. Tujuannya adalah untuk meminimalkan πΉ(π₯), di mana komponen π₯ adalah variabel desain π independen. Salah satu cara untuk mengatasi masalah adalah dengan menggunakan suksesi minimum satu dimensi untuk mendekati titik optimal. Strategi dasarnya adalah ο· ο·
ο·
Pilih satu titik π₯0 di ruang desain. Loop dengan π = 1,2,3, . .. Pilih vektor π£π Minimalkan πΉ(π₯) sepanjang garis melalui π₯πβ1 ke arah π£π . Biarkan titik minimum menjadi π₯π . Jika |π₯π β π₯πβ1 | keluar dari loop Akhiri loop
Minimalisasi sepanjang garis dapat dicapai dengan algoritma optimasi satu dimensi (seperti pencarian bagian emas). Satu-satunya pertanyaan yang dibiarkan terbuka adalah bagaimana memilih vektor π£π . Arah KonjugatType equation here. Perhatikan fungsi kuadrat 1 πΉ(π₯) = π β β ππ π₯π + β β π΄ππ π₯π π₯π 2 π
π
π
1 = π β π π π₯ + π₯ π π΄π₯ 2 Diferensiasi sehubungan dengan hasil xi ππΉ = βππ + β π΄ππ π₯π ππ₯π π
Yang dapat ditulis dalam notasi vektor sebagai βπΉ = βπ + π΄π₯ Dimana β adalah gradien πΉ. Sekarang perhatikan perubahan gradien ketika kita bergerak dari titik π₯0 ke arah vektor π’. Gerakan berlangsung sepanjang garis π₯ = π₯0 + π π’ Di mana jarak dipindahkan. Substitusi menjadi Persamaan. (10.6) menghasilkan persamaan untuk gradien sepanjang π’: βF|x0+π π’ = βπ + π΄(π₯0 + π π’) = βF|x0 + π π΄π’
Perhatikan bahwa perubahan gradien π adalah π΄π’. jika perubahan ini tegak lurus terhadap vektor π£; yaitu, jika π£ π π΄π’ = 0
arah dari π’ dan π£ dikatakan saling konjungtif (noninterfering). Implikasinya adalah bahwa begitu kita telah meminimalkan πΉ(π₯) ke arah π£, kita dapat bergerak sepanjang π’ tanpa merusak minimisasi sebelumnya. Untuk fungsi kuadrat dari n variabel independen adalah mungkin untuk membangun arah yang saling konjungtif. Oleh karena itu, perlu tepat n garis minimisasi sepanjang arah ini untuk mencapai titik minimum. Jika πΉ(π₯) bukan fungsi kuadrat, Persamaan (10.5) dapat diperlakukan sebagai pendekatan lokal dari fungsi merit, diperoleh dengan memotong ekspansi taylor seri πΉ(π₯) sekitar π₯0 (lihat lampiran A1) 1 πΉ(π₯) = πΉ(π₯0 ) + βF(x0 )(π₯ β π₯0 ) + (π₯ β π₯0 )π π»(π₯0 )(π₯ β π₯0 ) 2 Sekarang arah konjugasi berdasarkan bentuk kuadrat hanya perkiraan, berlaku di sekitar dekat π₯0 . Akibatnya, diperlukan beberapa siklus minimisasi garis π untuk mencapai titik optimal. Berbagai metode gradien konjugat menggunakan teknik yang berbeda untuk membangun arah konjugasi. Metode orde-nol hanya bekerja dengan πΉ(π₯) saja, sedangkan putasional lebih efisien, tentu saja, tetapi masukan πΉ(π₯) and βF (jika tersedia sama sekali) bisa sangat monoton.
Metode Powell Metode Powells adalah metode zero-order, membutuhkan evaluasi πΉ(π₯) saja. jika masalah melibatkan π variabel desain, algoritma dasarnya adalah ο· ο·
pilih titik π₯0 di ruang desain pilih starting vector π£1 , π = 1,2, . . . , π (pilihan ususal adalah π£π β ππ , di mana ππ adalah vektor satuan dalam arah koordinat π₯π ). ο· Siklus lakukan dengan π = 1,2, . . . , π minimalkan πΉ(π₯) sepanjang garis melalui π₯π β 1 ke arah π£π . biarkan titik minimum menjadi π₯π di akhir lakukan π£π+1 β π₯0 β π₯π (vektor ini konjugat ke π£π+1 yang dihasilkan pada loop sebelumnya) Minimalkan πΉ(π₯) sepanjang garis melalui π₯0 ke arah π£π+1. biarkan titik minimum menjadi π₯π+1 Jika |π₯π+1 β π₯0 | < π exit loop Lakukan dengan π = 1,2, β¦ , π
ο·
π£π β π£π+1 (π£1 dibuang, vektor lain digunakan kembali) akhir lakukan siklus akhir
Powell menunjukkan bahwa vektor-vektor π£1 yang dihasilkan dalam siklus berturut-turut saling konjugat, sehingga titik minimum dari permukaan kuadrat tercapai dalam siklus yang tepat. Dalam prakteknya, fungsi kelayakan kuadrat selama dapat didekati secara lokal oleh Persamaan (10.5), metode Powell akan berhasil. tentu saja, biasanya membutuhkan lebih dari π siklus untuk mencapai fungsi nonquadratic minimum. Perhatikan bahwa diperlukan minimalisasi untuk membuat setiap arah konjugat Gambar 10.3 (a) mengilustrasikan satu siklus metode yang khas dalam ruang desain dua dimensi (π = 2). kita mulai dengan titik π₯0 dan vektor π£1 dan π£2 . kita menemukan jarak π 1 yang meminimalkan πΉ(π₯0 + π π£1 ), menyelesaikan hingga titik π₯1 = π₯0 + π 1 π£1 . Selanjutnya, kita menentukan π 2 yang meminimalkan πΉ(π₯1 + π π£2 ), yang membawa kita ke π₯2 = π₯1 + π 2 π£2 . Arah pencarian terakhir adalah π£3 = π₯2 β π₯0 . setelah menemukan π 3 dengan meminimalkan πΉ(π₯0 + π π£3 ) kita mendapatkan π₯3 = π₯0 + π 3 π£3 , menyelesaikan siklus.
Gambar 10.3 (b) menunjukkan gerakan yang dilakukan dalam dua siklus yang dilapiskan pada peta kontur permukaan kuadrat. seperti yang dijelaskan sebelumnya, siklus pertama dimulai pada titik π0 dan berakhir pada π3 . siklus kedua membawa kita ke π6 , yang merupakan titik polinomial. arah π0 π3 dan π3 π6 saling konjugasi. Metode Powell memang memiliki cacat besar yang harus diperbaiki-jika πΉ(π₯) bukan kuadrat, algoritma cenderung menghasilkan arah pencarian yang secara bertahap menjadi bergantung secara linier, sehingga merusak kemajuan menuju minimum. sumber masalahnya adalah pembuangan π£1 secara otomatis pada akhir setiap siklus. Telah disarankan bahwa lebih baik untuk membuang arah yang menghasilkan penurunan πΉ(π₯) terbesar, kebijakan yang kita adopsi. Tampaknya berlawanan dengan intuisi untuk membuang arah terbaik, tetapi kemungkinan akan dekat dengan arah yang ditambahkan pada siklus berikutnya, sehingga berkontribusi pada ketergantungan linear. sebagai akibat dari perubahan, arah pencarian
berhenti menjadi saling konjugat, sehingga bentuk kuadrat tidak diminimalkan dalam siklus lagi. Ini bukan kerugian yang signifikan karena dalam prakteknya πΉ(π₯) jarang kuadratik pula. Powell menyarankan beberapa perbaikan lain untuk mempercepat konvergensi. karena ini mempersulit pembukuan secara signifikan, kami tidak mengimplementasikannya. Algoritma untuk metode Powell tercantum di bawah ini. Ini menggunakan dua aturan: df berisi penurunan fungsi yang sesuai dalam langkah pertama π dari siklus, dan matriks u menyimpan vektor arah yang sesuai π£π (satu vektor per kolom) Function [xMin, fMin, nCyc]=powell(h,tol) %Powellβs method for minimizing f(x1,x2,β¦,xn) %USAGE: [xMin, fMin, nCyc]=powell(h,tol) %INPUT: %h=initial search increment (default=0.1) %tol=error tolerance (default=1.0e-6) %GLOBALS (mus be declared GLOBAL in calling program) %X=starting point %FUNC=handle of function that returns f %OUTPUT: %xMin=minimum point %fMin=minimum value of f %nCyc=number of cycles to convergence Global X FUNC V If nargin>xMin= 1.000 1.000 fMin= 1.0072e-024 numCycles= 12
Contoh 10.4 Gunakan powell untuk menentukan jarak terkecil dari titik (5,8) ke kurva π₯π¦ = 5 Solusi Ini adalah masalah optimisasi yang dibatasi: minimalkan πΉ(π₯, π¦) = (π₯ β 5)2 + (π¦ β 8)2 (kuadrat jarak) yang bergantung pada batasan kesetaraan π₯π¦ β 5 = 0. Program berikut menggunakan metode Powell dengan fungsi penalti: %Example 10.4 (Powellβs method of minimization) Global X FUNC FUNC=@fex10_4; X=[1.0;5.0]; [xMin,fMin,nCyc]=powell; fprintf(βIntersection point=%8.5f %8.5f\nβ, X(1), X(2)) xy=X(1)*X(2); fprintf(βConstraint x*y=%8.5f\nβ, xy) dist=sqrt((X(1)-5.0)^2+(X(2)-8.0)^2); fprintf(βDistance=%8.5f\nβ, dist) fprintf(βNumber of cycles=%2.0fβ, nCyc)
Penalti dimasukkan dalam M-file dari fungsi yang harus diminimalkan: function y=fex10_4(X) %Function used in Example 10.4 lam=1.0; %Penalty multiplier c=X(1)*X(2)-5.0; %Constraint equation distSq=(X(1)-5.0)^2+(X(2)-8.0)^2; y=distSq+lam*c^2;
Seperti disebutkan sebelumnya, nilai fungsi penalti pengganda π (disebut lam dalam program) dapat memiliki efek mendalam pada hasil. Kita memilih π = 1 (seperti yang ditunjukkan dalam daftar fex10_4) dengan hasil sebagai berikut: >>Intersection point= 0.73307 7.58776 Constraint x*y=5.56234
Distance=4.28680 Number of cycles=7
Nilai kecil π favored kecepatan konvergensi atas akurasi. Karena pelanggaran kendala π₯π¦ = 5 jelas tidak dapat diterima, kami menjalankan program lagi dengan π = 10000 dan mengubah titik awal ke (0,73307, 7,58776), titik akhir dari run pertama. Hasil yang ditunjukkan di bawah sekarang dapat diterima. >>Intersection point= 0.65561 7.62654 Constraint x*y=5.00006 Distance=4.36041 Number of cycles=4
Bisakah kita menggunakan π = 10000 di run pertama? Dalam hal ini kita akan beruntung dan mendapatkan minimum dalam 17 siklus. Oleh karena itu, kami hanya menyimpan enam siklus dengan menggunakan dua kali run. Namun, besar π sering menyebabkan algoritma menggantung, sehingga biasanya bijaksana untuk memulai dengan π yang kecil.