Mahardhika, LizaTridiana (2012) Kombinasi Multi-Population Agent Algoritma Genetika dan Modifikasi BFGS untuk Optimasi Fungsi Nonlinier. Magister thesis, Universitas Brawijaya.
Abstract
Multi -population agent algoritma genetika merupakan salah satu bentuk modifikasi algoritma genetika yang dapat mengeksplorasi dan mengeksploitasi populasi yang ada agar keanekaragaman tetap terjaga dengan waktu komputasi yang lebih singkat. Modifikasi metode BFGS ( Broyden-Fletcher-Goldfard-Shanno ) yang diperkenalkan oleh Wei dkk terjadi pada persamaan Newton B k+1 s K = y k menjadi B k+1 s k = y* k , di mana y k adalah beda antara gradien pada dua iterasi terakhir sedangkan y* k adalah jumlahan dari dan A k s k di mana A k adalah matriks. Modifikasi BFGS dibuat agar metode BFGS bisa mencapai kondisi konvergen untuk semua line search. Kemudian Liu dkk membuktikan bahwa modifikasi yang diperkenalkan oleh Wei dkk bisa mencapai kondisi konvergen tanpa menggunakan line search. Kombinasi m ulti-population agent algoritma genetika dan modifikasi BFGS merupakan metode optimasi yang menggabungkan metode optimasi global dan optimasi lokal. Proses penggabungannya menggunakan post hybridization, di mana solusi terbaik m ulti-population agent algoritma genetika yang merupakan metode optimasi global digunakan sebagai nilai awal metode optimasi lokal yaitu modifikasi BFGS. Tujuan penggabungan tersebut adalah untuk mempercepat konvergensi menuju solusi optimal . Dengan menggunakan asumsi bahwa fungsi tujuan yang berdomain himpunan kompak merupakan fungsi Lipschitz, kontinu seragam dan memiliki turunan kedua yang kontinu Holder dan definit positif, Liu dkk membuktikan bahwa modifikasi BFGS dapat mencapai kondisi konvergen global dan superlinier tanpa menggunakan line search . Dengan mengikuti langkah-langkah pembuktian yang diberikan Liu dkk tersebut, dapat dibuktikan bahwa kombinasi multi-population agent algoritma genetika dan modifikasi BFGS juga akan konvergen menuju solusi optimal. H asil implementasi program menggunakan beberapa fungsi uji yang merupakan fungsi nonlinear tanpa kendala dan dapat diturunkan sampai turunan kedua menunjukkan bahwa kombinasi multi-population agent algoritma genetika dan modifikasi BFGS memberikan hasil yang sangat mendekati solusi eksak yaitu dengan rata-rata error ε ≤ 10 -15 dan waktu komputasi yang berbeda-beda, tergantung pada jenis fungsi uji dan banyaknya variabel.
English Abstract
The multi - population agent genetic algorithm is one of modified genetic algorithm that can explore and exploit the existing population in order to maintain the diversity in a shorter computing time . The modifications of BFGS method ( Broyden - Fletcher - Goldfard-Shanno), introduced by Wei et al, occurred in the Newton equation B k+1 s K = y k become B k+1 s k = y* k which y k is the difference between two gradient in the last two iteration, while y* k is the sum of y k and A k s k which A k is symmetric matrix that positive definite . BFGS modification method is used in which the methodology can achieve convergence conditions for all line search. Then Liu et al proved that the modifications introduced by Wei et al could achieve convergence conditions without using a line search. The combination of multi-population agent algorithm genetic and the modification of BFGS are an optimization method that combines the global and the local optimization method. The process of hybridization uses post hybridization which is the best solution of multi-population agent genetic algorithm which is also a global optimization method that is used as initial value of the local optimization method, that is modified BFGS method. The purpose of the hybridization is to accelerate the convergence into an optimal solution. By using several assumptions, which are the domain is compact set and the objective function is Lipschitz functions, uniformly continuous and has continuous second derivative Holder and positive definite, Liu et al have been proved that modified BFGS without line search is able to reach the global convergence and superliner condition. By following the strategy given by Liu et al, it can be proved that the combination of multi-population agent genetic algorithm and BFGS modification method will also converge to the optimal solution. The implementation program using several nonlinear test functions and twice continuously differentiable shows that the combination of multi-population agent genetic algorithm and modification of BGFS gives results very close to an exact solution which is ε ≤ 10 -15 rate of error with a different computation time, depending on the type and the size of the variable of test functions .
| Item Type: | Thesis (Magister) |
|---|---|
| Identification Number: | TES/519.62/MAH/k/041204111 |
| Subjects: | 500 Natural sciences and mathematics > 519 Probabilities and applied mathematics > 519.6 Mathematical optimization |
| Divisions: | S2/S3 > Magister Matematika, Fakultas MIPA |
| Depositing User: | Endro Setyobudi |
| Date Deposited: | 24 Jun 2013 13:09 |
| Last Modified: | 24 Jun 2013 13:09 |
| URI: | http://repository.ub.ac.id/id/eprint/157491 |
Actions (login required)
 |
View Item |